# HG changeset patch
# User Timo Sirainen <tss@iki.fi>
# Date 1042298986 -7200
# Node ID 501f076f2e74885bc8b217f3aa7a9086daf9903f
# Parent  4f38538aa4a19024bc9d825bce0556aa1415e264
Rewrote hash table code, works with less memory now. Also some memory
allocation fixes to thread extension code.

diff -r 4f38538aa4a1 -r 501f076f2e74 COPYING
--- a/COPYING	Sat Jan 11 17:09:35 2003 +0200
+++ b/COPYING	Sat Jan 11 17:29:46 2003 +0200
@@ -5,7 +5,7 @@
 
 src/lib/
   - md5.c : Public Domain
-  - base64.c, mkgmtime.c : BSD-like (read it)
-  - hash.c, primes.c, printf-upper-bound.c, tree.c : LGPL v2
+  - base64.c, utc-mktime.c : BSD-like (read it)
+  - primes.c, printf-upper-bound.c : LGPL v2
 
 src/lib-storage/mail-thread.c : merge sorting code is with MIT license.
diff -r 4f38538aa4a1 -r 501f076f2e74 src/auth/cookie.c
--- a/src/auth/cookie.c	Sat Jan 11 17:09:35 2003 +0200
+++ b/src/auth/cookie.c	Sat Jan 11 17:29:46 2003 +0200
@@ -155,7 +155,8 @@
 	oldest_cookie = NULL;
 	next_cookie = &oldest_cookie;
 
-	cookies = hash_create(default_pool, 100, cookie_hash, cookie_cmp);
+	cookies = hash_create(default_pool, default_pool, 100,
+			      cookie_hash, cookie_cmp);
 	to = timeout_add(10000, cookie_timeout, NULL);
 }
 
diff -r 4f38538aa4a1 -r 501f076f2e74 src/auth/userinfo-passwd-file.c
--- a/src/auth/userinfo-passwd-file.c	Sat Jan 11 17:09:35 2003 +0200
+++ b/src/auth/userinfo-passwd-file.c	Sat Jan 11 17:29:46 2003 +0200
@@ -350,7 +350,8 @@
 	pw->path = p_strdup(pool, path);
 	pw->stamp = st.st_mtime;
 	pw->fd = fd;
-	pw->users = hash_create(pool, 100, str_hash, (HashCompareFunc) strcmp);
+	pw->users = hash_create(default_pool, pool, 100,
+				str_hash, (HashCompareFunc) strcmp);
 
 	passwd_file_parse_file(pw);
 	return pw;
diff -r 4f38538aa4a1 -r 501f076f2e74 src/lib-index/maildir/maildir-sync.c
--- a/src/lib-index/maildir/maildir-sync.c	Sat Jan 11 17:09:35 2003 +0200
+++ b/src/lib-index/maildir/maildir-sync.c	Sat Jan 11 17:29:46 2003 +0200
@@ -213,9 +213,9 @@
 		return index_file_set_syscall_error(index, dir, "opendir()");
 
 	count = index->header->messages_count + 16;
