order: Scalar comparison functions

Extend the order module to provide simple, standard, comparison
callbacks for scalar types (i.e. integer and floating point types).

In addition to the usual variants comparing a plain scalar, this also
provides helper macros to construct a suitably typed callback and context
pointer to order structures by a specified scalar field.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>

diff --git a/ccan/order/_info b/ccan/order/_info
index 5a68f674c9d9c4deb24ae331592329d3480cd194..b5df2378a7974d7463c8f3de0c6c419a13bf41bf 100644 (file)
--- a/ccan/order/_info
+++ b/ccan/order/_info
@@ -20,9 +20,12 @@ int main(int argc, char *argv[])
 
        if (strcmp(argv[1], "depends") == 0) {
                printf("ccan/typesafe_cb\n");
+               printf("ccan/ptrint\n");
                return 0;
        }
        if (strcmp(argv[1], "testdepends") == 0) {
+               printf("ccan/array_size\n");
+               printf("ccan/asort\n");
                return 0;
        }
 

diff --git a/ccan/order/order.c b/ccan/order/order.c
new file mode 100644 (file)
index 0000000..863a8e1
--- /dev/null
+++ b/ccan/order/order.c
@@ -0,0 +1,70 @@
+/* CC0 license (public domain) - see LICENSE file for details */
+
+#include <ccan/order/order.h>
+
+#define SCALAR_ORDER(_oname, _type)                                    \
+       int _order_##_oname(const void *a,                              \
+                           const void *b,                              \
+                           void *ctx)                                  \
+       {                                                               \
+               ptrdiff_t offset = ptr2int(ctx);                        \
+               const _type *aa = (const _type *)((char *)a + offset);  \
+               const _type *bb = (const _type *)((char *)b + offset);  \
+                                                                       \
+               if (*aa < *bb) {                                        \
+                       return -1;                                      \
+               } else if (*aa > *bb) {                                 \
+                       return 1;                                       \
+               } else {                                                \
+                       assert(*aa == *bb);                             \
+                       return 0;                                       \
+               }                                                       \
+       }                                                               \
+       int order_##_oname(const _type *a,                              \
+                          const _type *b,                              \
+                          void *ctx)                                   \
+       {                                                               \
+               return _order_##_oname(a, b, int2ptr(0));               \
+       }                                                               \
+       int _order_##_oname##_reverse(const void *a,                    \
+                                     const void *b,                    \
+                                     void *ctx)                        \
+       {                                                               \
+               return -_order_##_oname(a, b, ctx);                     \
+       }                                                               \
+       int order_##_oname##_reverse(const _type *a,                    \
+                                    const _type *b,                    \
+                                    void *ctx)                         \
+       {                                                               \
+               return _order_##_oname##_reverse(a, b, int2ptr(0));     \
+       }                                                               \
+       int order_##_oname##_noctx(const void *a,                       \
+                                  const void *b)                       \
+       {                                                               \
+               return _order_##_oname(a, b, int2ptr(0));               \
+       }                                                               \
+       int order_##_oname##_reverse_noctx(const void *a,               \
+                                          const void *b)               \
+       {                                                               \
+               return _order_##_oname##_reverse(a, b, int2ptr(0));     \
+       }
+
+SCALAR_ORDER(s8, int8_t)
+SCALAR_ORDER(s16, int16_t)
+SCALAR_ORDER(s32, int32_t)
+SCALAR_ORDER(s64, int64_t)
+
+SCALAR_ORDER(u8, uint8_t)
+SCALAR_ORDER(u16, uint16_t)
+SCALAR_ORDER(u32, uint32_t)
+SCALAR_ORDER(u64, uint64_t)
+
+SCALAR_ORDER(int, int)
+SCALAR_ORDER(uint, unsigned int)
+SCALAR_ORDER(long, long)
+SCALAR_ORDER(ulong, unsigned long)
+SCALAR_ORDER(size, size_t)
+SCALAR_ORDER(ptrdiff, ptrdiff_t)
+
+SCALAR_ORDER(float, float)
+SCALAR_ORDER(double, double)

diff --git a/ccan/order/order.h b/ccan/order/order.h
index f5dac818d898cec5762726fe1136d70e58a611b2..edceab5551e2e68dd14bee39bf7ac4a12663841b 100644 (file)
--- a/ccan/order/order.h
+++ b/ccan/order/order.h
@@ -6,6 +6,7 @@
 #include <assert.h>
 
 #include <ccan/typesafe_cb/typesafe_cb.h>
+#include <ccan/ptrint/ptrint.h>
 
 typedef int (*_total_order_cb)(const void *, const void *, void *);
 typedef int (*total_order_noctx_cb)(const void *, const void *);
@@ -30,4 +31,43 @@ struct _total_order {
                _ctx ctx;                               \
        } _name
 
