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