summaryrefslogtreecommitdiffstats
path: root/mfbt/tests/TestSegmentedVector.cpp
blob: 31f9f4743246c0f05c3624626540b7161958bf96 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
/* -*- Mode: C++; tab-width: 9; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* 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/. */

// This is included first to ensure it doesn't implicitly depend on anything
// else.
#include "mozilla/SegmentedVector.h"

#include "mozilla/Alignment.h"
#include "mozilla/Assertions.h"

using mozilla::SegmentedVector;

// It would be nice if we could use the InfallibleAllocPolicy from mozalloc,
// but MFBT cannot use mozalloc.
class InfallibleAllocPolicy
{
public:
  template <typename T>
  T* pod_malloc(size_t aNumElems)
  {
    if (aNumElems & mozilla::tl::MulOverflowMask<sizeof(T)>::value) {
      MOZ_CRASH("TestSegmentedVector.cpp: overflow");
    }
    T* rv = static_cast<T*>(malloc(aNumElems * sizeof(T)));
    if (!rv) {
      MOZ_CRASH("TestSegmentedVector.cpp: out of memory");
    }
    return rv;
  }

  void free_(void* aPtr) { free(aPtr); }
};

// We want to test Append(), which is fallible and marked with
// MOZ_MUST_USE. But we're using an infallible alloc policy, and so
// don't really need to check the result. Casting to |void| works with clang
// but not GCC, so we instead use this dummy variable which works with both
// compilers.
static int gDummy;

// This tests basic segmented vector construction and iteration.
void TestBasics()
{
  // A SegmentedVector with a POD element type.
  typedef SegmentedVector<int, 1024, InfallibleAllocPolicy> MyVector;
  MyVector v;
  int i, n;

  MOZ_RELEASE_ASSERT(v.IsEmpty());

  // Add 100 elements, then check various things.
  i = 0;
  for ( ; i < 100; i++) {
    gDummy = v.Append(mozilla::Move(i));
  }
  MOZ_RELEASE_ASSERT(!v.IsEmpty());
  MOZ_RELEASE_ASSERT(v.Length() == 100);

  n = 0;
  for (auto iter = v.Iter(); !iter.Done(); iter.Next()) {
    MOZ_RELEASE_ASSERT(iter.Get() == n);
    n++;
  }
  MOZ_RELEASE_ASSERT(n == 100);

  // Add another 900 elements, then re-check.
  for ( ; i < 1000; i++) {
    v.InfallibleAppend(mozilla::Move(i));
  }
  MOZ_RELEASE_ASSERT(!v.IsEmpty());
  MOZ_RELEASE_ASSERT(v.Length() == 1000);

  n = 0;
  for (auto iter = v.Iter(); !iter.Done(); iter.Next()) {
    MOZ_RELEASE_ASSERT(iter.Get() == n);
    n++;
  }
  MOZ_RELEASE_ASSERT(n == 1000);

  // Pop off all of the elements.
  MOZ_RELEASE_ASSERT(v.Length() == 1000);
  for (int len = (int)v.Length(); len > 0; len--) {
    MOZ_RELEASE_ASSERT(v.GetLast() == len - 1);
    v.PopLast();
  }
  MOZ_RELEASE_ASSERT(v.IsEmpty());
  MOZ_RELEASE_ASSERT(v.Length() == 0);

  // Fill the vector up again to prepare for the clear.
  for (i = 0; i < 1000; i++) {
    v.InfallibleAppend(mozilla::Move(i));
  }
  MOZ_RELEASE_ASSERT(!v.IsEmpty());
  MOZ_RELEASE_ASSERT(v.Length() == 1000);

  v.Clear();
  MOZ_RELEASE_ASSERT(v.IsEmpty());
  MOZ_RELEASE_ASSERT(v.Length() == 0);

  // Fill the vector up to verify PopLastN works.
  for (i = 0; i < 1000; ++i) {
    v.InfallibleAppend(mozilla::Move(i));
  }
  MOZ_RELEASE_ASSERT(!v.IsEmpty());
  MOZ_RELEASE_ASSERT(v.Length() == 1000);

  // Verify we pop the right amount of elements.
  v.PopLastN(300);
  MOZ_RELEASE_ASSERT(v.Length() == 700);

  // Verify the contents are what we expect.
  n = 0;
  for (auto iter = v.Iter(); !iter.Done(); iter.Next()) {
    MOZ_RELEASE_ASSERT(iter.Get() == n);
    n++;
  }
  MOZ_RELEASE_ASSERT(n == 700);
}

static size_t gNumDefaultCtors;
static size_t gNumExplicitCtors;
static size_t gNumCopyCtors;
static size_t gNumMoveCtors;
static size_t gNumDtors;

struct NonPOD
{
  NonPOD()                { gNumDefaultCtors++; }
  explicit NonPOD(int x)  { gNumExplicitCtors++; }
  NonPOD(NonPOD&)         { gNumCopyCtors++; }
  NonPOD(NonPOD&&)        { gNumMoveCtors++; }
  ~NonPOD()               { gNumDtors++; }
};

