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