1 #include <cstdint>
2 #include <utility>
3 #include <iterator>
4 #include <algorithm>
5 #include <functional>
6 #include <type_traits>
7 #include <gtest/gtest.h>
8 #include <entt/entity/entity.hpp>
9 #include <entt/entity/sparse_set.hpp>
10 #include <entt/entity/fwd.hpp>
11 #include "throwing_allocator.hpp"
12
13 struct empty_type {};
14 struct boxed_int { int value; };
15
TEST(SparseSet,Functionalities)16 TEST(SparseSet, Functionalities) {
17 entt::sparse_set set;
18
19 set.reserve(42);
20
21 ASSERT_EQ(set.capacity(), 42u);
22 ASSERT_TRUE(set.empty());
23 ASSERT_EQ(set.size(), 0u);
24 ASSERT_EQ(std::as_const(set).begin(), std::as_const(set).end());
25 ASSERT_EQ(set.begin(), set.end());
26 ASSERT_FALSE(set.contains(entt::entity{0}));
27 ASSERT_FALSE(set.contains(entt::entity{42}));
28
29 set.reserve(0);
30
31 ASSERT_EQ(set.capacity(), 42u);
32 ASSERT_TRUE(set.empty());
33
34 ASSERT_EQ(set.emplace(entt::entity{42}), 0u);
35
36 ASSERT_FALSE(set.empty());
37 ASSERT_EQ(set.size(), 1u);
38 ASSERT_NE(std::as_const(set).begin(), std::as_const(set).end());
39 ASSERT_NE(set.begin(), set.end());
40 ASSERT_FALSE(set.contains(entt::entity{0}));
41 ASSERT_TRUE(set.contains(entt::entity{42}));
42 ASSERT_EQ(set.index(entt::entity{42}), 0u);
43 ASSERT_EQ(set.at(0u), entt::entity{42});
44 ASSERT_EQ(set.at(1u), static_cast<entt::entity>(entt::null));
45 ASSERT_EQ(set[0u], entt::entity{42});
46
47 set.erase(entt::entity{42});
48
49 ASSERT_TRUE(set.empty());
50 ASSERT_EQ(set.size(), 0u);
51 ASSERT_EQ(std::as_const(set).begin(), std::as_const(set).end());
52 ASSERT_EQ(set.begin(), set.end());
53 ASSERT_FALSE(set.contains(entt::entity{0}));
54 ASSERT_FALSE(set.contains(entt::entity{42}));
55 ASSERT_EQ(set.at(0u), static_cast<entt::entity>(entt::null));
56 ASSERT_EQ(set.at(1u), static_cast<entt::entity>(entt::null));
57
58 ASSERT_EQ(set.emplace(entt::entity{42}), 0u);
59
60 ASSERT_FALSE(set.empty());
61 ASSERT_EQ(set.index(entt::entity{42}), 0u);
62 ASSERT_EQ(set.at(0u), entt::entity{42});
63 ASSERT_EQ(set.at(1u), static_cast<entt::entity>(entt::null));
64 ASSERT_EQ(set[0u], entt::entity{42});
65
66 set.clear();
67
68 ASSERT_TRUE(set.empty());
69 ASSERT_EQ(set.size(), 0u);
70 ASSERT_EQ(std::as_const(set).begin(), std::as_const(set).end());
71 ASSERT_EQ(set.begin(), set.end());
72 ASSERT_FALSE(set.contains(entt::entity{0}));
73 ASSERT_FALSE(set.contains(entt::entity{42}));
74 }
75
TEST(SparseSet,Contains)76 TEST(SparseSet, Contains) {
77 entt::sparse_set set{entt::deletion_policy::in_place};
78
79 set.emplace(entt::entity{0});
80 set.emplace(entt::entity{3});
81 set.emplace(entt::entity{42});
82 set.emplace(entt::entity{99});
83
84 set.emplace(entt::entity{1});
85
86 ASSERT_TRUE(set.contains(entt::entity{0}));
87 ASSERT_TRUE(set.contains(entt::entity{3}));
88 ASSERT_TRUE(set.contains(entt::entity{42}));
89 ASSERT_TRUE(set.contains(entt::entity{99}));
90 ASSERT_TRUE(set.contains(entt::entity{1}));
91
92 set.erase(entt::entity{0});
93 set.erase(entt::entity{3});
94
95 set.remove(entt::entity{42});
96 set.remove(entt::entity{99});
97
98 ASSERT_FALSE(set.contains(entt::entity{0}));
99 ASSERT_FALSE(set.contains(entt::entity{3}));
100 ASSERT_FALSE(set.contains(entt::entity{42}));
101 ASSERT_FALSE(set.contains(entt::entity{99}));
102 ASSERT_TRUE(set.contains(entt::entity{1}));
103
104 ASSERT_DEATH(static_cast<void>(set.contains(entt::null)), "");
105 ASSERT_DEATH(static_cast<void>(set.contains(entt::tombstone)), "");
106 ASSERT_DEATH(static_cast<void>(set.contains(entt::tombstone | entt::entity{1u})), "");
107 ASSERT_DEATH(static_cast<void>(set.contains(entt::null | entt::entity{1u})), "");
108 }
109
TEST(SparseSet,Move)110 TEST(SparseSet, Move) {
111 entt::sparse_set set;
112 set.emplace(entt::entity{42});
113
114 ASSERT_TRUE(std::is_move_constructible_v<decltype(set)>);
115 ASSERT_TRUE(std::is_move_assignable_v<decltype(set)>);
116
117 entt::sparse_set other{std::move(set)};
118
119 ASSERT_TRUE(set.empty());
120 ASSERT_FALSE(other.empty());
121 ASSERT_EQ(set.at(0u), static_cast<entt::entity>(entt::null));
122 ASSERT_EQ(other.at(0u), entt::entity{42});
123
124 set = std::move(other);
125
126 ASSERT_FALSE(set.empty());
127 ASSERT_TRUE(other.empty());
128 ASSERT_EQ(set.at(0u), entt::entity{42});
129 ASSERT_EQ(other.at(0u), static_cast<entt::entity>(entt::null));
130
131 other = entt::sparse_set{};
132 other.emplace(entt::entity{3});
133 other = std::move(set);
134
135 ASSERT_TRUE(set.empty());
136 ASSERT_FALSE(other.empty());
137 ASSERT_EQ(set.at(0u), static_cast<entt::entity>(entt::null));
138 ASSERT_EQ(other.at(0u), entt::entity{42});
139 }
140
TEST(SparseSet,Pagination)141 TEST(SparseSet, Pagination) {
142 entt::sparse_set set;
143
144 ASSERT_EQ(set.extent(), 0u);
145
146 set.emplace(entt::entity{ENTT_SPARSE_PAGE-1u});
147
148 ASSERT_EQ(set.extent(), ENTT_SPARSE_PAGE);
149 ASSERT_TRUE(set.contains(entt::entity{ENTT_SPARSE_PAGE-1u}));
150
151 set.emplace(entt::entity{ENTT_SPARSE_PAGE});
152
153 ASSERT_EQ(set.extent(), 2 * ENTT_SPARSE_PAGE);
154 ASSERT_TRUE(set.contains(entt::entity{ENTT_SPARSE_PAGE-1u}));
155 ASSERT_TRUE(set.contains(entt::entity{ENTT_SPARSE_PAGE}));
156 ASSERT_FALSE(set.contains(entt::entity{ENTT_SPARSE_PAGE+1u}));
157
158 set.erase(entt::entity{ENTT_SPARSE_PAGE-1u});
159
160 ASSERT_EQ(set.extent(), 2 * ENTT_SPARSE_PAGE);
161 ASSERT_FALSE(set.contains(entt::entity{ENTT_SPARSE_PAGE-1u}));
162 ASSERT_TRUE(set.contains(entt::entity{ENTT_SPARSE_PAGE}));
163
164 set.shrink_to_fit();
165 set.erase(entt::entity{ENTT_SPARSE_PAGE});
166
167 ASSERT_EQ(set.extent(), 2 * ENTT_SPARSE_PAGE);
168 ASSERT_FALSE(set.contains(entt::entity{ENTT_SPARSE_PAGE-1u}));
169 ASSERT_FALSE(set.contains(entt::entity{ENTT_SPARSE_PAGE}));
170
171 set.shrink_to_fit();
172
173 ASSERT_EQ(set.extent(), 2 * ENTT_SPARSE_PAGE);
174 }
175
TEST(SparseSet,Emplace)176 TEST(SparseSet, Emplace) {
177 entt::sparse_set set{entt::deletion_policy::in_place};
178 entt::entity entities[2u];
179
180 entities[0u] = entt::entity{3};
181 entities[1u] = entt::entity{42};
182
183 ASSERT_TRUE(set.empty());
184
185 set.emplace(entities[0u]);
186 set.erase(entities[0u]);
187
188 set.emplace_back(entities[0u]);
189 set.emplace(entities[1u]);
190
191 ASSERT_DEATH(set.emplace_back(entities[1u]), "");
192 ASSERT_DEATH(set.emplace(entities[0u]), "");
193
194 ASSERT_EQ(set.at(0u), entities[1u]);
195 ASSERT_EQ(set.at(1u), entities[0u]);
196 ASSERT_EQ(set.index(entities[0u]), 1u);
197 ASSERT_EQ(set.index(entities[1u]), 0u);
198
199 set.erase(std::begin(entities), std::end(entities));
200 set.emplace(entities[1u]);
201 set.emplace_back(entities[0u]);
202
203 ASSERT_EQ(set.at(0u), entities[1u]);
204 ASSERT_EQ(set.at(1u), static_cast<entt::entity>(entt::null));
205 ASSERT_EQ(set.at(2u), entities[0u]);
206 ASSERT_EQ(set.index(entities[0u]), 2u);
207 ASSERT_EQ(set.index(entities[1u]), 0u);
208 }
209
TEST(SparseSet,EmplaceOutOfBounds)210 TEST(SparseSet, EmplaceOutOfBounds) {
211 entt::sparse_set set{entt::deletion_policy::in_place};
212 entt::entity entities[2u]{entt::entity{0}, entt::entity{ENTT_SPARSE_PAGE}};
213
214 ASSERT_EQ(set.emplace(entities[0u]), 0u);
215 ASSERT_EQ(set.extent(), ENTT_SPARSE_PAGE);
216
217 set.erase(entities[0u]);
218
219 ASSERT_EQ(set.emplace(entities[1u]), 0u);
220 ASSERT_EQ(set.extent(), 2u * ENTT_SPARSE_PAGE);
221 }
222
TEST(SparseSet,Insert)223 TEST(SparseSet, Insert) {
224 entt::sparse_set set{entt::deletion_policy::in_place};
225 entt::entity entities[2u];
226
227 entities[0u] = entt::entity{3};
228 entities[1u] = entt::entity{42};
229
230 set.emplace(entt::entity{12});
231 set.insert(std::end(entities), std::end(entities));
232 set.insert(std::begin(entities), std::end(entities));
233 set.emplace(entt::entity{24});
234
235 ASSERT_TRUE(set.contains(entities[0u]));
236 ASSERT_TRUE(set.contains(entities[1u]));
237 ASSERT_FALSE(set.contains(entt::entity{0}));
238 ASSERT_FALSE(set.contains(entt::entity{9}));
239 ASSERT_TRUE(set.contains(entt::entity{12}));
240 ASSERT_TRUE(set.contains(entt::entity{24}));
241
242 ASSERT_FALSE(set.empty());
243 ASSERT_EQ(set.size(), 4u);
244 ASSERT_EQ(set.index(entt::entity{12}), 0u);
245 ASSERT_EQ(set.index(entities[0u]), 1u);
246 ASSERT_EQ(set.index(entities[1u]), 2u);
247 ASSERT_EQ(set.index(entt::entity{24}), 3u);
248 ASSERT_EQ(set.data()[set.index(entt::entity{12})], entt::entity{12});
249 ASSERT_EQ(set.data()[set.index(entities[0u])], entities[0u]);
250 ASSERT_EQ(set.data()[set.index(entities[1u])], entities[1u]);
251 ASSERT_EQ(set.data()[set.index(entt::entity{24})], entt::entity{24});
252
253 set.erase(std::begin(entities), std::end(entities));
254 set.insert(std::rbegin(entities), std::rend(entities));
255
256 ASSERT_EQ(set.size(), 6u);
257 ASSERT_TRUE(set.at(1u) == entt::tombstone);
258 ASSERT_TRUE(set.at(2u) == entt::tombstone);
259 ASSERT_EQ(set.at(4u), entities[1u]);
260 ASSERT_EQ(set.at(5u), entities[0u]);
261 ASSERT_EQ(set.index(entities[0u]), 5u);
262 ASSERT_EQ(set.index(entities[1u]), 4u);
263 }
264
TEST(SparseSet,Erase)265 TEST(SparseSet, Erase) {
266 entt::sparse_set set;
267 entt::entity entities[3u];
268
269 entities[0u] = entt::entity{3};
270 entities[1u] = entt::entity{42};
271 entities[2u] = entt::entity{9};
272
273 ASSERT_EQ(set.policy(), entt::deletion_policy::swap_and_pop);
274 ASSERT_TRUE(set.empty());
275
276 ASSERT_DEATH(set.erase(std::begin(entities), std::end(entities)), "");
277 ASSERT_DEATH(set.erase(entities[1u]), "");
278
279 ASSERT_TRUE(set.empty());
280
281 set.insert(std::begin(entities), std::end(entities));
282 set.erase(set.begin(), set.end());
283
284 ASSERT_TRUE(set.empty());
285
286 set.insert(std::begin(entities), std::end(entities));
287 set.erase(entities, entities + 2u);
288
289 ASSERT_FALSE(set.empty());
290 ASSERT_EQ(*set.begin(), entities[2u]);
291
292 set.erase(entities[2u]);
293
294 ASSERT_DEATH(set.erase(entities[2u]), "");
295 ASSERT_TRUE(set.empty());
296
297 set.insert(std::begin(entities), std::end(entities));
298 std::swap(entities[1u], entities[2u]);
299 set.erase(entities, entities + 2u);
300
301 ASSERT_FALSE(set.empty());
302 ASSERT_EQ(*set.begin(), entities[2u]);
303 }
304
TEST(SparseSet,StableErase)305 TEST(SparseSet, StableErase) {
306 entt::sparse_set set{entt::deletion_policy::in_place};
307 entt::entity entities[3u];
308
309 entities[0u] = entt::entity{3};
310 entities[1u] = entt::entity{42};
311 entities[2u] = entt::entity{9};
312
313 ASSERT_EQ(set.policy(), entt::deletion_policy::in_place);
314 ASSERT_TRUE(set.empty());
315 ASSERT_EQ(set.size(), 0u);
316
317 ASSERT_DEATH(set.erase(std::begin(entities), std::end(entities)), "");
318 ASSERT_DEATH(set.erase(entities[1u]), "");
319
320 ASSERT_TRUE(set.empty());
321 ASSERT_EQ(set.size(), 0u);
322
323 set.insert(std::begin(entities), std::end(entities));
324 set.erase(set.begin(), set.end());
325
326 ASSERT_FALSE(set.empty());
327 ASSERT_EQ(set.size(), 3u);
328 ASSERT_TRUE(set.at(0u) == entt::tombstone);
329 ASSERT_TRUE(set.at(1u) == entt::tombstone);
330 ASSERT_TRUE(set.at(2u) == entt::tombstone);
331 ASSERT_EQ(set.slot(), 0u);
332
333 set.insert(std::begin(entities), std::end(entities));
334 set.erase(entities, entities + 2u);
335
336 ASSERT_FALSE(set.empty());
337 ASSERT_EQ(set.size(), 6u);
338 ASSERT_EQ(*set.begin(), entities[2u]);
339 ASSERT_TRUE(set.at(3u) == entt::tombstone);
340 ASSERT_TRUE(set.at(4u) == entt::tombstone);
341 ASSERT_EQ(set.slot(), 4u);
342
343 set.erase(entities[2u]);
344
345 ASSERT_DEATH(set.erase(entities[2u]), "");
346 ASSERT_FALSE(set.empty());
347 ASSERT_EQ(set.size(), 6u);
348 ASSERT_EQ(set.slot(), 5u);
349
350 set.insert(std::begin(entities), std::end(entities));
351 std::swap(entities[1u], entities[2u]);
352 set.erase(entities, entities + 2u);
353
354 ASSERT_FALSE(set.empty());
355 ASSERT_EQ(set.size(), 9u);
356 ASSERT_TRUE(set.at(6u) == entt::tombstone);
357 ASSERT_EQ(set.at(7u), entities[2u]);
358 ASSERT_EQ(*++set.begin(), entities[2u]);
359 ASSERT_TRUE(set.at(8u) == entt::tombstone);
360 ASSERT_EQ(set.slot(), 8u);
361
362 set.compact();
363
364 ASSERT_FALSE(set.empty());
365 ASSERT_EQ(set.size(), 1u);
366 ASSERT_EQ(*set.begin(), entities[2u]);
367 ASSERT_EQ(set.slot(), 1u);
368
369 set.clear();
370
371 ASSERT_EQ(set.size(), 0u);
372 ASSERT_EQ(set.slot(), 0u);
373
374 set.insert(std::begin(entities), std::end(entities));
375 set.erase(entities[2u]);
376
377 ASSERT_DEATH(set.erase(entities[2u]), "");
378 ASSERT_EQ(set.slot(), 2u);
379
380 set.erase(entities[0u]);
381 set.erase(entities[1u]);
382
383 ASSERT_DEATH(set.erase(entities, entities + 2u), "");
384 ASSERT_EQ(set.size(), 3u);
385 ASSERT_TRUE(*set.begin() == entt::tombstone);
386 ASSERT_EQ(set.slot(), 1u);
387
388 ASSERT_EQ(set.emplace(entities[0u]), 1u);
389 ASSERT_EQ(*++set.begin(), entities[0u]);
390
391 ASSERT_EQ(set.emplace(entities[1u]), 0u);
392 ASSERT_EQ(set.emplace(entities[2u]), 2u);
393 ASSERT_EQ(set.emplace(entt::entity{0}), 3u);
394
395 ASSERT_EQ(set.size(), 4u);
396 ASSERT_EQ(*set.begin(), entt::entity{0});
397 ASSERT_EQ(set.at(0u), entities[1u]);
398 ASSERT_EQ(set.at(1u), entities[0u]);
399 ASSERT_EQ(set.at(2u), entities[2u]);
400 }
401
TEST(SparseSet,Remove)402 TEST(SparseSet, Remove) {
403 entt::sparse_set set;
404 entt::entity entities[3u];
405
406 entities[0u] = entt::entity{3};
407 entities[1u] = entt::entity{42};
408 entities[2u] = entt::entity{9};
409
410 ASSERT_EQ(set.policy(), entt::deletion_policy::swap_and_pop);
411 ASSERT_TRUE(set.empty());
412
413 ASSERT_EQ(set.remove(std::begin(entities), std::end(entities)), 0u);
414 ASSERT_EQ(set.remove(entities[1u]), 0u);
415
416 ASSERT_TRUE(set.empty());
417
418 set.insert(std::begin(entities), std::end(entities));
419
420 ASSERT_EQ(set.remove(set.begin(), set.end()), 3u);
421 ASSERT_TRUE(set.empty());
422
423 set.insert(std::begin(entities), std::end(entities));
424
425 ASSERT_EQ(set.remove(entities, entities + 2u), 2u);
426 ASSERT_FALSE(set.empty());
427 ASSERT_EQ(*set.begin(), entities[2u]);
428
429 ASSERT_EQ(set.remove(entities[2u]), 1u);
430 ASSERT_EQ(set.remove(entities[2u]), 0u);
431 ASSERT_TRUE(set.empty());
432
433 set.insert(entities, entities + 2u);
434
435 ASSERT_EQ(set.remove(std::begin(entities), std::end(entities)), 2u);
436 ASSERT_TRUE(set.empty());
437
438 set.insert(std::begin(entities), std::end(entities));
439 std::swap(entities[1u], entities[2u]);
440
441 ASSERT_EQ(set.remove(entities, entities + 2u), 2u);
442 ASSERT_FALSE(set.empty());
443 ASSERT_EQ(*set.begin(), entities[2u]);
444 }
445
TEST(SparseSet,StableRemove)446 TEST(SparseSet, StableRemove) {
447 entt::sparse_set set{entt::deletion_policy::in_place};
448 entt::entity entities[3u];
449
450 entities[0u] = entt::entity{3};
451 entities[1u] = entt::entity{42};
452 entities[2u] = entt::entity{9};
453
454 ASSERT_EQ(set.policy(), entt::deletion_policy::in_place);
455 ASSERT_TRUE(set.empty());
456 ASSERT_EQ(set.size(), 0u);
457
458 ASSERT_EQ(set.remove(std::begin(entities), std::end(entities)), 0u);
459 ASSERT_EQ(set.remove(entities[1u]), 0u);
460
461 ASSERT_TRUE(set.empty());
462 ASSERT_EQ(set.size(), 0u);
463
464 set.insert(std::begin(entities), std::end(entities));
465
466 ASSERT_EQ(set.remove(set.begin(), set.end()), 3u);
467 ASSERT_FALSE(set.empty());
468 ASSERT_EQ(set.size(), 3u);
469 ASSERT_TRUE(set.at(0u) == entt::tombstone);
470 ASSERT_TRUE(set.at(1u) == entt::tombstone);
471 ASSERT_TRUE(set.at(2u) == entt::tombstone);
472 ASSERT_EQ(set.slot(), 0u);
473
474 set.insert(std::begin(entities), std::end(entities));
475
476 ASSERT_EQ(set.remove(entities, entities + 2u), 2u);
477 ASSERT_FALSE(set.empty());
478 ASSERT_EQ(set.size(), 6u);
479 ASSERT_EQ(*set.begin(), entt::entity{9});
480 ASSERT_TRUE(set.at(3u) == entt::tombstone);
481 ASSERT_TRUE(set.at(4u) == entt::tombstone);
482 ASSERT_EQ(set.slot(), 4u);
483
484 ASSERT_EQ(set.remove(entities[2u]), 1u);
485 ASSERT_EQ(set.remove(entities[2u]), 0u);
486 ASSERT_EQ(set.remove(entities[2u]), 0u);
487 ASSERT_EQ(set.remove(entities[2u]), 0u);
488 ASSERT_FALSE(set.empty());
489 ASSERT_EQ(set.size(), 6u);
490 ASSERT_TRUE(*set.begin() == entt::tombstone);
491 ASSERT_EQ(set.slot(), 5u);
492
493 set.insert(entities, entities + 2u);
494
495 ASSERT_EQ(set.remove(std::begin(entities), std::end(entities)), 2u);
496 ASSERT_FALSE(set.empty());
497 ASSERT_EQ(set.size(), 8u);
498 ASSERT_TRUE(set.at(6u) == entt::tombstone);
499 ASSERT_TRUE(set.at(7u) == entt::tombstone);
500 ASSERT_EQ(set.slot(), 7u);
501
502 set.insert(std::begin(entities), std::end(entities));
503 std::swap(entities[1u], entities[2u]);
504
505 ASSERT_EQ(set.remove(entities, entities + 2u), 2u);
506 ASSERT_FALSE(set.empty());
507 ASSERT_EQ(set.size(), 11u);
508 ASSERT_TRUE(set.at(8u) == entt::tombstone);
509 ASSERT_EQ(set.at(9u), entities[2u]);
510 ASSERT_EQ(*++set.begin(), entities[2u]);
511 ASSERT_TRUE(set.at(10u) == entt::tombstone);
512 ASSERT_EQ(set.slot(), 10u);
513
514 set.compact();
515
516 ASSERT_FALSE(set.empty());
517 ASSERT_EQ(set.size(), 1u);
518 ASSERT_EQ(*set.begin(), entities[2u]);
519 ASSERT_EQ(set.slot(), 1u);
520
521 set.clear();
522
523 ASSERT_EQ(set.size(), 0u);
524 ASSERT_EQ(set.slot(), 0u);
525
526 set.insert(std::begin(entities), std::end(entities));
527
528 ASSERT_EQ(set.remove(entities[2u]), 1u);
529 ASSERT_EQ(set.remove(entities[2u]), 0u);
530
531 ASSERT_EQ(set.remove(entities[0u]), 1u);
532 ASSERT_EQ(set.remove(entities[1u]), 1u);
533 ASSERT_EQ(set.remove(entities, entities + 2u), 0u);
534
535 ASSERT_EQ(set.size(), 3u);
536 ASSERT_TRUE(*set.begin() == entt::tombstone);
537 ASSERT_EQ(set.slot(), 1u);
538
539 ASSERT_EQ(set.emplace(entities[0u]), 1u);
540 ASSERT_EQ(*++set.begin(), entities[0u]);
541
542 ASSERT_EQ(set.emplace(entities[1u]), 0u);
543 ASSERT_EQ(set.emplace(entities[2u]), 2u);
544 ASSERT_EQ(set.emplace(entt::entity{0}), 3u);
545
546 ASSERT_EQ(set.size(), 4u);
547 ASSERT_EQ(*set.begin(), entt::entity{0});
548 ASSERT_EQ(set.at(0u), entities[1u]);
549 ASSERT_EQ(set.at(1u), entities[0u]);
550 ASSERT_EQ(set.at(2u), entities[2u]);
551 }
552
TEST(SparseSet,Compact)553 TEST(SparseSet, Compact) {
554 entt::sparse_set set{entt::deletion_policy::in_place};
555
556 ASSERT_TRUE(set.empty());
557 ASSERT_EQ(set.size(), 0u);
558
559 set.compact();
560
561 ASSERT_TRUE(set.empty());
562 ASSERT_EQ(set.size(), 0u);
563
564 set.emplace(entt::entity{0});
565 set.compact();
566
567 ASSERT_FALSE(set.empty());
568 ASSERT_EQ(set.size(), 1u);
569
570 set.emplace(entt::entity{42});
571 set.erase(entt::entity{0});
572
573 ASSERT_EQ(set.size(), 2u);
574 ASSERT_EQ(set.index(entt::entity{42}), 1u);
575
576 set.compact();
577
578 ASSERT_EQ(set.size(), 1u);
579 ASSERT_EQ(set.index(entt::entity{42}), 0u);
580
581 set.emplace(entt::entity{0});
582 set.compact();
583
584 ASSERT_EQ(set.size(), 2u);
585 ASSERT_EQ(set.index(entt::entity{42}), 0u);
586 ASSERT_EQ(set.index(entt::entity{0}), 1u);
587
588 set.erase(entt::entity{0});
589 set.erase(entt::entity{42});
590 set.compact();
591
592 ASSERT_TRUE(set.empty());
593 }
594
TEST(SparseSet,Clear)595 TEST(SparseSet, Clear) {
596 entt::sparse_set set;
597
598 set.emplace(entt::entity{3});
599 set.emplace(entt::entity{42});
600 set.emplace(entt::entity{9});
601
602 ASSERT_FALSE(set.empty());
603
604 set.clear();
605
606 ASSERT_TRUE(set.empty());
607 }
608
TEST(SparseSet,Iterator)609 TEST(SparseSet, Iterator) {
610 using iterator = typename entt::sparse_set::iterator;
611
612 entt::sparse_set set;
613 set.emplace(entt::entity{3});
614
615 iterator end{set.begin()};
616 iterator begin{};
617 begin = set.end();
618 std::swap(begin, end);
619
620 ASSERT_EQ(begin, set.begin());
621 ASSERT_EQ(end, set.end());
622 ASSERT_NE(begin, end);
623
624 ASSERT_EQ(begin++, set.begin());
625 ASSERT_EQ(begin--, set.end());
626
627 ASSERT_EQ(begin+1, set.end());
628 ASSERT_EQ(end-1, set.begin());
629
630 ASSERT_EQ(++begin, set.end());
631 ASSERT_EQ(--begin, set.begin());
632
633 ASSERT_EQ(begin += 1, set.end());
634 ASSERT_EQ(begin -= 1, set.begin());
635
636 ASSERT_EQ(begin + (end - begin), set.end());
637 ASSERT_EQ(begin - (begin - end), set.end());
638
639 ASSERT_EQ(end - (end - begin), set.begin());
640 ASSERT_EQ(end + (begin - end), set.begin());
641
642 ASSERT_EQ(begin[0u], *set.begin());
643
644 ASSERT_LT(begin, end);
645 ASSERT_LE(begin, set.begin());
646
647 ASSERT_GT(end, begin);
648 ASSERT_GE(end, set.end());
649
650 ASSERT_EQ(*begin, entt::entity{3});
651 ASSERT_EQ(*begin.operator->(), entt::entity{3});
652 }
653
TEST(SparseSet,ReverseIterator)654 TEST(SparseSet, ReverseIterator) {
655 using reverse_iterator = typename entt::sparse_set::reverse_iterator;
656
657 entt::sparse_set set;
658 set.emplace(entt::entity{3});
659
660 reverse_iterator end{set.rbegin()};
661 reverse_iterator begin{};
662 begin = set.rend();
663 std::swap(begin, end);
664
665 ASSERT_EQ(begin, set.rbegin());
666 ASSERT_EQ(end, set.rend());
667 ASSERT_NE(begin, end);
668
669 ASSERT_EQ(begin++, set.rbegin());
670 ASSERT_EQ(begin--, set.rend());
671
672 ASSERT_EQ(begin+1, set.rend());
673 ASSERT_EQ(end-1, set.rbegin());
674
675 ASSERT_EQ(++begin, set.rend());
676 ASSERT_EQ(--begin, set.rbegin());
677
678 ASSERT_EQ(begin += 1, set.rend());
679 ASSERT_EQ(begin -= 1, set.rbegin());
680
681 ASSERT_EQ(begin + (end - begin), set.rend());
682 ASSERT_EQ(begin - (begin - end), set.rend());
683
684 ASSERT_EQ(end - (end - begin), set.rbegin());
685 ASSERT_EQ(end + (begin - end), set.rbegin());
686
687 ASSERT_EQ(begin[0u], *set.rbegin());
688
689 ASSERT_LT(begin, end);
690 ASSERT_LE(begin, set.rbegin());
691
692 ASSERT_GT(end, begin);
693 ASSERT_GE(end, set.rend());
694
695 ASSERT_EQ(*begin, entt::entity{3});
696 }
697
TEST(SparseSet,Find)698 TEST(SparseSet, Find) {
699 entt::sparse_set set;
700 set.emplace(entt::entity{3});
701 set.emplace(entt::entity{42});
702 set.emplace(entt::entity{99});
703
704 ASSERT_NE(set.find(entt::entity{3}), set.end());
705 ASSERT_NE(set.find(entt::entity{42}), set.end());
706 ASSERT_NE(set.find(entt::entity{99}), set.end());
707 ASSERT_EQ(set.find(entt::entity{0}), set.end());
708
709 auto it = set.find(entt::entity{99});
710
711 ASSERT_EQ(*it, entt::entity{99});
712 ASSERT_EQ(*(++it), entt::entity{42});
713 ASSERT_EQ(*(++it), entt::entity{3});
714 ASSERT_EQ(++it, set.end());
715 ASSERT_EQ(++set.find(entt::entity{3}), set.end());
716 }
717
TEST(SparseSet,Data)718 TEST(SparseSet, Data) {
719 entt::sparse_set set;
720
721 set.emplace(entt::entity{3});
722 set.emplace(entt::entity{12});
723 set.emplace(entt::entity{42});
724
725 ASSERT_EQ(set.index(entt::entity{3}), 0u);
726 ASSERT_EQ(set.index(entt::entity{12}), 1u);
727 ASSERT_EQ(set.index(entt::entity{42}), 2u);
728
729 ASSERT_EQ(set.data()[0u], entt::entity{3});
730 ASSERT_EQ(set.data()[1u], entt::entity{12});
731 ASSERT_EQ(set.data()[2u], entt::entity{42});
732 }
733
TEST(SparseSet,SortOrdered)734 TEST(SparseSet, SortOrdered) {
735 entt::sparse_set set;
736 entt::entity entities[5u]{entt::entity{42}, entt::entity{12}, entt::entity{9}, entt::entity{7}, entt::entity{3}};
737
738 set.insert(std::begin(entities), std::end(entities));
739 set.sort(std::less{});
740
741 ASSERT_TRUE(std::equal(std::rbegin(entities), std::rend(entities), set.begin(), set.end()));
742 }
743
TEST(SparseSet,SortReverse)744 TEST(SparseSet, SortReverse) {
745 entt::sparse_set set;
746 entt::entity entities[5u]{entt::entity{3}, entt::entity{7}, entt::entity{9}, entt::entity{12}, entt::entity{42}};
747
748 set.insert(std::begin(entities), std::end(entities));
749 set.sort(std::less{});
750
751 ASSERT_TRUE(std::equal(std::begin(entities), std::end(entities), set.begin(), set.end()));
752 }
753
TEST(SparseSet,SortUnordered)754 TEST(SparseSet, SortUnordered) {
755 entt::sparse_set set;
756 entt::entity entities[5u]{entt::entity{9}, entt::entity{7}, entt::entity{3}, entt::entity{12}, entt::entity{42}};
757
758 set.insert(std::begin(entities), std::end(entities));
759 set.sort(std::less{});
760
761 auto begin = set.begin();
762 auto end = set.end();
763
764 ASSERT_EQ(*(begin++), entt::entity{3});
765 ASSERT_EQ(*(begin++), entt::entity{7});
766 ASSERT_EQ(*(begin++), entt::entity{9});
767 ASSERT_EQ(*(begin++), entt::entity{12});
768 ASSERT_EQ(*(begin++), entt::entity{42});
769 ASSERT_EQ(begin, end);
770 }
771
TEST(SparseSet,SortRange)772 TEST(SparseSet, SortRange) {
773 entt::sparse_set set;
774 entt::entity entities[5u]{entt::entity{7}, entt::entity{9}, entt::entity{3}, entt::entity{12}, entt::entity{42}};
775
776 set.insert(std::begin(entities), std::end(entities));
777 set.sort_n(0u, std::less{});
778
779 ASSERT_TRUE(std::equal(std::rbegin(entities), std::rend(entities), set.begin(), set.end()));
780
781 set.sort_n(2u, std::less{});
782
783 ASSERT_EQ(set.data()[0u], entt::entity{9});
784 ASSERT_EQ(set.data()[1u], entt::entity{7});
785 ASSERT_EQ(set.data()[2u], entt::entity{3});
786
787 set.sort_n(5u, std::less{});
788
789 auto begin = set.begin();
790 auto end = set.end();
791
792 ASSERT_EQ(*(begin++), entt::entity{3});
793 ASSERT_EQ(*(begin++), entt::entity{7});
794 ASSERT_EQ(*(begin++), entt::entity{9});
795 ASSERT_EQ(*(begin++), entt::entity{12});
796 ASSERT_EQ(*(begin++), entt::entity{42});
797 ASSERT_EQ(begin, end);
798 }
799
TEST(SparseSet,RespectDisjoint)800 TEST(SparseSet, RespectDisjoint) {
801 entt::sparse_set lhs;
802 entt::sparse_set rhs;
803
804 entt::entity lhs_entities[3u]{entt::entity{3}, entt::entity{12}, entt::entity{42}};
805 lhs.insert(std::begin(lhs_entities), std::end(lhs_entities));
806
807 ASSERT_TRUE(std::equal(std::rbegin(lhs_entities), std::rend(lhs_entities), lhs.begin(), lhs.end()));
808
809 lhs.respect(rhs);
810
811 ASSERT_TRUE(std::equal(std::rbegin(lhs_entities), std::rend(lhs_entities), lhs.begin(), lhs.end()));
812 }
813
TEST(SparseSet,RespectOverlap)814 TEST(SparseSet, RespectOverlap) {
815 entt::sparse_set lhs;
816 entt::sparse_set rhs;
817
818 entt::entity lhs_entities[3u]{entt::entity{3}, entt::entity{12}, entt::entity{42}};
819 lhs.insert(std::begin(lhs_entities), std::end(lhs_entities));
820
821 entt::entity rhs_entities[1u]{entt::entity{12}};
822 rhs.insert(std::begin(rhs_entities), std::end(rhs_entities));
823
824 ASSERT_TRUE(std::equal(std::rbegin(lhs_entities), std::rend(lhs_entities), lhs.begin(), lhs.end()));
825 ASSERT_TRUE(std::equal(std::rbegin(rhs_entities), std::rend(rhs_entities), rhs.begin(), rhs.end()));
826
827 lhs.respect(rhs);
828
829 auto begin = lhs.begin();
830 auto end = lhs.end();
831
832 ASSERT_EQ(*(begin++), entt::entity{12});
833 ASSERT_EQ(*(begin++), entt::entity{42});
834 ASSERT_EQ(*(begin++), entt::entity{3});
835 ASSERT_EQ(begin, end);
836 }
837
TEST(SparseSet,RespectOrdered)838 TEST(SparseSet, RespectOrdered) {
839 entt::sparse_set lhs;
840 entt::sparse_set rhs;
841
842 entt::entity lhs_entities[5u]{entt::entity{1}, entt::entity{2}, entt::entity{3}, entt::entity{4}, entt::entity{5}};
843 lhs.insert(std::begin(lhs_entities), std::end(lhs_entities));
844
845 entt::entity rhs_entities[6u]{entt::entity{6}, entt::entity{1}, entt::entity{2}, entt::entity{3}, entt::entity{4}, entt::entity{5}};
846 rhs.insert(std::begin(rhs_entities), std::end(rhs_entities));
847
848 ASSERT_TRUE(std::equal(std::rbegin(lhs_entities), std::rend(lhs_entities), lhs.begin(), lhs.end()));
849 ASSERT_TRUE(std::equal(std::rbegin(rhs_entities), std::rend(rhs_entities), rhs.begin(), rhs.end()));
850
851 rhs.respect(lhs);
852
853 ASSERT_TRUE(std::equal(std::rbegin(rhs_entities), std::rend(rhs_entities), rhs.begin(), rhs.end()));
854 }
855
TEST(SparseSet,RespectReverse)856 TEST(SparseSet, RespectReverse) {
857 entt::sparse_set lhs;
858 entt::sparse_set rhs;
859
860 entt::entity lhs_entities[5u]{entt::entity{1}, entt::entity{2}, entt::entity{3}, entt::entity{4}, entt::entity{5}};
861 lhs.insert(std::begin(lhs_entities), std::end(lhs_entities));
862
863 entt::entity rhs_entities[6u]{entt::entity{5}, entt::entity{4}, entt::entity{3}, entt::entity{2}, entt::entity{1}, entt::entity{6}};
864 rhs.insert(std::begin(rhs_entities), std::end(rhs_entities));
865
866 ASSERT_TRUE(std::equal(std::rbegin(lhs_entities), std::rend(lhs_entities), lhs.begin(), lhs.end()));
867 ASSERT_TRUE(std::equal(std::rbegin(rhs_entities), std::rend(rhs_entities), rhs.begin(), rhs.end()));
868
869 rhs.respect(lhs);
870
871 auto begin = rhs.begin();
872 auto end = rhs.end();
873
874 ASSERT_EQ(*(begin++), entt::entity{5});
875 ASSERT_EQ(*(begin++), entt::entity{4});
876 ASSERT_EQ(*(begin++), entt::entity{3});
877 ASSERT_EQ(*(begin++), entt::entity{2});
878 ASSERT_EQ(*(begin++), entt::entity{1});
879 ASSERT_EQ(*(begin++), entt::entity{6});
880 ASSERT_EQ(begin, end);
881 }
882
TEST(SparseSet,RespectUnordered)883 TEST(SparseSet, RespectUnordered) {
884 entt::sparse_set lhs;
885 entt::sparse_set rhs;
886
887 entt::entity lhs_entities[5u]{entt::entity{1}, entt::entity{2}, entt::entity{3}, entt::entity{4}, entt::entity{5}};
888 lhs.insert(std::begin(lhs_entities), std::end(lhs_entities));
889
890 entt::entity rhs_entities[6u]{entt::entity{3}, entt::entity{2}, entt::entity{6}, entt::entity{1}, entt::entity{4}, entt::entity{5}};
891 rhs.insert(std::begin(rhs_entities), std::end(rhs_entities));
892
893 ASSERT_TRUE(std::equal(std::rbegin(lhs_entities), std::rend(lhs_entities), lhs.begin(), lhs.end()));
894 ASSERT_TRUE(std::equal(std::rbegin(rhs_entities), std::rend(rhs_entities), rhs.begin(), rhs.end()));
895
896 rhs.respect(lhs);
897
898 auto begin = rhs.begin();
899 auto end = rhs.end();
900
901 ASSERT_EQ(*(begin++), entt::entity{5});
902 ASSERT_EQ(*(begin++), entt::entity{4});
903 ASSERT_EQ(*(begin++), entt::entity{3});
904 ASSERT_EQ(*(begin++), entt::entity{2});
905 ASSERT_EQ(*(begin++), entt::entity{1});
906 ASSERT_EQ(*(begin++), entt::entity{6});
907 ASSERT_EQ(begin, end);
908 }
909
TEST(SparseSet,CanModifyDuringIteration)910 TEST(SparseSet, CanModifyDuringIteration) {
911 entt::sparse_set set;
912 set.emplace(entt::entity{0});
913
914 ASSERT_EQ(set.capacity(), 1u);
915
916 const auto it = set.begin();
917 set.reserve(2u);
918
919 ASSERT_EQ(set.capacity(), 2u);
920
921 // this should crash with asan enabled if we break the constraint
922 const auto entity = *it;
923 (void)entity;
924 }
925
TEST(SparseSet,ThrowingAllocator)926 TEST(SparseSet, ThrowingAllocator) {
927 entt::basic_sparse_set<entt::entity, test::throwing_allocator<entt::entity>> set{};
928
929 test::throwing_allocator<entt::entity>::trigger_on_allocate = true;
930
931 // strong exception safety
932 ASSERT_THROW(set.reserve(1u), test::throwing_allocator<entt::entity>::exception_type);
933 ASSERT_EQ(set.capacity(), 0u);
934 ASSERT_EQ(set.extent(), 0u);
935
936 test::throwing_allocator<entt::entity>::trigger_on_allocate = true;
937
938 // strong exception safety
939 ASSERT_THROW(set.emplace(entt::entity{0}), test::throwing_allocator<entt::entity>::exception_type);
940 ASSERT_EQ(set.capacity(), 0u);
941 ASSERT_EQ(set.extent(), 0u);
942
943 set.emplace(entt::entity{0});
944 test::throwing_allocator<entt::entity>::trigger_on_allocate = true;
945
946 // strong exception safety
947 ASSERT_THROW(set.reserve(2u), test::throwing_allocator<entt::entity>::exception_type);
948 ASSERT_EQ(set.capacity(), 1u);
949 ASSERT_EQ(set.extent(), ENTT_SPARSE_PAGE);
950 ASSERT_TRUE(set.contains(entt::entity{0}));
951
952 entt::entity entities[2u]{entt::entity{1}, entt::entity{ENTT_SPARSE_PAGE}};
953 test::throwing_allocator<entt::entity>::trigger_after_allocate = true;
954
955 // basic exception safety
956 ASSERT_THROW(set.insert(std::begin(entities), std::end(entities)), test::throwing_allocator<entt::entity>::exception_type);
957 ASSERT_EQ(set.capacity(), 3u);
958 ASSERT_EQ(set.size(), 2u);
959 ASSERT_EQ(set.extent(), 2 * ENTT_SPARSE_PAGE);
960 ASSERT_TRUE(set.contains(entt::entity{0}));
961 ASSERT_TRUE(set.contains(entt::entity{1}));
962 ASSERT_FALSE(set.contains(entt::entity{ENTT_SPARSE_PAGE}));
963
964 set.emplace(entities[1u]);
965
966 ASSERT_TRUE(set.contains(entt::entity{ENTT_SPARSE_PAGE}));
967
968 // unnecessary but they test a bit of template machinery :)
969 set.clear();
970 set.shrink_to_fit();
971 set = decltype(set){};
972 }
973