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