tree.h (5408B)
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 32 /** 33 * @addtogroup lavu_tree AVTree 34 * @ingroup lavu_data 35 * 36 * Low-complexity tree container 37 * 38 * Insertion, removal, finding equal, largest which is smaller than and 39 * smallest which is larger than, all have O(log n) worst-case complexity. 40 * @{ 41 */ 42 43 44 struct AVTreeNode; 45 extern const int av_tree_node_size; 46 47 /** 48 * Allocate an AVTreeNode. 49 */ 50 struct AVTreeNode *av_tree_node_alloc(void); 51 52 /** 53 * Find an element. 54 * @param root a pointer to the root node of the tree 55 * @param next If next is not NULL, then next[0] will contain the previous 56 * element and next[1] the next element. If either does not exist, 57 * then the corresponding entry in next is unchanged. 58 * @param cmp compare function used to compare elements in the tree, 59 * API identical to that of Standard C's qsort 60 * It is guaranteed that the first and only the first argument to cmp() 61 * will be the key parameter to av_tree_find(), thus it could if the 62 * user wants, be a different type (like an opaque context). 63 * @return An element with cmp(key, elem) == 0 or NULL if no such element 64 * exists in the tree. 65 */ 66 void *av_tree_find(const struct AVTreeNode *root, void *key, 67 int (*cmp)(const void *key, const void *b), void *next[2]); 68 69 /** 70 * Insert or remove an element. 71 * 72 * If *next is NULL, then the supplied element will be removed if it exists. 73 * If *next is non-NULL, then the supplied element will be inserted, unless 74 * it already exists in the tree. 75 * 76 * @param rootp A pointer to a pointer to the root node of the tree; note that 77 * the root node can change during insertions, this is required 78 * to keep the tree balanced. 79 * @param key pointer to the element key to insert in the tree 80 * @param next Used to allocate and free AVTreeNodes. For insertion the user 81 * must set it to an allocated and zeroed object of at least 82 * av_tree_node_size bytes size. av_tree_insert() will set it to 83 * NULL if it has been consumed. 84 * For deleting elements *next is set to NULL by the user and 85 * av_tree_insert() will set it to the AVTreeNode which was 86 * used for the removed element. 87 * This allows the use of flat arrays, which have 88 * lower overhead compared to many malloced elements. 89 * You might want to define a function like: 90 * @code 91 * void *tree_insert(struct AVTreeNode **rootp, void *key, 92 * int (*cmp)(void *key, const void *b), 93 * AVTreeNode **next) 94 * { 95 * if (!*next) 96 * *next = av_mallocz(av_tree_node_size); 97 * return av_tree_insert(rootp, key, cmp, next); 98 * } 99 * void *tree_remove(struct AVTreeNode **rootp, void *key, 100 * int (*cmp)(void *key, const void *b, AVTreeNode **next)) 101 * { 102 * av_freep(next); 103 * return av_tree_insert(rootp, key, cmp, next); 104 * } 105 * @endcode 106 * @param cmp compare function used to compare elements in the tree, API identical 107 * to that of Standard C's qsort 108 * @return If no insertion happened, the found element; if an insertion or 109 * removal happened, then either key or NULL will be returned. 110 * Which one it is depends on the tree state and the implementation. You 111 * should make no assumptions that it's one or the other in the code. 112 */ 113 void *av_tree_insert(struct AVTreeNode **rootp, void *key, 114 int (*cmp)(const void *key, const void *b), 115 struct AVTreeNode **next); 116 117 void av_tree_destroy(struct AVTreeNode *t); 118 119 /** 120 * Apply enu(opaque, &elem) to all the elements in the tree in a given range. 121 * 122 * @param cmp a comparison function that returns < 0 for an element below the 123 * range, > 0 for an element above the range and == 0 for an 124 * element inside the range 125 * 126 * @note The cmp function should use the same ordering used to construct the 127 * tree. 128 */ 129 void av_tree_enumerate(struct AVTreeNode *t, void *opaque, 130 int (*cmp)(void *opaque, void *elem), 131 int (*enu)(void *opaque, void *elem)); 132 133 /** 134 * @} 135 */ 136 137 #endif /* AVUTIL_TREE_H */