michael@0: // Copyright (c) 2006-2008 The Chromium Authors. All rights reserved.
michael@0: // Use of this source code is governed by a BSD-style license that can be
michael@0: // found in the LICENSE file.
michael@0: 
michael@0: #ifndef BASE_ID_MAP_H__
michael@0: #define BASE_ID_MAP_H__
michael@0: 
michael@0: #include "base/basictypes.h"
michael@0: #include "base/hash_tables.h"
michael@0: #include "base/logging.h"
michael@0: 
michael@0: // This object maintains a list of IDs that can be quickly converted to
michael@0: // pointers to objects. It is implemented as a hash table, optimized for
michael@0: // relatively small data sets (in the common case, there will be exactly one
michael@0: // item in the list).
michael@0: //
michael@0: // Items can be inserted into the container with arbitrary ID, but the caller
michael@0: // must ensure they are unique. Inserting IDs and relying on automatically
michael@0: // generated ones is not allowed because they can collide.
michael@0: template<class T>
michael@0: class IDMap {
michael@0:  private:
michael@0:   typedef base::hash_map<int32_t, T*> HashTable;
michael@0:   typedef typename HashTable::iterator iterator;
michael@0: 
michael@0:  public:
michael@0:   // support const iterators over the items
michael@0:   // Note, use iterator->first to get the ID, iterator->second to get the T*
michael@0:   typedef typename HashTable::const_iterator const_iterator;
michael@0: 
michael@0:   IDMap() : next_id_(1) {
michael@0:   }
michael@0:   IDMap(const IDMap& other) : next_id_(other.next_id_),
michael@0:                                         data_(other.data_) {
michael@0:   }
michael@0: 
michael@0:   const_iterator begin() const {
michael@0:     return data_.begin();
michael@0:   }
michael@0:   const_iterator end() const {
michael@0:     return data_.end();
michael@0:   }
michael@0: 
michael@0:   // Adds a view with an automatically generated unique ID. See AddWithID.
michael@0:   int32_t Add(T* data) {
michael@0:     int32_t this_id = next_id_;
michael@0:     DCHECK(data_.find(this_id) == data_.end()) << "Inserting duplicate item";
michael@0:     data_[this_id] = data;
michael@0:     next_id_++;
michael@0:     return this_id;
michael@0:   }
michael@0: 
michael@0:   // Adds a new data member with the specified ID. The ID must not be in
michael@0:   // the list. The caller either must generate all unique IDs itself and use
michael@0:   // this function, or allow this object to generate IDs and call Add. These
michael@0:   // two methods may not be mixed, or duplicate IDs may be generated
michael@0:   void AddWithID(T* data, int32_t id) {
michael@0:     DCHECK(data_.find(id) == data_.end()) << "Inserting duplicate item";
michael@0:     data_[id] = data;
michael@0:   }
michael@0: 
michael@0:   void Remove(int32_t id) {
michael@0:     iterator i = data_.find(id);
michael@0:     if (i == data_.end()) {
michael@0:       NOTREACHED() << "Attempting to remove an item not in the list";
michael@0:       return;
michael@0:     }
michael@0:     data_.erase(i);
michael@0:   }
michael@0: 
michael@0:   bool IsEmpty() const {
michael@0:     return data_.empty();
michael@0:   }
michael@0: 
michael@0:   void Clear() {
michael@0:     data_.clear();
michael@0:   }
michael@0: 
michael@0:   bool HasData(const T* data) const {
michael@0:     // XXX would like to use <algorithm> here ...
michael@0:     for (const_iterator it = begin(); it != end(); ++it)
michael@0:       if (data == it->second)
michael@0:         return true;
michael@0:     return false;
michael@0:   }
michael@0: 
michael@0:   T* Lookup(int32_t id) const {
michael@0:     const_iterator i = data_.find(id);
michael@0:     if (i == data_.end())
michael@0:       return NULL;
michael@0:     return i->second;
michael@0:   }
michael@0: 
michael@0:   size_t size() const {
michael@0:     return data_.size();
michael@0:   }
michael@0: 
michael@0:  protected:
michael@0:   // The next ID that we will return from Add()
michael@0:   int32_t next_id_;
michael@0: 
michael@0:   HashTable data_;
michael@0: };
michael@0: 
michael@0: #endif  // BASE_ID_MAP_H__