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 11 namespace { 12 13 class TestObject { 14 }; 15 16 class DestructorCounter { 17 public: 18 explicit DestructorCounter(int* counter) : counter_(counter) {} 19 ~DestructorCounter() { ++(*counter_); } 20 21 private: 22 int* counter_; 23 }; 24 25 TEST(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 64 TEST(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 97 TEST(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 149 TEST(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 177 TEST(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 207 TEST(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 253 TEST(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 291 TEST(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 328 TEST(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 360 TEST(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
