Mercurial > dovecot > core-2.2

annotate src/lib/bsearch-insert-pos.c @ 22664:fea53c2725c0

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
director: Fix director_max_parallel_moves/kicks type Should be uint, not time.
author Timo Sirainen <timo.sirainen@dovecot.fi>
date Thu, 09 Nov 2017 12:24:16 +0200
parents 2e2563132d5f
children cb108f786fb4
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
21390
2e2563132d5f Updated copyright notices to include the year 2017.
Stephan Bosch <stephan.bosch@dovecot.fi>
parents: 19552
diff changeset
1 /* Copyright (c) 2005-2017 Dovecot authors, see the included COPYING file */
3757
23c401a76dc9 Added bsearch_insert_pos(). Similar to bsearch(), but if value isn't found,
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
2
23c401a76dc9 Added bsearch_insert_pos(). Similar to bsearch(), but if value isn't found,
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
3 #include "lib.h"
9608
5ab09480d6b4 Added type safe array_bsearch_insert_pos().
Timo Sirainen <tss@iki.fi>
parents: 8590
diff changeset
4 #include "array.h"
3757
23c401a76dc9 Added bsearch_insert_pos(). Similar to bsearch(), but if value isn't found,
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
5 #include "bsearch-insert-pos.h"
23c401a76dc9 Added bsearch_insert_pos(). Similar to bsearch(), but if value isn't found,
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
6
14921
d3db2ba15d00 Removed CONTEXT_TYPE_SAFETY macro and reimplemented its functionality better.
Timo Sirainen <tss@iki.fi>
parents: 14133
diff changeset
7 #undef bsearch_insert_pos
5336
109ca861405f bsearch_insert_pos() API changed. Patch by Max Kellermann
Timo Sirainen <tss@iki.fi>
parents: 3757
diff changeset
8 bool bsearch_insert_pos(const void *key, const void *base, unsigned int nmemb,
109ca861405f bsearch_insert_pos() API changed. Patch by Max Kellermann
Timo Sirainen <tss@iki.fi>
parents: 3757
diff changeset
9 size_t size, int (*cmp)(const void *, const void *),
109ca861405f bsearch_insert_pos() API changed. Patch by Max Kellermann
Timo Sirainen <tss@iki.fi>
parents: 3757
diff changeset
10 unsigned int *idx_r)
3757
23c401a76dc9 Added bsearch_insert_pos(). Similar to bsearch(), but if value isn't found,
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
11 {
23c401a76dc9 Added bsearch_insert_pos(). Similar to bsearch(), but if value isn't found,
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
12 const void *p;
23c401a76dc9 Added bsearch_insert_pos(). Similar to bsearch(), but if value isn't found,
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
13 unsigned int idx, left_idx, right_idx;
23c401a76dc9 Added bsearch_insert_pos(). Similar to bsearch(), but if value isn't found,
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
14 int ret;
23c401a76dc9 Added bsearch_insert_pos(). Similar to bsearch(), but if value isn't found,
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
15
16361
38ca85ccd5af Added asserts to binary searches to make sure we don't go to infinite loop.
Timo Sirainen <tss@iki.fi>
parents: 15715
diff changeset
16 i_assert(nmemb < INT_MAX);
38ca85ccd5af Added asserts to binary searches to make sure we don't go to infinite loop.
Timo Sirainen <tss@iki.fi>
parents: 15715
diff changeset
17
3757
23c401a76dc9 Added bsearch_insert_pos(). Similar to bsearch(), but if value isn't found,
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
18 idx = 0; left_idx = 0; right_idx = nmemb;
23c401a76dc9 Added bsearch_insert_pos(). Similar to bsearch(), but if value isn't found,
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
19 while (left_idx < right_idx) {
23c401a76dc9 Added bsearch_insert_pos(). Similar to bsearch(), but if value isn't found,
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
20 idx = (left_idx + right_idx) / 2;
23c401a76dc9 Added bsearch_insert_pos(). Similar to bsearch(), but if value isn't found,
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
21
23c401a76dc9 Added bsearch_insert_pos(). Similar to bsearch(), but if value isn't found,
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
22 p = CONST_PTR_OFFSET(base, idx * size);
23c401a76dc9 Added bsearch_insert_pos(). Similar to bsearch(), but if value isn't found,
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
23 ret = cmp(key, p);
23c401a76dc9 Added bsearch_insert_pos(). Similar to bsearch(), but if value isn't found,
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
24 if (ret > 0)
23c401a76dc9 Added bsearch_insert_pos(). Similar to bsearch(), but if value isn't found,
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
25 left_idx = idx+1;
23c401a76dc9 Added bsearch_insert_pos(). Similar to bsearch(), but if value isn't found,
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
26 else if (ret < 0)
23c401a76dc9 Added bsearch_insert_pos(). Similar to bsearch(), but if value isn't found,
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
27 right_idx = idx;
5336
109ca861405f bsearch_insert_pos() API changed. Patch by Max Kellermann
Timo Sirainen <tss@iki.fi>
parents: 3757
diff changeset
28 else {
109ca861405f bsearch_insert_pos() API changed. Patch by Max Kellermann
Timo Sirainen <tss@iki.fi>
parents: 3757
diff changeset
29 *idx_r = idx;
109ca861405f bsearch_insert_pos() API changed. Patch by Max Kellermann
Timo Sirainen <tss@iki.fi>
parents: 3757
diff changeset
30 return TRUE;
109ca861405f bsearch_insert_pos() API changed. Patch by Max Kellermann
Timo Sirainen <tss@iki.fi>
parents: 3757
diff changeset
31 }
3757
23c401a76dc9 Added bsearch_insert_pos(). Similar to bsearch(), but if value isn't found,
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
32 }
23c401a76dc9 Added bsearch_insert_pos(). Similar to bsearch(), but if value isn't found,
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
33
5337
40ec903ae306 Optimization. Patch by Max Kellermann
Timo Sirainen <tss@iki.fi>
parents: 5336
diff changeset
34 if (left_idx > idx)
40ec903ae306 Optimization. Patch by Max Kellermann
Timo Sirainen <tss@iki.fi>
parents: 5336
diff changeset
35 idx++;
5336
109ca861405f bsearch_insert_pos() API changed. Patch by Max Kellermann
Timo Sirainen <tss@iki.fi>
parents: 3757
diff changeset
36
109ca861405f bsearch_insert_pos() API changed. Patch by Max Kellermann
Timo Sirainen <tss@iki.fi>
parents: 3757
diff changeset
37 *idx_r = idx;
109ca861405f bsearch_insert_pos() API changed. Patch by Max Kellermann
Timo Sirainen <tss@iki.fi>
parents: 3757
diff changeset
38 return FALSE;
3757
23c401a76dc9 Added bsearch_insert_pos(). Similar to bsearch(), but if value isn't found,
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
39 }
23c401a76dc9 Added bsearch_insert_pos(). Similar to bsearch(), but if value isn't found,
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
40
9608
5ab09480d6b4 Added type safe array_bsearch_insert_pos().
Timo Sirainen <tss@iki.fi>
parents: 8590
diff changeset
41 bool array_bsearch_insert_pos_i(const struct array *array, const void *key,
5ab09480d6b4 Added type safe array_bsearch_insert_pos().
Timo Sirainen <tss@iki.fi>
parents: 8590
diff changeset
42 int (*cmp)(const void *, const void *),
5ab09480d6b4 Added type safe array_bsearch_insert_pos().
Timo Sirainen <tss@iki.fi>
parents: 8590
diff changeset
43 unsigned int *idx_r)
5ab09480d6b4 Added type safe array_bsearch_insert_pos().
Timo Sirainen <tss@iki.fi>
parents: 8590
diff changeset
44 {
5ab09480d6b4 Added type safe array_bsearch_insert_pos().
Timo Sirainen <tss@iki.fi>
parents: 8590
diff changeset
45 return bsearch_insert_pos(key, array->buffer->data,
5ab09480d6b4 Added type safe array_bsearch_insert_pos().
Timo Sirainen <tss@iki.fi>
parents: 8590
diff changeset
46 array_count_i(array),
5ab09480d6b4 Added type safe array_bsearch_insert_pos().
Timo Sirainen <tss@iki.fi>
parents: 8590
diff changeset
47 array->element_size, cmp, idx_r);
5ab09480d6b4 Added type safe array_bsearch_insert_pos().
Timo Sirainen <tss@iki.fi>
parents: 8590
diff changeset
48 }