]> git.sesse.net Git - ffmpeg/commit
checkasm: Use a self-balancing tree
authorHenrik Gramner <henrik@gramner.com>
Fri, 25 Sep 2015 19:35:35 +0000 (21:35 +0200)
committerAnton Khirnov <anton@khirnov.net>
Mon, 28 Sep 2015 09:16:33 +0000 (11:16 +0200)
commit5405584b7b54ca889c341743de1d58792449830d
treee3357b9942c3893291e8c61c7b664c10fea7da0d
parenta41e5e192ed8f79f6607f978dee3205580ba5039
checkasm: Use a self-balancing tree

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: Anton Khirnov <anton@khirnov.net>
tests/checkasm/checkasm.c