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
39
40
41
42
43
44
45
46
47
48
|
/* Copyright (c) 2005-2018 Dovecot authors, see the included COPYING file */
#include "lib.h"
#include "array.h"
#include "bsearch-insert-pos.h"
#undef bsearch_insert_pos
bool bsearch_insert_pos(const void *key, const void *base, unsigned int nmemb,
size_t size, int (*cmp)(const void *, const void *),
unsigned int *idx_r)
{
const void *p;
unsigned int idx, left_idx, right_idx;
int ret;
i_assert(nmemb < INT_MAX);
idx = 0; left_idx = 0; right_idx = nmemb;
while (left_idx < right_idx) {
idx = (left_idx + right_idx) / 2;
p = CONST_PTR_OFFSET(base, idx * size);
ret = cmp(key, p);
if (ret > 0)
left_idx = idx+1;
else if (ret < 0)
right_idx = idx;
else {
*idx_r = idx;
return TRUE;
}
}
if (left_idx > idx)
idx++;
*idx_r = idx;
return FALSE;
}
bool array_bsearch_insert_pos_i(const struct array *array, const void *key,
int (*cmp)(const void *, const void *),
unsigned int *idx_r)
{
return bsearch_insert_pos(key, array->buffer->data,
array_count_i(array),
array->element_size, cmp, idx_r);
}
|
