Fix selftest.
[ffmpeg.git] / libavutil / tree.c
index c929e48..cc36676 100644 (file)
@@ -28,6 +28,8 @@ typedef struct AVTreeNode{
     int state;
 }AVTreeNode;
 
+const int av_tree_node_size = sizeof(AVTreeNode);
+
 void *av_tree_find(const AVTreeNode *t, void *key, int (*cmp)(void *key, const void *b), void *next[2]){
     if(t){
         unsigned int v= cmp(t->elem, key);
@@ -35,51 +37,71 @@ void *av_tree_find(const AVTreeNode *t, void *key, int (*cmp)(void *key, const v
             if(next) next[(v>>31)^1]= t->elem;
             return av_tree_find(t->child[v>>31], key, cmp, next);
         }else{
+            if(next){
+                av_tree_find(t->child[0], key, cmp, next);
+                av_tree_find(t->child[1], key, cmp, next);
+            }
             return t->elem;
         }
     }
     return NULL;
 }
 
-void *av_tree_insert(AVTreeNode **tp, void *key, int (*cmp)(void *key, const void *b)){
+void *av_tree_insert(AVTreeNode **tp, void *key, int (*cmp)(void *key, const void *b), AVTreeNode **next){
     AVTreeNode *t= *tp;
     if(t){
         unsigned int v= cmp(t->elem, key);
-        if(v){
-            int i= v>>31;
-            AVTreeNode **child= &t->child[i];
-            void *ret= av_tree_insert(child, key, cmp);
+        void *ret;
+        if(!v){
+            if(*next)
+                return t->elem;
+            else if(t->child[0]||t->child[1]){
+                int i= !t->child[0];
+                AVTreeNode **child= &t->child[i];
+                void *next_elem[2];
+                av_tree_find(*child, key, cmp, next_elem);
+                key= t->elem= next_elem[i];
+                v= -i;
+            }else{
+                *next= t;
+                *tp=NULL;
+                return NULL;
+            }
+        }
+            ret= av_tree_insert(&t->child[v>>31], key, cmp, next);
             if(!ret){
-                t->state -= ((int)v>>31)|1;
+                int i= (v>>31) ^ !!*next;
+                AVTreeNode **child= &t->child[i];
+                t->state += 2*i - 1;
+
                 if(!(t->state&1)){
                     if(t->state){
-                        if((*child)->state*2 == t->state){
-                            *tp= *child;
-                            *child= (*child)->child[i^1];
-                            (*tp)->child[i^1]= t;
-                            t->state= 0;
-                        }else{
+                        if((*child)->state*2 == -t->state){
                             *tp= (*child)->child[i^1];
                             (*child)->child[i^1]= (*tp)->child[i];
                             (*tp)->child[i]= *child;
                             *child= (*tp)->child[i^1];
                             (*tp)->child[i^1]= t;
 
-                            i= (*tp)->state > 0;
-                            (*tp)->child[i  ]->state= 0;
-                            (*tp)->child[i^1]->state= -(*tp)->state;
+                            (*tp)->child[0]->state= -((*tp)->state>0);
+                            (*tp)->child[1]->state=   (*tp)->state<0 ;
+                            (*tp)->state=0;
+                        }else{
+                            *tp= *child;
+                            *child= (*child)->child[i^1];
+                            (*tp)->child[i^1]= t;
+                            if((*tp)->state) t->state  = 0;
+                            else             t->state>>= 1;
+                            (*tp)->state= -t->state;
                         }
-                        (*tp)->state=0;
                     }
-                    return key;
                 }
+                if(!(*tp)->state ^ !!*next)
+                    return key;
             }
             return ret;
-        }else{
-            return t->elem;
-        }
     }else{
-        *tp= av_mallocz(sizeof(AVTreeNode));
+        *tp= *next; *next= NULL;
         (*tp)->elem= key;
         return NULL;
     }
@@ -100,7 +122,7 @@ void av_tree_enumerate(AVTreeNode *t, void *opaque, int (*f)(void *opaque, void
 #endif
 
 #ifdef TEST
-
+#undef random
 static int check(AVTreeNode *t){
     if(t){
         int left= check(t->child[0]);
@@ -132,19 +154,31 @@ int cmp(const void *a, const void *b){
     return a-b;
 }
 
-int main(){
+int main(void){
     int i,j,k;
-    AVTreeNode *root= NULL;
+    AVTreeNode *root= NULL, *node=NULL;
 
     for(i=0; i<10000; i++){
-        int j= (random()%863294);
+        int j= (random()%86294);
         if(check(root) > 999){
             av_log(NULL, AV_LOG_ERROR, "FATAL error %d\n", i);
         print(root, 0);
             return -1;
         }
         av_log(NULL, AV_LOG_ERROR, "inserting %4d\n", j);
-        av_tree_insert(&root, (void*)(j+1), cmp);
+        if(!node)
+            node= av_mallocz(av_tree_node_size);
+        av_tree_insert(&root, (void*)(j+1), cmp, &node);
+
+        j= (random()%86294);
+        k= av_tree_find(root, (void*)(j+1), cmp, NULL);
+        if(k){
+            AVTreeNode *node2=NULL;
+            av_tree_insert(&root, (void*)(j+1), cmp, &node2);
+            k= av_tree_find(root, (void*)(j+1), cmp, NULL);
+            if(k)
+                av_log(NULL, AV_LOG_ERROR, "removial failure %d\n", i);
+        }
     }
     return 0;
 }