## ffmpeg / libavutil / tree.c @ d71ad089

History | View | Annotate | Download (6.43 KB)

1 | 9eb88fde | Michael Niedermayer | ```
/*
``` |
---|---|---|---|

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

31 | 6e8b982b | Michael Niedermayer | const int av_tree_node_size = sizeof(AVTreeNode); |

32 | |||

33 | 9eb88fde | Michael Niedermayer | void *av_tree_find(const AVTreeNode *t, void *key, int (*cmp)(void *key, const void *b), void *next[2]){ |

34 | ```
if(t){
``` |
||

35 | 2e1d2873 | Michael Niedermayer | unsigned int v= cmp(key, t->elem); |

36 | 9eb88fde | Michael Niedermayer | ```
if(v){
``` |

37 | 2e1d2873 | Michael Niedermayer | if(next) next[v>>31]= t->elem; |

38 | return av_tree_find(t->child[(v>>31)^1], key, cmp, next); |
||

39 | 9eb88fde | Michael Niedermayer | ```
}else{
``` |

40 | 116d15cc | Michael Niedermayer | ```
if(next){
``` |

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

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

43 | } |
||

44 | 9eb88fde | Michael Niedermayer | ```
return t->elem;
``` |

45 | } |
||

46 | } |
||

47 | return NULL; |
||

48 | } |
||

49 | |||

50 | 6e8b982b | Michael Niedermayer | void *av_tree_insert(AVTreeNode **tp, void *key, int (*cmp)(void *key, const void *b), AVTreeNode **next){ |

51 | 9eb88fde | Michael Niedermayer | AVTreeNode *t= *tp; |

52 | ```
if(t){
``` |
||

53 | unsigned int v= cmp(t->elem, key); |
||

54 | f05dda3b | Michael Niedermayer | ```
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 | 3f161c7e | Michael Niedermayer | av_tree_find(t->child[i], key, cmp, next_elem); |

62 | f05dda3b | Michael Niedermayer | key= t->elem= next_elem[i]; |

63 | v= -i; |
||

64 | ```
}else{
``` |
||

65 | *next= t; |
||

66 | ```
*tp=NULL;
``` |
||

67 | return NULL; |
||

68 | } |
||

69 | } |
||

70 | a35bf971 | Michael Niedermayer | ```
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 | f05dda3b | Michael Niedermayer | |

76 | a35bf971 | Michael Niedermayer | if(!(t->state&1)){ |

77 | ```
if(t->state){
``` |
||

78 | 51198a87 | Michael Niedermayer | ```
/* 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 | a35bf971 | Michael Niedermayer | 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 | 9eb88fde | Michael Niedermayer | |

103 | a35bf971 | Michael Niedermayer | (*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 | 9eb88fde | Michael Niedermayer | } |

114 | } |
||

115 | } |
||

116 | a35bf971 | Michael Niedermayer | ```
if(!(*tp)->state ^ !!*next)
``` |

117 | ```
return key;
``` |
||

118 | } |
||

119 | ```
return ret;
``` |
||

120 | 9eb88fde | Michael Niedermayer | ```
}else{
``` |

121 | 6e8b982b | Michael Niedermayer | ```
*tp= *next; *next= NULL;
``` |

122 | eed36075 | Michael Niedermayer | ```
if(*tp){
``` |

123 | (*tp)->elem= key; |
||

124 | return NULL; |
||

125 | ```
}else
``` |
||

126 | ```
return key;
``` |
||

127 | 9eb88fde | Michael Niedermayer | } |

128 | } |
||

129 | |||

130 | ```
void av_tree_destroy(AVTreeNode *t){
``` |
||

131 | d8bd113e | Aurelien Jacobs | ```
if(t){
``` |

132 | 045cbba9 | Aurelien Jacobs | ```
av_tree_destroy(t->child[0]);
``` |

133 | ```
av_tree_destroy(t->child[1]);
``` |
||

134 | av_free(t); |
||

135 | d8bd113e | Aurelien Jacobs | } |

136 | 9eb88fde | Michael Niedermayer | } |

137 | |||

138 | ```
#if 0
``` |
||

139 | ```
void av_tree_enumerate(AVTreeNode *t, void *opaque, int (*f)(void *opaque, void *elem)){
``` |
||

140 | 33206876 | Michael Niedermayer | ```
int v= f(opaque, t->elem);
``` |

141 | ```
if(v>=0) av_tree_enumerate(t->child[0], opaque, f);
``` |
||

142 | ```
if(v<=0) av_tree_enumerate(t->child[1], opaque, f);
``` |
||

143 | 9eb88fde | Michael Niedermayer | ```
}
``` |

144 | ```
#endif
``` |
||

145 | |||

146 | ```
#ifdef TEST
``` |
||

147 | 294eaa26 | Diego Biurrun | |

148 | #include "lfg.h" |
||

149 | |||

150 | 9eb88fde | Michael Niedermayer | 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 | 168fffdf | Benoit Fouet | av_log(NULL, AV_LOG_ERROR, "Node %p %2d %p\n", t, t->state, t->elem); |

171 | 9eb88fde | Michael Niedermayer | 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 | 168fffdf | Benoit Fouet | static int cmp(void *a, const void *b){ |

178 | return (uint8_t*)a-(const uint8_t*)b; |
||

179 | 9eb88fde | Michael Niedermayer | } |

180 | |||

181 | f8a80fd6 | Diego Biurrun | int main(void){ |

182 | 168fffdf | Benoit Fouet | ```
int i;
``` |

183 | ```
void *k;
``` |
||

184 | f05dda3b | Michael Niedermayer | AVTreeNode *root= NULL, *node=NULL; |

185 | 64bde197 | Diego Biurrun | AVLFG prng; |

186 | 294eaa26 | Diego Biurrun | |

187 | 64bde197 | Diego Biurrun | ```
av_lfg_init(&prng, 1);
``` |

188 | 9eb88fde | Michael Niedermayer | |

189 | for(i=0; i<10000; i++){ |
||

190 | 64bde197 | Diego Biurrun | int j = av_lfg_get(&prng) % 86294; |

191 | 9eb88fde | Michael Niedermayer | 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 | f05dda3b | Michael Niedermayer | ```
if(!node)
``` |

198 | node= av_mallocz(av_tree_node_size); |
||

199 | av_tree_insert(&root, (void*)(j+1), cmp, &node); |
||

200 | |||

201 | 64bde197 | Diego Biurrun | ```
j = av_lfg_get(&prng) % 86294;
``` |

202 | eed36075 | Michael Niedermayer | { |

203 | f05dda3b | Michael Niedermayer | ```
AVTreeNode *node2=NULL;
``` |

204 | 5d1e3d22 | Michael Niedermayer | av_log(NULL, AV_LOG_ERROR, "removing %4d\n", j); |

205 | f05dda3b | Michael Niedermayer | av_tree_insert(&root, (void*)(j+1), cmp, &node2); |

206 | k= av_tree_find(root, (void*)(j+1), cmp, NULL); |
||

207 | ```
if(k)
``` |
||

208 | 89c9ff50 | Diego Biurrun | av_log(NULL, AV_LOG_ERROR, "removal failure %d\n", i); |

209 | f05dda3b | Michael Niedermayer | } |

210 | 9eb88fde | Michael Niedermayer | } |

211 | return 0; |
||

212 | } |
||

213 | `#endif` |