From: David Gibson Date: Wed, 27 May 2015 14:17:35 +0000 (+1000) Subject: asearch: Add context pointer to asearch comparison callback X-Git-Url: https://git.ozlabs.org/?p=ccan;a=commitdiff_plain;h=e7519047a8b495c8e4011168c7ee777db0d90dc9 asearch: Add context pointer to asearch comparison callback asearch, like the standard library bsearch, takes a comparison callback. Like bsearch() that callback doesn't include a user supplied context pointer. As well as being generally limiting, that makes the comparison functions used by asearch gratuitously different from those used by the asort module. This patch alters this. Note that this is an incompatible change to the asearch interface. I think this is worth it to correct the oversight, but others might disagree. At present the only user within ccan is ntdb, which is corrected to match. This means actually supplying a binary search implementation, rather than relying on bsearch() from the standard library. We follow the lead of the asort module and steal^H^H^H^H^Hadapt the implementation from glibc. Signed-off-by: David Gibson Signed-off-by: Rusty Russell --- diff --git a/ccan/asearch/_info b/ccan/asearch/_info index e25f2e73..18d93953 100644 --- a/ccan/asearch/_info +++ b/ccan/asearch/_info @@ -18,7 +18,7 @@ * #include * #include * - * static int cmp(const char *key, char *const *elem) + * static int cmp(const char *key, char *const *elem, void *ctx) * { * return strcmp(key, *elem); * } @@ -34,7 +34,7 @@ * exit(1); * } * - * p = asearch(argv[1], &argv[2], argc-2, cmp); + * p = asearch(argv[1], &argv[2], argc-2, cmp, NULL); * if (!p) { * printf("Not found!\n"); * return 1; diff --git a/ccan/asearch/asearch.c b/ccan/asearch/asearch.c new file mode 100644 index 00000000..f189dcd7 --- /dev/null +++ b/ccan/asearch/asearch.c @@ -0,0 +1,49 @@ +#include + +#include + +/* Steal glibc's code. */ + +/* Perform binary search - inline version. + Copyright (C) 1991-2015 Free Software Foundation, Inc. + This file is part of the GNU C Library. + + The GNU C Library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + The GNU C Library 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 + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with the GNU C Library; if not, see + . */ + +void * +_asearch (const void *__key, const void *__base, size_t __nmemb, size_t __size, + asearch_cmp __compar, void *ctx) +{ + size_t __l, __u, __idx; + const void *__p; + int __comparison; + + __l = 0; + __u = __nmemb; + while (__l < __u) + { + __idx = (__l + __u) / 2; + __p = (void *) (((const char *) __base) + (__idx * __size)); + __comparison = (*__compar) (__key, __p, ctx); + if (__comparison < 0) + __u = __idx; + else if (__comparison > 0) + __l = __idx + 1; + else + return (void *) __p; + } + + return NULL; +} diff --git a/ccan/asearch/asearch.h b/ccan/asearch/asearch.h index aae6eeda..68ecebdb 100644 --- a/ccan/asearch/asearch.h +++ b/ccan/asearch/asearch.h @@ -4,6 +4,8 @@ #include #include +typedef int (*asearch_cmp)(const void *, const void *, void *); + /** * asearch - search an array of elements * @key: pointer to item being searched for @@ -22,17 +24,22 @@ * the same comparison function for both sort() and asearch(). */ #if HAVE_TYPEOF -#define asearch(key, base, num, cmp) \ - ((__typeof__(*(base))*)(bsearch((key), (base), (num), sizeof(*(base)), \ - typesafe_cb_cast(int (*)(const void *, const void *), \ +#define asearch(key, base, num, cmp, ctx) \ + ((__typeof__(*(base))*)(_asearch((key), (base), (num), sizeof(*(base)), \ + typesafe_cb_cast(asearch_cmp, \ int (*)(const __typeof__(*(key)) *, \ - const __typeof__(*(base)) *), \ - (cmp))))) + const __typeof__(*(base)) *, \ + __typeof__(*(ctx)) *), \ + (cmp)), (ctx)))) #else -#define asearch(key, base, num, cmp) \ - (bsearch((key), (base), (num), sizeof(*(base)), \ - (int (*)(const void *, const void *))(cmp))) +#define asearch(key, base, num, cmp, ctx) \ + (_asearch((key), (base), (num), sizeof(*(base)), \ + (int (*)(const void *, const void *, void *))(cmp), (ctx))) #endif +void *_asearch(const void *key, const void *base, + size_t nmemb, size_t size, + asearch_cmp compar, void *ctx); + #endif /* CCAN_ASEARCH_H */ diff --git a/ccan/asearch/test/compile_fail-return-value-const.c b/ccan/asearch/test/compile_fail-return-value-const.c index 2edee935..9797672b 100644 --- a/ccan/asearch/test/compile_fail-return-value-const.c +++ b/ccan/asearch/test/compile_fail-return-value-const.c @@ -2,7 +2,9 @@ #include #include -static int cmp(const char *key, const char *const *elem) +#include + +static int cmp(const char *key, const char *const *elem, void *ctx) { return strcmp(key, *elem); } @@ -20,6 +22,6 @@ int main(void) #else const char **p; #endif - p = asearch(key, elems, ARRAY_SIZE(elems), cmp); + p = asearch(key, elems, ARRAY_SIZE(elems), cmp, NULL); return p ? 0 : 1; } diff --git a/ccan/asearch/test/compile_fail-return-value.c b/ccan/asearch/test/compile_fail-return-value.c index 4aef5327..226f279b 100644 --- a/ccan/asearch/test/compile_fail-return-value.c +++ b/ccan/asearch/test/compile_fail-return-value.c @@ -1,6 +1,8 @@ #include -static int cmp(const char *key, char *const *elem) +#include + +static int cmp(const char *key, char *const *elem, void *ctx) { return 0; } @@ -17,6 +19,6 @@ int main(int argc, char **argv) #else char **p; #endif - p = asearch(key, argv+1, argc-1, cmp); + p = asearch(key, argv+1, argc-1, cmp, NULL); return p ? 0 : 1; } diff --git a/ccan/asearch/test/run-strings.c b/ccan/asearch/test/run-strings.c index 3ec45384..b48f8e31 100644 --- a/ccan/asearch/test/run-strings.c +++ b/ccan/asearch/test/run-strings.c @@ -3,7 +3,9 @@ #include #include -static int cmp(const int *key, const char *const *elem) +#include + +static int cmp(const int *key, const char *const *elem, void *ctx) { return *key - atoi(*elem); } @@ -15,7 +17,7 @@ int main(void) const char **p; plan_tests(1); - p = asearch(&key, args, ARRAY_SIZE(args), cmp); + p = asearch(&key, args, ARRAY_SIZE(args), cmp, NULL); ok1(p == &args[2]); return exit_status(); diff --git a/ccan/asearch/test/run.c b/ccan/asearch/test/run.c index 2a896fcc..ae35ac0c 100644 --- a/ccan/asearch/test/run.c +++ b/ccan/asearch/test/run.c @@ -3,7 +3,9 @@ #include #include -static int test_cmp(const int *key, const int *elt) +#include + +static int test_cmp(const int *key, const int *elt, void *ctx) { if (*key < *elt) return -1; @@ -23,12 +25,14 @@ int main(void) for (start = 0; start < ARRAY_SIZE(arr); start++) { for (num = 0; num < ARRAY_SIZE(arr) - start; num++) { key = 7; - ok1(asearch(&key, &arr[start], num, test_cmp) == NULL); + ok1(asearch(&key, &arr[start], num, test_cmp, + NULL) == NULL); total++; for (i = start; i < start+num; i++) { const int *ret; key = arr[i]; - ret = asearch(&key, &arr[start], num, test_cmp); + ret = asearch(&key, &arr[start], num, + test_cmp, NULL); ok1(ret); ok1(ret && *ret == key); total++; diff --git a/ccan/ntdb/check.c b/ccan/ntdb/check.c index 5b6e9055..f2423945 100644 --- a/ccan/ntdb/check.c +++ b/ccan/ntdb/check.c @@ -114,7 +114,7 @@ static enum NTDB_ERROR check_header(struct ntdb_context *ntdb, return NTDB_SUCCESS; } -static int off_cmp(const ntdb_off_t *a, const ntdb_off_t *b) +static int off_cmp(const ntdb_off_t *a, const ntdb_off_t *b, void *ctx) { /* Can overflow an int. */ return *a > *b ? 1 @@ -153,7 +153,7 @@ static enum NTDB_ERROR check_entry(struct ntdb_context *ntdb, " %llu", (long long)off_and_hash); } - p = asearch(&off, used, num_used, off_cmp); + p = asearch(&off, used, num_used, off_cmp, NULL); if (!p) { return ntdb_logerr(ntdb, NTDB_ERR_CORRUPT, NTDB_LOG_ERROR, "ntdb_check: Invalid offset" @@ -430,7 +430,7 @@ static enum NTDB_ERROR check_free_table(struct ntdb_context *ntdb, } /* FIXME: Check hash bits */ - p = asearch(&off, fr, num_free, off_cmp); + p = asearch(&off, fr, num_free, off_cmp, NULL); if (!p) { return ntdb_logerr(ntdb, NTDB_ERR_CORRUPT, NTDB_LOG_ERROR,