Add bindex and bindex_r

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

6 files changed, 152 insertions, 1 deletions

diff --git a/LICENSE b/LICENSE
index f4e0c18..68df9b2 100644
--- a/LICENSE
+++ b/LICENSE
@@ -1,6 +1,6 @@
 ISC License
 
-© 2017, 2018, 2021, 2022 Mattias Andrée <maandree@kth.se>
+© 2017, 2018, 2021, 2022, 2023 Mattias Andrée <maandree@kth.se>
 
 Permission to use, copy, modify, and/or distribute this software for any
 purpose with or without fee is hereby granted, provided that the above
diff --git a/Makefile b/Makefile
index 5d45bc4..7ea4e6e 100644
--- a/Makefile
+++ b/Makefile
@@ -45,6 +45,7 @@ SUBHDR =\
 	libsimple/pvalloc.h\
 	libsimple/pvallocz.h\
 	libsimple/realloc.h\
+	libsimple/search.h\
 	libsimple/str.h\
 	libsimple/strdup.h\
 	libsimple/strn.h\
@@ -80,6 +81,8 @@ OBJ =\
 	aligned_wmemdup.o\
 	allocn.o\
 	asprintf.o\
+	bindex.o\
+	bindex_r.o\
 	callocn.o\
 	close.o\
 	cmptimespec.o\
diff --git a/bindex.c b/bindex.c
new file mode 100644
index 0000000..e93803f
--- /dev/null
+++ b/bindex.c
@@ -0,0 +1,39 @@
+/* See LICENSE file for copyright and license details. */
+#include "common.h"
+#ifndef TEST
+
+
+ssize_t
+libsimple_bindex(const void *key, const void *base, size_t nel, size_t width,
+                 int (*compar)(const void *, const void *))
+{
+	size_t index = 0, offset = 0;
+	int cmp;
+
+	while (nel) {
+		index = offset + nel / 2;
+		cmp = (*compar)(key, (const char *)base + width * index);
+		if (cmp < 0) {
+			nel /= 2;
+		} else if (cmp > 0) {
+			offset = index += 1;
+			nel -= nel / 2 + 1;
+		} else {
+			return (ssize_t)index;
+		}
+	}
+
+	return ~(ssize_t)index;
+}
+
+
+#else
+#include "test.h"
+
+int
+main(void) /* TODO add test */
+{
+	return 0;
+}
+
+#endif
diff --git a/bindex_r.c b/bindex_r.c
new file mode 100644
index 0000000..805e74a
--- /dev/null
+++ b/bindex_r.c
@@ -0,0 +1,39 @@
+/* See LICENSE file for copyright and license details. */
+#include "common.h"
+#ifndef TEST
+
+
+ssize_t
+libsimple_bindex_r(const void *key, const void *base, size_t nel, size_t width,
+                   int (*compar)(const void *, const void *, void *), void *arg)
+{
+	size_t index = 0, offset = 0;
+	int cmp;
+
+	while (nel) {
+		index = offset + nel / 2;
+		cmp = (*compar)(key, (const char *)base + width * index, arg);
+		if (cmp < 0) {
+			nel /= 2;
+		} else if (cmp > 0) {
+			offset = index += 1;
+			nel -= nel / 2 + 1;
+		} else {
+			return (ssize_t)index;
+		}
+	}
+
+	return ~(ssize_t)index;
+}
+
+
+#else
+#include "test.h"
+
+int
+main(void) /* TODO add test */
+{
+	return 0;
+}
+
+#endif
diff --git a/libsimple.h b/libsimple.h
index ffb8f8a..f4238cb 100644
--- a/libsimple.h
+++ b/libsimple.h
@@ -164,6 +164,7 @@
 #include "libsimple/str.h"
 #include "libsimple/strn.h"
 #include "libsimple/strtoint.h"
+#include "libsimple/search.h"
 
 
 /**
diff --git a/libsimple/search.h b/libsimple/search.h
new file mode 100644
index 0000000..19c1f85
--- /dev/null
+++ b/libsimple/search.h
@@ -0,0 +1,69 @@
+/* See LICENSE file for copyright and license details. */
+
+
+/**
+ * Find, using binary search, the position where an item in
+ * sorted list is located or should be located
+ * 
+ * @param   key     The item to find the position for
+ * @param   base    Sorted array to search
+ * @param   nel     The number of elements in `base`
+ * @param   width   The byte-width of each element in `base`
+ * @param   compar  Function used to compare `key` against an element
+ *                  in the array. The function be given two arguments:
+ *                  the first argument will always be `key`, the other
+ *                  will be an element in `base`. The function shall
+ *                  return a negative value if first argument shall
+ *                  precede the second argument when sorted into the
+ *                  list, or a positive value if the first argument
+ *                  shall succeed the second argument, but if the
+ *                  two argument are equal, the function shall return 0.
+ * @return          If the function finds `key` in `base`, it returns
+ *                  the index (starting from 0) of some such element
+ *                  in `base`, however if `key` is not found, the
+ *                  function returns the bitwise complement the index
+ *                  to each `key` may be inserted.
+ * 
+ * @seealso  bsearch(3p)
+ * @seealso  libsimple_bindex_r(3p)
+ */
+ssize_t libsimple_bindex(const void *key, const void *base, size_t nel, size_t width, /* TODO man */
+                         int (*compar)(const void *, const void *));
+#ifndef bindex
+# define bindex(...) libsimple_bindex(__VA_ARGS__)
+#endif
+
+/**
+ * Find, using binary search, the position where an item in
+ * sorted list is located or should be located
+ * 
+ * @param   key     The item to find the position for
+ * @param   base    Sorted array to search
+ * @param   nel     The number of elements in `base`
+ * @param   width   The byte-width of each element in `base`
+ * @param   compar  Function used to compare `key` against an element
+ *                  in the array. The function be given three arguments:
+ *                  the first argument will always be `key`, the second
+ *                  will be an element in `base`, and the third will
+ *                  always be `arg`. The function shall return a negative
+ *                  value if first argument shall precede the second
+ *                  argument when sorted into the list, or a positive
+ *                  value if the first argument shall succeed the second
+ *                  argument, but if the two argument are equal, the
+ *                  function shall return 0.
+ * @param   arg     User-defined value that is passed directly into
+ *                  `compar` as the third argument at each callback
+ * @return          If the function finds `key` in `base`, it returns
+ *                  the index (starting from 0) of some such element
+ *                  in `base`, however if `key` is not found, the
+ *                  function returns the bitwise complement the index
+ *                  to each `key` may be inserted.
+ * 
+ * @seealso  bsearch(3p)
+ * @seealso  libsimple_bindex(3p)
+ */
+ssize_t libsimple_bindex_r(const void *key, const void *base, size_t nel, size_t width, /* TODO man */
+                           int (*compar)(const void *, const void *, void *), void *arg);
+#ifndef bindex_r
+# define bindex_r(...) libsimple_bindex_r(__VA_ARGS__)
+#endif