Mercurial > dovecot > core-2.2

changeset 12591:868f2de3898b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
imapc: Fixed seqmap to work. The algorithm is a bit slow, could be improved. But probably won't make much of a difference in real life.
author Timo Sirainen <tss@iki.fi>
date Sun, 23 Jan 2011 20:26:02 +0200
parents 9e471f267fb4
children 475050722f54
files src/lib-storage/index/imapc/Makefile.am src/lib-storage/index/imapc/imapc-seqmap.c src/lib-storage/index/imapc/test-imapc-seqmap.c
diffstat 3 files changed, 204 insertions(+), 3 deletions(-) [+]
line wrap: on
line diff
--- a/src/lib-storage/index/imapc/Makefile.am	Fri Jan 21 17:39:24 2011 +0200
+++ b/src/lib-storage/index/imapc/Makefile.am	Sun Jan 23 20:26:02 2011 +0200
@@ -2,6 +2,7 @@
 
 AM_CPPFLAGS = \
 	-I$(top_srcdir)/src/lib \
+	-I$(top_srcdir)/src/lib-test \
 	-I$(top_srcdir)/src/lib-dns \
 	-I$(top_srcdir)/src/lib-mail \
 	-I$(top_srcdir)/src/lib-imap \
@@ -30,3 +31,22 @@
 
 pkginc_libdir=$(pkgincludedir)
 pkginc_lib_HEADERS = $(headers)
+
+test_programs = \
+	test-imapc-seqmap
+
+noinst_PROGRAMS = $(test_programs)
+
+test_libs = \
+	../../../lib-test/libtest.la \
+	../../../lib/liblib.la
+
+test_imapc_seqmap_SOURCES = test-imapc-seqmap.c
+test_imapc_seqmap_LDADD = imapc-seqmap.lo $(test_libs)
+test_imapc_seqmap_DEPENDENCIES = imapc-seqmap.lo $(test_libs)
+
+check: check-am check-test
+check-test: all-am
+	for bin in $(test_programs); do \
+	  if ! $(RUN_TEST) ./$$bin; then exit 1; fi; \
+	done
--- a/src/lib-storage/index/imapc/imapc-seqmap.c	Fri Jan 21 17:39:24 2011 +0200
+++ b/src/lib-storage/index/imapc/imapc-seqmap.c	Sun Jan 23 20:26:02 2011 +0200
@@ -2,9 +2,11 @@
 
 #include "lib.h"
 #include "array.h"
+#include "bsearch-insert-pos.h"
 #include "imapc-seqmap.h"
 
 struct imapc_seqmap {
+	ARRAY_TYPE(uint32_t) queue;
 	ARRAY_TYPE(uint32_t) expunges;
 };
 
@@ -13,6 +15,7 @@
 	struct imapc_seqmap *seqmap;
 
 	seqmap = i_new(struct imapc_seqmap, 1);
+	i_array_init(&seqmap->queue, 64);
 	i_array_init(&seqmap->expunges, 64);
 	return seqmap;
 }
@@ -23,11 +26,13 @@
 
 	*_seqmap = NULL;
 	array_free(&seqmap->expunges);
+	array_free(&seqmap->queue);
 	i_free(seqmap);
 }
 
 void imapc_seqmap_reset(struct imapc_seqmap *seqmap)
 {
+	array_clear(&seqmap->queue);
 	array_clear(&seqmap->expunges);
 }
 
