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 : #ifndef mozilla_SmallPointerArray_h
9 : #define mozilla_SmallPointerArray_h
10 :
11 : #include "mozilla/Assertions.h"
12 : #include <iterator>
13 : #include <vector>
14 :
15 : namespace mozilla {
16 :
17 : // Array class for situations where a small number of elements (<= 2) is
18 : // expected, a large number of elements must be accomodated if necessary,
19 : // and the size of the class must be minimal. Typical vector implementations
20 : // will fulfill the first two requirements by simply adding inline storage
21 : // alongside the rest of their member variables. While this strategy works,
22 : // it brings unnecessary storage overhead for vectors with an expected small
23 : // number of elements. This class is intended to deal with that problem.
24 : //
25 : // This class is similar in performance to a vector class. Accessing its
26 : // elements when it has not grown over a size of 2 does not require an extra
27 : // level of indirection and will therefore be faster.
28 : //
29 : // The minimum (inline) size is 2 * sizeof(void*).
30 : //
31 : // Any modification of the array invalidates any outstanding iterators.
32 : template<typename T>
33 : class SmallPointerArray
34 : {
35 : public:
36 666 : SmallPointerArray()
37 : {
38 666 : mInlineElements[0] = mInlineElements[1] = nullptr;
39 : static_assert(sizeof(SmallPointerArray<T>) == (2 * sizeof(void*)),
40 : "SmallPointerArray must compile to the size of 2 pointers");
41 : static_assert(offsetof(SmallPointerArray<T>, mArray) ==
42 : offsetof(SmallPointerArray<T>, mInlineElements) + sizeof(T*),
43 : "mArray and mInlineElements[1] are expected to overlap in memory");
44 : static_assert(offsetof(SmallPointerArray<T>, mPadding) ==
45 : offsetof(SmallPointerArray<T>, mInlineElements),
46 : "mPadding and mInlineElements[0] are expected to overlap in memory");
47 666 : }
48 126 : ~SmallPointerArray()
49 : {
50 126 : if (!mInlineElements[0] && mArray) {
51 0 : delete mArray;
52 : }
53 126 : }
54 :
55 126 : void Clear() {
56 126 : if (!mInlineElements[0] && mArray) {
57 2 : delete mArray;
58 2 : mArray = nullptr;
59 2 : return;
60 : }
61 124 : mInlineElements[0] = mInlineElements[1] = nullptr;
62 : }
63 :
64 87 : void AppendElement(T* aElement) {
65 : // Storing nullptr as an element is not permitted, but we do check for it
66 : // to avoid corruption issues in non-debug builds.
67 :
68 : // In addition to this we assert in debug builds to point out mistakes to
69 : // users of the class.
70 87 : MOZ_ASSERT(aElement != nullptr);
71 87 : if (!mInlineElements[0]) {
72 58 : if (!mArray) {
73 49 : mInlineElements[0] = aElement;
74 : // Harmless if aElement == nullptr;
75 49 : return;
76 : }
77 :
78 9 : if (!aElement) {
79 0 : return;
80 : }
81 :
82 9 : mArray->push_back(aElement);
83 9 : return;
84 : }
85 :
86 29 : if (!aElement) {
87 0 : return;
88 : }
89 :
90 29 : if (!mInlineElements[1]) {
91 18 : mInlineElements[1] = aElement;
92 18 : return;
93 : }
94 :
95 22 : mArray = new std::vector<T*>({ mInlineElements[0], mInlineElements[1], aElement });
96 11 : mInlineElements[0] = nullptr;
97 : }
98 :
99 13 : void RemoveElement(T* aElement) {
100 13 : MOZ_ASSERT(aElement != nullptr);
101 13 : if (aElement == nullptr) {
102 0 : return;
103 : }
104 :
105 13 : if (mInlineElements[0] == aElement) {
106 : // Expectected case.
107 3 : mInlineElements[0] = mInlineElements[1];
108 3 : mInlineElements[1] = nullptr;
109 3 : return;
110 : }
111 :
112 10 : if (mInlineElements[0]) {
113 0 : if (mInlineElements[1] == aElement) {
114 0 : mInlineElements[1] = nullptr;
115 : }
116 0 : return;
117 : }
118 :
119 10 : if (mArray) {
120 11 : for (auto iter = mArray->begin(); iter != mArray->end(); iter++) {
121 11 : if (*iter == aElement) {
122 10 : mArray->erase(iter);
123 10 : return;
124 : }
125 : }
126 : }
127 : }
128 :
129 19897 : size_t Length() const
130 : {
131 19897 : if (mInlineElements[0]) {
132 5878 : if (!mInlineElements[1]) {
133 3240 : return 1;
134 : }
135 2638 : return 2;
136 : }
137 :
138 14019 : if (mArray) {
139 7450 : return mArray->size();
140 : }
141 :
142 6569 : return 0;
143 : }
144 :
145 6518 : T* ElementAt(size_t aIndex) const {
146 6518 : MOZ_ASSERT(aIndex < Length());
147 6518 : if (mInlineElements[0]) {
148 2826 : return mInlineElements[aIndex];
149 : }
150 :
151 3692 : return (*mArray)[aIndex];
152 : }
153 :
154 : T* operator[](size_t aIndex) const
155 : {
156 : return ElementAt(aIndex);
157 : }
158 :
159 : typedef T** iterator;
160 : typedef const T** const_iterator;
161 :
162 : // Methods for range-based for loops. Manipulation invalidates these.
163 252 : iterator begin() {
164 252 : return beginInternal();
165 : }
166 : const_iterator begin() const {
167 : return beginInternal();
168 : }
169 : const_iterator cbegin() const { return begin(); }
170 252 : iterator end() {
171 252 : return beginInternal() + Length();
172 : }
173 : const_iterator end() const {
174 : return beginInternal() + Length();
175 : }
176 : const_iterator cend() const { return end(); }
177 :
178 : private:
179 504 : T** beginInternal() const {
180 504 : if (mInlineElements[0] || !mArray) {
181 496 : return const_cast<T**>(&mInlineElements[0]);
182 : }
183 :
184 8 : if (!mArray->size()) {
185 0 : return nullptr;
186 : }
187 :
188 8 : return &(*mArray)[0];
189 : }
190 :
191 : // mArray and mInlineElements[1] share the same area in memory.
192 : //
193 : // When !mInlineElements[0] && !mInlineElements[1] the array is empty.
194 : //
195 : // When mInlineElements[0] && !mInlineElements[1], mInlineElements[0]
196 : // contains the first element. The array is of size 1.
197 : //
198 : // When mInlineElements[0] && mInlineElements[1], mInlineElements[0]
199 : // contains the first element and mInlineElements[1] the second. The
200 : // array is of size 2.
201 : //
202 : // When !mInlineElements[0] && mArray, mArray contains the full contents
203 : // of the array and is of arbitrary size.
204 : union {
205 : T* mInlineElements[2];
206 : struct {
207 : void* mPadding;
208 : std::vector<T*>* mArray;
209 : };
210 : };
211 : };
212 :
213 : } // namespace mozilla
214 :
215 : #endif // mozilla_SmallPointerArray_h
|
