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
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
56  // Sets whether Add should CHECK if passed in NULL data. Default is false.
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.
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
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
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
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
108  bool IsEmpty() const {
109    DCHECK(CalledOnValidThread());
110    return size() == 0u;
111  }
112
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
121  size_t size() const {
122    DCHECK(CalledOnValidThread());
123    return data_.size() - removed_ids_.size();
124  }
125
126#if defined(UNIT_TEST)
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:
137    Iterator(IDMap<T, OS>* map)
138        : map_(map),
139          iter_(map_->data_.begin()) {
140      Init();
141    }
142
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
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
167    bool IsAtEnd() const {
168      DCHECK(map_->CalledOnValidThread());
169      return iter_ == map_->data_.end();
170    }
171
172    KeyType GetCurrentKey() const {
173      DCHECK(map_->CalledOnValidThread());
174      return iter_->first;
175    }
176
177    ReturnType* GetCurrentValue() const {
178      DCHECK(map_->CalledOnValidThread());
179      return iter_->second;
180    }
181
182    void Advance() {
183      DCHECK(map_->CalledOnValidThread());
184      ++iter_;
185      SkipRemovedEntries();
186    }
187
188   private:
189    void Init() {
190      DCHECK(map_->CalledOnValidThread());
191      ++map_->iteration_depth_;
192      SkipRemovedEntries();
193    }
194
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 {
215    static inline void release(T* ptr) {}
216    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