1 files changed, 242 insertions, 0 deletions
diff --git a/src/lib/hash2.c b/src/lib/hash2.c
new file mode 100644
index 0000000..a8a23e0
--- /dev/null
+++ b/src/lib/hash2.c
@@ -0,0 +1,242 @@
+/* Copyright (c) 2002-2018 Dovecot authors, see the included COPYING file */
+
+#include "lib.h"
+#include "array.h"
+#include "primes.h"
+#include "hash2.h"
+
+#define HASH_TABLE_MIN_SIZE 131
+
+struct hash2_value {
+	struct hash2_value *next;
+	unsigned int key_hash;
+	/* user_data[value_size] */
+};
+ARRAY_DEFINE_TYPE(hash2_value, struct hash2_value *);
+
+struct hash2_table {
+	unsigned int count;
+	unsigned int initial_size;
+	unsigned int hash_table_size;
+	unsigned int value_size;
+
+	pool_t value_pool;
+	struct hash2_value *deleted_values;
+
+	ARRAY_TYPE(hash2_value) hash_table;
+
+	hash2_key_callback_t *key_hash_cb;
+	hash2_cmp_callback_t *key_compare_cb;
+	void *context;
+};
+
+static void hash2_alloc_table(struct hash2_table *hash, unsigned int size)
+{
+	hash->hash_table_size = size;
+
+	i_array_init(&hash->hash_table, hash->hash_table_size);
+	(void)array_idx_get_space(&hash->hash_table, hash->hash_table_size-1);
+}
+
+struct hash2_table *
+hash2_create(unsigned int initial_size, unsigned int value_size,
+	     hash2_key_callback_t *key_hash_cb,
+	     hash2_cmp_callback_t *key_compare_cb, void *context)
+{
+	struct hash2_table *hash;
+
+	hash = i_new(struct hash2_table, 1);
+	hash->initial_size = I_MAX(initial_size, HASH_TABLE_MIN_SIZE);
+	hash->value_size = value_size;
+	hash->key_hash_cb = key_hash_cb;
+	hash->key_compare_cb = key_compare_cb;
+	hash->context = context;
+
+	hash->value_pool = pool_alloconly_create("hash2 value pool", 16384);
+	hash2_alloc_table(hash, hash->initial_size);
+	return hash;
+}
+
+void hash2_destroy(struct hash2_table **_hash)
+{
+	struct hash2_table *hash = *_hash;
+
+	*_hash = NULL;
+	array_free(&hash->hash_table);
+	pool_unref(&hash->value_pool);
+	i_free(hash);
+}
+
+void hash2_clear(struct hash2_table *hash)
+{
+	array_free(&hash->hash_table);
+	hash2_alloc_table(hash, hash->initial_size);
+	p_clear(hash->value_pool);
+	hash->count = 0;
+	hash->deleted_values = NULL;
+}
+
+static void hash2_resize(struct hash2_table *hash, bool grow)
+{
+	ARRAY_TYPE(hash2_value) old_hash_table;
+	struct hash2_value *old_hash, *value, **valuep, *next;
+	unsigned int next_size, old_count, i, idx;
+	float nodes_per_list;
+
+	nodes_per_list = (float)hash->count / (float)hash->hash_table_size;
+	if (nodes_per_list > 0.3 && nodes_per_list < 2.0)
+		return;
+
+	next_size = I_MAX(primes_closest(hash->count + 1), hash->initial_size);
+	if (hash->hash_table_size >= next_size &&
+	    (grow || next_size == hash->hash_table_size))
+		return;
+
+	old_hash_table = hash->hash_table;
+	hash2_alloc_table(hash, next_size);
+
+	old_count = array_count(&old_hash_table);
+	for (i = 0; i < old_count; i++) {
+		old_hash = array_idx_elem(&old_hash_table, i);
+		for (value = old_hash; value != NULL; value = next) {
+			next = value->next;
+
+			idx = value->key_hash % hash->hash_table_size;
+			valuep = array_idx_modifiable(&hash->hash_table, idx);
+			value->next = *valuep;
+			*valuep = value;
+		}
+	}
+	array_free(&old_hash_table);
+}
+
+void *hash2_lookup(const struct hash2_table *hash, const void *key)
+{
+	unsigned int key_hash = hash->key_hash_cb(key);
+	struct hash2_value *value;
+	void *user_value;
+
+	value = array_idx_elem(&hash->hash_table,
+			       key_hash % hash->hash_table_size);
+	while (value != NULL) {
+		if (value->key_hash == key_hash) {
+			user_value = value + 1;
+			if (hash->key_compare_cb(key, user_value,
+						 hash->context))
+				return user_value;
+		}
+		value = value->next;
+	}
+	return NULL;
+}
+
+void *hash2_iterate(const struct hash2_table *hash,
+		    unsigned int key_hash, struct hash2_iter *iter)
+{
+	struct hash2_value *value;
+
+	if (iter->value == NULL) {
+		iter->key_hash = key_hash;
+		value = array_idx_elem(&hash->hash_table,
+				       key_hash % hash->hash_table_size);
+		iter->next_value = value;
+	}
+	while (iter->next_value != NULL) {
+		if (iter->next_value->key_hash == key_hash) {
+			iter->value = iter->next_value;
+			iter->next_value = iter->next_value->next;
+			return iter->value + 1;
+		}
+		iter->next_value = iter->next_value->next;
+	}
+	return NULL;
+}
+
+void *hash2_insert(struct hash2_table *hash, const void *key)
+{
+	return hash2_insert_hash(hash, hash->key_hash_cb(key));
+}
+
+void *hash2_insert_hash(struct hash2_table *hash, unsigned int key_hash)
+{
+	struct hash2_value *value, **valuep;
+
+	hash2_resize(hash, TRUE);
+
+	if (hash->deleted_values != NULL) {
+		value = hash->deleted_values;
+		hash->deleted_values = value->next;
+		value->next = NULL;
+		memset(value + 1, 0, hash->value_size);
+	} else {
+		value = p_malloc(hash->value_pool,
+				 sizeof(*value) + hash->value_size);
+	}
+	value->key_hash = key_hash;
+
+	valuep = array_idx_modifiable(&hash->hash_table,
+				      key_hash % hash->hash_table_size);
+	value->next = *valuep;
+	*valuep = value;
+
+	hash->count++;
+	return value + 1;
+}
+
+static void
+hash2_remove_value_p(struct hash2_table *hash, struct hash2_value **valuep)
+{
+	struct hash2_value *deleted_value;
+
+	deleted_value = *valuep;
+	*valuep = deleted_value->next;
+
+	deleted_value->next = hash->deleted_values;
+	hash->deleted_values = deleted_value;
+
+	hash->count--;
+}
+
+void hash2_remove(struct hash2_table *hash, const void *key)
+{
+	unsigned int key_hash = hash->key_hash_cb(key);
+	struct hash2_value **valuep;
+
+	valuep = array_idx_modifiable(&hash->hash_table,
+				      key_hash % hash->hash_table_size);
+	while (*valuep != NULL) {
+		if ((*valuep)->key_hash == key_hash &&
+		    hash->key_compare_cb(key, (*valuep) + 1, hash->context)) {
+			hash2_remove_value_p(hash, valuep);
+			hash2_resize(hash, FALSE);
+			return;
+		}
+		valuep = &(*valuep)->next;
+	}
+	i_panic("hash2_remove(): key not found");
+}
+
+void hash2_remove_iter(struct hash2_table *hash, struct hash2_iter *iter)
+{
+	struct hash2_value **valuep, *next;
+
+	valuep = array_idx_modifiable(&hash->hash_table,
+				      iter->key_hash % hash->hash_table_size);
+	while (*valuep != NULL) {
+		if (*valuep == iter->value) {
+			next = (*valuep)->next;
+			/* don't allow resizing, otherwise iterating would
+			   break completely */
+			hash2_remove_value_p(hash, valuep);
+			iter->next_value = next;
+			return;
+		}
+		valuep = &(*valuep)->next;
+	}
+	i_panic("hash2_remove_value(): key/value not found");
+}
+
+unsigned int hash2_count(const struct hash2_table *hash)
+{
+	return hash->count;
+}