--- a/src/lib-index/Makefile.am	Mon Jul 13 19:42:01 2009 -0400
+++ b/src/lib-index/Makefile.am	Mon Jul 13 19:54:28 2009 -0400
@@ -25,6 +25,7 @@
         mail-index-transaction-export.c \
         mail-index-transaction-finish.c \
         mail-index-transaction-sort-appends.c \
+        mail-index-transaction-update.c \
         mail-index-transaction-view.c \
         mail-index-strmap.c \
         mail-index-sync.c \
@@ -60,6 +61,7 @@
         mailbox-list-index-private.h
 
 test_programs = \
+	test-mail-index-transaction-update \
 	test-mail-transaction-log-append \
 	test-mail-transaction-log-view
 
@@ -70,6 +72,10 @@
 	../lib-test/libtest.la \
 	../lib/liblib.la
 
+test_mail_index_transaction_update_SOURCES = test-mail-index-transaction-update.c
+test_mail_index_transaction_update_LDADD = mail-index-transaction-update.lo $(test_libs)
+test_mail_index_transaction_update_DEPENDENCIES = mail-index-transaction-update.lo $(test_libs)
+
 test_mail_transaction_log_append_SOURCES = test-mail-transaction-log-append.c
 test_mail_transaction_log_append_LDADD = mail-transaction-log-append.lo $(test_libs)
 test_mail_transaction_log_append_DEPENDENCIES = mail-transaction-log-append.lo $(test_libs)

