Mercurial > dovecot > core-2.2

changeset 3756:5fcf8e16ba8c HEAD

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Use binary search for finding entries
author Timo Sirainen <tss@iki.fi>
date Wed, 21 Dec 2005 19:25:35 +0200
parents 1c830ec05cb5
children 23c401a76dc9
files src/lib-storage/index/dbox/dbox-uidlist.c
diffstat 1 files changed, 22 insertions(+), 18 deletions(-) [+]
line wrap: on
line diff
--- a/src/lib-storage/index/dbox/dbox-uidlist.c	Wed Dec 21 19:20:08 2005 +0200
+++ b/src/lib-storage/index/dbox/dbox-uidlist.c	Wed Dec 21 19:25:35 2005 +0200
@@ -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 *