Mercurial > dovecot > core-2.2

annotate src/lib/bsearch-insert-pos.h @ 23007:36e01285b5b8

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
lib: buffer - Improve header comment for buffer_insert() and buffer_delete().
author Stephan Bosch <stephan.bosch@dovecot.fi>
date Mon, 18 Mar 2019 00:52:37 +0100
parents 12015689471c
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
6410
e4eb71ae8e96 Changed .h ifdef/defines to use <NAME>_H format.
Timo Sirainen <tss@iki.fi>
parents: 6127
diff changeset
1 #ifndef BSEARCH_INSERT_POS_H
e4eb71ae8e96 Changed .h ifdef/defines to use <NAME>_H format.
Timo Sirainen <tss@iki.fi>
parents: 6127
diff changeset
2 #define BSEARCH_INSERT_POS_H
3757
23c401a76dc9 Added bsearch_insert_pos(). Similar to bsearch(), but if value isn't found,
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
3
17825
12015689471c lib: bsearch - make BINARY_NUMBER_SEARCH more widely usable
Phil Carmody <phil@dovecot.fi>
parents: 16361
diff changeset
4 /* Binary search template - getdata must be the name of a pure function
12015689471c lib: bsearch - make BINARY_NUMBER_SEARCH more widely usable
Phil Carmody <phil@dovecot.fi>
parents: 16361
diff changeset
5 or a function-like macro that takes the two obvious parameters. */
12015689471c lib: bsearch - make BINARY_NUMBER_SEARCH more widely usable
Phil Carmody <phil@dovecot.fi>
parents: 16361
diff changeset
6 #define BINARY_NUMERIC_SEARCH(getdata, data, count, value, idx_r) \
6127
32e229d89038 Added BINARY_NUMBER_SEARCH() macro.
Timo Sirainen <tss@iki.fi>
parents: 5336
diff changeset
7 unsigned int idx, left_idx, right_idx; \
32e229d89038 Added BINARY_NUMBER_SEARCH() macro.
Timo Sirainen <tss@iki.fi>
parents: 5336
diff changeset
8 \
16361
38ca85ccd5af Added asserts to binary searches to make sure we don't go to infinite loop.
Timo Sirainen <tss@iki.fi>
parents: 14921
diff changeset
9 i_assert((count) < INT_MAX); \
17825
12015689471c lib: bsearch - make BINARY_NUMBER_SEARCH more widely usable
Phil Carmody <phil@dovecot.fi>
parents: 16361
diff changeset
10 left_idx = 0; right_idx = (count); \
6127
32e229d89038 Added BINARY_NUMBER_SEARCH() macro.
Timo Sirainen <tss@iki.fi>
parents: 5336
diff changeset
11 while (left_idx < right_idx) { \
32e229d89038 Added BINARY_NUMBER_SEARCH() macro.
Timo Sirainen <tss@iki.fi>
parents: 5336
diff changeset
12 idx = (left_idx + right_idx) / 2; \
32e229d89038 Added BINARY_NUMBER_SEARCH() macro.
Timo Sirainen <tss@iki.fi>
parents: 5336
diff changeset
13 \
17825
12015689471c lib: bsearch - make BINARY_NUMBER_SEARCH more widely usable
Phil Carmody <phil@dovecot.fi>
parents: 16361
diff changeset
14 if (getdata(data, idx) < (value)) \
6127
32e229d89038 Added BINARY_NUMBER_SEARCH() macro.
Timo Sirainen <tss@iki.fi>
parents: 5336
diff changeset
15 left_idx = idx+1; \
17825
12015689471c lib: bsearch - make BINARY_NUMBER_SEARCH more widely usable
Phil Carmody <phil@dovecot.fi>
parents: 16361
diff changeset
16 else if (getdata(data, idx) > (value))\
6127
32e229d89038 Added BINARY_NUMBER_SEARCH() macro.
Timo Sirainen <tss@iki.fi>
parents: 5336
diff changeset
17 right_idx = idx; \
32e229d89038 Added BINARY_NUMBER_SEARCH() macro.
Timo Sirainen <tss@iki.fi>
parents: 5336
diff changeset
18 else { \
32e229d89038 Added BINARY_NUMBER_SEARCH() macro.
Timo Sirainen <tss@iki.fi>
parents: 5336
diff changeset
19 *(idx_r) = idx; \
32e229d89038 Added BINARY_NUMBER_SEARCH() macro.
Timo Sirainen <tss@iki.fi>
parents: 5336
diff changeset
20 return TRUE; \
32e229d89038 Added BINARY_NUMBER_SEARCH() macro.
Timo Sirainen <tss@iki.fi>
parents: 5336
diff changeset
21 } \
32e229d89038 Added BINARY_NUMBER_SEARCH() macro.
Timo Sirainen <tss@iki.fi>
parents: 5336
diff changeset
22 } \
32e229d89038 Added BINARY_NUMBER_SEARCH() macro.
Timo Sirainen <tss@iki.fi>
parents: 5336
diff changeset
23 return FALSE
32e229d89038 Added BINARY_NUMBER_SEARCH() macro.
Timo Sirainen <tss@iki.fi>
parents: 5336
diff changeset
24
17825
12015689471c lib: bsearch - make BINARY_NUMBER_SEARCH more widely usable
Phil Carmody <phil@dovecot.fi>
parents: 16361
diff changeset
25 #define BINARY_SEARCH_ARRAY_GET(array, index) ((array)[(index)])
12015689471c lib: bsearch - make BINARY_NUMBER_SEARCH more widely usable
Phil Carmody <phil@dovecot.fi>
parents: 16361
diff changeset
26 #define BINARY_NUMBER_SEARCH(data, count, value, idx_r) \
12015689471c lib: bsearch - make BINARY_NUMBER_SEARCH more widely usable
Phil Carmody <phil@dovecot.fi>
parents: 16361
diff changeset
27 BINARY_NUMERIC_SEARCH(BINARY_SEARCH_ARRAY_GET, data, count, value, idx_r);
12015689471c lib: bsearch - make BINARY_NUMBER_SEARCH more widely usable
Phil Carmody <phil@dovecot.fi>
parents: 16361
diff changeset
28
5336
109ca861405f bsearch_insert_pos() API changed. Patch by Max Kellermann
Timo Sirainen <tss@iki.fi>
parents: 3757
diff changeset
29 /* If key is found, returns TRUE and sets idx_r to the position where the key
109ca861405f bsearch_insert_pos() API changed. Patch by Max Kellermann
Timo Sirainen <tss@iki.fi>
parents: 3757
diff changeset
30 was found. If key isn't found, returns FALSE and sets idx_r to the position
109ca861405f bsearch_insert_pos() API changed. Patch by Max Kellermann
Timo Sirainen <tss@iki.fi>
parents: 3757
diff changeset
31 where the key should be inserted. */
14688
128c598d2870 Avoid using (void)s by adding ATTR_NOWARN_UNUSED_RESULT attributes and other ways.
Timo Sirainen <tss@iki.fi>
parents: 10450
diff changeset
32 bool ATTR_NOWARN_UNUSED_RESULT
128c598d2870 Avoid using (void)s by adding ATTR_NOWARN_UNUSED_RESULT attributes and other ways.
Timo Sirainen <tss@iki.fi>
parents: 10450
diff changeset
33 bsearch_insert_pos(const void *key, const void *base, unsigned int nmemb,
14921
d3db2ba15d00 Removed CONTEXT_TYPE_SAFETY macro and reimplemented its functionality better.
Timo Sirainen <tss@iki.fi>
parents: 14688
diff changeset
34 size_t size, int (*cmp)(const void *, const void *),
d3db2ba15d00 Removed CONTEXT_TYPE_SAFETY macro and reimplemented its functionality better.
Timo Sirainen <tss@iki.fi>
parents: 14688
diff changeset
35 unsigned int *idx_r);
d3db2ba15d00 Removed CONTEXT_TYPE_SAFETY macro and reimplemented its functionality better.
Timo Sirainen <tss@iki.fi>
parents: 14688
diff changeset
36 #define bsearch_insert_pos(key, base, nmemb, size, cmp, idx_r) \
d3db2ba15d00 Removed CONTEXT_TYPE_SAFETY macro and reimplemented its functionality better.
Timo Sirainen <tss@iki.fi>
parents: 14688
diff changeset
37 bsearch_insert_pos(key, base, nmemb, size + \
d3db2ba15d00 Removed CONTEXT_TYPE_SAFETY macro and reimplemented its functionality better.
Timo Sirainen <tss@iki.fi>
parents: 14688
diff changeset
38 CALLBACK_TYPECHECK(cmp, int (*)(typeof(const typeof(*key) *), \
d3db2ba15d00 Removed CONTEXT_TYPE_SAFETY macro and reimplemented its functionality better.
Timo Sirainen <tss@iki.fi>
parents: 14688
diff changeset
39 typeof(const typeof(*base) *))), \
d3db2ba15d00 Removed CONTEXT_TYPE_SAFETY macro and reimplemented its functionality better.
Timo Sirainen <tss@iki.fi>
parents: 14688
diff changeset
40 (int (*)(const void *, const void *))cmp, 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
41
14688
128c598d2870 Avoid using (void)s by adding ATTR_NOWARN_UNUSED_RESULT attributes and other ways.
Timo Sirainen <tss@iki.fi>
parents: 10450
diff changeset
42 bool ATTR_NOWARN_UNUSED_RESULT
128c598d2870 Avoid using (void)s by adding ATTR_NOWARN_UNUSED_RESULT attributes and other ways.
Timo Sirainen <tss@iki.fi>
parents: 10450
diff changeset
43 array_bsearch_insert_pos_i(const struct array *array, const void *key,
128c598d2870 Avoid using (void)s by adding ATTR_NOWARN_UNUSED_RESULT attributes and other ways.
Timo Sirainen <tss@iki.fi>
parents: 10450
diff changeset
44 int (*cmp)(const void *, const void *),
128c598d2870 Avoid using (void)s by adding ATTR_NOWARN_UNUSED_RESULT attributes and other ways.
Timo Sirainen <tss@iki.fi>
parents: 10450
diff changeset
45 unsigned int *idx_r);
9608
5ab09480d6b4 Added type safe array_bsearch_insert_pos().
Timo Sirainen <tss@iki.fi>
parents: 6410
diff changeset
46 #define array_bsearch_insert_pos(array, key, cmp, idx_r) \
14921
d3db2ba15d00 Removed CONTEXT_TYPE_SAFETY macro and reimplemented its functionality better.
Timo Sirainen <tss@iki.fi>
parents: 14688
diff changeset
47 array_bsearch_insert_pos_i(&(array)->arr + \
d3db2ba15d00 Removed CONTEXT_TYPE_SAFETY macro and reimplemented its functionality better.
Timo Sirainen <tss@iki.fi>
parents: 14688
diff changeset
48 CALLBACK_TYPECHECK(cmp, int (*)(typeof(const typeof(*key) *), \
d3db2ba15d00 Removed CONTEXT_TYPE_SAFETY macro and reimplemented its functionality better.
Timo Sirainen <tss@iki.fi>
parents: 14688
diff changeset
49 typeof(*(array)->v))), \
d3db2ba15d00 Removed CONTEXT_TYPE_SAFETY macro and reimplemented its functionality better.
Timo Sirainen <tss@iki.fi>
parents: 14688
diff changeset
50 (const void *)key, (int (*)(const void *, const void *))cmp, idx_r)
9608
5ab09480d6b4 Added type safe array_bsearch_insert_pos().
Timo Sirainen <tss@iki.fi>
parents: 6410
diff changeset
51
5ab09480d6b4 Added type safe array_bsearch_insert_pos().
Timo Sirainen <tss@iki.fi>
parents: 6410
diff changeset
52 #endif