src/lib-index/mail-index-transaction.c

	mail-index-transaction.c revision b492193936f0e63dd0a24137e600d495351bfca4
c25356d5978632df6203437e1953bcb29e0c736fTimo Sirainen/* Copyright (C) 2003-2004 Timo Sirainen */
c25356d5978632df6203437e1953bcb29e0c736fTimo Sirainen
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen/* Inside transaction we keep messages stored in sequences in uid fields.
49e358eebea107aad9919dcc4bd88cee8519ba2eTimo Sirainen   Before they're written to transaction log the sequences are changed to
49e358eebea107aad9919dcc4bd88cee8519ba2eTimo Sirainen   UIDs. This is because we're able to compress sequence ranges better. */
49e358eebea107aad9919dcc4bd88cee8519ba2eTimo Sirainen
c0435c854a0e7246373b9752d163095cc4fbe985Timo Sirainen#include "lib.h"
dd62b77c932d1b518f2a3e4bf80e36542becc256Timo Sirainen#include "buffer.h"
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen#include "mail-index-view-private.h"
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen#include "mail-transaction-log.h"
03f5c621d06d6b6d77a145196c9633a7aa64dc78Timo Sirainen#include "mail-cache-private.h"
c06f4017027263cf3a08becc551f5126409e2a83Timo Sirainen#include "mail-index-transaction-private.h"
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen
da2aa032ccfa8e7e4a4380ef738014549f4d2c2dTimo Sirainen#include <stddef.h>
da2aa032ccfa8e7e4a4380ef738014549f4d2c2dTimo Sirainen
411d6baa37f31d90730e90c4a28c43e1974bbe58Timo Sirainenstatic void mail_index_transaction_add_last(struct mail_index_transaction *t);
7e1f68ad71d3485f1882142837b01f7a98ca8467Timo Sirainen
7e1f68ad71d3485f1882142837b01f7a98ca8467Timo Sirainenstruct mail_index_transaction *
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainenmail_index_transaction_begin(struct mail_index_view *view, int hide)
252db51b6c0a605163326b3ea5d09e9936ca3b29Timo Sirainen{
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen    struct mail_index_transaction *t;
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen
5ac0b0bf32898c63da086ae169674ecac151a31eTimo Sirainen    /* don't allow syncing view while there's ongoing transactions */
5ac0b0bf32898c63da086ae169674ecac151a31eTimo Sirainen    mail_index_view_transaction_ref(view);
2526d52441ef368215ab6bf04fd0356d3b09d235Timo Sirainen
2526d52441ef368215ab6bf04fd0356d3b09d235Timo Sirainen    t = i_new(struct mail_index_transaction, 1);
09801f106cd531a28b4e03ec665e44c421264560Timo Sirainen    t->refcount = 1;
09801f106cd531a28b4e03ec665e44c421264560Timo Sirainen    t->view = view;
09801f106cd531a28b4e03ec665e44c421264560Timo Sirainen    t->hide_transaction = hide;
fe363b433b8038a69b55169da9dca27892ad7d18Timo Sirainen    t->first_new_seq = mail_index_view_get_message_count(t->view)+1;
c0435c854a0e7246373b9752d163095cc4fbe985Timo Sirainen    return t;
6ef7e31619edfaa17ed044b45861d106a86191efTimo Sirainen}
fe363b433b8038a69b55169da9dca27892ad7d18Timo Sirainen
10c96a244935de4add8213ba0b894178dfb889a5Timo Sirainenstatic void mail_index_transaction_free(struct mail_index_transaction *t)
bdcb00145ad87765e3fd22d4ebc4d2c029a326b9Timo Sirainen{
bdcb00145ad87765e3fd22d4ebc4d2c029a326b9Timo Sirainen    unsigned int i;
0c1835a90dd1dcedaeaedd1cd91672299cbeb5beTimo Sirainen
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen    mail_index_view_transaction_unref(t->view);
8cb72c59d5ea4e9e5f638d7ec840bb853f5a188eTimo Sirainen
8cb72c59d5ea4e9e5f638d7ec840bb853f5a188eTimo Sirainen    for (i = 0; i < t->view->index->extra_records_count; i++) {
8cb72c59d5ea4e9e5f638d7ec840bb853f5a188eTimo Sirainen        if (t->extra_rec_updates[i] != NULL)
8cb72c59d5ea4e9e5f638d7ec840bb853f5a188eTimo Sirainen            buffer_free(t->extra_rec_updates[i]);
8cb72c59d5ea4e9e5f638d7ec840bb853f5a188eTimo Sirainen    }
8cb72c59d5ea4e9e5f638d7ec840bb853f5a188eTimo Sirainen
8cb72c59d5ea4e9e5f638d7ec840bb853f5a188eTimo Sirainen    if (t->appends != NULL)
e2ce8d4a6ac5d82a906178148453e7613fab9ba0Timo Sirainen        buffer_free(t->appends);
cd56a23e21f1df3f79648cf07e2f4385e2fadebbTimo Sirainen    if (t->expunges != NULL)
cd56a23e21f1df3f79648cf07e2f4385e2fadebbTimo Sirainen        buffer_free(t->expunges);
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen    if (t->updates != NULL)
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen        buffer_free(t->updates);
c0435c854a0e7246373b9752d163095cc4fbe985Timo Sirainen    if (t->cache_updates != NULL)
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen        buffer_free(t->cache_updates);
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen    i_free(t);
5ac0b0bf32898c63da086ae169674ecac151a31eTimo Sirainen}
5ac0b0bf32898c63da086ae169674ecac151a31eTimo Sirainen
a10ed8c47534b4c6b6bf2711ccfe577e720a47b4Timo Sirainenvoid mail_index_transaction_ref(struct mail_index_transaction *t)
a10ed8c47534b4c6b6bf2711ccfe577e720a47b4Timo Sirainen{
5ac0b0bf32898c63da086ae169674ecac151a31eTimo Sirainen    t->refcount++;
27a44fcfd8d19bffe0f267f20a2b5d3fe7600fddTimo Sirainen}
27a44fcfd8d19bffe0f267f20a2b5d3fe7600fddTimo Sirainen
27a44fcfd8d19bffe0f267f20a2b5d3fe7600fddTimo Sirainenvoid mail_index_transaction_unref(struct mail_index_transaction *t)
c28f6aa0b70af4811c9ace9114fe827c2f503455Timo Sirainen{
c28f6aa0b70af4811c9ace9114fe827c2f503455Timo Sirainen    if (--t->refcount == 0)
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen        mail_index_transaction_free(t);
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen}
c0435c854a0e7246373b9752d163095cc4fbe985Timo Sirainen
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainenstatic void
e2ce8d4a6ac5d82a906178148453e7613fab9ba0Timo Sirainenmail_index_buffer_convert_to_uids(struct mail_index_view *view,
e2ce8d4a6ac5d82a906178148453e7613fab9ba0Timo Sirainen                  buffer_t *buf, size_t record_size, int range)
c0435c854a0e7246373b9752d163095cc4fbe985Timo Sirainen{
07e4875d250e7a7157cd99132aafc773cf3cdf83Timo Sirainen    unsigned char *data;
07e4875d250e7a7157cd99132aafc773cf3cdf83Timo Sirainen    size_t size, i;
07e4875d250e7a7157cd99132aafc773cf3cdf83Timo Sirainen    uint32_t *seq;
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen
7662010b03ffe5f2a6ecf4b4eb220d1c65efea76Timo Sirainen    if (buf == NULL)
7662010b03ffe5f2a6ecf4b4eb220d1c65efea76Timo Sirainen        return;
7662010b03ffe5f2a6ecf4b4eb220d1c65efea76Timo Sirainen
7662010b03ffe5f2a6ecf4b4eb220d1c65efea76Timo Sirainen    /* @UNSAFE */
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen    data = buffer_get_modifyable_data(buf, &size);
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen    for (i = 0; i < size; i += record_size) {
c0435c854a0e7246373b9752d163095cc4fbe985Timo Sirainen        seq = (uint32_t *)&data[i];
0a49b316fc729e5d57268ffa63c7122ac73f994cTimo Sirainen        i_assert(seq[0] <= view->map->records_count);
0a49b316fc729e5d57268ffa63c7122ac73f994cTimo Sirainen
51e1a1c280ccb461a15827f7987d09cb9708b6e3Timo Sirainen        seq[0] = MAIL_INDEX_MAP_IDX(view->map, seq[0]-1)->uid;
51e1a1c280ccb461a15827f7987d09cb9708b6e3Timo Sirainen        if (range) {
51e1a1c280ccb461a15827f7987d09cb9708b6e3Timo Sirainen            i_assert(seq[1] <= view->map->records_count);
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen            seq[1] = MAIL_INDEX_MAP_IDX(view->map, seq[1]-1)->uid;
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen        }
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen    }
c0435c854a0e7246373b9752d163095cc4fbe985Timo Sirainen}
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainenstatic int
c0435c854a0e7246373b9752d163095cc4fbe985Timo Sirainenmail_index_transaction_convert_to_uids(struct mail_index_transaction *t)
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen{
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen    struct mail_index *index = t->view->index;
c0435c854a0e7246373b9752d163095cc4fbe985Timo Sirainen    unsigned int i;
602a0434db30d8e3292d1c161a803d96a879a74fTimo Sirainen
602a0434db30d8e3292d1c161a803d96a879a74fTimo Sirainen    if (mail_index_view_lock(t->view) < 0)
602a0434db30d8e3292d1c161a803d96a879a74fTimo Sirainen        return -1;
602a0434db30d8e3292d1c161a803d96a879a74fTimo Sirainen
602a0434db30d8e3292d1c161a803d96a879a74fTimo Sirainen    for (i = 0; i < index->extra_records_count; i++) {
01f4ee4a0243f3fe9af763e1a540cd5cff0d63f5Timo Sirainen        if (t->extra_rec_updates[i] == NULL)
07e4875d250e7a7157cd99132aafc773cf3cdf83Timo Sirainen            continue;
7d207b1e77a7b5e3fda640e353acfc86d261fedfTimo Sirainen
7d207b1e77a7b5e3fda640e353acfc86d261fedfTimo Sirainen        mail_index_buffer_convert_to_uids(t->view,
7d207b1e77a7b5e3fda640e353acfc86d261fedfTimo Sirainen                          t->extra_rec_updates[i],
7d207b1e77a7b5e3fda640e353acfc86d261fedfTimo Sirainen                                                  sizeof(uint32_t) +
7d207b1e77a7b5e3fda640e353acfc86d261fedfTimo Sirainen                          index->extra_records[i].size,
01f4ee4a0243f3fe9af763e1a540cd5cff0d63f5Timo Sirainen                          FALSE);
4b9f99761df5014c659cd87fddaf6854af428cfcTimo Sirainen    }
4b9f99761df5014c659cd87fddaf6854af428cfcTimo Sirainen
4b9f99761df5014c659cd87fddaf6854af428cfcTimo Sirainen    mail_index_buffer_convert_to_uids(t->view, t->expunges,
7e1f68ad71d3485f1882142837b01f7a98ca8467Timo Sirainen        sizeof(struct mail_transaction_expunge), TRUE);
68a4946b12583b88fa802e52ebee45cd96056772Timo Sirainen    mail_index_buffer_convert_to_uids(t->view, t->updates,
a3c197999dfe2b0c8ea38cb77cfa5e95026005c0Timo Sirainen        sizeof(struct mail_transaction_flag_update), TRUE);
a3c197999dfe2b0c8ea38cb77cfa5e95026005c0Timo Sirainen    mail_index_buffer_convert_to_uids(t->view, t->cache_updates,
923115fd382904fa13bb09bf307bf2835b52df60Timo Sirainen        sizeof(struct mail_transaction_cache_update), FALSE);
923115fd382904fa13bb09bf307bf2835b52df60Timo Sirainen    return 0;
923115fd382904fa13bb09bf307bf2835b52df60Timo Sirainen}
7e1f68ad71d3485f1882142837b01f7a98ca8467Timo Sirainen
89e195dfb5c4b0efd9b9f459771a4467674e5b1fTimo Sirainenint mail_index_transaction_commit(struct mail_index_transaction *t,
51e1a1c280ccb461a15827f7987d09cb9708b6e3Timo Sirainen                  uint32_t *log_file_seq_r,
51e1a1c280ccb461a15827f7987d09cb9708b6e3Timo Sirainen                  uoff_t *log_file_offset_r)
c0435c854a0e7246373b9752d163095cc4fbe985Timo Sirainen{
89e195dfb5c4b0efd9b9f459771a4467674e5b1fTimo Sirainen    int ret;
a0b6b441fc679e562e79be0fb2819ffc24ab5b74Timo Sirainen
a0b6b441fc679e562e79be0fb2819ffc24ab5b74Timo Sirainen    if (mail_index_view_is_inconsistent(t->view)) {
89e195dfb5c4b0efd9b9f459771a4467674e5b1fTimo Sirainen        mail_index_transaction_rollback(t);
6f08b98ac63c25b747120d0c8f8e319b4e26ab0fTimo Sirainen        return -1;
6f08b98ac63c25b747120d0c8f8e319b4e26ab0fTimo Sirainen    }
6f08b98ac63c25b747120d0c8f8e319b4e26ab0fTimo Sirainen
7e1f68ad71d3485f1882142837b01f7a98ca8467Timo Sirainen    if (t->cache_trans_ctx != NULL) {
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen        mail_cache_transaction_commit(t->cache_trans_ctx);
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen                t->cache_trans_ctx = NULL;
68a4946b12583b88fa802e52ebee45cd96056772Timo Sirainen    }
68a4946b12583b88fa802e52ebee45cd96056772Timo Sirainen
3785910c303507db5f629684e6dde2cc7f83668eTimo Sirainen    if (t->last_update.uid1 != 0)
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen        mail_index_transaction_add_last(t);
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen
68a4946b12583b88fa802e52ebee45cd96056772Timo Sirainen    if (mail_index_transaction_convert_to_uids(t) < 0)
c06f4017027263cf3a08becc551f5126409e2a83Timo Sirainen        ret = -1;
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen    else {
699fdc186f982f70d990820796eaa0f12133e27cTimo Sirainen        ret = mail_transaction_log_append(t, log_file_seq_r,
699fdc186f982f70d990820796eaa0f12133e27cTimo Sirainen                          log_file_offset_r);
699fdc186f982f70d990820796eaa0f12133e27cTimo Sirainen    }
c06f4017027263cf3a08becc551f5126409e2a83Timo Sirainen
c06f4017027263cf3a08becc551f5126409e2a83Timo Sirainen    mail_index_transaction_unref(t);
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen    return ret;
282a436a74d8835edb45cc019b1c916013013fd3Timo Sirainen}
282a436a74d8835edb45cc019b1c916013013fd3Timo Sirainen
282a436a74d8835edb45cc019b1c916013013fd3Timo Sirainenvoid mail_index_transaction_rollback(struct mail_index_transaction *t)
282a436a74d8835edb45cc019b1c916013013fd3Timo Sirainen{
282a436a74d8835edb45cc019b1c916013013fd3Timo Sirainen    if (t->cache_trans_ctx != NULL) {
ecc81625167ed96c04c02aa190a1ea5baa65b474Timo Sirainen        mail_cache_transaction_rollback(t->cache_trans_ctx);
                t->cache_trans_ctx = NULL;
    }
        mail_index_transaction_unref(t);
}

