mail-index-transaction-sort-appends.c revision bcb4e51a409d94ae670de96afb8483a4f7855294
bcb4e51a409d94ae670de96afb8483a4f7855294Stephan Bosch/* Copyright (c) 2003-2018 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
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];
e34d170f8f0e084bd94bfbc1a7085ece67e508dfTimo Sirainen (void)mail_index_seq_array_add(&new_array, seq, ext_rec+1,
e34d170f8f0e084bd94bfbc1a7085ece67e508dfTimo Sirainen old_array->arr.element_size -
e34d170f8f0e084bd94bfbc1a7085ece67e508dfTimo 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++)
86bde2c1838d1ce967fa2b394bb952004a4adcb7Timo Sirainen seq_range_array_add(array, 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
250105a1440167ef000323cdb2721cd2a3688e1eTimo Sirainen if (!array_is_created(&t->keyword_updates))
250105a1440167ef000323cdb2721cd2a3688e1eTimo Sirainen return;
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen
250105a1440167ef000323cdb2721cd2a3688e1eTimo Sirainen array_foreach_modifiable(&t->keyword_updates, update) {
250105a1440167ef000323cdb2721cd2a3688e1eTimo Sirainen if (array_is_created(&update->add_seq)) {
250105a1440167ef000323cdb2721cd2a3688e1eTimo Sirainen sort_appends_seq_range(&update->add_seq,
250105a1440167ef000323cdb2721cd2a3688e1eTimo Sirainen t->first_new_seq,
250105a1440167ef000323cdb2721cd2a3688e1eTimo Sirainen old_to_newseq_map);
250105a1440167ef000323cdb2721cd2a3688e1eTimo Sirainen }
250105a1440167ef000323cdb2721cd2a3688e1eTimo Sirainen if (array_is_created(&update->remove_seq)) {
250105a1440167ef000323cdb2721cd2a3688e1eTimo Sirainen sort_appends_seq_range(&update->remove_seq,
250105a1440167ef000323cdb2721cd2a3688e1eTimo Sirainen t->first_new_seq,
250105a1440167ef000323cdb2721cd2a3688e1eTimo Sirainen old_to_newseq_map);
250105a1440167ef000323cdb2721cd2a3688e1eTimo Sirainen }
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
1731683fb0c6afceb20903b1c0a45912d00ed5daTimo Sirainen if (!array_is_created(&t->appends))
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen return;
f09d0344609e8c410a18685fa20ee3998646c2d9Timo Sirainen recs = array_get_modifiable(&t->appends, &count);
f09d0344609e8c410a18685fa20ee3998646c2d9Timo Sirainen i_assert(count > 0);
f09d0344609e8c410a18685fa20ee3998646c2d9Timo Sirainen
1731683fb0c6afceb20903b1c0a45912d00ed5daTimo Sirainen if (!t->appends_nonsorted) {
f09d0344609e8c410a18685fa20ee3998646c2d9Timo Sirainen i_assert(recs[0].uid != 0);
1731683fb0c6afceb20903b1c0a45912d00ed5daTimo Sirainen#ifdef DEBUG
1731683fb0c6afceb20903b1c0a45912d00ed5daTimo Sirainen for (i = 1; i < count; i++)
1731683fb0c6afceb20903b1c0a45912d00ed5daTimo Sirainen i_assert(recs[i-1].uid < recs[i].uid);
1731683fb0c6afceb20903b1c0a45912d00ed5daTimo Sirainen#endif
1731683fb0c6afceb20903b1c0a45912d00ed5daTimo Sirainen return;
1731683fb0c6afceb20903b1c0a45912d00ed5daTimo Sirainen }
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen /* first make a copy of the UIDs and map them to sequences */
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen new_uid_map = i_new(struct uid_map, count);
1279090ba03f9c176976a69ab7718f0ed77b19afTimo Sirainen for (i = 0; i < count; i++) {
f09d0344609e8c410a18685fa20ee3998646c2d9Timo Sirainen i_assert(recs[i].uid != 0);
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}