From 195e8492de575a352f8bb38bbfedaf6f27902e40 Mon Sep 17 00:00:00 2001 From: David Gibson Date: Tue, 27 Oct 2015 22:10:27 +1100 Subject: [PATCH] lpq: New module Simple, slow priority queue implementation. Signed-off-by: David Gibson --- 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 82fc346b..456e0a1d 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 00000000..dc314eca --- /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 00000000..08dcda9b --- /dev/null +++ b/ccan/lpq/_info @@ -0,0 +1,40 @@ +#include "config.h" +#include +#include + +/** + * 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 + * 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 00000000..a93c4bea --- /dev/null +++ b/ccan/lpq/lpq.c @@ -0,0 +1,31 @@ +/* GNU LGPL version 2 (or later) - see LICENSE file for details */ +#include + +#include + +#include + +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 00000000..4f9dd6ae --- /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 + +#include +#include +#include + +/** + * 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 00000000..b1a6d16c --- /dev/null +++ b/ccan/lpq/test/api.c @@ -0,0 +1,112 @@ +#include +#include +#include +#include + +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.39.2