From 37825438b65879dad1a343b45bb5ce9fc37ba8e7 Mon Sep 17 00:00:00 2001 From: David Gibson Date: Tue, 2 Jun 2015 17:30:58 +1000 Subject: [PATCH] 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 --- ccan/order/_info | 3 + ccan/order/order.c | 70 +++++++++++++++++ ccan/order/order.h | 40 ++++++++++ ccan/order/test/api.c | 138 +++++++++++++++++++++++++++++++++ ccan/priority_queue/test/run.c | 24 ++++++ 5 files changed, 275 insertions(+) create mode 100644 ccan/order/order.c create mode 100644 ccan/order/test/api.c create mode 100644 ccan/priority_queue/test/run.c diff --git a/ccan/order/_info b/ccan/order/_info index 5a68f674..b5df2378 100644 --- 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 index 00000000..863a8e16 --- /dev/null +++ b/ccan/order/order.c @@ -0,0 +1,70 @@ +/* CC0 license (public domain) - see LICENSE file for details */ + +#include + +#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 f5dac818..edceab55 100644 --- a/ccan/order/order.h +++ b/ccan/order/order.h @@ -6,6 +6,7 @@ #include #include +#include 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 index 00000000..61ec96f6 --- /dev/null +++ b/ccan/order/test/api.c @@ -0,0 +1,138 @@ +#include "config.h" + +#include +#include +#include +#include +#include + +#include + +#include +#include + +#include + +#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 index 00000000..6bc8e748 --- /dev/null +++ b/ccan/priority_queue/test/run.c @@ -0,0 +1,24 @@ +#include +#include + +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(); +} -- 2.39.2