--- a/src/lib-index/mail-index-transaction-finish.c	Mon Jul 13 19:42:01 2009 -0400
+++ b/src/lib-index/mail-index-transaction-finish.c	Mon Jul 13 19:54:28 2009 -0400
@@ -338,7 +338,10 @@
 
 int mail_index_transaction_finish(struct mail_index_transaction *t)
 {
-	mail_index_transaction_sort_appends(t);
+	if (array_is_created(&t->appends)) {
+		mail_index_update_day_headers(t);
+		mail_index_transaction_sort_appends(t);
+	}
 	mail_index_transaction_finish_flag_updates(t);
 
 	if (array_is_created(&t->ext_reset_atomic) || t->max_modseq != 0) {

--- a/src/lib-index/mail-index-transaction-private.h	Mon Jul 13 19:42:01 2009 -0400
+++ b/src/lib-index/mail-index-transaction-private.h	Mon Jul 13 19:54:28 2009 -0400
@@ -101,10 +101,12 @@
 
 void mail_index_transaction_ref(struct mail_index_transaction *t);
 void mail_index_transaction_unref(struct mail_index_transaction **t);
+void mail_index_transaction_reset_v(struct mail_index_transaction *t);
 
 void mail_index_transaction_sort_appends(struct mail_index_transaction *t);
 uint32_t mail_index_transaction_get_next_uid(struct mail_index_transaction *t);
 void mail_index_transaction_set_log_updates(struct mail_index_transaction *t);
+void mail_index_update_day_headers(struct mail_index_transaction *t);
 
 unsigned int
 mail_index_transaction_get_flag_update_pos(struct mail_index_transaction *t,
@@ -115,5 +117,10 @@
 int mail_index_transaction_finish(struct mail_index_transaction *t);
 void mail_index_transaction_export(struct mail_index_transaction *t,
 				   struct mail_transaction_log_append_ctx *append_ctx);
+unsigned int
+mail_index_transaction_get_flag_update_pos(struct mail_index_transaction *t,
+					   unsigned int left_idx,
+					   unsigned int right_idx,
+					   uint32_t seq);
 
 #endif

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/lib-index/mail-index-transaction-update.c	Mon Jul 13 19:54:28 2009 -0400
@@ -0,0 +1,1013 @@
+/* Copyright (c) 2003-2009 Dovecot authors, see the included COPYING file */
+
+/* Inside transaction we keep messages stored in sequences in uid fields.
+   Before they're written to transaction log the sequences are changed to
+   UIDs. */
+
+#include "lib.h"
+#include "ioloop.h"
+#include "array.h"
+#include "mail-index-private.h"
+#include "mail-index-transaction-private.h"
+
+static bool
+mail_index_transaction_has_ext_changes(struct mail_index_transaction *t);
+
+struct mail_index_record *
+mail_index_transaction_lookup(struct mail_index_transaction *t, uint32_t seq)
+{
+	i_assert(seq >= t->first_new_seq && seq <= t->last_new_seq);
+
+	return array_idx_modifiable(&t->appends, seq - t->first_new_seq);
+}
+
+void mail_index_transaction_reset_v(struct mail_index_transaction *t)
+{
+	ARRAY_TYPE(seq_array) *recs;
+	struct mail_index_transaction_ext_hdr_update *ext_hdrs;
+	unsigned i, count;
+
+	if (array_is_created(&t->ext_rec_updates)) {
+		recs = array_get_modifiable(&t->ext_rec_updates, &count);
+		for (i = 0; i < count; i++) {
+			if (array_is_created(&recs[i]))
+				array_free(&recs[i]);
+		}
+		array_free(&t->ext_rec_updates);
+	}
+	if (array_is_created(&t->ext_rec_atomics)) {
+		recs = array_get_modifiable(&t->ext_rec_atomics, &count);
+		for (i = 0; i < count; i++) {
+			if (array_is_created(&recs[i]))
+				array_free(&recs[i]);
+		}
+		array_free(&t->ext_rec_atomics);
+	}
+	if (array_is_created(&t->ext_hdr_updates)) {
+		ext_hdrs = array_get_modifiable(&t->ext_hdr_updates, &count);
+		for (i = 0; i < count; i++) {
+			i_free(ext_hdrs[i].data);
+			i_free(ext_hdrs[i].mask);
+		}
+		array_free(&t->ext_hdr_updates);
+	}
+
+	if (array_is_created(&t->keyword_updates)) {
+		struct mail_index_transaction_keyword_update *u;
+
+		u = array_get_modifiable(&t->keyword_updates, &count);
+		for (i = 0; i < count; i++) {
+			if (array_is_created(&u[i].add_seq))
+				array_free(&u[i].add_seq);
+			if (array_is_created(&u[i].remove_seq))
+				array_free(&u[i].remove_seq);
+		}
+		array_free(&t->keyword_updates);
+	}
+	if (array_is_created(&t->keyword_resets))
+		array_free(&t->keyword_resets);
+
+	if (array_is_created(&t->appends))
+		array_free(&t->appends);
+	if (array_is_created(&t->expunges))
+		array_free(&t->expunges);
+	if (array_is_created(&t->updates))
+		array_free(&t->updates);
+	if (array_is_created(&t->ext_resizes))
+		array_free(&t->ext_resizes);
+	if (array_is_created(&t->ext_resets))
+		array_free(&t->ext_resets);
+	if (array_is_created(&t->ext_reset_ids))
+		array_free(&t->ext_reset_ids);
+	if (array_is_created(&t->ext_reset_atomic))
+		array_free(&t->ext_reset_atomic);
+
+	t->first_new_seq = mail_index_view_get_messages_count(t->view)+1;
+	t->last_new_seq = 0;
+	t->last_update_idx = 0;
+	t->min_flagupdate_seq = 0;
+	t->max_flagupdate_seq = 0;
+
+	memset(t->pre_hdr_mask, 0, sizeof(t->pre_hdr_mask));
+	memset(t->post_hdr_mask, 0, sizeof(t->post_hdr_mask));
+
+	t->appends_nonsorted = FALSE;
+	t->drop_unnecessary_flag_updates = FALSE;
+	t->pre_hdr_changed = FALSE;
+	t->post_hdr_changed = FALSE;
+	t->reset = FALSE;
+	t->log_updates = FALSE;
+	t->log_ext_updates = FALSE;
+}
+
+void mail_index_transaction_set_log_updates(struct mail_index_transaction *t)
+{
+	/* flag updates aren't included in log_updates */
+	t->log_updates = array_is_created(&t->appends) ||
+		array_is_created(&t->expunges) ||
+		array_is_created(&t->keyword_resets) ||
+		array_is_created(&t->keyword_updates) ||
+		t->pre_hdr_changed || t->post_hdr_changed;
+}
+
+void mail_index_update_day_headers(struct mail_index_transaction *t)
+{
+	struct mail_index_header hdr;
+	const struct mail_index_record *rec;
+	const int max_days = N_ELEMENTS(hdr.day_first_uid);
+	struct tm tm;
+	time_t stamp;
+	int i, days;
+
+	hdr = *mail_index_get_header(t->view);
+	rec = array_idx(&t->appends, 0);
+
+	/* get beginning of today */
+	tm = *localtime(&ioloop_time);
+	tm.tm_hour = 0;
+	tm.tm_min = 0;
+	tm.tm_sec = 0;
+	stamp = mktime(&tm);
+	i_assert(stamp != (time_t)-1);
+
+	if ((time_t)hdr.day_stamp >= stamp)
+		return;
+
+	/* get number of days since last message */
+	days = (stamp - hdr.day_stamp) / (3600*24);
+	if (days > max_days)
+		days = max_days;
+
+	/* @UNSAFE: move days forward and fill the missing days with old
+	   day_first_uid[0]. */
+	memmove(hdr.day_first_uid + days, hdr.day_first_uid, max_days - days);
+	for (i = 1; i < days; i++)
+		hdr.day_first_uid[i] = hdr.day_first_uid[0];
+
+	hdr.day_stamp = stamp;
+	hdr.day_first_uid[0] = rec->uid;
+
+	mail_index_update_header(t,
+		offsetof(struct mail_index_header, day_stamp),
+		&hdr.day_stamp, sizeof(hdr.day_stamp), FALSE);
+	mail_index_update_header(t,
+		offsetof(struct mail_index_header, day_first_uid),
+		hdr.day_first_uid, sizeof(hdr.day_first_uid), FALSE);
+}
+
+void mail_index_append(struct mail_index_transaction *t, uint32_t uid,
+		       uint32_t *seq_r)
+{
+        struct mail_index_record *rec;
+
+	i_assert(!t->no_appends);
+
+	t->log_updates = TRUE;
+
+	if (!array_is_created(&t->appends))
+		i_array_init(&t->appends, 32);
+
+	/* 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 = array_append_space(&t->appends);
+	if (uid != 0) {
+		rec->uid = uid;
+		if (!t->appends_nonsorted &&
+		    t->last_new_seq != t->first_new_seq) {
+			/* if previous record's UID is larger than this one,
+			   we'll have to sort the appends later */
+			rec = mail_index_transaction_lookup(t, *seq_r - 1);
+			if (rec->uid > uid)
+				t->appends_nonsorted = TRUE;
+			else if (rec->uid == uid)
+				i_panic("Duplicate UIDs added in transaction");
+		}
+		if (t->highest_append_uid < uid)
+			t->highest_append_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 *recs;
+	unsigned int i, count;
+
+	if (!array_is_created(&t->appends))
+		return;
+
+	i_assert(first_uid > t->highest_append_uid);
+
+	recs = array_get_modifiable(&t->appends, &count);
+	for (i = 0; i < count; i++) {
+		if (recs[i].uid == 0)
+			recs[i].uid = first_uid++;
+	}
+
+	*next_uid_r = first_uid;
+}
+
+static void
+mail_index_expunge_last_append_ext(ARRAY_TYPE(seq_array_array) *ext_updates,
+				   uint32_t seq)
+{
+	ARRAY_TYPE(seq_array) *seqs;
+	unsigned int i, count, idx;
+
+	if (!array_is_created(ext_updates))
+		return;
+
+	seqs = array_get_modifiable(ext_updates, &count);
+	for (i = 0; i < count; i++) {
+		if (array_is_created(&seqs[i]) &&
+		    mail_index_seq_array_lookup(&seqs[i], seq, &idx))
+			array_delete(&seqs[i], idx, 1);
+	}
+}
+
+static void
+mail_index_expunge_last_append(struct mail_index_transaction *t, uint32_t seq)
+{
+	struct mail_index_transaction_keyword_update *kw_updates;
+	unsigned int i, count;
+
+	i_assert(seq == t->last_new_seq);
+
+	/* remove extension updates */
+	mail_index_expunge_last_append_ext(&t->ext_rec_updates, seq);
+	mail_index_expunge_last_append_ext(&t->ext_rec_atomics, seq);
+	t->log_ext_updates = mail_index_transaction_has_ext_changes(t);
+
+	/* remove keywords */
+	if (array_is_created(&t->keyword_resets))
+		seq_range_array_remove(&t->keyword_resets, seq);
+	if (array_is_created(&t->keyword_updates)) {
+		kw_updates = array_get_modifiable(&t->keyword_updates, &count);
+		for (i = 0; i < count; i++) {
+			if (array_is_created(&kw_updates[i].add_seq)) {
+				seq_range_array_remove(&kw_updates[i].add_seq,
+						       seq);
+			}
+			if (array_is_created(&kw_updates[i].remove_seq)) {
+				seq_range_array_remove(
+					&kw_updates[i].remove_seq, seq);
+			}
+		}
+	}
+
+	/* and finally remove the append itself */
+	array_delete(&t->appends, seq - t->first_new_seq, 1);
+	t->last_new_seq--;
+	if (t->first_new_seq > t->last_new_seq) {
+		t->last_new_seq = 0;
+		t->appends_nonsorted = FALSE;
+		array_free(&t->appends);
+	}
+	mail_index_transaction_set_log_updates(t);
+}
+
+void mail_index_expunge(struct mail_index_transaction *t, uint32_t seq)
+{
+	i_assert(seq > 0);
+	if (seq >= t->first_new_seq) {
+		/* we can handle only the last append. otherwise we'd have to
+		   renumber sequences and that gets tricky. for now this is
+		   enough, since we typically want to expunge all the
+		   appends. */
+		mail_index_expunge_last_append(t, seq);
+	} else {
+		t->log_updates = TRUE;
+
+		/* expunges is a sorted array of {seq1, seq2, ..}, .. */
+		seq_range_array_add(&t->expunges, 128, seq);
+	}
+}
+
+static void update_minmax_flagupdate_seq(struct mail_index_transaction *t,
+					 uint32_t seq1, uint32_t seq2)
+{
+	if (t->min_flagupdate_seq == 0) {
+		t->min_flagupdate_seq = seq1;
+		t->max_flagupdate_seq = seq2;
+	} else {
+		if (t->min_flagupdate_seq > seq1)
+			t->min_flagupdate_seq = seq1;
+		if (t->max_flagupdate_seq < seq2)
+			t->max_flagupdate_seq = seq2;
+	}
+}
+
+unsigned int
+mail_index_transaction_get_flag_update_pos(struct mail_index_transaction *t,
+					   unsigned int left_idx,
+					   unsigned int right_idx,
+					   uint32_t seq)
+{
+	const struct mail_transaction_flag_update *updates;
+	unsigned int idx, count;
+
+	updates = array_get(&t->updates, &count);
+	i_assert(left_idx <= right_idx && right_idx <= count);
+
+	/* find the first update with either overlapping range,
+	   or the update which will come after our insert */
+	idx = left_idx;
+	while (left_idx < right_idx) {
+		idx = (left_idx + right_idx) / 2;
+
+		if (updates[idx].uid2 < seq)
+			left_idx = idx+1;
+		else if (updates[idx].uid1 > seq)
+			right_idx = idx;
+		else
+			break;
+	}
+	if (left_idx > idx)
+		idx++;
+	return idx;
+}
+
+static void
+mail_index_insert_flag_update(struct mail_index_transaction *t,
+			      struct mail_transaction_flag_update u,
+			      unsigned int idx)
+{
+	struct mail_transaction_flag_update *updates, tmp_update;
+	unsigned int count, first_idx, max;
+
+	updates = array_get_modifiable(&t->updates, &count);
+
+	/* overlapping ranges, split/merge them */
+	i_assert(idx == 0 || updates[idx-1].uid2 < u.uid1);
+	i_assert(idx == count || updates[idx].uid2 >= u.uid1);
+
+	/* first we'll just add the changes without trying to merge anything */
+	first_idx = idx;
+	for (; idx < count && u.uid2 >= updates[idx].uid1; idx++) {
+		i_assert(u.uid1 <= updates[idx].uid2);
+		if (u.uid1 != updates[idx].uid1 &&
+		    (updates[idx].add_flags != u.add_flags ||
+		     updates[idx].remove_flags != u.remove_flags)) {
+			if (u.uid1 < updates[idx].uid1) {
+				/* insert new update */
+				tmp_update = u;
+				tmp_update.uid2 = updates[idx].uid1 - 1;
+			} else {
+				/* split existing update from beginning */
+				tmp_update = updates[idx];
+				tmp_update.uid2 = u.uid1 - 1;
+				updates[idx].uid1 = u.uid1;
+			}
+
+			i_assert(tmp_update.uid1 <= tmp_update.uid2);
+			i_assert(updates[idx].uid1 <= updates[idx].uid2);
+
+			array_insert(&t->updates, idx, &tmp_update, 1);
+			updates = array_get_modifiable(&t->updates, &count);
+			idx++;
+		} else if (u.uid1 < updates[idx].uid1) {
+			updates[idx].uid1 = u.uid1;
+		}
+
+		if (u.uid2 < updates[idx].uid2 &&
+		    (updates[idx].add_flags != u.add_flags ||
+		     updates[idx].remove_flags != u.remove_flags)) {
+			/* split existing update from end */
+			tmp_update = updates[idx];
+			tmp_update.uid2 = u.uid2;
+			updates[idx].uid1 = u.uid2 + 1;
+
+			i_assert(tmp_update.uid1 <= tmp_update.uid2);
+			i_assert(updates[idx].uid1 <= updates[idx].uid2);
+
+			array_insert(&t->updates, idx, &tmp_update, 1);
+			updates = array_get_modifiable(&t->updates, &count);
+		}
+
+		updates[idx].add_flags =
+			(updates[idx].add_flags | u.add_flags) &
+			~u.remove_flags;
+		updates[idx].remove_flags =
+			(updates[idx].remove_flags | u.remove_flags) &
+			~u.add_flags;
+		u.uid1 = updates[idx].uid2 + 1;
+
+		if (updates[idx].add_flags == 0 &&
+		    updates[idx].remove_flags == 0) {
+			/* we can remove this update completely */
+			array_delete(&t->updates, idx, 1);
+			updates = array_get_modifiable(&t->updates, &count);
+		}
+
+		if (u.uid1 > u.uid2) {
+			/* break here before idx++ so last_update_idx is set
+			   correctly */
+			break;
+		}
+	}
+	i_assert(idx <= count);
+
+	if (u.uid1 <= u.uid2) {
+		i_assert(idx == 0 || updates[idx-1].uid2 < u.uid1);
+		i_assert(idx == count || updates[idx].uid1 > u.uid2);
+		array_insert(&t->updates, idx, &u, 1);
+	}
+	updates = array_get_modifiable(&t->updates, &count);
+	t->last_update_idx = idx == count ? count-1 : idx;
+
+	/* merge everything */
+	idx = first_idx == 0 ? 0 : first_idx - 1;
+	max = I_MIN(t->last_update_idx + 1, count);
+	for (; idx < max; ) {
+		if (updates[idx].uid2 + 1 == updates[idx+1].uid1 &&
+		    updates[idx].add_flags == updates[idx+1].add_flags &&
+		    updates[idx].remove_flags == updates[idx+1].remove_flags) {
+			/* merge */
+			updates[idx].uid2 = updates[idx+1].uid2;
+			array_delete(&t->updates, idx + 1, 1);
+			max--;
+			if (t->last_update_idx > idx)
+				t->last_update_idx--;
+			updates = array_get_modifiable(&t->updates, &count);
+		} else {
+			idx++;
+		}
+	}
+}
+
+static void mail_index_record_modify_flags(struct mail_index_record *rec,
+					   enum modify_type modify_type,
+					   enum mail_flags flags)
+{
+	switch (modify_type) {
+	case MODIFY_REPLACE:
+		rec->flags = flags;
+		break;
+	case MODIFY_ADD:
+		rec->flags |= flags;
+		break;
+	case MODIFY_REMOVE:
+		rec->flags &= ~flags;
+		break;
+	}
+}
+
+void mail_index_update_flags_range(struct mail_index_transaction *t,
+				   uint32_t seq1, uint32_t seq2,
+				   enum modify_type modify_type,
+				   enum mail_flags flags)
+{
+	struct mail_index_record *rec;
+	struct mail_transaction_flag_update u, *last_update;
+	unsigned int idx, first_idx, count;
+
+	update_minmax_flagupdate_seq(t, seq1, seq2);
+	if (seq2 >= t->first_new_seq) {
+		/* updates for appended messages, modify them directly */
+		uint32_t seq;
+
+		for (seq = I_MAX(t->first_new_seq, seq1); seq <= seq2; seq++) {
+			rec = mail_index_transaction_lookup(t, seq);
+			mail_index_record_modify_flags(rec, modify_type, flags);
+		}
+		if (seq1 >= t->first_new_seq)
+			return;
+
+		/* range contains also existing messages. update them next. */
+		seq2 = t->first_new_seq - 1;
+	}
+
+	i_assert(seq1 <= seq2 && seq1 > 0);
+	i_assert(seq2 <= mail_index_view_get_messages_count(t->view));
+
+	if ((t->flags & MAIL_INDEX_TRANSACTION_FLAG_AVOID_FLAG_UPDATES) != 0)
+		t->drop_unnecessary_flag_updates = TRUE;
+
+	memset(&u, 0, sizeof(u));
+	u.uid1 = seq1;
+	u.uid2 = seq2;
+
+	switch (modify_type) {
+	case MODIFY_REPLACE:
+		u.add_flags = flags;
+		u.remove_flags = ~flags & MAIL_INDEX_FLAGS_MASK;
+		break;
+	case MODIFY_ADD:
+		if (flags == 0)
+			return;
+		u.add_flags = flags;
+		break;
+	case MODIFY_REMOVE:
+		if (flags == 0)
+			return;
+		u.remove_flags = flags;
+		break;
+	}
+
+	if (!array_is_created(&t->updates)) {
+		i_array_init(&t->updates, 256);
+		array_append(&t->updates, &u, 1);
+		return;
+	}
+
+	last_update = array_get_modifiable(&t->updates, &count);
+	if (t->last_update_idx < count) {
+		/* fast path - hopefully we're updating the next message,
+		   or a message that is to be appended as last update */
+		last_update += t->last_update_idx;
+		if (seq1 - 1 == last_update->uid2) {
+			if (u.add_flags == last_update->add_flags &&
+			    u.remove_flags == last_update->remove_flags &&
+			    (t->last_update_idx + 1 == count ||
+			     last_update[1].uid1 > seq2)) {
+				/* we can just update the UID range */
+				last_update->uid2 = seq2;
+				return;
+			}
+		} else if (seq1 > last_update->uid2) {
+			/* hopefully we can just append it */
+			t->last_update_idx++;
+			last_update++;
+		}
+	}
+
+	if (t->last_update_idx == count)
+		array_append(&t->updates, &u, 1);
+	else {
+		i_assert(t->last_update_idx < count);
+
+		/* slow path */
+		if (seq1 > last_update->uid2) {
+			/* added after this */
+			first_idx = t->last_update_idx + 1;
+		} else {
+			/* added before this or on top of this */
+			first_idx = 0;
+			count = t->last_update_idx + 1;
+		}
+		idx = mail_index_transaction_get_flag_update_pos(t, first_idx,
+								 count, u.uid1);
+		mail_index_insert_flag_update(t, u, idx);
+	}
+}
+
+void mail_index_update_flags(struct mail_index_transaction *t, uint32_t seq,
+			     enum modify_type modify_type,
+			     enum mail_flags flags)
+{
+	mail_index_update_flags_range(t, seq, seq, modify_type, flags);
+}
+
+void mail_index_update_header(struct mail_index_transaction *t,
+			      size_t offset, const void *data, size_t size,
+			      bool prepend)
+{
+	i_assert(offset < sizeof(t->pre_hdr_change));
+	i_assert(size <= sizeof(t->pre_hdr_change) - offset);
+
+	t->log_updates = TRUE;
+
+	if (prepend) {
+		t->pre_hdr_changed = TRUE;
+		memcpy(t->pre_hdr_change + offset, data, size);
+		for (; size > 0; size--)
+			t->pre_hdr_mask[offset++] = 1;
+	} else {
+		t->post_hdr_changed = TRUE;
+		memcpy(t->post_hdr_change + offset, data, size);
+		for (; size > 0; size--)
+			t->post_hdr_mask[offset++] = 1;
+	}
+}
+
+void mail_index_ext_resize(struct mail_index_transaction *t, uint32_t ext_id,
+			   uint32_t hdr_size, uint16_t record_size,
+			   uint16_t record_align)
+{
+	struct mail_transaction_ext_intro intro;
+	uint32_t old_record_size, old_record_align;
+
+	memset(&intro, 0, sizeof(intro));
+
+	/* get ext_id from transaction's map if it's there */
+	if (!mail_index_map_get_ext_idx(t->view->map, ext_id, &intro.ext_id)) {
+		/* have to create it */
+		const struct mail_index_registered_ext *rext;
+
+		intro.ext_id = (uint32_t)-1;
+		rext = array_idx(&t->view->index->extensions, ext_id);
+		old_record_size = rext->record_size;
+		old_record_align = rext->record_align;
+	} else {
+		const struct mail_index_ext *ext;
+
+		ext = array_idx(&t->view->map->extensions, intro.ext_id);
+		old_record_size = ext->record_size;
+		old_record_align = ext->record_align;
+	}
+
+	/* allow only header size changes if extension records have already
+	   been changed in transaction */
+	i_assert(!array_is_created(&t->ext_rec_updates) ||
+		 (old_record_size == record_size &&
+		  old_record_align == record_align));
+
+	t->log_ext_updates = TRUE;
+
+	if (!array_is_created(&t->ext_resizes))
+		i_array_init(&t->ext_resizes, ext_id + 2);
+
+	intro.hdr_size = hdr_size;
+	intro.record_size = record_size;
+	intro.record_align = record_align;
+	intro.name_size = 1;
+	array_idx_set(&t->ext_resizes, ext_id, &intro);
+}
+
+void mail_index_ext_reset(struct mail_index_transaction *t, uint32_t ext_id,
+			  uint32_t reset_id, bool clear_data)
+{
+	struct mail_transaction_ext_reset reset;
+
+	i_assert(reset_id != 0);
+
+	memset(&reset, 0, sizeof(reset));
+	reset.new_reset_id = reset_id;
+	reset.preserve_data = !clear_data;
+
+	mail_index_ext_set_reset_id(t, ext_id, reset_id);
+
+	if (!array_is_created(&t->ext_resets))
+		i_array_init(&t->ext_resets, ext_id + 2);
+	array_idx_set(&t->ext_resets, ext_id, &reset);
+	t->log_ext_updates = TRUE;
+}
+
+void mail_index_ext_reset_inc(struct mail_index_transaction *t, uint32_t ext_id,
+			      uint32_t prev_reset_id, bool clear_data)
+{
+	uint32_t expected_reset_id = prev_reset_id + 1;
+
+	mail_index_ext_reset(t, ext_id, (uint32_t)-1, clear_data);
+
+	if (!array_is_created(&t->ext_reset_atomic))
+		i_array_init(&t->ext_reset_atomic, ext_id + 2);
+	array_idx_set(&t->ext_reset_atomic, ext_id, &expected_reset_id);
+}
+
+static bool
+mail_index_transaction_has_ext_updates(const ARRAY_TYPE(seq_array_array) *arr)
+{
+	const ARRAY_TYPE(seq_array) *array;
+	unsigned int i, count;
+
+	if (array_is_created(arr)) {
+		array = array_get(arr, &count);
+		for (i = 0; i < count; i++) {
+			if (array_is_created(&array[i]))
+				return TRUE;
+		}
+	}
+	return FALSE;
+}
+
+static bool
+mail_index_transaction_has_ext_changes(struct mail_index_transaction *t)
+{
+	unsigned int i, count;
+
+	if (mail_index_transaction_has_ext_updates(&t->ext_rec_updates))
+		return TRUE;
+	if (mail_index_transaction_has_ext_updates(&t->ext_rec_atomics))
+		return TRUE;
+
+	if (array_is_created(&t->ext_hdr_updates)) {
+		const struct mail_index_transaction_ext_hdr_update *hdr;
+
+		hdr = array_get(&t->ext_hdr_updates, &count);
+		for (i = 0; i < count; i++) {
+			if (hdr[i].alloc_size > 0)
+				return TRUE;
+		}
+	}
+	if (array_is_created(&t->ext_resets)) {
+		const struct mail_transaction_ext_reset *resets;
+
+		resets = array_get(&t->ext_resets, &count);
+		for (i = 0; i < count; i++) {
+			if (resets[i].new_reset_id != 0)
+				return TRUE;
+		}
+	}
+	if (array_is_created(&t->ext_resizes)) {
+		const struct mail_transaction_ext_intro *resizes;
+
+		resizes = array_get(&t->ext_resizes, &count);
+		for (i = 0; i < count; i++) {
+			if (resizes[i].name_size > 0)
+				return TRUE;
+		}
+	}
+	return FALSE;
+}
+
+static void
+mail_index_ext_update_reset(ARRAY_TYPE(seq_array_array) *arr, uint32_t ext_id)
+{
+	if (array_is_created(arr) && ext_id < array_count(arr)) {
+		/* if extension records have been updated, clear them */
+		ARRAY_TYPE(seq_array) *array;
+
+		array = array_idx_modifiable(arr, ext_id);
+		if (array_is_created(array))
+			array_clear(array);
+	}
+}
+
+void mail_index_ext_set_reset_id(struct mail_index_transaction *t,
+				 uint32_t ext_id, uint32_t reset_id)
+{
+	mail_index_ext_update_reset(&t->ext_rec_updates, ext_id);
+	mail_index_ext_update_reset(&t->ext_rec_atomics, ext_id);
+	if (array_is_created(&t->ext_hdr_updates) &&
+	    ext_id < array_count(&t->ext_hdr_updates)) {
+		/* if extension headers have been updated, clear them */
+		struct mail_index_transaction_ext_hdr_update *hdr;
+
+		hdr = array_idx_modifiable(&t->ext_hdr_updates, ext_id);
+		if (hdr->alloc_size > 0) {
+			i_free_and_null(hdr->mask);
+			i_free_and_null(hdr->data);
+		}
+		hdr->alloc_size = 0;
+	}
+	if (array_is_created(&t->ext_resets) &&
+	    ext_id < array_count(&t->ext_resets)) {
+		/* clear resets */
+		array_idx_clear(&t->ext_resets, ext_id);
+	}
+	if (array_is_created(&t->ext_resizes) &&
+	    ext_id < array_count(&t->ext_resizes)) {
+		/* clear resizes */
+		array_idx_clear(&t->ext_resizes, ext_id);
+	}
+
+	if (!array_is_created(&t->ext_reset_ids))
+		i_array_init(&t->ext_reset_ids, ext_id + 2);
+	array_idx_set(&t->ext_reset_ids, ext_id, &reset_id);
+
+	t->log_ext_updates = mail_index_transaction_has_ext_changes(t);
+}
+
+void mail_index_update_header_ext(struct mail_index_transaction *t,
+				  uint32_t ext_id, size_t offset,
+				  const void *data, size_t size)
+{
+	struct mail_index_transaction_ext_hdr_update *hdr;
+	size_t new_size;
+
+	i_assert(offset <= (uint16_t)-1 && size <= (uint16_t)-1 &&
+		 offset + size <= (uint16_t)-1);
+
+	if (!array_is_created(&t->ext_hdr_updates))
+		i_array_init(&t->ext_hdr_updates, ext_id + 2);
+
+	hdr = array_idx_modifiable(&t->ext_hdr_updates, ext_id);
+	if (hdr->alloc_size < offset || hdr->alloc_size - offset < size) {
+		i_assert(size < (size_t)-1 - offset);
+		new_size = nearest_power(offset + size);
+		hdr->mask = i_realloc(hdr->mask, hdr->alloc_size, new_size);
+		hdr->data = i_realloc(hdr->data, hdr->alloc_size, new_size);
+		hdr->alloc_size = new_size;
+	}
+	memset(hdr->mask + offset, 1, size);
+	memcpy(hdr->data + offset, data, size);
+
+	t->log_ext_updates = TRUE;
+}
+
+void mail_index_update_ext(struct mail_index_transaction *t, uint32_t seq,
+			   uint32_t ext_id, const void *data, void *old_data_r)
+{
+	struct mail_index *index = t->view->index;
+        const struct mail_index_registered_ext *rext;
+	const struct mail_transaction_ext_intro *intro;
+	uint16_t record_size;
+	ARRAY_TYPE(seq_array) *array;
+	unsigned int count;
+
+	i_assert(seq > 0 &&
+		 (seq <= mail_index_view_get_messages_count(t->view) ||
+		  seq <= t->last_new_seq));
+	i_assert(ext_id < array_count(&index->extensions));
+
+	t->log_ext_updates = TRUE;
+
+	if (!array_is_created(&t->ext_resizes)) {
+		intro = NULL;
+		count = 0;
+	} else {
+		intro = array_get(&t->ext_resizes, &count);
+	}
+	if (ext_id < count && intro[ext_id].name_size != 0) {
+		/* resized record */
+		record_size = intro[ext_id].record_size;
+	} else {
+		rext = array_idx(&index->extensions, ext_id);
+		record_size = rext->record_size;
+	}
+
+	if (!array_is_created(&t->ext_rec_updates))
+		i_array_init(&t->ext_rec_updates, ext_id + 2);
+	array = array_idx_modifiable(&t->ext_rec_updates, ext_id);
+
+	/* @UNSAFE */
+	if (!mail_index_seq_array_add(array, seq, data, record_size,
+				      old_data_r)) {
+		/* not found, clear old_data if it was given */
+		if (old_data_r != NULL)
+			memset(old_data_r, 0, record_size);
+	}
+}
+
+int mail_index_atomic_inc_ext(struct mail_index_transaction *t,
+			      uint32_t seq, uint32_t ext_id, int diff)
+{
+	ARRAY_TYPE(seq_array) *array;
+	int32_t old_diff32, diff32 = diff;
+
+	i_assert(seq > 0 &&
+		 (seq <= mail_index_view_get_messages_count(t->view) ||
+		  seq <= t->last_new_seq));
+	i_assert(ext_id < array_count(&t->view->index->extensions));
+	/* currently non-external transactions can be applied multiple times,
+	   causing multiple increments. */
+	//FIXME:i_assert((t->flags & MAIL_INDEX_TRANSACTION_FLAG_EXTERNAL) != 0);
+
+	t->log_ext_updates = TRUE;
+	if (!array_is_created(&t->ext_rec_atomics))
+		i_array_init(&t->ext_rec_atomics, ext_id + 2);
+	array = array_idx_modifiable(&t->ext_rec_atomics, ext_id);
+	if (mail_index_seq_array_add(array, seq, &diff32, sizeof(diff32),
+				     &old_diff32)) {
+		/* already incremented this sequence in this transaction */
+		diff32 += old_diff32;
+		mail_index_seq_array_add(array, seq, &diff32, sizeof(diff32),
+					 NULL);
+	}
+	return diff32;
+}
+
+static bool
+keyword_update_has_changes(struct mail_index_transaction *t, uint32_t seq,
+			   enum modify_type modify_type,
+			   struct mail_keywords *keywords)
+{
+	struct mail_index_transaction_keyword_update *u;
+	ARRAY_TYPE(keyword_indexes) existing;
+	const unsigned int *existing_idx;
+	unsigned int i, j, existing_count;
+	bool found;
+
+	t_array_init(&existing, 32);
+	if (seq < t->first_new_seq)
+		mail_index_lookup_keywords(t->view, seq, &existing);
+	existing_idx = array_get(&existing, &existing_count);
+
+	if (modify_type == MODIFY_REPLACE && existing_count != keywords->count)
+		return TRUE;
+
+	for (i = 0; i < keywords->count; i++) {
+		u = array_idx_modifiable(&t->keyword_updates,
+					 keywords->idx[i]);
+		if (array_is_created(&u->add_seq) ||
+		    array_is_created(&u->remove_seq))
+			return TRUE;
+
+		found = FALSE;
+		for (j = 0; j < existing_count; j++) {
+			if (existing_idx[j] == keywords->idx[i]) {
+				found = TRUE;
+				break;
+			}
+		}
+		switch (modify_type) {
+		case MODIFY_ADD:
+		case MODIFY_REPLACE:
+			if (!found)
+				return TRUE;
+			break;
+		case MODIFY_REMOVE:
+			if (found)
+				return TRUE;
+			break;
+		}
+	}
+	return FALSE;
+}
+
+void mail_index_update_keywords(struct mail_index_transaction *t, uint32_t seq,
+				enum modify_type modify_type,
+				struct mail_keywords *keywords)
+{
+	struct mail_index_transaction_keyword_update *u;
+	unsigned int i, ku_count;
+	bool changed;
+
+	i_assert(seq > 0 &&
+		 (seq <= mail_index_view_get_messages_count(t->view) ||
+		  seq <= t->last_new_seq));
+	i_assert(keywords->count > 0 || modify_type == MODIFY_REPLACE);
+	i_assert(keywords->index == t->view->index);
+
+	update_minmax_flagupdate_seq(t, seq, seq);
+
+	if (!array_is_created(&t->keyword_updates) && keywords->count > 0) {
+		uint32_t max_idx = keywords->idx[keywords->count-1];
+
+		i_array_init(&t->keyword_updates, max_idx + 1);
+	}
+
+	if ((t->flags & MAIL_INDEX_TRANSACTION_FLAG_AVOID_FLAG_UPDATES) != 0) {
+		T_BEGIN {
+			changed = keyword_update_has_changes(t, seq,
+							     modify_type,
+							     keywords);
+		} T_END;
+		if (!changed)
+			return;
+	}
+
+	/* Update add_seq and remove_seq arrays which describe the keyword
+	   changes. Don't bother updating remove_seq or keyword resets for
+	   newly added messages since they default to not having any
+	   keywords anyway. */
+	switch (modify_type) {
+	case MODIFY_ADD:
+		for (i = 0; i < keywords->count; i++) {
+			u = array_idx_modifiable(&t->keyword_updates,
+						 keywords->idx[i]);
+			seq_range_array_add(&u->add_seq, 16, seq);
+			seq_range_array_remove(&u->remove_seq, seq);
+		}
+		break;
+	case MODIFY_REMOVE:
+		for (i = 0; i < keywords->count; i++) {
+			u = array_idx_modifiable(&t->keyword_updates,
+						 keywords->idx[i]);
+			seq_range_array_remove(&u->add_seq, seq);
+			if (seq < t->first_new_seq)
+				seq_range_array_add(&u->remove_seq, 16, seq);
+		}
+		break;
+	case MODIFY_REPLACE:
+		/* Remove sequence from all add/remove arrays */
+		if (array_is_created(&t->keyword_updates)) {
+			u = array_get_modifiable(&t->keyword_updates,
+						 &ku_count);
+			for (i = 0; i < ku_count; i++) {
+				seq_range_array_remove(&u[i].add_seq, seq);
+				seq_range_array_remove(&u[i].remove_seq, seq);
+			}
+		}
+		/* Add the wanted keyword back */
+		for (i = 0; i < keywords->count; i++) {
+			u = array_idx_modifiable(&t->keyword_updates,
+						 keywords->idx[i]);
+			seq_range_array_add(&u->add_seq, 16, seq);
+		}
+
+		if (seq < t->first_new_seq)
+			seq_range_array_add(&t->keyword_resets, 16, seq);
+		break;
+	}
+
+	t->log_updates = TRUE;
+}
+
+void mail_index_transaction_reset(struct mail_index_transaction *t)
+{
+	t->v.reset(t);
+}
+
+void mail_index_reset(struct mail_index_transaction *t)
+{
+	mail_index_transaction_reset(t);
+
+	t->reset = TRUE;
+}
+
+void mail_index_transaction_set_max_modseq(struct mail_index_transaction *t,
+					   uint64_t max_modseq,
+					   ARRAY_TYPE(seq_range) *seqs)
+{
+	i_assert(array_is_created(seqs));
+
+	t->max_modseq = max_modseq;
+	t->conflict_seqs = seqs;
+}

--- a/src/lib-index/mail-index-transaction.c	Mon Jul 13 19:42:01 2009 -0400
+++ b/src/lib-index/mail-index-transaction.c	Mon Jul 13 19:54:28 2009 -0400
@@ -1,9 +1,5 @@
 /* Copyright (c) 2003-2009 Dovecot authors, see the included COPYING file */
 
-/* Inside transaction we keep messages stored in sequences in uid fields.
-   Before they're written to transaction log the sequences are changed to
-   UIDs. This is because we're able to compress sequence ranges better. */
-
 #include "lib.h"
 #include "ioloop.h"
 #include "array.h"
@@ -12,110 +8,11 @@
 #include "mail-transaction-log-private.h"
 #include "mail-index-transaction-private.h"
 
+#include <stdlib.h>
+
 void (*hook_mail_index_transaction_created)
 		(struct mail_index_transaction *t) = NULL;
 
-static bool
-mail_index_transaction_has_ext_changes(struct mail_index_transaction *t);
-
-static void mail_index_transaction_reset_v(struct mail_index_transaction *t)
-{
-	ARRAY_TYPE(seq_array) *recs;
-	struct mail_index_transaction_ext_hdr_update *ext_hdrs;
-	unsigned i, count;
-
-	if (array_is_created(&t->ext_rec_updates)) {
-		recs = array_get_modifiable(&t->ext_rec_updates, &count);
-		for (i = 0; i < count; i++) {
-			if (array_is_created(&recs[i]))
-				array_free(&recs[i]);
-		}
-		array_free(&t->ext_rec_updates);
-	}
-	if (array_is_created(&t->ext_rec_atomics)) {
-		recs = array_get_modifiable(&t->ext_rec_atomics, &count);
-		for (i = 0; i < count; i++) {
-			if (array_is_created(&recs[i]))
-				array_free(&recs[i]);
-		}
-		array_free(&t->ext_rec_atomics);
-	}
-	if (array_is_created(&t->ext_hdr_updates)) {
-		ext_hdrs = array_get_modifiable(&t->ext_hdr_updates, &count);
-		for (i = 0; i < count; i++) {
-			i_free(ext_hdrs[i].data);
-			i_free(ext_hdrs[i].mask);
-		}
-		array_free(&t->ext_hdr_updates);
-	}
-
-	if (array_is_created(&t->keyword_updates)) {
-		struct mail_index_transaction_keyword_update *u;
-
-		u = array_get_modifiable(&t->keyword_updates, &count);
-		for (i = 0; i < count; i++) {
-			if (array_is_created(&u[i].add_seq))
-				array_free(&u[i].add_seq);
-			if (array_is_created(&u[i].remove_seq))
-				array_free(&u[i].remove_seq);
-		}
-		array_free(&t->keyword_updates);
-	}
-	if (array_is_created(&t->keyword_resets))
-		array_free(&t->keyword_resets);
-
-	if (array_is_created(&t->appends))
-		array_free(&t->appends);
-	if (array_is_created(&t->expunges))
-		array_free(&t->expunges);
-	if (array_is_created(&t->updates))
-		array_free(&t->updates);
-	if (array_is_created(&t->ext_resizes))
-		array_free(&t->ext_resizes);
-	if (array_is_created(&t->ext_resets))
-		array_free(&t->ext_resets);
-	if (array_is_created(&t->ext_reset_ids))
-		array_free(&t->ext_reset_ids);
-	if (array_is_created(&t->ext_reset_atomic))
-		array_free(&t->ext_reset_atomic);
-
-	t->first_new_seq = mail_index_view_get_messages_count(t->view)+1;
-	t->last_new_seq = 0;
-	t->last_update_idx = 0;
-	t->min_flagupdate_seq = 0;
-	t->max_flagupdate_seq = 0;
-
-	memset(t->pre_hdr_mask, 0, sizeof(t->pre_hdr_mask));
-	memset(t->post_hdr_mask, 0, sizeof(t->post_hdr_mask));
-
-	t->appends_nonsorted = FALSE;
-	t->pre_hdr_changed = FALSE;
-	t->post_hdr_changed = FALSE;
-	t->reset = FALSE;
-	t->log_updates = FALSE;
-	t->log_ext_updates = FALSE;
-}
-
-void mail_index_transaction_set_log_updates(struct mail_index_transaction *t)
-{
-	/* flag updates aren't included in log_updates */
-	t->log_updates = array_is_created(&t->appends) ||
-		array_is_created(&t->expunges) ||
-		array_is_created(&t->keyword_resets) ||
-		array_is_created(&t->keyword_updates) ||
-		t->pre_hdr_changed || t->post_hdr_changed;
-}
-
-static void mail_index_transaction_free(struct mail_index_transaction *t)
-{
-	mail_index_transaction_reset(t);
-
-	array_free(&t->module_contexts);
-	mail_index_view_transaction_unref(t->view);
-	mail_index_view_close(&t->view);
-	i_free(t);
-}
-
 struct mail_index_view *
 mail_index_transaction_get_view(struct mail_index_transaction *t)
 {
@@ -139,8 +36,15 @@
 	struct mail_index_transaction *t = *_t;
 
 	*_t = NULL;
-	if (--t->refcount == 0)
-		mail_index_transaction_free(t);
+	if (--t->refcount > 0)
+		return;
+
+	mail_index_transaction_reset(t);
+
+	array_free(&t->module_contexts);
+	mail_index_view_transaction_unref(t->view);
+	mail_index_view_close(&t->view);
+	i_free(t);
 }
 
 uint32_t mail_index_transaction_get_next_uid(struct mail_index_transaction *t)
@@ -174,11 +78,6 @@
 	return next_uid;
 }
 
-void mail_index_transaction_reset(struct mail_index_transaction *t)
-{
-	t->v.reset(t);
-}
-
 static int
 mail_transaction_log_file_refresh(struct mail_index_transaction *t,
 				  struct mail_transaction_log_append_ctx *ctx)
@@ -243,52 +142,6 @@
 	return 0;
 }
 
