// Copyright (c) 2011 The Chromium Authors. All rights reserved. // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. #include "base/containers/id_map.h" #include #include #include "base/test/gtest_util.h" #include "testing/gtest/include/gtest/gtest.h" namespace base { namespace { class TestObject { }; class DestructorCounter { public: explicit DestructorCounter(int* counter) : counter_(counter) {} ~DestructorCounter() { ++(*counter_); } private: int* counter_; }; } // namespace TEST(IDMapTest, Basic) { IDMap map; EXPECT_TRUE(map.IsEmpty()); EXPECT_EQ(0U, map.size()); TestObject obj1; TestObject obj2; int32_t id1 = map.Add(&obj1); EXPECT_FALSE(map.IsEmpty()); EXPECT_EQ(1U, map.size()); EXPECT_EQ(&obj1, map.Lookup(id1)); int32_t id2 = map.Add(&obj2); EXPECT_FALSE(map.IsEmpty()); EXPECT_EQ(2U, map.size()); EXPECT_EQ(&obj1, map.Lookup(id1)); EXPECT_EQ(&obj2, map.Lookup(id2)); map.Remove(id1); EXPECT_FALSE(map.IsEmpty()); EXPECT_EQ(1U, map.size()); map.Remove(id2); EXPECT_TRUE(map.IsEmpty()); EXPECT_EQ(0U, map.size()); map.AddWithID(&obj1, 1); map.AddWithID(&obj2, 2); EXPECT_EQ(&obj1, map.Lookup(1)); EXPECT_EQ(&obj2, map.Lookup(2)); EXPECT_EQ(&obj2, map.Replace(2, &obj1)); EXPECT_EQ(&obj1, map.Lookup(2)); EXPECT_EQ(0, map.iteration_depth()); } TEST(IDMapTest, IteratorRemainsValidWhenRemovingCurrentElement) { IDMap map; TestObject obj1; TestObject obj2; TestObject obj3; map.Add(&obj1); map.Add(&obj2); map.Add(&obj3); { IDMap::const_iterator iter(&map); EXPECT_EQ(1, map.iteration_depth()); while (!iter.IsAtEnd()) { map.Remove(iter.GetCurrentKey()); iter.Advance(); } // Test that while an iterator is still in scope, we get the map emptiness // right (http://crbug.com/35571). EXPECT_TRUE(map.IsEmpty()); EXPECT_EQ(0U, map.size()); } EXPECT_TRUE(map.IsEmpty()); EXPECT_EQ(0U, map.size()); EXPECT_EQ(0, map.iteration_depth()); } TEST(IDMapTest, IteratorRemainsValidWhenRemovingOtherElements) { IDMap map; const int kCount = 5; TestObject obj[kCount]; for (auto& i : obj) map.Add(&i); // IDMap has no predictable iteration order. int32_t ids_in_iteration_order[kCount]; const TestObject* objs_in_iteration_order[kCount]; int counter = 0; for (IDMap::const_iterator iter(&map); !iter.IsAtEnd(); iter.Advance()) { ids_in_iteration_order[counter] = iter.GetCurrentKey(); objs_in_iteration_order[counter] = iter.GetCurrentValue(); counter++; } counter = 0; for (IDMap::const_iterator iter(&map); !iter.IsAtEnd(); iter.Advance()) { EXPECT_EQ(1, map.iteration_depth()); switch (counter) { case 0: EXPECT_EQ(ids_in_iteration_order[0], iter.GetCurrentKey()); EXPECT_EQ(objs_in_iteration_order[0], iter.GetCurrentValue()); map.Remove(ids_in_iteration_order[1]); break; case 1: EXPECT_EQ(ids_in_iteration_order[2], iter.GetCurrentKey()); EXPECT_EQ(objs_in_iteration_order[2], iter.GetCurrentValue()); map.Remove(ids_in_iteration_order[3]); break; case 2: EXPECT_EQ(ids_in_iteration_order[4], iter.GetCurrentKey()); EXPECT_EQ(objs_in_iteration_order[4], iter.GetCurrentValue()); map.Remove(ids_in_iteration_order[0]); break; default: FAIL() << "should not have that many elements"; } counter++; } EXPECT_EQ(0, map.iteration_depth()); } TEST(IDMapTest, CopyIterator) { IDMap map; TestObject obj1; TestObject obj2; TestObject obj3; map.Add(&obj1); map.Add(&obj2); map.Add(&obj3); EXPECT_EQ(0, map.iteration_depth()); { IDMap::const_iterator iter1(&map); EXPECT_EQ(1, map.iteration_depth()); // Make sure that copying the iterator correctly increments // map's iteration depth. IDMap::const_iterator iter2(iter1); EXPECT_EQ(2, map.iteration_depth()); } // Make sure after destroying all iterators the map's iteration depth // returns to initial state. EXPECT_EQ(0, map.iteration_depth()); } TEST(IDMapTest, AssignIterator) { IDMap map; TestObject obj1; TestObject obj2; TestObject obj3; map.Add(&obj1); map.Add(&obj2); map.Add(&obj3); EXPECT_EQ(0, map.iteration_depth()); { IDMap::const_iterator iter1(&map); EXPECT_EQ(1, map.iteration_depth()); IDMap::const_iterator iter2(&map); EXPECT_EQ(2, map.iteration_depth()); // Make sure that assigning the iterator correctly updates // map's iteration depth (-1 for destruction, +1 for assignment). EXPECT_EQ(2, map.iteration_depth()); } // Make sure after destroying all iterators the map's iteration depth // returns to initial state. EXPECT_EQ(0, map.iteration_depth()); } TEST(IDMapTest, IteratorRemainsValidWhenClearing) { IDMap map; const int kCount = 5; TestObject obj[kCount]; for (auto& i : obj) map.Add(&i); // IDMap has no predictable iteration order. int32_t ids_in_iteration_order[kCount]; const TestObject* objs_in_iteration_order[kCount]; int counter = 0; for (IDMap::const_iterator iter(&map); !iter.IsAtEnd(); iter.Advance()) { ids_in_iteration_order[counter] = iter.GetCurrentKey(); objs_in_iteration_order[counter] = iter.GetCurrentValue(); counter++; } counter = 0; for (IDMap::const_iterator iter(&map); !iter.IsAtEnd(); iter.Advance()) { switch (counter) { case 0: EXPECT_EQ(ids_in_iteration_order[0], iter.GetCurrentKey()); EXPECT_EQ(objs_in_iteration_order[0], iter.GetCurrentValue()); break; case 1: EXPECT_EQ(ids_in_iteration_order[1], iter.GetCurrentKey()); EXPECT_EQ(objs_in_iteration_order[1], iter.GetCurrentValue()); map.Clear(); EXPECT_TRUE(map.IsEmpty()); EXPECT_EQ(0U, map.size()); break; default: FAIL() << "should not have that many elements"; } counter++; } EXPECT_TRUE(map.IsEmpty()); EXPECT_EQ(0U, map.size()); } TEST(IDMapTest, OwningPointersDeletesThemOnRemove) { const int kCount = 3; int external_del_count = 0; DestructorCounter* external_obj[kCount]; int map_external_ids[kCount]; int owned_del_count = 0; int map_owned_ids[kCount]; IDMap map_external; IDMap> map_owned; for (int i = 0; i < kCount; ++i) { external_obj[i] = new DestructorCounter(&external_del_count); map_external_ids[i] = map_external.Add(external_obj[i]); map_owned_ids[i] = map_owned.Add(std::make_unique(&owned_del_count)); } for (int i = 0; i < kCount; ++i) { EXPECT_EQ(external_del_count, 0); EXPECT_EQ(owned_del_count, i); map_external.Remove(map_external_ids[i]); map_owned.Remove(map_owned_ids[i]); } for (auto* i : external_obj) { delete i; } EXPECT_EQ(external_del_count, kCount); EXPECT_EQ(owned_del_count, kCount); } TEST(IDMapTest, OwningPointersDeletesThemOnClear) { const int kCount = 3; int external_del_count = 0; DestructorCounter* external_obj[kCount]; int owned_del_count = 0; IDMap map_external; IDMap> map_owned; for (auto*& i : external_obj) { i = new DestructorCounter(&external_del_count); map_external.Add(i); map_owned.Add(std::make_unique(&owned_del_count)); } EXPECT_EQ(external_del_count, 0); EXPECT_EQ(owned_del_count, 0); map_external.Clear(); map_owned.Clear(); EXPECT_EQ(external_del_count, 0); EXPECT_EQ(owned_del_count, kCount); for (auto* i : external_obj) { delete i; } EXPECT_EQ(external_del_count, kCount); EXPECT_EQ(owned_del_count, kCount); } TEST(IDMapTest, OwningPointersDeletesThemOnDestruct) { const int kCount = 3; int external_del_count = 0; DestructorCounter* external_obj[kCount]; int owned_del_count = 0; { IDMap map_external; IDMap> map_owned; for (auto*& i : external_obj) { i = new DestructorCounter(&external_del_count); map_external.Add(i); map_owned.Add(std::make_unique(&owned_del_count)); } } EXPECT_EQ(external_del_count, 0); for (auto* i : external_obj) { delete i; } EXPECT_EQ(external_del_count, kCount); EXPECT_EQ(owned_del_count, kCount); } TEST(IDMapTest, Int64KeyType) { IDMap map; TestObject obj1; const int64_t kId1 = 999999999999999999; map.AddWithID(&obj1, kId1); EXPECT_EQ(&obj1, map.Lookup(kId1)); IDMap::const_iterator iter(&map); ASSERT_FALSE(iter.IsAtEnd()); EXPECT_EQ(kId1, iter.GetCurrentKey()); EXPECT_EQ(&obj1, iter.GetCurrentValue()); iter.Advance(); ASSERT_TRUE(iter.IsAtEnd()); map.Remove(kId1); EXPECT_TRUE(map.IsEmpty()); } TEST(IDMapTest, RemovedValueHandling) { TestObject obj; IDMap map; int key = map.Add(&obj); IDMap::iterator itr(&map); map.Clear(); EXPECT_DCHECK_DEATH(map.Remove(key)); EXPECT_DCHECK_DEATH(map.Replace(key, &obj)); EXPECT_FALSE(map.Lookup(key)); EXPECT_FALSE(itr.IsAtEnd()); EXPECT_FALSE(itr.GetCurrentValue()); EXPECT_TRUE(map.IsEmpty()); map.AddWithID(&obj, key); EXPECT_EQ(1u, map.size()); } } // namespace base