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

12 files changed, 10 insertions, 280 deletions

diff --git a/chrome/browser/chrome_plugin_browsing_context.h b/chrome/browser/chrome_plugin_browsing_context.h
index d79f5d2..16499e8 100644
--- a/chrome/browser/chrome_plugin_browsing_context.h
+++ b/chrome/browser/chrome_plugin_browsing_context.h
@@ -7,8 +7,8 @@
 
 #include <map>
 
+#include "base/id_map.h"
 #include "chrome/common/chrome_plugin_api.h"
-#include "chrome/common/id_map.h"
 #include "chrome/common/notification_registrar.h"
 
 class URLRequestContext;
diff --git a/chrome/browser/renderer_host/render_process_host.h b/chrome/browser/renderer_host/render_process_host.h
index 20b9e81..4c12084 100644
--- a/chrome/browser/renderer_host/render_process_host.h
+++ b/chrome/browser/renderer_host/render_process_host.h
@@ -8,9 +8,9 @@
 #include <set>
 #include <string>
 
+#include "base/id_map.h"
 #include "base/process.h"
 #include "base/scoped_ptr.h"
-#include "chrome/common/id_map.h"
 #include "chrome/common/transport_dib.h"
 #include "chrome/common/visitedlink_common.h"
 #include "ipc/ipc_sync_channel.h"
diff --git a/chrome/chrome.gyp b/chrome/chrome.gyp
index 69700e7..8371db4 100644
--- a/chrome/chrome.gyp
+++ b/chrome/chrome.gyp
@@ -384,7 +384,6 @@
         'common/extensions/user_script.cc',
         'common/extensions/user_script.h',
         'common/gfx/utils.h',
-        'common/id_map.h',
         'common/net/cookie_monster_sqlite.cc',
         'common/net/cookie_monster_sqlite.h',
         'common/net/dns.h',
@@ -3982,7 +3981,6 @@
         'common/extensions/extension_unittest.cc',
         'common/extensions/url_pattern_unittest.cc',
         'common/extensions/user_script_unittest.cc',
-        'common/id_map_unittest.cc',
         'common/important_file_writer_unittest.cc',
         'common/json_value_serializer_unittest.cc',
         'common/mru_cache_unittest.cc',
@@ -4216,7 +4214,7 @@
       # Provides a syncapi dynamic library target from checked-in binaries,
       # or from compiling a stub implementation.
       'target_name': 'syncapi',
