From 36d22d82aa202bb199967e9512281e9a53db42c9 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 7 Apr 2024 21:33:14 +0200 Subject: Adding upstream version 115.7.0esr. Signed-off-by: Daniel Baumann --- mfbt/SmallPointerArray.h | 270 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 270 insertions(+) create mode 100644 mfbt/SmallPointerArray.h (limited to 'mfbt/SmallPointerArray.h') 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 +#include +#include +#include + +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 +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*(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({first(), second(), aElement}); + first() = nullptr; + new (&mArray[1].mVector) std::vector*(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*(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(mArray[0].mValue); } + + T*& second() const { + MOZ_ASSERT(first(), "first() must be non-null to have a T* second pointer"); + return const_cast(mArray[1].mValue); + } + + std::vector* 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*; 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* mVector; + } mArray[2]; +}; + +} // namespace mozilla + +#endif // mozilla_SmallPointerArray_h -- cgit v1.2.3