From 2e7b4df9f7dfd6a4a6796cd2fcee010ea78427ea Mon Sep 17 00:00:00 2001
From: Mattias Andrée <maandree@kth.se>
Date: Sun, 17 Dec 2023 13:23:51 +0100
Subject: Miscellaneous improvements
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

Signed-off-by: Mattias Andrée <maandree@kth.se>
---
 libsyscalls_find_named_number.c | 141 ++++++++++++++++++++++++++++++++++++++++
 1 file changed, 141 insertions(+)
 create mode 100644 libsyscalls_find_named_number.c

(limited to 'libsyscalls_find_named_number.c')

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);
-- 
cgit v1.2.3-70-g09d2