--- a/src/lib-index/Makefile.am	Sun Oct 06 00:47:33 2002 +0300
+++ b/src/lib-index/Makefile.am	Sun Oct 06 03:30:14 2002 +0300
@@ -9,7 +9,6 @@
 
 libstorage_index_a_SOURCES = \
 	mail-custom-flags.c \
-	mail-hash.c \
         mail-index.c \
         mail-index-compress.c \
         mail-index-fsck.c \
@@ -19,13 +18,15 @@
         mail-index-update-cache.c \
         mail-index-util.c \
         mail-lockdir.c \
-	mail-modifylog.c
+	mail-modifylog.c \
+	mail-tree.c \
+	mail-tree-redblack.c
 
 noinst_HEADERS = \
 	mail-custom-flags.h \
-	mail-hash.h \
 	mail-index.h \
         mail-index-data.h \
         mail-index-util.h \
         mail-lockdir.h \
-	mail-modifylog.h
+	mail-modifylog.h \
+	mail-tree.h

--- a/src/lib-index/mail-hash.c	Sun Oct 06 00:47:33 2002 +0300
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,590 +0,0 @@
-/* Copyright (C) 2002 Timo Sirainen */
-
-#include "lib.h"
-#include "ioloop.h"
-#include "file-set-size.h"
-#include "primes.h"
-#include "mmap-util.h"
-#include "write-full.h"
-#include "mail-index.h"
-#include "mail-index-util.h"
-#include "mail-hash.h"
-
-#include <stdio.h>
-#include <fcntl.h>
-
-/* Minimum record count for a hash file. By default, the hash file size is
-   the number of messages * 3, and it's rebuilt after the file is 3/4 full.
-   Use only primes as hash file sizes. */
-#define MIN_HASH_SIZE 109
-
-/* Maximum record count for a hash file. */
-#define MAX_HASH_SIZE \
-	((INT_MAX - sizeof(MailHashHeader)) / 100)
-
-/* When rebuilding hash, make it 30% full */
-#define MIN_PERCENTAGE 30
-
-/* Try rebuilding hash sometimes soon after it's 60% full */
-#define REBUILD_PERCENTAGE 60
-
-/* Force a rebuild when hash is 80% full */
-#define FORCED_REBUILD_PERCENTAGE 80
-
-/* our hashing function is simple - UID*2. The *2 is there because UIDs are
-   normally contiguous, so once the UIDs wrap around, we don't want to go
-   through lots of records just to find an empty spot */
-#define HASH_FUNC(uid) (uid * 2)
-
-#define HASH_FILE_SIZE(records) \
-	(sizeof(MailHashHeader) + (records) * sizeof(MailHashRecord))
-
-struct _MailHash {
-	MailIndex *index;
-
-	unsigned int size;
-
-	int fd;
-	char *filepath;
-
-	void *mmap_base;
-	size_t mmap_length;
-
-	MailHashHeader *header;
-	unsigned int anon_mmap:1;
-	unsigned int modified:1;
-};
-
-static int hash_set_syscall_error(MailHash *hash, const char *function)
-{
-	i_assert(function != NULL);
-
-	index_set_error(hash->index, "%s failed with hash file %s: %m",
-			function, hash->filepath);
-	return FALSE;
-}
-
-static void mail_hash_file_close(MailHash *hash)
-{
-	if (close(hash->fd) < 0)
-		hash_set_syscall_error(hash, "close()");
-	hash->fd = -1;
-}
-
-static int mail_hash_file_open(MailHash *hash)
-{
-	hash->fd = open(hash->filepath, O_RDWR);
-	if (hash->fd == -1) {
-		if (errno != ENOENT)
-			return hash_set_syscall_error(hash, "open()");
-
-		return mail_hash_rebuild(hash);
-	}
-
-	return TRUE;
-}
-
-static int mmap_update_real(MailHash *hash)
-{
-	i_assert(!hash->anon_mmap);
-
-	if (hash->mmap_base != NULL) {
-		if (munmap(hash->mmap_base, hash->mmap_length) < 0)
-			hash_set_syscall_error(hash, "munmap()");
-	}
-
-	hash->header = NULL;
-
-	hash->mmap_base = mmap_rw_file(hash->fd, &hash->mmap_length);
-	if (hash->mmap_base == MAP_FAILED) {
-		hash->header = NULL;
-		hash_set_syscall_error(hash, "mmap()");
-		return FALSE;
-	}
-
-	return TRUE;
-}
-
-static int hash_verify_header(MailHash *hash)
-{
-	if (hash->mmap_length <= sizeof(MailHashHeader) ||
-	    (hash->mmap_length - sizeof(MailHashHeader)) %
-	    sizeof(MailHashRecord) != 0) {
-		/* hash must be corrupted, rebuilding should have noticed
-		   if it was only partially written. */
-		index_set_error(hash->index, "Corrupted hash file %s: "
-				"Invalid file size %"PRIuSIZE_T"",
-				hash->filepath, hash->mmap_length);
-		return FALSE;
-	}
-
-	hash->size = (hash->mmap_length - sizeof(MailHashHeader)) /
-		sizeof(MailHashRecord);
-
-	if (hash->size < MIN_HASH_SIZE || hash->size > MAX_HASH_SIZE) {
-		/* invalid size, probably corrupted. */
-		index_set_error(hash->index, "Corrupted hash file %s: "
-				"Invalid size %u", hash->filepath, hash->size);
-		return FALSE;
-	}
-
-	hash->header = hash->mmap_base;
-	return TRUE;
-}
-
-static int mmap_update(MailHash *hash)
-{
-	if (hash->fd == -1)
-		return hash->anon_mmap;
-
-	/* see if it's been rebuilt */
-	if (hash->header->indexid == hash->index->indexid)
-		return TRUE;
-
-	if (hash->header->indexid != 0) {
-		/* index was just rebuilt. we should have noticed
-		   this before at index->set_lock() though. */
-		index_set_error(hash->index, "Warning: Inconsistency - Index "
-				"%s was rebuilt while we had it open",
-				hash->filepath);
-		hash->index->inconsistent = TRUE;
-		return FALSE;
-	}
-
-	mail_hash_file_close(hash);
-	if (!mail_hash_file_open(hash))
-		return FALSE;
-
-	return mmap_update_real(hash) && hash_verify_header(hash);
-}
-
-static void hash_munmap(MailHash *hash)
-{
-	if (hash->mmap_base == NULL)
-		return;
-
-	if (hash->anon_mmap) {
-		if (munmap_anon(hash->mmap_base, hash->mmap_length) < 0)
-			hash_set_syscall_error(hash, "munmap_anon()");
-
-		hash->anon_mmap = FALSE;
-	} else {
-		if (munmap(hash->mmap_base, hash->mmap_length) < 0)
-			hash_set_syscall_error(hash, "munmap()");
-	}
-
-	hash->mmap_base = NULL;
-}
-
-static MailHash *mail_hash_new(MailIndex *index)
-{
-	MailHash *hash;
-
-	hash = i_new(MailHash, 1);
-	hash->fd = -1;
-	hash->index = index;
-	hash->filepath = i_strconcat(index->filepath, ".hash", NULL);
-	index->hash = hash;
-	return hash;
-}
-
-int mail_hash_create(MailIndex *index)
-{
-	MailHash *hash;
-
-	i_assert(index->lock_type == MAIL_LOCK_EXCLUSIVE);
-
-	hash = mail_hash_new(index);
-	do {
-		if (!mail_hash_rebuild(hash))
-			break;
-
-		if (!hash->anon_mmap) {
-			if (!mmap_update_real(hash))
-				break;
-		}
-
-		if (!hash_verify_header(hash))
-			break;
-
-		return TRUE;
-	} while (0);
-
-	mail_hash_free(hash);
-	return FALSE;
-}
-
-int mail_hash_open_or_create(MailIndex *index)
-{
-	MailHash *hash;
-	int failed;
-
-	hash = mail_hash_new(index);
-
-	if (!mail_hash_file_open(hash))
-		return FALSE;
-
-	if (!mmap_update_real(hash)) {
-		/* mmap() failure is fatal */
-		mail_hash_free(hash);
-		return FALSE;
-	}
-
-	/* make sure the header looks fine */
-	if (!hash_verify_header(hash))
-		failed = TRUE;
-	else {
-		failed = hash->header->indexid != hash->index->indexid;
-		if (failed) {
-			index_set_error(hash->index,
-					"IndexID mismatch for hash file %s",
-					hash->filepath);
-		}
-	}
-
-	if (failed) {
-		/* recreate it */
-		hash_munmap(hash);
-
-		return mail_hash_rebuild(hash);
-	}
-
-	return TRUE;
-}
-
-void mail_hash_free(MailHash *hash)
-{
-	hash->index->hash = NULL;
-
-	hash_munmap(hash);
-
-	if (hash->fd != -1)
-		(void)close(hash->fd);
-	i_free(hash->filepath);
-	i_free(hash);
-}
-
-int mail_hash_sync_file(MailHash *hash)
-{
-	if (!hash->modified || hash->anon_mmap)
-		return TRUE;
-
-	if (msync(hash->mmap_base, hash->mmap_length, MS_SYNC) < 0)
-		return hash_set_syscall_error(hash, "msync()");
-
-	hash->modified = FALSE;
-	return TRUE;
-}
-
-static void hash_build(MailIndex *index, void *mmap_base,
-		       unsigned int hash_size)
-{
-	MailHashHeader *hdr;
-        MailHashRecord *rec;
-	MailIndexHeader *idx_hdr;
-	MailIndexRecord *idx_rec;
-	unsigned int i, count;
-
-	/* we have empty hash file mmap()ed now. fill it by reading the
-	   messages from index. */
-	rec = (MailHashRecord *) ((char *) mmap_base + sizeof(MailHashHeader));
-        idx_rec = index->lookup(index, 1);
-	for (count = 0; idx_rec != NULL; count++) {
-		i = HASH_FUNC(idx_rec->uid) % hash_size;
-		rec[i].uid = idx_rec->uid;
-		rec[i].position = INDEX_FILE_POSITION(index, idx_rec);
-		idx_rec = index->next(index, idx_rec);
-	}
-
-	idx_hdr = index->get_header(index);
-	if (count != idx_hdr->messages_count) {
-		/* mark this as an error but don't fail because of it. */
-		index_set_corrupted(index, "Missing messages while rebuilding "
-				    "hash file - %u found, header says %u",
-				    count, idx_hdr->messages_count);
-	}
-
-	/* setup header */
-	hdr = mmap_base;
-	hdr->indexid = index->indexid;
-	hdr->used_records = count;
-}
-
-static int hash_rebuild_to_file(MailIndex *index, int fd, const char *path,
-				unsigned int hash_size)
-{
-	void *mmap_base;
-	size_t mmap_length, new_size;
-	int failed;
-
-	i_assert(hash_size < MAX_HASH_SIZE);
-
-	new_size = HASH_FILE_SIZE(hash_size);
-
-	/* fill the file with zeros */
-	if (file_set_size(fd, (off_t)new_size) < 0) {
-		index_file_set_syscall_error(index, path, "file_set_size()");
-		return FALSE;
-	}
-
-	/* now, mmap() it */
-	mmap_base = mmap_rw_file(fd, &mmap_length);
-	if (mmap_base == MAP_FAILED)
-		return index_file_set_syscall_error(index, path, "mmap()");
-	i_assert(mmap_length == new_size);
-
-	hash_build(index, mmap_base, hash_size);
-
-	failed = FALSE;
-	if (msync(mmap_base, mmap_length, MS_SYNC) < 0) {
-		index_file_set_syscall_error(index, path, "msync()");
-		failed = TRUE;
-	}
-
-	/* we don't want to leave partially written hash around */
-	if (!failed && fsync(fd) < 0) {
-		index_file_set_syscall_error(index, path, "fsync()");
-		failed = TRUE;
-	}
-
-	if (munmap(mmap_base, mmap_length) < 0) {
-		index_file_set_syscall_error(index, path, "munmap()");
-		failed = TRUE;
-	}
-
-	return !failed;
-}
-
-/* set indexid to 0 in hash file */
-static int mail_hash_mark_deleted(MailHash *hash)
-{
-	MailIndexDataHeader hdr;
-
-	if (hash->fd == -1) {
-		/* see if we can open it */
-		hash->fd = open(hash->filepath, O_RDWR);
-		if (hash->fd == -1)
-			return TRUE;
-	}
-
-	memset(&hdr, 0, sizeof(hdr));
-	if (write_full(hash->fd, &hdr, sizeof(hdr)) < 0)
-		return hash_set_syscall_error(hash, "write_full()");
-
-	return TRUE;
-}
-
-int mail_hash_rebuild(MailHash *hash)
-{
-	MailIndexHeader *index_header;
-	const char *path;
-	unsigned int hash_size;
-	int fd, failed;
-
-	if (!hash->index->set_lock(hash->index, MAIL_LOCK_EXCLUSIVE))
-		return FALSE;
-
-	/* figure out size for our hash */
-	index_header = hash->index->get_header(hash->index);
-	hash_size = primes_closest(index_header->messages_count * 100 /
-				   MIN_PERCENTAGE);
-	if (hash_size < MIN_HASH_SIZE)
-		hash_size = MIN_HASH_SIZE;
-
-	if (hash_size < index_header->messages_count ||
-	    hash_size > MAX_HASH_SIZE) {
-		/* either our calculation overflowed, or we reached the
-		   max. value primes_closest() gave us. and there's more
-		   mails - very unlikely. */
-		index_set_corrupted(hash->index, "Too many mails in mailbox "
-				    "(%u)", index_header->messages_count);
-		return FALSE;
-	}
-
-	if (hash->index->nodiskspace) {
-		/* out of disk space - don't even try building it to file */
-		fd = -1;
-		errno = ENOSPC;
-	} else {
-		/* build the hash in a temp file, renaming it to the real hash
-		   once finished */
-		fd = mail_index_create_temp_file(hash->index, &path);
-	}
-
-	if (fd != -1) {
-		failed = !hash_rebuild_to_file(hash->index, fd,
-					       path, hash_size);
-
-		if (!failed)
-			failed = !mail_hash_mark_deleted(hash);
-
-		if (!failed && rename(path, hash->filepath) < 0) {
-			index_set_error(hash->index, "rename(%s, %s) failed: "
-					"%m", path, hash->filepath);
-			failed = TRUE;
-		}
-
-		if (failed) {
-			int old_errno = errno;
-
-			(void)close(fd);
-			(void)unlink(path);
-			fd = -1;
-
-			errno = old_errno;
-		}
-	}
-
-	if (fd == -1) {
-		/* building hash to file failed. if it was because there
-		   was no space in disk, we could just as well keep it in
-		   memory */
-		if (errno != ENOSPC)
-			return FALSE;
-
-		hash_munmap(hash);
-
-		hash->mmap_length = HASH_FILE_SIZE(hash_size);
-		hash->mmap_base = mmap_anon(hash->mmap_length);
-		hash_build(hash->index, hash->mmap_base, hash_size);
-
-		/* make sure it doesn't exist anymore */
-		(void)unlink(hash->filepath);
-	}
-
-	/* switch fds */
-	if (hash->fd != -1)
-		(void)close(hash->fd);
-	hash->fd = fd;
-	hash->anon_mmap = fd == -1;
-
-	if (fd != -1) {
-		if (!mmap_update_real(hash) || !hash_verify_header(hash))
-			return FALSE;
-	}
-
-	return TRUE;
-}
-
-uoff_t mail_hash_lookup_uid(MailHash *hash, unsigned int uid)
-{
-        MailHashRecord *rec;
-	unsigned int hashidx, idx;
-
-	i_assert(uid > 0);
-	i_assert(hash->index->lock_type != MAIL_LOCK_UNLOCK);
-
-	if (!mmap_update(hash))
-		return 0;
-
-	hashidx = HASH_FUNC(uid) % hash->size;
-	rec = (MailHashRecord *) ((char *) hash->mmap_base +
-				  sizeof(MailHashHeader));
-
-	/* check from hash index to end of file */
-	for (idx = hashidx; idx < hash->size; idx++) {
-		if (rec[idx].uid == uid)
-			return rec[idx].position;
-
-		if (rec[idx].uid == 0) {
-			/* empty hash record - not found. */
-			return 0;
-		}
-	}
-
-	/* check from beginning of file to hash index */
-	for (idx = 0; idx < hashidx; idx++) {
-		if (rec[idx].uid == uid)
-			return rec[idx].position;
-
-		if (rec[idx].uid == 0) {
-			/* empty hash record - not found. */
-			return 0;
-		}
-	}
-
-	/* checked through the whole hash file. this really shouldn't happen,
-	   we should have rebuilt it long time ago.. */
-	return 0;
-}
-
-static MailHashRecord *hash_find_uid_or_free(MailHash *hash, unsigned int uid)
-{
-        MailHashRecord *rec;
-	unsigned int hashidx, idx;
-
-	hashidx = HASH_FUNC(uid) % hash->size;
-	rec = (MailHashRecord *) ((char *) hash->mmap_base +
-				  sizeof(MailHashHeader));
-
-	/* check from hash index to end of file */
-	for (idx = hashidx; idx < hash->size; idx++) {
-		if (rec[idx].uid == 0 || rec[idx].uid == uid)
-			return rec+idx;
-	}
-
-	/* check from beginning of file to hash index */
-	for (idx = 0; idx < hashidx; idx++) {
-		if (rec[idx].uid == 0 || rec[idx].uid == uid)
-			return rec+idx;
-	}
-
-	/* hash file is full */
-	return NULL;
-}
-
-void mail_hash_update(MailHash *hash, unsigned int uid, uoff_t pos)
-{
-	MailHashRecord *rec;
-	unsigned int max_used;
-
-	i_assert(uid > 0);
-	i_assert(hash->index->lock_type == MAIL_LOCK_EXCLUSIVE);
-
-	if (!mmap_update(hash))
-		return;
-
-	if (hash->header->used_records >
-	    hash->size * FORCED_REBUILD_PERCENTAGE / 100) {
-		/* we really need a rebuild. */
-		if (!mail_hash_rebuild(hash))
-			return;
-	}
-
-	/* place the hash into first free record after wanted position */
-	rec = hash_find_uid_or_free(hash, uid);
-
-	if (rec == NULL) {
-		/* this should never happen, we had already checked that
-		   at least 1/5 of hash was empty. except, if the header
-		   contained invalid record count for some reason. rebuild.. */
-		i_error("Hash file was 100%% full, rebuilding");
-		if (!mail_hash_rebuild(hash))
-			return;
-
-		rec = hash_find_uid_or_free(hash, uid);
-		i_assert(rec != NULL);
-	}
-
-	if (pos != 0) {
-		/* insert/update record */
-		if (rec->uid == 0) {
-			/* update records count, and see if hash is
-			   getting full */
-			max_used = hash->size / 100 * REBUILD_PERCENTAGE;
-			if (++hash->header->used_records > max_used) {
-				hash->index->set_flags |=
-					MAIL_INDEX_FLAG_REBUILD_HASH;
-			}
-		}
-		rec->uid = uid;
-		rec->position = pos;
-	} else {
-		/* delete record */
-		rec->uid = 0;
-		rec->position = 0;
-                hash->header->used_records--;
-	}
-
-	hash->modified = FALSE;
-}

