yading@11: /* yading@11: * copyright (c) 2006 Michael Niedermayer yading@11: * yading@11: * This file is part of FFmpeg. yading@11: * yading@11: * FFmpeg is free software; you can redistribute it and/or yading@11: * modify it under the terms of the GNU Lesser General Public yading@11: * License as published by the Free Software Foundation; either yading@11: * version 2.1 of the License, or (at your option) any later version. yading@11: * yading@11: * FFmpeg is distributed in the hope that it will be useful, yading@11: * but WITHOUT ANY WARRANTY; without even the implied warranty of yading@11: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU yading@11: * Lesser General Public License for more details. yading@11: * yading@11: * You should have received a copy of the GNU Lesser General Public yading@11: * License along with FFmpeg; if not, write to the Free Software yading@11: * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA yading@11: */ yading@11: yading@11: /** yading@11: * @file yading@11: * A tree container. yading@11: * @author Michael Niedermayer yading@11: */ yading@11: yading@11: #ifndef AVUTIL_TREE_H yading@11: #define AVUTIL_TREE_H yading@11: yading@11: #include "attributes.h" yading@11: #include "version.h" yading@11: yading@11: /** yading@11: * @addtogroup lavu_tree AVTree yading@11: * @ingroup lavu_data yading@11: * yading@11: * Low complexity tree container yading@11: * yading@11: * Insertion, removal, finding equal, largest which is smaller than and yading@11: * smallest which is larger than, all have O(log n) worst case complexity. yading@11: * @{ yading@11: */ yading@11: yading@11: yading@11: struct AVTreeNode; yading@11: extern const int av_tree_node_size; yading@11: yading@11: /** yading@11: * Allocate an AVTreeNode. yading@11: */ yading@11: struct AVTreeNode *av_tree_node_alloc(void); yading@11: yading@11: /** yading@11: * Find an element. yading@11: * @param root a pointer to the root node of the tree yading@11: * @param next If next is not NULL, then next[0] will contain the previous yading@11: * element and next[1] the next element. If either does not exist, yading@11: * then the corresponding entry in next is unchanged. yading@11: * @return An element with cmp(key, elem)==0 or NULL if no such element exists in yading@11: * the tree. yading@11: */ yading@11: void *av_tree_find(const struct AVTreeNode *root, void *key, int (*cmp)(void *key, const void *b), void *next[2]); yading@11: yading@11: /** yading@11: * Insert or remove an element. yading@11: * yading@11: * If *next is NULL, then the supplied element will be removed if it exists. yading@11: * If *next is non-NULL, then the supplied element will be inserted, unless yading@11: * it already exists in the tree. yading@11: * yading@11: * @param rootp A pointer to a pointer to the root node of the tree; note that yading@11: * the root node can change during insertions, this is required yading@11: * to keep the tree balanced. yading@11: * @param key pointer to the element key to insert in the tree yading@11: * @param next Used to allocate and free AVTreeNodes. For insertion the user yading@11: * must set it to an allocated and zeroed object of at least yading@11: * av_tree_node_size bytes size. av_tree_insert() will set it to yading@11: * NULL if it has been consumed. yading@11: * For deleting elements *next is set to NULL by the user and yading@11: * av_tree_insert() will set it to the AVTreeNode which was yading@11: * used for the removed element. yading@11: * This allows the use of flat arrays, which have yading@11: * lower overhead compared to many malloced elements. yading@11: * You might want to define a function like: yading@11: * @code yading@11: * void *tree_insert(struct AVTreeNode **rootp, void *key, int (*cmp)(void *key, const void *b), AVTreeNode **next){ yading@11: * if(!*next) *next= av_mallocz(av_tree_node_size); yading@11: * return av_tree_insert(rootp, key, cmp, next); yading@11: * } yading@11: * void *tree_remove(struct AVTreeNode **rootp, void *key, int (*cmp)(void *key, const void *b, AVTreeNode **next)){ yading@11: * av_freep(next); yading@11: * return av_tree_insert(rootp, key, cmp, next); yading@11: * } yading@11: * @endcode yading@11: * @param cmp compare function used to compare elements in the tree yading@11: * @return If no insertion happened, the found element; if an insertion or yading@11: * removal happened, then either key or NULL will be returned. yading@11: * Which one it is depends on the tree state and the implementation. You yading@11: * should make no assumptions that it's one or the other in the code. yading@11: */ yading@11: void *av_tree_insert(struct AVTreeNode **rootp, void *key, int (*cmp)(void *key, const void *b), struct AVTreeNode **next); yading@11: void av_tree_destroy(struct AVTreeNode *t); yading@11: yading@11: /** yading@11: * Apply enu(opaque, &elem) to all the elements in the tree in a given range. yading@11: * yading@11: * @param cmp a comparison function that returns < 0 for a element below the yading@11: * range, > 0 for a element above the range and == 0 for a yading@11: * element inside the range yading@11: * yading@11: * @note The cmp function should use the same ordering used to construct the yading@11: * tree. yading@11: */ yading@11: void av_tree_enumerate(struct AVTreeNode *t, void *opaque, int (*cmp)(void *opaque, void *elem), int (*enu)(void *opaque, void *elem)); yading@11: yading@11: /** yading@11: * @} yading@11: */ yading@11: yading@11: #endif /* AVUTIL_TREE_H */