• 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 <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:
IDMap()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 
~IDMap()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 should CHECK if passed in NULL data. Default is false.
set_check_on_null_data(bool value)57   void set_check_on_null_data(bool value) { check_on_null_data_ = value; }
58 
59   // Adds a view with an automatically generated unique ID. See AddWithID.
Add(T * data)60   KeyType Add(T* data) {
61     DCHECK(CalledOnValidThread());
62     CHECK(!check_on_null_data_ || data);
63     KeyType this_id = next_id_;
64     DCHECK(data_.find(this_id) == data_.end()) << "Inserting duplicate item";
65     data_[this_id] = data;
66     next_id_++;
67     return this_id;
68   }
69 
70   // Adds a new data member with the specified ID. The ID must not be in
71   // the list. The caller either must generate all unique IDs itself and use
72   // this function, or allow this object to generate IDs and call Add. These
73   // two methods may not be mixed, or duplicate IDs may be generated
AddWithID(T * data,KeyType id)74   void AddWithID(T* data, KeyType id) {
75     DCHECK(CalledOnValidThread());
76     CHECK(!check_on_null_data_ || data);
77     DCHECK(data_.find(id) == data_.end()) << "Inserting duplicate item";
78     data_[id] = data;
79   }
80 
Remove(KeyType id)81   void Remove(KeyType id) {
82     DCHECK(CalledOnValidThread());
83     typename HashTable::iterator i = data_.find(id);
84     if (i == data_.end()) {
85       NOTREACHED() << "Attempting to remove an item not in the list";
86       return;
87     }
88 
89     if (iteration_depth_ == 0) {
90       Releaser<OS, 0>::release(i->second);
91       data_.erase(i);
92     } else {
93       removed_ids_.insert(id);
94     }
95   }
96 
Clear()97   void Clear() {
98     DCHECK(CalledOnValidThread());
99     if (iteration_depth_ == 0) {
100       Releaser<OS, 0>::release_all(&data_);
101     } else {
102       for (typename HashTable::iterator i = data_.begin();
103            i != data_.end(); ++i)
104         removed_ids_.insert(i->first);
105     }
106   }
107 
IsEmpty()108   bool IsEmpty() const {
109     DCHECK(CalledOnValidThread());
110     return size() == 0u;
111   }
112 
Lookup(KeyType id)113   T* Lookup(KeyType id) const {
114     DCHECK(CalledOnValidThread());
115     typename HashTable::const_iterator i = data_.find(id);
116     if (i == data_.end())
117       return NULL;
118     return i->second;
119   }
120 
size()121   size_t size() const {
122     DCHECK(CalledOnValidThread());
123     return data_.size() - removed_ids_.size();
124   }
125 
126 #if defined(UNIT_TEST)
iteration_depth()127   int iteration_depth() const {
128     return iteration_depth_;
129   }
130 #endif  // defined(UNIT_TEST)
131 
132   // It is safe to remove elements from the map during iteration. All iterators
133   // will remain valid.
134   template<class ReturnType>
135   class Iterator {
136    public:
Iterator(IDMap<T,OS> * map)137     Iterator(IDMap<T, OS>* map)
138         : map_(map),
139           iter_(map_->data_.begin()) {
140       Init();
141     }
142 
Iterator(const Iterator & iter)143     Iterator(const Iterator& iter)
144         : map_(iter.map_),
145           iter_(iter.iter_) {
146       Init();
147     }
148 
149     const Iterator& operator=(const Iterator& iter) {
150       map_ = iter.map;
151       iter_ = iter.iter;
152       Init();
153       return *this;
154     }
155 
~Iterator()156     ~Iterator() {
157       DCHECK(map_->CalledOnValidThread());
158 
159       // We're going to decrement iteration depth. Make sure it's greater than
160       // zero so that it doesn't become negative.
161       DCHECK_LT(0, map_->iteration_depth_);
162 
163       if (--map_->iteration_depth_ == 0)
164         map_->Compact();
165     }
166 
IsAtEnd()167     bool IsAtEnd() const {
168       DCHECK(map_->CalledOnValidThread());
169       return iter_ == map_->data_.end();
170     }
171 
GetCurrentKey()172     KeyType GetCurrentKey() const {
173       DCHECK(map_->CalledOnValidThread());
174       return iter_->first;
175     }
176 
GetCurrentValue()177     ReturnType* GetCurrentValue() const {
178       DCHECK(map_->CalledOnValidThread());
179       return iter_->second;
180     }
181 
Advance()182     void Advance() {
183       DCHECK(map_->CalledOnValidThread());
184       ++iter_;
185       SkipRemovedEntries();
186     }
187 
188    private:
Init()189     void Init() {
190       DCHECK(map_->CalledOnValidThread());
191       ++map_->iteration_depth_;
192       SkipRemovedEntries();
193     }
194 
SkipRemovedEntries()195     void SkipRemovedEntries() {
196       while (iter_ != map_->data_.end() &&
197              map_->removed_ids_.find(iter_->first) !=
198              map_->removed_ids_.end()) {
199         ++iter_;
200       }
201     }
202 
203     IDMap<T, OS>* map_;
204     typename HashTable::const_iterator iter_;
205   };
206 
207   typedef Iterator<T> iterator;
208   typedef Iterator<const T> const_iterator;
209 
210  private:
211 
212   // The dummy parameter is there because C++ standard does not allow
213   // explicitly specialized templates inside classes
214   template<IDMapOwnershipSemantics OI, int dummy> struct Releaser {
releaseReleaser215     static inline void release(T* ptr) {}
release_allReleaser216     static inline void release_all(HashTable* table) {}
217   };
218 
219   template<int dummy> struct Releaser<IDMapOwnPointer, dummy> {
220     static inline void release(T* ptr) { delete ptr;}
221     static inline void release_all(HashTable* table) {
222       for (typename HashTable::iterator i = table->begin();
223            i != table->end(); ++i) {
224         delete i->second;
225       }
226       table->clear();
227     }
228   };
229 
230   void Compact() {
231     DCHECK_EQ(0, iteration_depth_);
232     for (std::set<KeyType>::const_iterator i = removed_ids_.begin();
233          i != removed_ids_.end(); ++i) {
234       Remove(*i);
235     }
236     removed_ids_.clear();
237   }
238 
239   // Keep track of how many iterators are currently iterating on us to safely
240   // handle removing items during iteration.
241   int iteration_depth_;
242 
243   // Keep set of IDs that should be removed after the outermost iteration has
244   // finished. This way we manage to not invalidate the iterator when an element
245   // is removed.
246   std::set<KeyType> removed_ids_;
247 
248   // The next ID that we will return from Add()
249   KeyType next_id_;
250 
251   HashTable data_;
252 
253   // See description above setter.
254   bool check_on_null_data_;
255 
256   DISALLOW_COPY_AND_ASSIGN(IDMap);
257 };
258 
259 #endif  // BASE_ID_MAP_H_
260