Mercurial > repos > rliterman > csp2

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