static void
mail_index_transaction_update_append_size(struct mail_index_transaction *t)
{
    buffer_t *new_buf;
    unsigned int new_record_size;
    const void *src;
    void *dest;
    size_t i, size;

    new_record_size = t->view->index->max_record_size;
    if (t->append_record_size == new_record_size)
        return;

    i_assert(t->append_record_size < new_record_size);

    if (t->append_record_size != 0) {
        /* resize the records in buffer */
        src = buffer_get_data(t->appends, &size);
        size /= t->append_record_size;

        new_buf = buffer_create_dynamic(default_pool,
                        (size + 10) * new_record_size,
                        (size_t)-1);
        for (i = 0; i < size; i++) {
            dest = buffer_append_space_unsafe(new_buf,
                              new_record_size);
            memcpy(dest, src, t->append_record_size);
            src = CONST_PTR_OFFSET(src, t->append_record_size);
        }
        buffer_free(t->appends);
        t->appends = new_buf;
    }

    t->append_record_size = new_record_size;
}

struct mail_index_record *
mail_index_transaction_lookup(struct mail_index_transaction *t, uint32_t seq)
{
    size_t pos;

    i_assert(seq >= t->first_new_seq && seq <= t->last_new_seq);

    mail_index_transaction_update_append_size(t);

    pos = (seq - t->first_new_seq) * t->append_record_size;
    return buffer_get_space_unsafe(t->appends, pos, t->append_record_size);
}

