From 0eb1da8dd7fa3ae9d95e12df6058fb41a5ec1c11 Mon Sep 17 00:00:00 2001 From: Lukas Fleischer Date: Tue, 12 Apr 2011 19:10:50 +0200 Subject: Add linked lists implementation. As discussed on the mailing lists, the various linked list implementations we currently use at a dozen of different places in the calcurse source tree are inconvenient and should be replaced by a single generic solution. This is a first approach to introduce such a generic implemetation. It provides following functions: * llist_init(): Initialize a list. * llist_free_inner(): Loop through a list and free all items. * llist_free(): Free the list itself (but not the individual items). * llist_first(): Get the first item of a list. * llist_nth(): Get the nth item of a list. * llist_next(): Get the successor of a list item. * llist_find_first(): Find an item using a callback function. * llist_find_next(): Find the next match using a callback function. * llist_find_nth(): Find the nth item in a list (using a callback). * llist_get_data(): Get a pointer to the actual data of a list item. * llist_add(): Add an item at the end of a list. * llist_add_sorted(): Add an item to a sorted list (using a comparison callback function). * llist_remove(): Remove an item from a list. Linked lists are stored in "llist_t" structures, list items are to be stored in "llist_item_t" structs. All of the llist_*() functions either expect a pointer to a llist_t structure (in case the function operates on the list itself) or a pointer to a llist_item_t (llist_*_next() and llist_get_data()). Signed-off-by: Lukas Fleischer --- src/Makefile.am | 1 + src/calcurse.h | 1 + src/llist.c | 212 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/llist.h | 73 +++++++++++++++++++ 4 files changed, 287 insertions(+) create mode 100644 src/llist.c create mode 100644 src/llist.h (limited to 'src') diff --git a/src/Makefile.am b/src/Makefile.am index 787a8a7..e80c146 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -15,6 +15,7 @@ calcurse_SOURCES = \ help.c \ io.c \ keys.c \ + llist.c \ notify.c \ recur.c \ sigs.c \ diff --git a/src/calcurse.h b/src/calcurse.h index 916fc92..8c9d894 100644 --- a/src/calcurse.h +++ b/src/calcurse.h @@ -54,6 +54,7 @@ #include #include +#include "llist.h" #include "htable.h" /* Internationalization. */ diff --git a/src/llist.c b/src/llist.c new file mode 100644 index 0000000..021de82 --- /dev/null +++ b/src/llist.c @@ -0,0 +1,212 @@ +/* + * Calcurse - text-based organizer + * + * Copyright (c) 2004-2011 Frederic Culot + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above + * copyright notice, this list of conditions and the + * following disclaimer. + * + * - Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the + * following disclaimer in the documentation and/or other + * materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * + * Send your feedback or comments to : misc@calcurse.org + * Calcurse home page : http://calcurse.org + * + */ + +#include "calcurse.h" + +void +llist_init (llist_t *l) +{ + l->head = NULL; +} + +void +llist_free (llist_t *l) +{ + llist_item_t *i, *t; + + for (i = l->head; i; i = t) + { + t = i->next; + mem_free (i); + } +} + +void +llist_free_inner (llist_t *l, llist_fn_free_t fn_free) +{ + llist_item_t *i; + + for (i = l->head; i; i = i->next) + { + if (i->data) + fn_free(i->data); + } +} + +llist_item_t * +llist_first (llist_t *l) +{ + return l->head; +} + +llist_item_t * +llist_nth (llist_t *l, int n) +{ + llist_item_t *i; + + for (i = l->head; i && n > 0; n--) + i = i->next; + + return i; +} + +llist_item_t * +llist_next (llist_item_t *i) +{ + return i ? i->next : NULL; +} + +void * +llist_get_data (llist_item_t *i) +{ + return i ? i->data : NULL; +} + +void +llist_add (llist_t *l, void *data) +{ + llist_item_t *o = mem_malloc (sizeof (llist_item_t)); + llist_item_t *i; + + if (o) + { + o->data = data; + o->next = NULL; + + if (!l->head) + l->head = o; + else + { + for (i = l->head; i->next; i = i->next) + ; + i->next = o; + } + } +} + +void +llist_add_sorted (llist_t *l, void *data, llist_fn_cmp_t fn_cmp) +{ + llist_item_t *o = mem_malloc (sizeof (llist_item_t)); + llist_item_t *i; + + if (o) + { + o->data = data; + o->next = NULL; + + if (!l->head) + l->head = o; + else if (fn_cmp(o->data, l->head->data) <= 0) + { + o->next = l->head; + l->head = o; + } + else + { + i = l->head; + while (i->next && fn_cmp(o->data, i->next->data) > 0) + i = i->next; + o->next = i->next; + i->next = o; + } + } +} + +void +llist_remove (llist_t *l, llist_item_t *i) +{ + llist_item_t *j = NULL; + + if (l->head && i == l->head) + l->head = i->next; + else + { + for (j = l->head; j && j->next != i; j = j->next) + ; + } + + if (i) + { + if (j) + j->next = i->next; + mem_free (i); + } +} + +llist_item_t * +llist_find_first (llist_t *l, long data, llist_fn_match_t fn_match) +{ + llist_item_t *i; + + for (i = l->head; i; i = i->next) + { + if (fn_match (i->data, data)) + return i; + } + + return NULL; +} + +llist_item_t * +llist_find_next (llist_item_t *i, long data, llist_fn_match_t fn_match) +{ + if (i) + { + i = i->next; + for (; i; i = i->next) + { + if (fn_match (i->data, data)) + return i; + } + } + + return NULL; +} + +llist_item_t * +llist_find_nth (llist_t *l, int n, long data, llist_fn_match_t fn_match) +{ + llist_item_t *i; + + for (i = l->head; i; i = i->next) + { + if (fn_match (i->data, data) && (n-- == 0)) + return i; + } + + return NULL; +} diff --git a/src/llist.h b/src/llist.h new file mode 100644 index 0000000..c13761d --- /dev/null +++ b/src/llist.h @@ -0,0 +1,73 @@ +/* + * Calcurse - text-based organizer + * + * Copyright (c) 2004-2011 Frederic Culot + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above + * copyright notice, this list of conditions and the + * following disclaimer. + * + * - Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the + * following disclaimer in the documentation and/or other + * materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * + * Send your feedback or comments to : misc@calcurse.org + * Calcurse home page : http://calcurse.org + * + */ + +/* Linked lists. */ +typedef struct llist_item llist_item_t; +struct llist_item { + struct llist_item *next; + void *data; +}; + +typedef struct llist llist_t; +struct llist { + struct llist_item *head; +}; + +typedef int (*llist_fn_cmp_t) (void *, void *); +typedef int (*llist_fn_match_t) (void *, long); +typedef void (*llist_fn_free_t) (void *); + +/* Initialization and deallocation. */ +void llist_init (llist_t *); +void llist_free (llist_t *); +void llist_free_inner (llist_t *, llist_fn_free_t); + +/* Retrieving list items. */ +llist_item_t *llist_first (llist_t *); +llist_item_t *llist_nth (llist_t *, int); +llist_item_t *llist_next (llist_item_t *); +llist_item_t *llist_find_first (llist_t *, long, llist_fn_match_t); +llist_item_t *llist_find_next (llist_item_t *, long, llist_fn_match_t); +llist_item_t *llist_find_nth (llist_t *, int, long, llist_fn_match_t); + +/* Accessing list item data. */ +void *llist_get_data (llist_item_t *); + +/* List manipulation. */ +void llist_add (llist_t *, void *); +void llist_add_sorted (llist_t *, void *, llist_fn_cmp_t); +void llist_remove (llist_t *, llist_item_t *); + -- cgit v1.2.3-70-g09d2