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 // Clears the map of all values. 83 void clear() { 84 map_.clear(); 85 list_.clear(); 86 } 87 88 // Returns true iff the map is empty. 89 bool empty() const { 90 return list_.empty(); 91 } 92 93 // Erases values with the provided key. Returns the number of elements 94 // erased. In this implementation, this will be 0 or 1. 95 size_type erase(const Key& key) { 96 typename MapType::iterator found = map_.find(key); 97 if (found == map_.end()) return 0; 98 99 list_.erase(found->second); 100 map_.erase(found); 101 102 return 1; 103 } 104 105 // Erases values with the provided iterator. If the provided iterator is 106 // invalid or there is inconsistency between the map and list, a CHECK() error 107 // will occur. 108 void erase(iterator position) { 109 typename MapType::iterator found = map_.find(position->first); 110 CHECK(found->second == position) 111 << "Inconsisent iterator for map and list, or the iterator is invalid."; 112 113 list_.erase(position); 114 map_.erase(found); 115 } 116 117 // Erases values between first and last, not including last. 118 void erase(iterator first, iterator last) { 119 while (first != last && first != end()) { 120 erase(first++); 121 } 122 } 123 124 // Finds the element with the given key. Returns an iterator to the 125 // value found, or to end() if the value was not found. Like a map, this 126 // iterator points to a pair<Key, Value>. 127 iterator find(const Key& key) { 128 typename MapType::iterator found = map_.find(key); 129 if (found == map_.end()) { 130 return end(); 131 } 132 return found->second; 133 } 134 135 const_iterator find(const Key& key) const { 136 typename MapType::const_iterator found = map_.find(key); 137 if (found == map_.end()) { 138 return end(); 139 } 140 return found->second; 141 } 142 143 // Returns the bounds of a range that includes all the elements in the 144 // container with a key that compares equal to x. 145 std::pair<iterator, iterator> equal_range(const key_type& key) { 146 std::pair<typename MapType::iterator, typename MapType::iterator> eq_range = 147 map_.equal_range(key); 148 149 return std::make_pair(eq_range.first->second, eq_range.second->second); 150 } 151 152 std::pair<const_iterator, const_iterator> equal_range( 153 const key_type& key) const { 154 std::pair<typename MapType::const_iterator, 155 typename MapType::const_iterator> eq_range = 156 map_.equal_range(key); 157 const const_iterator& start_iter = eq_range.first != map_.end() ? 158 eq_range.first->second : end(); 159 const const_iterator& end_iter = eq_range.second != map_.end() ? 160 eq_range.second->second : end(); 161 162 return std::make_pair(start_iter, end_iter); 163 } 164 165 // Returns the value mapped to key, or an inserted iterator to that position 166 // in the map. 167 Value& operator[](const key_type& key) { 168 return (*((this->insert(std::make_pair(key, Value()))).first)).second; 169 } 170 171 // Inserts an element into the map 172 std::pair<iterator, bool> insert(const std::pair<Key, Value>& pair) { 173 // First make sure the map doesn't have a key with this value. If it does, 174 // return a pair with an iterator to it, and false indicating that we 175 // didn't insert anything. 176 typename MapType::iterator found = map_.find(pair.first); 177 if (found != map_.end()) return std::make_pair(found->second, false); 178 179 // Otherwise, insert into the list first. 180 list_.push_back(pair); 181 182 // Obtain an iterator to the newly added element. We do -- instead of - 183 // since list::iterator doesn't implement operator-(). 184 typename ListType::iterator last = list_.end(); 185 --last; 186 187 CHECK(map_.insert(std::make_pair(pair.first, last)).second) 188 << "Map and list are inconsistent"; 189 190 return std::make_pair(last, true); 191 } 192 193 size_type size() const { 194 return list_.size(); 195 } 196 197 void swap(linked_hash_map& other) { 198 map_.swap(other.map_); 199 list_.swap(other.list_); 200 } 201 202 private: 203 // The map component, used for speedy lookups 204 MapType map_; 205 206 // The list component, used for maintaining insertion order 207 ListType list_; 208 }; 209 210 #endif // UTIL_GTL_LINKED_HASH_MAP_H_ 211
