• Henrik Gramner's avatar
    checkasm: Use a self-balancing tree · 5405584b
    Henrik Gramner authored
    Tested functions are internally kept in a binary search tree for efficient
    lookups. The downside of the current implementation is that the tree quickly
    becomes unbalanced which causes an unneccessary amount of comparisons between
    nodes. Improve this by changing the tree into a self-balancing left-leaning
    red-black tree with a worst case lookup/insertion time complexity of O(log n).
    
    Significantly reduces the recursion depth and makes the tests run around 10%
    faster overall. The relative performance improvement compared to the existing
    non-balanced tree will also most likely increase as more tests are added.
    Signed-off-by: 's avatarAnton Khirnov <anton@khirnov.net>
    5405584b
checkasm.c 14.8 KB