From fd926b3901c5d6d8e7d3942faf392af3e0422835 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sun, 2 Oct 2005 13:10:42 +0000 Subject: [PATCH] Added a single-linked double-ended list module. Mostly syntactic sugar. The SLIST_WALK_DELSAFE macro has well-defined semantics of the auxilliary variable: it's a pointer to the previous list item or to the list head, making it possible to delete the current item efficiently by calling slist_remove_after(). Unfortunately, I failed to write SLIST_FOR_EACH_DELSAFE, C syntax doesn't seem to be flexible enough for that. --- lib/Makefile | 5 +-- lib/slists.c | 83 ++++++++++++++++++++++++++++++++++++++++++++++++ lib/slists.h | 90 ++++++++++++++++++++++++++++++++++++++++++++++++++++ lib/slists.t | 4 +++ 4 files changed, 180 insertions(+), 2 deletions(-) create mode 100644 lib/slists.c create mode 100644 lib/slists.h create mode 100644 lib/slists.t diff --git a/lib/Makefile b/lib/Makefile index c785ee64..bf3ede45 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -9,7 +9,7 @@ endif LIBUCW_MODS= \ alloc alloc_str realloc mempool mempool-str mempool-fmt \ mmap pagecache partmap hashfunc \ - lists sorter bitsig kmp \ + lists slists sorter bitsig kmp \ log log-file proctitle \ conf ipaccess \ profile \ @@ -76,13 +76,14 @@ $(o)/lib/redblack-test: $(o)/lib/redblack-test.o $(LIBUCW) $(o)/lib/binheap-test: $(o)/lib/binheap-test.o $(LIBUCW) $(o)/lib/lizard-test: $(o)/lib/lizard-test.o $(LIBUCW) -TESTS+=$(addprefix $(o)/lib/,regex.test unicode-utf8.test hash-test.test mempool.test stkstring.test) +TESTS+=$(addprefix $(o)/lib/,regex.test unicode-utf8.test hash-test.test mempool.test stkstring.test slists.test) $(o)/lib/regex.test: $(o)/lib/regex-t $(o)/lib/unicode-utf8.test: $(o)/lib/unicode-utf8-t $(o)/lib/hash-test.test: $(o)/lib/hash-test $(o)/lib/mempool.test: $(o)/lib/mempool-fmt-t $(o)/lib/mempool-str-t $(o)/lib/stkstring.test: $(o)/lib/stkstring-t $(o)/lib/bitops.test: $(o)/lib/bit-ffs-t $(o)/lib/bit-fls-t +$(o)/lib/slists.test: $(o)/lib/slists-t INCLUDES+=$(o)/lib/.include-stamp $(o)/lib/.include-stamp: $(addprefix $(s)/lib/,$(LIBUCW_INCLUDES)) diff --git a/lib/slists.c b/lib/slists.c new file mode 100644 index 00000000..fffc64ec --- /dev/null +++ b/lib/slists.c @@ -0,0 +1,83 @@ +/* + * UCW Library -- Single-Linked Lists + * + * (c) 2005 Martin Mares + * + * This software may be freely distributed and used according to the terms + * of the GNU Lesser General Public License. + */ + +#include "lib/lib.h" +#include "lib/slists.h" + +static inline snode * +slist_raw_prev(slist *l, snode *n) +{ + snode *m = &l->head; + while (m) + { + if (n == m->next) + return m; + m = m->next; + } + ASSERT(0); +} + +void * +slist_prev(slist *l, snode *n) +{ + snode *p = slist_raw_prev(l, n); + return (p == &l->head) ? NULL : p; +} + +void +slist_insert_before(slist *l, snode *what, snode *before) +{ + what->next = before; + slist_raw_prev(l, before)->next = what; +} + +void +slist_remove(slist *l, snode *n) +{ + snode *p = slist_raw_prev(l, n); + slist_remove_after(l, p); +} + +#ifdef TEST + +#include +#include + +int main(void) +{ + slist l; + + struct x { + snode n; + int val; + }; + + slist_init(&l); + for (int i=1; i<=10; i++) + { + struct x *x = alloca(sizeof(*x)); + x->val = i; + if (i % 2) + slist_add_head(&l, &x->n); + else + slist_add_tail(&l, &x->n); + } + + struct x *x, *prev; + SLIST_WALK_DELSAFE(x, l, prev) + if (x->val == 5) + slist_remove_after(&l, &prev->n); + else if (x->val == 6) + slist_remove(&l, &x->n); + SLIST_FOR_EACH(struct x *, x, l) + printf("%d/", x->val); + putchar('\n'); +} + +#endif diff --git a/lib/slists.h b/lib/slists.h new file mode 100644 index 00000000..b0e9f4e2 --- /dev/null +++ b/lib/slists.h @@ -0,0 +1,90 @@ +/* + * UCW Library -- Single-Linked Lists + * + * (c) 2005 Martin Mares + * + * This software may be freely distributed and used according to the terms + * of the GNU Lesser General Public License. + */ + +#ifndef _UCW_SLISTS_H +#define _UCW_SLISTS_H + +typedef struct snode { + struct snode *next; +} snode; + +typedef struct slist { + struct snode head, *last; +} slist; + +static inline void *slist_head(slist *l) +{ + return l->head.next; +} + +static inline void *slist_tail(slist *l) +{ + return l->last; +} + +static inline void *slist_next(snode *n) +{ + return n->next; +} + +static inline int slist_empty(slist *l) +{ + return !l->head.next; +} + +#define SLIST_WALK(n,list) for(n=(void*)(list).head.next; (n); (n)=(void*)((snode*)(n))->next) +#define SLIST_WALK_DELSAFE(n,list,prev) for((prev)=(void*)&(list).head; (n)=(void*)((snode*)prev)->next; (prev)=(((snode*)(prev))->next==(snode*)(n) ? (void*)(n) : (void*)(prev))) +#define SLIST_FOR_EACH(type,n,list) for(type n=(void*)(list).head.next; n; n=(void*)((snode*)(n))->next) + +static inline void slist_insert_after(slist *l, snode *what, snode *after) +{ + what->next = after->next; + after->next = what; + if (!what->next) + l->last = what; +} + +static inline void slist_add_head(slist *l, snode *n) +{ + n->next = l->head.next; + l->head.next = n; + if (!l->last) + l->last = n; +} + +static inline void slist_add_tail(slist *l, snode *n) +{ + if (l->last) + l->last->next = n; + else + l->head.next = n; + n->next = NULL; + l->last = n; +} + +static inline void slist_init(slist *l) +{ + l->head.next = l->last = NULL; +} + +static inline void slist_remove_after(slist *l, snode *after) +{ + snode *n = after->next; + after->next = n->next; + if (l->last == n) + l->last = (after == &l->head) ? NULL : after; +} + +/* Non-trivial functions */ + +void *slist_prev(slist *l, snode *n); +void slist_insert_before(slist *l, snode *what, snode *before); +void slist_remove(slist *l, snode *n); + +#endif diff --git a/lib/slists.t b/lib/slists.t new file mode 100644 index 00000000..f18dc7ad --- /dev/null +++ b/lib/slists.t @@ -0,0 +1,4 @@ +# Test for slists module + +Run: obj/lib/slists-t +Out: 9/7/3/1/2/4/8/10/ -- 2.39.2