danzh | c3be2d4 | 2019-04-25 07:47:41 -0700 | [diff] [blame] | 1 | // Copyright (c) 2019 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 point into the list and should be stable in the face of |
| 13 | // mutations, except for an iterator pointing to an element that was just |
| 14 | // deleted. |
| 15 | |
bnc | e46fe2e | 2021-04-30 08:00:30 -0700 | [diff] [blame] | 16 | #ifndef QUICHE_COMMON_QUICHE_LINKED_HASH_MAP_H_ |
| 17 | #define QUICHE_COMMON_QUICHE_LINKED_HASH_MAP_H_ |
danzh | c3be2d4 | 2019-04-25 07:47:41 -0700 | [diff] [blame] | 18 | |
QUICHE team | bbce603 | 2020-01-03 07:42:10 -0800 | [diff] [blame] | 19 | #include <functional> |
danzh | c3be2d4 | 2019-04-25 07:47:41 -0700 | [diff] [blame] | 20 | #include <list> |
| 21 | #include <tuple> |
| 22 | #include <type_traits> |
| 23 | #include <utility> |
| 24 | |
vasilvv | 112eccd | 2021-02-04 13:54:15 -0800 | [diff] [blame] | 25 | #include "absl/container/node_hash_map.h" |
bnc | e266d93 | 2021-12-03 13:07:11 -0800 | [diff] [blame] | 26 | #include "absl/hash/hash.h" |
| 27 | #include "common/platform/api/quiche_export.h" |
QUICHE team | 5be974e | 2020-12-29 18:35:24 -0500 | [diff] [blame] | 28 | #include "common/platform/api/quiche_logging.h" |
danzh | c3be2d4 | 2019-04-25 07:47:41 -0700 | [diff] [blame] | 29 | |
| 30 | namespace quiche { |
| 31 | |
| 32 | // This holds a list of pair<Key, Value> items. This list is what gets |
| 33 | // traversed, and it's iterators from this list that we return from |
| 34 | // begin/end/find. |
| 35 | // |
| 36 | // We also keep a set<list::iterator> for find. Since std::list is a |
| 37 | // doubly-linked list, the iterators should remain stable. |
| 38 | |
bnc | e266d93 | 2021-12-03 13:07:11 -0800 | [diff] [blame] | 39 | // QUICHE_NO_EXPORT comments suppress erroneous presubmit failures. |
| 40 | template <class Key, // QUICHE_NO_EXPORT |
| 41 | class Value, // QUICHE_NO_EXPORT |
| 42 | class Hash = absl::Hash<Key>, // QUICHE_NO_EXPORT |
| 43 | class Eq = std::equal_to<Key>> // QUICHE_NO_EXPORT |
bnc | 4003b67 | 2021-12-06 15:05:08 -0800 | [diff] [blame] | 44 | class QuicheLinkedHashMap { // QUICHE_NO_EXPORT |
danzh | c3be2d4 | 2019-04-25 07:47:41 -0700 | [diff] [blame] | 45 | private: |
| 46 | typedef std::list<std::pair<Key, Value>> ListType; |
vasilvv | 112eccd | 2021-02-04 13:54:15 -0800 | [diff] [blame] | 47 | typedef absl::node_hash_map<Key, typename ListType::iterator, Hash, Eq> |
QUICHE team | bbce603 | 2020-01-03 07:42:10 -0800 | [diff] [blame] | 48 | MapType; |
danzh | c3be2d4 | 2019-04-25 07:47:41 -0700 | [diff] [blame] | 49 | |
| 50 | public: |
| 51 | typedef typename ListType::iterator iterator; |
| 52 | typedef typename ListType::reverse_iterator reverse_iterator; |
| 53 | typedef typename ListType::const_iterator const_iterator; |
| 54 | typedef typename ListType::const_reverse_iterator const_reverse_iterator; |
| 55 | typedef typename MapType::key_type key_type; |
| 56 | typedef typename ListType::value_type value_type; |
| 57 | typedef typename ListType::size_type size_type; |
| 58 | |
bnc | e46fe2e | 2021-04-30 08:00:30 -0700 | [diff] [blame] | 59 | QuicheLinkedHashMap() = default; |
| 60 | explicit QuicheLinkedHashMap(size_type bucket_count) : map_(bucket_count) {} |
danzh | c3be2d4 | 2019-04-25 07:47:41 -0700 | [diff] [blame] | 61 | |
bnc | e46fe2e | 2021-04-30 08:00:30 -0700 | [diff] [blame] | 62 | QuicheLinkedHashMap(const QuicheLinkedHashMap& other) = delete; |
| 63 | QuicheLinkedHashMap& operator=(const QuicheLinkedHashMap& other) = delete; |
| 64 | QuicheLinkedHashMap(QuicheLinkedHashMap&& other) = default; |
| 65 | QuicheLinkedHashMap& operator=(QuicheLinkedHashMap&& other) = default; |
danzh | c3be2d4 | 2019-04-25 07:47:41 -0700 | [diff] [blame] | 66 | |
| 67 | // Returns an iterator to the first (insertion-ordered) element. Like a map, |
| 68 | // this can be dereferenced to a pair<Key, Value>. |
| 69 | iterator begin() { return list_.begin(); } |
| 70 | const_iterator begin() const { return list_.begin(); } |
| 71 | |
| 72 | // Returns an iterator beyond the last element. |
| 73 | iterator end() { return list_.end(); } |
| 74 | const_iterator end() const { return list_.end(); } |
| 75 | |
| 76 | // Returns an iterator to the last (insertion-ordered) element. Like a map, |
| 77 | // this can be dereferenced to a pair<Key, Value>. |
| 78 | reverse_iterator rbegin() { return list_.rbegin(); } |
| 79 | const_reverse_iterator rbegin() const { return list_.rbegin(); } |
| 80 | |
| 81 | // Returns an iterator beyond the first element. |
| 82 | reverse_iterator rend() { return list_.rend(); } |
| 83 | const_reverse_iterator rend() const { return list_.rend(); } |
| 84 | |
| 85 | // Front and back accessors common to many stl containers. |
| 86 | |
| 87 | // Returns the earliest-inserted element |
| 88 | const value_type& front() const { return list_.front(); } |
| 89 | |
| 90 | // Returns the earliest-inserted element. |
| 91 | value_type& front() { return list_.front(); } |
| 92 | |
| 93 | // Returns the most-recently-inserted element. |
| 94 | const value_type& back() const { return list_.back(); } |
| 95 | |
| 96 | // Returns the most-recently-inserted element. |
| 97 | value_type& back() { return list_.back(); } |
| 98 | |
| 99 | // Clears the map of all values. |
| 100 | void clear() { |
| 101 | map_.clear(); |
| 102 | list_.clear(); |
| 103 | } |
| 104 | |
| 105 | // Returns true iff the map is empty. |
| 106 | bool empty() const { return list_.empty(); } |
| 107 | |
| 108 | // Removes the first element from the list. |
| 109 | void pop_front() { erase(begin()); } |
| 110 | |
| 111 | // Erases values with the provided key. Returns the number of elements |
| 112 | // erased. In this implementation, this will be 0 or 1. |
| 113 | size_type erase(const Key& key) { |
| 114 | typename MapType::iterator found = map_.find(key); |
| 115 | if (found == map_.end()) { |
| 116 | return 0; |
| 117 | } |
| 118 | |
| 119 | list_.erase(found->second); |
| 120 | map_.erase(found); |
| 121 | |
| 122 | return 1; |
| 123 | } |
| 124 | |
| 125 | // Erases the item that 'position' points to. Returns an iterator that points |
| 126 | // to the item that comes immediately after the deleted item in the list, or |
| 127 | // end(). |
| 128 | // If the provided iterator is invalid or there is inconsistency between the |
vasilvv | b38e023 | 2021-02-02 15:20:07 -0800 | [diff] [blame] | 129 | // map and list, a QUICHE_CHECK() error will occur. |
danzh | c3be2d4 | 2019-04-25 07:47:41 -0700 | [diff] [blame] | 130 | iterator erase(iterator position) { |
| 131 | typename MapType::iterator found = map_.find(position->first); |
vasilvv | b38e023 | 2021-02-02 15:20:07 -0800 | [diff] [blame] | 132 | QUICHE_CHECK(found->second == position) |
bnc | 12c0f70 | 2021-05-10 09:37:24 -0700 | [diff] [blame] | 133 | << "Inconsistent iterator for map and list, or the iterator is " |
| 134 | "invalid."; |
danzh | c3be2d4 | 2019-04-25 07:47:41 -0700 | [diff] [blame] | 135 | |
| 136 | map_.erase(found); |
| 137 | return list_.erase(position); |
| 138 | } |
| 139 | |
| 140 | // Erases all the items in the range [first, last). Returns an iterator that |
| 141 | // points to the item that comes immediately after the last deleted item in |
| 142 | // the list, or end(). |
| 143 | iterator erase(iterator first, iterator last) { |
| 144 | while (first != last && first != end()) { |
| 145 | first = erase(first); |
| 146 | } |
| 147 | return first; |
| 148 | } |
| 149 | |
| 150 | // Finds the element with the given key. Returns an iterator to the |
| 151 | // value found, or to end() if the value was not found. Like a map, this |
| 152 | // iterator points to a pair<Key, Value>. |
| 153 | iterator find(const Key& key) { |
| 154 | typename MapType::iterator found = map_.find(key); |
| 155 | if (found == map_.end()) { |
| 156 | return end(); |
| 157 | } |
| 158 | return found->second; |
| 159 | } |
| 160 | |
| 161 | const_iterator find(const Key& key) const { |
| 162 | typename MapType::const_iterator found = map_.find(key); |
| 163 | if (found == map_.end()) { |
| 164 | return end(); |
| 165 | } |
| 166 | return found->second; |
| 167 | } |
| 168 | |
| 169 | bool contains(const Key& key) const { return find(key) != end(); } |
| 170 | |
| 171 | // Returns the value mapped to key, or an inserted iterator to that position |
| 172 | // in the map. |
| 173 | Value& operator[](const key_type& key) { |
| 174 | return (*((this->insert(std::make_pair(key, Value()))).first)).second; |
| 175 | } |
| 176 | |
| 177 | // Inserts an element into the map |
| 178 | std::pair<iterator, bool> insert(const std::pair<Key, Value>& pair) { |
bnc | 12c0f70 | 2021-05-10 09:37:24 -0700 | [diff] [blame] | 179 | return InsertInternal(pair); |
danzh | c3be2d4 | 2019-04-25 07:47:41 -0700 | [diff] [blame] | 180 | } |
| 181 | |
| 182 | // Inserts an element into the map |
| 183 | std::pair<iterator, bool> insert(std::pair<Key, Value>&& pair) { |
bnc | 12c0f70 | 2021-05-10 09:37:24 -0700 | [diff] [blame] | 184 | return InsertInternal(std::move(pair)); |
danzh | c3be2d4 | 2019-04-25 07:47:41 -0700 | [diff] [blame] | 185 | } |
| 186 | |
rch | c83b674 | 2019-07-01 17:41:32 -0700 | [diff] [blame] | 187 | // Derive size_ from map_, as list::size might be O(N). |
| 188 | size_type size() const { return map_.size(); } |
danzh | c3be2d4 | 2019-04-25 07:47:41 -0700 | [diff] [blame] | 189 | |
| 190 | template <typename... Args> |
| 191 | std::pair<iterator, bool> emplace(Args&&... args) { |
| 192 | ListType node_donor; |
| 193 | auto node_pos = |
| 194 | node_donor.emplace(node_donor.end(), std::forward<Args>(args)...); |
| 195 | const auto& k = node_pos->first; |
| 196 | auto ins = map_.insert({k, node_pos}); |
| 197 | if (!ins.second) { |
| 198 | return {ins.first->second, false}; |
| 199 | } |
| 200 | list_.splice(list_.end(), node_donor, node_pos); |
| 201 | return {ins.first->second, true}; |
| 202 | } |
| 203 | |
bnc | e46fe2e | 2021-04-30 08:00:30 -0700 | [diff] [blame] | 204 | void swap(QuicheLinkedHashMap& other) { |
danzh | c3be2d4 | 2019-04-25 07:47:41 -0700 | [diff] [blame] | 205 | map_.swap(other.map_); |
| 206 | list_.swap(other.list_); |
| 207 | } |
| 208 | |
| 209 | private: |
bnc | 12c0f70 | 2021-05-10 09:37:24 -0700 | [diff] [blame] | 210 | template <typename U> |
| 211 | std::pair<iterator, bool> InsertInternal(U&& pair) { |
| 212 | auto insert_result = map_.try_emplace(pair.first); |
| 213 | auto map_iter = insert_result.first; |
| 214 | |
| 215 | // If the map already contains this key, return a pair with an iterator to |
| 216 | // it, and false indicating that we didn't insert anything. |
| 217 | if (!insert_result.second) { |
| 218 | return {map_iter->second, false}; |
| 219 | } |
| 220 | |
| 221 | // Otherwise, insert into the list, and set value in map. |
| 222 | auto list_iter = list_.insert(list_.end(), std::forward<U>(pair)); |
| 223 | map_iter->second = list_iter; |
| 224 | |
| 225 | return {list_iter, true}; |
| 226 | } |
| 227 | |
danzh | c3be2d4 | 2019-04-25 07:47:41 -0700 | [diff] [blame] | 228 | // The map component, used for speedy lookups |
| 229 | MapType map_; |
| 230 | |
| 231 | // The list component, used for maintaining insertion order |
| 232 | ListType list_; |
| 233 | }; |
| 234 | |
| 235 | } // namespace quiche |
| 236 | |
bnc | e46fe2e | 2021-04-30 08:00:30 -0700 | [diff] [blame] | 237 | #endif // QUICHE_COMMON_QUICHE_LINKED_HASH_MAP_H_ |