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
19enum 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.
35template <typename T,
36          IDMapOwnershipSemantics OS = IDMapExternalPointer,
37          typename K = int32_t>
38class IDMap {
39 public:
40  using KeyType = K;
41
42 private:
43  typedef base::hash_map<KeyType, T*> HashTable;
44
45 public:
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
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.
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.
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
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
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.
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
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
134  bool IsEmpty() const {
135    DCHECK(sequence_checker_.CalledOnValidSequencedThread());
136    return size() == 0u;
137  }
138
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
147  size_t size() const {
148    DCHECK(sequence_checker_.CalledOnValidSequencedThread());
149    return data_.size() - removed_ids_.size();
150  }
151
152#if defined(UNIT_TEST)
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:
163    Iterator(IDMap<T, OS, K>* map)
164        : map_(map),
165          iter_(map_->data_.begin()) {
166      Init();
167    }
168
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
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
193    bool IsAtEnd() const {
194      DCHECK(map_->sequence_checker_.CalledOnValidSequencedThread());
195      return iter_ == map_->data_.end();
196    }
197
198    KeyType GetCurrentKey() const {
199      DCHECK(map_->sequence_checker_.CalledOnValidSequencedThread());
200      return iter_->first;
201    }
202
203    ReturnType* GetCurrentValue() const {
204      DCHECK(map_->sequence_checker_.CalledOnValidSequencedThread());
205      return iter_->second;
206    }
207
208    void Advance() {
209      DCHECK(map_->sequence_checker_.CalledOnValidSequencedThread());
210      ++iter_;
211      SkipRemovedEntries();
212    }
213
214   private:
215    void Init() {
216      DCHECK(map_->sequence_checker_.CalledOnValidSequencedThread());
217      ++map_->iteration_depth_;
218      SkipRemovedEntries();
219    }
220
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, K>* 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 {
241    static inline void release(T* ptr) {}
242    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