From 7d2a0ffc6968e2412b2c7806cf7770271d620c1a Mon Sep 17 00:00:00 2001 From: Christian Hopps Date: Fri, 18 Apr 2025 12:32:34 +0000 Subject: [PATCH] lib: darr: add string search macros Add macros to support searching for and finding (perhaps closest) matches for a key in an array of strings. Signed-off-by: Christian Hopps --- lib/darr.c | 65 ++++++++++++++++++++++ lib/darr.h | 60 ++++++++++++++++++++ tests/lib/test_darr.c | 125 ++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 250 insertions(+) diff --git a/lib/darr.c b/lib/darr.c index 0cffa64425..9e62a46044 100644 --- a/lib/darr.c +++ b/lib/darr.c @@ -158,3 +158,68 @@ void *__darr_insert_n(void *a, uint at, uint count, size_t esize, bool zero, return a; #undef _a_at } + +int _darr_search_floor(const void *a, size_t esize, const void *key, bool *equal, + darr_search_cmpf cmpf) +{ + struct darr_metadata *dm; + + if (equal) + *equal = false; + + if (!a) + return -1; + + dm = (struct darr_metadata *)a - 1; + + int len = dm->len; + int low = 0, high = len - 1; + int floor = -1; + +#define _a_at(i) ((void *)((char *)a + ((i)*esize))) + while (low <= high) { + int mid = low + (high - low) / 2; + int cmp = cmpf(_a_at(mid), key); + + if (!cmp) { + if (equal) + *equal = true; + return mid; + } else if (cmp < 0) { + floor = mid; + low = mid + 1; + } else { + high = mid - 1; + } + } + + return floor; +#undef _a_at +} + +int _darr_search(const void *a, size_t esize, const void *key, darr_search_cmpf cmpf) +{ + bool equal; + int i; + + i = _darr_search_floor(a, esize, key, &equal, cmpf); + if (!equal) + return -1; + return i; +} + +uint _darr_search_ceil(const void *a, size_t esize, const void *key, bool *equal, + darr_search_cmpf cmpf) +{ + uint i; + + i = _darr_search_floor(a, esize, key, equal, cmpf); + if (*equal) + return i; + return i + 1; +} + +int darr_strings_cmp(const char **a, const char *key) +{ + return strcmp(*a, key); +} diff --git a/lib/darr.h b/lib/darr.h index 791f1ed498..d6f76226f3 100644 --- a/lib/darr.h +++ b/lib/darr.h @@ -64,6 +64,9 @@ * - darr_strlen * - darr_strlen_fixup * - darr_strnul + * - darr_str_search + * - darr_str_search_ceil + * - darr_str_search_floor * - darr_sprintf, darr_vsprintf */ /* @@ -788,6 +791,63 @@ void *__darr_resize(void *a, uint count, size_t esize, struct memtype *mt); d; \ }) +/* + * darr_search_{floor,ceil}() functions - search for key in sorted arrays + */ +typedef int (*darr_search_cmpf)(const void *ep, const void *key); +extern int darr_strings_cmp(const char **a, const char *key); +extern int _darr_search(const void *a, size_t esize, const void *key, darr_search_cmpf cmpf); +extern uint _darr_search_ceil(const void *a, size_t esize, const void *key, bool *equal, + darr_search_cmpf cmpf); +extern int _darr_search_floor(const void *a, size_t esize, const void *key, bool *equal, + darr_search_cmpf cmpf); + +/** + * darr_str_search() - Find exact key in array of strings. + * + * Args: + * A: array of string pointers + * K: key string + * + * Return: + * The index of the string which matches the key or -1 for no match. + */ +#define darr_str_search(A, K) \ + _darr_search((A), _darr_esize(A), (K), (darr_search_cmpf)darr_strings_cmp) + +/** + * darr_str_search_ceil() - Find least elm greater than or equal to the key + * + * Args: + * A: array of string pointers + * K: key string + * E: Ptr to bool, set to true if element matching key is found + * + * Return: + * The index of the least element that is greater than or equal to the @K + * string. @E is set to true if equal otherwise false. The return value can + * be passed directly to darr_insert(). + */ +#define darr_str_search_ceil(A, K, E) \ + _darr_search_ceil((A), _darr_esize(A), (K), (E), (darr_search_cmpf)darr_strings_cmp) + +/** + * darr_str_search_floor() - Find greatest elm less than or equal to the key + * + * Args: + * A: array of string pointers + * K: key string + * E: Ptr to bool, set to true if element matching key is found + * + * Return: + * The index of the greatest element that is less than or equal to the @K + * string. @E is set to true if equal otherwise false. If used with + * darr_insert() then the index should be passed +1 because darr_insert() + * inserts *before* the given index. + */ +#define darr_str_search_floor(A, K, E) \ + _darr_search_floor((A), _darr_esize(A), (K), (E), (darr_search_cmpf)darr_strings_cmp) + /** * Iterate over array `A` using a pointer to each element in `P`. * diff --git a/tests/lib/test_darr.c b/tests/lib/test_darr.c index d980db505d..9cc8005a25 100644 --- a/tests/lib/test_darr.c +++ b/tests/lib/test_darr.c @@ -50,6 +50,9 @@ * [x] - darr_strlen * [x] - darr_strlen_fixup * [x] - darr_strnul + * [x] - darr_str_search + * [x] - darr_str_search_ceil + * [x] - darr_str_search_floor * [ ] - darr_vsprintf */ @@ -329,6 +332,8 @@ static void test_string(void) const char **strings = NULL; uint sum = 0; uint i; + bool b; + int idx; i = darr_strlen(da1); assert(i == 0); @@ -462,6 +467,126 @@ static void test_string(void) darr_free_free(strings); assert(strings == NULL); + + add = darr_strdup("5"); + i = darr_str_search_ceil(strings, add, &b); + assert(!b); + *darr_insert(strings, i) = add; + + add = darr_strdup("2"); + i = darr_str_search_ceil(strings, add, &b); + assert(!b); + *darr_insert(strings, i) = add; + + add = darr_strdup("9"); + i = darr_str_search_ceil(strings, add, &b); + assert(!b); + *darr_insert(strings, i) = add; + + add = darr_strdup("3"); + i = darr_str_search_ceil(strings, add, &b); + assert(!b); + *darr_insert(strings, i) = add; + + i = darr_str_search_ceil(strings, "0", &b); + assert(!b); + assert(i == 0); + i = darr_str_search_ceil(strings, "1", &b); + assert(!b); + assert(i == 0); + i = darr_str_search_ceil(strings, "2", &b); + assert(b); + assert(i == 0); + i = darr_str_search_ceil(strings, "3", &b); + assert(b); + assert(i == 1); + i = darr_str_search_ceil(strings, "4", &b); + assert(!b); + assert(i == 2); + i = darr_str_search_ceil(strings, "5", &b); + assert(b); + assert(i == 2); + i = darr_str_search_ceil(strings, "6", &b); + assert(!b); + assert(i == 3); + i = darr_str_search_ceil(strings, "7", &b); + assert(!b); + assert(i == 3); + i = darr_str_search_ceil(strings, "8", &b); + assert(!b); + assert(i == 3); + i = darr_str_search_ceil(strings, "9", &b); + assert(b); + assert(i == 3); + i = darr_str_search_ceil(strings, "X", &b); + assert(!b); + assert(i == 4); + + assert(!strcmp(strings[0], "2")); + assert(!strcmp(strings[1], "3")); + assert(!strcmp(strings[2], "5")); + assert(!strcmp(strings[3], "9")); + + darr_free_free(strings); + assert(strings == NULL); + + /* -------------------- */ + /* Test sorted prefixes */ + /* -------------------- */ + + add = darr_strdup("/foo"); + i = darr_str_search_ceil(strings, add, &b); + assert(!b); + *darr_insert(strings, i) = add; + + add = darr_strdup("/bar"); + i = darr_str_search_ceil(strings, add, &b); + assert(!b); + *darr_insert(strings, i) = add; + + add = darr_strdup("/abc"); + i = darr_str_search_ceil(strings, add, &b); + assert(!b); + *darr_insert(strings, i) = add; + + add = darr_strdup("/xyz/abc"); + i = darr_str_search_ceil(strings, add, &b); + assert(!b); + *darr_insert(strings, i) = add; + + add = darr_strdup("/foo/bar"); + i = darr_str_search_ceil(strings, add, &b); + assert(!b); + *darr_insert(strings, i) = add; + + i = darr_str_search_ceil(strings, "/abc", &b); + assert(i == 0 && b); + i = darr_str_search_ceil(strings, "/bar", &b); + assert(i == 1 && b); + i = darr_str_search_ceil(strings, "/foo", &b); + assert(i == 2 && b); + i = darr_str_search_ceil(strings, "/foo/bar", &b); + assert(i == 3 && b); + i = darr_str_search_ceil(strings, "/xyz/abc", &b); + assert(i == 4 && b); + + idx = darr_str_search(strings, "/abc"); + assert(idx == 0); + idx = darr_str_search(strings, "/abc/123"); + assert(idx == -1); + idx = darr_str_search(strings, "/xyz"); + assert(idx == -1); + idx = darr_str_search(strings, "/xyz/abc"); + assert(idx == 4); + + assert(!strcmp(strings[0], "/abc")); + assert(!strcmp(strings[1], "/bar")); + assert(!strcmp(strings[2], "/foo")); + assert(!strcmp(strings[3], "/foo/bar")); + assert(!strcmp(strings[4], "/xyz/abc")); + + darr_free_free(strings); + assert(strings == NULL); } int main(int argc, char **argv) -- 2.39.5