blob: 4aa60789284173f84bfe23a373c9da094f222a73 [file] [log] [blame]
danzhc3be2d42019-04-25 07:47:41 -07001// 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
bnce46fe2e2021-04-30 08:00:30 -070016#ifndef QUICHE_COMMON_QUICHE_LINKED_HASH_MAP_H_
17#define QUICHE_COMMON_QUICHE_LINKED_HASH_MAP_H_
danzhc3be2d42019-04-25 07:47:41 -070018
QUICHE teambbce6032020-01-03 07:42:10 -080019#include <functional>
danzhc3be2d42019-04-25 07:47:41 -070020#include <list>
21#include <tuple>
22#include <type_traits>
23#include <utility>
24
vasilvv112eccd2021-02-04 13:54:15 -080025#include "absl/container/node_hash_map.h"
bnce266d932021-12-03 13:07:11 -080026#include "absl/hash/hash.h"
27#include "common/platform/api/quiche_export.h"
QUICHE team5be974e2020-12-29 18:35:24 -050028#include "common/platform/api/quiche_logging.h"
danzhc3be2d42019-04-25 07:47:41 -070029
30namespace 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
bnce266d932021-12-03 13:07:11 -080039// QUICHE_NO_EXPORT comments suppress erroneous presubmit failures.
40template <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
bnc4003b672021-12-06 15:05:08 -080044class QuicheLinkedHashMap { // QUICHE_NO_EXPORT
danzhc3be2d42019-04-25 07:47:41 -070045 private:
46 typedef std::list<std::pair<Key, Value>> ListType;
vasilvv112eccd2021-02-04 13:54:15 -080047 typedef absl::node_hash_map<Key, typename ListType::iterator, Hash, Eq>
QUICHE teambbce6032020-01-03 07:42:10 -080048 MapType;
danzhc3be2d42019-04-25 07:47:41 -070049
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
bnce46fe2e2021-04-30 08:00:30 -070059 QuicheLinkedHashMap() = default;
60 explicit QuicheLinkedHashMap(size_type bucket_count) : map_(bucket_count) {}
danzhc3be2d42019-04-25 07:47:41 -070061
bnce46fe2e2021-04-30 08:00:30 -070062 QuicheLinkedHashMap(const QuicheLinkedHashMap& other) = delete;
63 QuicheLinkedHashMap& operator=(const QuicheLinkedHashMap& other) = delete;
64 QuicheLinkedHashMap(QuicheLinkedHashMap&& other) = default;
65 QuicheLinkedHashMap& operator=(QuicheLinkedHashMap&& other) = default;
danzhc3be2d42019-04-25 07:47:41 -070066
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
vasilvvb38e0232021-02-02 15:20:07 -0800129 // map and list, a QUICHE_CHECK() error will occur.
danzhc3be2d42019-04-25 07:47:41 -0700130 iterator erase(iterator position) {
131 typename MapType::iterator found = map_.find(position->first);
vasilvvb38e0232021-02-02 15:20:07 -0800132 QUICHE_CHECK(found->second == position)
bnc12c0f702021-05-10 09:37:24 -0700133 << "Inconsistent iterator for map and list, or the iterator is "
134 "invalid.";
danzhc3be2d42019-04-25 07:47:41 -0700135
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) {
bnc12c0f702021-05-10 09:37:24 -0700179 return InsertInternal(pair);
danzhc3be2d42019-04-25 07:47:41 -0700180 }
181
182 // Inserts an element into the map
183 std::pair<iterator, bool> insert(std::pair<Key, Value>&& pair) {
bnc12c0f702021-05-10 09:37:24 -0700184 return InsertInternal(std::move(pair));
danzhc3be2d42019-04-25 07:47:41 -0700185 }
186
rchc83b6742019-07-01 17:41:32 -0700187 // Derive size_ from map_, as list::size might be O(N).
188 size_type size() const { return map_.size(); }
danzhc3be2d42019-04-25 07:47:41 -0700189
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
bnce46fe2e2021-04-30 08:00:30 -0700204 void swap(QuicheLinkedHashMap& other) {
danzhc3be2d42019-04-25 07:47:41 -0700205 map_.swap(other.map_);
206 list_.swap(other.list_);
207 }
208
209 private:
bnc12c0f702021-05-10 09:37:24 -0700210 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
danzhc3be2d42019-04-25 07:47:41 -0700228 // 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
bnce46fe2e2021-04-30 08:00:30 -0700237#endif // QUICHE_COMMON_QUICHE_LINKED_HASH_MAP_H_