1 /* -*- Mode: C++; tab-width: 9; 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 file,
5 * You can obtain one at http://mozilla.org/MPL/2.0/. */
6
7 // This is included first to ensure it doesn't implicitly depend on anything
8 // else.
9 #include "mozilla/SegmentedVector.h"
10
11 #include "mozilla/Alignment.h"
12 #include "mozilla/Assertions.h"
13
14 using mozilla::SegmentedVector;
15
16 // It would be nice if we could use the InfallibleAllocPolicy from mozalloc,
17 // but MFBT cannot use mozalloc.
18 class InfallibleAllocPolicy {
19 public:
20 template <typename T>
pod_malloc(size_t aNumElems)21 T* pod_malloc(size_t aNumElems) {
22 if (aNumElems & mozilla::tl::MulOverflowMask<sizeof(T)>::value) {
23 MOZ_CRASH("TestSegmentedVector.cpp: overflow");
24 }
25 T* rv = static_cast<T*>(malloc(aNumElems * sizeof(T)));
26 if (!rv) {
27 MOZ_CRASH("TestSegmentedVector.cpp: out of memory");
28 }
29 return rv;
30 }
31
32 template <typename T>
free_(T * aPtr,size_t aNumElems=0)33 void free_(T* aPtr, size_t aNumElems = 0) {
34 free(aPtr);
35 }
36 };
37
38 // We want to test Append(), which is fallible and marked with
39 // [[nodiscard]]. But we're using an infallible alloc policy, and so
40 // don't really need to check the result. Casting to |void| works with clang
41 // but not GCC, so we instead use this dummy variable which works with both
42 // compilers.
43 static int gDummy;
44
45 // This tests basic segmented vector construction and iteration.
TestBasics()46 void TestBasics() {
47 // A SegmentedVector with a POD element type.
48 typedef SegmentedVector<int, 1024, InfallibleAllocPolicy> MyVector;
49 MyVector v;
50 int i, n;
51
52 MOZ_RELEASE_ASSERT(v.IsEmpty());
53
54 // Add 100 elements, then check various things.
55 i = 0;
56 for (; i < 100; i++) {
57 gDummy = v.Append(std::move(i));
58 }
59 MOZ_RELEASE_ASSERT(!v.IsEmpty());
60 MOZ_RELEASE_ASSERT(v.Length() == 100);
61
62 n = 0;
63 for (auto iter = v.Iter(); !iter.Done(); iter.Next()) {
64 MOZ_RELEASE_ASSERT(iter.Get() == n);
65 n++;
66 }
67 MOZ_RELEASE_ASSERT(n == 100);
68
69 // Add another 900 elements, then re-check.
70 for (; i < 1000; i++) {
71 v.InfallibleAppend(std::move(i));
72 }
73 MOZ_RELEASE_ASSERT(!v.IsEmpty());
74 MOZ_RELEASE_ASSERT(v.Length() == 1000);
75
76 n = 0;
77 for (auto iter = v.Iter(); !iter.Done(); iter.Next()) {
78 MOZ_RELEASE_ASSERT(iter.Get() == n);
79 n++;
80 }
81 MOZ_RELEASE_ASSERT(n == 1000);
82
83 // Pop off all of the elements.
84 MOZ_RELEASE_ASSERT(v.Length() == 1000);
85 for (int len = (int)v.Length(); len > 0; len--) {
86 MOZ_RELEASE_ASSERT(v.GetLast() == len - 1);
87 v.PopLast();
88 }
89 MOZ_RELEASE_ASSERT(v.IsEmpty());
90 MOZ_RELEASE_ASSERT(v.Length() == 0);
91
92 // Fill the vector up again to prepare for the clear.
93 for (i = 0; i < 1000; i++) {
94 v.InfallibleAppend(std::move(i));
95 }
96 MOZ_RELEASE_ASSERT(!v.IsEmpty());
97 MOZ_RELEASE_ASSERT(v.Length() == 1000);
98
99 v.Clear();
100 MOZ_RELEASE_ASSERT(v.IsEmpty());
101 MOZ_RELEASE_ASSERT(v.Length() == 0);
102
103 // Fill the vector up to verify PopLastN works.
104 for (i = 0; i < 1000; ++i) {
105 v.InfallibleAppend(std::move(i));
106 }
107 MOZ_RELEASE_ASSERT(!v.IsEmpty());
108 MOZ_RELEASE_ASSERT(v.Length() == 1000);
109
110 // Verify we pop the right amount of elements.
111 v.PopLastN(300);
112 MOZ_RELEASE_ASSERT(v.Length() == 700);
113
114 // Verify the contents are what we expect.
115 n = 0;
116 for (auto iter = v.Iter(); !iter.Done(); iter.Next()) {
117 MOZ_RELEASE_ASSERT(iter.Get() == n);
118 n++;
119 }
120 MOZ_RELEASE_ASSERT(n == 700);
121 }
122
123 static size_t gNumDefaultCtors;
124 static size_t gNumExplicitCtors;
125 static size_t gNumCopyCtors;
126 static size_t gNumMoveCtors;
127 static size_t gNumDtors;
128
129 struct NonPOD {
NonPODNonPOD130 NonPOD() { gNumDefaultCtors++; }
NonPODNonPOD131 explicit NonPOD(int x) { gNumExplicitCtors++; }
NonPODNonPOD132 NonPOD(NonPOD&) { gNumCopyCtors++; }
NonPODNonPOD133 NonPOD(NonPOD&&) { gNumMoveCtors++; }
~NonPODNonPOD134 ~NonPOD() { gNumDtors++; }
135 };
136
137 // This tests how segmented vectors with non-POD elements construct and
138 // destruct those elements.
TestConstructorsAndDestructors()139 void TestConstructorsAndDestructors() {
140 size_t defaultCtorCalls = 0;
141 size_t explicitCtorCalls = 0;
142 size_t copyCtorCalls = 0;
143 size_t moveCtorCalls = 0;
144 size_t dtorCalls = 0;
145
146 {
147 static const size_t segmentSize = 64;
148
149 // A SegmentedVector with a non-POD element type.
150 NonPOD x(1); // explicit constructor called
151 explicitCtorCalls++;
152 SegmentedVector<NonPOD, segmentSize, InfallibleAllocPolicy> v;
153 // default constructor called 0 times
154 MOZ_RELEASE_ASSERT(v.IsEmpty());
155 gDummy = v.Append(x); // copy constructor called
156 copyCtorCalls++;
157 NonPOD y(1); // explicit constructor called
158 explicitCtorCalls++;
159 gDummy = v.Append(std::move(y)); // move constructor called
160 moveCtorCalls++;
161 NonPOD z(1); // explicit constructor called
162 explicitCtorCalls++;
163 v.InfallibleAppend(std::move(z)); // move constructor called
164 moveCtorCalls++;
165 v.PopLast(); // destructor called 1 time
166 dtorCalls++;
167 MOZ_RELEASE_ASSERT(gNumDtors == dtorCalls);
168 v.Clear(); // destructor called 2 times
169 dtorCalls += 2;
170
171 // Test that PopLastN() correctly calls the destructors of all the
172 // elements in the segments it destroys.
173 //
174 // We depend on the size of NonPOD when determining how many things
175 // to push onto the vector. It would be nicer to get this information
176 // from SegmentedVector itself...
177 static_assert(sizeof(NonPOD) == 1, "Fix length calculations!");
178
179 size_t nonFullLastSegmentSize = segmentSize - 1;
180 for (size_t i = 0; i < nonFullLastSegmentSize; ++i) {
181 gDummy = v.Append(x); // copy constructor called
182 copyCtorCalls++;
183 }
184 MOZ_RELEASE_ASSERT(gNumCopyCtors == copyCtorCalls);
185
186 // Pop some of the elements.
187 {
188 size_t partialPopAmount = 5;
189 MOZ_RELEASE_ASSERT(nonFullLastSegmentSize > partialPopAmount);
190 v.PopLastN(partialPopAmount); // destructor called partialPopAmount times
191 dtorCalls += partialPopAmount;
192 MOZ_RELEASE_ASSERT(v.Length() ==
193 nonFullLastSegmentSize - partialPopAmount);
194 MOZ_RELEASE_ASSERT(!v.IsEmpty());
195 MOZ_RELEASE_ASSERT(gNumDtors == dtorCalls);
196 }
197
198 // Pop a full segment.
199 {
200 size_t length = v.Length();
201 v.PopLastN(length);
202 dtorCalls += length;
203 // These two tests *are* semantically different given the underlying
204 // implementation; Length sums up the sizes of the internal segments,
205 // while IsEmpty looks at the sequence of internal segments.
206 MOZ_RELEASE_ASSERT(v.Length() == 0);
207 MOZ_RELEASE_ASSERT(v.IsEmpty());
208 MOZ_RELEASE_ASSERT(gNumDtors == dtorCalls);
209 }
210
211 size_t multipleSegmentsSize = (segmentSize * 3) / 2;
212 for (size_t i = 0; i < multipleSegmentsSize; ++i) {
213 gDummy = v.Append(x); // copy constructor called
214 copyCtorCalls++;
215 }
216 MOZ_RELEASE_ASSERT(gNumCopyCtors == copyCtorCalls);
217
218 // Pop across segment boundaries.
219 {
220 v.PopLastN(segmentSize);
221 dtorCalls += segmentSize;
222 MOZ_RELEASE_ASSERT(v.Length() == (multipleSegmentsSize - segmentSize));
223 MOZ_RELEASE_ASSERT(!v.IsEmpty());
224 MOZ_RELEASE_ASSERT(gNumDtors == dtorCalls);
225 }
226
227 // Clear everything here to make calculations easier.
228 {
229 size_t length = v.Length();
230 v.Clear();
231 dtorCalls += length;
232 MOZ_RELEASE_ASSERT(v.IsEmpty());
233 MOZ_RELEASE_ASSERT(gNumDtors == dtorCalls);
234 }
235
236 MOZ_RELEASE_ASSERT(gNumDefaultCtors == defaultCtorCalls);
237 MOZ_RELEASE_ASSERT(gNumExplicitCtors == explicitCtorCalls);
238 MOZ_RELEASE_ASSERT(gNumCopyCtors == copyCtorCalls);
239 MOZ_RELEASE_ASSERT(gNumMoveCtors == moveCtorCalls);
240 MOZ_RELEASE_ASSERT(gNumDtors == dtorCalls);
241 } // destructor called for x, y, z
242 dtorCalls += 3;
243 MOZ_RELEASE_ASSERT(gNumDtors == dtorCalls);
244 }
245
246 struct A {
247 int mX;
248 int mY;
249 };
250 struct B {
251 int mX;
252 char mY;
253 double mZ;
254 };
255 struct C {
256 A mA;
257 B mB;
258 };
259 struct D {
260 char mBuf[101];
261 };
262 struct E {};
263
264 // This tests that we get the right segment capacities for specified segment
265 // sizes, and that the elements are aligned appropriately.
TestSegmentCapacitiesAndAlignments()266 void TestSegmentCapacitiesAndAlignments() {
267 // When SegmentedVector's constructor is passed a size, it asserts that the
268 // vector's segment capacity results in a segment size equal to (or very
269 // close to) the passed size.
270 //
271 // Also, SegmentedVector has a static assertion that elements are
272 // appropriately aligned.
273 SegmentedVector<double, 512> v1(512);
274 SegmentedVector<A, 1024> v2(1024);
275 SegmentedVector<B, 999> v3(999);
276 SegmentedVector<C, 10> v4(10);
277 SegmentedVector<D, 1234> v5(1234);
278 SegmentedVector<E> v6(4096); // 4096 is the default segment size
279 SegmentedVector<mozilla::AlignedElem<16>, 100> v7(100);
280 }
281
TestIterator()282 void TestIterator() {
283 SegmentedVector<int, 4> v;
284
285 auto iter = v.Iter();
286 auto iterFromLast = v.IterFromLast();
287 MOZ_RELEASE_ASSERT(iter.Done());
288 MOZ_RELEASE_ASSERT(iterFromLast.Done());
289
290 gDummy = v.Append(1);
291 iter = v.Iter();
292 iterFromLast = v.IterFromLast();
293 MOZ_RELEASE_ASSERT(!iter.Done());
294 MOZ_RELEASE_ASSERT(!iterFromLast.Done());
295
296 iter.Next();
297 MOZ_RELEASE_ASSERT(iter.Done());
298 iterFromLast.Next();
299 MOZ_RELEASE_ASSERT(iterFromLast.Done());
300
301 iter = v.Iter();
302 iterFromLast = v.IterFromLast();
303 MOZ_RELEASE_ASSERT(!iter.Done());
304 MOZ_RELEASE_ASSERT(!iterFromLast.Done());
305
306 iter.Prev();
307 MOZ_RELEASE_ASSERT(iter.Done());
308 iterFromLast.Prev();
309 MOZ_RELEASE_ASSERT(iterFromLast.Done());
310
311 // Append enough entries to ensure we have at least two segments.
312 gDummy = v.Append(1);
313 gDummy = v.Append(1);
314 gDummy = v.Append(1);
315 gDummy = v.Append(1);
316
317 iter = v.Iter();
318 iterFromLast = v.IterFromLast();
319 MOZ_RELEASE_ASSERT(!iter.Done());
320 MOZ_RELEASE_ASSERT(!iterFromLast.Done());
321
322 iter.Prev();
323 MOZ_RELEASE_ASSERT(iter.Done());
324 iterFromLast.Next();
325 MOZ_RELEASE_ASSERT(iterFromLast.Done());
326
327 iter = v.Iter();
328 iterFromLast = v.IterFromLast();
329 MOZ_RELEASE_ASSERT(!iter.Done());
330 MOZ_RELEASE_ASSERT(!iterFromLast.Done());
331
332 iter.Next();
333 MOZ_RELEASE_ASSERT(!iter.Done());
334 iterFromLast.Prev();
335 MOZ_RELEASE_ASSERT(!iterFromLast.Done());
336
337 iter = v.Iter();
338 iterFromLast = v.IterFromLast();
339 int count = 0;
340 for (; !iter.Done() && !iterFromLast.Done();
341 iter.Next(), iterFromLast.Prev()) {
342 ++count;
343 }
344 MOZ_RELEASE_ASSERT(count == 5);
345
346 // Modify the vector while using the iterator.
347 iterFromLast = v.IterFromLast();
348 gDummy = v.Append(2);
349 gDummy = v.Append(3);
350 gDummy = v.Append(4);
351 iterFromLast.Next();
352 MOZ_RELEASE_ASSERT(!iterFromLast.Done());
353 MOZ_RELEASE_ASSERT(iterFromLast.Get() == 2);
354 iterFromLast.Next();
355 MOZ_RELEASE_ASSERT(iterFromLast.Get() == 3);
356 iterFromLast.Next();
357 MOZ_RELEASE_ASSERT(iterFromLast.Get() == 4);
358 iterFromLast.Next();
359 MOZ_RELEASE_ASSERT(iterFromLast.Done());
360 }
361
main(void)362 int main(void) {
363 TestBasics();
364 TestConstructorsAndDestructors();
365 TestSegmentCapacitiesAndAlignments();
366 TestIterator();
367
368 return 0;
369 }
370