lstack: Linked list stack implementation
authorDavid Gibson <david@gibson.dropbear.id.au>
Tue, 9 Sep 2014 14:22:54 +0000 (00:22 +1000)
committerRusty Russell <rusty@rustcorp.com.au>
Sat, 13 Sep 2014 05:51:16 +0000 (15:21 +0930)
This new module provides a simple stack implementation as a singly
linked list.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
Makefile-ccan
ccan/lstack/LICENSE [new symlink]
ccan/lstack/_info [new file with mode: 0644]
ccan/lstack/lstack.h [new file with mode: 0644]
ccan/lstack/test/run.c [new file with mode: 0644]

index 4205bcdaeee035d79def0bf103a899d62e71bcb6..1388f892dc00bda310eeabfa07788424d9e92e3c 100644 (file)
@@ -69,6 +69,7 @@ MODS_WITH_SRC := antithread \
        likely \
        list \
        lqueue \
+       lstack \
        md4 \
        memmem \
        net \
diff --git a/ccan/lstack/LICENSE b/ccan/lstack/LICENSE
new file mode 120000 (symlink)
index 0000000..2354d12
--- /dev/null
@@ -0,0 +1 @@
+../../licenses/BSD-MIT
\ No newline at end of file
diff --git a/ccan/lstack/_info b/ccan/lstack/_info
new file mode 100644 (file)
index 0000000..5b270bc
--- /dev/null
@@ -0,0 +1,57 @@
+#include "config.h"
+#include <stdio.h>
+#include <string.h>
+
+/**
+ * lstack - Simple, singly-linked-list stack implementation
+ *
+ * This code provides a simple implementation of the Stack abstract
+ * data type in terms of a singly linked list.
+ *
+ * License: BSD-MIT
+ * Author: David Gibson <david@gibson.dropbear.id.au>
+ *
+ * Example:
+ *     #include <ccan/lstack/lstack.h>
+ *
+ *     struct arg {
+ *             const char *arg;
+ *             struct lstack_link sl;
+ *     };
+ *
+ *     int main(int argc, char *argv[])
+ *     {
+ *             int i;
+ *             struct arg *a;
+ *             LSTACK(argstack);
+ *
+ *             for (i = 0; i < argc; i++) {
+ *                     a = malloc(sizeof(*a));
+ *                     a->arg = argv[i];
+ *                     lstack_push(&argstack, a, sl);
+ *             }
+ *
+ *             printf("Command line arguments in reverse:\n");
+ *
+ *             while (!lstack_empty(&argstack)) {
+ *                     a = lstack_pop(&argstack, struct arg, sl);
+ *                     printf("Argument: %s\n", a->arg);
+ *                     free(a);
+ *             }
+ *
+ *             return 0;
+ *     }
+ */
+int main(int argc, char *argv[])
+{
+       /* Expect exactly one argument */
+       if (argc != 2)
+               return 1;
+
+       if (strcmp(argv[1], "depends") == 0) {
+               printf("ccan/container_of\n");
+               return 0;
+       }
+
+       return 1;
+}
diff --git a/ccan/lstack/lstack.h b/ccan/lstack/lstack.h
new file mode 100644 (file)
index 0000000..41a9f05
--- /dev/null
@@ -0,0 +1,155 @@
+/* Licensed under BSD-MIT - see LICENSE file for details */
+#ifndef CCAN_LSTACK_H
+#define CCAN_LSTACK_H
+
+#include <stdbool.h>
+#include <stdio.h>
+#include <assert.h>
+
+#include <ccan/container_of/container_of.h>
+
+/**
+ * struct lstack_link - a stack link
+ * @down: immedately lower entry in the stack, or NULL if this is the bottom.
+ *
+ * This is used as an entry in a stack.
+ *
+ * Example:
+ *     struct stacker {
+ *             char *name;
+ *             struct lstack_link sl;
+ *     };
+ */
+struct lstack_link {
+       struct lstack_link *down;
+};
+
+/**
+ * struct lstack - a stack
+ * @b: the top of the stack (NULL if empty)
+ */
+struct lstack {
+       struct lstack_link *top;
+};
+
+/**
+ * LSTACK - define and initialize an empty stack
+ * @name: the name of the lstack.
+ *
+ * The LSTACK macro defines an lstack and initializes it to an empty
+ * stack.  It can be prepended by "static" to define a static lstack.
+ *
+ * See also:
+ *     lstack_init()
+ *
+ * Example:
+ *     LSTACK(my_stack);
+ *
+ *     assert(lstack_empty(&my_stack));
+ */
+#define LSTACK(name) \
+       struct lstack name = { NULL, }
+
+/**
+ * lstack_init - initialize a stack
+ * @h: the lstack to set to an empty stack
+ *
+ * Example:
+ *     struct lstack *sp = malloc(sizeof(*sp));
+ *     lstack_init(sp);
+ */
+static inline void lstack_init(struct lstack *s)
+{
+       s->top = NULL;
+}
+
+/**
+ * lstack_empty - is a stack empty?
+ * @s: the stack
+ *
+ * If the stack is empty, returns true.
+ *
+ * Example:
+ *     assert(lstack_empty(sp));
+ */
+static inline bool lstack_empty(const struct lstack *s)
+{
+       return (s->top == NULL);
+}
+
+/**
+ * lstack_entry - convert an lstack_link back into the structure containing it.
+ * @e: the lstack_link
+ * @type: the type of the entry
+ * @member: the lstack_link member of the type
+ *
+ * Example:
+ *     struct stacker {
+ *             char *name;
+ *             struct lstack_link sl;
+ *     } st;
+ *     assert(lstack_entry(&st.sl, struct stacker, sl) == &st);
+ */
+#define lstack_entry(n, type, member) container_of_or_null(n, type, member)
+
+/**
+ * lstack_top - get top entry in a stack
+ * @s: the stack
+ * @type: the type of stack entries
+ * @member: the lstack_link entry
+ *
+ * If the stack is empty, returns NULL.
+ *
+ * Example:
+ *     struct stacker *t;
+ *
+ *     t = lstack_top(sp, struct stacker, sl);
+ *     assert(lstack_pop(sp, struct stacker, sl) == t);
+ */
+#define lstack_top(s, type, member) \
+       lstack_entry(lstack_top_((s)), type, member)
+static inline struct lstack_link *lstack_top_(const struct lstack *s)
+{
+       return s->top;
+}
+
+/**
+ * lstack_push - add an entry to the top of the stack
+ * @s: the stack to add the node to
+ * @e: the item to push
+ * @member: the lstack_link field of *e
+ *
+ * The lstack_link does not need to be initialized; it will be overwritten.
+ */
+#define lstack_push(s, e, member) \
+       lstack_push_((s), &((e)->member))
+static inline void lstack_push_(struct lstack *s, struct lstack_link *e)
+{
+       e->down = lstack_top_(s);
+       s->top = e;
+}
+
+/**
+ * lstack_pop - remove and return the entry from the top of the stack
+ * @s: the stack
+ * @type: the type of stack entries
+ * @member: the lstack_link field of @type
+ *
+ * Note that this leaves the returned entry's link in an undefined
+ * state; it can be added to another stack, but not deleted again.
+ */
+#define lstack_pop(s, type, member) \
+       lstack_entry(lstack_pop_((s)), type, member)
+static inline struct lstack_link *lstack_pop_(struct lstack *s)
+{
+       struct lstack_link *top;
+
+       if (lstack_empty(s))
+               return NULL;
+
+       top = lstack_top_(s);
+       s->top = top->down;
+       return top;
+}
+
+#endif /* CCAN_LSTACK_H */
diff --git a/ccan/lstack/test/run.c b/ccan/lstack/test/run.c
new file mode 100644 (file)
index 0000000..d67ba32
--- /dev/null
@@ -0,0 +1,62 @@
+#include "config.h"
+
+#include <ccan/lstack/lstack.h>
+#include <ccan/tap/tap.h>
+
+struct stacker {
+       const char *name;
+       struct lstack_link sl;
+};
+
+int main(void)
+{
+       LSTACK(s);
+       struct stacker a = { "Alice" };
+       struct stacker b = { "Bob" };
+       struct stacker c = { "Carol" };
+       struct stacker *stacker;
+
+       /* This is how many tests you plan to run */
+       plan_tests(18);
+
+       ok1(lstack_empty(&s));
+       ok1(lstack_top(&s, struct stacker, sl) == NULL);
+
+       lstack_push(&s, &a, sl);
+
+       ok1(!lstack_empty(&s));
+       ok1(lstack_top(&s, struct stacker, sl) == &a);
+
+       lstack_push(&s, &b, sl);
+
+       ok1(!lstack_empty(&s));
+       ok1(lstack_top(&s, struct stacker, sl) == &b);
+
+       lstack_push(&s, &c, sl);
+
+       ok1(!lstack_empty(&s));
+       ok1(lstack_top(&s, struct stacker, sl) == &c);
+
+       stacker = lstack_pop(&s, struct stacker, sl);
+       ok1(stacker == &c);
+
+       ok1(!lstack_empty(&s));
+       ok1(lstack_top(&s, struct stacker, sl) == &b);
+
+       stacker = lstack_pop(&s, struct stacker, sl);
+       ok1(stacker == &b);
+
+       ok1(!lstack_empty(&s));
+       ok1(lstack_top(&s, struct stacker, sl) == &a);
+
+       stacker = lstack_pop(&s, struct stacker, sl);
+       ok1(stacker == &a);
+
+       ok1(lstack_empty(&s));
+       ok1(lstack_top(&s, struct stacker, sl) == NULL);
+
+       ok1(lstack_pop(&s, struct stacker, sl) == NULL);
+
+       /* This exits depending on whether all tests passed */
+       return exit_status();
+}