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

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