← Back to branch summary

~ubuntu-branches/ubuntu/jaunty/xvidcap/jaunty-proposed

« back to all changes in this revision

Viewing changes to ffmpeg/libavutil/tree.h

  • Committer: Bazaar Package Importer
  • Author(s): Lionel Le Folgoc, Andrew Starr-Bochicchio, Lionel Le Folgoc
  • Date: 2008-12-26 00:10:06 UTC
  • mfrom: (1.1.2 upstream)
  • Revision ID: james.westby@ubuntu.com-20081226001006-2040ls9680bd1blt
Tags: 1.1.7-0.2ubuntu1
https://launchpad.net/bugs/298547
https://launchpad.net/bugs/311412
[ Andrew Starr-Bochicchio ]
* Merge from debian-multimedia (LP: #298547), Ubuntu Changes:
 - For ffmpeg-related build-deps, fix versionized dependencies
   as the ubuntu versioning is different than debian-multimedia's.

[ Lionel Le Folgoc ]
* LP: #311412 is fixed since the 1.1.7~rc1-0.1 revision.
* debian/patches/03_ffmpeg.diff: updated to fix FTBFS due to libswscale API
  change (cherry-pick from Gentoo #234383).

Show diffs side-by-side

added added

removed removed

Lines of Context:
ffmpeg/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
26
 * @author Michael Niedermayer <michaelni@gmx.at>
25
27
 */
26
28
 
27
 
#ifndef TREE_H
28
 
#define TREE_H
 
29
#ifndef FFMPEG_TREE_H
 
30
#define FFMPEG_TREE_H
29
31
 
30
32
struct AVTreeNode;
 
33
extern const int av_tree_node_size;
31
34
 
32
35
/**
33
36
 * Finds an element.
41
44
void *av_tree_find(const struct AVTreeNode *root, void *key, int (*cmp)(void *key, const void *b), void *next[2]);
42
45
 
43
46
/**
44
 
 * Finds a element for which cmp(key, elem)==0, if no such element is found key
45
 
 * is inserted into the tree.
 
47
 * Inserts or removes an element.
 
48
 * If *next is NULL then the element supplied will be removed, if no such
 
49
 * element exists behavior is undefined.
 
50
 * If *next is not NULL then the element supplied will be inserted, unless
 
51
 * it already exists in the tree.
46
52
 * @param rootp A pointer to a pointer to the root node of the tree. Note that
47
53
 *              the root node can change during insertions, this is required
48
54
 *              to keep the tree balanced.
 
55
 * @param next Used to allocate and free AVTreeNodes. For insertion the user
 
56
 *             must set it to an allocated and zeroed object of at least
 
57
 *             av_tree_node_size bytes size. av_tree_insert() will set it to
 
58
 *             NULL if it has been consumed.
 
59
 *             For deleting elements *next is set to NULL by the user and
 
60
 *             av_tree_node_size() will set it to the AVTreeNode which was
 
61
 *             used for the removed element.
 
62
 *             This allows the use of flat arrays, which have
 
63
 *             lower overhead compared to many malloced elements.
 
64
 *             You might want to define a function like:
 
65
 *             void *tree_insert(struct AVTreeNode **rootp, void *key, int (*cmp)(void *key, const void *b), AVTreeNode **next){
 
66
 *                 if(!*next) *next= av_mallocz(av_tree_node_size);
 
67
 *                 return av_tree_insert(rootp, key, cmp, next);
 
68
 *             }
 
69
 *             void *tree_remove(struct AVTreeNode **rootp, void *key, int (*cmp)(void *key, const void *b, AVTreeNode **next)){
 
70
 *                 if(*next) av_freep(next);
 
71
 *                 return av_tree_insert(rootp, key, cmp, next);
 
72
 *             }
49
73
 *
50
74
 * @return If no insertion happened, the found element.
51
 
 *         If an insertion happened, then either key or NULL will be returned.
 
75
 *         If an insertion or removial happened, then either key or NULL will be returned.
52
76
 *         Which one it is depends on the tree state and the implementation. You
53
77
 *         should make no assumptions that it's one or the other in the code.
54
78
 */
55
 
void *av_tree_insert(struct AVTreeNode **rootp, void *key, int (*cmp)(void *key, const void *b));
 
79
void *av_tree_insert(struct AVTreeNode **rootp, void *key, int (*cmp)(void *key, const void *b), struct AVTreeNode **next);
56
80
void av_tree_destroy(struct AVTreeNode *t);
57
81
 
58
 
#endif /* TREE_H */
 
82
#endif /* FFMPEG_TREE_H */