Always set next correctly, even if a matching element is found (that is
[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 void *av_tree_find(const AVTreeNode *t, void *key, int (*cmp)(void *key, const void *b), void *next[2]){
32     if(t){
33         unsigned int v= cmp(t->elem, key);
34         if(v){
35             if(next) next[(v>>31)^1]= t->elem;
36             return av_tree_find(t->child[v>>31], key, cmp, next);
37         }else{
38             if(next){
39                 av_tree_find(t->child[0], key, cmp, next);
40                 av_tree_find(t->child[1], key, cmp, next);
41             }
42             return t->elem;
43         }
44     }
45     return NULL;
46 }
47
48 void *av_tree_insert(AVTreeNode **tp, void *key, int (*cmp)(void *key, const void *b)){
49     AVTreeNode *t= *tp;
50     if(t){
51         unsigned int v= cmp(t->elem, key);
52         if(v){
53             int i= v>>31;
54             AVTreeNode **child= &t->child[i];
55             void *ret= av_tree_insert(child, key, cmp);
56             if(!ret){
57                 t->state -= ((int)v>>31)|1;
58                 if(!(t->state&1)){
59                     if(t->state){
60                         if((*child)->state*2 == t->state){
61                             *tp= *child;
62                             *child= (*child)->child[i^1];
63                             (*tp)->child[i^1]= t;
64                             t->state= 0;
65                         }else{
66                             *tp= (*child)->child[i^1];
67                             (*child)->child[i^1]= (*tp)->child[i];
68                             (*tp)->child[i]= *child;
69                             *child= (*tp)->child[i^1];
70                             (*tp)->child[i^1]= t;
71
72                             i= (*tp)->state > 0;
73                             (*tp)->child[i  ]->state= 0;
74                             (*tp)->child[i^1]->state= -(*tp)->state;
75                         }
76                         (*tp)->state=0;
77                     }
78                     return key;
79                 }
80             }
81             return ret;
82         }else{
83             return t->elem;
84         }
85     }else{
86         *tp= av_mallocz(sizeof(AVTreeNode));
87         (*tp)->elem= key;
88         return NULL;
89     }
90 }
91
92 void av_tree_destroy(AVTreeNode *t){
93     av_tree_destroy(t->child[0]);
94     av_tree_destroy(t->child[1]);
95     av_free(t);
96 }
97
98 #if 0
99 void av_tree_enumerate(AVTreeNode *t, void *opaque, int (*f)(void *opaque, void *elem)){
100     int v= f(opaque, t->elem);
101     if(v>=0) av_tree_enumerate(t->child[0], opaque, f);
102     if(v<=0) av_tree_enumerate(t->child[1], opaque, f);
103 }
104 #endif
105
106 #ifdef TEST
107
108 static int check(AVTreeNode *t){
109     if(t){
110         int left= check(t->child[0]);
111         int right= check(t->child[1]);
112
113         if(left>999 || right>999)
114             return 1000;
115         if(right - left != t->state)
116             return 1000;
117         if(t->state>1 || t->state<-1)
118             return 1000;
119         return FFMAX(left, right)+1;
120     }
121     return 0;
122 }
123
124 static void print(AVTreeNode *t, int depth){
125     int i;
126     for(i=0; i<depth*4; i++) av_log(NULL, AV_LOG_ERROR, " ");
127     if(t){
128         av_log(NULL, AV_LOG_ERROR, "Node %p %2d %4d\n", t, t->state, t->elem);
129         print(t->child[0], depth+1);
130         print(t->child[1], depth+1);
131     }else
132         av_log(NULL, AV_LOG_ERROR, "NULL\n");
133 }
134
135 int cmp(const void *a, const void *b){
136     return a-b;
137 }
138
139 int main(void){
140     int i,j,k;
141     AVTreeNode *root= NULL;
142
143     for(i=0; i<10000; i++){
144         int j= (random()%863294);
145         if(check(root) > 999){
146             av_log(NULL, AV_LOG_ERROR, "FATAL error %d\n", i);
147         print(root, 0);
148             return -1;
149         }
150         av_log(NULL, AV_LOG_ERROR, "inserting %4d\n", j);
151         av_tree_insert(&root, (void*)(j+1), cmp);
152     }
153     return 0;
154 }
155 #endif