-      
+
       'conditions': [
         ['chrome_personalization==0', {
           # Empty target.
diff --git a/chrome/common/app_cache/app_cache_context_impl.h b/chrome/common/app_cache/app_cache_context_impl.h
index b9ed757..ec2f25f 100644
--- a/chrome/common/app_cache/app_cache_context_impl.h
+++ b/chrome/common/app_cache/app_cache_context_impl.h
@@ -5,7 +5,7 @@
 #ifndef CHROME_COMMON_APP_CACHE_APP_CACHE_CONTEXT_IMPL_H_
 #define CHROME_COMMON_APP_CACHE_APP_CACHE_CONTEXT_IMPL_H_
 
-#include "chrome/common/id_map.h"
+#include "base/id_map.h"
 #include "ipc/ipc_message.h"
 #include "webkit/glue/webappcachecontext.h"
 
diff --git a/chrome/common/app_cache/app_cache_dispatcher_host.h b/chrome/common/app_cache/app_cache_dispatcher_host.h
index 6de17a3..749e74a 100644
--- a/chrome/common/app_cache/app_cache_dispatcher_host.h
+++ b/chrome/common/app_cache/app_cache_dispatcher_host.h
@@ -5,7 +5,7 @@
 #ifndef CHROME_COMMON_APP_CACHE_APP_CACHE_DISPATCHER_HOST_H_
 #define CHROME_COMMON_APP_CACHE_APP_CACHE_DISPATCHER_HOST_H_
 
-#include "chrome/common/id_map.h"
+#include "base/id_map.h"
 #include "ipc/ipc_message.h"
 #include "webkit/glue/webappcachecontext.h"
 
diff --git a/chrome/common/db_message_filter.cc b/chrome/common/db_message_filter.cc
index 992ffad..cba4aea 100644
--- a/chrome/common/db_message_filter.cc
+++ b/chrome/common/db_message_filter.cc
@@ -5,12 +5,12 @@
 #include "db_message_filter.h"
 
 #include "base/atomic_sequence_num.h"
+#include "base/id_map.h"
 #include "base/lock.h"
 #include "base/message_loop.h"
 #include "base/platform_file.h"
 #include "base/task.h"
 #include "chrome/common/child_process.h"
-#include "chrome/common/id_map.h"
 #include "chrome/common/render_messages.h"
 #include "ipc/ipc_channel.h"
 #include "ipc/ipc_message.h"
diff --git a/chrome/common/db_message_filter.h b/chrome/common/db_message_filter.h
index 4728400..1376db0 100644
--- a/chrome/common/db_message_filter.h
+++ b/chrome/common/db_message_filter.h
@@ -5,9 +5,9 @@
 #ifndef CHROME_COMMON_DB_MESSAGE_FILTER_H_
 #define CHROME_COMMON_DB_MESSAGE_FILTER_H_
 
+#include "base/id_map.h"
 #include "base/scoped_ptr.h"
 #include "base/waitable_event.h"
-#include "chrome/common/id_map.h"
 #include "ipc/ipc_channel_proxy.h"
 
 class Lock;
diff --git a/chrome/common/id_map.h b/chrome/common/id_map.h
deleted file mode 100644
index bf351b8..0000000
--- a/chrome/common/id_map.h
+++ /dev/null
@@ -1,162 +0,0 @@
-// 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 CHROME_COMMON_ID_MAP_H_
-#define CHROME_COMMON_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  // CHROME_COMMON_ID_MAP_H_
diff --git a/chrome/common/id_map_unittest.cc b/chrome/common/id_map_unittest.cc
deleted file mode 100644
index ed15cbe..0000000
--- a/chrome/common/id_map_unittest.cc
+++ /dev/null
@@ -1,106 +0,0 @@
-// 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 "chrome/common/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
diff --git a/chrome/common/message_router.h b/chrome/common/message_router.h
index ef648ab..ef18aaa 100644
--- a/chrome/common/message_router.h
+++ b/chrome/common/message_router.h
@@ -5,7 +5,7 @@
 #ifndef CHROME_COMMON_MESSAGE_ROUTER_H__
 #define CHROME_COMMON_MESSAGE_ROUTER_H__
 
-#include "chrome/common/id_map.h"
+#include "base/id_map.h"
 #include "ipc/ipc_channel.h"
 
 // The MessageRouter handles all incoming messages sent to it by routing them
diff --git a/chrome/renderer/audio_message_filter.h b/chrome/renderer/audio_message_filter.h
index ef3ecac..f714e1b 100644
--- a/chrome/renderer/audio_message_filter.h
+++ b/chrome/renderer/audio_message_filter.h
@@ -10,8 +10,8 @@
 #ifndef CHROME_RENDERER_AUDIO_MESSAGE_FILTER_H_
 #define CHROME_RENDERER_AUDIO_MESSAGE_FILTER_H_
 
+#include "base/id_map.h"
 #include "base/shared_memory.h"
-#include "chrome/common/id_map.h"
 #include "chrome/common/render_messages.h"
 #include "ipc/ipc_channel_proxy.h"
 #include "testing/gtest/include/gtest/gtest_prod.h"
diff --git a/chrome/renderer/render_view.h b/chrome/renderer/render_view.h
index 646b488..48923c4 100644
--- a/chrome/renderer/render_view.h
+++ b/chrome/renderer/render_view.h
@@ -13,11 +13,11 @@
 #include "base/file_path.h"
 #include "base/gfx/point.h"
 #include "base/gfx/rect.h"
+#include "base/id_map.h"
 #include "base/shared_memory.h"
 #include "base/timer.h"
 #include "base/values.h"
 #include "build/build_config.h"
-#include "chrome/common/id_map.h"
 #include "chrome/common/renderer_preferences.h"
 #include "chrome/common/view_types.h"
 #include "chrome/renderer/automation/dom_automation_controller.h"