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

[Cyrus Harmon]

On Jan 14, 2007, at 3:02 PM, Arthur Lemmens wrote:

> Cyrus Harmon wrote:
>
>> +  (let ((btree-key< (btree-key< btree))
>> +        (last (1- (btree-node-index-count node))))
>> +    (labels ((binary-search (start end)
>> +               (let* ((mid (+ start (truncate (- end start) 2)))
>> +                      (mid-binding (node-binding node mid)))
>> +                 (if (= start mid)
>> +                     (if (not (funcall btree-key< (binding-key  
>> mid-binding) key))
>> +                         (binding-value mid-binding)
>> +                         (binding-value (node-binding node (1+  
>> mid))))
>
> I would be inclined to get rid of the IF NOT by reversing the order
> of the branches:
>
>             (if (funcall btree-key< (binding-key mid-binding) key)
>                 (binding-value (node-binding node (1+ mid))
>                 (binding-value mid-binding))
>
> But that's no big deal.

Yes, that seems reasonable.

>
>> +                     (if (not (funcall btree-key< (binding-key  
>> mid-binding) key))
>> +                         (binary-search start mid)
>> +                         (binary-search mid end))))))
>
> Same here.

ditto

>
>> +      (if (funcall btree-key< (binding-key (node-binding node (1-  
>> last))) key)
>> +          (binding-value (node-binding node last))
>> +          (binary-search 0 (1- last)))))
>
> I find the (1- LAST) a bit suspicious here, because LAST is already
> (1- (BTREE-NODE-INDEX-COUNT NODE)).  So if a node has only one  
> element,
> this would fail, right?  (It's been a while, so I don't even remember
> if it's possible that a node has only 1 element.  But I'd feel safer
> if you wrote this part in such a way that it doesn't depend on a  
> minimum
> number of node elements.)

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. It took me a while to figure this out and ICBW, but that's what  
it looked like to me. Note that this only applies to find-subnode,  
not find-binding in node, or so it seemed to me.

Cyrus