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 | |
31 | namespace kj { |
32 | |
33 | template <typename Key, typename Value> |
34 | class 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 | |
43 | public: |
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 | |
105 | private: |
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 | |
128 | template <typename Key, typename Value> |
129 | class 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 | |
135 | public: |
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 | |
204 | private: |
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 | |
231 | namespace _ { // private |
232 | |
233 | class HashSetCallbacks { |
234 | public: |
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 | |
246 | class TreeSetCallbacks { |
247 | public: |
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 | |
259 | template <typename Element> |
260 | class HashSet: public Table<Element, HashIndex<_::HashSetCallbacks>> { |
261 | // A simple hashtable-based set, using kj::hashCode() and operator==(). |
262 | |
263 | public: |
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 | |
272 | template <typename Element> |
273 | class TreeSet: public Table<Element, TreeIndex<_::TreeSetCallbacks>> { |
274 | // A simple b-tree-based set, using operator<() and operator==(). |
275 | |
276 | public: |
277 | // Everything is inherited. |
278 | }; |
279 | |
280 | // ======================================================================================= |
281 | // inline implementation details |
282 | |
283 | template <typename Key, typename Value> |
284 | void HashMap<Key, Value>::reserve(size_t size) { |
285 | table.reserve(size); |
286 | } |
287 | |
288 | template <typename Key, typename Value> |
289 | size_t HashMap<Key, Value>::size() const { |
290 | return table.size(); |
291 | } |
292 | template <typename Key, typename Value> |
293 | size_t HashMap<Key, Value>::capacity() const { |
294 | return table.capacity(); |
295 | } |
296 | template <typename Key, typename Value> |
297 | void HashMap<Key, Value>::clear() { |
298 | return table.clear(); |
299 | } |
300 | |
301 | template <typename Key, typename Value> |
302 | typename HashMap<Key, Value>::Entry* HashMap<Key, Value>::begin() { |
303 | return table.begin(); |
304 | } |
305 | template <typename Key, typename Value> |
306 | typename HashMap<Key, Value>::Entry* HashMap<Key, Value>::end() { |
307 | return table.end(); |
308 | } |
309 | template <typename Key, typename Value> |
310 | const typename HashMap<Key, Value>::Entry* HashMap<Key, Value>::begin() const { |
311 | return table.begin(); |
312 | } |
313 | template <typename Key, typename Value> |
314 | const typename HashMap<Key, Value>::Entry* HashMap<Key, Value>::end() const { |
315 | return table.end(); |
316 | } |
317 | |
318 | template <typename Key, typename Value> |
319 | typename 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 | |
323 | template <typename Key, typename Value> |
324 | template <typename Collection> |
325 | void HashMap<Key, Value>::insertAll(Collection&& collection) { |
326 | return table.insertAll(kj::fwd<Collection>(collection)); |
327 | } |
328 | |
329 | template <typename Key, typename Value> |
330 | template <typename UpdateFunc> |
331 | typename 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 | |
339 | template <typename Key, typename Value> |
340 | template <typename KeyLike> |
341 | kj::Maybe<Value&> HashMap<Key, Value>::find(KeyLike&& key) { |
342 | return table.find(key).map([](Entry& e) -> Value& { return e.value; }); |
343 | } |
344 | template <typename Key, typename Value> |
345 | template <typename KeyLike> |
346 | kj::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 | |
350 | template <typename Key, typename Value> |
351 | template <typename KeyLike, typename Func> |
352 | Value& HashMap<Key, Value>::findOrCreate(KeyLike&& key, Func&& createEntry) { |
353 | return table.findOrCreate(key, kj::fwd<Func>(createEntry)).value; |
354 | } |
355 | |
356 | template <typename Key, typename Value> |
357 | template <typename KeyLike> |
358 | bool HashMap<Key, Value>::erase(KeyLike&& key) { |
359 | return table.eraseMatch(key); |
360 | } |
361 | |
362 | template <typename Key, typename Value> |
363 | void HashMap<Key, Value>::erase(Entry& entry) { |
364 | table.erase(entry); |
365 | } |
366 | |
367 | template <typename Key, typename Value> |
368 | template <typename Predicate, typename> |
369 | size_t HashMap<Key, Value>::eraseAll(Predicate&& predicate) { |
370 | return table.eraseAll(kj::fwd<Predicate>(predicate)); |
371 | } |
372 | |
373 | // ----------------------------------------------------------------------------- |
374 | |
375 | template <typename Key, typename Value> |
376 | void TreeMap<Key, Value>::reserve(size_t size) { |
377 | table.reserve(size); |
378 | } |
379 | |
380 | template <typename Key, typename Value> |
381 | size_t TreeMap<Key, Value>::size() const { |
382 | return table.size(); |
383 | } |
384 | template <typename Key, typename Value> |
385 | size_t TreeMap<Key, Value>::capacity() const { |
386 | return table.capacity(); |
387 | } |
388 | template <typename Key, typename Value> |
389 | void TreeMap<Key, Value>::clear() { |
390 | return table.clear(); |
391 | } |
392 | |
393 | template <typename Key, typename Value> |
394 | auto TreeMap<Key, Value>::begin() { |
395 | return table.ordered().begin(); |
396 | } |
397 | template <typename Key, typename Value> |
398 | auto TreeMap<Key, Value>::end() { |
399 | return table.ordered().end(); |
400 | } |
401 | template <typename Key, typename Value> |
402 | auto TreeMap<Key, Value>::begin() const { |
403 | return table.ordered().begin(); |
404 | } |
405 | template <typename Key, typename Value> |
406 | auto TreeMap<Key, Value>::end() const { |
407 | return table.ordered().end(); |
408 | } |
409 | |
410 | template <typename Key, typename Value> |
411 | typename 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 | |
415 | template <typename Key, typename Value> |
416 | template <typename Collection> |
417 | void TreeMap<Key, Value>::insertAll(Collection&& collection) { |
418 | return table.insertAll(kj::fwd<Collection>(collection)); |
419 | } |
420 | |
421 | template <typename Key, typename Value> |
422 | template <typename UpdateFunc> |
423 | typename 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 | |
431 | template <typename Key, typename Value> |
432 | template <typename KeyLike> |
433 | kj::Maybe<Value&> TreeMap<Key, Value>::find(KeyLike&& key) { |
434 | return table.find(key).map([](Entry& e) -> Value& { return e.value; }); |
435 | } |
436 | template <typename Key, typename Value> |
437 | template <typename KeyLike> |
438 | kj::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 | |
442 | template <typename Key, typename Value> |
443 | template <typename KeyLike, typename Func> |
444 | Value& TreeMap<Key, Value>::findOrCreate(KeyLike&& key, Func&& createEntry) { |
445 | return table.findOrCreate(key, kj::fwd<Func>(createEntry)).value; |
446 | } |
447 | |
448 | template <typename Key, typename Value> |
449 | template <typename K1, typename K2> |
450 | auto TreeMap<Key, Value>::range(K1&& k1, K2&& k2) { |
451 | return table.range(kj::fwd<K1>(k1), kj::fwd<K2>(k2)); |
452 | } |
453 | template <typename Key, typename Value> |
454 | template <typename K1, typename K2> |
455 | auto TreeMap<Key, Value>::range(K1&& k1, K2&& k2) const { |
456 | return table.range(kj::fwd<K1>(k1), kj::fwd<K2>(k2)); |
457 | } |
458 | |
459 | template <typename Key, typename Value> |
460 | template <typename KeyLike> |
461 | bool TreeMap<Key, Value>::erase(KeyLike&& key) { |
462 | return table.eraseMatch(key); |
463 | } |
464 | |
465 | template <typename Key, typename Value> |
466 | void TreeMap<Key, Value>::erase(Entry& entry) { |
467 | table.erase(entry); |
468 | } |
469 | |
470 | template <typename Key, typename Value> |
471 | template <typename Predicate, typename> |
472 | size_t TreeMap<Key, Value>::eraseAll(Predicate&& predicate) { |
473 | return table.eraseAll(kj::fwd<Predicate>(predicate)); |
474 | } |
475 | |
476 | template <typename Key, typename Value> |
477 | template <typename K1, typename K2> |
478 | size_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 | |