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