Mercurial > repos > rliterman > csp2

comparison CSP2/CSP2_env/env-d9b9114564458d9d-741b3de822f2aaca6c6caa4325c4afce/include/kj/map.h @ 69:33d812a61356

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
planemo upload commit 2e9511a184a1ca667c7be0c6321a36dc4e3d116d
author jpayne
date Tue, 18 Mar 2025 17:55:14 -0400
parents
children
comparison
equal deleted inserted replaced
67:0e9998148a16 69:33d812a61356
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 #include "table.h"
25 #include "hash.h"
26
27 KJ_BEGIN_HEADER
28
29 namespace kj {
30
31 template <typename Key, typename Value>
32 class HashMap {
33 // A key/value mapping backed by hashing.
34 //
35 // `Key` must be hashable (via a `.hashCode()` method or `KJ_HASHCODE()`; see `hash.h`) and must
36 // implement `operator==()`. Additionally, when performing lookups, you can use key types other
37 // than `Key` as long as the other type is also hashable (producing the same hash codes) and
38 // there is an `operator==` implementation with `Key` on the left and that other type on the
39 // right. For example, if the key type is `String`, you can pass `StringPtr` to `find()`.
40
41 public:
42 void reserve(size_t size);
43 // Pre-allocates space for a map of the given size.
44
45 size_t size() const;
46 size_t capacity() const;
47 void clear();
48
49 struct Entry {
50 Key key;
51 Value value;
52 };
53
54 Entry* begin();
55 Entry* end();
56 const Entry* begin() const;
57 const Entry* end() const;
58 // Deterministic iteration. If you only ever insert(), iteration order will be insertion order.
59 // If you erase(), the erased element is swapped with the last element in the ordering.
60
61 Entry& insert(Key key, Value value);
62 // Inserts a new entry. Throws if the key already exists.
63
64 template <typename Collection>
65 void insertAll(Collection&& collection);
66 // Given an iterable collection of `Entry`s, inserts all of them into this map. If the
67 // input is an rvalue, the entries will be moved rather than copied.
68
69 template <typename UpdateFunc>
70 Entry& upsert(Key key, Value value, UpdateFunc&& update);
71 Entry& upsert(Key key, Value value);
72 // Tries to insert a new entry. However, if a duplicate already exists (according to some index),
73 // then update(Value& existingValue, Value&& newValue) is called to modify the existing value.
74 // If no function is provided, the default is to simply replace the value (but not the key).
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 kj::Maybe<Entry&> findEntry(KeyLike&& key);
92 template <typename KeyLike>
93 kj::Maybe<const Entry&> findEntry(KeyLike&& key) const;
94 template <typename KeyLike, typename Func>
95 Entry& findOrCreateEntry(KeyLike&& key, Func&& createEntry);
96 // Sometimes you need to see the whole matching Entry, not just the Value.
97
98 template <typename KeyLike>
99 bool erase(KeyLike&& key);
100 // Erase the entry with the matching key.
101 //
102 // WARNING: This invalidates all pointers and iterators into the map. Use eraseAll() if you need
103 // to iterate and erase multiple entries.
104
105 void erase(Entry& entry);
106 // Erase an entry by reference.
107
108 Entry release(Entry& row);
109 // Erase an entry and return its content by move.
110
111 template <typename Predicate,
112 typename = decltype(instance<Predicate>()(instance<Key&>(), instance<Value&>()))>
113 size_t eraseAll(Predicate&& predicate);
114 // Erase all values for which predicate(key, value) returns true. This scans over the entire map.
115
116 private:
117 class Callbacks {
118 public:
119 inline const Key& keyForRow(const Entry& entry) const { return entry.key; }
120 inline Key& keyForRow(Entry& entry) const { return entry.key; }
121
122 template <typename KeyLike>
123 inline bool matches(Entry& e, KeyLike&& key) const {
124 return e.key == key;
125 }
126 template <typename KeyLike>
127 inline bool matches(const Entry& e, KeyLike&& key) const {
128 return e.key == key;
129 }
130 template <typename KeyLike>
131 inline auto hashCode(KeyLike&& key) const {
132 return kj::hashCode(key);
133 }
134 };
135
136 kj::Table<Entry, HashIndex<Callbacks>> table;
137 };
138
139 template <typename Key, typename Value>
140 class TreeMap {
141 // A key/value mapping backed by a B-tree.
142 //
143 // `Key` must support `operator<` and `operator==` against other Keys, and against any type
144 // which you might want to pass to find() (with `Key` always on the left of the comparison).
145
146 public:
147 void reserve(size_t size);
148 // Pre-allocates space for a map of the given size.
149
150 size_t size() const;
151 size_t capacity() const;
152 void clear();
153
154 struct Entry {
155 Key key;
156 Value value;
157 };
158
159 auto begin();
160 auto end();
161 auto begin() const;
162 auto end() const;
163 // Iteration is in sorted order by key.
164
165 Entry& insert(Key key, Value value);
166 // Inserts a new entry. Throws if the key already exists.
167
168 template <typename Collection>
169 void insertAll(Collection&& collection);
170 // Given an iterable collection of `Entry`s, inserts all of them into this map. If the
171 // input is an rvalue, the entries will be moved rather than copied.
172
173 template <typename UpdateFunc>
174 Entry& upsert(Key key, Value value, UpdateFunc&& update);
175 Entry& upsert(Key key, Value value);
176 // Tries to insert a new entry. However, if a duplicate already exists (according to some index),
177 // then update(Value& existingValue, Value&& newValue) is called to modify the existing value.
178 // If no function is provided, the default is to simply replace the value (but not the key).
179
180 template <typename KeyLike>
181 kj::Maybe<Value&> find(KeyLike&& key);
182 template <typename KeyLike>
183 kj::Maybe<const Value&> find(KeyLike&& key) const;
184 // Search for a matching key. The input does not have to be of type `Key`; it merely has to
185 // be something that can be compared against `Key`.
186
187 template <typename KeyLike, typename Func>
188 Value& findOrCreate(KeyLike&& key, Func&& createEntry);
189 // Like find() but if the key isn't present then call createEntry() to create the corresponding
190 // entry and insert it. createEntry() must return type `Entry`.
191
192 template <typename KeyLike>
193 kj::Maybe<Entry&> findEntry(KeyLike&& key);
194 template <typename KeyLike>
195 kj::Maybe<const Entry&> findEntry(KeyLike&& key) const;
196 template <typename KeyLike, typename Func>
197 Entry& findOrCreateEntry(KeyLike&& key, Func&& createEntry);
198 // Sometimes you need to see the whole matching Entry, not just the Value.
199
200 template <typename K1, typename K2>
201 auto range(K1&& k1, K2&& k2);
202 template <typename K1, typename K2>
203 auto range(K1&& k1, K2&& k2) const;
204 // Returns an iterable range of entries with keys between k1 (inclusive) and k2 (exclusive).
205
206 template <typename KeyLike>
207 bool erase(KeyLike&& key);
208 // Erase the entry with the matching key.
209 //
210 // WARNING: This invalidates all pointers and iterators into the map. Use eraseAll() if you need
211 // to iterate and erase multiple entries.
212
213 void erase(Entry& entry);
214 // Erase an entry by reference.
215
216 Entry release(Entry& row);
217 // Erase an entry and return its content by move.
218
219 template <typename Predicate,
220 typename = decltype(instance<Predicate>()(instance<Key&>(), instance<Value&>()))>
221 size_t eraseAll(Predicate&& predicate);
222 // Erase all values for which predicate(key, value) returns true. This scans over the entire map.
223
224 template <typename K1, typename K2>
225 size_t eraseRange(K1&& k1, K2&& k2);
226 // Erases all entries with keys between k1 (inclusive) and k2 (exclusive).
227
228 private:
229 class Callbacks {
230 public:
231 inline const Key& keyForRow(const Entry& entry) const { return entry.key; }
232 inline Key& keyForRow(Entry& entry) const { return entry.key; }
233
234 template <typename KeyLike>
235 inline bool matches(Entry& e, KeyLike&& key) const {
236 return e.key == key;
237 }
238 template <typename KeyLike>
239 inline bool matches(const Entry& e, KeyLike&& key) const {
240 return e.key == key;
241 }
242 template <typename KeyLike>
243 inline bool isBefore(Entry& e, KeyLike&& key) const {
244 return e.key < key;
245 }
246 template <typename KeyLike>
247 inline bool isBefore(const Entry& e, KeyLike&& key) const {
248 return e.key < key;
249 }
250 };
251
252 kj::Table<Entry, TreeIndex<Callbacks>> table;
253 };
254
255 namespace _ { // private
256
257 class HashSetCallbacks {
258 public:
259 template <typename Row>
260 inline Row& keyForRow(Row& row) const { return row; }
261
262 template <typename T, typename U>
263 inline bool matches(T& a, U& b) const { return a == b; }
264 template <typename KeyLike>
265 inline auto hashCode(KeyLike&& key) const {
266 return kj::hashCode(key);
267 }
268 };
269
270 class TreeSetCallbacks {
271 public:
272 template <typename Row>
273 inline Row& keyForRow(Row& row) const { return row; }
274
275 template <typename T, typename U>
276 inline bool matches(T& a, U& b) const { return a == b; }
277 template <typename T, typename U>
278 inline bool isBefore(T& a, U& b) const { return a < b; }
279 };
280
281 } // namespace _ (private)
282
283 template <typename Element>
284 class HashSet: public Table<Element, HashIndex<_::HashSetCallbacks>> {
285 // A simple hashtable-based set, using kj::hashCode() and operator==().
286
287 public:
288 // Everything is inherited.
289
290 template <typename... Params>
291 inline bool contains(Params&&... params) const {
292 return this->find(kj::fwd<Params>(params)...) != nullptr;
293 }
294 };
295
296 template <typename Element>
297 class TreeSet: public Table<Element, TreeIndex<_::TreeSetCallbacks>> {
298 // A simple b-tree-based set, using operator<() and operator==().
299
300 public:
301 // Everything is inherited.
302 };
303
304 // =======================================================================================
305 // inline implementation details
306
307 template <typename Key, typename Value>
308 void HashMap<Key, Value>::reserve(size_t size) {
309 table.reserve(size);
310 }
311
312 template <typename Key, typename Value>
313 size_t HashMap<Key, Value>::size() const {
314 return table.size();
315 }
316 template <typename Key, typename Value>
317 size_t HashMap<Key, Value>::capacity() const {
318 return table.capacity();
319 }
320 template <typename Key, typename Value>
321 void HashMap<Key, Value>::clear() {
322 return table.clear();
323 }
324
325 template <typename Key, typename Value>
326 typename HashMap<Key, Value>::Entry* HashMap<Key, Value>::begin() {
327 return table.begin();
328 }
329 template <typename Key, typename Value>
330 typename HashMap<Key, Value>::Entry* HashMap<Key, Value>::end() {
331 return table.end();
332 }
333 template <typename Key, typename Value>
334 const typename HashMap<Key, Value>::Entry* HashMap<Key, Value>::begin() const {
335 return table.begin();
336 }
337 template <typename Key, typename Value>
338 const typename HashMap<Key, Value>::Entry* HashMap<Key, Value>::end() const {
339 return table.end();
340 }
341
342 template <typename Key, typename Value>
343 typename HashMap<Key, Value>::Entry& HashMap<Key, Value>::insert(Key key, Value value) {
344 return table.insert(Entry { kj::mv(key), kj::mv(value) });
345 }
346
347 template <typename Key, typename Value>
348 template <typename Collection>
349 void HashMap<Key, Value>::insertAll(Collection&& collection) {
350 return table.insertAll(kj::fwd<Collection>(collection));
351 }
352
353 template <typename Key, typename Value>
354 template <typename UpdateFunc>
355 typename HashMap<Key, Value>::Entry& HashMap<Key, Value>::upsert(
356 Key key, Value value, UpdateFunc&& update) {
357 return table.upsert(Entry { kj::mv(key), kj::mv(value) },
358 [&](Entry& existingEntry, Entry&& newEntry) {
359 update(existingEntry.value, kj::mv(newEntry.value));
360 });
361 }
362
363 template <typename Key, typename Value>
364 typename HashMap<Key, Value>::Entry& HashMap<Key, Value>::upsert(
365 Key key, Value value) {
366 return table.upsert(Entry { kj::mv(key), kj::mv(value) },
367 [&](Entry& existingEntry, Entry&& newEntry) {
368 existingEntry.value = kj::mv(newEntry.value);
369 });
370 }
371
372 template <typename Key, typename Value>
373 template <typename KeyLike>
374 kj::Maybe<Value&> HashMap<Key, Value>::find(KeyLike&& key) {
375 return table.find(key).map([](Entry& e) -> Value& { return e.value; });
376 }
377 template <typename Key, typename Value>
378 template <typename KeyLike>
379 kj::Maybe<const Value&> HashMap<Key, Value>::find(KeyLike&& key) const {
380 return table.find(key).map([](const Entry& e) -> const Value& { return e.value; });
381 }
382
383 template <typename Key, typename Value>
384 template <typename KeyLike, typename Func>
385 Value& HashMap<Key, Value>::findOrCreate(KeyLike&& key, Func&& createEntry) {
386 return table.findOrCreate(key, kj::fwd<Func>(createEntry)).value;
387 }
388
389 template <typename Key, typename Value>
390 template <typename KeyLike>
391 kj::Maybe<typename HashMap<Key, Value>::Entry&>
392 HashMap<Key, Value>::findEntry(KeyLike&& key) {
393 return table.find(kj::fwd<KeyLike>(key));
394 }
395 template <typename Key, typename Value>
396 template <typename KeyLike>
397 kj::Maybe<const typename HashMap<Key, Value>::Entry&>
398 HashMap<Key, Value>::findEntry(KeyLike&& key) const {
399 return table.find(kj::fwd<KeyLike>(key));
400 }
401 template <typename Key, typename Value>
402 template <typename KeyLike, typename Func>
403 typename HashMap<Key, Value>::Entry&
404 HashMap<Key, Value>::findOrCreateEntry(KeyLike&& key, Func&& createEntry) {
405 return table.findOrCreate(kj::fwd<KeyLike>(key), kj::fwd<Func>(createEntry));
406 }
407
408 template <typename Key, typename Value>
409 template <typename KeyLike>
410 bool HashMap<Key, Value>::erase(KeyLike&& key) {
411 return table.eraseMatch(key);
412 }
413
414 template <typename Key, typename Value>
415 void HashMap<Key, Value>::erase(Entry& entry) {
416 table.erase(entry);
417 }
418
419 template <typename Key, typename Value>
420 typename HashMap<Key, Value>::Entry HashMap<Key, Value>::release(Entry& entry) {
421 return table.release(entry);
422 }
423
424 template <typename Key, typename Value>
425 template <typename Predicate, typename>
426 size_t HashMap<Key, Value>::eraseAll(Predicate&& predicate) {
427 return table.eraseAll([&](Entry& entry) {
428 return predicate(entry.key, entry.value);
429 });
430 }
431
432 // -----------------------------------------------------------------------------
433
434 template <typename Key, typename Value>
435 void TreeMap<Key, Value>::reserve(size_t size) {
436 table.reserve(size);
437 }
438
439 template <typename Key, typename Value>
440 size_t TreeMap<Key, Value>::size() const {
441 return table.size();
442 }
443 template <typename Key, typename Value>
444 size_t TreeMap<Key, Value>::capacity() const {
445 return table.capacity();
446 }
447 template <typename Key, typename Value>
448 void TreeMap<Key, Value>::clear() {
449 return table.clear();
450 }
451
452 template <typename Key, typename Value>
453 auto TreeMap<Key, Value>::begin() {
454 return table.ordered().begin();
455 }
456 template <typename Key, typename Value>
457 auto TreeMap<Key, Value>::end() {
458 return table.ordered().end();
459 }
460 template <typename Key, typename Value>
461 auto TreeMap<Key, Value>::begin() const {
462 return table.ordered().begin();
463 }
464 template <typename Key, typename Value>
465 auto TreeMap<Key, Value>::end() const {
466 return table.ordered().end();
467 }
468
469 template <typename Key, typename Value>
470 typename TreeMap<Key, Value>::Entry& TreeMap<Key, Value>::insert(Key key, Value value) {
471 return table.insert(Entry { kj::mv(key), kj::mv(value) });
472 }
473
474 template <typename Key, typename Value>
475 template <typename Collection>
476 void TreeMap<Key, Value>::insertAll(Collection&& collection) {
477 return table.insertAll(kj::fwd<Collection>(collection));
478 }
479
480 template <typename Key, typename Value>
481 template <typename UpdateFunc>
482 typename TreeMap<Key, Value>::Entry& TreeMap<Key, Value>::upsert(
483 Key key, Value value, UpdateFunc&& update) {
484 return table.upsert(Entry { kj::mv(key), kj::mv(value) },
485 [&](Entry& existingEntry, Entry&& newEntry) {
486 update(existingEntry.value, kj::mv(newEntry.value));
487 });
488 }
489
490 template <typename Key, typename Value>
491 typename TreeMap<Key, Value>::Entry& TreeMap<Key, Value>::upsert(
492 Key key, Value value) {
493 return table.upsert(Entry { kj::mv(key), kj::mv(value) },
494 [&](Entry& existingEntry, Entry&& newEntry) {
495 existingEntry.value = kj::mv(newEntry.value);
496 });
497 }
498
499 template <typename Key, typename Value>
500 template <typename KeyLike>
501 kj::Maybe<Value&> TreeMap<Key, Value>::find(KeyLike&& key) {
502 return table.find(key).map([](Entry& e) -> Value& { return e.value; });
503 }
504 template <typename Key, typename Value>
505 template <typename KeyLike>
506 kj::Maybe<const Value&> TreeMap<Key, Value>::find(KeyLike&& key) const {
507 return table.find(key).map([](const Entry& e) -> const Value& { return e.value; });
508 }
509
510 template <typename Key, typename Value>
511 template <typename KeyLike, typename Func>
512 Value& TreeMap<Key, Value>::findOrCreate(KeyLike&& key, Func&& createEntry) {
513 return table.findOrCreate(key, kj::fwd<Func>(createEntry)).value;
514 }
515
516 template <typename Key, typename Value>
517 template <typename KeyLike>
518 kj::Maybe<typename TreeMap<Key, Value>::Entry&>
519 TreeMap<Key, Value>::findEntry(KeyLike&& key) {
520 return table.find(kj::fwd<KeyLike>(key));
521 }
522 template <typename Key, typename Value>
523 template <typename KeyLike>
524 kj::Maybe<const typename TreeMap<Key, Value>::Entry&>
525 TreeMap<Key, Value>::findEntry(KeyLike&& key) const {
526 return table.find(kj::fwd<KeyLike>(key));
527 }
528 template <typename Key, typename Value>
529 template <typename KeyLike, typename Func>
530 typename TreeMap<Key, Value>::Entry&
531 TreeMap<Key, Value>::findOrCreateEntry(KeyLike&& key, Func&& createEntry) {
532 return table.findOrCreate(kj::fwd<KeyLike>(key), kj::fwd<Func>(createEntry));
533 }
534
535 template <typename Key, typename Value>
536 template <typename K1, typename K2>
537 auto TreeMap<Key, Value>::range(K1&& k1, K2&& k2) {
538 return table.range(kj::fwd<K1>(k1), kj::fwd<K2>(k2));
539 }
540 template <typename Key, typename Value>
541 template <typename K1, typename K2>
542 auto TreeMap<Key, Value>::range(K1&& k1, K2&& k2) const {
543 return table.range(kj::fwd<K1>(k1), kj::fwd<K2>(k2));
544 }
545
546 template <typename Key, typename Value>
547 template <typename KeyLike>
548 bool TreeMap<Key, Value>::erase(KeyLike&& key) {
549 return table.eraseMatch(key);
550 }
551
552 template <typename Key, typename Value>
553 void TreeMap<Key, Value>::erase(Entry& entry) {
554 table.erase(entry);
555 }
556
557 template <typename Key, typename Value>
558 typename TreeMap<Key, Value>::Entry TreeMap<Key, Value>::release(Entry& entry) {
559 return table.release(entry);
560 }
561
562 template <typename Key, typename Value>
563 template <typename Predicate, typename>
564 size_t TreeMap<Key, Value>::eraseAll(Predicate&& predicate) {
565 return table.eraseAll([&](Entry& entry) {
566 return predicate(entry.key, entry.value);
567 });
568 }
569
570 template <typename Key, typename Value>
571 template <typename K1, typename K2>
572 size_t TreeMap<Key, Value>::eraseRange(K1&& k1, K2&& k2) {
573 return table.eraseRange(kj::fwd<K1>(k1), kj::fwd<K2>(k2));
574 }
575
576 } // namespace kj
577
578 KJ_END_HEADER