--- a/src/lib-index/mail-hash.h	Sun Oct 06 00:47:33 2002 +0300
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,38 +0,0 @@
-#ifndef __MAIL_HASH_H
-#define __MAIL_HASH_H
-
-typedef struct _MailHashHeader MailHashHeader;
-typedef struct _MailHashRecord MailHashRecord;
-
-struct _MailHashHeader {
-	unsigned int indexid;
-	unsigned int used_records;
-};
-
-struct _MailHashRecord {
-	unsigned int uid;
-	uoff_t position;
-};
-
-/* Open or create a hash file for index. If the hash needs to be created,
-   it's also immediately built from the given index. */
-int mail_hash_create(MailIndex *index);
-int mail_hash_open_or_create(MailIndex *index);
-
-void mail_hash_free(MailHash *hash);
-
-/* Synchronize the hash file with memory map */
-int mail_hash_sync_file(MailHash *hash);
-
-/* Rebuild hash from index and reset the FLAG_REBUILD_HASH in header.
-   The index must have an exclusive lock before this function is called. */
-int mail_hash_rebuild(MailHash *hash);
-
-/* Returns position in index file to given UID, or 0 if not found. */
-uoff_t mail_hash_lookup_uid(MailHash *hash, unsigned int uid);
-
-/* Update hash file. If pos is 0, the record is deleted. This call may
-   rebuild the hash if it's too full. */
-void mail_hash_update(MailHash *hash, unsigned int uid, uoff_t pos);
-
-#endif

