From 4325c036fca0264d64212c6c837616387818d752 Mon Sep 17 00:00:00 2001 From: Dimitri Sokolyuk Date: Thu, 13 Nov 2008 16:34:47 +0000 Subject: BSD Lists macros --- LICENSE | 1 + Makefile | 22 +++++++++++++ circleq.c | 105 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ list.c | 88 ++++++++++++++++++++++++++++++++++++++++++++++++++++ simpleq.c | 91 +++++++++++++++++++++++++++++++++++++++++++++++++++++ slist.c | 90 +++++++++++++++++++++++++++++++++++++++++++++++++++++ tailq.c | 104 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 7 files changed, 501 insertions(+) create mode 100644 LICENSE create mode 100644 Makefile create mode 100644 circleq.c create mode 100644 list.c create mode 100644 simpleq.c create mode 100644 slist.c create mode 100644 tailq.c diff --git a/LICENSE b/LICENSE new file mode 100644 index 0000000..e8348e3 --- /dev/null +++ b/LICENSE @@ -0,0 +1 @@ +all source is public domain blah blah blah diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..27cfef0 --- /dev/null +++ b/Makefile @@ -0,0 +1,22 @@ +CC=gcc -g -Wall +PROGS=slist list simpleq tailq circleq + +all: $(PROGS) + +slist: slist.c + $(CC) -o $@ $? + +list: list.c + $(CC) -o $@ $? + +simpleq: simpleq.c + $(CC) -o $@ $? + +tailq: tailq.c + $(CC) -o $@ $? + +circelq: circleq.c + $(CC) -o $@ $? + +clean: + rm -f $(PROGS) *.core diff --git a/circleq.c b/circleq.c new file mode 100644 index 0000000..db66271 --- /dev/null +++ b/circleq.c @@ -0,0 +1,105 @@ +#include +#include +#include +#include + +/* + * circleq macro usage examples by Peter Werner + * + * please see http://www.ifost.org.au/~peterw/queue.html for more info + */ + +/* + * our struct definition, with the circleq element to be referenced by f_link + */ + +struct foo { + int f_a; + char f_b; + CIRCLEQ_ENTRY(foo) f_link; +}; + +/* + * the head of our circleq of struct foo's (see the manpage for more info) + */ +CIRCLEQ_HEAD(cqhead, foo) cq; + +struct foo *alloc_foo(int a, char b); + +int +main(void) +{ + struct foo *fp, *other; + struct cqhead *cqp; + + CIRCLEQ_INIT(&cq); + cqp = &cq; + + /* + * insert the elements, note the use of the f_link item + */ + fp = alloc_foo(1, 'a'); + CIRCLEQ_INSERT_HEAD(cqp, fp, f_link); + + fp = alloc_foo(2, 'b'); + CIRCLEQ_INSERT_TAIL(cqp, fp, f_link); + + /* + * put this one after the head of the queue + */ + fp = alloc_foo(3, 'c'); + CIRCLEQ_INSERT_AFTER(cqp, CIRCLEQ_FIRST(cqp), fp, f_link); + + /* + * put this one in front of the one we just inserted + */ + other = alloc_foo(4, 'd'); + CIRCLEQ_INSERT_BEFORE(cqp, fp, other, f_link); + + + /* + * loop through the list + */ + CIRCLEQ_FOREACH(fp, cqp, f_link) + printf("%d %c\n", fp->f_a, fp->f_b); + + /* + * loop through the other way, note the use of cqhead + */ + printf("backwards!\n"); + CIRCLEQ_FOREACH_REVERSE(fp, cqp, f_link) + printf("%d %c\n", fp->f_a, fp->f_b); + + /* + * free up our list + */ + for (fp = CIRCLEQ_FIRST(cqp); fp != CIRCLEQ_END(cqp); fp = other) { + other = CIRCLEQ_NEXT(fp, f_link); + CIRCLEQ_REMOVE(cqp, fp, f_link); + free(fp); + } + + /* + * make sure + */ + if (CIRCLEQ_EMPTY(cqp)) + printf("List is empty!\n"); + else + printf("List not empty!\n"); + + return(0); +} + +struct foo * +alloc_foo(int a, char b) +{ + struct foo *tmp; + + tmp = (struct foo *)malloc(sizeof(struct foo)); + if (tmp == NULL) + err(1, "malloc"); + + tmp->f_a = a; + tmp->f_b = b; + return(tmp); +} diff --git a/list.c b/list.c new file mode 100644 index 0000000..c509152 --- /dev/null +++ b/list.c @@ -0,0 +1,88 @@ +#include +#include +#include +#include + +/* + * list macro usage examples by Peter Werner + * + * please see http://www.ifost.org.au/~peterw/queue.html for more info + */ + +/* + * our struct definition, with the list element to be referenced by f_link + */ + +struct foo { + int f_a; + char f_b; + LIST_ENTRY(foo) f_link; +}; + +/* + * the head of our list of struct foo's (see the manpage for more info) + */ +LIST_HEAD(listhead, foo) list; + +struct foo *alloc_foo(int a, char b); + +int +main(void) +{ + struct foo *fp, *other; + struct listhead *listp; + + LIST_INIT(&list); + listp = &list; + + /* + * insert the elements, note the use of the f_link item + */ + fp = alloc_foo(1, 'a'); + LIST_INSERT_HEAD(listp, fp, f_link); + + other = alloc_foo(2, 'b'); + LIST_INSERT_AFTER(fp, other, f_link); + + fp = alloc_foo(3, 'c'); + LIST_INSERT_BEFORE(other, fp, f_link); + + /* + * loop through the list + */ + LIST_FOREACH(fp, listp, f_link) + printf("%d %c\n", fp->f_a, fp->f_b); + + /* + * free up our list + */ + for (fp = LIST_FIRST(listp); fp != LIST_END(listp); fp = other) { + other = LIST_NEXT(fp, f_link); + LIST_REMOVE(fp, f_link); + free(fp); + } + + /* + * make sure + */ + if (LIST_EMPTY(listp)) + printf("List is empty!\n"); + else + printf("List not empty!\n"); + + return(0); +} + +struct foo * +alloc_foo(int a, char b) +{ + struct foo *tmp; + + tmp = (struct foo *)malloc(sizeof(struct foo)); + if (tmp == NULL) + err(1, "malloc"); + + tmp->f_a = a; + tmp->f_b = b; + return(tmp); +} diff --git a/simpleq.c b/simpleq.c new file mode 100644 index 0000000..8c55c73 --- /dev/null +++ b/simpleq.c @@ -0,0 +1,91 @@ +#include +#include +#include +#include + +/* + * simpleq macro usage examples by Peter Werner + * + * please see http://www.ifost.org.au/~peterw/queue.html for more info + */ + +/* + * our struct definition, with the simpleq element to be referenced by f_link + */ + +struct foo { + int f_a; + char f_b; + SIMPLEQ_ENTRY(foo) f_link; +}; + +/* + * the head of our simpleq of struct foo's (see the manpage for more info) + */ +SIMPLEQ_HEAD(sqhead, foo) sq; + +struct foo *alloc_foo(int a, char b); + +int +main(void) +{ + struct foo *fp; + struct sqhead *sqp; + + SIMPLEQ_INIT(&sq); + sqp = &sq; + + /* + * insert the elements, note the use of the f_link item + */ + fp = alloc_foo(1, 'a'); + SIMPLEQ_INSERT_HEAD(sqp, fp, f_link); + + fp = alloc_foo(2, 'b'); + SIMPLEQ_INSERT_TAIL(sqp, fp, f_link); + + /* + * put this one after the head of the queue + */ + fp = alloc_foo(3, 'c'); + SIMPLEQ_INSERT_AFTER(sqp, SIMPLEQ_FIRST(sqp), fp, f_link); + + + /* + * loop through the list + */ + for (fp = SIMPLEQ_FIRST(sqp); fp != NULL; fp = SIMPLEQ_NEXT(fp, f_link)) + printf("%d %c\n", fp->f_a, fp->f_b); + + /* + * free up our list + */ + while ((fp = SIMPLEQ_FIRST(sqp)) != NULL) { + SIMPLEQ_REMOVE_HEAD(sqp, fp, f_link); + free(fp); + } + + /* + * make sure + */ + if (SIMPLEQ_EMPTY(sqp)) + printf("List is empty!\n"); + else + printf("List not empty!\n"); + + return(0); +} + +struct foo * +alloc_foo(int a, char b) +{ + struct foo *tmp; + + tmp = (struct foo *)malloc(sizeof(struct foo)); + if (tmp == NULL) + err(1, "malloc"); + + tmp->f_a = a; + tmp->f_b = b; + return(tmp); +} diff --git a/slist.c b/slist.c new file mode 100644 index 0000000..e05dd25 --- /dev/null +++ b/slist.c @@ -0,0 +1,90 @@ +#include +#include +#include +#include + +/* + * slist macro usage examples by Peter Werner + * + * please see http://www.ifost.org.au/~peterw/queue.html for more info + */ + +/* + * our struct definition, with the slist element + */ + +struct foo { + int f_a; + char f_b; + SLIST_ENTRY(foo) f_link; +}; + +/* + * the head of our list of struct foo's (see the manpage for more info) + */ +SLIST_HEAD(, foo) list; + +struct foo *alloc_foo(int a, char b); + +int +main(void) +{ + struct foo *fp; + + SLIST_INIT(&list); + + /* + * insert the elements, note the use of the f_link item + */ + fp = alloc_foo(1, 'a'); + SLIST_INSERT_HEAD(&list, fp, f_link); + fp = alloc_foo(2, 'b'); + SLIST_INSERT_HEAD(&list, fp, f_link); + fp = alloc_foo(3, 'c'); + SLIST_INSERT_HEAD(&list, fp, f_link); + + /* + * loop through the list + */ + for (fp = SLIST_FIRST(&list); fp != NULL; fp = SLIST_NEXT(fp, f_link)) + printf("%d %c\n", fp->f_a, fp->f_b); + + /* + * another way of looping + */ + SLIST_FOREACH(fp, &list, f_link) + printf("%d %c\n", fp->f_a, fp->f_b); + + /* + * free up our list + */ + while (!SLIST_EMPTY(&list)) { + fp = SLIST_FIRST(&list); + SLIST_REMOVE_HEAD(&list, f_link); + free(fp); + } + + /* + * make sure + */ + if (SLIST_EMPTY(&list)) + printf("List is empty!\n"); + else + printf("List not empty!\n"); + + return(0); +} + +struct foo * +alloc_foo(int a, char b) +{ + struct foo *tmp; + + tmp = (struct foo *)malloc(sizeof(struct foo)); + if (tmp == NULL) + err(1, "malloc"); + + tmp->f_a = a; + tmp->f_b = b; + return(tmp); +} diff --git a/tailq.c b/tailq.c new file mode 100644 index 0000000..de9e312 --- /dev/null +++ b/tailq.c @@ -0,0 +1,104 @@ +#include +#include +#include +#include + +/* + * tailq macro usage examples by Peter Werner + * + * please see http://www.ifost.org.au/~peterw/queue.html for more info + */ + +/* + * our struct definition, with the tailq element to be referenced by f_link + */ + +struct foo { + int f_a; + char f_b; + TAILQ_ENTRY(foo) f_link; +}; + +/* + * the head of our tailq of struct foo's (see the manpage for more info) + */ +TAILQ_HEAD(tqhead, foo) tq; + +struct foo *alloc_foo(int a, char b); + +int +main(void) +{ + struct foo *fp, *other; + struct tqhead *tqp; + + TAILQ_INIT(&tq); + tqp = &tq; + + /* + * insert the elements, note the use of the f_link item + */ + fp = alloc_foo(1, 'a'); + TAILQ_INSERT_HEAD(tqp, fp, f_link); + + fp = alloc_foo(2, 'b'); + TAILQ_INSERT_TAIL(tqp, fp, f_link); + + /* + * put this one after the head of the queue + */ + fp = alloc_foo(3, 'c'); + TAILQ_INSERT_AFTER(tqp, TAILQ_FIRST(tqp), fp, f_link); + + /* + * put this one in front of the one we just inserted + */ + other = alloc_foo(4, 'd'); + TAILQ_INSERT_BEFORE(fp, other, f_link); + + + /* + * loop through the list + */ + for (fp = TAILQ_FIRST(tqp); fp != NULL; fp = TAILQ_NEXT(fp, f_link)) + printf("%d %c\n", fp->f_a, fp->f_b); + + /* + * loop through the other way, note the use of tqhead + */ + printf("backwards!\n"); + TAILQ_FOREACH_REVERSE(fp, tqp, f_link, tqhead) + printf("%d %c\n", fp->f_a, fp->f_b); + + /* + * free up our list + */ + while ((fp = TAILQ_FIRST(tqp)) != NULL) { + TAILQ_REMOVE(tqp, fp, f_link); + free(fp); + } + + /* + * make sure + */ + if (TAILQ_EMPTY(tqp)) + printf("List is empty!\n"); + else + printf("List not empty!\n"); + + return(0); +} + +struct foo * +alloc_foo(int a, char b) +{ + struct foo *tmp; + + tmp = (struct foo *)malloc(sizeof(struct foo)); + if (tmp == NULL) + err(1, "malloc"); + + tmp->f_a = a; + tmp->f_b = b; + return(tmp); +} -- cgit v1.2.3