diff options
| -rw-r--r-- | libavformat/nut.c | 9 | ||||
| -rw-r--r-- | libavutil/tree.c | 8 | ||||
| -rw-r--r-- | libavutil/tree.h | 12 |
3 files changed, 22 insertions, 7 deletions
diff --git a/libavformat/nut.c b/libavformat/nut.c index 7eb53136d5..546bde1cd0 100644 --- a/libavformat/nut.c +++ b/libavformat/nut.c @@ -48,12 +48,15 @@ int ff_nut_sp_pts_cmp(syncpoint_t *a, syncpoint_t *b){ } void ff_nut_add_sp(NUTContext *nut, int64_t pos, int64_t back_ptr, int64_t ts){ - syncpoint_t *sp2, *sp= av_mallocz(sizeof(syncpoint_t)); + syncpoint_t *sp= av_mallocz(sizeof(syncpoint_t)); + struct AVTreeNode *node= av_mallocz(av_tree_node_size); sp->pos= pos; sp->back_ptr= back_ptr; sp->ts= ts; - sp2= av_tree_insert(&nut->syncpoints, sp, ff_nut_sp_pos_cmp); - if(sp2 && sp2 != sp) + av_tree_insert(&nut->syncpoints, sp, ff_nut_sp_pos_cmp, &node); + if(node){ av_free(sp); + av_free(node); + } } 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 */ |