Move *malloc() out of tree.c, that way the code can be used with
[ffmpeg.git] / libavutil / tree.c
1 /*
2  * copyright (c) 2006 Michael Niedermayer <michaelni@gmx.at>
3  *
4  * This file is part of FFmpeg.
5  *
6  * FFmpeg is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU Lesser General Public
8  * License as published by the Free Software Foundation; either
9  * version 2.1 of the License, or (at your option) any later version.
10  *
11  * FFmpeg is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14  * Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with FFmpeg; if not, write to the Free Software
18  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
19  */
20
21 #include "common.h"
22 #include "log.h"
23 #include "tree.h"
24
25 typedef struct AVTreeNode{
26     struct AVTreeNode *child[2];
27     void *elem;
28     int state;
29 }AVTreeNode;
30
31 const int av_tree_node_size = sizeof(AVTreeNode);
32
33 void *av_tree_find(const AVTreeNode *t, void *key, int (*cmp)(void *key, const void *b), void *next[2]){
34     if(t){
35         unsigned int v= cmp(t->elem, key);
36         if(v){
37             if(next) next[(v>>31)^1]= t->elem;
38             return av_tree_find(t->child[v>>31], key, cmp, next);
39         }else{
40             if(next){
41                 av_tree_find(t->child[0], key, cmp, next);
42                 av_tree_find(t->child[1], key, cmp, next);
43             }
44             return t->elem;
45         }
46     }
47     return NULL;
48 }
49
50 void *av_tree_insert(AVTreeNode **tp, void *key, int (*cmp)(void *key, const void *b), AVTreeNode **next){
51     AVTreeNode *t= *tp;
52     if(t){
53         unsigned int v= cmp(t->elem, key);
54         if(v){
55             int i= v>>31;
56             AVTreeNode **child= &t->child[i];
57             void *ret= av_tree_insert(child, key, cmp, next);
58             if(!ret){
59                 t->state -= ((int)v>>31)|1;
60                 if(!(t->state&1)){
61                     if(t->state){
62                         if((*child)->state*2 == t->state){
63                             *tp= *child;
64                             *child= (*child)->child[i^1];
65                             (*tp)->child[i^1]= t;
66                             t->state= 0;
67                         }else{
68                             *tp= (*child)->child[i^1];
69                             (*child)->child[i^1]= (*tp)->child[i];
70                             (*tp)->child[i]= *child;
71                             *child= (*tp)->child[i^1];
72                             (*tp)->child[i^1]= t;
73
74                             i= (*tp)->state > 0;
75                             (*tp)->child[i  ]->state= 0;
76                             (*tp)->child[i^1]->state= -(*tp)->state;
77                         }
78                         (*tp)->state=0;
79                     }
80                     return key;
81                 }
82             }
83             return ret;
84         }else{
85             return t->elem;
86         }
87     }else{
88         *tp= *next; *next= NULL;
89         (*tp)->elem= key;
90         return NULL;
91     }
92 }
93
94 void av_tree_destroy(AVTreeNode *t){
95     av_tree_destroy(t->child[0]);
96     av_tree_destroy(t->child[1]);
97     av_free(t);
98 }
99
100 #if 0
101 void av_tree_enumerate(AVTreeNode *t, void *opaque, int (*f)(void *opaque, void *elem)){
102     int v= f(opaque, t->elem);
103     if(v>=0) av_tree_enumerate(t->child[0], opaque, f);
104     if(v<=0) av_tree_enumerate(t->child[1], opaque, f);
105 }
106 #endif
107
108 #ifdef TEST
109
110 static int check(AVTreeNode *t){
111     if(t){
112         int left= check(t->child[0]);
113         int right= check(t->child[1]);
114
115         if(left>999 || right>999)
116             return 1000;
117         if(right - left != t->state)
118             return 1000;
119         if(t->state>1 || t->state<-1)
120             return 1000;
121         return FFMAX(left, right)+1;
122     }
123     return 0;
124 }
125
126 static void print(AVTreeNode *t, int depth){
127     int i;
128     for(i=0; i<depth*4; i++) av_log(NULL, AV_LOG_ERROR, " ");
129     if(t){
130         av_log(NULL, AV_LOG_ERROR, "Node %p %2d %4d\n", t, t->state, t->elem);
131         print(t->child[0], depth+1);
132         print(t->child[1], depth+1);
133     }else
134         av_log(NULL, AV_LOG_ERROR, "NULL\n");
135 }
136
137 int cmp(const void *a, const void *b){
138     return a-b;
139 }
140
141 int main(void){
142     int i,j,k;
143     AVTreeNode *root= NULL;
144
145     for(i=0; i<10000; i++){
146         int j= (random()%863294);
147         if(check(root) > 999){
148             av_log(NULL, AV_LOG_ERROR, "FATAL error %d\n", i);
149         print(root, 0);
150             return -1;
151         }
152         av_log(NULL, AV_LOG_ERROR, "inserting %4d\n", j);
153         av_tree_insert(&root, (void*)(j+1), cmp);
154     }
155     return 0;
156 }
157 #endif