From e9ff4fdd49f4be77ebfa45e8a4f300cc2e8f5f23 Mon Sep 17 00:00:00 2001
From: Ozkan Sezer <[EMAIL REDACTED]>
Date: Mon, 25 Apr 2022 23:55:50 +0300
Subject: [PATCH] add SDL_bsearch
---
CMakeLists.txt | 4 ++--
configure | 2 +-
configure.ac | 2 +-
include/SDL_config.h.cmake | 1 +
include/SDL_config.h.in | 1 +
include/SDL_config_android.h | 1 +
include/SDL_config_emscripten.h | 1 +
include/SDL_config_iphoneos.h | 3 ++-
include/SDL_config_macosx.h | 3 ++-
include/SDL_config_os2.h | 1 +
include/SDL_config_pandora.h | 1 +
include/SDL_config_windows.h | 1 +
include/SDL_config_winrt.h | 1 +
include/SDL_stdinc.h | 1 +
src/dynapi/SDL_dynapi_overrides.h | 1 +
src/dynapi/SDL_dynapi_procs.h | 1 +
src/stdlib/SDL_qsort.c | 33 +++++++++++++++++++++++++++++++
17 files changed, 52 insertions(+), 6 deletions(-)
diff --git a/CMakeLists.txt b/CMakeLists.txt
index a2f11e2668b..ede1a4c1c58 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -848,7 +848,7 @@ if(SDL_LIBC)
endforeach()
set(HAVE_SIGNAL_H 1)
foreach(_FN
- malloc calloc realloc free qsort abs memset memcpy memmove memcmp
+ malloc calloc realloc free bsearch qsort abs memset memcpy memmove memcmp
wcslen _wcsdup wcsdup wcsstr wcscmp wcsncmp _wcsicmp _wcsnicmp
strlen _strrev _strupr _strlwr strchr strrchr strstr itoa _ltoa
_ultoa strtol strtoul strtoll strtod atoi atof strcmp strncmp
@@ -885,7 +885,7 @@ if(SDL_LIBC)
int main(void) { return 0; }" HAVE_MPROTECT)
foreach(_FN
strtod malloc calloc realloc free getenv setenv putenv unsetenv
- qsort abs bcopy memset memcpy memmove memcmp strlen strlcpy strlcat
+ bsearch qsort abs bcopy memset memcpy memmove memcmp strlen strlcpy strlcat
_strrev _strupr _strlwr index rindex strchr strrchr strstr strtok_r
itoa _ltoa _uitoa _ultoa strtol strtoul _i64toa _ui64toa strtoll strtoull
atoi atof strcmp strncmp _stricmp strcasecmp _strnicmp strncasecmp
diff --git a/configure b/configure
index e487a8a035a..947d643a94e 100755
--- a/configure
+++ b/configure
@@ -17717,7 +17717,7 @@ fi
rm -f core conftest.err conftest.$ac_objext conftest.$ac_ext
fi
- for ac_func in malloc calloc realloc free getenv setenv putenv unsetenv qsort abs bcopy memset memcpy memmove wcslen wcslcpy wcslcat _wcsdup wcsdup wcsstr wcscmp wcsncmp wcscasecmp _wcsicmp wcsncasecmp _wcsnicmp strlen strlcpy strlcat _strrev _strupr _strlwr index rindex strchr strrchr strstr strtok_r itoa _ltoa _uitoa _ultoa strtol strtoul _i64toa _ui64toa strtoll strtoull atoi atof strcmp strncmp _stricmp strcasecmp _strnicmp strncasecmp vsscanf vsnprintf fopen64 fseeko fseeko64 sigaction setjmp nanosleep sysconf sysctlbyname getauxval elf_aux_info poll _Exit
+ for ac_func in malloc calloc realloc free getenv setenv putenv unsetenv bsearch qsort abs bcopy memset memcpy memmove wcslen wcslcpy wcslcat _wcsdup wcsdup wcsstr wcscmp wcsncmp wcscasecmp _wcsicmp wcsncasecmp _wcsnicmp strlen strlcpy strlcat _strrev _strupr _strlwr index rindex strchr strrchr strstr strtok_r itoa _ltoa _uitoa _ultoa strtol strtoul _i64toa _ui64toa strtoll strtoull atoi atof strcmp strncmp _stricmp strcasecmp _strnicmp strncasecmp vsscanf vsnprintf fopen64 fseeko fseeko64 sigaction setjmp nanosleep sysconf sysctlbyname getauxval elf_aux_info poll _Exit
do :
as_ac_var=`$as_echo "ac_cv_func_$ac_func" | $as_tr_sh`
ac_fn_c_check_func "$LINENO" "$ac_func" "$as_ac_var"
diff --git a/configure.ac b/configure.ac
index f2f4ae323e3..8bc41946a34 100644
--- a/configure.ac
+++ b/configure.ac
@@ -337,7 +337,7 @@ dnl Checks for library functions.
AC_DEFINE(HAVE_MPROTECT, 1, [ ])
],[]),
)
- AC_CHECK_FUNCS(malloc calloc realloc free getenv setenv putenv unsetenv qsort abs bcopy memset memcpy memmove wcslen wcslcpy wcslcat _wcsdup wcsdup wcsstr wcscmp wcsncmp wcscasecmp _wcsicmp wcsncasecmp _wcsnicmp strlen strlcpy strlcat _strrev _strupr _strlwr index rindex strchr strrchr strstr strtok_r itoa _ltoa _uitoa _ultoa strtol strtoul _i64toa _ui64toa strtoll strtoull atoi atof strcmp strncmp _stricmp strcasecmp _strnicmp strncasecmp vsscanf vsnprintf fopen64 fseeko fseeko64 sigaction setjmp nanosleep sysconf sysctlbyname getauxval elf_aux_info poll _Exit)
+ AC_CHECK_FUNCS(malloc calloc realloc free getenv setenv putenv unsetenv bsearch qsort abs bcopy memset memcpy memmove wcslen wcslcpy wcslcat _wcsdup wcsdup wcsstr wcscmp wcsncmp wcscasecmp _wcsicmp wcsncasecmp _wcsnicmp strlen strlcpy strlcat _strrev _strupr _strlwr index rindex strchr strrchr strstr strtok_r itoa _ltoa _uitoa _ultoa strtol strtoul _i64toa _ui64toa strtoll strtoull atoi atof strcmp strncmp _stricmp strcasecmp _strnicmp strncasecmp vsscanf vsnprintf fopen64 fseeko fseeko64 sigaction setjmp nanosleep sysconf sysctlbyname getauxval elf_aux_info poll _Exit)
AC_CHECK_LIB(m, pow, [LIBS="$LIBS -lm"; EXTRA_LDFLAGS="$EXTRA_LDFLAGS -lm"])
AC_CHECK_FUNCS(acos acosf asin asinf atan atanf atan2 atan2f ceil ceilf copysign copysignf cos cosf exp expf fabs fabsf floor floorf trunc truncf fmod fmodf log logf log10 log10f lround lroundf pow powf round roundf scalbn scalbnf sin sinf sqrt sqrtf tan tanf)
diff --git a/include/SDL_config.h.cmake b/include/SDL_config.h.cmake
index fcd18e57dfa..77433354237 100644
--- a/include/SDL_config.h.cmake
+++ b/include/SDL_config.h.cmake
@@ -88,6 +88,7 @@
#cmakedefine HAVE_UNSETENV 1
#endif
#cmakedefine HAVE_QSORT 1
+#cmakedefine HAVE_BSEARCH 1
#cmakedefine HAVE_ABS 1
#cmakedefine HAVE_BCOPY 1
#cmakedefine HAVE_MEMSET 1
diff --git a/include/SDL_config.h.in b/include/SDL_config.h.in
index f912e4112c2..51cadaea843 100644
--- a/include/SDL_config.h.in
+++ b/include/SDL_config.h.in
@@ -92,6 +92,7 @@
#undef HAVE_UNSETENV
#endif
#undef HAVE_QSORT
+#undef HAVE_BSEARCH
#undef HAVE_ABS
#undef HAVE_BCOPY
#undef HAVE_MEMSET
diff --git a/include/SDL_config_android.h b/include/SDL_config_android.h
index 4a13a3a5367..5a9cfc04590 100644
--- a/include/SDL_config_android.h
+++ b/include/SDL_config_android.h
@@ -60,6 +60,7 @@
#define HAVE_SETENV 1
#define HAVE_UNSETENV 1
#define HAVE_QSORT 1
+#define HAVE_BSEARCH 1
#define HAVE_ABS 1
#define HAVE_BCOPY 1
#define HAVE_MEMSET 1
diff --git a/include/SDL_config_emscripten.h b/include/SDL_config_emscripten.h
index 028777df1d3..989e1243a7b 100644
--- a/include/SDL_config_emscripten.h
+++ b/include/SDL_config_emscripten.h
@@ -69,6 +69,7 @@
#define HAVE_PUTENV 1
#define HAVE_UNSETENV 1
#define HAVE_QSORT 1
+#define HAVE_BSEARCH 1
#define HAVE_ABS 1
#define HAVE_BCOPY 1
#define HAVE_MEMSET 1
diff --git a/include/SDL_config_iphoneos.h b/include/SDL_config_iphoneos.h
index 0aa242563f8..48f9f9f9bef 100644
--- a/include/SDL_config_iphoneos.h
+++ b/include/SDL_config_iphoneos.h
@@ -60,6 +60,7 @@
#define HAVE_SETENV 1
#define HAVE_UNSETENV 1
#define HAVE_QSORT 1
+#define HAVE_BSEARCH 1
#define HAVE_ABS 1
#define HAVE_BCOPY 1
#define HAVE_MEMSET 1
@@ -117,7 +118,7 @@
#define HAVE_LROUNDF 1
#define HAVE_POW 1
#define HAVE_POWF 1
-#define HAVE_ROUND 1
+#define HAVE_ROUND 1
#define HAVE_ROUNDF 1
#define HAVE_SCALBN 1
#define HAVE_SCALBNF 1
diff --git a/include/SDL_config_macosx.h b/include/SDL_config_macosx.h
index ff42e3d5f70..1c9698a2896 100644
--- a/include/SDL_config_macosx.h
+++ b/include/SDL_config_macosx.h
@@ -63,6 +63,7 @@
#define HAVE_PUTENV 1
#define HAVE_UNSETENV 1
#define HAVE_QSORT 1
+#define HAVE_BSEARCH 1
#define HAVE_ABS 1
#define HAVE_BCOPY 1
#define HAVE_MEMSET 1
@@ -120,7 +121,7 @@
#define HAVE_LROUNDF 1
#define HAVE_POW 1
#define HAVE_POWF 1
-#define HAVE_ROUND 1
+#define HAVE_ROUND 1
#define HAVE_ROUNDF 1
#define HAVE_SCALBN 1
#define HAVE_SCALBNF 1
diff --git a/include/SDL_config_os2.h b/include/SDL_config_os2.h
index 1728bd772bc..ae11ccdebd5 100644
--- a/include/SDL_config_os2.h
+++ b/include/SDL_config_os2.h
@@ -106,6 +106,7 @@
#define HAVE_SETENV 1
#define HAVE_PUTENV 1
#define HAVE_QSORT 1
+#define HAVE_BSEARCH 1
#define HAVE_ABS 1
#define HAVE_BCOPY 1
#define HAVE_MEMSET 1
diff --git a/include/SDL_config_pandora.h b/include/SDL_config_pandora.h
index e0be390bcca..01bbf49b06f 100644
--- a/include/SDL_config_pandora.h
+++ b/include/SDL_config_pandora.h
@@ -65,6 +65,7 @@
#define HAVE_PUTENV 1
#define HAVE_UNSETENV 1
#define HAVE_QSORT 1
+#define HAVE_BSEARCH 1
#define HAVE_ABS 1
#define HAVE_BCOPY 1
#define HAVE_MEMSET 1
diff --git a/include/SDL_config_windows.h b/include/SDL_config_windows.h
index 770b19039d8..7c2d746437e 100644
--- a/include/SDL_config_windows.h
+++ b/include/SDL_config_windows.h
@@ -137,6 +137,7 @@ typedef unsigned int uintptr_t;
#define HAVE_FREE 1
#define HAVE_ALLOCA 1
#define HAVE_QSORT 1
+#define HAVE_BSEARCH 1
#define HAVE_ABS 1
#define HAVE_MEMSET 1
#define HAVE_MEMCPY 1
diff --git a/include/SDL_config_winrt.h b/include/SDL_config_winrt.h
index f3901a59743..9d8d2ebd683 100644
--- a/include/SDL_config_winrt.h
+++ b/include/SDL_config_winrt.h
@@ -123,6 +123,7 @@ typedef unsigned int uintptr_t;
#define HAVE_FREE 1
#define HAVE_ALLOCA 1
#define HAVE_QSORT 1
+#define HAVE_BSEARCH 1
#define HAVE_ABS 1
#define HAVE_MEMSET 1
#define HAVE_MEMCPY 1
diff --git a/include/SDL_stdinc.h b/include/SDL_stdinc.h
index 449e6445c46..ab1eac66ede 100644
--- a/include/SDL_stdinc.h
+++ b/include/SDL_stdinc.h
@@ -463,6 +463,7 @@ extern DECLSPEC char *SDLCALL SDL_getenv(const char *name);
extern DECLSPEC int SDLCALL SDL_setenv(const char *name, const char *value, int overwrite);
extern DECLSPEC void SDLCALL SDL_qsort(void *base, size_t nmemb, size_t size, int (*compare) (const void *, const void *));
+extern DECLSPEC void * SDLCALL SDL_bsearch(const void *key, const void *base, size_t nmemb, size_t size, int (*compare) (const void *, const void *));
extern DECLSPEC int SDLCALL SDL_abs(int x);
diff --git a/src/dynapi/SDL_dynapi_overrides.h b/src/dynapi/SDL_dynapi_overrides.h
index 526513ad577..ea01ac97471 100644
--- a/src/dynapi/SDL_dynapi_overrides.h
+++ b/src/dynapi/SDL_dynapi_overrides.h
@@ -865,3 +865,4 @@
#define SDL_EncloseFPoints SDL_EncloseFPoints_REAL
#define SDL_IntersectFRectAndLine SDL_IntersectFRectAndLine_REAL
#define SDL_RenderGetWindow SDL_RenderGetWindow_REAL
+#define SDL_bsearch SDL_bsearch_REAL
diff --git a/src/dynapi/SDL_dynapi_procs.h b/src/dynapi/SDL_dynapi_procs.h
index 22bf870d927..9f07b6bc7f2 100644
--- a/src/dynapi/SDL_dynapi_procs.h
+++ b/src/dynapi/SDL_dynapi_procs.h
@@ -936,3 +936,4 @@ SDL_DYNAPI_PROC(void,SDL_UnionFRect,(const SDL_FRect *a, const SDL_FRect *b, SDL
SDL_DYNAPI_PROC(SDL_bool,SDL_EncloseFPoints,(const SDL_FPoint *a, int b, const SDL_FRect *c, SDL_FRect *d),(a,b,c,d),return)
SDL_DYNAPI_PROC(SDL_bool,SDL_IntersectFRectAndLine,(const SDL_FRect *a, float *b, float *c, float *d, float *e),(a,b,c,d,e),return)
SDL_DYNAPI_PROC(SDL_Window*,SDL_RenderGetWindow,(SDL_Renderer *a),(a),return)
+SDL_DYNAPI_PROC(void*,SDL_bsearch,(const void *a, const void *b, size_t c, size_t d, int (*e)(const void *, const void *)),(a,b,c,d,e),return)
diff --git a/src/stdlib/SDL_qsort.c b/src/stdlib/SDL_qsort.c
index b175f444e0b..26e97c908bf 100644
--- a/src/stdlib/SDL_qsort.c
+++ b/src/stdlib/SDL_qsort.c
@@ -534,5 +534,38 @@ extern void qsortG(void *base, size_t nmemb, size_t size,
#endif /* HAVE_QSORT */
+void *
+SDL_bsearch(const void *key, const void *base, size_t nmemb, size_t size, int (*compare)(const void *, const void *))
+{
+#if defined(HAVE_BSEARCH)
+ return bsearch(key, base, nmemb, size, compare);
+#else
+/* SDL's replacement: Taken from the Public Domain C Library (PDCLib):
+ Permission is granted to use, modify, and / or redistribute at will.
+*/
+ const void *pivot;
+ size_t corr;
+ int rc;
+
+ while (nmemb) {
+ /* algorithm needs -1 correction if remaining elements are an even number. */
+ corr = nmemb % 2;
+ nmemb /= 2;
+ pivot = (const char *)base + (nmemb * size);
+ rc = compare(key, pivot);
+
+ if (rc > 0) {
+ base = (const char *)pivot + size;
+ /* applying correction */
+ nmemb -= (1 - corr);
+ } else if (rc == 0) {
+ return (void *)pivot;
+ }
+ }
+
+ return NULL;
+#endif /* HAVE_BSEARCH */
+}
+
/* vi: set ts=4 sw=4 expandtab: */