From 0d8d8a9c1db4c67602fc94d9d3723ef08485595a Mon Sep 17 00:00:00 2001 From: Rusty Russell Date: Wed, 30 Sep 2009 12:48:11 +0930 Subject: [PATCH] sparse_bsearch: new module --- ccan/sparse_bsearch/_info | 66 ++++++++++++++++++++++++++++ ccan/sparse_bsearch/sparse_bsearch.c | 36 +++++++++++++++ ccan/sparse_bsearch/sparse_bsearch.h | 50 +++++++++++++++++++++ ccan/sparse_bsearch/test/run.c | 64 +++++++++++++++++++++++++++ 4 files changed, 216 insertions(+) create mode 100644 ccan/sparse_bsearch/_info create mode 100644 ccan/sparse_bsearch/sparse_bsearch.c create mode 100644 ccan/sparse_bsearch/sparse_bsearch.h create mode 100644 ccan/sparse_bsearch/test/run.c diff --git a/ccan/sparse_bsearch/_info b/ccan/sparse_bsearch/_info new file mode 100644 index 00000000..9c5e8411 --- /dev/null +++ b/ccan/sparse_bsearch/_info @@ -0,0 +1,66 @@ +#include +#include +#include "config.h" + +/** + * sparse_bsearch - search a sorted array with some invalid entries + * + * bsearch() is great for searching an array, but if you are deleting from + * the array, you then need to memmove() to keep it dense. + * + * Sometimes there is a useful invalid value which can be used to mark deleted + * entries, but such a "gappy" array breaks bsearch. This function allows + * "invalid" entries in your array, which are ignored for the search. + * + * Example: + * #include + * + * static bool val_valid(unsigned int *val) + * { + * return *val != 0; + * } + * static int val_cmp(const unsigned int *a, const unsigned int *b) + * { + * return (int)((*a) - (*b)); + * } + * static unsigned int values[] = { 1, 7, 11, 1235, 99999 }; + * + * // Return true if this value is in set, and remove it. + * bool remove_from_values(unsigned int val) + * { + * unsigned int *p; + * // We use 5 here, but ccan/array_size.h is better! + * p = sparse_bsearch(&val, values, 5, val_cmp, val_valid); + * if (!p) + * return false; + * *p = 0; + * return true; + * } + * + * int main(int argc, char *argv[]) + * { + * int i, val; + * for (i = 1; i < argc; i++) { + * val = atoi(argv[i]); + * if (remove_from_values(val)) + * printf("%i removed.\n", val); + * else + * printf("%i wasn't there.\n", val); + * } + * return 0; + * } + */ +int main(int argc, char *argv[]) +{ + /* Expect exactly one argument */ + if (argc != 2) + return 1; + + if (strcmp(argv[1], "depends") == 0) { + printf("ccan/typesafe_cb\n" + "ccan/check_type\n"); + return 0; + } + + return 1; +} diff --git a/ccan/sparse_bsearch/sparse_bsearch.c b/ccan/sparse_bsearch/sparse_bsearch.c new file mode 100644 index 00000000..f0d58d23 --- /dev/null +++ b/ccan/sparse_bsearch/sparse_bsearch.c @@ -0,0 +1,36 @@ +#include "sparse_bsearch.h" + +void *_sparse_bsearch(const void *key, const void *base, + size_t nmemb, size_t size, + int (*cmpfn)(const void *, const void *), + bool (*validfn)(const void *)) +{ + ssize_t start = 0, end = nmemb - 1; + const char *p = base; + + while (start <= end) { + ssize_t next = (start + end) / 2; + int result; + + while (!validfn(p + next * size)) { + /* Try the next one along. */ + next++; + if (next > end) { + /* Hmm, none of these were valid. */ + next = (start + end) / 2; + goto trim; + } + } + + result = cmpfn(key, p + next * size); + if (result == 0) + return (void *)(p + next * size); + else if (result > 0) + start = next + 1; + else { + trim: + end = next - 1; + } + } + return NULL; +} diff --git a/ccan/sparse_bsearch/sparse_bsearch.h b/ccan/sparse_bsearch/sparse_bsearch.h new file mode 100644 index 00000000..5317dbf8 --- /dev/null +++ b/ccan/sparse_bsearch/sparse_bsearch.h @@ -0,0 +1,50 @@ +#ifndef SPARSE_BSEARCH_H +#define SPARSE_BSEARCH_H +#include +#include +#include +#include + +/** + * sparse_bsearch - binary search of a sorted array with gaps. + * @key: the key to search for + * @base: the head of the array + * @nmemb: the number of elements in the array + * @cmpfn: the compare function (qsort/bsearch style) + * @validfn: whether this element is valid. + * + * Binary search of a sorted array, which may have some invalid entries. + * + * Example: + * static bool val_valid(unsigned int *val) + * { + * return *val != 0; + * } + * static int val_cmp(const unsigned int *a, const unsigned int *b) + * { + * return (int)((*a) - (*b)); + * } + * static unsigned int values[] = { 1, 7, 11, 1235, 99999 }; + * + * // Return true if this value is in set, and remove it. + * bool remove_from_values(unsigned int val) + * { + * unsigned int *p; + * p = sparse_bsearch(&val, values, 5, val_cmp, val_valid); + * if (!p) + * return false; + * *p = 0; + * return true; + * } + */ +#define sparse_bsearch(key, base, nmemb, cmpfn, validfn) \ + _sparse_bsearch((key)+check_types_match((key), &(base)[0]), \ + (base), (nmemb), sizeof((base)[0]), \ + typesafe_cb_cmp(int, (cmpfn), (base)), \ + typesafe_cb_const(bool, (validfn), (base))) + +void *_sparse_bsearch(const void *key, const void *base, + size_t nmemb, size_t size, + int (*cmpfn)(const void *, const void *), + bool (*validfn)(const void *)); +#endif /* SPARSE_BSEARCH_H */ diff --git a/ccan/sparse_bsearch/test/run.c b/ccan/sparse_bsearch/test/run.c new file mode 100644 index 00000000..3acb3adb --- /dev/null +++ b/ccan/sparse_bsearch/test/run.c @@ -0,0 +1,64 @@ +/* Include the main header first, to test it works */ +#include +/* Include the C files directly. */ +#include +#include + +static int cmp(const unsigned int *a, const unsigned int *b) +{ + return (*a) - (*b); +} + +static bool valid(const unsigned int *a) +{ + return *a != 0; +} + +int main(void) +{ + unsigned int i, j, master[4] = { 1, 2, 3, 4 }, arr[4]; + + plan_tests((1 << 4) * 4+ (1 << 3) * 3); + + /* We test all possibilities of an even and an odd array len. */ + for (i = 0; i < (1 << 4); i++) { + /* Setup partial arr[] */ + for (j = 0; j < 4; j++) { + if (i & (1 << j)) + arr[j] = master[j]; + else + arr[j] = 0; + } + + for (j = 1; j <= 4; j++) { + unsigned int *ptr; + ptr = sparse_bsearch(&j, arr, 4, cmp, valid); + if (i & (1 << (j-1))) + ok1(ptr && *ptr == j); + else + ok1(!ptr); + } + } + + for (i = 0; i < (1 << 3); i++) { + /* Setup partial arr[] */ + for (j = 0; j < 3; j++) { + if (i & (1 << j)) + arr[j] = master[j]; + else + arr[j] = 0; + } + + for (j = 1; j <= 3; j++) { + unsigned int *ptr; + ptr = sparse_bsearch(&j, arr, 3, cmp, valid); + if (i & (1 << (j-1))) + ok1(ptr && *ptr == j); + else + ok1(!ptr); + } + } + + /* This exits depending on whether all tests passed */ + return exit_status(); +} -- 2.39.2