Commit | Line | Data |
---|---|---|
2ba45a60 DM |
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 */ |