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. 30template<class Key, class Value> 31class 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 values with the provided iterator. If the provided iterator is 128 // invalid or there is inconsistency between the map and list, a CHECK() error 129 // will occur. 130 void erase(iterator position) { 131 typename MapType::iterator found = map_.find(position->first); 132 CHECK(found->second == position) 133 << "Inconsisent iterator for map and list, or the iterator is invalid."; 134 135 list_.erase(position); 136 map_.erase(found); 137 } 138 139 // Erases values between first and last, not including last. 140 void erase(iterator first, iterator last) { 141 while (first != last && first != end()) { 142 erase(first++); 143 } 144 } 145 146 // Finds the element with the given key. Returns an iterator to the 147 // value found, or to end() if the value was not found. Like a map, this 148 // iterator points to a pair<Key, Value>. 149 iterator find(const Key& key) { 150 typename MapType::iterator found = map_.find(key); 151 if (found == map_.end()) { 152 return end(); 153 } 154 return found->second; 155 } 156 157 const_iterator find(const Key& key) const { 158 typename MapType::const_iterator found = map_.find(key); 159 if (found == map_.end()) { 160 return end(); 161 } 162 return found->second; 163 } 164 165 // Returns the bounds of a range that includes all the elements in the 166 // container with a key that compares equal to x. 167 std::pair<iterator, iterator> equal_range(const key_type& key) { 168 std::pair<typename MapType::iterator, typename MapType::iterator> eq_range = 169 map_.equal_range(key); 170 171 return std::make_pair(eq_range.first->second, eq_range.second->second); 172 } 173 174 std::pair<const_iterator, const_iterator> equal_range( 175 const key_type& key) const { 176 std::pair<typename MapType::const_iterator, 177 typename MapType::const_iterator> eq_range = 178 map_.equal_range(key); 179 const const_iterator& start_iter = eq_range.first != map_.end() ? 180 eq_range.first->second : end(); 181 const const_iterator& end_iter = eq_range.second != map_.end() ? 182 eq_range.second->second : end(); 183 184 return std::make_pair(start_iter, end_iter); 185 } 186 187 // Returns the value mapped to key, or an inserted iterator to that position 188 // in the map. 189 Value& operator[](const key_type& key) { 190 return (*((this->insert(std::make_pair(key, Value()))).first)).second; 191 } 192 193 // Inserts an element into the map 194 std::pair<iterator, bool> insert(const std::pair<Key, Value>& pair) { 195 // First make sure the map doesn't have a key with this value. If it does, 196 // return a pair with an iterator to it, and false indicating that we 197 // didn't insert anything. 198 typename MapType::iterator found = map_.find(pair.first); 199 if (found != map_.end()) return std::make_pair(found->second, false); 200 201 // Otherwise, insert into the list first. 202 list_.push_back(pair); 203 204 // Obtain an iterator to the newly added element. We do -- instead of - 205 // since list::iterator doesn't implement operator-(). 206 typename ListType::iterator last = list_.end(); 207 --last; 208 209 CHECK(map_.insert(std::make_pair(pair.first, last)).second) 210 << "Map and list are inconsistent"; 211 212 return std::make_pair(last, true); 213 } 214 215 size_type size() const { 216 return list_.size(); 217 } 218 219 void swap(linked_hash_map& other) { 220 map_.swap(other.map_); 221 list_.swap(other.list_); 222 } 223 224 private: 225 // The map component, used for speedy lookups 226 MapType map_; 227 228 // The list component, used for maintaining insertion order 229 ListType list_; 230}; 231 232#endif // UTIL_GTL_LINKED_HASH_MAP_H_ 233