void mail_index_append(struct mail_index_transaction *t, uint32_t uid,
               uint32_t *seq_r)
{
        struct mail_index_record *rec;

    if (t->appends == NULL) {
        t->appends = buffer_create_dynamic(default_pool,
                           4096, (size_t)-1);
        t->append_record_size = t->view->index->max_record_size;
    }
    mail_index_transaction_update_append_size(t);

    /* sequence number is visible only inside given view,
       so let it generate it */
    if (t->last_new_seq != 0)
        *seq_r = ++t->last_new_seq;
    else
        *seq_r = t->last_new_seq = t->first_new_seq;

    rec = buffer_append_space_unsafe(t->appends, t->append_record_size);
    memset(rec, 0, t->append_record_size);
    rec->uid = uid;
}

void mail_index_append_assign_uids(struct mail_index_transaction *t,
                   uint32_t first_uid, uint32_t *next_uid_r)
{
        struct mail_index_record *rec, *end;
    size_t size;

    if (t->appends == NULL)
        return;

    rec = buffer_get_modifyable_data(t->appends, &size);
    end = PTR_OFFSET(rec, size);

    /* find the first mail with uid = 0 */
    while (rec != end) {
        if (rec->uid == 0)
            break;
        rec = PTR_OFFSET(rec, t->append_record_size);
    }

    while (rec != end) {
        i_assert(rec->uid == 0);
        rec->uid = first_uid++;
        rec = PTR_OFFSET(rec, t->append_record_size);
    }

    *next_uid_r = first_uid;
}

