tdb2: implement tdb_chainlock_read/tdb_chainunlock_read.
[ccan] / 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 }