-static void
-mail_index_update_day_headers(struct mail_index_transaction *t)
-{
-	struct mail_index_header hdr;
-	const struct mail_index_record *rec;
-	const int max_days = N_ELEMENTS(hdr.day_first_uid);
-	struct tm tm;
-	time_t stamp;
-	int i, days;
-
-	hdr = *mail_index_get_header(t->view);
-	rec = array_idx(&t->appends, 0);
-
-	/* get beginning of today */
-	tm = *localtime(&ioloop_time);
-	tm.tm_hour = 0;
-	tm.tm_min = 0;
-	tm.tm_sec = 0;
-	stamp = mktime(&tm);
-	i_assert(stamp != (time_t)-1);
-
-	if ((time_t)hdr.day_stamp >= stamp)
-		return;
-
-	/* get number of days since last message */
-	days = (stamp - hdr.day_stamp) / (3600*24);
-	if (days > max_days)
-		days = max_days;
-
-	/* @UNSAFE: move days forward and fill the missing days with old
-	   day_first_uid[0]. */
-	memmove(hdr.day_first_uid + days, hdr.day_first_uid, max_days - days);
-	for (i = 1; i < days; i++)
-		hdr.day_first_uid[i] = hdr.day_first_uid[0];
-
-	hdr.day_stamp = stamp;
-	hdr.day_first_uid[0] = rec->uid;
-
-	mail_index_update_header(t,
-		offsetof(struct mail_index_header, day_stamp),
-		&hdr.day_stamp, sizeof(hdr.day_stamp), FALSE);
-	mail_index_update_header(t,
-		offsetof(struct mail_index_header, day_first_uid),
-		hdr.day_first_uid, sizeof(hdr.day_first_uid), FALSE);
-}
-
 static int mail_index_transaction_commit_v(struct mail_index_transaction *t,
 					   uint32_t *log_file_seq_r,
 					   uoff_t *log_file_offset_r)
