[dovecot-cvs]
dovecot/src/lib-storage/index/dbox dbox-uidlist.c, 1.2, 1.3
cras at dovecot.org
cras at dovecot.org
Wed Dec 21 19:25:37 EET 2005
- Previous message: [dovecot-cvs] dovecot/src/lib-storage/index/dbox
dbox-sync-expunge.c, 1.2, 1.3 dbox-uidlist.c, 1.1, 1.2
- Next message: [dovecot-cvs] dovecot/src/lib Makefile.am, 1.56,
1.57 bsearch-insert-pos.c, NONE, 1.1 bsearch-insert-pos.h, NONE, 1.1
- Messages sorted by:
[ date ]
[ thread ]
[ subject ]
[ author ]
Update of /var/lib/cvs/dovecot/src/lib-storage/index/dbox
In directory talvi:/tmp/cvs-serv29033
Modified Files:
dbox-uidlist.c
Log Message:
Use binary search for finding entries
Index: dbox-uidlist.c
===================================================================
RCS file: /var/lib/cvs/dovecot/src/lib-storage/index/dbox/dbox-uidlist.c,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -d -r1.2 -r1.3
--- dbox-uidlist.c 21 Dec 2005 17:20:08 -0000 1.2
+++ dbox-uidlist.c 21 Dec 2005 17:25:35 -0000 1.3
@@ -150,10 +150,18 @@
return TRUE;
}
+static int dbox_uidlist_entry_cmp(const void *key, const void *p)
+{
+ const unsigned int *file_seq = key;
+ const struct dbox_uidlist_entry **entry = p;
+
+ return (int)file_seq - (int)(*entry)->file_seq;
+}
+
static int dbox_uidlist_add_entry(struct dbox_uidlist *uidlist,
const struct dbox_uidlist_entry *src_entry)
{
- struct dbox_uidlist_entry *dest_entry, **entries;
+ struct dbox_uidlist_entry *dest_entry, **entries, **pos;
const struct seq_range *range;
unsigned int i, count;
@@ -169,14 +177,11 @@
uidlist->last_file_seq = src_entry->file_seq;
} else {
/* merge to existing entry. they're written in order, so we
- don't try to handle non-merging inserting. FIXME: we could
- use binary lookup for the entry */
+ don't try to handle non-merging inserting. */
entries = array_get_modifyable(&uidlist->entries, &count);
- for (i = 0; i < count; i++) {
- if (entries[i]->file_seq == src_entry->file_seq)
- break;
- }
- if (i == count) {
+ pos = bsearch(src_entry->file_seq, entries, count,
+ sizeof(*entries), dbox_uidlist_entry_cmp);
+ if (pos == NULL) {
mail_storage_set_critical(
STORAGE(uidlist->mbox->storage),
"%s: File sequences not ordered (%u < %u)",
@@ -187,7 +192,7 @@
/* now, do the merging. UIDs must be growing since only new
mails are appended */
- dest_entry = entries[i];
+ dest_entry = *pos;
if (src_entry->last_write > dest_entry->last_write)
dest_entry->last_write = src_entry->last_write;
if (src_entry->file_size > dest_entry->file_size)
@@ -428,18 +433,17 @@
dbox_uidlist_entry_lookup_int(struct dbox_uidlist *uidlist, uint32_t file_seq,
unsigned int *idx_r)
{
- struct dbox_uidlist_entry *const *entries;
+ struct dbox_uidlist_entry *const *entries, **entry;
unsigned int i, count;
- /* FIXME: binary lookup */
entries = array_get(&uidlist->entries, &count);
- for (i = 0; i < count; i++) {
- if (entries[i]->file_seq == file_seq) {
- *idx_r = i;
- return entries[i];
- }
- }
- return NULL;
+ entry = bsearch(file_seq, entries, count, sizeof(*entries),
+ dbox_uidlist_entry_cmp);
+ if (entry == NULL)
+ return NULL;
+
+ *idx_r = entry - entries;
+ return entry;
}
struct dbox_uidlist_entry *
- Previous message: [dovecot-cvs] dovecot/src/lib-storage/index/dbox
dbox-sync-expunge.c, 1.2, 1.3 dbox-uidlist.c, 1.1, 1.2
- Next message: [dovecot-cvs] dovecot/src/lib Makefile.am, 1.56,
1.57 bsearch-insert-pos.c, NONE, 1.1 bsearch-insert-pos.h, NONE, 1.1
- Messages sorted by:
[ date ]
[ thread ]
[ subject ]
[ author ]
More information about the dovecot-cvs
mailing list