/* 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);