summaryrefslogtreecommitdiff
path: root/src/stdlib/bsearch.c
diff options
context:
space:
mode:
authorJakob Kaivo <jkk@ung.org>2019-02-08 18:42:39 -0500
committerJakob Kaivo <jkk@ung.org>2019-02-08 18:42:39 -0500
commit7ef8a7379f7f7d09e71ccae2a0b688c3cd80423f (patch)
tree092ab0aed1769117fd7b28b8592f6f96b0e0d5af /src/stdlib/bsearch.c
parent6acf19370e8adff79cd83b257d3f04aeaf2a59dd (diff)
merge sources into single tree
Diffstat (limited to 'src/stdlib/bsearch.c')
-rw-r--r--src/stdlib/bsearch.c44
1 files changed, 44 insertions, 0 deletions
diff --git a/src/stdlib/bsearch.c b/src/stdlib/bsearch.c
new file mode 100644
index 00000000..d625599f
--- /dev/null
+++ b/src/stdlib/bsearch.c
@@ -0,0 +1,44 @@
+#include <stdlib.h>
+
+/** binary search **/
+
+void * bsearch(const void * key, const void * base, size_t nmemb, size_t size, int (*compar)(const void *, const void*))
+{
+ /* TODO: testing */
+ void *ret = NULL;
+ size_t i = nmemb / 2;
+ unsigned int trip = 1;
+ (void)size;
+
+ while (ret == NULL) {
+ int comp = compar(key, base + i);
+ if (comp == 0) {
+ return (void*)(base + i);
+ } else if (comp > 0) {
+ i -= (nmemb >> trip);
+ } else {
+ i += (nmemb >> trip);
+ }
+ }
+ return NULL;
+}
+
+/***
+performs a binary search for ARGUMENT(key) in the array
+ARGUMENT(base), which contains ARGUMENT(nmemb) members of ARGUMENT(size) bytes
+each.
+
+The search is performed by calling ARGUMENT(compar) with the first argument of
+ARGUMENT(key), and the second being an element from the array at
+ARGUMENT(base). The function must return less than 0 if ARGUMENT(key) is less
+than the other element, 0 if they are equal, and greater than 0 if
+ARGUMENT(key) is greater than the other element.
+***/
+
+/*
+UNSPECIFIED(Which element is matched if two elements are equal)
+UNDEFINED(The array at ARGUMENT(base) is not sorted)
+RETURN_FAILURE(CONSTANT(NULL))
+RETURN_SUCCESS(a pointer to the matching element)
+STDC(1)
+*/