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

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