diff options
Diffstat (limited to '')
| -rw-r--r-- | libsyscalls_find_named_number.c | 141 |
1 files changed, 141 insertions, 0 deletions
diff --git a/libsyscalls_find_named_number.c b/libsyscalls_find_named_number.c new file mode 100644 index 0000000..fe8bb47 --- /dev/null +++ b/libsyscalls_find_named_number.c @@ -0,0 +1,141 @@ +/* See LICENSE file for copyright and license details. */ +#include "common.h" + + +#ifdef USE_INTERPOLATION_SEARCH + +# ifndef INTERPOLATION_SEARCH_FLOAT +# define INTERPOLATION_SEARCH_FLOAT long double +# endif + + +/* convertion to unsigned is a modulo (unsigned maximum + 1) operation */ +# define DIFF(TYPE, A, B) ((unsigned TYPE)(A) - (unsigned TYPE)(B)) + +# define INTERPOL_SEARCH(KEY, BASE, N, READ)\ + do {\ + INTERPOLATION_SEARCH_FLOAT guess_d;\ + unsigned long long int guess;\ + size_t h = (N);\ + \ + if (!h--)\ + return NULL;\ + \ + if ((KEY) <= READ((BASE), 0))\ + return (KEY) == READ((BASE), 0) ? &(BASE)[0] : NULL;\ + if ((KEY) >= READ((BASE), h))\ + return (KEY) == READ((BASE), h) ? &(BASE)[h] : NULL;\ + if (READ((BASE), 0) == READ((BASE), h))\ + return NULL;\ + \ + goto use_double;\ + guess = DIFF(long long int, (KEY), READ((BASE), 0));\ + if (h > ULLONG_MAX / guess)\ + goto use_double;\ + \ + for (;;) {\ + guess = DIFF(long long int, (KEY), READ((BASE), 0));\ + guess *= (unsigned long long int)h;\ + guess /= DIFF(long long int, READ((BASE), h), READ((BASE), 0));\ + \ + if (READ((BASE), guess) < (KEY)) {\ + h -= guess += 1;\ + (BASE) = &(BASE)[guess];\ + } else if (READ((BASE), guess) > (KEY)) {\ + h = guess -= 1;\ + } else {\ + return &(BASE)[guess];\ + }\ + \ + if ((KEY) <= READ((BASE), 0))\ + return (KEY) == READ((BASE), 0) ? &(BASE)[0] : NULL;\ + if ((KEY) >= READ((BASE), h))\ + return (KEY) == READ((BASE), h) ? &(BASE)[h] : NULL;\ + if (READ((BASE), 0) == READ((BASE), h))\ + return NULL;\ + }\ + \ + use_double:\ + for (;;) {\ + guess = DIFF(long long int, (KEY), READ((BASE), 0));\ + guess_d = (INTERPOLATION_SEARCH_FLOAT)guess * (INTERPOLATION_SEARCH_FLOAT)h;\ + guess = DIFF(long long int, READ((BASE), h), READ((BASE), 0));\ + guess_d /= (INTERPOLATION_SEARCH_FLOAT)guess;\ + guess = (unsigned long long int)guess_d;\ + \ + if (READ((BASE), guess) < (KEY)) {\ + h -= guess += 1;\ + (BASE) = &(BASE)[guess];\ + } else if (READ((BASE), guess) > (KEY)) {\ + h = guess -= 1;\ + } else {\ + return &(BASE)[guess];\ + }\ + \ + if ((KEY) <= READ((BASE), 0))\ + return (KEY) == READ((BASE), 0) ? &(BASE)[0] : NULL;\ + if ((KEY) >= READ((BASE), h))\ + return (KEY) == READ((BASE), h) ? &(BASE)[h] : NULL;\ + if (READ((BASE), 0) == READ((BASE), h))\ + return NULL;\ + }\ + } while (0) + + +#else + + +PURE_FUNCTION +static int +signed_named_number_cmp(const void *a_, const void *b_) +{ + const struct libsyscalls_named_number *a = a_, *b = b_; + return a->number.s < b->number.s ? -1 : a->number.s > b->number.s; +} + + +PURE_FUNCTION +static int +unsigned_named_number_cmp(const void *a_, const void *b_) +{ + const struct libsyscalls_named_number *a = a_, *b = b_; + return a->number.u < b->number.u ? -1 : a->number.u > b->number.u; +} + + +#endif + + +const struct libsyscalls_named_number * +libsyscalls_find_signed_named_number(signed long long int key, + const struct libsyscalls_named_number *base, size_t n) +{ +#ifdef USE_INTERPOLATION_SEARCH +# define X(ARR, I) ((ARR)[I].number.s) + INTERPOL_SEARCH(key, base, n, X); +# undef X +#else + struct libsyscalls_named_number struct_key = {.number.s = key}; + return bsearch(&struct_key, base, n, sizeof(*base), &signed_named_number_cmp); +#endif +} + + +const struct libsyscalls_named_number * +libsyscalls_find_unsigned_named_number(unsigned long long int key, + const struct libsyscalls_named_number *base, size_t n) +{ +#ifdef USE_INTERPOLATION_SEARCH +# define X(ARR, I) ((ARR)[I].number.u) + INTERPOL_SEARCH(key, base, n, X); +# undef X +#else + struct libsyscalls_named_number struct_key = {.number.u = key}; + return bsearch(&struct_key, base, n, sizeof(*base), &unsigned_named_number_cmp); +#endif +} + + +extern inline const struct libsyscalls_named_number * +libsyscalls_find_named_number(unsigned long long int key, int is_signed, + const struct libsyscalls_named_number *base, size_t n); |