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