id_map_unittest.cc

// 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 (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<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 (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<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 (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<DestructorCounter*> map_external;
  IDMap<std::unique_ptr<DestructorCounter>> map_owned;

  for (auto*& i : external_obj) {
    i = new DestructorCounter(&external_del_count);
    map_external.Add(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 (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<DestructorCounter*> map_external;
    IDMap<std::unique_ptr<DestructorCounter>> map_owned;

    for (auto*& i : external_obj) {
      i = new DestructorCounter(&external_del_count);
      map_external.Add(i);

      map_owned.Add(std::make_unique<DestructorCounter>(&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<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