From eb5cf99742db1b02cc5cac4be19226b58009a106 Mon Sep 17 00:00:00 2001 From: David Gibson Date: Wed, 10 Sep 2014 00:22:54 +1000 Subject: [PATCH] lstack: Linked list stack implementation This new module provides a simple stack implementation as a singly linked list. Signed-off-by: David Gibson Signed-off-by: Rusty Russell --- Makefile-ccan | 1 + ccan/lstack/LICENSE | 1 + ccan/lstack/_info | 57 +++++++++++++++ ccan/lstack/lstack.h | 155 +++++++++++++++++++++++++++++++++++++++++ ccan/lstack/test/run.c | 62 +++++++++++++++++ 5 files changed, 276 insertions(+) create mode 120000 ccan/lstack/LICENSE create mode 100644 ccan/lstack/_info create mode 100644 ccan/lstack/lstack.h create mode 100644 ccan/lstack/test/run.c diff --git a/Makefile-ccan b/Makefile-ccan index 4205bcda..1388f892 100644 --- a/Makefile-ccan +++ b/Makefile-ccan @@ -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 index 00000000..2354d129 --- /dev/null +++ b/ccan/lstack/LICENSE @@ -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 index 00000000..5b270bcc --- /dev/null +++ b/ccan/lstack/_info @@ -0,0 +1,57 @@ +#include "config.h" +#include +#include + +/** + * 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 + * + * Example: + * #include + * + * 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 index 00000000..41a9f05a --- /dev/null +++ b/ccan/lstack/lstack.h @@ -0,0 +1,155 @@ +/* Licensed under BSD-MIT - see LICENSE file for details */ +#ifndef CCAN_LSTACK_H +#define CCAN_LSTACK_H + +#include +#include +#include + +#include + +/** + * 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 index 00000000..d67ba322 --- /dev/null +++ b/ccan/lstack/test/run.c @@ -0,0 +1,62 @@ +#include "config.h" + +#include +#include + +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(); +} -- 2.39.2