Mercurial > libavutil.hg
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); |