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#pragma once
8
9#include <set>
10
11#include "base/basictypes.h"
12#include "base/hash_tables.h"
13#include "base/logging.h"
14#include "base/threading/non_thread_safe.h"
15
16// Ownership semantics - own pointer means the pointer is deleted in Remove()
17// & during destruction
18enum IDMapOwnershipSemantics {
19  IDMapExternalPointer,
20  IDMapOwnPointer
21};
22
23// This object maintains a list of IDs that can be quickly converted to
24// pointers to objects. It is implemented as a hash table, optimized for
25// relatively small data sets (in the common case, there will be exactly one
26// item in the list).
27//
28// Items can be inserted into the container with arbitrary ID, but the caller
29// must ensure they are unique. Inserting IDs and relying on automatically
30// generated ones is not allowed because they can collide.
31//
32// This class does not have a virtual destructor, do not inherit from it when
33// ownership semantics are set to own because pointers will leak.
34template<typename T, IDMapOwnershipSemantics OS = IDMapExternalPointer>
35class IDMap : public base::NonThreadSafe {
36 private:
37  typedef int32 KeyType;
38  typedef base::hash_map<KeyType, T*> HashTable;
39
40 public:
41  IDMap() : iteration_depth_(0), next_id_(1), check_on_null_data_(false) {
42    // A number of consumers of IDMap create it on one thread but always access
43    // it from a different, but consitent, thread post-construction.
44    DetachFromThread();
45  }
46
47  ~IDMap() {
48    // Many IDMap's are static, and hence will be destroyed on the main thread.
49    // However, all the accesses may take place on another thread, such as the
50    // IO thread. Detaching again to clean this up.
51    DetachFromThread();
52    Releaser<OS, 0>::release_all(&data_);
53  }
54
55  // Sets whether Add should CHECK if passed in NULL data. Default is false.
56  void set_check_on_null_data(bool value) { check_on_null_data_ = value; }
57
58  // Adds a view with an automatically generated unique ID. See AddWithID.
59  KeyType Add(T* data) {
60    DCHECK(CalledOnValidThread());
61    CHECK(!check_on_null_data_ || data);
62    KeyType this_id = next_id_;
63    DCHECK(data_.find(this_id) == data_.end()) << "Inserting duplicate item";
64    data_[this_id] = data;
65    next_id_++;
66    return this_id;
67  }
68
69  // Adds a new data member with the specified ID. The ID must not be in
70  // the list. The caller either must generate all unique IDs itself and use
71  // this function, or allow this object to generate IDs and call Add. These
72  // two methods may not be mixed, or duplicate IDs may be generated
73  void AddWithID(T* data, KeyType id) {
74    DCHECK(CalledOnValidThread());
75    CHECK(!check_on_null_data_ || data);
76    DCHECK(data_.find(id) == data_.end()) << "Inserting duplicate item";
77    data_[id] = data;
78  }
79
80  void Remove(KeyType id) {
81    DCHECK(CalledOnValidThread());
82    typename HashTable::iterator i = data_.find(id);
83    if (i == data_.end()) {
84      NOTREACHED() << "Attempting to remove an item not in the list";
85      return;
86    }
87
88    if (iteration_depth_ == 0) {
89      Releaser<OS, 0>::release(i->second);
90      data_.erase(i);
91    } else {
92      removed_ids_.insert(id);
93    }
94  }
95
96  bool IsEmpty() const {
97    DCHECK(CalledOnValidThread());
98    return size() == 0u;
99  }
100
101  T* Lookup(KeyType id) const {
102    DCHECK(CalledOnValidThread());
103    typename HashTable::const_iterator i = data_.find(id);
104    if (i == data_.end())
105      return NULL;
106    return i->second;
107  }
108
109  size_t size() const {
110    DCHECK(CalledOnValidThread());
111    return data_.size() - removed_ids_.size();
112  }
113
114  // It is safe to remove elements from the map during iteration. All iterators
115  // will remain valid.
116  template<class ReturnType>
117  class Iterator {
118   public:
119    Iterator(IDMap<T, OS>* map)
120        : map_(map),
121          iter_(map_->data_.begin()) {
122      DCHECK(map->CalledOnValidThread());
123      ++map_->iteration_depth_;
124      SkipRemovedEntries();
125    }
126
127    ~Iterator() {
128      DCHECK(map_->CalledOnValidThread());
129      if (--map_->iteration_depth_ == 0)
130        map_->Compact();
131    }
132
133    bool IsAtEnd() const {
134      DCHECK(map_->CalledOnValidThread());
135      return iter_ == map_->data_.end();
136    }
137
138    KeyType GetCurrentKey() const {
139      DCHECK(map_->CalledOnValidThread());
140      return iter_->first;
141    }
142
143    ReturnType* GetCurrentValue() const {
144      DCHECK(map_->CalledOnValidThread());
145      return iter_->second;
146    }
147
148    void Advance() {
149      DCHECK(map_->CalledOnValidThread());
150      ++iter_;
151      SkipRemovedEntries();
152    }
153
154   private:
155    void SkipRemovedEntries() {
156      while (iter_ != map_->data_.end() &&
157             map_->removed_ids_.find(iter_->first) !=
158             map_->removed_ids_.end()) {
159        ++iter_;
160      }
161    }
162
163    IDMap<T, OS>* map_;
164    typename HashTable::const_iterator iter_;
165  };
166
167  typedef Iterator<T> iterator;
168  typedef Iterator<const T> const_iterator;
169
170 private:
171
172  // The dummy parameter is there because C++ standard does not allow
173  // explicitly specialized templates inside classes
174  template<IDMapOwnershipSemantics OI, int dummy> struct Releaser {
175    static inline void release(T* ptr) {}
176    static inline void release_all(HashTable* table) {}
177  };
178
179  template<int dummy> struct Releaser<IDMapOwnPointer, dummy> {
180    static inline void release(T* ptr) { delete ptr;}
181    static inline void release_all(HashTable* table) {
182      for (typename HashTable::iterator i = table->begin();
183           i != table->end(); ++i) {
184        delete i->second;
185      }
186      table->clear();
187    }
188  };
189
190  void Compact() {
191    DCHECK_EQ(0, iteration_depth_);
192    for (std::set<KeyType>::const_iterator i = removed_ids_.begin();
193         i != removed_ids_.end(); ++i) {
194      Remove(*i);
195    }
196    removed_ids_.clear();
197  }
198
199  // Keep track of how many iterators are currently iterating on us to safely
200  // handle removing items during iteration.
201  int iteration_depth_;
202
203  // Keep set of IDs that should be removed after the outermost iteration has
204  // finished. This way we manage to not invalidate the iterator when an element
205  // is removed.
206  std::set<KeyType> removed_ids_;
207
208  // The next ID that we will return from Add()
209  KeyType next_id_;
210
211  HashTable data_;
212
213  // See description above setter.
214  bool check_on_null_data_;
215
216  DISALLOW_COPY_AND_ASSIGN(IDMap);
217};
218
219#endif  // BASE_ID_MAP_H_
220