1// Copyright (c) 2018 Kenton Varda and contributors
2// Licensed under the MIT License:
3//
4// Permission is hereby granted, free of charge, to any person obtaining a copy
5// of this software and associated documentation files (the "Software"), to deal
6// in the Software without restriction, including without limitation the rights
7// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8// copies of the Software, and to permit persons to whom the Software is
9// furnished to do so, subject to the following conditions:
10//
11// The above copyright notice and this permission notice shall be included in
12// all copies or substantial portions of the Software.
13//
14// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
20// THE SOFTWARE.
21
22#pragma once
23
24#if defined(__GNUC__) && !KJ_HEADER_WARNINGS
25#pragma GCC system_header
26#endif
27
28#include "table.h"
29#include "hash.h"
30
31namespace kj {
32
33template <typename Key, typename Value>
34class HashMap {
35 // A key/value mapping backed by hashing.
36 //
37 // `Key` must be hashable (via a `.hashCode()` method or `KJ_HASHCODE()`; see `hash.h`) and must
38 // implement `operator==()`. Additionally, when performing lookups, you can use key types other
39 // than `Key` as long as the other type is also hashable (producing the same hash codes) and
40 // there is an `operator==` implementation with `Key` on the left and that other type on the
41 // right. For example, if the key type is `String`, you can pass `StringPtr` to `find()`.
42
43public:
44 void reserve(size_t size);
45 // Pre-allocates space for a map of the given size.
46
47 size_t size() const;
48 size_t capacity() const;
49 void clear();
50
51 struct Entry {
52 Key key;
53 Value value;
54 };
55
56 Entry* begin();
57 Entry* end();
58 const Entry* begin() const;
59 const Entry* end() const;
60 // Deterministic iteration. If you only ever insert(), iteration order will be insertion order.
61 // If you erase(), the erased element is swapped with the last element in the ordering.
62
63 Entry& insert(Key key, Value value);
64 // Inserts a new entry. Throws if the key already exists.
65
66 template <typename Collection>
67 void insertAll(Collection&& collection);
68 // Given an iterable collection of `Entry`s, inserts all of them into this map. If the
69 // input is an rvalue, the entries will be moved rather than copied.
70
71 template <typename UpdateFunc>
72 Entry& upsert(Key key, Value value, UpdateFunc&& update);
73 // Tries to insert a new entry. However, if a duplicate already exists (according to some index),
74 // then update(Value& existingValue, Value&& newValue) is called to modify the existing value.
75
76 template <typename KeyLike>
77 kj::Maybe<Value&> find(KeyLike&& key);
78 template <typename KeyLike>
79 kj::Maybe<const Value&> find(KeyLike&& key) const;
80 // Search for a matching key. The input does not have to be of type `Key`; it merely has to
81 // be something that the Hasher accepts.
82 //
83 // Note that the default hasher for String accepts StringPtr.
84
85 template <typename KeyLike, typename Func>
86 Value& findOrCreate(KeyLike&& key, Func&& createEntry);
87 // Like find() but if the key isn't present then call createEntry() to create the corresponding
88 // entry and insert it. createEntry() must return type `Entry`.
89
90 template <typename KeyLike>
91 bool erase(KeyLike&& key);
92 // Erase the entry with the matching key.
93 //
94 // WARNING: This invalidates all pointers and interators into the map. Use eraseAll() if you need
95 // to iterate and erase multiple entries.
96
97 void erase(Entry& entry);
98 // Erase an entry by reference.
99
100 template <typename Predicate,
101 typename = decltype(instance<Predicate>()(instance<Key&>(), instance<Value&>()))>
102 size_t eraseAll(Predicate&& predicate);
103 // Erase all values for which predicate(key, value) returns true. This scans over the entire map.
104
105private:
106 class Callbacks {
107 public:
108 inline const Key& keyForRow(const Entry& entry) const { return entry.key; }
109 inline Key& keyForRow(Entry& entry) const { return entry.key; }
110
111 template <typename KeyLike>
112 inline bool matches(Entry& e, KeyLike&& key) const {
113 return e.key == key;
114 }
115 template <typename KeyLike>
116 inline bool matches(const Entry& e, KeyLike&& key) const {
117 return e.key == key;
118 }
119 template <typename KeyLike>
120 inline bool hashCode(KeyLike&& key) const {
121 return kj::hashCode(key);
122 }
123 };
124
125 kj::Table<Entry, HashIndex<Callbacks>> table;
126};
127
128template <typename Key, typename Value>
129class TreeMap {
130 // A key/value mapping backed by a B-tree.
131 //
132 // `Key` must support `operator<` and `operator==` against other Keys, and against any type
133 // which you might want to pass to find() (with `Key` always on the left of the comparison).
134
135public:
136 void reserve(size_t size);
137 // Pre-allocates space for a map of the given size.
138
139 size_t size() const;
140 size_t capacity() const;
141 void clear();
142
143 struct Entry {
144 Key key;
145 Value value;
146 };
147
148 auto begin();
149 auto end();
150 auto begin() const;
151 auto end() const;
152 // Iteration is in sorted order by key.
153
154 Entry& insert(Key key, Value value);
155 // Inserts a new entry. Throws if the key already exists.
156
157 template <typename Collection>
158 void insertAll(Collection&& collection);
159 // Given an iterable collection of `Entry`s, inserts all of them into this map. If the
160 // input is an rvalue, the entries will be moved rather than copied.
161
162 template <typename UpdateFunc>
163 Entry& upsert(Key key, Value value, UpdateFunc&& update);
164 // Tries to insert a new entry. However, if a duplicate already exists (according to some index),
165 // then update(Value& existingValue, Value&& newValue) is called to modify the existing value.
166
167 template <typename KeyLike>
168 kj::Maybe<Value&> find(KeyLike&& key);
169 template <typename KeyLike>
170 kj::Maybe<const Value&> find(KeyLike&& key) const;
171 // Search for a matching key. The input does not have to be of type `Key`; it merely has to
172 // be something that can be compared against `Key`.
173
174 template <typename KeyLike, typename Func>
175 Value& findOrCreate(KeyLike&& key, Func&& createEntry);
176 // Like find() but if the key isn't present then call createEntry() to create the corresponding
177 // entry and insert it. createEntry() must return type `Entry`.
178
179 template <typename K1, typename K2>
180 auto range(K1&& k1, K2&& k2);
181 template <typename K1, typename K2>
182 auto range(K1&& k1, K2&& k2) const;
183 // Returns an iterable range of entries with keys between k1 (inclusive) and k2 (exclusive).
184
185 template <typename KeyLike>
186 bool erase(KeyLike&& key);
187 // Erase the entry with the matching key.
188 //
189 // WARNING: This invalidates all pointers and interators into the map. Use eraseAll() if you need
190 // to iterate and erase multiple entries.
191
192 void erase(Entry& entry);
193 // Erase an entry by reference.
194
195 template <typename Predicate,
196 typename = decltype(instance<Predicate>()(instance<Key&>(), instance<Value&>()))>
197 size_t eraseAll(Predicate&& predicate);
198 // Erase all values for which predicate(key, value) returns true. This scans over the entire map.
199
200 template <typename K1, typename K2>
201 size_t eraseRange(K1&& k1, K2&& k2);
202 // Erases all entries with keys between k1 (inclusive) and k2 (exclusive).
203
204private:
205 class Callbacks {
206 public:
207 inline const Key& keyForRow(const Entry& entry) const { return entry.key; }
208 inline Key& keyForRow(Entry& entry) const { return entry.key; }
209
210 template <typename KeyLike>
211 inline bool matches(Entry& e, KeyLike&& key) const {
212 return e.key == key;
213 }
214 template <typename KeyLike>
215 inline bool matches(const Entry& e, KeyLike&& key) const {
216 return e.key == key;
217 }
218 template <typename KeyLike>
219 inline bool isBefore(Entry& e, KeyLike&& key) const {
220 return e.key < key;
221 }
222 template <typename KeyLike>
223 inline bool isBefore(const Entry& e, KeyLike&& key) const {
224 return e.key < key;
225 }
226 };
227
228 kj::Table<Entry, TreeIndex<Callbacks>> table;
229};
230
231namespace _ { // private
232
233class HashSetCallbacks {
234public:
235 template <typename Row>
236 inline Row& keyForRow(Row& row) const { return row; }
237
238 template <typename T, typename U>
239 inline bool matches(T& a, U& b) const { return a == b; }
240 template <typename KeyLike>
241 inline bool hashCode(KeyLike&& key) const {
242 return kj::hashCode(key);
243 }
244};
245
246class TreeSetCallbacks {
247public:
248 template <typename Row>
249 inline Row& keyForRow(Row& row) const { return row; }
250
251 template <typename T, typename U>
252 inline bool matches(T& a, U& b) const { return a == b; }
253 template <typename T, typename U>
254 inline bool isBefore(T& a, U& b) const { return a < b; }
255};
256
257} // namespace _ (private)
258
259template <typename Element>
260class HashSet: public Table<Element, HashIndex<_::HashSetCallbacks>> {
261 // A simple hashtable-based set, using kj::hashCode() and operator==().
262
263public:
264 // Everything is inherited.
265
266 template <typename... Params>
267 inline bool contains(Params&&... params) const {
268 return this->find(kj::fwd<Params>(params)...) != nullptr;
269 }
270};
271
272template <typename Element>
273class TreeSet: public Table<Element, TreeIndex<_::TreeSetCallbacks>> {
274 // A simple b-tree-based set, using operator<() and operator==().
275
276public:
277 // Everything is inherited.
278};
279
280// =======================================================================================
281// inline implementation details
282
283template <typename Key, typename Value>
284void HashMap<Key, Value>::reserve(size_t size) {
285 table.reserve(size);
286}
287
288template <typename Key, typename Value>
289size_t HashMap<Key, Value>::size() const {
290 return table.size();
291}
292template <typename Key, typename Value>
293size_t HashMap<Key, Value>::capacity() const {
294 return table.capacity();
295}
296template <typename Key, typename Value>
297void HashMap<Key, Value>::clear() {
298 return table.clear();
299}
300
301template <typename Key, typename Value>
302typename HashMap<Key, Value>::Entry* HashMap<Key, Value>::begin() {
303 return table.begin();
304}
305template <typename Key, typename Value>
306typename HashMap<Key, Value>::Entry* HashMap<Key, Value>::end() {
307 return table.end();
308}
309template <typename Key, typename Value>
310const typename HashMap<Key, Value>::Entry* HashMap<Key, Value>::begin() const {
311 return table.begin();
312}
313template <typename Key, typename Value>
314const typename HashMap<Key, Value>::Entry* HashMap<Key, Value>::end() const {
315 return table.end();
316}
317
318template <typename Key, typename Value>
319typename HashMap<Key, Value>::Entry& HashMap<Key, Value>::insert(Key key, Value value) {
320 return table.insert(Entry { kj::mv(key), kj::mv(value) });
321}
322
323template <typename Key, typename Value>
324template <typename Collection>
325void HashMap<Key, Value>::insertAll(Collection&& collection) {
326 return table.insertAll(kj::fwd<Collection>(collection));
327}
328
329template <typename Key, typename Value>
330template <typename UpdateFunc>
331typename HashMap<Key, Value>::Entry& HashMap<Key, Value>::upsert(
332 Key key, Value value, UpdateFunc&& update) {
333 return table.upsert(Entry { kj::mv(key), kj::mv(value) },
334 [&](Entry& existingEntry, Entry&& newEntry) {
335 update(existingEntry.value, kj::mv(newEntry.value));
336 });
337}
338
339template <typename Key, typename Value>
340template <typename KeyLike>
341kj::Maybe<Value&> HashMap<Key, Value>::find(KeyLike&& key) {
342 return table.find(key).map([](Entry& e) -> Value& { return e.value; });
343}
344template <typename Key, typename Value>
345template <typename KeyLike>
346kj::Maybe<const Value&> HashMap<Key, Value>::find(KeyLike&& key) const {
347 return table.find(key).map([](const Entry& e) -> const Value& { return e.value; });
348}
349
350template <typename Key, typename Value>
351template <typename KeyLike, typename Func>
352Value& HashMap<Key, Value>::findOrCreate(KeyLike&& key, Func&& createEntry) {
353 return table.findOrCreate(key, kj::fwd<Func>(createEntry)).value;
354}
355
356template <typename Key, typename Value>
357template <typename KeyLike>
358bool HashMap<Key, Value>::erase(KeyLike&& key) {
359 return table.eraseMatch(key);
360}
361
362template <typename Key, typename Value>
363void HashMap<Key, Value>::erase(Entry& entry) {
364 table.erase(entry);
365}
366
367template <typename Key, typename Value>
368template <typename Predicate, typename>
369size_t HashMap<Key, Value>::eraseAll(Predicate&& predicate) {
370 return table.eraseAll(kj::fwd<Predicate>(predicate));
371}
372
373// -----------------------------------------------------------------------------
374
375template <typename Key, typename Value>
376void TreeMap<Key, Value>::reserve(size_t size) {
377 table.reserve(size);
378}
379
380template <typename Key, typename Value>
381size_t TreeMap<Key, Value>::size() const {
382 return table.size();
383}
384template <typename Key, typename Value>
385size_t TreeMap<Key, Value>::capacity() const {
386 return table.capacity();
387}
388template <typename Key, typename Value>
389void TreeMap<Key, Value>::clear() {
390 return table.clear();
391}
392
393template <typename Key, typename Value>
394auto TreeMap<Key, Value>::begin() {
395 return table.ordered().begin();
396}
397template <typename Key, typename Value>
398auto TreeMap<Key, Value>::end() {
399 return table.ordered().end();
400}
401template <typename Key, typename Value>
402auto TreeMap<Key, Value>::begin() const {
403 return table.ordered().begin();
404}
405template <typename Key, typename Value>
406auto TreeMap<Key, Value>::end() const {
407 return table.ordered().end();
408}
409
410template <typename Key, typename Value>
411typename TreeMap<Key, Value>::Entry& TreeMap<Key, Value>::insert(Key key, Value value) {
412 return table.insert(Entry { kj::mv(key), kj::mv(value) });
413}
414
415template <typename Key, typename Value>
416template <typename Collection>
417void TreeMap<Key, Value>::insertAll(Collection&& collection) {
418 return table.insertAll(kj::fwd<Collection>(collection));
419}
420
421template <typename Key, typename Value>
422template <typename UpdateFunc>
423typename TreeMap<Key, Value>::Entry& TreeMap<Key, Value>::upsert(
424 Key key, Value value, UpdateFunc&& update) {
425 return table.upsert(Entry { kj::mv(key), kj::mv(value) },
426 [&](Entry& existingEntry, Entry&& newEntry) {
427 update(existingEntry.value, kj::mv(newEntry.value));
428 });
429}
430
431template <typename Key, typename Value>
432template <typename KeyLike>
433kj::Maybe<Value&> TreeMap<Key, Value>::find(KeyLike&& key) {
434 return table.find(key).map([](Entry& e) -> Value& { return e.value; });
435}
436template <typename Key, typename Value>
437template <typename KeyLike>
438kj::Maybe<const Value&> TreeMap<Key, Value>::find(KeyLike&& key) const {
439 return table.find(key).map([](const Entry& e) -> const Value& { return e.value; });
440}
441
442template <typename Key, typename Value>
443template <typename KeyLike, typename Func>
444Value& TreeMap<Key, Value>::findOrCreate(KeyLike&& key, Func&& createEntry) {
445 return table.findOrCreate(key, kj::fwd<Func>(createEntry)).value;
446}
447
448template <typename Key, typename Value>
449template <typename K1, typename K2>
450auto TreeMap<Key, Value>::range(K1&& k1, K2&& k2) {
451 return table.range(kj::fwd<K1>(k1), kj::fwd<K2>(k2));
452}
453template <typename Key, typename Value>
454template <typename K1, typename K2>
455auto TreeMap<Key, Value>::range(K1&& k1, K2&& k2) const {
456 return table.range(kj::fwd<K1>(k1), kj::fwd<K2>(k2));
457}
458
459template <typename Key, typename Value>
460template <typename KeyLike>
461bool TreeMap<Key, Value>::erase(KeyLike&& key) {
462 return table.eraseMatch(key);
463}
464
465template <typename Key, typename Value>
466void TreeMap<Key, Value>::erase(Entry& entry) {
467 table.erase(entry);
468}
469
470template <typename Key, typename Value>
471template <typename Predicate, typename>
472size_t TreeMap<Key, Value>::eraseAll(Predicate&& predicate) {
473 return table.eraseAll(kj::fwd<Predicate>(predicate));
474}
475
476template <typename Key, typename Value>
477template <typename K1, typename K2>
478size_t TreeMap<Key, Value>::eraseRange(K1&& k1, K2&& k2) {
479 return table.eraseRange(kj::fwd<K1>(k1), kj::fwd<K2>(k2));
480}
481
482} // namespace kj
483