Implement circular double-linked list

diff --git a/Makefile.am b/Makefile.am
index f387cf899fe0e49476f9aaa41738abb11bd20d16..57a1da3c23c87e9246863364dc485e7d73f80945 100644 (file)
--- a/Makefile.am
+++ b/Makefile.am
@@ -29,7 +29,9 @@ lib_LTLIBRARIES = libkmod/libkmod.la
 libkmod_libkmod_la_SOURCES =\
        libkmod/libkmod.h \
        libkmod/libkmod-private.h \
-       libkmod/libkmod.c
+       libkmod/libkmod-util.h \
+       libkmod/libkmod.c \
+       libkmod/libkmod-list.c
 
 EXTRA_DIST += libkmod/libkmod.sym
 

diff --git a/libkmod/libkmod-list.c b/libkmod/libkmod-list.c
new file mode 100644 (file)
index 0000000..b7673c4
--- /dev/null
+++ b/libkmod/libkmod-list.c
@@ -0,0 +1,153 @@
+/*
+ * libkmod - interface to kernel module operations
+ *
+ * Copyright (C) 2011  ProFUSION embedded systems
+ * Copyright (C) 2011  Lucas De Marchi <lucas.de.marchi@gmail.com>
+ *
+ * This library 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 version 2.1.
+ *
+ * This library 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 this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
+ */
+
+#include <stdlib.h>
+
+#include "libkmod.h"
+#include "libkmod-private.h"
+#include "libkmod-util.h"
+
+static inline struct list_node *list_node_init(struct list_node *node)
+{
+       node->next = node;
+       node->prev = node;
+
+       return node;
+}
+
+static inline struct list_node *list_node_next(struct list_node *node)
+{
+       if (node == NULL)
+               return NULL;
+
+       return node->next;
+}
+
+static inline struct list_node *list_node_prev(struct list_node *node)
+{
+       if (node == NULL)
+               return NULL;
+
+       return node->prev;
+}
+
+static inline void list_node_append(struct list_node *list,
+                                                       struct list_node *node)
+{
+       if (list == NULL) {
+               list_node_init(node);
+               return;
+       }
+
+       node->prev = list->prev;
+       list->prev->next = node;
+       list->prev = node;
+       node->next = list;
+}
+
+static inline struct list_node *list_node_remove(struct list_node *node)
+{
+       if (node->prev == node || node->next == node)
+               return NULL;
+
+       node->prev->next = node->next;
+       node->next->prev = node->prev;
+
+       return node->prev;
+}
+
+struct kmod_list *kmod_list_append(struct kmod_list *list, void *data)
+{
+       struct kmod_list *new;
+
+       new = malloc(sizeof(*new));
+       if (new == NULL)
+               return NULL;
+
+       new->data = data;
+       list_node_append(list ? &list->node : NULL, &new->node);
+
+       return list ? list : new;
+}
+
+struct kmod_list *kmod_list_prepend(struct kmod_list *list, void *data)
+{
+       struct kmod_list *new;
+
+       new = malloc(sizeof(*new));
+       if (new == NULL)
+               return NULL;
+
+       new->data = data;
+       list_node_append(list ? &list->node : NULL, &new->node);
+
+       return new;
+}
+
+struct kmod_list *kmod_list_remove(struct kmod_list *list)
+{
+       struct list_node *node;
+
+       if (list == NULL)
+               return NULL;
+
+       node = list_node_remove(&list->node);
+       free(list);
+
+       if (node == NULL)
+               return NULL;
+
+       return container_of(node, struct kmod_list, node);
+}
+
+struct kmod_list *kmod_list_remove_data(struct kmod_list *list,
+                                                       const void *data)
+{
+       struct kmod_list *itr;
+       struct list_node *node;
+
+       for (itr = list; itr != NULL; itr = kmod_list_next(list, itr)) {
+               if (itr->data == data)
+                       break;
+       }
+
+       if (itr == NULL)
+               return list;
+
+       node = list_node_remove(&itr->node);
+       free(itr);
+
+       if (node == NULL)
+               return NULL;
+
+       return container_of(node, struct kmod_list, node);
+}
+
+KMOD_EXPORT struct kmod_list *kmod_list_next(struct kmod_list *list,
+                                                       struct kmod_list *curr)
+{
+       if (list == NULL || curr == NULL)
+               return NULL;
+
+       if (curr->node.next == &list->node)
+               return NULL;
+
+       return container_of(curr->node.next, struct kmod_list, node);
+}

