add bsearch

Signed-off-by: Mattias Andrée <maandree@kth.se>

2 files changed, 100 insertions, 0 deletions

diff --git a/include/stdlib.h b/include/stdlib.h
index f68c046..d3e07f8 100644
--- a/include/stdlib.h
+++ b/include/stdlib.h
@@ -343,6 +343,36 @@ char* getenv(const char*)
   __GCC_ONLY(__attribute__((__warn_unused_result__, __nonnull__)));
 
 
+/**
+ * Search for an item in a sorted list of comparable
+ * elements. The list must be sorted in ascending order.
+ * The function usually implements binary search,
+ * as is done in this implementation.
+ * 
+ * @etymology  (B)inary (search).
+ * 
+ * @param   sought  The sought item.
+ * @param   list    The beginning of the list to search.
+ * @param   n       The number of elements in the list.
+ * @param   width   The width, in bytes, of each element in the list.
+ * @param   compar  A function that shall compare two items, and return
+ *                  a value less than, equal to, or greater than zero
+ *                  if the first argument is less than, equal to, or
+ *                  greater than the second argument, respectively.
+ * @return          The address of an arbritrart element in `list` that
+ *                  is equal to `sought`, or `NULL` if no such element
+ *                  can be found (does not exist, or because `list`
+ *                  is not properly sorted.)
+ * 
+ * @since  Always.
+ */
+void* bsearch(const void*, const void*, size_t, size_t, int (*)(const void*, const void*))
+  __GCC_ONLY(__attribute__((__warn_unused_result__, __nonnull__(1, 5), __pure__)));
+#ifdef __CONST_CORRECT
+# define bsearch(...)  (__const_correct2(bsearch, __VA_ARGS__))
+#endif
+
+
 
 /* TODO implement rand-functions */
 #define RAND_MAX  1
diff --git a/src/stdlib/bsearch.c b/src/stdlib/bsearch.c
new file mode 100644
index 0000000..c459ea4
--- /dev/null
+++ b/src/stdlib/bsearch.c
@@ -0,0 +1,70 @@
+/**
+ * slibc — Yet another C library
+ * Copyright © 2015, 2016  Mattias Andrée (maandree@member.fsf.org)
+ * 
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ * 
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ * 
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+#include <stdlib.h>
+
+
+# pragma GCC diagnostic ignored "-Wdiscarded-qualifiers"
+
+
+
+/**
+ * Search for an item in a sorted list of comparable
+ * elements. The list must be sorted in ascending order.
+ * The function usually implements binary search,
+ * as is done in this implementation.
+ * 
+ * @etymology  (B)inary (search).
+ * 
+ * @param   sought  The sought item.
+ * @param   list    The beginning of the list to search.
+ * @param   n       The number of elements in the list.
+ * @param   width   The width, in bytes, of each element in the list.
+ * @param   compar  A function that shall compare two items, and return
+ *                  a value less than, equal to, or greater than zero
+ *                  if the first argument is less than, equal to, or
+ *                  greater than the second argument, respectively.
+ * @return          The address of an arbritrart element in `list` that
+ *                  is equal to `sought`, or `NULL` if no such element
+ *                  can be found (does not exist, or because `list`
+ *                  is not properly sorted.)
+ * 
+ * @since  Always.
+ */
+void* (bsearch)(const void* sought, const void* list, size_t n, size_t width,
+		int (*compar)(const void*, const void*))
+{
+  int cmp, i;
+  char* test;
+  if (n == 0)
+    return NULL;
+  for (;;)
+    {
+      i = n >> 1;
+      test = (char*)list + i * width;
+      cmp = compar(sought, test);
+      if (!i)
+	return cmp ? NULL : test;
+      else if (cmp < 0)
+	n = i;
+      else if (cmp > 0)
+	n -= i, list = test;
+      else
+	return test;
+    }
+}
+