Revision bfe3676f libavutil/tree.h
libavutil/tree.h  

21  21 
/** 
22  22 
* @file tree.h 
23  23 
* A tree container. 
24 
* Insertion, Removial, Finding equal, largest which is smaller than and


25 
* smallest which is larger than all have O(log n) worst case time.


24 
* Insertion, removal, finding equal, largest which is smaller than and


25 
* smallest which is larger than, all have O(log n) worst case complexity.


26  26 
* @author Michael Niedermayer <michaelni@gmx.at> 
27  27 
*/ 
28  28  
...  ...  
35  35 
/** 
36  36 
* Finds an element. 
37  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 

39 
* element and next[1] the next element if either does not exist


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,


40  40 
* then the corresponding entry in next is unchanged. 
41  41 
* @return An element with cmp(key, elem)==0 or NULL if no such element exists in 
42  42 
* the tree. 
...  ...  
45  45  
46  46 
/** 
47  47 
* Inserts or removes an element. 
48 
* If *next is NULL then the element supplied will be removed if it exists.


49 
* If *next is not NULL then the element supplied will be inserted, unless


48 
* If *next is NULL, then the supplied element will be removed if it exists.


49 
* If *next is not NULL, then the supplied element will be inserted, unless


50  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  52 
* the root node can change during insertions, this is required 
53  53 
* to keep the tree balanced. 
54  54 
* @param next Used to allocate and free AVTreeNodes. For insertion the user 
...  ...  
70  70 
* return av_tree_insert(rootp, key, cmp, next); 
71  71 
* } 
72  72 
* 
73 
* @return If no insertion happened, the found element.


74 
* If an insertion or removial happened, then either key or NULL will be returned.


73 
* @return If no insertion happened, the found element; if an insertion or


74 
removal happened, then either key or NULL will be returned.


75  75 
* Which one it is depends on the tree state and the implementation. You 
76  76 
* should make no assumptions that it's one or the other in the code. 
77  77 
*/ 
Also available in: Unified diff