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