FFmpeg
Main Page
Related Pages
Modules
Namespaces
Data Structures
Files
Examples
File List
Globals
All
Data Structures
Namespaces
Files
Functions
Variables
Typedefs
Enumerations
Enumerator
Macros
Groups
Pages
libavutil
tree.h
Go to the documentation of this file.
1
/*
2
* copyright (c) 2006 Michael Niedermayer <michaelni@gmx.at>
3
*
4
* This file is part of FFmpeg.
5
*
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.
10
*
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.
15
*
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
19
*/
20
21
/**
22
* @file
23
* A tree container.
24
* @author Michael Niedermayer <michaelni@gmx.at>
25
*/
26
27
#ifndef AVUTIL_TREE_H
28
#define AVUTIL_TREE_H
29
30
#include "
attributes.h
"
31
#include "
version.h
"
32
33
/**
34
* @addtogroup lavu_tree AVTree
35
* @ingroup lavu_data
36
*
37
* Low-complexity tree container
38
*
39
* Insertion, removal, finding equal, largest which is smaller than and
40
* smallest which is larger than, all have O(log n) worst-case complexity.
41
* @{
42
*/
43
44
45
struct
AVTreeNode
;
46
extern
const
int
av_tree_node_size
;
47
48
/**
49
* Allocate an AVTreeNode.
50
*/
51
struct
AVTreeNode
*
av_tree_node_alloc
(
void
);
52
53
/**
54
* Find an element.
55
* @param root a pointer to the root node of the tree
56
* @param next If next is not NULL, then next[0] will contain the previous
57
* element and next[1] the next element. If either does not exist,
58
* then the corresponding entry in next is unchanged.
59
* @return An element with cmp(key, elem) == 0 or NULL if no such element
60
* exists in the tree.
61
*/
62
void
*
av_tree_find
(
const
struct
AVTreeNode
*root,
void
*key,
63
int
(*
cmp
)(
void
*key,
const
void
*
b
),
void
*next[2]);
64
65
/**
66
* Insert or remove an element.
67
*
68
* If *next is NULL, then the supplied element will be removed if it exists.
69
* If *next is non-NULL, then the supplied element will be inserted, unless
70
* it already exists in the tree.
71
*
72
* @param rootp A pointer to a pointer to the root node of the tree; note that
73
* the root node can change during insertions, this is required
74
* to keep the tree balanced.
75
* @param key pointer to the element key to insert in the tree
76
* @param next Used to allocate and free AVTreeNodes. For insertion the user
77
* must set it to an allocated and zeroed object of at least
78
* av_tree_node_size bytes size. av_tree_insert() will set it to
79
* NULL if it has been consumed.
80
* For deleting elements *next is set to NULL by the user and
81
* av_tree_insert() will set it to the AVTreeNode which was
82
* used for the removed element.
83
* This allows the use of flat arrays, which have
84
* lower overhead compared to many malloced elements.
85
* You might want to define a function like:
86
* @code
87
* void *tree_insert(struct AVTreeNode **rootp, void *key,
88
* int (*cmp)(void *key, const void *b),
89
* AVTreeNode **next)
90
* {
91
* if (!*next)
92
* *next = av_mallocz(av_tree_node_size);
93
* return av_tree_insert(rootp, key, cmp, next);
94
* }
95
* void *tree_remove(struct AVTreeNode **rootp, void *key,
96
* int (*cmp)(void *key, const void *b, AVTreeNode **next))
97
* {
98
* av_freep(next);
99
* return av_tree_insert(rootp, key, cmp, next);
100
* }
101
* @endcode
102
* @param cmp compare function used to compare elements in the tree
103
* @return If no insertion happened, the found element; if an insertion or
104
* removal happened, then either key or NULL will be returned.
105
* Which one it is depends on the tree state and the implementation. You
106
* should make no assumptions that it's one or the other in the code.
107
*/
108
void
*
av_tree_insert
(
struct
AVTreeNode
**rootp,
void
*key,
109
int
(*
cmp
)(
void
*key,
const
void
*
b
),
110
struct
AVTreeNode
**next);
111
112
void
av_tree_destroy
(
struct
AVTreeNode
*t);
113
114
/**
115
* Apply enu(opaque, &elem) to all the elements in the tree in a given range.
116
*
117
* @param cmp a comparison function that returns < 0 for a element below the
118
* range, > 0 for a element above the range and == 0 for a
119
* element inside the range
120
*
121
* @note The cmp function should use the same ordering used to construct the
122
* tree.
123
*/
124
void
av_tree_enumerate
(
struct
AVTreeNode
*t,
void
*opaque,
125
int
(*
cmp
)(
void
*opaque,
void
*
elem
),
126
int
(*enu)(
void
*opaque,
void
*elem));
127
128
/**
129
* @}
130
*/
131
132
#endif
/* AVUTIL_TREE_H */
Generated on Sun Mar 8 2015 02:35:14 for FFmpeg by
1.8.2