00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021 #include "common.h"
00022 #include "log.h"
00023 #include "tree.h"
00024
00025 typedef struct AVTreeNode{
00026 struct AVTreeNode *child[2];
00027 void *elem;
00028 int state;
00029 }AVTreeNode;
00030
00031 const int av_tree_node_size = sizeof(AVTreeNode);
00032
00033 void *av_tree_find(const AVTreeNode *t, void *key, int (*cmp)(void *key, const void *b), void *next[2]){
00034 if(t){
00035 unsigned int v= cmp(key, t->elem);
00036 if(v){
00037 if(next) next[v>>31]= t->elem;
00038 return av_tree_find(t->child[(v>>31)^1], key, cmp, next);
00039 }else{
00040 if(next){
00041 av_tree_find(t->child[0], key, cmp, next);
00042 av_tree_find(t->child[1], key, cmp, next);
00043 }
00044 return t->elem;
00045 }
00046 }
00047 return NULL;
00048 }
00049
00050 void *av_tree_insert(AVTreeNode **tp, void *key, int (*cmp)(void *key, const void *b), AVTreeNode **next){
00051 AVTreeNode *t= *tp;
00052 if(t){
00053 unsigned int v= cmp(t->elem, key);
00054 void *ret;
00055 if(!v){
00056 if(*next)
00057 return t->elem;
00058 else if(t->child[0]||t->child[1]){
00059 int i= !t->child[0];
00060 void *next_elem[2];
00061 av_tree_find(t->child[i], key, cmp, next_elem);
00062 key= t->elem= next_elem[i];
00063 v= -i;
00064 }else{
00065 *next= t;
00066 *tp=NULL;
00067 return NULL;
00068 }
00069 }
00070 ret= av_tree_insert(&t->child[v>>31], key, cmp, next);
00071 if(!ret){
00072 int i= (v>>31) ^ !!*next;
00073 AVTreeNode **child= &t->child[i];
00074 t->state += 2*i - 1;
00075
00076 if(!(t->state&1)){
00077 if(t->state){
00078
00079
00080
00081
00082
00083
00084
00085
00086
00087
00088
00089
00090
00091
00092
00093
00094
00095
00096 if((*child)->state*2 == -t->state){
00097 *tp= (*child)->child[i^1];
00098 (*child)->child[i^1]= (*tp)->child[i];
00099 (*tp)->child[i]= *child;
00100 *child= (*tp)->child[i^1];
00101 (*tp)->child[i^1]= t;
00102
00103 (*tp)->child[0]->state= -((*tp)->state>0);
00104 (*tp)->child[1]->state= (*tp)->state<0 ;
00105 (*tp)->state=0;
00106 }else{
00107 *tp= *child;
00108 *child= (*child)->child[i^1];
00109 (*tp)->child[i^1]= t;
00110 if((*tp)->state) t->state = 0;
00111 else t->state>>= 1;
00112 (*tp)->state= -t->state;
00113 }
00114 }
00115 }
00116 if(!(*tp)->state ^ !!*next)
00117 return key;
00118 }
00119 return ret;
00120 }else{
00121 *tp= *next; *next= NULL;
00122 (*tp)->elem= key;
00123 return NULL;
00124 }
00125 }
00126
00127 void av_tree_destroy(AVTreeNode *t){
00128 av_tree_destroy(t->child[0]);
00129 av_tree_destroy(t->child[1]);
00130 av_free(t);
00131 }
00132
00133 #if 0
00134 void av_tree_enumerate(AVTreeNode *t, void *opaque, int (*f)(void *opaque, void *elem)){
00135 int v= f(opaque, t->elem);
00136 if(v>=0) av_tree_enumerate(t->child[0], opaque, f);
00137 if(v<=0) av_tree_enumerate(t->child[1], opaque, f);
00138 }
00139 #endif
00140
00141 #ifdef TEST
00142 #undef random
00143 static int check(AVTreeNode *t){
00144 if(t){
00145 int left= check(t->child[0]);
00146 int right= check(t->child[1]);
00147
00148 if(left>999 || right>999)
00149 return 1000;
00150 if(right - left != t->state)
00151 return 1000;
00152 if(t->state>1 || t->state<-1)
00153 return 1000;
00154 return FFMAX(left, right)+1;
00155 }
00156 return 0;
00157 }
00158
00159 static void print(AVTreeNode *t, int depth){
00160 int i;
00161 for(i=0; i<depth*4; i++) av_log(NULL, AV_LOG_ERROR, " ");
00162 if(t){
00163 av_log(NULL, AV_LOG_ERROR, "Node %p %2d %4d\n", t, t->state, t->elem);
00164 print(t->child[0], depth+1);
00165 print(t->child[1], depth+1);
00166 }else
00167 av_log(NULL, AV_LOG_ERROR, "NULL\n");
00168 }
00169
00170 int cmp(const void *a, const void *b){
00171 return a-b;
00172 }
00173
00174 int main(void){
00175 int i,k;
00176 AVTreeNode *root= NULL, *node=NULL;
00177
00178 for(i=0; i<10000; i++){
00179 int j= (random()%86294);
00180 if(check(root) > 999){
00181 av_log(NULL, AV_LOG_ERROR, "FATAL error %d\n", i);
00182 print(root, 0);
00183 return -1;
00184 }
00185 av_log(NULL, AV_LOG_ERROR, "inserting %4d\n", j);
00186 if(!node)
00187 node= av_mallocz(av_tree_node_size);
00188 av_tree_insert(&root, (void*)(j+1), cmp, &node);
00189
00190 j= (random()%86294);
00191 k= av_tree_find(root, (void*)(j+1), cmp, NULL);
00192 if(k){
00193 AVTreeNode *node2=NULL;
00194 av_log(NULL, AV_LOG_ERROR, "removing %4d\n", j);
00195 av_tree_insert(&root, (void*)(j+1), cmp, &node2);
00196 k= av_tree_find(root, (void*)(j+1), cmp, NULL);
00197 if(k)
00198 av_log(NULL, AV_LOG_ERROR, "removial failure %d\n", i);
00199 }
00200 }
00201 return 0;
00202 }
00203 #endif