1 files changed, 218 insertions, 0 deletions
diff --git a/src/hashtable.c b/src/hashtable.c
new file mode 100644
index 000000000..4006a8714
--- /dev/null
+++ b/src/hashtable.c
@@ -0,0 +1,218 @@
+/*
+ * This file is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License, version 2,
+ * as published by the Free Software Foundation.
+ *
+ * In addition to the permissions in the GNU General Public License,
+ * the authors give you unlimited permission to link the compiled
+ * version of this file into combinations with other programs,
+ * and to distribute those combinations without any restriction
+ * coming from the use of this file.  (The General Public License
+ * restrictions do apply in other respects; for example, they cover
+ * modification of the file, and distribution when not linked into
+ * a combined executable.)
+ *
+ * This file 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 General Public License
+ * along with this program; see the file COPYING.  If not, write to
+ * the Free Software Foundation, 51 Franklin Street, Fifth Floor,
+ * Boston, MA 02110-1301, USA.
+ */
+
+#include "common.h"
+#include "repository.h"
+#include "commit.h"
+
+static const int default_table_size = 32;
+static const double max_load_factor = 0.65;
+
+static void hashtable_resize(git_hashtable *table)
+{
+	git_hashtable_node **new_nodes;
+	unsigned int new_size, i;
+
+	assert(table);
+
+	new_size = (table->size_mask + 1) * 2;
+
+	new_nodes = git__malloc(new_size * sizeof(git_hashtable_node *));
+	if (new_nodes == NULL)
+		return;
+
+	memset(new_nodes, 0x0, new_size * sizeof(git_hashtable_node *));
+
+	for (i = 0; i <= table->size_mask; ++i) {
+		git_hashtable_node *n;
+		unsigned int index;
+
+		while ((n = table->nodes[i]) != NULL) {
+			table->nodes[i] = n->next;
+			index = n->hash & (new_size - 1);
+			n->next = new_nodes[index];
+			new_nodes[index] = n;
+		}
+	}
+
+	free(table->nodes);
+	table->nodes = new_nodes;
+	table->size_mask = (new_size - 1);
+	table->max_count = (unsigned int)(new_size * max_load_factor);
+}
+
+git_hashtable *git_hashtable_alloc(unsigned int min_size, 
+		git_hash_ptr hash,
+		git_hash_keyeq_ptr key_eq)
+{
+	unsigned int i;
+	git_hashtable *table;
+
+	assert(hash && key_eq);
+
+	if ((table = git__malloc(sizeof(git_hashtable))) == NULL)
+		return NULL;
+
+	/* round up size to closest power of 2 */
+	min_size--;
+	min_size |= min_size >> 1;
+	min_size |= min_size >> 2;
+	min_size |= min_size >> 4;
+	min_size |= min_size >> 8;
+	min_size |= min_size >> 16;
+
+	table->size_mask = min_size;
+	table->count = 0;
+	table->max_count = (unsigned int)((min_size + 1) * max_load_factor);
+
+	table->hash = hash;
+	table->key_equal = key_eq;
+
+	table->nodes = git__malloc((min_size + 1) * sizeof(git_hashtable_node *));
+
+	if (table->nodes == NULL) {
+		free(table);
+		return NULL;
+	}
+
+	for (i = 0; i <= min_size; ++i)
+		table->nodes[i] = NULL;
+
+	return table;
+}
+
+void git_hashtable_clear(git_hashtable *table)
+{
+	unsigned int index;
+
+	assert(table);
+
+	for (index = 0; index <= table->size_mask; ++index) {
+		git_hashtable_node *node, *next_node;
+
+		node = table->nodes[index];
+		while (node != NULL) {
+			next_node = node->next;
+			free(node);
+			node = next_node;
+		}
+
+		table->nodes[index] = NULL;
+	}
+
+	table->count = 0;
+}
+
+void git_hashtable_free(git_hashtable *table)
+{
+	assert(table);
+
+	git_hashtable_clear(table);
+	free(table->nodes);
+	free(table);
+}
+
+
+int git_hashtable_insert(git_hashtable *table, const void *key, void *value)
+{
+	git_hashtable_node *node;
+	uint32_t index, hash;
+
+	assert(table);
+
+	if (table->count + 1 > table->max_count)
+		hashtable_resize(table);
+
+	node = git__malloc(sizeof(git_hashtable_node));
+	if (node == NULL)
+		return GIT_ENOMEM;
+
+	hash = table->hash(key);
+	index = (hash & table->size_mask);
+
+	node->object = value;
+	node->hash = hash;
+	node->next = table->nodes[index];
+
+	table->nodes[index] = node;
+	table->count++;
+
+	return GIT_SUCCESS;
+}
+
+void *git_hashtable_lookup(git_hashtable *table, const void *key)
+{
+	git_hashtable_node *node;
+	uint32_t index, hash;
+
+	assert(table);
+
+	hash = table->hash(key);
+	index = (hash & table->size_mask);
+	node = table->nodes[index];
+
+	while (node != NULL) {
+		if (node->hash == hash && table->key_equal(node->object, key))
+			return node->object;
+
+		node = node->next;
+	}
+
+	return NULL;
+}
+
+
+
+void git_hashtable_iterator_init(git_hashtable *table, git_hashtable_iterator *it)
+{
+	assert(table && it);
+
+	memset(it, 0x0, sizeof(git_hashtable_iterator));
+
+	it->nodes = table->nodes;
+	it->current_node = NULL;
+	it->current_pos = 0;
+	it->size = table->size_mask + 1;
+}
+
+void *git_hashtable_iterator_next(git_hashtable_iterator *it)
+{
+	git_hashtable_node *next = NULL;
+
+	assert(it);
+
+	while (it->current_node == NULL) {
+		if (it->current_pos >= it->size)
+			return NULL;
+
+		it->current_node = it->nodes[it->current_pos++];
+	}
+
+	next = it->current_node;
+	it->current_node = it->current_node->next;
+
+	return next->object;
+}
+