base/id_map_unittest.cc

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