You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
400 lines
9.6 KiB
400 lines
9.6 KiB
// 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
|