| OLD | NEW |
|---|
| (Empty) |
| 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. | |
| 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 | |
| 17 enum 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. | |
| 33 template<typename T, IDMapOwnershipSemantics OS = IDMapExternalPointer> | |
| 34 class 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 | |
| 56 // Sets whether Add and Replace should DCHECK if passed in NULL data. | |
| 57 // Default is false. | |
| 58 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()); | |
| 63 DCHECK(!check_on_null_data_ || data); | |
| 64 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()); | |
| 77 DCHECK(!check_on_null_data_ || data); | |
| 78 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 | |
| 98 // 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 | |
| 117 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_ | |
| OLD | NEW |
|---|
Chromium Code Reviews
