[ccan] [PATCH 1/4] order_functions: Module for comparison callbacks
David Gibson
david at gibson.dropbear.id.au
Mon Jun 1 20:21:05 AEST 2015
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 <david at gibson.dropbear.id.au>
---
ccan/order_functions/LICENSE | 1 +
ccan/order_functions/_info | 30 +++++++++++++++++++
ccan/order_functions/order_functions.h | 33 +++++++++++++++++++++
ccan/order_functions/test/compile_fail_1.c | 24 +++++++++++++++
ccan/order_functions/test/compile_fail_2.c | 25 ++++++++++++++++
ccan/order_functions/test/compile_ok.c | 19 ++++++++++++
ccan/order_functions/test/fancy_cmp.h | 47 ++++++++++++++++++++++++++++++
7 files changed, 179 insertions(+)
create mode 120000 ccan/order_functions/LICENSE
create mode 100644 ccan/order_functions/_info
create mode 100644 ccan/order_functions/order_functions.h
create mode 100644 ccan/order_functions/test/compile_fail_1.c
create mode 100644 ccan/order_functions/test/compile_fail_2.c
create mode 100644 ccan/order_functions/test/compile_ok.c
create mode 100644 ccan/order_functions/test/fancy_cmp.h
diff --git a/ccan/order_functions/LICENSE b/ccan/order_functions/LICENSE
new file mode 120000
index 0000000..b7951da
--- /dev/null
+++ b/ccan/order_functions/LICENSE
@@ -0,0 +1 @@
+../../licenses/CC0
\ No newline at end of file
diff --git a/ccan/order_functions/_info b/ccan/order_functions/_info
new file mode 100644
index 0000000..28fe845
--- /dev/null
+++ b/ccan/order_functions/_info
@@ -0,0 +1,30 @@
+#include "config.h"
+#include <stdio.h>
+#include <string.h>
+
+/**
+ * order_functions - 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 <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/typesafe_cb\n");
+ return 0;
+ }
+ if (strcmp(argv[1], "testdepends") == 0) {
+ return 0;
+ }
+
+ return 1;
+}
diff --git a/ccan/order_functions/order_functions.h b/ccan/order_functions/order_functions.h
new file mode 100644
index 0000000..a2beb33
--- /dev/null
+++ b/ccan/order_functions/order_functions.h
@@ -0,0 +1,33 @@
+/* CC0 license (public domain) - see LICENSE file for details */
+#ifndef CCAN_ORDER_FUNCTIONS_H
+#define CCAN_ORDER_FUNCTIONS_H
+
+#include <stdint.h>
+#include <assert.h>
+
+#include <ccan/typesafe_cb/typesafe_cb.h>
+
+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_FUNCTIONS_H */
diff --git a/ccan/order_functions/test/compile_fail_1.c b/ccan/order_functions/test/compile_fail_1.c
new file mode 100644
index 0000000..29897d9
--- /dev/null
+++ b/ccan/order_functions/test/compile_fail_1.c
@@ -0,0 +1,24 @@
+#include <stdlib.h>
+#include <string.h>
+#include <stdio.h>
+
+#include <ccan/order_functions/order_functions.h>
+
+#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_functions/test/compile_fail_2.c b/ccan/order_functions/test/compile_fail_2.c
new file mode 100644
index 0000000..854f44b
--- /dev/null
+++ b/ccan/order_functions/test/compile_fail_2.c
@@ -0,0 +1,25 @@
+#include <stdlib.h>
+#include <string.h>
+#include <stdio.h>
+
+#include <ccan/order_functions/order_functions.h>
+
+#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_functions/test/compile_ok.c b/ccan/order_functions/test/compile_ok.c
new file mode 100644
index 0000000..73381d3
--- /dev/null
+++ b/ccan/order_functions/test/compile_ok.c
@@ -0,0 +1,19 @@
+#include <stdlib.h>
+#include <string.h>
+#include <stdio.h>
+
+#include <ccan/order_functions/order_functions.h>
+
+#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_functions/test/fancy_cmp.h b/ccan/order_functions/test/fancy_cmp.h
new file mode 100644
index 0000000..b794037
--- /dev/null
+++ b/ccan/order_functions/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 */
--
2.4.2
More information about the ccan
mailing list