dovecot-1.2: Optimized searching with virtual mailboxes.
dovecot at dovecot.org
dovecot at dovecot.org
Sun Nov 23 02:40:16 EET 2008
details: http://hg.dovecot.org/dovecot-1.2/rev/b12705704329
changeset: 8483:b12705704329
user: Timo Sirainen <tss at iki.fi>
date: Sun Nov 23 02:40:09 2008 +0200
description:
Optimized searching with virtual mailboxes.
Instead of going through the messages in the virtual mailbox order, go them
through one mailbox at a time and in ascending message order within that
mailbox.
diffstat:
4 files changed, 230 insertions(+), 4 deletions(-)
src/plugins/virtual/Makefile.am | 1
src/plugins/virtual/virtual-search.c | 208 +++++++++++++++++++++++++++++++++
src/plugins/virtual/virtual-storage.c | 10 -
src/plugins/virtual/virtual-storage.h | 15 ++
diffs (289 lines):
diff -r 1ff129ed866a -r b12705704329 src/plugins/virtual/Makefile.am
--- a/src/plugins/virtual/Makefile.am Sun Nov 23 02:37:23 2008 +0200
+++ b/src/plugins/virtual/Makefile.am Sun Nov 23 02:40:09 2008 +0200
@@ -15,6 +15,7 @@ lib20_virtual_plugin_la_SOURCES = \
virtual-config.c \
virtual-mail.c \
virtual-plugin.c \
+ virtual-search.c \
virtual-storage.c \
virtual-sync.c \
virtual-transaction.c
diff -r 1ff129ed866a -r b12705704329 src/plugins/virtual/virtual-search.c
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/plugins/virtual/virtual-search.c Sun Nov 23 02:40:09 2008 +0200
@@ -0,0 +1,208 @@
+/* Copyright (c) 2008 Dovecot authors, see the included COPYING file */
+
+#include "lib.h"
+#include "array.h"
+#include "mail-search.h"
+#include "index-storage.h"
+#include "virtual-storage.h"
+
+#include <stdlib.h>
+
+enum virtual_search_state {
+ VIRTUAL_SEARCH_STATE_FAILED = -1,
+ VIRTUAL_SEARCH_STATE_BUILD,
+ VIRTUAL_SEARCH_STATE_RETURN,
+ VIRTUAL_SEARCH_STATE_SORT,
+ VIRTUAL_SEARCH_STATE_SORT_DONE
+};
+
+struct virtual_search_record {
+ uint32_t mailbox_id;
+ uint32_t real_uid;
+ uint32_t virtual_seq;
+};
+
+struct virtual_search_context {
+ union mail_search_module_context module_ctx;
+
+ ARRAY_TYPE(seq_range) result;
+ struct seq_range_iter result_iter;
+ ARRAY_DEFINE(records, struct virtual_search_record);
+
+ enum virtual_search_state search_state;
+ unsigned int next_result_n;
+ unsigned int next_record_idx;
+};
+
+static int virtual_search_record_cmp(const void *p1, const void *p2)
+{
+ const struct virtual_search_record *r1 = p1, *r2 = p2;
+
+ if (r1->mailbox_id < r2->mailbox_id)
+ return -1;
+ if (r1->mailbox_id > r2->mailbox_id)
+ return 1;
+
+ if (r1->real_uid < r2->real_uid)
+ return -1;
+ if (r1->real_uid > r2->real_uid)
+ return 1;
+ return 0;
+}
+
+static int mail_search_get_result(struct mail_search_context *ctx)
+{
+ const struct mail_search_arg *arg;
+ int ret = 1;
+
+ for (arg = ctx->args->args; arg != NULL; arg = arg->next) {
+ if (arg->result < 0)
+ return -1;
+ if (arg->result == 0)
+ ret = 0;
+ }
+ return ret;
+}
+
+static int virtual_search_get_records(struct mail_search_context *ctx,
+ struct virtual_search_context *vctx)
+{
+ struct virtual_mailbox *mbox =
+ (struct virtual_mailbox *)ctx->transaction->box;
+ const struct virtual_mail_index_record *vrec;
+ struct virtual_search_record srec, *srecs;
+ unsigned int count;
+ const void *data;
+ bool expunged;
+ int ret, result;
+
+ memset(&srec, 0, sizeof(srec));
+ while ((ret = index_storage_search_next_update_seq(ctx)) > 0) {
+ result = mail_search_get_result(ctx);
+ i_assert(result != 0);
+ if (result > 0) {
+ /* full match, no need to check this any further */
+ seq_range_array_add(&vctx->result, 0, ctx->seq);
+ } else {
+ /* possible match, save and check later */
+ mail_index_lookup_ext(mbox->ibox.view, ctx->seq,
+ mbox->virtual_ext_id,
+ &data, &expunged);
+ vrec = data;
+
+ srec.mailbox_id = vrec->mailbox_id;
+ srec.real_uid = vrec->real_uid;
+ srec.virtual_seq = ctx->seq;
+ array_append(&vctx->records, &srec, 1);
+ }
+ mail_search_args_reset(ctx->args->args, FALSE);
+ }
+ srecs = array_get_modifiable(&vctx->records, &count);
+ qsort(srecs, count, sizeof(*srecs), virtual_search_record_cmp);
+ return ret;
+}
+
+struct mail_search_context *
+virtual_search_init(struct mailbox_transaction_context *t,
+ struct mail_search_args *args,
+ const enum mail_sort_type *sort_program)
+{
+ struct mail_search_context *ctx;
+ struct virtual_search_context *vctx;
+
+ ctx = index_storage_search_init(t, args, sort_program);
+
+ vctx = i_new(struct virtual_search_context, 1);
+ vctx->search_state = VIRTUAL_SEARCH_STATE_BUILD;
+ i_array_init(&vctx->result, 64);
+ i_array_init(&vctx->records, 64);
+ MODULE_CONTEXT_SET(ctx, virtual_storage_module, vctx);
+
+ if (virtual_search_get_records(ctx, vctx) < 0)
+ vctx->search_state = VIRTUAL_SEARCH_STATE_FAILED;
+
+ seq_range_array_iter_init(&vctx->result_iter, &vctx->result);
+ return ctx;
+}
+
+int virtual_search_deinit(struct mail_search_context *ctx)
+{
+ struct virtual_search_context *vctx = VIRTUAL_CONTEXT(ctx);
+
+ array_free(&vctx->result);
+ array_free(&vctx->records);
+ i_free(vctx);
+ return index_storage_search_deinit(ctx);
+}
+
+int virtual_search_next_nonblock(struct mail_search_context *ctx,
+ struct mail *mail, bool *tryagain_r)
+{
+ struct virtual_search_context *vctx = VIRTUAL_CONTEXT(ctx);
+ uint32_t seq;
+ int ret;
+
+ switch (vctx->search_state) {
+ case VIRTUAL_SEARCH_STATE_FAILED:
+ return -1;
+ case VIRTUAL_SEARCH_STATE_BUILD:
+ if (ctx->sort_program == NULL)
+ vctx->search_state = VIRTUAL_SEARCH_STATE_SORT;
+ else
+ vctx->search_state = VIRTUAL_SEARCH_STATE_RETURN;
+ return virtual_search_next_nonblock(ctx, mail, tryagain_r);
+ case VIRTUAL_SEARCH_STATE_RETURN:
+ return index_storage_search_next_nonblock(ctx, mail, tryagain_r);
+ case VIRTUAL_SEARCH_STATE_SORT:
+ /* the messages won't be returned sorted, so we'll have to
+ do it ourself */
+ while ((ret = index_storage_search_next_nonblock(ctx, mail,
+ tryagain_r)) > 0)
+ seq_range_array_add(&vctx->result, 0, mail->seq);
+ if (ret < 0 || *tryagain_r)
+ return ret;
+
+ vctx->next_result_n = 0;
+ vctx->search_state = VIRTUAL_SEARCH_STATE_SORT_DONE;
+ /* fall through */
+ case VIRTUAL_SEARCH_STATE_SORT_DONE:
+ *tryagain_r = FALSE;
+ if (!seq_range_array_iter_nth(&vctx->result_iter,
+ vctx->next_result_n, &seq))
+ return 0;
+ vctx->next_result_n++;
+ mail_set_seq(mail, seq);
+ return 1;
+ }
+ i_unreached();
+}
+
+static void search_args_set_full_match(struct mail_search_arg *args)
+{
+ for (; args != NULL; args = args->next)
+ args->result = 1;
+}
+
+bool virtual_search_next_update_seq(struct mail_search_context *ctx)
+{
+ struct virtual_search_context *vctx = VIRTUAL_CONTEXT(ctx);
+ const struct virtual_search_record *recs;
+ unsigned int count;
+
+ recs = array_get(&vctx->records, &count);
+ if (vctx->next_record_idx < count) {
+ ctx->seq = recs[vctx->next_record_idx++].virtual_seq - 1;
+ if (!index_storage_search_next_update_seq(ctx))
+ i_unreached();
+ return TRUE;
+ }
+
+ if (ctx->sort_program != NULL &&
+ seq_range_array_iter_nth(&vctx->result_iter,
+ vctx->next_result_n, &ctx->seq)) {
+ search_args_set_full_match(ctx->args->args);
+ vctx->next_result_n++;
+ return TRUE;
+ }
+ return FALSE;
+}
diff -r 1ff129ed866a -r b12705704329 src/plugins/virtual/virtual-storage.c
--- a/src/plugins/virtual/virtual-storage.c Sun Nov 23 02:37:23 2008 +0200
+++ b/src/plugins/virtual/virtual-storage.c Sun Nov 23 02:40:09 2008 +0200
@@ -24,6 +24,8 @@ extern struct mail_storage virtual_stora
extern struct mail_storage virtual_storage;
extern struct mailbox virtual_mailbox;
+struct virtual_storage_module virtual_storage_module =
+ MODULE_CONTEXT_INIT(&mail_storage_module_register);
static MODULE_CONTEXT_DEFINE_INIT(virtual_mailbox_list_module,
&mailbox_list_module_register);
@@ -584,10 +586,10 @@ struct mailbox virtual_mailbox = {
index_header_lookup_init,
index_header_lookup_ref,
index_header_lookup_unref,
- index_storage_search_init,
- index_storage_search_deinit,
- index_storage_search_next_nonblock,
- index_storage_search_next_update_seq,
+ virtual_search_init,
+ virtual_search_deinit,
+ virtual_search_next_nonblock,
+ virtual_search_next_update_seq,
NULL,
NULL,
NULL,
diff -r 1ff129ed866a -r b12705704329 src/plugins/virtual/virtual-storage.h
--- a/src/plugins/virtual/virtual-storage.h Sun Nov 23 02:37:23 2008 +0200
+++ b/src/plugins/virtual/virtual-storage.h Sun Nov 23 02:40:09 2008 +0200
@@ -9,6 +9,9 @@
#define VIRTUAL_SUBSCRIPTION_FILE_NAME ".virtual-subscriptions"
#define VIRTUAL_CONFIG_FNAME "dovecot-virtual"
#define VIRTUAL_INDEX_PREFIX "dovecot.index"
+
+#define VIRTUAL_CONTEXT(obj) \
+ MODULE_CONTEXT(obj, virtual_storage_module)
struct virtual_mail_index_header {
/* Increased by one each time the header is modified */
@@ -107,6 +110,9 @@ struct virtual_mailbox {
unsigned int sync_initialized:1;
};
+extern MODULE_CONTEXT_DEFINE(virtual_storage_module,
+ &mail_storage_module_register);
+
extern struct mail_storage virtual_storage;
extern struct mail_vfuncs virtual_mail_vfuncs;
@@ -120,6 +126,15 @@ struct mailbox_transaction_context *
struct mailbox_transaction_context *
virtual_transaction_get(struct mailbox_transaction_context *trans,
struct mailbox *backend_box);
+
+struct mail_search_context *
+virtual_search_init(struct mailbox_transaction_context *t,
+ struct mail_search_args *args,
+ const enum mail_sort_type *sort_program);
+int virtual_search_deinit(struct mail_search_context *ctx);
+int virtual_search_next_nonblock(struct mail_search_context *ctx,
+ struct mail *mail, bool *tryagain_r);
+bool virtual_search_next_update_seq(struct mail_search_context *ctx);
struct mail *
virtual_mail_alloc(struct mailbox_transaction_context *t,
More information about the dovecot-cvs
mailing list