--- a/configure.in	Wed Dec 04 20:05:50 2002 +0200
+++ b/configure.in	Wed Dec 04 20:28:37 2002 +0200
@@ -689,7 +689,7 @@
 dnl **
 
 STORAGE="maildir mbox"
-file="src/lib-storage/mail-storage-register.c"
+file="src/lib-storage/register/mail-storage-register.c"
 
 echo "/* this file is generated by configure */" > $file
 echo '#include "lib.h"' >> $file
@@ -719,6 +719,7 @@
 src/lib-storage/index/maildir/Makefile
 src/lib-storage/index/mbox/Makefile
 src/lib-storage/subscription-file/Makefile
+src/lib-storage/register/Makefile
 src/auth/Makefile
 src/imap/Makefile
 src/login/Makefile

--- a/src/imap/Makefile.am	Wed Dec 04 20:05:50 2002 +0200
+++ b/src/imap/Makefile.am	Wed Dec 04 20:28:37 2002 +0200
@@ -9,10 +9,11 @@
 	-I$(top_srcdir)/src/lib-storage
 
 imap_LDADD = \
-	../lib-storage/libstorage.a \
+	../lib-storage/register/libstorage-register.a \
 	../lib-storage/index/maildir/libstorage_maildir.a \
 	../lib-storage/index/mbox/libstorage_mbox.a \
 	../lib-storage/index/libstorage_index.a \
+	../lib-storage/libstorage.a \
 	../lib-index/maildir/libstorage_index_maildir.a \
 	../lib-index/mbox/libstorage_index_mbox.a \
 	../lib-index/libstorage_index.a \
@@ -42,6 +43,7 @@
 	cmd-rename.c \
 	cmd-search.c \
 	cmd-select.c \
+	cmd-sort.c \
 	cmd-status.c \
 	cmd-store.c \
 	cmd-subscribe.c \

