aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMichael Niedermayer <michaelni@gmx.at>2008-01-23 21:03:21 +0000
committerMichael Niedermayer <michaelni@gmx.at>2008-01-23 21:03:21 +0000
commit51198a8737d5088e2fa972ba5251fa4a3c06bbaf (patch)
treea1ee319f60f324b45347afb1c1709b354d6eeef0
parent07ad12ecdd951a171e9f5e1a64db3890198c993b (diff)
downloadffmpeg-51198a8737d5088e2fa972ba5251fa4a3c06bbaf.tar.gz
Comment to explain how the add/remove core works.
Originally committed as revision 11603 to svn://svn.ffmpeg.org/ffmpeg/trunk
-rw-r--r--libavutil/tree.c18
1 files changed, 18 insertions, 0 deletions
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];