[FFmpeg-devel] [PATCH] lavu: add a linked list API.
Nicolas George
nicolas.george at normalesup.org
Sun Jul 21 23:11:52 CEST 2013
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
More information about the ffmpeg-devel
mailing list