Line data Source code
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 397 : SmallPointerArray()
41 : {
42 : // List-initialization would be nicer, but it only lets you initialize the
43 : // first union member.
44 397 : mArray[0].mValue = nullptr;
45 397 : mArray[1].mVector = nullptr;
46 : }
47 :
48 48 : ~SmallPointerArray()
49 : {
50 48 : if (!first()) {
51 0 : delete maybeVector();
52 : }
53 48 : }
54 :
55 48 : void Clear() {
56 0 : if (first()) {
57 0 : first() = nullptr;
58 0 : new (&mArray[1].mValue) std::vector<T*>*(nullptr);
59 : return;
60 : }
61 :
62 0 : delete maybeVector();
63 45 : mArray[1].mVector = nullptr;
64 : }
65 :
66 44 : 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 0 : MOZ_ASSERT(aElement != nullptr);
73 0 : if (aElement == nullptr) {
74 : return;
75 : }
76 :
77 44 : if (!first()) {
78 33 : auto* vec = maybeVector();
79 0 : if (!vec) {
80 33 : first() = aElement;
81 33 : new (&mArray[1].mValue) T*(nullptr);
82 : return;
83 : }
84 :
85 0 : vec->push_back(aElement);
86 0 : return;
87 : }
88 :
89 11 : if (!second()) {
90 6 : second() = aElement;
91 0 : return;
92 : }
93 :
94 20 : auto* vec = new std::vector<T*>({ first(), second(), aElement });
95 5 : first() = nullptr;
96 0 : new (&mArray[1].mVector) std::vector<T*>*(vec);
97 : }
98 :
99 2 : bool RemoveElement(T* aElement) {
100 0 : MOZ_ASSERT(aElement != nullptr);
101 0 : if (aElement == nullptr) {
102 : return false;
103 : }
104 :
105 2 : if (first() == aElement) {
106 : // Expected case.
107 2 : T* maybeSecond = second();
108 0 : first() = maybeSecond;
109 0 : if (maybeSecond) {
110 0 : second() = nullptr;
111 : } else {
112 2 : new (&mArray[1].mVector) std::vector<T*>*(nullptr);
113 : }
114 :
115 : return true;
116 : }
117 :
118 0 : if (first()) {
119 0 : if (second() == aElement) {
120 0 : second() = nullptr;
121 0 : return true;
122 : }
123 : return false;
124 : }
125 :
126 0 : if (auto* vec = maybeVector()) {
127 0 : for (auto iter = vec->begin(); iter != vec->end(); iter++) {
128 0 : if (*iter == aElement) {
129 0 : vec->erase(iter);
130 0 : 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 2302 : size_t Length() const
155 : {
156 0 : if (first()) {
157 904 : return second() ? 2 : 1;
158 : }
159 :
160 1398 : if (auto* vec = maybeVector()) {
161 853 : return vec->size();
162 : }
163 :
164 : return 0;
165 : }
166 :
167 841 : T* ElementAt(size_t aIndex) const {
168 841 : MOZ_ASSERT(aIndex < Length());
169 841 : if (first()) {
170 428 : return mArray[aIndex].mValue;
171 : }
172 :
173 0 : auto* vec = maybeVector();
174 0 : MOZ_ASSERT(vec, "must have backing vector if accessing an element");
175 0 : 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 96 : return beginInternal();
189 : }
190 : const_iterator begin() const {
191 : return beginInternal();
192 : }
193 : const_iterator cbegin() const { return begin(); }
194 96 : iterator end() {
195 96 : 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 192 : T** beginInternal() const {
204 192 : if (first()) {
205 : static_assert(sizeof(T*) == sizeof(Element),
206 : "pointer ops on &first() must produce adjacent "
207 : "Element::mValue arms");
208 0 : return &first();
209 : }
210 :
211 0 : auto* vec = maybeVector();
212 180 : if (!vec) {
213 176 : 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
|
