map.h (18273B)
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 // Tries to insert a new entry. However, if a duplicate already exists (according to some index), 72 // then update(Value& existingValue, Value&& newValue) is called to modify the existing value. 73 74 template <typename KeyLike> 75 kj::Maybe<Value&> find(KeyLike&& key); 76 template <typename KeyLike> 77 kj::Maybe<const Value&> find(KeyLike&& key) const; 78 // Search for a matching key. The input does not have to be of type `Key`; it merely has to 79 // be something that the Hasher accepts. 80 // 81 // Note that the default hasher for String accepts StringPtr. 82 83 template <typename KeyLike, typename Func> 84 Value& findOrCreate(KeyLike&& key, Func&& createEntry); 85 // Like find() but if the key isn't present then call createEntry() to create the corresponding 86 // entry and insert it. createEntry() must return type `Entry`. 87 88 template <typename KeyLike> 89 kj::Maybe<Entry&> findEntry(KeyLike&& key); 90 template <typename KeyLike> 91 kj::Maybe<const Entry&> findEntry(KeyLike&& key) const; 92 template <typename KeyLike, typename Func> 93 Entry& findOrCreateEntry(KeyLike&& key, Func&& createEntry); 94 // Sometimes you need to see the whole matching Entry, not just the Value. 95 96 template <typename KeyLike> 97 bool erase(KeyLike&& key); 98 // Erase the entry with the matching key. 99 // 100 // WARNING: This invalidates all pointers and interators into the map. Use eraseAll() if you need 101 // to iterate and erase multiple entries. 102 103 void erase(Entry& entry); 104 // Erase an entry by reference. 105 106 template <typename Predicate, 107 typename = decltype(instance<Predicate>()(instance<Key&>(), instance<Value&>()))> 108 size_t eraseAll(Predicate&& predicate); 109 // Erase all values for which predicate(key, value) returns true. This scans over the entire map. 110 111 private: 112 class Callbacks { 113 public: 114 inline const Key& keyForRow(const Entry& entry) const { return entry.key; } 115 inline Key& keyForRow(Entry& entry) const { return entry.key; } 116 117 template <typename KeyLike> 118 inline bool matches(Entry& e, KeyLike&& key) const { 119 return e.key == key; 120 } 121 template <typename KeyLike> 122 inline bool matches(const Entry& e, KeyLike&& key) const { 123 return e.key == key; 124 } 125 template <typename KeyLike> 126 inline auto hashCode(KeyLike&& key) const { 127 return kj::hashCode(key); 128 } 129 }; 130 131 kj::Table<Entry, HashIndex<Callbacks>> table; 132 }; 133 134 template <typename Key, typename Value> 135 class TreeMap { 136 // A key/value mapping backed by a B-tree. 137 // 138 // `Key` must support `operator<` and `operator==` against other Keys, and against any type 139 // which you might want to pass to find() (with `Key` always on the left of the comparison). 140 141 public: 142 void reserve(size_t size); 143 // Pre-allocates space for a map of the given size. 144 145 size_t size() const; 146 size_t capacity() const; 147 void clear(); 148 149 struct Entry { 150 Key key; 151 Value value; 152 }; 153 154 auto begin(); 155 auto end(); 156 auto begin() const; 157 auto end() const; 158 // Iteration is in sorted order by key. 159 160 Entry& insert(Key key, Value value); 161 // Inserts a new entry. Throws if the key already exists. 162 163 template <typename Collection> 164 void insertAll(Collection&& collection); 165 // Given an iterable collection of `Entry`s, inserts all of them into this map. If the 166 // input is an rvalue, the entries will be moved rather than copied. 167 168 template <typename UpdateFunc> 169 Entry& upsert(Key key, Value value, UpdateFunc&& update); 170 // Tries to insert a new entry. However, if a duplicate already exists (according to some index), 171 // then update(Value& existingValue, Value&& newValue) is called to modify the existing value. 172 173 template <typename KeyLike> 174 kj::Maybe<Value&> find(KeyLike&& key); 175 template <typename KeyLike> 176 kj::Maybe<const Value&> find(KeyLike&& key) const; 177 // Search for a matching key. The input does not have to be of type `Key`; it merely has to 178 // be something that can be compared against `Key`. 179 180 template <typename KeyLike, typename Func> 181 Value& findOrCreate(KeyLike&& key, Func&& createEntry); 182 // Like find() but if the key isn't present then call createEntry() to create the corresponding 183 // entry and insert it. createEntry() must return type `Entry`. 184 185 template <typename KeyLike> 186 kj::Maybe<Entry&> findEntry(KeyLike&& key); 187 template <typename KeyLike> 188 kj::Maybe<const Entry&> findEntry(KeyLike&& key) const; 189 template <typename KeyLike, typename Func> 190 Entry& findOrCreateEntry(KeyLike&& key, Func&& createEntry); 191 // Sometimes you need to see the whole matching Entry, not just the Value. 192 193 template <typename K1, typename K2> 194 auto range(K1&& k1, K2&& k2); 195 template <typename K1, typename K2> 196 auto range(K1&& k1, K2&& k2) const; 197 // Returns an iterable range of entries with keys between k1 (inclusive) and k2 (exclusive). 198 199 template <typename KeyLike> 200 bool erase(KeyLike&& key); 201 // Erase the entry with the matching key. 202 // 203 // WARNING: This invalidates all pointers and interators into the map. Use eraseAll() if you need 204 // to iterate and erase multiple entries. 205 206 void erase(Entry& entry); 207 // Erase an entry by reference. 208 209 template <typename Predicate, 210 typename = decltype(instance<Predicate>()(instance<Key&>(), instance<Value&>()))> 211 size_t eraseAll(Predicate&& predicate); 212 // Erase all values for which predicate(key, value) returns true. This scans over the entire map. 213 214 template <typename K1, typename K2> 215 size_t eraseRange(K1&& k1, K2&& k2); 216 // Erases all entries with keys between k1 (inclusive) and k2 (exclusive). 217 218 private: 219 class Callbacks { 220 public: 221 inline const Key& keyForRow(const Entry& entry) const { return entry.key; } 222 inline Key& keyForRow(Entry& entry) const { return entry.key; } 223 224 template <typename KeyLike> 225 inline bool matches(Entry& e, KeyLike&& key) const { 226 return e.key == key; 227 } 228 template <typename KeyLike> 229 inline bool matches(const Entry& e, KeyLike&& key) const { 230 return e.key == key; 231 } 232 template <typename KeyLike> 233 inline bool isBefore(Entry& e, KeyLike&& key) const { 234 return e.key < key; 235 } 236 template <typename KeyLike> 237 inline bool isBefore(const Entry& e, KeyLike&& key) const { 238 return e.key < key; 239 } 240 }; 241 242 kj::Table<Entry, TreeIndex<Callbacks>> table; 243 }; 244 245 namespace _ { // private 246 247 class HashSetCallbacks { 248 public: 249 template <typename Row> 250 inline Row& keyForRow(Row& row) const { return row; } 251 252 template <typename T, typename U> 253 inline bool matches(T& a, U& b) const { return a == b; } 254 template <typename KeyLike> 255 inline auto hashCode(KeyLike&& key) const { 256 return kj::hashCode(key); 257 } 258 }; 259 260 class TreeSetCallbacks { 261 public: 262 template <typename Row> 263 inline Row& keyForRow(Row& row) const { return row; } 264 265 template <typename T, typename U> 266 inline bool matches(T& a, U& b) const { return a == b; } 267 template <typename T, typename U> 268 inline bool isBefore(T& a, U& b) const { return a < b; } 269 }; 270 271 } // namespace _ (private) 272 273 template <typename Element> 274 class HashSet: public Table<Element, HashIndex<_::HashSetCallbacks>> { 275 // A simple hashtable-based set, using kj::hashCode() and operator==(). 276 277 public: 278 // Everything is inherited. 279 280 template <typename... Params> 281 inline bool contains(Params&&... params) const { 282 return this->find(kj::fwd<Params>(params)...) != nullptr; 283 } 284 }; 285 286 template <typename Element> 287 class TreeSet: public Table<Element, TreeIndex<_::TreeSetCallbacks>> { 288 // A simple b-tree-based set, using operator<() and operator==(). 289 290 public: 291 // Everything is inherited. 292 }; 293 294 // ======================================================================================= 295 // inline implementation details 296 297 template <typename Key, typename Value> 298 void HashMap<Key, Value>::reserve(size_t size) { 299 table.reserve(size); 300 } 301 302 template <typename Key, typename Value> 303 size_t HashMap<Key, Value>::size() const { 304 return table.size(); 305 } 306 template <typename Key, typename Value> 307 size_t HashMap<Key, Value>::capacity() const { 308 return table.capacity(); 309 } 310 template <typename Key, typename Value> 311 void HashMap<Key, Value>::clear() { 312 return table.clear(); 313 } 314 315 template <typename Key, typename Value> 316 typename HashMap<Key, Value>::Entry* HashMap<Key, Value>::begin() { 317 return table.begin(); 318 } 319 template <typename Key, typename Value> 320 typename HashMap<Key, Value>::Entry* HashMap<Key, Value>::end() { 321 return table.end(); 322 } 323 template <typename Key, typename Value> 324 const typename HashMap<Key, Value>::Entry* HashMap<Key, Value>::begin() const { 325 return table.begin(); 326 } 327 template <typename Key, typename Value> 328 const typename HashMap<Key, Value>::Entry* HashMap<Key, Value>::end() const { 329 return table.end(); 330 } 331 332 template <typename Key, typename Value> 333 typename HashMap<Key, Value>::Entry& HashMap<Key, Value>::insert(Key key, Value value) { 334 return table.insert(Entry { kj::mv(key), kj::mv(value) }); 335 } 336 337 template <typename Key, typename Value> 338 template <typename Collection> 339 void HashMap<Key, Value>::insertAll(Collection&& collection) { 340 return table.insertAll(kj::fwd<Collection>(collection)); 341 } 342 343 template <typename Key, typename Value> 344 template <typename UpdateFunc> 345 typename HashMap<Key, Value>::Entry& HashMap<Key, Value>::upsert( 346 Key key, Value value, UpdateFunc&& update) { 347 return table.upsert(Entry { kj::mv(key), kj::mv(value) }, 348 [&](Entry& existingEntry, Entry&& newEntry) { 349 update(existingEntry.value, kj::mv(newEntry.value)); 350 }); 351 } 352 353 template <typename Key, typename Value> 354 template <typename KeyLike> 355 kj::Maybe<Value&> HashMap<Key, Value>::find(KeyLike&& key) { 356 return table.find(key).map([](Entry& e) -> Value& { return e.value; }); 357 } 358 template <typename Key, typename Value> 359 template <typename KeyLike> 360 kj::Maybe<const Value&> HashMap<Key, Value>::find(KeyLike&& key) const { 361 return table.find(key).map([](const Entry& e) -> const Value& { return e.value; }); 362 } 363 364 template <typename Key, typename Value> 365 template <typename KeyLike, typename Func> 366 Value& HashMap<Key, Value>::findOrCreate(KeyLike&& key, Func&& createEntry) { 367 return table.findOrCreate(key, kj::fwd<Func>(createEntry)).value; 368 } 369 370 template <typename Key, typename Value> 371 template <typename KeyLike> 372 kj::Maybe<typename HashMap<Key, Value>::Entry&> 373 HashMap<Key, Value>::findEntry(KeyLike&& key) { 374 return table.find(kj::fwd<KeyLike>(key)); 375 } 376 template <typename Key, typename Value> 377 template <typename KeyLike> 378 kj::Maybe<const typename HashMap<Key, Value>::Entry&> 379 HashMap<Key, Value>::findEntry(KeyLike&& key) const { 380 return table.find(kj::fwd<KeyLike>(key)); 381 } 382 template <typename Key, typename Value> 383 template <typename KeyLike, typename Func> 384 typename HashMap<Key, Value>::Entry& 385 HashMap<Key, Value>::findOrCreateEntry(KeyLike&& key, Func&& createEntry) { 386 return table.findOrCreate(kj::fwd<KeyLike>(key), kj::fwd<Func>(createEntry)); 387 } 388 389 template <typename Key, typename Value> 390 template <typename KeyLike> 391 bool HashMap<Key, Value>::erase(KeyLike&& key) { 392 return table.eraseMatch(key); 393 } 394 395 template <typename Key, typename Value> 396 void HashMap<Key, Value>::erase(Entry& entry) { 397 table.erase(entry); 398 } 399 400 template <typename Key, typename Value> 401 template <typename Predicate, typename> 402 size_t HashMap<Key, Value>::eraseAll(Predicate&& predicate) { 403 return table.eraseAll([&](Entry& entry) { 404 return predicate(entry.key, entry.value); 405 }); 406 } 407 408 // ----------------------------------------------------------------------------- 409 410 template <typename Key, typename Value> 411 void TreeMap<Key, Value>::reserve(size_t size) { 412 table.reserve(size); 413 } 414 415 template <typename Key, typename Value> 416 size_t TreeMap<Key, Value>::size() const { 417 return table.size(); 418 } 419 template <typename Key, typename Value> 420 size_t TreeMap<Key, Value>::capacity() const { 421 return table.capacity(); 422 } 423 template <typename Key, typename Value> 424 void TreeMap<Key, Value>::clear() { 425 return table.clear(); 426 } 427 428 template <typename Key, typename Value> 429 auto TreeMap<Key, Value>::begin() { 430 return table.ordered().begin(); 431 } 432 template <typename Key, typename Value> 433 auto TreeMap<Key, Value>::end() { 434 return table.ordered().end(); 435 } 436 template <typename Key, typename Value> 437 auto TreeMap<Key, Value>::begin() const { 438 return table.ordered().begin(); 439 } 440 template <typename Key, typename Value> 441 auto TreeMap<Key, Value>::end() const { 442 return table.ordered().end(); 443 } 444 445 template <typename Key, typename Value> 446 typename TreeMap<Key, Value>::Entry& TreeMap<Key, Value>::insert(Key key, Value value) { 447 return table.insert(Entry { kj::mv(key), kj::mv(value) }); 448 } 449 450 template <typename Key, typename Value> 451 template <typename Collection> 452 void TreeMap<Key, Value>::insertAll(Collection&& collection) { 453 return table.insertAll(kj::fwd<Collection>(collection)); 454 } 455 456 template <typename Key, typename Value> 457 template <typename UpdateFunc> 458 typename TreeMap<Key, Value>::Entry& TreeMap<Key, Value>::upsert( 459 Key key, Value value, UpdateFunc&& update) { 460 return table.upsert(Entry { kj::mv(key), kj::mv(value) }, 461 [&](Entry& existingEntry, Entry&& newEntry) { 462 update(existingEntry.value, kj::mv(newEntry.value)); 463 }); 464 } 465 466 template <typename Key, typename Value> 467 template <typename KeyLike> 468 kj::Maybe<Value&> TreeMap<Key, Value>::find(KeyLike&& key) { 469 return table.find(key).map([](Entry& e) -> Value& { return e.value; }); 470 } 471 template <typename Key, typename Value> 472 template <typename KeyLike> 473 kj::Maybe<const Value&> TreeMap<Key, Value>::find(KeyLike&& key) const { 474 return table.find(key).map([](const Entry& e) -> const Value& { return e.value; }); 475 } 476 477 template <typename Key, typename Value> 478 template <typename KeyLike, typename Func> 479 Value& TreeMap<Key, Value>::findOrCreate(KeyLike&& key, Func&& createEntry) { 480 return table.findOrCreate(key, kj::fwd<Func>(createEntry)).value; 481 } 482 483 template <typename Key, typename Value> 484 template <typename KeyLike> 485 kj::Maybe<typename TreeMap<Key, Value>::Entry&> 486 TreeMap<Key, Value>::findEntry(KeyLike&& key) { 487 return table.find(kj::fwd<KeyLike>(key)); 488 } 489 template <typename Key, typename Value> 490 template <typename KeyLike> 491 kj::Maybe<const typename TreeMap<Key, Value>::Entry&> 492 TreeMap<Key, Value>::findEntry(KeyLike&& key) const { 493 return table.find(kj::fwd<KeyLike>(key)); 494 } 495 template <typename Key, typename Value> 496 template <typename KeyLike, typename Func> 497 typename TreeMap<Key, Value>::Entry& 498 TreeMap<Key, Value>::findOrCreateEntry(KeyLike&& key, Func&& createEntry) { 499 return table.findOrCreate(kj::fwd<KeyLike>(key), kj::fwd<Func>(createEntry)); 500 } 501 502 template <typename Key, typename Value> 503 template <typename K1, typename K2> 504 auto TreeMap<Key, Value>::range(K1&& k1, K2&& k2) { 505 return table.range(kj::fwd<K1>(k1), kj::fwd<K2>(k2)); 506 } 507 template <typename Key, typename Value> 508 template <typename K1, typename K2> 509 auto TreeMap<Key, Value>::range(K1&& k1, K2&& k2) const { 510 return table.range(kj::fwd<K1>(k1), kj::fwd<K2>(k2)); 511 } 512 513 template <typename Key, typename Value> 514 template <typename KeyLike> 515 bool TreeMap<Key, Value>::erase(KeyLike&& key) { 516 return table.eraseMatch(key); 517 } 518 519 template <typename Key, typename Value> 520 void TreeMap<Key, Value>::erase(Entry& entry) { 521 table.erase(entry); 522 } 523 524 template <typename Key, typename Value> 525 template <typename Predicate, typename> 526 size_t TreeMap<Key, Value>::eraseAll(Predicate&& predicate) { 527 return table.eraseAll([&](Entry& entry) { 528 return predicate(entry.key, entry.value); 529 }); 530 } 531 532 template <typename Key, typename Value> 533 template <typename K1, typename K2> 534 size_t TreeMap<Key, Value>::eraseRange(K1&& k1, K2&& k2) { 535 return table.eraseRange(kj::fwd<K1>(k1), kj::fwd<K2>(k2)); 536 } 537 538 } // namespace kj 539 540 KJ_END_HEADER