[ccan] [PATCH 2/2] asearch: Add context pointer to asearch comparison callback
David Gibson
david at gibson.dropbear.id.au
Thu May 28 00:17:35 AEST 2015
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 <david at gibson.dropbear.id.au>
---
ccan/asearch/_info | 4 +-
ccan/asearch/asearch.c | 49 ++++++++++++++++++++++
ccan/asearch/asearch.h | 23 ++++++----
.../asearch/test/compile_fail-return-value-const.c | 6 ++-
ccan/asearch/test/compile_fail-return-value.c | 6 ++-
ccan/asearch/test/run-strings.c | 6 ++-
ccan/asearch/test/run.c | 10 +++--
ccan/ntdb/check.c | 6 +--
8 files changed, 88 insertions(+), 22 deletions(-)
create mode 100644 ccan/asearch/asearch.c
diff --git a/ccan/asearch/_info b/ccan/asearch/_info
index e25f2e7..18d9395 100644
--- a/ccan/asearch/_info
+++ b/ccan/asearch/_info
@@ -18,7 +18,7 @@
* #include <stdio.h>
* #include <string.h>
*
- * 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 0000000..f189dcd
--- /dev/null
+++ b/ccan/asearch/asearch.c
@@ -0,0 +1,49 @@
+#include <ccan/asearch/asearch.h>
+
+#include <stddef.h>
+
+/* 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
+ <http://www.gnu.org/licenses/>. */
+
+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 aae6eed..68ecebd 100644
--- a/ccan/asearch/asearch.h
+++ b/ccan/asearch/asearch.h
@@ -4,6 +4,8 @@
#include <stdlib.h>
#include <ccan/typesafe_cb/typesafe_cb.h>
+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 2edee93..9797672 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 <ccan/array_size/array_size.h>
#include <string.h>
-static int cmp(const char *key, const char *const *elem)
+#include <ccan/asearch/asearch.c>
+
+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 4aef532..226f279 100644
--- a/ccan/asearch/test/compile_fail-return-value.c
+++ b/ccan/asearch/test/compile_fail-return-value.c
@@ -1,6 +1,8 @@
#include <ccan/asearch/asearch.h>
-static int cmp(const char *key, char *const *elem)
+#include <ccan/asearch/asearch.c>
+
+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 3ec4538..b48f8e3 100644
--- a/ccan/asearch/test/run-strings.c
+++ b/ccan/asearch/test/run-strings.c
@@ -3,7 +3,9 @@
#include <ccan/tap/tap.h>
#include <stdlib.h>
-static int cmp(const int *key, const char *const *elem)
+#include <ccan/asearch/asearch.c>
+
+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 2a896fc..ae35ac0 100644
--- a/ccan/asearch/test/run.c
+++ b/ccan/asearch/test/run.c
@@ -3,7 +3,9 @@
#include <ccan/tap/tap.h>
#include <limits.h>
-static int test_cmp(const int *key, const int *elt)
+#include <ccan/asearch/asearch.c>
+
+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 5b6e905..f242394 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,
--
2.1.0
More information about the ccan
mailing list