## ffmpeg / libavutil / tree.c @ a5b13b14

History | View | Annotate | Download (6.53 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 "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 | 6e8b982b | Michael Niedermayer | const int av_tree_node_size = sizeof(AVTreeNode); |

31 | |||

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

33 | ```
if(t){
``` |
||

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

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

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

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

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

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

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

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

42 | } |
||

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

44 | } |
||

45 | } |
||

46 | return NULL; |
||

47 | } |
||

48 | |||

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

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

51 | ```
if(t){
``` |
||

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

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

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

62 | v= -i; |
||

63 | ```
}else{
``` |
||

64 | *next= t; |
||

65 | ```
*tp=NULL;
``` |
||

66 | return NULL; |
||

67 | } |
||

68 | } |
||

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

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

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

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

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

113 | } |
||

114 | } |
||

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

116 | ```
return key;
``` |
||

117 | } |
||

118 | ```
return ret;
``` |
||

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

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

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

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

123 | return NULL; |
||

124 | ```
}else
``` |
||

125 | ```
return key;
``` |
||

126 | 9eb88fde | Michael Niedermayer | } |

127 | } |
||

128 | |||

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

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

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

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

133 | av_free(t); |
||

134 | d8bd113e | Aurelien Jacobs | } |

135 | 9eb88fde | Michael Niedermayer | } |

136 | |||

137 | 1bf83b95 | Michael Niedermayer | void av_tree_enumerate(AVTreeNode *t, void *opaque, int (*cmp)(void *opaque, void *elem), int (*enu)(void *opaque, void *elem)){ |

138 | edabf359 | Michael Niedermayer | ```
if(t){
``` |

139 | b154ed5a | Michael Niedermayer | 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 | edabf359 | Michael Niedermayer | } |

144 | 9eb88fde | Michael Niedermayer | } |

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