1 /*
2 * This file is part of FFmpeg.
3 *
4 * FFmpeg is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Lesser General Public
6 * License as published by the Free Software Foundation; either
7 * version 2.1 of the License, or (at your option) any later version.
8 *
9 * FFmpeg is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Lesser General Public License for more details.
13 *
14 * You should have received a copy of the GNU Lesser General Public
15 * License along with FFmpeg; if not, write to the Free Software
16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
17 */
18
19 #include "libavutil/tree.c"
20
21 #include <stdint.h>
22
23 #include "libavutil/common.h"
24 #include "libavutil/lfg.h"
25 #include "libavutil/log.h"
26
check(AVTreeNode * t)27 static int check(AVTreeNode *t)
28 {
29 if (t) {
30 int left = check(t->child[0]);
31 int right = check(t->child[1]);
32
33 if (left > 999 || right > 999)
34 return 1000;
35 if (right - left != t->state)
36 return 1000;
37 if (t->state > 1 || t->state < -1)
38 return 1000;
39 return FFMAX(left, right) + 1;
40 }
41 return 0;
42 }
43
print(AVTreeNode * t,int depth)44 static void print(AVTreeNode *t, int depth)
45 {
46 int i;
47 for (i = 0; i < depth * 4; i++)
48 av_log(NULL, AV_LOG_ERROR, " ");
49 if (t) {
50 av_log(NULL, AV_LOG_ERROR, "Node %p %2d %p\n", t, t->state, t->elem);
51 print(t->child[0], depth + 1);
52 print(t->child[1], depth + 1);
53 } else
54 av_log(NULL, AV_LOG_ERROR, "NULL\n");
55 }
56
cmp(const void * a,const void * b)57 static int cmp(const void *a, const void *b)
58 {
59 return (const uint8_t *) a - (const uint8_t *) b;
60 }
61
main(int argc,char ** argv)62 int main(int argc, char **argv)
63 {
64 int i;
65 void *k;
66 AVTreeNode *root = NULL, *node = NULL;
67 AVLFG prng;
68 int log_level = argc <= 1 ? AV_LOG_INFO : atoi(argv[1]);
69
70 av_log_set_level(log_level);
71
72 av_lfg_init(&prng, 1);
73
74 for (i = 0; i < 10000; i++) {
75 intptr_t j = av_lfg_get(&prng) % 86294;
76
77 if (check(root) > 999) {
78 av_log(NULL, AV_LOG_ERROR, "FATAL error %d\n", i);
79 print(root, 0);
80 return 1;
81 }
82 av_log(NULL, AV_LOG_DEBUG, "inserting %4d\n", (int)j);
83
84 if (!node)
85 node = av_tree_node_alloc();
86 if (!node) {
87 av_log(NULL, AV_LOG_ERROR, "Memory allocation failure.\n");
88 return 1;
89 }
90 av_tree_insert(&root, (void *)(j + 1), cmp, &node);
91
92 j = av_lfg_get(&prng) % 86294;
93 {
94 AVTreeNode *node2 = NULL;
95 av_log(NULL, AV_LOG_DEBUG, "removing %4d\n", (int)j);
96 av_tree_insert(&root, (void *)(j + 1), cmp, &node2);
97 k = av_tree_find(root, (void *)(j + 1), cmp, NULL);
98 if (k)
99 av_log(NULL, AV_LOG_ERROR, "removal failure %d\n", i);
100 av_free(node2);
101 }
102 }
103 av_free(node);
104
105 av_tree_destroy(root);
106
107 return 0;
108 }
109