base/id_map.h

   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:
  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_