1 //
2 // Copyright 2018 The ANGLE Project Authors. All rights reserved.
3 // Use of this source code is governed by a BSD-style license that can be
4 // found in the LICENSE file.
5 //
6 // FixedVector_unittest:
7 // Tests of the FastVector class
8 //
9
10 #include <gtest/gtest.h>
11
12 #include "common/FastVector.h"
13
14 namespace angle
15 {
16 // Make sure the various constructors compile and do basic checks
TEST(FastVector,Constructors)17 TEST(FastVector, Constructors)
18 {
19 FastVector<int, 5> defaultContructor;
20 EXPECT_EQ(0u, defaultContructor.size());
21
22 // Try varying initial vector sizes to test purely stack-allocated and
23 // heap-allocated vectors, and ensure they copy correctly.
24 size_t vectorSizes[] = {5, 3, 16, 32};
25
26 for (size_t i = 0; i < sizeof(vectorSizes) / sizeof(vectorSizes[0]); i++)
27 {
28 FastVector<int, 5> count(vectorSizes[i]);
29 EXPECT_EQ(vectorSizes[i], count.size());
30
31 FastVector<int, 5> countAndValue(vectorSizes[i], 2);
32 EXPECT_EQ(vectorSizes[i], countAndValue.size());
33 EXPECT_EQ(2, countAndValue[1]);
34
35 FastVector<int, 5> copy(countAndValue);
36 EXPECT_EQ(copy, countAndValue);
37
38 FastVector<int, 5> copyRValue(std::move(count));
39 EXPECT_EQ(vectorSizes[i], copyRValue.size());
40
41 FastVector<int, 5> copyIter(countAndValue.begin(), countAndValue.end());
42 EXPECT_EQ(copyIter, countAndValue);
43
44 FastVector<int, 5> copyIterEmpty(countAndValue.begin(), countAndValue.begin());
45 EXPECT_TRUE(copyIterEmpty.empty());
46
47 FastVector<int, 5> assignCopy(copyRValue);
48 EXPECT_EQ(vectorSizes[i], assignCopy.size());
49
50 FastVector<int, 5> assignRValue(std::move(assignCopy));
51 EXPECT_EQ(vectorSizes[i], assignRValue.size());
52 }
53
54 FastVector<int, 5> initializerList{1, 2, 3, 4, 5};
55 EXPECT_EQ(5u, initializerList.size());
56 EXPECT_EQ(3, initializerList[2]);
57
58 // Larger than stack-allocated vector size
59 FastVector<int, 5> initializerListHeap{1, 2, 3, 4, 5, 6, 7, 8};
60 EXPECT_EQ(8u, initializerListHeap.size());
61 EXPECT_EQ(3, initializerListHeap[2]);
62
63 FastVector<int, 5> assignmentInitializerList = {1, 2, 3, 4, 5};
64 EXPECT_EQ(5u, assignmentInitializerList.size());
65 EXPECT_EQ(3, assignmentInitializerList[2]);
66
67 // Larger than stack-allocated vector size
68 FastVector<int, 5> assignmentInitializerListLarge = {1, 2, 3, 4, 5, 6, 7, 8};
69 EXPECT_EQ(8u, assignmentInitializerListLarge.size());
70 EXPECT_EQ(3, assignmentInitializerListLarge[2]);
71 }
72
73 // Test indexing operations (at, operator[])
TEST(FastVector,Indexing)74 TEST(FastVector, Indexing)
75 {
76 FastVector<int, 5> vec = {0, 1, 2, 3, 4};
77 for (int i = 0; i < 5; ++i)
78 {
79 EXPECT_EQ(i, vec.at(i));
80 EXPECT_EQ(vec[i], vec.at(i));
81 }
82 }
83
84 // Test the push_back functions
TEST(FastVector,PushBack)85 TEST(FastVector, PushBack)
86 {
87 FastVector<int, 5> vec;
88 vec.push_back(1);
89 EXPECT_EQ(1, vec[0]);
90 vec.push_back(1);
91 vec.push_back(1);
92 vec.push_back(1);
93 vec.push_back(1);
94 EXPECT_EQ(5u, vec.size());
95 }
96
97 // Tests growing the fast vector beyond the fixed storage.
TEST(FastVector,Growth)98 TEST(FastVector, Growth)
99 {
100 constexpr size_t kSize = 4;
101 FastVector<size_t, kSize> vec;
102
103 for (size_t i = 0; i < kSize * 2; ++i)
104 {
105 vec.push_back(i);
106 }
107
108 EXPECT_EQ(kSize * 2, vec.size());
109
110 for (size_t i = kSize * 2; i > 0; --i)
111 {
112 ASSERT_EQ(vec.back(), i - 1);
113 vec.pop_back();
114 }
115
116 EXPECT_EQ(0u, vec.size());
117 }
118
119 // Test the pop_back function
TEST(FastVector,PopBack)120 TEST(FastVector, PopBack)
121 {
122 FastVector<int, 5> vec;
123 vec.push_back(1);
124 EXPECT_EQ(1, (int)vec.size());
125 vec.pop_back();
126 EXPECT_EQ(0, (int)vec.size());
127 }
128
129 // Test the back function
TEST(FastVector,Back)130 TEST(FastVector, Back)
131 {
132 FastVector<int, 5> vec;
133 vec.push_back(1);
134 vec.push_back(2);
135 EXPECT_EQ(2, vec.back());
136 }
137
138 // Test the back function
TEST(FastVector,Front)139 TEST(FastVector, Front)
140 {
141 FastVector<int, 5> vec;
142 vec.push_back(1);
143 vec.push_back(2);
144 EXPECT_EQ(1, vec.front());
145 }
146
147 // Test the sizing operations
TEST(FastVector,Size)148 TEST(FastVector, Size)
149 {
150 FastVector<int, 5> vec;
151 EXPECT_TRUE(vec.empty());
152 EXPECT_EQ(0u, vec.size());
153
154 vec.push_back(1);
155 EXPECT_FALSE(vec.empty());
156 EXPECT_EQ(1u, vec.size());
157 }
158
159 // Test clearing the vector
TEST(FastVector,Clear)160 TEST(FastVector, Clear)
161 {
162 FastVector<int, 5> vec = {0, 1, 2, 3, 4};
163 vec.clear();
164 EXPECT_TRUE(vec.empty());
165 }
166
167 // Test clearing the vector larger than the fixed size.
TEST(FastVector,ClearWithLargerThanFixedSize)168 TEST(FastVector, ClearWithLargerThanFixedSize)
169 {
170 FastVector<int, 3> vec = {0, 1, 2, 3, 4};
171 vec.clear();
172 EXPECT_TRUE(vec.empty());
173 }
174
175 // Test resizing the vector
TEST(FastVector,Resize)176 TEST(FastVector, Resize)
177 {
178 FastVector<int, 5> vec;
179 vec.resize(5u, 1);
180 EXPECT_EQ(5u, vec.size());
181 for (int i : vec)
182 {
183 EXPECT_EQ(1, i);
184 }
185
186 vec.resize(2u);
187 EXPECT_EQ(2u, vec.size());
188 for (int i : vec)
189 {
190 EXPECT_EQ(1, i);
191 }
192
193 // Resize to larger than minimum
194 vec.resize(10u, 2);
195 EXPECT_EQ(10u, vec.size());
196
197 for (size_t index = 0; index < 2u; ++index)
198 {
199 EXPECT_EQ(1, vec[index]);
200 }
201 for (size_t index = 2u; index < 10u; ++index)
202 {
203 EXPECT_EQ(2, vec[index]);
204 }
205
206 // Resize back to smaller
207 vec.resize(2u, 2);
208 EXPECT_EQ(2u, vec.size());
209 }
210
211 // Test iterating over the vector
TEST(FastVector,Iteration)212 TEST(FastVector, Iteration)
213 {
214 FastVector<int, 5> vec = {0, 1, 2, 3};
215
216 int vistedCount = 0;
217 for (int value : vec)
218 {
219 EXPECT_EQ(vistedCount, value);
220 vistedCount++;
221 }
222 EXPECT_EQ(4, vistedCount);
223 }
224
225 // Tests that equality comparisons work even if reserved size differs.
TEST(FastVector,EqualityWithDifferentReservedSizes)226 TEST(FastVector, EqualityWithDifferentReservedSizes)
227 {
228 FastVector<int, 3> vec1 = {1, 2, 3, 4, 5};
229 FastVector<int, 5> vec2 = {1, 2, 3, 4, 5};
230 EXPECT_EQ(vec1, vec2);
231 vec2.push_back(6);
232 EXPECT_NE(vec1, vec2);
233 }
234
235 // Tests vector operations with a non copyable type.
TEST(FastVector,NonCopyable)236 TEST(FastVector, NonCopyable)
237 {
238 struct s : angle::NonCopyable
239 {
240 s() : x(0) {}
241 s(int xin) : x(xin) {}
242 s(s &&other) : x(other.x) {}
243 s &operator=(s &&other)
244 {
245 x = other.x;
246 return *this;
247 }
248 int x;
249 };
250
251 FastVector<s, 3> vec;
252 vec.push_back(3);
253 EXPECT_EQ(3, vec[0].x);
254
255 FastVector<s, 3> copy = std::move(vec);
256 EXPECT_EQ(1u, copy.size());
257 EXPECT_EQ(3, copy[0].x);
258 }
259
260 // Basic functionality for FlatUnorderedMap
TEST(FlatUnorderedMap,BasicUsage)261 TEST(FlatUnorderedMap, BasicUsage)
262 {
263 FlatUnorderedMap<int, bool, 3> testMap;
264 EXPECT_TRUE(testMap.empty());
265 EXPECT_EQ(testMap.size(), 0u);
266
267 testMap.insert(5, true);
268 EXPECT_TRUE(testMap.contains(5));
269 EXPECT_EQ(testMap.size(), 1u);
270
271 bool value = false;
272 EXPECT_TRUE(testMap.get(5, &value));
273 EXPECT_TRUE(value);
274 EXPECT_FALSE(testMap.get(6, &value));
275
276 EXPECT_FALSE(testMap.empty());
277 testMap.clear();
278 EXPECT_TRUE(testMap.empty());
279 EXPECT_EQ(testMap.size(), 0u);
280
281 for (int i = 0; i < 10; ++i)
282 {
283 testMap.insert(i, false);
284 }
285
286 EXPECT_FALSE(testMap.empty());
287 EXPECT_EQ(testMap.size(), 10u);
288
289 for (int i = 0; i < 10; ++i)
290 {
291 EXPECT_TRUE(testMap.contains(i));
292 EXPECT_TRUE(testMap.get(i, &value));
293 EXPECT_FALSE(value);
294 }
295 }
296
297 // Basic functionality for FlatUnorderedSet
TEST(FlatUnorderedSet,BasicUsage)298 TEST(FlatUnorderedSet, BasicUsage)
299 {
300 FlatUnorderedSet<int, 3> testMap;
301 EXPECT_TRUE(testMap.empty());
302
303 testMap.insert(5);
304 EXPECT_TRUE(testMap.contains(5));
305 EXPECT_FALSE(testMap.contains(6));
306 EXPECT_FALSE(testMap.empty());
307
308 testMap.clear();
309 EXPECT_TRUE(testMap.empty());
310
311 for (int i = 0; i < 10; ++i)
312 {
313 testMap.insert(i);
314 }
315
316 for (int i = 0; i < 10; ++i)
317 {
318 EXPECT_TRUE(testMap.contains(i));
319 }
320 }
321
322 // Basic functionality for FastIntegerSet
TEST(FastIntegerSet,BasicUsage)323 TEST(FastIntegerSet, BasicUsage)
324 {
325 FastIntegerSet testMap;
326 EXPECT_TRUE(testMap.empty());
327
328 testMap.insert(5);
329 EXPECT_TRUE(testMap.contains(5));
330 EXPECT_FALSE(testMap.contains(6));
331 EXPECT_FALSE(testMap.empty());
332
333 testMap.clear();
334 EXPECT_TRUE(testMap.empty());
335
336 for (int i = 0; i < 10; ++i)
337 {
338 testMap.insert(i);
339 }
340
341 for (int i = 0; i < 10; ++i)
342 {
343 EXPECT_TRUE(testMap.contains(i));
344 }
345 }
346
347 // Basic functionality for FastIntegerMap
TEST(FastIntegerMap,BasicUsage)348 TEST(FastIntegerMap, BasicUsage)
349 {
350 using KeyValuePair = std::pair<int, std::string>;
351 std::set<KeyValuePair> entries = {KeyValuePair(17, "testing"), KeyValuePair(63, "fast"),
352 KeyValuePair(97, "integer"), KeyValuePair(256, "map")};
353
354 FastIntegerMap<std::string> testMap;
355 EXPECT_TRUE(testMap.empty());
356
357 std::string str;
358 testMap.insert(entries.begin()->first, entries.begin()->second);
359 EXPECT_TRUE(testMap.contains(entries.begin()->first));
360 EXPECT_FALSE(testMap.contains(entries.rbegin()->first));
361 EXPECT_FALSE(testMap.empty());
362 EXPECT_EQ(testMap.size(), 1u);
363 EXPECT_TRUE(testMap.get(entries.begin()->first, &str));
364 EXPECT_EQ(entries.begin()->second, str);
365 EXPECT_FALSE(testMap.get(1, &str));
366
367 testMap.clear();
368 EXPECT_TRUE(testMap.empty());
369 EXPECT_EQ(testMap.size(), 0u);
370
371 for (KeyValuePair entry : entries)
372 {
373 testMap.insert(entry.first, entry.second);
374 }
375 EXPECT_EQ(testMap.size(), 4u);
376
377 for (KeyValuePair entry : entries)
378 {
379 EXPECT_TRUE(testMap.get(entry.first, &str));
380 EXPECT_EQ(entry.second, str);
381 }
382
383 testMap.clear();
384 EXPECT_TRUE(testMap.empty());
385 EXPECT_EQ(testMap.size(), 0u);
386 }
387
388 // Basic usage tests of fast map.
TEST(FastMap,Basic)389 TEST(FastMap, Basic)
390 {
391 FastMap<int, 5> testMap;
392 EXPECT_TRUE(testMap.empty());
393
394 testMap[5] = 5;
395 EXPECT_FALSE(testMap.empty());
396
397 testMap.clear();
398 EXPECT_TRUE(testMap.empty());
399
400 for (int i = 0; i < 10; ++i)
401 {
402 testMap[i] = i;
403 }
404
405 for (int i = 0; i < 10; ++i)
406 {
407 EXPECT_TRUE(testMap[i] == i);
408 }
409 }
410 } // namespace angle
411