void mail_index_expunge(struct mail_index_transaction *t, uint32_t seq)
{
        struct mail_transaction_expunge exp, *data;
    unsigned int idx, left_idx, right_idx;
    size_t size;

    i_assert(seq > 0 && seq <= mail_index_view_get_message_count(t->view));

    exp.uid1 = exp.uid2 = seq;

    /* expunges is a sorted array of {seq1, seq2, ..}, .. */

    if (t->expunges == NULL) {
        t->expunges = buffer_create_dynamic(default_pool,
                            1024, (size_t)-1);
        buffer_append(t->expunges, &exp, sizeof(exp));
        return;
    }

    data = buffer_get_modifyable_data(t->expunges, &size);
    size /= sizeof(*data);
    i_assert(size > 0);

    /* quick checks */
    if (data[size-1].uid2 == seq-1) {
        /* grow last range */
        data[size-1].uid2 = seq;
        return;
    }
    if (data[size-1].uid2 < seq) {
        buffer_append(t->expunges, &exp, sizeof(exp));
        return;
    }
    if (data[0].uid1 == seq+1) {
        /* grow down first range */
        data[0].uid1 = seq;
        return;
    }
    if (data[0].uid1 > seq) {
        buffer_insert(t->expunges, 0, &exp, sizeof(exp));
        return;
    }

    /* somewhere in the middle, array is sorted so find it with
       binary search */
    idx = 0; left_idx = 0; right_idx = size;
    while (left_idx < right_idx) {
        idx = (left_idx + right_idx) / 2;

        if (data[idx].uid1 < seq)
            left_idx = idx+1;
        else if (data[idx].uid1 > seq)
            right_idx = idx;
        else
            break;
    }

    if (data[idx].uid2 < seq)
        idx++;

        /* idx == size couldn't happen because we already handle it above */
    i_assert(idx < size && data[idx].uid1 >= seq);

    if (data[idx].uid1 <= seq && data[idx].uid2 >= seq) {
        /* already expunged */
        return;
    }

    if (data[idx].uid1 == seq+1) {
        data[idx].uid1 = seq;
        if (idx > 0 && data[idx-1].uid2 == seq-1) {
            /* merge */
            data[idx-1].uid2 = data[idx].uid2;
            buffer_delete(t->expunges, idx * sizeof(*data),
                      sizeof(*data));
        }
    } else if (data[idx].uid2 == seq-1) {
        i_assert(idx+1 < size); /* already handled above */
        data[idx].uid2 = seq;
        if (data[idx+1].uid1 == seq+1) {
            /* merge */
            data[idx+1].uid1 = data[idx].uid1;
            buffer_delete(t->expunges, idx * sizeof(*data),
                      sizeof(*data));
        }
    } else {
        buffer_insert(t->expunges, idx * sizeof(*data),
                              &exp, sizeof(exp));
    }
}

