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