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 <david@gibson.dropbear.id.au>

diff --git a/ccan/order/LICENSE b/ccan/order/LICENSE
new file mode 120000 (symlink)
index 0000000..b7951da
--- /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 (file)
index 0000000..5a68f67
--- /dev/null
+++ b/ccan/order/_info
@@ -0,0 +1,30 @@
+#include "config.h"
+#include <stdio.h>
+#include <string.h>
+
+/**
+ * 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 <david@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/order.h b/ccan/order/order.h
new file mode 100644 (file)
index 0000000..f5dac81
--- /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 <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_H */

diff --git a/ccan/order/test/compile_fail_1.c b/ccan/order/test/compile_fail_1.c
new file mode 100644 (file)
index 0000000..ba63ca1
--- /dev/null
+++ b/ccan/order/test/compile_fail_1.c
@@ -0,0 +1,24 @@
+#include <stdlib.h>
+#include <string.h>
+#include <stdio.h>
+
+#include <ccan/order/order.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/test/compile_fail_2.c b/ccan/order/test/compile_fail_2.c
new file mode 100644 (file)
index 0000000..5a7126d
--- /dev/null
+++ b/ccan/order/test/compile_fail_2.c
@@ -0,0 +1,25 @@
+#include <stdlib.h>
+#include <string.h>
+#include <stdio.h>
+
+#include <ccan/order/order.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/test/compile_ok.c b/ccan/order/test/compile_ok.c
new file mode 100644 (file)
index 0000000..33a4204
--- /dev/null
+++ b/ccan/order/test/compile_ok.c
@@ -0,0 +1,19 @@
+#include <stdlib.h>
+#include <string.h>
+#include <stdio.h>
+
+#include <ccan/order/order.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/test/fancy_cmp.h b/ccan/order/test/fancy_cmp.h
new file mode 100644 (file)
index 0000000..b794037
--- /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 */