aboutsummaryrefslogtreecommitdiffstats
path: root/libavutil
diff options
context:
space:
mode:
authorMichael Niedermayer <michaelni@gmx.at>2008-01-04 17:52:16 +0000
committerMichael Niedermayer <michaelni@gmx.at>2008-01-04 17:52:16 +0000
commit6e8b982bcc1ff1b647b28d70a5900ed1bb41e52a (patch)
tree1e8972327b9f47d04444ada6d95d88412280a0d0 /libavutil
parentf1917274cc900a1d29879117a1bfbc74ac44f88a (diff)
downloadffmpeg-6e8b982bcc1ff1b647b28d70a5900ed1bb41e52a.tar.gz
Move *malloc() out of tree.c, that way the code can be used with
flat arrays which have lower overhead than millions of mallocd() elements. Originally committed as revision 11399 to svn://svn.ffmpeg.org/ffmpeg/trunk
Diffstat (limited to 'libavutil')
-rw-r--r--libavutil/tree.c8
-rw-r--r--libavutil/tree.h12
2 files changed, 16 insertions, 4 deletions
diff --git a/libavutil/tree.c b/libavutil/tree.c
index 6126ffaaa4..5c4f510db8 100644
--- a/libavutil/tree.c
+++ b/libavutil/tree.c
@@ -28,6 +28,8 @@ typedef struct AVTreeNode{
int state;
}AVTreeNode;
+const int av_tree_node_size = sizeof(AVTreeNode);
+
void *av_tree_find(const AVTreeNode *t, void *key, int (*cmp)(void *key, const void *b), void *next[2]){
if(t){
unsigned int v= cmp(t->elem, key);
@@ -45,14 +47,14 @@ void *av_tree_find(const AVTreeNode *t, void *key, int (*cmp)(void *key, const v
return NULL;
}
-void *av_tree_insert(AVTreeNode **tp, void *key, int (*cmp)(void *key, const void *b)){
+void *av_tree_insert(AVTreeNode **tp, void *key, int (*cmp)(void *key, const void *b), AVTreeNode **next){
AVTreeNode *t= *tp;
if(t){
unsigned int v= cmp(t->elem, key);
if(v){
int i= v>>31;
AVTreeNode **child= &t->child[i];
- void *ret= av_tree_insert(child, key, cmp);
+ void *ret= av_tree_insert(child, key, cmp, next);
if(!ret){
t->state -= ((int)v>>31)|1;
if(!(t->state&1)){
@@ -83,7 +85,7 @@ void *av_tree_insert(AVTreeNode **tp, void *key, int (*cmp)(void *key, const voi
return t->elem;
}
}else{
- *tp= av_mallocz(sizeof(AVTreeNode));
+ *tp= *next; *next= NULL;
(*tp)->elem= key;
return NULL;
}
diff --git a/libavutil/tree.h b/libavutil/tree.h
index 146d35d56e..d801a4e028 100644
--- a/libavutil/tree.h
+++ b/libavutil/tree.h
@@ -28,6 +28,7 @@
#define FFMPEG_TREE_H
struct AVTreeNode;
+extern const int av_tree_node_size;
/**
* Finds an element.
@@ -46,13 +47,22 @@ void *av_tree_find(const struct AVTreeNode *root, void *key, int (*cmp)(void *ke
* @param rootp A pointer to a pointer to the root node of the tree. Note that
* the root node can change during insertions, this is required
* to keep the tree balanced.
+ * @param next AVTreeNode used for the inserted element, must be allocated and
+ * zeroed by the user. And will be set to NULL if used by
+ * av_tree_insert(). This allows the use of flat arrays, which have
+ * lower overhead compared to many malloced elements.
+ * You might want to define a function like:
+ * void *tree_insert(struct AVTreeNode **rootp, void *key, int (*cmp)(void *key, const void *b), AVTreeNode **next){
+ * if(!*next) *next= av_mallocz(av_tree_node_size);
+ * return av_tree_insert(rootp, key, cmp, next);
+ * }
*
* @return If no insertion happened, the found element.
* If an insertion happened, then either key or NULL will be returned.
* Which one it is depends on the tree state and the implementation. You
* should make no assumptions that it's one or the other in the code.
*/
-void *av_tree_insert(struct AVTreeNode **rootp, void *key, int (*cmp)(void *key, const void *b));
+void *av_tree_insert(struct AVTreeNode **rootp, void *key, int (*cmp)(void *key, const void *b), struct AVTreeNode **next);
void av_tree_destroy(struct AVTreeNode *t);
#endif /* FFMPEG_TREE_H */