static void mail_index_record_modify_flags(struct mail_index_record *rec,
                       enum modify_type modify_type,
                       enum mail_flags flags,
                       keywords_mask_t keywords)
{
    int i;

    switch (modify_type) {
    case MODIFY_REPLACE:
        rec->flags = flags;
        memcpy(rec->keywords, keywords, INDEX_KEYWORDS_BYTE_COUNT);
        break;
    case MODIFY_ADD:
        rec->flags |= flags;
        for (i = 0; i < INDEX_KEYWORDS_BYTE_COUNT; i++)
            rec->keywords[i] |= keywords[i];
        break;
    case MODIFY_REMOVE:
        rec->flags &= ~flags;
        for (i = 0; i < INDEX_KEYWORDS_BYTE_COUNT; i++)
            rec->keywords[i] &= ~keywords[i];
        break;
    }
}

#define IS_COMPATIBLE_UPDATE(t, modify_type, flags, keywords) \
    ((t)->last_update_modify_type == (modify_type) && \
     (t)->last_update.add_flags == (flags) && \
     memcmp((t)->last_update.add_keywords, keywords, \
            INDEX_KEYWORDS_BYTE_COUNT) == 0)

void mail_index_update_flags(struct mail_index_transaction *t, uint32_t seq,
                 enum modify_type modify_type,
                 enum mail_flags flags, keywords_mask_t keywords)
{
    struct mail_index_record *rec;

