Updating trunk VERSION from 935.0 to 936.0
[chromium-blink-merge.git] / base / id_map.h
blob5aea98e82dfe98666ca77f699d21cbac82fad189
1 // Copyright (c) 2011 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
5 #ifndef BASE_ID_MAP_H_
6 #define BASE_ID_MAP_H_
7 #pragma once
9 #include <set>
11 #include "base/basictypes.h"
12 #include "base/hash_tables.h"
13 #include "base/logging.h"
14 #include "base/threading/non_thread_safe.h"
16 // Ownership semantics - own pointer means the pointer is deleted in Remove()
17 // & during destruction
18 enum IDMapOwnershipSemantics {
19 IDMapExternalPointer,
20 IDMapOwnPointer
23 // This object maintains a list of IDs that can be quickly converted to
24 // pointers to objects. It is implemented as a hash table, optimized for
25 // relatively small data sets (in the common case, there will be exactly one
26 // item in the list).
28 // Items can be inserted into the container with arbitrary ID, but the caller
29 // must ensure they are unique. Inserting IDs and relying on automatically
30 // generated ones is not allowed because they can collide.
32 // This class does not have a virtual destructor, do not inherit from it when
33 // ownership semantics are set to own because pointers will leak.
34 template<typename T, IDMapOwnershipSemantics OS = IDMapExternalPointer>
35 class IDMap : public base::NonThreadSafe {
36 private:
37 typedef int32 KeyType;
38 typedef base::hash_map<KeyType, T*> HashTable;
40 public:
41 IDMap() : iteration_depth_(0), next_id_(1), check_on_null_data_(false) {
42 // A number of consumers of IDMap create it on one thread but always access
43 // it from a different, but consitent, thread post-construction.
44 DetachFromThread();
47 ~IDMap() {
48 // Many IDMap's are static, and hence will be destroyed on the main thread.
49 // However, all the accesses may take place on another thread, such as the
50 // IO thread. Detaching again to clean this up.
51 DetachFromThread();
52 Releaser<OS, 0>::release_all(&data_);
55 // Sets whether Add should CHECK if passed in NULL data. Default is false.
56 void set_check_on_null_data(bool value) { check_on_null_data_ = value; }
58 // Adds a view with an automatically generated unique ID. See AddWithID.
59 KeyType Add(T* data) {
60 DCHECK(CalledOnValidThread());
61 CHECK(!check_on_null_data_ || data);
62 KeyType this_id = next_id_;
63 DCHECK(data_.find(this_id) == data_.end()) << "Inserting duplicate item";
64 data_[this_id] = data;
65 next_id_++;
66 return this_id;
69 // Adds a new data member with the specified ID. The ID must not be in
70 // the list. The caller either must generate all unique IDs itself and use
71 // this function, or allow this object to generate IDs and call Add. These
72 // two methods may not be mixed, or duplicate IDs may be generated
73 void AddWithID(T* data, KeyType id) {
74 DCHECK(CalledOnValidThread());
75 CHECK(!check_on_null_data_ || data);
76 DCHECK(data_.find(id) == data_.end()) << "Inserting duplicate item";
77 data_[id] = data;
80 void Remove(KeyType id) {
81 DCHECK(CalledOnValidThread());
82 typename HashTable::iterator i = data_.find(id);
83 if (i == data_.end()) {
84 NOTREACHED() << "Attempting to remove an item not in the list";
85 return;
88 if (iteration_depth_ == 0) {
89 Releaser<OS, 0>::release(i->second);
90 data_.erase(i);
91 } else {
92 removed_ids_.insert(id);
96 bool IsEmpty() const {
97 DCHECK(CalledOnValidThread());
98 return size() == 0u;
101 T* Lookup(KeyType id) const {
102 DCHECK(CalledOnValidThread());
103 typename HashTable::const_iterator i = data_.find(id);
104 if (i == data_.end())
105 return NULL;
106 return i->second;
109 size_t size() const {
110 DCHECK(CalledOnValidThread());
111 return data_.size() - removed_ids_.size();
114 // It is safe to remove elements from the map during iteration. All iterators
115 // will remain valid.
116 template<class ReturnType>
117 class Iterator {
118 public:
119 Iterator(IDMap<T, OS>* map)
120 : map_(map),
121 iter_(map_->data_.begin()) {
122 DCHECK(map->CalledOnValidThread());
123 ++map_->iteration_depth_;
124 SkipRemovedEntries();
127 ~Iterator() {
128 DCHECK(map_->CalledOnValidThread());
129 if (--map_->iteration_depth_ == 0)
130 map_->Compact();
133 bool IsAtEnd() const {
134 DCHECK(map_->CalledOnValidThread());
135 return iter_ == map_->data_.end();
138 KeyType GetCurrentKey() const {
139 DCHECK(map_->CalledOnValidThread());
140 return iter_->first;
143 ReturnType* GetCurrentValue() const {
144 DCHECK(map_->CalledOnValidThread());
145 return iter_->second;
148 void Advance() {
149 DCHECK(map_->CalledOnValidThread());
150 ++iter_;
151 SkipRemovedEntries();
154 private:
155 void SkipRemovedEntries() {
156 while (iter_ != map_->data_.end() &&
157 map_->removed_ids_.find(iter_->first) !=
158 map_->removed_ids_.end()) {
159 ++iter_;
163 IDMap<T, OS>* map_;
164 typename HashTable::const_iterator iter_;
167 typedef Iterator<T> iterator;
168 typedef Iterator<const T> const_iterator;
170 private:
172 // The dummy parameter is there because C++ standard does not allow
173 // explicitly specialized templates inside classes
174 template<IDMapOwnershipSemantics OI, int dummy> struct Releaser {
175 static inline void release(T* ptr) {}
176 static inline void release_all(HashTable* table) {}
179 template<int dummy> struct Releaser<IDMapOwnPointer, dummy> {
180 static inline void release(T* ptr) { delete ptr;}
181 static inline void release_all(HashTable* table) {
182 for (typename HashTable::iterator i = table->begin();
183 i != table->end(); ++i) {
184 delete i->second;
186 table->clear();
190 void Compact() {
191 DCHECK_EQ(0, iteration_depth_);
192 for (std::set<KeyType>::const_iterator i = removed_ids_.begin();
193 i != removed_ids_.end(); ++i) {
194 Remove(*i);
196 removed_ids_.clear();
199 // Keep track of how many iterators are currently iterating on us to safely
200 // handle removing items during iteration.
201 int iteration_depth_;
203 // Keep set of IDs that should be removed after the outermost iteration has
204 // finished. This way we manage to not invalidate the iterator when an element
205 // is removed.
206 std::set<KeyType> removed_ids_;
208 // The next ID that we will return from Add()
209 KeyType next_id_;
211 HashTable data_;
213 // See description above setter.
214 bool check_on_null_data_;
216 DISALLOW_COPY_AND_ASSIGN(IDMap);
219 #endif // BASE_ID_MAP_H_