--- a/src/lib-index/mail-index-compress.c	Sun Oct 06 00:47:33 2002 +0300
+++ b/src/lib-index/mail-index-compress.c	Sun Oct 06 03:30:14 2002 +0300
@@ -5,7 +5,7 @@
 #include "mail-index.h"
 #include "mail-index-data.h"
 #include "mail-index-util.h"
-#include "mail-hash.h"
+#include "mail-tree.h"
 
 #include <stdio.h>
 #include <unistd.h>
@@ -45,6 +45,7 @@
 int mail_index_compress(MailIndex *index)
 {
 	MailIndexRecord *rec, *hole_rec, *end_rec;
+	uoff_t pos;
 
 	if (!index->set_lock(index, MAIL_LOCK_EXCLUSIVE))
 		return FALSE;
@@ -73,8 +74,9 @@
 	while (rec < end_rec) {
 		if (rec->uid != 0) {
 			memcpy(hole_rec, rec, sizeof(MailIndexRecord));
-			mail_hash_update(index->hash, rec->uid,
-					 INDEX_FILE_POSITION(index, hole_rec));
+			pos = INDEX_FILE_POSITION(index, hole_rec);
+			if (!mail_tree_update(index->tree, rec->uid, pos))
+				return FALSE;
 			hole_rec++;
 		}
 		rec++;

--- a/src/lib-index/mail-index-open.c	Sun Oct 06 00:47:33 2002 +0300
+++ b/src/lib-index/mail-index-open.c	Sun Oct 06 03:30:14 2002 +0300
@@ -10,7 +10,7 @@
 #include "mail-index.h"
 #include "mail-index-data.h"
 #include "mail-index-util.h"
-#include "mail-hash.h"
+#include "mail-tree.h"
 #include "mail-lockdir.h"
 #include "mail-modifylog.h"
 #include "mail-custom-flags.h"
@@ -21,7 +21,7 @@
 #include <fcntl.h>
 
 static const char *index_file_prefixes[] =
-	{ "data", "hash", "log", "log.2", NULL };
+	{ "data", "tree", "log", "log.2", NULL };
 
 static int delete_index(const char *path)
 {
@@ -189,7 +189,7 @@
 		index->inconsistent = FALSE;
 	}
 
-	if (!mail_hash_open_or_create(index))
+	if (!mail_tree_open_or_create(index))
 		return FALSE;
 	if (!mail_modifylog_open_or_create(index))
 		return FALSE;
@@ -206,8 +206,8 @@
 			return FALSE;
 	}
 
-	if (index->header->flags & MAIL_INDEX_FLAG_REBUILD_HASH) {
-		if (!mail_hash_rebuild(index->hash))
+	if (index->header->flags & MAIL_INDEX_FLAG_REBUILD_TREE) {
+		if (!mail_tree_rebuild(index->tree))
 			return FALSE;
 	}
 
@@ -434,7 +434,7 @@
 			break;
 		}
 
-		if (!mail_hash_create(index))
+		if (!mail_tree_create(index))
 			break;
 		if (!mail_modifylog_create(index))
 			break;

--- a/src/lib-index/mail-index.c	Sun Oct 06 00:47:33 2002 +0300
+++ b/src/lib-index/mail-index.c	Sun Oct 06 03:30:14 2002 +0300
@@ -8,7 +8,7 @@
 #include "mail-index.h"
 #include "mail-index-data.h"
 #include "mail-index-util.h"
-#include "mail-hash.h"
+#include "mail-tree.h"
 #include "mail-modifylog.h"
 #include "mail-custom-flags.h"
 
@@ -156,9 +156,9 @@
 		index->data = NULL;
 	}
 
