Mercurial > libavutil.hg
comparison tree.h @ 636:c04808220c83 libavutil
spelling/grammar/consistency review part II
author | diego |
---|---|
date | Wed, 28 Jan 2009 23:03:17 +0000 |
parents | 5877edf05eb7 |
children | 70bdd5501662 |
comparison
equal
deleted
inserted
replaced
635:0a51400a64c9 | 636:c04808220c83 |
---|---|
19 */ | 19 */ |
20 | 20 |
21 /** | 21 /** |
22 * @file tree.h | 22 * @file tree.h |
23 * A tree container. | 23 * A tree container. |
24 * Insertion, Removial, Finding equal, largest which is smaller than and | 24 * Insertion, removal, finding equal, largest which is smaller than and |
25 * smallest which is larger than all have O(log n) worst case time. | 25 * smallest which is larger than, all have O(log n) worst case complexity. |
26 * @author Michael Niedermayer <michaelni@gmx.at> | 26 * @author Michael Niedermayer <michaelni@gmx.at> |
27 */ | 27 */ |
28 | 28 |
29 #ifndef AVUTIL_TREE_H | 29 #ifndef AVUTIL_TREE_H |
30 #define AVUTIL_TREE_H | 30 #define AVUTIL_TREE_H |
33 extern const int av_tree_node_size; | 33 extern const int av_tree_node_size; |
34 | 34 |
35 /** | 35 /** |
36 * Finds an element. | 36 * Finds an element. |
37 * @param root a pointer to the root node of the tree | 37 * @param root a pointer to the root node of the tree |
38 * @param next If next is not NULL then next[0] will contain the previous | 38 * @param next If next is not NULL, then next[0] will contain the previous |
39 * element and next[1] the next element if either does not exist | 39 * element and next[1] the next element. If either does not exist, |
40 * then the corresponding entry in next is unchanged. | 40 * then the corresponding entry in next is unchanged. |
41 * @return An element with cmp(key, elem)==0 or NULL if no such element exists in | 41 * @return An element with cmp(key, elem)==0 or NULL if no such element exists in |
42 * the tree. | 42 * the tree. |
43 */ | 43 */ |
44 void *av_tree_find(const struct AVTreeNode *root, void *key, int (*cmp)(void *key, const void *b), void *next[2]); | 44 void *av_tree_find(const struct AVTreeNode *root, void *key, int (*cmp)(void *key, const void *b), void *next[2]); |
45 | 45 |
46 /** | 46 /** |
47 * Inserts or removes an element. | 47 * Inserts or removes an element. |
48 * If *next is NULL then the element supplied will be removed if it exists. | 48 * If *next is NULL, then the supplied element will be removed if it exists. |
49 * If *next is not NULL then the element supplied will be inserted, unless | 49 * If *next is not NULL, then the supplied element will be inserted, unless |
50 * it already exists in the tree. | 50 * it already exists in the tree. |
51 * @param rootp A pointer to a pointer to the root node of the tree. Note that | 51 * @param rootp A pointer to a pointer to the root node of the tree; note that |
52 * the root node can change during insertions, this is required | 52 * the root node can change during insertions, this is required |
53 * to keep the tree balanced. | 53 * to keep the tree balanced. |
54 * @param next Used to allocate and free AVTreeNodes. For insertion the user | 54 * @param next Used to allocate and free AVTreeNodes. For insertion the user |
55 * must set it to an allocated and zeroed object of at least | 55 * must set it to an allocated and zeroed object of at least |
56 * av_tree_node_size bytes size. av_tree_insert() will set it to | 56 * av_tree_node_size bytes size. av_tree_insert() will set it to |
68 * void *tree_remove(struct AVTreeNode **rootp, void *key, int (*cmp)(void *key, const void *b, AVTreeNode **next)){ | 68 * void *tree_remove(struct AVTreeNode **rootp, void *key, int (*cmp)(void *key, const void *b, AVTreeNode **next)){ |
69 * if(*next) av_freep(next); | 69 * if(*next) av_freep(next); |
70 * return av_tree_insert(rootp, key, cmp, next); | 70 * return av_tree_insert(rootp, key, cmp, next); |
71 * } | 71 * } |
72 * | 72 * |
73 * @return If no insertion happened, the found element. | 73 * @return If no insertion happened, the found element; if an insertion or |
74 * If an insertion or removial happened, then either key or NULL will be returned. | 74 removal happened, then either key or NULL will be returned. |
75 * Which one it is depends on the tree state and the implementation. You | 75 * Which one it is depends on the tree state and the implementation. You |
76 * should make no assumptions that it's one or the other in the code. | 76 * should make no assumptions that it's one or the other in the code. |
77 */ | 77 */ |
78 void *av_tree_insert(struct AVTreeNode **rootp, void *key, int (*cmp)(void *key, const void *b), struct AVTreeNode **next); | 78 void *av_tree_insert(struct AVTreeNode **rootp, void *key, int (*cmp)(void *key, const void *b), struct AVTreeNode **next); |
79 void av_tree_destroy(struct AVTreeNode *t); | 79 void av_tree_destroy(struct AVTreeNode *t); |