1 // Copyright 2011 The Chromium Authors
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #ifdef UNSAFE_BUFFERS_BUILD
6 // TODO(crbug.com/40284755): Remove this and spanify to fix the errors.
7 #pragma allow_unsafe_buffers
8 #endif
9
10 #include "base/containers/id_map.h"
11
12 #include <stdint.h>
13
14 #include <functional>
15 #include <memory>
16
17 #include "base/memory/raw_ptr.h"
18 #include "base/test/gtest_util.h"
19 #include "testing/gtest/include/gtest/gtest.h"
20
21 namespace base::test::id_map {
22 struct RepeatingKeyType {
RepeatingKeyTypebase::test::id_map::RepeatingKeyType23 explicit RepeatingKeyType(int i) : i(i) {}
24
operator ++base::test::id_map::RepeatingKeyType25 constexpr void operator++() {}
operator ++base::test::id_map::RepeatingKeyType26 constexpr RepeatingKeyType& operator++(int) { return *this; }
27
operator ==base::test::id_map::RepeatingKeyType28 constexpr bool operator==(const RepeatingKeyType& o) const {
29 return i == o.i;
30 }
operator <base::test::id_map::RepeatingKeyType31 constexpr bool operator<(const RepeatingKeyType& o) const { return i < o.i; }
32
33 int i = 0;
34 };
35 } // namespace base::test::id_map
36
37 namespace std {
38 template <>
39 struct hash<::base::test::id_map::RepeatingKeyType> {
operator ()std::hash40 size_t operator()(
41 const ::base::test::id_map::RepeatingKeyType& k) const noexcept {
42 return std::hash<int>()(k.i);
43 }
44 };
45 } // namespace std
46
47 namespace base {
48
49 namespace {
50
51 class TestObject {};
52
53 class DestructorCounter {
54 public:
DestructorCounter(int * counter)55 explicit DestructorCounter(int* counter) : counter_(counter) {}
~DestructorCounter()56 ~DestructorCounter() { ++(*counter_); }
57
58 private:
59 raw_ptr<int> counter_;
60 };
61
62 } // namespace
63
TEST(IDMapTest,Basic)64 TEST(IDMapTest, Basic) {
65 IDMap<TestObject*> map;
66 EXPECT_TRUE(map.IsEmpty());
67 EXPECT_EQ(0U, map.size());
68
69 TestObject obj1;
70 TestObject obj2;
71
72 int32_t id1 = map.Add(&obj1);
73 EXPECT_FALSE(map.IsEmpty());
74 EXPECT_EQ(1U, map.size());
75 EXPECT_EQ(&obj1, map.Lookup(id1));
76
77 int32_t id2 = map.Add(&obj2);
78 EXPECT_FALSE(map.IsEmpty());
79 EXPECT_EQ(2U, map.size());
80
81 EXPECT_EQ(&obj1, map.Lookup(id1));
82 EXPECT_EQ(&obj2, map.Lookup(id2));
83
84 map.Remove(id1);
85 EXPECT_FALSE(map.IsEmpty());
86 EXPECT_EQ(1U, map.size());
87
88 map.Remove(id2);
89 EXPECT_TRUE(map.IsEmpty());
90 EXPECT_EQ(0U, map.size());
91
92 map.AddWithID(&obj1, 1);
93 map.AddWithID(&obj2, 2);
94 EXPECT_EQ(&obj1, map.Lookup(1));
95 EXPECT_EQ(&obj2, map.Lookup(2));
96
97 EXPECT_EQ(&obj2, map.Replace(2, &obj1));
98 EXPECT_EQ(&obj1, map.Lookup(2));
99
100 EXPECT_EQ(0, map.iteration_depth());
101 }
102
TEST(IDMapTest,IteratorRemainsValidWhenRemovingCurrentElement)103 TEST(IDMapTest, IteratorRemainsValidWhenRemovingCurrentElement) {
104 IDMap<TestObject*> map;
105
106 TestObject obj1;
107 TestObject obj2;
108 TestObject obj3;
109
110 map.Add(&obj1);
111 map.Add(&obj2);
112 map.Add(&obj3);
113
114 {
115 IDMap<TestObject*>::const_iterator iter(&map);
116
117 EXPECT_EQ(1, map.iteration_depth());
118
119 while (!iter.IsAtEnd()) {
120 map.Remove(iter.GetCurrentKey());
121 iter.Advance();
122 }
123
124 // Test that while an iterator is still in scope, we get the map emptiness
125 // right (http://crbug.com/35571).
126 EXPECT_TRUE(map.IsEmpty());
127 EXPECT_EQ(0U, map.size());
128 }
129
130 EXPECT_TRUE(map.IsEmpty());
131 EXPECT_EQ(0U, map.size());
132
133 EXPECT_EQ(0, map.iteration_depth());
134 }
135
TEST(IDMapTest,IteratorRemainsValidWhenRemovingOtherElements)136 TEST(IDMapTest, IteratorRemainsValidWhenRemovingOtherElements) {
137 IDMap<TestObject*> map;
138
139 const int kCount = 5;
140 TestObject obj[kCount];
141
142 for (auto& i : obj) {
143 map.Add(&i);
144 }
145
146 // IDMap has no predictable iteration order.
147 int32_t ids_in_iteration_order[kCount];
148 const TestObject* objs_in_iteration_order[kCount];
149 int counter = 0;
150 for (IDMap<TestObject*>::const_iterator iter(&map); !iter.IsAtEnd();
151 iter.Advance()) {
152 ids_in_iteration_order[counter] = iter.GetCurrentKey();
153 objs_in_iteration_order[counter] = iter.GetCurrentValue();
154 counter++;
155 }
156
157 counter = 0;
158 for (IDMap<TestObject*>::const_iterator iter(&map); !iter.IsAtEnd();
159 iter.Advance()) {
160 EXPECT_EQ(1, map.iteration_depth());
161
162 switch (counter) {
163 case 0:
164 EXPECT_EQ(ids_in_iteration_order[0], iter.GetCurrentKey());
165 EXPECT_EQ(objs_in_iteration_order[0], iter.GetCurrentValue());
166 map.Remove(ids_in_iteration_order[1]);
167 break;
168 case 1:
169 EXPECT_EQ(ids_in_iteration_order[2], iter.GetCurrentKey());
170 EXPECT_EQ(objs_in_iteration_order[2], iter.GetCurrentValue());
171 map.Remove(ids_in_iteration_order[3]);
172 break;
173 case 2:
174 EXPECT_EQ(ids_in_iteration_order[4], iter.GetCurrentKey());
175 EXPECT_EQ(objs_in_iteration_order[4], iter.GetCurrentValue());
176 map.Remove(ids_in_iteration_order[0]);
177 break;
178 default:
179 FAIL() << "should not have that many elements";
180 }
181
182 counter++;
183 }
184
185 EXPECT_EQ(0, map.iteration_depth());
186 }
187
TEST(IDMapTest,CopyIterator)188 TEST(IDMapTest, CopyIterator) {
189 IDMap<TestObject*> map;
190
191 TestObject obj1;
192 TestObject obj2;
193 TestObject obj3;
194
195 map.Add(&obj1);
196 map.Add(&obj2);
197 map.Add(&obj3);
198
199 EXPECT_EQ(0, map.iteration_depth());
200
201 {
202 IDMap<TestObject*>::const_iterator iter1(&map);
203 EXPECT_EQ(1, map.iteration_depth());
204
205 // Make sure that copying the iterator correctly increments
206 // map's iteration depth.
207 IDMap<TestObject*>::const_iterator iter2(iter1);
208 EXPECT_EQ(2, map.iteration_depth());
209 }
210
211 // Make sure after destroying all iterators the map's iteration depth
212 // returns to initial state.
213 EXPECT_EQ(0, map.iteration_depth());
214 }
215
TEST(IDMapTest,AssignIterator)216 TEST(IDMapTest, AssignIterator) {
217 IDMap<TestObject*> map;
218
219 TestObject obj1;
220 TestObject obj2;
221 TestObject obj3;
222
223 map.Add(&obj1);
224 map.Add(&obj2);
225 map.Add(&obj3);
226
227 EXPECT_EQ(0, map.iteration_depth());
228
229 {
230 IDMap<TestObject*>::const_iterator iter1(&map);
231 EXPECT_EQ(1, map.iteration_depth());
232
233 IDMap<TestObject*>::const_iterator iter2(&map);
234 EXPECT_EQ(2, map.iteration_depth());
235
236 // Make sure that assigning the iterator correctly updates
237 // map's iteration depth (-1 for destruction, +1 for assignment).
238 EXPECT_EQ(2, map.iteration_depth());
239 }
240
241 // Make sure after destroying all iterators the map's iteration depth
242 // returns to initial state.
243 EXPECT_EQ(0, map.iteration_depth());
244 }
245
TEST(IDMapTest,IteratorRemainsValidWhenClearing)246 TEST(IDMapTest, IteratorRemainsValidWhenClearing) {
247 IDMap<TestObject*> map;
248
249 const int kCount = 5;
250 TestObject obj[kCount];
251
252 for (auto& i : obj) {
253 map.Add(&i);
254 }
255
256 // IDMap has no predictable iteration order.
257 int32_t ids_in_iteration_order[kCount];
258 const TestObject* objs_in_iteration_order[kCount];
259 int counter = 0;
260 for (IDMap<TestObject*>::const_iterator iter(&map); !iter.IsAtEnd();
261 iter.Advance()) {
262 ids_in_iteration_order[counter] = iter.GetCurrentKey();
263 objs_in_iteration_order[counter] = iter.GetCurrentValue();
264 counter++;
265 }
266
267 counter = 0;
268 for (IDMap<TestObject*>::const_iterator iter(&map); !iter.IsAtEnd();
269 iter.Advance()) {
270 switch (counter) {
271 case 0:
272 EXPECT_EQ(ids_in_iteration_order[0], iter.GetCurrentKey());
273 EXPECT_EQ(objs_in_iteration_order[0], iter.GetCurrentValue());
274 break;
275 case 1:
276 EXPECT_EQ(ids_in_iteration_order[1], iter.GetCurrentKey());
277 EXPECT_EQ(objs_in_iteration_order[1], iter.GetCurrentValue());
278 map.Clear();
279 EXPECT_TRUE(map.IsEmpty());
280 EXPECT_EQ(0U, map.size());
281 break;
282 default:
283 FAIL() << "should not have that many elements";
284 }
285 counter++;
286 }
287
288 EXPECT_TRUE(map.IsEmpty());
289 EXPECT_EQ(0U, map.size());
290 }
291
TEST(IDMapTest,OwningPointersDeletesThemOnRemove)292 TEST(IDMapTest, OwningPointersDeletesThemOnRemove) {
293 const int kCount = 3;
294
295 int external_del_count = 0;
296 DestructorCounter* external_obj[kCount];
297 int map_external_ids[kCount];
298
299 int owned_del_count = 0;
300 int map_owned_ids[kCount];
301
302 IDMap<DestructorCounter*> map_external;
303 IDMap<std::unique_ptr<DestructorCounter>> map_owned;
304
305 for (int i = 0; i < kCount; ++i) {
306 external_obj[i] = new DestructorCounter(&external_del_count);
307 map_external_ids[i] = map_external.Add(external_obj[i]);
308
309 map_owned_ids[i] =
310 map_owned.Add(std::make_unique<DestructorCounter>(&owned_del_count));
311 }
312
313 for (int i = 0; i < kCount; ++i) {
314 EXPECT_EQ(external_del_count, 0);
315 EXPECT_EQ(owned_del_count, i);
316
317 map_external.Remove(map_external_ids[i]);
318 map_owned.Remove(map_owned_ids[i]);
319 }
320
321 for (auto* i : external_obj) {
322 delete i;
323 }
324
325 EXPECT_EQ(external_del_count, kCount);
326 EXPECT_EQ(owned_del_count, kCount);
327 }
328
TEST(IDMapTest,OwningPointersDeletesThemOnClear)329 TEST(IDMapTest, OwningPointersDeletesThemOnClear) {
330 const int kCount = 3;
331
332 int external_del_count = 0;
333 DestructorCounter* external_obj[kCount];
334
335 int owned_del_count = 0;
336
337 IDMap<DestructorCounter*> map_external;
338 IDMap<std::unique_ptr<DestructorCounter>> map_owned;
339
340 for (auto*& i : external_obj) {
341 i = new DestructorCounter(&external_del_count);
342 map_external.Add(i);
343
344 map_owned.Add(std::make_unique<DestructorCounter>(&owned_del_count));
345 }
346
347 EXPECT_EQ(external_del_count, 0);
348 EXPECT_EQ(owned_del_count, 0);
349
350 map_external.Clear();
351 map_owned.Clear();
352
353 EXPECT_EQ(external_del_count, 0);
354 EXPECT_EQ(owned_del_count, kCount);
355
356 for (auto* i : external_obj) {
357 delete i;
358 }
359
360 EXPECT_EQ(external_del_count, kCount);
361 EXPECT_EQ(owned_del_count, kCount);
362 }
363
TEST(IDMapTest,OwningPointersDeletesThemOnDestruct)364 TEST(IDMapTest, OwningPointersDeletesThemOnDestruct) {
365 const int kCount = 3;
366
367 int external_del_count = 0;
368 DestructorCounter* external_obj[kCount];
369
370 int owned_del_count = 0;
371
372 {
373 IDMap<DestructorCounter*> map_external;
374 IDMap<std::unique_ptr<DestructorCounter>> map_owned;
375
376 for (auto*& i : external_obj) {
377 i = new DestructorCounter(&external_del_count);
378 map_external.Add(i);
379
380 map_owned.Add(std::make_unique<DestructorCounter>(&owned_del_count));
381 }
382 }
383
384 EXPECT_EQ(external_del_count, 0);
385
386 for (auto* i : external_obj) {
387 delete i;
388 }
389
390 EXPECT_EQ(external_del_count, kCount);
391 EXPECT_EQ(owned_del_count, kCount);
392 }
393
TEST(IDMapTest,Int64KeyType)394 TEST(IDMapTest, Int64KeyType) {
395 IDMap<TestObject*, int64_t> map;
396 TestObject obj1;
397 const int64_t kId1 = 999999999999999999;
398
399 map.AddWithID(&obj1, kId1);
400 EXPECT_EQ(&obj1, map.Lookup(kId1));
401
402 IDMap<TestObject*, int64_t>::const_iterator iter(&map);
403 ASSERT_FALSE(iter.IsAtEnd());
404 EXPECT_EQ(kId1, iter.GetCurrentKey());
405 EXPECT_EQ(&obj1, iter.GetCurrentValue());
406 iter.Advance();
407 ASSERT_TRUE(iter.IsAtEnd());
408
409 map.Remove(kId1);
410 EXPECT_TRUE(map.IsEmpty());
411 }
412
TEST(IDMapTest,RemovedValueHandling)413 TEST(IDMapTest, RemovedValueHandling) {
414 TestObject obj;
415 {
416 IDMap<TestObject*> map;
417 int key = map.Add(&obj);
418
419 IDMap<TestObject*>::iterator itr(&map);
420 // Queues the `key` for removal.
421 map.Clear();
422 // Removes nothing, already queued.
423 map.Remove(key);
424 // Can not replace a key that is not present. If it's queued for removal
425 // it's not present.
426 EXPECT_CHECK_DEATH(map.Replace(key, &obj));
427 EXPECT_FALSE(map.Lookup(key));
428 EXPECT_FALSE(itr.IsAtEnd());
429 EXPECT_FALSE(itr.GetCurrentValue());
430
431 EXPECT_TRUE(map.IsEmpty());
432 // Replaces the element that's queued for removal when `itr` is destroyed.
433 map.AddWithID(&obj, key);
434 EXPECT_EQ(1u, map.size());
435 }
436
437 {
438 using base::test::id_map::RepeatingKeyType;
439
440 IDMap<TestObject*, RepeatingKeyType> map;
441 RepeatingKeyType key = map.Add(&obj);
442 IDMap<TestObject*, RepeatingKeyType>::iterator itr(&map);
443 map.Remove(key); // Queues it for removal.
444
445 // The RepeatingKeyType's operator++ does not always return a unique id. The
446 // Add() method does not make extra assumptions about this, and can replace
447 // a queued-for-removal item just like AddWithID().
448
449 // Replaces the element that's queued for removal when `itr` is destroyed.
450 RepeatingKeyType key2 = map.Add(&obj);
451 EXPECT_EQ(key, key2);
452 }
453 }
454
455 } // namespace base
456