From: David Gibson Date: Tue, 2 Jun 2015 07:26:49 +0000 (+1000) Subject: order: Module for comparison callbacks X-Git-Url: http://git.ozlabs.org/?p=ccan;a=commitdiff_plain;h=c2a3098b254830f33e800bfa398882786632631e order: Module for comparison callbacks Many common algorithms take a callback for comparing items - effectively giving the items a user defined order. For example, the standard library qsort() and bsearch() routines take such a callback. The ccan/avl module takes an identical one. The ccan/asort and ccan/asearch modules use a different variant: their callback takes an additional context parameter, and is also typed via use of macros and typesafe_cb. This module provides helper types and macros for easily declaring any of the common variants on comparison functions: the 2-parameter untyped form (as used by qsort), the 3-parameter untyped form (used by the asort back end) and the 3-parameter typed form (used by the asort front end). It provides a wrapper macro for doing the typesafe_cb conversion from 3-parameter typed to 3-parameter untyped. It also provides a container struct to describe both a comparison callback and a context value as a single structure. This also comes in both untyped and typed variants. Signed-off-by: David Gibson --- diff --git a/ccan/order/LICENSE b/ccan/order/LICENSE new file mode 120000 index 00000000..b7951dab --- /dev/null +++ b/ccan/order/LICENSE @@ -0,0 +1 @@ +../../licenses/CC0 \ No newline at end of file diff --git a/ccan/order/_info b/ccan/order/_info new file mode 100644 index 00000000..5a68f674 --- /dev/null +++ b/ccan/order/_info @@ -0,0 +1,30 @@ +#include "config.h" +#include +#include + +/** + * order - Simple, common value comparison functions + * + * This implements a number of commonly useful comparison functions in + * a form which can be used with qsort() and bsearch() in the standard + * library, or asort() and asearch() in ccan amongst other places. + * + * License: CC0 + * Author: David Gibson + */ +int main(int argc, char *argv[]) +{ + /* Expect exactly one argument */ + if (argc != 2) + return 1; + + if (strcmp(argv[1], "depends") == 0) { + printf("ccan/typesafe_cb\n"); + return 0; + } + if (strcmp(argv[1], "testdepends") == 0) { + return 0; + } + + return 1; +} diff --git a/ccan/order/order.h b/ccan/order/order.h new file mode 100644 index 00000000..f5dac818 --- /dev/null +++ b/ccan/order/order.h @@ -0,0 +1,33 @@ +/* CC0 license (public domain) - see LICENSE file for details */ +#ifndef CCAN_ORDER_H +#define CCAN_ORDER_H + +#include +#include + +#include + +typedef int (*_total_order_cb)(const void *, const void *, void *); +typedef int (*total_order_noctx_cb)(const void *, const void *); + +#define total_order_cb(_name, _item, _ctx) \ + int (*_name)(const __typeof__(_item) *, \ + const __typeof__(_item) *, \ + __typeof__(_ctx)) + +#define total_order_cast(cmp, item, ctx) \ + typesafe_cb_cast(_total_order_cb, total_order_cb(, item, ctx), \ + (cmp)) + +struct _total_order { + _total_order_cb cb; + void *ctx; +}; + +#define total_order(_name, _item, _ctx) \ + struct { \ + total_order_cb(cb, _item, _ctx); \ + _ctx ctx; \ + } _name + +#endif /* CCAN_ORDER_H */ diff --git a/ccan/order/test/compile_fail_1.c b/ccan/order/test/compile_fail_1.c new file mode 100644 index 00000000..ba63ca1e --- /dev/null +++ b/ccan/order/test/compile_fail_1.c @@ -0,0 +1,24 @@ +#include +#include +#include + +#include + +#include "fancy_cmp.h" + +#ifdef FAIL +typedef int item_t; +#else +typedef struct item item_t; +#endif + +int main(int argc, char *argv[]) +{ + total_order_cb(cb0, struct item, struct cmp_info *) = fancy_cmp; + _total_order_cb cb1 = total_order_cast(fancy_cmp, + item_t, struct cmp_info *); + + printf("%p %p\n", cb0, cb1); + + exit(0); +} diff --git a/ccan/order/test/compile_fail_2.c b/ccan/order/test/compile_fail_2.c new file mode 100644 index 00000000..5a7126d8 --- /dev/null +++ b/ccan/order/test/compile_fail_2.c @@ -0,0 +1,25 @@ +#include +#include +#include + +#include + +#include "fancy_cmp.h" + +#ifdef FAIL +typedef int ctx_t; +#else +typedef struct cmp_info ctx_t; +#endif + +int main(int argc, char *argv[]) +{ + total_order_cb(cb0, struct item, struct cmp_info *) = fancy_cmp; + _total_order_cb cb1 = total_order_cast(fancy_cmp, struct item, + ctx_t *); + + printf("%p %p\n", cb0, cb1); + + exit(0); + +} diff --git a/ccan/order/test/compile_ok.c b/ccan/order/test/compile_ok.c new file mode 100644 index 00000000..33a42042 --- /dev/null +++ b/ccan/order/test/compile_ok.c @@ -0,0 +1,19 @@ +#include +#include +#include + +#include + +#include "fancy_cmp.h" + +int main(int argc, char *argv[]) +{ + total_order_cb(cb0, struct item, struct cmp_info *) = fancy_cmp; + _total_order_cb cb1 = total_order_cast(fancy_cmp, + struct item, struct cmp_info *); + total_order_noctx_cb cb_noctx = fancy_cmp_noctx; + + printf("%p %p %p\n", cb0, cb1, cb_noctx); + + exit(0); +} diff --git a/ccan/order/test/fancy_cmp.h b/ccan/order/test/fancy_cmp.h new file mode 100644 index 00000000..b7940377 --- /dev/null +++ b/ccan/order/test/fancy_cmp.h @@ -0,0 +1,47 @@ +#ifndef _FANCY_CMP_H +#define _FANCY_CMP_H + +struct cmp_info { + unsigned xcode; + int offset; +}; + +struct item { + unsigned value; + char *str; +}; + +static inline int fancy_cmp(const struct item *a, const struct item *b, + struct cmp_info *ctx) +{ + unsigned vala = a->value ^ ctx->xcode; + unsigned valb = b->value ^ ctx->xcode; + const char *stra, *strb; + + if (vala < valb) + return -1; + else if (valb < vala) + return 1; + + stra = a->str + ctx->offset; + strb = b->str + ctx->offset; + + return strcmp(stra, strb); +} + +static inline int fancy_cmp_noctx(const void *av, const void *bv) +{ + const struct item *a = (const struct item *)av; + const struct item *b = (const struct item *)bv; + struct cmp_info ctx_default = { + .xcode = 0x1234, + .offset = 3, + }; + total_order(default_order, struct item, struct cmp_info *) = { + fancy_cmp, &ctx_default, + }; + + return default_order.cb(a, b, default_order.ctx); +} + +#endif /* _FANCY_CMP_H */