comparison tree.h @ 416:dee66b77779a libavutil

Document node removial API.
author michael
date Fri, 04 Jan 2008 18:46:53 +0000
parents a54e20281de9
children ba2d05538ec1
comparison
equal deleted inserted replaced
415:1f1ebfcfa9cd 416:dee66b77779a
40 * the tree. 40 * the tree.
41 */ 41 */
42 void *av_tree_find(const struct AVTreeNode *root, void *key, int (*cmp)(void *key, const void *b), void *next[2]); 42 void *av_tree_find(const struct AVTreeNode *root, void *key, int (*cmp)(void *key, const void *b), void *next[2]);
43 43
44 /** 44 /**
45 * Finds a element for which cmp(key, elem)==0, if no such element is found key 45 * Inserts or removes an element.
46 * is inserted into the tree. 46 * If *next is NULL then the element supplied will be removed, if no such
47 * element exists behavior is undefined.
48 * If *next is not NULL then the element supplied will be inserted, unless
49 * it already exists in the tree.
47 * @param rootp A pointer to a pointer to the root node of the tree. Note that 50 * @param rootp A pointer to a pointer to the root node of the tree. Note that
48 * the root node can change during insertions, this is required 51 * the root node can change during insertions, this is required
49 * to keep the tree balanced. 52 * to keep the tree balanced.
50 * @param next AVTreeNode used for the inserted element, must be allocated and 53 * @param next Used to allocate and free AVTreeNodes. For insertion the user
51 * zeroed by the user. And will be set to NULL if used by 54 * must set it to an allocated and zeroed object of at least
52 * av_tree_insert(). This allows the use of flat arrays, which have 55 * av_tree_node_size bytes size. av_tree_insert() will set it to
56 * NULL if it has been consumed.
57 * For deleting elements *next is set to NULL by the user and
58 * av_tree_node_size() will set it to the AVTreeNode which was
59 * used for the removed element.
60 * This allows the use of flat arrays, which have
53 * lower overhead compared to many malloced elements. 61 * lower overhead compared to many malloced elements.
54 * You might want to define a function like: 62 * You might want to define a function like:
55 * void *tree_insert(struct AVTreeNode **rootp, void *key, int (*cmp)(void *key, const void *b), AVTreeNode **next){ 63 * void *tree_insert(struct AVTreeNode **rootp, void *key, int (*cmp)(void *key, const void *b), AVTreeNode **next){
56 * if(!*next) *next= av_mallocz(av_tree_node_size); 64 * if(!*next) *next= av_mallocz(av_tree_node_size);
57 * return av_tree_insert(rootp, key, cmp, next); 65 * return av_tree_insert(rootp, key, cmp, next);
58 * } 66 * }
67 * void *tree_remove(struct AVTreeNode **rootp, void *key, int (*cmp)(void *key, const void *b, AVTreeNode **next)){
68 * if(*next) av_freep(next);
69 * return av_tree_insert(rootp, key, cmp, next);
70 * }
59 * 71 *
60 * @return If no insertion happened, the found element. 72 * @return If no insertion happened, the found element.
61 * If an insertion happened, then either key or NULL will be returned. 73 * If an insertion or removial happened, then either key or NULL will be returned.
62 * Which one it is depends on the tree state and the implementation. You 74 * Which one it is depends on the tree state and the implementation. You
63 * should make no assumptions that it's one or the other in the code. 75 * should make no assumptions that it's one or the other in the code.
64 */ 76 */
65 void *av_tree_insert(struct AVTreeNode **rootp, void *key, int (*cmp)(void *key, const void *b), struct AVTreeNode **next); 77 void *av_tree_insert(struct AVTreeNode **rootp, void *key, int (*cmp)(void *key, const void *b), struct AVTreeNode **next);
66 void av_tree_destroy(struct AVTreeNode *t); 78 void av_tree_destroy(struct AVTreeNode *t);