mfbt/SmallPointerArray.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 vector of pointers space-optimized for a small number of elements. */
   8
   9 #ifndef mozilla_SmallPointerArray_h
  10 #define mozilla_SmallPointerArray_h
  11
  12 #include "mozilla/Assertions.h"
  13 #include "mozilla/PodOperations.h"
  14
  15 #include <algorithm>
  16 #include <iterator>
  17 #include <new>
  18 #include <vector>
  19
  20 namespace mozilla {
  21
  22 // Array class for situations where a small number of NON-NULL elements (<= 2)
  23 // is expected, a large number of elements must be accommodated if necessary,
  24 // and the size of the class must be minimal. Typical vector implementations
  25 // will fulfill the first two requirements by simply adding inline storage
  26 // alongside the rest of their member variables. While this strategy works,
  27 // it brings unnecessary storage overhead for vectors with an expected small
  28 // number of elements. This class is intended to deal with that problem.
  29 //
  30 // This class is similar in performance to a vector class. Accessing its
  31 // elements when it has not grown over a size of 2 does not require an extra
  32 // level of indirection and will therefore be faster.
  33 //
  34 // The minimum (inline) size is 2 * sizeof(void*).
  35 //
  36 // Any modification of the array invalidates any outstanding iterators.
  37 template <typename T>
  38 class SmallPointerArray {
  39  public:
  40   SmallPointerArray() {
  41     // List-initialization would be nicer, but it only lets you initialize the
  42     // first union member.
  43     mArray[0].mValue = nullptr;
  44     mArray[1].mVector = nullptr;
  45   }
  46
  47   ~SmallPointerArray() {
  48     if (!first()) {
  49       delete maybeVector();
  50     }
  51   }
  52
  53   SmallPointerArray(SmallPointerArray&& aOther) {
  54     PodCopy(mArray, aOther.mArray, 2);
  55     aOther.mArray[0].mValue = nullptr;
  56     aOther.mArray[1].mVector = nullptr;
  57   }
  58
  59   SmallPointerArray& operator=(SmallPointerArray&& aOther) {
  60     std::swap(mArray, aOther.mArray);
  61     return *this;
  62   }
  63
  64   void Clear() {
  65     if (first()) {
  66       first() = nullptr;
  67       new (&mArray[1].mValue) std::vector<T*>*(nullptr);
  68       return;
  69     }
  70
  71     delete maybeVector();
  72     mArray[1].mVector = nullptr;
  73   }
  74
  75   void AppendElement(T* aElement) {
  76     // Storing nullptr as an element is not permitted, but we do check for it
  77     // to avoid corruption issues in non-debug builds.
  78
  79     // In addition to this we assert in debug builds to point out mistakes to
  80     // users of the class.
  81     MOZ_ASSERT(aElement != nullptr);
  82     if (aElement == nullptr) {
  83       return;
  84     }
  85
  86     if (!first()) {
  87       auto* vec = maybeVector();
  88       if (!vec) {
  89         first() = aElement;
  90         new (&mArray[1].mValue) T*(nullptr);
  91         return;
  92       }
  93
  94       vec->push_back(aElement);
  95       return;
  96     }
  97
  98     if (!second()) {
  99       second() = aElement;
 100       return;
 101     }
 102
 103     auto* vec = new std::vector<T*>({first(), second(), aElement});
 104     first() = nullptr;
 105     new (&mArray[1].mVector) std::vector<T*>*(vec);
 106   }
 107
 108   bool RemoveElement(T* aElement) {
 109     MOZ_ASSERT(aElement != nullptr);
 110     if (aElement == nullptr) {
 111       return false;
 112     }
 113
 114     if (first() == aElement) {
 115       // Expected case.
 116       T* maybeSecond = second();
 117       first() = maybeSecond;
 118       if (maybeSecond) {
 119         second() = nullptr;
 120       } else {
 121         new (&mArray[1].mVector) std::vector<T*>*(nullptr);
 122       }
 123
 124       return true;
 125     }
 126
 127     if (first()) {
 128       if (second() == aElement) {
 129         second() = nullptr;
 130         return true;
 131       }
 132       return false;
 133     }
 134
 135     if (auto* vec = maybeVector()) {
 136       for (auto iter = vec->begin(); iter != vec->end(); iter++) {
 137         if (*iter == aElement) {
 138           vec->erase(iter);
 139           return true;
 140         }
 141       }
 142     }
 143     return false;
 144   }
 145
 146   bool Contains(T* aElement) const {
 147     MOZ_ASSERT(aElement != nullptr);
 148     if (aElement == nullptr) {
 149       return false;
 150     }
 151
 152     if (T* v = first()) {
 153       return v == aElement || second() == aElement;
 154     }
 155
 156     if (auto* vec = maybeVector()) {
 157       return std::find(vec->begin(), vec->end(), aElement) != vec->end();
 158     }
 159
 160     return false;
 161   }
 162
 163   size_t Length() const {
 164     if (first()) {
 165       return second() ? 2 : 1;
 166     }
 167
 168     if (auto* vec = maybeVector()) {
 169       return vec->size();
 170     }
 171
 172     return 0;
 173   }
 174
 175   bool IsEmpty() const { return Length() == 0; }
 176
 177   T* ElementAt(size_t aIndex) const {
 178     MOZ_ASSERT(aIndex < Length());
 179     if (first()) {
 180       return mArray[aIndex].mValue;
 181     }
 182
 183     auto* vec = maybeVector();
 184     MOZ_ASSERT(vec, "must have backing vector if accessing an element");
 185     return (*vec)[aIndex];
 186   }
 187
 188   T* operator[](size_t aIndex) const { return ElementAt(aIndex); }
 189
 190   using iterator = T**;
 191   using const_iterator = const T**;
 192
 193   // Methods for range-based for loops. Manipulation invalidates these.
 194   iterator begin() { return beginInternal(); }
 195   const_iterator begin() const { return beginInternal(); }
 196   const_iterator cbegin() const { return begin(); }
 197   iterator end() { return beginInternal() + Length(); }
 198   const_iterator end() const { return beginInternal() + Length(); }
 199   const_iterator cend() const { return end(); }
 200
 201  private:
 202   T** beginInternal() const {
 203     if (first()) {
 204       static_assert(sizeof(T*) == sizeof(Element),
 205                     "pointer ops on &first() must produce adjacent "
 206                     "Element::mValue arms");
 207       return &first();
 208     }
 209
 210     auto* vec = maybeVector();
 211     if (!vec) {
 212       return &first();
 213     }
 214
 215     if (vec->empty()) {
 216       return nullptr;
 217     }
 218
 219     return &(*vec)[0];
 220   }
 221
 222   // Accessors for |mArray| element union arms.
 223
 224   T*& first() const { return const_cast<T*&>(mArray[0].mValue); }
 225
 226   T*& second() const {
 227     MOZ_ASSERT(first(), "first() must be non-null to have a T* second pointer");
 228     return const_cast<T*&>(mArray[1].mValue);
 229   }
 230
 231   std::vector<T*>* maybeVector() const {
 232     MOZ_ASSERT(!first(),
 233                "function must only be called when this is either empty or has "
 234                "std::vector-backed elements");
 235     return mArray[1].mVector;
 236   }
 237
 238   // In C++ active-union-arm terms:
 239   //
 240   //   - mArray[0].mValue is always active: a possibly null T*;
 241   //   - if mArray[0].mValue is null, mArray[1].mVector is active: a possibly
 242   //     null std::vector<T*>*; if mArray[0].mValue isn't null, mArray[1].mValue
 243   //     is active: a possibly null T*.
 244   //
 245   // SmallPointerArray begins empty, with mArray[1].mVector active and null.
 246   // Code that makes mArray[0].mValue non-null, i.e. assignments to first(),
 247   // must placement-new mArray[1].mValue with the proper value; code that goes
 248   // the opposite direction, making mArray[0].mValue null, must placement-new
 249   // mArray[1].mVector with the proper value.
 250   //
 251   // When !mArray[0].mValue && !mArray[1].mVector, the array is empty.
 252   //
 253   // When mArray[0].mValue && !mArray[1].mValue, the array has size 1 and
 254   // contains mArray[0].mValue.
 255   //
 256   // When mArray[0] && mArray[1], the array has size 2 and contains
 257   // mArray[0].mValue and mArray[1].mValue.
 258   //
 259   // When !mArray[0].mValue && mArray[1].mVector, mArray[1].mVector contains
 260   // the contents of an array of arbitrary size (even less than two if it ever
 261   // contained three elements and elements were removed).
 262   union Element {
 263     T* mValue;
 264     std::vector<T*>* mVector;
 265   } mArray[2];
 266 };
 267
 268 }  // namespace mozilla
 269
 270 #endif  // mozilla_SmallPointerArray_h