various: make the _info License: wording uniform for GPL variants.
[ccan] / ccan / sparse_bsearch / sparse_bsearch.h
1 #ifndef SPARSE_BSEARCH_H
2 #define SPARSE_BSEARCH_H
3 #include <stdbool.h>
4 #include <stdlib.h>
5 #include <ccan/typesafe_cb/typesafe_cb.h>
6 #include <ccan/check_type/check_type.h>
7
8 /**
9  * sparse_bsearch - binary search of a sorted array with gaps.
10  * @key: the key to search for
11  * @base: the head of the array
12  * @nmemb: the number of elements in the array
13  * @cmpfn: the compare function (qsort/bsearch style)
14  * @validfn: whether this element is valid.
15  *
16  * Binary search of a sorted array, which may have some invalid entries.
17  * Note that cmpfn and validfn take const pointers.
18  *
19  * Example:
20  *      static bool val_valid(const unsigned int *val)
21  *      {
22  *              return *val != 0;
23  *      }
24  *      static int val_cmp(const unsigned int *a, const unsigned int *b)
25  *      {
26  *              return (int)((*a) - (*b));
27  *      }
28  *      static unsigned int values[] = { 1, 7, 11, 1235, 99999 };
29  *
30  *      // Return true if this value is in set, and remove it.
31  *      static bool remove_from_values(unsigned int val)
32  *      {
33  *              unsigned int *p;
34  *              p = sparse_bsearch(&val, values, 5, val_cmp, val_valid);
35  *              if (!p)
36  *                      return false;
37  *              *p = 0;
38  *              return true;
39  *      }
40  */
41 #define sparse_bsearch(key, base, nmemb, cmpfn, validfn)                \
42         _sparse_bsearch((key)+check_types_match((key), &(base)[0]),     \
43                         (base), (nmemb), sizeof((base)[0]),             \
44                         typesafe_cb_cast(int (*)(const void *, const void *), \
45                                          int (*)(const __typeof__(*(base)) *, \
46                                                  const __typeof__(*(base)) *), \
47                                          (cmpfn)),                      \
48                         typesafe_cb_cast(bool (*)(const void *),        \
49                                          bool (*)(const __typeof__(*(base)) *), \
50                                          (validfn)))
51
52 void *_sparse_bsearch(const void *key, const void *base,
53                       size_t nmemb, size_t size,
54                       int (*cmpfn)(const void *, const void *),
55                       bool (*validfn)(const void *));
56 #endif /* SPARSE_BSEARCH_H */