aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMattias Andrée <maandree@kth.se>2023-07-04 19:37:10 +0200
committerMattias Andrée <maandree@kth.se>2023-07-04 19:37:10 +0200
commitaab65f6d1793d2ded2629437afab007ba3db0bf1 (patch)
tree5750c8006bc8b280ed63e587d1062356747fc63d
parentlibsimple_localtime.3: fix formatting (diff)
downloadlibsimple-aab65f6d1793d2ded2629437afab007ba3db0bf1.tar.gz
libsimple-aab65f6d1793d2ded2629437afab007ba3db0bf1.tar.bz2
libsimple-aab65f6d1793d2ded2629437afab007ba3db0bf1.tar.xz
Add bindex and bindex_r
Signed-off-by: Mattias Andrée <maandree@kth.se>
-rw-r--r--LICENSE2
-rw-r--r--Makefile3
-rw-r--r--bindex.c39
-rw-r--r--bindex_r.c39
-rw-r--r--libsimple.h1
-rw-r--r--libsimple/search.h69
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