// This tests how segmented vectors with non-POD elements construct and
// destruct those elements.
void TestConstructorsAndDestructors()
{
  size_t defaultCtorCalls = 0;
  size_t explicitCtorCalls = 0;
  size_t copyCtorCalls = 0;
  size_t moveCtorCalls = 0;
  size_t dtorCalls = 0;

  {
    static const size_t segmentSize = 64;

    // A SegmentedVector with a non-POD element type.
    NonPOD x(1);                          // explicit constructor called
    explicitCtorCalls++;
    SegmentedVector<NonPOD, segmentSize, InfallibleAllocPolicy> v;
                                          // default constructor called 0 times
    MOZ_RELEASE_ASSERT(v.IsEmpty());
    gDummy = v.Append(x);                 // copy constructor called
    copyCtorCalls++;
    NonPOD y(1);                          // explicit constructor called
    explicitCtorCalls++;
    gDummy = v.Append(mozilla::Move(y));  // move constructor called
    moveCtorCalls++;
    NonPOD z(1);                          // explicit constructor called
    explicitCtorCalls++;
    v.InfallibleAppend(mozilla::Move(z)); // move constructor called
    moveCtorCalls++;
    v.PopLast();                          // destructor called 1 time
    dtorCalls++;
    MOZ_RELEASE_ASSERT(gNumDtors == dtorCalls);
    v.Clear();                            // destructor called 2 times
    dtorCalls += 2;

    // Test that PopLastN() correctly calls the destructors of all the
    // elements in the segments it destroys.
    //
    // We depend on the size of NonPOD when determining how many things
    // to push onto the vector.  It would be nicer to get this information
    // from SegmentedVector itself...
    static_assert(sizeof(NonPOD) == 1, "Fix length calculations!");

    size_t nonFullLastSegmentSize = segmentSize - 1;
    for (size_t i = 0; i < nonFullLastSegmentSize; ++i) {
      gDummy = v.Append(x);     // copy constructor called
      copyCtorCalls++;
    }
    MOZ_RELEASE_ASSERT(gNumCopyCtors == copyCtorCalls);

    // Pop some of the elements.
    {
      size_t partialPopAmount = 5;
      MOZ_RELEASE_ASSERT(nonFullLastSegmentSize > partialPopAmount);
      v.PopLastN(partialPopAmount); // destructor called partialPopAmount times
      dtorCalls += partialPopAmount;
      MOZ_RELEASE_ASSERT(v.Length() == nonFullLastSegmentSize - partialPopAmount);
      MOZ_RELEASE_ASSERT(!v.IsEmpty());
      MOZ_RELEASE_ASSERT(gNumDtors == dtorCalls);
    }

    // Pop a full segment.
    {
      size_t length = v.Length();
      v.PopLastN(length);
      dtorCalls += length;
      // These two tests *are* semantically different given the underlying
      // implementation; Length sums up the sizes of the internal segments,
      // while IsEmpty looks at the sequence of internal segments.
      MOZ_RELEASE_ASSERT(v.Length() == 0);
      MOZ_RELEASE_ASSERT(v.IsEmpty());
      MOZ_RELEASE_ASSERT(gNumDtors == dtorCalls);
    }

    size_t multipleSegmentsSize = (segmentSize * 3) / 2;
    for (size_t i = 0; i < multipleSegmentsSize; ++i) {
      gDummy = v.Append(x);     // copy constructor called
      copyCtorCalls++;
    }
    MOZ_RELEASE_ASSERT(gNumCopyCtors == copyCtorCalls);

    // Pop across segment boundaries.
    {
      v.PopLastN(segmentSize);
      dtorCalls += segmentSize;
      MOZ_RELEASE_ASSERT(v.Length() == (multipleSegmentsSize - segmentSize));
      MOZ_RELEASE_ASSERT(!v.IsEmpty());
      MOZ_RELEASE_ASSERT(gNumDtors == dtorCalls);
    }

    // Clear everything here to make calculations easier.
    {
      size_t length = v.Length();
      v.Clear();
      dtorCalls += length;
      MOZ_RELEASE_ASSERT(v.IsEmpty());
      MOZ_RELEASE_ASSERT(gNumDtors == dtorCalls);
    }

    MOZ_RELEASE_ASSERT(gNumDefaultCtors  == defaultCtorCalls);
    MOZ_RELEASE_ASSERT(gNumExplicitCtors == explicitCtorCalls);
    MOZ_RELEASE_ASSERT(gNumCopyCtors     == copyCtorCalls);
    MOZ_RELEASE_ASSERT(gNumMoveCtors     == moveCtorCalls);
    MOZ_RELEASE_ASSERT(gNumDtors         == dtorCalls);
  }                                       // destructor called for x, y, z
  dtorCalls += 3;
  MOZ_RELEASE_ASSERT(gNumDtors == dtorCalls);
}

struct A { int mX; int mY; };
struct B { int mX; char mY; double mZ; };
struct C { A mA; B mB; };
struct D { char mBuf[101]; };
struct E { };

// This tests that we get the right segment capacities for specified segment
// sizes, and that the elements are aligned appropriately.
void TestSegmentCapacitiesAndAlignments()
{
  // When SegmentedVector's constructor is passed a size, it asserts that the
  // vector's segment capacity results in a segment size equal to (or very
  // close to) the passed size.
  //
  // Also, SegmentedVector has a static assertion that elements are
  // appropriately aligned.
  SegmentedVector<double, 512> v1(512);
  SegmentedVector<A, 1024> v2(1024);
  SegmentedVector<B, 999> v3(999);
  SegmentedVector<C, 10> v4(10);
  SegmentedVector<D, 1234> v5(1234);
  SegmentedVector<E> v6(4096);  // 4096 is the default segment size
  SegmentedVector<mozilla::AlignedElem<16>, 100> v7(100);
}

int main(void)
{
  TestBasics();
  TestConstructorsAndDestructors();
  TestSegmentCapacitiesAndAlignments();

  return 0;
}