    if (seq >= t->first_new_seq) {
        /* just appended message, modify it directly */
                rec = mail_index_transaction_lookup(t, seq);
        mail_index_record_modify_flags(rec, modify_type,
                           flags, keywords);
        return;
    }

    i_assert(seq > 0 && seq <= mail_index_view_get_message_count(t->view));

    /* first get group updates into same structure. this allows faster
       updates if same mails have multiple flag updates during same
       transaction (eg. 1:10 +seen, 1:10 +deleted) */
    if (t->last_update.uid2 == seq-1) {
        if (t->last_update.uid1 != 0 &&
            IS_COMPATIBLE_UPDATE(t, modify_type, flags, keywords)) {
            t->last_update.uid2 = seq;
            return;
        }
    } else if (t->last_update.uid1 == seq+1) {
        if (t->last_update.uid1 != 0 &&
            IS_COMPATIBLE_UPDATE(t, modify_type, flags, keywords)) {
            t->last_update.uid1 = seq;
            return;
        }
    }

    if (t->last_update.uid1 != 0)
        mail_index_transaction_add_last(t);

    t->last_update_modify_type = modify_type;
    t->last_update.uid1 = t->last_update.uid2 = seq;
    t->last_update.add_flags = flags;
    memcpy(t->last_update.add_keywords, keywords,
           INDEX_KEYWORDS_BYTE_COUNT);
}

static void
mail_index_transaction_get_last(struct mail_index_transaction *t,
                struct mail_transaction_flag_update *update)
{
    int i;

