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