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
11namespace {
12
13class TestObject {
14};
15
16class DestructorCounter {
17 public:
18  explicit DestructorCounter(int* counter) : counter_(counter) {}
19  ~DestructorCounter() { ++(*counter_); }
20
21 private:
22  int* counter_;
23};
24
25TEST(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
64TEST(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
97TEST(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
149TEST(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
177TEST(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
207TEST(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
253TEST(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
291TEST(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
328TEST(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
360TEST(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  IDMap<TestObject, IDMapExternalPointer, int64_t>::const_iterator iter(&map);
369  ASSERT_FALSE(iter.IsAtEnd());
370  EXPECT_EQ(kId1, iter.GetCurrentKey());
371  EXPECT_EQ(&obj1, iter.GetCurrentValue());
372  iter.Advance();
373  ASSERT_TRUE(iter.IsAtEnd());
374
375  map.Remove(kId1);
376  EXPECT_TRUE(map.IsEmpty());
377}
378
379}  // namespace
380