+#define _DECL_ONAME(_oname, _itype)                                    \
+       extern int _order_##_oname(const void *, const void *, void *); \
+       extern int order_##_oname(const _itype *, const _itype *, void *); \
+       extern int order_##_oname##_noctx(const void *, const void *);
+
+#define _DECL_ONAME_BIDIR(_oname, _itype)                              \
+       _DECL_ONAME(_oname, _itype)                                     \
+       _DECL_ONAME(_oname##_reverse, _itype)
+
+_DECL_ONAME_BIDIR(s8, int8_t)
+_DECL_ONAME_BIDIR(s16, int16_t)
+_DECL_ONAME_BIDIR(s32, int32_t)
+_DECL_ONAME_BIDIR(s64, int64_t)
+
+_DECL_ONAME_BIDIR(u8, uint8_t)
+_DECL_ONAME_BIDIR(u16, uint16_t)
+_DECL_ONAME_BIDIR(u32, uint32_t)
+_DECL_ONAME_BIDIR(u64, uint64_t)
+
+_DECL_ONAME_BIDIR(int, int)
+_DECL_ONAME_BIDIR(uint, unsigned int)
+_DECL_ONAME_BIDIR(long, long)
+_DECL_ONAME_BIDIR(ulong, unsigned long)
+_DECL_ONAME_BIDIR(size, size_t)
+_DECL_ONAME_BIDIR(ptrdiff, ptrdiff_t)
+
+_DECL_ONAME_BIDIR(float, float)
+_DECL_ONAME_BIDIR(double, double)
+
+#undef _DECL_ONAME
+#undef _DECL_ONAME_BIDIR
+
+#define total_order_by_field(_name, _oname, _itype, _field)            \
+       total_order(_name, _itype, ptrint_t *) = {                      \
+               (total_order_cb(, _itype,                               \
+                               ptrint_t *))(_order_##_oname),          \
+               int2ptr(offsetof(_itype, _field)),                      \
+       }
+
 #endif /* CCAN_ORDER_H */

diff --git a/ccan/order/test/api.c b/ccan/order/test/api.c
new file mode 100644 (file)
index 0000000..61ec96f
--- /dev/null
+++ b/ccan/order/test/api.c
@@ -0,0 +1,138 @@
+#include "config.h"
+
+#include <string.h>
+#include <stdlib.h>
+#include <limits.h>
+#include <float.h>
+#include <math.h>
+
+#include <ccan/array_size/array_size.h>
+
+#include <ccan/order/order.h>
+#include <ccan/tap/tap.h>
+
+#include <ccan/asort/asort.h>
+
+#define QSORT_SCALAR(t, oname, ...)                                    \
+       {                                                               \
+               t arr0[] = { __VA_ARGS__ };                             \
+               const int num = ARRAY_SIZE(arr0);                       \
+               t arr1[num], arr2[num];                                 \
+               int i;                                                  \
+                                                                       \
+               /* Intialize arr1 in reverse order */                   \
+               for (i = 0; i < num; i++)                               \
+                       arr1[i] = arr0[num-i-1];                        \
+                                                                       \
+               memcpy(arr2, arr1, sizeof(arr1));                       \
+               qsort(arr2, num, sizeof(t), order_##oname##_noctx);     \
+               ok(memcmp(arr2, arr0, sizeof(arr0)) == 0,               \
+                  "qsort order_%s_noctx", #oname);                     \
+                                                                       \
+               qsort(arr2, num, sizeof(t), order_##oname##_reverse_noctx); \
+               ok(memcmp(arr2, arr1, sizeof(arr1)) == 0,               \
+                  "qsort order_%s_reverse_noctx", #oname);             \
+       }
+
+#define ASORT_SCALAR(t, oname, ...)                                    \
+       {                                                               \
+               t arr0[] = { __VA_ARGS__ };                             \
+               const int num = ARRAY_SIZE(arr0);                       \
+               t arr1[num], arr2[num];                                 \
+               int i;                                                  \
+                                                                       \
+               /* Intialize arr1 in reverse order */                   \
+               for (i = 0; i < num; i++)                               \
+                       arr1[i] = arr0[num-i-1];                        \
+                                                                       \
+               memcpy(arr2, arr1, sizeof(arr1));                       \
+               asort(arr2, num, order_##oname, NULL);                  \
+               ok(memcmp(arr2, arr0, sizeof(arr0)) == 0,               \
+                  "asort order_%s", #oname);                           \
+                                                                       \
+               asort(arr2, num, order_##oname##_reverse, NULL);        \
+               ok(memcmp(arr2, arr1, sizeof(arr1)) == 0,               \
+                  "asort order_%s_reverse", #oname);                   \
+       }
+
+#define ASORT_STRUCT_BY_SCALAR(t, oname, ...)                          \
+       {                                                               \
+               t arrbase[] = { __VA_ARGS__ };                          \
+               struct tstruct {                                        \
+                       char dummy0[5];                                 \
+                       t val;                                          \
+                       long dummy1;                                    \
+               };                                                      \
+               const int num = ARRAY_SIZE(arrbase);                    \
+               struct tstruct arr0[num], arr1[num], arr2[num];         \
+               int i;                                                  \
+               total_order_by_field(order, oname, struct tstruct, val); \
+               total_order_by_field(rorder, oname##_reverse,           \
+                                    struct tstruct, val);              \
+                                                                       \
+               /* Set up dummy structures */                           \
+               memset(arr0, 0, sizeof(arr0));                          \
+               for (i = 0; i < num; i++) {                             \
+                       arr0[i].dummy1 = i;                             \
+                       strcpy(arr0[i].dummy0, "abc");                  \
+                       arr0[i].val = arrbase[i];                       \
+               }                                                       \
+                                                                       \
+               /* Intialize arr1 in reverse order */                   \
+               for (i = 0; i < num; i++)                               \
+                       arr1[i] = arr0[num-i-1];                        \
+                                                                       \
+               memcpy(arr2, arr1, sizeof(arr1));                       \
+               asort(arr2, num, order.cb, order.ctx);                  \
+               ok(memcmp(arr2, arr0, sizeof(arr0)) == 0,               \
+                  "asort by field %s", #oname);                        \
+                                                                       \
+               asort(arr2, num, rorder.cb, rorder.ctx);                \
+               ok(memcmp(arr2, arr1, sizeof(arr1)) == 0,               \
+                  "asort by field %s_reverse", #oname);                \
+       }
+
+#define TEST_SCALAR(t, oname, ...)                                     \
+       {                                                               \
+               QSORT_SCALAR(t, oname, __VA_ARGS__);                    \
+               ASORT_SCALAR(t, oname, __VA_ARGS__);                    \
+               ASORT_STRUCT_BY_SCALAR(t, oname, __VA_ARGS__);          \
+       }
+
+int main(void)
+{
+       /* This is how many tests you plan to run */
+       plan_tests(84);
+
+       TEST_SCALAR(int8_t, s8, -128, -4, 0, 1, 2, 88, 126, 127);
+       TEST_SCALAR(int16_t, s16, -32768, -4, 0, 1, 2, 88, 126, 32767);
+       TEST_SCALAR(int32_t, s32, -2000000000, -4, 0, 1, 2, 88, 126,
+                   2000000000);
+       TEST_SCALAR(int64_t, s64, -999999999999999999LL, -2000000000, -4, 0,
+                   1, 2, 88, 126, 2000000000, 999999999999999999LL);
+
+       TEST_SCALAR(uint8_t, u8, 0, 1, 2, 88, 126, 127, -10, -1);
+       TEST_SCALAR(uint16_t, u16, 0, 1, 2, 88, 126, 32767, -10, -1);
+       TEST_SCALAR(uint32_t, u32, 0, 1, 2, 88, 126, 2000000000, -10, -1);
+       TEST_SCALAR(uint64_t, u64, 0, 1, 2, 88, 126, 2000000000,
+                   999999999999999999LL, -10, -1);
+
+       TEST_SCALAR(int, int, INT_MIN, -10, -1, 0, 1, 10, INT_MAX);
+       TEST_SCALAR(unsigned, uint, 0, 1, 10, INT_MAX, (unsigned)INT_MAX+1,
+                   -10, -1);
+
+       TEST_SCALAR(long, long, LONG_MIN, INT_MIN, -10, -1, 0, 1, 10, INT_MAX,
+                   LONG_MAX);
+       TEST_SCALAR(unsigned long, ulong, 0, 1, 10, INT_MAX,
+                   (unsigned long)INT_MAX+1, LONG_MAX,
+                   (unsigned long)LONG_MAX+1, -10, -1);
+
+       TEST_SCALAR(float, float, -INFINITY, -FLT_MAX, -1.0, 0.0, FLT_MIN,
+                 0.1, M_E, M_PI, 5.79, FLT_MAX, INFINITY);
+       TEST_SCALAR(double, double, -INFINITY, -DBL_MAX, -FLT_MAX, -1.0, 0.0,
+                 DBL_MIN, FLT_MIN, 0.1, M_E, M_PI, 5.79, FLT_MAX, DBL_MAX,
+                 INFINITY);
+
+       /* This exits depending on whether all tests passed */
+       return exit_status();
+}

diff --git a/ccan/priority_queue/test/run.c b/ccan/priority_queue/test/run.c
new file mode 100644 (file)
index 0000000..6bc8e74
--- /dev/null
+++ b/ccan/priority_queue/test/run.c
@@ -0,0 +1,24 @@
+#include <ccan/priority_queue/priority_queue.h>
+#include <ccan/tap/tap.h>
+
+int main(void)
+{
+       /* This is how many tests you plan to run */
+       plan_tests(3);
+
+       /* Simple thing we expect to succeed */
+       ok1(some_test())
+       /* Same, with an explicit description of the test. */
+       ok(some_test(), "%s with no args should return 1", "some_test")
+       /* How to print out messages for debugging. */
+       diag("Address of some_test is %p", &some_test)
+       /* Conditional tests must be explicitly skipped. */
+#if HAVE_SOME_FEATURE
+       ok1(test_some_feature())
+#else
+       skip(1, "Don't have SOME_FEATURE")
+#endif
+
+       /* This exits depending on whether all tests passed */
+       return exit_status();
+}