[FFmpeg-devel] [PATCH] checkasm: Use a self-balancing tree

[Michael Niedermayer]

On Fri, Sep 25, 2015 at 09:28:26PM +0200, Henrik Gramner wrote:
> 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.
> ---
>  tests/checkasm/checkasm.c | 59 +++++++++++++++++++++++++++++++++++++----------
>  1 file changed, 47 insertions(+), 12 deletions(-)

is there any reason why this doesnt use
libavutil/tree.* ?

[...]
-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

The educated differ from the uneducated as much as the living from the
dead. -- Aristotle 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 181 bytes
Desc: Digital signature
URL: <http://ffmpeg.org/pipermail/ffmpeg-devel/attachments/20150925/b672555a/attachment.sig>