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