null
mail-index-transaction-sort-appends.c revision 5f5870385cff47efd2f58e7892f251cf13761528
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher/* Copyright (c) 2003-2012 Dovecot authors, see the included COPYING file */
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher
ee359fe1384507fed6c2274e7bfe81d288de4542Stephen Gallagher#include "lib.h"
33396dc46ea52c18f47db1b5d590880806521005Sumit Bose#include "array.h"
ee359fe1384507fed6c2274e7bfe81d288de4542Stephen Gallagher#include "seq-range-array.h"
33396dc46ea52c18f47db1b5d590880806521005Sumit Bose#include "mail-index-private.h"
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher#include "mail-index-transaction-private.h"
324fb26ba803a999bedc29e93c46c84f27abf5b7Sumit Bose
324fb26ba803a999bedc29e93c46c84f27abf5b7Sumit Bose#include <stdlib.h>
324fb26ba803a999bedc29e93c46c84f27abf5b7Sumit Bose
324fb26ba803a999bedc29e93c46c84f27abf5b7Sumit Bosestruct uid_map {
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher uint32_t idx;
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher uint32_t uid;
84ae5edab16ad6be5e3be956cb6fa031c1428eb5Stephen Gallagher};
84ae5edab16ad6be5e3be956cb6fa031c1428eb5Stephen Gallagher
84ae5edab16ad6be5e3be956cb6fa031c1428eb5Stephen Gallagherstatic int uid_map_cmp(const void *p1, const void *p2)
e65df5b966b27e13283c65f59f99ac44781e0333Simo Sorce{
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher const struct uid_map *m1 = p1, *m2 = p2;
672f430c2e5d55226261a281bc3fa77311ace5a4Jakub Hrozek
672f430c2e5d55226261a281bc3fa77311ace5a4Jakub Hrozek return m1->uid < m2->uid ? -1 :
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher (m1->uid > m2->uid ? 1 : 0);
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher}
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagherstatic void
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallaghermail_index_transaction_sort_appends_ext(ARRAY_TYPE(seq_array_array) *updates,
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher uint32_t first_new_seq,
84ae5edab16ad6be5e3be956cb6fa031c1428eb5Stephen Gallagher const uint32_t *old_to_newseq_map)
cc98edd9479d4622634a1275c98058916c14059aStephen Gallagher{
ee359fe1384507fed6c2274e7bfe81d288de4542Stephen Gallagher ARRAY_TYPE(seq_array) *ext_rec_arrays;
cc98edd9479d4622634a1275c98058916c14059aStephen Gallagher ARRAY_TYPE(seq_array) *old_array;
d3da1c165cdb4c1ec126a8f4b6b544ca415b9d20Pavel Březina ARRAY_TYPE(seq_array) new_array;
d3da1c165cdb4c1ec126a8f4b6b544ca415b9d20Pavel Březina unsigned int ext_count;
d3da1c165cdb4c1ec126a8f4b6b544ca415b9d20Pavel Březina const uint32_t *ext_rec;
1183d29d87c5c7439cf2364b7d7324d4a13b6e35Stephen Gallagher uint32_t seq;
1183d29d87c5c7439cf2364b7d7324d4a13b6e35Stephen Gallagher unsigned int i, j, count;
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher if (!array_is_created(updates))
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher return;
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher ext_rec_arrays = array_get_modifiable(updates, &count);
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher for (j = 0; j < count; j++) {
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher old_array = &ext_rec_arrays[j];
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher if (!array_is_created(old_array))
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher continue;
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher ext_count = array_count(old_array);
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher array_create(&new_array, default_pool,
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher old_array->arr.element_size, ext_count);
c89589fa349f38214c9cb8d9389c0fd557e5dca2Simo Sorce for (i = 0; i < ext_count; i++) {
c89589fa349f38214c9cb8d9389c0fd557e5dca2Simo Sorce ext_rec = array_idx(old_array, i);
c89589fa349f38214c9cb8d9389c0fd557e5dca2Simo Sorce
86b61156743b7ebdc049450a6f88452890fd9a61Jakub Hrozek seq = *ext_rec < first_new_seq ? *ext_rec :
86b61156743b7ebdc049450a6f88452890fd9a61Jakub Hrozek old_to_newseq_map[*ext_rec - first_new_seq];
86b61156743b7ebdc049450a6f88452890fd9a61Jakub Hrozek mail_index_seq_array_add(&new_array, seq, ext_rec+1,
c89589fa349f38214c9cb8d9389c0fd557e5dca2Simo Sorce old_array->arr.element_size -
c89589fa349f38214c9cb8d9389c0fd557e5dca2Simo Sorce sizeof(*ext_rec), NULL);
86b61156743b7ebdc049450a6f88452890fd9a61Jakub Hrozek }
86b61156743b7ebdc049450a6f88452890fd9a61Jakub Hrozek array_free(old_array);
86b61156743b7ebdc049450a6f88452890fd9a61Jakub Hrozek ext_rec_arrays[j] = new_array;
86b61156743b7ebdc049450a6f88452890fd9a61Jakub Hrozek }
86b61156743b7ebdc049450a6f88452890fd9a61Jakub Hrozek}
86b61156743b7ebdc049450a6f88452890fd9a61Jakub Hrozek
86b61156743b7ebdc049450a6f88452890fd9a61Jakub Hrozekstatic void
86b61156743b7ebdc049450a6f88452890fd9a61Jakub Hrozeksort_appends_seq_range(ARRAY_TYPE(seq_range) *array, uint32_t first_new_seq,
86b61156743b7ebdc049450a6f88452890fd9a61Jakub Hrozek const uint32_t *old_to_newseq_map)
86b61156743b7ebdc049450a6f88452890fd9a61Jakub Hrozek{
86b61156743b7ebdc049450a6f88452890fd9a61Jakub Hrozek struct seq_range *range, temp_range;
48130eef6c5c64a07094b9e8582ba358b2048f24Jakub Hrozek ARRAY_TYPE(seq_range) old_seqs;
48130eef6c5c64a07094b9e8582ba358b2048f24Jakub Hrozek uint32_t idx, idx1, idx2;
48130eef6c5c64a07094b9e8582ba358b2048f24Jakub Hrozek unsigned int i, count;
48130eef6c5c64a07094b9e8582ba358b2048f24Jakub Hrozek
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher range = array_get_modifiable(array, &count);
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher for (i = 0; i < count; i++) {
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher if (range[i].seq2 >= first_new_seq)
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher break;
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher }
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher if (i == count) {
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher /* nothing to do */
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher return;
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher }
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher i_array_init(&old_seqs, count - i);
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher if (range[i].seq1 < first_new_seq) {
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher temp_range.seq1 = first_new_seq;
d921c1eba437662437847279f251a0a5d8f70127Maxim temp_range.seq2 = range[i].seq2;
d921c1eba437662437847279f251a0a5d8f70127Maxim array_append(&old_seqs, &temp_range, 1);
d921c1eba437662437847279f251a0a5d8f70127Maxim range[i].seq2 = first_new_seq - 1;
d921c1eba437662437847279f251a0a5d8f70127Maxim i++;
d921c1eba437662437847279f251a0a5d8f70127Maxim }
d921c1eba437662437847279f251a0a5d8f70127Maxim array_append(&old_seqs, &range[i], count - i);
d921c1eba437662437847279f251a0a5d8f70127Maxim array_delete(array, i, count - i);
327127bb7fcc07f882209f029e14026de1b23c94Maxim
327127bb7fcc07f882209f029e14026de1b23c94Maxim range = array_get_modifiable(&old_seqs, &count);
327127bb7fcc07f882209f029e14026de1b23c94Maxim for (i = 0; i < count; i++) {
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher idx1 = range[i].seq1 - first_new_seq;
d3da1c165cdb4c1ec126a8f4b6b544ca415b9d20Pavel Březina idx2 = range[i].seq2 - first_new_seq;
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher for (idx = idx1; idx <= idx2; idx++)
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher seq_range_array_add(array, 0, old_to_newseq_map[idx]);
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher }
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher array_free(&old_seqs);
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher}
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher
eb2e21b764d03544d8161e9956d7f70b07b75f77Simo Sorcestatic void
bc9235cfb80bd64a3bfa959e8d26d5ad1be0bdf4Jakub Hrozekmail_index_transaction_sort_appends_keywords(struct mail_index_transaction *t,
bc9235cfb80bd64a3bfa959e8d26d5ad1be0bdf4Jakub Hrozek const uint32_t *old_to_newseq_map)
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher{
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher struct mail_index_transaction_keyword_update *update;
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher if (array_is_created(&t->keyword_updates)) {
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher array_foreach_modifiable(&t->keyword_updates, update) {
4b6a0d0b3d42e5fdb457f47d9adfa5e66b160256Stephen Gallagher if (array_is_created(&update->add_seq)) {
90fd1bbd6035cdab46faa3a695a2fb2be6508b17Sumit Bose sort_appends_seq_range(&update->add_seq,
03713859dffacc7142393e53c73d8d4cf7dee8d5Pavel Březina t->first_new_seq,
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher old_to_newseq_map);
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher }
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher if (array_is_created(&update->remove_seq)) {
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher sort_appends_seq_range(&update->remove_seq,
068dbee9ca7bf5b37330eff91c94ae10f288d09fJakub Hrozek t->first_new_seq,
98ce3c3e85a4bb2e1822bf8ab2a1c2ab9e3dd61dJakub Hrozek old_to_newseq_map);
be65f065fef1d387281096ef095a2acef39ecc12Jakub Hrozek }
e124844907ed6973915e4d56f5442ecd07535a12Jakub Hrozek }
f36078af138f052cd9a30360867b0ebd0805af5eJakub Hrozek }
34c78b745eb349eef2b0f13ef2b722632aebe619Jan Cholasta
e07a94a66985b674c5df11ca466792902164c4e2George McCollister if (array_is_created(&t->keyword_resets)) {
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher sort_appends_seq_range(&t->keyword_resets, t->first_new_seq,
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher old_to_newseq_map);
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher }
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher}
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallaghervoid mail_index_transaction_sort_appends(struct mail_index_transaction *t)
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher{
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher struct mail_index_record *recs, *sorted_recs;
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher struct uid_map *new_uid_map;
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher uint32_t *old_to_newseq_map;
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher unsigned int i, count;
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher if (!t->appends_nonsorted || !array_is_created(&t->appends))
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher return;
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher
a5077712fc8c24e8cad08207b7b5a6603bde6a7cJakub Hrozek /* first make a copy of the UIDs and map them to sequences */
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher recs = array_get_modifiable(&t->appends, &count);
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher i_assert(count > 0);
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher new_uid_map = i_new(struct uid_map, count);
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher for (i = 0; i < count; i++) {
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher new_uid_map[i].idx = i;
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher new_uid_map[i].uid = recs[i].uid;
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher }
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher
2a5790216f57e9bdfb2930d52860bb5300366536Jakub Hrozek /* now sort the UID map */
b9e5bd09a5ff7009537a18914dbebcf10498f592Sumit Bose qsort(new_uid_map, count, sizeof(*new_uid_map), uid_map_cmp);
6b0a7c72bb841d6885a620c68bd51d55109b66c7Jakub Hrozek
a679f0167b646cffdae86546ed77e105576991b0Pavel Březina /* sort mail records */
b32159300fea63222d8dd9200ed634087704ea74Stephen Gallagher sorted_recs = i_new(struct mail_index_record, count);
b32159300fea63222d8dd9200ed634087704ea74Stephen Gallagher sorted_recs[0] = recs[new_uid_map[0].idx];
b32159300fea63222d8dd9200ed634087704ea74Stephen Gallagher for (i = 1; i < count; i++) {
b32159300fea63222d8dd9200ed634087704ea74Stephen Gallagher sorted_recs[i] = recs[new_uid_map[i].idx];
b32159300fea63222d8dd9200ed634087704ea74Stephen Gallagher if (sorted_recs[i].uid == sorted_recs[i-1].uid)
b32159300fea63222d8dd9200ed634087704ea74Stephen Gallagher i_panic("Duplicate UIDs added in transaction");
b32159300fea63222d8dd9200ed634087704ea74Stephen Gallagher }
b32159300fea63222d8dd9200ed634087704ea74Stephen Gallagher buffer_write(t->appends.arr.buffer, 0, sorted_recs,
b32159300fea63222d8dd9200ed634087704ea74Stephen Gallagher sizeof(*sorted_recs) * count);
b32159300fea63222d8dd9200ed634087704ea74Stephen Gallagher i_free(sorted_recs);
b32159300fea63222d8dd9200ed634087704ea74Stephen Gallagher
b32159300fea63222d8dd9200ed634087704ea74Stephen Gallagher old_to_newseq_map = i_new(uint32_t, count);
b32159300fea63222d8dd9200ed634087704ea74Stephen Gallagher for (i = 0; i < count; i++)
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher old_to_newseq_map[new_uid_map[i].idx] = i + t->first_new_seq;
539b1be3507abdf8ac235b06eeed5011b0b5cde2Ondrej Kos i_free(new_uid_map);
539b1be3507abdf8ac235b06eeed5011b0b5cde2Ondrej Kos
574a1c20f114851071ae74112b34488c3d1aeeb3Ondrej Kos mail_index_transaction_sort_appends_ext(&t->ext_rec_updates,
574a1c20f114851071ae74112b34488c3d1aeeb3Ondrej Kos t->first_new_seq,
574a1c20f114851071ae74112b34488c3d1aeeb3Ondrej Kos old_to_newseq_map);
574a1c20f114851071ae74112b34488c3d1aeeb3Ondrej Kos mail_index_transaction_sort_appends_ext(&t->ext_rec_atomics,
2a5790216f57e9bdfb2930d52860bb5300366536Jakub Hrozek t->first_new_seq,
e6e26182d58c05d896f72f2925426658a6dc70b5Jakub Hrozek old_to_newseq_map);
e6e26182d58c05d896f72f2925426658a6dc70b5Jakub Hrozek mail_index_transaction_sort_appends_keywords(t, old_to_newseq_map);
e6e26182d58c05d896f72f2925426658a6dc70b5Jakub Hrozek i_free(old_to_newseq_map);
2a5790216f57e9bdfb2930d52860bb5300366536Jakub Hrozek
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher t->appends_nonsorted = FALSE;
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher}
551aa6c36797ed720487f5974dcadabf19e6ff9fStephen Gallagher