thodg/libgit2

diff --git a/src/apply.c b/src/apply.c
index 0becf94..156221f 100644
--- a/src/apply.c
+++ b/src/apply.c
@@ -439,7 +439,6 @@ static int apply_one(
 	git_filemode_t pre_filemode;
 	git_index_entry pre_entry, post_entry;
 	bool skip_preimage = false;
-	size_t pos;
 	int error;
 
 	if ((error = git_patch_from_diff(&patch, diff, i)) < 0)
@@ -464,8 +463,7 @@ static int apply_one(
 	 */
 	if (delta->status != GIT_DELTA_RENAMED &&
 	    delta->status != GIT_DELTA_ADDED) {
-		pos = git_strmap_lookup_index(removed_paths, delta->old_file.path);
-		if (git_strmap_valid_index(removed_paths, pos)) {
+		if (git_strmap_exists(removed_paths, delta->old_file.path)) {
 			error = apply_err("path '%s' has been renamed or deleted", delta->old_file.path);
 			goto done;
 		}
@@ -549,7 +547,7 @@ static int apply_one(
 
 	if (delta->status == GIT_DELTA_RENAMED ||
 	    delta->status == GIT_DELTA_DELETED)
-		git_strmap_insert(removed_paths, delta->old_file.path, (char *)delta->old_file.path, &error);
+		error = git_strmap_set(removed_paths, delta->old_file.path, (char *) delta->old_file.path);
 
 	if (delta->status == GIT_DELTA_RENAMED ||
 	    delta->status == GIT_DELTA_ADDED)
@@ -577,7 +575,7 @@ static int apply_deltas(
 	size_t i;
 	int error = 0;
 
-	if (git_strmap_alloc(&removed_paths) < 0)
+	if (git_strmap_new(&removed_paths) < 0)
 		return -1;
 
 	for (i = 0; i < git_diff_num_deltas(diff); i++) {
diff --git a/src/attr.c b/src/attr.c
index 1f26433..c6867e1 100644
--- a/src/attr.c
+++ b/src/attr.c
@@ -215,7 +215,7 @@ int git_attr_foreach(
 		return -1;
 
 	if ((error = collect_attr_files(repo, NULL, flags, pathname, &files)) < 0 ||
-		(error = git_strmap_alloc(&seen)) < 0)
+	    (error = git_strmap_new(&seen)) < 0)
 		goto cleanup;
 
 	git_vector_foreach(&files, i, file) {
@@ -227,8 +227,7 @@ int git_attr_foreach(
 				if (git_strmap_exists(seen, assign->name))
 					continue;
 
-				git_strmap_insert(seen, assign->name, assign, &error);
-				if (error < 0)
+				if ((error = git_strmap_set(seen, assign->name, assign)) < 0)
 					goto cleanup;
 
 				error = callback(assign->name, assign->value, payload);
diff --git a/src/attrcache.c b/src/attrcache.c
index cb8a4a4..00e4596 100644
--- a/src/attrcache.c
+++ b/src/attrcache.c
@@ -33,12 +33,7 @@ GIT_INLINE(void) attr_cache_unlock(git_attr_cache *cache)
 GIT_INLINE(git_attr_file_entry *) attr_cache_lookup_entry(
 	git_attr_cache *cache, const char *path)
 {
-	size_t pos = git_strmap_lookup_index(cache->files, path);
-
-	if (git_strmap_valid_index(cache->files, pos))
-		return git_strmap_value_at(cache->files, pos);
-	else
-		return NULL;
+	return git_strmap_get(cache->files, path);
 }
 
 int git_attr_cache__alloc_file_entry(
@@ -80,18 +75,16 @@ int git_attr_cache__alloc_file_entry(
 static int attr_cache_make_entry(
 	git_attr_file_entry **out, git_repository *repo, const char *path)
 {
-	int error = 0;
 	git_attr_cache *cache = git_repository_attr_cache(repo);
 	git_attr_file_entry *entry = NULL;
+	int error;
 
-	error = git_attr_cache__alloc_file_entry(
-		&entry, git_repository_workdir(repo), path, &cache->pool);
+	if ((error = git_attr_cache__alloc_file_entry(&entry, git_repository_workdir(repo),
+						      path, &cache->pool)) < 0)
+		return error;
 
-	if (!error) {
-		git_strmap_insert(cache->files, entry->path, entry, &error);
-		if (error > 0)
-			error = 0;
-	}
+	if ((error = git_strmap_set(cache->files, entry->path, entry)) < 0)
+		return error;
 
 	*out = entry;
 	return error;
@@ -265,19 +258,15 @@ bool git_attr_cache__is_cached(
 	const char *filename)
 {
 	git_attr_cache *cache = git_repository_attr_cache(repo);
-	git_strmap *files;
-	size_t pos;
 	git_attr_file_entry *entry;
+	git_strmap *files;
 
 	if (!cache || !(files = cache->files))
 		return false;
 
-	pos = git_strmap_lookup_index(files, filename);
-	if (!git_strmap_valid_index(files, pos))
+	if ((entry = git_strmap_get(files, filename)) == NULL)
 		return false;
 
-	entry = git_strmap_value_at(files, pos);
-
 	return entry && (entry->file[source] != NULL);
 }
 
@@ -400,8 +389,8 @@ int git_attr_cache__init(git_repository *repo)
 	/* allocate hashtable for attribute and ignore file contents,
 	 * hashtable for attribute macros, and string pool
 	 */
-	if ((ret = git_strmap_alloc(&cache->files)) < 0 ||
-		(ret = git_strmap_alloc(&cache->macros)) < 0)
+	if ((ret = git_strmap_new(&cache->files)) < 0 ||
+	    (ret = git_strmap_new(&cache->macros)) < 0)
 		goto cancel;
 
 	git_pool_init(&cache->pool, 1);
@@ -446,24 +435,17 @@ int git_attr_cache__insert_macro(git_repository *repo, git_attr_rule *macro)
 		git_error_set(GIT_ERROR_OS, "unable to get attr cache lock");
 		error = -1;
 	} else {
-		git_strmap_insert(macros, macro->match.pattern, macro, &error);
+		error = git_strmap_set(macros, macro->match.pattern, macro);
 		git_mutex_unlock(&cache->lock);
 	}
 
-	return (error < 0) ? -1 : 0;
+	return error;
 }
 
 git_attr_rule *git_attr_cache__lookup_macro(
 	git_repository *repo, const char *name)
 {
 	git_strmap *macros = git_repository_attr_cache(repo)->macros;
-	size_t pos;
 
-	pos = git_strmap_lookup_index(macros, name);
-
-	if (!git_strmap_valid_index(macros, pos))
-		return NULL;
-
-	return (git_attr_rule *)git_strmap_value_at(macros, pos);
+	return git_strmap_get(macros, name);
 }
-
diff --git a/src/cache.c b/src/cache.c
index 4af2321..2f5c8f9 100644
--- a/src/cache.c
+++ b/src/cache.c
@@ -65,12 +65,15 @@ void git_cache_dump_stats(git_cache *cache)
 int git_cache_init(git_cache *cache)
 {
 	memset(cache, 0, sizeof(*cache));
-	cache->map = git_oidmap_alloc();
-	GIT_ERROR_CHECK_ALLOC(cache->map);
+
+	if ((git_oidmap_new(&cache->map)) < 0)
+		return -1;
+
 	if (git_rwlock_init(&cache->lock)) {
 		git_error_set(GIT_ERROR_OS, "failed to initialize cache rwlock");
 		return -1;
 	}
+
 	return 0;
 }
 
@@ -112,8 +115,7 @@ void git_cache_dispose(git_cache *cache)
 /* Called with lock */
 static void cache_evict_entries(git_cache *cache)
 {
-	uint32_t seed = rand();
-	size_t evict_count = 8;
+	size_t evict_count = 8, i;
 	ssize_t evicted_memory = 0;
 
 	/* do not infinite loop if there's not enough entries to evict  */
@@ -122,18 +124,19 @@ static void cache_evict_entries(git_cache *cache)
 		return;
 	}
 
+	i = 0;
 	while (evict_count > 0) {
-		size_t pos = seed++ % git_oidmap_end(cache->map);
+		git_cached_obj *evict;
+		const git_oid *key;
 
-		if (git_oidmap_has_data(cache->map, pos)) {
-			git_cached_obj *evict = git_oidmap_value_at(cache->map, pos);
+		if (git_oidmap_iterate((void **) &evict, cache->map, &i, &key) == GIT_ITEROVER)
+			break;
 
-			evict_count--;
-			evicted_memory += evict->size;
-			git_cached_obj_decref(evict);
+		evict_count--;
+		evicted_memory += evict->size;
+		git_cached_obj_decref(evict);
 
-			git_oidmap_delete_at(cache->map, pos);
-		}
+		git_oidmap_delete(cache->map, key);
 	}
 
 	cache->used_memory -= evicted_memory;
@@ -148,16 +151,12 @@ static bool cache_should_store(git_object_t object_type, size_t object_size)
 
 static void *cache_get(git_cache *cache, const git_oid *oid, unsigned int flags)
 {
-	size_t pos;
-	git_cached_obj *entry = NULL;
+	git_cached_obj *entry;
 
 	if (!git_cache__enabled || git_rwlock_rdlock(&cache->lock) < 0)
 		return NULL;
 
-	pos = git_oidmap_lookup_index(cache->map, oid);
-	if (git_oidmap_valid_index(cache->map, pos)) {
-		entry = git_oidmap_value_at(cache->map, pos);
-
+	if ((entry = git_oidmap_get(cache->map, oid)) != NULL) {
 		if (flags && entry->flags != flags) {
 			entry = NULL;
 		} else {
@@ -172,7 +171,7 @@ static void *cache_get(git_cache *cache, const git_oid *oid, unsigned int flags)
 
 static void *cache_store(git_cache *cache, git_cached_obj *entry)
 {
-	size_t pos;
+	git_cached_obj *stored_entry;
 
 	git_cached_obj_incref(entry);
 
@@ -191,14 +190,9 @@ static void *cache_store(git_cache *cache, git_cached_obj *entry)
 	if (git_cache__current_storage.val > git_cache__max_storage)
 		cache_evict_entries(cache);
 
-	pos = git_oidmap_lookup_index(cache->map, &entry->oid);
-
 	/* not found */
-	if (!git_oidmap_valid_index(cache->map, pos)) {
-		int rval;
-
-		git_oidmap_insert(cache->map, &entry->oid, entry, &rval);
-		if (rval >= 0) {
+	if ((stored_entry = git_oidmap_get(cache->map, &entry->oid)) == NULL) {
+		if (git_oidmap_set(cache->map, &entry->oid, entry) == 0) {
 			git_cached_obj_incref(entry);
 			cache->used_memory += entry->size;
 			git_atomic_ssize_add(&git_cache__current_storage, (ssize_t)entry->size);
@@ -206,19 +200,16 @@ static void *cache_store(git_cache *cache, git_cached_obj *entry)
 	}
 	/* found */
 	else {
-		git_cached_obj *stored_entry = git_oidmap_value_at(cache->map, pos);
-
 		if (stored_entry->flags == entry->flags) {
 			git_cached_obj_decref(entry);
 			git_cached_obj_incref(stored_entry);
 			entry = stored_entry;
 		} else if (stored_entry->flags == GIT_CACHE_STORE_RAW &&
-			entry->flags == GIT_CACHE_STORE_PARSED) {
+			   entry->flags == GIT_CACHE_STORE_PARSED) {
 			git_cached_obj_decref(stored_entry);
 			git_cached_obj_incref(entry);
 
-			git_oidmap_set_key_at(cache->map, pos, &entry->oid);
-			git_oidmap_set_value_at(cache->map, pos, entry);
+			git_oidmap_set(cache->map, &entry->oid, entry);
 		} else {
 			/* NO OP */
 		}
diff --git a/src/checkout.c b/src/checkout.c
index fe02089..35862bd 100644
--- a/src/checkout.c
+++ b/src/checkout.c
@@ -2518,11 +2518,11 @@ static int checkout_data_init(
 	git_pool_init(&data->pool, 1);
 
 	if ((error = git_vector_init(&data->removes, 0, git__strcmp_cb)) < 0 ||
-		(error = git_vector_init(&data->remove_conflicts, 0, NULL)) < 0 ||
-		(error = git_vector_init(&data->update_conflicts, 0, NULL)) < 0 ||
-		(error = git_buf_puts(&data->target_path, data->opts.target_directory)) < 0 ||
-		(error = git_path_to_dir(&data->target_path)) < 0 ||
-		(error = git_strmap_alloc(&data->mkdir_map)) < 0)
+	    (error = git_vector_init(&data->remove_conflicts, 0, NULL)) < 0 ||
+	    (error = git_vector_init(&data->update_conflicts, 0, NULL)) < 0 ||
+	    (error = git_buf_puts(&data->target_path, data->opts.target_directory)) < 0 ||
+	    (error = git_path_to_dir(&data->target_path)) < 0 ||
+	    (error = git_strmap_new(&data->mkdir_map)) < 0)
 		goto cleanup;
 
 	data->target_len = git_buf_len(&data->target_path);
diff --git a/src/config_entries.c b/src/config_entries.c
index f6277bc..18f8b21 100644
--- a/src/config_entries.c
+++ b/src/config_entries.c
@@ -59,7 +59,7 @@ int git_config_entries_new(git_config_entries **out)
 	GIT_ERROR_CHECK_ALLOC(entries);
 	GIT_REFCOUNT_INC(entries);
 
-	if ((error = git_strmap_alloc(&entries->map)) < 0)
+	if ((error = git_strmap_new(&entries->map)) < 0)
 		git__free(entries);
 	else
 		*out = entries;
@@ -133,14 +133,12 @@ int git_config_entries_append(git_config_entries *entries, git_config_entry *ent
 {
 	config_entry_list *existing, *var;
 	int error = 0;
-	size_t pos;
 
 	var = git__calloc(1, sizeof(config_entry_list));
 	GIT_ERROR_CHECK_ALLOC(var);
 	var->entry = entry;
 
-	pos = git_strmap_lookup_index(entries->map, entry->name);
-	if (!git_strmap_valid_index(entries->map, pos)) {
+	if ((existing = git_strmap_get(entries->map, entry->name)) == NULL) {
 		/*
 		 * We only ever inspect `last` from the first config
 		 * entry in a multivar. In case where this new entry is
@@ -152,12 +150,8 @@ int git_config_entries_append(git_config_entries *entries, git_config_entry *ent
 		 */
 		var->last = var;
 
-		git_strmap_insert(entries->map, entry->name, var, &error);
-
-		if (error > 0)
-			error = 0;
+		error = git_strmap_set(entries->map, entry->name, var);
 	} else {
-		existing = git_strmap_value_at(entries->map, pos);
 		config_entry_list_append(&existing, var);
 	}
 
@@ -171,15 +165,12 @@ int git_config_entries_append(git_config_entries *entries, git_config_entry *ent
 
 int config_entry_get(config_entry_list **out, git_config_entries *entries, const char *key)
 {
-	size_t pos;
-
-	pos = git_strmap_lookup_index(entries->map, key);
+	config_entry_list *list;
 
-	/* no error message; the config system will write one */
-	if (!git_strmap_valid_index(entries->map, pos))
+	if ((list = git_strmap_get(entries->map, key)) == NULL)
 		return GIT_ENOTFOUND;
 
-	*out = git_strmap_value_at(entries->map, pos);
+	*out = list;
 
 	return 0;
 }
diff --git a/src/describe.c b/src/describe.c
index 893ca64..943fa55 100644
--- a/src/describe.c
+++ b/src/describe.c
@@ -36,12 +36,7 @@ struct commit_name {
 
 static void *oidmap_value_bykey(git_oidmap *map, const git_oid *key)
 {
-	size_t pos = git_oidmap_lookup_index(map, key);
-
-	if (!git_oidmap_valid_index(map, pos))
-		return NULL;
-
-	return git_oidmap_value_at(map, pos);
+	return git_oidmap_get(map, key);
 }
 
 static struct commit_name *find_commit_name(
@@ -124,13 +119,8 @@ static int add_to_known_names(
 		e->path = git__strdup(path);
 		git_oid_cpy(&e->peeled, peeled);
 
-		if (!found) {
-			int ret;
-
-			git_oidmap_insert(names, &e->peeled, e, &ret);
-			if (ret < 0)
-				return -1;
-		}
+		if (!found && git_oidmap_set(names, &e->peeled, e) < 0)
+			return -1;
 	}
 	else
 		git_tag_free(tag);
@@ -681,8 +671,8 @@ int git_describe_commit(
 		"git_describe_options");
 	data.opts = &normalized;
 
-	data.names = git_oidmap_alloc();
-	GIT_ERROR_CHECK_ALLOC(data.names);
+	if ((error = git_oidmap_new(&data.names)) < 0)
+		return error;
 
 	/** TODO: contains to be implemented */
 
diff --git a/src/diff_driver.c b/src/diff_driver.c
index 05246df..959cf62 100644
--- a/src/diff_driver.c
+++ b/src/diff_driver.c
@@ -63,7 +63,7 @@ git_diff_driver_registry *git_diff_driver_registry_new(void)
 	if (!reg)
 		return NULL;
 
-	if (git_strmap_alloc(&reg->drivers) < 0) {
+	if (git_strmap_new(&reg->drivers) < 0) {
 		git_diff_driver_registry_free(reg);
 		return NULL;
 	}
@@ -183,9 +183,9 @@ static int git_diff_driver_builtin(
 	git_diff_driver_registry *reg,
 	const char *driver_name)
 {
-	int error = 0;
 	git_diff_driver_definition *ddef = NULL;
 	git_diff_driver *drv = NULL;
+	int error = 0;
 	size_t idx;
 
 	for (idx = 0; idx < ARRAY_SIZE(builtin_defs); ++idx) {
@@ -215,9 +215,8 @@ static int git_diff_driver_builtin(
 		goto done;
 	}
 
-	git_strmap_insert(reg->drivers, drv->name, drv, &error);
-	if (error > 0)
-		error = 0;
+	if ((error = git_strmap_set(reg->drivers, drv->name, drv)) < 0)
+		goto done;
 
 done:
 	if (error && drv)
@@ -233,8 +232,8 @@ static int git_diff_driver_load(
 {
 	int error = 0;
 	git_diff_driver_registry *reg;
-	git_diff_driver *drv = NULL;
-	size_t namelen, pos;
+	git_diff_driver *drv;
+	size_t namelen;
 	git_config *cfg = NULL;
 	git_buf name = GIT_BUF_INIT;
 	git_config_entry *ce = NULL;
@@ -243,9 +242,8 @@ static int git_diff_driver_load(
 	if ((reg = git_repository_driver_registry(repo)) == NULL)
 		return -1;
 
-	pos = git_strmap_lookup_index(reg->drivers, driver_name);
-	if (git_strmap_valid_index(reg->drivers, pos)) {
-		*out = git_strmap_value_at(reg->drivers, pos);
+	if ((drv = git_strmap_get(reg->drivers, driver_name)) != NULL) {
+		*out = drv;
 		return 0;
 	}
 
@@ -328,10 +326,8 @@ static int git_diff_driver_load(
 		goto done;
 
 	/* store driver in registry */
-	git_strmap_insert(reg->drivers, drv->name, drv, &error);
-	if (error < 0)
+	if ((error = git_strmap_set(reg->drivers, drv->name, drv)) < 0)
 		goto done;
-	error = 0;
 
 	*out = drv;
 
diff --git a/src/fileops.c b/src/fileops.c
index 988ea0f..61906ed 100644
--- a/src/fileops.c
+++ b/src/fileops.c
@@ -640,8 +640,7 @@ retry_lstat:
 
 			memcpy(cache_path, make_path.ptr, make_path.size + 1);
 
-			git_strmap_insert(opts->dir_map, cache_path, cache_path, &error);
-			if (error < 0)
+			if ((error = git_strmap_set(opts->dir_map, cache_path, cache_path)) < 0)
 				goto done;
 		}
 	}
diff --git a/src/idxmap.c b/src/idxmap.c
index 3a5fc10..e75887c 100644
--- a/src/idxmap.c
+++ b/src/idxmap.c
@@ -32,122 +32,146 @@ static kh_inline khint_t idxentry_hash(const git_index_entry *e)
 __KHASH_IMPL(idx, static kh_inline, const git_index_entry *, git_index_entry *, 1, idxentry_hash, idxentry_equal)
 __KHASH_IMPL(idxicase, static kh_inline, const git_index_entry *, git_index_entry *, 1, idxentry_hash, idxentry_icase_equal)
 
-int git_idxmap_alloc(git_idxmap **map)
+int git_idxmap_new(git_idxmap **out)
 {
-	if ((*map = kh_init(idx)) == NULL) {
-		git_error_set_oom();
-		return -1;
-	}
+	*out = kh_init(idx);
+	GIT_ERROR_CHECK_ALLOC(*out);
 
 	return 0;
 }
 
-int git_idxmap_icase_alloc(git_idxmap_icase **map)
+int git_idxmap_icase_new(git_idxmap_icase **out)
 {
-	if ((*map = kh_init(idxicase)) == NULL) {
-		git_error_set_oom();
-		return -1;
-	}
+	*out = kh_init(idxicase);
+	GIT_ERROR_CHECK_ALLOC(*out);
 
 	return 0;
 }
 
-void git_idxmap_insert(git_idxmap *map, const git_index_entry *key, void *value, int *rval)
+void git_idxmap_free(git_idxmap *map)
 {
-	khiter_t idx = kh_put(idx, map, key, rval);
-
-	if ((*rval) >= 0) {
-		if ((*rval) == 0)
-			kh_key(map, idx) = key;
-		kh_val(map, idx) = value;
-	}
+	kh_destroy(idx, map);
 }
 
-void git_idxmap_icase_insert(git_idxmap_icase *map, const git_index_entry *key, void *value, int *rval)
+void git_idxmap_icase_free(git_idxmap_icase *map)
 {
-	khiter_t idx = kh_put(idxicase, map, key, rval);
-
-	if ((*rval) >= 0) {
-		if ((*rval) == 0)
-			kh_key(map, idx) = key;
-		kh_val(map, idx) = value;
-	}
+	kh_destroy(idxicase, map);
 }
 
-size_t git_idxmap_lookup_index(git_idxmap *map, const git_index_entry *key)
+void git_idxmap_clear(git_idxmap *map)
 {
-	return kh_get(idx, map, key);
+	kh_clear(idx, map);
 }
 
-size_t git_idxmap_icase_lookup_index(git_idxmap_icase *map, const git_index_entry *key)
+void git_idxmap_icase_clear(git_idxmap_icase *map)
 {
-	return kh_get(idxicase, map, key);
+	kh_clear(idxicase, map);
 }
 
-void *git_idxmap_value_at(git_idxmap *map, size_t idx)
+int git_idxmap_resize(git_idxmap *map, size_t size)
 {
-	return kh_val(map, idx);
+	if (kh_resize(idx, map, size) < 0) {
+		git_error_set_oom();
+		return -1;
+	}
+	return 0;
 }
 
-int git_idxmap_valid_index(git_idxmap *map, size_t idx)
+int git_idxmap_icase_resize(git_idxmap_icase *map, size_t size)
 {
-	return idx != kh_end(map);
+	if (kh_resize(idxicase, map, size) < 0) {
+		git_error_set_oom();
+		return -1;
+	}
+	return 0;
 }
 
-int git_idxmap_has_data(git_idxmap *map, size_t idx)
+void *git_idxmap_get(git_idxmap *map, const git_index_entry *key)
 {
-	return kh_exist(map, idx);
+	size_t idx = kh_get(idx, map, key);
+	if (idx == kh_end(map) || !kh_exist(map, idx))
+		return NULL;
+	return kh_val(map, idx);
 }
 
-void git_idxmap_resize(git_idxmap *map, size_t size)
+int git_idxmap_set(git_idxmap *map, const git_index_entry *key, void *value)
 {
-	kh_resize(idx, map, size);
-}
+	size_t idx;
+	int rval;
 
-void git_idxmap_icase_resize(git_idxmap_icase *map, size_t size)
-{
-	kh_resize(idxicase, map, size);
+	idx = kh_put(idx, map, key, &rval);
+	if (rval < 0)
+		return -1;
+
+	if (rval == 0)
+		kh_key(map, idx) = key;
+
+	kh_val(map, idx) = value;
+
+	return 0;
 }
 
-void git_idxmap_free(git_idxmap *map)
+int git_idxmap_icase_set(git_idxmap_icase *map, const git_index_entry *key, void *value)
 {
-	kh_destroy(idx, map);
+	size_t idx;
+	int rval;
+
+	idx = kh_put(idxicase, map, key, &rval);
+	if (rval < 0)
+		return -1;
+
+	if (rval == 0)
+		kh_key(map, idx) = key;
+
+	kh_val(map, idx) = value;
+
+	return 0;
 }
 
-void git_idxmap_icase_free(git_idxmap_icase *map)
+void *git_idxmap_icase_get(git_idxmap_icase *map, const git_index_entry *key)
 {
-	kh_destroy(idxicase, map);
+	size_t idx = kh_get(idxicase, map, key);
+	if (idx == kh_end(map) || !kh_exist(map, idx))
+		return NULL;
+	return kh_val(map, idx);
 }
 
-void git_idxmap_clear(git_idxmap *map)
+void git_idxmap_insert(git_idxmap *map, const git_index_entry *key, void *value, int *rval)
 {
-	kh_clear(idx, map);
+	khiter_t idx = kh_put(idx, map, key, rval);
+
+	if ((*rval) >= 0) {
+		if ((*rval) == 0)
+			kh_key(map, idx) = key;
+		kh_val(map, idx) = value;
+	}
 }
 
-void git_idxmap_icase_clear(git_idxmap_icase *map)
+void git_idxmap_icase_insert(git_idxmap_icase *map, const git_index_entry *key, void *value, int *rval)
 {
-	kh_clear(idxicase, map);
+	khiter_t idx = kh_put(idxicase, map, key, rval);
+
+	if ((*rval) >= 0) {
+		if ((*rval) == 0)
+			kh_key(map, idx) = key;
+		kh_val(map, idx) = value;
+	}
 }
 
-void git_idxmap_delete_at(git_idxmap *map, size_t idx)
+int git_idxmap_delete(git_idxmap *map, const git_index_entry *key)
 {
+	khiter_t idx = kh_get(idx, map, key);
+	if (idx == kh_end(map))
+		return GIT_ENOTFOUND;
 	kh_del(idx, map, idx);
+	return 0;
 }
 
-void git_idxmap_icase_delete_at(git_idxmap_icase *map, size_t idx)
+int git_idxmap_icase_delete(git_idxmap_icase *map, const git_index_entry *key)
 {
+	khiter_t idx = kh_get(idxicase, map, key);
+	if (idx == kh_end(map))
+		return GIT_ENOTFOUND;
 	kh_del(idxicase, map, idx);
-}
-
-void git_idxmap_delete(git_idxmap *map, const git_index_entry *key)
-{
-	khiter_t idx = git_idxmap_lookup_index(map, key);
-	if (git_idxmap_valid_index(map, idx))
-		git_idxmap_delete_at(map, idx);
-}
-void git_idxmap_icase_delete(git_idxmap_icase *map, const git_index_entry *key)
-{
-	khiter_t idx = git_idxmap_icase_lookup_index(map, key);
-	if (git_idxmap_valid_index((git_idxmap *)map, idx))
-		git_idxmap_icase_delete_at(map, idx);
+	return 0;
 }
diff --git a/src/idxmap.h b/src/idxmap.h
index 215a245..76170ef 100644
--- a/src/idxmap.h
+++ b/src/idxmap.h
@@ -11,31 +11,167 @@
 
 #include "git2/index.h"
 
+/** A map with `git_index_entry`s as key. */
 typedef struct kh_idx_s git_idxmap;
+/** A map with case-insensitive `git_index_entry`s as key */
 typedef struct kh_idxicase_s git_idxmap_icase;
 
-int git_idxmap_alloc(git_idxmap **map);
-int git_idxmap_icase_alloc(git_idxmap_icase **map);
-void git_idxmap_insert(git_idxmap *map, const git_index_entry *key, void *value, int *rval);
-void git_idxmap_icase_insert(git_idxmap_icase *map, const git_index_entry *key, void *value, int *rval);
+/**
+ * Allocate a new index entry map.
+ *
+ * @param out Pointer to the map that shall be allocated.
+ * @return 0 on success, an error code if allocation has failed.
+ */
+int git_idxmap_new(git_idxmap **out);
 
-size_t git_idxmap_lookup_index(git_idxmap *map, const git_index_entry *key);
-size_t git_idxmap_icase_lookup_index(git_idxmap_icase *map, const git_index_entry *key);
-void *git_idxmap_value_at(git_idxmap *map, size_t idx);
-int git_idxmap_valid_index(git_idxmap *map, size_t idx);
-int git_idxmap_has_data(git_idxmap *map, size_t idx);
+/**
+ * Allocate a new case-insensitive index entry map.
+ *
+ * @param out Pointer to the map that shall be allocated.
+ * @return 0 on success, an error code if allocation has failed.
+ */
+int git_idxmap_icase_new(git_idxmap_icase **out);
 
-void git_idxmap_resize(git_idxmap *map, size_t size);
-void git_idxmap_icase_resize(git_idxmap_icase *map, size_t size);
+/**
+ * Free memory associated with the map.
+ *
+ * Note that this function will _not_ free values added to this
+ * map.
+ *
+ * @param map Pointer to the map that is to be free'd. May be
+ *            `NULL`.
+ */
 void git_idxmap_free(git_idxmap *map);
+
+/**
+ * Free memory associated with the map.
+ *
+ * Note that this function will _not_ free values added to this
+ * map.
+ *
+ * @param map Pointer to the map that is to be free'd. May be
+ *            `NULL`.
+ */
 void git_idxmap_icase_free(git_idxmap_icase *map);
+
+/**
+ * Clear all entries from the map.
+ *
+ * This function will remove all entries from the associated map.
+ * Memory associated with it will not be released, though.
+ *
+ * @param map Pointer to the map that shall be cleared. May be
+ *            `NULL`.
+ */
 void git_idxmap_clear(git_idxmap *map);
+
+/**
+ * Clear all entries from the map.
+ *
+ * This function will remove all entries from the associated map.
+ * Memory associated with it will not be released, though.
+ *
+ * @param map Pointer to the map that shall be cleared. May be
+ *            `NULL`.
+ */
 void git_idxmap_icase_clear(git_idxmap_icase *map);
 
-void git_idxmap_delete_at(git_idxmap *map, size_t idx);
-void git_idxmap_icase_delete_at(git_idxmap_icase *map, size_t idx);
+/**
+ * Resize the map by allocating more memory.
+ *
+ * @param map map that shall be resized
+ * @param size count of entries that the map shall hold
+ * @return `0` if the map was successfully resized, a negative
+ *         error code otherwise
+ */
+int git_idxmap_resize(git_idxmap *map, size_t size);
 
-void git_idxmap_delete(git_idxmap *map, const git_index_entry *key);
-void git_idxmap_icase_delete(git_idxmap_icase *map, const git_index_entry *key);
+/**
+ * Resize the map by allocating more memory.
+ *
+ * @param map map that shall be resized
+ * @param size count of entries that the map shall hold
+ * @return `0` if the map was successfully resized, a negative
+ *         error code otherwise
+ */
+int git_idxmap_icase_resize(git_idxmap_icase *map, size_t size);
+
+/**
+ * Return value associated with the given key.
+ *
+ * @param map map to search key in
+ * @param key key to search for; the index entry will be searched
+ *            for by its case-sensitive path
+ * @return value associated with the given key or NULL if the key was not found
+ */
+void *git_idxmap_get(git_idxmap *map, const git_index_entry *key);
+
+/**
+ * Return value associated with the given key.
+ *
+ * @param map map to search key in
+ * @param key key to search for; the index entry will be searched
+ *            for by its case-insensitive path
+ * @return value associated with the given key or NULL if the key was not found
+ */
+void *git_idxmap_icase_get(git_idxmap_icase *map, const git_index_entry *key);
+
+/**
+ * Set the entry for key to value.
+ *
+ * If the map has no corresponding entry for the given key, a new
+ * entry will be created with the given value. If an entry exists
+ * already, its value will be updated to match the given value.
+ *
+ * @param map map to create new entry in
+ * @param key key to set
+ * @param value value to associate the key with; may be NULL
+ * @return zero if the key was successfully set, a negative error
+ *         code otherwise
+ */
+int git_idxmap_set(git_idxmap *map, const git_index_entry *key, void *value);
+
+/**
+ * Set the entry for key to value.
+ *
+ * If the map has no corresponding entry for the given key, a new
+ * entry will be created with the given value. If an entry exists
+ * already, its value will be updated to match the given value.
+ *
+ * @param map map to create new entry in
+ * @param key key to set
+ * @param value value to associate the key with; may be NULL
+ * @return zero if the key was successfully set, a negative error
+ *         code otherwise
+ */
+int git_idxmap_icase_set(git_idxmap_icase *map, const git_index_entry *key, void *value);
+
+/**
+ * Delete an entry from the map.
+ *
+ * Delete the given key and its value from the map. If no such
+ * key exists, this will do nothing.
+ *
+ * @param map map to delete key in
+ * @param key key to delete
+ * @return `0` if the key has been deleted, GIT_ENOTFOUND if no
+ *         such key was found, a negative code in case of an
+ *         error
+ */
+int git_idxmap_delete(git_idxmap *map, const git_index_entry *key);
+
+/**
+ * Delete an entry from the map.
+ *
+ * Delete the given key and its value from the map. If no such
+ * key exists, this will do nothing.
+ *
+ * @param map map to delete key in
+ * @param key key to delete
+ * @return `0` if the key has been deleted, GIT_ENOTFOUND if no
+ *         such key was found, a negative code in case of an
+ *         error
+ */
+int git_idxmap_icase_delete(git_idxmap_icase *map, const git_index_entry *key);
 
 #endif
diff --git a/src/index.c b/src/index.c
index 7f865c2..ee8dfd5 100644
--- a/src/index.c
+++ b/src/index.c
@@ -29,18 +29,18 @@
 
 #define INSERT_IN_MAP_EX(idx, map, e, err) do {				\
 		if ((idx)->ignore_case)					\
-			git_idxmap_icase_insert((git_idxmap_icase *) (map), (e), (e), (err)); \
+			(err) = git_idxmap_icase_set((git_idxmap_icase *) (map), (e), (e)); \
 		else							\
-			git_idxmap_insert((map), (e), (e), (err));	\
+			(err) = git_idxmap_set((map), (e), (e));	\
 	} while (0)
 
 #define INSERT_IN_MAP(idx, e, err) INSERT_IN_MAP_EX(idx, (idx)->entries_map, e, err)
 
-#define LOOKUP_IN_MAP(p, idx, k) do {					\
+#define LOOKUP_IN_MAP(v, idx, k) do {					\
 		if ((idx)->ignore_case)					\
-			(p) = git_idxmap_icase_lookup_index((git_idxmap_icase *) index->entries_map, (k)); \
+			(v) = git_idxmap_icase_get((git_idxmap_icase *) index->entries_map, (k)); \
 		else							\
-			(p) = git_idxmap_lookup_index(index->entries_map, (k)); \
+			(v) = git_idxmap_get(index->entries_map, (k)); \
 	} while (0)
 
 #define DELETE_IN_MAP(idx, e) do {					\
@@ -423,10 +423,10 @@ int git_index_open(git_index **index_out, const char *index_path)
 	}
 
 	if (git_vector_init(&index->entries, 32, git_index_entry_cmp) < 0 ||
-		git_idxmap_alloc(&index->entries_map) < 0 ||
-		git_vector_init(&index->names, 8, conflict_name_cmp) < 0 ||
-		git_vector_init(&index->reuc, 8, reuc_cmp) < 0 ||
-		git_vector_init(&index->deleted, 8, git_index_entry_cmp) < 0)
+	    git_idxmap_new(&index->entries_map) < 0 ||
+	    git_vector_init(&index->names, 8, conflict_name_cmp) < 0 ||
+	    git_vector_init(&index->reuc, 8, reuc_cmp) < 0 ||
+	    git_vector_init(&index->deleted, 8, git_index_entry_cmp) < 0)
 		goto fail;
 
 	index->entries_cmp_path = git__strcmp_cb;
@@ -852,20 +852,21 @@ const git_index_entry *git_index_get_bypath(
 	git_index *index, const char *path, int stage)
 {
 	git_index_entry key = {{ 0 }};
-	size_t pos;
+	git_index_entry *value;
 
 	assert(index);
 
 	key.path = path;
 	GIT_INDEX_ENTRY_STAGE_SET(&key, stage);
 
-	LOOKUP_IN_MAP(pos, index, &key);
+	LOOKUP_IN_MAP(value, index, &key);
 
-	if (git_idxmap_valid_index(index->entries_map, pos))
-		return git_idxmap_value_at(index->entries_map, pos);
+	if (!value) {
+	    git_error_set(GIT_ERROR_INDEX, "index does not contain '%s'", path);
+	    return NULL;
+	}
 
-	git_error_set(GIT_ERROR_INDEX, "index does not contain '%s'", path);
-	return NULL;
+	return value;
 }
 
 void git_index_entry__init_from_stat(
@@ -1401,7 +1402,7 @@ static int index_insert(
 		if ((error = git_vector_insert_sorted(&index->entries, entry, index_no_dups)) < 0)
 			goto out;
 
-		INSERT_IN_MAP(index, entry, &error);
+		INSERT_IN_MAP(index, entry, error);
 	}
 
 	index->dirty = 1;
@@ -1618,8 +1619,9 @@ int git_index__fill(git_index *index, const git_vector *source_entries)
 	if (!source_entries->length)
 		return 0;
 
-	git_vector_size_hint(&index->entries, source_entries->length);
-	git_idxmap_resize(index->entries_map, (size_t)(source_entries->length * 1.3));
+	if (git_vector_size_hint(&index->entries, source_entries->length) < 0 ||
+	    git_idxmap_resize(index->entries_map, (size_t)(source_entries->length * 1.3)) < 0)
+		return -1;
 
 	git_vector_foreach(source_entries, i, source_entry) {
 		git_index_entry *entry = NULL;
@@ -1634,7 +1636,7 @@ int git_index__fill(git_index *index, const git_vector *source_entries)
 		if ((ret = git_vector_insert(&index->entries, entry)) < 0)
 			break;
 
-		INSERT_IN_MAP(index, entry, &ret);
+		INSERT_IN_MAP(index, entry, ret);
 		if (ret < 0)
 			break;
 
@@ -2607,10 +2609,12 @@ static int parse_index(git_index *index, const char *buffer, size_t buffer_size)
 
 	assert(!index->entries.length);
 
-	if (index->ignore_case)
-		git_idxmap_icase_resize((git_idxmap_icase *) index->entries_map, header.entry_count);
-	else
-		git_idxmap_resize(index->entries_map, header.entry_count);
+	if (index->ignore_case &&
+	    (error = git_idxmap_icase_resize((git_idxmap_icase *) index->entries_map,
+					     header.entry_count)) < 0)
+		return error;
+	else if ((error = git_idxmap_resize(index->entries_map, header.entry_count)) < 0)
+		return error;
 
 	/* Parse all the entries */
 	for (i = 0; i < header.entry_count && buffer_size > INDEX_FOOTER_SIZE; ++i) {
@@ -2627,7 +2631,7 @@ static int parse_index(git_index *index, const char *buffer, size_t buffer_size)
 			goto done;
 		}
 
-		INSERT_IN_MAP(index, entry, &error);
+		INSERT_IN_MAP(index, entry, error);
 
 		if (error < 0) {
 			index_entry_free(entry);
@@ -3106,7 +3110,7 @@ int git_index_read_tree(git_index *index, const git_tree *tree)
 	size_t i;
 	git_index_entry *e;
 
-	if (git_idxmap_alloc(&entries_map) < 0)
+	if (git_idxmap_new(&entries_map) < 0)
 		return -1;
 
 	git_vector_set_cmp(&entries, index->entries._cmp); /* match sort */
@@ -3124,13 +3128,15 @@ int git_index_read_tree(git_index *index, const git_tree *tree)
 	if ((error = git_tree_walk(tree, GIT_TREEWALK_POST, read_tree_cb, &data)) < 0)
 		goto cleanup;
 
-	if (index->ignore_case)
-		git_idxmap_icase_resize((git_idxmap_icase *) entries_map, entries.length);
-	else
-		git_idxmap_resize(entries_map, entries.length);
+	if (index->ignore_case &&
+	    (error = git_idxmap_icase_resize((git_idxmap_icase *) entries_map,
+					     entries.length)) < 0)
+		goto cleanup;
+	else if ((error = git_idxmap_resize(entries_map, entries.length)) < 0)
+		goto cleanup;
 
 	git_vector_foreach(&entries, i, e) {
-		INSERT_IN_MAP_EX(index, entries_map, e, &error);
+		INSERT_IN_MAP_EX(index, entries_map, e, error);
 
 		if (error < 0) {
 			git_error_set(GIT_ERROR_INDEX, "failed to insert entry into map");
@@ -3180,14 +3186,17 @@ static int git_index_read_iterator(
 	assert((new_iterator->flags & GIT_ITERATOR_DONT_IGNORE_CASE));
 
 	if ((error = git_vector_init(&new_entries, new_length_hint, index->entries._cmp)) < 0 ||
-		(error = git_vector_init(&remove_entries, index->entries.length, NULL)) < 0 ||
-		(error = git_idxmap_alloc(&new_entries_map)) < 0)
+	    (error = git_vector_init(&remove_entries, index->entries.length, NULL)) < 0 ||
+	    (error = git_idxmap_new(&new_entries_map)) < 0)
 		goto done;
 
-	if (index->ignore_case && new_length_hint)
-		git_idxmap_icase_resize((git_idxmap_icase *) new_entries_map, new_length_hint);
-	else if (new_length_hint)
-		git_idxmap_resize(new_entries_map, new_length_hint);
+	if (index->ignore_case && new_length_hint &&
+	    (error = git_idxmap_icase_resize((git_idxmap_icase *) new_entries_map,
+					     new_length_hint)) < 0)
+		goto done;
+	else if (new_length_hint &&
+	         (error = git_idxmap_resize(new_entries_map, new_length_hint)) < 0)
+		goto done;
 
 	opts.flags = GIT_ITERATOR_DONT_IGNORE_CASE |
 		GIT_ITERATOR_INCLUDE_CONFLICTS;
@@ -3251,7 +3260,7 @@ static int git_index_read_iterator(
 
 		if (add_entry) {
 			if ((error = git_vector_insert(&new_entries, add_entry)) == 0)
-				INSERT_IN_MAP_EX(index, new_entries_map, add_entry, &error);
+				INSERT_IN_MAP_EX(index, new_entries_map, add_entry, error);
 		}
 
 		if (remove_entry && error >= 0)
diff --git a/src/indexer.c b/src/indexer.c
index 27b7637..6153cc2 100644
--- a/src/indexer.c
+++ b/src/indexer.c
@@ -19,6 +19,7 @@
 #include "pack.h"
 #include "filebuf.h"
 #include "oid.h"
+#include "oidarray.h"
 #include "oidmap.h"
 #include "zstream.h"
 #include "object.h"
@@ -147,8 +148,9 @@ int git_indexer_new(
 	git_hash_ctx_init(&idx->hash_ctx);
 	git_hash_ctx_init(&idx->trailer);
 	git_buf_init(&idx->entry_data, 0);
-	idx->expected_oids = git_oidmap_alloc();
-	GIT_ERROR_CHECK_ALLOC(idx->expected_oids);
+
+	if ((error = git_oidmap_new(&idx->expected_oids)) < 0)
+		goto cleanup;
 
 	idx->do_verify = opts.verify;
 
@@ -308,10 +310,8 @@ static int crc_object(uint32_t *crc_out, git_mwindow_file *mwf, git_off_t start,
 	return 0;
 }
 
-static void add_expected_oid(git_indexer *idx, const git_oid *oid)
+static int add_expected_oid(git_indexer *idx, const git_oid *oid)
 {
-	int ret;
-
 	/*
 	 * If we know about that object because it is stored in our ODB or
 	 * because we have already processed it as part of our pack file, we do
@@ -322,14 +322,16 @@ static void add_expected_oid(git_indexer *idx, const git_oid *oid)
 	    !git_oidmap_exists(idx->expected_oids, oid)) {
 		    git_oid *dup = git__malloc(sizeof(*oid));
 		    git_oid_cpy(dup, oid);
-		    git_oidmap_put(idx->expected_oids, dup, &ret);
+		    return git_oidmap_set(idx->expected_oids, dup, dup);
 	}
+
+	return 0;
 }
 
 static int check_object_connectivity(git_indexer *idx, const git_rawobj *obj)
 {
 	git_object *object;
-	size_t keyidx;
+	git_oid *expected;
 	int error;
 
 	if (obj->type != GIT_OBJECT_BLOB &&
@@ -341,11 +343,9 @@ static int check_object_connectivity(git_indexer *idx, const git_rawobj *obj)
 	if ((error = git_object__from_raw(&object, obj->data, obj->len, obj->type)) < 0)
 		goto out;
 
-	keyidx = git_oidmap_lookup_index(idx->expected_oids, &object->cached.oid);
-	if (git_oidmap_valid_index(idx->expected_oids, keyidx)) {
-		const git_oid *key = git_oidmap_key(idx->expected_oids, keyidx);
-		git__free((git_oid *) key);
-		git_oidmap_delete_at(idx->expected_oids, keyidx);
+	if ((expected = git_oidmap_get(idx->expected_oids, &object->cached.oid)) != NULL) {
+		git_oidmap_delete(idx->expected_oids, &object->cached.oid);
+		git__free(expected);
 	}
 
 	/*
@@ -363,7 +363,8 @@ static int check_object_connectivity(git_indexer *idx, const git_rawobj *obj)
 			size_t i;
 
 			git_array_foreach(tree->entries, i, entry)
-				add_expected_oid(idx, entry->oid);
+				if (add_expected_oid(idx, entry->oid) < 0)
+					goto out;
 
 			break;
 		}
@@ -374,9 +375,11 @@ static int check_object_connectivity(git_indexer *idx, const git_rawobj *obj)
 			size_t i;
 
 			git_array_foreach(commit->parent_ids, i, parent_oid)
-				add_expected_oid(idx, parent_oid);
+				if (add_expected_oid(idx, parent_oid) < 0)
+					goto out;
 
-			add_expected_oid(idx, &commit->tree_id);
+			if (add_expected_oid(idx, &commit->tree_id) < 0)
+				goto out;
 
 			break;
 		}
@@ -384,7 +387,8 @@ static int check_object_connectivity(git_indexer *idx, const git_rawobj *obj)
 		{
 			git_tag *tag = (git_tag *) object;
 
-			add_expected_oid(idx, &tag->target);
+			if (add_expected_oid(idx, &tag->target) < 0)
+				goto out;
 
 			break;
 		}
@@ -402,7 +406,6 @@ out:
 static int store_object(git_indexer *idx)
 {
 	int i, error;
-	size_t k;
 	git_oid oid;
 	struct entry *entry;
 	git_off_t entry_size;
@@ -438,22 +441,18 @@ static int store_object(git_indexer *idx)
 	git_oid_cpy(&pentry->sha1, &oid);
 	pentry->offset = entry_start;
 
-	k = git_oidmap_put(idx->pack->idx_cache, &pentry->sha1, &error);
-	if (error == -1) {
+	if (git_oidmap_exists(idx->pack->idx_cache, &pentry->sha1)) {
+		git_error_set(GIT_ERROR_INDEXER, "duplicate object %s found in pack", git_oid_tostr_s(&pentry->sha1));
 		git__free(pentry);
-		git_error_set_oom();
 		goto on_error;
 	}
 
-	if (error == 0) {
-		git_error_set(GIT_ERROR_INDEXER, "duplicate object %s found in pack", git_oid_tostr_s(&pentry->sha1));
+	if ((error = git_oidmap_set(idx->pack->idx_cache, &pentry->sha1, pentry)) < 0) {
 		git__free(pentry);
+		git_error_set_oom();
 		goto on_error;
 	}
 
-
-	git_oidmap_set_value_at(idx->pack->idx_cache, k, pentry);
-
 	git_oid_cpy(&entry->oid, &oid);
 
 	if (crc_object(&entry->crc, &idx->pack->mwf, entry_start, entry_size) < 0)
@@ -482,8 +481,7 @@ GIT_INLINE(bool) has_entry(git_indexer *idx, git_oid *id)
 
 static int save_entry(git_indexer *idx, struct entry *entry, struct git_pack_entry *pentry, git_off_t entry_start)
 {
-	int i, error;
-	size_t k;
+	int i;
 
 	if (entry_start > UINT31_MAX) {
 		entry->offset = UINT32_MAX;
@@ -493,15 +491,13 @@ static int save_entry(git_indexer *idx, struct entry *entry, struct git_pack_ent
 	}
 
 	pentry->offset = entry_start;
-	k = git_oidmap_put(idx->pack->idx_cache, &pentry->sha1, &error);
 
-	if (error <= 0) {
+	if (git_oidmap_exists(idx->pack->idx_cache, &pentry->sha1) ||
+	    git_oidmap_set(idx->pack->idx_cache, &pentry->sha1, pentry) < 0) {
 		git_error_set(GIT_ERROR_INDEXER, "cannot insert object into pack");
 		return -1;
 	}
 
-	git_oidmap_set_value_at(idx->pack->idx_cache, k, pentry);
-
 	/* Add the object to the list */
 	if (git_vector_insert(&idx->objects, entry) < 0)
 		return -1;
@@ -781,8 +777,8 @@ int git_indexer_append(git_indexer *idx, const void *data, size_t size, git_tran
 			return -1;
 		}
 
-		idx->pack->idx_cache = git_oidmap_alloc();
-		GIT_ERROR_CHECK_ALLOC(idx->pack->idx_cache);
+		if (git_oidmap_new(&idx->pack->idx_cache) < 0)
+			return -1;
 
 		idx->pack->has_cache = 1;
 		if (git_vector_init(&idx->objects, total_objects, objects_cmp) < 0)
@@ -1292,7 +1288,9 @@ on_error:
 
 void git_indexer_free(git_indexer *idx)
 {
-	size_t pos;
+	const git_oid *key;
+	git_oid *value;
+	size_t iter;
 
 	if (idx == NULL)
 		return;
@@ -1321,14 +1319,9 @@ void git_indexer_free(git_indexer *idx)
 		git_mutex_unlock(&git__mwindow_mutex);
 	}
 
-	for (pos = git_oidmap_begin(idx->expected_oids);
-	    pos != git_oidmap_end(idx->expected_oids); pos++)
-	{
-		if (git_oidmap_has_data(idx->expected_oids, pos)) {
-			git__free((git_oid *) git_oidmap_key(idx->expected_oids, pos));
-			git_oidmap_delete_at(idx->expected_oids, pos);
-		}
-	}
+	iter = 0;
+	while (git_oidmap_iterate((void **) &value, idx->expected_oids, &iter, &key) == 0)
+		git__free(value);
 
 	git_hash_ctx_cleanup(&idx->trailer);
 	git_hash_ctx_cleanup(&idx->hash_ctx);
diff --git a/src/merge.c b/src/merge.c
index 14b76fa..fbae704 100644
--- a/src/merge.c
+++ b/src/merge.c
@@ -1104,14 +1104,12 @@ static void deletes_by_oid_free(git_oidmap *map) {
 	git_oidmap_free(map);
 }
 
-static int deletes_by_oid_enqueue(git_oidmap *map, git_pool* pool, const git_oid *id, size_t idx) {
-	size_t pos;
+static int deletes_by_oid_enqueue(git_oidmap *map, git_pool* pool, const git_oid *id, size_t idx)
+{
 	deletes_by_oid_queue *queue;
 	size_t *array_entry;
-	int error;
 
-	pos = git_oidmap_lookup_index(map, id);
-	if (!git_oidmap_valid_index(map, pos)) {
+	if ((queue = git_oidmap_get(map, id)) == NULL) {
 		queue = git_pool_malloc(pool, sizeof(deletes_by_oid_queue));
 		GIT_ERROR_CHECK_ALLOC(queue);
 
@@ -1119,11 +1117,9 @@ static int deletes_by_oid_enqueue(git_oidmap *map, git_pool* pool, const git_oid
 		queue->next_pos = 0;
 		queue->first_entry = idx;
 
-		git_oidmap_insert(map, id, queue, &error);
-		if (error < 0)
+		if (git_oidmap_set(map, id, queue) < 0)
 			return -1;
 	} else {
-		queue = git_oidmap_value_at(map, pos);
 		array_entry = git_array_alloc(queue->arr);
 		GIT_ERROR_CHECK_ALLOC(array_entry);
 		*array_entry = idx;
@@ -1132,18 +1128,14 @@ static int deletes_by_oid_enqueue(git_oidmap *map, git_pool* pool, const git_oid
 	return 0;
 }
 
-static int deletes_by_oid_dequeue(size_t *idx, git_oidmap *map, const git_oid *id) {
-	size_t pos;
+static int deletes_by_oid_dequeue(size_t *idx, git_oidmap *map, const git_oid *id)
+{
 	deletes_by_oid_queue *queue;
 	size_t *array_entry;
 
-	pos = git_oidmap_lookup_index(map, id);
-
-	if (!git_oidmap_valid_index(map, pos))
+	if ((queue = git_oidmap_get(map, id)) == NULL)
 		return GIT_ENOTFOUND;
 
-	queue = git_oidmap_value_at(map, pos);
-
 	if (queue->next_pos == 0) {
 		*idx = queue->first_entry;
 	} else {
@@ -1168,8 +1160,8 @@ static int merge_diff_mark_similarity_exact(
 	git_oidmap *ours_deletes_by_oid = NULL, *theirs_deletes_by_oid = NULL;
 	int error = 0;
 
-	if (!(ours_deletes_by_oid = git_oidmap_alloc()) ||
-		!(theirs_deletes_by_oid = git_oidmap_alloc())) {
+	if (git_oidmap_new(&ours_deletes_by_oid) < 0 ||
+	    git_oidmap_new(&theirs_deletes_by_oid) < 0) {
 		error = -1;
 		goto done;
 	}
diff --git a/src/mwindow.c b/src/mwindow.c
index ffbee7d..949e5fa 100644
--- a/src/mwindow.c
+++ b/src/mwindow.c
@@ -44,15 +44,14 @@ int git_mwindow_global_init(void)
 	assert(!git__pack_cache);
 
 	git__on_shutdown(git_mwindow_files_free);
-	return git_strmap_alloc(&git__pack_cache);
+	return git_strmap_new(&git__pack_cache);
 }
 
 int git_mwindow_get_pack(struct git_pack_file **out, const char *path)
 {
-	int error;
-	char *packname;
-	size_t pos;
 	struct git_pack_file *pack;
+	char *packname;
+	int error;
 
 	if ((error = git_packfile__name(&packname, path)) < 0)
 		return error;
@@ -62,13 +61,11 @@ int git_mwindow_get_pack(struct git_pack_file **out, const char *path)
 		return -1;
 	}
 
-	pos = git_strmap_lookup_index(git__pack_cache, packname);
+	pack = git_strmap_get(git__pack_cache, packname);
 	git__free(packname);
 
-	if (git_strmap_valid_index(git__pack_cache, pos)) {
-		pack = git_strmap_value_at(git__pack_cache, pos);
+	if (pack != NULL) {
 		git_atomic_inc(&pack->refcount);
-
 		git_mutex_unlock(&git__mwindow_mutex);
 		*out = pack;
 		return 0;
@@ -82,7 +79,7 @@ int git_mwindow_get_pack(struct git_pack_file **out, const char *path)
 
 	git_atomic_inc(&pack->refcount);
 
-	git_strmap_insert(git__pack_cache, pack->pack_name, pack, &error);
+	error = git_strmap_set(git__pack_cache, pack->pack_name, pack);
 	git_mutex_unlock(&git__mwindow_mutex);
 
 	if (error < 0) {
@@ -97,7 +94,6 @@ int git_mwindow_get_pack(struct git_pack_file **out, const char *path)
 void git_mwindow_put_pack(struct git_pack_file *pack)
 {
 	int count;
-	size_t pos;
 
 	if (git_mutex_lock(&git__mwindow_mutex) < 0)
 		return;
@@ -105,13 +101,12 @@ void git_mwindow_put_pack(struct git_pack_file *pack)
 	/* put before get would be a corrupted state */
 	assert(git__pack_cache);
 
-	pos = git_strmap_lookup_index(git__pack_cache, pack->pack_name);
 	/* if we cannot find it, the state is corrupted */
-	assert(git_strmap_valid_index(git__pack_cache, pos));
+	assert(git_strmap_exists(git__pack_cache, pack->pack_name));
 
 	count = git_atomic_dec(&pack->refcount);
 	if (count == 0) {
-		git_strmap_delete_at(git__pack_cache, pos);
+		git_strmap_delete(git__pack_cache, pack->pack_name);
 		git_packfile_free(pack);
 	}
 
diff --git a/src/odb_mempack.c b/src/odb_mempack.c
index fb29ddd..fc23023 100644
--- a/src/odb_mempack.c
+++ b/src/odb_mempack.c
@@ -37,15 +37,9 @@ static int impl__write(git_odb_backend *_backend, const git_oid *oid, const void
 {
 	struct memory_packer_db *db = (struct memory_packer_db *)_backend;
 	struct memobject *obj = NULL;
-	size_t pos;
 	size_t alloc_len;
-	int rval;
 
-	pos = git_oidmap_put(db->objects, oid, &rval);
-	if (rval < 0)
-		return -1;
-
-	if (rval == 0)
+	if (git_oidmap_exists(db->objects, oid))
 		return 0;
 
 	GIT_ERROR_CHECK_ALLOC_ADD(&alloc_len, sizeof(struct memobject), len);
@@ -57,8 +51,8 @@ static int impl__write(git_odb_backend *_backend, const git_oid *oid, const void
 	obj->len = len;
 	obj->type = type;
 
-	git_oidmap_set_key_at(db->objects, pos, &obj->oid);
-	git_oidmap_set_value_at(db->objects, pos, obj);
+	if (git_oidmap_set(db->objects, &obj->oid, obj) < 0)
+		return -1;
 
 	if (type == GIT_OBJECT_COMMIT) {
 		struct memobject **store = git_array_alloc(db->commits);
@@ -79,15 +73,11 @@ static int impl__exists(git_odb_backend *backend, const git_oid *oid)
 static int impl__read(void **buffer_p, size_t *len_p, git_object_t *type_p, git_odb_backend *backend, const git_oid *oid)
 {
 	struct memory_packer_db *db = (struct memory_packer_db *)backend;
-	struct memobject *obj = NULL;
-	size_t pos;
+	struct memobject *obj;
 
-	pos = git_oidmap_lookup_index(db->objects, oid);
-	if (!git_oidmap_valid_index(db->objects, pos))
+	if ((obj = git_oidmap_get(db->objects, oid)) == NULL)
 		return GIT_ENOTFOUND;
 
-	obj = git_oidmap_value_at(db->objects, pos);
-
 	*len_p = obj->len;
 	*type_p = obj->type;
 	*buffer_p = git__malloc(obj->len);
@@ -100,15 +90,11 @@ static int impl__read(void **buffer_p, size_t *len_p, git_object_t *type_p, git_
 static int impl__read_header(size_t *len_p, git_object_t *type_p, git_odb_backend *backend, const git_oid *oid)
 {
 	struct memory_packer_db *db = (struct memory_packer_db *)backend;
-	struct memobject *obj = NULL;
-	size_t pos;
+	struct memobject *obj;
 
-	pos = git_oidmap_lookup_index(db->objects, oid);
-	if (!git_oidmap_valid_index(db->objects, pos))
+	if ((obj = git_oidmap_get(db->objects, oid)) == NULL)
 		return GIT_ENOTFOUND;
 
-	obj = git_oidmap_value_at(db->objects, pos);
-
 	*len_p = obj->len;
 	*type_p = obj->type;
 	return 0;
@@ -171,7 +157,8 @@ int git_mempack_new(git_odb_backend **out)
 	db = git__calloc(1, sizeof(struct memory_packer_db));
 	GIT_ERROR_CHECK_ALLOC(db);
 
-	db->objects = git_oidmap_alloc();
+	if (git_oidmap_new(&db->objects) < 0)
+		return -1;
 
 	db->parent.version = GIT_ODB_BACKEND_VERSION;
 	db->parent.read = &impl__read;
diff --git a/src/offmap.c b/src/offmap.c
index d0fa9f0..ba86bc0 100644
--- a/src/offmap.c
+++ b/src/offmap.c
@@ -18,9 +18,13 @@ __KHASH_TYPE(off, git_off_t, void *)
 
 __KHASH_IMPL(off, static kh_inline, git_off_t, void *, 1, kh_int64_hash_func, kh_int64_hash_equal)
 
-git_offmap *git_offmap_alloc(void)
+
+int git_offmap_new(git_offmap **out)
 {
-	return kh_init(off);
+	*out = kh_init(off);
+	GIT_ERROR_CHECK_ALLOC(*out);
+
+	return 0;
 }
 
 void git_offmap_free(git_offmap *map)
@@ -33,81 +37,65 @@ void git_offmap_clear(git_offmap *map)
 	kh_clear(off, map);
 }
 
-size_t git_offmap_num_entries(git_offmap *map)
+size_t git_offmap_size(git_offmap *map)
 {
 	return kh_size(map);
 }
 
-size_t git_offmap_lookup_index(git_offmap *map, const git_off_t key)
-{
-	return kh_get(off, map, key);
-}
-
-int git_offmap_valid_index(git_offmap *map, size_t idx)
-{
-	return idx != kh_end(map);
-}
-
-int git_offmap_exists(git_offmap *map, const git_off_t key)
+void *git_offmap_get(git_offmap *map, const git_off_t key)
 {
-	return kh_get(off, map, key) != kh_end(map);
+	size_t idx = kh_get(off, map, key);
+	if (idx == kh_end(map) || !kh_exist(map, idx))
+		return NULL;
+	return kh_val(map, idx);
 }
 
-int git_offmap_has_data(git_offmap *map, size_t idx)
+int git_offmap_set(git_offmap *map, const git_off_t key, void *value)
 {
-	return kh_exist(map, idx);
-}
+	size_t idx;
+	int rval;
 
-git_off_t git_offmap_key_at(git_offmap *map, size_t idx)
-{
-	return kh_key(map, idx);
-}
+	idx = kh_put(off, map, key, &rval);
+	if (rval < 0)
+		return -1;
 
-void *git_offmap_value_at(git_offmap *map, size_t idx)
-{
-	return kh_val(map, idx);
-}
+	if (rval == 0)
+		kh_key(map, idx) = key;
 
-void git_offmap_set_value_at(git_offmap *map, size_t idx, void *value)
-{
 	kh_val(map, idx) = value;
+
+	return 0;
 }
 
-void git_offmap_delete_at(git_offmap *map, size_t idx)
+int git_offmap_delete(git_offmap *map, const git_off_t key)
 {
+	khiter_t idx = kh_get(off, map, key);
+	if (idx == kh_end(map))
+		return GIT_ENOTFOUND;
 	kh_del(off, map, idx);
+	return 0;
 }
 
-int git_offmap_put(git_offmap *map, const git_off_t key, int *err)
+int git_offmap_exists(git_offmap *map, const git_off_t key)
 {
-	return kh_put(off, map, key, err);
+	return kh_get(off, map, key) != kh_end(map);
 }
 
-void git_offmap_insert(git_offmap *map, const git_off_t key, void *value, int *rval)
+int git_offmap_iterate(void **value, git_offmap *map, size_t *iter, git_off_t *key)
 {
-	khiter_t idx = kh_put(off, map, key, rval);
+	size_t i = *iter;
 
-	if ((*rval) >= 0) {
-		if ((*rval) == 0)
-			kh_key(map, idx) = key;
-		kh_val(map, idx) = value;
-	}
-}
+	while (i < map->n_buckets && !kh_exist(map, i))
+		i++;
 
-void git_offmap_delete(git_offmap *map, const git_off_t key)
-{
-	khiter_t idx = git_offmap_lookup_index(map, key);
-	if (git_offmap_valid_index(map, idx))
-		git_offmap_delete_at(map, idx);
-}
+	if (i >= map->n_buckets)
+		return GIT_ITEROVER;
 
-size_t git_offmap_begin(git_offmap *map)
-{
-	GIT_UNUSED(map);
-	return 0;
-}
+	if (key)
+		*key = kh_key(map, i);
+	if (value)
+		*value = kh_value(map, i);
+	*iter = ++i;
 
-size_t git_offmap_end(git_offmap *map)
-{
-	return map->n_buckets;
+	return 0;
 }
diff --git a/src/offmap.h b/src/offmap.h
index c688093..6fa7d2f 100644
--- a/src/offmap.h
+++ b/src/offmap.h
@@ -11,44 +11,122 @@
 
 #include "git2/types.h"
 
+/** A map with `git_off_t`s as key. */
 typedef struct kh_off_s git_offmap;
 
-git_offmap *git_offmap_alloc(void);
+/**
+ * Allocate a new `git_off_t` map.
+ *
+ * @param out Pointer to the map that shall be allocated.
+ * @return 0 on success, an error code if allocation has failed.
+ */
+int git_offmap_new(git_offmap **out);
+
+/**
+ * Free memory associated with the map.
+ *
+ * Note that this function will _not_ free values added to this
+ * map.
+ *
+ * @param map Pointer to the map that is to be free'd. May be
+ *            `NULL`.
+ */
 void git_offmap_free(git_offmap *map);
+
+/**
+ * Clear all entries from the map.
+ *
+ * This function will remove all entries from the associated map.
+ * Memory associated with it will not be released, though.
+ *
+ * @param map Pointer to the map that shall be cleared. May be
+ *            `NULL`.
+ */
 void git_offmap_clear(git_offmap *map);
 
-size_t git_offmap_num_entries(git_offmap *map);
+/**
+ * Return the number of elements in the map.
+ *
+ * @parameter map map containing the elements
+ * @return number of elements in the map
+ */
+size_t git_offmap_size(git_offmap *map);
 
-size_t git_offmap_lookup_index(git_offmap *map, const git_off_t key);
-int git_offmap_valid_index(git_offmap *map, size_t idx);
+/**
+ * Return value associated with the given key.
+ *
+ * @param map map to search key in
+ * @param key key to search for
+ * @return value associated with the given key or NULL if the key was not found
+ */
+void *git_offmap_get(git_offmap *map, const git_off_t key);
 
-int git_offmap_exists(git_offmap *map, const git_off_t key);
-int git_offmap_has_data(git_offmap *map, size_t idx);
+/**
+ * Set the entry for key to value.
+ *
+ * If the map has no corresponding entry for the given key, a new
+ * entry will be created with the given value. If an entry exists
+ * already, its value will be updated to match the given value.
+ *
+ * @param map map to create new entry in
+ * @param key key to set
+ * @param value value to associate the key with; may be NULL
+ * @return zero if the key was successfully set, a negative error
+ *         code otherwise
+ */
+int git_offmap_set(git_offmap *map, const git_off_t key, void *value);
 
-git_off_t git_offmap_key_at(git_offmap *map, size_t idx);
-void *git_offmap_value_at(git_offmap *map, size_t idx);
-void git_offmap_set_value_at(git_offmap *map, size_t idx, void *value);
-void git_offmap_delete_at(git_offmap *map, size_t idx);
+/**
+ * Delete an entry from the map.
+ *
+ * Delete the given key and its value from the map. If no such
+ * key exists, this will do nothing.
+ *
+ * @param map map to delete key in
+ * @param key key to delete
+ * @return `0` if the key has been deleted, GIT_ENOTFOUND if no
+ *         such key was found, a negative code in case of an
+ *         error
+ */
+int git_offmap_delete(git_offmap *map, const git_off_t key);
 
-int git_offmap_put(git_offmap *map, const git_off_t key, int *err);
-void git_offmap_insert(git_offmap *map, const git_off_t key, void *value, int *rval);
-void git_offmap_delete(git_offmap *map, const git_off_t key);
+/**
+ * Check whether a key exists in the given map.
+ *
+ * @param map map to query for the key
+ * @param key key to search for
+ * @return 0 if the key has not been found, 1 otherwise
+ */
+int git_offmap_exists(git_offmap *map, const git_off_t key);
 
-size_t git_offmap_begin(git_offmap *map);
-size_t git_offmap_end(git_offmap *map);
+/**
+ * Iterate over entries of the map.
+ *
+ * This functions allows to iterate over all key-value entries of
+ * the map. The current position is stored in the `iter` variable
+ * and should be initialized to `0` before the first call to this
+ * function.
+ *
+ * @param map map to iterate over
+ * @param value pointer to the variable where to store the current
+ *            value. May be NULL.
+ * @param iter iterator storing the current position. Initialize
+ *             with zero previous to the first call.
+ * @param key pointer to the variable where to store the current
+ *            key. May be NULL.
+ * @return `0` if the next entry was correctly retrieved.
+ *        GIT_ITEROVER if no entries are left. A negative error
+ *        code otherwise.
+ */
+int git_offmap_iterate(void **value, git_offmap *map, size_t *iter, git_off_t *key);
 
-#define git_offmap_foreach(h, kvar, vvar, code) { size_t __i;			\
-	for (__i = git_offmap_begin(h); __i != git_offmap_end(h); ++__i) {	\
-		if (!git_offmap_has_data(h,__i)) continue;			\
-		(kvar) = git_offmap_key_at(h,__i);				\
-		(vvar) = git_offmap_value_at(h,__i);				\
+#define git_offmap_foreach(h, kvar, vvar, code) { size_t __i = 0;		\
+	while (git_offmap_iterate((void **) &(vvar), h, &__i, &(kvar)) == 0) {	\
 		code;								\
 	} }
 
-#define git_offmap_foreach_value(h, vvar, code) { size_t __i;			\
-	for (__i = git_offmap_begin(h); __i != git_offmap_end(h); ++__i) {	\
-		if (!git_offmap_has_data(h,__i)) continue;			\
-		(vvar) = git_offmap_value_at(h,__i);				\
+#define git_offmap_foreach_value(h, vvar, code) { size_t __i = 0;		\
+	while (git_offmap_iterate((void **) &(vvar), h, &__i, NULL) == 0) {	\
 		code;								\
 	} }
 
diff --git a/src/oidmap.c b/src/oidmap.c
index c42e5c2..0ae8bf3 100644
--- a/src/oidmap.c
+++ b/src/oidmap.c
@@ -25,9 +25,12 @@ GIT_INLINE(khint_t) git_oidmap_hash(const git_oid *oid)
 
 __KHASH_IMPL(oid, static kh_inline, const git_oid *, void *, 1, git_oidmap_hash, git_oid_equal)
 
-git_oidmap *git_oidmap_alloc()
+int git_oidmap_new(git_oidmap **out)
 {
-	return kh_init(oid);
+	*out = kh_init(oid);
+	GIT_ERROR_CHECK_ALLOC(*out);
+
+	return 0;
 }
 
 void git_oidmap_free(git_oidmap *map)
@@ -45,81 +48,60 @@ size_t git_oidmap_size(git_oidmap *map)
 	return kh_size(map);
 }
 
-size_t git_oidmap_lookup_index(git_oidmap *map, const git_oid *key)
-{
-	return kh_get(oid, map, key);
-}
-
-int git_oidmap_valid_index(git_oidmap *map, size_t idx)
-{
-	return idx != kh_end(map);
-}
-
-int git_oidmap_exists(git_oidmap *map, const git_oid *key)
+void *git_oidmap_get(git_oidmap *map, const git_oid *key)
 {
-	return kh_get(oid, map, key) != kh_end(map);
-}
-
-int git_oidmap_has_data(git_oidmap *map, size_t idx)
-{
-	return kh_exist(map, idx);
+	size_t idx = kh_get(oid, map, key);
+	if (idx == kh_end(map) || !kh_exist(map, idx))
+		return NULL;
+	return kh_val(map, idx);
 }
 
-const git_oid *git_oidmap_key(git_oidmap *map, size_t idx)
+int git_oidmap_set(git_oidmap *map, const git_oid *key, void *value)
 {
-	return kh_key(map, idx);
-}
+	size_t idx;
+	int rval;
 
-void git_oidmap_set_key_at(git_oidmap *map, size_t idx, git_oid *key)
-{
-	kh_key(map, idx) = key;
-}
+	idx = kh_put(oid, map, key, &rval);
+	if (rval < 0)
+		return -1;
 
-void *git_oidmap_value_at(git_oidmap *map, size_t idx)
-{
-	return kh_val(map, idx);
-}
+	if (rval == 0)
+		kh_key(map, idx) = key;
 
-void git_oidmap_set_value_at(git_oidmap *map, size_t idx, void *value)
-{
 	kh_val(map, idx) = value;
+
+	return 0;
 }
 
-void git_oidmap_delete_at(git_oidmap *map, size_t idx)
+int git_oidmap_delete(git_oidmap *map, const git_oid *key)
 {
+	khiter_t idx = kh_get(oid, map, key);
+	if (idx == kh_end(map))
+		return GIT_ENOTFOUND;
 	kh_del(oid, map, idx);
+	return 0;
 }
 
-int git_oidmap_put(git_oidmap *map, const git_oid *key, int *err)
+int git_oidmap_exists(git_oidmap *map, const git_oid *key)
 {
-	return kh_put(oid, map, key, err);
+	return kh_get(oid, map, key) != kh_end(map);
 }
 
-void git_oidmap_insert(git_oidmap *map, const git_oid *key, void *value, int *rval)
+int git_oidmap_iterate(void **value, git_oidmap *map, size_t *iter, const git_oid **key)
 {
-	khiter_t idx = kh_put(oid, map, key, rval);
+	size_t i = *iter;
 
-	if ((*rval) >= 0) {
-		if ((*rval) == 0)
-			kh_key(map, idx) = key;
-		kh_val(map, idx) = value;
-	}
-}
+	while (i < map->n_buckets && !kh_exist(map, i))
+		i++;
 
-void git_oidmap_delete(git_oidmap *map, const git_oid *key)
-{
-	khiter_t idx = git_oidmap_lookup_index(map, key);
-	if (git_oidmap_valid_index(map, idx))
-		git_oidmap_delete_at(map, idx);
-}
+	if (i >= map->n_buckets)
+		return GIT_ITEROVER;
 
-size_t git_oidmap_begin(git_oidmap *map)
-{
-	GIT_UNUSED(map);
-	return 0;
-}
+	if (key)
+		*key = kh_key(map, i);
+	if (value)
+		*value = kh_value(map, i);
+	*iter = ++i;
 
-size_t git_oidmap_end(git_oidmap *map)
-{
-	return map->n_buckets;
+	return 0;
 }
diff --git a/src/oidmap.h b/src/oidmap.h
index a417907..b748f72 100644
--- a/src/oidmap.h
+++ b/src/oidmap.h
@@ -11,37 +11,117 @@
 
 #include "git2/oid.h"
 
+/** A map with `git_oid`s as key. */
 typedef struct kh_oid_s git_oidmap;
 
-git_oidmap *git_oidmap_alloc(void);
+/**
+ * Allocate a new OID map.
+ *
+ * @param out Pointer to the map that shall be allocated.
+ * @return 0 on success, an error code if allocation has failed.
+ */
+int git_oidmap_new(git_oidmap **out);
+
+/**
+ * Free memory associated with the map.
+ *
+ * Note that this function will _not_ free values added to this
+ * map.
+ *
+ * @param map Pointer to the map that is to be free'd. May be
+ *            `NULL`.
+ */
 void git_oidmap_free(git_oidmap *map);
+
+/**
+ * Clear all entries from the map.
+ *
+ * This function will remove all entries from the associated map.
+ * Memory associated with it will not be released, though.
+ *
+ * @param map Pointer to the map that shall be cleared. May be
+ *            `NULL`.
+ */
 void git_oidmap_clear(git_oidmap *map);
 
+/**
+ * Return the number of elements in the map.
+ *
+ * @parameter map map containing the elements
+ * @return number of elements in the map
+ */
 size_t git_oidmap_size(git_oidmap *map);
 
-size_t git_oidmap_lookup_index(git_oidmap *map, const git_oid *key);
-int git_oidmap_valid_index(git_oidmap *map, size_t idx);
+/**
+ * Return value associated with the given key.
+ *
+ * @param map map to search key in
+ * @param key key to search for
+ * @return value associated with the given key or NULL if the key was not found
+ */
+void *git_oidmap_get(git_oidmap *map, const git_oid *key);
 
-int git_oidmap_exists(git_oidmap *map, const git_oid *key);
-int git_oidmap_has_data(git_oidmap *map, size_t idx);
+/**
+ * Set the entry for key to value.
+ *
+ * If the map has no corresponding entry for the given key, a new
+ * entry will be created with the given value. If an entry exists
+ * already, its value will be updated to match the given value.
+ *
+ * @param map map to create new entry in
+ * @param key key to set
+ * @param value value to associate the key with; may be NULL
+ * @return zero if the key was successfully set, a negative error
+ *         code otherwise
+ */
+int git_oidmap_set(git_oidmap *map, const git_oid *key, void *value);
 
-const git_oid *git_oidmap_key(git_oidmap *map, size_t idx);
-void git_oidmap_set_key_at(git_oidmap *map, size_t idx, git_oid *key);
-void *git_oidmap_value_at(git_oidmap *map, size_t idx);
-void git_oidmap_set_value_at(git_oidmap *map, size_t idx, void *value);
-void git_oidmap_delete_at(git_oidmap *map, size_t idx);
+/**
+ * Delete an entry from the map.
+ *
+ * Delete the given key and its value from the map. If no such
+ * key exists, this will do nothing.
+ *
+ * @param map map to delete key in
+ * @param key key to delete
+ * @return `0` if the key has been deleted, GIT_ENOTFOUND if no
+ *         such key was found, a negative code in case of an
+ *         error
+ */
+int git_oidmap_delete(git_oidmap *map, const git_oid *key);
 
-int git_oidmap_put(git_oidmap *map, const git_oid *key, int *err);
-void git_oidmap_insert(git_oidmap *map, const git_oid *key, void *value, int *rval);
-void git_oidmap_delete(git_oidmap *map, const git_oid *key);
+/**
+ * Check whether a key exists in the given map.
+ *
+ * @param map map to query for the key
+ * @param key key to search for
+ * @return 0 if the key has not been found, 1 otherwise
+ */
+int git_oidmap_exists(git_oidmap *map, const git_oid *key);
 
-size_t git_oidmap_begin(git_oidmap *map);
-size_t git_oidmap_end(git_oidmap *map);
+/**
+ * Iterate over entries of the map.
+ *
+ * This functions allows to iterate over all key-value entries of
+ * the map. The current position is stored in the `iter` variable
+ * and should be initialized to `0` before the first call to this
+ * function.
+ *
+ * @param map map to iterate over
+ * @param value pointer to the variable where to store the current
+ *            value. May be NULL.
+ * @param iter iterator storing the current position. Initialize
+ *             with zero previous to the first call.
+ * @param key pointer to the variable where to store the current
+ *            key. May be NULL.
+ * @return `0` if the next entry was correctly retrieved.
+ *        GIT_ITEROVER if no entries are left. A negative error
+ *        code otherwise.
+ */
+int git_oidmap_iterate(void **value, git_oidmap *map, size_t *iter, const git_oid **key);
 
-#define git_oidmap_foreach_value(h, vvar, code) { size_t __i;			\
-	for (__i = git_oidmap_begin(h); __i != git_oidmap_end(h); ++__i) {	\
-		if (!git_oidmap_has_data(h,__i)) continue;			\
-		(vvar) = git_oidmap_value_at(h,__i);				\
+#define git_oidmap_foreach_value(h, vvar, code) { size_t __i = 0;		\
+	while (git_oidmap_iterate((void **) &(vvar), h, &__i, NULL) == 0) {	\
 		code;								\
 	} }
 
diff --git a/src/pack-objects.c b/src/pack-objects.c
index e152864..b2e2457 100644
--- a/src/pack-objects.c
+++ b/src/pack-objects.c
@@ -141,12 +141,10 @@ int git_packbuilder_new(git_packbuilder **out, git_repository *repo)
 	pb = git__calloc(1, sizeof(*pb));
 	GIT_ERROR_CHECK_ALLOC(pb);
 
-	pb->object_ix = git_oidmap_alloc();
-	if (!pb->object_ix)
+	if (git_oidmap_new(&pb->object_ix) < 0)
 		goto on_error;
 
-	pb->walk_objects = git_oidmap_alloc();
-	if (!pb->walk_objects)
+	if (git_oidmap_new(&pb->walk_objects) < 0)
 		goto on_error;
 
 	git_pool_init(&pb->object_pool, sizeof(struct walk_object));
@@ -194,24 +192,26 @@ unsigned int git_packbuilder_set_threads(git_packbuilder *pb, unsigned int n)
 	return pb->nr_threads;
 }
 
-static void rehash(git_packbuilder *pb)
+static int rehash(git_packbuilder *pb)
 {
 	git_pobject *po;
-	size_t pos, i;
-	int ret;
+	size_t i;
 
 	git_oidmap_clear(pb->object_ix);
+
 	for (i = 0, po = pb->object_list; i < pb->nr_objects; i++, po++) {
-		pos = git_oidmap_put(pb->object_ix, &po->id, &ret);
-		git_oidmap_set_value_at(pb->object_ix, pos, po);
+		if (git_oidmap_set(pb->object_ix, &po->id, po) < 0)
+			return -1;
 	}
+
+	return 0;
 }
 
 int git_packbuilder_insert(git_packbuilder *pb, const git_oid *oid,
 			   const char *name)
 {
 	git_pobject *po;
-	size_t newsize, pos;
+	size_t newsize;
 	int ret;
 
 	assert(pb && oid);
@@ -235,7 +235,9 @@ int git_packbuilder_insert(git_packbuilder *pb, const git_oid *oid,
 		pb->object_list = git__reallocarray(pb->object_list,
 			pb->nr_alloc, sizeof(*po));
 		GIT_ERROR_CHECK_ALLOC(pb->object_list);
-		rehash(pb);
+
+		if (rehash(pb) < 0)
+			return -1;
 	}
 
 	po = pb->object_list + pb->nr_objects;
@@ -248,13 +250,10 @@ int git_packbuilder_insert(git_packbuilder *pb, const git_oid *oid,
 	git_oid_cpy(&po->id, oid);
 	po->hash = name_hash(name);
 
-	pos = git_oidmap_put(pb->object_ix, &po->id, &ret);
-	if (ret < 0) {
+	if (git_oidmap_set(pb->object_ix, &po->id, po) < 0) {
 		git_error_set_oom();
-		return ret;
+		return -1;
 	}
-	assert(ret != 0);
-	git_oidmap_set_value_at(pb->object_ix, pos, po);
 
 	pb->done = false;
 
@@ -514,15 +513,12 @@ static int cb_tag_foreach(const char *name, git_oid *oid, void *data)
 {
 	git_packbuilder *pb = data;
 	git_pobject *po;
-	size_t pos;
 
 	GIT_UNUSED(name);
 
-	pos = git_oidmap_lookup_index(pb->object_ix, oid);
-	if (!git_oidmap_valid_index(pb->object_ix, pos))
+	if ((po = git_oidmap_get(pb->object_ix, oid)) == NULL)
 		return 0;
 
-	po = git_oidmap_value_at(pb->object_ix, pos);
 	po->tagged = 1;
 
 	/* TODO: peel objects */
@@ -1539,18 +1535,15 @@ static int lookup_walk_object(struct walk_object **out, git_packbuilder *pb, con
 
 static int retrieve_object(struct walk_object **out, git_packbuilder *pb, const git_oid *id)
 {
-	int error;
-	size_t pos;
 	struct walk_object *obj;
+	int error;
 
-	pos = git_oidmap_lookup_index(pb->walk_objects, id);
-	if (git_oidmap_valid_index(pb->walk_objects, pos)) {
-		obj = git_oidmap_value_at(pb->walk_objects, pos);
-	} else {
+	if ((obj = git_oidmap_get(pb->walk_objects, id)) == NULL) {
 		if ((error = lookup_walk_object(&obj, pb, id)) < 0)
 			return error;
 
-		git_oidmap_insert(pb->walk_objects, &obj->id, obj, &error);
+		if ((error = git_oidmap_set(pb->walk_objects, &obj->id, obj)) < 0)
+			return error;
 	}
 
 	*out = obj;
diff --git a/src/pack.c b/src/pack.c
index cdd7e9e..c9d5602 100644
--- a/src/pack.c
+++ b/src/pack.c
@@ -92,8 +92,8 @@ static void cache_free(git_pack_cache *cache)
 
 static int cache_init(git_pack_cache *cache)
 {
-	cache->entries = git_offmap_alloc();
-	GIT_ERROR_CHECK_ALLOC(cache->entries);
+	if (git_offmap_new(&cache->entries) < 0)
+		return -1;
 
 	cache->memory_limit = GIT_PACK_CACHE_MEMORY_LIMIT;
 
@@ -111,15 +111,12 @@ static int cache_init(git_pack_cache *cache)
 
 static git_pack_cache_entry *cache_get(git_pack_cache *cache, git_off_t offset)
 {
-	git_pack_cache_entry *entry = NULL;
-	size_t k;
+	git_pack_cache_entry *entry;
 
 	if (git_mutex_lock(&cache->lock) < 0)
 		return NULL;
 
-	k = git_offmap_lookup_index(cache->entries, offset);
-	if (git_offmap_valid_index(cache->entries, k)) { /* found it */
-		entry = git_offmap_value_at(cache->entries, k);
+	if ((entry = git_offmap_get(cache->entries, offset)) != NULL) {
 		git_atomic_inc(&entry->refcount);
 		entry->last_usage = cache->use_ctr++;
 	}
@@ -150,8 +147,7 @@ static int cache_add(
 		git_off_t offset)
 {
 	git_pack_cache_entry *entry;
-	int error, exists = 0;
-	size_t k;
+	int exists;
 
 	if (base->len > GIT_PACK_CACHE_SIZE_LIMIT)
 		return -1;
@@ -169,9 +165,7 @@ static int cache_add(
 			while (cache->memory_used + base->len > cache->memory_limit)
 				free_lowest_entry(cache);
 
-			k = git_offmap_put(cache->entries, offset, &error);
-			assert(error != 0);
-			git_offmap_set_value_at(cache->entries, k, entry);
+			git_offmap_set(cache->entries, offset, entry);
 			cache->memory_used += entry->raw.len;
 
 			*cached_out = entry;
@@ -957,14 +951,13 @@ git_off_t get_delta_base(
 	} else if (type == GIT_OBJECT_REF_DELTA) {
 		/* If we have the cooperative cache, search in it first */
 		if (p->has_cache) {
+			struct git_pack_entry *entry;
 			git_oid oid;
-			size_t k;
 
 			git_oid_fromraw(&oid, base_info);
-			k = git_oidmap_lookup_index(p->idx_cache, &oid);
-			if (git_oidmap_valid_index(p->idx_cache, k)) {
+			if ((entry = git_oidmap_get(p->idx_cache, &oid)) != NULL) {
 				*curpos += 20;
-				return ((struct git_pack_entry *)git_oidmap_value_at(p->idx_cache, k))->offset;
+				return entry->offset;
 			} else {
 				/* If we're building an index, don't try to find the pack
 				 * entry; we just haven't seen it yet.  We'll make
diff --git a/src/pack.h b/src/pack.h
index f21ad9f..483c4e8 100644
--- a/src/pack.h
+++ b/src/pack.h
@@ -17,6 +17,7 @@
 #include "map.h"
 #include "mwindow.h"
 #include "odb.h"
+#include "offmap.h"
 #include "oidmap.h"
 #include "array.h"
 
@@ -71,9 +72,6 @@ struct pack_chain_elem {
 
 typedef git_array_t(struct pack_chain_elem) git_dependency_chain;
 
-#include "offmap.h"
-#include "oidmap.h"
-
 #define GIT_PACK_CACHE_MEMORY_LIMIT 16 * 1024 * 1024
 #define GIT_PACK_CACHE_SIZE_LIMIT 1024 * 1024 /* don't bother caching anything over 1MB */
 
diff --git a/src/repository.c b/src/repository.c
index 203a6e8..349ddf1 100644
--- a/src/repository.c
+++ b/src/repository.c
@@ -2916,7 +2916,7 @@ int git_repository_submodule_cache_all(git_repository *repo)
 
 	assert(repo);
 
-	if ((error = git_strmap_alloc(&repo->submodule_cache)))
+	if ((error = git_strmap_new(&repo->submodule_cache)))
 		return error;
 
 	error = git_submodule__map(repo, repo->submodule_cache);
diff --git a/src/revwalk.c b/src/revwalk.c
index 1e3a5f2..6d12d34 100644
--- a/src/revwalk.c
+++ b/src/revwalk.c
@@ -21,13 +21,10 @@ git_commit_list_node *git_revwalk__commit_lookup(
 	git_revwalk *walk, const git_oid *oid)
 {
 	git_commit_list_node *commit;
-	size_t pos;
-	int ret;
 
 	/* lookup and reserve space if not already present */
-	pos = git_oidmap_lookup_index(walk->commits, oid);
-	if (git_oidmap_valid_index(walk->commits, pos))
-		return git_oidmap_value_at(walk->commits, pos);
+	if ((commit = git_oidmap_get(walk->commits, oid)) != NULL)
+		return commit;
 
 	commit = git_commit_list_alloc_node(walk);
 	if (commit == NULL)
@@ -35,9 +32,8 @@ git_commit_list_node *git_revwalk__commit_lookup(
 
 	git_oid_cpy(&commit->oid, oid);
 
-	pos = git_oidmap_put(walk->commits, &commit->oid, &ret);
-	assert(ret != 0);
-	git_oidmap_set_value_at(walk->commits, pos, commit);
+	if ((git_oidmap_set(walk->commits, &commit->oid, commit)) < 0)
+		return NULL;
 
 	return commit;
 }
@@ -626,8 +622,8 @@ int git_revwalk_new(git_revwalk **revwalk_out, git_repository *repo)
 	git_revwalk *walk = git__calloc(1, sizeof(git_revwalk));
 	GIT_ERROR_CHECK_ALLOC(walk);
 
-	walk->commits = git_oidmap_alloc();
-	GIT_ERROR_CHECK_ALLOC(walk->commits);
+	if (git_oidmap_new(&walk->commits) < 0)
+		return -1;
 
 	if (git_pqueue_init(&walk->iterator_time, 0, 8, git_commit_list_time_cmp) < 0)
 		return -1;
diff --git a/src/sortedcache.c b/src/sortedcache.c
index 02a685e..15ba6fd 100644
--- a/src/sortedcache.c
+++ b/src/sortedcache.c
@@ -28,7 +28,7 @@ int git_sortedcache_new(
 	git_pool_init(&sc->pool, 1);
 
 	if (git_vector_init(&sc->items, 4, item_cmp) < 0 ||
-		git_strmap_alloc(&sc->map) < 0)
+	    git_strmap_new(&sc->map) < 0)
 		goto fail;
 
 	if (git_rwlock_init(&sc->lock)) {
@@ -270,17 +270,13 @@ int git_sortedcache_clear(git_sortedcache *sc, bool wlock)
 /* find and/or insert item, returning pointer to item data */
 int git_sortedcache_upsert(void **out, git_sortedcache *sc, const char *key)
 {
-	size_t pos;
-	int error = 0;
-	void *item;
 	size_t keylen, itemlen;
+	int error = 0;
 	char *item_key;
+	void *item;
 
-	pos = git_strmap_lookup_index(sc->map, key);
-	if (git_strmap_valid_index(sc->map, pos)) {
-		item = git_strmap_value_at(sc->map, pos);
+	if ((item = git_strmap_get(sc->map, key)) != NULL)
 		goto done;
-	}
 
 	keylen  = strlen(key);
 	itemlen = sc->item_path_offset + keylen + 1;
@@ -299,17 +295,11 @@ int git_sortedcache_upsert(void **out, git_sortedcache *sc, const char *key)
 	item_key = ((char *)item) + sc->item_path_offset;
 	memcpy(item_key, key, keylen);
 
-	pos = git_strmap_put(sc->map, item_key, &error);
-	if (error < 0)
+	if ((error = git_strmap_set(sc->map, item_key, item)) < 0)
 		goto done;
 
-	if (!error)
-		git_strmap_set_key_at(sc->map, pos, item_key);
-	git_strmap_set_value_at(sc->map, pos, item);
-
-	error = git_vector_insert(&sc->items, item);
-	if (error < 0)
-		git_strmap_delete_at(sc->map, pos);
+	if ((error = git_vector_insert(&sc->items, item)) < 0)
+		git_strmap_delete(sc->map, item_key);
 
 done:
 	if (out)
@@ -320,10 +310,7 @@ done:
 /* lookup item by key */
 void *git_sortedcache_lookup(const git_sortedcache *sc, const char *key)
 {
-	size_t pos = git_strmap_lookup_index(sc->map, key);
-	if (git_strmap_valid_index(sc->map, pos))
-		return git_strmap_value_at(sc->map, pos);
-	return NULL;
+	return git_strmap_get(sc->map, key);
 }
 
 /* find out how many items are in the cache */
@@ -371,9 +358,9 @@ int git_sortedcache_lookup_index(
 int git_sortedcache_remove(git_sortedcache *sc, size_t pos)
 {
 	char *item;
-	size_t mappos;
 
-	/* because of pool allocation, this can't actually remove the item,
+	/*
+	 * Because of pool allocation, this can't actually remove the item,
 	 * but we can remove it from the items vector and the hash table.
 	 */
 
@@ -384,8 +371,7 @@ int git_sortedcache_remove(git_sortedcache *sc, size_t pos)
 
 	(void)git_vector_remove(&sc->items, pos);
 
-	mappos = git_strmap_lookup_index(sc->map, item + sc->item_path_offset);
-	git_strmap_delete_at(sc->map, mappos);
+	git_strmap_delete(sc->map, item + sc->item_path_offset);
 
 	if (sc->free_item)
 		sc->free_item(sc->free_item_payload, item);
diff --git a/src/strmap.c b/src/strmap.c
index 20b14ac..c6e5b6d 100644
--- a/src/strmap.c
+++ b/src/strmap.c
@@ -18,12 +18,10 @@ __KHASH_TYPE(str, const char *, void *)
 
 __KHASH_IMPL(str, static kh_inline, const char *, void *, 1, kh_str_hash_func, kh_str_hash_equal)
 
-int git_strmap_alloc(git_strmap **map)
+int git_strmap_new(git_strmap **out)
 {
-	if ((*map = kh_init(str)) == NULL) {
-		git_error_set_oom();
-		return -1;
-	}
+	*out = kh_init(str);
+	GIT_ERROR_CHECK_ALLOC(*out);
 
 	return 0;
 }
@@ -38,110 +36,65 @@ void git_strmap_clear(git_strmap *map)
 	kh_clear(str, map);
 }
 
-size_t git_strmap_num_entries(git_strmap *map)
+size_t git_strmap_size(git_strmap *map)
 {
 	return kh_size(map);
 }
 
-size_t git_strmap_lookup_index(git_strmap *map, const char *key)
-{
-	return kh_get(str, map, key);
-}
-
-int git_strmap_valid_index(git_strmap *map, size_t idx)
-{
-	return idx != kh_end(map);
-}
-
-int git_strmap_exists(git_strmap *map, const char *key)
-{
-	return kh_get(str, map, key) != kh_end(map);
-}
-
-int git_strmap_has_data(git_strmap *map, size_t idx)
-{
-	return kh_exist(map, idx);
-}
-
-const char *git_strmap_key(git_strmap *map, size_t idx)
-{
-	return kh_key(map, idx);
-}
-
-void git_strmap_set_key_at(git_strmap *map, size_t idx, char *key)
-{
-	kh_val(map, idx) = key;
-}
-
-void *git_strmap_value_at(git_strmap *map, size_t idx)
+void *git_strmap_get(git_strmap *map, const char *key)
 {
+	size_t idx = kh_get(str, map, key);
+	if (idx == kh_end(map) || !kh_exist(map, idx))
+		return NULL;
 	return kh_val(map, idx);
 }
 
-void git_strmap_set_value_at(git_strmap *map, size_t idx, void *value)
-{
-	kh_val(map, idx) = value;
-}
-
-void git_strmap_delete_at(git_strmap *map, size_t idx)
+int git_strmap_set(git_strmap *map, const char *key, void *value)
 {
-	kh_del(str, map, idx);
-}
+	size_t idx;
+	int rval;
 
-int git_strmap_put(git_strmap *map, const char *key, int *err)
-{
-	return kh_put(str, map, key, err);
-}
+	idx = kh_put(str, map, key, &rval);
+	if (rval < 0)
+		return -1;
 
-void git_strmap_insert(git_strmap *map, const char *key, void *value, int *rval)
-{
-	khiter_t idx = kh_put(str, map, key, rval);
+	if (rval == 0)
+		kh_key(map, idx) = key;
 
-	if ((*rval) >= 0) {
-		if ((*rval) == 0)
-			kh_key(map, idx) = key;
-		kh_val(map, idx) = value;
-	}
-}
+	kh_val(map, idx) = value;
 
-void git_strmap_delete(git_strmap *map, const char *key)
-{
-	khiter_t idx = git_strmap_lookup_index(map, key);
-	if (git_strmap_valid_index(map, idx))
-		git_strmap_delete_at(map, idx);
+	return 0;
 }
 
-size_t git_strmap_begin(git_strmap *map)
+int git_strmap_delete(git_strmap *map, const char *key)
 {
-	GIT_UNUSED(map);
+	khiter_t idx = kh_get(str, map, key);
+	if (idx == kh_end(map))
+		return GIT_ENOTFOUND;
+	kh_del(str, map, idx);
 	return 0;
 }
 
-size_t git_strmap_end(git_strmap *map)
+int git_strmap_exists(git_strmap *map, const char *key)
 {
-	return map->n_buckets;
+	return kh_get(str, map, key) != kh_end(map);
 }
 
-int git_strmap_next(
-	void **data,
-	size_t* iter,
-	git_strmap *map)
+int git_strmap_iterate(void **value, git_strmap *map, size_t *iter, const char **key)
 {
-	if (!map)
-		return GIT_ERROR;
+	size_t i = *iter;
 
-	while (*iter != git_strmap_end(map)) {
-		if (!(git_strmap_has_data(map, *iter))) {
-			++(*iter);
-			continue;
-		}
+	while (i < map->n_buckets && !kh_exist(map, i))
+		i++;
 
-		*data = git_strmap_value_at(map, *iter);
+	if (i >= map->n_buckets)
+		return GIT_ITEROVER;
 
-		++(*iter);
+	if (key)
+		*key = kh_key(map, i);
+	if (value)
+		*value = kh_val(map, i);
+	*iter = ++i;
 
-		return GIT_OK;
-	}
-
-	return GIT_ITEROVER;
+	return 0;
 }
diff --git a/src/strmap.h b/src/strmap.h
index 2649acb..9f5e4cc 100644
--- a/src/strmap.h
+++ b/src/strmap.h
@@ -9,51 +9,123 @@
 
 #include "common.h"
 
+/** A map with C strings as key. */
 typedef struct kh_str_s git_strmap;
 
-int git_strmap_alloc(git_strmap **map);
+/**
+ * Allocate a new string map.
+ *
+ * @param out Pointer to the map that shall be allocated.
+ * @return 0 on success, an error code if allocation has failed.
+ */
+int git_strmap_new(git_strmap **out);
+
+/**
+ * Free memory associated with the map.
+ *
+ * Note that this function will _not_ free keys or values added
+ * to this map.
+ *
+ * @param map Pointer to the map that is to be free'd. May be
+ *            `NULL`.
+ */
 void git_strmap_free(git_strmap *map);
+
+/**
+ * Clear all entries from the map.
+ *
+ * This function will remove all entries from the associated map.
+ * Memory associated with it will not be released, though.
+ *
+ * @param map Pointer to the map that shall be cleared. May be
+ *            `NULL`.
+ */
 void git_strmap_clear(git_strmap *map);
 
-size_t git_strmap_num_entries(git_strmap *map);
+/**
+ * Return the number of elements in the map.
+ *
+ * @parameter map map containing the elements
+ * @return number of elements in the map
+ */
+size_t git_strmap_size(git_strmap *map);
 
-size_t git_strmap_lookup_index(git_strmap *map, const char *key);
-int git_strmap_valid_index(git_strmap *map, size_t idx);
+/**
+ * Return value associated with the given key.
+ *
+ * @param map map to search key in
+ * @param key key to search for
+ * @return value associated with the given key or NULL if the key was not found
+ */
+void *git_strmap_get(git_strmap *map, const char *key);
 
+/**
+ * Set the entry for key to value.
+ *
+ * If the map has no corresponding entry for the given key, a new
+ * entry will be created with the given value. If an entry exists
+ * already, its value will be updated to match the given value.
+ *
+ * @param map map to create new entry in
+ * @param key key to set
+ * @param value value to associate the key with; may be NULL
+ * @return zero if the key was successfully set, a negative error
+ *         code otherwise
+ */
+int git_strmap_set(git_strmap *map, const char *key, void *value);
+
+/**
+ * Delete an entry from the map.
+ *
+ * Delete the given key and its value from the map. If no such
+ * key exists, this will do nothing.
+ *
+ * @param map map to delete key in
+ * @param key key to delete
+ * @return `0` if the key has been deleted, GIT_ENOTFOUND if no
+ *         such key was found, a negative code in case of an
+ *         error
+ */
+int git_strmap_delete(git_strmap *map, const char *key);
+
+/**
+ * Check whether a key exists in the given map.
+ *
+ * @param map map to query for the key
+ * @param key key to search for
+ * @return 0 if the key has not been found, 1 otherwise
+ */
 int git_strmap_exists(git_strmap *map, const char *key);
-int git_strmap_has_data(git_strmap *map, size_t idx);
-
-const char *git_strmap_key(git_strmap *map, size_t idx);
-void git_strmap_set_key_at(git_strmap *map, size_t idx, char *key);
-void *git_strmap_value_at(git_strmap *map, size_t idx);
-void git_strmap_set_value_at(git_strmap *map, size_t idx, void *value);
-void git_strmap_delete_at(git_strmap *map, size_t idx);
-
-int git_strmap_put(git_strmap *map, const char *key, int *err);
-void git_strmap_insert(git_strmap *map, const char *key, void *value, int *rval);
-void git_strmap_delete(git_strmap *map, const char *key);
-
-#define git_strmap_foreach(h, kvar, vvar, code) { size_t __i;			\
-	for (__i = git_strmap_begin(h); __i != git_strmap_end(h); ++__i) {	\
-		if (!git_strmap_has_data(h,__i)) continue;			\
-		(kvar) = git_strmap_key(h,__i);					\
-		(vvar) = git_strmap_value_at(h,__i);				\
+
+/**
+ * Iterate over entries of the map.
+ *
+ * This functions allows to iterate over all key-value entries of
+ * the map. The current position is stored in the `iter` variable
+ * and should be initialized to `0` before the first call to this
+ * function.
+ *
+ * @param map map to iterate over
+ * @param value pointer to the variable where to store the current
+ *            value. May be NULL.
+ * @param iter iterator storing the current position. Initialize
+ *             with zero previous to the first call.
+ * @param key pointer to the variable where to store the current
+ *            key. May be NULL.
+ * @return `0` if the next entry was correctly retrieved.
+ *        GIT_ITEROVER if no entries are left. A negative error
+ *        code otherwise.
+ */
+int git_strmap_iterate(void **value, git_strmap *map, size_t *iter, const char **key);
+
+#define git_strmap_foreach(h, kvar, vvar, code) { size_t __i = 0;		\
+	while (git_strmap_iterate((void **) &(vvar), h, &__i, &(kvar)) == 0) {	\
 		code;								\
 	} }
 
-#define git_strmap_foreach_value(h, vvar, code) { size_t __i;			\
-	for (__i = git_strmap_begin(h); __i != git_strmap_end(h); ++__i) {	\
-		if (!git_strmap_has_data(h,__i)) continue;			\
-		(vvar) = git_strmap_value_at(h,__i);				\
+#define git_strmap_foreach_value(h, vvar, code) { size_t __i = 0;		\
+	while (git_strmap_iterate((void **) &(vvar), h, &__i, NULL) == 0) {	\
 		code;								\
 	} }
 
-size_t git_strmap_begin(git_strmap *map);
-size_t git_strmap_end(git_strmap *map);
-
-int git_strmap_next(
-	void **data,
-	size_t *iter,
-	git_strmap *map);
-
 #endif
diff --git a/src/submodule.c b/src/submodule.c
index e3ec885..c54b9df 100644
--- a/src/submodule.c
+++ b/src/submodule.c
@@ -197,12 +197,11 @@ static int load_submodule_names(git_strmap **out, git_repository *repo, git_conf
 	git_config_entry *entry;
 	git_buf buf = GIT_BUF_INIT;
 	git_strmap *names;
-	int rval, isvalid;
-	int error = 0;
+	int isvalid, error;
 
 	*out = NULL;
 
-	if ((error = git_strmap_alloc(&names)) < 0)
+	if ((error = git_strmap_new(&names)) < 0)
 		goto out;
 
 	if ((error = git_config_iterator_glob_new(&iter, cfg, key)) < 0)
@@ -230,8 +229,7 @@ static int load_submodule_names(git_strmap **out, git_repository *repo, git_conf
 		if (!isvalid)
 			continue;
 
-		git_strmap_insert(names, git__strdup(entry->value), git_buf_detach(&buf), &rval);
-		if (rval < 0) {
+		if ((error = git_strmap_set(names, git__strdup(entry->value), git_buf_detach(&buf))) < 0) {
 			git_error_set(GIT_ERROR_NOMEMORY, "error inserting submodule into hash table");
 			error = -1;
 			goto out;
@@ -267,10 +265,9 @@ int git_submodule_lookup(
 	}
 
 	if (repo->submodule_cache != NULL) {
-		size_t pos = git_strmap_lookup_index(repo->submodule_cache, name);
-		if (git_strmap_valid_index(repo->submodule_cache, pos)) {
+		if ((sm = git_strmap_get(repo->submodule_cache, name)) != NULL) {
 			if (out) {
-				*out = git_strmap_value_at(repo->submodule_cache, pos);
+				*out = sm;
 				GIT_REFCOUNT_INC(*out);
 			}
 			return 0;
@@ -395,30 +392,21 @@ static void submodule_free_dup(void *sm)
 
 static int submodule_get_or_create(git_submodule **out, git_repository *repo, git_strmap *map, const char *name)
 {
-	int error = 0;
-	size_t pos;
 	git_submodule *sm = NULL;
+	int error;
 
-	pos = git_strmap_lookup_index(map, name);
-	if (git_strmap_valid_index(map, pos)) {
-		sm = git_strmap_value_at(map, pos);
+	if ((sm = git_strmap_get(map, name)) != NULL)
 		goto done;
-	}
 
 	/* if the submodule doesn't exist yet in the map, create it */
 	if ((error = submodule_alloc(&sm, repo, name)) < 0)
 		return error;
 
-	pos = git_strmap_put(map, sm->name, &error);
-	/* nobody can beat us to adding it */
-	assert(error != 0);
-	if (error < 0) {
+	if ((error = git_strmap_set(map, sm->name, sm)) < 0) {
 		git_submodule_free(sm);
 		return error;
 	}
 
-	git_strmap_set_value_at(map, pos, sm);
-
 done:
 	GIT_REFCOUNT_INC(sm);
 	*out = sm;
@@ -439,26 +427,18 @@ static int submodules_from_index(git_strmap *map, git_index *idx, git_config *cf
 		goto done;
 
 	while (!(error = git_iterator_advance(&entry, i))) {
-		size_t pos = git_strmap_lookup_index(map, entry->path);
 		git_submodule *sm;
 
-		if (git_strmap_valid_index(map, pos)) {
-			sm = git_strmap_value_at(map, pos);
-
+		if ((sm = git_strmap_get(map, entry->path)) != NULL) {
 			if (S_ISGITLINK(entry->mode))
 				submodule_update_from_index_entry(sm, entry);
 			else
 				sm->flags |= GIT_SUBMODULE_STATUS__INDEX_NOT_SUBMODULE;
 		} else if (S_ISGITLINK(entry->mode)) {
-			size_t name_pos;
 			const char *name;
 
-			name_pos = git_strmap_lookup_index(names, entry->path);
-			if (git_strmap_valid_index(names, name_pos)) {
-				name = git_strmap_value_at(names, name_pos);
-			} else {
+			if ((name = git_strmap_get(names, entry->path)) == NULL)
 				name = entry->path;
-			}
 
 			if (!submodule_get_or_create(&sm, git_index_owner(idx), map, name)) {
 				submodule_update_from_index_entry(sm, entry);
@@ -491,26 +471,18 @@ static int submodules_from_head(git_strmap *map, git_tree *head, git_config *cfg
 		goto done;
 
 	while (!(error = git_iterator_advance(&entry, i))) {
-		size_t pos = git_strmap_lookup_index(map, entry->path);
 		git_submodule *sm;
 
-		if (git_strmap_valid_index(map, pos)) {
-			sm = git_strmap_value_at(map, pos);
-
+		if ((sm = git_strmap_get(map, entry->path)) != NULL) {
 			if (S_ISGITLINK(entry->mode))
 				submodule_update_from_head_data(sm, entry->mode, &entry->id);
 			else
 				sm->flags |= GIT_SUBMODULE_STATUS__HEAD_NOT_SUBMODULE;
 		} else if (S_ISGITLINK(entry->mode)) {
-			size_t name_pos;
 			const char *name;
 
-			name_pos = git_strmap_lookup_index(names, entry->path);
-			if (git_strmap_valid_index(names, name_pos)) {
-				name = git_strmap_value_at(names, name_pos);
-			} else {
+			if ((name = git_strmap_get(names, entry->path)) == NULL)
 				name = entry->path;
-			}
 
 			if (!submodule_get_or_create(&sm, git_tree_owner(head), map, name)) {
 				submodule_update_from_head_data(
@@ -618,14 +590,14 @@ int git_submodule_foreach(
 		return -1;
 	}
 
-	if ((error = git_strmap_alloc(&submodules)) < 0)
+	if ((error = git_strmap_new(&submodules)) < 0)
 		return error;
 
 	if ((error = git_submodule__map(repo, submodules)) < 0)
 		goto done;
 
 	if (!(error = git_vector_init(
-			&snapshot, git_strmap_num_entries(submodules), submodule_cmp))) {
+			&snapshot, git_strmap_size(submodules), submodule_cmp))) {
 
 		git_strmap_foreach_value(submodules, sm, {
 			if ((error = git_vector_insert(&snapshot, sm)) < 0)
@@ -1935,7 +1907,6 @@ static int submodule_load_each(const git_config_entry *entry, void *payload)
 {
 	lfc_data *data = payload;
 	const char *namestart, *property;
-	size_t pos;
 	git_strmap *map = data->map;
 	git_buf name = GIT_BUF_INIT;
 	git_submodule *sm;
@@ -1967,8 +1938,7 @@ static int submodule_load_each(const git_config_entry *entry, void *payload)
 	 * a new submodule, load the config and insert it. If it's
 	 * already inserted, we've already loaded it, so we skip.
 	 */
-	pos = git_strmap_lookup_index(map, name.ptr);
-	if (git_strmap_valid_index(map, pos)) {
+	if (git_strmap_exists(map, name.ptr)) {
 		error = 0;
 		goto done;
 	}
@@ -1981,9 +1951,7 @@ static int submodule_load_each(const git_config_entry *entry, void *payload)
 		goto done;
 	}
 
-	git_strmap_insert(map, sm->name, sm, &error);
-	assert(error != 0);
-	if (error < 0)
+	if ((error = git_strmap_set(map, sm->name, sm)) < 0)
 		goto done;
 
 	error = 0;
diff --git a/src/transaction.c b/src/transaction.c
index d8e38d8..5dd7f42 100644
--- a/src/transaction.c
+++ b/src/transaction.c
@@ -84,7 +84,7 @@ int git_transaction_new(git_transaction **out, git_repository *repo)
 		goto on_error;
 	}
 
-	if ((error = git_strmap_alloc(&tx->locks)) < 0) {
+	if ((error = git_strmap_new(&tx->locks)) < 0) {
 		error = -1;
 		goto on_error;
 	}
@@ -119,8 +119,7 @@ int git_transaction_lock_ref(git_transaction *tx, const char *refname)
 	if ((error = git_refdb_lock(&node->payload, tx->db, refname)) < 0)
 		return error;
 
-	git_strmap_insert(tx->locks, node->name, node, &error);
-	if (error < 0)
+	if ((error = git_strmap_set(tx->locks, node->name, node)) < 0)
 		goto cleanup;
 
 	return 0;
@@ -134,16 +133,12 @@ cleanup:
 static int find_locked(transaction_node **out, git_transaction *tx, const char *refname)
 {
 	transaction_node *node;
-	size_t pos;
 
-	pos = git_strmap_lookup_index(tx->locks, refname);
-	if (!git_strmap_valid_index(tx->locks, pos)) {
+	if ((node = git_strmap_get(tx->locks, refname)) == NULL) {
 		git_error_set(GIT_ERROR_REFERENCE, "the specified reference is not locked");
 		return GIT_ENOTFOUND;
 	}
 
-	node = git_strmap_value_at(tx->locks, pos);
-
 	*out = node;
 	return 0;
 }
diff --git a/src/tree.c b/src/tree.c
index 4661804..1231754 100644
--- a/src/tree.c
+++ b/src/tree.c
@@ -344,7 +344,7 @@ unsigned int git_treebuilder_entrycount(git_treebuilder *bld)
 {
 	assert(bld);
 
-	return git_strmap_num_entries(bld->map);
+	return git_strmap_size(bld->map);
 }
 
 static int tree_error(const char *str, const char *path)
@@ -507,8 +507,7 @@ static int append_entry(
 
 	entry->attr = (uint16_t)filemode;
 
-	git_strmap_insert(bld->map, entry->filename, entry, &error);
-	if (error < 0) {
+	if ((error = git_strmap_set(bld->map, entry->filename, entry)) < 0) {
 		git_tree_entry_free(entry);
 		git_error_set(GIT_ERROR_TREE, "failed to append entry %s to the tree builder", filename);
 		return -1;
@@ -688,7 +687,7 @@ int git_treebuilder_new(
 
 	bld->repo = repo;
 
-	if (git_strmap_alloc(&bld->map) < 0) {
+	if (git_strmap_new(&bld->map) < 0) {
 		git__free(bld);
 		return -1;
 	}
@@ -723,24 +722,19 @@ int git_treebuilder_insert(
 {
 	git_tree_entry *entry;
 	int error;
-	size_t pos;
 
 	assert(bld && id && filename);
 
 	if ((error = check_entry(bld->repo, filename, id, filemode)) < 0)
 		return error;
 
-	pos = git_strmap_lookup_index(bld->map, filename);
-	if (git_strmap_valid_index(bld->map, pos)) {
-		entry = git_strmap_value_at(bld->map, pos);
+	if ((entry = git_strmap_get(bld->map, filename)) != NULL) {
 		git_oid_cpy((git_oid *) entry->oid, id);
 	} else {
 		entry = alloc_entry(filename, strlen(filename), id);
 		GIT_ERROR_CHECK_ALLOC(entry);
 
-		git_strmap_insert(bld->map, entry->filename, entry, &error);
-
-		if (error < 0) {
+		if ((error = git_strmap_set(bld->map, entry->filename, entry)) < 0) {
 			git_tree_entry_free(entry);
 			git_error_set(GIT_ERROR_TREE, "failed to insert %s", filename);
 			return -1;
@@ -757,16 +751,8 @@ int git_treebuilder_insert(
 
 static git_tree_entry *treebuilder_get(git_treebuilder *bld, const char *filename)
 {
-	git_tree_entry *entry = NULL;
-	size_t pos;
-
 	assert(bld && filename);
-
-	pos = git_strmap_lookup_index(bld->map, filename);
-	if (git_strmap_valid_index(bld->map, pos))
-		entry = git_strmap_value_at(bld->map, pos);
-
-	return entry;
+	return git_strmap_get(bld->map, filename);
 }
 
 const git_tree_entry *git_treebuilder_get(git_treebuilder *bld, const char *filename)
@@ -811,7 +797,7 @@ int git_treebuilder_write_with_buffer(git_oid *oid, git_treebuilder *bld, git_bu
 
 	git_buf_clear(tree);
 
-	entrycount = git_strmap_num_entries(bld->map);
+	entrycount = git_strmap_size(bld->map);
 	if ((error = git_vector_init(&entries, entrycount, entry_sort_cmp)) < 0)
 		goto out;
 
diff --git a/tests/core/oidmap.c b/tests/core/oidmap.c
index b5f6f99..7f98287 100644
--- a/tests/core/oidmap.c
+++ b/tests/core/oidmap.c
@@ -1,108 +1,127 @@
 #include "clar_libgit2.h"
 #include "oidmap.h"
 
-typedef struct {
+static struct {
 	git_oid oid;
 	size_t extra;
-} oidmap_item;
+} test_oids[0x0FFF];
 
-#define NITEMS 0x0fff
+static git_oidmap *g_map;
 
-void test_core_oidmap__basic(void)
+void test_core_oidmap__initialize(void)
 {
-	git_oidmap *map;
-	oidmap_item items[NITEMS];
 	uint32_t i, j;
+	for (i = 0; i < ARRAY_SIZE(test_oids); ++i) {
+		uint32_t segment = i / 8;
+		int modi = i - (segment * 8);
+
+		test_oids[i].extra = i;
 
-	for (i = 0; i < NITEMS; ++i) {
-		items[i].extra = i;
 		for (j = 0; j < GIT_OID_RAWSZ / 4; ++j) {
-			items[i].oid.id[j * 4    ] = (unsigned char)i;
-			items[i].oid.id[j * 4 + 1] = (unsigned char)(i >> 8);
-			items[i].oid.id[j * 4 + 2] = (unsigned char)(i >> 16);
-			items[i].oid.id[j * 4 + 3] = (unsigned char)(i >> 24);
+			test_oids[i].oid.id[j * 4    ] = (unsigned char)modi;
+			test_oids[i].oid.id[j * 4 + 1] = (unsigned char)(modi >> 8);
+			test_oids[i].oid.id[j * 4 + 2] = (unsigned char)(modi >> 16);
+			test_oids[i].oid.id[j * 4 + 3] = (unsigned char)(modi >> 24);
 		}
-	}
-
-	map = git_oidmap_alloc();
-	cl_assert(map != NULL);
-
-	for (i = 0; i < NITEMS; ++i) {
-		size_t pos;
-		int ret;
-
-		pos = git_oidmap_lookup_index(map, &items[i].oid);
-		cl_assert(!git_oidmap_valid_index(map, pos));
-
-		pos = git_oidmap_put(map, &items[i].oid, &ret);
-		cl_assert(ret != 0);
 
-		git_oidmap_set_value_at(map, pos, &items[i]);
+		test_oids[i].oid.id[ 8] = (unsigned char)i;
+		test_oids[i].oid.id[ 9] = (unsigned char)(i >> 8);
+		test_oids[i].oid.id[10] = (unsigned char)(i >> 16);
+		test_oids[i].oid.id[11] = (unsigned char)(i >> 24);
 	}
 
+	cl_git_pass(git_oidmap_new(&g_map));
+}
 
-	for (i = 0; i < NITEMS; ++i) {
-		size_t pos;
+void test_core_oidmap__cleanup(void)
+{
+	git_oidmap_free(g_map);
+}
 
-		pos = git_oidmap_lookup_index(map, &items[i].oid);
-		cl_assert(git_oidmap_valid_index(map, pos));
+void test_core_oidmap__basic(void)
+{
+	size_t i;
 
-		cl_assert_equal_p(git_oidmap_value_at(map, pos), &items[i]);
+	for (i = 0; i < ARRAY_SIZE(test_oids); ++i) {
+		cl_assert(!git_oidmap_exists(g_map, &test_oids[i].oid));
+		cl_git_pass(git_oidmap_set(g_map, &test_oids[i].oid, &test_oids[i]));
 	}
 
-	git_oidmap_free(map);
+	for (i = 0; i < ARRAY_SIZE(test_oids); ++i) {
+		cl_assert(git_oidmap_exists(g_map, &test_oids[i].oid));
+		cl_assert_equal_p(git_oidmap_get(g_map, &test_oids[i].oid), &test_oids[i]);
+	}
 }
 
 void test_core_oidmap__hash_collision(void)
 {
-	git_oidmap *map;
-	oidmap_item items[NITEMS];
-	uint32_t i, j;
-
-	for (i = 0; i < NITEMS; ++i) {
-		uint32_t segment = i / 8;
-		int modi = i - (segment * 8);
-
-		items[i].extra = i;
+	size_t i;
 
-		for (j = 0; j < GIT_OID_RAWSZ / 4; ++j) {
-			items[i].oid.id[j * 4    ] = (unsigned char)modi;
-			items[i].oid.id[j * 4 + 1] = (unsigned char)(modi >> 8);
-			items[i].oid.id[j * 4 + 2] = (unsigned char)(modi >> 16);
-			items[i].oid.id[j * 4 + 3] = (unsigned char)(modi >> 24);
-		}
+	for (i = 0; i < ARRAY_SIZE(test_oids); ++i) {
+		cl_assert(!git_oidmap_exists(g_map, &test_oids[i].oid));
+		cl_git_pass(git_oidmap_set(g_map, &test_oids[i].oid, &test_oids[i]));
+	}
 
-		items[i].oid.id[ 8] = (unsigned char)i;
-		items[i].oid.id[ 9] = (unsigned char)(i >> 8);
-		items[i].oid.id[10] = (unsigned char)(i >> 16);
-		items[i].oid.id[11] = (unsigned char)(i >> 24);
+	for (i = 0; i < ARRAY_SIZE(test_oids); ++i) {
+		cl_assert(git_oidmap_exists(g_map, &test_oids[i].oid));
+		cl_assert_equal_p(git_oidmap_get(g_map, &test_oids[i].oid), &test_oids[i]);
 	}
+}
 
-	map = git_oidmap_alloc();
-	cl_assert(map != NULL);
+void test_core_oidmap__get_succeeds_with_existing_keys(void)
+{
+	size_t i;
 
-	for (i = 0; i < NITEMS; ++i) {
-		size_t pos;
-		int ret;
+	for (i = 0; i < ARRAY_SIZE(test_oids); ++i)
+		cl_git_pass(git_oidmap_set(g_map, &test_oids[i].oid, &test_oids[i]));
 
-		pos = git_oidmap_lookup_index(map, &items[i].oid);
-		cl_assert(!git_oidmap_valid_index(map, pos));
+	for (i = 0; i < ARRAY_SIZE(test_oids); ++i)
+		cl_assert_equal_p(git_oidmap_get(g_map, &test_oids[i].oid), &test_oids[i]);
+}
 
-		pos = git_oidmap_put(map, &items[i].oid, &ret);
-		cl_assert(ret != 0);
+void test_core_oidmap__get_fails_with_nonexisting_key(void)
+{
+	size_t i;
 
-		git_oidmap_set_value_at(map, pos, &items[i]);
-	}
+	/* Do _not_ add last OID to verify that we cannot look it up */
+	for (i = 0; i < ARRAY_SIZE(test_oids) - 1; ++i)
+		cl_git_pass(git_oidmap_set(g_map, &test_oids[i].oid, &test_oids[i]));
+
+	cl_assert_equal_p(git_oidmap_get(g_map, &test_oids[ARRAY_SIZE(test_oids) - 1].oid), NULL);
+}
 
+void test_core_oidmap__setting_oid_persists(void)
+{
+	git_oid oids[] = {
+	    {{ 0x01 }},
+	    {{ 0x02 }},
+	    {{ 0x03 }}
+	};
+
+	cl_git_pass(git_oidmap_set(g_map, &oids[0], "one"));
+	cl_git_pass(git_oidmap_set(g_map, &oids[1], "two"));
+	cl_git_pass(git_oidmap_set(g_map, &oids[2], "three"));
+
+	cl_assert_equal_s(git_oidmap_get(g_map, &oids[0]), "one");
+	cl_assert_equal_s(git_oidmap_get(g_map, &oids[1]), "two");
+	cl_assert_equal_s(git_oidmap_get(g_map, &oids[2]), "three");
+}
 
-	for (i = 0; i < NITEMS; ++i) {
-		size_t pos;
+void test_core_oidmap__setting_existing_key_updates(void)
+{
+	git_oid oids[] = {
+	    {{ 0x01 }},
+	    {{ 0x02 }},
+	    {{ 0x03 }}
+	};
 
-		pos = git_oidmap_lookup_index(map, &items[i].oid);
-		cl_assert(git_oidmap_valid_index(map, pos));
+	cl_git_pass(git_oidmap_set(g_map, &oids[0], "one"));
+	cl_git_pass(git_oidmap_set(g_map, &oids[1], "two"));
+	cl_git_pass(git_oidmap_set(g_map, &oids[2], "three"));
+	cl_assert_equal_i(git_oidmap_size(g_map), 3);
 
-		cl_assert_equal_p(git_oidmap_value_at(map, pos), &items[i]);
-	}
+	cl_git_pass(git_oidmap_set(g_map, &oids[1], "other"));
+	cl_assert_equal_i(git_oidmap_size(g_map), 3);
 
-	git_oidmap_free(map);
+	cl_assert_equal_s(git_oidmap_get(g_map, &oids[1]), "other");
 }
diff --git a/tests/core/strmap.c b/tests/core/strmap.c
index 64f5164..ba118ae 100644
--- a/tests/core/strmap.c
+++ b/tests/core/strmap.c
@@ -1,11 +1,11 @@
 #include "clar_libgit2.h"
 #include "strmap.h"
 
-git_strmap *g_table;
+static git_strmap *g_table;
 
 void test_core_strmap__initialize(void)
 {
-	cl_git_pass(git_strmap_alloc(&g_table));
+	cl_git_pass(git_strmap_new(&g_table));
 	cl_assert(g_table != NULL);
 }
 
@@ -16,12 +16,12 @@ void test_core_strmap__cleanup(void)
 
 void test_core_strmap__0(void)
 {
-	cl_assert(git_strmap_num_entries(g_table) == 0);
+	cl_assert(git_strmap_size(g_table) == 0);
 }
 
-static void insert_strings(git_strmap *table, int count)
+static void insert_strings(git_strmap *table, size_t count)
 {
-	int i, j, over, err;
+	size_t i, j, over;
 	char *str;
 
 	for (i = 0; i < count; ++i) {
@@ -34,17 +34,16 @@ static void insert_strings(git_strmap *table, int count)
 		for (j = 0, over = i / 26; over > 0; j++, over = over / 26)
 			str[j] = 'A' + (over % 26);
 
-		git_strmap_insert(table, str, str, &err);
-		cl_assert(err >= 0);
+		cl_git_pass(git_strmap_set(table, str, str));
 	}
 
-	cl_assert((int)git_strmap_num_entries(table) == count);
+	cl_assert_equal_i(git_strmap_size(table), count);
 }
 
-void test_core_strmap__1(void)
+void test_core_strmap__inserted_strings_can_be_retrieved(void)
 {
-	int i;
 	char *str;
+	int i;
 
 	insert_strings(g_table, 20);
 
@@ -58,41 +57,134 @@ void test_core_strmap__1(void)
 	cl_assert(i == 20);
 }
 
-void test_core_strmap__2(void)
+void test_core_strmap__deleted_entry_cannot_be_retrieved(void)
 {
-	size_t pos;
-	int i;
 	char *str;
+	int i;
 
 	insert_strings(g_table, 20);
 
-	cl_assert(git_strmap_exists(g_table, "aaaaaaaaa"));
-	cl_assert(git_strmap_exists(g_table, "ggggggggg"));
-	cl_assert(!git_strmap_exists(g_table, "aaaaaaaab"));
-	cl_assert(!git_strmap_exists(g_table, "abcdefghi"));
-
 	cl_assert(git_strmap_exists(g_table, "bbbbbbbbb"));
-	pos = git_strmap_lookup_index(g_table, "bbbbbbbbb");
-	cl_assert(git_strmap_valid_index(g_table, pos));
-	cl_assert_equal_s(git_strmap_value_at(g_table, pos), "bbbbbbbbb");
-	free(git_strmap_value_at(g_table, pos));
-	git_strmap_delete_at(g_table, pos);
+	str = git_strmap_get(g_table, "bbbbbbbbb");
+	cl_assert_equal_s(str, "bbbbbbbbb");
+	cl_git_pass(git_strmap_delete(g_table, "bbbbbbbbb"));
+	free(str);
 
 	cl_assert(!git_strmap_exists(g_table, "bbbbbbbbb"));
 
 	i = 0;
 	git_strmap_foreach_value(g_table, str, { i++; free(str); });
-	cl_assert(i == 19);
+	cl_assert_equal_i(i, 19);
 }
 
-void test_core_strmap__3(void)
+void test_core_strmap__inserting_many_keys_succeeds(void)
 {
-	int i;
 	char *str;
+	int i;
 
 	insert_strings(g_table, 10000);
 
 	i = 0;
 	git_strmap_foreach_value(g_table, str, { i++; free(str); });
-	cl_assert(i == 10000);
+	cl_assert_equal_i(i, 10000);
+}
+
+void test_core_strmap__get_succeeds_with_existing_entries(void)
+{
+	const char *keys[] = { "foo", "bar", "gobble" };
+	char *values[] = { "oof", "rab", "elbbog" };
+	size_t i;
+
+	for (i = 0; i < ARRAY_SIZE(keys); i++)
+		cl_git_pass(git_strmap_set(g_table, keys[i], values[i]));
+
+	cl_assert_equal_s(git_strmap_get(g_table, "foo"), "oof");
+	cl_assert_equal_s(git_strmap_get(g_table, "bar"), "rab");
+	cl_assert_equal_s(git_strmap_get(g_table, "gobble"), "elbbog");
+}
+
+void test_core_strmap__get_returns_null_on_nonexisting_key(void)
+{
+	const char *keys[] = { "foo", "bar", "gobble" };
+	char *values[] = { "oof", "rab", "elbbog" };
+	size_t i;
+
+	for (i = 0; i < ARRAY_SIZE(keys); i++)
+		cl_git_pass(git_strmap_set(g_table, keys[i], values[i]));
+
+	cl_assert_equal_p(git_strmap_get(g_table, "other"), NULL);
+}
+
+void test_core_strmap__set_persists_key(void)
+{
+	cl_git_pass(git_strmap_set(g_table, "foo", "oof"));
+	cl_assert_equal_s(git_strmap_get(g_table, "foo"), "oof");
+}
+
+void test_core_strmap__set_persists_multpile_keys(void)
+{
+	cl_git_pass(git_strmap_set(g_table, "foo", "oof"));
+	cl_git_pass(git_strmap_set(g_table, "bar", "rab"));
+	cl_assert_equal_s(git_strmap_get(g_table, "foo"), "oof");
+	cl_assert_equal_s(git_strmap_get(g_table, "bar"), "rab");
+}
+
+void test_core_strmap__set_updates_existing_key(void)
+{
+	cl_git_pass(git_strmap_set(g_table, "foo", "oof"));
+	cl_git_pass(git_strmap_set(g_table, "bar", "rab"));
+	cl_git_pass(git_strmap_set(g_table, "gobble", "elbbog"));
+	cl_assert_equal_i(git_strmap_size(g_table), 3);
+
+	cl_git_pass(git_strmap_set(g_table, "foo", "other"));
+	cl_assert_equal_i(git_strmap_size(g_table), 3);
+
+	cl_assert_equal_s(git_strmap_get(g_table, "foo"), "other");
+}
+
+void test_core_strmap__iteration(void)
+{
+	struct {
+		char *key;
+		char *value;
+		int seen;
+	} entries[] = {
+		{ "foo", "oof" },
+		{ "bar", "rab" },
+		{ "gobble", "elbbog" },
+	};
+	const char *key, *value;
+	size_t i, n;
+
+	for (i = 0; i < ARRAY_SIZE(entries); i++)
+		cl_git_pass(git_strmap_set(g_table, entries[i].key, entries[i].value));
+
+	i = 0, n = 0;
+	while (git_strmap_iterate((void **) &value, g_table, &i, &key) == 0) {
+		size_t j;
+
+		for (j = 0; j < ARRAY_SIZE(entries); j++) {
+			if (strcmp(entries[j].key, key))
+				continue;
+
+			cl_assert_equal_i(entries[j].seen, 0);
+			cl_assert_equal_s(entries[j].value, value);
+			entries[j].seen++;
+			break;
+		}
+
+		n++;
+	}
+
+	for (i = 0; i < ARRAY_SIZE(entries); i++)
+		cl_assert_equal_i(entries[i].seen, 1);
+
+	cl_assert_equal_i(n, ARRAY_SIZE(entries));
+}
+
+void test_core_strmap__iterating_empty_map_stops_immediately(void)
+{
+	size_t i = 0;
+
+	cl_git_fail_with(git_strmap_iterate(NULL, g_table, &i, NULL), GIT_ITEROVER);
 }
diff --git a/tests/pack/sharing.c b/tests/pack/sharing.c
index f6f78ca..eaf7686 100644
--- a/tests/pack/sharing.c
+++ b/tests/pack/sharing.c
@@ -24,13 +24,13 @@ void test_pack_sharing__open_two_repos(void)
 	cl_git_pass(git_object_lookup(&obj2, repo2, &id, GIT_OBJECT_ANY));
 
 	pos = 0;
-	while ((error = git_strmap_next(&data, &pos, git__pack_cache)) == 0) {
+	while ((error = git_strmap_iterate(&data, git__pack_cache, &pos, NULL)) == 0) {
 		struct git_pack_file *pack = (struct git_pack_file *) data;
 
 		cl_assert_equal_i(2, pack->refcount.val);
 	}
 
-	cl_assert_equal_i(3, git_strmap_num_entries(git__pack_cache));
+	cl_assert_equal_i(3, git_strmap_size(git__pack_cache));
 
 	git_object_free(obj1);
 	git_object_free(obj2);
@@ -38,5 +38,5 @@ void test_pack_sharing__open_two_repos(void)
 	git_repository_free(repo2);
 
 	/* we don't want to keep the packs open after the repos go away */
-	cl_assert_equal_i(0, git_strmap_num_entries(git__pack_cache));
+	cl_assert_equal_i(0, git_strmap_size(git__pack_cache));
 }