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
9namespace {
10
11class TestObject {
12};
13
14class DestructorCounter {
15 public:
16  explicit DestructorCounter(int* counter) : counter_(counter) {}
17  ~DestructorCounter() { ++(*counter_); }
18
19 private:
20  int* counter_;
21};
22
23TEST(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
59TEST(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
92TEST(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
144TEST(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
172TEST(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
202TEST(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
248TEST(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
286TEST(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
323TEST(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