@@ -299,9 +152,6 @@
 	i_assert(t->first_new_seq >
 		 mail_index_view_get_messages_count(t->view));
 
-	if (array_is_created(&t->appends))
-		mail_index_update_day_headers(t);
-
 	if (!MAIL_INDEX_TRANSACTION_HAS_CHANGES(t) && !t->reset) {
 		/* nothing to append */
 		ret = 0;
@@ -364,873 +214,6 @@
 	t->v.rollback(t);
 }
 
-struct mail_index_record *
-mail_index_transaction_lookup(struct mail_index_transaction *t, uint32_t seq)
-{
-	i_assert(seq >= t->first_new_seq && seq <= t->last_new_seq);
-
-	return array_idx_modifiable(&t->appends, seq - t->first_new_seq);
-}
-
-void mail_index_append(struct mail_index_transaction *t, uint32_t uid,
-		       uint32_t *seq_r)
-{
-        struct mail_index_record *rec;
-
-	i_assert(!t->no_appends);
-
-	t->log_updates = TRUE;
-
-	if (!array_is_created(&t->appends))
-		i_array_init(&t->appends, 32);
-
-	/* 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 = array_append_space(&t->appends);
-	if (uid != 0) {
-		rec->uid = uid;
-		if (!t->appends_nonsorted &&
-		    t->last_new_seq != t->first_new_seq) {
-			/* if previous record's UID is larger than this one,
-			   we'll have to sort the appends later */
-			rec = mail_index_transaction_lookup(t, *seq_r - 1);
-			if (rec->uid > uid)
-				t->appends_nonsorted = TRUE;
-			else if (rec->uid == uid)
-				i_panic("Duplicate UIDs added in transaction");
-		}
-		if (t->highest_append_uid < uid)
-			t->highest_append_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 *recs;
-	unsigned int i, count;
-
-	i_assert(first_uid != 0);
-
-	if (!array_is_created(&t->appends))
-		return;
-
-	recs = array_get_modifiable(&t->appends, &count);
-
-	/* find the first mail with uid = 0 */
-	for (i = 0; i < count; i++) {
-		if (recs[i].uid == 0)
-			break;
-	}
-
-	for (; i < count; i++) {
-		i_assert(recs[i].uid == 0);
-		recs[i].uid = first_uid++;
-	}
-
-	*next_uid_r = first_uid;
-}
-
-static void
-mail_index_expunge_last_append_ext(ARRAY_TYPE(seq_array_array) *ext_updates,
-				   uint32_t seq)
-{
-	ARRAY_TYPE(seq_array) *seqs;
-	unsigned int i, count, idx;
-
-	if (!array_is_created(ext_updates))
-		return;
-
-	seqs = array_get_modifiable(ext_updates, &count);
-	for (i = 0; i < count; i++) {
-		if (array_is_created(&seqs[i]) &&
-		    mail_index_seq_array_lookup(&seqs[i], seq, &idx))
-			array_delete(&seqs[i], idx, 1);
-	}
-}
-
-static void
-mail_index_expunge_last_append(struct mail_index_transaction *t, uint32_t seq)
-{
-	struct mail_index_transaction_keyword_update *kw_updates;
-	unsigned int i, count;
-
-	i_assert(seq == t->last_new_seq);
-
-	/* remove extension updates */
-	mail_index_expunge_last_append_ext(&t->ext_rec_updates, seq);
-	mail_index_expunge_last_append_ext(&t->ext_rec_atomics, seq);
-	t->log_ext_updates = mail_index_transaction_has_ext_changes(t);
-
-	/* remove keywords */
-	if (array_is_created(&t->keyword_resets))
-		seq_range_array_remove(&t->keyword_resets, seq);
-	if (array_is_created(&t->keyword_updates)) {
-		kw_updates = array_get_modifiable(&t->keyword_updates, &count);
-		for (i = 0; i < count; i++) {
-			if (array_is_created(&kw_updates[i].add_seq)) {
-				seq_range_array_remove(&kw_updates[i].add_seq,
-						       seq);
-			}
-			if (array_is_created(&kw_updates[i].remove_seq)) {
-				seq_range_array_remove(
-					&kw_updates[i].remove_seq, seq);
-			}
-		}
-	}
-
-	/* and finally remove the append itself */
-	array_delete(&t->appends, seq - t->first_new_seq, 1);
-	t->last_new_seq--;
-	if (t->first_new_seq > t->last_new_seq) {
-		t->last_new_seq = 0;
-		t->appends_nonsorted = FALSE;
-		array_free(&t->appends);
-	}
-	mail_index_transaction_set_log_updates(t);
-}
-
-void mail_index_expunge(struct mail_index_transaction *t, uint32_t seq)
-{
-	i_assert(seq > 0);
-	if (seq >= t->first_new_seq) {
-		/* we can handle only the last append. otherwise we'd have to
-		   renumber sequences and that gets tricky. for now this is
-		   enough, since we typically want to expunge all the
-		   appends. */
-		mail_index_expunge_last_append(t, seq);
-	} else {
-		t->log_updates = TRUE;
-
-		/* expunges is a sorted array of {seq1, seq2, ..}, .. */
-		seq_range_array_add(&t->expunges, 128, seq);
-	}
-}
-
-static void update_minmax_flagupdate_seq(struct mail_index_transaction *t,
-					 uint32_t seq1, uint32_t seq2)
-{
-	if (t->min_flagupdate_seq == 0) {
-		t->min_flagupdate_seq = seq1;
-		t->max_flagupdate_seq = seq2;
-	} else {
-		if (t->min_flagupdate_seq > seq1)
-			t->min_flagupdate_seq = seq1;
-		if (t->max_flagupdate_seq < seq2)
-			t->max_flagupdate_seq = seq2;
-	}
-}
-
-unsigned int
-mail_index_transaction_get_flag_update_pos(struct mail_index_transaction *t,
-					   unsigned int left_idx,
-					   unsigned int right_idx,
-					   uint32_t seq)
-{
-	const struct mail_transaction_flag_update *updates;
-	unsigned int idx, count;
-
-	updates = array_get(&t->updates, &count);
-	i_assert(left_idx <= right_idx && right_idx <= count);
-
-	/* find the first update with either overlapping range,
-	   or the update which will come after our insert */
-	idx = left_idx;
-	while (left_idx < right_idx) {
-		idx = (left_idx + right_idx) / 2;
-
-		if (updates[idx].uid2 < seq)
-			left_idx = idx+1;
-		else if (updates[idx].uid1 > seq)
-			right_idx = idx;
-		else
-			break;
-	}
-	if (left_idx > idx)
-		idx++;
-	return idx;
-}
-
-static void
-mail_index_insert_flag_update(struct mail_index_transaction *t,
-			      struct mail_transaction_flag_update u,
-			      unsigned int idx)
-{
-	struct mail_transaction_flag_update *updates, tmp_update;
-	unsigned int count, first_idx, max;
-
-	updates = array_get_modifiable(&t->updates, &count);
-
-	/* overlapping ranges, split/merge them */
-	i_assert(idx == 0 || updates[idx-1].uid2 < u.uid1);
-	i_assert(idx == count || updates[idx].uid2 >= u.uid1);
-
-	/* first we'll just add the changes without trying to merge anything */
-	first_idx = idx;
-	for (; idx < count && u.uid2 >= updates[idx].uid1; idx++) {
-		i_assert(u.uid1 <= updates[idx].uid2);
-		if (u.uid1 != updates[idx].uid1 &&
-		    (updates[idx].add_flags != u.add_flags ||
-		     updates[idx].remove_flags != u.remove_flags)) {
-			if (u.uid1 < updates[idx].uid1) {
-				/* insert new update */
-				tmp_update = u;
-				tmp_update.uid2 = updates[idx].uid1 - 1;
-			} else {
-				/* split existing update from beginning */
-				tmp_update = updates[idx];
-				tmp_update.uid2 = u.uid1 - 1;
-				updates[idx].uid1 = u.uid1;
-			}
-
-			i_assert(tmp_update.uid1 <= tmp_update.uid2);
-			i_assert(updates[idx].uid1 <= updates[idx].uid2);
-
-			array_insert(&t->updates, idx, &tmp_update, 1);
-			updates = array_get_modifiable(&t->updates, &count);
-			idx++;
-		} else if (u.uid1 < updates[idx].uid1) {
-			updates[idx].uid1 = u.uid1;
-		}
-
-		if (u.uid2 < updates[idx].uid2 &&
-		    (updates[idx].add_flags != u.add_flags ||
-		     updates[idx].remove_flags != u.remove_flags)) {
-			/* split existing update from end */
-			tmp_update = updates[idx];
-			tmp_update.uid2 = u.uid2;
-			updates[idx].uid1 = u.uid2 + 1;
-
-			i_assert(tmp_update.uid1 <= tmp_update.uid2);
-			i_assert(updates[idx].uid1 <= updates[idx].uid2);
-
-			array_insert(&t->updates, idx, &tmp_update, 1);
-			updates = array_get_modifiable(&t->updates, &count);
-		}
-
-		updates[idx].add_flags =
-			(updates[idx].add_flags | u.add_flags) &
-			~u.remove_flags;
-		updates[idx].remove_flags =
-			(updates[idx].remove_flags | u.remove_flags) &
-			~u.add_flags;
-		u.uid1 = updates[idx].uid2 + 1;
-
-		if (updates[idx].add_flags == 0 &&
-		    updates[idx].remove_flags == 0) {
-			/* we can remove this update completely */
-			array_delete(&t->updates, idx, 1);
-			updates = array_get_modifiable(&t->updates, &count);
-		}
-
-		if (u.uid1 > u.uid2) {
-			/* break here before idx++ so last_update_idx is set
-			   correctly */
-			break;
-		}
-	}
-	i_assert(idx <= count);
-
-	if (u.uid1 <= u.uid2) {
-		i_assert(idx == 0 || updates[idx-1].uid2 < u.uid1);
-		i_assert(idx == count || updates[idx].uid1 > u.uid2);
-		array_insert(&t->updates, idx, &u, 1);
-	}
-	updates = array_get_modifiable(&t->updates, &count);
-	t->last_update_idx = idx == count ? count-1 : idx;
-
-	/* merge everything */
-	idx = first_idx == 0 ? 0 : first_idx - 1;
-	max = I_MIN(t->last_update_idx + 1, count);
-	for (; idx < max; ) {
-		if (updates[idx].uid2 + 1 == updates[idx+1].uid1 &&
-		    updates[idx].add_flags == updates[idx+1].add_flags &&
-		    updates[idx].remove_flags == updates[idx+1].remove_flags) {
-			/* merge */
-			updates[idx].uid2 = updates[idx+1].uid2;
-			array_delete(&t->updates, idx + 1, 1);
-			max--;
-			if (t->last_update_idx > idx)
-				t->last_update_idx--;
-			updates = array_get_modifiable(&t->updates, &count);
-		} else {
-			idx++;
-		}
-	}
-}
-
-static void mail_index_record_modify_flags(struct mail_index_record *rec,
-					   enum modify_type modify_type,
-					   enum mail_flags flags)
-{
-	switch (modify_type) {
-	case MODIFY_REPLACE:
-		rec->flags = flags;
-		break;
-	case MODIFY_ADD:
-		rec->flags |= flags;
-		break;
-	case MODIFY_REMOVE:
-		rec->flags &= ~flags;
-		break;
-	}
-}
-
-void mail_index_update_flags_range(struct mail_index_transaction *t,
-				   uint32_t seq1, uint32_t seq2,
-				   enum modify_type modify_type,
-				   enum mail_flags flags)
-{
-	struct mail_index_record *rec;
-	struct mail_transaction_flag_update u, *last_update;
-	unsigned int idx, first_idx, count;
-
-	update_minmax_flagupdate_seq(t, seq1, seq2);
-	if (seq2 >= t->first_new_seq) {
-		/* updates for appended messages, modify them directly */
-		uint32_t seq;
-
-		for (seq = I_MAX(t->first_new_seq, seq1); seq <= seq2; seq++) {
-			rec = mail_index_transaction_lookup(t, seq);
-			mail_index_record_modify_flags(rec, modify_type, flags);
-		}
-		if (seq1 >= t->first_new_seq)
-			return;
-
-		/* range contains also existing messages. update them next. */
-		seq2 = t->first_new_seq - 1;
-	}
-
-	i_assert(seq1 <= seq2 && seq1 > 0);
-	i_assert(seq2 <= mail_index_view_get_messages_count(t->view));
-
-	if ((t->flags & MAIL_INDEX_TRANSACTION_FLAG_AVOID_FLAG_UPDATES) != 0)
-		t->drop_unnecessary_flag_updates = TRUE;
-
-	memset(&u, 0, sizeof(u));
-	u.uid1 = seq1;
-	u.uid2 = seq2;
-
-	switch (modify_type) {
-	case MODIFY_REPLACE:
-		u.add_flags = flags;
-		u.remove_flags = ~flags & MAIL_INDEX_FLAGS_MASK;
-		break;
-	case MODIFY_ADD:
-		if (flags == 0)
-			return;
-		u.add_flags = flags;
-		break;
-	case MODIFY_REMOVE:
-		if (flags == 0)
-			return;
-		u.remove_flags = flags;
-		break;
-	}
-
-	if (!array_is_created(&t->updates)) {
-		i_array_init(&t->updates, 256);
-		array_append(&t->updates, &u, 1);
-		return;
-	}
-
-	last_update = array_get_modifiable(&t->updates, &count);
-	if (t->last_update_idx < count) {
-		/* fast path - hopefully we're updating the next message,
-		   or a message that is to be appended as last update */
-		last_update += t->last_update_idx;
-		if (seq1 - 1 == last_update->uid2) {
-			if (u.add_flags == last_update->add_flags &&
-			    u.remove_flags == last_update->remove_flags &&
-			    (t->last_update_idx + 1 == count ||
-			     last_update[1].uid1 > seq2)) {
-				/* we can just update the UID range */
-				last_update->uid2 = seq2;
-				return;
-			}
-		} else if (seq1 > last_update->uid2) {
-			/* hopefully we can just append it */
-			t->last_update_idx++;
-			last_update++;
-		}
-	}
-
-	if (t->last_update_idx == count)
-		array_append(&t->updates, &u, 1);
-	else {
-		i_assert(t->last_update_idx < count);
-
-		/* slow path */
-		if (seq1 > last_update->uid2) {
-			/* added after this */
-			first_idx = t->last_update_idx + 1;
-		} else {
-			/* added before this or on top of this */
-			first_idx = 0;
-			count = t->last_update_idx + 1;
-		}
-		idx = mail_index_transaction_get_flag_update_pos(t, first_idx,
-								 count, u.uid1);
-		mail_index_insert_flag_update(t, u, idx);
-	}
-}
-
-void mail_index_update_flags(struct mail_index_transaction *t, uint32_t seq,
-			     enum modify_type modify_type,
-			     enum mail_flags flags)
-{
-	mail_index_update_flags_range(t, seq, seq, modify_type, flags);
-}
-
-void mail_index_update_header(struct mail_index_transaction *t,
-			      size_t offset, const void *data, size_t size,
-			      bool prepend)
-{
-	i_assert(offset < sizeof(t->pre_hdr_change));
-	i_assert(size <= sizeof(t->pre_hdr_change) - offset);
-
-	t->log_updates = TRUE;
-
-	if (prepend) {
-		t->pre_hdr_changed = TRUE;
-		memcpy(t->pre_hdr_change + offset, data, size);
-		for (; size > 0; size--)
-			t->pre_hdr_mask[offset++] = 1;
-	} else {
-		t->post_hdr_changed = TRUE;
-		memcpy(t->post_hdr_change + offset, data, size);
-		for (; size > 0; size--)
-			t->post_hdr_mask[offset++] = 1;
-	}
-}
-
-void mail_index_ext_resize(struct mail_index_transaction *t, uint32_t ext_id,
-			   uint32_t hdr_size, uint16_t record_size,
-			   uint16_t record_align)
-{
-	struct mail_transaction_ext_intro intro;
-	uint32_t old_record_size, old_record_align;
-
-	memset(&intro, 0, sizeof(intro));
-
-	/* get ext_id from transaction's map if it's there */
-	if (!mail_index_map_get_ext_idx(t->view->map, ext_id, &intro.ext_id)) {
-		/* have to create it */
-		const struct mail_index_registered_ext *rext;
-
-		intro.ext_id = (uint32_t)-1;
-		rext = array_idx(&t->view->index->extensions, ext_id);
-		old_record_size = rext->record_size;
-		old_record_align = rext->record_align;
-	} else {
-		const struct mail_index_ext *ext;
-
-		ext = array_idx(&t->view->map->extensions, intro.ext_id);
-		old_record_size = ext->record_size;
-		old_record_align = ext->record_align;
-	}
-
-	/* allow only header size changes if extension records have already
-	   been changed in transaction */
-	i_assert(!array_is_created(&t->ext_rec_updates) ||
-		 (old_record_size == record_size &&
-		  old_record_align == record_align));
-
-	t->log_ext_updates = TRUE;
-
-	if (!array_is_created(&t->ext_resizes))
-		i_array_init(&t->ext_resizes, ext_id + 2);
-
-	intro.hdr_size = hdr_size;
-	intro.record_size = record_size;
-	intro.record_align = record_align;
-	intro.name_size = 1;
-	array_idx_set(&t->ext_resizes, ext_id, &intro);
-}
-
-void mail_index_ext_reset(struct mail_index_transaction *t, uint32_t ext_id,
-			  uint32_t reset_id, bool clear_data)
-{
-	struct mail_transaction_ext_reset reset;
-
-	i_assert(reset_id != 0);
-
-	memset(&reset, 0, sizeof(reset));
-	reset.new_reset_id = reset_id;
-	reset.preserve_data = !clear_data;
-
-	mail_index_ext_set_reset_id(t, ext_id, reset_id);
-
-	if (!array_is_created(&t->ext_resets))
-		i_array_init(&t->ext_resets, ext_id + 2);
-	array_idx_set(&t->ext_resets, ext_id, &reset);
-	t->log_ext_updates = TRUE;
-}
-
-void mail_index_ext_reset_inc(struct mail_index_transaction *t, uint32_t ext_id,
-			      uint32_t prev_reset_id, bool clear_data)
-{
-	uint32_t expected_reset_id = prev_reset_id + 1;
-
-	mail_index_ext_reset(t, ext_id, (uint32_t)-1, clear_data);
-
-	if (!array_is_created(&t->ext_reset_atomic))
-		i_array_init(&t->ext_reset_atomic, ext_id + 2);
-	array_idx_set(&t->ext_reset_atomic, ext_id, &expected_reset_id);
-}
-
-static bool
-mail_index_transaction_has_ext_updates(const ARRAY_TYPE(seq_array_array) *arr)
-{
-	const ARRAY_TYPE(seq_array) *array;
-	unsigned int i, count;
-
-	if (array_is_created(arr)) {
-		array = array_get(arr, &count);
-		for (i = 0; i < count; i++) {
-			if (array_is_created(&array[i]))
-				return TRUE;
-		}
-	}
-	return FALSE;
-}
-
-static bool
-mail_index_transaction_has_ext_changes(struct mail_index_transaction *t)
-{
-	unsigned int i, count;
-
-	if (mail_index_transaction_has_ext_updates(&t->ext_rec_updates))
-		return TRUE;
-	if (mail_index_transaction_has_ext_updates(&t->ext_rec_atomics))
-		return TRUE;
-
-	if (array_is_created(&t->ext_hdr_updates)) {
-		const struct mail_index_transaction_ext_hdr_update *hdr;
-
-		hdr = array_get(&t->ext_hdr_updates, &count);
-		for (i = 0; i < count; i++) {
-			if (hdr[i].alloc_size > 0)
-				return TRUE;
-		}
-	}
-	if (array_is_created(&t->ext_resets)) {
-		const struct mail_transaction_ext_reset *resets;
-
-		resets = array_get(&t->ext_resets, &count);
-		for (i = 0; i < count; i++) {
-			if (resets[i].new_reset_id != 0)
-				return TRUE;
-		}
-	}
-	if (array_is_created(&t->ext_resizes)) {
-		const struct mail_transaction_ext_intro *resizes;
-
-		resizes = array_get(&t->ext_resizes, &count);
-		for (i = 0; i < count; i++) {
-			if (resizes[i].name_size > 0)
-				return TRUE;
-		}
-	}
-	return FALSE;
-}
-
-static void
-mail_index_ext_update_reset(ARRAY_TYPE(seq_array_array) *arr, uint32_t ext_id)
-{
-	if (array_is_created(arr) && ext_id < array_count(arr)) {
-		/* if extension records have been updated, clear them */
-		ARRAY_TYPE(seq_array) *array;
-
-		array = array_idx_modifiable(arr, ext_id);
-		if (array_is_created(array))
-			array_clear(array);
-	}
-}
-
-void mail_index_ext_set_reset_id(struct mail_index_transaction *t,
-				 uint32_t ext_id, uint32_t reset_id)
-{
-	mail_index_ext_update_reset(&t->ext_rec_updates, ext_id);
-	mail_index_ext_update_reset(&t->ext_rec_atomics, ext_id);
-	if (array_is_created(&t->ext_hdr_updates) &&
-	    ext_id < array_count(&t->ext_hdr_updates)) {
-		/* if extension headers have been updated, clear them */
-		struct mail_index_transaction_ext_hdr_update *hdr;
-
-		hdr = array_idx_modifiable(&t->ext_hdr_updates, ext_id);
-		if (hdr->alloc_size > 0) {
-			i_free_and_null(hdr->mask);
-			i_free_and_null(hdr->data);
-		}
-		hdr->alloc_size = 0;
-	}
-	if (array_is_created(&t->ext_resets) &&
-	    ext_id < array_count(&t->ext_resets)) {
-		/* clear resets */
-		array_idx_clear(&t->ext_resets, ext_id);
-	}
-	if (array_is_created(&t->ext_resizes) &&
-	    ext_id < array_count(&t->ext_resizes)) {
-		/* clear resizes */
-		array_idx_clear(&t->ext_resizes, ext_id);
-	}
-
-	if (!array_is_created(&t->ext_reset_ids))
-		i_array_init(&t->ext_reset_ids, ext_id + 2);
-	array_idx_set(&t->ext_reset_ids, ext_id, &reset_id);
-
-	t->log_ext_updates = mail_index_transaction_has_ext_changes(t);
-}
-
-void mail_index_update_header_ext(struct mail_index_transaction *t,
-				  uint32_t ext_id, size_t offset,
-				  const void *data, size_t size)
-{
-	struct mail_index_transaction_ext_hdr_update *hdr;
-	size_t new_size;
-
-	i_assert(offset <= (uint16_t)-1 && size <= (uint16_t)-1 &&
-		 offset + size <= (uint16_t)-1);
-
-	if (!array_is_created(&t->ext_hdr_updates))
-		i_array_init(&t->ext_hdr_updates, ext_id + 2);
-
-	hdr = array_idx_modifiable(&t->ext_hdr_updates, ext_id);
-	if (hdr->alloc_size < offset || hdr->alloc_size - offset < size) {
-		i_assert(size < (size_t)-1 - offset);
-		new_size = nearest_power(offset + size);
-		hdr->mask = i_realloc(hdr->mask, hdr->alloc_size, new_size);
-		hdr->data = i_realloc(hdr->data, hdr->alloc_size, new_size);
-		hdr->alloc_size = new_size;
-	}
-	memset(hdr->mask + offset, 1, size);
-	memcpy(hdr->data + offset, data, size);
-
-	t->log_ext_updates = TRUE;
-}
-
-void mail_index_update_ext(struct mail_index_transaction *t, uint32_t seq,
-			   uint32_t ext_id, const void *data, void *old_data_r)
-{
-	struct mail_index *index = t->view->index;
-        const struct mail_index_registered_ext *rext;
-	const struct mail_transaction_ext_intro *intro;
-	uint16_t record_size;
-	ARRAY_TYPE(seq_array) *array;
-	unsigned int count;
-
-	i_assert(seq > 0 &&
-		 (seq <= mail_index_view_get_messages_count(t->view) ||
-		  seq <= t->last_new_seq));
-	i_assert(ext_id < array_count(&index->extensions));
-
-	t->log_ext_updates = TRUE;
-
-	if (!array_is_created(&t->ext_resizes)) {
-		intro = NULL;
-		count = 0;
-	} else {
-		intro = array_get(&t->ext_resizes, &count);
-	}
-	if (ext_id < count && intro[ext_id].name_size != 0) {
-		/* resized record */
-		record_size = intro[ext_id].record_size;
-	} else {
-		rext = array_idx(&index->extensions, ext_id);
-		record_size = rext->record_size;
-	}
-
-	if (!array_is_created(&t->ext_rec_updates))
-		i_array_init(&t->ext_rec_updates, ext_id + 2);
-	array = array_idx_modifiable(&t->ext_rec_updates, ext_id);
-
-	/* @UNSAFE */
-	if (!mail_index_seq_array_add(array, seq, data, record_size,
-				      old_data_r)) {
-		/* not found, clear old_data if it was given */
-		if (old_data_r != NULL)
-			memset(old_data_r, 0, record_size);
-	}
-}
-
-int mail_index_atomic_inc_ext(struct mail_index_transaction *t,
-			      uint32_t seq, uint32_t ext_id, int diff)
-{
-	ARRAY_TYPE(seq_array) *array;
-	int32_t old_diff32, diff32 = diff;
-
-	i_assert(seq > 0 &&
-		 (seq <= mail_index_view_get_messages_count(t->view) ||
-		  seq <= t->last_new_seq));
-	i_assert(ext_id < array_count(&t->view->index->extensions));
-	/* currently non-external transactions can be applied multiple times,
-	   causing multiple increments. */
-	//FIXME:i_assert((t->flags & MAIL_INDEX_TRANSACTION_FLAG_EXTERNAL) != 0);
-
-	t->log_ext_updates = TRUE;
-	if (!array_is_created(&t->ext_rec_atomics))
-		i_array_init(&t->ext_rec_atomics, ext_id + 2);
-	array = array_idx_modifiable(&t->ext_rec_atomics, ext_id);
-	if (mail_index_seq_array_add(array, seq, &diff32, sizeof(diff32),
-				     &old_diff32)) {
-		/* already incremented this sequence in this transaction */
-		diff32 += old_diff32;
-		mail_index_seq_array_add(array, seq, &diff32, sizeof(diff32),
-					 NULL);
-	}
-	return diff32;
-}
-
-static bool
-keyword_update_has_changes(struct mail_index_transaction *t, uint32_t seq,
-			   enum modify_type modify_type,
-			   struct mail_keywords *keywords)
-{
-	struct mail_index_transaction_keyword_update *u;
-	ARRAY_TYPE(keyword_indexes) existing;
-	const unsigned int *existing_idx;
-	unsigned int i, j, existing_count;
-	bool found;
-
-	t_array_init(&existing, 32);
-	if (seq < t->first_new_seq)
-		mail_index_lookup_keywords(t->view, seq, &existing);
-	existing_idx = array_get(&existing, &existing_count);
-
-	if (modify_type == MODIFY_REPLACE && existing_count != keywords->count)
-		return TRUE;
-
-	for (i = 0; i < keywords->count; i++) {
-		u = array_idx_modifiable(&t->keyword_updates,
-					 keywords->idx[i]);
-		if (array_is_created(&u->add_seq) ||
-		    array_is_created(&u->remove_seq))
-			return TRUE;
-
-		found = FALSE;
-		for (j = 0; j < existing_count; j++) {
-			if (existing_idx[j] == keywords->idx[i]) {
-				found = TRUE;
-				break;
-			}
-		}
-		switch (modify_type) {
-		case MODIFY_ADD:
-		case MODIFY_REPLACE:
-			if (!found)
-				return TRUE;
-			break;
-		case MODIFY_REMOVE:
-			if (found)
-				return TRUE;
-			break;
-		}
-	}
-	return FALSE;
-}
-
-void mail_index_update_keywords(struct mail_index_transaction *t, uint32_t seq,
-				enum modify_type modify_type,
-				struct mail_keywords *keywords)
-{
-	struct mail_index_transaction_keyword_update *u;
-	unsigned int i, ku_count;
-	bool changed;
-
-	i_assert(seq > 0 &&
-		 (seq <= mail_index_view_get_messages_count(t->view) ||
-		  seq <= t->last_new_seq));
-	i_assert(keywords->count > 0 || modify_type == MODIFY_REPLACE);
-	i_assert(keywords->index == t->view->index);
-
-	update_minmax_flagupdate_seq(t, seq, seq);
-
-	if (!array_is_created(&t->keyword_updates) && keywords->count > 0) {
-		uint32_t max_idx = keywords->idx[keywords->count-1];
-
-		i_array_init(&t->keyword_updates, max_idx + 1);
-	}
-
-	if ((t->flags & MAIL_INDEX_TRANSACTION_FLAG_AVOID_FLAG_UPDATES) != 0) {
-		T_BEGIN {
-			changed = keyword_update_has_changes(t, seq,
-							     modify_type,
-							     keywords);
-		} T_END;
-		if (!changed)
-			return;
-	}
-
-	/* Update add_seq and remove_seq arrays which describe the keyword
-	   changes. Don't bother updating remove_seq or keyword resets for
-	   newly added messages since they default to not having any
-	   keywords anyway. */
-	switch (modify_type) {
-	case MODIFY_ADD:
-		for (i = 0; i < keywords->count; i++) {
-			u = array_idx_modifiable(&t->keyword_updates,
-						 keywords->idx[i]);
-			seq_range_array_add(&u->add_seq, 16, seq);
-			seq_range_array_remove(&u->remove_seq, seq);
-		}
-		break;
-	case MODIFY_REMOVE:
-		for (i = 0; i < keywords->count; i++) {
-			u = array_idx_modifiable(&t->keyword_updates,
-						 keywords->idx[i]);
-			seq_range_array_remove(&u->add_seq, seq);
-			if (seq < t->first_new_seq)
-				seq_range_array_add(&u->remove_seq, 16, seq);
-		}
-		break;
-	case MODIFY_REPLACE:
-		/* Remove sequence from all add/remove arrays */
-		if (array_is_created(&t->keyword_updates)) {
-			u = array_get_modifiable(&t->keyword_updates,
-						 &ku_count);
-			for (i = 0; i < ku_count; i++) {
-				seq_range_array_remove(&u[i].add_seq, seq);
-				seq_range_array_remove(&u[i].remove_seq, seq);
-			}
-		}
-		/* Add the wanted keyword back */
-		for (i = 0; i < keywords->count; i++) {
-			u = array_idx_modifiable(&t->keyword_updates,
-						 keywords->idx[i]);
-			seq_range_array_add(&u->add_seq, 16, seq);
-		}
-
-		if (seq < t->first_new_seq)
-			seq_range_array_add(&t->keyword_resets, 16, seq);
-		break;
-	}
-
-	t->log_updates = TRUE;
-}
-
-void mail_index_reset(struct mail_index_transaction *t)
-{
-	mail_index_transaction_reset(t);
-
-	t->reset = TRUE;
-}
-
-void mail_index_transaction_set_max_modseq(struct mail_index_transaction *t,
-					   uint64_t max_modseq,
-					   ARRAY_TYPE(seq_range) *seqs)
-{
-	i_assert(array_is_created(seqs));
-
-	t->max_modseq = max_modseq;
-	t->conflict_seqs = seqs;
-}
-
 static struct mail_index_transaction_vfuncs trans_vfuncs = {
 	mail_index_transaction_reset_v,
 	mail_index_transaction_commit_v,

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/lib-index/test-mail-index-transaction-update.c	Mon Jul 13 19:54:28 2009 -0400
@@ -0,0 +1,435 @@
+/* Copyright (c) 2009 Dovecot authors, see the included COPYING file */
+
+#include "lib.h"
+#include "array.h"
+#include "test-common.h"
+#include "mail-index-private.h"
+#include "mail-index-transaction-private.h"
+
+#include <stdlib.h>
+
+static struct mail_index_header hdr;
+static struct mail_index_record rec;
+
+const struct mail_index_header *
+mail_index_get_header(struct mail_index_view *view ATTR_UNUSED)
+{
+	return &hdr;
+}
+
+const struct mail_index_record *
+mail_index_lookup(struct mail_index_view *view ATTR_UNUSED,
+		  uint32_t seq ATTR_UNUSED)
+{
+	return &rec;
+}
+
+void mail_index_lookup_keywords(struct mail_index_view *view ATTR_UNUSED,
+				uint32_t seq ATTR_UNUSED,
+				ARRAY_TYPE(keyword_indexes) *keyword_idx ATTR_UNUSED)
+{
+	array_clear(keyword_idx);
+}
+
+bool mail_index_map_get_ext_idx(struct mail_index_map *map ATTR_UNUSED,
+				uint32_t ext_id ATTR_UNUSED,
+				uint32_t *idx_r ATTR_UNUSED)
+{
+	return FALSE;
+}
+
+uint32_t mail_index_view_get_messages_count(struct mail_index_view *view ATTR_UNUSED)
+{
+	return hdr.messages_count;
+}
+
+static struct mail_index_transaction *
+mail_index_transaction_new(void)
+{
+	struct mail_index_transaction *t;
+
+	t = t_new(struct mail_index_transaction, 1);
+	t->first_new_seq = hdr.messages_count + 1;
+	return t;
+}
+
+static void test_mail_index_append(void)
+{
+	struct mail_index_transaction *t;
+	const struct mail_index_record *appends;
+	unsigned int count;
+	uint32_t seq, next_uid;
+
+	hdr.messages_count = 4;
+	t = mail_index_transaction_new();
+
+	test_begin("mail index append");
+	mail_index_append(t, 0, &seq);
+	test_assert(t->log_updates);
+	test_assert(seq == 5);
+	mail_index_append(t, 0, &seq);
+	test_assert(seq == 6);
+	test_assert(!t->appends_nonsorted);
+
+	mail_index_append_assign_uids(t, 123, &next_uid);
+	test_assert(next_uid == 125);
+
+	appends = array_get(&t->appends, &count);
+	test_assert(appends[0].uid == 123);
+	test_assert(appends[0].flags == 0);
+	test_assert(appends[1].uid == 124);
+	test_assert(appends[1].flags == 0);
+	test_end();
+
+	/* test with some uids */
+	t = mail_index_transaction_new();
+
+	test_begin("mail index append with uids");
+	mail_index_append(t, 0, &seq);
+	test_assert(seq == 5);
+	mail_index_append(t, 126, &seq);
+	test_assert(seq == 6);
+	test_assert(!t->appends_nonsorted);
+	mail_index_append(t, 124, &seq);
+	test_assert(seq == 7);
+	test_assert(t->appends_nonsorted);
+	mail_index_append(t, 0, &seq);
+	test_assert(seq == 8);
+	mail_index_append(t, 128, &seq);
+	test_assert(seq == 9);
+	test_assert(t->highest_append_uid == 128);
+
+	mail_index_append_assign_uids(t, 129, &next_uid);
+	test_assert(next_uid == 131);
+
+	appends = array_get(&t->appends, &count);
+	test_assert(count == 5);
+	test_assert(appends[0].uid == 129);
+	test_assert(appends[1].uid == 126);
+	test_assert(appends[2].uid == 124);
+	test_assert(appends[3].uid == 130);
+	test_assert(appends[4].uid == 128);
+	test_end();
+}
+
+static void test_mail_index_flag_update_fastpath(void)
+{
+	struct mail_index_transaction *t;
+	const struct mail_transaction_flag_update *updates;
+	unsigned int count;
+
+	hdr.messages_count = 20;
+	t = mail_index_transaction_new();
+
+	test_begin("mail index flag update fast paths");
+
+	mail_index_update_flags_range(t, 13, 14, MODIFY_REPLACE,
+				      MAIL_DELETED);
+	test_assert(t->last_update_idx == 0);
+	test_assert(array_count(&t->updates) == 1);
+
+	mail_index_update_flags_range(t, 15, 15, MODIFY_REPLACE,
+				      MAIL_DELETED);
+	test_assert(t->last_update_idx == 0);
+	test_assert(array_count(&t->updates) == 1);
+
+	mail_index_update_flags_range(t, 16, 16, MODIFY_ADD,
+				      MAIL_DELETED);
+	test_assert(t->last_update_idx == 1);
+	test_assert(array_count(&t->updates) == 2);
+
+	updates = array_get(&t->updates, &count);
+	test_assert(updates[0].uid1 == 13);
+	test_assert(updates[0].uid2 == 15);
+	test_assert(updates[0].add_flags == MAIL_DELETED);
+	test_assert(updates[0].remove_flags ==
+		    (MAIL_ANSWERED | MAIL_FLAGGED | MAIL_SEEN | MAIL_DRAFT));
+	test_assert(updates[0].padding == 0);
+	test_assert(updates[1].uid1 == 16);
+	test_assert(updates[1].uid2 == 16);
+	test_assert(updates[1].add_flags == MAIL_DELETED);
+	test_assert(updates[1].remove_flags == 0);
+	test_assert(updates[1].padding == 0);
+	test_assert(!t->log_updates);
+	test_end();
+}
+
+static void test_mail_index_flag_update_simple_merges(void)
+{
+	struct mail_index_transaction *t;
+	const struct mail_transaction_flag_update *updates;
+	unsigned int count;
+
+	hdr.messages_count = 20;
+	t = mail_index_transaction_new();
+
+	test_begin("mail index flag update simple merges");
+
+	mail_index_update_flags_range(t, 6, 8, MODIFY_ADD,
+				      MAIL_FLAGGED);
+	test_assert(t->last_update_idx == 0);
+	mail_index_update_flags_range(t, 5, 6, MODIFY_ADD,
+				      MAIL_FLAGGED);
+	test_assert(t->last_update_idx == 0);
+	mail_index_update_flags_range(t, 4, 4, MODIFY_ADD,
+				      MAIL_FLAGGED);
+	test_assert(t->last_update_idx == 0);
+	mail_index_update_flags_range(t, 7, 9, MODIFY_ADD,
+				      MAIL_FLAGGED);
+	test_assert(t->last_update_idx == 0);
+	mail_index_update_flags_range(t, 10, 10, MODIFY_ADD,
+				      MAIL_FLAGGED);
+	updates = array_get(&t->updates, &count);
+	test_assert(count == 1);
+	test_assert(updates[0].uid1 == 4);
+	test_assert(updates[0].uid2 == 10);
+	test_assert(updates[0].add_flags == MAIL_FLAGGED);
+	test_assert(updates[0].remove_flags == 0);
+
+	mail_index_update_flags_range(t, 12, 12, MODIFY_ADD,
+				      MAIL_FLAGGED);
+	mail_index_update_flags_range(t, 11, 11, MODIFY_ADD,
+				      MAIL_FLAGGED);
+	test_assert(count == 1);
+	test_assert(updates[0].uid1 == 4);
+	test_assert(updates[0].uid2 == 12);
+	test_end();
+}
+
+static void test_mail_index_flag_update_complex_merges(void)
+{
+	struct mail_index_transaction *t;
+	const struct mail_transaction_flag_update *updates;
+	unsigned int count;
+
+	hdr.messages_count = 20;
+	t = mail_index_transaction_new();
+
+	test_begin("mail index flag update complex merges");
+
+	mail_index_update_flags_range(t, 6, 8, MODIFY_REPLACE,
+				      MAIL_SEEN);
+	mail_index_update_flags_range(t, 3, 6, MODIFY_ADD,
+				      MAIL_FLAGGED);
+	mail_index_update_flags_range(t, 5, 7, MODIFY_ADD,
+				      MAIL_DRAFT);
+	mail_index_update_flags_range(t, 6, 6, MODIFY_REPLACE,
+				      MAIL_SEEN | MAIL_ANSWERED);
+	mail_index_update_flags_range(t, 5, 10, MODIFY_REMOVE,
+				      MAIL_ANSWERED);
+	mail_index_update_flags_range(t, 7, 12, MODIFY_ADD,
+				      MAIL_DELETED);
+
+	updates = array_get(&t->updates, &count);
+	test_assert(count == 7);
+	test_assert(updates[0].uid1 == 3);
+	test_assert(updates[0].uid2 == 4);
+	test_assert(updates[0].add_flags == MAIL_FLAGGED);
+	test_assert(updates[0].remove_flags == 0);
+	test_assert(updates[1].uid1 == 5);
+	test_assert(updates[1].uid2 == 5);
+	test_assert(updates[1].add_flags == (MAIL_DRAFT | MAIL_FLAGGED));
+	test_assert(updates[1].remove_flags == MAIL_ANSWERED);
+	test_assert(updates[2].uid1 == 6);
+	test_assert(updates[2].uid2 == 6);
+	test_assert(updates[2].add_flags == MAIL_SEEN);
+	test_assert(updates[2].remove_flags == (MAIL_ANSWERED | MAIL_FLAGGED | MAIL_DELETED | MAIL_DRAFT));
+	test_assert(updates[3].uid1 == 7);
+	test_assert(updates[3].uid2 == 7);
+	test_assert(updates[3].add_flags == (MAIL_SEEN | MAIL_DRAFT | MAIL_DELETED));
+	test_assert(updates[3].remove_flags == (MAIL_ANSWERED | MAIL_FLAGGED));
+	test_assert(updates[4].uid1 == 8);
+	test_assert(updates[4].uid2 == 8);
+	test_assert(updates[4].add_flags == (MAIL_SEEN | MAIL_DELETED));
+	test_assert(updates[4].remove_flags == (MAIL_ANSWERED | MAIL_FLAGGED | MAIL_DRAFT));
+	test_assert(updates[5].uid1 == 9);
+	test_assert(updates[5].uid2 == 10);
+	test_assert(updates[5].add_flags == MAIL_DELETED);
+	test_assert(updates[5].remove_flags == MAIL_ANSWERED);
+	test_assert(updates[6].uid1 == 11);
+	test_assert(updates[6].uid2 == 12);
+	test_assert(updates[6].add_flags == MAIL_DELETED);
+	test_assert(updates[6].remove_flags == 0);
+
+	test_end();
+}
+
+static bool
+flags_array_check(struct mail_index_transaction *t,
+		  const enum mail_flags *flags, unsigned int msg_count)
+{
+	const struct mail_transaction_flag_update *updates;
+	unsigned int i, count, seq;
+
+	if (array_is_created(&t->updates))
+		updates = array_get(&t->updates, &count);
+	else {
+		updates = NULL;
+		count = 0;
+	}
+	for (seq = 1, i = 0; i < count; i++) {
+		if (i > 0) {
+			test_assert(updates[i-1].uid2 < updates[i].uid1);
+			test_assert(updates[i-1].uid2 + 1 != updates[i].uid1 ||
+				    updates[i-1].add_flags != updates[i].add_flags ||
+				    updates[i-1].remove_flags != updates[i].remove_flags);
+		}
+		for (; seq != updates[i].uid1; seq++)
+			test_assert(flags[seq] == 0);
+		for (; seq <= updates[i].uid2; seq++)
+			test_assert(flags[seq] == updates[i].add_flags);
+	}
+	for (; seq <= msg_count; seq++)
+		test_assert(flags[seq] == 0);
+	return TRUE;
+}
+
+static void test_mail_index_flag_update_random(void)
+{
+	struct mail_index_transaction *t;
+	unsigned int r, seq1, seq2, seq;
+	enum mail_flags *flags, change;
+	enum modify_type modify_type;
+
+	hdr.messages_count = 20;
+	t = mail_index_transaction_new();
+
+	test_begin("mail index flag update random");
+
+	flags = t_new(enum mail_flags, hdr.messages_count + 1);
+	for (r = 0; r < 1000; r++) {
+		change = rand() % (MAIL_FLAGS_NONRECENT+1);
+		seq1 = (rand() % hdr.messages_count) + 1;
+		seq2 = seq1 == hdr.messages_count ? seq1 :
+			(rand() % (hdr.messages_count - seq1)) + seq1;
+
+		switch (rand() % 3) {
+		case 0:
+			modify_type = MODIFY_ADD;
+			for (seq = seq1; seq <= seq2; seq++)
+				flags[seq] |= change;
+			break;
+		case 1:
+			modify_type = MODIFY_REMOVE;
+			for (seq = seq1; seq <= seq2; seq++)
+				flags[seq] &= ~change;
+			break;
+		case 2:
+			modify_type = MODIFY_REPLACE;
+			for (seq = seq1; seq <= seq2; seq++)
+				flags[seq] = change;
+			break;
+		default:
+			i_unreached();
+		}
+		mail_index_update_flags_range(t, seq1, seq2, modify_type,
+					      change);
+		flags_array_check(t, flags, hdr.messages_count);
+	}
+	test_end();
+}
+
+static void test_mail_index_flag_update_appends(void)
+{
+	struct mail_index_transaction *t;
+	const struct mail_index_record *appends;
+	const struct mail_transaction_flag_update *updates;
+	unsigned int count;
+	uint32_t seq;
+
+	hdr.messages_count = 4;
+	t = mail_index_transaction_new();
+
+	test_begin("mail index flag update appends");
+	mail_index_append(t, 0, &seq);
+	test_assert(seq == 5);
+	mail_index_append(t, 0, &seq);
+	test_assert(seq == 6);
+	mail_index_append(t, 0, &seq);
+	test_assert(seq == 7);
+
+	mail_index_update_flags_range(t, 5, 6, MODIFY_REPLACE,
+				      MAIL_SEEN | MAIL_FLAGGED);
+	mail_index_update_flags_range(t, 6, 7, MODIFY_ADD,
+				      MAIL_DRAFT | MAIL_FLAGGED);
+	mail_index_update_flags_range(t, 5, 7, MODIFY_REMOVE,
+				      MAIL_FLAGGED);
+
+	appends = array_get(&t->appends, &count);
+	test_assert(count == 3);
+	test_assert(appends[0].flags == MAIL_SEEN);
+	test_assert(appends[1].flags == (MAIL_SEEN | MAIL_DRAFT));
+	test_assert(appends[2].flags == MAIL_DRAFT);
+
+	/* mixed existing/appends */
+	mail_index_update_flags_range(t, 4, 5, MODIFY_ADD,
+				      MAIL_ANSWERED);
+	test_assert(appends[0].flags == (MAIL_SEEN | MAIL_ANSWERED));
+
+	updates = array_get(&t->updates, &count);
+	test_assert(count == 1);
+	test_assert(updates[0].uid1 == 4);
+	test_assert(updates[0].uid2 == 4);
+	test_assert(updates[0].add_flags == MAIL_ANSWERED);
+	test_end();
+}
+
+static bool test_flag_update_pos(struct mail_index_transaction *t,
+				 uint32_t seq, unsigned int idx)
+{
+	unsigned int i, j, count;
+
+	count = array_count(&t->updates);
+	for (i = 0; i < idx; i++) {
+		for (j = idx + 1; j <= count; j++) {
+			if (!mail_index_transaction_get_flag_update_pos(t, i, j, seq) == idx) {
+				test_assert(FALSE);
+				return FALSE;
+			}
+		}
+	}
+	return TRUE;
+}
+
+static void test_mail_index_transaction_get_flag_update_pos(void)
+{
+	struct mail_index_transaction *t;
+
+	test_begin("mail index transaction get flag update pos");
+
+	hdr.messages_count = 10;
+	t = mail_index_transaction_new();
+	mail_index_update_flags_range(t, 1, 1, MODIFY_REPLACE, 0);
+	mail_index_update_flags_range(t, 3, 4, MODIFY_REPLACE, 0);
+	mail_index_update_flags_range(t, 6, 7, MODIFY_REPLACE, 0);
+	mail_index_update_flags_range(t, 9, 10, MODIFY_REPLACE, 0);
+
+	test_assert(test_flag_update_pos(t, 1, 0));
+	test_assert(test_flag_update_pos(t, 2, 1));
+	test_assert(test_flag_update_pos(t, 3, 1));
+	test_assert(test_flag_update_pos(t, 4, 1));
+	test_assert(test_flag_update_pos(t, 5, 2));
+	test_assert(test_flag_update_pos(t, 6, 2));
+	test_assert(test_flag_update_pos(t, 7, 2));
+	test_assert(test_flag_update_pos(t, 8, 3));
+	test_assert(test_flag_update_pos(t, 9, 3));
+	test_assert(test_flag_update_pos(t, 10, 3));
+	test_assert(test_flag_update_pos(t, 11, 4));
+	test_assert(test_flag_update_pos(t, 12, 4));
+	test_end();
+}
+
+int main(void)
+{
+	static void (*test_functions[])(void) = {
+		test_mail_index_append,
+		test_mail_index_flag_update_fastpath,
+		test_mail_index_flag_update_simple_merges,
+		test_mail_index_flag_update_complex_merges,
+		test_mail_index_flag_update_random,
+		test_mail_index_flag_update_appends,
+		test_mail_index_transaction_get_flag_update_pos,
+		NULL
+	};
+	return test_run(test_functions);
+}