From 6924e47a8d1af9ed2d42709358802fbb43fff8d4 Mon Sep 17 00:00:00 2001 From: Lucas De Marchi Date: Tue, 22 Nov 2011 05:38:28 -0200 Subject: [PATCH] Implement circular double-linked list --- Makefile.am | 4 +- libkmod/libkmod-list.c | 153 ++++++++++++++++++++++++++++++++++++++++++++++ libkmod/libkmod-private.h | 15 +++++ libkmod/libkmod-util.h | 32 ++++++++++ libkmod/libkmod.h | 9 +-- 5 files changed, 208 insertions(+), 5 deletions(-) create mode 100644 libkmod/libkmod-list.c create mode 100644 libkmod/libkmod-util.h diff --git a/Makefile.am b/Makefile.am index f387cf8..57a1da3 100644 --- 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 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 + * + * 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 + +#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 24175f3..8208d94 100644 --- 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 index 0000000..81ccc99 --- /dev/null +++ b/libkmod/libkmod-util.h @@ -0,0 +1,32 @@ +#ifndef _LIBKMOD_UTIL_H_ +#define _LIBKMOD_UTIL_H_ + +#include + +#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 ff8c6a6..2f3006d 100644 --- 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" */ -- 2.7.4