ffmpeg / libavutil / tree.c @ 08675bb3
History  View  Annotate  Download (6.53 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 "log.h" 
22 
#include "tree.h" 
23  
24 
typedef struct AVTreeNode{ 
25 
struct AVTreeNode *child[2]; 
26 
void *elem;

27 
int state;

28 
}AVTreeNode; 
29  
30 
const int av_tree_node_size = sizeof(AVTreeNode); 
31  
32 
void *av_tree_find(const AVTreeNode *t, void *key, int (*cmp)(void *key, const void *b), void *next[2]){ 
33 
if(t){

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

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

39 
if(next){

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

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

42 
} 
43 
return t>elem;

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

52 
unsigned int v= cmp(t>elem, key); 
53 
void *ret;

54 
if(!v){

55 
if(*next)

56 
return t>elem;

57 
else if(t>child[0]t>child[1]){ 
58 
int i= !t>child[0]; 
59 
void *next_elem[2]; 
60 
av_tree_find(t>child[i], key, cmp, next_elem); 
61 
key= t>elem= next_elem[i]; 
62 
v= i; 
63 
}else{

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

66 
return NULL; 
67 
} 
68 
} 
69 
ret= av_tree_insert(&t>child[v>>31], key, cmp, next);

70 
if(!ret){

71 
int i= (v>>31) ^ !!*next; 
72 
AVTreeNode **child= &t>child[i]; 
73 
t>state += 2*i  1; 
74  
75 
if(!(t>state&1)){ 
76 
if(t>state){

77 
/* The following code is equivalent to

78 
if((*child)>state*2 == t>state)

79 
rotate(child, i^1);

80 
rotate(tp, i);

81 

82 
with rotate():

83 
static void rotate(AVTreeNode **tp, int i){

84 
AVTreeNode *t= *tp;

85 

86 
*tp= t>child[i];

87 
t>child[i]= t>child[i]>child[i^1];

88 
(*tp)>child[i^1]= t;

89 
i= 4*t>state + 2*(*tp)>state + 12;

90 
t >state= ((0x614586 >> i) & 3)1;

91 
(*tp)>state= ((*tp)>state>>1) + ((0x400EEA >> i) & 3)1;

92 
}

93 
but such a rotate function is both bigger and slower

94 
*/

95 
if((*child)>state*2 == t>state){ 
96 
*tp= (*child)>child[i^1];

97 
(*child)>child[i^1]= (*tp)>child[i];

98 
(*tp)>child[i]= *child; 
99 
*child= (*tp)>child[i^1];

100 
(*tp)>child[i^1]= t;

101  
102 
(*tp)>child[0]>state= ((*tp)>state>0); 
103 
(*tp)>child[1]>state= (*tp)>state<0 ; 
104 
(*tp)>state=0;

105 
}else{

106 
*tp= *child; 
107 
*child= (*child)>child[i^1];

108 
(*tp)>child[i^1]= t;

109 
if((*tp)>state) t>state = 0; 
110 
else t>state>>= 1; 
111 
(*tp)>state= t>state; 
112 
} 
113 
} 
114 
} 
115 
if(!(*tp)>state ^ !!*next)

116 
return key;

117 
} 
118 
return ret;

119 
}else{

120 
*tp= *next; *next= NULL;

121 
if(*tp){

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

125 
return key;

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

130 
if(t){

131 
av_tree_destroy(t>child[0]);

132 
av_tree_destroy(t>child[1]);

133 
av_free(t); 
134 
} 
135 
} 
136  
137 
void av_tree_enumerate(AVTreeNode *t, void *opaque, int (*cmp)(void *opaque, void *elem), int (*enu)(void *opaque, void *elem)){ 
138 
if(t){

139 
int v= cmp ? cmp(opaque, t>elem) : 0; 
140 
if(v>=0) av_tree_enumerate(t>child[0], opaque, cmp, enu); 
141 
if(v==0) enu(opaque, t>elem); 
142 
if(v<=0) av_tree_enumerate(t>child[1], opaque, cmp, enu); 
143 
} 
144 
} 
145  
146 
#ifdef TEST

147  
148 
#include "lfg.h" 
149  
150 
static int check(AVTreeNode *t){ 
151 
if(t){

152 
int left= check(t>child[0]); 
153 
int right= check(t>child[1]); 
154  
155 
if(left>999  right>999) 
156 
return 1000; 
157 
if(right  left != t>state)

158 
return 1000; 
159 
if(t>state>1  t>state<1) 
160 
return 1000; 
161 
return FFMAX(left, right)+1; 
162 
} 
163 
return 0; 
164 
} 
165  
166 
static void print(AVTreeNode *t, int depth){ 
167 
int i;

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

170 
av_log(NULL, AV_LOG_ERROR, "Node %p %2d %p\n", t, t>state, t>elem); 
171 
print(t>child[0], depth+1); 
172 
print(t>child[1], depth+1); 
173 
}else

174 
av_log(NULL, AV_LOG_ERROR, "NULL\n"); 
175 
} 
176  
177 
static int cmp(void *a, const void *b){ 
178 
return (uint8_t*)a(const uint8_t*)b; 
179 
} 
180  
181 
int main(void){ 
182 
int i;

183 
void *k;

184 
AVTreeNode *root= NULL, *node=NULL; 
185 
AVLFG prng; 
186  
187 
av_lfg_init(&prng, 1);

188  
189 
for(i=0; i<10000; i++){ 
190 
int j = av_lfg_get(&prng) % 86294; 
191 
if(check(root) > 999){ 
192 
av_log(NULL, AV_LOG_ERROR, "FATAL error %d\n", i); 
193 
print(root, 0);

194 
return 1; 
195 
} 
196 
av_log(NULL, AV_LOG_ERROR, "inserting %4d\n", j); 
197 
if(!node)

198 
node= av_mallocz(av_tree_node_size); 
199 
av_tree_insert(&root, (void*)(j+1), cmp, &node); 
200  
201 
j = av_lfg_get(&prng) % 86294;

202 
{ 
203 
AVTreeNode *node2=NULL;

204 
av_log(NULL, AV_LOG_ERROR, "removing %4d\n", j); 
205 
av_tree_insert(&root, (void*)(j+1), cmp, &node2); 
206 
k= av_tree_find(root, (void*)(j+1), cmp, NULL); 
207 
if(k)

208 
av_log(NULL, AV_LOG_ERROR, "removal failure %d\n", i); 
209 
} 
210 
} 
211 
return 0; 
212 
} 
213 
#endif
