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 #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
  18 enum 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.
  34 template<typename T, IDMapOwnershipSemantics OS = IDMapExternalPointer>
  35 class 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_