-	if (index->hash != NULL) {
-                mail_hash_free(index->hash);
-		index->hash = NULL;
+	if (index->tree != NULL) {
+                mail_tree_free(index->tree);
+		index->tree = NULL;
 	}
 
 	if (index->modifylog != NULL) {
@@ -193,8 +193,8 @@
 
 	failed = FALSE;
 
-	if (index->hash != NULL) {
-		if (!mail_hash_sync_file(index->hash))
+	if (index->tree != NULL) {
+		if (!mail_tree_sync_file(index->tree))
 			failed = TRUE;
 	}
 
@@ -445,9 +445,9 @@
 MailIndexRecord *mail_index_lookup(MailIndex *index, unsigned int seq)
 {
 	MailIndexHeader *hdr;
-	MailIndexRecord *rec, *last_rec;
-	unsigned int rec_seq;
-	uoff_t seekpos;
+	MailIndexRecord *rec;
+	const char *format;
+	uoff_t pos;
 
 	i_assert(seq > 0);
 	i_assert(index->lock_type != MAIL_LOCK_UNLOCK);
@@ -467,73 +467,40 @@
 	if (!mail_index_verify_hole_range(index))
 		return NULL;
 
-	seekpos = sizeof(MailIndexHeader) +
+	pos = sizeof(MailIndexHeader) +
 		(uoff_t)(seq-1) * sizeof(MailIndexRecord);
-	if (seekpos + sizeof(MailIndexRecord) > index->mmap_used_length) {
-		/* minimum file position for wanted sequence would point
-		   ouside file, so it can't exist. however, header said it
-		   should be found.. */
-		i_assert(index->header->used_file_size ==
-			 index->mmap_used_length);
+	if (hdr->first_hole_position == 0 ||
+	    hdr->first_hole_position > pos) {
+		/* easy, it's just at the expected index */
+		format = "Invalid first_hole_position in header: %"PRIuUOFF_T;
+	} else {
+		/* find from binary tree */
+		pos = mail_tree_lookup_sequence(index->tree, seq);
+		if (pos == 0) {
+			index_set_corrupted(index, "Sequence %u not found from "
+					    "binary tree (%u msgs says header)",
+					    seq, hdr->messages_count);
+			return NULL;
+		}
+		format = "Invalid offset returned by binary tree: %"PRIuUOFF_T;
+	}
 
-		index_set_corrupted(index,
-				    "Header contains invalid message count");
+	if (pos < sizeof(MailIndexHeader) ||
+	    pos > index->mmap_used_length - sizeof(MailIndexRecord) ||
+	    (pos - sizeof(MailIndexHeader)) % sizeof(MailIndexRecord) != 0) {
+		index_set_corrupted(index, format, pos);
 		return NULL;
 	}
 
-	rec = (MailIndexRecord *) ((char *) index->mmap_base +
-				   sizeof(MailIndexHeader));
-	last_rec = (MailIndexRecord *) ((char *) index->mmap_base +
-					index->mmap_used_length -
-					sizeof(MailIndexRecord));
-
-	if (hdr->first_hole_position == 0 ||
-	    hdr->first_hole_position > seekpos) {
-		/* easy, it's just at the expected index */
-		rec += seq-1;
-		i_assert(rec <= last_rec);
-
-		if (rec->uid == 0) {
-			index_set_corrupted(index, "first_hole_position "
-					    "wasn't updated properly");
-			return NULL;
-		}
-
-		index->last_lookup = rec;
-		index->last_lookup_seq = seq;
-		return rec;
+	rec = (MailIndexRecord *) ((char *) index->mmap_base + pos);
+	if (rec->uid == 0) {
+		index_set_corrupted(index, format, pos);
+		return NULL;
 	}
 
-	/* we need to walk through the index to get to wanted position */
-
-	/* some mails are deleted, jump after the first known hole
-	   and start counting non-deleted messages.. */
-	rec_seq = INDEX_POSITION_INDEX(hdr->first_hole_position+1) + 1;
-	rec += rec_seq-1 + hdr->first_hole_records;
-
-	if (seq > index->last_lookup_seq && index->last_lookup_seq > rec_seq) {
-		/* we want to lookup data after last lookup -
-		   this helps us some */
-		rec = index->last_lookup;
-		rec_seq = index->last_lookup_seq;
-	}
-
-	i_assert(rec->uid != 0);
-
-	while (rec_seq < seq && rec <= last_rec) {
-		rec++;
-
-		if (rec->uid != 0)
-			rec_seq++;
-	}
-
-	if (rec_seq != seq)
-		return NULL;
-	else {
-		index->last_lookup = rec;
-		index->last_lookup_seq = rec_seq;
-		return rec;
-	}
+	index->last_lookup = rec;
+	index->last_lookup_seq = seq;
+	return rec;
 }
 
 MailIndexRecord *mail_index_next(MailIndex *index, MailIndexRecord *rec)
@@ -559,89 +526,32 @@
 
 MailIndexRecord *mail_index_lookup_uid_range(MailIndex *index,
 					     unsigned int first_uid,
-					     unsigned int last_uid)
+					     unsigned int last_uid,
+					     unsigned int *seq_r)
 {
-	MailIndexRecord *rec, *end_rec;
-	unsigned int uid, last_try_uid;
+	MailIndexRecord *rec;
 	uoff_t pos;
 
 	i_assert(index->lock_type != MAIL_LOCK_UNLOCK);
 	i_assert(first_uid > 0 && last_uid > 0);
 	i_assert(first_uid <= last_uid);
 
-	if (!mail_index_verify_hole_range(index))
+	pos = mail_tree_lookup_uid_range(index->tree, seq_r,
+					 first_uid, last_uid);
+	if (pos == 0)
 		return NULL;
 
-	end_rec = (MailIndexRecord *) ((char *) index->mmap_base +
-				       index->mmap_used_length);
-
-	/* check if first_uid is the first UID in the index, or an UID
-	   before that. this is quite common and hash lookup would be
-	   useless to try with those nonexisting old UIDs */
-	if (index->header->first_hole_position != sizeof(MailIndexHeader)) {
-		rec = (MailIndexRecord *) ((char *) index->mmap_base +
-					   sizeof(MailIndexHeader));
-	} else {
-		rec = (MailIndexRecord *) ((char *) index->mmap_base +
-					   index->header->first_hole_position +
-					   index->header->first_hole_records *
-					   sizeof(MailIndexRecord));
-	}
-
-	if (rec >= end_rec) {
-		/* no messages in index */
-		return NULL;
-	}
-
-	if (first_uid <= rec->uid) {
-		/* yes, first_uid pointed to beginning of index.
-		   make sure last_uid is in that range too. */
-		return last_uid >= rec->uid ? rec : NULL;
-	}
-
-	if (first_uid >= index->header->next_uid) {
-		/* UID doesn't even exist yet */
+	rec = (MailIndexRecord *) ((char *) index->mmap_base + pos);
+	if (rec->uid < first_uid || rec->uid > last_uid) {
+		index_set_error(index, "Corrupted binary tree for index %s: "
+				"lookup returned offset to wrong UID "
+				"(%u vs %u..%u)", index->filepath,
+				rec->uid, first_uid, last_uid);
+		index->set_flags |= MAIL_INDEX_FLAG_REBUILD_TREE;
 		return NULL;
 	}
 
-	/* try the few first with hash lookups */
-	last_try_uid = last_uid - first_uid < 10 ? last_uid : first_uid + 4;
-	for (uid = first_uid; uid <= last_try_uid; uid++) {
-		pos = mail_hash_lookup_uid(index->hash, uid);
-		if (pos == 0)
-			continue;
-
-		rec = (MailIndexRecord *) ((char *) index->mmap_base + pos);
-		if (rec->uid != uid) {
-			index_set_error(index, "Corrupted hash for index %s: "
-					"lookup returned offset to different "
-					"UID (%u vs %u)", index->filepath,
-					rec->uid, uid);
-			index->set_flags |= MAIL_INDEX_FLAG_REBUILD_HASH;
-			rec = NULL;
-		}
-		return rec;
-	}
-
-	if (last_try_uid == last_uid)
-		return NULL;
-
-	/* fallback to looking through the whole index - this shouldn't be
-	   needed often, so don't bother trying anything too fancy. */
-	rec = (MailIndexRecord *) ((char *) index->mmap_base +
-				   sizeof(MailIndexHeader));
-	while (rec < end_rec) {
-		if (rec->uid != 0) {
-			if (rec->uid > last_uid)
-				return NULL;
-
-			if (rec->uid >= first_uid)
-				return rec;
-		}
-		rec++;
-	}
-
-	return NULL;
+	return rec;
 }
 
 static MailIndexDataRecord *
@@ -701,64 +611,6 @@
 	return datarec->data;
 }
 
-static unsigned int mail_index_get_sequence_real(MailIndex *index,
-						 MailIndexRecord *rec)
-{
-	MailIndexRecord *seekrec;
-	unsigned int seq;
-
-	i_assert(index->lock_type != MAIL_LOCK_UNLOCK);
-
-	if (rec == index->last_lookup) {
-		/* same as last lookup sequence - too easy */
-		return index->last_lookup_seq;
-	}
-
-	if (index->header->first_hole_position == 0) {
-		/* easy, it's just at the expected index */
-		return INDEX_POSITION_INDEX(
-			INDEX_FILE_POSITION(index, rec)) + 1;
-	}
-
-	if (!mail_index_verify_hole_range(index))
-		return 0;
-
-	seekrec = (MailIndexRecord *) ((char *) index->mmap_base +
-				       index->header->first_hole_position);
-	if (rec < seekrec) {
-		/* record before first hole */
-		return INDEX_POSITION_INDEX(
-			INDEX_FILE_POSITION(index, rec)) + 1;
-	}
-
-	/* we know the sequence after the first hole - skip to there and
-	   start browsing the records until ours is found */
-	seq = INDEX_POSITION_INDEX(INDEX_FILE_POSITION(index, seekrec))+1;
-	seekrec += index->header->first_hole_records;
-
-	for (; seekrec < rec; seekrec++) {
-		if (seekrec->uid != 0)
-			seq++;
-	}
-
-	return seq;
-}
-
-unsigned int mail_index_get_sequence(MailIndex *index, MailIndexRecord *rec)
-{
-	unsigned int seq;
-
-	seq = mail_index_get_sequence_real(index, rec);
-	if (seq > index->header->messages_count) {
-		index_set_corrupted(index, "Too small messages_count in header "
-				    "(found %u > %u)", seq,
-				    index->header->messages_count);
-		return 0;
-	}
-
-	return seq;
-}
-
 void mail_index_mark_flag_changes(MailIndex *index, MailIndexRecord *rec,
 				  MailFlags old_flags, MailFlags new_flags)
 {
@@ -858,11 +710,11 @@
 
 	/* expunge() may be called while index is being rebuilt and when
 	   there's no hash yet */
-	if (index->hash != NULL)
-		mail_hash_update(index->hash, rec->uid, 0);
+	if (index->tree != NULL)
+		mail_tree_delete(index->tree, rec->uid);
 	else {
 		/* make sure it also gets updated */
-		index->header->flags |= MAIL_INDEX_FLAG_REBUILD_HASH;
+		index->header->flags |= MAIL_INDEX_FLAG_REBUILD_TREE;
 	}
 
 	/* setting UID to 0 is enough for deleting the mail from index */
@@ -1030,8 +882,8 @@
 
 	rec->uid = index->header->next_uid++;
 
-	if (index->hash != NULL) {
-		mail_hash_update(index->hash, rec->uid,
+	if (index->tree != NULL) {
+		mail_tree_insert(index->tree, rec->uid,
 				 INDEX_FILE_POSITION(index, rec));
 	}
 

--- a/src/lib-index/mail-index.h	Sun Oct 06 00:47:33 2002 +0300
+++ b/src/lib-index/mail-index.h	Sun Oct 06 03:30:14 2002 +0300
@@ -21,7 +21,7 @@
 	MAIL_INDEX_FLAG_CACHE_FIELDS		= 0x04,
 	MAIL_INDEX_FLAG_COMPRESS		= 0x08,
 	MAIL_INDEX_FLAG_COMPRESS_DATA		= 0x10,
-	MAIL_INDEX_FLAG_REBUILD_HASH		= 0x20,
+	MAIL_INDEX_FLAG_REBUILD_TREE		= 0x20,
 	MAIL_INDEX_FLAG_DIRTY_MESSAGES		= 0x40,
 	MAIL_INDEX_FLAG_DIRTY_CUSTOMFLAGS	= 0x80
 };
@@ -80,7 +80,7 @@
 
 typedef struct _MailIndex MailIndex;
 typedef struct _MailIndexData MailIndexData;
-typedef struct _MailHash MailHash;
+typedef struct _MailTree MailTree;
 typedef struct _MailModifyLog MailModifyLog;
 typedef struct _MailCustomFlags MailCustomFlags;
 
@@ -222,10 +222,11 @@
 	   lookup() and last next() call. */
 	MailIndexRecord *(*next)(MailIndex *index, MailIndexRecord *rec);
 
-	/* First first existing UID in range. */
+	/* Find first existing UID in range. */
 	MailIndexRecord *(*lookup_uid_range)(MailIndex *index,
 					     unsigned int first_uid,
-					     unsigned int last_uid);
+					     unsigned int last_uid,
+					     unsigned int *seq_r);
 
 	/* Find field from specified record, or NULL if it's not in index.
 	   Makes sure that the field ends with \0. */
@@ -236,14 +237,11 @@
 	const void *(*lookup_field_raw)(MailIndex *index, MailIndexRecord *rec,
 					MailField field, size_t *size);
 
-	/* Returns sequence for given message, or 0 if failed. */
-	unsigned int (*get_sequence)(MailIndex *index, MailIndexRecord *rec);
-
 	/* Open mail file and return it as mmap()ed IOBuffer, or
 	   NULL if failed. */
 	IOBuffer *(*open_mail)(MailIndex *index, MailIndexRecord *rec);
 
-	/* Expunge a mail from index. Hash and modifylog is also updated. The
+	/* Expunge a mail from index. Tree and modifylog is also updated. The
 	   index must be exclusively locked before calling this function.
 	   If seq is 0, the modify log isn't updated. This is useful if
 	   after append() something goes wrong and you wish to delete the
@@ -310,7 +308,7 @@
 
 /* private: */
 	MailIndexData *data;
-	MailHash *hash;
+	MailTree *tree;
 	MailModifyLog *modifylog;
 	MailCustomFlags *custom_flags;
 
@@ -369,12 +367,12 @@
 MailIndexRecord *mail_index_next(MailIndex *index, MailIndexRecord *rec);
 MailIndexRecord *mail_index_lookup_uid_range(MailIndex *index,
 					     unsigned int first_uid,
-					     unsigned int last_uid);
+					     unsigned int last_uid,
+					     unsigned int *seq_r);
 const char *mail_index_lookup_field(MailIndex *index, MailIndexRecord *rec,
 				    MailField field);
 const void *mail_index_lookup_field_raw(MailIndex *index, MailIndexRecord *rec,
 					MailField field, size_t *size);
-unsigned int mail_index_get_sequence(MailIndex *index, MailIndexRecord *rec);
 int mail_index_expunge(MailIndex *index, MailIndexRecord *rec,
 		       unsigned int seq, int external_change);
 int mail_index_update_flags(MailIndex *index, MailIndexRecord *rec,

--- a/src/lib-index/mail-modifylog.c	Sun Oct 06 00:47:33 2002 +0300
+++ b/src/lib-index/mail-modifylog.c	Sun Oct 06 03:30:14 2002 +0300
@@ -174,7 +174,7 @@
 	}
 
 	log->header = log->mmap_base;
-	log->mmap_used_length = log->header->used_file_size;
+	log->mmap_used_length = hdr->used_file_size;
 	return TRUE;
 }
 

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/lib-index/mail-tree-redblack.c	Sun Oct 06 03:30:14 2002 +0300
@@ -0,0 +1,800 @@
+/*
+   Redblack balanced tree algorithm, http://libredblack.sourceforge.net/
+   Copyright (C) Damian Ivereigh 2000
+
+   Modified to be suitable for mmap()ing and for IMAP server
+   Copyright (C) Timo Sirainen 2002
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU Lesser General Public License as published by
+   the Free Software Foundation; either version 2.1 of the License, or
+   (at your option) any later version. See the file COPYING for details.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ */
+
+#include "lib.h"
+#include "mail-index.h"
+#include "mail-tree.h"
+
+#define DEBUG_TREE
+
+#ifndef DEBUG_TREE
+#  define rb_check(tree)
+#endif
+
+/* Dummy (sentinel) node, so that we can make X->left->up = X
+** We then use this instead of NULL to mean the top or bottom
+** end of the rb tree. It is a black node.
+*/
+#define RBNULL 0
+
+/*
+** OK here we go, the balanced tree stuff. The algorithm is the
+** fairly standard red/black taken from "Introduction to Algorithms"
+** by Cormen, Leiserson & Rivest. Maybe one of these days I will
+** fully understand all this stuff.
+**
+** Basically a red/black balanced tree has the following properties:-
+** 1) Every node is either red or black (color is RED or BLACK)
+** 2) A leaf (RBNULL pointer) is considered black
+** 3) If a node is red then its children are black
+** 4) Every path from a node to a leaf contains the same no
+**    of black nodes
+**
+** 3) & 4) above guarantee that the longest path (alternating
+** red and black nodes) is only twice as long as the shortest
+** path (all black nodes). Thus the tree remains fairly balanced.
+*/
+
+static unsigned int
+rb_alloc(MailTree *tree)
+{
+        MailTreeNode *node = tree->node_base;
+	unsigned int x;
+
+	if (tree->header->unused_root != RBNULL) {
+		/* use the nodes in the middle of the file */
+		x = tree->header->unused_root;
+		tree->header->unused_root = node[x].up;
+		return x;
+	}
+
+	/* use nodes at the end of file */
+	if (tree->mmap_used_length == tree->mmap_full_length) {
+		if (!_mail_tree_grow(tree))
+			return RBNULL;
+	}
+
+	i_assert(tree->header->used_file_size == tree->mmap_used_length);
+	i_assert(tree->mmap_used_length + sizeof(MailTreeNode) <=
+		 tree->mmap_full_length);
+
+	tree->header->used_file_size += sizeof(MailTreeNode);
+	tree->mmap_used_length += sizeof(MailTreeNode);
+
+	return (tree->mmap_used_length - sizeof(MailTreeHeader)) /
+		sizeof(MailTreeNode) - 1;
+}
+
+static void
+rb_free(MailTree *tree, unsigned int x)
+{
+        MailTreeNode *node = tree->node_base;
+
+	node[x].up = tree->header->unused_root;
+	tree->header->unused_root = x;
+}
+
+/*
+** Rotate our tree thus:-
+**
+**             X        rb_left_rotate(X)--->            Y
+**           /   \                                     /   \
+**          A     Y     <---rb_right_rotate(Y)        X     C
+**              /   \                               /   \
+**             B     C                             A     B
+**
+** N.B. This does not change the ordering.
+**
+** We assume that neither X or Y is NULL
+**
+** Node count changes:
+**   X += C+1              X -= C+1
+**   Y -= A+1              Y += A+1
+*/
+
+static void
+rb_left_rotate(MailTree *tree, unsigned int x)
+{
+	MailTreeNode *node = tree->node_base;
+	unsigned int y, a_nodes, c_nodes;
+
+	i_assert(x != RBNULL);
+	i_assert(node[x].right != RBNULL);
+
+	y = node[x].right;
+	a_nodes = node[node[x].left].node_count;
+	c_nodes = node[node[y].right].node_count;
+
+	/* Turn Y's left subtree into X's right subtree (move B) */
+	node[x].right = node[y].left;
+
+	/* If B is not null, set it's parent to be X */
+	if (node[y].left != RBNULL)
+		node[node[y].left].up = x;
+
+	/* Set Y's parent to be what X's parent was */
+	node[y].up = node[x].up;
+
+	/* if X was the root */
+	if (node[x].up == RBNULL) {
+		tree->header->root = y;
+	} else {
+		/* Set X's parent's left or right pointer to be Y */
+		if (x == node[node[x].up].left)
+			node[node[x].up].left = y;
+		else
+			node[node[x].up].right = y;
+	}
+
+	/* Put X on Y's left */
+	node[y].left = x;
+
+	/* Set X's parent to be Y */
+	node[x].up = y;
+
+	/* Update node counts */
+	node[x].node_count -= c_nodes+1;
+	node[y].node_count += a_nodes+1;
+}
+
+static void
+rb_right_rotate(MailTree *tree, unsigned int y)
+{
+	MailTreeNode *node = tree->node_base;
+	unsigned int x, a_nodes, c_nodes;
+
+	i_assert(y != RBNULL);
+	i_assert(node[y].left != RBNULL);
+
+	x = node[y].left;
+	a_nodes = node[node[x].left].node_count;
+	c_nodes = node[node[y].right].node_count;
+
+	/* Turn X's right subtree into Y's left subtree (move B) */
+	node[y].left = node[x].right;
+
+	/* If B is not null, set it's parent to be Y */
+	if (node[x].right != RBNULL)
+		node[node[x].right].up = y;
+
+	/* Set X's parent to be what Y's parent was */
+	node[x].up = node[y].up;
+
+	/* if Y was the root */
+	if (node[y].up == RBNULL)
+		tree->header->root = x;
+	else {
+		/* Set Y's parent's left or right pointer to be X */
+		if (y == node[node[y].up].left)
+			node[node[y].up].left = x;
+		else
+			node[node[y].up].right = x;
+	}
+
+	/* Put Y on X's right */
+	node[x].right = y;
+
+	/* Set Y's parent to be X */
+	node[y].up = x;
+
+	/* Update node counts */
+	node[x].node_count += c_nodes+1;
+	node[y].node_count -= a_nodes+1;
+}
+
+/* Return index to the smallest key greater than x
+*/
+static unsigned int 
+rb_successor(MailTree *tree, unsigned int x)
+{
+	MailTreeNode *node = tree->node_base;
+	unsigned int y;
+
+	if (node[x].right != RBNULL) {
+		/* If right is not NULL then go right one and
+		** then keep going left until we find a node with
+		** no left pointer.
+		*/
+		y = node[x].right;
+		while (node[y].left != RBNULL)
+			y = node[y].left;
+	} else {
+		/* Go up the tree until we get to a node that is on the
+		** left of its parent (or the root) and then return the
+		** parent.
+		*/
+		y = node[x].up;
+		while (y != RBNULL && x == node[y].right) {
+			x = y;
+			y = node[y].up;
+		}
+	}
+
+	return y;
+}
+
+/* Restore the reb-black properties after insert */
+static int
+rb_insert_fix(MailTree *tree, unsigned int z)
+{
+	MailTreeNode *node = tree->node_base;
+	unsigned int x, y, x_up_up;
+
+	/* color this new node red */
+	node[z].color = RED;
+
+	/* Having added a red node, we must now walk back up the tree balancing
+	** it, by a series of rotations and changing of colors
+	*/
+	x = z;
+
+	/* While we are not at the top and our parent node is red
+	** N.B. Since the root node is garanteed black, then we
+	** are also going to stop if we are the child of the root
+	*/
+
+	while (x != tree->header->root && node[node[x].up].color == RED) {
+		/* if our parent is on the left side of our grandparent */
+		x_up_up = node[node[x].up].up;
+		if (node[x].up == node[x_up_up].left) {
+			/* get the right side of our grandparent (uncle?) */
+			y = node[x_up_up].right;
+			if (node[y].color == RED) {
+				/* make our parent black */
+				node[node[x].up].color = BLACK;
+				/* make our uncle black */
+				node[y].color = BLACK;
+				/* make our grandparent red */
+				node[x_up_up].color = RED;
+
+				/* now consider our grandparent */
+				x = x_up_up;
+			} else {
+				/* if we are on the right side of our parent */
+				if (x == node[node[x].up].right) {
+					/* Move up to our parent */
+					x = node[x].up;
+					rb_left_rotate(tree, x);
+				}
+
+				/* make our parent black */
+				node[node[x].up].color = BLACK;
+				/* make our grandparent red */
+				node[x_up_up].color = RED;
+				/* right rotate our grandparent */
+				rb_right_rotate(tree, x_up_up);
+			}
+		} else {
+			/* everything here is the same as above, but
+			** exchanging left for right
+			*/
+
+			y = node[x_up_up].left;
+			if (node[y].color == RED) {
+				node[node[x].up].color = BLACK;
+				node[y].color = BLACK;
+				node[x_up_up].color = RED;
+
+				x = x_up_up;
+			} else {
+				if (x == node[node[x].up].left) {
+					x = node[x].up;
+					rb_right_rotate(tree, x);
+				}
+
+				node[node[x].up].color = BLACK;
+				node[x_up_up].color = RED;
+				rb_left_rotate(tree, x_up_up);
+			}
+		}
+	}
+
+	/* Set the root node black */
+	node[tree->header->root].color = BLACK;
+	return z;
+}
+
+/* Restore the reb-black properties after a delete */
+static void
+rb_delete_fix(MailTree *tree, unsigned int x)
+{
+	MailTreeNode *node = tree->node_base;
+	unsigned int w;
+
+	while (x != tree->header->root && node[x].color == BLACK) {
+		if (x == node[node[x].up].left) {
+			w = node[node[x].up].right;
+			if (node[w].color == RED) {
+				node[w].color = BLACK;
+				node[node[x].up].color = RED;
+				rb_left_rotate(tree, node[x].up);
+				w = node[node[x].up].right;
+			}
+
+			if (node[node[w].left].color == BLACK &&
+			    node[node[w].right].color == BLACK) {
+				node[w].color = RED;
+				x = node[x].up;
+			} else {
+				if (node[node[w].right].color == BLACK) {
+					node[node[w].left].color = BLACK;
+					node[w].color = RED;
+					rb_right_rotate(tree, w);
+					w = node[node[x].up].right;
+				}
+
+
+				node[w].color = node[node[x].up].color;
+				node[node[x].up].color = BLACK;
+				node[node[w].right].color = BLACK;
+				rb_left_rotate(tree, node[x].up);
+				x = tree->header->root;
+			}
+		} else {
+			w = node[node[x].up].left;
+			if (node[w].color == RED) {
+				node[w].color = BLACK;
+				node[node[x].up].color = RED;
+				rb_right_rotate(tree, node[x].up);
+				w = node[node[x].up].left;
+			}
+
+			if (node[node[w].right].color == BLACK &&
+			    node[node[w].left].color == BLACK) {
+				node[w].color = RED;
+				x = node[x].up;
+			} else {
+				if (node[node[w].left].color == BLACK) {
+					node[node[w].right].color = BLACK;
+					node[w].color = RED;
+					rb_left_rotate(tree, w);
+					w = node[node[x].up].left;
+				}
+
+				node[w].color = node[node[x].up].color;
+				node[node[x].up].color = BLACK;
+				node[node[w].left].color = BLACK;
+				rb_right_rotate(tree, node[x].up);
+				x = tree->header->root;
+			}
+		}
+	}
+
+	node[x].color = BLACK;
+}
+
+/*
+** case 1 - only one child:
+**
+**            Z       -->  Y
+**           /
+**          Y
+**
+** Node count changes:
+**   parents -= 1
+**
+** case 2 - right child has no left child:
+**
+**             Z              Y
+**           /   \          /   \
+**          A     Y   -->  A     X
+**                  \
+**                   X
+**
+** Node count changes:
+**   parents -= 1
+**   Y = Z-1
+**
+** case 3 - right child has left child:
+**
+**             Z              Y
+**           /   \          /   \
+**          A     B   -->  A     B
+**              /              /
+**            ..             ..
+**           /              /
+**          Y              X
+**           \
+**            X
+**
+** Node count changes:
+**   parents -= 1
+**   Y = Z-1
+**   B .. X.up -= 1 (NOTE: X may not exist)
+*/
+
+/* Delete the node z, and free up the space
+*/
+static void
+rb_delete(MailTree *tree, unsigned int z)
+{
+	MailTreeNode *node = tree->node_base;
+        unsigned int x, y, b;
+
+	if (node[z].left == RBNULL || node[z].right == RBNULL) {
+		y = z;
+		b = RBNULL;
+	} else {
+		y = rb_successor(tree, z);
+		if (y == node[z].right)
+			b = RBNULL;
+		else
+			b = node[z].right;
+	}
+
+	if (node[y].left != RBNULL)
+		x = node[y].left;
+	else
+		x = node[y].right;
+
+	if (x != RBNULL)
+		node[x].up = node[y].up;
+
+	if (node[y].up == RBNULL) {
+		tree->header->root = x;
+	} else {
+		if (y == node[node[y].up].left)
+			node[node[y].up].left = x;
+		else
+			node[node[y].up].right = x;
+	}
+
+	if (y != z) {
+		node[z].key = node[y].key;
+		node[z].value = node[y].value;
+	}
+
+	if (b != RBNULL) {
+		/* case 3 updates */
+		while (b != x) {
+			node[b].node_count--;
+			b = node[b].left;
+		}
+	}
+
+	while (z != RBNULL) {
+		node[b].node_count--;
+		z = node[z].up;
+	}
+
+	if (node[y].color == BLACK)
+		rb_delete_fix(tree, x);
+
+	rb_free(tree, y);
+}
+
+#ifdef DEBUG_TREE
+int
+rb_check1(MailTree *tree, unsigned int x)
+{
+        MailTreeNode *node = tree->node_base;
+
+	if (node[x].color == RED) {
+		if (node[node[x].left].color != BLACK &&
+		    node[node[x].right].color != BLACK) {
+			i_error("Children of red node not both black, x=%u", x);
+			return -1;
+		}
+	}
+
+	if (node[x].left != RBNULL) {
+		if (node[node[x].left].up != x) {
+			i_error("x->left->up != x, x=%u", x);
+			return -1;
+		}
+
+		if (rb_check1(tree, node[x].left))
+			return -1;
+	}		
+
+	if (node[x].right != RBNULL) {
+		if (node[node[x].right].up != x) {
+			i_error("x->right->up != x, x=%u", x);
+			return -1;
+		}
+
+		if (rb_check1(tree, node[x].right))
+			return -1;
+	}
+
+	return 0;
+}
+
+int count_black(MailTree *tree, unsigned int x)
+{
+        MailTreeNode *node = tree->node_base;
+	int nleft, nright;
+
+	if (x == RBNULL)
+		return 1;
+
+	nleft = count_black(tree, node[x].left);
+	nright = count_black(tree, node[x].right);
+
+	if (nleft == -1 || nright == -1)
+		return -1;
+
+	if (nleft != nright) {
+		i_error("Black count not equal on left & right, x=%u", x);
+		return -1;
+	}
+
+	if (node[x].color == BLACK)
+		nleft++;
+
+	return nleft;
+}
+
+int count_nodes(MailTree *tree, unsigned int x)
+{
+        MailTreeNode *node = tree->node_base;
+	int nleft, nright;
+
+	if (x == RBNULL)
+		return 0;
+
+	nleft = count_nodes(tree, node[x].left);
+	nright = count_nodes(tree, node[x].right);
+
+	if (nleft == -1 || nright == -1)
+		return -1;
+
+	if (nleft+nright+1 != (int)node[x].node_count) {
+		i_error("Invalid node count, x=%u, %d+%d+1 != %u",
+			x, nleft, nright, node[x].node_count);
+		return -1;
+	}
+
+	return nleft+nright+1;
+}
+
+void dumptree(MailTree *tree, unsigned int x, int n)
+{
+        MailTreeNode *node = tree->node_base;
+
+	if (x != RBNULL) {
+		n++;
+		i_error("Tree: %*s %u: left=%u, right=%u, color=%s, nodes=%u, key=%u",
+			n, "", x, node[x].left, node[x].right,
+			node[x].color == BLACK ? "BLACK" : "RED",
+			node[x].node_count, node[x].key);
+
+		dumptree(tree, node[x].left, n);
+		dumptree(tree, node[x].right, n);
+	}	
+}
+
+int
+rb_check(MailTree *tree)
+{
+        MailTreeNode *node = tree->node_base;
+	unsigned int root;
+
+	root = tree->header->root;
+	if (root == RBNULL)
+		return 0;
+
+	if (node[root].up != RBNULL) {
+		i_error("Root up pointer not RBNULL");
+		dumptree(tree, root, 0);
+		return 1;
+	}
+
+	if (rb_check1(tree, root)) {
+		dumptree(tree, root, 0);
+		return 1;
+	}
+
+	if (count_black(tree, root) == -1) {
+		dumptree(tree, root, 0);
+		return -1;
+	}
+
+	if (count_nodes(tree, root) == -1) {
+		dumptree(tree, root, 0);
+		return -1;
+	}
+
+	return 0;
+}
+#endif
+
+uoff_t mail_tree_lookup_uid_range(MailTree *tree, unsigned int *seq_r,
+				  unsigned int first_uid,
+				  unsigned int last_uid)
+{
+	MailTreeNode *node = tree->node_base;
+	unsigned int x, y, seq;
+
+	i_assert(tree->index->lock_type != MAIL_LOCK_UNLOCK);
+
+	rb_check(tree);
+
+	*seq_r = 0;
+
+	y = RBNULL; /* points to the parent of x */
+	x = tree->header->root;
+
+	/* walk x down the tree */
+	seq = 0;
+	while (x != RBNULL) {
+		y = x;
+
+		if (first_uid < node[x].key)
+			x = node[x].left;
+		else {
+			seq += node[node[x].left].node_count+1;
+			if (first_uid > node[x].key)
+				x = node[x].right;
+			else {
+				/* found it */
+				*seq_r = seq;
+				return node[x].value;
+			}
+		}
+	}
+
+	if (first_uid < last_uid) {
+		/* get the next key, make sure it's in range */
+		x = rb_successor(tree, y);
+		if (node[x].key <= last_uid)
+			*seq_r = seq+1;
+		else
+			x = RBNULL;
+	}
+
+	return x == RBNULL ? 0 : node[x].value;
+}
+
+uoff_t mail_tree_lookup_sequence(MailTree *tree, unsigned int seq)
+{
+        MailTreeNode *node = tree->node_base;
+	unsigned int x, upleft_nodes, left_nodes;
+
+	i_assert(tree->index->lock_type != MAIL_LOCK_UNLOCK);
+
+	rb_check(tree);
+
+	x = tree->header->root;
+
+	/* walk x down the tree */
+	seq--;
+	upleft_nodes = left_nodes = 0;
+	while (x != RBNULL) {
+		left_nodes = upleft_nodes + node[node[x].left].node_count;
+
+		if (seq < left_nodes)
+			x = node[x].left;
+		else if (seq > left_nodes) {
+			upleft_nodes = left_nodes;
+			x = node[x].right;
+		} else {
+			/* found it */
+			return node[x].value;
+		}
+	}
+
+	return 0;
+}
+
+int mail_tree_insert(MailTree *tree, unsigned int uid, uoff_t pos)
+{
+        MailTreeNode *node = tree->node_base;
+	unsigned int x, z;
+
+	i_assert(tree->index->lock_type == MAIL_LOCK_EXCLUSIVE);
+
+	tree->modified = TRUE;
+
+	/* we'll always insert to right side of the tree */
+	x = tree->header->root;
+	if (x != RBNULL) {
+		while (node[x].right != RBNULL)
+			x = node[x].right;
+	}
+
+	if (node[x].key >= uid) {
+		_mail_tree_set_corrupted(tree,
+			"UID to be inserted isn't higher than existing "
+			"(%u <= %u)", uid, node[x].key);
+		return FALSE;
+	}
+
+	if ((z = rb_alloc(tree)) == RBNULL)
+		return FALSE;
+
+	node[z].key = uid;
+	node[z].value = pos;
+	node[z].up = x;
+	node[z].node_count = 1;
+	node[z].left = RBNULL;
+	node[z].right = RBNULL;
+
+	if (x == RBNULL)
+		tree->header->root = z;
+	else {
+		if (node[z].key < node[x].key)
+			node[x].left = z;
+		else
+			node[x].right = z;
+	}
+
+	for (; x != RBNULL; x = node[x].up)
+	     node[x].node_count++;
+
+        rb_insert_fix(tree, z);
+        rb_check(tree);
+	return TRUE;
+}
+
+int mail_tree_update(MailTree *tree, unsigned int uid, uoff_t pos)
+{
+	MailTreeNode *node = tree->node_base;
+	unsigned int x;
+
+	i_assert(tree->index->lock_type == MAIL_LOCK_EXCLUSIVE);
+
+	rb_check(tree);
+
+	tree->modified = TRUE;
+
+	x = tree->header->root;
+	while (x != RBNULL) {
+		if (uid < node[x].key)
+			x = node[x].left;
+		else if (uid > node[x].key)
+			x = node[x].right;
+		else {
+			/* found it */
+			node[x].value = pos;
+			return TRUE;
+		}
+	}
+
+	_mail_tree_set_corrupted(tree, "Tried to update nonexisting UID %u",
+				 uid);
+	return FALSE;
+}
+
+void mail_tree_delete(MailTree *tree, unsigned int uid)
+{
+	MailTreeNode *node = tree->node_base;
+	unsigned int x;
+
+	i_assert(tree->index->lock_type == MAIL_LOCK_EXCLUSIVE);
+
+	tree->modified = TRUE;
+
+	x = tree->header->root;
+	while (x != RBNULL) {
+		if (uid < node[x].key)
+			x = node[x].left;
+		else if (uid > node[x].key)
+			x = node[x].right;
+		else {
+			/* found it */
+			rb_delete(tree, x);
+			rb_check(tree);
+			break;
+		}
+	}
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/lib-index/mail-tree.c	Sun Oct 06 03:30:14 2002 +0300
@@ -0,0 +1,345 @@
+/* Copyright (C) 2002 Timo Sirainen */
+
+#include "lib.h"
+#include "mmap-util.h"
+#include "file-set-size.h"
+#include "write-full.h"
+#include "mail-index.h"
+#include "mail-index-util.h"
+#include "mail-tree.h"
+
+#include <unistd.h>
+#include <fcntl.h>
+
+#define MAIL_TREE_INITIAL_SIZE \
+	(sizeof(MailTreeHeader) + sizeof(MailTreeNode) * 64)
+
+#define TREE_GROW_SIZE \
+	(sizeof(MailTreeNode) * 64)
+
+static int tree_set_syscall_error(MailTree *tree, const char *function)
+{
+	i_assert(function != NULL);
+
+	index_set_error(tree->index, "%s failed with tree file %s: %m",
+			function, tree->filepath);
+	return FALSE;
+}
+
+int _mail_tree_set_corrupted(MailTree *tree, const char *fmt, ...)
+{
+	va_list va;
+
+	va_start(va, fmt);
+	t_push();
+
+	index_set_error(tree->index, "Corrupted tree file %s: %s",
+			tree->filepath, t_strdup_vprintf(fmt, va));
+
+	t_pop();
+	va_end(va);
+
+	/* make sure we don't get back here */
+	tree->index->inconsistent = TRUE;
+	(void)unlink(tree->filepath);
+
+	return FALSE;
+}
+
+static int mmap_update(MailTree *tree, int forced)
+{
+	if (!forced && tree->header != NULL &&
+	    tree->mmap_full_length >= tree->header->used_file_size) {
+		tree->mmap_used_length = tree->header->used_file_size;
+		return TRUE;
+	}
+
+	i_assert(!tree->anon_mmap);
+
+	if (tree->mmap_base != NULL) {
+		/* make sure we're synced before munmap() */
+		if (tree->modified &&
+		    msync(tree->mmap_base, tree->mmap_used_length, MS_SYNC) < 0)
+			return tree_set_syscall_error(tree, "msync()");
+
+		if (munmap(tree->mmap_base, tree->mmap_full_length) < 0)
+			tree_set_syscall_error(tree, "munmap()");
+	}
+
+	tree->mmap_used_length = 0;
+	tree->header = NULL;
+	tree->node_base = NULL;
+
+	tree->mmap_base = mmap_rw_file(tree->fd, &tree->mmap_full_length);
+	if (tree->mmap_base == MAP_FAILED) {
+		tree->mmap_base = NULL;
+		return tree_set_syscall_error(tree, "mmap()");
+	}
+
+	return TRUE;
+}
+
+static int mmap_verify(MailTree *tree)
+{
+	MailTreeHeader *hdr;
+	unsigned int extra;
+
+	if (tree->mmap_full_length <
+	    sizeof(MailTreeHeader) + sizeof(MailTreeNode)) {
+		index_set_error(tree->index, "Too small tree file %s",
+				tree->filepath);
+		(void)unlink(tree->filepath);
+		return FALSE;
+	}
+
+	extra = (tree->mmap_full_length - sizeof(MailTreeHeader)) %
+		sizeof(MailTreeNode);
+
+	if (extra != 0) {
+		/* partial write or corrupted -
+		   truncate the file to valid length */
+		tree->mmap_full_length -= extra;
+		if (ftruncate(tree->fd, (off_t)tree->mmap_full_length) < 0)
+			tree_set_syscall_error(tree, "ftruncate()");
+	}
+
+	hdr = tree->mmap_base;
+	if (hdr->used_file_size > tree->mmap_full_length) {
+		_mail_tree_set_corrupted(tree,
+			"used_file_size larger than real file size "
+			"(%"PRIuUOFF_T" vs %"PRIuSIZE_T")",
+			hdr->used_file_size, tree->mmap_full_length);
+		return FALSE;
+	}
+
+	if ((hdr->used_file_size - sizeof(MailTreeHeader)) %
+	    sizeof(MailTreeNode) != 0) {
+		_mail_tree_set_corrupted(tree,
+			"Invalid used_file_size in header (%"PRIuUOFF_T")",
+			hdr->used_file_size);
+		return FALSE;
+	}
+
+	tree->header = tree->mmap_base;
+	tree->node_base = (MailTreeNode *) ((char *) tree->mmap_base +
+					    sizeof(MailTreeHeader));
+	tree->mmap_used_length = hdr->used_file_size;
+	return TRUE;
+}
+
+static MailTree *mail_tree_open(MailIndex *index)
+{
+	MailTree *tree;
+	const char *path;
+	int fd;
+
+	path = t_strconcat(index->filepath, ".tree", NULL);
+	fd = open(path, O_RDWR | O_CREAT, 0660);
+	if (fd == -1) {
+		if (errno == ENOSPC)
+			index->nodiskspace = TRUE;
+
+		index_file_set_syscall_error(index, path, "open()");
+		return NULL;
+	}
+
+	tree = i_new(MailTree, 1);
+	tree->fd = fd;
+	tree->index = index;
+	tree->filepath = i_strdup(path);
+
+	index->tree = tree;
+	return tree;
+}
+
+static void mail_tree_close(MailTree *tree)
+{
+	if (tree->anon_mmap) {
+		if (munmap_anon(tree->mmap_base, tree->mmap_full_length) < 0)
+			tree_set_syscall_error(tree, "munmap_anon()");
+	} else if (tree->mmap_base != NULL) {
+		if (munmap(tree->mmap_base, tree->mmap_full_length) < 0)
+			tree_set_syscall_error(tree, "munmap()");
+	}
+	tree->mmap_base = NULL;
+	tree->mmap_full_length = 0;
+	tree->mmap_used_length = 0;
+	tree->header = NULL;
+
+	if (tree->fd != -1) {
+		if (close(tree->fd) < 0)
+			tree_set_syscall_error(tree, "close()");
+		tree->fd = -1;
+	}
+
+	i_free(tree->filepath);
+}
+
+int mail_tree_create(MailIndex *index)
+{
+	MailTree *tree;
+
+	i_assert(index->lock_type == MAIL_LOCK_EXCLUSIVE);
+
+	tree = mail_tree_open(index);
+	if (tree == NULL)
+		return FALSE;
+
+	if (!mail_tree_rebuild(tree)) {
+		mail_tree_free(tree);
+		return FALSE;
+	}
+
+	return TRUE;
+}
+
+int mail_tree_open_or_create(MailIndex *index)
+{
+	MailTree *tree;
+
+	tree = mail_tree_open(index);
+	if (tree == NULL)
+		return FALSE;
+
+	do {
+		if (!mmap_update(tree, TRUE))
+			break;
+
+		if (tree->mmap_full_length == 0) {
+			/* just created it */
+			if (!mail_tree_rebuild(tree))
+				break;
+		} else if (!mmap_verify(tree)) {
+			/* broken header */
+			if (!mail_tree_rebuild(tree))
+				break;
+		} else if (tree->header->indexid != index->indexid) {
+			index_set_error(tree->index,
+				"IndexID mismatch for binary tree file %s",
+				tree->filepath);
+
+			if (!mail_tree_rebuild(tree))
+				break;
+		}
+
+		return TRUE;
+	} while (0);
+
+	mail_tree_free(tree);
+	return FALSE;
+}
+
+void mail_tree_free(MailTree *tree)
+{
+	tree->index->tree = NULL;
+
+	mail_tree_close(tree);
+	i_free(tree);
+}
+
+static int mail_tree_init(MailTree *tree)
+{
+        MailTreeHeader hdr;
+
+	/* first node is always used, and is the RBNULL node */
+	memset(&hdr, 0, sizeof(MailTreeHeader));
+	hdr.indexid = tree->index->indexid;
+	hdr.used_file_size = sizeof(MailTreeHeader) + sizeof(MailTreeNode);
+
+	if (write_full(tree->fd, &hdr, sizeof(hdr)) < 0) {
+		if (errno == ENOSPC)
+			tree->index->nodiskspace = TRUE;
+
+		return tree_set_syscall_error(tree, "write_full()");
+	}
+
+	if (file_set_size(tree->fd, MAIL_TREE_INITIAL_SIZE) < 0) {
+		if (errno == ENOSPC)
+			tree->index->nodiskspace = TRUE;
+
+		return tree_set_syscall_error(tree, "file_set_size()");
+	}
+
+	return TRUE;
+
+}
+
+int mail_tree_rebuild(MailTree *tree)
+{
+	MailIndexRecord *rec;
+	uoff_t offset;
+
+	if (!tree->index->set_lock(tree->index, MAIL_LOCK_EXCLUSIVE))
+		return FALSE;
+
+	if (!mail_tree_init(tree) ||
+	    !mmap_update(tree, TRUE) ||
+	    !mmap_verify(tree)) {
+		tree->index->header->flags |= MAIL_INDEX_FLAG_REBUILD_TREE;
+		return FALSE;
+	}
+
+	rec = tree->index->lookup(tree->index, 1);
+	while (rec != NULL) {
+		offset = INDEX_FILE_POSITION(tree->index, rec);
+		if (!mail_tree_insert(tree, rec->uid, offset)) {
+			tree->index->header->flags |=
+				MAIL_INDEX_FLAG_REBUILD_TREE;
+			return FALSE;
+		}
+
+		rec = tree->index->next(tree->index, rec);
+	}
+
+	return TRUE;
+}
+
+int mail_tree_sync_file(MailTree *tree)
+{
+	if (!tree->modified || tree->anon_mmap)
+		return TRUE;
+
+	if (tree->mmap_base != NULL) {
+		if (msync(tree->mmap_base, tree->mmap_used_length, MS_SYNC) < 0)
+			return tree_set_syscall_error(tree, "msync()");
+	}
+
+	if (fsync(tree->fd) < 0)
+		return tree_set_syscall_error(tree, "fsync()");
+
+	tree->modified = FALSE;
+	return TRUE;
+}
+
+int _mail_tree_grow(MailTree *tree)
+{
+	uoff_t new_fsize;
+	void *base;
+
+	new_fsize = (uoff_t)tree->mmap_full_length + TREE_GROW_SIZE;
+	i_assert(new_fsize < OFF_T_MAX);
+
+	if (tree->anon_mmap) {
+		i_assert(new_fsize < SSIZE_T_MAX);
+
+		base = mremap_anon(tree->mmap_base, tree->mmap_full_length,
+				   (size_t)new_fsize, MREMAP_MAYMOVE);
+		if (base == MAP_FAILED)
+			return tree_set_syscall_error(tree, "mremap_anon()");
+
+		tree->mmap_base = base;
+		tree->mmap_full_length = (size_t)new_fsize;
+		return TRUE;
+	}
+
+	if (file_set_size(tree->fd, (off_t)new_fsize) < 0) {
+		if (errno == ENOSPC)
+			tree->index->nodiskspace = TRUE;
+		return tree_set_syscall_error(tree, "file_set_size()");
+	}
+
+	if (!mmap_update(tree, TRUE) || !mmap_verify(tree))
+		return FALSE;
+
+	return TRUE;
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/lib-index/mail-tree.h	Sun Oct 06 03:30:14 2002 +0300
@@ -0,0 +1,77 @@
+#ifndef __MAIL_TREE_H
+#define __MAIL_TREE_H
+
+typedef struct _MailTreeHeader MailTreeHeader;
+typedef struct _MailTreeNode MailTreeNode;
+
+enum nodecolor { BLACK = 0, RED };
+
+struct _MailTree {
+	MailIndex *index;
+
+	int fd;
+	char *filepath;
+
+	void *mmap_base;
+	MailTreeNode *node_base;
+	size_t mmap_used_length;
+	size_t mmap_full_length;
+
+        MailTreeHeader *header;
+	unsigned int anon_mmap:1;
+	unsigned int modified:1;
+};
+
+struct _MailTreeHeader {
+	unsigned int indexid;
+
+	unsigned int root;
+	unsigned int unused_root;
+
+	unsigned int alignment;
+	uoff_t used_file_size;
+};
+
+struct _MailTreeNode {
+	unsigned int left;
+	unsigned int right;
+	unsigned int up;
+	unsigned int color;
+
+	/* number of child nodes + 1, used to figure out message
+	   sequence numbers */
+	unsigned int node_count;
+
+	unsigned int key;
+	uoff_t value;
+};
+
+int mail_tree_create(MailIndex *index);
+int mail_tree_open_or_create(MailIndex *index);
+void mail_tree_free(MailTree *tree);
+
+int mail_tree_rebuild(MailTree *tree);
+int mail_tree_sync_file(MailTree *tree);
+
+/* Find first existing UID in range. */
+uoff_t mail_tree_lookup_uid_range(MailTree *tree, unsigned int *seq_r,
+				  unsigned int first_uid,
+				  unsigned int last_uid);
+
+/* Find message by sequence number. */
+uoff_t mail_tree_lookup_sequence(MailTree *tree, unsigned int seq);
+
+/* Insert a new record in tree. */
+int mail_tree_insert(MailTree *tree, unsigned int uid, uoff_t pos);
+
+/* Update existing record in tree. */
+int mail_tree_update(MailTree *tree, unsigned int uid, uoff_t pos);
+
+/* Delete record from tree. */
+void mail_tree_delete(MailTree *tree, unsigned int uid);
+
+/* private: */
+int _mail_tree_set_corrupted(MailTree *tree, const char *fmt, ...);
+int _mail_tree_grow(MailTree *tree);
+
+#endif

--- a/src/lib-index/maildir/maildir-index.c	Sun Oct 06 00:47:33 2002 +0300
+++ b/src/lib-index/maildir/maildir-index.c	Sun Oct 06 03:30:14 2002 +0300
@@ -215,7 +215,6 @@
         mail_index_lookup_uid_range,
 	mail_index_lookup_field,
 	mail_index_lookup_field_raw,
-	mail_index_get_sequence,
 	maildir_open_mail,
 	mail_index_expunge,
 	maildir_index_update_flags,

--- a/src/lib-index/maildir/maildir-rebuild.c	Sun Oct 06 00:47:33 2002 +0300
+++ b/src/lib-index/maildir/maildir-rebuild.c	Sun Oct 06 03:30:14 2002 +0300
@@ -4,7 +4,6 @@
 #include "maildir-index.h"
 #include "mail-index-data.h"
 #include "mail-index-util.h"
-#include "mail-hash.h"
 
 #include <unistd.h>
 #include <sys/stat.h>

--- a/src/lib-index/mbox/mbox-index.c	Sun Oct 06 00:47:33 2002 +0300
+++ b/src/lib-index/mbox/mbox-index.c	Sun Oct 06 03:30:14 2002 +0300
@@ -471,7 +471,6 @@
         mail_index_lookup_uid_range,
 	mail_index_lookup_field,
 	mail_index_lookup_field_raw,
-	mail_index_get_sequence,
 	mbox_open_mail,
 	mail_index_expunge,
 	mbox_index_update_flags,

--- a/src/lib-index/mbox/mbox-rebuild.c	Sun Oct 06 00:47:33 2002 +0300
+++ b/src/lib-index/mbox/mbox-rebuild.c	Sun Oct 06 03:30:14 2002 +0300
@@ -6,7 +6,6 @@
 #include "mbox-lock.h"
 #include "mail-index-data.h"
 #include "mail-index-util.h"
-#include "mail-hash.h"
 
 #include <unistd.h>
 #include <fcntl.h>

--- a/src/lib-storage/index/index-expunge.c	Sun Oct 06 00:47:33 2002 +0300
+++ b/src/lib-storage/index/index-expunge.c	Sun Oct 06 03:30:14 2002 +0300
@@ -23,7 +23,7 @@
 		*rec = hdr->first_deleted_uid_lowwater >= hdr->next_uid ? NULL :
 			ibox->index->lookup_uid_range(ibox->index,
 						hdr->first_deleted_uid_lowwater,
-						hdr->next_uid-1);
+						hdr->next_uid-1, seq);
 		if (*rec == NULL) {
 			mail_storage_set_critical(ibox->box.storage,
 				"index header's deleted_messages_count (%u) "
@@ -34,8 +34,6 @@
 			/* fsck should be enough to fix it */
 			ibox->index->set_flags |= MAIL_INDEX_FLAG_FSCK;
 			return FALSE;
-		} else {
-			*seq = ibox->index->get_sequence(ibox->index, *rec);
 		}
 	} else {
 		*rec = ibox->index->lookup(ibox->index, 1);

--- a/src/lib-storage/index/index-messageset.c	Sun Oct 06 00:47:33 2002 +0300
+++ b/src/lib-storage/index/index-messageset.c	Sun Oct 06 03:30:14 2002 +0300
@@ -3,7 +3,6 @@
 #include "lib.h"
 #include "mail-index.h"
 #include "mail-index-util.h"
-#include "mail-hash.h"
 #include "mail-modifylog.h"
 #include "index-messageset.h"
 
@@ -205,11 +204,10 @@
 		}
 	}
 
-	rec = index->lookup_uid_range(index, uid, uid2);
+	rec = index->lookup_uid_range(index, uid, uid2, &idx_seq);
 	if (rec == NULL)
 		return expunges_found ? 2 : 1;
 
-	idx_seq = index->get_sequence(index, rec);
 	client_seq = idx_seq + expunges_before;
 
 	while (rec != NULL && rec->uid <= uid2) {

--- a/src/lib-storage/index/index-search.c	Sun Oct 06 00:47:33 2002 +0300
+++ b/src/lib-storage/index/index-search.c	Sun Oct 06 03:30:14 2002 +0300
@@ -682,18 +682,14 @@
 	if (!search_get_uid_range(ibox, args, &first_uid, &last_uid))
 		return TRUE;
 
-	rec = ibox->index->lookup_uid_range(ibox->index, first_uid, last_uid);
+	rec = ibox->index->lookup_uid_range(ibox->index, first_uid, last_uid,
+					    &client_seq);
 	if (rec == NULL)
 		return TRUE;
 
 	expunges = mail_modifylog_uid_get_expunges(ibox->index->modifylog,
 						   rec->uid, last_uid,
 						   &expunges_before);
-
-	client_seq = ibox->index->get_sequence(ibox->index, rec);
-	if (client_seq == 0)
-		return mail_storage_set_index_error(ibox);
-
 	client_seq += expunges_before;
 
 	ctx.ibox = ibox;

--- a/src/lib-storage/index/index-status.c	Sun Oct 06 00:47:33 2002 +0300
+++ b/src/lib-storage/index/index-status.c	Sun Oct 06 03:30:14 2002 +0300
@@ -20,14 +20,12 @@
 	if (lowwater_uid != 0) {
 		/* begin scanning from the low water mark */
 		rec = index->lookup_uid_range(index, lowwater_uid,
-					      hdr->next_uid - 1);
+					      hdr->next_uid - 1, &seq);
 		if (rec == NULL) {
 			i_error("index header's seen_messages_count or "
 				"first_unseen_uid_lowwater is invalid.");
                         INDEX_MARK_CORRUPTED(index);
 			return 0;
-		} else {
-			seq = index->get_sequence(index, rec);
 		}
 	} else {
 		/* begin scanning from the beginning */

--- a/src/lib-storage/index/index-storage.c	Sun Oct 06 00:47:33 2002 +0300
+++ b/src/lib-storage/index/index-storage.c	Sun Oct 06 03:30:14 2002 +0300
@@ -94,21 +94,6 @@
 		return 0;
 
 	rec = index->lookup_uid_range(index, index->first_recent_uid,
-				      hdr->next_uid - 1);
-	if (rec == NULL)
-		return 0;
-
-	/* now we know the record, but we'd still need to know how many
-	   messages there's after this. there's two way to do this -
-	   get the sequence number thus far (fast, unless there's deleted
-	   messages) or just start reading messages forward until we're at
-	   the end (fast assuming there's only a few recent messages).
-	   it's a bit easier to use the first method and often it should be
-	   faster too.. */
-	seq = index->get_sequence(index, rec);
-	if (seq == 0) {
-		i_error("Couldn't get sequence for UID %u", rec->uid);
-		return 0;
-	}
-	return hdr->messages_count+1 - seq;
+				      hdr->next_uid - 1, &seq);
+	return rec == NULL ? 0 : hdr->messages_count+1 - seq;
 }

--- a/src/lib-storage/index/index-sync.c	Sun Oct 06 00:47:33 2002 +0300
+++ b/src/lib-storage/index/index-sync.c	Sun Oct 06 03:30:14 2002 +0300
@@ -34,7 +34,7 @@
 	MailIndexRecord *rec;
 	MailFlags flags;
 	const char **custom_flags;
-	unsigned int count;
+	unsigned int count, seq;
 
 	/* show the log */
 	log = mail_modifylog_get_nonsynced(index->modifylog, &count);
@@ -55,7 +55,7 @@
 				break;
 
 			rec = index->lookup_uid_range(index,
-						      log->uid, log->uid);
+						      log->uid, log->uid, &seq);
 			if (rec != NULL) {
 				flags = rec->msg_flags;
 				if (rec->uid >= index->first_recent_uid)