diff options
| -rw-r--r-- | meson_options.txt | 2 | ||||
| -rw-r--r-- | src/defs.h | 30 | ||||
| -rw-r--r-- | src/mergesort.c | 3 | ||||
| -rw-r--r-- | src/meson.build | 2 | ||||
| -rw-r--r-- | src/util.h | 46 |
5 files changed, 80 insertions, 3 deletions
diff --git a/meson_options.txt b/meson_options.txt index 52d535b..3833423 100644 --- a/meson_options.txt +++ b/meson_options.txt @@ -4,6 +4,6 @@ option('data-signed', description : 'Switch whether to use signed data type') option('data-bitness', type : 'combo', - choices : ['64', '32', '16', '8'], + choices : ['256', '128', '64', '32', '16', '8'], value : '64', description : 'Size of a data entry to use, in bits') @@ -41,12 +41,40 @@ # else typedef uint32_t field; # endif -#else +#elif entry_field_size == 64 # ifdef entry_field_signed typedef int64_t field; # else typedef uint64_t field; # endif +#elif entry_field_size == 128 +# ifdef entry_field_signed + typedef struct field { + uint64_t low; + int64_t high; + } field; +# else + typedef struct field { + uint64_t low; + uint64_t high; + } field; +# endif +#elif entry_field_size == 256 +# ifdef entry_field_signed + typedef struct field { + uint64_t low; + uint64_t midlow; + uint64_t midhigh; + int64_t high; + } field; +# else + typedef struct field { + uint64_t low; + uint64_t midlow; + uint64_t midhigh; + uint64_t high; + } field; +# endif #endif union nextoff { diff --git a/src/mergesort.c b/src/mergesort.c index 1b21db7..053e702 100644 --- a/src/mergesort.c +++ b/src/mergesort.c @@ -7,6 +7,7 @@ #include "defs.h" #include "stream.h" #include "mergesort.h" +#include "util.h" static int merge(struct stream * const dest, struct stream * const A, struct stream * const B); @@ -53,7 +54,7 @@ static int merge(struct stream * const dest, struct stream * const A, struct str b = B->get(B); while (a || b) { - if (a && (!b || a->val <= b->val)) { + if (a && (!b || is_less_equal(a->val, b->val))) { dest->put(dest, a); a = A->get(A); } else { diff --git a/src/meson.build b/src/meson.build index aed222e..7f391ab 100644 --- a/src/meson.build +++ b/src/meson.build @@ -4,6 +4,7 @@ source_files = [ 'stream.c', 'main.c', 'mergesort.c', + 'util.h', ] header_files = [ @@ -12,6 +13,7 @@ header_files = [ 'datagen.h', 'stream.h', 'mergesort.h', + 'util.h', ] sources = files(source_files) diff --git a/src/util.h b/src/util.h new file mode 100644 index 0000000..af819f4 --- /dev/null +++ b/src/util.h @@ -0,0 +1,46 @@ +/* SPDX-License-Identifier: LGPL-2.1-only */ + +/* Copyright (C) 2021 Gediminas Jakutis */ + +#ifndef ALGOS_UTIL_H_INCLUDED +#define ALGOS_UTIL_H_INCLUDED + +#include "defs.h" + +static inline int is_less_equal(const field a, const field b) __attribute__((always_inline)); + +static inline int is_less_equal(const field a, const field b) +{ + int ret; + +/* all sizes fitting in a primitive type */ +#if entry_field_size <= 64 + + ret = a <= b; + +/* composite of two 64bit */ +#elif entry_field_size == 128 + + if (unlikely(a.high == b.high)) { + ret = a.low <= b.low; + } else { + ret = a.high < b.high; + } + +/* composite of four 64bit */ +#elif entry_field_size == 256 + if (likely(a.high != b.high)) { + ret = a.high < b.high; + } else if (likely(a.midhigh != b.midhigh)){ + ret = a.midhigh < b.midhigh; + } else if (likely(a.midlow != b.midlow)){ + ret = a.midlow < b.midlow; + } else { + ret = a.low <= b.low; + } +#endif + + return ret; +} + +#endif /* ALGOS_UTIL_H_INCLUDED */ |