asearch: typesafe binary search.

diff --git a/ccan/asearch/_info b/ccan/asearch/_info
new file mode 100644 (file)
index 0000000..327519d
--- /dev/null
+++ b/ccan/asearch/_info
@@ -0,0 +1,57 @@
+#include <stdio.h>
+#include <string.h>
+#include "config.h"
+
+/**
+ * asearch - typesafe binary search (bsearch)
+ *
+ * An ordered array of objects can be efficiently searched using a binary
+ * search algorithm; the time taken is around log(number of elements).
+ *
+ * This version uses macros to be typesafe on platforms which support it.
+ *
+ * Licence: LGPL
+ *
+ * Example:
+ *     #include <ccan/asearch/asearch.h>
+ *     #include <stdio.h>
+ *     #include <string.h>
+ *     
+ *     static int cmp(const char *key, char *const *elem)
+ *     {
+ *             return strcmp(key, *elem);
+ *     }
+ *     
+ *     int main(int argc, char *argv[])
+ *     {
+ *             char **p;
+ *     
+ *             if (argc < 2) {
+ *                     fprintf(stderr, "Usage: %s <key> <list>...\n"
+ *                             "Print position of key in (sorted) list\n",
+ *                             argv[0]);
+ *                     exit(1);
+ *             }
+ *     
+ *             p = asearch(argv[1], &argv[2], argc-2, cmp);
+ *             if (!p) {
+ *                     printf("Not found!\n");
+ *                     return 1;
+ *             }
+ *             printf("%u\n", p - &argv[2]);
+ *             return 0;
+ *     }
+ */
+int main(int argc, char *argv[])
+{
+       if (argc != 2)
+               return 1;
+
+       if (strcmp(argv[1], "depends") == 0) {
+               printf("ccan/typesafe_cb\n");
+               printf("ccan/array_size\n");
+               return 0;
+       }
+
+       return 1;
+}

diff --git a/ccan/asearch/asearch.h b/ccan/asearch/asearch.h
new file mode 100644 (file)
index 0000000..2c28ab1
--- /dev/null
+++ b/ccan/asearch/asearch.h
@@ -0,0 +1,36 @@
+#ifndef CCAN_ASEARCH_H
+#define CCAN_ASEARCH_H
+#include <stdlib.h>
+#include <ccan/typesafe_cb/typesafe_cb.h>
+
+/*
+ * asearch - search an array of elements
+ * @key: pointer to item being searched for
+ * @base: pointer to data to sort
+ * @num: number of elements
+ * @cmp: pointer to comparison function
+ *
+ * This function does a binary search on the given array.  The
+ * contents of the array should already be in ascending sorted order
+ * under the provided comparison function.
+ *
+ * Note that the key need not have the same type as the elements in
+ * the array, e.g. key could be a string and the comparison function
+ * could compare the string with the struct's name field.  However, if
+ * the key and elements in the array are of the same type, you can use
+ * 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)), \
+            cast_if_type((cmp),                                        \
+                         int (*)(const __typeof__(*(key)) *,           \
+                                 const __typeof__(*(base)) *),         \
+                         int (*)(const void *, const void *)))))
+#else
+#define asearch(key, base, num, cmp)                           \
+       (bsearch((key), (base), (num), sizeof(*(base)),         \
+                (int (*)(const void *, const void *))(cmp)))
+#endif
+
+#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
new file mode 100644 (file)
index 0000000..2edee93
--- /dev/null
+++ b/ccan/asearch/test/compile_fail-return-value-const.c
@@ -0,0 +1,25 @@
+#include <ccan/asearch/asearch.h>
+#include <ccan/array_size/array_size.h>
+#include <string.h>
+
+static int cmp(const char *key, const char *const *elem)
+{
+       return strcmp(key, *elem);
+}
+
+int main(void)
+{
+       const char key[] = "key";
+       const char *elems[] = { "a", "big", "list", "of", "things" };
+
+#ifdef FAIL
+       char **p;
+#if !HAVE_TYPEOF
+#error "Unfortunately we don't fail if no typeof."
+#endif
+#else
+       const char **p;
+#endif
+       p = asearch(key, elems, ARRAY_SIZE(elems), cmp);
+       return p ? 0 : 1;
+}

diff --git a/ccan/asearch/test/compile_fail-return-value.c b/ccan/asearch/test/compile_fail-return-value.c
new file mode 100644 (file)
index 0000000..4aef532
--- /dev/null
+++ b/ccan/asearch/test/compile_fail-return-value.c
@@ -0,0 +1,22 @@
+#include <ccan/asearch/asearch.h>
+
+static int cmp(const char *key, char *const *elem)
+{
+       return 0;
+}
+
+int main(int argc, char **argv)
+{
+       const char key[] = "key";
+
+#ifdef FAIL
+       int **p;
+#if !HAVE_TYPEOF
+#error "Unfortunately we don't fail if no typeof."
+#endif
+#else
+       char **p;
+#endif
+       p = asearch(key, argv+1, argc-1, cmp);
+       return p ? 0 : 1;
+}

diff --git a/ccan/asearch/test/run-strings.c b/ccan/asearch/test/run-strings.c
new file mode 100644 (file)
index 0000000..3ec4538
--- /dev/null
+++ b/ccan/asearch/test/run-strings.c
@@ -0,0 +1,22 @@
+#include <ccan/asearch/asearch.h>
+#include <ccan/array_size/array_size.h>
+#include <ccan/tap/tap.h>
+#include <stdlib.h>
+
+static int cmp(const int *key, const char *const *elem)
+{
+       return *key - atoi(*elem);
+}
+
+int main(void)
+{
+       const char *args[] = { "1", "4", "7", "9" };
+       int key = 7;
+       const char **p;
+
+       plan_tests(1);
+       p = asearch(&key, args, ARRAY_SIZE(args), cmp);
+       ok1(p == &args[2]);
+
+       return exit_status();
+}

diff --git a/ccan/asearch/test/run.c b/ccan/asearch/test/run.c
new file mode 100644 (file)
index 0000000..2a896fc
--- /dev/null
+++ b/ccan/asearch/test/run.c
@@ -0,0 +1,40 @@
+#include <ccan/asearch/asearch.h>
+#include <ccan/array_size/array_size.h>
+#include <ccan/tap/tap.h>
+#include <limits.h>
+
+static int test_cmp(const int *key, const int *elt)
+{
+       if (*key < *elt)
+               return -1;
+       else if (*key > *elt)
+               return 1;
+       return 0;
+}
+
+int main(void)
+{
+       const int arr[] = { INT_MIN, 0, 1, 2, 3, 4, 5, 6, INT_MAX };
+       unsigned int start, num, i, total = 0;
+       int key;
+
+       plan_tests(285);
+
+       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);
+                       total++;
+                       for (i = start; i < start+num; i++) {
+                               const int *ret;
+                               key = arr[i];
+                               ret = asearch(&key, &arr[start], num, test_cmp);
+                               ok1(ret);
+                               ok1(ret && *ret == key);
+                               total++;
+                       }
+               }
+       }
+       diag("Tested %u searches\n", total);
+       return exit_status();
+}