lqueue: Linked list queue implementation
authorDavid Gibson <david@gibson.dropbear.id.au>
Tue, 9 Sep 2014 14:22:53 +0000 (00:22 +1000)
committerRusty Russell <rusty@rustcorp.com.au>
Sat, 13 Sep 2014 05:49:34 +0000 (15:19 +0930)
This new module provides a simple queue implementation as a singly
linked (circular) list.

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

index 40d03891e47c6e619c78b31466c1ea6538ee1ba4..4205bcdaeee035d79def0bf103a899d62e71bcb6 100644 (file)
@@ -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 (symlink)
index 0000000..2354d12
--- /dev/null
@@ -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 (file)
index 0000000..4d7c6a4
--- /dev/null
@@ -0,0 +1,57 @@
+#include "config.h"
+#include <stdio.h>
+#include <string.h>
+
+/**
+ * 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 <david@gibson.dropbear.id.au>
+ *
+ * Example:
+ *     #include <ccan/lqueue/lqueue.h>
+ *
+ *     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 (file)
index 0000000..15d242e
--- /dev/null
@@ -0,0 +1,191 @@
+/* Licensed under BSD-MIT - see LICENSE file for details */
+#ifndef CCAN_LQUEUE_H
+#define CCAN_LQUEUE_H
+
+#include <stdbool.h>
+#include <stdio.h>
+#include <assert.h>
+
+#include <ccan/container_of/container_of.h>
+
+/**
+ * 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 (file)
index 0000000..b10b4cd
--- /dev/null
@@ -0,0 +1,69 @@
+#include "config.h"
+
+#include <ccan/lqueue/lqueue.h>
+#include <ccan/tap/tap.h>
+
+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();
+}