--- a/src/director/Makefile.am	Thu Apr 19 20:29:25 2012 +0300
+++ b/src/director/Makefile.am	Thu Apr 19 21:51:48 2012 +0300
@@ -4,6 +4,7 @@
 
 AM_CPPFLAGS = \
 	-I$(top_srcdir)/src/lib \
+	-I$(top_srcdir)/src/lib-test \
 	-I$(top_srcdir)/src/lib-auth \
 	-I$(top_srcdir)/src/lib-imap \
 	-I$(top_srcdir)/src/lib-settings \
@@ -40,10 +41,27 @@
 	notify-connection.h \
 	user-directory.h
 
-noinst_PROGRAMS = director-test
+noinst_PROGRAMS = director-test $(test_programs)
 
 director_test_LDADD = $(LIBDOVECOT)
 director_test_DEPENDENCIES = $(LIBDOVECOT_DEPS)
 
 director_test_SOURCES = \
 	director-test.c
+
+test_programs = \
+	test-user-directory
+
+test_libs = \
+	../lib-test/libtest.la \
+	../lib/liblib.la
+
+test_user_directory_SOURCES = test-user-directory.c
+test_user_directory_LDADD = user-directory.o $(test_libs)
+test_user_directory_DEPENDENCIES = user-directory.o $(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/director/director-connection.c	Thu Apr 19 20:29:25 2012 +0300
+++ b/src/director/director-connection.c	Thu Apr 19 21:51:48 2012 +0300
@@ -540,7 +540,7 @@
 	}
 
 	if (director_user_refresh(conn, username_hash,
-				  host, ioloop_time, FALSE, &user)) {
+				  host, (time_t)-1, FALSE, &user)) {
 		i_assert(!user->weak);
 		director_update_user(conn->dir, conn->host, user);
 	}
@@ -674,7 +674,7 @@
 	}
 
 	if (director_user_refresh(conn, username_hash,
-				  host, ioloop_time, weak, &user)) {
+				  host, (time_t)-1, weak, &user)) {
 		if (!user->weak)
 			director_update_user(conn->dir, src_host, user);
 		else {

--- a/src/director/director-request.c	Thu Apr 19 20:29:25 2012 +0300
+++ b/src/director/director-request.c	Thu Apr 19 21:51:48 2012 +0300
@@ -225,7 +225,7 @@
 			return FALSE;
 		}
 		user = user_directory_add(dir->users, request->username_hash,
-					  host, ioloop_time);
+					  host, (time_t)-1);
 	}
 
 	i_assert(!user->weak);

--- a/src/director/director.c	Thu Apr 19 20:29:25 2012 +0300
+++ b/src/director/director.c	Thu Apr 19 21:51:48 2012 +0300
@@ -582,7 +582,7 @@
 	user = user_directory_lookup(dir->users, username_hash);
 	if (user == NULL) {
 		user = user_directory_add(dir->users, username_hash,
-					  host, ioloop_time);
+					  host, (time_t)-1);
 	} else {
 		if (user->host == host) {
 			/* user is already in this host */

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/director/test-user-directory.c	Thu Apr 19 21:51:48 2012 +0300
@@ -0,0 +1,104 @@
+/* Copyright (c) 2012 Dovecot authors, see the included COPYING file */
+
+#include "lib.h"
+#include "ioloop.h"
+#include "mail-user-hash.h"
+#include "mail-host.h"
+#include "user-directory.h"
+#include "test-common.h"
+
+#include <stdlib.h>
+
+#define USER_DIR_TIMEOUT 1000000
+
+unsigned int mail_user_hash(const char *username ATTR_UNUSED,
+			    const char *format ATTR_UNUSED) { return 0; }
+
+static void
+verify_user_directory(struct user_directory *dir, unsigned int user_count)
+{
+	struct user_directory_iter *iter;
+	struct user *user, *prev = NULL;
+	unsigned int prev_stamp = 0, iter_count = 0;
+
+	iter = user_directory_iter_init(dir);
+	while ((user = user_directory_iter_next(iter)) != NULL) {
+		test_assert(prev_stamp <= user->timestamp);
+		test_assert(user->prev == prev);
+		test_assert(prev == NULL || user->prev->next == user);
+
+		iter_count++;
+		prev = user;
+	}
+	test_assert(prev == NULL || prev->next == NULL);
+	user_directory_iter_deinit(&iter);
+	test_assert(iter_count == user_count);
+}
+
+static void test_user_directory_ascending(void)
+{
+	const unsigned int count = 100000;
+	struct user_directory *dir;
+	struct mail_host *host = t_new(struct mail_host, 1);
+	unsigned int i;
+
+	test_begin("user directory ascending");
+	dir = user_directory_init(USER_DIR_TIMEOUT, "%u");
+	user_directory_add(dir, 1, host, ioloop_time + count+1);
+
+	for (i = 0; i < count; i++)
+		user_directory_add(dir, i+2, host, ioloop_time + i);
+	verify_user_directory(dir, count+1);
+	user_directory_deinit(&dir);
+	test_end();
+}
+
+static void test_user_directory_descending(void)
+{
+	const unsigned int count = 1000;
+	struct user_directory *dir;
+	struct mail_host *host = t_new(struct mail_host, 1);
+	unsigned int i;
+
+	test_begin("user directory descending");
+	dir = user_directory_init(USER_DIR_TIMEOUT, "%u");
+
+	for (i = 0; i < count; i++)
+		user_directory_add(dir, i+1, host, ioloop_time - i);
+	verify_user_directory(dir, count);
+	user_directory_deinit(&dir);
+	test_end();
+}
+
+static void test_user_directory_random(void)
+{
+	struct user_directory *dir;
+	struct mail_host *host = t_new(struct mail_host, 1);
+	time_t timestamp;
+	unsigned int i, count = 10000 + rand()%10000;
+
+	test_begin("user directory random");
+	dir = user_directory_init(USER_DIR_TIMEOUT, "%u");
+	for (i = 0; i < count; i++) {
+		if (rand() % 10 == 0)
+			timestamp = (time_t)-1;
+		else
+			timestamp = ioloop_time-rand()%100;
+		user_directory_add(dir, i+1, host, timestamp);
+	}
+	verify_user_directory(dir, count);
+	user_directory_deinit(&dir);
+	test_end();
+}
+
+int main(void)
+{
+	static void (*test_functions[])(void) = {
+		test_user_directory_ascending,
+		test_user_directory_descending,
+		test_user_directory_random,
+		NULL
+	};
+	ioloop_time = 1234567890;
+	return test_run(test_functions);
+}

--- a/src/director/user-directory.c	Thu Apr 19 20:29:25 2012 +0300
+++ b/src/director/user-directory.c	Thu Apr 19 21:51:48 2012 +0300
@@ -24,6 +24,7 @@
 	struct hash_table *hash;
 	/* sorted by time */
 	struct user *head, *tail;
+	struct user *prev_insert_pos;
 
 	ARRAY_DEFINE(iters, struct user_directory_iter *);
 
@@ -42,6 +43,9 @@
 		if ((*iterp)->pos == user)
 			(*iterp)->pos = user->next;
 	}
+
+	if (dir->prev_insert_pos == user)
+		dir->prev_insert_pos = user->next;
 }
 
 static void user_free(struct user_directory *dir, struct user *user)
