ref: 1437af59aab6295023dff89337b24b84f2096d9f
parent: 4c1d2d44db117f01d4af59d18d06c5fc0b20f3c1
author: Ori Bernstein <ori@eigenstate.org>
date: Thu Mar 23 15:52:12 EDT 2023
splitleaf: stop resetting fullness
We only pull nodes down as long as there's room in the
leaf; when we switch to the next leaf, it intuitively
makes sense that we're no longer full, but there's a
problem if we do:
If we're splitting:
up: [c d e f g h i j k]
b: [a b c e f w x y z]
and we fill up the new leaf node early:
v
up: [c d e f g h i j k]
b: [a b c e f w x y z]
^
l: [a b c d e f w]
r: []
then we clean out the full marker, and resume
copying, getting this result:
up: []
l: [a b c d e f w]
r: [g h i j k x y z]
we end up with misplaced values, with 'w'
in the left node, when it should be in the right.
While it's suboptimal, if we never resume
pulling values from up, we at least get a
correct result:
up: [g h i j k]
^
l: [a b c d e f w]
r: [x y z]
While we can do a better computation of the
split point to balance things properly,
this gives us a correct result.
--- a/tree.c
+++ b/tree.c
@@ -654,7 +654,6 @@
if(d == l)
if((i == b->nval-2) || (i >= 2 && copied >= halfsz)){d = r;
- full = 0;
spc = Leafspc - (halfsz + Msgmax);
getval(b, i, mid);
}