FFmpeg: libavutil/tree.c Source File

FFmpeg

[フレーム]

libavutil

tree.c

Go to the documentation of this file.

1 /*

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

21 #include "error.h"

22 #include "log.h"

23 #include "mem.h"

24 #include "tree.h"

26 typedef struct AVTreeNode {

27 struct AVTreeNode *child[2];

28 void *elem;

29 int state;

30 } AVTreeNode;

32 const int av_tree_node_size = sizeof(AVTreeNode);

34 struct AVTreeNode *av_tree_node_alloc(void)

35 {

36 return av_mallocz(sizeof(struct AVTreeNode));

37 }

39 void *av_tree_find(const AVTreeNode *t, void *key,

40 int (*cmp)(void *key, const void *b), void *next[2])

41 {

42 if (t) {

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

44 if (v) {

45 if (next)

46 next[v >> 31] = t->elem;

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

48 } else {

49 if (next) {

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

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

52 }

53 return t->elem;

54 }

55 }

56 return NULL;

57 }

59 void *av_tree_insert(AVTreeNode **tp, void *key,

60 int (*cmp)(void *key, const void *b), AVTreeNode **next)

61 {

62 AVTreeNode *t = *tp;

63 if (t) {

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

65 void *ret;

66 if (!v) {

67 if (*next)

68 return t->elem;

69 else if (t->child[0] || t->child[1]) {

70 int i = !t->child[0];

71 void *next_elem[2];

72 av_tree_find(t->child[i], key, cmp, next_elem);

73 key = t->elem = next_elem[i];

74 v = -i;

75 } else {

76 *next = t;

77 *tp = NULL;

78 return NULL;

79 }

80 }

81 ret = av_tree_insert(&t->child[v >> 31], key, cmp, next);

82 if (!ret) {

83 int i = (v >> 31) ^ !!*next;

84 AVTreeNode **child = &t->child[i];

85 t->state += 2 * i - 1;

87 if (!(t->state & 1)) {

88 if (t->state) {

89 /* The following code is equivalent to

90 * if ((*child)->state * 2 == -t->state)

91 * rotate(child, i ^ 1);

92 * rotate(tp, i);

93 *

94 * with rotate():

95 * static void rotate(AVTreeNode **tp, int i)

96 * {

97 * AVTreeNode *t= *tp;

98 *

99 * *tp = t->child[i];

100 * t->child[i] = t->child[i]->child[i ^ 1];

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

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

103 * t->state = ((0x614586 >> i) & 3) - 1;

104 * (*tp)->state = ((0x400EEA >> i) & 3) - 1 +

105 * ((*tp)->state >> 1);

106 * }

107 * but such a rotate function is both bigger and slower

108 */

109 if ((*child)->state * 2 == -t->state) {

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

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

112 (*tp)->child[i] = *child;

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

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

115

116 (*tp)->child[0]->state = -((*tp)->state > 0);

117 (*tp)->child[1]->state = (*tp)->state < 0;

118 (*tp)->state = 0;

119 } else {

120 *tp = *child;

121 *child = (*child)->child[i ^ 1];

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

123 if ((*tp)->state)

124 t->state = 0;

125 else

126 t->state >>= 1;

127 (*tp)->state = -t->state;

128 }

129 }

130 }

131 if (!(*tp)->state ^ !!*next)

132 return key;

133 }

134 return ret;

135 } else {

136 *tp = *next;

137 *next = NULL;

138 if (*tp) {

139 (*tp)->elem = key;

140 return NULL;

141 } else

142 return key;

143 }

144 }

145

146 void av_tree_destroy(AVTreeNode *t)

147 {

148 if (t) {

149 av_tree_destroy(t->child[0]);

150 av_tree_destroy(t->child[1]);

151 av_free(t);

152 }

153 }

154

155 void av_tree_enumerate(AVTreeNode *t, void *opaque,

156 int (*cmp)(void *opaque, void *elem),

157 int (*enu)(void *opaque, void *elem))

158 {

159 if (t) {

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

161 if (v >= 0)

162 av_tree_enumerate(t->child[0], opaque, cmp, enu);

163 if (v == 0)

164 enu(opaque, t->elem);

165 if (v <= 0)

166 av_tree_enumerate(t->child[1], opaque, cmp, enu);

167 }

168 }

169

170 #ifdef TEST

171

172 #include "common.h"

173 #include "lfg.h"

174

175 static int check(AVTreeNode *t)

176 {

177 if (t) {

178 int left = check(t->child[0]);

179 int right = check(t->child[1]);

180

181 if (left > 999 || right > 999)

182 return 1000;

183 if (right - left != t->state)

184 return 1000;

185 if (t->state > 1 || t->state < -1)

186 return 1000;

187 return FFMAX(left, right) + 1;

188 }

189 return 0;

190 }

191

192 static void print(AVTreeNode *t, int depth)

193 {

194 int i;

195 for (i = 0; i < depth * 4; i++)

196 av_log(NULL, AV_LOG_ERROR, " ");

197 if (t) {

198 av_log(NULL, AV_LOG_ERROR, "Node %p %2d %p\n", t, t->state, t->elem);

199 print(t->child[0], depth + 1);

200 print(t->child[1], depth + 1);

201 } else

202 av_log(NULL, AV_LOG_ERROR, "NULL\n");

203 }

204

205 static int cmp(void *a, const void *b)

206 {

207 return (uint8_t *) a - (const uint8_t *) b;

208 }

209

210 int main(int argc, char **argv)

211 {

212 int i;

213 void *k;

214 AVTreeNode *root = NULL, *node = NULL;

215 AVLFG prng;

216 int log_level = argc <= 1 ? AV_LOG_INFO : atoi(argv[1]);

217

218 av_log_set_level(log_level);

219

220 av_lfg_init(&prng, 1);

221

222 for (i = 0; i < 10000; i++) {

223 intptr_t j = av_lfg_get(&prng) % 86294;

224

225 if (check(root) > 999) {

226 av_log(NULL, AV_LOG_ERROR, "FATAL error %d\n", i);

227 print(root, 0);

228 return 1;

229 }

230 av_log(NULL, AV_LOG_DEBUG, "inserting %4d\n", (int)j);

231

232 if (!node)

233 node = av_tree_node_alloc();

234 if (!node) {

235 av_log(NULL, AV_LOG_ERROR, "Memory allocation failure.\n");

236 return 1;

237 }

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

239

240 j = av_lfg_get(&prng) % 86294;

241 {

242 AVTreeNode *node2 = NULL;

243 av_log(NULL, AV_LOG_DEBUG, "removing %4d\n", (int)j);

244 av_tree_insert(&root, (void *)(j + 1), cmp, &node2);

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

246 if (k)

247 av_log(NULL, AV_LOG_ERROR, "removal failure %d\n", i);

248 av_free(node2);

249 }

250 }

251 av_free(node);

252

253 av_tree_destroy(root);

254

255 return 0;

256 }

257 #endif

Generated on Sat Jan 25 2014 19:52:07 for FFmpeg by doxygen 1.8.2