ffmpeg / libavutil / tree.c @ fee6faa2
History  View  Annotate  Download (6.76 KB)
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 021101301 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  
31 
const int av_tree_node_size = sizeof(AVTreeNode); 
32  
33 
void *av_tree_find(const AVTreeNode *t, void *key, int (*cmp)(void *key, const void *b), void *next[2]){ 
34 
if(t){

35 
unsigned int v= cmp(key, t>elem); 
36 
if(v){

37 
if(next) next[v>>31]= t>elem; 
38 
return av_tree_find(t>child[(v>>31)^1], key, cmp, next); 
39 
}else{

40 
if(next){

41 
av_tree_find(t>child[0], key, cmp, next);

42 
av_tree_find(t>child[1], key, cmp, next);

43 
} 
44 
return t>elem;

45 
} 
46 
} 
47 
return NULL; 
48 
} 
49  
50 
void *av_tree_insert(AVTreeNode **tp, void *key, int (*cmp)(void *key, const void *b), AVTreeNode **next){ 
51 
AVTreeNode *t= *tp; 
52 
if(t){

53 
unsigned int v= cmp(t>elem, key); 
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]; 
61 
av_tree_find(t>child[i], key, cmp, next_elem); 
62 
key= t>elem= next_elem[i]; 
63 
v= i; 
64 
}else{

65 
*next= t; 
66 
*tp=NULL;

67 
return NULL; 
68 
} 
69 
} 
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; 
75  
76 
if(!(t>state&1)){ 
77 
if(t>state){

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 
*/

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;

102  
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; 
113 
} 
114 
} 
115 
} 
116 
if(!(*tp)>state ^ !!*next)

117 
return key;

118 
} 
119 
return ret;

120 
}else{

121 
*tp= *next; *next= NULL;

122 
if(*tp){

123 
(*tp)>elem= key; 
124 
return NULL; 
125 
}else

126 
return key;

127 
} 
128 
} 
129  
130 
void av_tree_destroy(AVTreeNode *t){

131 
if(t){

132 
av_tree_destroy(t>child[0]);

133 
av_tree_destroy(t>child[1]);

134 
av_free(t); 
135 
} 
136 
} 
137  
138 
void av_tree_destroy_free_elem(AVTreeNode *t){

139 
if(t){

140 
av_tree_destroy_free_elem(t>child[0]);

141 
av_tree_destroy_free_elem(t>child[1]);

142 
av_free(t>elem); 
143 
av_free(t); 
144 
} 
145 
} 
146  
147 
#if 0

148 
void av_tree_enumerate(AVTreeNode *t, void *opaque, int (*cmp)(void *opaque, void *elem), int (*enu)(void *opaque, void *elem)){

149 
if(t){

150 
int v= cmp ? cmp(opaque, t>elem) : 0;

151 
if(v>=0) av_tree_enumerate(t>child[0], opaque, cmp, enu);

152 
if(v==0) enu(opaque, t>elem);

153 
if(v<=0) av_tree_enumerate(t>child[1], opaque, cmp, enu);

154 
}

155 
}

156 
#endif

157  
158 
#ifdef TEST

159  
160 
#include "lfg.h" 
161  
162 
static int check(AVTreeNode *t){ 
163 
if(t){

164 
int left= check(t>child[0]); 
165 
int right= check(t>child[1]); 
166  
167 
if(left>999  right>999) 
168 
return 1000; 
169 
if(right  left != t>state)

170 
return 1000; 
171 
if(t>state>1  t>state<1) 
172 
return 1000; 
173 
return FFMAX(left, right)+1; 
174 
} 
175 
return 0; 
176 
} 
177  
178 
static void print(AVTreeNode *t, int depth){ 
179 
int i;

180 
for(i=0; i<depth*4; i++) av_log(NULL, AV_LOG_ERROR, " "); 
181 
if(t){

182 
av_log(NULL, AV_LOG_ERROR, "Node %p %2d %p\n", t, t>state, t>elem); 
183 
print(t>child[0], depth+1); 
184 
print(t>child[1], depth+1); 
185 
}else

186 
av_log(NULL, AV_LOG_ERROR, "NULL\n"); 
187 
} 
188  
189 
static int cmp(void *a, const void *b){ 
190 
return (uint8_t*)a(const uint8_t*)b; 
191 
} 
192  
193 
int main(void){ 
194 
int i;

195 
void *k;

196 
AVTreeNode *root= NULL, *node=NULL; 
197 
AVLFG prng; 
198  
199 
av_lfg_init(&prng, 1);

200  
201 
for(i=0; i<10000; i++){ 
202 
int j = av_lfg_get(&prng) % 86294; 
203 
if(check(root) > 999){ 
204 
av_log(NULL, AV_LOG_ERROR, "FATAL error %d\n", i); 
205 
print(root, 0);

206 
return 1; 
207 
} 
208 
av_log(NULL, AV_LOG_ERROR, "inserting %4d\n", j); 
209 
if(!node)

210 
node= av_mallocz(av_tree_node_size); 
211 
av_tree_insert(&root, (void*)(j+1), cmp, &node); 
212  
213 
j = av_lfg_get(&prng) % 86294;

214 
{ 
215 
AVTreeNode *node2=NULL;

216 
av_log(NULL, AV_LOG_ERROR, "removing %4d\n", j); 
217 
av_tree_insert(&root, (void*)(j+1), cmp, &node2); 
218 
k= av_tree_find(root, (void*)(j+1), cmp, NULL); 
219 
if(k)

220 
av_log(NULL, AV_LOG_ERROR, "removal failure %d\n", i); 
221 
} 
222 
} 
223 
return 0; 
224 
} 
225 
#endif
