[Dovecot] [PATCH 3/5] make bsearch return the new index
Max Kellermann
max at duempel.org
Thu Mar 15 16:35:02 EET 2007
On 2007/03/15 12:30, Timo Sirainen <tss at iki.fi> wrote:
> That's ok, but I'm not sure about bsearch_insert_pos(). It's the way it
> is mostly because I wanted to keep bsearch() API. If it can't return
> void * then maybe it could be easier to just change the whole API to
> something like:
>
> /* If key is found, returns TRUE and sets pos_r to the position where
> the key
> was found. If key isn't found, returns FALSE and sets pos_r to the
> position
> where the key should be inserted. */
> bool bsearch_insert_pos(const void *key, const void *base, unsigned int
> nmemb,
> size_t size, int (*cmp)(const void *, const void *),
> unsigned int *pos_r);
>
> Because that's how it's usually used anyway, so it probably makes the
> code simpler also. Hmm. And maybe s/pos/idx/ :)
---
src/lib-index/mailbox-list-index-sync.c | 25 ++++++++++---------------
src/lib-storage/index/dbox/dbox-keywords.c | 13 ++++++++-----
src/lib-storage/index/dbox/dbox-uidlist.c | 20 ++++++++++----------
src/lib-storage/index/index-sort.c | 22 ++++++++++++----------
src/lib/bsearch-insert-pos.c | 23 +++++++++++++++--------
src/lib/bsearch-insert-pos.h | 5 +++--
src/plugins/fts-squat/squat-trie.c | 25 ++++++++++++-------------
7 files changed, 70 insertions(+), 63 deletions(-)
diff --git a/src/lib-index/mailbox-list-index-sync.c b/src/lib-index/mailbox-list-index-sync.c
index af089c6..aec85d8 100644
--- a/src/lib-index/mailbox-list-index-sync.c
+++ b/src/lib-index/mailbox-list-index-sync.c
@@ -66,7 +66,6 @@ struct mailbox_list_index_sync_ctx {
struct mailbox_list_sync_lookup_key {
uint32_t name_hash;
const char *name;
- bool *match;
};
static bool mailbox_list_index_need_compress(struct mailbox_list_index *index);
@@ -134,17 +133,13 @@ static int mailbox_list_sync_record_cmp(const void *_key, const void *_rec)
{
const struct mailbox_list_sync_lookup_key *key = _key;
const struct mailbox_list_sync_record *rec = _rec;
- int ret;
if (key->name_hash < rec->name_hash)
return -1;
if (key->name_hash > rec->name_hash)
return 1;
- ret = strcmp(key->name, rec->name);
- if (ret == 0)
- *key->match = TRUE;
- return ret;
+ return strcmp(key->name, rec->name);
}
static struct mailbox_list_sync_record *
@@ -152,24 +147,24 @@ mailbox_list_sync_dir_lookup(struct mailbox_list_sync_dir *dir,
const char *name, unsigned int *idx_r)
{
struct mailbox_list_sync_lookup_key key;
- const struct mailbox_list_sync_record *recs;
- struct mailbox_list_sync_record *rec;
+ struct mailbox_list_sync_record *recs;
unsigned int count;
bool match;
/* binary search the current hierarchy level name. the values are
sorted primarily by their hash value and secondarily by the actual
name */
- match = FALSE;
key.name = name;
key.name_hash = crc32_str(name);
- key.match = &match;
- recs = array_get(&dir->records, &count);
- rec = bsearch_insert_pos(&key, recs, count, sizeof(*rec),
- mailbox_list_sync_record_cmp);
- *idx_r = rec - recs;
- return match ? rec : NULL;
+ recs = array_get_modifiable(&dir->records, &count);
+ match = bsearch_insert_pos(&key, recs, count, sizeof(*recs),
+ mailbox_list_sync_record_cmp,
+ idx_r);
+ if (!match)
+ return NULL;
+
+ return &recs[*idx_r];
}
static struct mailbox_list_sync_record *
diff --git a/src/lib-storage/index/dbox/dbox-keywords.c b/src/lib-storage/index/dbox/dbox-keywords.c
index db44890..4e84958 100644
--- a/src/lib-storage/index/dbox/dbox-keywords.c
+++ b/src/lib-storage/index/dbox/dbox-keywords.c
@@ -23,9 +23,9 @@ static int dbox_keyword_map_compare(const void *p1, const void *p2)
int dbox_file_read_keywords(struct dbox_mailbox *mbox, struct dbox_file *file)
{
- struct keyword_map *map, *pos, kw;
+ struct keyword_map *map, kw;
const char *line;
- unsigned int idx, count;
+ unsigned int idx, count, insert_idx;
uoff_t last_offset;
if (array_is_created(&file->idx_file_keywords)) {
@@ -58,10 +58,13 @@ int dbox_file_read_keywords(struct dbox_mailbox *mbox, struct dbox_file *file)
/* look up the position where to insert it */
map = array_get_modifiable(&file->idx_file_keywords, &count);
- pos = idx == 0 ? map :
+ if (idx == 0)
+ insert_idx = 0;
+ else
bsearch_insert_pos(&kw, map, count, sizeof(*map),
- dbox_keyword_map_compare);
- array_insert(&file->idx_file_keywords, pos - map, &kw, 1);
+ dbox_keyword_map_compare,
+ &insert_idx);
+ array_insert(&file->idx_file_keywords, insert_idx, &kw, 1);
array_append(&file->file_idx_keywords, &kw.index_idx, 1);
if (++idx == file->keyword_count)
diff --git a/src/lib-storage/index/dbox/dbox-uidlist.c b/src/lib-storage/index/dbox/dbox-uidlist.c
index e48ba55..170e368 100644
--- a/src/lib-storage/index/dbox/dbox-uidlist.c
+++ b/src/lib-storage/index/dbox/dbox-uidlist.c
@@ -152,7 +152,7 @@ static void dbox_uidlist_update_last_uid(struct dbox_uidlist *uidlist,
static bool dbox_uidlist_add_entry(struct dbox_uidlist *uidlist,
const struct dbox_uidlist_entry *src_entry)
{
- struct dbox_uidlist_entry *dest_entry, **entries, **pos;
+ struct dbox_uidlist_entry *dest_entry, **entries;
const struct seq_range *range;
unsigned int i, idx, count;
@@ -163,10 +163,10 @@ static bool dbox_uidlist_add_entry(struct dbox_uidlist *uidlist,
/* append new file sequence */
idx = count;
} else {
- pos = bsearch_insert_pos(&src_entry->file_seq, entries, count,
- sizeof(*entries),
- dbox_uidlist_entry_cmp);
- idx = pos - entries;
+ bsearch_insert_pos(&src_entry->file_seq, entries, count,
+ sizeof(*entries),
+ dbox_uidlist_entry_cmp,
+ &idx);
}
if (idx == count || entries[idx]->file_seq != src_entry->file_seq) {
@@ -1318,7 +1318,7 @@ void dbox_uidlist_sync_set_modified(struct dbox_uidlist_sync_ctx *ctx)
void dbox_uidlist_sync_append(struct dbox_uidlist_sync_ctx *ctx,
const struct dbox_uidlist_entry *entry)
{
- struct dbox_uidlist_entry *const *entries, **pos;
+ struct dbox_uidlist_entry *const *entries;
struct dbox_uidlist_entry *new_entry;
unsigned int count;
@@ -1344,10 +1344,10 @@ void dbox_uidlist_sync_append(struct dbox_uidlist_sync_ctx *ctx,
else {
unsigned int idx;
- pos = bsearch_insert_pos(&new_entry->file_seq, entries,
- count, sizeof(*entries),
- dbox_uidlist_entry_cmp);
- idx = pos - entries;
+ bsearch_insert_pos(&new_entry->file_seq, entries,
+ count, sizeof(*entries),
+ dbox_uidlist_entry_cmp,
+ &idx);
i_assert(idx < count || idx == 0 ||
new_entry->file_seq > entries[idx-1]->file_seq);
diff --git a/src/lib-storage/index/index-sort.c b/src/lib-storage/index/index-sort.c
index 0fd00d0..36eb2b3 100644
--- a/src/lib-storage/index/index-sort.c
+++ b/src/lib-storage/index/index-sort.c
@@ -554,8 +554,8 @@ static void index_sort_headers(struct mail_search_sort_program *program,
uint32_t last_seq)
{
struct mail_sort_node *nodes, node;
- const struct mail_sort_node *cnodes, *pos;
- unsigned int count;
+ const struct mail_sort_node *cnodes;
+ unsigned int count, idx;
/* we wish to avoid reading the actual headers as much as possible.
first sort the nodes which already have sort_ids, then start
@@ -578,9 +578,10 @@ static void index_sort_headers(struct mail_search_sort_program *program,
program->sort_program[0], node.seq);
cnodes = array_get_modifiable(&program->nodes, &count);
- pos = bsearch_insert_pos(&node, cnodes, count, sizeof(*cnodes),
- sort_node_cmp_no_sort_id);
- array_insert(&program->nodes, pos - cnodes, &node, 1);
+ bsearch_insert_pos(&node, cnodes, count, sizeof(*cnodes),
+ sort_node_cmp_no_sort_id,
+ &idx);
+ array_insert(&program->nodes, idx, &node, 1);
}
index_sort_add_ids(program, static_node_cmp_context.mail);
@@ -634,17 +635,18 @@ static int index_sort_build(struct mail_search_sort_program *program,
static void index_sort_add_node(struct mail_search_sort_program *program,
const struct mail_sort_node *node)
{
- const struct mail_sort_node *nodes, *pos;
- unsigned int count;
+ const struct mail_sort_node *nodes;
+ unsigned int count, idx;
memset(&static_node_cmp_context, 0, sizeof(static_node_cmp_context));
static_node_cmp_context.program = program;
static_node_cmp_context.mail = program->temp_mail;
nodes = array_get(&program->nodes, &count);
- pos = bsearch_insert_pos(node, nodes, count,
- sizeof(*node), sort_node_cmp);
- array_insert(&program->nodes, pos - nodes, node, 1);
+ bsearch_insert_pos(node, nodes, count,
+ sizeof(*node), sort_node_cmp,
+ &idx);
+ array_insert(&program->nodes, idx, node, 1);
program->last_sorted_seq = node->seq;
program->prev_seq = node->seq;
diff --git a/src/lib/bsearch-insert-pos.c b/src/lib/bsearch-insert-pos.c
index 06441d7..7e5f8ae 100644
--- a/src/lib/bsearch-insert-pos.c
+++ b/src/lib/bsearch-insert-pos.c
@@ -3,8 +3,9 @@
#include "lib.h"
#include "bsearch-insert-pos.h"
-void *bsearch_insert_pos(const void *key, const void *base, unsigned int nmemb,
- size_t size, int (*cmp)(const void *, const void *))
+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;
@@ -21,13 +22,19 @@ void *bsearch_insert_pos(const void *key, const void *base, unsigned int nmemb,
left_idx = idx+1;
else if (ret < 0)
right_idx = idx;
- else
- return (void *)p;
+ else {
+ *idx_r = idx;
+ return TRUE;
+ }
}
- p = CONST_PTR_OFFSET(base, idx * size);
- if (idx < nmemb && cmp(key, p) > 0)
- p = CONST_PTR_OFFSET(p, size);
- return (void *)p;
+ if (idx < nmemb) {
+ p = CONST_PTR_OFFSET(base, idx * size);
+ if (cmp(key, p) > 0)
+ ++idx;
+ }
+
+ *idx_r = idx;
+ return FALSE;
}
diff --git a/src/lib/bsearch-insert-pos.h b/src/lib/bsearch-insert-pos.h
index a9c1339..e4232a7 100644
--- a/src/lib/bsearch-insert-pos.h
+++ b/src/lib/bsearch-insert-pos.h
@@ -3,7 +3,8 @@
/* If key is found, returns the pointer to it. If not, returns a pointer to
where it should be inserted. */
-void *bsearch_insert_pos(const void *key, const void *base, unsigned int nmemb,
- size_t size, int (*cmp)(const void *, const void *));
+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);
#endif
diff --git a/src/plugins/fts-squat/squat-trie.c b/src/plugins/fts-squat/squat-trie.c
index 92051f1..cf90155 100644
--- a/src/plugins/fts-squat/squat-trie.c
+++ b/src/plugins/fts-squat/squat-trie.c
@@ -1030,7 +1030,7 @@ trie_insert_node(struct squat_trie_build_context *ctx,
struct trie_node *node = *parent;
struct trie_node **children;
uint32_t char_idx;
- bool modified = FALSE;
+ bool match, modified = FALSE;
int ret;
if (*data < MAX_8BIT_CHAR_COUNT) {
@@ -1045,14 +1045,13 @@ trie_insert_node(struct squat_trie_build_context *ctx,
char_idx = *data;
} else {
uint8_t *chars = NODE_CHARS8(node);
- uint8_t *pos;
count = node->chars_8bit_count;
- pos = bsearch_insert_pos(data, chars, count,
- sizeof(chars[0]),
- chr_8bit_cmp);
- char_idx = pos - chars;
- if (char_idx == count || *pos != *data) {
+ match = bsearch_insert_pos(data, chars, count,
+ sizeof(chars[0]),
+ chr_8bit_cmp,
+ &char_idx);
+ if (!match) {
node = node_realloc(node, char_idx,
*data, level);
*parent = node;
@@ -1071,7 +1070,7 @@ trie_insert_node(struct squat_trie_build_context *ctx,
modified = TRUE;
} else {
unsigned int idx_size;
- uint16_t *chars, *pos;
+ uint16_t *chars;
idx_size = level < BLOCK_SIZE ?
sizeof(struct trie_node *) : sizeof(uint32_t);
@@ -1080,11 +1079,11 @@ trie_insert_node(struct squat_trie_build_context *ctx,
chars = PTR_OFFSET(node, offset);
count = node->chars_16bit_count;
- pos = bsearch_insert_pos(data, chars, count,
- sizeof(chars[0]),
- chr_16bit_cmp);
- char_idx = pos - chars;
- if (char_idx == count || *pos != *data) {
+ match = bsearch_insert_pos(data, chars, count,
+ sizeof(chars[0]),
+ chr_16bit_cmp,
+ &char_idx);
+ if (!match) {
node = node_realloc(node, char_idx,
*data, level);
*parent = node;
More information about the dovecot
mailing list