[ccan] [PATCH 1/4] queue: Simple queue implementation
Rusty Russell
rusty at rustcorp.com.au
Sun Jul 13 22:51:29 EST 2014
David Gibson <david at gibson.dropbear.id.au> writes:
> On Tue, Jul 08, 2014 at 08:20:38PM +0930, Paul 'Rusty' Russell wrote:
>> Cody P Schafer <dev at codyps.com> writes:
>> > On Mon, Jul 7, 2014 at 8:51 AM, David Gibson
>> > <david at gibson.dropbear.id.au> wrote:
>> >> This new module provides a simple queue implementation as a singly linked
>> >> (circular) list.
>> >>
>> >> Signed-off-by: David Gibson <david at gibson.dropbear.id.au>
>> >
>> > I've been looking for a singly-linked list for places where I don't
>> > necessarily need a doubly linked one (as provided by ccan/list).
>>
>> Yes, an slist module is a tempting thought. At risk of making David
>> rewrite everything :)
>
> Yeah.. I am tempted to say "patches welcome" to that...
Always a good idea! Here's my first cut of slist-like-list.h.
I'm not entirely happy with the result. A single linked list
implemented as a head-including chain is quite limited. If you
implement it as a pointer to the tail of a ring of nodes, you can
view the tail and append to the list, but there are more branches
since you have to test for NULL in the empty case...
Anyway, here's what I've got:
>From 3cb2e824d6d9c649f8cd74ad8c3a1c263b9d7ef1 Mon Sep 17 00:00:00 2001
From: Rusty Russell <rusty at rustcorp.com.au>
Date: Sun, 13 Jul 2014 22:18:05 +0930
Subject: [PATCH] slist: new module
Signed-off-by: Rusty Russell <rusty at rustcorp.com.au>
diff --git a/ccan/slist/LICENSE b/ccan/slist/LICENSE
new file mode 120000
index 0000000..2354d12
--- /dev/null
+++ b/ccan/slist/LICENSE
@@ -0,0 +1 @@
+../../licenses/BSD-MIT
\ No newline at end of file
diff --git a/ccan/slist/_info b/ccan/slist/_info
new file mode 100644
index 0000000..8fe7da0
--- /dev/null
+++ b/ccan/slist/_info
@@ -0,0 +1,76 @@
+#include "config.h"
+#include <stdio.h>
+#include <string.h>
+
+/**
+ * slist - single linked list routines
+ *
+ * The list header contains routines for manipulating single linked lists.
+ * It defines two types: struct slist_head used for anchoring lists, and
+ * struct slist_node which is usually embedded in the structure which is placed
+ * in the list.
+ *
+ * See Also:
+ * <sys/queue.h>
+ * ccan/list
+ *
+ * Example:
+ * #include <err.h>
+ * #include <stdio.h>
+ * #include <stdlib.h>
+ * #include <ccan/slist/slist.h>
+ *
+ * struct parent {
+ * const char *name;
+ * struct slist_head children;
+ * unsigned int num_children;
+ * };
+ *
+ * struct child {
+ * const char *name;
+ * struct slist_node list;
+ * };
+ *
+ * int main(int argc, char *argv[])
+ * {
+ * struct parent p;
+ * struct child *c;
+ * unsigned int i;
+ *
+ * if (argc < 2)
+ * errx(1, "Usage: %s parent children...", argv[0]);
+ *
+ * p.name = argv[1];
+ * slist_head_init(&p.children);
+ * p.num_children = 0;
+ * for (i = 2; i < argc; i++) {
+ * c = malloc(sizeof(*c));
+ * c->name = argv[i];
+ * slist_add(&p.children, &c->list);
+ * p.num_children++;
+ * }
+ *
+ * printf("%s has %u children:", p.name, p.num_children);
+ * slist_for_each(&p.children, c, list)
+ * printf("%s ", c->name);
+ * printf("\n");
+ * return 0;
+ * }
+ *
+ * License: BSD-MIT
+ * Author: Rusty Russell <rusty at rustcorp.com.au>
+ */
+int main(int argc, char *argv[])
+{
+ if (argc != 2)
+ return 1;
+
+ if (strcmp(argv[1], "depends") == 0) {
+ printf("ccan/str\n");
+ printf("ccan/container_of\n");
+ printf("ccan/check_type\n");
+ return 0;
+ }
+
+ return 1;
+}
diff --git a/ccan/slist/slist.c b/ccan/slist/slist.c
new file mode 100644
index 0000000..f4f9156
--- /dev/null
+++ b/ccan/slist/slist.c
@@ -0,0 +1,41 @@
+/* Licensed under BSD-MIT - see LICENSE file for details */
+#include <stdio.h>
+#include <stdlib.h>
+#include "slist.h"
+
+static void *corrupt(const char *abortstr,
+ const struct slist_node *node, const char *problem)
+{
+ if (abortstr) {
+ fprintf(stderr,
+ "%s: %s node %p\n", abortstr, problem, node);
+ abort();
+ }
+ return NULL;
+}
+
+struct slist_node *slist_check_node(const struct slist_node *node,
+ const char *abortstr)
+{
+ const struct slist_node *p, *p2;
+ int count = 0;
+
+ /* We may have a loop which doesn't include node! */
+ for (p2 = node, p = node->next; p != node; p = p->next) {
+ if (count++ & 1)
+ p2 = p2->next;
+ if (p == p2)
+ return corrupt(abortstr, p, "loop in");
+ if (!p->next)
+ return corrupt(abortstr, p, "NULL next ptr in");
+ }
+
+ return (struct slist_node *)node;
+}
+
+struct slist_head *slist_check(const struct slist_head *h, const char *abortstr)
+{
+ if (!slist_check_node(&h->n, abortstr))
+ return NULL;
+ return (struct slist_head *)h;
+}
diff --git a/ccan/slist/slist.h b/ccan/slist/slist.h
new file mode 100644
index 0000000..9785dc4
--- /dev/null
+++ b/ccan/slist/slist.h
@@ -0,0 +1,415 @@
+/* Licensed under BSD-MIT - see LICENSE file for details */
+#ifndef CCAN_SLIST_H
+#define CCAN_SLIST_H
+//#define CCAN_SLIST_DEBUG 1
+#include <stdbool.h>
+#include <assert.h>
+#include <ccan/str/str.h>
+#include <ccan/container_of/container_of.h>
+#include <ccan/check_type/check_type.h>
+
+/**
+ * struct slist_node - an entry in a singly-linked slist
+ * @next: next entry (self if empty)
+ *
+ * This is used as an entry in a linked list.
+ *
+ * Example:
+ * struct child {
+ * const char *name;
+ * // Linked slist of all us children.
+ * struct slist_node list;
+ * };
+ */
+struct slist_node {
+ struct slist_node *next;
+};
+
+/**
+ * struct slist_head - the head of a doubly-linked list
+ * @h: the slist_head (containing next pointers)
+ *
+ * This is used as the head of a linked list.
+ * Example:
+ * struct parent {
+ * const char *name;
+ * struct slist_head children;
+ * unsigned int num_children;
+ * };
+ */
+struct slist_head {
+ struct slist_node n;
+};
+
+/**
+ * slist_check - check head of a list for consistency
+ * @h: the slist_head
+ * @abortstr: the location to print on aborting, or NULL.
+ *
+ * Because slist is circular, we can check that it loops. This is
+ * useful as a debugging check. If @abortstr is non-NULL, that will
+ * be printed in a diagnostic if the list is inconsistent, and the
+ * function will abort.
+ *
+ * Returns the slist_head if the list is consistent, NULL if not (it
+ * can never return NULL if @abortstr is set).
+ *
+ * See also: slist_check_node()
+ *
+ * Example:
+ * static void dump_parent(struct parent *p)
+ * {
+ * struct child *c;
+ *
+ * printf("%s (%u children):\n", p->name, p->num_children);
+ * slist_check(&p->children, "bad child list");
+ * slist_for_each(&p->children, c, list)
+ * printf(" -> %s\n", c->name);
+ * }
+ */
+struct slist_head *slist_check(const struct slist_head *h,
+ const char *abortstr);
+
+/**
+ * slist_check_node - check node of a list for consistency
+ * @n: the slist_node
+ * @abortstr: the location to print on aborting, or NULL.
+ *
+ * Check consistency of the slist node is in (it must be in one).
+ *
+ * See also: slist_check()
+ *
+ * Example:
+ * static void dump_child(const struct child *c)
+ * {
+ * slist_check_node(&c->list, "bad child list");
+ * printf("%s\n", c->name);
+ * }
+ */
+struct slist_node *slist_check_node(const struct slist_node *n,
+ const char *abortstr);
+
+#define SLIST_LOC __FILE__ ":" stringify(__LINE__)
+#ifdef CCAN_SLIST_DEBUG
+#define slist_debug(h, loc) slist_check((h), loc)
+#define slist_debug_node(n, loc) slist_check_node((n), loc)
+#else
+#define slist_debug(h, loc) (h)
+#define slist_debug_node(n, loc) (n)
+#endif
+
+/**
+ * SLIST_HEAD_INIT - initializer for an empty slist_head
+ * @name: the name of the list.
+ *
+ * Explicit initializer for an empty list.
+ *
+ * See also:
+ * SLIST_HEAD, slist_head_init()
+ *
+ * Example:
+ * static struct slist_head my_list = SLIST_HEAD_INIT(my_list);
+ */
+#define SLIST_HEAD_INIT(name) { { &name.n } }
+
+/**
+ * SLIST_HEAD - define and initialize an empty slist_head
+ * @name: the name of the list.
+ *
+ * The SLIST_HEAD macro defines a slist_head and initializes it to an empty
+ * slist. It can be prepended by "static" to define a static slist_head.
+ *
+ * See also:
+ * SLIST_HEAD_INIT, slist_head_init()
+ *
+ * Example:
+ * static SLIST_HEAD(my_global_list);
+ */
+#define SLIST_HEAD(name) \
+ struct slist_head name = SLIST_HEAD_INIT(name)
+
+/**
+ * slist_head_init - initialize a slist_head
+ * @h: the slist_head to set to the empty list
+ *
+ * Example:
+ * ...
+ * struct parent *parent = malloc(sizeof(*parent));
+ *
+ * slist_head_init(&parent->children);
+ * parent->num_children = 0;
+ */
+static inline void slist_head_init(struct slist_head *h)
+{
+ h->n.next = &h->n;
+}
+
+/**
+ * slist_add - add an entry at the start of a linked list.
+ * @h: the slist_head to add the node to
+ * @n: the slist_node to add to the slist.
+ *
+ * The slist_node does not need to be initialized; it will be overwritten.
+ * Example:
+ * struct child *child = malloc(sizeof(*child));
+ *
+ * child->name = "marvin";
+ * slist_add(&parent->children, &child->list);
+ * parent->num_children++;
+ */
+#define slist_add(h, n) slist_add_(h, n, SLIST_LOC)
+static inline void slist_add_(struct slist_head *h,
+ struct slist_node *n,
+ const char *abortstr)
+{
+ n->next = h->n.next;
+ h->n.next = n;
+ (void)slist_debug(h, abortstr);
+}
+
+/**
+ * slist_empty - is a list empty?
+ * @h: the slist_head
+ *
+ * If the list is empty, returns true.
+ *
+ * Example:
+ * assert(slist_empty(&parent->children) == (parent->num_children == 0));
+ */
+#define slist_empty(h) slist_empty_(h, SLIST_LOC)
+static inline bool slist_empty_(const struct slist_head *h,
+ const char* abortstr)
+{
+ (void)slist_debug(h, abortstr);
+ return h->n.next == &h->n;
+}
+
+/**
+ * slist_empty_nodebug - is a list empty (and don't perform debug checks)?
+ * @h: the slist_head
+ *
+ * If the slist is empty, returns true.
+ * This differs from slist_empty() in that if CCAN_SLIST_DEBUG is set it
+ * will NOT perform debug checks. Only use this function if you REALLY
+ * know what you're doing.
+ *
+ * Example:
+ * assert(slist_empty_nodebug(&parent->children) == (parent->num_children == 0));
+ */
+#ifndef CCAN_SLIST_DEBUG
+#define slist_empty_nodebug(h) slist_empty(h)
+#else
+static inline bool slist_empty_nodebug(const struct slist_head *h)
+{
+ return h->n.next == &h->n;
+}
+#endif
+
+/**
+ * slist_del - delete the next entry from a linked list.
+ * @p: the pointer to the previous list_node.
+ *
+ * Note that this leaves @n in an undefined state; it can be added to
+ * another list, but not deleted again.
+ *
+ * See also:
+ * slist_del_from(), slist_for_each_safe()
+ *
+ * Example:
+ * struct slist_node **p = &parent->children.n.next;
+ * slist_del(p);
+ * parent->num_children--;
+ */
+#define slist_del(p) slist_del_(p, SLIST_LOC)
+static inline void slist_del_(struct slist_node **p, const char* abortstr)
+{
+ struct slist_node *next = (*p)->next;
+
+ (void)slist_debug_node(*p, abortstr);
+#ifdef CCAN_LIST_DEBUG
+ /* Catch use-after-del. */
+ (*p)->next = NULL;
+#endif
+ *p = next;
+}
+
+/**
+ * slist_del_from - delete an entry from a linked list.
+ * @h: the slist_head the node is in.
+ * @n: the slist_node to delete from the list.
+ *
+ * Example:
+ * slist_del_from(&parent->children, &child->list);
+ * parent->num_children--;
+ */
+static inline void slist_del_from(struct slist_head *h, struct slist_node *n)
+{
+ struct slist_node **p;
+
+ for (p = &slist_debug(h, SLIST_LOC)->n.next;
+ *p != &(h)->n;
+ p = &(*p)->next) {
+ if (*p == n) {
+ slist_del(p);
+ return;
+ }
+ }
+ assert(0);
+}
+
+/**
+ * slist_entry - convert a slist_node back into the structure containing it.
+ * @n: the slist_node
+ * @type: the type of the entry
+ * @member: the slist_node member of the type
+ *
+ * Example:
+ * // First list entry is children.next; convert back to child.
+ * child = slist_entry(parent->children.n.next, struct child, list);
+ *
+ * See Also:
+ * slist_top(), slist_for_each()
+ */
+#define slist_entry(n, type, member) container_of(n, type, member)
+
+/**
+ * slist_top - get the first entry in a list
+ * @h: the slist_head
+ * @type: the type of the entry
+ * @member: the slist_node member of the type
+ *
+ * If the list is empty, returns NULL.
+ *
+ * Example:
+ * struct child *first;
+ * first = slist_top(&parent->children, struct child, list);
+ * if (!first)
+ * printf("Empty list!\n");
+ */
+#define slist_top(h, type, member) \
+ ((type *)slist_top_((h), slist_off_(type, member)))
+
+static inline void *slist_top_(const struct slist_head *h, size_t off)
+{
+ if (slist_empty(h))
+ return NULL;
+ return (char *)h->n.next - off;
+}
+
+/**
+ * slist_pop - remove the first entry in a list
+ * @h: the slist_head
+ * @type: the type of the entry
+ * @member: the slist_node member of the type
+ *
+ * If the list is empty, returns NULL.
+ *
+ * Example:
+ * struct child *one;
+ * one = slist_pop(&parent->children, struct child, list);
+ * if (!one)
+ * printf("Empty list!\n");
+ */
+#define slist_pop(h, type, member) \
+ ((type *)slist_pop_((h), slist_off_(type, member)))
+
+static inline void *slist_pop_(struct slist_head *h, size_t off)
+{
+ struct slist_node *n;
+
+ if (slist_empty(h))
+ return NULL;
+ n = h->n.next;
+ slist_del(&h->n.next);
+ return (char *)n - off;
+}
+
+/**
+ * slist_for_each - iterate through a list
+ * @h: the slist_head (warning: evaluated multiple times!)
+ * @i: the structure containing the slist_node
+ * @member: the slist_node member of the structure
+ *
+ * This is a convenient wrapper to iterate @i over the entire list. It's
+ * a for loop, so you can break and continue as normal.
+ *
+ * Example:
+ * slist_for_each(&parent->children, child, list)
+ * printf("Name: %s\n", child->name);
+ */
+#define slist_for_each(h, i, member) \
+ for (i = container_of_var(slist_debug(h, SLIST_LOC)->n.next,i,member); \
+ &i->member != &(h)->n; \
+ i = container_of_var(i->member.next, i, member))
+
+/**
+ * slist_for_each_safe - iterate through a list, maybe during deletion
+ * @h: the slist_head (warning: evaluated multiple times!)
+ * @i: the structure containing the slist_node
+ * @p: a struct slist_node **
+ * @member: the slist_node member of the structure
+ *
+ * This is a convenient wrapper to iterate @i over the entire list.
+ * It's a for loop, so you can break and continue as normal. @p is
+ * used to hold the previous pointer, so you can delete @i from the
+ * list efficiently using slist_del(@p).
+ *
+ * Example:
+ * struct slist_node **np;
+ * slist_for_each_safe(&parent->children, child, np, list) {
+ * slist_del(np);
+ * parent->num_children--;
+ * }
+ */
+#define slist_for_each_safe(h, i, p, member) \
+ for (p = &(slist_debug(h, SLIST_LOC))->n.next; \
+ (i = container_of_var(*p, i, member)) && *p != &(h)->n; \
+ p = *p == &i->member ? &(*p)->next : p)
+
+
+/**
+ * slist_next - get the next entry in a list
+ * @h: the slist_head
+ * @i: a pointer to an entry in the list.
+ * @member: the slist_node member of the structure
+ *
+ * If @i was the last entry in the list, returns NULL.
+ *
+ * Example:
+ * struct child *second;
+ * second = slist_next(&parent->children, first, list);
+ * if (!second)
+ * printf("No second child!\n");
+ */
+#define slist_next(h, i, member) \
+ ((slist_typeof(i))slist_entry_or_null(slist_debug(h, \
+ __FILE__ ":" stringify(__LINE__)), \
+ (i)->member.next, \
+ slist_off_var_((i), member)))
+
+
+/* Get the offset of the member, but make sure it's a slist_node. */
+#define slist_off_(type, member) \
+ (container_off(type, member) + \
+ check_type(((type *)0)->member, struct slist_node))
+
+#define slist_off_var_(var, member) \
+ (container_off_var(var, member) + \
+ check_type(var->member, struct slist_node))
+
+#if HAVE_TYPEOF
+#define slist_typeof(var) typeof(var)
+#else
+#define slist_typeof(var) void *
+#endif
+
+/* Returns member, or NULL if at end of list. */
+static inline void *slist_entry_or_null(const struct slist_head *h,
+ const struct slist_node *n,
+ size_t off)
+{
+ if (n == &h->n)
+ return NULL;
+ return (char *)n - off;
+}
+#endif /* CCAN_SLIST_H */
diff --git a/ccan/slist/test/compile_ok-constant.c b/ccan/slist/test/compile_ok-constant.c
new file mode 100644
index 0000000..6c80e4e
--- /dev/null
+++ b/ccan/slist/test/compile_ok-constant.c
@@ -0,0 +1,43 @@
+#include <ccan/slist/slist.h>
+#include <ccan/tap/tap.h>
+#include <ccan/slist/slist.c>
+#include <stdbool.h>
+#include <stdio.h>
+
+struct child {
+ const char *name;
+ struct slist_node slist;
+};
+
+static bool children(const struct slist_head *slist)
+{
+ return !slist_empty(slist);
+}
+
+static const struct child *first_child(const struct slist_head *slist)
+{
+ return slist_top(slist, struct child, slist);
+}
+
+static void check_children(const struct slist_head *slist)
+{
+ slist_check(slist, "bad child slist");
+}
+
+static void print_children(const struct slist_head *slist)
+{
+ const struct child *c;
+ slist_for_each(slist, c, slist)
+ printf("%s\n", c->name);
+}
+
+int main(void)
+{
+ SLIST_HEAD(h);
+
+ children(&h);
+ first_child(&h);
+ check_children(&h);
+ print_children(&h);
+ return 0;
+}
diff --git a/ccan/slist/test/run-CCAN_SLIST_DEBUG.c b/ccan/slist/test/run-CCAN_SLIST_DEBUG.c
new file mode 100644
index 0000000..9f8a515
--- /dev/null
+++ b/ccan/slist/test/run-CCAN_SLIST_DEBUG.c
@@ -0,0 +1,58 @@
+/* Check that CCAN_SLIST_DEBUG works */
+#include <setjmp.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <stdarg.h>
+#include <string.h>
+#include <err.h>
+
+/* We don't actually want it to exit... */
+static jmp_buf aborted;
+#define abort() longjmp(aborted, 1)
+
+#define fprintf my_fprintf
+static char printf_buffer[1000];
+
+static int my_fprintf(FILE *stream, const char *format, ...)
+{
+ va_list ap;
+ int ret;
+ va_start(ap, format);
+ ret = vsprintf(printf_buffer, format, ap);
+ va_end(ap);
+ return ret;
+}
+
+#define CCAN_SLIST_DEBUG 1
+#include <ccan/slist/slist.h>
+#include <ccan/tap/tap.h>
+#include <ccan/slist/slist.c>
+
+int main(int argc, char *argv[])
+{
+ struct slist_head slist;
+ struct slist_node n1;
+ char expect[100];
+
+ plan_tests(2);
+ /* Empty entry slist. */
+ slist.n.next = &slist.n;
+ ok1(slist_check(&slist, NULL) == &slist);
+
+ /* Single entry, which loops to itself. */
+ slist.n.next = &n1;
+ n1.next = &n1;
+
+ /* Aborting version. */
+ sprintf(expect, "run-CCAN_SLIST_DEBUG.c:49: loop in node %p\n", &n1);
+ if (setjmp(aborted) == 0) {
+ assert(slist_empty(&slist));
+ fail("slist_empty on empty with bad back ptr didn't fail!");
+ } else {
+ /* __FILE__ might give full path. */
+ int prep = strlen(printf_buffer) - strlen(expect);
+ ok1(prep >= 0 && strcmp(printf_buffer + prep, expect) == 0);
+ }
+
+ return exit_status();
+}
diff --git a/ccan/slist/test/run-check-nonconst.c b/ccan/slist/test/run-check-nonconst.c
new file mode 100644
index 0000000..386fdae
--- /dev/null
+++ b/ccan/slist/test/run-check-nonconst.c
@@ -0,0 +1,26 @@
+#include <ccan/slist/slist.h>
+#include <ccan/tap/tap.h>
+#include <ccan/slist/slist.c>
+
+struct child {
+ const char *name;
+ struct slist_node slist;
+};
+
+int main(int argc, char *argv[])
+{
+ struct child c1, c2;
+ struct slist_head slist = SLIST_HEAD_INIT(slist);
+
+ plan_tests(1);
+
+ slist_add(&slist, &c1.slist);
+ slist_add(slist_check(&slist, "Bad slist!"), &c2.slist);
+ slist_del_from(slist_check(&slist, "Bad slist!"),
+ slist_check_node(&c2.slist, "Bad node!"));
+ slist_del_from(slist_check(&slist, "Bad slist!"),
+ slist_check_node(&c1.slist, "Bad node!"));
+ ok1(slist_empty(slist_check(&slist, "Bad emptied slist")));
+
+ return exit_status();
+}
diff --git a/ccan/slist/test/run-single-eval.c b/ccan/slist/test/run-single-eval.c
new file mode 100644
index 0000000..7a77d93
--- /dev/null
+++ b/ccan/slist/test/run-single-eval.c
@@ -0,0 +1,130 @@
+/* Make sure macros only evaluate their args once. */
+#include <ccan/slist/slist.h>
+#include <ccan/tap/tap.h>
+#include <ccan/slist/slist.c>
+
+struct parent {
+ const char *name;
+ struct slist_head children;
+ unsigned int num_children;
+ int eval_count;
+};
+
+struct child {
+ const char *name;
+ struct slist_node slist;
+};
+
+static SLIST_HEAD(static_slist);
+
+#define ref(obj, counter) ((counter)++, (obj))
+
+int main(int argc, char *argv[])
+{
+ struct parent parent;
+ struct child c1, c2, *c;
+ struct slist_node **p;
+ unsigned int i;
+ unsigned int static_count = 0, parent_count = 0, slist_count = 0,
+ node_count = 0;
+ struct slist_head slist = SLIST_HEAD_INIT(slist);
+
+ plan_tests(47);
+ /* Test SLIST_HEAD, SLIST_HEAD_INIT, slist_empty and check_slist */
+ ok1(slist_empty(ref(&static_slist, static_count)));
+ ok1(static_count == 1);
+ ok1(slist_check(ref(&static_slist, static_count), NULL));
+ ok1(static_count == 2);
+ ok1(slist_empty(ref(&slist, slist_count)));
+ ok1(slist_count == 1);
+ ok1(slist_check(ref(&slist, slist_count), NULL));
+ ok1(slist_count == 2);
+
+ parent.num_children = 0;
+ slist_head_init(ref(&parent.children, parent_count));
+ ok1(parent_count == 1);
+ /* Test slist_head_init */
+ ok1(slist_empty(ref(&parent.children, parent_count)));
+ ok1(parent_count == 2);
+ ok1(slist_check(ref(&parent.children, parent_count), NULL));
+ ok1(parent_count == 3);
+
+ c2.name = "c2";
+ slist_add(ref(&parent.children, parent_count), &c2.slist);
+ ok1(parent_count == 4);
+ /* Test slist_add and !slist_empty. */
+ ok1(!slist_empty(ref(&parent.children, parent_count)));
+ ok1(parent_count == 5);
+ ok1(c2.slist.next == &parent.children.n);
+ ok1(parent.children.n.next == &c2.slist);
+ /* Test slist_check */
+ ok1(slist_check(ref(&parent.children, parent_count), NULL));
+ ok1(parent_count == 6);
+
+ c1.name = "c1";
+ slist_add(ref(&parent.children, parent_count), &c1.slist);
+ ok1(parent_count == 7);
+ /* Test slist_add and !slist_empty. */
+ ok1(!slist_empty(ref(&parent.children, parent_count)));
+ ok1(parent_count == 8);
+ ok1(c2.slist.next == &parent.children.n);
+ ok1(parent.children.n.next == &c1.slist);
+ ok1(c1.slist.next == &c2.slist);
+ /* Test slist_check */
+ ok1(slist_check(ref(&parent.children, parent_count), NULL));
+ ok1(parent_count == 9);
+
+ /* Test slist_check_node */
+ ok1(slist_check_node(&c1.slist, NULL));
+ ok1(slist_check_node(&c2.slist, NULL));
+
+ /* Test slist_top */
+ ok1(slist_top(ref(&parent.children, parent_count), struct child, slist) == &c1);
+ ok1(parent_count == 10);
+
+ /* Test slist_for_each. */
+ i = 0;
+ slist_for_each(&parent.children, c, slist) {
+ switch (i++) {
+ case 0:
+ ok1(c == &c1);
+ break;
+ case 1:
+ ok1(c == &c2);
+ break;
+ }
+ if (i > 1)
+ break;
+ }
+ ok1(i == 2);
+
+ /* Test slist_for_each_safe, slist_del and slist_del_from. */
+ i = 0;
+ slist_for_each_safe(&parent.children, c, p, slist) {
+ switch (i++) {
+ case 0:
+ ok1(c == &c1);
+ slist_del(ref(p, node_count));
+ ok1(node_count == 1);
+ break;
+ case 1:
+ ok1(c == &c2);
+ slist_del_from(ref(&parent.children, parent_count),
+ ref(&c->slist, node_count));
+ ok1(node_count == 2);
+ break;
+ }
+ ok1(slist_check(ref(&parent.children, parent_count), NULL));
+ if (i > 1)
+ break;
+ }
+ ok1(i == 2);
+ ok1(parent_count == 13);
+ ok1(slist_empty(ref(&parent.children, parent_count)));
+ ok1(parent_count == 14);
+
+ /* Test slist_top on empty slist. */
+ ok1(slist_top(ref(&parent.children, parent_count), struct child, slist) == NULL);
+ ok1(parent_count == 15);
+ return exit_status();
+}
diff --git a/ccan/slist/test/run-slist_del_from-assert.c b/ccan/slist/test/run-slist_del_from-assert.c
new file mode 100644
index 0000000..da9a243
--- /dev/null
+++ b/ccan/slist/test/run-slist_del_from-assert.c
@@ -0,0 +1,36 @@
+#define CCAN_SLIST_DEBUG 1
+#include <ccan/slist/slist.h>
+#include <ccan/tap/tap.h>
+#include <ccan/slist/slist.c>
+#include <sys/types.h>
+#include <sys/wait.h>
+#include <unistd.h>
+#include <signal.h>
+
+int main(int argc, char *argv[])
+{
+ struct slist_head slist1, slist2;
+ struct slist_node n1, n2, n3;
+ pid_t child;
+ int status;
+
+ plan_tests(1);
+ slist_head_init(&slist1);
+ slist_head_init(&slist2);
+ slist_add(&slist1, &n1);
+ slist_add(&slist2, &n2);
+ slist_add(&slist2, &n3);
+
+ child = fork();
+ if (child) {
+ wait(&status);
+ } else {
+ /* This should abort. */
+ slist_del_from(&slist1, &n3);
+ exit(0);
+ }
+
+ ok1(WIFSIGNALED(status) && WTERMSIG(status) == SIGABRT);
+ slist_del_from(&slist2, &n3);
+ return exit_status();
+}
diff --git a/ccan/slist/test/run-slist_next.c b/ccan/slist/test/run-slist_next.c
new file mode 100644
index 0000000..c84ddaa
--- /dev/null
+++ b/ccan/slist/test/run-slist_next.c
@@ -0,0 +1,54 @@
+#include <ccan/slist/slist.h>
+#include <ccan/tap/tap.h>
+#include <ccan/slist/slist.c>
+
+struct parent {
+ const char *name;
+ unsigned int num_children;
+ struct slist_head children;
+};
+
+struct child {
+ const char *name;
+ struct slist_node slist;
+};
+
+int main(int argc, char *argv[])
+{
+ struct parent parent;
+ struct child c1, c2, c3;
+ const struct parent *p;
+ const struct child *c;
+
+ plan_tests(10);
+ parent.num_children = 0;
+ slist_head_init(&parent.children);
+
+ c1.name = "c1";
+ slist_add(&parent.children, &c1.slist);
+
+ ok1(slist_next(&parent.children, &c1, slist) == NULL);
+
+ c2.name = "c2";
+ slist_add(&parent.children, &c2.slist);
+
+ ok1(slist_next(&parent.children, &c2, slist) == &c1);
+ ok1(slist_next(&parent.children, &c1, slist) == NULL);
+
+ c3.name = "c3";
+ slist_add(&parent.children, &c3.slist);
+
+ ok1(slist_next(&parent.children, &c3, slist) == &c2);
+ ok1(slist_next(&parent.children, &c2, slist) == &c1);
+ ok1(slist_next(&parent.children, &c1, slist) == NULL);
+
+ /* Const variants */
+ p = &parent;
+ c = &c2;
+ ok1(slist_next(&p->children, &c3, slist) == &c2);
+ ok1(slist_next(&p->children, c, slist) == &c1);
+ ok1(slist_next(&parent.children, c, slist) == &c1);
+ ok1(slist_next(&p->children, &c1, slist) == NULL);
+
+ return exit_status();
+}
diff --git a/ccan/slist/test/run-with-debug.c b/ccan/slist/test/run-with-debug.c
new file mode 100644
index 0000000..ac5723d
--- /dev/null
+++ b/ccan/slist/test/run-with-debug.c
@@ -0,0 +1,3 @@
+/* Just like run.c, but with all debug checks enabled. */
+#define CCAN_SLIST_DEBUG 1
+#include <ccan/slist/test/run.c>
diff --git a/ccan/slist/test/run.c b/ccan/slist/test/run.c
new file mode 100644
index 0000000..83b7811
--- /dev/null
+++ b/ccan/slist/test/run.c
@@ -0,0 +1,110 @@
+#include <ccan/slist/slist.h>
+#include <ccan/tap/tap.h>
+#include <ccan/slist/slist.c>
+
+struct parent {
+ const char *name;
+ struct slist_head children;
+ unsigned int num_children;
+};
+
+struct child {
+ const char *name;
+ struct slist_node slist;
+};
+
+static SLIST_HEAD(static_slist);
+
+int main(int argc, char *argv[])
+{
+ struct parent parent;
+ struct child c1, c2, *c;
+ struct slist_node **p;
+ unsigned int i;
+ struct slist_head slist = SLIST_HEAD_INIT(slist);
+
+ plan_tests(31);
+ /* Test SLIST_HEAD, SLIST_HEAD_INIT, slist_empty and check_slist */
+ ok1(slist_empty(&static_slist));
+ ok1(slist_check(&static_slist, NULL));
+ ok1(slist_empty(&slist));
+ ok1(slist_check(&slist, NULL));
+
+ parent.num_children = 0;
+ slist_head_init(&parent.children);
+ /* Test slist_head_init */
+ ok1(slist_empty(&parent.children));
+ ok1(slist_check(&parent.children, NULL));
+
+ c2.name = "c2";
+ slist_add(&parent.children, &c2.slist);
+ /* Test slist_add and !slist_empty. */
+ ok1(!slist_empty(&parent.children));
+ ok1(c2.slist.next == &parent.children.n);
+ ok1(parent.children.n.next == &c2.slist);
+ /* Test slist_check */
+ ok1(slist_check(&parent.children, NULL));
+
+ c1.name = "c1";
+ slist_add(&parent.children, &c1.slist);
+ /* Test slist_add and !slist_empty. */
+ ok1(!slist_empty(&parent.children));
+ ok1(c2.slist.next == &parent.children.n);
+ ok1(parent.children.n.next == &c1.slist);
+ ok1(c1.slist.next == &c2.slist);
+ /* Test slist_check */
+ ok1(slist_check(&parent.children, NULL));
+
+ /* Test slist_check_node */
+ ok1(slist_check_node(&c1.slist, NULL));
+ ok1(slist_check_node(&c2.slist, NULL));
+
+ /* Test slist_top */
+ ok1(slist_top(&parent.children, struct child, slist) == &c1);
+
+ /* Test slist_pop */
+ ok1(slist_pop(&parent.children, struct child, slist) == &c1);
+ ok1(slist_top(&parent.children, struct child, slist) == &c2);
+ slist_add(&parent.children, &c1.slist);
+
+ /* Test slist_for_each. */
+ i = 0;
+ slist_for_each(&parent.children, c, slist) {
+ switch (i++) {
+ case 0:
+ ok1(c == &c1);
+ break;
+ case 1:
+ ok1(c == &c2);
+ break;
+ }
+ if (i > 1)
+ break;
+ }
+ ok1(i == 2);
+
+ /* Test slist_for_each_safe, slist_del and slist_del_from. */
+ i = 0;
+ slist_for_each_safe(&parent.children, c, p, slist) {
+ switch (i++) {
+ case 0:
+ ok1(c == &c1);
+ slist_del(p);
+ break;
+ case 1:
+ ok1(c == &c2);
+ slist_del_from(&parent.children, &c->slist);
+ break;
+ }
+ ok1(slist_check(&parent.children, NULL));
+ if (i > 1)
+ break;
+ }
+ ok1(i == 2);
+ ok1(slist_empty(&parent.children));
+
+ /* Test slist_top/slist_pop on empty slist. */
+ ok1(slist_top(&parent.children, struct child, slist) == NULL);
+ ok1(slist_pop(&parent.children, struct child, slist) == NULL);
+ return exit_status();
+}
More information about the ccan
mailing list