Mercurial > libavutil.hg
annotate tree.c @ 429:3be382cb92ba libavutil
simplify
author | michael |
---|---|
date | Wed, 16 Jan 2008 01:54:18 +0000 |
parents | 344948d71978 |
children | 42011b593830 |
rev | line source |
---|---|
136 | 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 "common.h" | |
22 #include "log.h" | |
23 #include "tree.h" | |
24 | |
25 typedef struct AVTreeNode{ | |
26 struct AVTreeNode *child[2]; | |
27 void *elem; | |
28 int state; | |
29 }AVTreeNode; | |
30 | |
413
a54e20281de9
Move *malloc() out of tree.c, that way the code can be used with
michael
parents:
412
diff
changeset
|
31 const int av_tree_node_size = sizeof(AVTreeNode); |
a54e20281de9
Move *malloc() out of tree.c, that way the code can be used with
michael
parents:
412
diff
changeset
|
32 |
136 | 33 void *av_tree_find(const AVTreeNode *t, void *key, int (*cmp)(void *key, const void *b), void *next[2]){ |
34 if(t){ | |
418
9f2461caf179
Flip key and element so types match, not that it matters for any code
michael
parents:
415
diff
changeset
|
35 unsigned int v= cmp(key, t->elem); |
136 | 36 if(v){ |
418
9f2461caf179
Flip key and element so types match, not that it matters for any code
michael
parents:
415
diff
changeset
|
37 if(next) next[v>>31]= t->elem; |
9f2461caf179
Flip key and element so types match, not that it matters for any code
michael
parents:
415
diff
changeset
|
38 return av_tree_find(t->child[(v>>31)^1], key, cmp, next); |
136 | 39 }else{ |
412
357ac44f4720
Always set next correctly, even if a matching element is found (that is
michael
parents:
404
diff
changeset
|
40 if(next){ |
357ac44f4720
Always set next correctly, even if a matching element is found (that is
michael
parents:
404
diff
changeset
|
41 av_tree_find(t->child[0], key, cmp, next); |
357ac44f4720
Always set next correctly, even if a matching element is found (that is
michael
parents:
404
diff
changeset
|
42 av_tree_find(t->child[1], key, cmp, next); |
357ac44f4720
Always set next correctly, even if a matching element is found (that is
michael
parents:
404
diff
changeset
|
43 } |
136 | 44 return t->elem; |
45 } | |
46 } | |
47 return NULL; | |
48 } | |
49 | |
413
a54e20281de9
Move *malloc() out of tree.c, that way the code can be used with
michael
parents:
412
diff
changeset
|
50 void *av_tree_insert(AVTreeNode **tp, void *key, int (*cmp)(void *key, const void *b), AVTreeNode **next){ |
136 | 51 AVTreeNode *t= *tp; |
52 if(t){ | |
53 unsigned int v= cmp(t->elem, key); | |
414 | 54 void *ret; |
55 if(!v){ | |
56 if(*next) | |
57 return t->elem; | |
58 else if(t->child[0]||t->child[1]){ | |
59 int i= !t->child[0]; | |
60 void *next_elem[2]; | |
429 | 61 av_tree_find(t->child[i], key, cmp, next_elem); |
414 | 62 key= t->elem= next_elem[i]; |
63 v= -i; | |
64 }else{ | |
65 *next= t; | |
66 *tp=NULL; | |
67 return NULL; | |
68 } | |
69 } | |
419 | 70 ret= av_tree_insert(&t->child[v>>31], key, cmp, next); |
71 if(!ret){ | |
72 int i= (v>>31) ^ !!*next; | |
73 AVTreeNode **child= &t->child[i]; | |
74 t->state += 2*i - 1; | |
414 | 75 |
419 | 76 if(!(t->state&1)){ |
77 if(t->state){ | |
78 if((*child)->state*2 == -t->state){ | |
79 *tp= (*child)->child[i^1]; | |
80 (*child)->child[i^1]= (*tp)->child[i]; | |
81 (*tp)->child[i]= *child; | |
82 *child= (*tp)->child[i^1]; | |
83 (*tp)->child[i^1]= t; | |
136 | 84 |
419 | 85 (*tp)->child[0]->state= -((*tp)->state>0); |
86 (*tp)->child[1]->state= (*tp)->state<0 ; | |
87 (*tp)->state=0; | |
88 }else{ | |
89 *tp= *child; | |
90 *child= (*child)->child[i^1]; | |
91 (*tp)->child[i^1]= t; | |
92 if((*tp)->state) t->state = 0; | |
93 else t->state>>= 1; | |
94 (*tp)->state= -t->state; | |
136 | 95 } |
414 | 96 } |
136 | 97 } |
419 | 98 if(!(*tp)->state ^ !!*next) |
99 return key; | |
100 } | |
101 return ret; | |
136 | 102 }else{ |
413
a54e20281de9
Move *malloc() out of tree.c, that way the code can be used with
michael
parents:
412
diff
changeset
|
103 *tp= *next; *next= NULL; |
136 | 104 (*tp)->elem= key; |
105 return NULL; | |
106 } | |
107 } | |
108 | |
109 void av_tree_destroy(AVTreeNode *t){ | |
110 av_tree_destroy(t->child[0]); | |
111 av_tree_destroy(t->child[1]); | |
112 av_free(t); | |
113 } | |
114 | |
115 #if 0 | |
116 void av_tree_enumerate(AVTreeNode *t, void *opaque, int (*f)(void *opaque, void *elem)){ | |
137
dbcf66639764
improve enumerate so arbitrary ranges can be enumerated quickly
michael
parents:
136
diff
changeset
|
117 int v= f(opaque, t->elem); |
dbcf66639764
improve enumerate so arbitrary ranges can be enumerated quickly
michael
parents:
136
diff
changeset
|
118 if(v>=0) av_tree_enumerate(t->child[0], opaque, f); |
dbcf66639764
improve enumerate so arbitrary ranges can be enumerated quickly
michael
parents:
136
diff
changeset
|
119 if(v<=0) av_tree_enumerate(t->child[1], opaque, f); |
136 | 120 } |
121 #endif | |
122 | |
123 #ifdef TEST | |
415 | 124 #undef random |
136 | 125 static int check(AVTreeNode *t){ |
126 if(t){ | |
127 int left= check(t->child[0]); | |
128 int right= check(t->child[1]); | |
129 | |
130 if(left>999 || right>999) | |
131 return 1000; | |
132 if(right - left != t->state) | |
133 return 1000; | |
134 if(t->state>1 || t->state<-1) | |
135 return 1000; | |
136 return FFMAX(left, right)+1; | |
137 } | |
138 return 0; | |
139 } | |
140 | |
141 static void print(AVTreeNode *t, int depth){ | |
142 int i; | |
143 for(i=0; i<depth*4; i++) av_log(NULL, AV_LOG_ERROR, " "); | |
144 if(t){ | |
145 av_log(NULL, AV_LOG_ERROR, "Node %p %2d %4d\n", t, t->state, t->elem); | |
146 print(t->child[0], depth+1); | |
147 print(t->child[1], depth+1); | |
148 }else | |
149 av_log(NULL, AV_LOG_ERROR, "NULL\n"); | |
150 } | |
151 | |
152 int cmp(const void *a, const void *b){ | |
153 return a-b; | |
154 } | |
155 | |
404 | 156 int main(void){ |
425 | 157 int i,k; |
414 | 158 AVTreeNode *root= NULL, *node=NULL; |
136 | 159 |
160 for(i=0; i<10000; i++){ | |
414 | 161 int j= (random()%86294); |
136 | 162 if(check(root) > 999){ |
163 av_log(NULL, AV_LOG_ERROR, "FATAL error %d\n", i); | |
164 print(root, 0); | |
165 return -1; | |
166 } | |
167 av_log(NULL, AV_LOG_ERROR, "inserting %4d\n", j); | |
414 | 168 if(!node) |
169 node= av_mallocz(av_tree_node_size); | |
170 av_tree_insert(&root, (void*)(j+1), cmp, &node); | |
171 | |
172 j= (random()%86294); | |
173 k= av_tree_find(root, (void*)(j+1), cmp, NULL); | |
174 if(k){ | |
175 AVTreeNode *node2=NULL; | |
176 av_tree_insert(&root, (void*)(j+1), cmp, &node2); | |
177 k= av_tree_find(root, (void*)(j+1), cmp, NULL); | |
178 if(k) | |
179 av_log(NULL, AV_LOG_ERROR, "removial failure %d\n", i); | |
180 } | |
136 | 181 } |
182 return 0; | |
183 } | |
184 #endif |