Mercurial > libavutil.hg
annotate tree.c @ 510:b7593ce78422 libavutil
Make av_fifo*_read() ignore the available amount of data.
This is more efficient as in practice the check is redundant most of the
time. Callers which do not know if enough data is available have to check
it with av_fifo_size(). Doing the check in *read() means the caller has
no choice to skip the check when its known to be redundant.
Also the return value was never documented in a public header so
changing it should not break the API. Besides this fixes the case where
read() failed on a 100% full fifo.
author | michael |
---|---|
date | Sun, 25 May 2008 22:20:39 +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 |