mfbt/CompactPair.h

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
   3 /* This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 /* A class holding a pair of objects that tries to conserve storage space. */
   8
   9 #ifndef mozilla_CompactPair_h
  10 #define mozilla_CompactPair_h
  11
  12 #include <type_traits>
  13 #include <tuple>
  14 #include <utility>
  15
  16 #include "mozilla/Attributes.h"
  17
  18 namespace mozilla {
  19
  20 namespace detail {
  21
  22 enum StorageType { AsBase, AsMember };
  23
  24 // Optimize storage using the Empty Base Optimization -- that empty base classes
  25 // don't take up space -- to optimize size when one or the other class is
  26 // stateless and can be used as a base class.
  27 //
  28 // The extra conditions on storage for B are necessary so that CompactPairHelper
  29 // won't ambiguously inherit from either A or B, such that one or the other base
  30 // class would be inaccessible.
  31 template <typename A, typename B,
  32           detail::StorageType =
  33               std::is_empty_v<A> ? detail::AsBase : detail::AsMember,
  34           detail::StorageType = std::is_empty_v<B> &&
  35                                         !std::is_base_of<A, B>::value &&
  36                                         !std::is_base_of<B, A>::value
  37                                     ? detail::AsBase
  38                                     : detail::AsMember>
  39 struct CompactPairHelper;
  40
  41 template <typename A, typename B>
  42 struct CompactPairHelper<A, B, AsMember, AsMember> {
  43  protected:
  44   template <typename... AArgs, std::size_t... AIndexes, typename... BArgs,
  45             std::size_t... BIndexes>
  46   constexpr CompactPairHelper(std::tuple<AArgs...>& aATuple,
  47                               std::tuple<BArgs...>& aBTuple,
  48                               std::index_sequence<AIndexes...>,
  49                               std::index_sequence<BIndexes...>)
  50       : mFirstA(std::forward<AArgs>(std::get<AIndexes>(aATuple))...),
  51         mSecondB(std::forward<BArgs>(std::get<BIndexes>(aBTuple))...) {}
  52
  53  public:
  54   template <typename AArg, typename BArg>
  55   constexpr CompactPairHelper(AArg&& aA, BArg&& aB)
  56       : mFirstA(std::forward<AArg>(aA)), mSecondB(std::forward<BArg>(aB)) {}
  57
  58   constexpr A& first() { return mFirstA; }
  59   constexpr const A& first() const { return mFirstA; }
  60   constexpr B& second() { return mSecondB; }
  61   constexpr const B& second() const { return mSecondB; }
  62
  63   void swap(CompactPairHelper& aOther) {
  64     std::swap(mFirstA, aOther.mFirstA);
  65     std::swap(mSecondB, aOther.mSecondB);
  66   }
  67
  68  private:
  69   A mFirstA;
  70   B mSecondB;
  71 };
  72
  73 template <typename A, typename B>
  74 struct CompactPairHelper<A, B, AsMember, AsBase> : private B {
  75  protected:
  76   template <typename... AArgs, std::size_t... AIndexes, typename... BArgs,
  77             std::size_t... BIndexes>
  78   constexpr CompactPairHelper(std::tuple<AArgs...>& aATuple,
  79                               std::tuple<BArgs...>& aBTuple,
  80                               std::index_sequence<AIndexes...>,
  81                               std::index_sequence<BIndexes...>)
  82       : B(std::forward<BArgs>(std::get<BIndexes>(aBTuple))...),
  83         mFirstA(std::forward<AArgs>(std::get<AIndexes>(aATuple))...) {}
  84
  85  public:
  86   template <typename AArg, typename BArg>
  87   constexpr CompactPairHelper(AArg&& aA, BArg&& aB)
  88       : B(std::forward<BArg>(aB)), mFirstA(std::forward<AArg>(aA)) {}
  89
  90   constexpr A& first() { return mFirstA; }
  91   constexpr const A& first() const { return mFirstA; }
  92   constexpr B& second() { return *this; }
  93   constexpr const B& second() const { return *this; }
  94
  95   void swap(CompactPairHelper& aOther) {
  96     std::swap(mFirstA, aOther.mFirstA);
  97     std::swap(static_cast<B&>(*this), static_cast<B&>(aOther));
  98   }
  99
 100  private:
 101   A mFirstA;
 102 };
 103
 104 template <typename A, typename B>
 105 struct CompactPairHelper<A, B, AsBase, AsMember> : private A {
 106  protected:
 107   template <typename... AArgs, std::size_t... AIndexes, typename... BArgs,
 108             std::size_t... BIndexes>
 109   constexpr CompactPairHelper(std::tuple<AArgs...>& aATuple,
 110                               std::tuple<BArgs...>& aBTuple,
 111                               std::index_sequence<AIndexes...>,
 112                               std::index_sequence<BIndexes...>)
 113       : A(std::forward<AArgs>(std::get<AIndexes>(aATuple))...),
 114         mSecondB(std::forward<BArgs>(std::get<BIndexes>(aBTuple))...) {}
 115
 116  public:
 117   template <typename AArg, typename BArg>
 118   constexpr CompactPairHelper(AArg&& aA, BArg&& aB)
 119       : A(std::forward<AArg>(aA)), mSecondB(std::forward<BArg>(aB)) {}
 120
 121   constexpr A& first() { return *this; }
 122   constexpr const A& first() const { return *this; }
 123   constexpr B& second() { return mSecondB; }
 124   constexpr const B& second() const { return mSecondB; }
 125
 126   void swap(CompactPairHelper& aOther) {
 127     std::swap(static_cast<A&>(*this), static_cast<A&>(aOther));
 128     std::swap(mSecondB, aOther.mSecondB);
 129   }
 130
 131  private:
 132   B mSecondB;
 133 };
 134
 135 template <typename A, typename B>
 136 struct CompactPairHelper<A, B, AsBase, AsBase> : private A, private B {
 137  protected:
 138   template <typename... AArgs, std::size_t... AIndexes, typename... BArgs,
 139             std::size_t... BIndexes>
 140   constexpr CompactPairHelper(std::tuple<AArgs...>& aATuple,
 141                               std::tuple<BArgs...>& aBTuple,
 142                               std::index_sequence<AIndexes...>,
 143                               std::index_sequence<BIndexes...>)
 144       : A(std::forward<AArgs>(std::get<AIndexes>(aATuple))...),
 145         B(std::forward<BArgs>(std::get<BIndexes>(aBTuple))...) {}
 146
 147  public:
 148   template <typename AArg, typename BArg>
 149   constexpr CompactPairHelper(AArg&& aA, BArg&& aB)
 150       : A(std::forward<AArg>(aA)), B(std::forward<BArg>(aB)) {}
 151
 152   constexpr A& first() { return static_cast<A&>(*this); }
 153   constexpr const A& first() const { return static_cast<A&>(*this); }
 154   constexpr B& second() { return static_cast<B&>(*this); }
 155   constexpr const B& second() const { return static_cast<B&>(*this); }
 156
 157   void swap(CompactPairHelper& aOther) {
 158     std::swap(static_cast<A&>(*this), static_cast<A&>(aOther));
 159     std::swap(static_cast<B&>(*this), static_cast<B&>(aOther));
 160   }
 161 };
 162
 163 }  // namespace detail
 164
 165 /**
 166  * CompactPair is the logical concatenation of an instance of A with an instance
 167  * B. Space is conserved when possible.  Neither A nor B may be a final class.
 168  *
 169  * In general if space conservation is not critical is preferred to use
 170  * std::pair.
 171  *
 172  * It's typically clearer to have individual A and B member fields.  Except if
 173  * you want the space-conserving qualities of CompactPair, you're probably
 174  * better off not using this!
 175  *
 176  * No guarantees are provided about the memory layout of A and B, the order of
 177  * initialization or destruction of A and B, and so on.  (This is approximately
 178  * required to optimize space usage.)  The first/second names are merely
 179  * conceptual!
 180  */
 181 template <typename A, typename B>
 182 struct CompactPair : private detail::CompactPairHelper<A, B> {
 183   typedef typename detail::CompactPairHelper<A, B> Base;
 184
 185   using Base::Base;
 186
 187   template <typename... AArgs, typename... BArgs>
 188   constexpr CompactPair(std::piecewise_construct_t, std::tuple<AArgs...> aFirst,
 189                         std::tuple<BArgs...> aSecond)
 190       : Base(aFirst, aSecond, std::index_sequence_for<AArgs...>(),
 191              std::index_sequence_for<BArgs...>()) {}
 192
 193   CompactPair(CompactPair&& aOther) = default;
 194   CompactPair(const CompactPair& aOther) = default;
 195
 196   CompactPair& operator=(CompactPair&& aOther) = default;
 197   CompactPair& operator=(const CompactPair& aOther) = default;
 198
 199   /** The A instance. */
 200   using Base::first;
 201   /** The B instance. */
 202   using Base::second;
 203
 204   /** Swap this pair with another pair. */
 205   void swap(CompactPair& aOther) { Base::swap(aOther); }
 206 };
 207
 208 /**
 209  * MakeCompactPair allows you to construct a CompactPair instance using type
 210  * inference. A call like this:
 211  *
 212  *   MakeCompactPair(Foo(), Bar())
 213  *
 214  * will return a CompactPair<Foo, Bar>.
 215  */
 216 template <typename A, typename B>
 217 CompactPair<std::remove_cv_t<std::remove_reference_t<A>>,
 218             std::remove_cv_t<std::remove_reference_t<B>>>
 219 MakeCompactPair(A&& aA, B&& aB) {
 220   return CompactPair<std::remove_cv_t<std::remove_reference_t<A>>,
 221                      std::remove_cv_t<std::remove_reference_t<B>>>(
 222       std::forward<A>(aA), std::forward<B>(aB));
 223 }
 224
 225 /**
 226  * CompactPair equality comparison
 227  */
 228 template <typename A, typename B>
 229 bool operator==(const CompactPair<A, B>& aLhs, const CompactPair<A, B>& aRhs) {
 230   return aLhs.first() == aRhs.first() && aLhs.second() == aRhs.second();
 231 }
 232
 233 }  // namespace mozilla
 234
 235 namespace std {
 236
 237 template <typename A, class B>
 238 void swap(mozilla::CompactPair<A, B>& aX, mozilla::CompactPair<A, B>& aY) {
 239   aX.swap(aY);
 240 }
 241
 242 }  // namespace std
 243
 244 #endif /* mozilla_CompactPair_h */