Skip to content
  • Szabolcs Nagy's avatar
    new tsearch implementation · c50985d5
    Szabolcs Nagy authored
    Rewrote the AVL tree implementation:
    
    - It is now non-recursive with fixed stack usage (large enough for
    worst case tree height). twalk and tdestroy are still recursive as
    that's smaller/simpler.
    
    - Moved unrelated interfaces into separate translation units.
    
    - The node structure is changed to use indexed children instead of
    left/right pointers, this simplifies the balancing logic.
    
    - Using void * pointers instead of struct node * in various places,
    because this better fits the api (node address is passed in a void**
    argument, so it is tempting to incorrectly cast it to struct node **).
    
    - As a further performance improvement the rebalancing now stops
    when it is not needed (subtree height is unchanged). Otherwise
    the behaviour should be the same as before (checked over generated
    random inputs that the resulting tree shape is equivalent).
    
    - Removed the old copyright notice (including prng related one: it
    should be licensed under the same terms as the rest of the project).
    
    .text size of pic tsearch + tfind + tdelete + twalk:
    
       x86_64 i386 aarch64  arm mips powerpc ppc64le  sh4 m68k s390x
    old   941  899    1220 1068 1852    1400    1600 1008 1008  1488
    new   857  881    1040  976 1564    1192    1360  736  820  1408
    c50985d5