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(0, map.iteration_depth());
  57 }
  58
  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
  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
 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
 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
 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
 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
 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
 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