[rucksack-devel] Re: btree-delete bug

[Arthur Lemmens]

> Reinserting works well, but 1 out of, say, 10 times I still get a
> problem while deleting very much stuff from the btree.  Did you try
> that earlier with your tests?  My impression is that your original
> delete works well as long as you don't delete very much, but once
> you start deleting a lot (say more than 60 percent or so), you can
> run into problems, depending on the exact structure of the btree.

It looks like sometimes leaf nodes could become totally empty without
being merged with another node.  I fixed this by changing < to <=
in NODE-HAS-MIN-SIZE-P:

(defun node-has-min-size-p (btree node)
   (<= (btree-node-index-count node)
       (floor (btree-max-node-size btree) 2)))

This makes the test in ENLARGE-NODE less rigid and means that JOIN-NODES
will also be called when nodes happen to become less than half full
instead of exactly half full.

This seems to work well.  But I still haven't reached the finish. Once
every 20 runs or so I now get a problem when re-inserting.  Oh well...
At least I'm making progress.

Arthur