git.ozlabs.org Git - ccan/blob - ccan/sparse_bsearch/sparse_bsearch.h

   1 /* Licensed under LGPLv2+ - see LICENSE file for details */
   2 #ifndef SPARSE_BSEARCH_H
   3 #define SPARSE_BSEARCH_H
   4 #include <stdbool.h>
   5 #include <stdlib.h>
   6 #include <ccan/typesafe_cb/typesafe_cb.h>
   7 #include <ccan/check_type/check_type.h>
   8
   9 /**
  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.
  16  *
  17  * Binary search of a sorted array, which may have some invalid entries.
  18  * Note that cmpfn and validfn take const pointers.
  19  *
  20  * Example:
  21  *      static bool val_valid(const unsigned int *val)
  22  *      {
  23  *              return *val != 0;
  24  *      }
  25  *      static int val_cmp(const unsigned int *a, const unsigned int *b)
  26  *      {
  27  *              return (int)((*a) - (*b));
  28  *      }
  29  *      static unsigned int values[] = { 1, 7, 11, 1235, 99999 };
  30  *
  31  *      // Return true if this value is in set, and remove it.
  32  *      static bool remove_from_values(unsigned int val)
  33  *      {
  34  *              unsigned int *p;
  35  *              p = sparse_bsearch(&val, values, 5, val_cmp, val_valid);
  36  *              if (!p)
  37  *                      return false;
  38  *              *p = 0;
  39  *              return true;
  40  *      }
  41  */
  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)) *), \
  48                                          (cmpfn)),                      \
  49                         typesafe_cb_cast(bool (*)(const void *),        \
  50                                          bool (*)(const __typeof__(*(base)) *), \
  51                                          (validfn)))
  52
  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 */