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 <stddef.h> 9 #include <stdint.h> 10 #include <memory> 11 #include <set> 12 #include <type_traits> 13 #include <utility> 14 15 #include "base/containers/hash_tables.h" 16 #include "base/logging.h" 17 #include "base/macros.h" 18 #include "base/sequence_checker.h" 19 20 // This object maintains a list of IDs that can be quickly converted to 21 // pointers to objects. It is implemented as a hash table, optimized for 22 // relatively small data sets (in the common case, there will be exactly one 23 // item in the list). 24 // 25 // Items can be inserted into the container with arbitrary ID, but the caller 26 // must ensure they are unique. Inserting IDs and relying on automatically 27 // generated ones is not allowed because they can collide. 28 29 // The map's value type (the V param) can be any dereferenceable type, such as a 30 // raw pointer or smart pointer 31 template <typename V, typename K = int32_t> 32 class IDMap final { 33 public: 34 using KeyType = K; 35 36 private: 37 using T = typename std::remove_reference<decltype(*V())>::type; 38 using HashTable = base::hash_map<KeyType, V>; 39 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 43 // access it from a different, but consistent, thread (or sequence) 44 // post-construction. The first call to CalledOnValidSequence() will re-bind 45 // it. 46 sequence_checker_.DetachFromSequence(); 47 } 48 49 ~IDMap() { 50 // Many IDMap's are static, and hence will be destroyed on the main 51 // thread. However, all the accesses may take place on another thread (or 52 // sequence), such as the IO thread. Detaching again to clean this up. 53 sequence_checker_.DetachFromSequence(); 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(V data) { return AddInternal(std::move(data)); } 62 63 // Adds a new data member with the specified ID. The ID must not be in 64 // the list. The caller either must generate all unique IDs itself and use 65 // this function, or allow this object to generate IDs and call Add. These 66 // two methods may not be mixed, or duplicate IDs may be generated. 67 void AddWithID(V data, KeyType id) { AddWithIDInternal(std::move(data), id); } 68 69 void Remove(KeyType id) { 70 DCHECK(sequence_checker_.CalledOnValidSequence()); 71 typename HashTable::iterator i = data_.find(id); 72 if (i == data_.end()) { 73 NOTREACHED() << "Attempting to remove an item not in the list"; 74 return; 75 } 76 77 if (iteration_depth_ == 0) { 78 data_.erase(i); 79 } else { 80 removed_ids_.insert(id); 81 } 82 } 83 84 // Replaces the value for |id| with |new_data| and returns the existing value. 85 // Should only be called with an already added id. 86 V Replace(KeyType id, V new_data) { 87 DCHECK(sequence_checker_.CalledOnValidSequence()); 88 DCHECK(!check_on_null_data_ || new_data); 89 typename HashTable::iterator i = data_.find(id); 90 DCHECK(i != data_.end()); 91 92 std::swap(i->second, new_data); 93 return new_data; 94 } 95 96 void Clear() { 97 DCHECK(sequence_checker_.CalledOnValidSequence()); 98 if (iteration_depth_ == 0) { 99 data_.clear(); 100 } else { 101 for (typename HashTable::iterator i = data_.begin(); 102 i != data_.end(); ++i) 103 removed_ids_.insert(i->first); 104 } 105 } 106 107 bool IsEmpty() const { 108 DCHECK(sequence_checker_.CalledOnValidSequence()); 109 return size() == 0u; 110 } 111 112 T* Lookup(KeyType id) const { 113 DCHECK(sequence_checker_.CalledOnValidSequence()); 114 typename HashTable::const_iterator i = data_.find(id); 115 if (i == data_.end()) 116 return nullptr; 117 return &*i->second; 118 } 119 120 size_t size() const { 121 DCHECK(sequence_checker_.CalledOnValidSequence()); 122 return data_.size() - removed_ids_.size(); 123 } 124 125 #if defined(UNIT_TEST) 126 int iteration_depth() const { 127 return iteration_depth_; 128 } 129 #endif // defined(UNIT_TEST) 130 131 // It is safe to remove elements from the map during iteration. All iterators 132 // will remain valid. 133 template<class ReturnType> 134 class Iterator { 135 public: 136 Iterator(IDMap<V, K>* map) : map_(map), iter_(map_->data_.begin()) { 137 Init(); 138 } 139 140 Iterator(const Iterator& iter) 141 : map_(iter.map_), 142 iter_(iter.iter_) { 143 Init(); 144 } 145 146 const Iterator& operator=(const Iterator& iter) { 147 map_ = iter.map; 148 iter_ = iter.iter; 149 Init(); 150 return *this; 151 } 152 153 ~Iterator() { 154 DCHECK(map_->sequence_checker_.CalledOnValidSequence()); 155 156 // We're going to decrement iteration depth. Make sure it's greater than 157 // zero so that it doesn't become negative. 158 DCHECK_LT(0, map_->iteration_depth_); 159 160 if (--map_->iteration_depth_ == 0) 161 map_->Compact(); 162 } 163 164 bool IsAtEnd() const { 165 DCHECK(map_->sequence_checker_.CalledOnValidSequence()); 166 return iter_ == map_->data_.end(); 167 } 168 169 KeyType GetCurrentKey() const { 170 DCHECK(map_->sequence_checker_.CalledOnValidSequence()); 171 return iter_->first; 172 } 173 174 ReturnType* GetCurrentValue() const { 175 DCHECK(map_->sequence_checker_.CalledOnValidSequence()); 176 return &*iter_->second; 177 } 178 179 void Advance() { 180 DCHECK(map_->sequence_checker_.CalledOnValidSequence()); 181 ++iter_; 182 SkipRemovedEntries(); 183 } 184 185 private: 186 void Init() { 187 DCHECK(map_->sequence_checker_.CalledOnValidSequence()); 188 ++map_->iteration_depth_; 189 SkipRemovedEntries(); 190 } 191 192 void SkipRemovedEntries() { 193 while (iter_ != map_->data_.end() && 194 map_->removed_ids_.find(iter_->first) != 195 map_->removed_ids_.end()) { 196 ++iter_; 197 } 198 } 199 200 IDMap<V, K>* map_; 201 typename HashTable::const_iterator iter_; 202 }; 203 204 typedef Iterator<T> iterator; 205 typedef Iterator<const T> const_iterator; 206 207 private: 208 KeyType AddInternal(V data) { 209 DCHECK(sequence_checker_.CalledOnValidSequence()); 210 DCHECK(!check_on_null_data_ || data); 211 KeyType this_id = next_id_; 212 DCHECK(data_.find(this_id) == data_.end()) << "Inserting duplicate item"; 213 data_[this_id] = std::move(data); 214 next_id_++; 215 return this_id; 216 } 217 218 void AddWithIDInternal(V data, KeyType id) { 219 DCHECK(sequence_checker_.CalledOnValidSequence()); 220 DCHECK(!check_on_null_data_ || data); 221 DCHECK(data_.find(id) == data_.end()) << "Inserting duplicate item"; 222 data_[id] = std::move(data); 223 } 224 225 void Compact() { 226 DCHECK_EQ(0, iteration_depth_); 227 for (const auto& i : removed_ids_) 228 Remove(i); 229 removed_ids_.clear(); 230 } 231 232 // Keep track of how many iterators are currently iterating on us to safely 233 // handle removing items during iteration. 234 int iteration_depth_; 235 236 // Keep set of IDs that should be removed after the outermost iteration has 237 // finished. This way we manage to not invalidate the iterator when an element 238 // is removed. 239 std::set<KeyType> removed_ids_; 240 241 // The next ID that we will return from Add() 242 KeyType next_id_; 243 244 HashTable data_; 245 246 // See description above setter. 247 bool check_on_null_data_; 248 249 base::SequenceChecker sequence_checker_; 250 251 DISALLOW_COPY_AND_ASSIGN(IDMap); 252 }; 253 254 #endif // BASE_ID_MAP_H_ 255