    *update = t->last_update;
    switch (t->last_update_modify_type) {
    case MODIFY_REPLACE:
        /* remove_flags = ~add_flags */
        update->remove_flags =
            ~update->add_flags & MAIL_INDEX_FLAGS_MASK;
        for (i = 0; i < INDEX_KEYWORDS_BYTE_COUNT; i++)
            update->remove_keywords[i] = ~update->add_keywords[i];
        break;
    case MODIFY_ADD:
        /* already in add_flags */
        break;
    case MODIFY_REMOVE:
        /* add_flags -> remove_flags */
        update->remove_flags = update->add_flags;
        memcpy(&update->remove_keywords, &update->add_keywords,
               INDEX_KEYWORDS_BYTE_COUNT);
        update->add_flags = 0;
        memset(&update->add_keywords, 0, INDEX_KEYWORDS_BYTE_COUNT);
        break;
    }
}

static void mail_index_transaction_add_last(struct mail_index_transaction *t)
{
    struct mail_transaction_flag_update update, *data;
    unsigned int idx, left_idx, right_idx;
    uint32_t last;
    size_t size;

        mail_index_transaction_get_last(t, &update);

    if (t->updates == NULL) {
        t->updates = buffer_create_dynamic(default_pool,
                           4096, (size_t)-1);
    }

    data = buffer_get_modifyable_data(t->updates, &size);
    size /= sizeof(*data);

    /* find the nearest sequence from existing updates */
    idx = 0; left_idx = 0; right_idx = size;
    while (left_idx < right_idx) {
        idx = (left_idx + right_idx) / 2;

        if (data[idx].uid1 < update.uid1)
            left_idx = idx+1;
        else if (data[idx].uid1 > update.uid1)
            right_idx = idx;
        else
            break;
    }
    if (idx < size && data[idx].uid2 < update.uid1)
        idx++;

    i_assert(idx == size || data[idx].uid1 <= update.uid1);

    /* insert it into buffer, split it in multiple parts if needed
       to make sure the ordering stays the same */
    for (; idx < size; idx++) {
        if (data[idx].uid1 > update.uid2)
            break;

        /* partial */
        last = update.uid2;
        update.uid2 = data[idx].uid1-1;

        if (update.uid1 <= update.uid2) {
            buffer_insert(t->updates, idx * sizeof(update),
                      &update, sizeof(update));
            data = buffer_get_modifyable_data(t->updates, NULL);
            size++;
        }

        update.uid1 = update.uid2+1;
        update.uid2 = last;
    }

    buffer_insert(t->updates, idx * sizeof(update),
              &update, sizeof(update));
}

static int
mail_index_seq_buffer_lookup(buffer_t *buffer, uint32_t seq,
                 size_t record_size, size_t *pos_r)
{
    unsigned int idx, left_idx, right_idx;
    void *data;
    uint32_t full_record_size, *seq_p;
    size_t size;

    full_record_size = record_size + sizeof(seq);

    data = buffer_get_modifyable_data(buffer, &size);

    /* we're probably appending it, check */
    if (size == 0)
        idx = 0;
    else if (*((uint32_t *)PTR_OFFSET(data, size-full_record_size)) < seq)
        idx = size / full_record_size;
    else {
        idx = 0; left_idx = 0; right_idx = size / full_record_size;
        while (left_idx < right_idx) {
            idx = (left_idx + right_idx) / 2;

            seq_p = PTR_OFFSET(data, idx * full_record_size);
            if (*seq_p < seq)
                left_idx = idx+1;
            else if (*seq_p > seq)
                right_idx = idx;
            else {
                *pos_r = idx * full_record_size;
                return TRUE;
            }
        }
    }

    *pos_r = idx * full_record_size;
    return FALSE;
}

