Mercurial > dovecot > original-hg > dovecot-1.2

annotate src/lib/bsearch-insert-pos.h @ 8590:b9faf4db2a9f HEAD

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Updated copyright notices to include year 2009.
author Timo Sirainen <tss@iki.fi>
date Tue, 06 Jan 2009 09:25:38 -0500
parents e4eb71ae8e96
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
6127
32e229d89038 Added BINARY_NUMBER_SEARCH() macro.
Timo Sirainen <tss@iki.fi>
parents: 5336
diff changeset
4 /* Binary search template */
32e229d89038 Added BINARY_NUMBER_SEARCH() macro.
Timo Sirainen <tss@iki.fi>
parents: 5336
diff changeset
5 #define BINARY_NUMBER_SEARCH(data, count, value, idx_r) \
32e229d89038 Added BINARY_NUMBER_SEARCH() macro.
Timo Sirainen <tss@iki.fi>
parents: 5336
diff changeset
6 unsigned int idx, left_idx, right_idx; \
32e229d89038 Added BINARY_NUMBER_SEARCH() macro.
Timo Sirainen <tss@iki.fi>
parents: 5336
diff changeset
7 \
32e229d89038 Added BINARY_NUMBER_SEARCH() macro.
Timo Sirainen <tss@iki.fi>
parents: 5336
diff changeset
8 idx = 0; left_idx = 0; right_idx = (count); \
32e229d89038 Added BINARY_NUMBER_SEARCH() macro.
Timo Sirainen <tss@iki.fi>
parents: 5336
diff changeset
9 while (left_idx < right_idx) { \
32e229d89038 Added BINARY_NUMBER_SEARCH() macro.
Timo Sirainen <tss@iki.fi>
parents: 5336
diff changeset
10 idx = (left_idx + right_idx) / 2; \
32e229d89038 Added BINARY_NUMBER_SEARCH() macro.
Timo Sirainen <tss@iki.fi>
parents: 5336
diff changeset
11 \
32e229d89038 Added BINARY_NUMBER_SEARCH() macro.
Timo Sirainen <tss@iki.fi>
parents: 5336
diff changeset
12 if ((data)[idx] < (value)) \
32e229d89038 Added BINARY_NUMBER_SEARCH() macro.
Timo Sirainen <tss@iki.fi>
parents: 5336
diff changeset
13 left_idx = idx+1; \
32e229d89038 Added BINARY_NUMBER_SEARCH() macro.
Timo Sirainen <tss@iki.fi>
parents: 5336
diff changeset
14 else if ((data)[idx] > (value)) \
32e229d89038 Added BINARY_NUMBER_SEARCH() macro.
Timo Sirainen <tss@iki.fi>
parents: 5336
diff changeset
15 right_idx = idx; \
32e229d89038 Added BINARY_NUMBER_SEARCH() macro.
Timo Sirainen <tss@iki.fi>
parents: 5336
diff changeset
16 else { \
32e229d89038 Added BINARY_NUMBER_SEARCH() macro.
Timo Sirainen <tss@iki.fi>
parents: 5336
diff changeset
17 *(idx_r) = idx; \
32e229d89038 Added BINARY_NUMBER_SEARCH() macro.
Timo Sirainen <tss@iki.fi>
parents: 5336
diff changeset
18 return TRUE; \
32e229d89038 Added BINARY_NUMBER_SEARCH() macro.
Timo Sirainen <tss@iki.fi>
parents: 5336
diff changeset
19 } \
32e229d89038 Added BINARY_NUMBER_SEARCH() macro.
Timo Sirainen <tss@iki.fi>
parents: 5336
diff changeset
20 } \
32e229d89038 Added BINARY_NUMBER_SEARCH() macro.
Timo Sirainen <tss@iki.fi>
parents: 5336
diff changeset
21 return FALSE
32e229d89038 Added BINARY_NUMBER_SEARCH() macro.
Timo Sirainen <tss@iki.fi>
parents: 5336
diff changeset
22
5336
109ca861405f bsearch_insert_pos() API changed. Patch by Max Kellermann
Timo Sirainen <tss@iki.fi>
parents: 3757
diff changeset
23 /* 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
24 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
25 where the key should be inserted. */
109ca861405f bsearch_insert_pos() API changed. Patch by Max Kellermann
Timo Sirainen <tss@iki.fi>
parents: 3757
diff changeset
26 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
27 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
28 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
29
23c401a76dc9 Added bsearch_insert_pos(). Similar to bsearch(), but if value isn't found,
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
30 #endif