--- a/src/imap/cmd-search.c	Wed Dec 04 20:05:50 2002 +0200
+++ b/src/imap/cmd-search.c	Wed Dec 04 20:28:37 2002 +0200
@@ -49,7 +49,8 @@
 		/* error in search arguments */
 		client_send_tagline(client, t_strconcat("NO ", error, NULL));
 	} else {
-		if (client->mailbox->search(client->mailbox, charset, sargs,
+		if (client->mailbox->search(client->mailbox, charset,
+					    sargs, NULL,
 					    client->outbuf, client->cmd_uid)) {
 			/* NOTE: syncing isn't allowed here */
 			client_sync_without_expunges(client);

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/imap/cmd-sort.c	Wed Dec 04 20:28:37 2002 +0200
@@ -0,0 +1,137 @@
+/* Copyright (C) 2002 Timo Sirainen */
+
+#include "common.h"
+#include "commands.h"
+#include "mail-search.h"
+#include "mail-sort.h"
+
+typedef struct {
+	MailSortType type;
+	const char *name;
+} SortName;
+
+static SortName sort_names[] = {
+	{ MAIL_SORT_ARRIVAL,	"arrival" },
+	{ MAIL_SORT_CC,		"cc" },
+	{ MAIL_SORT_DATE,	"date" },
+	{ MAIL_SORT_FROM,	"from" },
+	{ MAIL_SORT_SIZE,	"size" },
+	{ MAIL_SORT_SUBJECT,	"subject" },
+	{ MAIL_SORT_TO,		"to" },
+
+	{ MAIL_SORT_REVERSE,	"reverse" },
+	{ MAIL_SORT_END,	NULL }
+};
+
+static MailSortType *get_sort_program(Client *client, ImapArg *args)
+{
+	MailSortType *program, *temp_prog;
+	size_t program_alloc, program_size;
+	int i;
+
+	program_alloc = 32; program_size = 0;
+	program = t_new(MailSortType, program_alloc+1);
+
+	while (args->type == IMAP_ARG_ATOM || args->type == IMAP_ARG_STRING) {
+		const char *arg = args->data.str;
+
+		for (i = 0; sort_names[i].type != MAIL_SORT_END; i++) {
+			if (strcasecmp(arg, sort_names[i].name) == 0)
+				break;
+		}
+
+		if (sort_names[i].type == MAIL_SORT_END) {
+			client_send_command_error(client, t_strconcat(
+				"Unknown sort argument: ", arg, NULL));
+			return NULL;
+		}
+
+		if (program_size == program_alloc) {
+			program_alloc *= 2;
+			if (!t_try_realloc(program, program_alloc+1)) {
+				temp_prog = t_new(MailSortType, program_alloc);
+				memcpy(temp_prog, program,
+				       sizeof(MailSortType) * program_size);
+				program = temp_prog;
+			}
+		}
+		program[program_size++] = sort_names[i].type;
+		args++;
+	}
+
+	program[program_size] = MAIL_SORT_END;
+
+	if (args->type != IMAP_ARG_EOL) {
+		client_send_command_error(client,
+					  "Invalid sort list argument.");
+		return NULL;
+	}
+
+	return program;
+}
+
+int cmd_sort(Client *client)
+{
+	MailSearchArg *sargs;
+	MailSortType *sorting;
+	ImapArg *args;
+	int args_count;
+	Pool pool;
+	const char *error, *charset;
+
+	args_count = imap_parser_read_args(client->parser, 0, 0, &args);
+	if (args_count == -2)
+		return FALSE;
+
+	if (args_count < 3) {
+		client_send_command_error(client,
+					  "Missing or invalid arguments.");
+		return TRUE;
+	}
+
+	if (!client_verify_open_mailbox(client))
+		return TRUE;
+
+	/* sort program */
+	if (args->type != IMAP_ARG_LIST) {
+		client_send_command_error(client, "Invalid sort argument.");
+		return TRUE;
+	}
+
+	sorting = get_sort_program(client, args->data.list->args);
+	if (sorting == NULL)
+		return TRUE;
+	args++;
+
+	/* charset */
+	if (args->type != IMAP_ARG_ATOM && args->type != IMAP_ARG_STRING) {
+		client_send_command_error(client,
+					  "Invalid charset argument.");
+	}
+	charset = args->data.str;
+	args++;
+
+	pool = pool_create("MailSortArgs", 2048, FALSE);
+
+	sargs = mail_search_args_build(pool, args, &error);
+	if (sargs == NULL) {
+		/* error in search arguments */
+		client_send_tagline(client, t_strconcat("NO ", error, NULL));
+	} else {
+		if (client->mailbox->search(client->mailbox, charset,
+					    sargs, sorting,
+					    client->outbuf, client->cmd_uid)) {
+			/* NOTE: syncing is allowed when returning UIDs */
+			if (client->cmd_uid)
+				client_sync_full(client);
+			else
+				client_sync_without_expunges(client);
+			client_send_tagline(client, "OK Search completed.");
+		} else {
+			client_send_storage_error(client);
+		}
+	}
+
+	pool_unref(pool);
+	return TRUE;
+}

--- a/src/imap/commands.c	Wed Dec 04 20:05:50 2002 +0200
+++ b/src/imap/commands.c	Wed Dec 04 20:28:37 2002 +0200
@@ -64,6 +64,8 @@
 			return cmd_store;
 		if (strcmp(name, "SEARCH") == 0)
 			return cmd_search;
+		if (strcmp(name, "SORT") == 0)
+			return cmd_sort;
 		if (strcmp(name, "SELECT") == 0)
 			return cmd_select;
 		if (strcmp(name, "STATUS") == 0)

--- a/src/imap/commands.h	Wed Dec 04 20:05:50 2002 +0200
+++ b/src/imap/commands.h	Wed Dec 04 20:28:37 2002 +0200
@@ -36,6 +36,7 @@
 int cmd_close(Client *client);
 int cmd_expunge(Client *client);
 int cmd_search(Client *client);
+int cmd_sort(Client *client);
 int cmd_fetch(Client *client);
 int cmd_store(Client *client);
 int cmd_copy(Client *client);

--- a/src/lib-storage/.cvsignore	Wed Dec 04 20:05:50 2002 +0200
+++ b/src/lib-storage/.cvsignore	Wed Dec 04 20:28:37 2002 +0200
@@ -6,4 +6,3 @@
 Makefile
 Makefile.in
 so_locations
-mail-storage-register.c

--- a/src/lib-storage/Makefile.am	Wed Dec 04 20:05:50 2002 +0200
+++ b/src/lib-storage/Makefile.am	Wed Dec 04 20:28:37 2002 +0200
@@ -1,4 +1,4 @@
-SUBDIRS = index subscription-file
+SUBDIRS = index subscription-file register
 
 noinst_LIBRARIES = libstorage.a
 
@@ -6,19 +6,12 @@
 	-I$(top_srcdir)/src/lib \
 	-I$(top_srcdir)/src/lib-imap
 
-real_sources = \
+libstorage_a_SOURCES = \
 	mail-search.c \
+	mail-sort.c \
 	mail-storage.c
 
-libstorage_a_SOURCES = \
-	$(real_sources) \
-	mail-storage-register.c
-
 noinst_HEADERS = \
 	mail-search.h \
+	mail-sort.h \
 	mail-storage.h
-
-DISTFILES = $(DIST_COMMON) $(real_sources) $(HEADERS) $(TEXINFOS) $(EXTRA_DIST)
-
-distclean-generic:
-	rm -f Makefile mail-storage-register.c

--- a/src/lib-storage/index/Makefile.am	Wed Dec 04 20:05:50 2002 +0200
+++ b/src/lib-storage/index/Makefile.am	Wed Dec 04 20:28:37 2002 +0200
@@ -19,6 +19,7 @@
 	index-msgcache.c \
 	index-save.c \
 	index-search.c \
+	index-sort.c \
 	index-status.c \
 	index-storage.c \
 	index-sync.c \

--- a/src/lib-storage/index/index-search.c	Wed Dec 04 20:05:50 2002 +0200
+++ b/src/lib-storage/index/index-search.c	Wed Dec 04 20:28:37 2002 +0200
@@ -12,6 +12,7 @@
 #include "imap-date.h"
 #include "imap-envelope.h"
 #include "index-storage.h"
+#include "index-sort.h"
 #include "mail-index-util.h"
 #include "mail-modifylog.h"
 #include "mail-custom-flags.h"
@@ -53,6 +54,8 @@
 	MessagePart *part;
 } SearchBodyContext;
 
+static MailSortType sort_unsorted[] = { MAIL_SORT_END };
+
 static int msgset_contains(const char *set, unsigned int match_num,
 			   unsigned int max_num)
 {
@@ -753,7 +756,8 @@
 }
 
 static int search_messages(IndexMailbox *ibox, const char *charset,
-			   MailSearchArg *args, OBuffer *outbuf, int uid_result)
+			   MailSearchArg *args, MailSortContext *sort_ctx,
+			   OBuffer *outbuf, int uid_result)
 {
 	SearchIndexContext ctx;
 	MailIndexRecord *rec;
@@ -821,9 +825,16 @@
 			}
 
 			if (found) {
-				i_snprintf(num, sizeof(num), " %u",
-					   uid_result ? rec->uid : client_seq);
-				o_buffer_send(outbuf, num, strlen(num));
+				if (sort_ctx == NULL) {
+					size_t len;
+
+					len = i_snprintf(num, sizeof(num),
+							 " %u", uid_result ?
+							 rec->uid : client_seq);
+					o_buffer_send(outbuf, num, len);
+				} else {
+					mail_sort_input(sort_ctx, rec->uid);
+				}
 			}
 		}
 
@@ -839,16 +850,34 @@
 }
 
 int index_storage_search(Mailbox *box, const char *charset, MailSearchArg *args,
-			 OBuffer *outbuf, int uid_result)
+			 MailSortType *sorting, OBuffer *outbuf, int uid_result)
 {
 	IndexMailbox *ibox = (IndexMailbox *) box;
+	MailSortContext *sort_ctx;
+	IndexSortContext index_sort_ctx;
 	int failed;
 
 	if (!index_storage_sync_and_lock(ibox, TRUE, MAIL_LOCK_SHARED))
 		return FALSE;
 
-	o_buffer_send(outbuf, "* SEARCH", 8);
-	failed = !search_messages(ibox, charset, args, outbuf, uid_result);
+	if (sorting == NULL) {
+		sort_ctx = NULL;
+		o_buffer_send(outbuf, "* SEARCH", 8);
+	} else {
+		memset(&index_sort_ctx, 0, sizeof(index_sort_ctx));
+		index_sort_ctx.ibox = ibox;
+		index_sort_ctx.outbuf = outbuf;
+
+		sort_ctx = mail_sort_init(sort_unsorted, sorting,
+					  index_sort_funcs, &index_sort_ctx);
+		o_buffer_send(outbuf, "* SORT", 6);
+	}
+
+	failed = !search_messages(ibox, charset, args, sort_ctx,
+				  outbuf, uid_result);
+	if (sort_ctx != NULL)
+		mail_sort_deinit(sort_ctx);
+
 	o_buffer_send(outbuf, "\r\n", 2);
 
 	if (!index_storage_lock(ibox, MAIL_LOCK_UNLOCK))

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/lib-storage/index/index-sort.c	Wed Dec 04 20:28:37 2002 +0200
@@ -0,0 +1,137 @@
+/* Copyright (C) 2002 Timo Sirainen */
+
+#include "lib.h"
+#include "obuffer.h"
+#include "rfc822-date.h"
+#include "imap-envelope.h"
+#include "imap-message-cache.h"
+#include "mail-index.h"
+#include "index-storage.h"
+#include "index-sort.h"
+
+static ImapMessageCache *search_open_cache(IndexSortContext *ctx,
+					   unsigned int uid)
+{
+	if (ctx->last_uid != uid) {
+		ctx->cached = FALSE;
+		ctx->last_uid = uid;
+		ctx->rec = ctx->ibox->index->lookup_uid_range(ctx->ibox->index,
+							      uid, uid, NULL);
+		if (ctx->rec == NULL) {
+			ctx->last_uid = 0;
+			return NULL;
+		}
+	}
+
+	if (!ctx->cached) {
+		ctx->cached = TRUE;
+		(void)index_msgcache_open(ctx->ibox->cache,
+					  ctx->ibox->index, ctx->rec,
+					  IMAP_CACHE_ENVELOPE);
+	}
+
+	return ctx->ibox->cache;
+}
+
+static uoff_t _input_uofft(MailSortType type, unsigned int id, void *context)
+{
+	IndexSortContext *ctx = context;
+        ImapMessageCache *cache;
+
+	if (type != MAIL_SORT_SIZE) {
+		i_unreached();
+		return 0;
+	}
+
+        cache = search_open_cache(ctx, id);
+	return cache == NULL ? 0 : imap_msgcache_get_virtual_size(cache);
+}
+
+static const char *_input_str(MailSortType type, unsigned int id, void *context)
+{
+	IndexSortContext *ctx = context;
+	ImapEnvelopeField env_field;
+	const char *envelope;
+
+	switch (type) {
+	case MAIL_SORT_CC:
+		env_field = IMAP_ENVELOPE_CC;
+		break;
+	case MAIL_SORT_DATE:
+                env_field = IMAP_ENVELOPE_DATE;
+		break;
+	case MAIL_SORT_FROM:
+                env_field = IMAP_ENVELOPE_FROM;
+		break;
+	case MAIL_SORT_SUBJECT:
+                env_field = IMAP_ENVELOPE_SUBJECT;
+		break;
+	case MAIL_SORT_TO:
+                env_field = IMAP_ENVELOPE_TO;
+		break;
+	default:
+		i_unreached();
+		return NULL;
+	}
+
+	/* get field from hopefully cached envelope */
+	envelope = imap_msgcache_get(search_open_cache(ctx, id),
+				     IMAP_CACHE_ENVELOPE);
+	return envelope == NULL ? NULL :
+		imap_envelope_parse(envelope, env_field);
+}
+
+static time_t _input_time(MailSortType type, unsigned int id, void *context)
+{
+	IndexSortContext *ctx = context;
+        ImapMessageCache *cache;
+	const char *str;
+	time_t time;
+	int timezone_offset;
+
+	switch (type) {
+	case MAIL_SORT_ARRIVAL:
+		cache = search_open_cache(ctx, id);
+		return cache == NULL ? 0 :
+			imap_msgcache_get_internal_date(cache);
+	case MAIL_SORT_DATE:
+		str = _input_str(type, id, context);
+		if (str == NULL)
+			return 0;
+
+		if (!rfc822_parse_date(str, &time, &timezone_offset))
+			return 0;
+
+		return time - timezone_offset*60;
+	default:
+		i_unreached();
+		return 0;
+	}
+}
+
+static void _input_reset(void *context)
+{
+	IndexSortContext *ctx = context;
+
+	ctx->cached = FALSE;
+}
+
+static void _output(unsigned int *data, size_t count, void *context)
+{
+	IndexSortContext *ctx = context;
+	char num[MAX_INT_STRLEN+1];
+	size_t i, len;
+
+	for (i = 0; i < count; i++) {
+		len = i_snprintf(num, sizeof(num), " %u", data[i]);
+		o_buffer_send(ctx->outbuf, num, len);
+	}
+}
+
+MailSortFuncs index_sort_funcs = {
+	_input_time,
+	_input_uofft,
+	_input_str,
+	_input_reset,
+	_output
+};

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/lib-storage/index/index-sort.h	Wed Dec 04 20:28:37 2002 +0200
@@ -0,0 +1,19 @@
+#ifndef __INDEX_SORT_H
+#define __INDEX_SORT_H
+
+#include "mail-storage.h"
+#include "mail-sort.h"
+
+typedef struct {
+	IndexMailbox *ibox;
+	OBuffer *outbuf;
+
+	unsigned int last_uid;
+	MailIndexRecord *rec;
+
+	unsigned int cached:1;
+} IndexSortContext;
+
+extern MailSortFuncs index_sort_funcs;
+
+#endif

--- a/src/lib-storage/index/index-storage.h	Wed Dec 04 20:05:50 2002 +0200
+++ b/src/lib-storage/index/index-storage.h	Wed Dec 04 20:28:37 2002 +0200
@@ -84,6 +84,7 @@
 int index_storage_fetch(Mailbox *box, MailFetchData *fetch_data,
 			OBuffer *outbuf, int *all_found);
 int index_storage_search(Mailbox *box, const char *charset, MailSearchArg *args,
-			 OBuffer *outbuf, int uid_result);
+			 MailSortType *sorting, OBuffer *outbuf,
+			 int uid_result);
 
 #endif

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/lib-storage/mail-sort.c	Wed Dec 04 20:28:37 2002 +0200
@@ -0,0 +1,298 @@
+/* Copyright (C) 2002 Timo Sirainen */
+
+#include "lib.h"
+#include "obuffer.h"
+#include "mail-sort.h"
+
+#include <stdlib.h>
+
+struct _MailSortContext {
+	MailSortType output[MAX_SORT_PROGRAM_SIZE];
+	MailSortType output_mask, common_mask;
+
+	MailSortFuncs funcs;
+	void *func_context;
+
+	size_t sort_buffer_size, sort_buffer_alloc;
+	unsigned int *sort_buffer;
+
+	time_t last_arrival, last_date;
+	uoff_t last_size;
+	char *last_cc, *last_from, *last_subject, *last_to;
+};
+
+static void mail_sort_flush(MailSortContext *ctx);
+
+static MailSortType
+mail_sort_normalize(const MailSortType *input,
+		    MailSortType output[MAX_SORT_PROGRAM_SIZE])
+{
+        MailSortType mask = 0;
+	int pos, reverse;
+
+	reverse = FALSE;
+	for (pos = 0; *input != MAIL_SORT_END; input++) {
+		if (*input == MAIL_SORT_REVERSE)
+			reverse = !reverse;
+		else {
+			if ((mask & *input) == 0) {
+				if (reverse) {
+					i_assert(pos < MAX_SORT_PROGRAM_SIZE);
+					output[pos++] = MAIL_SORT_REVERSE;
+				}
+
+				i_assert(pos < MAX_SORT_PROGRAM_SIZE);
+				output[pos++] = *input;
+				mask |= *input;
+			}
+			reverse = FALSE;
+		}
+	}
+
+	i_assert(pos < MAX_SORT_PROGRAM_SIZE);
+	output[pos] = MAIL_SORT_END;
+
+	return mask;
+}
+
+static MailSortType
+mail_sort_get_common_mask(const MailSortType *input, const MailSortType *output)
+{
+	MailSortType mask = 0;
+
+	while (*input == *output && *input != MAIL_SORT_END) {
+		if (*input != MAIL_SORT_REVERSE)
+			mask |= *input;
+		input++; output++;
+	}
+
+	return mask;
+}
+
+MailSortContext *mail_sort_init(const MailSortType *input, MailSortType *output,
+				MailSortFuncs funcs, void *context)
+{
+	MailSortContext *ctx;
+	MailSortType norm_input[MAX_SORT_PROGRAM_SIZE];
+
+	ctx = i_new(MailSortContext, 1);
+
+	mail_sort_normalize(input, norm_input);
+	ctx->output_mask = mail_sort_normalize(output, ctx->output);
+        ctx->common_mask = mail_sort_get_common_mask(norm_input, ctx->output);
+
+	ctx->sort_buffer_alloc = 128;
+	ctx->sort_buffer = i_new(unsigned int, ctx->sort_buffer_alloc);
+
+	ctx->funcs = funcs;
+	ctx->func_context = context;
+	return ctx;
+}
+
+void mail_sort_deinit(MailSortContext *ctx)
+{
+	mail_sort_flush(ctx);
+
+	i_free(ctx->last_cc);
+	i_free(ctx->last_from);
+	i_free(ctx->last_subject);
+	i_free(ctx->last_to);
+
+	i_free(ctx->sort_buffer);
+	i_free(ctx);
+}
+
+static int sort_strcmp(const char *s1, const char *s2)
+{
+	if (s1 == NULL)
+		return s2 == NULL ? 0 : -1;
+	if (s2 == NULL)
+		return 1;
+
+	return strcasecmp(s1, s2); /* FIXME */
+}
+
+static int subject_cmp(const char *s1, const char *s2)
+{
+	if (s1 == NULL)
+		return s2 == NULL ? 0 : -1;
+	if (s2 == NULL)
+		return 1;
+
+	return strcasecmp(s1, s2); /* FIXME */
+}
+
+static void mail_sort_check_flush(MailSortContext *ctx, unsigned int id)
+{
+	const char *str;
+	time_t t;
+	uoff_t size;
+	int changed = FALSE;
+
+	if (ctx->common_mask & MAIL_SORT_ARRIVAL) {
+		t = ctx->funcs.input_time(MAIL_SORT_ARRIVAL, id,
+					  ctx->func_context);
+		if (t != ctx->last_arrival) {
+			ctx->last_arrival = t;
+			changed = TRUE;
+		}
+	}
+
+	if (ctx->common_mask & MAIL_SORT_CC) {
+		str = ctx->funcs.input_str(MAIL_SORT_CC, id,
+					   ctx->func_context);
+		if (sort_strcmp(str, ctx->last_cc) != 0) {
+			i_free(ctx->last_cc);
+			ctx->last_cc = i_strdup(str);
+			changed = TRUE;
+		}
+	}
+
+	if (ctx->common_mask & MAIL_SORT_DATE) {
+		t = ctx->funcs.input_time(MAIL_SORT_DATE, id,
+					  ctx->func_context);
+		if (t != ctx->last_date) {
+			ctx->last_date = t;
+			changed = TRUE;
+		}
+	}
+
+	if (ctx->common_mask & MAIL_SORT_FROM) {
+		str = ctx->funcs.input_str(MAIL_SORT_FROM, id,
+					   ctx->func_context);
+		if (sort_strcmp(str, ctx->last_from) != 0) {
+			i_free(ctx->last_from);
+			ctx->last_from = i_strdup(str);
+			changed = TRUE;
+		}
+	}
+
+	if (ctx->common_mask & MAIL_SORT_SIZE) {
+		size = ctx->funcs.input_time(MAIL_SORT_SIZE, id,
+					     ctx->func_context);
+		if (size != ctx->last_size) {
+			ctx->last_size = size;
+			changed = TRUE;
+		}
+	}
+
+	if (ctx->common_mask & MAIL_SORT_SUBJECT) {
+		str = ctx->funcs.input_str(MAIL_SORT_SUBJECT, id,
+					   ctx->func_context);
+		if (subject_cmp(str, ctx->last_subject) != 0) {
+			i_free(ctx->last_subject);
+			ctx->last_subject = i_strdup(str);
+			changed = TRUE;
+		}
+	}
+
+	if (ctx->common_mask & MAIL_SORT_TO) {
+		str = ctx->funcs.input_str(MAIL_SORT_TO, id,
+					   ctx->func_context);
+		if (sort_strcmp(str, ctx->last_to) != 0) {
+			i_free(ctx->last_to);
+			ctx->last_to = i_strdup(str);
+			changed = TRUE;
+		}
+	}
+
+	if (changed)
+		mail_sort_flush(ctx);
+}
+
+void mail_sort_input(MailSortContext *ctx, unsigned int id)
+{
+	if (ctx->common_mask != 0)
+		mail_sort_check_flush(ctx, id);
+
+	if (ctx->sort_buffer_size == ctx->sort_buffer_alloc) {
+		ctx->sort_buffer_alloc *= 2;
+		ctx->sort_buffer = i_realloc(ctx->sort_buffer,
+					     ctx->sort_buffer_alloc *
+					     sizeof(unsigned int));
+	}
+
+	ctx->sort_buffer[ctx->sort_buffer_size++] = id;
+}
+
+static MailSortContext *mail_sort_qsort_context;
+
+static int mail_sort_qsort_func(const void *p1, const void *p2)
+{
+	const unsigned int *i1 = p1;
+	const unsigned int *i2 = p2;
+	MailSortType *output = mail_sort_qsort_context->output;
+        MailSortFuncs *funcs = &mail_sort_qsort_context->funcs;
+	void *ctx = mail_sort_qsort_context->func_context;
+	int ret, reverse = FALSE;
+
+	t_push();
+
+	ret = 0;
+	for (; *output != MAIL_SORT_END && ret == 0; output++) {
+		if (*output == MAIL_SORT_REVERSE) {
+			reverse = !reverse;
+			continue;
+		}
+
+		switch (*output) {
+		case MAIL_SORT_ARRIVAL:
+		case MAIL_SORT_DATE: {
+			time_t r1, r2;
+
+			r1 = funcs->input_time(*output, *i1, ctx);
+			r2 = funcs->input_time(*output, *i2, ctx);
+			ret = r1 < r2 ? -1 : r1 > r2 ? 1 : 0;
+			break;
+		}
+		case MAIL_SORT_SIZE: {
+			uoff_t r1, r2;
+
+			r1 = funcs->input_uofft(*output, *i1, ctx);
+			r2 = funcs->input_uofft(*output, *i2, ctx);
+			ret = r1 < r2 ? -1 : r1 > r2 ? 1 : 0;
+			break;
+		}
+		case MAIL_SORT_CC:
+		case MAIL_SORT_FROM:
+		case MAIL_SORT_TO:
+			ret = sort_strcmp(funcs->input_str(*output, *i1, ctx),
+					  funcs->input_str(*output, *i2, ctx));
+			break;
+
+		case MAIL_SORT_SUBJECT:
+			ret = subject_cmp(funcs->input_str(*output, *i1, ctx),
+					  funcs->input_str(*output, *i2, ctx));
+			break;
+		default:
+			i_unreached();
+		}
+
+		if (reverse) {
+			if (ret > 0)
+				ret = -1;
+			else if (ret < 0)
+				ret = 1;
+		}
+
+		reverse = FALSE;
+	}
+
+	funcs->input_reset(ctx);
+
+	t_pop();
+
+	return ret != 0 ? ret : (*i1 < *i2 ? -1 : 1);
+}
+
+static void mail_sort_flush(MailSortContext *ctx)
+{
+	mail_sort_qsort_context = ctx;
+
+	qsort(ctx->sort_buffer, ctx->sort_buffer_size, sizeof(unsigned int),
+	      mail_sort_qsort_func);
+
+	ctx->funcs.output(ctx->sort_buffer, ctx->sort_buffer_size,
+			  ctx->func_context);
+	ctx->sort_buffer_size = 0;
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/lib-storage/mail-sort.h	Wed Dec 04 20:28:37 2002 +0200
@@ -0,0 +1,49 @@
+#ifndef __MAIL_SORT_H
+#define __MAIL_SORT_H
+
+#include "mail-storage.h"
+
+/* Maximum size for sort program, 2x for reverse + END */
+#define MAX_SORT_PROGRAM_SIZE (2*7 + 1)
+
+enum _MailSortType {
+	MAIL_SORT_ARRIVAL	= 0x0010,
+	MAIL_SORT_CC		= 0x0020,
+	MAIL_SORT_DATE		= 0x0040,
+	MAIL_SORT_FROM		= 0x0080,
+	MAIL_SORT_SIZE		= 0x0100,
+	MAIL_SORT_SUBJECT	= 0x0200,
+	MAIL_SORT_TO		= 0x0400,
+
+	MAIL_SORT_REVERSE	= 0x0001, /* reverse the next type */
+
+	MAIL_SORT_END		= 0x0000 /* ends sort program */
+};
+
+typedef struct _MailSortContext MailSortContext;
+
+typedef struct {
+	time_t (*input_time)(MailSortType type, unsigned int id,
+			     void *context);
+	uoff_t (*input_uofft)(MailSortType type, unsigned int id,
+			      void *context);
+	const char *(*input_str)(MailSortType type, unsigned int id,
+				 void *context);
+	void (*input_reset)(void *context);
+
+	void (*output)(unsigned int *data, size_t count, void *context);
+} MailSortFuncs;
+
+/* input and output are arrays of sort programs ending with MAIL_SORT_END.
+   input specifies the order in which the messages are arriving to sorting.
+   It may be just MAIL_SORT_END if the order is random. The better the ordering
+   is known, the less memory is used. */
+MailSortContext *mail_sort_init(const MailSortType *input, MailSortType *output,
+				MailSortFuncs funcs, void *context);
+void mail_sort_deinit(MailSortContext *ctx);
+
+/* id is either UID or sequence number of message, depending which one we
+   want to send user. */
+void mail_sort_input(MailSortContext *ctx, unsigned int id);
+
+#endif

--- a/src/lib-storage/mail-storage.h	Wed Dec 04 20:05:50 2002 +0200
+++ b/src/lib-storage/mail-storage.h	Wed Dec 04 20:28:37 2002 +0200
@@ -44,6 +44,7 @@
 typedef struct _MailFetchData MailFetchData;
 typedef struct _MailFetchBodyData MailFetchBodyData;
 typedef struct _MailSearchArg MailSearchArg;
+typedef enum _MailSortType MailSortType;
 
 typedef void (*MailboxFunc)(MailStorage *storage, const char *name,
 			    MailboxFlags flags, void *context);
@@ -161,7 +162,7 @@
 	   If charset is NULL, the given search strings are matched without
 	   any conversion. */
 	int (*search)(Mailbox *box, const char *charset, MailSearchArg *args,
-		      OBuffer *outbuf, int uid_result);
+		      MailSortType *sorting, OBuffer *outbuf, int uid_result);
 
 	/* Save a new mail into mailbox. timezone_offset specifies the
 	   timezone in minutes which internal_date was originally given

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/lib-storage/register/.cvsignore	Wed Dec 04 20:28:37 2002 +0200
@@ -0,0 +1,9 @@
+*.la
+*.lo
+*.o
+.deps
+.libs
+Makefile
+Makefile.in
+so_locations
+mail-storage-register.c

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/lib-storage/register/Makefile.am	Wed Dec 04 20:28:37 2002 +0200
@@ -0,0 +1,14 @@
+noinst_LIBRARIES = libstorage-register.a
+
+INCLUDES = \
+	-I$(top_srcdir)/src/lib \
+	-I$(top_srcdir)/src/lib-imap \
+	-I$(top_srcdir)/src/lib-storage
+
+libstorage_register_a_SOURCES = \
+	mail-storage-register.c
+
+DISTFILES = $(DIST_COMMON) $(HEADERS) $(TEXINFOS) $(EXTRA_DIST)
+
+distclean-generic:
+	rm -f Makefile mail-storage-register.c