summaryrefslogtreecommitdiffstats
path: root/mfbt/SmallPointerArray.h
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--mfbt/SmallPointerArray.h270
1 files changed, 270 insertions, 0 deletions
diff --git a/mfbt/SmallPointerArray.h b/mfbt/SmallPointerArray.h
new file mode 100644
index 0000000000..c63e3980f9
--- /dev/null
+++ b/mfbt/SmallPointerArray.h
@@ -0,0 +1,270 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=8 sts=2 et sw=2 tw=80: */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+/* A vector of pointers space-optimized for a small number of elements. */
+
+#ifndef mozilla_SmallPointerArray_h
+#define mozilla_SmallPointerArray_h
+
+#include "mozilla/Assertions.h"
+#include "mozilla/PodOperations.h"
+
+#include <algorithm>
+#include <cstddef>
+#include <new>
+#include <vector>
+
+namespace mozilla {
+
+// Array class for situations where a small number of NON-NULL elements (<= 2)
+// is expected, a large number of elements must be accommodated if necessary,
+// and the size of the class must be minimal. Typical vector implementations
+// will fulfill the first two requirements by simply adding inline storage
+// alongside the rest of their member variables. While this strategy works,
+// it brings unnecessary storage overhead for vectors with an expected small
+// number of elements. This class is intended to deal with that problem.
+//
+// This class is similar in performance to a vector class. Accessing its
+// elements when it has not grown over a size of 2 does not require an extra
+// level of indirection and will therefore be faster.
+//
+// The minimum (inline) size is 2 * sizeof(void*).
+//
+// Any modification of the array invalidates any outstanding iterators.
+template <typename T>
+class SmallPointerArray {
+ public:
+ SmallPointerArray() {
+ // List-initialization would be nicer, but it only lets you initialize the
+ // first union member.
+ mArray[0].mValue = nullptr;
+ mArray[1].mVector = nullptr;
+ }
+
+ ~SmallPointerArray() {
+ if (!first()) {
+ delete maybeVector();
+ }
+ }
+
+ SmallPointerArray(SmallPointerArray&& aOther) {
+ PodCopy(mArray, aOther.mArray, 2);
+ aOther.mArray[0].mValue = nullptr;
+ aOther.mArray[1].mVector = nullptr;
+ }
+
+ SmallPointerArray& operator=(SmallPointerArray&& aOther) {
+ std::swap(mArray, aOther.mArray);
+ return *this;
+ }
+
+ void Clear() {
+ if (first()) {
+ first() = nullptr;
+ new (&mArray[1].mValue) std::vector<T*>*(nullptr);
+ return;
+ }
+
+ delete maybeVector();
+ mArray[1].mVector = nullptr;
+ }
+
+ void AppendElement(T* aElement) {
+ // Storing nullptr as an element is not permitted, but we do check for it
+ // to avoid corruption issues in non-debug builds.
+
+ // In addition to this we assert in debug builds to point out mistakes to
+ // users of the class.
+ MOZ_ASSERT(aElement != nullptr);
+ if (aElement == nullptr) {
+ return;
+ }
+
+ if (!first()) {
+ auto* vec = maybeVector();
+ if (!vec) {
+ first() = aElement;
+ new (&mArray[1].mValue) T*(nullptr);
+ return;
+ }
+
+ vec->push_back(aElement);
+ return;
+ }
+
+ if (!second()) {
+ second() = aElement;
+ return;
+ }
+
+ auto* vec = new std::vector<T*>({first(), second(), aElement});
+ first() = nullptr;
+ new (&mArray[1].mVector) std::vector<T*>*(vec);
+ }
+
+ bool RemoveElement(T* aElement) {
+ MOZ_ASSERT(aElement != nullptr);
+ if (aElement == nullptr) {
+ return false;
+ }
+
+ if (first() == aElement) {
+ // Expected case.
+ T* maybeSecond = second();
+ first() = maybeSecond;
+ if (maybeSecond) {
+ second() = nullptr;
+ } else {
+ new (&mArray[1].mVector) std::vector<T*>*(nullptr);
+ }
+
+ return true;
+ }
+
+ if (first()) {
+ if (second() == aElement) {
+ second() = nullptr;
+ return true;
+ }
+ return false;
+ }
+
+ if (auto* vec = maybeVector()) {
+ for (auto iter = vec->begin(); iter != vec->end(); iter++) {
+ if (*iter == aElement) {
+ vec->erase(iter);
+ return true;
+ }
+ }
+ }
+ return false;
+ }
+
+ bool Contains(T* aElement) const {
+ MOZ_ASSERT(aElement != nullptr);
+ if (aElement == nullptr) {
+ return false;
+ }
+
+ if (T* v = first()) {
+ return v == aElement || second() == aElement;
+ }
+
+ if (auto* vec = maybeVector()) {
+ return std::find(vec->begin(), vec->end(), aElement) != vec->end();
+ }
+
+ return false;
+ }
+
+ size_t Length() const {
+ if (first()) {
+ return second() ? 2 : 1;
+ }
+
+ if (auto* vec = maybeVector()) {
+ return vec->size();
+ }
+
+ return 0;
+ }
+
+ bool IsEmpty() const { return Length() == 0; }
+
+ T* ElementAt(size_t aIndex) const {
+ MOZ_ASSERT(aIndex < Length());
+ if (first()) {
+ return mArray[aIndex].mValue;
+ }
+
+ auto* vec = maybeVector();
+ MOZ_ASSERT(vec, "must have backing vector if accessing an element");
+ return (*vec)[aIndex];
+ }
+
+ T* operator[](size_t aIndex) const { return ElementAt(aIndex); }
+
+ using iterator = T**;
+ using const_iterator = const T**;
+
+ // Methods for range-based for loops. Manipulation invalidates these.
+ iterator begin() { return beginInternal(); }
+ const_iterator begin() const { return beginInternal(); }
+ const_iterator cbegin() const { return begin(); }
+ iterator end() { return beginInternal() + Length(); }
+ const_iterator end() const { return beginInternal() + Length(); }
+ const_iterator cend() const { return end(); }
+
+ private:
+ T** beginInternal() const {
+ if (first()) {
+ static_assert(sizeof(T*) == sizeof(Element),
+ "pointer ops on &first() must produce adjacent "
+ "Element::mValue arms");
+ return &first();
+ }
+
+ auto* vec = maybeVector();
+ if (!vec) {
+ return &first();
+ }
+
+ if (vec->empty()) {
+ return nullptr;
+ }
+
+ return &(*vec)[0];
+ }
+
+ // Accessors for |mArray| element union arms.
+
+ T*& first() const { return const_cast<T*&>(mArray[0].mValue); }
+
+ T*& second() const {
+ MOZ_ASSERT(first(), "first() must be non-null to have a T* second pointer");
+ return const_cast<T*&>(mArray[1].mValue);
+ }
+
+ std::vector<T*>* maybeVector() const {
+ MOZ_ASSERT(!first(),
+ "function must only be called when this is either empty or has "
+ "std::vector-backed elements");
+ return mArray[1].mVector;
+ }
+
+ // In C++ active-union-arm terms:
+ //
+ // - mArray[0].mValue is always active: a possibly null T*;
+ // - if mArray[0].mValue is null, mArray[1].mVector is active: a possibly
+ // null std::vector<T*>*; if mArray[0].mValue isn't null, mArray[1].mValue
+ // is active: a possibly null T*.
+ //
+ // SmallPointerArray begins empty, with mArray[1].mVector active and null.
+ // Code that makes mArray[0].mValue non-null, i.e. assignments to first(),
+ // must placement-new mArray[1].mValue with the proper value; code that goes
+ // the opposite direction, making mArray[0].mValue null, must placement-new
+ // mArray[1].mVector with the proper value.
+ //
+ // When !mArray[0].mValue && !mArray[1].mVector, the array is empty.
+ //
+ // When mArray[0].mValue && !mArray[1].mValue, the array has size 1 and
+ // contains mArray[0].mValue.
+ //
+ // When mArray[0] && mArray[1], the array has size 2 and contains
+ // mArray[0].mValue and mArray[1].mValue.
+ //
+ // When !mArray[0].mValue && mArray[1].mVector, mArray[1].mVector contains
+ // the contents of an array of arbitrary size (even less than two if it ever
+ // contained three elements and elements were removed).
+ union Element {
+ T* mValue;
+ std::vector<T*>* mVector;
+ } mArray[2];
+};
+
+} // namespace mozilla
+
+#endif // mozilla_SmallPointerArray_h