capnproto

table.c++ (32147B)

---

 // 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.
 
 #include "table.h"
 #include "debug.h"
 #include <stdlib.h>
 
 #if KJ_DEBUG_TABLE_IMPL
 #undef KJ_DASSERT
 #define KJ_DASSERT KJ_ASSERT
 #endif
 
 namespace kj {
 namespace _ {
 
 static inline uint lg(uint value) {
   // Compute floor(log2(value)).
   //
   // Undefined for value = 0.
 #if _MSC_VER && !defined(__clang__)
   unsigned long i;
   auto found = _BitScanReverse(&i, value);
   KJ_DASSERT(found);  // !found means value = 0
   return i;
 #else
   return sizeof(uint) * 8 - 1 - __builtin_clz(value);
 #endif
 }
 
 void throwDuplicateTableRow() {
   KJ_FAIL_REQUIRE("inserted row already exists in table");
 }
 
 void logHashTableInconsistency() {
   KJ_LOG(ERROR,
       "HashIndex detected hash table inconsistency. This can happen if you create a kj::Table "
       "with a hash index and you modify the rows in the table post-indexing in a way that would "
       "change their hash. This is a serious bug which will lead to undefined behavior."
       "\nstack: ", kj::getStackTrace());
 }
 
 // List of primes where each element is roughly double the previous.  Obtained
 // from:
 //   http://planetmath.org/goodhashtableprimes
 // Primes < 53 were added to ensure that small tables don't allocate excessive memory.
 static const size_t PRIMES[] = {
            1,  // 2^ 0 = 1
            3,  // 2^ 1 = 2
            5,  // 2^ 2 = 4
           11,  // 2^ 3 = 8
           23,  // 2^ 4 = 16
           53,  // 2^ 5 = 32
           97,  // 2^ 6 = 64
          193,  // 2^ 7 = 128
          389,  // 2^ 8 = 256
          769,  // 2^ 9 = 512
         1543,  // 2^10 = 1024
         3079,  // 2^11 = 2048
         6151,  // 2^12 = 4096
        12289,  // 2^13 = 8192
        24593,  // 2^14 = 16384
        49157,  // 2^15 = 32768
        98317,  // 2^16 = 65536
       196613,  // 2^17 = 131072
       393241,  // 2^18 = 262144
       786433,  // 2^19 = 524288
      1572869,  // 2^20 = 1048576
      3145739,  // 2^21 = 2097152
      6291469,  // 2^22 = 4194304
     12582917,  // 2^23 = 8388608
     25165843,  // 2^24 = 16777216
     50331653,  // 2^25 = 33554432
    100663319,  // 2^26 = 67108864
    201326611,  // 2^27 = 134217728
    402653189,  // 2^28 = 268435456
    805306457,  // 2^29 = 536870912
   1610612741,  // 2^30 = 1073741824
 };
 
 uint chooseBucket(uint hash, uint count) {
   // Integer modulus is really, really slow. It turns out that the compiler can generate much
   // faster code if the denominator is a constant. Since we have a fixed set of possible
   // denominators, a big old switch() statement is a win.
 
   // TODO(perf): Consider using power-of-two bucket sizes. We can safely do so as long as we demand
   //   high-quality hash functions -- kj::hashCode() needs good diffusion even for integers, can't
   //   just be a cast. Also be sure to implement Robin Hood hashing to avoid extremely bad negative
   //   lookup time when elements have sequential hashes (otherwise, it could be necessary to scan
   //   the entire list to determine that an element isn't present).
 
   switch (count) {
 #define HANDLE(i) case i##u: return hash % i##u
     HANDLE(         1);
     HANDLE(         3);
     HANDLE(         5);
     HANDLE(        11);
     HANDLE(        23);
     HANDLE(        53);
     HANDLE(        97);
     HANDLE(       193);
     HANDLE(       389);
     HANDLE(       769);
     HANDLE(      1543);
     HANDLE(      3079);
     HANDLE(      6151);
     HANDLE(     12289);
     HANDLE(     24593);
     HANDLE(     49157);
     HANDLE(     98317);
     HANDLE(    196613);
     HANDLE(    393241);
     HANDLE(    786433);
     HANDLE(   1572869);
     HANDLE(   3145739);
     HANDLE(   6291469);
     HANDLE(  12582917);
     HANDLE(  25165843);
     HANDLE(  50331653);
     HANDLE( 100663319);
     HANDLE( 201326611);
     HANDLE( 402653189);
     HANDLE( 805306457);
     HANDLE(1610612741);
 #undef HANDLE
     default: return hash % count;
   }
 }
 
 size_t chooseHashTableSize(uint size) {
   if (size == 0) return 0;
 
   // Add 1 to compensate for the floor() above, then look up the best prime bucket size for that
   // target size.
   return PRIMES[lg(size) + 1];
 }
 
 kj::Array<HashBucket> rehash(kj::ArrayPtr<const HashBucket> oldBuckets, size_t targetSize) {
   // Rehash the whole table.
 
   KJ_REQUIRE(targetSize < (1 << 30), "hash table has reached maximum size");
 
   size_t size = chooseHashTableSize(targetSize);
 
   if (size < oldBuckets.size()) {
     size = oldBuckets.size();
   }
 
   auto newBuckets = kj::heapArray<HashBucket>(size);
   memset(newBuckets.begin(), 0, sizeof(HashBucket) * size);
 
   uint entryCount = 0;
   uint collisionCount = 0;
 
   for (auto& oldBucket: oldBuckets) {
     if (oldBucket.isOccupied()) {
       ++entryCount;
       for (uint i = oldBucket.hash % newBuckets.size();; i = probeHash(newBuckets, i)) {
         auto& newBucket = newBuckets[i];
         if (newBucket.isEmpty()) {
           newBucket = oldBucket;
           break;
         }
         ++collisionCount;
       }
     }
   }
 
   if (collisionCount > 16 + entryCount * 4) {
     static bool warned = false;
     if (!warned) {
       KJ_LOG(WARNING, "detected excessive collisions in hash table; is your hash function OK?",
           entryCount, collisionCount, kj::getStackTrace());
       warned = true;
     }
   }
 
   return newBuckets;
 }
 
 // =======================================================================================
 // BTree
 
 #if _WIN32
 #define aligned_free _aligned_free
 #else
 #define aligned_free ::free
 #endif
 
 BTreeImpl::BTreeImpl()
     : tree(const_cast<NodeUnion*>(&EMPTY_NODE)),
       treeCapacity(1),
       height(0),
       freelistHead(1),
       freelistSize(0),
       beginLeaf(0),
       endLeaf(0) {}
 
 BTreeImpl::~BTreeImpl() noexcept(false) {
   if (tree != &EMPTY_NODE) {
     aligned_free(tree);
   }
 }
 
 BTreeImpl::BTreeImpl(BTreeImpl&& other)
   : BTreeImpl() {
   *this = kj::mv(other);
 }
 
 BTreeImpl& BTreeImpl::operator=(BTreeImpl&& other) {
   KJ_DASSERT(&other != this);
 
   if (tree != &EMPTY_NODE) {
     aligned_free(tree);
   }
   tree = other.tree;
   treeCapacity = other.treeCapacity;
   height = other.height;
   freelistHead = other.freelistHead;
   freelistSize = other.freelistSize;
   beginLeaf = other.beginLeaf;
   endLeaf = other.endLeaf;
 
   other.tree = const_cast<NodeUnion*>(&EMPTY_NODE);
   other.treeCapacity = 1;
   other.height = 0;
   other.freelistHead = 1;
   other.freelistSize = 0;
   other.beginLeaf = 0;
   other.endLeaf = 0;
 
   return *this;
 }
 
 const BTreeImpl::NodeUnion BTreeImpl::EMPTY_NODE = {{{0, {0}}}};
 
 void BTreeImpl::verify(size_t size, FunctionParam<bool(uint, uint)> f) {
   KJ_ASSERT(verifyNode(size, f, 0, height, nullptr) == size);
 }
 size_t BTreeImpl::verifyNode(size_t size, FunctionParam<bool(uint, uint)>& f,
                              uint pos, uint height, MaybeUint maxRow) {
   if (height > 0) {
     auto& parent = tree[pos].parent;
 
     auto n = parent.keyCount();
     size_t total = 0;
     for (auto i: kj::zeroTo(n)) {
       KJ_ASSERT(*parent.keys[i] < size, n, i);
       total += verifyNode(size, f, parent.children[i], height - 1, parent.keys[i]);
       if (i + 1 < n) {
         KJ_ASSERT(f(*parent.keys[i], *parent.keys[i + 1]),
             n, i, parent.keys[i], parent.keys[i + 1]);
       }
     }
     total += verifyNode(size, f, parent.children[n], height - 1, maxRow);
     if (maxRow != nullptr) {
       KJ_ASSERT(f(*parent.keys[n-1], *maxRow), n, parent.keys[n-1], maxRow);
     }
     return total;
   } else {
     auto& leaf = tree[pos].leaf;
     auto n = leaf.size();
     for (auto i: kj::zeroTo(n)) {
       KJ_ASSERT(*leaf.rows[i] < size, n, i);
       if (i + 1 < n) {
         KJ_ASSERT(f(*leaf.rows[i], *leaf.rows[i + 1]),
             n, i, leaf.rows[i], leaf.rows[i + 1]);
       } else if (maxRow != nullptr) {
         KJ_ASSERT(leaf.rows[n-1] == maxRow);
       }
     }
     return n;
   }
 }
 
 kj::String BTreeImpl::MaybeUint::toString() const {
   return i == 0 ? kj::str("(null)") : kj::str(i - 1);
 }
 
 void BTreeImpl::logInconsistency() const {
   KJ_LOG(ERROR,
       "BTreeIndex detected tree state inconsistency. This can happen if you create a kj::Table "
       "with a b-tree index and you modify the rows in the table post-indexing in a way that would "
       "change their ordering. This is a serious bug which will lead to undefined behavior."
       "\nstack: ", kj::getStackTrace());
 }
 
 void BTreeImpl::reserve(size_t size) {
   KJ_REQUIRE(size < (1u << 31), "b-tree has reached maximum size");
 
   // Calculate the worst-case number of leaves to cover the size, given that a leaf is always at
   // least half-full. (Note that it's correct for this calculation to round down, not up: The
   // remainder will necessarily be distributed among the non-full leaves, rather than creating a
   // new leaf, because if it went into a new leaf, that leaf would be less than half-full.)
   uint leaves = size / (Leaf::NROWS / 2);
 
   // Calculate the worst-case number of parents to cover the leaves, given that a parent is always
   // at least half-full. Since the parents form a tree with branching factor B, the size of the
   // tree is N/B + N/B^2 + N/B^3 + N/B^4 + ... = N / (B - 1). Math.
   constexpr uint branchingFactor = Parent::NCHILDREN / 2;
   uint parents = leaves / (branchingFactor - 1);
 
   // Height is log-base-branching-factor of leaves, plus 1 for the root node.
   uint height = lg(leaves | 1) / lg(branchingFactor) + 1;
 
   size_t newSize = leaves +
       parents + 1 +  // + 1 for the root
       height + 2;    // minimum freelist size needed by insert()
 
   if (treeCapacity < newSize) {
     growTree(newSize);
   }
 }
 
 void BTreeImpl::clear() {
   if (tree != &EMPTY_NODE) {
     azero(tree, treeCapacity);
     height = 0;
     freelistHead = 1;
     freelistSize = treeCapacity;
     beginLeaf = 0;
     endLeaf = 0;
   }
 }
 
 void BTreeImpl::growTree(uint minCapacity) {
   uint newCapacity = kj::max(kj::max(minCapacity, treeCapacity * 2), 4);
   freelistSize += newCapacity - treeCapacity;
 
   // Allocate some aligned memory! In theory this should be as simple as calling the C11 standard
   // aligned_alloc() function. Unfortunately, many platforms don't implement it. Luckily, there
   // are usually alternatives.
 
 #if _WIN32
   // Windows lacks aligned_alloc() but has its own _aligned_malloc() (which requires freeing using
   // _aligned_free()).
   // WATCH OUT: The argument order for _aligned_malloc() is opposite of aligned_alloc()!
   NodeUnion* newTree = reinterpret_cast<NodeUnion*>(
       _aligned_malloc(newCapacity * sizeof(BTreeImpl::NodeUnion), sizeof(BTreeImpl::NodeUnion)));
   KJ_ASSERT(newTree != nullptr, "memory allocation failed", newCapacity);
 #else
   // macOS, OpenBSD, and Android lack aligned_alloc(), but have posix_memalign(). Fine.
   void* allocPtr;
   int error = posix_memalign(&allocPtr,
       sizeof(BTreeImpl::NodeUnion), newCapacity * sizeof(BTreeImpl::NodeUnion));
   if (error != 0) {
     KJ_FAIL_SYSCALL("posix_memalign", error);
   }
   NodeUnion* newTree = reinterpret_cast<NodeUnion*>(allocPtr);
 #endif
 
   // Note: C11 introduces aligned_alloc() as a standard, but it's still missing on many platforms,
   //   so we don't use it. But if you wanted to use it, you'd do this:
 //  NodeUnion* newTree = reinterpret_cast<NodeUnion*>(
 //      aligned_alloc(sizeof(BTreeImpl::NodeUnion), newCapacity * sizeof(BTreeImpl::NodeUnion)));
 //  KJ_ASSERT(newTree != nullptr, "memory allocation failed", newCapacity);
 
   acopy(newTree, tree, treeCapacity);
   azero(newTree + treeCapacity, newCapacity - treeCapacity);
   if (tree != &EMPTY_NODE) aligned_free(tree);
   tree = newTree;
   treeCapacity = newCapacity;
 }
 
 BTreeImpl::Iterator BTreeImpl::search(const SearchKey& searchKey) const {
   // Find the "first" row number (in sorted order) for which searchKey.isAfter(rowNumber) returns
   // false.
 
   uint pos = 0;
 
   for (auto i KJ_UNUSED: zeroTo(height)) {
     auto& parent = tree[pos].parent;
     pos = parent.children[searchKey.search(parent)];
   }
 
   auto& leaf = tree[pos].leaf;
   return { tree, &leaf, searchKey.search(leaf) };
 }
 
 template <typename T>
 struct BTreeImpl::AllocResult {
   uint index;
   T& node;
 };
 
 template <typename T>
 inline BTreeImpl::AllocResult<T> BTreeImpl::alloc() {
   // Allocate a new item from the freelist. Guaranteed to be zero'd except for the first member.
   uint i = freelistHead;
   NodeUnion* ptr = &tree[i];
   freelistHead = i + 1 + ptr->freelist.nextOffset;
   --freelistSize;
   return { i, *ptr };
 }
 
 inline void BTreeImpl::free(uint pos) {
   // Add the given node to the freelist.
 
   // HACK: This is typically called on a node immediately after copying its contents away, but the
   //   pointer used to copy it away may be a different pointer pointing to a different union member
   //   which the compiler may not recgonize as aliasing with this object. Just to be extra-safe,
   //   insert a compiler barrier.
   compilerBarrier();
 
   auto& node = tree[pos];
   node.freelist.nextOffset = freelistHead - pos - 1;
   azero(node.freelist.zero, kj::size(node.freelist.zero));
   freelistHead = pos;
   ++freelistSize;
 }
 
 BTreeImpl::Iterator BTreeImpl::insert(const SearchKey& searchKey) {
   // Like search() but ensures that there is room in the leaf node to insert a new row.
 
   // If we split the root node it will generate two new nodes. If we split any other node in the
   // path it will generate one new node. `height` doesn't count leaf nodes, but we can equivalently
   // think of it as not counting the root node, so in the worst case we may allocate height + 2
   // new nodes.
   //
   // (Also note that if the tree is currently empty, then `tree` points to a dummy root node in
   // read-only memory. We definitely need to allocate a real tree node array in this case, and
   // we'll start out allocating space for four nodes, which will be all we need up to 28 rows.)
   if (freelistSize < height + 2) {
     if (height > 0 && !tree[0].parent.isFull() && freelistSize >= height) {
       // Slight optimization: The root node is not full, so we're definitely not going to split it.
       // That means that the maximum allocations we might do is equal to `height`, not
       // `height + 2`, and we have that much space, so no need to grow yet.
       //
       // This optimization is particularly important for small trees, e.g. when treeCapacity is 4
       // and the tree so far consists of a root and two children, we definitely don't need to grow
       // the tree yet.
     } else {
       growTree();
 
       if (freelistHead == 0) {
         // We have no root yet. Allocate one.
         KJ_ASSERT(alloc<Parent>().index == 0);
       }
     }
   }
 
   uint pos = 0;
 
   // Track grandparent node and child index within grandparent.
   Parent* parent = nullptr;
   uint indexInParent = 0;
 
   for (auto i KJ_UNUSED: zeroTo(height)) {
     Parent& node = insertHelper(searchKey, tree[pos].parent, parent, indexInParent, pos);
 
     parent = &node;
     indexInParent = searchKey.search(node);
     pos = node.children[indexInParent];
   }
 
   Leaf& leaf = insertHelper(searchKey, tree[pos].leaf, parent, indexInParent, pos);
 
   // Fun fact: Unlike erase(), there's no need to climb back up the tree modifying keys, because
   // either the newly-inserted node will not be the last in the leaf (and thus parent keys aren't
   // modified), or the leaf is the last leaf in the tree (and thus there's no parent key to
   // modify).
 
   return { tree, &leaf, searchKey.search(leaf) };
 }
 
 template <typename Node>
 Node& BTreeImpl::insertHelper(const SearchKey& searchKey,
     Node& node, Parent* parent, uint indexInParent, uint pos) {
   if (node.isFull()) {
     // This node is full. Need to split.
     if (parent == nullptr) {
       // This is the root node. We need to split into two nodes and create a new root.
       auto n1 = alloc<Node>();
       auto n2 = alloc<Node>();
 
       uint pivot = split(n2.node, n2.index, node, pos);
       move(n1.node, n1.index, node);
 
       // Rewrite root to have the two children.
       tree[0].parent.initRoot(pivot, n1.index, n2.index);
 
       // Increased height.
       ++height;
 
       // Decide which new branch has our search key.
       if (searchKey.isAfter(pivot)) {
         // the right one
         return n2.node;
       } else {
         // the left one
         return n1.node;
       }
     } else {
       // This is a non-root parent node. We need to split it into two and insert the new node
       // into the grandparent.
       auto n = alloc<Node>();
       uint pivot = split(n.node, n.index, node, pos);
 
       // Insert new child into grandparent.
       parent->insertAfter(indexInParent, pivot, n.index);
 
       // Decide which new branch has our search key.
       if (searchKey.isAfter(pivot)) {
         // the new one, which is right of the original
         return n.node;
       } else {
         // the original one, which is left of the new one
         return node;
       }
     }
   } else {
     // No split needed.
     return node;
   }
 }
 
 void BTreeImpl::erase(uint row, const SearchKey& searchKey) {
   // Erase the given row number from the tree. predicate() returns true for the given row and all
   // rows after it.
 
   uint pos = 0;
 
   // Track grandparent node and child index within grandparent.
   Parent* parent = nullptr;
   uint indexInParent = 0;
 
   MaybeUint* fixup = nullptr;
 
   for (auto i KJ_UNUSED: zeroTo(height)) {
     Parent& node = eraseHelper(tree[pos].parent, parent, indexInParent, pos, fixup);
 
     parent = &node;
     indexInParent = searchKey.search(node);
     pos = node.children[indexInParent];
 
     if (indexInParent < kj::size(node.keys) && node.keys[indexInParent] == row) {
       // Oh look, the row is a key in this node! We'll need to come back and fix this up later.
       // Note that any particular row can only appear as *one* key value anywhere in the tree, so
       // we only need one fixup pointer, which is nice.
       MaybeUint* newFixup = &node.keys[indexInParent];
       if (fixup == newFixup) {
         // The fixup pointer was already set while processing a parent node, and then a merge or
         // rotate caused it to be moved, but the fixup pointer was updated... so it's already set
         // to point at the slot we wanted it to point to, so nothing to see here.
       } else {
         KJ_DASSERT(fixup == nullptr);
         fixup = newFixup;
       }
     }
   }
 
   Leaf& leaf = eraseHelper(tree[pos].leaf, parent, indexInParent, pos, fixup);
 
   uint r = searchKey.search(leaf);
   if (leaf.rows[r] == row) {
     leaf.erase(r);
 
     if (fixup != nullptr) {
       // There's a key in a parent node that needs fixup. This is only possible if the removed
       // node is the last in its leaf.
       KJ_DASSERT(leaf.rows[r] == nullptr);
       KJ_DASSERT(r > 0);  // non-root nodes must be at least half full so this can't be item 0
       KJ_DASSERT(*fixup == row);
       *fixup = leaf.rows[r - 1];
     }
   } else {
     logInconsistency();
   }
 }
 
 template <typename Node>
 Node& BTreeImpl::eraseHelper(
     Node& node, Parent* parent, uint indexInParent, uint pos, MaybeUint*& fixup) {
   if (parent != nullptr && !node.isMostlyFull()) {
     // This is not the root, but it's only half-full. Rebalance.
     KJ_DASSERT(node.isHalfFull());
 
     if (indexInParent > 0) {
       // There's a sibling to the left.
       uint sibPos = parent->children[indexInParent - 1];
       Node& sib = tree[sibPos];
       if (sib.isMostlyFull()) {
         // Left sibling is more than half full. Steal one member.
         rotateRight(sib, node, *parent, indexInParent - 1);
         return node;
       } else {
         // Left sibling is half full, too. Merge.
         KJ_ASSERT(sib.isHalfFull());
         merge(sib, sibPos, *parent->keys[indexInParent - 1], node);
         parent->eraseAfter(indexInParent - 1);
         free(pos);
         if (fixup == &parent->keys[indexInParent]) --fixup;
 
         if (parent->keys[0] == nullptr) {
           // Oh hah, the parent has no keys left. It must be the root. We can eliminate it.
           KJ_DASSERT(parent == &tree->parent);
           compilerBarrier();  // don't reorder any writes to parent below here
           move(tree[0], 0, sib);
           free(sibPos);
           --height;
           return tree[0];
         } else {
           return sib;
         }
       }
     } else if (indexInParent < Parent::NKEYS && parent->keys[indexInParent] != nullptr) {
       // There's a sibling to the right.
       uint sibPos = parent->children[indexInParent + 1];
       Node& sib = tree[sibPos];
       if (sib.isMostlyFull()) {
         // Right sibling is more than half full. Steal one member.
         rotateLeft(node, sib, *parent, indexInParent, fixup);
         return node;
       } else {
         // Right sibling is half full, too. Merge.
         KJ_ASSERT(sib.isHalfFull());
         merge(node, pos, *parent->keys[indexInParent], sib);
         parent->eraseAfter(indexInParent);
         free(sibPos);
         if (fixup == &parent->keys[indexInParent]) fixup = nullptr;
 
         if (parent->keys[0] == nullptr) {
           // Oh hah, the parent has no keys left. It must be the root. We can eliminate it.
           KJ_DASSERT(parent == &tree->parent);
           compilerBarrier();  // don't reorder any writes to parent below here
           move(tree[0], 0, node);
           free(pos);
           --height;
           return tree[0];
         } else {
           return node;
         }
       }
     } else {
       KJ_FAIL_ASSERT("inconsistent b-tree");
     }
   }
 
   return node;
 }
 
 void BTreeImpl::renumber(uint oldRow, uint newRow, const SearchKey& searchKey) {
   // Renumber the given row from oldRow to newRow. predicate() returns true for oldRow and all
   // rows after it. (It will not be called on newRow.)
 
   uint pos = 0;
 
   for (auto i KJ_UNUSED: zeroTo(height)) {
     auto& node = tree[pos].parent;
     uint indexInParent = searchKey.search(node);
     pos = node.children[indexInParent];
     if (indexInParent < kj::size(node.keys) && node.keys[indexInParent] == oldRow) {
       node.keys[indexInParent] = newRow;
     }
     KJ_DASSERT(pos != 0);
   }
 
   auto& leaf = tree[pos].leaf;
   uint r = searchKey.search(leaf);
   if (leaf.rows[r] == oldRow) {
     leaf.rows[r] = newRow;
   } else {
     logInconsistency();
   }
 }
 
 uint BTreeImpl::split(Parent& dst, uint dstPos, Parent& src, uint srcPos) {
   constexpr size_t mid = Parent::NKEYS / 2;
   uint pivot = *src.keys[mid];
   acopy(dst.keys, src.keys + mid + 1, Parent::NKEYS - mid - 1);
   azero(src.keys + mid, Parent::NKEYS - mid);
   acopy(dst.children, src.children + mid + 1, Parent::NCHILDREN - mid - 1);
   azero(src.children + mid + 1, Parent::NCHILDREN - mid - 1);
   return pivot;
 }
 
 uint BTreeImpl::split(Leaf& dst, uint dstPos, Leaf& src, uint srcPos) {
   constexpr size_t mid = Leaf::NROWS / 2;
   uint pivot = *src.rows[mid - 1];
   acopy(dst.rows, src.rows + mid, Leaf::NROWS - mid);
   azero(src.rows + mid, Leaf::NROWS - mid);
 
   if (src.next == 0) {
     endLeaf = dstPos;
   } else {
     tree[src.next].leaf.prev = dstPos;
   }
   dst.next = src.next;
   dst.prev = srcPos;
   src.next = dstPos;
 
   return pivot;
 }
 
 void BTreeImpl::merge(Parent& dst, uint dstPos, uint pivot, Parent& src) {
   // merge() is only legal if both nodes are half-empty. Meanwhile, B-tree invariants
   // guarantee that the node can't be more than half-empty, or we would have merged it sooner.
   // (The root can be more than half-empty, but it is never merged with anything.)
   KJ_DASSERT(src.isHalfFull());
   KJ_DASSERT(dst.isHalfFull());
 
   constexpr size_t mid = Parent::NKEYS/2;
   dst.keys[mid] = pivot;
   acopy(dst.keys + mid + 1, src.keys, mid);
   acopy(dst.children + mid + 1, src.children, mid + 1);
 }
 
 void BTreeImpl::merge(Leaf& dst, uint dstPos, uint pivot, Leaf& src) {
   // merge() is only legal if both nodes are half-empty. Meanwhile, B-tree invariants
   // guarantee that the node can't be more than half-empty, or we would have merged it sooner.
   // (The root can be more than half-empty, but it is never merged with anything.)
   KJ_DASSERT(src.isHalfFull());
   KJ_DASSERT(dst.isHalfFull());
 
   constexpr size_t mid = Leaf::NROWS/2;
   dst.rows[mid] = pivot;
   acopy(dst.rows + mid, src.rows, mid);
 
   dst.next = src.next;
   if (dst.next == 0) {
     endLeaf = dstPos;
   } else {
     tree[dst.next].leaf.prev = dstPos;
   }
 }
 
 void BTreeImpl::move(Parent& dst, uint dstPos, Parent& src) {
   dst = src;
 }
 
 void BTreeImpl::move(Leaf& dst, uint dstPos, Leaf& src) {
   dst = src;
   if (src.next == 0) {
     endLeaf = dstPos;
   } else {
     tree[src.next].leaf.prev = dstPos;
   }
   if (src.prev == 0) {
     beginLeaf = dstPos;
   } else {
     tree[src.prev].leaf.next = dstPos;
   }
 }
 
 void BTreeImpl::rotateLeft(
     Parent& left, Parent& right, Parent& parent, uint indexInParent, MaybeUint*& fixup) {
   // Steal one item from the right node and move it to the left node.
 
   // Like merge(), this is only called on an exactly-half-empty node.
   KJ_DASSERT(left.isHalfFull());
   KJ_DASSERT(right.isMostlyFull());
 
   constexpr size_t mid = Parent::NKEYS/2;
   left.keys[mid] = parent.keys[indexInParent];
   if (fixup == &parent.keys[indexInParent]) fixup = &left.keys[mid];
   parent.keys[indexInParent] = right.keys[0];
   left.children[mid + 1] = right.children[0];
   amove(right.keys, right.keys + 1, Parent::NKEYS - 1);
   right.keys[Parent::NKEYS - 1] = nullptr;
   amove(right.children, right.children + 1, Parent::NCHILDREN - 1);
   right.children[Parent::NCHILDREN - 1] = 0;
 }
 
 void BTreeImpl::rotateLeft(
     Leaf& left, Leaf& right, Parent& parent, uint indexInParent, MaybeUint*& fixup) {
   // Steal one item from the right node and move it to the left node.
 
   // Like merge(), this is only called on an exactly-half-empty node.
   KJ_DASSERT(left.isHalfFull());
   KJ_DASSERT(right.isMostlyFull());
 
   constexpr size_t mid = Leaf::NROWS/2;
   parent.keys[indexInParent] = left.rows[mid] = right.rows[0];
   if (fixup == &parent.keys[indexInParent]) fixup = nullptr;
   amove(right.rows, right.rows + 1, Leaf::NROWS - 1);
   right.rows[Leaf::NROWS - 1] = nullptr;
 }
 
 void BTreeImpl::rotateRight(Parent& left, Parent& right, Parent& parent, uint indexInParent) {
   // Steal one item from the left node and move it to the right node.
 
   // Like merge(), this is only called on an exactly-half-empty node.
   KJ_DASSERT(right.isHalfFull());
   KJ_DASSERT(left.isMostlyFull());
 
   constexpr size_t mid = Parent::NKEYS/2;
   amove(right.keys + 1, right.keys, mid);
   amove(right.children + 1, right.children, mid + 1);
 
   uint back = left.keyCount() - 1;
 
   right.keys[0] = parent.keys[indexInParent];
   parent.keys[indexInParent] = left.keys[back];
   right.children[0] = left.children[back + 1];
   left.keys[back] = nullptr;
   left.children[back + 1] = 0;
 }
 
 void BTreeImpl::rotateRight(Leaf& left, Leaf& right, Parent& parent, uint indexInParent) {
   // Steal one item from the left node and move it to the right node.
 
   // Like mergeFrom(), this is only called on an exactly-half-empty node.
   KJ_DASSERT(right.isHalfFull());
   KJ_DASSERT(left.isMostlyFull());
 
   constexpr size_t mid = Leaf::NROWS/2;
   amove(right.rows + 1, right.rows, mid);
 
   uint back = left.size() - 1;
 
   right.rows[0] = left.rows[back];
   parent.keys[indexInParent] = left.rows[back - 1];
   left.rows[back] = nullptr;
 }
 
 void BTreeImpl::Parent::initRoot(uint key, uint leftChild, uint rightChild) {
   // HACK: This is typically called on the root node immediately after copying its contents away,
   //   but the pointer used to copy it away may be a different pointer pointing to a different
   //   union member which the compiler may not recgonize as aliasing with this object. Just to
   //   be extra-safe, insert a compiler barrier.
   compilerBarrier();
 
   keys[0] = key;
   children[0] = leftChild;
   children[1] = rightChild;
   azero(keys + 1, Parent::NKEYS - 1);
   azero(children + 2, Parent::NCHILDREN - 2);
 }
 
 void BTreeImpl::Parent::insertAfter(uint i, uint splitKey, uint child) {
   KJ_IREQUIRE(children[Parent::NCHILDREN - 1] == 0);  // check not full
 
   amove(keys + i + 1, keys + i, Parent::NKEYS - (i + 1));
   keys[i] = splitKey;
 
   amove(children + i + 2, children + i + 1, Parent::NCHILDREN - (i + 2));
   children[i + 1] = child;
 }
 
 void BTreeImpl::Parent::eraseAfter(uint i) {
   amove(keys + i, keys + i + 1, Parent::NKEYS - (i + 1));
   keys[Parent::NKEYS - 1] = nullptr;
   amove(children + i + 1, children + i + 2, Parent::NCHILDREN - (i + 2));
   children[Parent::NCHILDREN - 1] = 0;
 }
 
 }  // namespace _
 
 // =======================================================================================
 // Insertion order
 
 const InsertionOrderIndex::Link InsertionOrderIndex::EMPTY_LINK = { 0, 0 };
 
 InsertionOrderIndex::InsertionOrderIndex(): capacity(0), links(const_cast<Link*>(&EMPTY_LINK)) {}
 InsertionOrderIndex::InsertionOrderIndex(InsertionOrderIndex&& other)
     : capacity(other.capacity), links(other.links) {
   other.capacity = 0;
   other.links = const_cast<Link*>(&EMPTY_LINK);
 }
 InsertionOrderIndex& InsertionOrderIndex::operator=(InsertionOrderIndex&& other) {
   KJ_DASSERT(&other != this);
   capacity = other.capacity;
   links = other.links;
   other.capacity = 0;
   other.links = const_cast<Link*>(&EMPTY_LINK);
   return *this;
 }
 InsertionOrderIndex::~InsertionOrderIndex() noexcept(false) {
   if (links != &EMPTY_LINK) delete[] links;
 }
 
 void InsertionOrderIndex::reserve(size_t size) {
   KJ_ASSERT(size < (1u << 31), "Table too big for InsertionOrderIndex");
 
   if (size > capacity) {
     // Need to grow.
     // Note that `size` and `capacity` do not include the special link[0].
 
     // Round up to the next power of 2.
     size_t allocation = 1u << (_::lg(size) + 1);
     KJ_DASSERT(allocation > size);
     KJ_DASSERT(allocation <= size * 2);
 
     // Round first allocation up to 8.
     allocation = kj::max(allocation, 8);
 
     Link* newLinks = new Link[allocation];
 #ifdef KJ_DEBUG
     // To catch bugs, fill unused links with 0xff.
     memset(newLinks, 0xff, allocation * sizeof(Link));
 #endif
     _::acopy(newLinks, links, capacity + 1);
     if (links != &EMPTY_LINK) delete[] links;
     links = newLinks;
     capacity = allocation - 1;
   }
 }
 
 void InsertionOrderIndex::clear() {
   links[0] = Link { 0, 0 };
 
 #ifdef KJ_DEBUG
   // To catch bugs, fill unused links with 0xff.
   memset(links + 1, 0xff, capacity * sizeof(Link));
 #endif
 }
 
 kj::Maybe<size_t> InsertionOrderIndex::insertImpl(size_t pos) {
   if (pos >= capacity) {
     reserve(pos + 1);
   }
 
   links[pos + 1].prev = links[0].prev;
   links[pos + 1].next = 0;
   links[links[0].prev].next = pos + 1;
   links[0].prev = pos + 1;
 
   return nullptr;
 }
 
 void InsertionOrderIndex::eraseImpl(size_t pos) {
   Link& link = links[pos + 1];
   links[link.next].prev = link.prev;
   links[link.prev].next = link.next;
 
 #ifdef KJ_DEBUG
   memset(&link, 0xff, sizeof(Link));
 #endif
 }
 
 void InsertionOrderIndex::moveImpl(size_t oldPos, size_t newPos) {
   Link& link = links[oldPos + 1];
   Link& newLink = links[newPos + 1];
 
   newLink = link;
 
   KJ_DASSERT(links[link.next].prev == oldPos + 1);
   KJ_DASSERT(links[link.prev].next == oldPos + 1);
   links[link.next].prev = newPos + 1;
   links[link.prev].next = newPos + 1;
 
 #ifdef KJ_DEBUG
   memset(&link, 0xff, sizeof(Link));
 #endif
 }
 
 }  // namespace kj