From e6944616bf0a671a0cf538c324b44f93f56b293a Mon Sep 17 00:00:00 2001 From: David Gibson Date: Wed, 10 Sep 2014 00:22:53 +1000 Subject: [PATCH] lqueue: Linked list queue implementation This new module provides a simple queue implementation as a singly linked (circular) list. Signed-off-by: David Gibson Signed-off-by: Rusty Russell --- Makefile-ccan | 1 + ccan/lqueue/LICENSE | 1 + ccan/lqueue/_info | 57 ++++++++++++ ccan/lqueue/lqueue.h | 191 +++++++++++++++++++++++++++++++++++++++++ ccan/lqueue/test/run.c | 69 +++++++++++++++ 5 files changed, 319 insertions(+) create mode 120000 ccan/lqueue/LICENSE create mode 100644 ccan/lqueue/_info create mode 100644 ccan/lqueue/lqueue.h create mode 100644 ccan/lqueue/test/run.c diff --git a/Makefile-ccan b/Makefile-ccan index 40d03891..4205bcda 100644 --- a/Makefile-ccan +++ b/Makefile-ccan @@ -68,6 +68,7 @@ MODS_WITH_SRC := antithread \ lbalance \ likely \ list \ + lqueue \ md4 \ memmem \ net \ diff --git a/ccan/lqueue/LICENSE b/ccan/lqueue/LICENSE new file mode 120000 index 00000000..2354d129 --- /dev/null +++ b/ccan/lqueue/LICENSE @@ -0,0 +1 @@ +../../licenses/BSD-MIT \ No newline at end of file diff --git a/ccan/lqueue/_info b/ccan/lqueue/_info new file mode 100644 index 00000000..4d7c6a40 --- /dev/null +++ b/ccan/lqueue/_info @@ -0,0 +1,57 @@ +#include "config.h" +#include +#include + +/** + * lqueue - Simple, singly-linked-list queue implementation + * + * This code provides a simple implementation of the Queue abstract + * data type in terms of a singly linked (circular) list. + * + * License: BSD-MIT + * Author: David Gibson + * + * Example: + * #include + * + * struct arg { + * const char *arg; + * struct lqueue_link ql; + * }; + * + * int main(int argc, char *argv[]) + * { + * int i; + * struct arg *a; + * LQUEUE(argq); + * + * for (i = 0; i < argc; i++) { + * a = malloc(sizeof(*a)); + * a->arg = argv[i]; + * lqueue_enqueue(&argq, a, ql); + * } + * + * printf("Command line arguments in order:\n"); + * + * while (!lqueue_empty(&argq)) { + * a = lqueue_dequeue(&argq, struct arg, ql); + * 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/lqueue/lqueue.h b/ccan/lqueue/lqueue.h new file mode 100644 index 00000000..15d242ef --- /dev/null +++ b/ccan/lqueue/lqueue.h @@ -0,0 +1,191 @@ +/* Licensed under BSD-MIT - see LICENSE file for details */ +#ifndef CCAN_LQUEUE_H +#define CCAN_LQUEUE_H + +#include +#include +#include + +#include + +/** + * struct lqueue_link - a queue link + * @next: next entry, or front of queue, if this is the back + * + * This is used as a link within a queue entry. + * + * Example: + * struct waiter { + * char *name; + * struct lqueue_link ql; + * }; + */ +struct lqueue_link { + struct lqueue_link *next; +}; + +/** + * struct lqueue - the head of a queue + * @b: the back of the queue (NULL if empty) + */ +struct lqueue { + struct lqueue_link *back; +}; + +/** + * LQUEUE - define and initialize an empty queue + * @name: the name of the lqueue. + * + * The LQUEUE macro defines an lqueue and initializes it to an empty + * queue. It can be prepended by "static" to define a static lqueue. + * + * See also: + * lqueue_init() + * + * Example: + * LQUEUE(my_queue); + * + * assert(lqueue_empty(&my_queue)); + */ +#define LQUEUE(name) \ + struct lqueue name = { NULL, } + +/** + * lqueue_init - initialize a queue + * @h: the lqueue to set to an empty queue + * + * Example: + * struct lqueue *qp = malloc(sizeof(*qp)); + * lqueue_init(qp); + */ +static inline void lqueue_init(struct lqueue *q) +{ + q->back = NULL; +} + +/** + * lqueue_empty - is a queue empty? + * @q: the queue + * + * If the queue is empty, returns true. + * + * Example: + * assert(lqueue_empty(qp)); + */ +static inline bool lqueue_empty(const struct lqueue *q) +{ + return (q->back == NULL); +} + +/** + * lqueue_entry - convert an lqueue_link back into the structure containing it. + * @e: the lqueue_link + * @type: the type of the entry + * @member: the lqueue_link member of the type + * + * Example: + * struct waiter { + * char *name; + * struct lqueue_link ql; + * } w; + * assert(lqueue_entry(&w.ql, struct waiter, ql) == &w); + */ +#define lqueue_entry(n, type, member) container_of_or_null(n, type, member) + +/** + * lqueue_front - get front entry in a queue + * @q: the queue + * @type: the type of queue entries + * @member: the lqueue_link entry + * + * If the queue is empty, returns NULL. + * + * Example: + * struct waiter *f; + * + * f = lqueue_front(qp, struct waiter, ql); + * assert(lqueue_dequeue(qp, struct waiter, ql) == f); + */ +#define lqueue_front(q, type, member) \ + lqueue_entry(lqueue_front_((q)), type, member) +static inline struct lqueue_link *lqueue_front_(const struct lqueue *q) +{ + if (!q->back) + return NULL; + else + return q->back->next; +} + +/** + * lqueue_back - get back entry in a queue + * @q: the queue + * @type: the type of queue entries + * @member: the lqueue_link entry + * + * If the queue is empty, returns NULL. + * + * Example: + * struct waiter b; + * + * lqueue_enqueue(qp, &b, ql); + * assert(lqueue_back(qp, struct waiter, ql) == &b); + */ +#define lqueue_back(q, type, member) \ + lqueue_entry(lqueue_back_((q)), type, member) +static inline struct lqueue_link *lqueue_back_(const struct lqueue *q) +{ + return q->back; +} + +/** + * lqueue_enqueue - add an entry to the back of a queue + * @q: the queue to add the node to + * @e: the item to enqueue + * @member: the lqueue_link field of *e + * + * The lqueue_link does not need to be initialized; it will be overwritten. + */ +#define lqueue_enqueue(q, e, member) \ + lqueue_enqueue_((q), &((e)->member)) +static inline void lqueue_enqueue_(struct lqueue *q, struct lqueue_link *e) +{ + if (lqueue_empty(q)) { + /* New entry will be both front and back of queue */ + e->next = e; + q->back = e; + } else { + e->next = lqueue_front_(q); + q->back->next = e; + q->back = e; + } +} + +/** + * lqueue_dequeue - remove and return the entry from the front of the queue + * @q: the queue + * @type: the type of queue entries + * @member: the lqueue_link field of @type + * + * Note that this leaves the returned entry's link in an undefined + * state; it can be added to another queue, but not deleted again. + */ +#define lqueue_dequeue(q, type, member) \ + lqueue_entry(lqueue_dequeue_((q)), type, member) +static inline struct lqueue_link *lqueue_dequeue_(struct lqueue *q) +{ + struct lqueue_link *front; + + if (lqueue_empty(q)) + return NULL; + + front = lqueue_front_(q); + if (front == lqueue_back_(q)) { + assert(front->next == front); + q->back = NULL; + } else { + q->back->next = front->next; + } + return front; +} + +#endif /* CCAN_LQUEUE_H */ diff --git a/ccan/lqueue/test/run.c b/ccan/lqueue/test/run.c new file mode 100644 index 00000000..b10b4cd1 --- /dev/null +++ b/ccan/lqueue/test/run.c @@ -0,0 +1,69 @@ +#include "config.h" + +#include +#include + +struct waiter { + const char *name; + struct lqueue_link ql; +}; + +int main(void) +{ + LQUEUE(q); + struct waiter a = { "Alice" }; + struct waiter b = { "Bob" }; + struct waiter c = { "Carol" }; + struct waiter *waiter; + + /* This is how many tests you plan to run */ + plan_tests(25); + + ok1(lqueue_empty(&q)); + ok1(lqueue_front(&q, struct waiter, ql) == NULL); + ok1(lqueue_back(&q, struct waiter, ql) == NULL); + + lqueue_enqueue(&q, &a, ql); + + ok1(!lqueue_empty(&q)); + ok1(lqueue_front(&q, struct waiter, ql) == &a); + ok1(lqueue_back(&q, struct waiter, ql) == &a); + + lqueue_enqueue(&q, &b, ql); + + ok1(!lqueue_empty(&q)); + ok1(lqueue_front(&q, struct waiter, ql) == &a); + ok1(lqueue_back(&q, struct waiter, ql) == &b); + + lqueue_enqueue(&q, &c, ql); + + ok1(!lqueue_empty(&q)); + ok1(lqueue_front(&q, struct waiter, ql) == &a); + ok1(lqueue_back(&q, struct waiter, ql) == &c); + + waiter = lqueue_dequeue(&q, struct waiter, ql); + ok1(waiter == &a); + + ok1(!lqueue_empty(&q)); + ok1(lqueue_front(&q, struct waiter, ql) == &b); + ok1(lqueue_back(&q, struct waiter, ql) == &c); + + waiter = lqueue_dequeue(&q, struct waiter, ql); + ok1(waiter == &b); + + ok1(!lqueue_empty(&q)); + ok1(lqueue_front(&q, struct waiter, ql) == &c); + ok1(lqueue_back(&q, struct waiter, ql) == &c); + + waiter = lqueue_dequeue(&q, struct waiter, ql); + ok1(waiter == &c); + + ok1(lqueue_empty(&q)); + ok1(lqueue_front(&q, struct waiter, ql) == NULL); + ok1(lqueue_back(&q, struct waiter, ql) == NULL); + + ok1(lqueue_dequeue(&q, struct waiter, ql) == NULL); + + /* This exits depending on whether all tests passed */ + return exit_status(); +} -- 2.39.2