[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