jpayne@69: // Copyright (c) 2018 Kenton Varda and contributors
jpayne@69: // Licensed under the MIT License:
jpayne@69: //
jpayne@69: // Permission is hereby granted, free of charge, to any person obtaining a copy
jpayne@69: // of this software and associated documentation files (the "Software"), to deal
jpayne@69: // in the Software without restriction, including without limitation the rights
jpayne@69: // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
jpayne@69: // copies of the Software, and to permit persons to whom the Software is
jpayne@69: // furnished to do so, subject to the following conditions:
jpayne@69: //
jpayne@69: // The above copyright notice and this permission notice shall be included in
jpayne@69: // all copies or substantial portions of the Software.
jpayne@69: //
jpayne@69: // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
jpayne@69: // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
jpayne@69: // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
jpayne@69: // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
jpayne@69: // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
jpayne@69: // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
jpayne@69: // THE SOFTWARE.
jpayne@69: 
jpayne@69: #pragma once
jpayne@69: 
jpayne@69: #include "table.h"
jpayne@69: #include "hash.h"
jpayne@69: 
jpayne@69: KJ_BEGIN_HEADER
jpayne@69: 
jpayne@69: namespace kj {
jpayne@69: 
jpayne@69: template <typename Key, typename Value>
jpayne@69: class HashMap {
jpayne@69:   // A key/value mapping backed by hashing.
jpayne@69:   //
jpayne@69:   // `Key` must be hashable (via a `.hashCode()` method or `KJ_HASHCODE()`; see `hash.h`) and must
jpayne@69:   // implement `operator==()`. Additionally, when performing lookups, you can use key types other
jpayne@69:   // than `Key` as long as the other type is also hashable (producing the same hash codes) and
jpayne@69:   // there is an `operator==` implementation with `Key` on the left and that other type on the
jpayne@69:   // right. For example, if the key type is `String`, you can pass `StringPtr` to `find()`.
jpayne@69: 
jpayne@69: public:
jpayne@69:   void reserve(size_t size);
jpayne@69:   // Pre-allocates space for a map of the given size.
jpayne@69: 
jpayne@69:   size_t size() const;
jpayne@69:   size_t capacity() const;
jpayne@69:   void clear();
jpayne@69: 
jpayne@69:   struct Entry {
jpayne@69:     Key key;
jpayne@69:     Value value;
jpayne@69:   };
jpayne@69: 
jpayne@69:   Entry* begin();
jpayne@69:   Entry* end();
jpayne@69:   const Entry* begin() const;
jpayne@69:   const Entry* end() const;
jpayne@69:   // Deterministic iteration. If you only ever insert(), iteration order will be insertion order.
jpayne@69:   // If you erase(), the erased element is swapped with the last element in the ordering.
jpayne@69: 
jpayne@69:   Entry& insert(Key key, Value value);
jpayne@69:   // Inserts a new entry. Throws if the key already exists.
jpayne@69: 
jpayne@69:   template <typename Collection>
jpayne@69:   void insertAll(Collection&& collection);
jpayne@69:   // Given an iterable collection of `Entry`s, inserts all of them into this map. If the
jpayne@69:   // input is an rvalue, the entries will be moved rather than copied.
jpayne@69: 
jpayne@69:   template <typename UpdateFunc>
jpayne@69:   Entry& upsert(Key key, Value value, UpdateFunc&& update);
jpayne@69:   Entry& upsert(Key key, Value value);
jpayne@69:   // Tries to insert a new entry. However, if a duplicate already exists (according to some index),
jpayne@69:   // then update(Value& existingValue, Value&& newValue) is called to modify the existing value.
jpayne@69:   // If no function is provided, the default is to simply replace the value (but not the key).
jpayne@69: 
jpayne@69:   template <typename KeyLike>
jpayne@69:   kj::Maybe<Value&> find(KeyLike&& key);
jpayne@69:   template <typename KeyLike>
jpayne@69:   kj::Maybe<const Value&> find(KeyLike&& key) const;
jpayne@69:   // Search for a matching key. The input does not have to be of type `Key`; it merely has to
jpayne@69:   // be something that the Hasher accepts.
jpayne@69:   //
jpayne@69:   // Note that the default hasher for String accepts StringPtr.
jpayne@69: 
jpayne@69:   template <typename KeyLike, typename Func>
jpayne@69:   Value& findOrCreate(KeyLike&& key, Func&& createEntry);
jpayne@69:   // Like find() but if the key isn't present then call createEntry() to create the corresponding
jpayne@69:   // entry and insert it. createEntry() must return type `Entry`.
jpayne@69: 
jpayne@69:   template <typename KeyLike>
jpayne@69:   kj::Maybe<Entry&> findEntry(KeyLike&& key);
jpayne@69:   template <typename KeyLike>
jpayne@69:   kj::Maybe<const Entry&> findEntry(KeyLike&& key) const;
jpayne@69:   template <typename KeyLike, typename Func>
jpayne@69:   Entry& findOrCreateEntry(KeyLike&& key, Func&& createEntry);
jpayne@69:   // Sometimes you need to see the whole matching Entry, not just the Value.
jpayne@69: 
jpayne@69:   template <typename KeyLike>
jpayne@69:   bool erase(KeyLike&& key);
jpayne@69:   // Erase the entry with the matching key.
jpayne@69:   //
jpayne@69:   // WARNING: This invalidates all pointers and iterators into the map. Use eraseAll() if you need
jpayne@69:   //   to iterate and erase multiple entries.
jpayne@69: 
jpayne@69:   void erase(Entry& entry);
jpayne@69:   // Erase an entry by reference.
jpayne@69: 
jpayne@69:   Entry release(Entry& row);
jpayne@69:   // Erase an entry and return its content by move.
jpayne@69: 
jpayne@69:   template <typename Predicate,
jpayne@69:       typename = decltype(instance<Predicate>()(instance<Key&>(), instance<Value&>()))>
jpayne@69:   size_t eraseAll(Predicate&& predicate);
jpayne@69:   // Erase all values for which predicate(key, value) returns true. This scans over the entire map.
jpayne@69: 
jpayne@69: private:
jpayne@69:   class Callbacks {
jpayne@69:   public:
jpayne@69:     inline const Key& keyForRow(const Entry& entry) const { return entry.key; }
jpayne@69:     inline Key& keyForRow(Entry& entry) const { return entry.key; }
jpayne@69: 
jpayne@69:     template <typename KeyLike>
jpayne@69:     inline bool matches(Entry& e, KeyLike&& key) const {
jpayne@69:       return e.key == key;
jpayne@69:     }
jpayne@69:     template <typename KeyLike>
jpayne@69:     inline bool matches(const Entry& e, KeyLike&& key) const {
jpayne@69:       return e.key == key;
jpayne@69:     }
jpayne@69:     template <typename KeyLike>
jpayne@69:     inline auto hashCode(KeyLike&& key) const {
jpayne@69:       return kj::hashCode(key);
jpayne@69:     }
jpayne@69:   };
jpayne@69: 
jpayne@69:   kj::Table<Entry, HashIndex<Callbacks>> table;
jpayne@69: };
jpayne@69: 
jpayne@69: template <typename Key, typename Value>
jpayne@69: class TreeMap {
jpayne@69:   // A key/value mapping backed by a B-tree.
jpayne@69:   //
jpayne@69:   // `Key` must support `operator<` and `operator==` against other Keys, and against any type
jpayne@69:   // which you might want to pass to find() (with `Key` always on the left of the comparison).
jpayne@69: 
jpayne@69: public:
jpayne@69:   void reserve(size_t size);
jpayne@69:   // Pre-allocates space for a map of the given size.
jpayne@69: 
jpayne@69:   size_t size() const;
jpayne@69:   size_t capacity() const;
jpayne@69:   void clear();
jpayne@69: 
jpayne@69:   struct Entry {
jpayne@69:     Key key;
jpayne@69:     Value value;
jpayne@69:   };
jpayne@69: 
jpayne@69:   auto begin();
jpayne@69:   auto end();
jpayne@69:   auto begin() const;
jpayne@69:   auto end() const;
jpayne@69:   // Iteration is in sorted order by key.
jpayne@69: 
jpayne@69:   Entry& insert(Key key, Value value);
jpayne@69:   // Inserts a new entry. Throws if the key already exists.
jpayne@69: 
jpayne@69:   template <typename Collection>
jpayne@69:   void insertAll(Collection&& collection);
jpayne@69:   // Given an iterable collection of `Entry`s, inserts all of them into this map. If the
jpayne@69:   // input is an rvalue, the entries will be moved rather than copied.
jpayne@69: 
jpayne@69:   template <typename UpdateFunc>
jpayne@69:   Entry& upsert(Key key, Value value, UpdateFunc&& update);
jpayne@69:   Entry& upsert(Key key, Value value);
jpayne@69:   // Tries to insert a new entry. However, if a duplicate already exists (according to some index),
jpayne@69:   // then update(Value& existingValue, Value&& newValue) is called to modify the existing value.
jpayne@69:   // If no function is provided, the default is to simply replace the value (but not the key).
jpayne@69: 
jpayne@69:   template <typename KeyLike>
jpayne@69:   kj::Maybe<Value&> find(KeyLike&& key);
jpayne@69:   template <typename KeyLike>
jpayne@69:   kj::Maybe<const Value&> find(KeyLike&& key) const;
jpayne@69:   // Search for a matching key. The input does not have to be of type `Key`; it merely has to
jpayne@69:   // be something that can be compared against `Key`.
jpayne@69: 
jpayne@69:   template <typename KeyLike, typename Func>
jpayne@69:   Value& findOrCreate(KeyLike&& key, Func&& createEntry);
jpayne@69:   // Like find() but if the key isn't present then call createEntry() to create the corresponding
jpayne@69:   // entry and insert it. createEntry() must return type `Entry`.
jpayne@69: 
jpayne@69:   template <typename KeyLike>
jpayne@69:   kj::Maybe<Entry&> findEntry(KeyLike&& key);
jpayne@69:   template <typename KeyLike>
jpayne@69:   kj::Maybe<const Entry&> findEntry(KeyLike&& key) const;
jpayne@69:   template <typename KeyLike, typename Func>
jpayne@69:   Entry& findOrCreateEntry(KeyLike&& key, Func&& createEntry);
jpayne@69:   // Sometimes you need to see the whole matching Entry, not just the Value.
jpayne@69: 
jpayne@69:   template <typename K1, typename K2>
jpayne@69:   auto range(K1&& k1, K2&& k2);
jpayne@69:   template <typename K1, typename K2>
jpayne@69:   auto range(K1&& k1, K2&& k2) const;
jpayne@69:   // Returns an iterable range of entries with keys between k1 (inclusive) and k2 (exclusive).
jpayne@69: 
jpayne@69:   template <typename KeyLike>
jpayne@69:   bool erase(KeyLike&& key);
jpayne@69:   // Erase the entry with the matching key.
jpayne@69:   //
jpayne@69:   // WARNING: This invalidates all pointers and iterators into the map. Use eraseAll() if you need
jpayne@69:   //   to iterate and erase multiple entries.
jpayne@69: 
jpayne@69:   void erase(Entry& entry);
jpayne@69:   // Erase an entry by reference.
jpayne@69: 
jpayne@69:   Entry release(Entry& row);
jpayne@69:   // Erase an entry and return its content by move.
jpayne@69: 
jpayne@69:   template <typename Predicate,
jpayne@69:       typename = decltype(instance<Predicate>()(instance<Key&>(), instance<Value&>()))>
jpayne@69:   size_t eraseAll(Predicate&& predicate);
jpayne@69:   // Erase all values for which predicate(key, value) returns true. This scans over the entire map.
jpayne@69: 
jpayne@69:   template <typename K1, typename K2>
jpayne@69:   size_t eraseRange(K1&& k1, K2&& k2);
jpayne@69:   // Erases all entries with keys between k1 (inclusive) and k2 (exclusive).
jpayne@69: 
jpayne@69: private:
jpayne@69:   class Callbacks {
jpayne@69:   public:
jpayne@69:     inline const Key& keyForRow(const Entry& entry) const { return entry.key; }
jpayne@69:     inline Key& keyForRow(Entry& entry) const { return entry.key; }
jpayne@69: 
jpayne@69:     template <typename KeyLike>
jpayne@69:     inline bool matches(Entry& e, KeyLike&& key) const {
jpayne@69:       return e.key == key;
jpayne@69:     }
jpayne@69:     template <typename KeyLike>
jpayne@69:     inline bool matches(const Entry& e, KeyLike&& key) const {
jpayne@69:       return e.key == key;
jpayne@69:     }
jpayne@69:     template <typename KeyLike>
jpayne@69:     inline bool isBefore(Entry& e, KeyLike&& key) const {
jpayne@69:       return e.key < key;
jpayne@69:     }
jpayne@69:     template <typename KeyLike>
jpayne@69:     inline bool isBefore(const Entry& e, KeyLike&& key) const {
jpayne@69:       return e.key < key;
jpayne@69:     }
jpayne@69:   };
jpayne@69: 
jpayne@69:   kj::Table<Entry, TreeIndex<Callbacks>> table;
jpayne@69: };
jpayne@69: 
jpayne@69: namespace _ {  // private
jpayne@69: 
jpayne@69: class HashSetCallbacks {
jpayne@69: public:
jpayne@69:   template <typename Row>
jpayne@69:   inline Row& keyForRow(Row& row) const { return row; }
jpayne@69: 
jpayne@69:   template <typename T, typename U>
jpayne@69:   inline bool matches(T& a, U& b) const { return a == b; }
jpayne@69:   template <typename KeyLike>
jpayne@69:   inline auto hashCode(KeyLike&& key) const {
jpayne@69:     return kj::hashCode(key);
jpayne@69:   }
jpayne@69: };
jpayne@69: 
jpayne@69: class TreeSetCallbacks {
jpayne@69: public:
jpayne@69:   template <typename Row>
jpayne@69:   inline Row& keyForRow(Row& row) const { return row; }
jpayne@69: 
jpayne@69:   template <typename T, typename U>
jpayne@69:   inline bool matches(T& a, U& b) const { return a == b; }
jpayne@69:   template <typename T, typename U>
jpayne@69:   inline bool isBefore(T& a, U& b) const { return a < b; }
jpayne@69: };
jpayne@69: 
jpayne@69: }  // namespace _ (private)
jpayne@69: 
jpayne@69: template <typename Element>
jpayne@69: class HashSet: public Table<Element, HashIndex<_::HashSetCallbacks>> {
jpayne@69:   // A simple hashtable-based set, using kj::hashCode() and operator==().
jpayne@69: 
jpayne@69: public:
jpayne@69:   // Everything is inherited.
jpayne@69: 
jpayne@69:   template <typename... Params>
jpayne@69:   inline bool contains(Params&&... params) const {
jpayne@69:     return this->find(kj::fwd<Params>(params)...) != nullptr;
jpayne@69:   }
jpayne@69: };
jpayne@69: 
jpayne@69: template <typename Element>
jpayne@69: class TreeSet: public Table<Element, TreeIndex<_::TreeSetCallbacks>> {
jpayne@69:   // A simple b-tree-based set, using operator<() and operator==().
jpayne@69: 
jpayne@69: public:
jpayne@69:   // Everything is inherited.
jpayne@69: };
jpayne@69: 
jpayne@69: // =======================================================================================
jpayne@69: // inline implementation details
jpayne@69: 
jpayne@69: template <typename Key, typename Value>
jpayne@69: void HashMap<Key, Value>::reserve(size_t size) {
jpayne@69:   table.reserve(size);
jpayne@69: }
jpayne@69: 
jpayne@69: template <typename Key, typename Value>
jpayne@69: size_t HashMap<Key, Value>::size() const {
jpayne@69:   return table.size();
jpayne@69: }
jpayne@69: template <typename Key, typename Value>
jpayne@69: size_t HashMap<Key, Value>::capacity() const {
jpayne@69:   return table.capacity();
jpayne@69: }
jpayne@69: template <typename Key, typename Value>
jpayne@69: void HashMap<Key, Value>::clear() {
jpayne@69:   return table.clear();
jpayne@69: }
jpayne@69: 
jpayne@69: template <typename Key, typename Value>
jpayne@69: typename HashMap<Key, Value>::Entry* HashMap<Key, Value>::begin() {
jpayne@69:   return table.begin();
jpayne@69: }
jpayne@69: template <typename Key, typename Value>
jpayne@69: typename HashMap<Key, Value>::Entry* HashMap<Key, Value>::end() {
jpayne@69:   return table.end();
jpayne@69: }
jpayne@69: template <typename Key, typename Value>
jpayne@69: const typename HashMap<Key, Value>::Entry* HashMap<Key, Value>::begin() const {
jpayne@69:   return table.begin();
jpayne@69: }
jpayne@69: template <typename Key, typename Value>
jpayne@69: const typename HashMap<Key, Value>::Entry* HashMap<Key, Value>::end() const {
jpayne@69:   return table.end();
jpayne@69: }
jpayne@69: 
jpayne@69: template <typename Key, typename Value>
jpayne@69: typename HashMap<Key, Value>::Entry& HashMap<Key, Value>::insert(Key key, Value value) {
jpayne@69:   return table.insert(Entry { kj::mv(key), kj::mv(value) });
jpayne@69: }
jpayne@69: 
jpayne@69: template <typename Key, typename Value>
jpayne@69: template <typename Collection>
jpayne@69: void HashMap<Key, Value>::insertAll(Collection&& collection) {
jpayne@69:   return table.insertAll(kj::fwd<Collection>(collection));
jpayne@69: }
jpayne@69: 
jpayne@69: template <typename Key, typename Value>
jpayne@69: template <typename UpdateFunc>
jpayne@69: typename HashMap<Key, Value>::Entry& HashMap<Key, Value>::upsert(
jpayne@69:     Key key, Value value, UpdateFunc&& update) {
jpayne@69:   return table.upsert(Entry { kj::mv(key), kj::mv(value) },
jpayne@69:       [&](Entry& existingEntry, Entry&& newEntry) {
jpayne@69:     update(existingEntry.value, kj::mv(newEntry.value));
jpayne@69:   });
jpayne@69: }
jpayne@69: 
jpayne@69: template <typename Key, typename Value>
jpayne@69: typename HashMap<Key, Value>::Entry& HashMap<Key, Value>::upsert(
jpayne@69:     Key key, Value value) {
jpayne@69:   return table.upsert(Entry { kj::mv(key), kj::mv(value) },
jpayne@69:       [&](Entry& existingEntry, Entry&& newEntry) {
jpayne@69:     existingEntry.value = kj::mv(newEntry.value);
jpayne@69:   });
jpayne@69: }
jpayne@69: 
jpayne@69: template <typename Key, typename Value>
jpayne@69: template <typename KeyLike>
jpayne@69: kj::Maybe<Value&> HashMap<Key, Value>::find(KeyLike&& key) {
jpayne@69:   return table.find(key).map([](Entry& e) -> Value& { return e.value; });
jpayne@69: }
jpayne@69: template <typename Key, typename Value>
jpayne@69: template <typename KeyLike>
jpayne@69: kj::Maybe<const Value&> HashMap<Key, Value>::find(KeyLike&& key) const {
jpayne@69:   return table.find(key).map([](const Entry& e) -> const Value& { return e.value; });
jpayne@69: }
jpayne@69: 
jpayne@69: template <typename Key, typename Value>
jpayne@69: template <typename KeyLike, typename Func>
jpayne@69: Value& HashMap<Key, Value>::findOrCreate(KeyLike&& key, Func&& createEntry) {
jpayne@69:   return table.findOrCreate(key, kj::fwd<Func>(createEntry)).value;
jpayne@69: }
jpayne@69: 
jpayne@69: template <typename Key, typename Value>
jpayne@69: template <typename KeyLike>
jpayne@69: kj::Maybe<typename HashMap<Key, Value>::Entry&>
jpayne@69: HashMap<Key, Value>::findEntry(KeyLike&& key) {
jpayne@69:   return table.find(kj::fwd<KeyLike>(key));
jpayne@69: }
jpayne@69: template <typename Key, typename Value>
jpayne@69: template <typename KeyLike>
jpayne@69: kj::Maybe<const typename HashMap<Key, Value>::Entry&>
jpayne@69: HashMap<Key, Value>::findEntry(KeyLike&& key) const {
jpayne@69:   return table.find(kj::fwd<KeyLike>(key));
jpayne@69: }
jpayne@69: template <typename Key, typename Value>
jpayne@69: template <typename KeyLike, typename Func>
jpayne@69: typename HashMap<Key, Value>::Entry&
jpayne@69: HashMap<Key, Value>::findOrCreateEntry(KeyLike&& key, Func&& createEntry) {
jpayne@69:   return table.findOrCreate(kj::fwd<KeyLike>(key), kj::fwd<Func>(createEntry));
jpayne@69: }
jpayne@69: 
jpayne@69: template <typename Key, typename Value>
jpayne@69: template <typename KeyLike>
jpayne@69: bool HashMap<Key, Value>::erase(KeyLike&& key) {
jpayne@69:   return table.eraseMatch(key);
jpayne@69: }
jpayne@69: 
jpayne@69: template <typename Key, typename Value>
jpayne@69: void HashMap<Key, Value>::erase(Entry& entry) {
jpayne@69:   table.erase(entry);
jpayne@69: }
jpayne@69: 
jpayne@69: template <typename Key, typename Value>
jpayne@69: typename HashMap<Key, Value>::Entry HashMap<Key, Value>::release(Entry& entry) {
jpayne@69:   return table.release(entry);
jpayne@69: }
jpayne@69: 
jpayne@69: template <typename Key, typename Value>
jpayne@69: template <typename Predicate, typename>
jpayne@69: size_t HashMap<Key, Value>::eraseAll(Predicate&& predicate) {
jpayne@69:   return table.eraseAll([&](Entry& entry) {
jpayne@69:     return predicate(entry.key, entry.value);
jpayne@69:   });
jpayne@69: }
jpayne@69: 
jpayne@69: // -----------------------------------------------------------------------------
jpayne@69: 
jpayne@69: template <typename Key, typename Value>
jpayne@69: void TreeMap<Key, Value>::reserve(size_t size) {
jpayne@69:   table.reserve(size);
jpayne@69: }
jpayne@69: 
jpayne@69: template <typename Key, typename Value>
jpayne@69: size_t TreeMap<Key, Value>::size() const {
jpayne@69:   return table.size();
jpayne@69: }
jpayne@69: template <typename Key, typename Value>
jpayne@69: size_t TreeMap<Key, Value>::capacity() const {
jpayne@69:   return table.capacity();
jpayne@69: }
jpayne@69: template <typename Key, typename Value>
jpayne@69: void TreeMap<Key, Value>::clear() {
jpayne@69:   return table.clear();
jpayne@69: }
jpayne@69: 
jpayne@69: template <typename Key, typename Value>
jpayne@69: auto TreeMap<Key, Value>::begin() {
jpayne@69:   return table.ordered().begin();
jpayne@69: }
jpayne@69: template <typename Key, typename Value>
jpayne@69: auto TreeMap<Key, Value>::end() {
jpayne@69:   return table.ordered().end();
jpayne@69: }
jpayne@69: template <typename Key, typename Value>
jpayne@69: auto TreeMap<Key, Value>::begin() const {
jpayne@69:   return table.ordered().begin();
jpayne@69: }
jpayne@69: template <typename Key, typename Value>
jpayne@69: auto TreeMap<Key, Value>::end() const {
jpayne@69:   return table.ordered().end();
jpayne@69: }
jpayne@69: 
jpayne@69: template <typename Key, typename Value>
jpayne@69: typename TreeMap<Key, Value>::Entry& TreeMap<Key, Value>::insert(Key key, Value value) {
jpayne@69:   return table.insert(Entry { kj::mv(key), kj::mv(value) });
jpayne@69: }
jpayne@69: 
jpayne@69: template <typename Key, typename Value>
jpayne@69: template <typename Collection>
jpayne@69: void TreeMap<Key, Value>::insertAll(Collection&& collection) {
jpayne@69:   return table.insertAll(kj::fwd<Collection>(collection));
jpayne@69: }
jpayne@69: 
jpayne@69: template <typename Key, typename Value>
jpayne@69: template <typename UpdateFunc>
jpayne@69: typename TreeMap<Key, Value>::Entry& TreeMap<Key, Value>::upsert(
jpayne@69:     Key key, Value value, UpdateFunc&& update) {
jpayne@69:   return table.upsert(Entry { kj::mv(key), kj::mv(value) },
jpayne@69:       [&](Entry& existingEntry, Entry&& newEntry) {
jpayne@69:     update(existingEntry.value, kj::mv(newEntry.value));
jpayne@69:   });
jpayne@69: }
jpayne@69: 
jpayne@69: template <typename Key, typename Value>
jpayne@69: typename TreeMap<Key, Value>::Entry& TreeMap<Key, Value>::upsert(
jpayne@69:     Key key, Value value) {
jpayne@69:   return table.upsert(Entry { kj::mv(key), kj::mv(value) },
jpayne@69:       [&](Entry& existingEntry, Entry&& newEntry) {
jpayne@69:     existingEntry.value = kj::mv(newEntry.value);
jpayne@69:   });
jpayne@69: }
jpayne@69: 
jpayne@69: template <typename Key, typename Value>
jpayne@69: template <typename KeyLike>
jpayne@69: kj::Maybe<Value&> TreeMap<Key, Value>::find(KeyLike&& key) {
jpayne@69:   return table.find(key).map([](Entry& e) -> Value& { return e.value; });
jpayne@69: }
jpayne@69: template <typename Key, typename Value>
jpayne@69: template <typename KeyLike>
jpayne@69: kj::Maybe<const Value&> TreeMap<Key, Value>::find(KeyLike&& key) const {
jpayne@69:   return table.find(key).map([](const Entry& e) -> const Value& { return e.value; });
jpayne@69: }
jpayne@69: 
jpayne@69: template <typename Key, typename Value>
jpayne@69: template <typename KeyLike, typename Func>
jpayne@69: Value& TreeMap<Key, Value>::findOrCreate(KeyLike&& key, Func&& createEntry) {
jpayne@69:   return table.findOrCreate(key, kj::fwd<Func>(createEntry)).value;
jpayne@69: }
jpayne@69: 
jpayne@69: template <typename Key, typename Value>
jpayne@69: template <typename KeyLike>
jpayne@69: kj::Maybe<typename TreeMap<Key, Value>::Entry&>
jpayne@69: TreeMap<Key, Value>::findEntry(KeyLike&& key) {
jpayne@69:   return table.find(kj::fwd<KeyLike>(key));
jpayne@69: }
jpayne@69: template <typename Key, typename Value>
jpayne@69: template <typename KeyLike>
jpayne@69: kj::Maybe<const typename TreeMap<Key, Value>::Entry&>
jpayne@69: TreeMap<Key, Value>::findEntry(KeyLike&& key) const {
jpayne@69:   return table.find(kj::fwd<KeyLike>(key));
jpayne@69: }
jpayne@69: template <typename Key, typename Value>
jpayne@69: template <typename KeyLike, typename Func>
jpayne@69: typename TreeMap<Key, Value>::Entry&
jpayne@69: TreeMap<Key, Value>::findOrCreateEntry(KeyLike&& key, Func&& createEntry) {
jpayne@69:   return table.findOrCreate(kj::fwd<KeyLike>(key), kj::fwd<Func>(createEntry));
jpayne@69: }
jpayne@69: 
jpayne@69: template <typename Key, typename Value>
jpayne@69: template <typename K1, typename K2>
jpayne@69: auto TreeMap<Key, Value>::range(K1&& k1, K2&& k2) {
jpayne@69:   return table.range(kj::fwd<K1>(k1), kj::fwd<K2>(k2));
jpayne@69: }
jpayne@69: template <typename Key, typename Value>
jpayne@69: template <typename K1, typename K2>
jpayne@69: auto TreeMap<Key, Value>::range(K1&& k1, K2&& k2) const {
jpayne@69:   return table.range(kj::fwd<K1>(k1), kj::fwd<K2>(k2));
jpayne@69: }
jpayne@69: 
jpayne@69: template <typename Key, typename Value>
jpayne@69: template <typename KeyLike>
jpayne@69: bool TreeMap<Key, Value>::erase(KeyLike&& key) {
jpayne@69:   return table.eraseMatch(key);
jpayne@69: }
jpayne@69: 
jpayne@69: template <typename Key, typename Value>
jpayne@69: void TreeMap<Key, Value>::erase(Entry& entry) {
jpayne@69:   table.erase(entry);
jpayne@69: }
jpayne@69: 
jpayne@69: template <typename Key, typename Value>
jpayne@69: typename TreeMap<Key, Value>::Entry TreeMap<Key, Value>::release(Entry& entry) {
jpayne@69:   return table.release(entry);
jpayne@69: }
jpayne@69: 
jpayne@69: template <typename Key, typename Value>
jpayne@69: template <typename Predicate, typename>
jpayne@69: size_t TreeMap<Key, Value>::eraseAll(Predicate&& predicate) {
jpayne@69:   return table.eraseAll([&](Entry& entry) {
jpayne@69:     return predicate(entry.key, entry.value);
jpayne@69:   });
jpayne@69: }
jpayne@69: 
jpayne@69: template <typename Key, typename Value>
jpayne@69: template <typename K1, typename K2>
jpayne@69: size_t TreeMap<Key, Value>::eraseRange(K1&& k1, K2&& k2) {
jpayne@69:   return table.eraseRange(kj::fwd<K1>(k1), kj::fwd<K2>(k2));
jpayne@69: }
jpayne@69: 
jpayne@69: } // namespace kj
jpayne@69: 
jpayne@69: KJ_END_HEADER