[rucksack-devel] PATCH: b-tree binary search

[Arthur Lemmens]

Cyrus Harmon wrote:

> My understanding from reading the code was that the last element was
> somehow special and has a weird key value that we can't do btree-key<
> on and that this was detected in the old version by the presence of
> the (= i last-index), but we still return the (binding-value ...) for
> it.

Yes, I think you're right.  The key for the last element is the symbol
KEY-IRRELEVANT.  It's irrelevant because the child values for a btree
element are all BTREE-KEY<= the key, but the children of the last element
are all BTREE-KEY> the key of the previous element.  You could say they're
less than infinity ;-)

> Note that this only applies to find-subnode, not find-binding in node,
> or so it seemed to me.

Yes, FIND-BINDING-IN-NODE only needs to work for leaf nodes.  In leaf
nodes, you're looking for an exact key match (according to BTREE-KEY=).
This is different from FIND-SUBNODE, which looks for a child node that
contains a certain range of keys.

Arthur