@@ -35,17 +40,82 @@
 {
 	i_assert(rseq > 0);
 
-	array_append(&seqmap->expunges, &rseq, 1);
+	array_append(&seqmap->queue, &rseq, 1);
+}
+
+static int uint32_cmp_p(const uint32_t *p1, const uint32_t *p2)
+{
+	if (*p1 < *p2)
+		return -1;
+	else if (*p1 > *p2)
+		return 1;
+	else
+		return 0;
+}
+
+static uint32_t
+imapc_seqmap_rseq_idx_lookup(struct imapc_seqmap *seqmap, uint32_t rseq,
+			     unsigned int *idx_r)
+{
+	const uint32_t *seqs;
+	unsigned int idx, count;
+	uint32_t lseq = rseq;
+
+	seqs = array_get(&seqmap->expunges, &count);
+	for (;;) {
+		array_bsearch_insert_pos(&seqmap->expunges, &lseq, uint32_cmp_p, &idx);
+		lseq = rseq + idx;
+		if (idx == count || seqs[idx] > lseq) {
+			*idx_r = idx;
+			return lseq;
+		}
+		if (seqs[idx] == lseq)
+			lseq++;
+	}
+}
+
+static void
+imapc_seqmap_dequeue_rseq(struct imapc_seqmap *seqmap, uint32_t rseq)
+{
+	unsigned int idx;
+	uint32_t lseq;
+
+	lseq = imapc_seqmap_rseq_idx_lookup(seqmap, rseq, &idx);
+	array_insert(&seqmap->expunges, idx, &lseq, 1);
+}
+
+static void imapc_seqmap_dequeue(struct imapc_seqmap *seqmap)
+{
+	const uint32_t *seqp;
+
+	array_foreach(&seqmap->queue, seqp)
+		imapc_seqmap_dequeue_rseq(seqmap, *seqp);
+	array_clear(&seqmap->queue);
 }
 
 uint32_t imapc_seqmap_rseq_to_lseq(struct imapc_seqmap *seqmap, uint32_t rseq)
 {
+	unsigned int idx;
+
 	i_assert(rseq > 0);
-	return rseq; // FIXME
+
+	imapc_seqmap_dequeue(seqmap);
+	return imapc_seqmap_rseq_idx_lookup(seqmap, rseq, &idx);
 }
 
 uint32_t imapc_seqmap_lseq_to_rseq(struct imapc_seqmap *seqmap, uint32_t lseq)
 {
+	const uint32_t *seqs;
+	unsigned int idx, count;
+
 	i_assert(lseq > 0);
-	return lseq; // FIXME
+
+	imapc_seqmap_dequeue(seqmap);
+
+	seqs = array_get(&seqmap->expunges, &count);
+	if (array_bsearch_insert_pos(&seqmap->expunges, &lseq,
+				     uint32_cmp_p, &idx))
+		return 0;
+
+	return lseq - idx;
 }
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/lib-storage/index/imapc/test-imapc-seqmap.c	Sun Jan 23 20:26:02 2011 +0200
@@ -0,0 +1,111 @@
+/* Copyright (c) 2011 Dovecot authors, see the included COPYING file */
+
+#include "lib.h"
+#include "array.h"
+#include "imapc-seqmap.h"
+#include "test-common.h"
+
+#include <stdlib.h>
+
+static void test_imapc_seqmap(void)
+{
+	struct imapc_seqmap *seqmap;
+
+	test_begin("imapc seqmap");
+	seqmap = imapc_seqmap_init();
+
+	imapc_seqmap_expunge(seqmap, 4);
+	imapc_seqmap_expunge(seqmap, 3);
+	imapc_seqmap_expunge(seqmap, 2);
+
+	test_assert(imapc_seqmap_rseq_to_lseq(seqmap, 1) == 1);
+	test_assert(imapc_seqmap_rseq_to_lseq(seqmap, 2) == 5);
+
+	test_assert(imapc_seqmap_lseq_to_rseq(seqmap, 1) == 1);
+	test_assert(imapc_seqmap_lseq_to_rseq(seqmap, 2) == 0);
+	test_assert(imapc_seqmap_lseq_to_rseq(seqmap, 3) == 0);
+	test_assert(imapc_seqmap_lseq_to_rseq(seqmap, 4) == 0);
+	test_assert(imapc_seqmap_lseq_to_rseq(seqmap, 5) == 2);
+
+	imapc_seqmap_reset(seqmap);
+	imapc_seqmap_expunge(seqmap, 3);
+	imapc_seqmap_expunge(seqmap, 3);
+	imapc_seqmap_expunge(seqmap, 3);
+
+	test_assert(imapc_seqmap_rseq_to_lseq(seqmap, 1) == 1);
+	test_assert(imapc_seqmap_rseq_to_lseq(seqmap, 2) == 2);
+	test_assert(imapc_seqmap_rseq_to_lseq(seqmap, 3) == 6);
+
+	test_assert(imapc_seqmap_lseq_to_rseq(seqmap, 1) == 1);
+	test_assert(imapc_seqmap_lseq_to_rseq(seqmap, 2) == 2);
+	test_assert(imapc_seqmap_lseq_to_rseq(seqmap, 3) == 0);
+	test_assert(imapc_seqmap_lseq_to_rseq(seqmap, 4) == 0);
+	test_assert(imapc_seqmap_lseq_to_rseq(seqmap, 5) == 0);
+	test_assert(imapc_seqmap_lseq_to_rseq(seqmap, 6) == 3);
+
+	imapc_seqmap_reset(seqmap);
+	/* 9,8,5,4,2,1 */
+	imapc_seqmap_expunge(seqmap, 4);
+	imapc_seqmap_expunge(seqmap, 4);
+	imapc_seqmap_expunge(seqmap, 1);
+	imapc_seqmap_expunge(seqmap, 1);
+	imapc_seqmap_expunge(seqmap, 4);
+	imapc_seqmap_expunge(seqmap, 4);
+
+	test_assert(imapc_seqmap_rseq_to_lseq(seqmap, 1) == 3);
+	test_assert(imapc_seqmap_rseq_to_lseq(seqmap, 2) == 6);
+	test_assert(imapc_seqmap_rseq_to_lseq(seqmap, 3) == 7);
+	test_assert(imapc_seqmap_rseq_to_lseq(seqmap, 4) == 10);
+
+	test_assert(imapc_seqmap_lseq_to_rseq(seqmap, 1) == 0);
+	test_assert(imapc_seqmap_lseq_to_rseq(seqmap, 2) == 0);
+	test_assert(imapc_seqmap_lseq_to_rseq(seqmap, 3) == 1);
+	test_assert(imapc_seqmap_lseq_to_rseq(seqmap, 6) == 2);
+	test_assert(imapc_seqmap_lseq_to_rseq(seqmap, 7) == 3);
+	test_assert(imapc_seqmap_lseq_to_rseq(seqmap, 10) == 4);
+
+	imapc_seqmap_deinit(&seqmap);
+	test_end();
+}
+
+static void test_imapc_seqmap_random(void)
+{
+#define UIDMAP_SIZE 1000
+	struct imapc_seqmap *seqmap;
+	ARRAY_TYPE(uint32_t) uidmap;
+	const uint32_t *uids;
+	unsigned int i, count;
+	uint32_t seq, uid;
+
+	test_begin("imapc seqmap random");
+	seqmap = imapc_seqmap_init();
+
+	t_array_init(&uidmap, UIDMAP_SIZE);
+	for (uid = 1; uid <= UIDMAP_SIZE; uid++)
+		array_append(&uidmap, &uid, 1);
+
+	for (i = 0; i < 100; i++) {
+		seq = (rand() % array_count(&uidmap)) + 1;
+		array_delete(&uidmap, seq-1, 1);
+		imapc_seqmap_expunge(seqmap, seq);
+	}
+
+	uids = array_get(&uidmap, &count);
+	for (i = 0; i < 100; i++) {
+		seq = i + 1;
+		test_assert(imapc_seqmap_rseq_to_lseq(seqmap, seq) == uids[i]);
+		test_assert(imapc_seqmap_lseq_to_rseq(seqmap, uids[i]) == seq);
+	}
+	imapc_seqmap_deinit(&seqmap);
+	test_end();
+}
+
+int main(void)
+{
+	static void (*test_functions[])(void) = {
+		test_imapc_seqmap,
+		test_imapc_seqmap_random,
+		NULL
+	};
+	return test_run(test_functions);
+}