From 51198a8737d5088e2fa972ba5251fa4a3c06bbaf Mon Sep 17 00:00:00 2001 From: Michael Niedermayer Date: Wed, 23 Jan 2008 21:03:21 +0000 Subject: Comment to explain how the add/remove core works. Originally committed as revision 11603 to svn://svn.ffmpeg.org/ffmpeg/trunk --- libavutil/tree.c | 18 ++++++++++++++++++ 1 file changed, 18 insertions(+) (limited to 'libavutil/tree.c') diff --git a/libavutil/tree.c b/libavutil/tree.c index 1a102e4e95..cb442ff4b0 100644 --- a/libavutil/tree.c +++ b/libavutil/tree.c @@ -75,6 +75,24 @@ void *av_tree_insert(AVTreeNode **tp, void *key, int (*cmp)(void *key, const voi if(!(t->state&1)){ if(t->state){ + /* The following code is equivalent to + if((*child)->state*2 == -t->state) + rotate(child, i^1); + rotate(tp, i); + + with rotate(): + static void rotate(AVTreeNode **tp, int i){ + AVTreeNode *t= *tp; + + *tp= t->child[i]; + t->child[i]= t->child[i]->child[i^1]; + (*tp)->child[i^1]= t; + i= 4*t->state + 2*(*tp)->state + 12; + t ->state= ((0x614586 >> i) & 3)-1; + (*tp)->state= ((*tp)->state>>1) + ((0x400EEA >> i) & 3)-1; + } + but such a rotate function is both bigger and slower + */ if((*child)->state*2 == -t->state){ *tp= (*child)->child[i^1]; (*child)->child[i^1]= (*tp)->child[i]; -- cgit v1.2.3