2 * copyright (c) 2006 Michael Niedermayer <michaelni@gmx.at>
4 * This file is part of FFmpeg.
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.
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.
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
26 typedef struct AVTreeNode
{
27 struct AVTreeNode
*child
[2];
32 const int av_tree_node_size
= sizeof(AVTreeNode
);
34 struct AVTreeNode
*av_tree_node_alloc(void)
36 return av_mallocz(sizeof(struct AVTreeNode
));
39 void *av_tree_find(const AVTreeNode
*t
, void *key
,
40 int (*cmp
)(void *key
, const void *b
), void *next
[2])
43 unsigned int v
= cmp(key
, t
->elem
);
46 next
[v
>> 31] = t
->elem
;
47 return av_tree_find(t
->child
[(v
>> 31) ^ 1], key
, cmp
, next
);
50 av_tree_find(t
->child
[0], key
, cmp
, next
);
51 av_tree_find(t
->child
[1], key
, cmp
, next
);
59 void *av_tree_insert(AVTreeNode
**tp
, void *key
,
60 int (*cmp
)(void *key
, const void *b
), AVTreeNode
**next
)
64 unsigned int v
= cmp(t
->elem
, key
);
69 else if (t
->child
[0] || t
->child
[1]) {
72 av_tree_find(t
->child
[i
], key
, cmp
, next_elem
);
73 key
= t
->elem
= next_elem
[i
];
81 ret
= av_tree_insert(&t
->child
[v
>> 31], key
, cmp
, next
);
83 int i
= (v
>> 31) ^ !!*next
;
84 AVTreeNode
**child
= &t
->child
[i
];
85 t
->state
+= 2 * i
- 1;
87 if (!(t
->state
& 1)) {
89 /* The following code is equivalent to
90 * if ((*child)->state * 2 == -t->state)
91 * rotate(child, i ^ 1);
95 * static void rotate(AVTreeNode **tp, int 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);
107 * but such a rotate function is both bigger and slower
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
;
116 (*tp
)->child
[0]->state
= -((*tp
)->state
> 0);
117 (*tp
)->child
[1]->state
= (*tp
)->state
< 0;
121 *child
= (*child
)->child
[i
^ 1];
122 (*tp
)->child
[i
^ 1] = t
;
127 (*tp
)->state
= -t
->state
;
131 if (!(*tp
)->state
^ !!*next
)
146 void av_tree_destroy(AVTreeNode
*t
)
149 av_tree_destroy(t
->child
[0]);
150 av_tree_destroy(t
->child
[1]);
155 void av_tree_enumerate(AVTreeNode
*t
, void *opaque
,
156 int (*cmp
)(void *opaque
, void *elem
),
157 int (*enu
)(void *opaque
, void *elem
))
160 int v
= cmp
? cmp(opaque
, t
->elem
) : 0;
162 av_tree_enumerate(t
->child
[0], opaque
, cmp
, enu
);
164 enu(opaque
, t
->elem
);
166 av_tree_enumerate(t
->child
[1], opaque
, cmp
, enu
);
175 static int check(AVTreeNode
*t
)
178 int left
= check(t
->child
[0]);
179 int right
= check(t
->child
[1]);
181 if (left
> 999 || right
> 999)
183 if (right
- left
!= t
->state
)
185 if (t
->state
> 1 || t
->state
< -1)
187 return FFMAX(left
, right
) + 1;
192 static void print(AVTreeNode
*t
, int depth
)
195 for (i
= 0; i
< depth
* 4; i
++)
196 av_log(NULL
, AV_LOG_ERROR
, " ");
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);
202 av_log(NULL
, AV_LOG_ERROR
, "NULL\n");
205 static int cmp(void *a
, const void *b
)
207 return (uint8_t *) a
- (const uint8_t *) b
;
210 int main(int argc
, char **argv
)
214 AVTreeNode
*root
= NULL
, *node
= NULL
;
216 int log_level
= argc
<= 1 ? AV_LOG_INFO
: atoi(argv
[1]);
218 av_log_set_level(log_level
);
220 av_lfg_init(&prng
, 1);
222 for (i
= 0; i
< 10000; i
++) {
223 intptr_t j
= av_lfg_get(&prng
) % 86294;
225 if (check(root
) > 999) {
226 av_log(NULL
, AV_LOG_ERROR
, "FATAL error %d\n", i
);
230 av_log(NULL
, AV_LOG_DEBUG
, "inserting %4d\n", (int)j
);
233 node
= av_tree_node_alloc();
235 av_log(NULL
, AV_LOG_ERROR
, "Memory allocation failure.\n");
238 av_tree_insert(&root
, (void *)(j
+ 1), cmp
, &node
);
240 j
= av_lfg_get(&prng
) % 86294;
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
);
247 av_log(NULL
, AV_LOG_ERROR
, "removal failure %d\n", i
);
253 av_tree_destroy(root
);