Mercurial > dovecot > original-hg > dovecot-1.2

comparison src/plugins/virtual/virtual-search.c @ 8483:b12705704329 HEAD

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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.
author Timo Sirainen <tss@iki.fi>
date Sun, 23 Nov 2008 02:40:09 +0200
parents
children f323bf2465bd
comparison
equal deleted inserted replaced
8482:1ff129ed866a 8483:b12705704329
1 /* Copyright (c) 2008 Dovecot authors, see the included COPYING file */
2
3 #include "lib.h"
4 #include "array.h"
5 #include "mail-search.h"
6 #include "index-storage.h"
7 #include "virtual-storage.h"
8
9 #include <stdlib.h>
10
11 enum virtual_search_state {
12 VIRTUAL_SEARCH_STATE_FAILED = -1,
13 VIRTUAL_SEARCH_STATE_BUILD,
14 VIRTUAL_SEARCH_STATE_RETURN,
15 VIRTUAL_SEARCH_STATE_SORT,
16 VIRTUAL_SEARCH_STATE_SORT_DONE
17 };
18
19 struct virtual_search_record {
20 uint32_t mailbox_id;
21 uint32_t real_uid;
22 uint32_t virtual_seq;
23 };
24
25 struct virtual_search_context {
26 union mail_search_module_context module_ctx;
27
28 ARRAY_TYPE(seq_range) result;
29 struct seq_range_iter result_iter;
30 ARRAY_DEFINE(records, struct virtual_search_record);
31
32 enum virtual_search_state search_state;
33 unsigned int next_result_n;
34 unsigned int next_record_idx;
35 };
36
37 static int virtual_search_record_cmp(const void *p1, const void *p2)
38 {
39 const struct virtual_search_record *r1 = p1, *r2 = p2;
40
41 if (r1->mailbox_id < r2->mailbox_id)
42 return -1;
43 if (r1->mailbox_id > r2->mailbox_id)
44 return 1;
45
46 if (r1->real_uid < r2->real_uid)
47 return -1;
48 if (r1->real_uid > r2->real_uid)
49 return 1;
50 return 0;
51 }
52
53 static int mail_search_get_result(struct mail_search_context *ctx)
54 {
55 const struct mail_search_arg *arg;
56 int ret = 1;
57
58 for (arg = ctx->args->args; arg != NULL; arg = arg->next) {
59 if (arg->result < 0)
60 return -1;
61 if (arg->result == 0)
62 ret = 0;
63 }
64 return ret;
65 }
66
67 static int virtual_search_get_records(struct mail_search_context *ctx,
68 struct virtual_search_context *vctx)
69 {
70 struct virtual_mailbox *mbox =
71 (struct virtual_mailbox *)ctx->transaction->box;
72 const struct virtual_mail_index_record *vrec;
73 struct virtual_search_record srec, *srecs;
74 unsigned int count;
75 const void *data;
76 bool expunged;
77 int ret, result;
78
79 memset(&srec, 0, sizeof(srec));
80 while ((ret = index_storage_search_next_update_seq(ctx)) > 0) {
81 result = mail_search_get_result(ctx);
82 i_assert(result != 0);
83 if (result > 0) {
84 /* full match, no need to check this any further */
85 seq_range_array_add(&vctx->result, 0, ctx->seq);
86 } else {
87 /* possible match, save and check later */
88 mail_index_lookup_ext(mbox->ibox.view, ctx->seq,
89 mbox->virtual_ext_id,
90 &data, &expunged);
91 vrec = data;
92
93 srec.mailbox_id = vrec->mailbox_id;
94 srec.real_uid = vrec->real_uid;
95 srec.virtual_seq = ctx->seq;
96 array_append(&vctx->records, &srec, 1);
97 }
98 mail_search_args_reset(ctx->args->args, FALSE);
99 }
100 srecs = array_get_modifiable(&vctx->records, &count);
101 qsort(srecs, count, sizeof(*srecs), virtual_search_record_cmp);
102 return ret;
103 }
104
105 struct mail_search_context *
106 virtual_search_init(struct mailbox_transaction_context *t,
107 struct mail_search_args *args,
108 const enum mail_sort_type *sort_program)
109 {
110 struct mail_search_context *ctx;
111 struct virtual_search_context *vctx;
112
113 ctx = index_storage_search_init(t, args, sort_program);
114
115 vctx = i_new(struct virtual_search_context, 1);
116 vctx->search_state = VIRTUAL_SEARCH_STATE_BUILD;
117 i_array_init(&vctx->result, 64);
118 i_array_init(&vctx->records, 64);
119 MODULE_CONTEXT_SET(ctx, virtual_storage_module, vctx);
120
121 if (virtual_search_get_records(ctx, vctx) < 0)
122 vctx->search_state = VIRTUAL_SEARCH_STATE_FAILED;
123
124 seq_range_array_iter_init(&vctx->result_iter, &vctx->result);
125 return ctx;
126 }
127
128 int virtual_search_deinit(struct mail_search_context *ctx)
129 {
130 struct virtual_search_context *vctx = VIRTUAL_CONTEXT(ctx);
131
132 array_free(&vctx->result);
133 array_free(&vctx->records);
134 i_free(vctx);
135 return index_storage_search_deinit(ctx);
136 }
137
138 int virtual_search_next_nonblock(struct mail_search_context *ctx,
139 struct mail *mail, bool *tryagain_r)
140 {
141 struct virtual_search_context *vctx = VIRTUAL_CONTEXT(ctx);
142 uint32_t seq;
143 int ret;
144
145 switch (vctx->search_state) {
146 case VIRTUAL_SEARCH_STATE_FAILED:
147 return -1;
148 case VIRTUAL_SEARCH_STATE_BUILD:
149 if (ctx->sort_program == NULL)
150 vctx->search_state = VIRTUAL_SEARCH_STATE_SORT;
151 else
152 vctx->search_state = VIRTUAL_SEARCH_STATE_RETURN;
153 return virtual_search_next_nonblock(ctx, mail, tryagain_r);
154 case VIRTUAL_SEARCH_STATE_RETURN:
155 return index_storage_search_next_nonblock(ctx, mail, tryagain_r);
156 case VIRTUAL_SEARCH_STATE_SORT:
157 /* the messages won't be returned sorted, so we'll have to
158 do it ourself */
159 while ((ret = index_storage_search_next_nonblock(ctx, mail,
160 tryagain_r)) > 0)
161 seq_range_array_add(&vctx->result, 0, mail->seq);
162 if (ret < 0 || *tryagain_r)
163 return ret;
164
165 vctx->next_result_n = 0;
166 vctx->search_state = VIRTUAL_SEARCH_STATE_SORT_DONE;
167 /* fall through */
168 case VIRTUAL_SEARCH_STATE_SORT_DONE:
169 *tryagain_r = FALSE;
170 if (!seq_range_array_iter_nth(&vctx->result_iter,
171 vctx->next_result_n, &seq))
172 return 0;
173 vctx->next_result_n++;
174 mail_set_seq(mail, seq);
175 return 1;
176 }
177 i_unreached();
178 }
179
180 static void search_args_set_full_match(struct mail_search_arg *args)
181 {
182 for (; args != NULL; args = args->next)
183 args->result = 1;
184 }
185
186 bool virtual_search_next_update_seq(struct mail_search_context *ctx)
187 {
188 struct virtual_search_context *vctx = VIRTUAL_CONTEXT(ctx);
189 const struct virtual_search_record *recs;
190 unsigned int count;
191
192 recs = array_get(&vctx->records, &count);
193 if (vctx->next_record_idx < count) {
194 ctx->seq = recs[vctx->next_record_idx++].virtual_seq - 1;
195 if (!index_storage_search_next_update_seq(ctx))
196 i_unreached();
197 return TRUE;
198 }
199
200 if (ctx->sort_program != NULL &&
201 seq_range_array_iter_nth(&vctx->result_iter,
202 vctx->next_result_n, &ctx->seq)) {
203 search_args_set_full_match(ctx->args->args);
204 vctx->next_result_n++;
205 return TRUE;
206 }
207 return FALSE;
208 }