Convert hashtable usage over to khash

This updates khash.h with some extra features (like error checking
on allocations, ability to use wrapped malloc, foreach calls, etc),
creates two high-level wrappers around khash: `git_khash_str` and
`git_khash_oid` for string-to-void-ptr and oid-to-void-ptr tables,
then converts all of the old usage of `git_hashtable` over to use
these new hashtables.

For `git_khash_str`, I've tried to create a set of macros that
yield an API not too unlike the old `git_hashtable` API.  Since
the oid hashtable is only used in one file, I haven't bother to
set up all those macros and just use the khash APIs directly for
now.

13 files changed, 433 insertions, 202 deletions

diff --git a/src/attr.c b/src/attr.c
index f5d50bb42..1d7f3aa22 100644
--- a/src/attr.c
+++ b/src/attr.c
@@ -3,6 +3,8 @@
 #include "config.h"
 #include <ctype.h>
 
+GIT_KHASH_STR__IMPLEMENTATION;
+
 static int collect_attr_files(
 	git_repository *repo, const char *path, git_vector *files);
 
@@ -124,14 +126,14 @@ int git_attr_foreach(
 	git_attr_file *file;
 	git_attr_rule *rule;
 	git_attr_assignment *assign;
-	git_hashtable *seen = NULL;
+	git_khash_str *seen = NULL;
 
 	if ((error = git_attr_path__init(
 			&path, pathname, git_repository_workdir(repo))) < 0 ||
 		(error = collect_attr_files(repo, pathname, &files)) < 0)
 		return error;
 
-	seen = git_hashtable_alloc(8, git_hash__strhash_cb, git_hash__strcmp_cb);
+	seen = git_khash_str_alloc();
 	GITERR_CHECK_ALLOC(seen);
 
 	git_vector_foreach(&files, i, file) {
@@ -140,10 +142,11 @@ int git_attr_foreach(
 
 			git_vector_foreach(&rule->assigns, k, assign) {
 				/* skip if higher priority assignment was already seen */
-				if (git_hashtable_lookup(seen, assign->name))
+				if (git_khash_str_exists(seen, assign->name))
 					continue;
 
-				if (!(error = git_hashtable_insert(seen, assign->name, assign)))
+				git_khash_str_insert(seen, assign->name, assign, error);
+				if (error >= 0)
 					error = callback(assign->name, assign->value, payload);
 
 				if (error != 0)
@@ -153,7 +156,7 @@ int git_attr_foreach(
 	}
 
 cleanup:
-	git_hashtable_free(seen);
+	git_khash_str_free(seen);
 	git_vector_free(&files);
 
 	return error;
@@ -197,10 +200,12 @@ int git_attr_add_macro(
 bool git_attr_cache__is_cached(git_repository *repo, const char *path)
 {
 	const char *cache_key = path;
+	git_khash_str *files = git_repository_attr_cache(repo)->files;
+
 	if (repo && git__prefixcmp(cache_key, git_repository_workdir(repo)) == 0)
 		cache_key += strlen(git_repository_workdir(repo));
-	return (git_hashtable_lookup(
-		git_repository_attr_cache(repo)->files, cache_key) != NULL);
+
+	return git_khash_str_exists(files, cache_key);
 }
 
 int git_attr_cache__lookup_or_create_file(
@@ -213,9 +218,11 @@ int git_attr_cache__lookup_or_create_file(
 	int error;
 	git_attr_cache *cache = git_repository_attr_cache(repo);
 	git_attr_file *file = NULL;
+	khiter_t pos;
 
-	if ((file = git_hashtable_lookup(cache->files, key)) != NULL) {
-		*file_ptr = file;
+	pos = git_khash_str_lookup_index(cache->files, key);
+	if (git_khash_str_valid_index(cache->files, pos)) {
+		*file_ptr = git_khash_str_value_at(cache->files, pos);
 		return 0;
 	}
 
@@ -232,8 +239,11 @@ int git_attr_cache__lookup_or_create_file(
 	else
 		error = git_attr_file__set_path(repo, key, file);
 
-	if (!error)
-		error = git_hashtable_insert(cache->files, file->path, file);
+	if (!error) {
+		git_khash_str_insert(cache->files, file->path, file, error);
+		if (error > 0)
+			error = 0;
+	}
 
 	if (error < 0) {
 		git_attr_file__free(file);
@@ -373,18 +383,14 @@ int git_attr_cache__init(git_repository *repo)
 
 	/* allocate hashtable for attribute and ignore file contents */
 	if (cache->files == NULL) {
-		cache->files = git_hashtable_alloc(
-			8, git_hash__strhash_cb, git_hash__strcmp_cb);
-		if (!cache->files)
-			return -1;
+		cache->files = git_khash_str_alloc();
+		GITERR_CHECK_ALLOC(cache->files);
 	}
 
 	/* allocate hashtable for attribute macros */
 	if (cache->macros == NULL) {
-		cache->macros = git_hashtable_alloc(
-			8, git_hash__strhash_cb, git_hash__strcmp_cb);
-		if (!cache->macros)
-			return -1;
+		cache->macros = git_khash_str_alloc();
+		GITERR_CHECK_ALLOC(cache->macros);
 	}
 
 	/* allocate string pool */
@@ -409,19 +415,22 @@ void git_attr_cache_flush(
 
 	if (cache->files != NULL) {
 		git_attr_file *file;
-		GIT_HASHTABLE_FOREACH_VALUE(
-			cache->files, file, git_attr_file__free(file));
-		git_hashtable_free(cache->files);
-		cache->files = NULL;
+
+		git_khash_str_foreach_value(cache->files, file, {
+			git_attr_file__free(file);
+		});
+
+		git_khash_str_free(cache->files);
 	}
 
 	if (cache->macros != NULL) {
 		git_attr_rule *rule;
 
-		GIT_HASHTABLE_FOREACH_VALUE(
-			cache->macros, rule, git_attr_rule__free(rule));
-		git_hashtable_free(cache->macros);
-		cache->macros = NULL;
+		git_khash_str_foreach_value(cache->macros, rule, {
+			git_attr_rule__free(rule);
+		});
+
+		git_khash_str_free(cache->macros);
 	}
 
 	git_pool_clear(&cache->pool);
@@ -431,10 +440,28 @@ void git_attr_cache_flush(
 
 int git_attr_cache__insert_macro(git_repository *repo, git_attr_rule *macro)
 {
+	git_khash_str *macros = git_repository_attr_cache(repo)->macros;
+	int error;
+
 	/* TODO: generate warning log if (macro->assigns.length == 0) */
 	if (macro->assigns.length == 0)
 		return 0;
 
-	return git_hashtable_insert(
-		git_repository_attr_cache(repo)->macros, macro->match.pattern, macro);
+	git_khash_str_insert(macros, macro->match.pattern, macro, error);
+	return (error < 0) ? -1 : 0;
 }
+
+git_attr_rule *git_attr_cache__lookup_macro(
+	git_repository *repo, const char *name)
+{
+	git_khash_str *macros = git_repository_attr_cache(repo)->macros;
+	khiter_t pos;
+
+	pos = git_khash_str_lookup_index(macros, name);
+
+	if (!git_khash_str_valid_index(macros, pos))
+		return NULL;
+
+	return (git_attr_rule *)git_khash_str_value_at(macros, pos);
+}
+
diff --git a/src/attr.h b/src/attr.h
index 825cbfe4e..75e98607f 100644
--- a/src/attr.h
+++ b/src/attr.h
@@ -8,6 +8,7 @@
 #define INCLUDE_attr_h__
 
 #include "attr_file.h"
+#include "khash_str.h"
 
 #define GIT_ATTR_CONFIG   "core.attributesfile"
 #define GIT_IGNORE_CONFIG "core.excludesfile"
@@ -15,8 +16,8 @@
 typedef struct {
 	int initialized;
 	git_pool pool;
-	git_hashtable *files;	/* hash path to git_attr_file of rules */
-	git_hashtable *macros;	/* hash name to vector<git_attr_assignment> */
+	git_khash_str *files;	/* hash path to git_attr_file of rules */
+	git_khash_str *macros;	/* hash name to vector<git_attr_assignment> */
 	const char *cfg_attr_file; /* cached value of core.attributesfile */
 	const char *cfg_excl_file; /* cached value of core.excludesfile */
 } git_attr_cache;
@@ -26,6 +27,9 @@ extern int git_attr_cache__init(git_repository *repo);
 extern int git_attr_cache__insert_macro(
 	git_repository *repo, git_attr_rule *macro);
 
+extern git_attr_rule *git_attr_cache__lookup_macro(
+	git_repository *repo, const char *name);
+
 extern int git_attr_cache__lookup_or_create_file(
 	git_repository *repo,
 	const char *key,
diff --git a/src/attr_file.c b/src/attr_file.c
index 7909c49b4..e34053fc3 100644
--- a/src/attr_file.c
+++ b/src/attr_file.c
@@ -515,8 +515,8 @@ int git_attr_assignment__parse(
 
 		/* expand macros (if given a repo with a macro cache) */
 		if (repo != NULL && assign->value == git_attr__true) {
-			git_attr_rule *macro = git_hashtable_lookup(
-				git_repository_attr_cache(repo)->macros, assign->name);
+			git_attr_rule *macro =
+				git_attr_cache__lookup_macro(repo, assign->name);
 
 			if (macro != NULL) {
 				unsigned int i;
diff --git a/src/config.c b/src/config.c
index f5cfa9ec0..4c971924c 100644
--- a/src/config.c
+++ b/src/config.c
@@ -7,7 +7,6 @@
 
 #include "common.h"
 #include "fileops.h"
-#include "hashtable.h"
 #include "config.h"
 #include "git2/config.h"
 #include "vector.h"
diff --git a/src/config_file.c b/src/config_file.c
index fd634fbca..a0ce329fc 100644
--- a/src/config_file.c
+++ b/src/config_file.c
@@ -12,12 +12,14 @@
 #include "buffer.h"
 #include "git2/config.h"
 #include "git2/types.h"
-
+#include "khash_str.h"
 
 #include <ctype.h>
 #include <sys/types.h>
 #include <regex.h>
 
+GIT_KHASH_STR__IMPLEMENTATION;
+
 typedef struct cvar_t {
 	struct cvar_t *next;
 	char *key; /* TODO: we might be able to get rid of this */
@@ -70,7 +72,7 @@ typedef struct {
 typedef struct {
 	git_config_file parent;
 
-	git_hashtable *values;
+	git_khash_str *values;
 
 	struct {
 		git_buf buffer;
@@ -130,22 +132,21 @@ static int normalize_name(const char *in, char **out)
 	return 0;
 }
 
-static void free_vars(git_hashtable *values)
+static void free_vars(git_khash_str *values)
 {
 	cvar_t *var = NULL;
 
 	if (values == NULL)
 		return;
 
-	GIT_HASHTABLE_FOREACH_VALUE(values, var,
-	      do {
-		      cvar_t *next = CVAR_LIST_NEXT(var);
-		      cvar_free(var);
-		      var = next;
-	      } while (var != NULL);
-	)
+	git_khash_str_foreach_value(values, var,
+		while (var != NULL) {
+			cvar_t *next = CVAR_LIST_NEXT(var);
+			cvar_free(var);
+			var = next;
+		});
 
-	git_hashtable_free(values);
+	git_khash_str_free(values);
 }
 
 static int config_open(git_config_file *cfg)
@@ -153,7 +154,7 @@ static int config_open(git_config_file *cfg)
 	int res;
 	diskfile_backend *b = (diskfile_backend *)cfg;
 
-	b->values = git_hashtable_alloc (20, git_hash__strhash_cb, git_hash__strcmp_cb);
+	b->values = git_khash_str_alloc();
 	GITERR_CHECK_ALLOC(b->values);
 
 	git_buf_init(&b->reader.buffer, 0);
@@ -195,24 +196,25 @@ static int file_foreach(git_config_file *backend, int (*fn)(const char *, const
 	if (!b->values)
 		return 0;
 
-	GIT_HASHTABLE_FOREACH(b->values, key, var,
+	git_khash_str_foreach(b->values, key, var,
 		do {
 			if (fn(key, var->value, data) < 0)
 				break;
 
 			var = CVAR_LIST_NEXT(var);
 		} while (var != NULL);
-	)
+	);
 
 	return 0;
 }
 
 static int config_set(git_config_file *cfg, const char *name, const char *value)
 {
-	cvar_t *var = NULL;
-	cvar_t *existing = NULL, *old_value = NULL;
+	cvar_t *var = NULL, *old_var;
 	diskfile_backend *b = (diskfile_backend *)cfg;
 	char *key;
+	khiter_t pos;
+	int rval;
 
 	if (normalize_name(name, &key) < 0)
 		return -1;
@@ -221,8 +223,9 @@ static int config_set(git_config_file *cfg, const char *name, const char *value)
 	 * Try to find it in the existing values and update it if it
 	 * only has one value.
 	 */
-	existing = git_hashtable_lookup(b->values, key);
-	if (existing != NULL) {
+	pos = git_khash_str_lookup_index(b->values, key);
+	if (git_khash_str_valid_index(b->values, pos)) {
+		cvar_t *existing = git_khash_str_value_at(b->values, pos);
 		char *tmp = NULL;
 
 		git__free(key);
@@ -255,10 +258,11 @@ static int config_set(git_config_file *cfg, const char *name, const char *value)
 		GITERR_CHECK_ALLOC(var->value);
 	}
 
-	if (git_hashtable_insert2(b->values, key, var, (void **)&old_value) < 0)
+	git_khash_str_insert2(b->values, key, var, old_var, rval);
+	if (rval < 0)
 		return -1;
-
-	cvar_free(old_value);
+	if (old_var != NULL)
+		cvar_free(old_var);
 
 	if (config_write(b, key, NULL, value) < 0) {
 		cvar_free(var);
@@ -273,21 +277,22 @@ static int config_set(git_config_file *cfg, const char *name, const char *value)
  */
 static int config_get(git_config_file *cfg, const char *name, const char **out)
 {
-	cvar_t *var;
 	diskfile_backend *b = (diskfile_backend *)cfg;
 	char *key;
+	khiter_t pos;
 
 	if (normalize_name(name, &key) < 0)
 		return -1;
 
-	var = git_hashtable_lookup(b->values, key);
+	pos = git_khash_str_lookup_index(b->values, key);
 	git__free(key);
 
 	/* no error message; the config system will write one */
-	if (var == NULL)
+	if (!git_khash_str_valid_index(b->values, pos))
 		return GIT_ENOTFOUND;
 
-	*out = var->value;
+	*out = ((cvar_t *)git_khash_str_value_at(b->values, pos))->value;
+
 	return 0;
 }
 
@@ -301,16 +306,19 @@ static int config_get_multivar(
 	cvar_t *var;
 	diskfile_backend *b = (diskfile_backend *)cfg;
 	char *key;
+	khiter_t pos;
 
 	if (normalize_name(name, &key) < 0)
 		return -1;
 
-	var = git_hashtable_lookup(b->values, key);
+	pos = git_khash_str_lookup_index(b->values, key);
 	git__free(key);
 
-	if (var == NULL)
+	if (!git_khash_str_valid_index(b->values, pos))
 		return GIT_ENOTFOUND;
 
+	var = git_khash_str_value_at(b->values, pos);
+
 	if (regex_str != NULL) {
 		regex_t regex;
 		int result;
@@ -350,7 +358,8 @@ static int config_get_multivar(
 	return 0;
 }
 
-static int config_set_multivar(git_config_file *cfg, const char *name, const char *regexp, const char *value)
+static int config_set_multivar(
+	git_config_file *cfg, const char *name, const char *regexp, const char *value)
 {
 	int replaced = 0;
 	cvar_t *var, *newvar;
@@ -358,15 +367,20 @@ static int config_set_multivar(git_config_file *cfg, const char *name, const cha
 	char *key;
 	regex_t preg;
 	int result;
+	khiter_t pos;
 
 	assert(regexp);
 
 	if (normalize_name(name, &key) < 0)
 		return -1;
 
-	var = git_hashtable_lookup(b->values, key);
-	if (var == NULL)
+	pos = git_khash_str_lookup_index(b->values, key);
+	if (!git_khash_str_valid_index(b->values, pos)) {
+		git__free(key);
 		return GIT_ENOTFOUND;
+	}
+
+	var = git_khash_str_value_at(b->values, pos);
 
 	result = regcomp(&preg, regexp, REG_EXTENDED);
 	if (result < 0) {
@@ -421,22 +435,26 @@ static int config_delete(git_config_file *cfg, const char *name)
 	diskfile_backend *b = (diskfile_backend *)cfg;
 	char *key;
 	int result;
+	khiter_t pos;
 
 	if (normalize_name(name, &key) < 0)
 		return -1;
 
-	var = git_hashtable_lookup(b->values, key);
+	pos = git_khash_str_lookup_index(b->values, key);
 	git__free(key);
 
-	if (var == NULL)
+	if (!git_khash_str_valid_index(b->values, pos))
 		return GIT_ENOTFOUND;
 
+	var = git_khash_str_value_at(b->values, pos);
+
 	if (var->next != NULL) {
 		giterr_set(GITERR_CONFIG, "Cannot delete multivar with a single delete");
 		return -1;
 	}
 
-	git_hashtable_remove(b->values, var->key);
+	git_khash_str_delete_at(b->values, pos);
+
 	result = config_write(b, var->key, NULL, NULL);
 
 	cvar_free(var);
@@ -843,6 +861,7 @@ static int config_parse(diskfile_backend *cfg_file)
 	cvar_t *var, *existing;
 	git_buf buf = GIT_BUF_INIT;
 	int result = 0;
+	khiter_t pos;
 
 	/* Initialize the reading position */
 	cfg_file->reader.read_ptr = cfg_file->reader.buffer.ptr;
@@ -895,10 +914,14 @@ static int config_parse(diskfile_backend *cfg_file)
 			var->value = var_value;
 
 			/* Add or append the new config option */
-			existing = git_hashtable_lookup(cfg_file->values, var->key);
-			if (existing == NULL) {
-				result = git_hashtable_insert(cfg_file->values, var->key, var);
+			pos = git_khash_str_lookup_index(cfg_file->values, var->key);
+			if (!git_khash_str_valid_index(cfg_file->values, pos)) {
+				git_khash_str_insert(cfg_file->values, var->key, var, result);
+				if (result < 0)
+					break;
+				result = 0;
 			} else {
+				existing = git_khash_str_value_at(cfg_file->values, pos);
 				while (existing->next != NULL) {
 					existing = existing->next;
 				}
diff --git a/src/khash.h b/src/khash.h
index 1a28e1184..f9d239336 100644
--- a/src/khash.h
+++ b/src/khash.h
@@ -157,6 +157,19 @@ typedef khint_t khiter_t;
 #define kroundup32(x) (--(x), (x)|=(x)>>1, (x)|=(x)>>2, (x)|=(x)>>4, (x)|=(x)>>8, (x)|=(x)>>16, ++(x))
 #endif
 
+#ifndef kcalloc
+#define kcalloc(N,Z) calloc(N,Z)
+#endif
+#ifndef kmalloc
+#define kmalloc(Z) malloc(Z)
+#endif
+#ifndef krealloc
+#define krealloc(P,Z) realloc(P,Z)
+#endif
+#ifndef kfree
+#define kfree(P) free(P)
+#endif
+
 static const double __ac_HASH_UPPER = 0.77;
 
 #define __KHASH_TYPE(name, khkey_t, khval_t) \
@@ -167,27 +180,25 @@ static const double __ac_HASH_UPPER = 0.77;
 		khval_t *vals; \
 	} kh_##name##_t;
 
-#define KHASH_DECLARE(name, khkey_t, khval_t)		 					\
-	__KHASH_TYPE(name, khkey_t, khval_t) 								\
-	extern kh_##name##_t *kh_init_##name();								\
+#define __KHASH_PROTOTYPES(name, khkey_t, khval_t)	 					\
+	extern kh_##name##_t *kh_init_##name(void);							\
 	extern void kh_destroy_##name(kh_##name##_t *h);					\
 	extern void kh_clear_##name(kh_##name##_t *h);						\
 	extern khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key); 	\
-	extern void kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets); \
+	extern int kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets); \
 	extern khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret); \
 	extern void kh_del_##name(kh_##name##_t *h, khint_t x);
 
-#define KHASH_INIT2(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \
-	__KHASH_TYPE(name, khkey_t, khval_t) 								\
-	SCOPE kh_##name##_t *kh_init_##name() {								\
-		return (kh_##name##_t*)calloc(1, sizeof(kh_##name##_t));		\
+#define __KHASH_IMPL(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \
+	SCOPE kh_##name##_t *kh_init_##name(void) {							\
+		return (kh_##name##_t*)kcalloc(1, sizeof(kh_##name##_t));		\
 	}																	\
 	SCOPE void kh_destroy_##name(kh_##name##_t *h)						\
 	{																	\
 		if (h) {														\
-			free(h->keys); free(h->flags);								\
-			free(h->vals);												\
-			free(h);													\
+			kfree(h->keys); kfree(h->flags);								\
+			kfree(h->vals);												\
+			kfree(h);													\
 		}																\
 	}																	\
 	SCOPE void kh_clear_##name(kh_##name##_t *h)						\
@@ -211,7 +222,7 @@ static const double __ac_HASH_UPPER = 0.77;
 			return __ac_iseither(h->flags, i)? h->n_buckets : i;		\
 		} else return 0;												\
 	}																	\
-	SCOPE void kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets) \
+	SCOPE int kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets) \
 	{ /* This function uses 0.25*n_bucktes bytes of working space instead of [sizeof(key_t+val_t)+.25]*n_buckets. */ \
 		khint32_t *new_flags = 0;										\
 		khint_t j = 1;													\
@@ -220,11 +231,18 @@ static const double __ac_HASH_UPPER = 0.77;
 			if (new_n_buckets < 4) new_n_buckets = 4;					\
 			if (h->size >= (khint_t)(new_n_buckets * __ac_HASH_UPPER + 0.5)) j = 0;	/* requested size is too small */ \
 			else { /* hash table size to be changed (shrink or expand); rehash */ \
-				new_flags = (khint32_t*)malloc(__ac_fsize(new_n_buckets) * sizeof(khint32_t));	\
+				new_flags = (khint32_t*)kmalloc(__ac_fsize(new_n_buckets) * sizeof(khint32_t));	\
+				if (!new_flags) return -1;								\
 				memset(new_flags, 0xaa, __ac_fsize(new_n_buckets) * sizeof(khint32_t)); \
 				if (h->n_buckets < new_n_buckets) {	/* expand */		\
-					h->keys = (khkey_t*)realloc(h->keys, new_n_buckets * sizeof(khkey_t)); \
-					if (kh_is_map) h->vals = (khval_t*)realloc(h->vals, new_n_buckets * sizeof(khval_t)); \
+					khkey_t *new_keys = (khkey_t*)krealloc(h->keys, new_n_buckets * sizeof(khkey_t)); \
+					if (!new_keys) return -1;							\
+					h->keys = new_keys;									\
+					if (kh_is_map) {									\
+						khval_t *new_vals = (khval_t*)krealloc(h->vals, new_n_buckets * sizeof(khval_t)); \
+						if (!new_vals) return -1;						\
+						h->vals = new_vals;								\
+					}													\
 				} /* otherwise shrink */								\
 			}															\
 		}																\
@@ -257,22 +275,28 @@ static const double __ac_HASH_UPPER = 0.77;
 				}														\
 			}															\
 			if (h->n_buckets > new_n_buckets) { /* shrink the hash table */ \
-				h->keys = (khkey_t*)realloc(h->keys, new_n_buckets * sizeof(khkey_t)); \
-				if (kh_is_map) h->vals = (khval_t*)realloc(h->vals, new_n_buckets * sizeof(khval_t)); \
+				h->keys = (khkey_t*)krealloc(h->keys, new_n_buckets * sizeof(khkey_t)); \
+				if (kh_is_map) h->vals = (khval_t*)krealloc(h->vals, new_n_buckets * sizeof(khval_t)); \
 			}															\
-			free(h->flags); /* free the working space */				\
+			kfree(h->flags); /* free the working space */				\
 			h->flags = new_flags;										\
 			h->n_buckets = new_n_buckets;								\
 			h->n_occupied = h->size;									\
 			h->upper_bound = (khint_t)(h->n_buckets * __ac_HASH_UPPER + 0.5); \
 		}																\
+		return 0;														\
 	}																	\
 	SCOPE khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret) \
 	{																	\
 		khint_t x;														\
 		if (h->n_occupied >= h->upper_bound) { /* update the hash table */ \
-			if (h->n_buckets > (h->size<<1)) kh_resize_##name(h, h->n_buckets - 1); /* clear "deleted" elements */ \
-			else kh_resize_##name(h, h->n_buckets + 1); /* expand the hash table */ \
+			if (h->n_buckets > (h->size<<1)) {							\
+				if (kh_resize_##name(h, h->n_buckets - 1) < 0) { /* clear "deleted" elements */ \
+					*ret = -1; return h->n_buckets;						\
+				}														\
+			} else if (kh_resize_##name(h, h->n_buckets + 1) < 0) { /* expand the hash table */ \
+				*ret = -1; return h->n_buckets;							\
+			}															\
 		} /* TODO: to implement automatically shrinking; resize() already support shrinking */ \
 		{																\
 			khint_t inc, k, i, site, last, mask = h->n_buckets - 1;		\
@@ -312,6 +336,14 @@ static const double __ac_HASH_UPPER = 0.77;
 		}																\
 	}
 
+#define KHASH_DECLARE(name, khkey_t, khval_t)		 					\
+	__KHASH_TYPE(name, khkey_t, khval_t) 								\
+	__KHASH_PROTOTYPES(name, khkey_t, khval_t)
+
+#define KHASH_INIT2(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \
+	__KHASH_TYPE(name, khkey_t, khval_t) 								\
+	__KHASH_IMPL(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal)
+
 #define KHASH_INIT(name, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \
 	KHASH_INIT2(name, static inline, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal)
 
@@ -497,6 +529,34 @@ static inline khint_t __ac_Wang_hash(khint_t key)
  */
 #define kh_n_buckets(h) ((h)->n_buckets)
 
+/*! @function
+  @abstract     Iterate over the entries in the hash table
+  @param  h     Pointer to the hash table [khash_t(name)*]
+  @param  kvar  Variable to which key will be assigned
+  @param  vvar  Variable to which value will be assigned
+  @param  code  Block of code to execute
+ */
+#define kh_foreach(h, kvar, vvar, code) { khint_t __i;		\
+	for (__i = kh_begin(h); __i != kh_end(h); ++__i) {		\
+		if (!kh_exist(h,__i)) continue;						\
+		(kvar) = kh_key(h,__i);								\
+		(vvar) = kh_val(h,__i);								\
+		code;												\
+	} }
+
+/*! @function
+  @abstract     Iterate over the values in the hash table
+  @param  h     Pointer to the hash table [khash_t(name)*]
+  @param  vvar  Variable to which value will be assigned
+  @param  code  Block of code to execute
+ */
+#define kh_foreach_value(h, vvar, code) { khint_t __i;		\
+	for (__i = kh_begin(h); __i != kh_end(h); ++__i) {		\
+		if (!kh_exist(h,__i)) continue;						\
+		(vvar) = kh_val(h,__i);								\
+		code;												\
+	} }
+
 /* More conenient interfaces */
 
 /*! @function
diff --git a/src/khash_oid.h b/src/khash_oid.h
new file mode 100644
index 000000000..96d82c759
--- /dev/null
+++ b/src/khash_oid.h
@@ -0,0 +1,42 @@
+/*
+ * Copyright (C) 2012 the libgit2 contributors
+ *
+ * This file is part of libgit2, distributed under the GNU GPL v2 with
+ * a Linking Exception. For full terms see the included COPYING file.
+ */
+#ifndef INCLUDE_khash_oid_h__
+#define INCLUDE_khash_oid_h__
+
+#include "common.h"
+#include "git2/oid.h"
+
+#define kmalloc git__malloc
+#define kcalloc git__calloc
+#define krealloc git__realloc
+#define kfree git__free
+#include "khash.h"
+
+__KHASH_TYPE(oid, const git_oid *, void *);
+typedef khash_t(oid) git_khash_oid;
+
+GIT_INLINE(khint_t) hash_git_oid(const git_oid *oid)
+{
+	int i;
+	khint_t h = 0;
+	for (i = 0; i < 20; ++i)
+		h = (h << 5) - h + oid->id[i];
+	return h;
+}
+
+GIT_INLINE(int) hash_git_oid_equal(const git_oid *a, const git_oid *b)
+{
+	return (memcmp(a->id, b->id, sizeof(a->id)) == 0);
+}
+
+#define GIT_KHASH_OID__IMPLEMENTATION \
+	__KHASH_IMPL(oid, static inline, const git_oid *, void *, 1, hash_git_oid, hash_git_oid_equal)
+
+#define git_khash_oid_alloc() kh_init(oid)
+#define git_khash_oid_free(h) kh_destroy(oid,h), h = NULL
+
+#endif
diff --git a/src/khash_str.h b/src/khash_str.h
new file mode 100644
index 000000000..0b840d836
--- /dev/null
+++ b/src/khash_str.h
@@ -0,0 +1,54 @@
+/*
+ * Copyright (C) 2012 the libgit2 contributors
+ *
+ * This file is part of libgit2, distributed under the GNU GPL v2 with
+ * a Linking Exception. For full terms see the included COPYING file.
+ */
+#ifndef INCLUDE_khash_str_h__
+#define INCLUDE_khash_str_h__
+
+#include "common.h"
+
+#define kmalloc git__malloc
+#define kcalloc git__calloc
+#define krealloc git__realloc
+#define kfree git__free
+#include "khash.h"
+
+__KHASH_TYPE(str, const char *, void *);
+typedef khash_t(str) git_khash_str;
+
+#define GIT_KHASH_STR__IMPLEMENTATION \
+	__KHASH_IMPL(str, static inline, const char *, void *, 1, kh_str_hash_func, kh_str_hash_equal)
+
+#define git_khash_str_alloc()  kh_init(str)
+#define git_khash_str_free(h)  kh_destroy(str, h), h = NULL
+#define git_khash_str_clear(h) kh_clear(str, h)
+
+#define git_khash_str_num_entries(h) kh_size(h)
+
+#define git_khash_str_lookup_index(h, k)  kh_get(str, h, k)
+#define git_khash_str_valid_index(h, idx) (idx != kh_end(h))
+
+#define git_khash_str_exists(h, k) (kh_get(str, h, k) != kh_end(h))
+
+#define git_khash_str_value_at(h, idx)        kh_val(h, idx)
+#define git_khash_str_set_value_at(h, idx, v) kh_val(h, idx) = v
+#define git_khash_str_delete_at(h, idx)       kh_del(str, h, idx)
+
+#define git_khash_str_insert(h, key, val, err) do { \
+	khiter_t __pos = kh_put(str, h, key, &err); \
+	if (err >= 0) kh_val(h, __pos) = val; \
+	} while (0)
+
+#define git_khash_str_insert2(h, key, val, old, err) do { \
+	khiter_t __pos = kh_put(str, h, key, &err); \
+	if (err >= 0) { \
+		old = (err == 0) ? kh_val(h, __pos) : NULL; \
+		kh_val(h, __pos) = val; \
+	} } while (0)
+
+#define git_khash_str_foreach		kh_foreach
+#define git_khash_str_foreach_value	kh_foreach_value
+
+#endif
diff --git a/src/refs.c b/src/refs.c
index 447f3a7b6..7050b4af9 100644
--- a/src/refs.c
+++ b/src/refs.c
@@ -15,6 +15,8 @@
 #include <git2/tag.h>
 #include <git2/object.h>
 
+GIT_KHASH_STR__IMPLEMENTATION;
+
 #define DEFAULT_NESTING_LEVEL	5
 #define MAX_NESTING_LEVEL		10
 
@@ -30,8 +32,6 @@ struct packref {
 	char name[GIT_FLEX_ARRAY];
 };
 
-static const int default_table_size = 32;
-
 static int reference_read(
 	git_buf *file_content,
 	time_t *mtime,
@@ -423,9 +423,7 @@ static int packed_load(git_repository *repo)
 
 	/* First we make sure we have allocated the hash table */
 	if (ref_cache->packfile == NULL) {
-		ref_cache->packfile = git_hashtable_alloc(
-			default_table_size, git_hash__strhash_cb, git_hash__strcmp_cb);
-
+		ref_cache->packfile = git_khash_str_alloc();
 		GITERR_CHECK_ALLOC(ref_cache->packfile);
 	}
 
@@ -440,7 +438,7 @@ static int packed_load(git_repository *repo)
 	 * refresh the packed refs.
 	 */
 	if (result == GIT_ENOTFOUND) {
-		git_hashtable_clear(ref_cache->packfile);
+		git_khash_str_clear(ref_cache->packfile);
 		return 0;
 	}
 
@@ -454,7 +452,7 @@ static int packed_load(git_repository *repo)
 	 * At this point, we want to refresh the packed refs. We already
 	 * have the contents in our buffer.
 	 */
-	git_hashtable_clear(ref_cache->packfile);
+	git_khash_str_clear(ref_cache->packfile);
 
 	buffer_start = (const char *)packfile.ptr;
 	buffer_end = (const char *)(buffer_start) + packfile.size;
@@ -468,6 +466,7 @@ static int packed_load(git_repository *repo)
 	}
 
 	while (buffer_start < buffer_end) {
+		int err;
 		struct packref *ref = NULL;
 
 		if (packed_parse_oid(&ref, &buffer_start, buffer_end) < 0)
@@ -478,15 +477,16 @@ static int packed_load(git_repository *repo)
 				goto parse_failed;
 		}
 
-		if (git_hashtable_insert(ref_cache->packfile, ref->name, ref) < 0)
-			return -1;
+		git_khash_str_insert(ref_cache->packfile, ref->name, ref, err);
+		if (err < 0)
+			goto parse_failed;
 	}
 
 	git_buf_free(&packfile);
 	return 0;
 
 parse_failed:
-	git_hashtable_free(ref_cache->packfile);
+	git_khash_str_free(ref_cache->packfile);
 	ref_cache->packfile = NULL;
 	git_buf_free(&packfile);
 	return -1;
@@ -512,7 +512,7 @@ static int _dirent_loose_listall(void *_data, git_buf *full_path)
 
 	/* do not add twice a reference that exists already in the packfile */
 	if ((data->list_flags & GIT_REF_PACKED) != 0 &&
-		git_hashtable_lookup(data->repo->references.packfile, file_path) != NULL)
+		git_khash_str_exists(data->repo->references.packfile, file_path))
 		return 0;
 
 	if (data->list_flags != GIT_REF_LISTALL) {
@@ -529,6 +529,7 @@ static int _dirent_loose_load(void *data, git_buf *full_path)
 	void *old_ref = NULL;
 	struct packref *ref;
 	const char *file_path;
+	int err;
 
 	if (git_path_isdir(full_path->ptr) == true)
 		return git_path_direach(full_path, _dirent_loose_load, repository);
@@ -538,8 +539,9 @@ static int _dirent_loose_load(void *data, git_buf *full_path)
 	if (loose_lookup_to_packfile(&ref, repository, file_path) < 0)
 		return -1;
 
-	if (git_hashtable_insert2(repository->references.packfile,
-			ref->name, ref, &old_ref) < 0) {
+	git_khash_str_insert2(
+		repository->references.packfile, ref->name, ref, old_ref, err);
+	if (err < 0) {
 		git__free(ref);
 		return -1;
 	}
@@ -734,7 +736,8 @@ static int packed_write(git_repository *repo)
 
 	assert(repo && repo->references.packfile);
 
-	total_refs = (unsigned int)repo->references.packfile->key_count;
+	total_refs =
+		(unsigned int)git_khash_str_num_entries(repo->references.packfile);
 
 	if (git_vector_init(&packing_list, total_refs, packed_sort) < 0)
 		return -1;
@@ -743,10 +746,10 @@ static int packed_write(git_repository *repo)
 	{
 		struct packref *reference;
 
-		GIT_HASHTABLE_FOREACH_VALUE(repo->references.packfile, reference,
-			/* cannot fail: vector already has the right size */
+		/* cannot fail: vector already has the right size */
+		git_khash_str_foreach_value(repo->references.packfile, reference, {
 			git_vector_insert(&packing_list, reference);
-		);
+		});
 	}
 
 	/* sort the vector so the entries appear sorted on the packfile */
@@ -870,7 +873,8 @@ static int reference_exists(int *exists, git_repository *repo, const char *ref_n
 		return -1;
 
 	if (git_path_isfile(ref_path.ptr) == true ||
-		git_hashtable_lookup(repo->references.packfile, ref_path.ptr) != NULL) {
+		git_khash_str_exists(repo->references.packfile, ref_path.ptr))
+	{
 		*exists = 1;
 	} else {
 		*exists = 0;
@@ -936,6 +940,8 @@ static int reference_can_write(
 static int packed_lookup(git_reference *ref)
 {
 	struct packref *pack_ref = NULL;
+	git_khash_str *packfile_refs;
+	khiter_t pos;
 
 	if (packed_load(ref->owner) < 0)
 		return -1;
@@ -952,12 +958,15 @@ static int packed_lookup(git_reference *ref)
 	}
 
 	/* Look up on the packfile */
-	pack_ref = git_hashtable_lookup(ref->owner->references.packfile, ref->name);
-	if (pack_ref == NULL) {
+	packfile_refs = ref->owner->references.packfile;
+	pos = git_khash_str_lookup_index(packfile_refs, ref->name);
+	if (!git_khash_str_valid_index(packfile_refs, pos)) {
 		giterr_set(GITERR_REFERENCE, "Reference '%s' not found", ref->name);
 		return GIT_ENOTFOUND;
 	}
 
+	pack_ref = git_khash_str_value_at(packfile_refs, pos);
+
 	ref->flags = GIT_REF_OID | GIT_REF_PACKED;
 	ref->mtime = ref->owner->references.packfile_time;
 	git_oid_cpy(&ref->target.oid, &pack_ref->oid);
@@ -1002,18 +1011,25 @@ static int reference_delete(git_reference *ref)
 	 * We need to reload the packfile, remove the reference from the
 	 * packing list, and repack */
 	if (ref->flags & GIT_REF_PACKED) {
+		git_khash_str *packfile_refs;
 		struct packref *packref;
+		khiter_t pos;
+
 		/* load the existing packfile */
 		if (packed_load(ref->owner) < 0)
 			return -1;
 
-		if (git_hashtable_remove2(ref->owner->references.packfile,
-				ref->name, (void **) &packref) < 0) {
+		packfile_refs = ref->owner->references.packfile;
+		pos = git_khash_str_lookup_index(packfile_refs, ref->name);
+		if (!git_khash_str_valid_index(packfile_refs, pos)) {
 			giterr_set(GITERR_REFERENCE,
 				"Reference %s stopped existing in the packfile", ref->name);
 			return -1;
 		}
 
+		packref = git_khash_str_value_at(packfile_refs, pos);
+		git_khash_str_delete_at(packfile_refs, pos);
+
 		git__free(packref);
 		if (packed_write(ref->owner) < 0)
 			return -1;
@@ -1467,14 +1483,15 @@ int git_reference_foreach(
 	/* list all the packed references first */
 	if (list_flags & GIT_REF_PACKED) {
 		const char *ref_name;
+		void *ref;
 
 		if (packed_load(repo) < 0)
 			return -1;
 
-		GIT_HASHTABLE_FOREACH_KEY(repo->references.packfile, ref_name,
+		git_khash_str_foreach(repo->references.packfile, ref_name, ref, {
 			if (callback(ref_name, payload) < 0)
 				return 0;
-		);
+		});
 	}
 
 	/* now list the loose references, trying not to
@@ -1538,10 +1555,11 @@ void git_repository__refcache_free(git_refcache *refs)
 	if (refs->packfile) {
 		struct packref *reference;
 
-		GIT_HASHTABLE_FOREACH_VALUE(
-			refs->packfile, reference, git__free(reference));
+		git_khash_str_foreach_value(refs->packfile, reference, {
+			git__free(reference);
+		});
 
-		git_hashtable_free(refs->packfile);
+		git_khash_str_free(refs->packfile);
 	}
 }
 
diff --git a/src/refs.h b/src/refs.h
index e4a225ca3..39648e6d9 100644
--- a/src/refs.h
+++ b/src/refs.h
@@ -10,7 +10,7 @@
 #include "common.h"
 #include "git2/oid.h"
 #include "git2/refs.h"
-#include "hashtable.h"
+#include "khash_str.h"
 
 #define GIT_REFS_DIR "refs/"
 #define GIT_REFS_HEADS_DIR GIT_REFS_DIR "heads/"
@@ -46,7 +46,7 @@ struct git_reference {
 };
 
 typedef struct {
-	git_hashtable *packfile;
+	git_khash_str *packfile;
 	time_t packfile_time;
 } git_refcache;
 
diff --git a/src/repository.h b/src/repository.h
index 178f29742..f53fa697e 100644
--- a/src/repository.h
+++ b/src/repository.h
@@ -13,13 +13,13 @@
 #include "git2/repository.h"
 #include "git2/object.h"
 
-#include "hashtable.h"
 #include "index.h"
 #include "cache.h"
 #include "refs.h"
 #include "buffer.h"
 #include "odb.h"
 #include "attr.h"
+#include "khash_str.h"
 
 #define DOT_GIT ".git"
 #define GIT_DIR DOT_GIT "/"
@@ -83,7 +83,7 @@ struct git_repository {
 	git_cache objects;
 	git_refcache references;
 	git_attr_cache attrcache;
-	git_hashtable *submodules;
+	git_khash_str *submodules;
 
 	char *path_repository;
 	char *workdir;
diff --git a/src/revwalk.c b/src/revwalk.c
index 557966b94..5867e133e 100644
--- a/src/revwalk.c
+++ b/src/revwalk.c
@@ -8,15 +8,17 @@
 #include "common.h"
 #include "commit.h"
 #include "odb.h"
-#include "hashtable.h"
 #include "pqueue.h"
 #include "pool.h"
+#include "khash_oid.h"
 
 #include "git2/revwalk.h"
 #include "git2/merge.h"
 
 #include <regex.h>
 
+GIT_KHASH_OID__IMPLEMENTATION;
+
 #define PARENT1  (1 << 0)
 #define PARENT2  (1 << 1)
 #define RESULT   (1 << 2)
@@ -46,7 +48,7 @@ struct git_revwalk {
 	git_repository *repo;
 	git_odb *odb;
 
-	git_hashtable *commits;
+	git_khash_oid *commits;
 	git_pool commit_pool;
 
 	commit_list *iterator_topo;
@@ -123,15 +125,6 @@ static commit_object *commit_list_pop(commit_list **stack)
 	return item;
 }
 
-static uint32_t object_table_hash(const void *key, int hash_id)
-{
-	uint32_t r;
-	const git_oid *id = key;
-
-	memcpy(&r, id->id + (hash_id * sizeof(uint32_t)), sizeof(r));
-	return r;
-}
-
 #define PARENTS_PER_COMMIT	2
 #define COMMIT_ALLOC \
 	(sizeof(commit_object) + PARENTS_PER_COMMIT * sizeof(commit_object *))
@@ -155,9 +148,13 @@ static commit_object **alloc_parents(
 static commit_object *commit_lookup(git_revwalk *walk, const git_oid *oid)
 {
 	commit_object *commit;
+	khiter_t pos;
+	int ret;
 
-	if ((commit = git_hashtable_lookup(walk->commits, oid)) != NULL)
-		return commit;
+	/* lookup and reserve space if not already present */
+	pos = kh_get(oid, walk->commits, oid);
+	if (pos != kh_end(walk->commits))
+		return kh_value(walk->commits, pos);
 
 	commit = alloc_commit(walk);
 	if (commit == NULL)
@@ -165,8 +162,9 @@ static commit_object *commit_lookup(git_revwalk *walk, const git_oid *oid)
 
 	git_oid_cpy(&commit->oid, oid);
 
-	if (git_hashtable_insert(walk->commits, &commit->oid, commit) < 0)
-		return NULL;
+	pos = kh_put(oid, walk->commits, &commit->oid, &ret);
+	assert(ret != 0);
+	kh_value(walk->commits, pos) = commit;
 
 	return commit;
 }
@@ -728,9 +726,7 @@ int git_revwalk_new(git_revwalk **revwalk_out, git_repository *repo)
 
 	memset(walk, 0x0, sizeof(git_revwalk));
 
-	walk->commits = git_hashtable_alloc(64,
-			object_table_hash,
-			(git_hash_keyeq_ptr)git_oid_cmp);
+	walk->commits = git_khash_oid_alloc();
 	GITERR_CHECK_ALLOC(walk->commits);
 
 	if (git_pqueue_init(&walk->iterator_time, 8, commit_time_cmp) < 0 ||
@@ -761,7 +757,7 @@ void git_revwalk_free(git_revwalk *walk)
 	git_revwalk_reset(walk);
 	git_odb_free(walk->odb);
 
-	git_hashtable_free(walk->commits);
+	git_khash_oid_free(walk->commits);
 	git_pool_clear(&walk->commit_pool);
 	git_pqueue_free(&walk->iterator_time);
 	git_vector_free(&walk->twos);
@@ -823,12 +819,12 @@ void git_revwalk_reset(git_revwalk *walk)
 
 	assert(walk);
 
-	GIT_HASHTABLE_FOREACH_VALUE(walk->commits, commit,
+	kh_foreach_value(walk->commits, commit, {
 		commit->seen = 0;
 		commit->in_degree = 0;
 		commit->topo_delay = 0;
 		commit->uninteresting = 0;
-	);
+		});
 
 	git_pqueue_clear(&walk->iterator_time);
 	commit_list_free(&walk->iterator_topo);
diff --git a/src/submodule.c b/src/submodule.c
index 907e43e88..8072053af 100644
--- a/src/submodule.c
+++ b/src/submodule.c
@@ -12,7 +12,6 @@
 #include "git2/index.h"
 #include "git2/submodule.h"
 #include "buffer.h"
-#include "hashtable.h"
 #include "vector.h"
 #include "posix.h"
 #include "config_file.h"
@@ -32,41 +31,32 @@ static git_cvar_map _sm_ignore_map[] = {
 	{GIT_CVAR_STRING, "none", GIT_SUBMODULE_IGNORE_NONE}
 };
 
-static uint32_t strhash_no_trailing_slash(const void *key, int hash_id)
+static inline khint_t str_hash_no_trailing_slash(const char *s)
 {
-	static uint32_t hash_seeds[GIT_HASHTABLE_HASHES] = {
-		0x01010101,
-		0x12345678,
-		0xFEDCBA98
-	};
+	khint_t h;
 
-	size_t key_len = key ? strlen((const char *)key) : 0;
-	if (key_len > 0 && ((const char *)key)[key_len - 1] == '/')
-		key_len--;
+	for (h = 0; *s; ++s)
+		if (s[1] || *s != '/')
+			h = (h << 5) - h + *s;
 
-	return git__hash(key, (int)key_len, hash_seeds[hash_id]);
+	return h;
 }
 
-static int strcmp_no_trailing_slash(const void *a, const void *b)
+static inline int str_equal_no_trailing_slash(const char *a, const char *b)
 {
-	const char *astr = (const char *)a;
-	const char *bstr = (const char *)b;
-	size_t alen = a ? strlen(astr) : 0;
-	size_t blen = b ? strlen(bstr) : 0;
-	int cmp;
+	size_t alen = a ? strlen(a) : 0;
+	size_t blen = b ? strlen(b) : 0;
 
-	if (alen > 0 && astr[alen - 1] == '/')
+	if (alen && a[alen] == '/')
 		alen--;
-	if (blen > 0 && bstr[blen - 1] == '/')
+	if (blen && b[blen] == '/')
 		blen--;
 
-	cmp = strncmp(astr, bstr, min(alen, blen));
-	if (cmp == 0)
-		cmp = (alen < blen) ? -1 : (alen > blen) ? 1 : 0;
-
-	return cmp;
+	return (alen == blen && strncmp(a, b, alen) == 0);
 }
 
+__KHASH_IMPL(str, static inline, const char *, void *, 1, str_hash_no_trailing_slash, str_equal_no_trailing_slash);
+
 static git_submodule *submodule_alloc(const char *name)
 {
 	git_submodule *sm = git__calloc(1, sizeof(git_submodule));
@@ -99,13 +89,18 @@ static void submodule_release(git_submodule *sm, int decr)
 }
 
 static int submodule_from_entry(
-	git_hashtable *smcfg, git_index_entry *entry)
+	git_khash_str *smcfg, git_index_entry *entry)
 {
 	git_submodule *sm;
 	void *old_sm;
+	khiter_t pos;
+	int error;
 
-	sm = git_hashtable_lookup(smcfg, entry->path);
-	if (!sm)
+	pos = git_khash_str_lookup_index(smcfg, entry->path);
+
+	if (git_khash_str_valid_index(smcfg, pos))
+		sm = git_khash_str_value_at(smcfg, pos);
+	else
 		sm = submodule_alloc(entry->path);
 
 	git_oid_cpy(&sm->oid, &entry->oid);
@@ -120,7 +115,8 @@ static int submodule_from_entry(
 			goto fail;
 	}
 
-	if (git_hashtable_insert2(smcfg, sm->path, sm, &old_sm) < 0)
+	git_khash_str_insert2(smcfg, sm->path, sm, old_sm, error);
+	if (error < 0)
 		goto fail;
 	sm->refcount++;
 
@@ -139,13 +135,15 @@ fail:
 static int submodule_from_config(
 	const char *key, const char *value, void *data)
 {
-	git_hashtable *smcfg = data;
+	git_khash_str *smcfg = data;
 	const char *namestart;
 	const char *property;
 	git_buf name = GIT_BUF_INIT;
 	git_submodule *sm;
 	void *old_sm = NULL;
 	bool is_path;
+	khiter_t pos;
+	int error;
 
 	if (git__prefixcmp(key, "submodule.") != 0)
 		return 0;
@@ -160,32 +158,40 @@ static int submodule_from_config(
 	if (git_buf_set(&name, namestart, property - namestart - 1) < 0)
 		return -1;
 
-	sm = git_hashtable_lookup(smcfg, name.ptr);
-	if (!sm && is_path)
-		sm = git_hashtable_lookup(smcfg, value);
-	if (!sm)
+	pos = git_khash_str_lookup_index(smcfg, name.ptr);
+	if (!git_khash_str_valid_index(smcfg, pos) && is_path)
+		pos = git_khash_str_lookup_index(smcfg, value);
+	if (!git_khash_str_valid_index(smcfg, pos))
 		sm = submodule_alloc(name.ptr);
+	else
+		sm = git_khash_str_value_at(smcfg, pos);
 	if (!sm)
 		goto fail;
 
 	if (strcmp(sm->name, name.ptr) != 0) {
 		assert(sm->path == sm->name);
 		sm->name = git_buf_detach(&name);
-		if (git_hashtable_insert2(smcfg, sm->name, sm, &old_sm) < 0)
+
+		git_khash_str_insert2(smcfg, sm->name, sm, old_sm, error);
+		if (error < 0)
 			goto fail;
 		sm->refcount++;
 	}
 	else if (is_path && strcmp(sm->path, value) != 0) {
 		assert(sm->path == sm->name);
-		if ((sm->path = git__strdup(value)) == NULL ||
-			git_hashtable_insert2(smcfg, sm->path, sm, &old_sm) < 0)
+		sm->path = git__strdup(value);
+		if (sm->path == NULL)
+			goto fail;
+
+		git_khash_str_insert2(smcfg, sm->path, sm, old_sm, error);
+		if (error < 0)
 			goto fail;
 		sm->refcount++;
 	}
 	git_buf_free(&name);
 
 	if (old_sm && ((git_submodule *)old_sm) != sm) {
-		/* TODO: log entry about multiple submodules with same path */
+		/* TODO: log warning about multiple submodules with same path */
 		submodule_release(old_sm, 1);
 	}
 
@@ -241,7 +247,7 @@ static int load_submodule_config(git_repository *repo)
 	git_index *index;
 	unsigned int i, max_i;
 	git_oid gitmodules_oid;
-	git_hashtable *smcfg;
+	git_khash_str *smcfg;
 	struct git_config_file *mods = NULL;
 
 	if (repo->submodules)
@@ -251,8 +257,7 @@ static int load_submodule_config(git_repository *repo)
 	 * under both its name and its path.  These are usually the same, but
 	 * that is not guaranteed.
 	 */
-	smcfg = git_hashtable_alloc(
-		4, strhash_no_trailing_slash, strcmp_no_trailing_slash);
+	smcfg = git_khash_str_alloc();
 	GITERR_CHECK_ALLOC(smcfg);
 
 	/* scan index for gitmodules (and .gitmodules entry) */
@@ -302,13 +307,13 @@ cleanup:
 	if (mods != NULL)
 		git_config_file_free(mods);
 	if (error)
-		git_hashtable_free(smcfg);
+		git_khash_str_free(smcfg);
 	return error;
 }
 
 void git_submodule_config_free(git_repository *repo)
 {
-	git_hashtable *smcfg = repo->submodules;
+	git_khash_str *smcfg = repo->submodules;
 	git_submodule *sm;
 
 	repo->submodules = NULL;
@@ -316,8 +321,10 @@ void git_submodule_config_free(git_repository *repo)
 	if (smcfg == NULL)
 		return;
 
-	GIT_HASHTABLE_FOREACH_VALUE(smcfg, sm, { submodule_release(sm,1); });
-	git_hashtable_free(smcfg);
+	git_khash_str_foreach_value(smcfg, sm, {
+		submodule_release(sm,1);
+	});
+	git_khash_str_free(smcfg);
 }
 
 static int submodule_cmp(const void *a, const void *b)
@@ -338,19 +345,18 @@ int git_submodule_foreach(
 	if ((error = load_submodule_config(repo)) < 0)
 		return error;
 
-	GIT_HASHTABLE_FOREACH_VALUE(
-		repo->submodules, sm, {
-			/* usually the following will not come into play */
-			if (sm->refcount > 1) {
-				if (git_vector_bsearch(&seen, sm) != GIT_ENOTFOUND)
-					continue;
-				if ((error = git_vector_insert(&seen, sm)) < 0)
-					break;
-			}
-
-			if ((error = callback(sm->name, payload)) < 0)
+	git_khash_str_foreach_value(repo->submodules, sm, {
+		/* usually the following will not come into play */
+		if (sm->refcount > 1) {
+			if (git_vector_bsearch(&seen, sm) != GIT_ENOTFOUND)
+				continue;
+			if ((error = git_vector_insert(&seen, sm)) < 0)
 				break;
-		});
+		}
+
+		if ((error = callback(sm->name, payload)) < 0)
+			break;
+	});
 
 	git_vector_free(&seen);
 
@@ -362,15 +368,17 @@ int git_submodule_lookup(
 	git_repository *repo,
 	const char *name)       /* trailing slash is allowed */
 {
-	git_submodule *sm;
+	khiter_t pos;
 
 	if (load_submodule_config(repo) < 0)
 		return -1;
 
-	sm = git_hashtable_lookup(repo->submodules, name);
+	pos = git_khash_str_lookup_index(repo->submodules, name);
+	if (!git_khash_str_valid_index(repo->submodules, pos))
+		return GIT_ENOTFOUND;
 
 	if (sm_ptr)
-		*sm_ptr = sm;
+		*sm_ptr = git_khash_str_value_at(repo->submodules, pos);
 
-	return sm ? 0 : GIT_ENOTFOUND;
+	return 0;
 }