• Henrik Gramner's avatar
    checkasm: Use a self-balancing tree · 2ab65b65
    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.
    2ab65b65
Name
Last commit
Last update
..
api Loading commit data...
checkasm Loading commit data...
fate Loading commit data...
filtergraphs Loading commit data...
ref Loading commit data...
Makefile Loading commit data...
audiogen.c Loading commit data...
base64.c Loading commit data...
copycooker.sh Loading commit data...
fate-run.sh Loading commit data...
fate-valgrind.supp Loading commit data...
fate.sh Loading commit data...
ffserver-regression.sh Loading commit data...
ffserver.conf Loading commit data...
ffserver.regression.ref Loading commit data...
lavf-regression.sh Loading commit data...
md5.sh Loading commit data...
reference.pnm Loading commit data...
regression-funcs.sh Loading commit data...
rotozoom.c Loading commit data...
test.ffmeta Loading commit data...
tiny_psnr.c Loading commit data...
tiny_ssim.c Loading commit data...
utils.c Loading commit data...
videogen.c Loading commit data...