| 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 | |
| 26 | typedef struct AVTreeNode { |
| 27 | struct AVTreeNode *child[2]; |
| 28 | void *elem; |
| 29 | int state; |
| 30 | } AVTreeNode; |
| 31 | |
| 32 | const int av_tree_node_size = sizeof(AVTreeNode); |
| 33 | |
| 34 | struct AVTreeNode *av_tree_node_alloc(void) |
| 35 | { |
| 36 | return av_mallocz(sizeof(struct AVTreeNode)); |
| 37 | } |
| 38 | |
| 39 | void *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 | |
| 59 | void *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 | |
| 146 | void 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 | |
| 155 | void 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 | |
| 175 | static 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 | |
| 192 | static 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 | |
| 205 | static int cmp(void *a, const void *b) |
| 206 | { |
| 207 | return (uint8_t *) a - (const uint8_t *) b; |
| 208 | } |
| 209 | |
| 210 | int 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 |