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