• Tim Peters's avatar
    BTree_findRangeEnd(): Fixed "the range search bug": if the smallest · d82d25a3
    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
BTreeTemplate.c 37.2 KB