[ccan] [PATCH] lpq: New module
David Gibson
david at gibson.dropbear.id.au
Tue Oct 27 22:11:18 AEDT 2015
Simple, slow priority queue implementation.
Signed-off-by: David Gibson <david at gibson.dropbear.id.au>
---
Makefile-ccan | 1 +
ccan/lpq/LICENSE | 1 +
ccan/lpq/_info | 40 ++++++++++++
ccan/lpq/lpq.c | 31 +++++++++
ccan/lpq/lpq.h | 185 ++++++++++++++++++++++++++++++++++++++++++++++++++++
ccan/lpq/test/api.c | 112 +++++++++++++++++++++++++++++++
6 files changed, 370 insertions(+)
create mode 120000 ccan/lpq/LICENSE
create mode 100644 ccan/lpq/_info
create mode 100644 ccan/lpq/lpq.c
create mode 100644 ccan/lpq/lpq.h
create mode 100644 ccan/lpq/test/api.c
diff --git a/Makefile-ccan b/Makefile-ccan
index 82fc346..456e0a1 100644
--- a/Makefile-ccan
+++ b/Makefile-ccan
@@ -79,6 +79,7 @@ MODS_WITH_SRC := aga \
lbalance \
likely \
list \
+ lpq \
md4 \
mem \
net \
diff --git a/ccan/lpq/LICENSE b/ccan/lpq/LICENSE
new file mode 120000
index 0000000..dc314ec
--- /dev/null
+++ b/ccan/lpq/LICENSE
@@ -0,0 +1 @@
+../../licenses/LGPL-2.1
\ No newline at end of file
diff --git a/ccan/lpq/_info b/ccan/lpq/_info
new file mode 100644
index 0000000..08dcda9
--- /dev/null
+++ b/ccan/lpq/_info
@@ -0,0 +1,40 @@
+#include "config.h"
+#include <stdio.h>
+#include <string.h>
+
+/**
+ * lpq - Simple, slow priority queue implementation
+ *
+ * This code implements a priority queue. This is a trivial linked
+ * list implementation, which is simple and generally slow.
+ *
+ * init: O(1)
+ * enqueue: O(1)
+ * front: O(n)
+ * dequeue: O(n)
+ * reorder: O(1)
+ *
+ * Author: David Gibson <david at gibson.dropbear.id.au>
+ * License: LGPL (v2.1 or any later version)
+ */
+int main(int argc, char *argv[])
+{
+ /* Expect exactly one argument */
+ if (argc != 2)
+ return 1;
+
+ if (strcmp(argv[1], "depends") == 0) {
+ printf("ccan/tcon\n");
+ printf("ccan/order\n");
+ printf("ccan/cast\n");
+ return 0;
+ }
+
+ if (strcmp(argv[1], "testdepends") == 0) {
+ printf("ccan/permutation\n");
+ printf("ccan/array_size\n");
+ return 0;
+ }
+
+ return 1;
+}
diff --git a/ccan/lpq/lpq.c b/ccan/lpq/lpq.c
new file mode 100644
index 0000000..a93c4be
--- /dev/null
+++ b/ccan/lpq/lpq.c
@@ -0,0 +1,31 @@
+/* GNU LGPL version 2 (or later) - see LICENSE file for details */
+#include <assert.h>
+
+#include <ccan/cast/cast.h>
+
+#include <ccan/lpq/lpq.h>
+
+static int lpq_cmp(const struct lpq_ *pq, size_t offset,
+ const struct lpq_link *al, const struct lpq_link *bl)
+{
+ void *a = (char *)al - offset;
+ void *b = (char *)bl - offset;
+
+ return total_order_cmp(pq->order, a, b);
+}
+
+struct lpq_link **lpq_frontp_(struct lpq_ *pq, size_t offset)
+{
+ struct lpq_link **frontp = &pq->list;
+ struct lpq_link **p;
+
+ if (lpq_empty_(pq))
+ return NULL;
+
+ for (p = &(pq->list->next); *p; p = &(*p)->next) {
+ if (lpq_cmp(pq, offset, *p, *frontp) >= 0)
+ frontp = p;
+ }
+
+ return frontp;
+}
diff --git a/ccan/lpq/lpq.h b/ccan/lpq/lpq.h
new file mode 100644
index 0000000..4f9dd6a
--- /dev/null
+++ b/ccan/lpq/lpq.h
@@ -0,0 +1,185 @@
+/* GNU LGPL version 2 (or later) - see LICENSE file for details */
+#ifndef CCAN_LPQ_H
+#define CCAN_LPQ_H
+
+#include <stdbool.h>
+
+#include <ccan/cast/cast.h>
+#include <ccan/tcon/tcon.h>
+#include <ccan/order/order.h>
+
+/**
+ * struct lpq_link - a priority link
+ * @next: next entry in the list of items in the priority queue
+ *
+ * This is used as a link within a priority queue entry.
+ *
+ * Example:
+ * struct waiter {
+ * char *name;
+ * int priority;
+ * struct lpq_link pql;
+ * };
+ */
+struct lpq_link {
+ struct lpq_link *next;
+};
+
+/**
+ * struct lpq_ - a linear priority queue (internal type)
+ * @order: ordering callback to compare entry priorities
+ * @list: head of the list of items in the priority queue
+ */
+struct lpq_ {
+ struct _total_order order;
+ struct lpq_link *list;
+};
+
+/**
+ * LPQ - define and initialize an empty priority queue
+ * @type: type of items in the queue / items compared by the callback
+ * @link: name of the lpq_link field in @type
+ *
+ * The LPQ macro defines an lpq and initializes it to an empty
+ * priority queue. It can be prepended by "static" to define a static
+ * lpq.
+ *
+ * See also:
+ * lpq_init()
+ */
+#define LPQ(etype_, link_) \
+ TCON_WRAP(struct lpq_, \
+ TCON_CONTAINER(canary, etype_, link_))
+
+/**
+ * lpq_init - initialize a priority queue
+ * @pq: the lpq to set to an empty queue
+ * @order: priority ordering callback for items in the queue
+ *
+ * Example:
+ * total_order_by_field(my_order, int, struct waiter, priority);
+ * LPQ(struct waiter, pql) *pqp = malloc(sizeof(*pqp));
+ * lpq_init(pqp, my_order.cb, my_order.ctx);
+ */
+#define lpq_init(pq_, order_cb_, order_ctx_) \
+ lpq_init_(tcon_unwrap(pq_), \
+ total_order_cast((order_cb_), \
+ tcon_container_type((pq_), canary), \
+ (order_ctx_)), \
+ (order_ctx_))
+static inline void lpq_init_(struct lpq_ *pq,
+ _total_order_cb order_cb, void *order_ctx)
+{
+ pq->order.cb = order_cb;
+ pq->order.ctx = order_ctx;
+ pq->list = NULL;
+}
+
+/**
+ * lpq_empty - is a priority queue empty?
+ * @pq: the priority queue
+ *
+ * If the priority queue is empty, returns true.
+ */
+#define lpq_empty(pq_) \
+ lpq_empty_(tcon_unwrap(pq_))
+static inline bool lpq_empty_(const struct lpq_ *pq)
+{
+ return (pq->list == NULL);
+}
+
+/**
+ * lpq_entry - convert an lpq_link back into the structure containing it.
+ * @pq: the priority queue
+ * @l: the lpq_link
+ */
+#define lpq_entry(pq_, l_) tcon_container_of((pq_), canary, (l_))
+
+/**
+ * lpq_frontp_ - get pointer to pointer to front element (internal function)
+ */
+struct lpq_link **lpq_frontp_(struct lpq_ *pq, size_t offset);
+
+/**
+ * lpq_front - get front (highest priority) entry in a priority queue
+ * @pq: the priority queue
+ *
+ * If the priority queue is empty, returns NULL.
+ *
+ * Example:
+ * struct waiter *f;
+ *
+ * f = lpq_front(pqp);
+ * assert(lpq_dequeue(pqp) == f);
+ */
+#define lpq_front(pq_) \
+ lpq_entry((pq_), lpq_front_(tcon_unwrap(pq_), \
+ tcon_offset((pq_), canary)))
+static inline struct lpq_link *lpq_front_(const struct lpq_ *pq, size_t offset)
+{
+ struct lpq_link **frontp = lpq_frontp_(cast_const(struct lpq_ *, pq),
+ offset);
+
+ return frontp ? *frontp : NULL;
+}
+
+/**
+ * lpq_enqueue - add an entry to a priority queue
+ * @pq: the priority queue to add the node to
+ * @e: the item to enqueue
+ *
+ * The lpq_link does not need to be initialized; it will be overwritten.
+ */
+#define lpq_enqueue(pq_, e_) \
+ lpq_enqueue_(tcon_unwrap(pq_), tcon_member_of((pq_), canary, (e_)))
+static inline void lpq_enqueue_(struct lpq_ *pq, struct lpq_link *e)
+{
+ e->next = pq->list;
+ pq->list = e;
+}
+
+/**
+ * lpq_dequeue - remove and return the highest priority item from the
+ * priority queue
+ * @pq: the priority queue
+ *
+ * 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 lpq_dequeue(pq_) \
+ lpq_entry((pq_), lpq_dequeue_(tcon_unwrap(pq_), \
+ tcon_offset((pq_), canary)))
+static inline struct lpq_link *lpq_dequeue_(struct lpq_ *pq, size_t offset)
+{
+ struct lpq_link **frontp = lpq_frontp_(pq, offset);
+ struct lpq_link *front;
+
+ if (!frontp)
+ return NULL;
+
+ front = *frontp;
+ *frontp = front->next;
+ return front;
+}
+
+/**
+ * lpq_reorder - adjust the queue after an element changes priority
+ * @pq: the priority queue
+ * @e: the entry which has changed priority
+ *
+ * If any element already inserted into @pq is altered to change its
+ * priority, lpq_reorder() must be called before any other function is
+ * called on @pq.
+ *
+ * NOTE: For the dumb priority queue implementation in lpq, this is
+ * actually a no-op. But this call exists so that users will be more
+ * easily able to change to a better priority queue implementation
+ * later.
+ */
+#define lpq_reorder(pq_, e_) \
+ (lpq_reorder_(tcon_unwrap(pq_), tcon_member_of((pq_), canary, (e_))))
+static inline void lpq_reorder_(struct lpq_ *pq, struct lpq_link *e)
+{
+}
+
+#endif /* CCAN_LPQ_H */
diff --git a/ccan/lpq/test/api.c b/ccan/lpq/test/api.c
new file mode 100644
index 0000000..b1a6d16
--- /dev/null
+++ b/ccan/lpq/test/api.c
@@ -0,0 +1,112 @@
+#include <ccan/lpq/lpq.h>
+#include <ccan/array_size/array_size.h>
+#include <ccan/permutation/permutation.h>
+#include <ccan/tap/tap.h>
+
+struct waiter {
+ int intval;
+ float floatval;
+ struct lpq_link link;
+};
+
+static void test_array(struct waiter *waiters, int n,
+ total_order_cb(order_cb, struct waiter, ptrint_t *),
+ ptrint_t *order_ctx, bool invert)
+{
+ LPQ(struct waiter, link) pq;
+ struct permutation *pi = permutation_new(n);
+ int i;
+
+ lpq_init(&pq, order_cb, order_ctx);
+
+ ok1(lpq_empty(&pq));
+ ok1(lpq_front(&pq) == NULL);
+ ok1(lpq_dequeue(&pq) == NULL);
+ ok1(lpq_empty(&pq));
+
+ do {
+ for (i = 0; i < n; i++) {
+ lpq_enqueue(&pq, &waiters[pi->v[i]]);
+ ok1(!lpq_empty(&pq));
+ ok1(lpq_front(&pq) != NULL);
+ }
+
+ for (i = 0; i < n; i++) {
+ int expected = invert ? i : (n - 1 - i);
+
+ ok1(!lpq_empty(&pq));
+ ok1(lpq_front(&pq) == &waiters[expected]);
+ ok1(lpq_dequeue(&pq) == &waiters[expected]);
+ }
+
+ ok1(lpq_empty(&pq));
+ } while (permutation_change(pi));
+ free(pi);
+}
+
+#define ARRAY_NTESTS(arr) \
+ ((1 + 5 * ARRAY_SIZE(arr)) * permutation_count(ARRAY_SIZE(arr)) + 4)
+
+static void test_reorder(void)
+{
+ struct waiter waiters[] = {
+ { .intval = -1, },
+ { .intval = 0, },
+ { .intval = 1, },
+ { .intval = 12, },
+ };
+ int n = ARRAY_SIZE(waiters);
+ total_order_by_field(order, int, struct waiter, intval);
+ LPQ(struct waiter, link) pq;
+ int i;
+
+ lpq_init(&pq, order.cb, order.ctx);
+
+ for (i = 0; i < n; i++)
+ lpq_enqueue(&pq, &waiters[i]);
+
+ for (i = 0; i < n; i++) {
+ waiters[i].intval = -waiters[i].intval;
+ lpq_reorder(&pq, &waiters[i]);
+ }
+
+ for (i = 0; i < n; i++) {
+ ok1(lpq_dequeue(&pq) == &waiters[i]);
+ }
+
+ ok1(lpq_empty(&pq));
+}
+
+int main(void)
+{
+ struct waiter w1[] = {
+ { .intval = -1, },
+ { .intval = 0, },
+ { .intval = 1, },
+ { .intval = 12, },
+ };
+ total_order_by_field(order1, int, struct waiter, intval);
+ total_order_by_field(order1r, int_reverse, struct waiter, intval);
+ struct waiter w2[] = {
+ { .floatval = 0.01, },
+ { .floatval = 0.1, },
+ { .floatval = 0.2 },
+ { .floatval = 1.0E+18, },
+ };
+ total_order_by_field(order2, float, struct waiter, floatval);
+ total_order_by_field(order2r, float_reverse, struct waiter, floatval);
+
+ /* This is how many tests you plan to run */
+ plan_tests(2 * (ARRAY_NTESTS(w1) + ARRAY_NTESTS(w2)) + 5);
+
+ test_array(w1, ARRAY_SIZE(w1), order1.cb, order1.ctx, false);
+ test_array(w1, ARRAY_SIZE(w1), order1r.cb, order1r.ctx, true);
+
+ test_array(w2, ARRAY_SIZE(w2), order2.cb, order2.ctx, false);
+ test_array(w2, ARRAY_SIZE(w2), order2r.cb, order2r.ctx, true);
+
+ test_reorder();
+
+ /* This exits depending on whether all tests passed */
+ return exit_status();
+}
--
2.4.3
More information about the ccan
mailing list