Cross Reference: /dovecot/src/lib-index/mail-index-transaction-sort-appends.c
mail-index-transaction-sort-appends.c revision e20e638805c4bd54e039891a3e92760b1dfa189a
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
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen/* Copyright (c) 2003-2009 Dovecot authors, see the included COPYING file */
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen#include "lib.h"
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen#include "array.h"
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen#include "seq-range-array.h"
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen#include "mail-index-private.h"
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen#include "mail-index-transaction-private.h"
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen#include <stdlib.h>
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainenstruct uid_map {
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen uint32_t idx;
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen uint32_t uid;
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen};
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainenstatic int uid_map_cmp(const void *p1, const void *p2)
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen{
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen const struct uid_map *m1 = p1, *m2 = p2;
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen return m1->uid < m2->uid ? -1 :
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen (m1->uid > m2->uid ? 1 : 0);
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen}
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainenstatic void
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainenmail_index_transaction_sort_appends_ext(ARRAY_TYPE(seq_array_array) *updates,
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen uint32_t first_new_seq,
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen const uint32_t *old_to_newseq_map)
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen{
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen ARRAY_TYPE(seq_array) *ext_rec_arrays;
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen ARRAY_TYPE(seq_array) *old_array;
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen ARRAY_TYPE(seq_array) new_array;
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen unsigned int ext_count;
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen const uint32_t *ext_rec;
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen uint32_t seq;
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen unsigned int i, j, count;
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen if (!array_is_created(updates))
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen return;
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen ext_rec_arrays = array_get_modifiable(updates, &count);
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen for (j = 0; j < count; j++) {
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen old_array = &ext_rec_arrays[j];
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen if (!array_is_created(old_array))
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen continue;
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen ext_count = array_count(old_array);
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen array_create(&new_array, default_pool,
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen old_array->arr.element_size, ext_count);
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen for (i = 0; i < ext_count; i++) {
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen ext_rec = array_idx(old_array, i);
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen seq = *ext_rec < first_new_seq ? *ext_rec :
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen old_to_newseq_map[*ext_rec - first_new_seq];
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen mail_index_seq_array_add(&new_array, seq, ext_rec+1,
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen old_array->arr.element_size -
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen sizeof(*ext_rec), NULL);
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen }
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen array_free(old_array);
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen ext_rec_arrays[j] = new_array;
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen }
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen}
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainenstatic void
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainensort_appends_seq_range(ARRAY_TYPE(seq_range) *array, uint32_t first_new_seq,
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen const uint32_t *old_to_newseq_map)
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen{
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen struct seq_range *range, temp_range;
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen ARRAY_TYPE(seq_range) old_seqs;
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen uint32_t idx, idx1, idx2;
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen unsigned int i, count;
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen range = array_get_modifiable(array, &count);
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen for (i = 0; i < count; i++) {
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen if (range[i].seq2 >= first_new_seq)
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen break;
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen }
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen if (i == count) {
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen /* nothing to do */
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen return;
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen }
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen i_array_init(&old_seqs, count - i);
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen if (range[i].seq1 < first_new_seq) {
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen temp_range.seq1 = first_new_seq;
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen temp_range.seq2 = range[i].seq2;
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen array_append(&old_seqs, &temp_range, 1);
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen range[i].seq2 = first_new_seq - 1;
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen i++;
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen }
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen array_append(&old_seqs, &range[i], count - i);
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen array_delete(array, i, count - i);
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen range = array_get_modifiable(&old_seqs, &count);
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen for (i = 0; i < count; i++) {
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen idx1 = range[i].seq1 - first_new_seq;
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen idx2 = range[i].seq2 - first_new_seq;
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen for (idx = idx1; idx <= idx2; idx++)
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen seq_range_array_add(array, 0, old_to_newseq_map[idx]);
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen }
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen array_free(&old_seqs);
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen}
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainenstatic void
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainenmail_index_transaction_sort_appends_keywords(struct mail_index_transaction *t,
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen const uint32_t *old_to_newseq_map)
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen{
e20e638805c4bd54e039891a3e92760b1dfa189aTimo Sirainen struct mail_index_transaction_keyword_update *update;
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen if (array_is_created(&t->keyword_updates)) {
e20e638805c4bd54e039891a3e92760b1dfa189aTimo Sirainen array_foreach_modifiable(&t->keyword_updates, update) {
e20e638805c4bd54e039891a3e92760b1dfa189aTimo Sirainen if (array_is_created(&update->add_seq)) {
e20e638805c4bd54e039891a3e92760b1dfa189aTimo Sirainen sort_appends_seq_range(&update->add_seq,
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen t->first_new_seq,
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen old_to_newseq_map);
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen }
e20e638805c4bd54e039891a3e92760b1dfa189aTimo Sirainen if (array_is_created(&update->remove_seq)) {
e20e638805c4bd54e039891a3e92760b1dfa189aTimo Sirainen sort_appends_seq_range(&update->remove_seq,
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen t->first_new_seq,
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen old_to_newseq_map);
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen }
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen }
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen }
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen if (array_is_created(&t->keyword_resets)) {
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen sort_appends_seq_range(&t->keyword_resets, t->first_new_seq,
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen old_to_newseq_map);
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen }
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen}
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainenvoid mail_index_transaction_sort_appends(struct mail_index_transaction *t)
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen{
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen struct mail_index_record *recs, *sorted_recs;
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen struct uid_map *new_uid_map;
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen uint32_t *old_to_newseq_map;
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen unsigned int i, count;
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen if (!t->appends_nonsorted || !array_is_created(&t->appends))
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen return;
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen /* first make a copy of the UIDs and map them to sequences */
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen recs = array_get_modifiable(&t->appends, &count);
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen i_assert(count > 0);
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen new_uid_map = i_new(struct uid_map, count);
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen for (i = 0; i < count; i++) {
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen new_uid_map[i].idx = i;
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen new_uid_map[i].uid = recs[i].uid;
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen }
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen /* now sort the UID map */
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen qsort(new_uid_map, count, sizeof(*new_uid_map), uid_map_cmp);
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen /* sort mail records */
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen sorted_recs = i_new(struct mail_index_record, count);
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen sorted_recs[0] = recs[new_uid_map[0].idx];
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen for (i = 1; i < count; i++) {
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen sorted_recs[i] = recs[new_uid_map[i].idx];
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen if (sorted_recs[i].uid == sorted_recs[i-1].uid)
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen i_panic("Duplicate UIDs added in transaction");
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen }
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen buffer_write(t->appends.arr.buffer, 0, sorted_recs,
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen sizeof(*sorted_recs) * count);
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen i_free(sorted_recs);
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen old_to_newseq_map = i_new(uint32_t, count);
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen for (i = 0; i < count; i++)
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen old_to_newseq_map[new_uid_map[i].idx] = i + t->first_new_seq;
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen i_free(new_uid_map);
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen mail_index_transaction_sort_appends_ext(&t->ext_rec_updates,
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen t->first_new_seq,
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen old_to_newseq_map);
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen mail_index_transaction_sort_appends_ext(&t->ext_rec_atomics,
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen t->first_new_seq,
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen old_to_newseq_map);
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen mail_index_transaction_sort_appends_keywords(t, old_to_newseq_map);
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen i_free(old_to_newseq_map);
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen t->appends_nonsorted = FALSE;
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen}