Details | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
6147 | serge | 1 | /* |
2 | * copyright (c) 2006 Michael Niedermayer |
||
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 |
||
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 */> |