From 049ff67817e0db5afbba30930531d8ea3f7f2d18 Mon Sep 17 00:00:00 2001 From: Guus Sliepen Date: Sun, 7 Jan 2001 15:24:52 +0000 Subject: [PATCH] - Changed list routines to give it the same look'n'feel as the rbl and avl tree library. --- lib/list.c | 216 ++++++++++++++++++++++++++++++++--------------------- lib/list.h | 58 +++++++++++--- 2 files changed, 178 insertions(+), 96 deletions(-) diff --git a/lib/list.c b/lib/list.c index f509e216..d317622d 100644 --- a/lib/list.c +++ b/lib/list.c @@ -17,127 +17,175 @@ along with this program; if not, write to the Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. - $Id: list.c,v 1.1.2.6 2000/11/22 23:09:38 guus Exp $ + $Id: list.c,v 1.1.2.7 2001/01/07 15:24:52 guus Exp $ */ #include "config.h" #include -#include -#include -#include #include - #include -/* - list_new +#include "list.h" - Initialize a new list. -*/ -list_t *list_new(void) +/* (De)constructors */ + +list_t *list_alloc(list_action_t delete) { list_t *list; list = xmalloc_and_zero(sizeof(list_t)); + list->delete = delete; + return list; } -/* - list_delete +void list_free(list_t *list) +{ + free(list); +} - Delete the element pointed to by idx from the list. -*/ -void list_delete(list_t *list, list_node_t *idx) +list_node_t *list_alloc_node(void) { - if(!list || !idx) - return; + list_node_t *node; + + node = xmalloc_and_zero(sizeof(list_node_t)); + + return node; +} - if(list->callbacks->delete != NULL) - if(list->callbacks->delete(idx->data)) - syslog(LOG_WARNING, _("List callback[delete] failed for %08lx - freeing anyway"), idx->data); +void list_free_node(list_t *list, list_node_t *node) +{ + if(node->data && list->delete) + list->delete(node->data); - free(idx->data); + free(node->data); +} + +/* Insertion and deletion */ + +list_node_t *list_insert_head(list_t *list, void *data) +{ + list_node_t *node; - if(idx->prev == NULL) - /* First element in list */ - { - list->head = idx->next; - } - if(idx->next == NULL) - /* Last element in list */ - { - list->tail = idx->prev; - } - if(idx->prev != NULL && idx->next != NULL) - /* Neither first nor last element */ - { - idx->prev->next = idx->next; - idx->next->prev = idx->prev; - } - if(list->head == NULL) - list->tail = NULL; + node = list_alloc_node(); + + node->data = data; + node->prev = NULL; + node->next = list->head; + list->head = node; + + if(node->next) + node->next->prev = node; else - if(list->tail == NULL) - list->head = NULL; + list->tail = node; - free(idx); + return node; } -/* - list_forall_nodes +list_node_t *list_insert_tail(list_t *list, void *data) +{ + list_node_t *node; + + node = list_alloc_node(); + + node->data = data; + node->next = NULL; + node->prev = list->tail; + list->tail = node; + + if(node->prev) + node->prev->next = node; + else + list->head = node; - Call function() on each element in the list. If this function - returns non-zero, the element will be removed from the list. -*/ -void list_forall_nodes(list_t *list, int (*function)(void *data)) + return node; +} + +void list_unlink_node(list_t *list, list_node_t *node) { - list_node_t *p, *next; - int res; + if(node->prev) + node->prev->next = node->next; + else + list->head = node->next; + + if(node->next) + node->next->prev = node->prev; + else + list->tail = node->prev; +} + +void list_delete_node(list_t *list, list_node_t *node) +{ + list_unlink_node(list, node); + list_free_node(list, node); +} + +void list_delete_head(list_t *list) +{ + list_delete_node(list, list->head); +} + +void list_delete_tail(list_t *list) +{ + list_delete_node(list, list->tail); +} + +/* Head/tail lookup */ + +void *list_get_head(list_t *list) +{ + if(list->head) + return list->head->data; + else + return NULL; +} + +void *list_get_tail(list_t *list) +{ + if(list->tail) + return list->tail->data; + else + return NULL; +} + +/* Fast list deletion */ + +void list_delete_list(list_t *list) +{ + list_node_t *node, *next; - if(!list) /* no list given */ - return; - if(!function) /* no function given */ - return; - if(!list->head) /* list is empty */ - return; - for(p = list->head; p != NULL; p = next) + for(node = list->head; node; node = next) { - next = p->next; - res = function(p->data); - if(res != 0) - list_delete(list, p); + next = node->next; + list_free_node(list, node); } + + list_free(list); } -/* - list_destroy +/* Traversing */ - Free all datastructures contained in this list. It uses the delete - callback for this list to free each element. -*/ -void list_destroy(list_t *list) +void list_foreach_node(list_t *list, list_action_node_t action) { - if(!list) - return; -/* list_destroy_nodes(list); */ - free(list); -} + list_node_t *node, *next; -/* - list_append + for(node = list->head; node; node = next) + { + next = node->next; + action(node); + } +} - Append a new node to the list that points to data. -*/ -void list_append(list_t *list, void *data) +void list_foreach(list_t *list, list_action_t action) { - list_node_t *n; + list_node_t *node, *next; - n = xmalloc_and_zero(sizeof(list_node_t)); - n->data = data; - n->prev = list->tail; - if(list->tail) - list->tail->next = n; - list->tail = n; + for(node = list->head; node; node = next) + { + next = node->next; + if(node->data) + action(node->data); + } } diff --git a/lib/list.h b/lib/list.h index 86e17e62..960a9091 100644 --- a/lib/list.h +++ b/lib/list.h @@ -17,31 +17,65 @@ along with this program; if not, write to the Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. - $Id: list.h,v 1.1.2.2 2000/11/16 22:13:09 zarq Exp $ + $Id: list.h,v 1.1.2.3 2001/01/07 15:24:52 guus Exp $ */ #ifndef __TINC_LIST_H__ #define __TINC_LIST_H__ -typedef struct list_callbacks_t { - int (*delete) (void *); -} list_callbacks_t; - -typedef struct list_node_t { - void *data; +typedef struct list_node_t +{ struct list_node_t *prev; struct list_node_t *next; + + /* Payload */ + + void *data; } list_node_t; -typedef struct list_t { +typedef void (*list_action_t) (const void *); +typedef void (*list_action_node_t) (const list_node_t *); + +typedef struct list_t +{ list_node_t *head; list_node_t *tail; - list_callbacks_t *callbacks; + + /* Callbacks */ + + list_action_t delete; } list_t; -extern list_t *list_new(void); -extern void list_append(list_t *, void *); -extern void list_forall_nodes(list_t *, int (*)(void *)); +/* (De)constructors */ + +extern list_t *list_alloc(list_action_t); +extern void list_free(list_t *); +extern list_node_t *list_alloc_node(void); +extern void list_free_node(list_t *, list_node_t *); + +/* Insertion and deletion */ + +extern list_node_t *list_insert_head(list_t *, void *); +extern list_node_t *list_insert_tail(list_t *, void *); + +extern void list_unlink_node(list_t *, list_node_t *); +extern void list_delete_node(list_t *, list_node_t *); + +extern void list_delete_head(list_t *); +extern void list_delete_tail(list_t *); + +/* Head/tail lookup */ + +extern void *list_get_head(list_t *); +extern void *list_get_tail(list_t *); + +/* Fast list deletion */ + +extern void list_delete_list(list_t *); + +/* Traversing */ +extern void list_foreach(list_t *, list_action_t); +extern void list_foreach_node(list_t *, list_action_node_t); #endif /* __TINC_LIST_H__ */ -- 2.39.5