[rucksack-devel] Fixed the btree stress-test bug

[Arthur Lemmens]

Henrik Hjelte wrote:

> The patch bundle is from darcs, but it is easy to read.

Thanks a lot, I've commited your fixes to CVS now.  See also my
comments below.


> hunk ./p-btrees.lisp 831
> -    (remove-key leaf key)
> +    (remove-key leaf (binding-key binding))

This is a bug fix that you'd sent earlier already, right?
It was in CVS already.


> hunk ./p-btrees.lisp 551
> -  (unless (typep value (btree-key-type btree))
> +  (unless (typep value (btree-value-type btree))

Yes, that looks like a copy & paste error.  Thanks.


> I think it would be nice if rucksack signals error when I give
> a duplicated key to a unique slot.
>But then I noticed the following comment in do.txt:
>  - Check that btrees actually signal an error for duplicate keys.
>     Handle those errors correctly for slot indexes.
> Why does rucksack need to handle the errors?

It's been a while since I looked at this, but I suppose my reasoning was that
the btree errors may need to be signalled in a slightly different way at the
rucksack level.


> hunk ./rucksack.lisp 864
> -          (index-insert index new-value id))))))
> +          (index-insert index new-value id
> +                        :if-exists
> +                        (and (slot-unique slot) :error)))))))

I modified this fix a bit.  If the slot may have duplicate values, your
version passes :IF-EXISTS NIL to INDEX-INSERT.  But :IF-EXISTS is specified
to take either :OVERWRITE or :ERROR, not NIL.


> I think it would be nicer if rucksack signals error for me
> when I give an imcompatible value to a slot with a index.
> (e.g. giving string to :symbol-index.)
>Adding :key-type to index-spec definitions seems to accomplish
> it. But I'm not sure this is right.
>What do you think?

This sounds like a good idea to me. Thanks, I've incorporated
this.


> +(defun update-parents-for-deleted-key (btree parent-stack old-key new-key)
> +  (when parent-stack
> +    (let ((node (first parent-stack)))
> +      (when node
> +        (let ((position (key-position old-key node)))
> +          (when position
> +            (setf (binding-key (node-binding node position))
> +                  new-key)
> +            (update-parents-for-deleted-key btree (rest parent-stack) old-key new-key)))))))
> +
> hunk ./p-btrees.lisp 874
> -    (remove-key leaf (binding-key binding))
> -    (unless (node-full-enough-p btree leaf)
> -      (enlarge-node btree leaf parent-stack))))
> +
> +    (let ((position (key-position key leaf))
> +          (length (btree-node-index-count leaf))
> +          (was-biggest-key-p nil))
> +      (when (= position (1- length))
> +        (setf was-biggest-key-p t))
> +     +      (remove-key leaf (binding-key binding))
> +
> +      (unless (node-full-enough-p btree leaf)
> +        (enlarge-node btree leaf parent-stack))
> +     +      (when was-biggest-key-p
> +        (unless (= 0 (btree-node-index-count leaf))
> +          (update-parents-for-deleted-key btree parent-stack key (biggest-key leaf)))))))


So this was the big bug, right?  If we're deleting the biggest key from
a leaf, we should update the parents so they'll use the key that has now
become the biggest, right?  Thanks a lot for finding and fixing this!

Arthur