[FFmpeg-devel] [PATCH] lavu: add a linked list API.

Paul B Mahol onemda at gmail.com
Mon Jul 22 14:03:43 CEST 2013


On 7/21/13, Nicolas George <nicolas.george at normalesup.org> wrote:
>
> Signed-off-by: Nicolas George <nicolas.george at normalesup.org>
> ---
>  libavutil/Makefile      |    1 +
>  libavutil/linked_list.c |   72 ++++++++++++++++
>  libavutil/linked_list.h |  212
> +++++++++++++++++++++++++++++++++++++++++++++++
>  3 files changed, 285 insertions(+)
>  create mode 100644 libavutil/linked_list.c
>  create mode 100644 libavutil/linked_list.h
>
>
> This is not completely filanized, but I am rather satisfied with it. I
> believe it would be nice to have this kind of API, there are a few places
> that could benefit from it. And since it is only a header, it is basically
> free at the code level.
>
> Anyway, I post it so it does not get lost.
>
>
> diff --git a/libavutil/Makefile b/libavutil/Makefile
> index 21746f0..1a21cf9 100644
> --- a/libavutil/Makefile
> +++ b/libavutil/Makefile
> @@ -142,6 +142,7 @@ TESTPROGS = adler32
>                \
>              fifo                                                        \
>              hmac                                                        \
>              lfg                                                         \
> +            linked_list                                                 \
>              lls                                                         \
>              md5                                                         \
>              murmur3                                                     \
> diff --git a/libavutil/linked_list.c b/libavutil/linked_list.c
> new file mode 100644
> index 0000000..c9bf1af
> --- /dev/null
> +++ b/libavutil/linked_list.c
> @@ -0,0 +1,72 @@
> +/*
> + * Copyright (c) Nicolas George
> + *
> + * This file is part of FFmpeg.
> + *
> + * FFmpeg is free software; you can redistribute it and/or
> + * modify it under the terms of the GNU Lesser General Public License
> + * as published by the Free Software Foundation; either
> + * version 2.1 of the License, or (at your option) any later version.
> + *
> + * FFmpeg is distributed in the hope that it will be useful,
> + * but WITHOUT ANY WARRANTY; without even the implied warranty of
> + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
> + * GNU Lesser General Public License for more details.
> + *
> + * You should have received a copy of the GNU Lesser General Public
> License
> + * along with FFmpeg; if not, write to the Free Software Foundation, Inc.,
> + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
> + */
> +
> +#include "linked_list.h"
> +#include "mem.h"
> +
> +typedef struct {
> +    char label[64];
> +    AVListHead lh;
> +    int uid;
> +} Test;
> +
> +av_list_make(test, Test, lh);
> +
> +static void dump_list(AVListHead *list)
> +{
> +    Test *t;
> +
> +    for (t = test_first(list); t; t = test_next(list, t))
> +        printf("  [%04x] %s\n", t->uid, t->label);
> +}
> +
> +int main(void)
> +{
> +    AVListHead list = av_list_init(list);
> +    Test *t, *t2;
> +    unsigned i;
> +
> +    for (i = 0; i < 12; i++) {
> +        t = av_malloc(sizeof(*t));
> +        if (!t)
> +            abort();
> +        snprintf(t->label, sizeof(t->label), "List item #%d", i);
> +        t->uid = i * 3 + 5;
> +        test_append(&list, t);
> +    }
> +
> +    /* move #3 after #6 */
> +    t = test_first(&list);
> +    for (i = 0; i < 3; i++)
> +        t = test_next(&list, t);
> +    t2 = t;
> +    for (; i < 6; i++)
> +        t2 = test_next(&list, t2);
> +    test_remove(t);
> +    test_insert_after(t2, t);
> +
> +    dump_list(&list);
> +    for (t = test_first(&list); t; t = t2) {
> +        t2 = test_next (&list, t);
> +        test_remove(t);
> +        av_free(t);
> +    }
> +    return 0;
> +}
> diff --git a/libavutil/linked_list.h b/libavutil/linked_list.h
> new file mode 100644
> index 0000000..b830146
> --- /dev/null
> +++ b/libavutil/linked_list.h
> @@ -0,0 +1,212 @@
> +/*
> + * Copyright (c) the FFMpeg developers
> + *
> + * This file is part of FFmpeg.
> + *
> + * FFmpeg is free software; you can redistribute it and/or
> + * modify it under the terms of the GNU Lesser General Public License
> + * as published by the Free Software Foundation; either
> + * version 2.1 of the License, or (at your option) any later version.
> + *
> + * FFmpeg is distributed in the hope that it will be useful,
> + * but WITHOUT ANY WARRANTY; without even the implied warranty of
> + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
> + * GNU Lesser General Public License for more details.
> + *
> + * You should have received a copy of the GNU Lesser General Public
> License
> + * along with FFmpeg; if not, write to the Free Software Foundation, Inc.,
> + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
> + */
> +
> +#ifndef AVUTIL_LINKED_LIST_H
> +#define AVUTIL_LINKED_LIST_H
> +
> +#include <stddef.h>
> +
> +/**
> + * Generic doubly linked list API.
> + *
> + * This structure has a double use:
> + *
> + * 1. As a field in a structure, it allows to build a linked list of
> + *    instances of the structure. There are no constraints on the field
> + *    containing the list head; in particular it does not need to be the
> + *    first member of the structure. A structure can contain several list
> + *    heads, and therefore be part of several lists independently.
> + *
> + * 2. As a stand-alone variable (or member of anything), it points to a
> list
> + *    of items; this is known as a sentinel node using a circular list.
> + *
> + * These uses will be referred as "local list head" and "global list head"
> + * respectively.
> + */
> +typedef struct AVListHead AVListHead;
> +struct AVListHead {
> +    AVListHead *next;
> +    AVListHead *prev;
> +};
> +
> +/**
> + * Initializer for an empty list.
> + */
> +#define av_list_init(head) \
> +    { &head, &head }
> +
> +/**
> + * Make a global list head point to an empty list.
> + */
> +static inline void av_list_clear(AVListHead *head)
> +{
> +    head->next = head->prev = head;
> +}
> +
> +/**
> + * Get the item containing a local list head.
> + *
> + * @param type   type of the item structure
> + * @param field  field of the item structure containing the local list
> head
> + * @param head   pointer to the local list head
> + * @note  This macro should probably not be used directly.
> + */
> +#define av_list_head_to_item(type, field, head) \
> +        (type *)((char *)(head) - offsetof(type, field))
> +
> +/**
> + * Get the first or last item of a list (generic macro for internal use)
> + */
> +#define av_list_enditem(type, field, dirf, list) \
> +    ((list)->dirf == (list) ? NULL : \
> +     av_list_head_to_item(type, field, (list)->dirf))
> +
> +/**
> + * Insert newh between prev and next.
> + */
> +static inline void av_list_insert_head(AVListHead *prev, AVListHead *next,
> +                                       AVListHead *newh)
> +{
> +    prev->next = next->prev = newh;
> +    newh->prev = prev;
> +    newh->next = next;
> +}
> +
> +/**
> + * Remove delh from a list.
> + */
> +static inline void av_list_remove_head(AVListHead *delh)
> +{
> +    delh->prev->next = delh->next;
> +    delh->next->prev = delh->prev;
> +    delh->prev = delh->next = NULL;
> +}
> +
> +#define av_list_make(prefix, type, field)
>   \
> +
>   \
> +/**
>   \
> + * Get the first item pointed by a global list head, NULL if empty.
>   \
> + */
>   \
> +static inline type *prefix ## _first(AVListHead *list)
>   \
> +{
>   \
> +    return av_list_enditem(type, field, next, list);
>   \
> +}
>   \
> +
>   \
> +/**
>   \
> + * Get the last item pointed by a global list head, NULL if empty.
>   \
> + */
>   \
> +static inline type *prefix ## _last(AVListHead *list)
>   \
> +{
>   \
> +    return av_list_enditem(type, field, prev, list);
>   \
> +}
>   \
> +
>   \
> +/**
>   \
> + * Test whether an item is the last in the list.
>   \
> + */
>   \
> +static inline int prefix ## _is_last(AVListHead *list, type *item)
>   \
> +{
>   \
> +    return item->field.next == list;
>   \
> +}
>   \
> +
>   \
> +/**
>   \
> + * Test whether an item is the first in the list.
>   \
> + */
>   \
> +static inline int prefix ## _is_first(AVListHead *list, type *item)
>   \
> +{
>   \
> +    return item->field.prev == list;
>   \
> +}
>   \
> +
>   \
> +/**
>   \
> + * Get the next item in a circular list.
>   \
> + */
>   \
> +static inline type *prefix ## _circ_next(type *item)
>   \
> +{
>   \
> +    return av_list_head_to_item(type, field, item->field.next);
>   \
> +}
>   \
> +
>   \
> +/**
>   \
> + * Get the previous item in a circular list.
>   \
> + */
>   \
> +static inline type *prefix ## _circ_prev(type *item)
>   \
> +{
>   \
> +    return av_list_head_to_item(type, field, item->field.prev);
>   \
> +}
>   \
> +
>   \
> +/**
>   \
> + * Get the next item in a list, or NULL if it was the last.
>   \
> + */
>   \
> +static inline type *prefix ## _next(AVListHead *list, type *item)
>   \
> +{
>   \
> +    return prefix ## _is_last(list, item) ? NULL :
>   \
> +           prefix ## _circ_next(item);
>   \
> +}
>   \
> +
>   \
> +/**
>   \
> + * Get the previous item in a list, or NULL if it was the first.
>   \
> + */
>   \
> +static inline type *prefix ## _prev(AVListHead *list, type *item)
>   \
> +{
>   \
> +    return prefix ## _is_first(list, item) ? NULL :
>   \
> +           prefix ## _circ_prev(item);
>   \
> +}
>   \
> +
>   \
> +/**
>   \
> + * Insert new_item at the end of a list
>   \
> + */
>   \
> +static inline void prefix ## _append(AVListHead *list, type *new_item)
>   \
> +{
>   \
> +    av_list_insert_head(list->prev, list, &new_item->field);
>   \
> +}
>   \
> +
>   \
> +/**
>   \
> + * Insert new_item at the beginning of a list
>   \
> + */
>   \
> +static inline void prefix ## _prepend(AVListHead *list, type *new_item)
>   \
> +{
>   \
> +    av_list_insert_head(list, list->next, &new_item->field);
>   \
> +}
>   \
> +
>   \
> +/**
>   \
> + * Insert new_item after old_item.
>   \
> + */
>   \
> +static inline void prefix ## _insert_after(type *old_item, type *new_item)
>   \
> +{
>   \
> +    av_list_insert_head(&old_item->field, old_item->field.next,
>   \
> +                        &new_item->field);
>   \
> +}
>   \
> +
>   \
> +/**
>   \
> + * Insert new_item after old_item.
>   \
> + */
>   \
> +static inline void prefix ## _insert_before(type *old_item, type *new_item)
>   \
> +{
>   \
> +    av_list_insert_head(old_item->field.prev, &old_item->field,
>   \
> +                        &new_item->field);
>   \
> +}
>   \
> +
>   \
> +/**
>   \
> + * Remove item from a list.
>   \
> + */
>   \
> +static inline void prefix ## _remove(type *item)
>   \
> +{
>   \
> +    av_list_remove_head(&item->field);
>   \
> +}
>   \
> +
> +#endif /* AVUTIL_LINKED_LIST_H */
> --
> 1.7.10.4
>
> _______________________________________________
> ffmpeg-devel mailing list
> ffmpeg-devel at ffmpeg.org
> http://ffmpeg.org/mailman/listinfo/ffmpeg-devel
>

I'm more interested in list of items for AVOption.


More information about the ffmpeg-devel mailing list