• Tim Peters's avatar
    New btrees module check.py (and test program). The primary new function · f4e8c075
    Tim Peters authored
    is check.check(btree), which performs value-based sanity checks on a
    BTree (or TreeSet) that the btree._check() method doesn't do.  The new
    checks include that all the bucket keys are in sorted order, and that
    all the keys within each bucket, and within each internal BTree node,
    lie within the range necessary for that node.  That last is a subtle
    invariant that can't be checked locally:  it requires propagating range
    info down the tree, and modifying it for each child and each level.
    This *should* catch any BTree B for which iterating over the keys yields
    a key K for which B.has_key(K) returns false.
    
    Another function check.display(btree) prints the internal structure of
    a BTree (or TreeSet, Bucket, or Set) to stdout.  If check.check(B) ever
    complains, a clearer picture of the damage can be gotten by staring at
    check.display(B)'s output.
    
    Also beefed up the regular BTree tests by calling check.check() in key
    places.  No surprises (the tests still pass).
    f4e8c075
check.py 14.8 KB