Home | History | Annotate | Download | only in base 
      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_
    260