static int mail_index_update_seq_buffer(buffer_t **buffer, uint32_t seq,
                    const void *record, size_t record_size,
                    void *old_record)
{
    void *p;
    size_t pos;

    if (*buffer == NULL) {
        *buffer = buffer_create_dynamic(default_pool, 1024, (size_t)-1);
        buffer_append(*buffer, &seq, sizeof(seq));
        buffer_append(*buffer, record, record_size);
        return FALSE;
    }

    if (mail_index_seq_buffer_lookup(*buffer, seq, record_size, &pos)) {
        /* already there, update */
        p = buffer_get_space_unsafe(*buffer, pos + sizeof(seq),
                        record_size);
        if (old_record != NULL)
            memcpy(old_record, p, record_size);
        memcpy(p, record, record_size);
        return TRUE;
    } else {
        /* insert */
        buffer_copy(*buffer, pos + sizeof(seq) + record_size,
                *buffer, pos, (size_t)-1);
        buffer_write(*buffer, pos, &seq, sizeof(seq));
        buffer_write(*buffer, pos + sizeof(seq), record, record_size);
        return FALSE;
    }
}

static void
mail_index_transaction_reset_cache_updates(struct mail_index_transaction *t)
{
    struct mail_index_record *rec;
    uint32_t seq;

    if (t->last_cache_file_seq == 0)
        return;

    buffer_set_used_size(t->cache_updates, 0);

    if (t->first_new_seq != 0) {
        for (seq = t->first_new_seq; seq <= t->last_new_seq; seq++) {
            rec = mail_index_transaction_lookup(t, seq);
            rec->cache_offset = 0;
        }
    }
}

void mail_index_reset_cache(struct mail_index_transaction *t,
                uint32_t new_file_seq)
{
    mail_index_transaction_reset_cache_updates(t);
    t->new_cache_file_seq = new_file_seq;
        t->last_cache_file_seq = new_file_seq;
}

void mail_index_update_cache(struct mail_index_transaction *t, uint32_t seq,
                 uint32_t file_seq, uint32_t offset,
                 uint32_t *old_offset_r)
{
    struct mail_index_record *rec;

    if (file_seq > t->last_cache_file_seq) {
        mail_index_transaction_reset_cache_updates(t);
                t->last_cache_file_seq = file_seq;
    }

    if (seq >= t->first_new_seq) {
        /* just appended message, modify it directly */
        rec = mail_index_transaction_lookup(t, seq);
        *old_offset_r = rec->cache_offset;
        rec->cache_offset = offset;
    } else {
        if (!mail_index_update_seq_buffer(&t->cache_updates, seq,
                          &offset, sizeof(offset),
                          old_offset_r))
            *old_offset_r = 0;
    }
}

int mail_index_update_cache_lookup(struct mail_index_transaction *t,
                   uint32_t seq, uint32_t *offset_r)
{
    const void *p;
    size_t pos;

    if (t->cache_updates == NULL)
        return FALSE;

    if (!mail_index_seq_buffer_lookup(t->cache_updates, seq,
                      sizeof(*offset_r), &pos))
        return FALSE;

    p = buffer_get_data(t->cache_updates, NULL);
    memcpy(offset_r, CONST_PTR_OFFSET(p, pos + sizeof(*offset_r)),
           sizeof(*offset_r));
    return TRUE;
}

void mail_index_update_extra_rec(struct mail_index_transaction *t,
                 uint32_t seq, uint32_t data_id,
                 const void *data)
{
    struct mail_index *index = t->view->index;
    struct mail_index_record *rec;

    i_assert(data_id < index->extra_records_count);

    if (seq >= t->first_new_seq) {
        /* just appended message, modify it directly */
        /* FIXME: do data_id mapping conversion */
        rec = mail_index_transaction_lookup(t, seq);
        memcpy(PTR_OFFSET(rec, index->extra_records[data_id].offset),
               data, index->extra_records[data_id].size);
    } else {
        mail_index_update_seq_buffer(&t->extra_rec_updates[data_id],
            seq, data, index->extra_records[data_id].size, NULL);
    }
}

void mail_index_update_header(struct mail_index_transaction *t,
                  size_t offset, const void *data, size_t size)
{
    i_assert(offset < sizeof(t->hdr_change));
    i_assert(size <= sizeof(t->hdr_change) - offset);

    t->hdr_changed = TRUE;

    memcpy(t->hdr_change + offset, data, size);
    for (; size > 0; size--)
        t->hdr_mask[offset++] = 1;
}