On 2007/03/15 12:30, Timo Sirainen 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;

--- src/plugins/acl/acl-plugin.c | 3 --- src/plugins/expire/expire-plugin.c | 3 --- src/plugins/mail-log/mail-log-plugin.c | 3 --- src/plugins/zlib/zlib-plugin.c | 3 --- 4 files changed, 0 insertions(+), 12 deletions(-) diff --git a/src/plugins/acl/acl-plugin.c b/src/plugins/acl/acl-plugin.c index 7316c3b..5054c0e 100644 --- a/src/plugins/acl/acl-plugin.c +++ b/src/plugins/acl/acl-plugin.c @@ -8,9 +8,6 @@ #include -/* defined by imap, pop3, lda */ -extern void (*hook_mail_storage_created)(struct mail_storage *storage); - void (*acl_next_hook_mail_storage_created)(struct mail_storage *storage); void (*acl_next_hook_mailbox_list_created)(struct mailbox_list *list); diff --git a/src/plugins/expire/expire-plugin.c b/src/plugins/expire/expire-plugin.c index db0f1ee..e88bcae 100644 --- a/src/plugins/expire/expire-plugin.c +++ b/src/plugins/expire/expire-plugin.c @@ -46,9 +46,6 @@ struct expire_transaction_context { unsigned int first_expunged:1; }; -/* defined by imap, pop3, lda */ -extern void (*hook_mail_storage_created)(struct mail_storage *storage); - const char *expire_plugin_version = PACKAGE_VERSION; static struct expire expire; diff --git a/src/plugins/mail-log/mail-log-plugin.c b/src/plugins/mail-log/mail-log-plugin.c index d1609a8..be87ae6 100644 --- a/src/plugins/mail-log/mail-log-plugin.c +++ b/src/plugins/mail-log/mail-log-plugin.c @@ -25,9 +25,6 @@ struct mail_log_mail { struct mail_vfuncs super; }; -/* defined by imap, pop3, lda */ -extern void (*hook_mail_storage_created)(struct mail_storage *storage); - const char *mail_log_plugin_version = PACKAGE_VERSION; static void (*mail_log_next_hook_mail_storage_created) diff --git a/src/plugins/zlib/zlib-plugin.c b/src/plugins/zlib/zlib-plugin.c index bf94be0..851055b 100644 --- a/src/plugins/zlib/zlib-plugin.c +++ b/src/plugins/zlib/zlib-plugin.c @@ -18,9 +18,6 @@ struct zlib_mail_storage { *((void **)array_idx_modifiable(&(obj)->module_contexts, \ zlib_storage_module_id)) -/* defined by imap, pop3, lda */ -extern void (*hook_mail_storage_created)(struct mail_storage *storage); - const char *zlib_plugin_version = PACKAGE_VERSION; static void (*zlib_next_hook_mail_storage_created)

Since the comparison function cmp() has already been called with the correct parameters in the loop, it is enough to check if the assignment "left_idx = idx+1" has been executed. The special case "nmemb==0" is also handled well by this trick. --- src/lib/bsearch-insert-pos.c | 7 ++----- 1 files changed, 2 insertions(+), 5 deletions(-) diff --git a/src/lib/bsearch-insert-pos.c b/src/lib/bsearch-insert-pos.c index 7e5f8ae..8e63cf2 100644 --- a/src/lib/bsearch-insert-pos.c +++ b/src/lib/bsearch-insert-pos.c @@ -28,11 +28,8 @@ bool bsearch_insert_pos(const void *key, const void *base, unsigned int nmemb, } } - if (idx < nmemb) { - p = CONST_PTR_OFFSET(base, idx * size); - if (cmp(key, p) > 0) - ++idx; - } + if (left_idx > idx) + ++idx; *idx_r = idx; return FALSE;