blob: 852c1380471d776689a9b05c99e67c228d0557e2 [file] [log] [blame]
James Robinson646469d2014-10-03 15:33:28 -07001// 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.
4
5#ifndef BASE_ID_MAP_H_
6#define BASE_ID_MAP_H_
7
8#include <set>
9
10#include "base/basictypes.h"
11#include "base/containers/hash_tables.h"
12#include "base/logging.h"
13#include "base/threading/non_thread_safe.h"
14
15// Ownership semantics - own pointer means the pointer is deleted in Remove()
16// & during destruction
17enum IDMapOwnershipSemantics {
18 IDMapExternalPointer,
19 IDMapOwnPointer
20};
21
22// This object maintains a list of IDs that can be quickly converted to
23// pointers to objects. It is implemented as a hash table, optimized for
24// relatively small data sets (in the common case, there will be exactly one
25// item in the list).
26//
27// Items can be inserted into the container with arbitrary ID, but the caller
28// must ensure they are unique. Inserting IDs and relying on automatically
29// generated ones is not allowed because they can collide.
30//
31// This class does not have a virtual destructor, do not inherit from it when
32// ownership semantics are set to own because pointers will leak.
33template<typename T, IDMapOwnershipSemantics OS = IDMapExternalPointer>
34class IDMap : public base::NonThreadSafe {
35 public:
36 typedef int32 KeyType;
37
38 private:
39 typedef base::hash_map<KeyType, T*> HashTable;
40
41 public:
42 IDMap() : iteration_depth_(0), next_id_(1), check_on_null_data_(false) {
43 // A number of consumers of IDMap create it on one thread but always access
44 // it from a different, but consitent, thread post-construction.
45 DetachFromThread();
46 }
47
48 ~IDMap() {
49 // Many IDMap's are static, and hence will be destroyed on the main thread.
50 // However, all the accesses may take place on another thread, such as the
51 // IO thread. Detaching again to clean this up.
52 DetachFromThread();
53 Releaser<OS, 0>::release_all(&data_);
54 }
55
Przemyslaw Pietrzkiewiczea77f0b2014-12-10 15:35:08 +010056 // Sets whether Add and Replace should DCHECK if passed in NULL data.
57 // Default is false.
James Robinson646469d2014-10-03 15:33:28 -070058 void set_check_on_null_data(bool value) { check_on_null_data_ = value; }
59
60 // Adds a view with an automatically generated unique ID. See AddWithID.
61 KeyType Add(T* data) {
62 DCHECK(CalledOnValidThread());
Przemyslaw Pietrzkiewiczea77f0b2014-12-10 15:35:08 +010063 DCHECK(!check_on_null_data_ || data);
James Robinson646469d2014-10-03 15:33:28 -070064 KeyType this_id = next_id_;
65 DCHECK(data_.find(this_id) == data_.end()) << "Inserting duplicate item";
66 data_[this_id] = data;
67 next_id_++;
68 return this_id;
69 }
70
71 // Adds a new data member with the specified ID. The ID must not be in
72 // the list. The caller either must generate all unique IDs itself and use
73 // this function, or allow this object to generate IDs and call Add. These
74 // two methods may not be mixed, or duplicate IDs may be generated
75 void AddWithID(T* data, KeyType id) {
76 DCHECK(CalledOnValidThread());
Przemyslaw Pietrzkiewiczea77f0b2014-12-10 15:35:08 +010077 DCHECK(!check_on_null_data_ || data);
James Robinson646469d2014-10-03 15:33:28 -070078 DCHECK(data_.find(id) == data_.end()) << "Inserting duplicate item";
79 data_[id] = data;
80 }
81
82 void Remove(KeyType id) {
83 DCHECK(CalledOnValidThread());
84 typename HashTable::iterator i = data_.find(id);
85 if (i == data_.end()) {
86 NOTREACHED() << "Attempting to remove an item not in the list";
87 return;
88 }
89
90 if (iteration_depth_ == 0) {
91 Releaser<OS, 0>::release(i->second);
92 data_.erase(i);
93 } else {
94 removed_ids_.insert(id);
95 }
96 }
97
Przemyslaw Pietrzkiewiczea77f0b2014-12-10 15:35:08 +010098 // Replaces the value for |id| with |new_data| and returns a pointer to the
99 // existing value. If there is no entry for |id|, the map is not altered and
100 // nullptr is returned. The OwnershipSemantics of the map have no effect on
101 // how the existing value is treated, the IDMap does not delete the existing
102 // value being replaced.
103 T* Replace(KeyType id, T* new_data) {
104 DCHECK(CalledOnValidThread());
105 DCHECK(!check_on_null_data_ || new_data);
106 typename HashTable::iterator i = data_.find(id);
107 if (i == data_.end()) {
108 NOTREACHED() << "Attempting to replace an item not in the list";
109 return nullptr;
110 }
111
112 T* temp = i->second;
113 i->second = new_data;
114 return temp;
115 }
116
James Robinson646469d2014-10-03 15:33:28 -0700117 void Clear() {
118 DCHECK(CalledOnValidThread());
119 if (iteration_depth_ == 0) {
120 Releaser<OS, 0>::release_all(&data_);
121 } else {
122 for (typename HashTable::iterator i = data_.begin();
123 i != data_.end(); ++i)
124 removed_ids_.insert(i->first);
125 }
126 }
127
128 bool IsEmpty() const {
129 DCHECK(CalledOnValidThread());
130 return size() == 0u;
131 }
132
133 T* Lookup(KeyType id) const {
134 DCHECK(CalledOnValidThread());
135 typename HashTable::const_iterator i = data_.find(id);
136 if (i == data_.end())
137 return NULL;
138 return i->second;
139 }
140
141 size_t size() const {
142 DCHECK(CalledOnValidThread());
143 return data_.size() - removed_ids_.size();
144 }
145
146#if defined(UNIT_TEST)
147 int iteration_depth() const {
148 return iteration_depth_;
149 }
150#endif // defined(UNIT_TEST)
151
152 // It is safe to remove elements from the map during iteration. All iterators
153 // will remain valid.
154 template<class ReturnType>
155 class Iterator {
156 public:
157 Iterator(IDMap<T, OS>* map)
158 : map_(map),
159 iter_(map_->data_.begin()) {
160 Init();
161 }
162
163 Iterator(const Iterator& iter)
164 : map_(iter.map_),
165 iter_(iter.iter_) {
166 Init();
167 }
168
169 const Iterator& operator=(const Iterator& iter) {
170 map_ = iter.map;
171 iter_ = iter.iter;
172 Init();
173 return *this;
174 }
175
176 ~Iterator() {
177 DCHECK(map_->CalledOnValidThread());
178
179 // We're going to decrement iteration depth. Make sure it's greater than
180 // zero so that it doesn't become negative.
181 DCHECK_LT(0, map_->iteration_depth_);
182
183 if (--map_->iteration_depth_ == 0)
184 map_->Compact();
185 }
186
187 bool IsAtEnd() const {
188 DCHECK(map_->CalledOnValidThread());
189 return iter_ == map_->data_.end();
190 }
191
192 KeyType GetCurrentKey() const {
193 DCHECK(map_->CalledOnValidThread());
194 return iter_->first;
195 }
196
197 ReturnType* GetCurrentValue() const {
198 DCHECK(map_->CalledOnValidThread());
199 return iter_->second;
200 }
201
202 void Advance() {
203 DCHECK(map_->CalledOnValidThread());
204 ++iter_;
205 SkipRemovedEntries();
206 }
207
208 private:
209 void Init() {
210 DCHECK(map_->CalledOnValidThread());
211 ++map_->iteration_depth_;
212 SkipRemovedEntries();
213 }
214
215 void SkipRemovedEntries() {
216 while (iter_ != map_->data_.end() &&
217 map_->removed_ids_.find(iter_->first) !=
218 map_->removed_ids_.end()) {
219 ++iter_;
220 }
221 }
222
223 IDMap<T, OS>* map_;
224 typename HashTable::const_iterator iter_;
225 };
226
227 typedef Iterator<T> iterator;
228 typedef Iterator<const T> const_iterator;
229
230 private:
231
232 // The dummy parameter is there because C++ standard does not allow
233 // explicitly specialized templates inside classes
234 template<IDMapOwnershipSemantics OI, int dummy> struct Releaser {
235 static inline void release(T* ptr) {}
236 static inline void release_all(HashTable* table) {}
237 };
238
239 template<int dummy> struct Releaser<IDMapOwnPointer, dummy> {
240 static inline void release(T* ptr) { delete ptr;}
241 static inline void release_all(HashTable* table) {
242 for (typename HashTable::iterator i = table->begin();
243 i != table->end(); ++i) {
244 delete i->second;
245 }
246 table->clear();
247 }
248 };
249
250 void Compact() {
251 DCHECK_EQ(0, iteration_depth_);
252 for (std::set<KeyType>::const_iterator i = removed_ids_.begin();
253 i != removed_ids_.end(); ++i) {
254 Remove(*i);
255 }
256 removed_ids_.clear();
257 }
258
259 // Keep track of how many iterators are currently iterating on us to safely
260 // handle removing items during iteration.
261 int iteration_depth_;
262
263 // Keep set of IDs that should be removed after the outermost iteration has
264 // finished. This way we manage to not invalidate the iterator when an element
265 // is removed.
266 std::set<KeyType> removed_ids_;
267
268 // The next ID that we will return from Add()
269 KeyType next_id_;
270
271 HashTable data_;
272
273 // See description above setter.
274 bool check_on_null_data_;
275
276 DISALLOW_COPY_AND_ASSIGN(IDMap);
277};
278
279#endif // BASE_ID_MAP_H_