1 /* Licensed under LGPLv2+ - see LICENSE file for details */
2 #ifndef SPARSE_BSEARCH_H
3 #define SPARSE_BSEARCH_H
6 #include <ccan/typesafe_cb/typesafe_cb.h>
7 #include <ccan/check_type/check_type.h>
10 * sparse_bsearch - binary search of a sorted array with gaps.
11 * @key: the key to search for
12 * @base: the head of the array
13 * @nmemb: the number of elements in the array
14 * @cmpfn: the compare function (qsort/bsearch style)
15 * @validfn: whether this element is valid.
17 * Binary search of a sorted array, which may have some invalid entries.
18 * Note that cmpfn and validfn take const pointers.
21 * static bool val_valid(const unsigned int *val)
25 * static int val_cmp(const unsigned int *a, const unsigned int *b)
27 * return (int)((*a) - (*b));
29 * static unsigned int values[] = { 1, 7, 11, 1235, 99999 };
31 * // Return true if this value is in set, and remove it.
32 * static bool remove_from_values(unsigned int val)
35 * p = sparse_bsearch(&val, values, 5, val_cmp, val_valid);
42 #define sparse_bsearch(key, base, nmemb, cmpfn, validfn) \
43 _sparse_bsearch((key)+check_types_match((key), &(base)[0]), \
44 (base), (nmemb), sizeof((base)[0]), \
45 typesafe_cb_cast(int (*)(const void *, const void *), \
46 int (*)(const __typeof__(*(base)) *, \
47 const __typeof__(*(base)) *), \
49 typesafe_cb_cast(bool (*)(const void *), \
50 bool (*)(const __typeof__(*(base)) *), \
53 void *_sparse_bsearch(const void *key, const void *base,
54 size_t nmemb, size_t size,
55 int (*cmpfn)(const void *, const void *),
56 bool (*validfn)(const void *));
57 #endif /* SPARSE_BSEARCH_H */