net/base/linked_hash_map.h

   1 // Copyright (c) 2013 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 // This is a simplistic insertion-ordered map.  It behaves similarly to an STL
   6 // map, but only implements a small subset of the map's methods.  Internally, we
   7 // just keep a map and a list going in parallel.
   8 //
   9 // This class provides no thread safety guarantees, beyond what you would
  10 // normally see with std::list.
  11 //
  12 // Iterators should be stable in the face of mutations, except for an
  13 // iterator pointing to an element that was just deleted.
  14
  15 #ifndef UTIL_GTL_LINKED_HASH_MAP_H_
  16 #define UTIL_GTL_LINKED_HASH_MAP_H_
  17
  18 #include <list>
  19 #include <utility>
  20
  21 #include "base/containers/hash_tables.h"
  22 #include "base/logging.h"
  23
  24 // This holds a list of pair<Key, Value> items.  This list is what gets
  25 // traversed, and it's iterators from this list that we return from
  26 // begin/end/find.
  27 //
  28 // We also keep a map<Key, list::iterator> for find.  Since std::list is a
  29 // doubly-linked list, the iterators should remain stable.
  30 template<class Key, class Value>
  31 class linked_hash_map {
  32  private:
  33   typedef std::list<std::pair<Key, Value> > ListType;
  34   typedef base::hash_map<Key, typename ListType::iterator> MapType;
  35
  36  public:
  37   typedef typename ListType::iterator iterator;
  38   typedef typename ListType::reverse_iterator reverse_iterator;
  39   typedef typename ListType::const_iterator const_iterator;
  40   typedef typename ListType::const_reverse_iterator const_reverse_iterator;
  41   typedef typename MapType::key_type key_type;
  42   typedef typename ListType::value_type value_type;
  43   typedef typename ListType::size_type size_type;
  44
  45   linked_hash_map() : map_(), list_() {
  46   }
  47
  48   // Returns an iterator to the first (insertion-ordered) element.  Like a map,
  49   // this can be dereferenced to a pair<Key, Value>.
  50   iterator begin() {
  51     return list_.begin();
  52   }
  53   const_iterator begin() const {
  54     return list_.begin();
  55   }
  56
  57   // Returns an iterator beyond the last element.
  58   iterator end() {
  59     return list_.end();
  60   }
  61   const_iterator end() const {
  62     return list_.end();
  63   }
  64
  65   // Returns an iterator to the last (insertion-ordered) element.  Like a map,
  66   // this can be dereferenced to a pair<Key, Value>.
  67   reverse_iterator rbegin() {
  68     return list_.rbegin();
  69   }
  70   const_reverse_iterator rbegin() const {
  71     return list_.rbegin();
  72   }
  73
  74   // Returns an iterator beyond the first element.
  75   reverse_iterator rend() {
  76     return list_.rend();
  77   }
  78   const_reverse_iterator rend() const {
  79     return list_.rend();
  80   }
  81
  82   // Front and back accessors common to many stl containers.
  83
  84   // Returns the earliest-inserted element
  85   const value_type& front() const {
  86     return list_.front();
  87   }
  88
  89   // Returns the earliest-inserted element.
  90   value_type& front() {
  91     return list_.front();
  92   }
  93
  94   // Returns the most-recently-inserted element.
  95   const value_type& back() const {
  96     return list_.back();
  97   }
  98
  99   // Returns the most-recently-inserted element.
 100   value_type& back() {
 101     return list_.back();
 102   }
 103
 104   // Clears the map of all values.
 105   void clear() {
 106     map_.clear();
 107     list_.clear();
 108   }
 109
 110   // Returns true iff the map is empty.
 111   bool empty() const {
 112     return list_.empty();
 113   }
 114
 115   // Erases values with the provided key.  Returns the number of elements
 116   // erased.  In this implementation, this will be 0 or 1.
 117   size_type erase(const Key& key) {
 118     typename MapType::iterator found = map_.find(key);
 119     if (found == map_.end()) return 0;
 120
 121     list_.erase(found->second);
 122     map_.erase(found);
 123
 124     return 1;
 125   }
 126
 127   // Erases the item that 'position' points to. Returns an iterator that points
 128   // to the item that comes immediately after the deleted item in the list, or
 129   // end().
 130   // If the provided iterator is invalid or there is inconsistency between the
 131   // map and list, a CHECK() error will occur.
 132   iterator erase(iterator position) {
 133     typename MapType::iterator found = map_.find(position->first);
 134     CHECK(found->second == position)
 135         << "Inconsisent iterator for map and list, or the iterator is invalid.";
 136
 137     map_.erase(found);
 138     return list_.erase(position);
 139   }
 140
 141   // Erases all the items in the range [first, last).  Returns an iterator that
 142   // points to the item that comes immediately after the last deleted item in
 143   // the list, or end().
 144   iterator erase(iterator first, iterator last) {
 145     while (first != last && first != end()) {
 146       first = erase(first);
 147     }
 148     return first;
 149   }
 150
 151   // Finds the element with the given key.  Returns an iterator to the
 152   // value found, or to end() if the value was not found.  Like a map, this
 153   // iterator points to a pair<Key, Value>.
 154   iterator find(const Key& key) {
 155     typename MapType::iterator found = map_.find(key);
 156     if (found == map_.end()) {
 157       return end();
 158     }
 159     return found->second;
 160   }
 161
 162   const_iterator find(const Key& key) const {
 163     typename MapType::const_iterator found = map_.find(key);
 164     if (found == map_.end()) {
 165       return end();
 166     }
 167     return found->second;
 168   }
 169
 170   // Returns the bounds of a range that includes all the elements in the
 171   // container with a key that compares equal to x.
 172   std::pair<iterator, iterator> equal_range(const key_type& key) {
 173     std::pair<typename MapType::iterator, typename MapType::iterator> eq_range =
 174         map_.equal_range(key);
 175
 176     return std::make_pair(eq_range.first->second, eq_range.second->second);
 177   }
 178
 179   std::pair<const_iterator, const_iterator> equal_range(
 180       const key_type& key) const {
 181     std::pair<typename MapType::const_iterator,
 182         typename MapType::const_iterator> eq_range =
 183         map_.equal_range(key);
 184     const const_iterator& start_iter = eq_range.first != map_.end() ?
 185         eq_range.first->second : end();
 186     const const_iterator& end_iter = eq_range.second != map_.end() ?
 187         eq_range.second->second : end();
 188
 189     return std::make_pair(start_iter, end_iter);
 190   }
 191
 192   // Returns the value mapped to key, or an inserted iterator to that position
 193   // in the map.
 194   Value& operator[](const key_type& key) {
 195     return (*((this->insert(std::make_pair(key, Value()))).first)).second;
 196   }
 197
 198   // Inserts an element into the map
 199   std::pair<iterator, bool> insert(const std::pair<Key, Value>& pair) {
 200     // First make sure the map doesn't have a key with this value.  If it does,
 201     // return a pair with an iterator to it, and false indicating that we
 202     // didn't insert anything.
 203     typename MapType::iterator found = map_.find(pair.first);
 204     if (found != map_.end()) return std::make_pair(found->second, false);
 205
 206     // Otherwise, insert into the list first.
 207     list_.push_back(pair);
 208
 209     // Obtain an iterator to the newly added element.  We do -- instead of -
 210     // since list::iterator doesn't implement operator-().
 211     typename ListType::iterator last = list_.end();
 212     --last;
 213
 214     CHECK(map_.insert(std::make_pair(pair.first, last)).second)
 215         << "Map and list are inconsistent";
 216
 217     return std::make_pair(last, true);
 218   }
 219
 220   size_type size() const {
 221     return list_.size();
 222   }
 223
 224   void swap(linked_hash_map& other) {
 225     map_.swap(other.map_);
 226     list_.swap(other.list_);
 227   }
 228
 229  private:
 230   // The map component, used for speedy lookups
 231   MapType map_;
 232
 233   // The list component, used for maintaining insertion order
 234   ListType list_;
 235 };
 236
 237 #endif  // UTIL_GTL_LINKED_HASH_MAP_H_