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 "error.h" 22#include "log.h" 23#include "mem.h" 24#include "tree.h" 25 26typedef struct AVTreeNode { 27 struct AVTreeNode *child[2]; 28 void *elem; 29 int state; 30} AVTreeNode; 31 32const int av_tree_node_size = sizeof(AVTreeNode); 33 34struct AVTreeNode *av_tree_node_alloc(void) 35{ 36 return av_mallocz(sizeof(struct AVTreeNode)); 37} 38 39void *av_tree_find(const AVTreeNode *t, void *key, 40 int (*cmp)(void *key, const void *b), void *next[2]) 41{ 42 if (t) { 43 unsigned int v = cmp(key, t->elem); 44 if (v) { 45 if (next) 46 next[v >> 31] = t->elem; 47 return av_tree_find(t->child[(v >> 31) ^ 1], key, cmp, next); 48 } else { 49 if (next) { 50 av_tree_find(t->child[0], key, cmp, next); 51 av_tree_find(t->child[1], key, cmp, next); 52 } 53 return t->elem; 54 } 55 } 56 return NULL; 57} 58 59void *av_tree_insert(AVTreeNode **tp, void *key, 60 int (*cmp)(void *key, const void *b), AVTreeNode **next) 61{ 62 AVTreeNode *t = *tp; 63 if (t) { 64 unsigned int v = cmp(t->elem, key); 65 void *ret; 66 if (!v) { 67 if (*next) 68 return t->elem; 69 else if (t->child[0] || t->child[1]) { 70 int i = !t->child[0]; 71 void *next_elem[2]; 72 av_tree_find(t->child[i], key, cmp, next_elem); 73 key = t->elem = next_elem[i]; 74 v = -i; 75 } else { 76 *next = t; 77 *tp = NULL; 78 return NULL; 79 } 80 } 81 ret = av_tree_insert(&t->child[v >> 31], key, cmp, next); 82 if (!ret) { 83 int i = (v >> 31) ^ !!*next; 84 AVTreeNode **child = &t->child[i]; 85 t->state += 2 * i - 1; 86 87 if (!(t->state & 1)) { 88 if (t->state) { 89 /* The following code is equivalent to 90 * if ((*child)->state * 2 == -t->state) 91 * rotate(child, i ^ 1); 92 * rotate(tp, i); 93 * 94 * with rotate(): 95 * static void rotate(AVTreeNode **tp, int i) 96 * { 97 * AVTreeNode *t= *tp; 98 * 99 * *tp = t->child[i]; 100 * t->child[i] = t->child[i]->child[i ^ 1]; 101 * (*tp)->child[i ^ 1] = t; 102 * i = 4 * t->state + 2 * (*tp)->state + 12; 103 * t->state = ((0x614586 >> i) & 3) - 1; 104 * (*tp)->state = ((0x400EEA >> i) & 3) - 1 + 105 * ((*tp)->state >> 1); 106 * } 107 * but such a rotate function is both bigger and slower 108 */ 109 if ((*child)->state * 2 == -t->state) { 110 *tp = (*child)->child[i ^ 1]; 111 (*child)->child[i ^ 1] = (*tp)->child[i]; 112 (*tp)->child[i] = *child; 113 *child = (*tp)->child[i ^ 1]; 114 (*tp)->child[i ^ 1] = t; 115 116 (*tp)->child[0]->state = -((*tp)->state > 0); 117 (*tp)->child[1]->state = (*tp)->state < 0; 118 (*tp)->state = 0; 119 } else { 120 *tp = *child; 121 *child = (*child)->child[i ^ 1]; 122 (*tp)->child[i ^ 1] = t; 123 if ((*tp)->state) 124 t->state = 0; 125 else 126 t->state >>= 1; 127 (*tp)->state = -t->state; 128 } 129 } 130 } 131 if (!(*tp)->state ^ !!*next) 132 return key; 133 } 134 return ret; 135 } else { 136 *tp = *next; 137 *next = NULL; 138 if (*tp) { 139 (*tp)->elem = key; 140 return NULL; 141 } else 142 return key; 143 } 144} 145 146void av_tree_destroy(AVTreeNode *t) 147{ 148 if (t) { 149 av_tree_destroy(t->child[0]); 150 av_tree_destroy(t->child[1]); 151 av_free(t); 152 } 153} 154 155void av_tree_enumerate(AVTreeNode *t, void *opaque, 156 int (*cmp)(void *opaque, void *elem), 157 int (*enu)(void *opaque, void *elem)) 158{ 159 if (t) { 160 int v = cmp ? cmp(opaque, t->elem) : 0; 161 if (v >= 0) 162 av_tree_enumerate(t->child[0], opaque, cmp, enu); 163 if (v == 0) 164 enu(opaque, t->elem); 165 if (v <= 0) 166 av_tree_enumerate(t->child[1], opaque, cmp, enu); 167 } 168} 169 170#ifdef TEST 171 172#include "common.h" 173#include "lfg.h" 174 175static int check(AVTreeNode *t) 176{ 177 if (t) { 178 int left = check(t->child[0]); 179 int right = check(t->child[1]); 180 181 if (left > 999 || right > 999) 182 return 1000; 183 if (right - left != t->state) 184 return 1000; 185 if (t->state > 1 || t->state < -1) 186 return 1000; 187 return FFMAX(left, right) + 1; 188 } 189 return 0; 190} 191 192static void print(AVTreeNode *t, int depth) 193{ 194 int i; 195 for (i = 0; i < depth * 4; i++) 196 av_log(NULL, AV_LOG_ERROR, " "); 197 if (t) { 198 av_log(NULL, AV_LOG_ERROR, "Node %p %2d %p\n", t, t->state, t->elem); 199 print(t->child[0], depth + 1); 200 print(t->child[1], depth + 1); 201 } else 202 av_log(NULL, AV_LOG_ERROR, "NULL\n"); 203} 204 205static int cmp(void *a, const void *b) 206{ 207 return (uint8_t *) a - (const uint8_t *) b; 208} 209 210int main(int argc, char **argv) 211{ 212 int i; 213 void *k; 214 AVTreeNode *root = NULL, *node = NULL; 215 AVLFG prng; 216 int log_level = argc <= 1 ? AV_LOG_INFO : atoi(argv[1]); 217 218 av_log_set_level(log_level); 219 220 av_lfg_init(&prng, 1); 221 222 for (i = 0; i < 10000; i++) { 223 intptr_t j = av_lfg_get(&prng) % 86294; 224 225 if (check(root) > 999) { 226 av_log(NULL, AV_LOG_ERROR, "FATAL error %d\n", i); 227 print(root, 0); 228 return 1; 229 } 230 av_log(NULL, AV_LOG_DEBUG, "inserting %4d\n", (int)j); 231 232 if (!node) 233 node = av_tree_node_alloc(); 234 if (!node) { 235 av_log(NULL, AV_LOG_ERROR, "Memory allocation failure.\n"); 236 return 1; 237 } 238 av_tree_insert(&root, (void *)(j + 1), cmp, &node); 239 240 j = av_lfg_get(&prng) % 86294; 241 { 242 AVTreeNode *node2 = NULL; 243 av_log(NULL, AV_LOG_DEBUG, "removing %4d\n", (int)j); 244 av_tree_insert(&root, (void *)(j + 1), cmp, &node2); 245 k = av_tree_find(root, (void *)(j + 1), cmp, NULL); 246 if (k) 247 av_log(NULL, AV_LOG_ERROR, "removal failure %d\n", i); 248 av_free(node2); 249 } 250 } 251 av_free(node); 252 253 av_tree_destroy(root); 254 255 return 0; 256} 257#endif 258