| // 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 <stdint.h> |
| |
| #include <memory> |
| |
| #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<TestObject*> 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<TestObject*> map; |
| |
| TestObject obj1; |
| TestObject obj2; |
| TestObject obj3; |
| |
| map.Add(&obj1); |
| map.Add(&obj2); |
| map.Add(&obj3); |
| |
| { |
| IDMap<TestObject*>::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<TestObject*> map; |
| |
| const int kCount = 5; |
| TestObject obj[kCount]; |
| |
| for (int i = 0; i < kCount; i++) |
| map.Add(&obj[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<TestObject*>::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<TestObject*>::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"; |
| break; |
| } |
| |
| counter++; |
| } |
| |
| EXPECT_EQ(0, map.iteration_depth()); |
| } |
| |
| TEST(IDMapTest, CopyIterator) { |
| IDMap<TestObject*> map; |
| |
| TestObject obj1; |
| TestObject obj2; |
| TestObject obj3; |
| |
| map.Add(&obj1); |
| map.Add(&obj2); |
| map.Add(&obj3); |
| |
| EXPECT_EQ(0, map.iteration_depth()); |
| |
| { |
| IDMap<TestObject*>::const_iterator iter1(&map); |
| EXPECT_EQ(1, map.iteration_depth()); |
| |
| // Make sure that copying the iterator correctly increments |
| // map's iteration depth. |
| IDMap<TestObject*>::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<TestObject*> map; |
| |
| TestObject obj1; |
| TestObject obj2; |
| TestObject obj3; |
| |
| map.Add(&obj1); |
| map.Add(&obj2); |
| map.Add(&obj3); |
| |
| EXPECT_EQ(0, map.iteration_depth()); |
| |
| { |
| IDMap<TestObject*>::const_iterator iter1(&map); |
| EXPECT_EQ(1, map.iteration_depth()); |
| |
| IDMap<TestObject*>::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<TestObject*> map; |
| |
| const int kCount = 5; |
| TestObject obj[kCount]; |
| |
| for (int i = 0; i < kCount; i++) |
| map.Add(&obj[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<TestObject*>::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<TestObject*>::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"; |
| break; |
| } |
| 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<DestructorCounter*> map_external; |
| IDMap<std::unique_ptr<DestructorCounter>> 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<DestructorCounter>(&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 (int i = 0; i < kCount; ++i) { |
| delete external_obj[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<DestructorCounter*> map_external; |
| IDMap<std::unique_ptr<DestructorCounter>> map_owned; |
| |
| for (int i = 0; i < kCount; ++i) { |
| external_obj[i] = new DestructorCounter(&external_del_count); |
| map_external.Add(external_obj[i]); |
| |
| map_owned.Add(std::make_unique<DestructorCounter>(&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 (int i = 0; i < kCount; ++i) { |
| delete external_obj[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<DestructorCounter*> map_external; |
| IDMap<std::unique_ptr<DestructorCounter>> map_owned; |
| |
| for (int i = 0; i < kCount; ++i) { |
| external_obj[i] = new DestructorCounter(&external_del_count); |
| map_external.Add(external_obj[i]); |
| |
| map_owned.Add(std::make_unique<DestructorCounter>(&owned_del_count)); |
| } |
| } |
| |
| EXPECT_EQ(external_del_count, 0); |
| |
| for (int i = 0; i < kCount; ++i) { |
| delete external_obj[i]; |
| } |
| |
| EXPECT_EQ(external_del_count, kCount); |
| EXPECT_EQ(owned_del_count, kCount); |
| } |
| |
| TEST(IDMapTest, Int64KeyType) { |
| IDMap<TestObject*, int64_t> map; |
| TestObject obj1; |
| const int64_t kId1 = 999999999999999999; |
| |
| map.AddWithID(&obj1, kId1); |
| EXPECT_EQ(&obj1, map.Lookup(kId1)); |
| |
| IDMap<TestObject*, int64_t>::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<TestObject*> map; |
| int key = map.Add(&obj); |
| |
| IDMap<TestObject*>::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 |