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 356