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