2 * copyright (c) 2006 Michael Niedermayer <michaelni@gmx.at>
4 * This file is part of FFmpeg.
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.
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.
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
25 typedef struct AVTreeNode{
26 struct AVTreeNode *child[2];
31 void *av_tree_find(const AVTreeNode *t, void *key, int (*cmp)(void *key, const void *b), void *next[2]){
33 unsigned int v= cmp(t->elem, key);
35 if(next) next[(v>>31)^1]= t->elem;
36 return av_tree_find(t->child[v>>31], key, cmp, next);
44 void *av_tree_insert(AVTreeNode **tp, void *key, int (*cmp)(void *key, const void *b)){
47 unsigned int v= cmp(t->elem, key);
50 AVTreeNode **child= &t->child[i];
51 void *ret= av_tree_insert(child, key, cmp);
53 t->state -= ((int)v>>31)|1;
56 if((*child)->state*2 == t->state){
58 *child= (*child)->child[i^1];
62 *tp= (*child)->child[i^1];
63 (*child)->child[i^1]= (*tp)->child[i];
64 (*tp)->child[i]= *child;
65 *child= (*tp)->child[i^1];
69 (*tp)->child[i ]->state= 0;
70 (*tp)->child[i^1]->state= -(*tp)->state;
82 *tp= av_mallocz(sizeof(AVTreeNode));
88 void av_tree_destroy(AVTreeNode *t){
89 av_tree_destroy(t->child[0]);
90 av_tree_destroy(t->child[1]);
95 void av_tree_enumerate(AVTreeNode *t, void *opaque, int (*f)(void *opaque, void *elem)){
96 int v= f(opaque, t->elem);
97 if(v>=0) av_tree_enumerate(t->child[0], opaque, f);
98 if(v<=0) av_tree_enumerate(t->child[1], opaque, f);
104 static int check(AVTreeNode *t){
106 int left= check(t->child[0]);
107 int right= check(t->child[1]);
109 if(left>999 || right>999)
111 if(right - left != t->state)
113 if(t->state>1 || t->state<-1)
115 return FFMAX(left, right)+1;
120 static void print(AVTreeNode *t, int depth){
122 for(i=0; i<depth*4; i++) av_log(NULL, AV_LOG_ERROR, " ");
124 av_log(NULL, AV_LOG_ERROR, "Node %p %2d %4d\n", t, t->state, t->elem);
125 print(t->child[0], depth+1);
126 print(t->child[1], depth+1);
128 av_log(NULL, AV_LOG_ERROR, "NULL\n");
131 int cmp(const void *a, const void *b){
137 AVTreeNode *root= NULL;
139 for(i=0; i<10000; i++){
140 int j= (random()%863294);
141 if(check(root) > 999){
142 av_log(NULL, AV_LOG_ERROR, "FATAL error %d\n", i);
146 av_log(NULL, AV_LOG_ERROR, "inserting %4d\n", j);
147 av_tree_insert(&root, (void*)(j+1), cmp);