[ccan] [PATCH 1/4] queue: Simple queue implementation

[David Gibson]

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>
---
 ccan/queue/LICENSE    |   1 +
 ccan/queue/_info      |  26 ++++++++
 ccan/queue/queue.h    | 163 ++++++++++++++++++++++++++++++++++++++++++++++++++
 ccan/queue/test/run.c |  67 +++++++++++++++++++++
 4 files changed, 257 insertions(+)
 create mode 120000 ccan/queue/LICENSE
 create mode 100644 ccan/queue/_info
 create mode 100644 ccan/queue/queue.h
 create mode 100644 ccan/queue/test/run.c

diff --git a/ccan/queue/LICENSE b/ccan/queue/LICENSE
new file mode 120000
index 0000000..2354d12
--- /dev/null
+++ b/ccan/queue/LICENSE
@@ -0,0 +1 @@
+../../licenses/BSD-MIT
\ No newline at end of file
diff --git a/ccan/queue/_info b/ccan/queue/_info
new file mode 100644
index 0000000..8ed7045
--- /dev/null
+++ b/ccan/queue/_info
@@ -0,0 +1,26 @@
+#include "config.h"
+#include <stdio.h>
+#include <string.h>
+
+/**
+ * queue - 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 at gibson.dropbear.id.au>
+ */
+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/queue/queue.h b/ccan/queue/queue.h
new file mode 100644
index 0000000..04758ae
--- /dev/null
+++ b/ccan/queue/queue.h
@@ -0,0 +1,163 @@
+/* Licensed under BSD-MIT - see LICENSE file for details */
+#ifndef CCAN_QUEUE_H
+#define CCAN_QUEUE_H
+
+#include <stdbool.h>
+#include <stdio.h>
+#include <assert.h>
+
+#include <ccan/container_of/container_of.h>
+
+/**
+ * struct queue_entry - an entry in a queue
+ * @next: next entry, or front of queue, if this is the back
+ *
+ * This is used as an entry in a queue.
+ */
+struct queue_entry {
+	struct queue_entry *next;
+};
+
+/**
+ * struct queue - the head of a queue
+ * @b: the back of the queue (NULL if empty)
+ */
+struct queue {
+	struct queue_entry *back;
+};
+
+/**
+ * QUEUE - define and initialize an empty queue
+ * @name: the name of the queue.
+ *
+ * The QUEUE macro defines a queue and initializes it to an empty
+ * queue.  It can be prepended by "static" to define a static queue.
+ *
+ * See also:
+ *	queue_init()
+ *
+ * Example:
+ *	QUEUE(my_queue);
+ *
+ *	assert(queue_empty(&my_queue));
+ */
+#define QUEUE(name) \
+	struct queue name = { NULL, }
+
+/**
+ * queue_init - initialize a queue
+ * @h: the queue to set to an empty queue
+ *
+ * Example:
+ *	struct queue *qp = malloc(sizeof(*qp));
+ *	queue_init(qp);
+ */
+static inline void queue_init(struct queue *q)
+{
+	q->back = NULL;
+}
+
+/**
+ * queue_empty - is a queue empty?
+ * @q: the queue
+ *
+ * If the queue is empty, returns true.
+ *
+ * Example:
+ *	assert(queue_empty(qp));
+ */
+static inline bool queue_empty(const struct queue *q)
+{
+	return (q->back == NULL);
+}
+
+/**
+ * queue_front - get front entry in a queue
+ * @q: the queue
+ *
+ * If the queue is empty, returns NULL.
+ *
+ * Example:
+ *	struct queue_entry *fe;
+ *
+ *	fe = queue_front(qp);
+ *	assert(queue_dequeue(qp) == fe);
+ */
+static inline struct queue_entry *queue_front(const struct queue *q)
+{
+	if (!q->back)
+		return NULL;
+	else
+		return q->back->next;
+}
+
+/**
+ * queue_back - get back entry in a queue
+ * @q: the queue
+ *
+ * If the queue is empty, returns NULL.
+ *
+ * Example:
+ *	struct queue_entry be;
+ *
+ *	queue_enqueue(qp, &be);
+ *	assert(queue_back(qp) == &be);
+ */
+static inline struct queue_entry *queue_back(const struct queue *q)
+{
+	return q->back;
+}
+
+/**
+ * queue_enqueue - add an entry to the back of a queue
+ * @q: the queue to add the node to
+ * @e: the queue_entry to enqueue
+ *
+ * The queue_entry does not need to be initialized; it will be overwritten.
+ */
+static inline void queue_enqueue(struct queue *q, struct queue_entry *e)
+{
+	if (queue_empty(q)) {
+		/* New entry will be both front and back of queue */
+		e->next = e;
+		q->back = e;
+	} else {
+		e->next = queue_front(q);
+		q->back->next = e;
+		q->back = e;
+	}
+}
+
+/**
+ * queue_dequeue - remove and return the entry from the front of the queue
+ * @q: the queue
+ *
+ * Note that this leaves the returned queue_entry in an undefined
+ * state; it can be added to another queue, but not deleted again.
+ */
+static inline struct queue_entry *queue_dequeue(struct queue *q)
+{
+	struct queue_entry *front;
+
+	if (queue_empty(q))
+		return NULL;
+
+	front = queue_front(q);
+	if (front == queue_back(q)) {
+		assert(front->next == front);
+		q->back = NULL;
+	} else {
+		q->back->next = front->next;
+	}
+	return front;
+}
+
+/**
+ * queue_entry - convert a queue_entry back into the structure containing it.
+ * @e: the queue_entry
+ * @type: the type of the entry
+ * @member: the queue_entry member of the type
+ */
+#define queue_entry(n, type, member) container_of(n, type, member)
+
+#endif /* CCAN_LIST_H */
diff --git a/ccan/queue/test/run.c b/ccan/queue/test/run.c
new file mode 100644
index 0000000..f18d3bd
--- /dev/null
+++ b/ccan/queue/test/run.c
@@ -0,0 +1,67 @@
+#include <ccan/queue/queue.h>
+#include <ccan/tap/tap.h>
+
+struct entry {
+	const char *name;
+	struct queue_entry q;
+};
+
+int main(void)
+{
+	QUEUE(q);
+	struct entry a = { "Alice" };
+	struct entry b = { "Bob" };
+	struct entry c = { "Carol" };
+	struct entry *entry;
+
+	/* This is how many tests you plan to run */
+	plan_tests(25);
+
+	ok1(queue_empty(&q));
+	ok1(queue_front(&q) == NULL);
+	ok1(queue_back(&q) == NULL);
+
+	queue_enqueue(&q, &a.q);
+
+	ok1(!queue_empty(&q));
+	ok1(queue_front(&q) == &a.q);
+	ok1(queue_back(&q) == &a.q);
+
+	queue_enqueue(&q, &b.q);
+
+	ok1(!queue_empty(&q));
+	ok1(queue_front(&q) == &a.q);
+	ok1(queue_back(&q) == &b.q);
+
+	queue_enqueue(&q, &c.q);
+
+	ok1(!queue_empty(&q));
+	ok1(queue_front(&q) == &a.q);
+	ok1(queue_back(&q) == &c.q);
+
+	entry = queue_entry(queue_dequeue(&q), struct entry, q);
+	ok1(entry == &a);
+
+	ok1(!queue_empty(&q));
+	ok1(queue_front(&q) == &b.q);
+	ok1(queue_back(&q) == &c.q);
+
+	entry = queue_entry(queue_dequeue(&q), struct entry, q);
+	ok1(entry == &b);
+
+	ok1(!queue_empty(&q));
+	ok1(queue_front(&q) == &c.q);
+	ok1(queue_back(&q) == &c.q);
+
+	entry = queue_entry(queue_dequeue(&q), struct entry, q);
+	ok1(entry == &c);
+
+	ok1(queue_empty(&q));
+	ok1(queue_front(&q) == NULL);
+	ok1(queue_back(&q) == NULL);
+
+	ok1(queue_dequeue(&q) == NULL);
+
+	/* This exits depending on whether all tests passed */
+	return exit_status();
+}
-- 
1.9.3