diff --git a/libkmod/libkmod-private.h b/libkmod/libkmod-private.h
index 24175f3c9b5f9e0c9349f591b7ff9bbbee7bce54..8208d94cf8ad6a00460f7add49b02a44af249acb 100644 (file)
--- a/libkmod/libkmod-private.h
+++ b/libkmod/libkmod-private.h
@@ -35,4 +35,19 @@ void kmod_log(struct kmod_ctx *ctx,
                int priority, const char *file, int line, const char *fn,
                const char *format, ...) __attribute__((format(printf, 6, 7)));
 
+struct list_node {
+       struct list_node *next, *prev;
+};
+
+struct kmod_list {
+       struct list_node node;
+       void *data;
+};
+
+struct kmod_list *kmod_list_append(struct kmod_list *list, void *data);
+struct kmod_list *kmod_list_prepend(struct kmod_list *list, void *data);
+struct kmod_list *kmod_list_remove(struct kmod_list *list);
+struct kmod_list *kmod_list_remove_data(struct kmod_list *list,
+                                                       const void *data);
+
 #endif

diff --git a/libkmod/libkmod-util.h b/libkmod/libkmod-util.h
new file mode 100644 (file)
index 0000000..81ccc99
--- /dev/null
+++ b/libkmod/libkmod-util.h
@@ -0,0 +1,32 @@
+#ifndef _LIBKMOD_UTIL_H_
+#define _LIBKMOD_UTIL_H_
+
+#include <stddef.h>
+
+#define BUILD_ASSERT(cond) \
+       do { (void) sizeof(char [1 - 2*!(cond)]); } while(0)
+
+#define EXPR_BUILD_ASSERT(cond) \
+       (sizeof(char [1 - 2*!(cond)]) - 1)
+
+#if HAVE_TYPEOF
+#define check_type(expr, type)                 \
+       ((typeof(expr) *)0 != (type *)0)
+
+#define check_types_match(expr1, expr2)                \
+       ((typeof(expr1) *)0 != (typeof(expr2) *)0)
+#else
+/* Without typeof, we can only test the sizes. */
+#define check_type(expr, type)                                 \
+       EXPR_BUILD_ASSERT(sizeof(expr) == sizeof(type))
+
+#define check_types_match(expr1, expr2)                                \
+       EXPR_BUILD_ASSERT(sizeof(expr1) == sizeof(expr2))
+#endif /* HAVE_TYPEOF */
+
+#define container_of(member_ptr, containing_type, member)              \
+       ((containing_type *)                                            \
+        ((char *)(member_ptr) - offsetof(containing_type, member))     \
+        - check_types_match(*(member_ptr), ((containing_type *)0)->member))
+
+#endif

diff --git a/libkmod/libkmod.h b/libkmod/libkmod.h
index ff8c6a68b8f8094e629f7e73fcd9ff7b5be1a387..2f3006dd89769a88939c675dc9cb6950030adbae 100644 (file)
--- a/libkmod/libkmod.h
+++ b/libkmod/libkmod.h
@@ -52,12 +52,13 @@ void kmod_set_userdata(struct kmod_ctx *ctx, void *userdata);
  *
  * access to kmod generated lists
  */
-struct kmod_list_entry;
-struct kmod_list_entry *kmod_list_entry_get_next(struct kmod_list_entry *list_entry);
-#define kmod_list_entry_foreach(list_entry, first_entry) \
+struct kmod_list;
+struct kmod_list *kmod_list_next(struct kmod_list *first_entry,
+                                               struct kmod_list *list_entry);
+#define kmod_list_foreach(list_entry, first_entry) \
        for (list_entry = first_entry; \
                list_entry != NULL; \
-               list_entry = kmod_list_entry_get_next(list_entry))
+               list_entry = kmod_list_next(first_entry, list_entry))
 
 #ifdef __cplusplus
 } /* extern "C" */