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