Move IDMap back to base/ where it is needed.

TEST=Covered by base_unittests.
BUG=none

Review URL: http://codereview.chromium.org/173026

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@23709 0039d316-1c4b-4281-b951-d872f2087c98

3 files changed, 270 insertions, 0 deletions

diff --git a/base/base.gyp b/base/base.gyp
index 6603ce6..7be1225 100644
--- a/base/base.gyp
+++ b/base/base.gyp
@@ -150,6 +150,7 @@
         'idle_timer.cc',
         'idle_timer.h',
         'idle_timer_none.cc',
+        'id_map.h',
         'image_util.cc',
         'image_util.h',
         'json_reader.cc',
@@ -579,6 +580,7 @@
         'histogram_unittest.cc',
         'hmac_unittest.cc',
         'idletimer_unittest.cc',
+        'id_map_unittest.cc',
         'json_reader_unittest.cc',
         'json_writer_unittest.cc',
         'lazy_instance_unittest.cc',
diff --git a/base/id_map.h b/base/id_map.h
new file mode 100644
index 0000000..13fb2f2
--- /dev/null
+++ b/base/id_map.h
@@ -0,0 +1,162 @@
+// Copyright (c) 2006-2008 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.
+
+#ifndef BASE_ID_MAP_H_
+#define BASE_ID_MAP_H_
+
+#include <set>
+
+#include "base/basictypes.h"
+#include "base/hash_tables.h"
+#include "base/logging.h"
+
+// This object maintains a list of IDs that can be quickly converted to
+// pointers to objects. It is implemented as a hash table, optimized for
+// relatively small data sets (in the common case, there will be exactly one
+// item in the list).
+//
+// Items can be inserted into the container with arbitrary ID, but the caller
+// must ensure they are unique. Inserting IDs and relying on automatically
+// generated ones is not allowed because they can collide.
+template<class T>
+class IDMap {
+ private:
+  typedef base::hash_map<int32, T*> HashTable;
+
+ public:
+  IDMap() : iteration_depth_(0), next_id_(1), check_on_null_data_(false) {
+  }
+
+  // Sets whether Add should CHECK if passed in NULL data. Default is false.
+  void set_check_on_null_data(bool value) { check_on_null_data_ = value; }
+
+  // Adds a view with an automatically generated unique ID. See AddWithID.
+  int32 Add(T* data) {
+    CHECK(!check_on_null_data_ || data);
+    int32 this_id = next_id_;
+    DCHECK(data_.find(this_id) == data_.end()) << "Inserting duplicate item";
+    data_[this_id] = data;
+    next_id_++;
+    return this_id;
+  }
+
+  // Adds a new data member with the specified ID. The ID must not be in
+  // the list. The caller either must generate all unique IDs itself and use
+  // this function, or allow this object to generate IDs and call Add. These
+  // two methods may not be mixed, or duplicate IDs may be generated
+  void AddWithID(T* data, int32 id) {
+    CHECK(!check_on_null_data_ || data);
+    DCHECK(data_.find(id) == data_.end()) << "Inserting duplicate item";
+    data_[id] = data;
+  }
+
+  void Remove(int32 id) {
+    typename HashTable::iterator i = data_.find(id);
+    if (i == data_.end()) {
+      NOTREACHED() << "Attempting to remove an item not in the list";
+      return;
+    }
+
+    if (iteration_depth_ == 0)
+      data_.erase(i);
+    else
+      removed_ids_.insert(id);
+  }
+
+  bool IsEmpty() const {
+    return data_.empty();
+  }
+
+  T* Lookup(int32 id) const {
+    typename HashTable::const_iterator i = data_.find(id);
+    if (i == data_.end())
+      return NULL;
+    return i->second;
+  }
+
+  size_t size() const {
+    return data_.size();
+  }
+
+  // It is safe to remove elements from the map during iteration. All iterators
+  // will remain valid.
+  template<class ReturnType>
+  class Iterator {
+   public:
+    Iterator(IDMap<T>* map)
+        : map_(map),
+          iter_(map_->data_.begin()) {
+      ++map_->iteration_depth_;
+      SkipRemovedEntries();
+    }
+
+    ~Iterator() {
+      if (--map_->iteration_depth_ == 0)
+        map_->Compact();
+    }
+
+    bool IsAtEnd() const {
+      return iter_ == map_->data_.end();
+    }
+
+    int32 GetCurrentKey() const {
+      return iter_->first;
+    }
+
+    ReturnType* GetCurrentValue() const {
+      return iter_->second;
+    }
+
+    void Advance() {
+      ++iter_;
+      SkipRemovedEntries();
+    }
+
+   private:
+    void SkipRemovedEntries() {
+      while (iter_ != map_->data_.end() &&
+             map_->removed_ids_.find(iter_->first) !=
+             map_->removed_ids_.end()) {
+        ++iter_;
+      }
+    }
+
+    IDMap<T>* map_;
+    typename HashTable::const_iterator iter_;
+  };
+
+  typedef Iterator<T> iterator;
+  typedef Iterator<const T> const_iterator;
+
+ private:
+  void Compact() {
+    DCHECK_EQ(0, iteration_depth_);
+    for (std::set<int32>::const_iterator i = removed_ids_.begin();
+         i != removed_ids_.end(); ++i) {
+      Remove(*i);
+    }
+    removed_ids_.clear();
+  }
+
+  // Keep track of how many iterators are currently iterating on us to safely
+  // handle removing items during iteration.
+  int iteration_depth_;
+
+  // Keep set of IDs that should be removed after the outermost iteration has
+  // finished. This way we manage to not invalidate the iterator when an element
+  // is removed.
+  std::set<int32> removed_ids_;
+
+  // The next ID that we will return from Add()
+  int32 next_id_;
+
+  HashTable data_;
+
+  // See description above setter.
+  bool check_on_null_data_;
+
+  DISALLOW_COPY_AND_ASSIGN(IDMap);
+};
+
+#endif  // BASE_ID_MAP_H_
diff --git a/base/id_map_unittest.cc b/base/id_map_unittest.cc
new file mode 100644
index 0000000..7b12e35
--- /dev/null
+++ b/base/id_map_unittest.cc
@@ -0,0 +1,106 @@
+// Copyright (c) 2009 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/id_map.h"
+
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace {
+
+class IDMapTest : public testing::Test {
+};
+
+class TestObject {
+};
+
+TEST_F(IDMapTest, Basic) {
+  IDMap<TestObject> map;
+  EXPECT_TRUE(map.IsEmpty());
+  EXPECT_EQ(0U, map.size());
+
+  TestObject obj1;
+  TestObject obj2;
+
+  int32 id1 = map.Add(&obj1);
+  EXPECT_FALSE(map.IsEmpty());
+  EXPECT_EQ(1U, map.size());
+  EXPECT_EQ(&obj1, map.Lookup(id1));
+
+  int32 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));
+}
+
+TEST_F(IDMapTest, IteratorRemainsValidWhenRemovingCurrentElement) {
+  IDMap<TestObject> map;
+
+  TestObject obj1;
+  TestObject obj2;
+  TestObject obj3;
+
+  map.Add(&obj1);
+  map.Add(&obj2);
+  map.Add(&obj3);
+
+  for (IDMap<TestObject>::const_iterator iter(&map);
+       !iter.IsAtEnd(); iter.Advance()) {
+    map.Remove(iter.GetCurrentKey());
+  }
+}
+
+TEST_F(IDMapTest, IteratorRemainsValidWhenRemovingOtherElements) {
+  IDMap<TestObject> map;
+
+  const int kCount = 5;
+  TestObject obj[kCount];
+  int32 ids[kCount];
+
+  for (int i = 0; i < kCount; i++)
+    ids[i] = map.Add(&obj[i]);
+
+  int counter = 0;
+  for (IDMap<TestObject>::const_iterator iter(&map);
+       !iter.IsAtEnd(); iter.Advance()) {
+    switch (counter) {
+      case 0:
+        EXPECT_EQ(ids[0], iter.GetCurrentKey());
+        EXPECT_EQ(&obj[0], iter.GetCurrentValue());
+        map.Remove(ids[1]);
+        break;
+      case 1:
+        EXPECT_EQ(ids[2], iter.GetCurrentKey());
+        EXPECT_EQ(&obj[2], iter.GetCurrentValue());
+        map.Remove(ids[3]);
+        break;
+      case 2:
+        EXPECT_EQ(ids[4], iter.GetCurrentKey());
+        EXPECT_EQ(&obj[4], iter.GetCurrentValue());
+        map.Remove(ids[0]);
+        break;
+      default:
+        FAIL() << "should not have that many elements";
+        break;
+    }
+
+    counter++;
+  }
+}
+
+}  // namespace