Line data    Source code

       1             : /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
       2             : /* vim: set ts=8 sts=2 et sw=2 tw=80: */
       3             : // Copyright (c) 2006-2008 The Chromium Authors. All rights reserved.
       4             : // Use of this source code is governed by a BSD-style license that can be
       5             : // found in the LICENSE file.
       6             : 
       7             : #ifndef BASE_ID_MAP_H__
       8             : #define BASE_ID_MAP_H__
       9             : 
      10             : #include "base/basictypes.h"
      11             : #include "base/hash_tables.h"
      12             : #include "base/logging.h"
      13             : 
      14             : // This object maintains a list of IDs that can be quickly converted to
      15             : // objects. It is implemented as a hash table, optimized for
      16             : // relatively small data sets (in the common case, there will be exactly one
      17             : // item in the list).
      18             : //
      19             : // Items can be inserted into the container with arbitrary ID, but the caller
      20             : // must ensure they are unique. Inserting IDs and relying on automatically
      21             : // generated ones is not allowed because they can collide.
      22             : template<class T>
      23           0 : class IDMap {
      24             :  private:
      25             :   typedef base::hash_map<int32_t, T> HashTable;
      26             :   typedef typename HashTable::iterator iterator;
      27             : 
      28             :  public:
      29             :   // support const iterators over the items
      30             :   // Note, use iterator->first to get the ID, iterator->second to get the T*
      31             :   typedef typename HashTable::const_iterator const_iterator;
      32             : 
      33         120 :   IDMap() : next_id_(1) {
      34         120 :   }
      35             :   IDMap(const IDMap& other) : next_id_(other.next_id_),
      36             :                                         data_(other.data_) {
      37             :   }
      38             : 
      39           0 :   const_iterator begin() const {
      40           0 :     return data_.begin();
      41             :   }
      42           0 :   const_iterator end() const {
      43           0 :     return data_.end();
      44             :   }
      45             : 
      46             :   // Adds a view with an automatically generated unique ID. See AddWithID.
      47             :   int32_t Add(const T& data) {
      48             :     int32_t this_id = next_id_;
      49             :     DCHECK(data_.find(this_id) == data_.end()) << "Inserting duplicate item";
      50             :     data_[this_id] = data;
      51             :     next_id_++;
      52             :     return this_id;
      53             :   }
      54             : 
      55             :   // Adds a new data member with the specified ID. The ID must not be in
      56             :   // the list. The caller either must generate all unique IDs itself and use
      57             :   // this function, or allow this object to generate IDs and call Add. These
      58             :   // two methods may not be mixed, or duplicate IDs may be generated
      59         119 :   void AddWithID(const T& data, int32_t id) {
      60         119 :     DCHECK(data_.find(id) == data_.end()) << "Inserting duplicate item";
      61         119 :     data_[id] = data;
      62         119 :   }
      63             : 
      64          25 :   void Remove(int32_t id) {
      65          25 :     iterator i = data_.find(id);
      66          25 :     if (i == data_.end()) {
      67           0 :       NOTREACHED() << "Attempting to remove an item not in the list";
      68           0 :       return;
      69             :     }
      70          25 :     data_.erase(i);
      71             :   }
      72             : 
      73          25 :   void RemoveIfPresent(int32_t id) {
      74          25 :     iterator i = data_.find(id);
      75          25 :     if (i != data_.end()) {
      76          15 :       data_.erase(i);
      77             :     }
      78          25 :   }
      79             : 
      80           0 :   void ReplaceWithID(const T& data, int32_t id) {
      81           0 :     DCHECK(data_.find(id) != data_.end()) << "item doesn't exist";
      82           0 :     data_[id] = data;
      83           0 :   }
      84             : 
      85             :   bool IsEmpty() const {
      86             :     return data_.empty();
      87             :   }
      88             : 
      89           0 :   void Clear() {
      90           0 :     data_.clear();
      91           0 :   }
      92             : 
      93           0 :   bool HasData(const T& data) const {
      94             :     // XXX would like to use <algorithm> here ...
      95           0 :     for (const_iterator it = begin(); it != end(); ++it)
      96           0 :       if (data == it->second)
      97           0 :         return true;
      98           0 :     return false;
      99             :   }
     100             : 
     101         908 :   T Lookup(int32_t id) const {
     102         908 :     const_iterator i = data_.find(id);
     103         908 :     if (i == data_.end())
     104         299 :       return T();
     105         609 :     return i->second;
     106             :   }
     107             : 
     108             :   size_t size() const {
     109             :     return data_.size();
     110             :   }
     111             : 
     112             :  protected:
     113             :   // The next ID that we will return from Add()
     114             :   int32_t next_id_;
     115             : 
     116             :   HashTable data_;
     117             : };
     118             : 
     119             : #endif  // BASE_ID_MAP_H__