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

   1 #include "sparse_bsearch.h"
   2
   3 void *_sparse_bsearch(const void *key, const void *base,
   4                       size_t nmemb, size_t size,
   5                       int (*cmpfn)(const void *, const void *),
   6                       bool (*validfn)(const void *))
   7 {
   8         ssize_t start = 0, end = nmemb - 1;
   9         const char *p = base;
  10
  11         while (start <= end) {
  12                 ssize_t next = (start + end) / 2;
  13                 int result;
  14
  15                 while (!validfn(p + next * size)) {
  16                         /* Try the next one along. */
  17                         next++;
  18                         if (next > end) {
  19                                 /* Hmm, none of these were valid. */
  20                                 next = (start + end) / 2;
  21                                 goto trim;
  22                         }
  23                 }
  24
  25                 result = cmpfn(key, p + next * size);
  26                 if (result == 0)
  27                         return (void *)(p + next * size);
  28                 else if (result > 0)
  29                         start = next + 1;
  30                 else {
  31                 trim:
  32                         end = next - 1;
  33                 }
  34         }
  35         return NULL;
  36 }