@@ -79,11 +83,61 @@
 	return hash_table_lookup(dir->hash, POINTER_CAST(username_hash));
 }
 
+static void
+user_directory_insert_backwards(struct user_directory *dir,
+				struct user *pos, struct user *user)
+{
+	for (; pos != NULL; pos = pos->prev) {
+		if ((time_t)pos->timestamp <= user->timestamp)
+			break;
+	}
+	if (pos == NULL)
+		DLLIST2_PREPEND(&dir->head, &dir->tail, user);
+	else {
+		user->prev = pos;
+		user->next = pos->next;
+		user->prev->next = user;
+		if (user->next != NULL)
+			user->next->prev = user;
+		else
+			dir->tail = user;
+	}
+}
+
+static void
+user_directory_insert_forwards(struct user_directory *dir,
+			       struct user *pos, struct user *user)
+{
+	for (; pos != NULL; pos = pos->next) {
+		if ((time_t)pos->timestamp >= user->timestamp)
+			break;
+	}
+	if (pos == NULL)
+		DLLIST2_APPEND(&dir->head, &dir->tail, user);
+	else {
+		user->prev = pos->prev;
+		user->next = pos;
+		if (user->prev != NULL)
+			user->prev->next = user;
+		else
+			dir->head = user;
+		user->next->prev = user;
+	}
+}
+
 struct user *
 user_directory_add(struct user_directory *dir, unsigned int username_hash,
 		   struct mail_host *host, time_t timestamp)
 {
-	struct user *user, *pos;
+	struct user *user;
+
+	if (timestamp == (time_t)-1) {
+		/* make sure we add it at the end */
+		timestamp = ioloop_time;
+		if (dir->tail != NULL &&
+		    timestamp < (time_t)dir->tail->timestamp)
+			timestamp = (time_t)dir->tail->timestamp;
+	}
 
 	user = i_new(struct user, 1);
 	user->username_hash = username_hash;
@@ -94,21 +148,24 @@
 	if (dir->tail == NULL || (time_t)dir->tail->timestamp <= timestamp)
 		DLLIST2_APPEND(&dir->head, &dir->tail, user);
 	else {
-		/* need to insert to correct position */
-		for (pos = dir->tail; pos != NULL; pos = pos->prev) {
-			if ((time_t)pos->timestamp <= timestamp)
-				break;
-		}
-		if (pos == NULL)
-			DLLIST2_PREPEND(&dir->head, &dir->tail, user);
-		else {
-			user->prev = pos;
-			user->next = pos->next;
-			user->prev->next = user;
-			user->next->prev = user;
+		/* need to insert to correct position. we should get here
+		   only when handshaking. the handshaking USER requests should
+		   come sorted by timestamp. so keep track of the previous
+		   insert position, the next USER should be inserted after
+		   it. */
+		if (dir->prev_insert_pos == NULL) {
+			/* find the position starting from tail */
+			user_directory_insert_backwards(dir, dir->tail, user);
+		} else if (timestamp < dir->prev_insert_pos->timestamp) {
+			user_directory_insert_backwards(dir, dir->prev_insert_pos,
+							user);
+		} else {
+			user_directory_insert_forwards(dir, dir->prev_insert_pos,
+						       user);
 		}
 	}
 
+	dir->prev_insert_pos = user;
 	hash_table_insert(dir->hash, POINTER_CAST(user->username_hash), user);
 	return user;
 }

--- a/src/director/user-directory.h	Thu Apr 19 20:29:25 2012 +0300
+++ b/src/director/user-directory.h	Thu Apr 19 21:51:48 2012 +0300
@@ -54,7 +54,8 @@
 /* Look up username from directory. Returns NULL if not found. */
 struct user *user_directory_lookup(struct user_directory *dir,
 				   unsigned int username_hash);
-/* Add a user to directory and return it. */
+/* Add a user to directory and return it. If timestamp is (time_t)-1,
+   the current time is used. */
 struct user *
 user_directory_add(struct user_directory *dir, unsigned int username_hash,
 		   struct mail_host *host, time_t timestamp);