From: Rusty Russell Date: Thu, 19 Nov 2009 13:26:33 +0000 (+1030) Subject: asearch: typesafe binary search. X-Git-Url: https://git.ozlabs.org/?p=ccan;a=commitdiff_plain;h=93d1e1063c6b5599ab334398234d2de05c1236e8 asearch: typesafe binary search. --- diff --git a/ccan/asearch/_info b/ccan/asearch/_info new file mode 100644 index 00000000..327519d3 --- /dev/null +++ b/ccan/asearch/_info @@ -0,0 +1,57 @@ +#include +#include +#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 + * #include + * #include + * + * 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 ...\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 index 00000000..2c28ab1c --- /dev/null +++ b/ccan/asearch/asearch.h @@ -0,0 +1,36 @@ +#ifndef CCAN_ASEARCH_H +#define CCAN_ASEARCH_H +#include +#include + +/* + * 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 index 00000000..2edee935 --- /dev/null +++ b/ccan/asearch/test/compile_fail-return-value-const.c @@ -0,0 +1,25 @@ +#include +#include +#include + +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 index 00000000..4aef5327 --- /dev/null +++ b/ccan/asearch/test/compile_fail-return-value.c @@ -0,0 +1,22 @@ +#include + +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 index 00000000..3ec45384 --- /dev/null +++ b/ccan/asearch/test/run-strings.c @@ -0,0 +1,22 @@ +#include +#include +#include +#include + +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 index 00000000..2a896fcc --- /dev/null +++ b/ccan/asearch/test/run.c @@ -0,0 +1,40 @@ +#include +#include +#include +#include + +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(); +}