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 if(*tp){
00123 (*tp)->elem= key;
00124 return NULL;
00125 }else
00126 return key;
00127 }
00128 }
00129
00130 void av_tree_destroy(AVTreeNode *t){
00131 if(t){
00132 av_tree_destroy(t->child[0]);
00133 av_tree_destroy(t->child[1]);
00134 av_free(t);
00135 }
00136 }
00137
00138 #if 0
00139 void av_tree_enumerate(AVTreeNode *t, void *opaque, int (*f)(void *opaque, void *elem)){
00140 int v= f(opaque, t->elem);
00141 if(v>=0) av_tree_enumerate(t->child[0], opaque, f);
00142 if(v<=0) av_tree_enumerate(t->child[1], opaque, f);
00143 }
00144 #endif
00145
00146 #ifdef TEST
00147 #undef random
00148 static int check(AVTreeNode *t){
00149 if(t){
00150 int left= check(t->child[0]);
00151 int right= check(t->child[1]);
00152
00153 if(left>999 || right>999)
00154 return 1000;
00155 if(right - left != t->state)
00156 return 1000;
00157 if(t->state>1 || t->state<-1)
00158 return 1000;
00159 return FFMAX(left, right)+1;
00160 }
00161 return 0;
00162 }
00163
00164 static void print(AVTreeNode *t, int depth){
00165 int i;
00166 for(i=0; i<depth*4; i++) av_log(NULL, AV_LOG_ERROR, " ");
00167 if(t){
00168 av_log(NULL, AV_LOG_ERROR, "Node %p %2d %4d\n", t, t->state, t->elem);
00169 print(t->child[0], depth+1);
00170 print(t->child[1], depth+1);
00171 }else
00172 av_log(NULL, AV_LOG_ERROR, "NULL\n");
00173 }
00174
00175 int cmp(const void *a, const void *b){
00176 return a-b;
00177 }
00178
00179 int main(void){
00180 int i,k;
00181 AVTreeNode *root= NULL, *node=NULL;
00182
00183 for(i=0; i<10000; i++){
00184 int j= (random()%86294);
00185 if(check(root) > 999){
00186 av_log(NULL, AV_LOG_ERROR, "FATAL error %d\n", i);
00187 print(root, 0);
00188 return -1;
00189 }
00190 av_log(NULL, AV_LOG_ERROR, "inserting %4d\n", j);
00191 if(!node)
00192 node= av_mallocz(av_tree_node_size);
00193 av_tree_insert(&root, (void*)(j+1), cmp, &node);
00194
00195 j= (random()%86294);
00196 {
00197 AVTreeNode *node2=NULL;
00198 av_log(NULL, AV_LOG_ERROR, "removing %4d\n", j);
00199 av_tree_insert(&root, (void*)(j+1), cmp, &node2);
00200 k= av_tree_find(root, (void*)(j+1), cmp, NULL);
00201 if(k)
00202 av_log(NULL, AV_LOG_ERROR, "removal failure %d\n", i);
00203 }
00204 }
00205 return 0;
00206 }
00207 #endif