From aab65f6d1793d2ded2629437afab007ba3db0bf1 Mon Sep 17 00:00:00 2001 From: Mattias Andrée Date: Tue, 4 Jul 2023 19:37:10 +0200 Subject: Add bindex and bindex_r MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Signed-off-by: Mattias Andrée --- LICENSE | 2 +- Makefile | 3 +++ bindex.c | 39 ++++++++++++++++++++++++++++++ bindex_r.c | 39 ++++++++++++++++++++++++++++++ libsimple.h | 1 + libsimple/search.h | 69 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 152 insertions(+), 1 deletion(-) create mode 100644 bindex.c create mode 100644 bindex_r.c create mode 100644 libsimple/search.h 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 +© 2017, 2018, 2021, 2022, 2023 Mattias Andrée 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 -- cgit v1.2.3-70-g09d2