base/id_map.h

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