-
Tim Peters authored
key S in a bucket in a BTree is deleted, doing a range search on the BTree with S on the high end may claim that the range is empty even when it's not. It proved difficult to fix this correctly and efficiently in all cases (our BTrees don't like "searching backwards"). The implementation here is a new and non-recursive one (in effect, to do this efficiently you have to remember the deepest point in the tree where it was *possible* to "go one left" of where binary search tells you to go; an iterative algorithm makes that part all but obvious). Alas, the number of uses of persistence macros is amazing, unfortunately making this still-hairy algorithm hard to follow. testPathologicalRangeSearch(): uncommented the lines that failed before this patch. They pass now. Insecurity: The test case only exercises the simplest possible form of the failure. Any failing case is hard to provoke, even the simplest. The hairier failing cases require generating degenerate trees, deep and with some interior nodes near the top having just one or two children (since the tree needs to be deep too, that isn't easy to provoke). I'll think about how to provoke this without needing to build up multi-million element trees first; maybe using __setstate__ directly is the answer.
d82d25a3