diff tree.c @ 413:a54e20281de9 libavutil

Move *malloc() out of tree.c, that way the code can be used with flat arrays which have lower overhead than millions of mallocd() elements.

--- a/tree.c	Fri Jan 04 10:14:21 2008 +0000
+++ b/tree.c	Fri Jan 04 17:52:16 2008 +0000
@@ -28,6 +28,8 @@
     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);
@@ -45,14 +47,14 @@
     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= av_tree_insert(child, key, cmp, next);
             if(!ret){
                 t->state -= ((int)v>>31)|1;
                 if(!(t->state&1)){
@@ -83,7 +85,7 @@
             return t->elem;
         }
     }else{
-        *tp= av_mallocz(sizeof(AVTreeNode));
+        *tp= *next; *next= NULL;
         (*tp)->elem= key;
         return NULL;
     }