FFmpeg
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
tree.c
Go to the documentation of this file.
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 }
Definition: lfg.h:25
#define NULL
Definition: coverity.c:32
void av_log_set_level(int level)
Set the log level.
Definition: log.c:391
const char * b
Definition: vf_curves.c:109
int main(int argc, char **argv)
Definition: tree.c:62
void * av_tree_find(const AVTreeNode *t, void *key, int(*cmp)(const void *key, const void *b), void *next[2])
Definition: tree.c:39
struct AVTreeNode * av_tree_node_alloc(void)
Allocate an AVTreeNode.
Definition: tree.c:34
uint8_t
#define av_log(a,...)
void av_tree_destroy(AVTreeNode *t)
Definition: tree.c:146
#define AV_LOG_ERROR
Something went wrong and cannot losslessly be recovered.
Definition: log.h:176
struct AVTreeNode * child[2]
Definition: tree.c:27
#define AV_LOG_DEBUG
Stuff which is only useful for libav* developers.
Definition: log.h:197
int state
Definition: tree.c:29
#define FFMAX(a, b)
Definition: common.h:94
int depth
Definition: v4l.c:62
#define AV_LOG_INFO
Standard information.
Definition: log.h:187
static int cmp(const void *a, const void *b)
Definition: tree.c:57
static unsigned int av_lfg_get(AVLFG *c)
Get the next random unsigned 32-bit number using an ALFG.
Definition: lfg.h:38
static int check(AVTreeNode *t)
Definition: tree.c:27
av_cold void av_lfg_init(AVLFG *c, unsigned int seed)
Definition: lfg.c:30
common internal and external API header
#define av_free(p)
void * av_tree_insert(AVTreeNode **tp, void *key, int(*cmp)(const void *key, const void *b), AVTreeNode **next)
Insert or remove an element.
Definition: tree.c:59
static void print(AVTreeNode *t, int depth)
Definition: tree.c:44
void * elem
Definition: tree.c:28