Merge commit 'a6a750c7ef240b72ce01e9653343a0ddf247d196'
[ffmpeg.git] / libavutil / tests / tree.c
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
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(const void *a, const void *b)
58 {
59     return (const uint8_t *) a - (const uint8_t *) b;
60 }
61
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 }