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 <david@gibson.dropbear.id.au>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

diff --git a/ccan/asearch/_info b/ccan/asearch/_info
index e25f2e7384c5a6a205aec5ea6464c53666c20b90..18d9395309c80455a05798a9a4de16dbdc9614a4 100644 (file)
--- a/ccan/asearch/_info
+++ b/ccan/asearch/_info
@@ -18,7 +18,7 @@
  *     #include <stdio.h>
  *     #include <string.h>
  *     
  *     #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);
  *     }
  *     {
  *             return strcmp(key, *elem);
  *     }


@@ -34,7 +34,7 @@
  *                     exit(1);
  *             }
  *     
  *                     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;
  *             if (!p) {
  *                     printf("Not found!\n");
  *                     return 1;

diff --git a/ccan/asearch/asearch.c b/ccan/asearch/asearch.c
new file mode 100644 (file)
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 aae6eeda959acd9a18695f7f9707fa83c3170392..68ecebdb28f5a756908c333dbb2eca0d4e957ea6 100644 (file)
--- a/ccan/asearch/asearch.h
+++ b/ccan/asearch/asearch.h
@@ -4,6 +4,8 @@
 #include <stdlib.h>
 #include <ccan/typesafe_cb/typesafe_cb.h>
 
 #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
 /**
  * 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
  * 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)) *,    \
                                 int (*)(const __typeof__(*(key)) *,    \

-                                        const __typeof__(*(base)) *),  \
-                                (cmp)))))
+                                        const __typeof__(*(base)) *,   \
+                                        __typeof__(*(ctx)) *),         \
+                                (cmp)), (ctx))))

 
 #else
 
 #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
 
 #endif
 

+void *_asearch(const void *key, const void *base,
+              size_t nmemb, size_t size,
+              asearch_cmp compar, void *ctx);
+

 #endif /* CCAN_ASEARCH_H */
 #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 2edee935012ff2c2352710e9d88120a962f6ab47..9797672bd08438012b83958fea22fae584e61bf8 100644 (file)
--- 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>
 
 #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);
 }
 {
        return strcmp(key, *elem);
 }


@@ -20,6 +22,6 @@ int main(void)
 #else
        const char **p;
 #endif
 #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;
 }
        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 4aef5327a8347970b19e5470cfdcde5cf50e45c7..226f279bd9e5cbae490f8e3eedbca6234b292191 100644 (file)
--- 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>
 
 #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;
 }
 {
        return 0;
 }


@@ -17,6 +19,6 @@ int main(int argc, char **argv)
 #else
        char **p;
 #endif
 #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;
 }
        return p ? 0 : 1;
 }

diff --git a/ccan/asearch/test/run-strings.c b/ccan/asearch/test/run-strings.c
index 3ec453842f8df6e3e6a6d8f69f2d2edea49c83b6..b48f8e3100c29c270b0916d3860442ca16ce908b 100644 (file)
--- 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>
 
 #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);
 }
 {
        return *key - atoi(*elem);
 }


@@ -15,7 +17,7 @@ int main(void)
        const char **p;
 
        plan_tests(1);
        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();
        ok1(p == &args[2]);
 
        return exit_status();

diff --git a/ccan/asearch/test/run.c b/ccan/asearch/test/run.c
index 2a896fccfe807c2c9a0ecb28dc1ea4d02e2b395b..ae35ac0c8ff43a8ef295820cc9d35e9d9940560f 100644 (file)
--- a/ccan/asearch/test/run.c
+++ b/ccan/asearch/test/run.c
@@ -3,7 +3,9 @@
 #include <ccan/tap/tap.h>
 #include <limits.h>
 
 #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;
 {
        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;
        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];
                        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++;
                                ok1(ret);
                                ok1(ret && *ret == key);
                                total++;

diff --git a/ccan/ntdb/check.c b/ccan/ntdb/check.c
index 5b6e90558255c11e78bad08b67288e78d9606abb..f24239457b53dd84c6fb4069612ba41394f1aa77 100644 (file)
--- 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;
 }
 
        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
 {
        /* 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);
        }
 
                                   " %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"
        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 */
                        }
 
                        /* 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,
                        if (!p) {
                                return ntdb_logerr(ntdb, NTDB_ERR_CORRUPT,
                                                  NTDB_LOG_ERROR,