-	pool = pool_alloconly_create("Maildir sync", nearest_power(count*30));
-	files = hash_create(pool, index->header->messages_count*2, str_hash,
-			    (HashCompareFunc) strcmp);
+	pool = pool_alloconly_create("Maildir sync", count*20);
+	files = hash_create(default_pool, pool, index->header->messages_count*2,
+			    str_hash, (HashCompareFunc) strcmp);
 
 	while ((d = readdir(dirp)) != NULL) {
 		if (d->d_name[0] == '.')
diff -r 4f38538aa4a1 -r 501f076f2e74 src/lib-storage/mail-thread.c
--- a/src/lib-storage/mail-thread.c	Sat Jan 11 17:09:35 2003 +0200
+++ b/src/lib-storage/mail-thread.c	Sat Jan 11 17:29:46 2003 +0200
@@ -67,7 +67,7 @@
 
 struct mail_thread_context {
 	pool_t pool;
-	pool_t str_pool; /* for node->msgid and root_info->base_subject */
+	pool_t temp_pool;
 
 	struct hash_table *msgid_hash;
 	struct hash_table *subject_hash;
@@ -94,12 +94,11 @@
 
 	ctx = p_new(pool, struct mail_thread_context, 1);
 	ctx->pool = pool;
-	ctx->str_pool =
-		pool_alloconly_create("mail_thread_context strings",
-				      sizeof(struct node) *
-				      APPROX_MSG_COUNT * APPROX_MSGID_SIZE);
-	ctx->msgid_hash = hash_create(default_pool,
-				      APPROX_MSGID_SIZE*2, str_hash,
+	ctx->temp_pool = pool_alloconly_create("mail_thread_context temp",
+					       APPROX_MSG_COUNT *
+					       APPROX_MSGID_SIZE);
+	ctx->msgid_hash = hash_create(default_pool, ctx->temp_pool,
+				      APPROX_MSG_COUNT*2, str_hash,
 				      (HashCompareFunc)strcmp);
 	ctx->callbacks = callbacks;
 	ctx->callback_context = callback_context;
@@ -113,7 +112,8 @@
 		hash_destroy(ctx->msgid_hash);
 	if (ctx->subject_hash != NULL)
 		hash_destroy(ctx->subject_hash);
-	pool_unref(ctx->str_pool);
+
+	pool_unref(ctx->temp_pool);
 	pool_unref(ctx->pool);
 }
 
@@ -132,7 +132,7 @@
 	struct node *node;
 
 	node = p_new(ctx->pool, struct node, 1);
-	node->u.msgid = p_strdup(ctx->str_pool, msgid);
+	node->u.msgid = p_strdup(ctx->temp_pool, msgid);
 
 	hash_insert(ctx->msgid_hash, node->u.msgid, node);
 	return node;
@@ -558,7 +558,7 @@
 		return;
 
 	if (!hash_lookup_full(ctx->subject_hash, subject, &key, &value)) {
-		hash_subject = p_strdup(ctx->str_pool, subject);
+		hash_subject = p_strdup(ctx->temp_pool, subject);
 		hash_insert(ctx->subject_hash, hash_subject, node);
 	} else {
 		hash_subject = key;
@@ -582,9 +582,8 @@
 
 	cb = ctx->callbacks;
 	ctx->subject_hash =
-		hash_create(default_pool, ctx->root_count * 2, str_hash,
-			    (HashCompareFunc)strcmp);
-
+		hash_create(default_pool, ctx->temp_pool, ctx->root_count * 2,
+			    str_hash, (HashCompareFunc)strcmp);
 	for (node = ctx->root_nodes; node != NULL; node = node->next) {
 		if (!NODE_IS_DUMMY(node))
 			id = node->id;
@@ -834,17 +833,19 @@
 {
 	struct node *node;
 
-	/* drop the memory allocated for message-IDs, reuse their memory
-	   for base subjects */
-	p_clear(ctx->str_pool);
-
 	/* (2) save root nodes and drop the msgids */
 	hash_foreach(ctx->msgid_hash, save_root_cb, ctx);
+
+	/* drop the memory allocated for message-IDs and msgid_hash,
+	   reuse their memory for base subjects */
 	hash_destroy(ctx->msgid_hash);
 	ctx->msgid_hash = NULL;
 
+	p_clear(ctx->temp_pool);
+
 	if (ctx->root_nodes == NULL) {
 		/* no messages */
+		mail_thread_deinit(ctx);
 		return;
 	}
 
diff -r 4f38538aa4a1 -r 501f076f2e74 src/lib/hash.c
--- a/src/lib/hash.c	Sat Jan 11 17:09:35 2003 +0200
+++ b/src/lib/hash.c	Sat Jan 11 17:29:46 2003 +0200
@@ -1,30 +1,27 @@
-/* GLIB - Library of useful routines for C programming
- * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
- *
- * This library is free software; you can redistribute it and/or
- * modify it under the terms of the GNU Library General Public
- * License as published by the Free Software Foundation; either
- * version 2 of the License, or (at your option) any later version.
- *
- * This library 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
- * Library General Public License for more details.
- *
- * You should have received a copy of the GNU Library General Public
- * License along with this library; if not, write to the
- * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
- * Boston, MA 02111-1307, USA.
- */
+/*
+    Copyright (c) 2003 Timo Sirainen
+
+    Permission is hereby granted, free of charge, to any person obtaining
+    a copy of this software and associated documentation files (the
+    "Software"), to deal in the Software without restriction, including
+    without limitation the rights to use, copy, modify, merge, publish,
+    distribute, sublicense, and/or sell copies of the Software, and to
+    permit persons to whom the Software is furnished to do so, subject to
+    the following conditions:
 
-/*
- * Modified by the GLib Team and others 1997-1999.  See the AUTHORS
- * file for a list of people on the GLib Team.  See the ChangeLog
- * files for a list of changes.  These files are distributed with
- * GLib at ftp://ftp.gtk.org/pub/gtk/. 
- */
+    The above copyright notice and this permission notice shall be
+    included in all copies or substantial portions of the Software.
 
-/* several modifications Copyright (C) 2002 by Timo Sirainen */
+    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
+    OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+    MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
+    IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
+    CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
+    TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
+    SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+*/
+
+/* @UNSAFE: whole file */
 
 #include "lib.h"
 #include "hash.h"
@@ -32,143 +29,180 @@
 
 #include <ctype.h>
 
-#define HASH_TABLE_MIN_SIZE 11
-#define HASH_TABLE_MAX_SIZE 13845163
+#define HASH_TABLE_MIN_SIZE 109
+#define COLLISIONS_MIN_SIZE 37
 
 struct hash_node {
 	void *key;
 	void *value;
+};
 
-	int destroyed;
-	struct hash_node *next;
+struct collision_node {
+	struct hash_node node;
+	struct collision_node *next;
 };
 
 struct hash_table {
-	pool_t pool;
+	pool_t table_pool, node_pool;
+
+	int frozen;
+	size_t nodes_count, removed_count;
+#ifdef DEBUG
+	size_t collisions_count;
+#endif
 
-	unsigned int size;
-	unsigned int nodes_count, nodes_destroyed;
-	int frozen;
-	struct hash_node **nodes;
+	size_t size;
+	struct hash_node *nodes;
+
+	size_t collisions_size;
+	struct collision_node *collisions;
+
+	struct collision_node *free_cnodes;
 
 	HashFunc hash_func;
 	HashCompareFunc key_compare_func;
 };
 
-static void hash_cleanup(struct hash_table *table);
 static int hash_resize(struct hash_table *table);
 
 static int foreach_stop;
 
+static int direct_cmp(const void *p1, const void *p2)
+{
+	return p1 == p2 ? 0 : 1;
+}
+
 static unsigned int direct_hash(const void *p)
 {
 	/* NOTE: may truncate the value, but that doesn't matter. */
 	return POINTER_CAST_TO(p, unsigned int);
 }
 
-static struct hash_node *hash_node_create(pool_t pool, void *key, void *value)
-{
-	struct hash_node *node;
-
-        node = p_new(pool, struct hash_node, 1);
-	node->key = key;
-	node->value = value;
-
-	return node;
-}
-
-static void hash_nodes_destroy(struct hash_table *table, struct hash_node *node)
-{
-	struct hash_node *next;
-
-	while (node != NULL) {
-		next = node->next;
-                p_free(table->pool, node);
-                node = next;
-	}
-}
-
-struct hash_table *hash_create(pool_t pool, unsigned int initial_size,
-			       HashFunc hash_func,
+struct hash_table *hash_create(pool_t table_pool, pool_t node_pool,
+			       size_t initial_size, HashFunc hash_func,
 			       HashCompareFunc key_compare_func)
 {
 	struct hash_table *table;
 
-        i_assert(pool != NULL);
-
-	table = p_new(pool, struct hash_table, 1);
-        table->pool = pool;
-	table->size = CLAMP(primes_closest(initial_size),
-			    HASH_TABLE_MIN_SIZE,
-			    HASH_TABLE_MAX_SIZE);
+	table = p_new(node_pool, struct hash_table, 1);
+        table->table_pool = table_pool;
+        table->node_pool = node_pool;
+	table->size = I_MAX(primes_closest(initial_size),
+			    HASH_TABLE_MIN_SIZE);
 
 	table->hash_func = hash_func != NULL ? hash_func : direct_hash;
-	table->key_compare_func = key_compare_func;
-	table->nodes = p_new(pool, struct hash_node *, table->size);
+	table->key_compare_func = key_compare_func == NULL ?
+		direct_cmp : key_compare_func;
+	table->nodes = p_new(table_pool, struct hash_node, table->size);
+	table->collisions_size = I_MAX(table->size / 10, COLLISIONS_MIN_SIZE);
+	table->collisions = p_new(table_pool, struct collision_node,
+				  table->collisions_size);
 
 	return table;
 }
 
+static void free_cnode(struct hash_table *table, struct collision_node *cnode)
+{
+	if (!table->node_pool->alloconly_pool)
+		p_free(table->node_pool, cnode);
+	else {
+		cnode->next = table->free_cnodes;
+		table->free_cnodes = cnode;
+	}
+}
+
+static void destroy_collision(struct hash_table *table,
+			      struct collision_node *cnode)
+{
+	struct collision_node *next;
+
+	while (cnode != NULL) {
+		next = cnode->next;
+		p_free(table->node_pool, cnode);
+		cnode = next;
+	}
+}
+
+static void hash_destroy_collision_nodes(struct hash_table *table)
+{
+	size_t i;
+
+	for (i = 0; i < table->collisions_size; i++) {
+		if (table->collisions[i].next != NULL)
+			destroy_collision(table, table->collisions[i].next);
+	}
+}
+
 void hash_destroy(struct hash_table *table)
 {
-	unsigned int i;
-
-	if (table == NULL)
-                return;
+	if (!table->node_pool->alloconly_pool) {
+		hash_destroy_collision_nodes(table);
+		destroy_collision(table, table->free_cnodes);
+	}
 
-	for (i = 0; i < table->size; i++)
-		hash_nodes_destroy(table, table->nodes[i]);
-
-	p_free(table->pool, table->nodes);
-	p_free(table->pool, table);
+	p_free(table->table_pool, table->nodes);
+	p_free(table->table_pool, table->collisions);
+	p_free(table->node_pool, table);
 }
 
 void hash_clear(struct hash_table *table)
 {
-	unsigned int i;
-
-	i_assert(table != NULL);
+	if (!table->node_pool->alloconly_pool)
+		hash_destroy_collision_nodes(table);
 
-	for (i = 0; i < table->size; i++) {
-		hash_nodes_destroy(table, table->nodes[i]);
-		table->nodes[i] = NULL;
-	}
+	memset(table->nodes, 0, sizeof(struct hash_node) * table->size);
+	memset(table->collisions, 0,
+	       sizeof(struct collision_node) * table->collisions_size);
+
+	table->nodes_count = 0;
+	table->removed_count = 0;
+#ifdef DEBUG
+	table->collisions_count = 0;
+#endif
 }
 
-static inline struct hash_node **
-hash_lookup_node(struct hash_table *table, const void *key)
+static struct hash_node *
+hash_lookup_collision(struct hash_table *table,
+		      const void *key, unsigned int hash)
 {
-	struct hash_node **node;
+	struct collision_node *cnode;
 
-	node = &table->nodes[table->hash_func(key) % table->size];
+	cnode = &table->collisions[hash % table->collisions_size];
+	do {
+		if (cnode->node.key != NULL) {
+			if (table->key_compare_func(cnode->node.key, key) == 0)
+				return &cnode->node;
+		}
+		cnode = cnode->next;
+	} while (cnode != NULL);
 
-	/* Hash table lookup needs to be fast.
-	   We therefore remove the extra conditional of testing
-	   whether to call the key_compare_func or not from
-	   the inner loop. */
-	if (table->key_compare_func) {
-		while (*node != NULL) {
-                        if (!(*node)->destroyed &&
-			    table->key_compare_func((*node)->key, key) == 0)
-                                break;
-			node = &(*node)->next;
-		}
+	return NULL;
+}
+
+static struct hash_node *
+hash_lookup_node(struct hash_table *table, const void *key, unsigned int hash)
+{
+	struct hash_node *node;
+
+	node = &table->nodes[hash % table->size];
+
+	if (node->key == NULL) {
+		if (table->removed_count == 0)
+			return NULL;
 	} else {
-		while (*node != NULL && (*node)->key != key)
-			node = &(*node)->next;
+		if (table->key_compare_func(node->key, key) == 0)
+			return node;
 	}
 
-	return node;
+	return hash_lookup_collision(table, key, hash);
 }
 
 void *hash_lookup(struct hash_table *table, const void *key)
 {
 	struct hash_node *node;
 
-	i_assert(table != NULL);
-
-	node = *hash_lookup_node(table, key);
-	return node != NULL && !node->destroyed ? node->value : NULL;
+	node = hash_lookup_node(table, key, table->hash_func(key));
+	return node != NULL ? node->value : NULL;
 }
 
 int hash_lookup_full(struct hash_table *table, const void *lookup_key,
@@ -176,10 +210,9 @@
 {
 	struct hash_node *node;
 
-	i_assert(table != NULL);
-
-	node = *hash_lookup_node(table, lookup_key);
-	if (node == NULL || node->destroyed)
+	node = hash_lookup_node(table, lookup_key,
+				table->hash_func(lookup_key));
+	if (node == NULL)
 		return FALSE;
 
 	if (orig_key != NULL)
@@ -189,104 +222,227 @@
 	return TRUE;
 }
 
-static void hash_insert_full(struct hash_table *table, void *key, void *value,
-			     int replace_key)
+static struct hash_node *
+hash_insert_node(struct hash_table *table, void *key, void *value,
+		 int check_existing)
 {
-	struct hash_node **node;
+	struct hash_node *node;
+	struct collision_node *cnode, *prev;
+	unsigned int hash;
+
+	i_assert(key != NULL);
+
+	hash = table->hash_func(key);
 
-	i_assert(table != NULL);
+	if (check_existing && table->removed_count > 0) {
+		/* there may be holes, have to check everything */
+		node = hash_lookup_node(table, key, hash);
+		if (node != NULL)
+			return node;
+
+                check_existing = FALSE;
+	}
 
-	node = hash_lookup_node(table, key);
-	if (*node == NULL) {
-		*node = hash_node_create(table->pool, key, value);
-
+	/* a) primary hash */
+	node = &table->nodes[hash % table->size];
+	if (node->key == NULL) {
 		table->nodes_count++;
-		if (!table->frozen)
-			hash_resize(table);
-	} else {
-		if (replace_key || (*node)->destroyed) {
-			(*node)->key = key;
-			(*node)->destroyed = FALSE;
+
+		node->key = key;
+		node->value = value;
+		return node;
+	}
+
+	if (check_existing) {
+		if (table->key_compare_func(node->key, key) == 0)
+			return node;
+	}
+
+	/* b) collisions list */
+	prev = NULL;
+	cnode = &table->collisions[hash % table->collisions_size];
+
+	do {
+		if (cnode->node.key == NULL)
+			break;
+
+		if (check_existing) {
+			if (table->key_compare_func(cnode->node.key, key) == 0)
+				return node;
 		}
 
-		(*node)->value = value;
+		prev = cnode;
+		cnode = cnode->next;
+	} while (cnode != NULL);
+
+	if (cnode == NULL) {
+		if (table->frozen == 0 && hash_resize(table)) {
+			/* resized table, try again */
+			return hash_insert_node(table, key, value, FALSE);
+		}
+
+		if (table->free_cnodes == NULL) {
+			cnode = p_new(table->node_pool,
+				      struct collision_node, 1);
+		} else {
+			cnode = table->free_cnodes;
+			table->free_cnodes = cnode->next;
+			cnode->next = NULL;
+		}
+		prev->next = cnode;
 	}
+
+	cnode->node.key = key;
+	cnode->node.value = value;;
+
+#ifdef DEBUG
+	table->collisions_count++;
+#endif
+	table->nodes_count++;
+	return &cnode->node;
 }
 
 void hash_insert(struct hash_table *table, void *key, void *value)
 {
-	hash_insert_full(table, key, value, TRUE);
+	struct hash_node *node;
+
+	node = hash_insert_node(table, key, value, TRUE);
+	node->key = key;
 }
 
 void hash_update(struct hash_table *table, void *key, void *value)
 {
-	hash_insert_full(table, key, value, FALSE);
+	(void)hash_insert_node(table, key, value, TRUE);
+}
+
+static void hash_compress(struct hash_table *table,
+			  unsigned int collision_idx,
+			  unsigned int hash)
+{
+	struct collision_node *croot, *cnode, *next;
+	struct hash_node *node;
+
+	/* remove deleted nodes from the list */
+	croot = cnode = &table->collisions[collision_idx];
+	while (cnode->next != NULL) {
+		next = cnode->next;
+
+		if (next->node.key == NULL) {
+			cnode->next = next->next;
+			free_cnode(table, next);
+#ifdef DEBUG
+			table->collisions_count--;
+#endif
+		}
+	}
+
+	do {
+		/* if root is marked as deleted, replace it with first node
+		   from list */
+		if (croot->node.key == NULL) {
+			next = croot->next;
+			if (next == NULL) {
+				/* no collisions left - nothing to do */
+				return;
+			}
+
+			memcpy(&croot->node, &next->node, sizeof(croot->node));
+			croot->next = next->next;
+			free_cnode(table, next);
+#ifdef DEBUG
+			table->collisions_count--;
+#endif
+		}
+
+		/* see if node in primary table was deleted */
+		if (hash == 0)
+			hash = table->hash_func(croot->node.key);
+		node = &table->nodes[hash % table->size];
+		if (node->key == NULL) {
+			memcpy(node, &croot->node, sizeof(*node));
+			croot->node.key = NULL;
+#ifdef DEBUG
+			table->collisions_count--;
+#endif
+		}
+	} while (croot->node.key == NULL);
+}
+
+static void hash_compress_collisions(struct hash_table *table)
+{
+	struct collision_node *cnode;
+	size_t i;
+
+	for (i = 0; i < table->collisions_size; i++) {
+		cnode = &table->collisions[i];
+
+		if (cnode->node.key != NULL || cnode->next != NULL)
+			hash_compress(table, i, 0);
+	}
 }
 
 void hash_remove(struct hash_table *table, const void *key)
 {
-	struct hash_node **node, *old_node;
-
-	i_assert(table != NULL);
+	struct hash_node *node;
+	unsigned int hash;
 
-	node = hash_lookup_node(table, key);
-	if (*node != NULL && !(*node)->destroyed) {
-		table->nodes_count--;
+	hash = table->hash_func(key);
 
-		if (table->frozen) {
-			(*node)->destroyed = TRUE;
-                        table->nodes_destroyed++;
-		} else {
-			old_node = *node;
-			*node = old_node->next;
-			p_free(table->pool, old_node);
+	node = hash_lookup_node(table, key, hash);
+	node->key = NULL;
 
-			hash_resize(table);
-		}
-	}
+	if (table->frozen != 0)
+		table->removed_count++;
+	else if (!hash_resize(table))
+		hash_compress(table, hash % table->collisions_size, hash);
 }
 
-void hash_freeze(struct hash_table *table)
+size_t hash_size(struct hash_table *table)
 {
-	i_assert(table != NULL);
-
-	table->frozen++;
-}
-
-void hash_thaw(struct hash_table *table)
-{
-	i_assert(table != NULL);
-	i_assert(table->frozen > 0);
-
-	if (--table->frozen == 0)
-                hash_cleanup(table);
+	return table->nodes_count;
 }
 
 void hash_foreach(struct hash_table *table, HashForeachFunc func, void *context)
 {
 	struct hash_node *node;
-	unsigned int i;
-
-	i_assert(table != NULL);
-	i_assert(func != NULL);
+	struct collision_node *cnode;
+	size_t i;
 
 	hash_freeze(table);
 
-        foreach_stop = FALSE;
+	foreach_stop = FALSE;
+
 	for (i = 0; i < table->size; i++) {
-		for (node = table->nodes[i]; node; node = node->next) {
-			if (!node->destroyed) {
-				func(node->key, node->value, context);
+		node = &table->nodes[i];
 
-				if (foreach_stop) {
-					foreach_stop = FALSE;
-					hash_thaw(table);
-                                        return;
-				}
+		if (node->key != NULL) {
+			func(node->key, node->value, context);
+			if (foreach_stop) {
+				table->frozen--;
+				return;
 			}
 		}
 	}
-        hash_thaw(table);
+
+	if (!foreach_stop) {
+		for (i = 0; i < table->collisions_size; i++) {
+			cnode = &table->collisions[i];
+
+			do {
+				if (cnode->node.key != NULL) {
+					func(cnode->node.key, cnode->node.value,
+					     context);
+					if (foreach_stop) {
+						table->frozen--;
+						return;
+					}
+				}
+				cnode = cnode->next;
+			} while (cnode != NULL);
+		}
+	}
+
+	hash_thaw(table);
 }
 
 void hash_foreach_stop(void)
@@ -294,85 +450,85 @@
         foreach_stop = TRUE;
 }
 
-/* Returns the number of elements contained in the hash table. */
-unsigned int hash_size(struct hash_table *table)
+void hash_freeze(struct hash_table *table)
+{
+	table->frozen++;
+}
+
+void hash_thaw(struct hash_table *table)
 {
-	i_assert(table != NULL);
+	i_assert(table->frozen > 0);
+	if (--table->frozen > 0)
+		return;
 
-	return table->nodes_count;
+	if (table->removed_count > 0) {
+		if (!hash_resize(table))
+			hash_compress_collisions(table);
+	}
 }
 
 static int hash_resize(struct hash_table *table)
 {
-        HashFunc hash_func;
-	struct hash_node *node, *next, **new_nodes;
+	struct hash_node *old_nodes;
+	struct collision_node *old_cnodes, *cnode;
+	size_t old_size, old_csize, i;
+
 	float nodes_per_list;
-	unsigned int hash_val, new_size, i;
 
-	nodes_per_list = (float) table->nodes_count / (float) table->size;
-	if ((nodes_per_list > 0.3 || table->size <= HASH_TABLE_MIN_SIZE) &&
-	    (nodes_per_list < 3.0 || table->size >= HASH_TABLE_MAX_SIZE))
-		return FALSE;
+        nodes_per_list = (float) table->nodes_count / (float) table->size;
+        if ((nodes_per_list > 0.3 || table->size <= HASH_TABLE_MIN_SIZE) &&
+            (nodes_per_list < 2.0))
+                return FALSE;
 
-	new_size = CLAMP(primes_closest(table->nodes_count+1),
-			 HASH_TABLE_MIN_SIZE,
-			 HASH_TABLE_MAX_SIZE);
+	/* recreate primary table */
+	old_size = table->size;
+	old_nodes = table->nodes;
+
+	table->size = I_MAX(primes_closest(table->nodes_count+1),
+			    HASH_TABLE_MIN_SIZE);
+	table->nodes = p_new(table->table_pool, struct hash_node, table->size);
 
-	new_nodes = p_new(table->pool, struct hash_node *, new_size);
+	/* recreate collisions table */
+	old_csize = table->collisions_size;
+	old_cnodes = table->collisions;
 
-        hash_func = table->hash_func;
-	for (i = 0; i < table->size; i++) {
-		for (node = table->nodes[i]; node != NULL; node = next) {
-			next = node->next;
+	table->collisions_size = I_MAX(table->size / 10, COLLISIONS_MIN_SIZE);
+	table->collisions = p_new(table->table_pool, struct collision_node,
+				  table->collisions_size);
 
-			if (node->destroyed) {
-                                p_free(table->pool, node);
-			} else {
-				hash_val = hash_func(node->key) % new_size;
+	table->nodes_count = 0;
+	table->removed_count = 0;
+#ifdef DEBUG
+	table->collisions_count = 0;
+#endif
 
-				node->next = new_nodes[hash_val];
-				new_nodes[hash_val] = node;
-			}
+	table->frozen++;
+
+	/* move the data */
+	for (i = 0; i < old_size; i++) {
+		if (old_nodes[i].key != NULL) {
+			hash_insert_node(table, old_nodes[i].key,
+					 old_nodes[i].value, FALSE);
 		}
 	}
 
-	p_free(table->pool, table->nodes);
-	table->nodes = new_nodes;
-	table->size = new_size;
-	table->nodes_destroyed = 0;
-        return TRUE;
-}
-
-static void hash_cleanup(struct hash_table *table)
-{
-	struct hash_node **node, **next, *old_node;
-        unsigned int i;
-
-	if (hash_resize(table))
-		return;
-
-	if (table->nodes_destroyed == 0)
-                return;
+	for (i = 0; i < old_csize; i++) {
+		cnode = &old_cnodes[i];
 
-        /* find the destroyed nodes from hash table and remove them */
-	for (i = 0; i < table->size; i++) {
-		for (node = &table->nodes[i]; *node != NULL; node = next) {
-			next = &(*node)->next;
-
-			if ((*node)->destroyed) {
-                                old_node = *node;
-				*node = *next;
-				p_free(table->pool, old_node);
+		do {
+			if (cnode->node.key != NULL) {
+				hash_insert_node(table, cnode->node.key,
+						 cnode->node.value, FALSE);
+			}
+			cnode = cnode->next;
+		} while (cnode != NULL);
+	}
 
-				/* next points to free'd memory area now,
-				   fix it */
-				next = node;
+	table->frozen--;
 
-				if (--table->nodes_destroyed == 0)
-                                        return;
-			}
-		}
-	}
+	p_free(table->table_pool, old_nodes);
+	p_free(table->table_pool, old_cnodes);
+	return TRUE;
 }
 
 /* a char* hash function from ASU -- from glib */
diff -r 4f38538aa4a1 -r 501f076f2e74 src/lib/hash.h
--- a/src/lib/hash.h	Sat Jan 11 17:09:35 2003 +0200
+++ b/src/lib/hash.h	Sat Jan 11 17:29:46 2003 +0200
@@ -9,18 +9,15 @@
 
 /* Create a new hash table. If initial_size is 0, the default value is used.
    If hash_func or key_compare_func is NULL, direct hashing/comparing
-   is used. */
-struct hash_table *hash_create(pool_t pool, unsigned int initial_size,
-			       HashFunc hash_func,
+   is used.
+
+   table_pool is used to allocate/free large hash tables, node_pool is used
+   for smaller allocations and can also be alloconly pool. The pools must not
+   be free'd before hash_destroy() is called. */
+struct hash_table *hash_create(pool_t table_pool, pool_t node_pool,
+			       size_t initial_size, HashFunc hash_func,
 			       HashCompareFunc key_compare_func);
 void hash_destroy(struct hash_table *table);
-
-#ifdef POOL_CHECK_LEAKS
-#  define hash_destroy_clean(table) hash_destroy(table)
-#else
-#  define hash_destroy_clean(table)
-#endif
-
 void hash_clear(struct hash_table *table);
 
 void *hash_lookup(struct hash_table *table, const void *key);
@@ -33,7 +30,7 @@
 void hash_update(struct hash_table *table, void *key, void *value);
 
 void hash_remove(struct hash_table *table, const void *key);
-unsigned int hash_size(struct hash_table *table);
+size_t hash_size(struct hash_table *table);
 
 /* Calls the given function for each node in hash table. You may safely
    call hash_*() functions inside your function, but if you add any
diff -r 4f38538aa4a1 -r 501f076f2e74 src/login/auth-connection.c
--- a/src/login/auth-connection.c	Sat Jan 11 17:09:35 2003 +0200
+++ b/src/login/auth-connection.c	Sat Jan 11 17:29:46 2003 +0200
@@ -80,7 +80,8 @@
 					   FALSE);
 	conn->output = o_stream_create_file(fd, default_pool, MAX_OUTBUF_SIZE,
 					    IO_PRIORITY_DEFAULT, FALSE);
-	conn->requests = hash_create(default_pool, 100, NULL, NULL);
+	conn->requests = hash_create(default_pool, default_pool, 100,
+				     NULL, NULL);
 
 	conn->next = auth_connections;
 	auth_connections = conn;
@@ -300,6 +301,10 @@
 	request->mech = mech;
 	request->conn = conn;
 	request->id = ++request_id_counter;
+	if (request->id == 0) {
+		/* wrapped - ID 0 not allowed */
+		request->id = ++request_id_counter;
+	}
 	request->callback = callback;
 	request->context = context;
 
diff -r 4f38538aa4a1 -r 501f076f2e74 src/login/client.c
--- a/src/login/client.c	Sat Jan 11 17:09:35 2003 +0200
+++ b/src/login/client.c	Sat Jan 11 17:29:46 2003 +0200
@@ -436,7 +436,7 @@
 
 void clients_init(void)
 {
-	clients = hash_create(default_pool, 128, NULL, NULL);
+	clients = hash_create(default_pool, default_pool, 128, NULL, NULL);
 	to_idle = timeout_add(1000, idle_timeout, NULL);
 }
 
diff -r 4f38538aa4a1 -r 501f076f2e74 src/master/login-process.c
--- a/src/master/login-process.c	Sat Jan 11 17:09:35 2003 +0200
+++ b/src/master/login-process.c	Sat Jan 11 17:29:46 2003 +0200
@@ -423,7 +423,7 @@
         wanted_processes_count = 0;
 	oldest_nonlisten_process = newest_nonlisten_process = NULL;
 
-	processes = hash_create(default_pool, 128, NULL, NULL);
+	processes = hash_create(default_pool, default_pool, 128, NULL, NULL);
 	to = timeout_add(1000, login_processes_start_missing, NULL);
 }
 
diff -r 4f38538aa4a1 -r 501f076f2e74 src/master/main.c
--- a/src/master/main.c	Sat Jan 11 17:09:35 2003 +0200
+++ b/src/master/main.c	Sat Jan 11 17:29:46 2003 +0200
@@ -246,7 +246,7 @@
 
 	lib_init_signals(sig_quit);
 
-	pids = hash_create(default_pool, 128, NULL, NULL);
+	pids = hash_create(default_pool, default_pool, 128, NULL, NULL);
 	to = timeout_add(100, timeout_handler, NULL);
 
 	ssl_init();