capnproto

table.h (58554B)

---

 // Copyright (c) 2018 Kenton Varda and contributors
 // Licensed under the MIT License:
 //
 // Permission is hereby granted, free of charge, to any person obtaining a copy
 // of this software and associated documentation files (the "Software"), to deal
 // in the Software without restriction, including without limitation the rights
 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 // copies of the Software, and to permit persons to whom the Software is
 // furnished to do so, subject to the following conditions:
 //
 // The above copyright notice and this permission notice shall be included in
 // all copies or substantial portions of the Software.
 //
 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 // THE SOFTWARE.
 
 #pragma once
 
 #include "common.h"
 #include "tuple.h"
 #include "vector.h"
 #include "function.h"
 
 #if _MSC_VER
 // Need _ReadWriteBarrier
 #if _MSC_VER < 1910
 #include <intrin.h>
 #else
 #include <intrin0.h>
 #endif
 #endif
 
 #if KJ_DEBUG_TABLE_IMPL
 #include "debug.h"
 #define KJ_TABLE_IREQUIRE KJ_REQUIRE
 #define KJ_TABLE_IASSERT KJ_ASSERT
 #else
 #define KJ_TABLE_IREQUIRE KJ_IREQUIRE
 #define KJ_TABLE_IASSERT KJ_IASSERT
 #endif
 
 KJ_BEGIN_HEADER
 
 namespace kj {
 
 class String;
 
 namespace _ {  // private
 
 template <typename Row>
 class TableMapping;
 template <typename Row, typename Inner>
 using TableIterable = MappedIterable<Inner, TableMapping<Row>>;
 template <typename Row, typename Inner>
 using TableIterator = MappedIterator<Inner, TableMapping<Row>>;
 
 }  // namespace _ (private)
 
 template <typename Row, typename... Indexes>
 class Table {
   // A table with one or more indexes. This is the KJ alternative to map, set, unordered_map, and
   // unordered_set.
   //
   // Unlike a traditional map, which explicitly stores key/value pairs, a Table simply stores
   // "rows" of arbitrary type, and then lets the application specify how these should be indexed.
   // Rows could be indexed on a specific struct field, or they could be indexed based on a computed
   // property. An index could be hash-based or tree-based. Multiple indexes are supported, making
   // it easy to construct a "bimap".
   //
   // The table has deterministic iteration order based on the sequence of insertions and deletions.
   // In the case of only insertions, the iteration order is the order of insertion. If deletions
   // occur, then the current last row is moved to occupy the deleted slot. This determinism is
   // intended to be reliable for the purpose of testing, etc.
   //
   // Each index is a class that looks like:
   //
   //   class Index {
   //   public:
   //     void reserve(size_t size);
   //     // Called when Table::reserve() is called.
   //
   //     SearchParam& keyForRow(const Row& row) const;
   //     // Given a row, return a value appropriate to pass as SearchParams to the other functions.
   //
   //     // In all function calls below, `SearchPrams` refers to whatever parameters the index
   //     // supports for looking up a row in the table.
   //
   //     template <typename... SearchParams>
   //     kj::Maybe<size_t> insert(kj::ArrayPtr<const Row> table, size_t pos, SearchParams&&...);
   //     // Called to indicate that we're about to insert a new row which will match the given
   //     // search parameters, and will be located at the given position. If this index disallows
   //     //  duplicates and some other matching row already exists, then insert() returns the index
   //     // of that row without modifying the index. If the row does not exist, then insert()
   //     // updates the index to note that the new row is located at `pos`. Note that `table[pos]`
   //     // may not be valid yet at the time of this call; the index must go on the search params
   //     // alone.
   //     //
   //     // Insert may throw an exception, in which case the table will roll back insertion.
   //
   //     template <typename... SearchParams>
   //     void erase(kj::ArrayPtr<const Row> table, size_t pos, SearchParams&&...);
   //     // Called to indicate that the index must remove references to row number `pos`. The
   //     // index must not attempt to access table[pos] directly -- in fact, `pos` may be equal to
   //     // `table.size()`, i.e., may be out-of-bounds (this happens when rolling back a failed
   //     // insertion). Instead, the index can use the search params to search for the row -- they
   //     // will either be the same as the params passed to insert(), or will be a single value of
   //     // type `Row&`.
   //     //
   //     // erase() called immediately after a successful insert() must not throw an exception, as
   //     // it may be called during unwind.
   //
   //     template <typename... SearchParams>
   //     void move(kj::ArrayPtr<const Row> table, size_t oldPos, size_t newPos, SearchParams&&...);
   //     // Called when a row is about to be moved from `oldPos` to `newPos` in the table. The
   //     // index should update it to the new location. Neither `table[oldPos]` nor `table[newPos]`
   //     // is valid during the call -- use the search params to find the row. Before this call
   //     // `oldPos` is indexed and `newPos` is not -- after the call, the opposite is true.
   //     //
   //     // This should never throw; if it does the table may be corrupted.
   //
   //     class Iterator;  // Behaves like a C++ iterator over size_t values.
   //     class Iterable;  // Has begin() and end() methods returning iterators.
   //
   //     template <typename... SearchParams>
   //     Maybe<size_t> find(kj::ArrayPtr<const Row> table, SearchParams&&...) const;
   //     // Optional. Implements Table::find<Index>(...).
   //
   //     template <typename... SearchParams>
   //     Iterator seek(kj::ArrayPtr<const Row> table, SearchParams&&...) const;
   //     // Optional. Implements Table::seek<Index>() and Table::range<Index>(...).
   //
   //     Iterator begin() const;
   //     Iterator end() const;
   //     // Optional. Implements Table::ordered<Index>().
   //   };
 
 public:
   Table();
   Table(Indexes&&... indexes);
 
   void reserve(size_t size);
   // Pre-allocates space for a table of the given size. Normally a Table grows by re-allocating
   // its backing array whenever more space is needed. Reserving in advance avoids redundantly
   // re-allocating as the table grows.
 
   size_t size() const;
   size_t capacity() const;
 
   void clear();
 
   Row* begin();
   Row* end();
   const Row* begin() const;
   const Row* end() const;
 
   Row& insert(Row&& row);
   Row& insert(const Row& row);
   // Inserts a new row. Throws an exception if this would violate the uniqueness constraints of any
   // of the indexes.
 
   template <typename Collection>
   void insertAll(Collection&& collection);
   template <typename Collection>
   void insertAll(Collection& collection);
   // Given an iterable collection of Rows, inserts all of them into this table. If the input is
   // an rvalue, the rows will be moved rather than copied.
   //
   // If an insertion throws (e.g. because it violates a uniqueness constraint of some index),
   // subsequent insertions do not occur, but previous insertions remain inserted.
 
   template <typename UpdateFunc>
   Row& upsert(Row&& row, UpdateFunc&& update);
   template <typename UpdateFunc>
   Row& upsert(const Row& row, UpdateFunc&& update);
   // Tries to insert a new row. However, if a duplicate already exists (according to some index),
   // then update(Row& existingRow, Row&& newRow) is called to modify the existing row.
 
   template <typename Index, typename... Params>
   kj::Maybe<Row&> find(Params&&... params);
   template <typename Index, typename... Params>
   kj::Maybe<const Row&> find(Params&&... params) const;
   // Using the given index, search for a matching row. What parameters are accepted depends on the
   // index. Not all indexes support this method -- "multimap" indexes may support only range().
 
   template <typename Index, typename... Params, typename Func>
   Row& findOrCreate(Params&&... params, Func&& createFunc);
   // Like find(), but if the row doesn't exist, call a function to create it. createFunc() must
   // return `Row` or something that implicitly converts to `Row`.
   //
   // NOTE: C++ doesn't actually properly support inferring types of a parameter pack at the
   //   beginning of an argument list, but we define a hack to support it below. Don't worry about
   //   it.
 
   template <typename Index, typename BeginKey, typename EndKey>
   auto range(BeginKey&& begin, EndKey&& end);
   template <typename Index, typename BeginKey, typename EndKey>
   auto range(BeginKey&& begin, EndKey&& end) const;
   // Using the given index, look up a range of values, returning an iterable. What parameters are
   // accepted depends on the index. Not all indexes support this method (in particular, unordered
   // indexes normally don't).
 
   template <typename Index>
   _::TableIterable<Row, Index&> ordered();
   template <typename Index>
   _::TableIterable<const Row, const Index&> ordered() const;
   // Returns an iterable over the whole table ordered using the given index. Not all indexes
   // support this method.
 
   template <typename Index, typename... Params>
   auto seek(Params&&... params);
   template <typename Index, typename... Params>
   auto seek(Params&&... params) const;
   // Takes same parameters as find(), but returns an iterator at the position where the search
   // key should go. That is, this returns an iterator that points to the matching entry or, if
   // there is no matching entry, points at the next entry after the key, in order. Or, if there
   // is no such entry, the returned iterator is the same as ordered().end().
   //
   // seek() is only supported by indexes that support ordered(). It returns the same kind of
   // iterator that ordered() uses.
 
   template <typename Index, typename... Params>
   bool eraseMatch(Params&&... params);
   // Erase the row that would be matched by `find<Index>(params)`. Returns true if there was a
   // match.
 
   template <typename Index, typename BeginKey, typename EndKey>
   size_t eraseRange(BeginKey&& begin, EndKey&& end);
   // Erase the row that would be matched by `range<Index>(params)`. Returns the number of
   // elements erased.
 
   void erase(Row& row);
   // Erase the given row.
   //
   // WARNING: This invalidates all iterators, so you can't iterate over rows and erase them this
   //   way. Use `eraseAll()` for that.
 
   Row release(Row& row);
   // Remove the given row from the table and return it in one operation.
   //
   // WARNING: This invalidates all iterators, so you can't iterate over rows and release them this
   //   way.
 
   template <typename Predicate, typename = decltype(instance<Predicate>()(instance<Row&>()))>
   size_t eraseAll(Predicate&& predicate);
   // Erase all rows for which predicate(row) returns true. This scans over the entire table.
 
   template <typename Collection, typename = decltype(instance<Collection>().begin()), bool = true>
   size_t eraseAll(Collection&& collection);
   // Erase all rows in the given iterable collection of rows. This carefully marks rows for
   // deletion in a first pass then deletes them in a second.
 
   template <size_t index = 0, typename... Params>
   kj::Maybe<Row&> find(Params&&... params);
   template <size_t index = 0, typename... Params>
   kj::Maybe<const Row&> find(Params&&... params) const;
   template <size_t index = 0, typename... Params, typename Func>
   Row& findOrCreate(Params&&... params, Func&& createFunc);
   template <size_t index = 0, typename BeginKey, typename EndKey>
   auto range(BeginKey&& begin, EndKey&& end);
   template <size_t index = 0, typename BeginKey, typename EndKey>
   auto range(BeginKey&& begin, EndKey&& end) const;
   template <size_t index = 0>
   _::TableIterable<Row, TypeOfIndex<index, Tuple<Indexes...>>&> ordered();
   template <size_t index = 0>
   _::TableIterable<const Row, const TypeOfIndex<index, Tuple<Indexes...>>&> ordered() const;
   template <size_t index = 0, typename... Params>
   auto seek(Params&&... params);
   template <size_t index = 0, typename... Params>
   auto seek(Params&&... params) const;
   template <size_t index = 0, typename... Params>
   bool eraseMatch(Params&&... params);
   template <size_t index = 0, typename BeginKey, typename EndKey>
   size_t eraseRange(BeginKey&& begin, EndKey&& end);
   // Methods which take an index type as a template parameter can also take an index number. This
   // is useful particularly when you have multiple indexes of the same type but different runtime
   // properties. Additionally, you can omit the template parameter altogether to use the first
   // index.
 
   template <size_t index = 0>
   void verify();
   // Checks the integrity of indexes, throwing an exception if there are any problems. This is
   // intended to be called within the unit test for an index.
 
   template <typename Index, typename First, typename... Rest>
   Row& findOrCreate(First&& first, Rest&&... rest);
   template <size_t index = 0, typename First, typename... Rest>
   Row& findOrCreate(First&& first, Rest&&... rest);
   // HACK: A parameter pack can only be inferred if it lives at the end of the argument list, so
   //   the findOrCreate() definitions from earlier won't actually work. These ones will, but we
   //   have to do some annoying things inside to regroup the arguments.
 
 private:
   Vector<Row> rows;
   Tuple<Indexes...> indexes;
 
   template <size_t index = 0, bool final = (index >= sizeof...(Indexes))>
   class Impl;
   template <typename Func, typename... Params>
   class FindOrCreateImpl;
 
   template <typename ParamsTuple, typename... Params>
   struct FindOrCreateHack;
 
   void eraseImpl(size_t pos);
   template <typename Collection>
   size_t eraseAllImpl(Collection&& collection);
 };
 
 template <typename Callbacks>
 class HashIndex;
 // A Table index based on a hash table.
 //
 // This implementation:
 // * Is based on linear probing, not chaining. It is important to use a high-quality hash function.
 //   Use the KJ hashing library if possible.
 // * Is limited to tables of 2^30 rows or less, mainly to allow for tighter packing with 32-bit
 //   integers instead of 64-bit.
 // * Caches hash codes so that each table row need only be hashed once, and never checks equality
 //   unless hash codes have already been determined to be equal.
 //
 // The `Callbacks` type defines how to compute hash codes and equality. It should be defined like:
 //
 //   class Callbacks {
 //   public:
 //     // In this interface, `SearchParams...` means whatever parameters you want to support in
 //     // a call to table.find(...). By overloading the calls to support various inputs, you can
 //     // affect what table.find(...) accepts.
 //
 //     SearchParam& keyForRow(const Row& row);
 //     // Given a row of the table, return the SearchParams that might be passed to the other
 //     // methods to match this row.
 //
 //     bool matches(const Row&, SearchParams&&...) const;
 //     // Returns true if the row on the left matches thes search params on the right.
 //
 //     uint hashCode(SearchParams&&...) const;
 //     // Computes the hash code of the given search params. Matching rows (as determined by
 //     // matches()) must have the same hash code. Non-matching rows should have different hash
 //     // codes, to the maximum extent possible. Non-matching rows with the same hash code hurt
 //     // performance.
 //   };
 //
 // If your `Callbacks` type has dynamic state, you may pass its constructor parameters as the
 // constructor parameters to `HashIndex`.
 
 template <typename Callbacks>
 class TreeIndex;
 // A Table index based on a B-tree.
 //
 // This allows sorted iteration over rows.
 //
 // The `Callbacks` type defines how to compare rows. It should be defined like:
 //
 //   class Callbacks {
 //   public:
 //     // In this interface, `SearchParams...` means whatever parameters you want to support in
 //     // a call to table.find(...). By overloading the calls to support various inputs, you can
 //     // affect what table.find(...) accepts.
 //
 //     SearchParam& keyForRow(const Row& row);
 //     // Given a row of the table, return the SearchParams that might be passed to the other
 //     // methods to match this row.
 //
 //     bool isBefore(const Row&, SearchParams&&...) const;
 //     // Returns true if the row on the left comes before the search params on the right.
 //
 //     bool matches(const Row&, SearchParams&&...) const;
 //     // Returns true if the row "matches" the search params.
 //   };
 
 // =======================================================================================
 // inline implementation details
 
 namespace _ {  // private
 
 KJ_NORETURN(void throwDuplicateTableRow());
 
 template <typename Dst, typename Src, typename = decltype(instance<Src>().size())>
 inline void tryReserveSize(Dst& dst, Src&& src) { dst.reserve(dst.size() + src.size()); }
 template <typename... Params>
 inline void tryReserveSize(Params&&...) {}
 // If `src` has a `.size()` method, call dst.reserve(dst.size() + src.size()).
 // Otherwise, do nothing.
 
 template <typename Row>
 class TableMapping {
 public:
   TableMapping(Row* table): table(table) {}
   Row& map(size_t i) const { return table[i]; }
 
 private:
   Row* table;
 };
 
 template <typename Row>
 class TableUnmapping {
 public:
   TableUnmapping(Row* table): table(table) {}
   size_t map(Row& row) const { return &row - table; }
   size_t map(Row* row) const { return row - table; }
 
 private:
   Row* table;
 };
 
 template <typename Iterator>
 class IterRange {
 public:
   inline IterRange(Iterator b, Iterator e): b(b), e(e) {}
 
   inline Iterator begin() const { return b; }
   inline Iterator end() const { return e; }
 private:
   Iterator b;
   Iterator e;
 };
 
 template <typename Iterator>
 inline IterRange<Decay<Iterator>> iterRange(Iterator b, Iterator e) {
   return { b, e };
 }
 
 }  // namespace _ (private)
 
 template <typename Row, typename... Indexes>
 template <size_t index>
 class Table<Row, Indexes...>::Impl<index, false> {
 public:
   static void reserve(Table<Row, Indexes...>& table, size_t size) {
     get<index>(table.indexes).reserve(size);
     Impl<index + 1>::reserve(table, size);
   }
 
   static void clear(Table<Row, Indexes...>& table) {
     get<index>(table.indexes).clear();
     Impl<index + 1>::clear(table);
   }
 
   static kj::Maybe<size_t> insert(Table<Row, Indexes...>& table, size_t pos, Row& row, uint skip) {
     if (skip == index) {
       return Impl<index + 1>::insert(table, pos, row, skip);
     }
     auto& indexObj = get<index>(table.indexes);
     KJ_IF_MAYBE(existing, indexObj.insert(table.rows.asPtr(), pos, indexObj.keyForRow(row))) {
       return *existing;
     }
 
     bool success = false;
     KJ_DEFER(if (!success) {
       indexObj.erase(table.rows.asPtr(), pos, indexObj.keyForRow(row));
     });
     auto result = Impl<index + 1>::insert(table, pos, row, skip);
     success = result == nullptr;
     return result;
   }
 
   static void erase(Table<Row, Indexes...>& table, size_t pos, Row& row) {
     auto& indexObj = get<index>(table.indexes);
     indexObj.erase(table.rows.asPtr(), pos, indexObj.keyForRow(row));
     Impl<index + 1>::erase(table, pos, row);
   }
 
   static void move(Table<Row, Indexes...>& table, size_t oldPos, size_t newPos, Row& row) {
     auto& indexObj = get<index>(table.indexes);
     indexObj.move(table.rows.asPtr(), oldPos, newPos, indexObj.keyForRow(row));
     Impl<index + 1>::move(table, oldPos, newPos, row);
   }
 };
 
 template <typename Row, typename... Indexes>
 template <size_t index>
 class Table<Row, Indexes...>::Impl<index, true> {
 public:
   static void reserve(Table<Row, Indexes...>& table, size_t size) {}
   static void clear(Table<Row, Indexes...>& table) {}
   static kj::Maybe<size_t> insert(Table<Row, Indexes...>& table, size_t pos, Row& row, uint skip) {
     return nullptr;
   }
   static void erase(Table<Row, Indexes...>& table, size_t pos, Row& row) {}
   static void move(Table<Row, Indexes...>& table, size_t oldPos, size_t newPos, Row& row) {}
 };
 
 template <typename Row, typename... Indexes>
 Table<Row, Indexes...>::Table() {}
 
 template <typename Row, typename... Indexes>
 Table<Row, Indexes...>::Table(Indexes&&... indexes)
     : indexes(tuple(kj::fwd<Indexes&&>(indexes)...)) {}
 
 template <typename Row, typename... Indexes>
 void Table<Row, Indexes...>::reserve(size_t size) {
   rows.reserve(size);
   Impl<>::reserve(*this, size);
 }
 
 template <typename Row, typename... Indexes>
 size_t Table<Row, Indexes...>::size() const {
   return rows.size();
 }
 template <typename Row, typename... Indexes>
 void Table<Row, Indexes...>::clear() {
   Impl<>::clear(*this);
   rows.clear();
 }
 template <typename Row, typename... Indexes>
 size_t Table<Row, Indexes...>::capacity() const {
   return rows.capacity();
 }
 
 template <typename Row, typename... Indexes>
 Row* Table<Row, Indexes...>::begin() {
   return rows.begin();
 }
 template <typename Row, typename... Indexes>
 Row* Table<Row, Indexes...>::end() {
   return rows.end();
 }
 template <typename Row, typename... Indexes>
 const Row* Table<Row, Indexes...>::begin() const {
   return rows.begin();
 }
 template <typename Row, typename... Indexes>
 const Row* Table<Row, Indexes...>::end() const {
   return rows.end();
 }
 
 template <typename Row, typename... Indexes>
 Row& Table<Row, Indexes...>::insert(Row&& row) {
   KJ_IF_MAYBE(existing, Impl<>::insert(*this, rows.size(), row, kj::maxValue)) {
     _::throwDuplicateTableRow();
   } else {
     return rows.add(kj::mv(row));
   }
 }
 template <typename Row, typename... Indexes>
 Row& Table<Row, Indexes...>::insert(const Row& row) {
   return insert(kj::cp(row));
 }
 
 template <typename Row, typename... Indexes>
 template <typename Collection>
 void Table<Row, Indexes...>::insertAll(Collection&& collection) {
   _::tryReserveSize(*this, collection);
   for (auto& row: collection) {
     insert(kj::mv(row));
   }
 }
 
 template <typename Row, typename... Indexes>
 template <typename Collection>
 void Table<Row, Indexes...>::insertAll(Collection& collection) {
   _::tryReserveSize(*this, collection);
   for (auto& row: collection) {
     insert(row);
   }
 }
 
 template <typename Row, typename... Indexes>
 template <typename UpdateFunc>
 Row& Table<Row, Indexes...>::upsert(Row&& row, UpdateFunc&& update) {
   KJ_IF_MAYBE(existing, Impl<>::insert(*this, rows.size(), row, kj::maxValue)) {
     update(rows[*existing], kj::mv(row));
     return rows[*existing];
   } else {
     return rows.add(kj::mv(row));
   }
 }
 template <typename Row, typename... Indexes>
 template <typename UpdateFunc>
 Row& Table<Row, Indexes...>::upsert(const Row& row, UpdateFunc&& update) {
   return upsert(kj::cp(row), kj::fwd<UpdateFunc>(update));
 }
 
 template <typename Row, typename... Indexes>
 template <typename Index, typename... Params>
 kj::Maybe<Row&> Table<Row, Indexes...>::find(Params&&... params) {
   return find<indexOfType<Index, Tuple<Indexes...>>()>(kj::fwd<Params>(params)...);
 }
 template <typename Row, typename... Indexes>
 template <size_t index, typename... Params>
 kj::Maybe<Row&> Table<Row, Indexes...>::find(Params&&... params) {
   KJ_IF_MAYBE(pos, get<index>(indexes).find(rows.asPtr(), kj::fwd<Params>(params)...)) {
     return rows[*pos];
   } else {
     return nullptr;
   }
 }
 template <typename Row, typename... Indexes>
 template <typename Index, typename... Params>
 kj::Maybe<const Row&> Table<Row, Indexes...>::find(Params&&... params) const {
   return find<indexOfType<Index, Tuple<Indexes...>>()>(kj::fwd<Params>(params)...);
 }
 template <typename Row, typename... Indexes>
 template <size_t index, typename... Params>
 kj::Maybe<const Row&> Table<Row, Indexes...>::find(Params&&... params) const {
   KJ_IF_MAYBE(pos, get<index>(indexes).find(rows.asPtr(), kj::fwd<Params>(params)...)) {
     return rows[*pos];
   } else {
     return nullptr;
   }
 }
 
 template <typename Row, typename... Indexes>
 template <typename Func, typename... Params>
 class Table<Row, Indexes...>::FindOrCreateImpl {
 public:
   template <size_t index>
   static Row& apply(Table<Row, Indexes...>& table, Params&&... params, Func&& createFunc) {
     auto pos = table.rows.size();
     KJ_IF_MAYBE(existing, get<index>(table.indexes).insert(table.rows.asPtr(), pos, params...)) {
       return table.rows[*existing];
     } else {
       bool success = false;
       KJ_DEFER({
         if (!success) {
           get<index>(table.indexes).erase(table.rows.asPtr(), pos, params...);
         }
       });
       auto& newRow = table.rows.add(createFunc());
       KJ_DEFER({
         if (!success) {
           table.rows.removeLast();
         }
       });
       if (Table<Row, Indexes...>::template Impl<>::insert(table, pos, newRow, index) == nullptr) {
         success = true;
       } else {
         _::throwDuplicateTableRow();
       }
       return newRow;
     }
   }
 };
 
 template <typename Row, typename... Indexes>
 template <typename... T, typename U, typename V, typename... W>
 struct Table<Row, Indexes...>::FindOrCreateHack<_::Tuple<T...>, U, V, W...>
     : public FindOrCreateHack<_::Tuple<T..., U>, V, W...> {};
 template <typename Row, typename... Indexes>
 template <typename... T, typename U>
 struct Table<Row, Indexes...>::FindOrCreateHack<_::Tuple<T...>, U>
     : public FindOrCreateImpl<U, T...> {};
 // This awful hack works around C++'s lack of support for parameter packs anywhere other than at
 // the end of an argument list. We accumulate all of the types except for the last one into a
 // Tuple, then forward to FindOrCreateImpl with the last parameter as the Func.
 
 template <typename Row, typename... Indexes>
 template <typename Index, typename First, typename... Rest>
 Row& Table<Row, Indexes...>::findOrCreate(First&& first, Rest&&... rest) {
   return findOrCreate<indexOfType<Index, Tuple<Indexes...>>()>(
       kj::fwd<First>(first), kj::fwd<Rest>(rest)...);
 }
 template <typename Row, typename... Indexes>
 template <size_t index, typename First, typename... Rest>
 Row& Table<Row, Indexes...>::findOrCreate(First&& first, Rest&&... rest) {
   return FindOrCreateHack<_::Tuple<>, First, Rest...>::template apply<index>(
       *this, kj::fwd<First>(first), kj::fwd<Rest>(rest)...);
 }
 
 template <typename Row, typename... Indexes>
 template <typename Index, typename BeginKey, typename EndKey>
 auto Table<Row, Indexes...>::range(BeginKey&& begin, EndKey&& end) {
   return range<indexOfType<Index, Tuple<Indexes...>>()>(
       kj::fwd<BeginKey>(begin), kj::fwd<EndKey>(end));
 }
 template <typename Row, typename... Indexes>
 template <size_t index, typename BeginKey, typename EndKey>
 auto Table<Row, Indexes...>::range(BeginKey&& begin, EndKey&& end) {
   auto inner = _::iterRange(get<index>(indexes).seek(rows.asPtr(), kj::fwd<BeginKey>(begin)),
                             get<index>(indexes).seek(rows.asPtr(), kj::fwd<EndKey>(end)));
   return _::TableIterable<Row, decltype(inner)>(kj::mv(inner), rows.begin());
 }
 template <typename Row, typename... Indexes>
 template <typename Index, typename BeginKey, typename EndKey>
 auto Table<Row, Indexes...>::range(BeginKey&& begin, EndKey&& end) const {
   return range<indexOfType<Index, Tuple<Indexes...>>()>(
       kj::fwd<BeginKey>(begin), kj::fwd<EndKey>(end));
 }
 template <typename Row, typename... Indexes>
 template <size_t index, typename BeginKey, typename EndKey>
 auto Table<Row, Indexes...>::range(BeginKey&& begin, EndKey&& end) const {
   auto inner = _::iterRange(get<index>(indexes).seek(rows.asPtr(), kj::fwd<BeginKey>(begin)),
                             get<index>(indexes).seek(rows.asPtr(), kj::fwd<EndKey>(end)));
   return _::TableIterable<const Row, decltype(inner)>(kj::mv(inner), rows.begin());
 }
 
 template <typename Row, typename... Indexes>
 template <typename Index>
 _::TableIterable<Row, Index&> Table<Row, Indexes...>::ordered() {
   return ordered<indexOfType<Index, Tuple<Indexes...>>()>();
 }
 template <typename Row, typename... Indexes>
 template <size_t index>
 _::TableIterable<Row, TypeOfIndex<index, Tuple<Indexes...>>&> Table<Row, Indexes...>::ordered() {
   return { get<index>(indexes), rows.begin() };
 }
 template <typename Row, typename... Indexes>
 template <typename Index>
 _::TableIterable<const Row, const Index&> Table<Row, Indexes...>::ordered() const {
   return ordered<indexOfType<Index, Tuple<Indexes...>>()>();
 }
 template <typename Row, typename... Indexes>
 template <size_t index>
 _::TableIterable<const Row, const TypeOfIndex<index, Tuple<Indexes...>>&>
 Table<Row, Indexes...>::ordered() const {
   return { get<index>(indexes), rows.begin() };
 }
 
 template <typename Row, typename... Indexes>
 template <typename Index, typename... Params>
 auto Table<Row, Indexes...>::seek(Params&&... params) {
   return seek<indexOfType<Index, Tuple<Indexes...>>()>(kj::fwd<Params>(params)...);
 }
 template <typename Row, typename... Indexes>
 template <size_t index, typename... Params>
 auto Table<Row, Indexes...>::seek(Params&&... params) {
   auto inner = get<index>(indexes).seek(rows.asPtr(), kj::fwd<Params>(params)...);
   return _::TableIterator<Row, decltype(inner)>(kj::mv(inner), rows.begin());
 }
 template <typename Row, typename... Indexes>
 template <typename Index, typename... Params>
 auto Table<Row, Indexes...>::seek(Params&&... params) const {
   return seek<indexOfType<Index, Tuple<Indexes...>>()>(kj::fwd<Params>(params)...);
 }
 template <typename Row, typename... Indexes>
 template <size_t index, typename... Params>
 auto Table<Row, Indexes...>::seek(Params&&... params) const {
   auto inner = get<index>(indexes).seek(rows.asPtr(), kj::fwd<Params>(params)...);
   return _::TableIterator<Row, decltype(inner)>(kj::mv(inner), rows.begin());
 }
 
 template <typename Row, typename... Indexes>
 template <typename Index, typename... Params>
 bool Table<Row, Indexes...>::eraseMatch(Params&&... params) {
   return eraseMatch<indexOfType<Index, Tuple<Indexes...>>()>(kj::fwd<Params>(params)...);
 }
 template <typename Row, typename... Indexes>
 template <size_t index, typename... Params>
 bool Table<Row, Indexes...>::eraseMatch(Params&&... params) {
   KJ_IF_MAYBE(pos, get<index>(indexes).find(rows.asPtr(), kj::fwd<Params>(params)...)) {
     eraseImpl(*pos);
     return true;
   } else {
     return false;
   }
 }
 
 template <typename Row, typename... Indexes>
 template <typename Index, typename BeginKey, typename EndKey>
 size_t Table<Row, Indexes...>::eraseRange(BeginKey&& begin, EndKey&& end) {
   return eraseRange<indexOfType<Index, Tuple<Indexes...>>()>(
       kj::fwd<BeginKey>(begin), kj::fwd<EndKey>(end));
 }
 template <typename Row, typename... Indexes>
 template <size_t index, typename BeginKey, typename EndKey>
 size_t Table<Row, Indexes...>::eraseRange(BeginKey&& begin, EndKey&& end) {
   auto inner = _::iterRange(get<index>(indexes).seek(rows.asPtr(), kj::fwd<BeginKey>(begin)),
                             get<index>(indexes).seek(rows.asPtr(), kj::fwd<EndKey>(end)));
   return eraseAllImpl(inner);
 }
 
 template <typename Row, typename... Indexes>
 template <size_t index>
 void Table<Row, Indexes...>::verify() {
   get<index>(indexes).verify(rows.asPtr());
 }
 
 template <typename Row, typename... Indexes>
 void Table<Row, Indexes...>::erase(Row& row) {
   KJ_TABLE_IREQUIRE(&row >= rows.begin() && &row < rows.end(), "row is not a member of this table");
   eraseImpl(&row - rows.begin());
 }
 template <typename Row, typename... Indexes>
 void Table<Row, Indexes...>::eraseImpl(size_t pos) {
   Impl<>::erase(*this, pos, rows[pos]);
   size_t back = rows.size() - 1;
   if (pos != back) {
     Impl<>::move(*this, back, pos, rows[back]);
     rows[pos] = kj::mv(rows[back]);
   }
   rows.removeLast();
 }
 
 template <typename Row, typename... Indexes>
 Row Table<Row, Indexes...>::release(Row& row) {
   KJ_TABLE_IREQUIRE(&row >= rows.begin() && &row < rows.end(), "row is not a member of this table");
   size_t pos = &row - rows.begin();
   Impl<>::erase(*this, pos, row);
   Row result = kj::mv(row);
   size_t back = rows.size() - 1;
   if (pos != back) {
     Impl<>::move(*this, back, pos, rows[back]);
     row = kj::mv(rows[back]);
   }
   rows.removeLast();
   return result;
 }
 
 template <typename Row, typename... Indexes>
 template <typename Predicate, typename>
 size_t Table<Row, Indexes...>::eraseAll(Predicate&& predicate) {
   size_t count = 0;
   for (size_t i = 0; i < rows.size();) {
     if (predicate(rows[i])) {
       eraseImpl(i);
       ++count;
       // eraseImpl() replaces the erased row with the last row, so don't increment i here; repeat
       // with the same i.
     } else {
       ++i;
     }
   }
   return count;
 }
 
 template <typename Row, typename... Indexes>
 template <typename Collection, typename, bool>
 size_t Table<Row, Indexes...>::eraseAll(Collection&& collection) {
   return eraseAllImpl(MappedIterable<Collection&, _::TableUnmapping<Row>>(
       collection, rows.begin()));
 }
 
 template <typename Row, typename... Indexes>
 template <typename Collection>
 size_t Table<Row, Indexes...>::eraseAllImpl(Collection&& collection) {
   // We need to transform the collection of row numbers into a sequence of erasures, accounting
   // for the fact that each erasure re-positions the last row into its slot.
   Vector<size_t> erased;
   _::tryReserveSize(erased, collection);
   for (size_t pos: collection) {
     while (pos >= rows.size() - erased.size()) {
       // Oops, the next item to be erased is already scheduled to be moved to a different location
       // due to a previous erasure. Figure out where it will be at this point.
       size_t erasureNumber = rows.size() - pos - 1;
       pos = erased[erasureNumber];
     }
     erased.add(pos);
   }
 
   // Now we can execute the sequence of erasures.
   for (size_t pos: erased) {
     eraseImpl(pos);
   }
 
   return erased.size();
 }
 
 // -----------------------------------------------------------------------------
 // Hash table index
 
 namespace _ {  // private
 
 void logHashTableInconsistency();
 
 struct HashBucket {
   uint hash;
   uint value;
 
   HashBucket() = default;
   HashBucket(uint hash, uint pos)
       : hash(hash), value(pos + 2) {}
 
   inline bool isEmpty() const { return value == 0; }
   inline bool isErased() const { return value == 1; }
   inline bool isOccupied() const { return value >= 2; }
   template <typename Row>
   inline Row& getRow(ArrayPtr<Row> table) const { return table[getPos()]; }
   template <typename Row>
   inline const Row& getRow(ArrayPtr<const Row> table) const { return table[getPos()]; }
   inline bool isPos(uint pos) const { return pos + 2 == value; }
   inline uint getPos() const {
     KJ_TABLE_IASSERT(value >= 2);
     return value - 2;
   }
   inline void setEmpty() { value = 0; }
   inline void setErased() { value = 1; }
   inline void setPos(uint pos) { value = pos + 2; }
 };
 
 inline size_t probeHash(const kj::Array<HashBucket>& buckets, size_t i) {
   // TODO(perf): Is linear probing OK or should we do something fancier?
   if (++i == buckets.size()) {
     return 0;
   } else {
     return i;
   }
 }
 
 kj::Array<HashBucket> rehash(kj::ArrayPtr<const HashBucket> oldBuckets, size_t targetSize);
 
 uint chooseBucket(uint hash, uint count);
 
 }  // namespace _ (private)
 
 template <typename Callbacks>
 class HashIndex {
 public:
   HashIndex() = default;
   template <typename... Params>
   HashIndex(Params&&... params): cb(kj::fwd<Params>(params)...) {}
 
   size_t capacity() {
     // This method is for testing.
     return buckets.size();
   }
 
   void reserve(size_t size) {
     if (buckets.size() < size * 2) {
       rehash(size);
     }
   }
 
   void clear() {
     erasedCount = 0;
     memset(buckets.begin(), 0, buckets.asBytes().size());
   }
 
   template <typename Row>
   decltype(auto) keyForRow(Row&& row) const {
     return cb.keyForRow(kj::fwd<Row>(row));
   }
 
   template <typename Row, typename... Params>
   kj::Maybe<size_t> insert(kj::ArrayPtr<Row> table, size_t pos, Params&&... params) {
     if (buckets.size() * 2 < (table.size() + 1 + erasedCount) * 3) {
       // Load factor is more than 2/3, let's rehash so that it's 1/3, i.e. double the buckets.
       // Note that rehashing also cleans up erased entries, so we may not actually be doubling if
       // there are a lot of erasures. Nevertheless, this gives us amortized constant time -- it
       // would take at least O(table.size()) more insertions (whether or not erasures occur)
       // before another rehash is needed.
       rehash((table.size() + 1) * 3);
     }
 
     uint hashCode = cb.hashCode(params...);
     Maybe<_::HashBucket&> erasedSlot;
     for (uint i = _::chooseBucket(hashCode, buckets.size());; i = _::probeHash(buckets, i)) {
       auto& bucket = buckets[i];
       if (bucket.isEmpty()) {
         // no duplicates found
         KJ_IF_MAYBE(s, erasedSlot) {
           --erasedCount;
           *s = { hashCode, uint(pos) };
         } else {
           bucket = { hashCode, uint(pos) };
         }
         return nullptr;
       } else if (bucket.isErased()) {
         // We can fill in the erased slot. However, we have to keep searching to make sure there
         // are no duplicates before we do that.
         if (erasedSlot == nullptr) {
           erasedSlot = bucket;
         }
       } else if (bucket.hash == hashCode &&
                  cb.matches(bucket.getRow(table), params...)) {
         // duplicate row
         return size_t(bucket.getPos());
       }
     }
   }
 
   template <typename Row, typename... Params>
   void erase(kj::ArrayPtr<Row> table, size_t pos, Params&&... params) {
     uint hashCode = cb.hashCode(params...);
     for (uint i = _::chooseBucket(hashCode, buckets.size());; i = _::probeHash(buckets, i)) {
       auto& bucket = buckets[i];
       if (bucket.isPos(pos)) {
         // found it
         ++erasedCount;
         bucket.setErased();
         return;
       } else if (bucket.isEmpty()) {
         // can't find the bucket, something is very wrong
         _::logHashTableInconsistency();
         return;
       }
     }
   }
 
   template <typename Row, typename... Params>
   void move(kj::ArrayPtr<Row> table, size_t oldPos, size_t newPos, Params&&... params) {
     uint hashCode = cb.hashCode(params...);
     for (uint i = _::chooseBucket(hashCode, buckets.size());; i = _::probeHash(buckets, i)) {
       auto& bucket = buckets[i];
       if (bucket.isPos(oldPos)) {
         // found it
         bucket.setPos(newPos);
         return;
       } else if (bucket.isEmpty()) {
         // can't find the bucket, something is very wrong
         _::logHashTableInconsistency();
         return;
       }
     }
   }
 
   template <typename Row, typename... Params>
   Maybe<size_t> find(kj::ArrayPtr<Row> table, Params&&... params) const {
     if (buckets.size() == 0) return nullptr;
 
     uint hashCode = cb.hashCode(params...);
     for (uint i = _::chooseBucket(hashCode, buckets.size());; i = _::probeHash(buckets, i)) {
       auto& bucket = buckets[i];
       if (bucket.isEmpty()) {
         // not found.
         return nullptr;
       } else if (bucket.isErased()) {
         // skip, keep searching
       } else if (bucket.hash == hashCode &&
                  cb.matches(bucket.getRow(table), params...)) {
         // found
         return size_t(bucket.getPos());
       }
     }
   }
 
   // No begin() nor end() because hash tables are not usefully ordered.
 
 private:
   Callbacks cb;
   size_t erasedCount = 0;
   Array<_::HashBucket> buckets;
 
   void rehash(size_t targetSize) {
     buckets = _::rehash(buckets, targetSize);
     erasedCount = 0;
   }
 };
 
 // -----------------------------------------------------------------------------
 // BTree index
 
 namespace _ {  // private
 
 KJ_ALWAYS_INLINE(void compilerBarrier());
 void compilerBarrier() {
   // Make sure that reads occurring before this call cannot be re-ordered to happen after
   // writes that occur after this call. We need this in a couple places below to prevent C++
   // strict aliasing rules from breaking things.
 #if _MSC_VER
   _ReadWriteBarrier();
 #else
   __asm__ __volatile__("": : :"memory");
 #endif
 }
 
 template <typename T>
 inline void acopy(T* to, T* from, size_t size) { memcpy(to, from, size * sizeof(T)); }
 template <typename T>
 inline void amove(T* to, T* from, size_t size) { memmove(to, from, size * sizeof(T)); }
 template <typename T>
 inline void azero(T* ptr, size_t size) { memset(ptr, 0, size * sizeof(T)); }
 // memcpy/memmove/memset variants that count size in elements, not bytes.
 //
 // TODO(cleanup): These are generally useful, put them somewhere.
 
 class BTreeImpl {
 public:
   class Iterator;
   class MaybeUint;
   struct NodeUnion;
   struct Leaf;
   struct Parent;
   struct Freelisted;
 
   class SearchKey {
     // Passed to methods that need to search the tree. This class allows most of the B-tree
     // implementation to be kept out of templates, avoiding code bloat, at the cost of some
     // performance trade-off. In order to lessen the performance cost of virtual calls, we design
     // this interface so that it only needs to be called once per tree node, rather than once per
     // comparison.
 
   public:
     virtual uint search(const Parent& parent) const = 0;
     virtual uint search(const Leaf& leaf) const = 0;
     // Binary search for the first key/row in the parent/leaf that is equal to or comes after the
     // search key.
 
     virtual bool isAfter(uint rowIndex) const = 0;
     // Returns true if the key comes after the value in the given row.
   };
 
   BTreeImpl();
   ~BTreeImpl() noexcept(false);
 
   KJ_DISALLOW_COPY(BTreeImpl);
   BTreeImpl(BTreeImpl&& other);
   BTreeImpl& operator=(BTreeImpl&& other);
 
   void logInconsistency() const;
 
   void reserve(size_t size);
 
   void clear();
 
   Iterator begin() const;
   Iterator end() const;
 
   Iterator search(const SearchKey& searchKey) const;
   // Find the "first" row (in sorted order) for which searchKey.isAfter(rowNumber) returns true.
 
   Iterator insert(const SearchKey& searchKey);
   // Like search() but ensures that there is room in the leaf node to insert a new row.
 
   void erase(uint row, const SearchKey& searchKey);
   // Erase the given row number from the tree. searchKey.isAfter() returns true for the given row
   // and all rows after it.
 
   void renumber(uint oldRow, uint newRow, const SearchKey& searchKey);
   // Renumber the given row from oldRow to newRow. searchKey.isAfter() returns true for oldRow and
   // all rows after it. (It will not be called on newRow.)
 
   void verify(size_t size, FunctionParam<bool(uint, uint)>);
 
 private:
   NodeUnion* tree;        // allocated with aligned_alloc aligned to cache lines
   uint treeCapacity;
   uint height;            // height of *parent* tree -- does not include the leaf level
   uint freelistHead;
   uint freelistSize;
   uint beginLeaf;
   uint endLeaf;
   void growTree(uint minCapacity = 0);
 
   template <typename T>
   struct AllocResult;
 
   template <typename T>
   inline AllocResult<T> alloc();
   inline void free(uint pos);
 
   inline uint split(Parent& src, uint srcPos, Parent& dst, uint dstPos);
   inline uint split(Leaf& dst, uint dstPos, Leaf& src, uint srcPos);
   inline void merge(Parent& dst, uint dstPos, uint pivot, Parent& src);
   inline void merge(Leaf& dst, uint dstPos, uint pivot, Leaf& src);
   inline void move(Parent& dst, uint dstPos, Parent& src);
   inline void move(Leaf& dst, uint dstPos, Leaf& src);
   inline void rotateLeft(
       Parent& left, Parent& right, Parent& parent, uint indexInParent, MaybeUint*& fixup);
   inline void rotateLeft(
       Leaf& left, Leaf& right, Parent& parent, uint indexInParent, MaybeUint*& fixup);
   inline void rotateRight(Parent& left, Parent& right, Parent& parent, uint indexInParent);
   inline void rotateRight(Leaf& left, Leaf& right, Parent& parent, uint indexInParent);
 
   template <typename Node>
   inline Node& insertHelper(const SearchKey& searchKey,
       Node& node, Parent* parent, uint indexInParent, uint pos);
 
   template <typename Node>
   inline Node& eraseHelper(
       Node& node, Parent* parent, uint indexInParent, uint pos, MaybeUint*& fixup);
 
   size_t verifyNode(size_t size, FunctionParam<bool(uint, uint)>&,
                     uint pos, uint height, MaybeUint maxRow);
 
   static const NodeUnion EMPTY_NODE;
 };
 
 class BTreeImpl::MaybeUint {
   // A nullable uint, using the value zero to mean null and shifting all other values up by 1.
 public:
   MaybeUint() = default;
   inline MaybeUint(uint i): i(i - 1) {}
   inline MaybeUint(decltype(nullptr)): i(0) {}
 
   inline bool operator==(decltype(nullptr)) const { return i == 0; }
   inline bool operator==(uint j) const { return i == j + 1; }
   inline bool operator==(const MaybeUint& other) const { return i == other.i; }
   inline bool operator!=(decltype(nullptr)) const { return i != 0; }
   inline bool operator!=(uint j) const { return i != j + 1; }
   inline bool operator!=(const MaybeUint& other) const { return i != other.i; }
 
   inline MaybeUint& operator=(decltype(nullptr)) { i = 0; return *this; }
   inline MaybeUint& operator=(uint j) { i = j + 1; return *this; }
 
   inline uint operator*() const { KJ_TABLE_IREQUIRE(i != 0); return i - 1; }
 
   template <typename Func>
   inline bool check(Func& func) const { return i != 0 && func(i - 1); }
   // Equivalent to *this != nullptr && func(**this)
 
   kj::String toString() const;
 
 private:
   uint i;
 };
 
 struct BTreeImpl::Leaf {
   uint next;
   uint prev;
   // Pointers to next and previous nodes at the same level, used for fast iteration.
 
   static constexpr size_t NROWS = 14;
   MaybeUint rows[NROWS];
   // Pointers to table rows, offset by 1 so that 0 is an empty value.
 
   inline bool isFull() const;
   inline bool isMostlyFull() const;
   inline bool isHalfFull() const;
 
   inline void insert(uint i, uint newRow) {
     KJ_TABLE_IREQUIRE(rows[Leaf::NROWS - 1] == nullptr);  // check not full
 
     amove(rows + i + 1, rows + i, Leaf::NROWS - (i + 1));
     rows[i] = newRow;
   }
 
   inline void erase(uint i) {
     KJ_TABLE_IREQUIRE(rows[0] != nullptr);  // check not empty
 
     amove(rows + i, rows + i + 1, Leaf::NROWS - (i + 1));
     rows[Leaf::NROWS - 1] = nullptr;
   }
 
   inline uint size() const {
     static_assert(Leaf::NROWS == 14, "logic here needs updating");
 
     // Binary search for first empty element in `rows`, or return 14 if no empty elements. We do
     // this in a branch-free manner. Since there are 15 possible results (0 through 14, inclusive),
     // this isn't a perfectly balanced binary search. We carefully choose the split points so that
     // there's no way we'll try to dereference row[14] or later (which would be a buffer overflow).
     uint i = (rows[6] != nullptr) * 7;
     i += (rows[i + 3] != nullptr) * 4;
     i += (rows[i + 1] != nullptr) * 2;
     i += (rows[i    ] != nullptr);
     return i;
   }
 
   template <typename Func>
   inline uint binarySearch(Func& predicate) const {
     // Binary search to find first row for which predicate(row) is false.
 
     static_assert(Leaf::NROWS == 14, "logic here needs updating");
 
     // See comments in size().
     uint i = (rows[6].check(predicate)) * 7;
     i += (rows[i + 3].check(predicate)) * 4;
     i += (rows[i + 1].check(predicate)) * 2;
     if (i != 6) {  // don't redundantly check row 6
       i += (rows[i    ].check(predicate));
     }
     return i;
   }
 };
 
 struct BTreeImpl::Parent {
   uint unused;
   // Not used. May be arbitrarily non-zero due to overlap with Freelisted::nextOffset.
 
   static constexpr size_t NKEYS = 7;
   MaybeUint keys[NKEYS];
   // Pointers to table rows, offset by 1 so that 0 is an empty value.
   //
   // Each keys[i] specifies the table row which is the "last" row found under children[i].
   //
   // Note that `keys` has size 7 but `children` has size 8. `children[8]`'s "last row" is not
   // recorded here, because the Parent's Parent records it instead. (Or maybe the Parent's Parent's
   // Parent, if this Parent is `children[8]` of its own Parent. And so on.)
 
   static constexpr size_t NCHILDREN = NKEYS + 1;
   uint children[NCHILDREN];
   // Pointers to children. Not offset because the root is always at position 0, and a pointer
   // to the root would be nonsensical.
 
   inline bool isFull() const;
   inline bool isMostlyFull() const;
   inline bool isHalfFull() const;
   inline void initRoot(uint key, uint leftChild, uint rightChild);
   inline void insertAfter(uint i, uint splitKey, uint child);
   inline void eraseAfter(uint i);
 
   inline uint keyCount() const {
     static_assert(Parent::NKEYS == 7, "logic here needs updating");
 
     // Binary search for first empty element in `keys`, or return 7 if no empty elements. We do
     // this in a branch-free manner. Since there are 8 possible results (0 through 7, inclusive),
     // this is a perfectly balanced binary search.
     uint i = (keys[3] != nullptr) * 4;
     i += (keys[i + 1] != nullptr) * 2;
     i += (keys[i    ] != nullptr);
     return i;
   }
 
   template <typename Func>
   inline uint binarySearch(Func& predicate) const {
     // Binary search to find first key for which predicate(key) is false.
 
     static_assert(Parent::NKEYS == 7, "logic here needs updating");
 
     // See comments in size().
     uint i = (keys[3].check(predicate)) * 4;
     i += (keys[i + 1].check(predicate)) * 2;
     i += (keys[i    ].check(predicate));
     return i;
   }
 };
 
 struct BTreeImpl::Freelisted {
   int nextOffset;
   // The next node in the freelist is at: this + 1 + nextOffset
   //
   // Hence, newly-allocated space can initialize this to zero.
 
   uint zero[15];
   // Freelisted entries are always zero'd.
 };
 
 struct BTreeImpl::NodeUnion {
   union {
     Freelisted freelist;
     // If this node is in the freelist.
 
     Leaf leaf;
     // If this node is a leaf.
 
     Parent parent;
     // If this node is not a leaf.
   };
 
   inline operator Leaf&() { return leaf; }
   inline operator Parent&() { return parent; }
   inline operator const Leaf&() const { return leaf; }
   inline operator const Parent&() const { return parent; }
 };
 
 static_assert(sizeof(BTreeImpl::Parent) == 64,
     "BTreeImpl::Parent should be optimized to fit a cache line");
 static_assert(sizeof(BTreeImpl::Leaf) == 64,
     "BTreeImpl::Leaf should be optimized to fit a cache line");
 static_assert(sizeof(BTreeImpl::Freelisted) == 64,
     "BTreeImpl::Freelisted should be optimized to fit a cache line");
 static_assert(sizeof(BTreeImpl::NodeUnion) == 64,
     "BTreeImpl::NodeUnion should be optimized to fit a cache line");
 
 bool BTreeImpl::Leaf::isFull() const {
   return rows[Leaf::NROWS - 1] != nullptr;
 }
 bool BTreeImpl::Leaf::isMostlyFull() const {
   return rows[Leaf::NROWS / 2] != nullptr;
 }
 bool BTreeImpl::Leaf::isHalfFull() const {
   KJ_TABLE_IASSERT(rows[Leaf::NROWS / 2 - 1] != nullptr);
   return rows[Leaf::NROWS / 2] == nullptr;
 }
 
 bool BTreeImpl::Parent::isFull() const {
   return keys[Parent::NKEYS - 1] != nullptr;
 }
 bool BTreeImpl::Parent::isMostlyFull() const {
   return keys[Parent::NKEYS / 2] != nullptr;
 }
 bool BTreeImpl::Parent::isHalfFull() const {
   KJ_TABLE_IASSERT(keys[Parent::NKEYS / 2 - 1] != nullptr);
   return keys[Parent::NKEYS / 2] == nullptr;
 }
 
 class BTreeImpl::Iterator {
 public:
   Iterator(const NodeUnion* tree, const Leaf* leaf, uint row)
       : tree(tree), leaf(leaf), row(row) {}
 
   size_t operator*() const {
     KJ_TABLE_IREQUIRE(row < Leaf::NROWS && leaf->rows[row] != nullptr,
         "tried to dereference end() iterator");
     return *leaf->rows[row];
   }
 
   inline Iterator& operator++() {
     KJ_TABLE_IREQUIRE(leaf->rows[row] != nullptr, "B-tree iterator overflow");
     ++row;
     if (row >= Leaf::NROWS || leaf->rows[row] == nullptr) {
       if (leaf->next == 0) {
         // at end; stay on current leaf
       } else {
         leaf = &tree[leaf->next].leaf;
         row = 0;
       }
     }
     return *this;
   }
   inline Iterator operator++(int) {
     Iterator other = *this;
     ++*this;
     return other;
   }
 
   inline Iterator& operator--() {
     if (row == 0) {
       KJ_TABLE_IREQUIRE(leaf->prev != 0, "B-tree iterator underflow");
       leaf = &tree[leaf->prev].leaf;
       row = leaf->size() - 1;
     } else {
       --row;
     }
     return *this;
   }
   inline Iterator operator--(int) {
     Iterator other = *this;
     --*this;
     return other;
   }
 
   inline bool operator==(const Iterator& other) const {
     return leaf == other.leaf && row == other.row;
   }
   inline bool operator!=(const Iterator& other) const {
     return leaf != other.leaf || row != other.row;
   }
 
   bool isEnd() {
     return row == Leaf::NROWS || leaf->rows[row] == nullptr;
   }
 
   void insert(BTreeImpl& impl, uint newRow) {
     KJ_TABLE_IASSERT(impl.tree == tree);
     const_cast<Leaf*>(leaf)->insert(row, newRow);
   }
 
   void erase(BTreeImpl& impl) {
     KJ_TABLE_IASSERT(impl.tree == tree);
     const_cast<Leaf*>(leaf)->erase(row);
   }
 
   void replace(BTreeImpl& impl, uint newRow) {
     KJ_TABLE_IASSERT(impl.tree == tree);
     const_cast<Leaf*>(leaf)->rows[row] = newRow;
   }
 
 private:
   const NodeUnion* tree;
   const Leaf* leaf;
   uint row;
 };
 
 inline BTreeImpl::Iterator BTreeImpl::begin() const {
   return { tree, &tree[beginLeaf].leaf, 0 };
 }
 inline BTreeImpl::Iterator BTreeImpl::end() const {
   auto& leaf = tree[endLeaf].leaf;
   return { tree, &leaf, leaf.size() };
 }
 
 }  // namespace _ (private)
 
 template <typename Callbacks>
 class TreeIndex {
 public:
   TreeIndex() = default;
   template <typename... Params>
   TreeIndex(Params&&... params): cb(kj::fwd<Params>(params)...) {}
 
   template <typename Row>
   void verify(kj::ArrayPtr<Row> table) {
     impl.verify(table.size(), [&](uint i, uint j) {
       return cb.isBefore(table[i], table[j]);
     });
   }
 
   inline void reserve(size_t size) { impl.reserve(size); }
   inline void clear() { impl.clear(); }
   inline auto begin() const { return impl.begin(); }
   inline auto end() const { return impl.end(); }
 
   template <typename Row>
   decltype(auto) keyForRow(Row&& row) const {
     return cb.keyForRow(kj::fwd<Row>(row));
   }
 
   template <typename Row, typename... Params>
   kj::Maybe<size_t> insert(kj::ArrayPtr<Row> table, size_t pos, Params&&... params) {
     auto iter = impl.insert(searchKey(table, params...));
 
     if (!iter.isEnd() && cb.matches(table[*iter], params...)) {
       return *iter;
     } else {
       iter.insert(impl, pos);
       return nullptr;
     }
   }
 
   template <typename Row, typename... Params>
   void erase(kj::ArrayPtr<Row> table, size_t pos, Params&&... params) {
     impl.erase(pos, searchKey(table, params...));
   }
 
   template <typename Row, typename... Params>
   void move(kj::ArrayPtr<Row> table, size_t oldPos, size_t newPos, Params&&... params) {
     impl.renumber(oldPos, newPos, searchKey(table, params...));
   }
 
   template <typename Row, typename... Params>
   Maybe<size_t> find(kj::ArrayPtr<Row> table, Params&&... params) const {
     auto iter = impl.search(searchKey(table, params...));
 
     if (!iter.isEnd() && cb.matches(table[*iter], params...)) {
       return size_t(*iter);
     } else {
       return nullptr;
     }
   }
 
   template <typename Row, typename... Params>
   _::BTreeImpl::Iterator seek(kj::ArrayPtr<Row> table, Params&&... params) const {
     return impl.search(searchKey(table, params...));
   }
 
 private:
   Callbacks cb;
   _::BTreeImpl impl;
 
   template <typename Predicate>
   class SearchKeyImpl: public _::BTreeImpl::SearchKey {
   public:
     SearchKeyImpl(Predicate&& predicate)
         : predicate(kj::mv(predicate)) {}
 
     uint search(const _::BTreeImpl::Parent& parent) const override {
       return parent.binarySearch(predicate);
     }
     uint search(const _::BTreeImpl::Leaf& leaf) const override {
       return leaf.binarySearch(predicate);
     }
     bool isAfter(uint rowIndex) const override {
       return predicate(rowIndex);
     }
 
   private:
     Predicate predicate;
   };
 
   template <typename Row, typename... Params>
   inline auto searchKey(kj::ArrayPtr<Row>& table, Params&... params) const {
     auto predicate = [&](uint i) { return cb.isBefore(table[i], params...); };
     return SearchKeyImpl<decltype(predicate)>(kj::mv(predicate));
   }
 };
 
 // -----------------------------------------------------------------------------
 // Insertion order index
 
 class InsertionOrderIndex {
   // Table index which allows iterating over elements in order of insertion. This index cannot
   // be used for Table::find(), but can be used for Table::ordered().
 
   struct Link;
 public:
   InsertionOrderIndex();
   InsertionOrderIndex(const InsertionOrderIndex&) = delete;
   InsertionOrderIndex& operator=(const InsertionOrderIndex&) = delete;
   InsertionOrderIndex(InsertionOrderIndex&& other);
   InsertionOrderIndex& operator=(InsertionOrderIndex&& other);
   ~InsertionOrderIndex() noexcept(false);
 
   class Iterator {
   public:
     Iterator(const Link* links, uint pos)
         : links(links), pos(pos) {}
 
     inline size_t operator*() const {
       KJ_TABLE_IREQUIRE(pos != 0, "can't derefrence end() iterator");
       return pos - 1;
     };
 
     inline Iterator& operator++() {
       pos = links[pos].next;
       return *this;
     }
     inline Iterator operator++(int) {
       Iterator result = *this;
       ++*this;
       return result;
     }
     inline Iterator& operator--() {
       pos = links[pos].prev;
       return *this;
     }
     inline Iterator operator--(int) {
       Iterator result = *this;
       --*this;
       return result;
     }
 
     inline bool operator==(const Iterator& other) const {
       return pos == other.pos;
     }
     inline bool operator!=(const Iterator& other) const {
       return pos != other.pos;
     }
 
   private:
     const Link* links;
     uint pos;
   };
 
   template <typename Row>
   Row& keyForRow(Row& row) const { return row; }
 
   void reserve(size_t size);
   void clear();
   inline Iterator begin() const { return Iterator(links, links[0].next); }
   inline Iterator end() const { return Iterator(links, 0); }
 
   template <typename Row>
   kj::Maybe<size_t> insert(kj::ArrayPtr<Row> table, size_t pos, const Row& row) {
     return insertImpl(pos);
   }
 
   template <typename Row>
   void erase(kj::ArrayPtr<Row> table, size_t pos, const Row& row) {
     eraseImpl(pos);
   }
 
   template <typename Row>
   void move(kj::ArrayPtr<Row> table, size_t oldPos, size_t newPos, const Row& row) {
     return moveImpl(oldPos, newPos);
   }
 
 private:
   struct Link {
     uint next;
     uint prev;
   };
 
   uint capacity;
   Link* links;
   // links[0] is special: links[0].next points to the first link, links[0].prev points to the last.
   // links[n+1] corresponds to row n.
 
   kj::Maybe<size_t> insertImpl(size_t pos);
   void eraseImpl(size_t pos);
   void moveImpl(size_t oldPos, size_t newPos);
 
   static const Link EMPTY_LINK;
 };
 
 } // namespace kj
 
 KJ_END_HEADER