Debian Codegraph @

src/kj/table.c++

raw
1 // Copyright (c) 2018 Kenton Varda and contributors
2 // Licensed under the MIT License:
3 //
4 // Permission is hereby granted, free of charge, to any person obtaining a copy
5 // of this software and associated documentation files (the "Software"), to deal
6 // in the Software without restriction, including without limitation the rights
7 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8 // copies of the Software, and to permit persons to whom the Software is
9 // furnished to do so, subject to the following conditions:
10 //
11 // The above copyright notice and this permission notice shall be included in
12 // all copies or substantial portions of the Software.
13 //
14 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
20 // THE SOFTWARE.
21
22 #include "table.h"
23 #include "debug.h"
24 #include <stdlib.h>
25
26 #if KJ_DEBUG_TABLE_IMPL
27 #undef KJ_DASSERT
28 #define KJ_DASSERT KJ_ASSERT
29 #endif
30
31 namespace kj {
32 namespace _ {
33
34 static inline uint lg(uint value) {
35 // Compute floor(log2(value)).
36 //
37 // Undefined for value = 0.
38 #if _MSC_VER && !defined(__clang__)
39 unsigned long i;
40 auto found = _BitScanReverse(&i, value);
41 KJ_DASSERT(found); // !found means value = 0
42 return i;
43 #else
44 return sizeof(uint) * 8 - 1 - __builtin_clz(value);
45 #endif
46 }
47
48 void throwDuplicateTableRow() {
49 KJ_FAIL_REQUIRE("inserted row already exists in table");
50 }
51
52 void logHashTableInconsistency() {
53 KJ_LOG(ERROR,
54 "HashIndex detected hash table inconsistency. This can happen if you create a kj::Table "
55 "with a hash index and you modify the rows in the table post-indexing in a way that would "
56 "change their hash. This is a serious bug which will lead to undefined behavior."
57 "\nstack: ", kj::getStackTrace());
58 }
59
60 // List of primes where each element is roughly double the previous. Obtained
61 // from:
62 // http://planetmath.org/goodhashtableprimes
63 // Primes < 53 were added to ensure that small tables don't allocate excessive memory.
64 static const size_t PRIMES[] = {
65 1, // 2^ 0 = 1
66 3, // 2^ 1 = 2
67 5, // 2^ 2 = 4
68 11, // 2^ 3 = 8
69 23, // 2^ 4 = 16
70 53, // 2^ 5 = 32
71 97, // 2^ 6 = 64
72 193, // 2^ 7 = 128
73 389, // 2^ 8 = 256
74 769, // 2^ 9 = 512
75 1543, // 2^10 = 1024
76 3079, // 2^11 = 2048
77 6151, // 2^12 = 4096
78 12289, // 2^13 = 8192
79 24593, // 2^14 = 16384
80 49157, // 2^15 = 32768
81 98317, // 2^16 = 65536
82 196613, // 2^17 = 131072
83 393241, // 2^18 = 262144
84 786433, // 2^19 = 524288
85 1572869, // 2^20 = 1048576
86 3145739, // 2^21 = 2097152
87 6291469, // 2^22 = 4194304
88 12582917, // 2^23 = 8388608
89 25165843, // 2^24 = 16777216
90 50331653, // 2^25 = 33554432
91 100663319, // 2^26 = 67108864
92 201326611, // 2^27 = 134217728
93 402653189, // 2^28 = 268435456
94 805306457, // 2^29 = 536870912
95 1610612741, // 2^30 = 1073741824
96 };
97
98 uint chooseBucket(uint hash, uint count) {
99 // Integer modulus is really, really slow. It turns out that the compiler can generate much
100 // faster code if the denominator is a constant. Since we have a fixed set of possible
101 // denominators, a big old switch() statement is a win.
102
103 // TODO(perf): Consider using power-of-two bucket sizes. We can safely do so as long as we demand
104 // high-quality hash functions -- kj::hashCode() needs good diffusion even for integers, can't
105 // just be a cast. Also be sure to implement Robin Hood hashing to avoid extremely bad negative
106 // lookup time when elements have sequential hashes (otherwise, it could be necessary to scan
107 // the entire list to determine that an element isn't present).
108
109 switch (count) {
110 #define HANDLE(i) case i##u: return hash % i##u
111 HANDLE( 1);
112 HANDLE( 3);
113 HANDLE( 5);
114 HANDLE( 11);
115 HANDLE( 23);
116 HANDLE( 53);
117 HANDLE( 97);
118 HANDLE( 193);
119 HANDLE( 389);
120 HANDLE( 769);
121 HANDLE( 1543);
122 HANDLE( 3079);
123 HANDLE( 6151);
124 HANDLE( 12289);
125 HANDLE( 24593);
126 HANDLE( 49157);
127 HANDLE( 98317);
128 HANDLE( 196613);
129 HANDLE( 393241);
130 HANDLE( 786433);
131 HANDLE( 1572869);
132 HANDLE( 3145739);
133 HANDLE( 6291469);
134 HANDLE( 12582917);
135 HANDLE( 25165843);
136 HANDLE( 50331653);
137 HANDLE( 100663319);
138 HANDLE( 201326611);
139 HANDLE( 402653189);
140 HANDLE( 805306457);
141 HANDLE(1610612741);
142 #undef HANDLE
143 default: return hash % count;
144 }
145 }
146
147 size_t chooseHashTableSize(uint size) {
148 if (size == 0) return 0;
149
150 // Add 1 to compensate for the floor() above, then look up the best prime bucket size for that
151 // target size.
152 return PRIMES[lg(size) + 1];
153 }
154
155 kj::Array<HashBucket> rehash(kj::ArrayPtr<const HashBucket> oldBuckets, size_t targetSize) {
156 // Rehash the whole table.
157
158 KJ_REQUIRE(targetSize < (1 << 30), "hash table has reached maximum size");
159
160 size_t size = chooseHashTableSize(targetSize);
161
162 if (size < oldBuckets.size()) {
163 size = oldBuckets.size();
164 }
165
166 auto newBuckets = kj::heapArray<HashBucket>(size);
167 memset(newBuckets.begin(), 0, sizeof(HashBucket) * size);
168
169 uint entryCount = 0;
170 uint collisionCount = 0;
171
172 for (auto& oldBucket: oldBuckets) {
173 if (oldBucket.isOccupied()) {
174 ++entryCount;
175 for (uint i = oldBucket.hash % newBuckets.size();; i = probeHash(newBuckets, i)) {
176 auto& newBucket = newBuckets[i];
177 if (newBucket.isEmpty()) {
178 newBucket = oldBucket;
179 break;
180 }
181 ++collisionCount;
182 }
183 }
184 }
185
186 if (collisionCount > 16 + entryCount * 4) {
187 static bool warned = false;
188 if (!warned) {
189 KJ_LOG(WARNING, "detected excessive collisions in hash table; is your hash function OK?",
190 entryCount, collisionCount, kj::getStackTrace());
191 warned = true;
192 }
193 }
194
195 return newBuckets;
196 }
197
198 // =======================================================================================
199 // BTree
200
201 #if _WIN32
202 #define aligned_free _aligned_free
203 #else
204 #define aligned_free ::free
205 #endif
206
207 BTreeImpl::BTreeImpl()
208 : tree(const_cast<NodeUnion*>(&EMPTY_NODE)),
209 treeCapacity(1),
210 height(0),
211 freelistHead(1),
212 freelistSize(0),
213 beginLeaf(0),
214 endLeaf(0) {}
215
216 BTreeImpl::~BTreeImpl() noexcept(false) {
217 if (tree != &EMPTY_NODE) {
218 aligned_free(tree);
219 }
220 }
221
222 BTreeImpl::BTreeImpl(BTreeImpl&& other)
223 : BTreeImpl() {
224 *this = kj::mv(other);
225 }
226
227 BTreeImpl& BTreeImpl::operator=(BTreeImpl&& other) {
228 KJ_DASSERT(&other != this);
229
230 if (tree != &EMPTY_NODE) {
231 aligned_free(tree);
232 }
233 tree = other.tree;
234 treeCapacity = other.treeCapacity;
235 height = other.height;
236 freelistHead = other.freelistHead;
237 freelistSize = other.freelistSize;
238 beginLeaf = other.beginLeaf;
239 endLeaf = other.endLeaf;
240
241 other.tree = const_cast<NodeUnion*>(&EMPTY_NODE);
242 other.treeCapacity = 1;
243 other.height = 0;
244 other.freelistHead = 1;
245 other.freelistSize = 0;
246 other.beginLeaf = 0;
247 other.endLeaf = 0;
248
249 return *this;
250 }
251
252 const BTreeImpl::NodeUnion BTreeImpl::EMPTY_NODE = {{{0, {0}}}};
253
254 void BTreeImpl::verify(size_t size, FunctionParam<bool(uint, uint)> f) {
255 KJ_ASSERT(verifyNode(size, f, 0, height, nullptr) == size);
256 }
257 size_t BTreeImpl::verifyNode(size_t size, FunctionParam<bool(uint, uint)>& f,
258 uint pos, uint height, MaybeUint maxRow) {
259 if (height > 0) {
260 auto& parent = tree[pos].parent;
261
262 auto n = parent.keyCount();
263 size_t total = 0;
264 for (auto i: kj::zeroTo(n)) {
265 KJ_ASSERT(*parent.keys[i] < size, n, i);
266 total += verifyNode(size, f, parent.children[i], height - 1, parent.keys[i]);
267 if (i > 0) {
268 KJ_ASSERT(f(*parent.keys[i - 1], *parent.keys[i]),
269 n, i, parent.keys[i - 1], parent.keys[i]);
270 }
271 }
272 total += verifyNode(size, f, parent.children[n], height - 1, maxRow);
273 if (maxRow != nullptr) {
274 KJ_ASSERT(f(*parent.keys[n-1], *maxRow), n, parent.keys[n-1], maxRow);
275 }
276 return total;
277 } else {
278 auto& leaf = tree[pos].leaf;
279 auto n = leaf.size();
280 for (auto i: kj::zeroTo(n)) {
281 KJ_ASSERT(*leaf.rows[i] < size, n, i);
282 if (i > 0) {
283 KJ_ASSERT(f(*leaf.rows[i - 1], *leaf.rows[i]),
284 n, i, leaf.rows[i - 1], leaf.rows[i]);
285 }
286 }
287 if (maxRow != nullptr) {
288 KJ_ASSERT(leaf.rows[n-1] == maxRow, n);
289 }
290 return n;
291 }
292 }
293
294 kj::String BTreeImpl::MaybeUint::toString() const {
295 return i == 0 ? kj::str("(null)") : kj::str(i - 1);
296 }
297
298 void BTreeImpl::logInconsistency() const {
299 KJ_LOG(ERROR,
300 "BTreeIndex detected tree state inconsistency. This can happen if you create a kj::Table "
301 "with a b-tree index and you modify the rows in the table post-indexing in a way that would "
302 "change their ordering. This is a serious bug which will lead to undefined behavior."
303 "\nstack: ", kj::getStackTrace());
304 }
305
306 void BTreeImpl::reserve(size_t size) {
307 KJ_REQUIRE(size < (1u << 31), "b-tree has reached maximum size");
308
309 // Calculate the worst-case number of leaves to cover the size, given that a leaf is always at
310 // least half-full. (Note that it's correct for this calculation to round down, not up: The
311 // remainder will necessarily be distributed among the non-full leaves, rather than creating a
312 // new leaf, because if it went into a new leaf, that leaf would be less than half-full.)
313 uint leaves = size / (Leaf::NROWS / 2);
314
315 // Calculate the worst-case number of parents to cover the leaves, given that a parent is always
316 // at least half-full. Since the parents form a tree with branching factor B, the size of the
317 // tree is N/B + N/B^2 + N/B^3 + N/B^4 + ... = N / (B - 1). Math.
318 constexpr uint branchingFactor = Parent::NCHILDREN / 2;
319 uint parents = leaves / (branchingFactor - 1);
320
321 // Height is log-base-branching-factor of leaves, plus 1 for the root node.
322 uint height = lg(leaves | 1) / lg(branchingFactor) + 1;
323
324 size_t newSize = leaves +
325 parents + 1 + // + 1 for the root
326 height + 2; // minimum freelist size needed by insert()
327
328 if (treeCapacity < newSize) {
329 growTree(newSize);
330 }
331 }
332
333 void BTreeImpl::clear() {
334 if (tree != &EMPTY_NODE) {
335 azero(tree, treeCapacity);
336 height = 0;
337 freelistHead = 1;
338 freelistSize = treeCapacity - 1; // subtract one to account for the root node
339 beginLeaf = 0;
340 endLeaf = 0;
341 }
342 }
343
344 void BTreeImpl::growTree(uint minCapacity) {
345 uint newCapacity = kj::max(kj::max(minCapacity, treeCapacity * 2), 4);
346 freelistSize += newCapacity - treeCapacity;
347
348 // Allocate some aligned memory! In theory this should be as simple as calling the C11 standard
349 // aligned_alloc() function. Unfortunately, many platforms don't implement it. Luckily, there
350 // are usually alternatives.
351
352 #if _WIN32
353 // Windows lacks aligned_alloc() but has its own _aligned_malloc() (which requires freeing using
354 // _aligned_free()).
355 // WATCH OUT: The argument order for _aligned_malloc() is opposite of aligned_alloc()!
356 NodeUnion* newTree = reinterpret_cast<NodeUnion*>(
357 _aligned_malloc(newCapacity * sizeof(BTreeImpl::NodeUnion), sizeof(BTreeImpl::NodeUnion)));
358 KJ_ASSERT(newTree != nullptr, "memory allocation failed", newCapacity);
359 #else
360 // macOS, OpenBSD, and Android lack aligned_alloc(), but have posix_memalign(). Fine.
361 void* allocPtr;
362 int error = posix_memalign(&allocPtr,
363 sizeof(BTreeImpl::NodeUnion), newCapacity * sizeof(BTreeImpl::NodeUnion));
364 if (error != 0) {
365 KJ_FAIL_SYSCALL("posix_memalign", error);
366 }
367 NodeUnion* newTree = reinterpret_cast<NodeUnion*>(allocPtr);
368 #endif
369
370 // Note: C11 introduces aligned_alloc() as a standard, but it's still missing on many platforms,
371 // so we don't use it. But if you wanted to use it, you'd do this:
372 // NodeUnion* newTree = reinterpret_cast<NodeUnion*>(
373 // aligned_alloc(sizeof(BTreeImpl::NodeUnion), newCapacity * sizeof(BTreeImpl::NodeUnion)));
374 // KJ_ASSERT(newTree != nullptr, "memory allocation failed", newCapacity);
375
376 acopy(newTree, tree, treeCapacity);
377 azero(newTree + treeCapacity, newCapacity - treeCapacity);
378 if (tree != &EMPTY_NODE) aligned_free(tree);
379 tree = newTree;
380 treeCapacity = newCapacity;
381 }
382
383 BTreeImpl::Iterator BTreeImpl::search(const SearchKey& searchKey) const {
384 // Find the "first" row number (in sorted order) for which searchKey.isAfter(rowNumber) returns
385 // false.
386
387 uint pos = 0;
388
389 for (auto i KJ_UNUSED: zeroTo(height)) {
390 auto& parent = tree[pos].parent;
391 pos = parent.children[searchKey.search(parent)];
392 }
393
394 auto& leaf = tree[pos].leaf;
395 return { tree, &leaf, searchKey.search(leaf) };
396 }
397
398 template <typename T>
399 struct BTreeImpl::AllocResult {
400 uint index;
401 T& node;
402 };
403
404 template <typename T>
405 inline BTreeImpl::AllocResult<T> BTreeImpl::alloc() {
406 // Allocate a new item from the freelist. Guaranteed to be zero'd except for the first member.
407 uint i = freelistHead;
408 NodeUnion* ptr = &tree[i];
409 freelistHead = i + 1 + ptr->freelist.nextOffset;
410 --freelistSize;
411 return { i, *ptr };
412 }
413
414 inline void BTreeImpl::free(uint pos) {
415 // Add the given node to the freelist.
416
417 // HACK: This is typically called on a node immediately after copying its contents away, but the
418 // pointer used to copy it away may be a different pointer pointing to a different union member
419 // which the compiler may not recgonize as aliasing with this object. Just to be extra-safe,
420 // insert a compiler barrier.
421 compilerBarrier();
422
423 auto& node = tree[pos];
424 node.freelist.nextOffset = freelistHead - pos - 1;
425 azero(node.freelist.zero, kj::size(node.freelist.zero));
426 freelistHead = pos;
427 ++freelistSize;
428 }
429
430 BTreeImpl::Iterator BTreeImpl::insert(const SearchKey& searchKey) {
431 // Like search() but ensures that there is room in the leaf node to insert a new row.
432
433 // If we split the root node it will generate two new nodes. If we split any other node in the
434 // path it will generate one new node. `height` doesn't count leaf nodes, but we can equivalently
435 // think of it as not counting the root node, so in the worst case we may allocate height + 2
436 // new nodes.
437 //
438 // (Also note that if the tree is currently empty, then `tree` points to a dummy root node in
439 // read-only memory. We definitely need to allocate a real tree node array in this case, and
440 // we'll start out allocating space for four nodes, which will be all we need up to 28 rows.)
441 if (freelistSize < height + 2) {
442 if (height > 0 && !tree[0].parent.isFull() && freelistSize >= height) {
443 // Slight optimization: The root node is not full, so we're definitely not going to split it.
444 // That means that the maximum allocations we might do is equal to `height`, not
445 // `height + 2`, and we have that much space, so no need to grow yet.
446 //
447 // This optimization is particularly important for small trees, e.g. when treeCapacity is 4
448 // and the tree so far consists of a root and two children, we definitely don't need to grow
449 // the tree yet.
450 } else {
451 growTree();
452
453 if (freelistHead == 0) {
454 // We have no root yet. Allocate one.
455 KJ_ASSERT(alloc<Parent>().index == 0);
456 }
457 }
458 }
459
460 uint pos = 0;
461
462 // Track grandparent node and child index within grandparent.
463 Parent* parent = nullptr;
464 uint indexInParent = 0;
465
466 for (auto i KJ_UNUSED: zeroTo(height)) {
467 Parent& node = insertHelper(searchKey, tree[pos].parent, parent, indexInParent, pos);
468
469 parent = &node;
470 indexInParent = searchKey.search(node);
471 pos = node.children[indexInParent];
472 }
473
474 Leaf& leaf = insertHelper(searchKey, tree[pos].leaf, parent, indexInParent, pos);
475
476 // Fun fact: Unlike erase(), there's no need to climb back up the tree modifying keys, because
477 // either the newly-inserted node will not be the last in the leaf (and thus parent keys aren't
478 // modified), or the leaf is the last leaf in the tree (and thus there's no parent key to
479 // modify).
480
481 return { tree, &leaf, searchKey.search(leaf) };
482 }
483
484 template <typename Node>
485 Node& BTreeImpl::insertHelper(const SearchKey& searchKey,
486 Node& node, Parent* parent, uint indexInParent, uint pos) {
487 if (node.isFull()) {
488 // This node is full. Need to split.
489 if (parent == nullptr) {
490 // This is the root node. We need to split into two nodes and create a new root.
491 auto n1 = alloc<Node>();
492 auto n2 = alloc<Node>();
493
494 uint pivot = split(n2.node, n2.index, node, pos);
495 move(n1.node, n1.index, node);
496
497 // Rewrite root to have the two children.
498 tree[0].parent.initRoot(pivot, n1.index, n2.index);
499
500 // Increased height.
501 ++height;
502
503 // Decide which new branch has our search key.
504 if (searchKey.isAfter(pivot)) {
505 // the right one
506 return n2.node;
507 } else {
508 // the left one
509 return n1.node;
510 }
511 } else {
512 // This is a non-root parent node. We need to split it into two and insert the new node
513 // into the grandparent.
514 auto n = alloc<Node>();
515 uint pivot = split(n.node, n.index, node, pos);
516
517 // Insert new child into grandparent.
518 parent->insertAfter(indexInParent, pivot, n.index);
519
520 // Decide which new branch has our search key.
521 if (searchKey.isAfter(pivot)) {
522 // the new one, which is right of the original
523 return n.node;
524 } else {
525 // the original one, which is left of the new one
526 return node;
527 }
528 }
529 } else {
530 // No split needed.
531 return node;
532 }
533 }
534
535 void BTreeImpl::erase(uint row, const SearchKey& searchKey) {
536 // Erase the given row number from the tree. predicate() returns true for the given row and all
537 // rows after it.
538
539 uint pos = 0;
540
541 // Track grandparent node and child index within grandparent.
542 Parent* parent = nullptr;
543 uint indexInParent = 0;
544
545 MaybeUint* fixup = nullptr;
546
547 for (auto i KJ_UNUSED: zeroTo(height)) {
548 Parent& node = eraseHelper(tree[pos].parent, parent, indexInParent, pos, fixup);
549
550 parent = &node;
551 indexInParent = searchKey.search(node);
552 pos = node.children[indexInParent];
553
554 if (indexInParent < kj::size(node.keys) && node.keys[indexInParent] == row) {
555 // Oh look, the row is a key in this node! We'll need to come back and fix this up later.
556 // Note that any particular row can only appear as *one* key value anywhere in the tree, so
557 // we only need one fixup pointer, which is nice.
558 MaybeUint* newFixup = &node.keys[indexInParent];
559 if (fixup == newFixup) {
560 // The fixup pointer was already set while processing a parent node, and then a merge or
561 // rotate caused it to be moved, but the fixup pointer was updated... so it's already set
562 // to point at the slot we wanted it to point to, so nothing to see here.
563 } else {
564 KJ_DASSERT(fixup == nullptr);
565 fixup = newFixup;
566 }
567 }
568 }
569
570 Leaf& leaf = eraseHelper(tree[pos].leaf, parent, indexInParent, pos, fixup);
571
572 uint r = searchKey.search(leaf);
573 if (leaf.rows[r] == row) {
574 leaf.erase(r);
575
576 if (fixup != nullptr) {
577 // There's a key in a parent node that needs fixup. This is only possible if the removed
578 // node is the last in its leaf.
579 KJ_DASSERT(leaf.rows[r] == nullptr);
580 KJ_DASSERT(r > 0); // non-root nodes must be at least half full so this can't be item 0
581 KJ_DASSERT(*fixup == row);
582 *fixup = leaf.rows[r - 1];
583 }
584 } else {
585 logInconsistency();
586 }
587 }
588
589 template <typename Node>
590 Node& BTreeImpl::eraseHelper(
591 Node& node, Parent* parent, uint indexInParent, uint pos, MaybeUint*& fixup) {
592 if (parent != nullptr && !node.isMostlyFull()) {
593 // This is not the root, but it's only half-full. Rebalance.
594 KJ_DASSERT(node.isHalfFull());
595
596 if (indexInParent > 0) {
597 // There's a sibling to the left.
598 uint sibPos = parent->children[indexInParent - 1];
599 Node& sib = tree[sibPos];
600 if (sib.isMostlyFull()) {
601 // Left sibling is more than half full. Steal one member.
602 rotateRight(sib, node, *parent, indexInParent - 1);
603 return node;
604 } else {
605 // Left sibling is half full, too. Merge.
606 KJ_ASSERT(sib.isHalfFull());
607 merge(sib, sibPos, *parent->keys[indexInParent - 1], node);
608 parent->eraseAfter(indexInParent - 1);
609 free(pos);
610 if (fixup == &parent->keys[indexInParent]) --fixup;
611
612 if (parent->keys[0] == nullptr) {
613 // Oh hah, the parent has no keys left. It must be the root. We can eliminate it.
614 KJ_DASSERT(parent == &tree->parent);
615 compilerBarrier(); // don't reorder any writes to parent below here
616 move(tree[0], 0, sib);
617 free(sibPos);
618 --height;
619 return tree[0];
620 } else {
621 return sib;
622 }
623 }
624 } else if (indexInParent < Parent::NKEYS && parent->keys[indexInParent] != nullptr) {
625 // There's a sibling to the right.
626 uint sibPos = parent->children[indexInParent + 1];
627 Node& sib = tree[sibPos];
628 if (sib.isMostlyFull()) {
629 // Right sibling is more than half full. Steal one member.
630 rotateLeft(node, sib, *parent, indexInParent, fixup);
631 return node;
632 } else {
633 // Right sibling is half full, too. Merge.
634 KJ_ASSERT(sib.isHalfFull());
635 merge(node, pos, *parent->keys[indexInParent], sib);
636 parent->eraseAfter(indexInParent);
637 free(sibPos);
638 if (fixup == &parent->keys[indexInParent]) fixup = nullptr;
639
640 if (parent->keys[0] == nullptr) {
641 // Oh hah, the parent has no keys left. It must be the root. We can eliminate it.
642 KJ_DASSERT(parent == &tree->parent);
643 compilerBarrier(); // don't reorder any writes to parent below here
644 move(tree[0], 0, node);
645 free(pos);
646 --height;
647 return tree[0];
648 } else {
649 return node;
650 }
651 }
652 } else {
653 KJ_FAIL_ASSERT("inconsistent b-tree");
654 }
655 }
656
657 return node;
658 }
659
660 void BTreeImpl::renumber(uint oldRow, uint newRow, const SearchKey& searchKey) {
661 // Renumber the given row from oldRow to newRow. predicate() returns true for oldRow and all
662 // rows after it. (It will not be called on newRow.)
663
664 uint pos = 0;
665
666 for (auto i KJ_UNUSED: zeroTo(height)) {
667 auto& node = tree[pos].parent;
668 uint indexInParent = searchKey.search(node);
669 pos = node.children[indexInParent];
670 if (indexInParent < kj::size(node.keys) && node.keys[indexInParent] == oldRow) {
671 node.keys[indexInParent] = newRow;
672 }
673 KJ_DASSERT(pos != 0);
674 }
675
676 auto& leaf = tree[pos].leaf;
677 uint r = searchKey.search(leaf);
678 if (leaf.rows[r] == oldRow) {
679 leaf.rows[r] = newRow;
680 } else {
681 logInconsistency();
682 }
683 }
684
685 uint BTreeImpl::split(Parent& dst, uint dstPos, Parent& src, uint srcPos) {
686 constexpr size_t mid = Parent::NKEYS / 2;
687 uint pivot = *src.keys[mid];
688 acopy(dst.keys, src.keys + mid + 1, Parent::NKEYS - mid - 1);
689 azero(src.keys + mid, Parent::NKEYS - mid);
690 acopy(dst.children, src.children + mid + 1, Parent::NCHILDREN - mid - 1);
691 azero(src.children + mid + 1, Parent::NCHILDREN - mid - 1);
692 return pivot;
693 }
694
695 uint BTreeImpl::split(Leaf& dst, uint dstPos, Leaf& src, uint srcPos) {
696 constexpr size_t mid = Leaf::NROWS / 2;
697 uint pivot = *src.rows[mid - 1];
698 acopy(dst.rows, src.rows + mid, Leaf::NROWS - mid);
699 azero(src.rows + mid, Leaf::NROWS - mid);
700
701 if (src.next == 0) {
702 endLeaf = dstPos;
703 } else {
704 tree[src.next].leaf.prev = dstPos;
705 }
706 dst.next = src.next;
707 dst.prev = srcPos;
708 src.next = dstPos;
709
710 return pivot;
711 }
712
713 void BTreeImpl::merge(Parent& dst, uint dstPos, uint pivot, Parent& src) {
714 // merge() is only legal if both nodes are half-empty. Meanwhile, B-tree invariants
715 // guarantee that the node can't be more than half-empty, or we would have merged it sooner.
716 // (The root can be more than half-empty, but it is never merged with anything.)
717 KJ_DASSERT(src.isHalfFull());
718 KJ_DASSERT(dst.isHalfFull());
719
720 constexpr size_t mid = Parent::NKEYS/2;
721 dst.keys[mid] = pivot;
722 acopy(dst.keys + mid + 1, src.keys, mid);
723 acopy(dst.children + mid + 1, src.children, mid + 1);
724 }
725
726 void BTreeImpl::merge(Leaf& dst, uint dstPos, uint pivot, Leaf& src) {
727 // merge() is only legal if both nodes are half-empty. Meanwhile, B-tree invariants
728 // guarantee that the node can't be more than half-empty, or we would have merged it sooner.
729 // (The root can be more than half-empty, but it is never merged with anything.)
730 KJ_DASSERT(src.isHalfFull());
731 KJ_DASSERT(dst.isHalfFull());
732
733 constexpr size_t mid = Leaf::NROWS/2;
734 KJ_DASSERT(dst.rows[mid-1] == pivot);
735 acopy(dst.rows + mid, src.rows, mid);
736
737 dst.next = src.next;
738 if (dst.next == 0) {
739 endLeaf = dstPos;
740 } else {
741 tree[dst.next].leaf.prev = dstPos;
742 }
743 }
744
745 void BTreeImpl::move(Parent& dst, uint dstPos, Parent& src) {
746 dst = src;
747 }
748
749 void BTreeImpl::move(Leaf& dst, uint dstPos, Leaf& src) {
750 dst = src;
751 if (src.next == 0) {
752 endLeaf = dstPos;
753 } else {
754 tree[src.next].leaf.prev = dstPos;
755 }
756 if (src.prev == 0) {
757 beginLeaf = dstPos;
758 } else {
759 tree[src.prev].leaf.next = dstPos;
760 }
761 }
762
763 void BTreeImpl::rotateLeft(
764 Parent& left, Parent& right, Parent& parent, uint indexInParent, MaybeUint*& fixup) {
765 // Steal one item from the right node and move it to the left node.
766
767 // Like merge(), this is only called on an exactly-half-empty node.
768 KJ_DASSERT(left.isHalfFull());
769 KJ_DASSERT(right.isMostlyFull());
770
771 constexpr size_t mid = Parent::NKEYS/2;
772 left.keys[mid] = parent.keys[indexInParent];
773 if (fixup == &parent.keys[indexInParent]) fixup = &left.keys[mid];
774 parent.keys[indexInParent] = right.keys[0];
775 left.children[mid + 1] = right.children[0];
776 amove(right.keys, right.keys + 1, Parent::NKEYS - 1);
777 right.keys[Parent::NKEYS - 1] = nullptr;
778 amove(right.children, right.children + 1, Parent::NCHILDREN - 1);
779 right.children[Parent::NCHILDREN - 1] = 0;
780 }
781
782 void BTreeImpl::rotateLeft(
783 Leaf& left, Leaf& right, Parent& parent, uint indexInParent, MaybeUint*& fixup) {
784 // Steal one item from the right node and move it to the left node.
785
786 // Like merge(), this is only called on an exactly-half-empty node.
787 KJ_DASSERT(left.isHalfFull());
788 KJ_DASSERT(right.isMostlyFull());
789
790 constexpr size_t mid = Leaf::NROWS/2;
791 parent.keys[indexInParent] = left.rows[mid] = right.rows[0];
792 if (fixup == &parent.keys[indexInParent]) fixup = nullptr;
793 amove(right.rows, right.rows + 1, Leaf::NROWS - 1);
794 right.rows[Leaf::NROWS - 1] = nullptr;
795 }
796
797 void BTreeImpl::rotateRight(Parent& left, Parent& right, Parent& parent, uint indexInParent) {
798 // Steal one item from the left node and move it to the right node.
799
800 // Like merge(), this is only called on an exactly-half-empty node.
801 KJ_DASSERT(right.isHalfFull());
802 KJ_DASSERT(left.isMostlyFull());
803
804 constexpr size_t mid = Parent::NKEYS/2;
805 amove(right.keys + 1, right.keys, mid);
806 amove(right.children + 1, right.children, mid + 1);
807
808 uint back = left.keyCount() - 1;
809
810 right.keys[0] = parent.keys[indexInParent];
811 parent.keys[indexInParent] = left.keys[back];
812 right.children[0] = left.children[back + 1];
813 left.keys[back] = nullptr;
814 left.children[back + 1] = 0;
815 }
816
817 void BTreeImpl::rotateRight(Leaf& left, Leaf& right, Parent& parent, uint indexInParent) {
818 // Steal one item from the left node and move it to the right node.
819
820 // Like mergeFrom(), this is only called on an exactly-half-empty node.
821 KJ_DASSERT(right.isHalfFull());
822 KJ_DASSERT(left.isMostlyFull());
823
824 constexpr size_t mid = Leaf::NROWS/2;
825 amove(right.rows + 1, right.rows, mid);
826
827 uint back = left.size() - 1;
828
829 right.rows[0] = left.rows[back];
830 parent.keys[indexInParent] = left.rows[back - 1];
831 left.rows[back] = nullptr;
832 }
833
834 void BTreeImpl::Parent::initRoot(uint key, uint leftChild, uint rightChild) {
835 // HACK: This is typically called on the root node immediately after copying its contents away,
836 // but the pointer used to copy it away may be a different pointer pointing to a different
837 // union member which the compiler may not recgonize as aliasing with this object. Just to
838 // be extra-safe, insert a compiler barrier.
839 compilerBarrier();
840
841 keys[0] = key;
842 children[0] = leftChild;
843 children[1] = rightChild;
844 azero(keys + 1, Parent::NKEYS - 1);
845 azero(children + 2, Parent::NCHILDREN - 2);
846 }
847
848 void BTreeImpl::Parent::insertAfter(uint i, uint splitKey, uint child) {
849 KJ_IREQUIRE(children[Parent::NCHILDREN - 1] == 0); // check not full
850
851 amove(keys + i + 1, keys + i, Parent::NKEYS - (i + 1));
852 keys[i] = splitKey;
853
854 amove(children + i + 2, children + i + 1, Parent::NCHILDREN - (i + 2));
855 children[i + 1] = child;
856 }
857
858 void BTreeImpl::Parent::eraseAfter(uint i) {
859 amove(keys + i, keys + i + 1, Parent::NKEYS - (i + 1));
860 keys[Parent::NKEYS - 1] = nullptr;
861 amove(children + i + 1, children + i + 2, Parent::NCHILDREN - (i + 2));
862 children[Parent::NCHILDREN - 1] = 0;
863 }
864
865 } // namespace _
866
867 // =======================================================================================
868 // Insertion order
869
870 const InsertionOrderIndex::Link InsertionOrderIndex::EMPTY_LINK = { 0, 0 };
871
872 InsertionOrderIndex::InsertionOrderIndex(): capacity(0), links(const_cast<Link*>(&EMPTY_LINK)) {}
873 InsertionOrderIndex::InsertionOrderIndex(InsertionOrderIndex&& other)
874 : capacity(other.capacity), links(other.links) {
875 other.capacity = 0;
876 other.links = const_cast<Link*>(&EMPTY_LINK);
877 }
878 InsertionOrderIndex& InsertionOrderIndex::operator=(InsertionOrderIndex&& other) {
879 KJ_DASSERT(&other != this);
880 capacity = other.capacity;
881 links = other.links;
882 other.capacity = 0;
883 other.links = const_cast<Link*>(&EMPTY_LINK);
884 return *this;
885 }
886 InsertionOrderIndex::~InsertionOrderIndex() noexcept(false) {
887 if (links != &EMPTY_LINK) delete[] links;
888 }
889
890 void InsertionOrderIndex::reserve(size_t size) {
891 KJ_ASSERT(size < (1u << 31), "Table too big for InsertionOrderIndex");
892
893 if (size > capacity) {
894 // Need to grow.
895 // Note that `size` and `capacity` do not include the special link[0].
896
897 // Round up to the next power of 2.
898 size_t allocation = 1u << (_::lg(size) + 1);
899 KJ_DASSERT(allocation > size);
900 KJ_DASSERT(allocation <= size * 2);
901
902 // Round first allocation up to 8.
903 allocation = kj::max(allocation, 8);
904
905 Link* newLinks = new Link[allocation];
906 #ifdef KJ_DEBUG
907 // To catch bugs, fill unused links with 0xff.
908 memset(newLinks, 0xff, allocation * sizeof(Link));
909 #endif
910 _::acopy(newLinks, links, capacity + 1);
911 if (links != &EMPTY_LINK) delete[] links;
912 links = newLinks;
913 capacity = allocation - 1;
914 }
915 }
916
917 void InsertionOrderIndex::clear() {
918 links[0] = Link { 0, 0 };
919
920 #ifdef KJ_DEBUG
921 // To catch bugs, fill unused links with 0xff.
922 memset(links + 1, 0xff, capacity * sizeof(Link));
923 #endif
924 }
925
926 kj::Maybe<size_t> InsertionOrderIndex::insertImpl(size_t pos) {
927 if (pos >= capacity) {
928 reserve(pos + 1);
929 }
930
931 links[pos + 1].prev = links[0].prev;
932 links[pos + 1].next = 0;
933 links[links[0].prev].next = pos + 1;
934 links[0].prev = pos + 1;
935
936 return nullptr;
937 }
938
939 void InsertionOrderIndex::eraseImpl(size_t pos) {
940 Link& link = links[pos + 1];
941 links[link.next].prev = link.prev;
942 links[link.prev].next = link.next;
943
944 #ifdef KJ_DEBUG
945 memset(&link, 0xff, sizeof(Link));
946 #endif
947 }
948
949 void InsertionOrderIndex::moveImpl(size_t oldPos, size_t newPos) {
950 Link& link = links[oldPos + 1];
951 Link& newLink = links[newPos + 1];
952
953 newLink = link;
954
955 KJ_DASSERT(links[link.next].prev == oldPos + 1);
956 KJ_DASSERT(links[link.prev].next == oldPos + 1);
957 links[link.next].prev = newPos + 1;
958 links[link.prev].next = newPos + 1;
959
960 #ifdef KJ_DEBUG
961 memset(&link, 0xff, sizeof(Link));
962 #endif
963 }
964
965 } // namespace kj