Split global .gitignore file into per-directory files
[libav.git] / libavutil / tree-test.c
1 /*
2 * This file is part of Libav.
3 *
4 * Libav 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 * Libav 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 Libav; if not, write to the Free Software
16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
17 */
18
19 #include "tree.c"
20
21 #include <stdint.h>
22
23 #include "common.h"
24 #include "lfg.h"
25 #include "log.h"
26
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
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
57 static int cmp(void *a, const void *b)
58 {
59 return (uint8_t *) a - (const uint8_t *) b;
60 }
61
62 int main(void)
63 {
64 int i;
65 AVTreeNode *root = NULL, *node = NULL;
66 AVLFG prng;
67
68 av_lfg_init(&prng, 1);
69
70 for (i = 0; i < 10000; i++) {
71 AVTreeNode *node2 = NULL;
72 intptr_t j = av_lfg_get(&prng) % 86294;
73 void *ret, *jj = (void *)(j + 1);
74
75 while (ret = av_tree_find(root, jj, cmp, NULL)) {
76 j = av_lfg_get(&prng) % 86294;
77 jj = (void *)(j + 1);
78 }
79
80 if (check(root) > 999) {
81 av_log(NULL, AV_LOG_ERROR, "FATAL error %d\n", i);
82 print(root, 0);
83 return 1;
84 }
85
86 if (!node)
87 node = av_tree_node_alloc();
88 if (!node) {
89 av_log(NULL, AV_LOG_ERROR, "Memory allocation failure.\n");
90 return 1;
91 }
92 av_tree_insert(&root, jj, cmp, &node);
93
94 while (ret = av_tree_find(root, jj, cmp, NULL)) {
95 j = av_lfg_get(&prng) % 86294;
96 jj = (void *)(j + 1);
97 }
98
99 ret = av_tree_insert(&root, jj, cmp, &node2);
100 if (ret != jj)
101 av_tree_destroy(node2);
102 ret = av_tree_find(root, jj, cmp, NULL);
103 if (ret)
104 av_log(NULL, AV_LOG_ERROR, "removal failure %d\n", i);
105 }
106
107 av_tree_destroy(root);
108
109 return 0;
110 }