Commit | Line | Data |
---|---|---|
2ba45a60 DM |
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 |