[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