Mercurial > libavutil.hg
annotate tree.c @ 483:c6cd6e70780b libavutil
'malloc' attribute isn't supported in old gcc.
author | zuxy |
---|---|
date | Wed, 19 Mar 2008 07:42:50 +0000 |
parents | 0839746f3fcf |
children | 5877edf05eb7 |
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){ | |
433 | 78 /* The following code is equivalent to |
79 if((*child)->state*2 == -t->state) | |
80 rotate(child, i^1); | |
81 rotate(tp, i); | |
82 | |
83 with rotate(): | |
84 static void rotate(AVTreeNode **tp, int i){ | |
85 AVTreeNode *t= *tp; | |
86 | |
87 *tp= t->child[i]; | |
88 t->child[i]= t->child[i]->child[i^1]; | |
89 (*tp)->child[i^1]= t; | |
90 i= 4*t->state + 2*(*tp)->state + 12; | |
91 t ->state= ((0x614586 >> i) & 3)-1; | |
92 (*tp)->state= ((*tp)->state>>1) + ((0x400EEA >> i) & 3)-1; | |
93 } | |
94 but such a rotate function is both bigger and slower | |
95 */ | |
419 | 96 if((*child)->state*2 == -t->state){ |
97 *tp= (*child)->child[i^1]; | |
98 (*child)->child[i^1]= (*tp)->child[i]; | |
99 (*tp)->child[i]= *child; | |
100 *child= (*tp)->child[i^1]; | |
101 (*tp)->child[i^1]= t; | |
136 | 102 |
419 | 103 (*tp)->child[0]->state= -((*tp)->state>0); |
104 (*tp)->child[1]->state= (*tp)->state<0 ; | |
105 (*tp)->state=0; | |
106 }else{ | |
107 *tp= *child; | |
108 *child= (*child)->child[i^1]; | |
109 (*tp)->child[i^1]= t; | |
110 if((*tp)->state) t->state = 0; | |
111 else t->state>>= 1; | |
112 (*tp)->state= -t->state; | |
136 | 113 } |
414 | 114 } |
136 | 115 } |
419 | 116 if(!(*tp)->state ^ !!*next) |
117 return key; | |
118 } | |
119 return ret; | |
136 | 120 }else{ |
413
a54e20281de9
Move *malloc() out of tree.c, that way the code can be used with
michael
parents:
412
diff
changeset
|
121 *tp= *next; *next= NULL; |
136 | 122 (*tp)->elem= key; |
123 return NULL; | |
124 } | |
125 } | |
126 | |
127 void av_tree_destroy(AVTreeNode *t){ | |
128 av_tree_destroy(t->child[0]); | |
129 av_tree_destroy(t->child[1]); | |
130 av_free(t); | |
131 } | |
132 | |
133 #if 0 | |
134 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
|
135 int v= f(opaque, t->elem); |
dbcf66639764
improve enumerate so arbitrary ranges can be enumerated quickly
michael
parents:
136
diff
changeset
|
136 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
|
137 if(v<=0) av_tree_enumerate(t->child[1], opaque, f); |
136 | 138 } |
139 #endif | |
140 | |
141 #ifdef TEST | |
415 | 142 #undef random |
136 | 143 static int check(AVTreeNode *t){ |
144 if(t){ | |
145 int left= check(t->child[0]); | |
146 int right= check(t->child[1]); | |
147 | |
148 if(left>999 || right>999) | |
149 return 1000; | |
150 if(right - left != t->state) | |
151 return 1000; | |
152 if(t->state>1 || t->state<-1) | |
153 return 1000; | |
154 return FFMAX(left, right)+1; | |
155 } | |
156 return 0; | |
157 } | |
158 | |
159 static void print(AVTreeNode *t, int depth){ | |
160 int i; | |
161 for(i=0; i<depth*4; i++) av_log(NULL, AV_LOG_ERROR, " "); | |
162 if(t){ | |
163 av_log(NULL, AV_LOG_ERROR, "Node %p %2d %4d\n", t, t->state, t->elem); | |
164 print(t->child[0], depth+1); | |
165 print(t->child[1], depth+1); | |
166 }else | |
167 av_log(NULL, AV_LOG_ERROR, "NULL\n"); | |
168 } | |
169 | |
170 int cmp(const void *a, const void *b){ | |
171 return a-b; | |
172 } | |
173 | |
404 | 174 int main(void){ |
425 | 175 int i,k; |
414 | 176 AVTreeNode *root= NULL, *node=NULL; |
136 | 177 |
178 for(i=0; i<10000; i++){ | |
414 | 179 int j= (random()%86294); |
136 | 180 if(check(root) > 999){ |
181 av_log(NULL, AV_LOG_ERROR, "FATAL error %d\n", i); | |
182 print(root, 0); | |
183 return -1; | |
184 } | |
185 av_log(NULL, AV_LOG_ERROR, "inserting %4d\n", j); | |
414 | 186 if(!node) |
187 node= av_mallocz(av_tree_node_size); | |
188 av_tree_insert(&root, (void*)(j+1), cmp, &node); | |
189 | |
190 j= (random()%86294); | |
191 k= av_tree_find(root, (void*)(j+1), cmp, NULL); | |
192 if(k){ | |
193 AVTreeNode *node2=NULL; | |
430 | 194 av_log(NULL, AV_LOG_ERROR, "removing %4d\n", j); |
414 | 195 av_tree_insert(&root, (void*)(j+1), cmp, &node2); |
196 k= av_tree_find(root, (void*)(j+1), cmp, NULL); | |
197 if(k) | |
198 av_log(NULL, AV_LOG_ERROR, "removial failure %d\n", i); | |
199 } | |
136 | 200 } |
201 return 0; | |
202 } | |
203 #endif |