thodg/got

diff --git a/got/Makefile b/got/Makefile
index 8ebd171..a0db6ed 100644
--- a/got/Makefile
+++ b/got/Makefile
@@ -3,9 +3,8 @@
 PROG=		got
 SRCS=		got.c blame.c commit_graph.c delta.c diff.c diffoffset.c \
 		diffreg.c error.c fileindex.c object.c object_cache.c \
-		object_idcache.c object_idset.c object_parse.c opentemp.c \
-		path.c pack.c privsep.c reference.c repository.c sha1.c \
-		worktree.c inflate.c
+		object_idset.c object_parse.c opentemp.c path.c pack.c \
+		privsep.c reference.c repository.c sha1.c worktree.c inflate.c
 
 CPPFLAGS = -I${.CURDIR}/../include -I${.CURDIR}/../lib \
 	-DGOT_LIBEXECDIR=${GOT_LIBEXECDIR}
diff --git a/lib/got_lib_object_cache.h b/lib/got_lib_object_cache.h
index d574268..067f6f0 100644
--- a/lib/got_lib_object_cache.h
+++ b/lib/got_lib_object_cache.h
@@ -31,7 +31,7 @@ struct got_object_cache_entry {
 
 struct got_object_cache {
 	enum got_object_cache_type type;
-	struct got_object_idcache *idcache;
+	struct got_object_idset *idset;
 	size_t size;
 	int cache_searches;
 	int cache_hit;
diff --git a/lib/object.c b/lib/object.c
index fef5ccd..166807b 100644
--- a/lib/object.c
+++ b/lib/object.c
@@ -56,13 +56,6 @@
 #define	MIN(_a,_b) ((_a) < (_b) ? (_a) : (_b))
 #endif
 
-int
-got_object_id_cmp(const struct got_object_id *id1,
-    const struct got_object_id *id2)
-{
-	return memcmp(id1->sha1, id2->sha1, SHA1_DIGEST_LENGTH);
-}
-
 struct got_object_id *
 got_object_id_dup(struct got_object_id *id1)
 {
diff --git a/lib/object_cache.c b/lib/object_cache.c
index f965839..1433b27 100644
--- a/lib/object_cache.c
+++ b/lib/object_cache.c
@@ -29,7 +29,7 @@
 #include "got_lib_delta.h"
 #include "got_lib_inflate.h"
 #include "got_lib_object.h"
-#include "got_lib_object_idcache.h"
+#include "got_lib_object_idset.h"
 #include "got_lib_object_cache.h"
 
 #define GOT_OBJECT_CACHE_SIZE_OBJ	256
@@ -40,27 +40,24 @@ const struct got_error *
 got_object_cache_init(struct got_object_cache *cache,
     enum got_object_cache_type type)
 {
-	size_t size;
-
 	memset(cache, 0, sizeof(*cache));
 
+	cache->idset = got_object_idset_alloc();
+	if (cache->idset == NULL)
+		return got_error_from_errno();
+
+	cache->type = type;
 	switch (type) {
 	case GOT_OBJECT_CACHE_TYPE_OBJ:
-		size = GOT_OBJECT_CACHE_SIZE_OBJ;
+		cache->size = GOT_OBJECT_CACHE_SIZE_OBJ;
 		break;
 	case GOT_OBJECT_CACHE_TYPE_TREE:
-		size = GOT_OBJECT_CACHE_SIZE_TREE;
+		cache->size = GOT_OBJECT_CACHE_SIZE_TREE;
 		break;
 	case GOT_OBJECT_CACHE_TYPE_COMMIT:
-		size = GOT_OBJECT_CACHE_SIZE_COMMIT;
+		cache->size = GOT_OBJECT_CACHE_SIZE_COMMIT;
 		break;
 	}
-
-	cache->idcache = got_object_idcache_alloc(size);
-	if (cache->idcache == NULL)
-		return got_error_from_errno();
-	cache->type = type;
-	cache->size = size;
 	return NULL;
 }
 
@@ -71,10 +68,10 @@ got_object_cache_add(struct got_object_cache *cache, struct got_object_id *id, v
 	struct got_object_cache_entry *ce;
 	int nelem;
 
-	nelem = got_object_idcache_num_elements(cache->idcache);
+	nelem = got_object_idset_num_elements(cache->idset);
 	if (nelem >= cache->size) {
-		err = got_object_idcache_remove_one((void **)&ce,
-		    cache->idcache, id);
+		err = got_object_idset_remove((void **)&ce,
+		    cache->idset, NULL);
 		if (err)
 			return err;
 		switch (cache->type) {
@@ -108,7 +105,7 @@ got_object_cache_add(struct got_object_cache *cache, struct got_object_id *id, v
 		break;
 	}
 
-	err = got_object_idcache_add(cache->idcache, id, ce);
+	err = got_object_idset_add(cache->idset, id, ce);
 	if (err) {
 		if (err->code == GOT_ERR_OBJ_EXISTS) {
 			free(ce);
@@ -124,7 +121,7 @@ got_object_cache_get(struct got_object_cache *cache, struct got_object_id *id)
 	struct got_object_cache_entry *ce;
 
 	cache->cache_searches++;
-	ce = got_object_idcache_get(cache->idcache, id);
+	ce = got_object_idset_get(cache->idset, id);
 	if (ce) {
 		cache->cache_hit++;
 		switch (cache->type) {
@@ -147,7 +144,7 @@ print_cache_stats(struct got_object_cache *cache, const char *name)
 {
 	fprintf(stderr, "%s: %s cache: %d elements, %d searches, %d hits, "
 	    "%d missed, %d evicted\n", getprogname(), name,
-	    got_object_idcache_num_elements(cache->idcache),
+	    got_object_idset_num_elements(cache->idset),
 	    cache->cache_searches, cache->cache_hit,
 	    cache->cache_miss, cache->cache_evict);
 }
@@ -207,12 +204,12 @@ got_object_cache_close(struct got_object_cache *cache)
 		break;
 	}
 
-	got_object_idcache_for_each(cache->idcache, check_refcount, cache);
+	got_object_idset_for_each(cache->idset, check_refcount, cache);
 #endif
 
-	if (cache->idcache) {
-		got_object_idcache_free(cache->idcache);
-		cache->idcache = NULL;
+	if (cache->idset) {
+		got_object_idset_free(cache->idset);
+		cache->idset = NULL;
 	}
 	cache->size = 0;
 }
diff --git a/lib/object_idcache.c b/lib/object_idcache.c
deleted file mode 100644
index 3206b9e..0000000
--- a/lib/object_idcache.c
+++ /dev/null
@@ -1,200 +0,0 @@
-/*
- * Copyright (c) 2018 Stefan Sperling <stsp@openbsd.org>
- *
- * Permission to use, copy, modify, and distribute this software for any
- * purpose with or without fee is hereby granted, provided that the above
- * copyright notice and this permission notice appear in all copies.
- *
- * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
- * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
- * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
- * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
- * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
- * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
- * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
- */
-
-#include <sys/queue.h>
-
-#include <stdlib.h>
-#include <string.h>
-#include <sha1.h>
-#include <stdio.h>
-#include <zlib.h>
-#include <limits.h>
-#include <time.h>
-
-#include "got_object.h"
-#include "got_error.h"
-
-#include "got_lib_delta.h"
-#include "got_lib_inflate.h"
-#include "got_lib_object.h"
-#include "got_lib_object_idcache.h"
-
-#ifndef nitems
-#define nitems(_a) (sizeof(_a) / sizeof((_a)[0]))
-#endif
-
-struct got_object_idcache_element {
-	TAILQ_ENTRY(got_object_idcache_element) entry;
-	struct got_object_id id;
-	void *data;	/* API user data */
-};
-
-TAILQ_HEAD(got_object_idcache_head, got_object_idcache_element);
-
-struct got_object_idcache {
-	/*
-	 * The cache is implemented as a collection of 256 lists.
-	 * The value of the first byte of an object ID determines
-	 * which of these lists an object ID is stored in.
-	 */
-	struct got_object_idcache_head entries[0xff + 1];
-	int nelem[0xff + 1];
-	int totelem;
-	int maxelem;
-};
-
-struct got_object_idcache *
-got_object_idcache_alloc(int maxelem)
-{
-	struct got_object_idcache *cache;
-	int i;
-
-	cache = calloc(1, sizeof(*cache));
-	if (cache == NULL)
-		return NULL;
-
-	for (i = 0; i < nitems(cache->entries); i++)
-		TAILQ_INIT(&cache->entries[i]);
-	cache->maxelem = maxelem;
-	return cache;
-}
-
-void
-got_object_idcache_free(struct got_object_idcache *cache)
-{
-	struct got_object_idcache_element *entry;
-	int i;
-
-	for (i = 0; i < nitems(cache->entries); i++) {
-		while (!TAILQ_EMPTY(&cache->entries[i])) {
-			entry = TAILQ_FIRST(&cache->entries[i]);
-			TAILQ_REMOVE(&cache->entries[i], entry, entry);
-			/* User data should be freed by caller. */
-			free(entry);
-		}
-	}
-	free(cache);
-}
-
-const struct got_error *
-got_object_idcache_add(struct got_object_idcache *cache,
-    struct got_object_id *id, void *data)
-{
-	struct got_object_idcache_element *entry;
-	uint8_t i = id->sha1[0];
-
-	if (cache->totelem >= cache->maxelem)
-		return got_error(GOT_ERR_NO_SPACE);
-
-	entry = malloc(sizeof(*entry));
-	if (entry == NULL)
-		return got_error_from_errno();
-
-	memcpy(&entry->id, id, sizeof(entry->id));
-	entry->data = data;
-
-	TAILQ_INSERT_HEAD(&cache->entries[i], entry, entry);
-	cache->nelem[i]++;
-	cache->totelem++;
-	return NULL;
-}
-
-void *
-got_object_idcache_get(struct got_object_idcache *cache, struct got_object_id *id)
-{
-	struct got_object_idcache_element *entry;
-	uint8_t i = id->sha1[0];
-
-	TAILQ_FOREACH(entry, &cache->entries[i], entry) {
-		if (memcmp(&entry->id.sha1, id->sha1, SHA1_DIGEST_LENGTH) != 0)
-			continue;
-		if (entry != TAILQ_FIRST(&cache->entries[i])) {
-			TAILQ_REMOVE(&cache->entries[i], entry, entry);
-			TAILQ_INSERT_HEAD(&cache->entries[i], entry, entry);
-		}
-		return entry->data;
-	}
-
-	return NULL;
-}
-
-const struct got_error *
-got_object_idcache_remove_one(void **data, struct got_object_idcache *cache,
-    struct got_object_id *id)
-{
-	struct got_object_idcache_element *entry;
-	uint8_t idx = id->sha1[0];
-
-	if (data)
-		*data = NULL;
-
-	if (cache->totelem == 0)
-		return got_error(GOT_ERR_NO_OBJ);
-
-	if (cache->nelem[idx] == 0) {
-		/* Remove an element from the longest list. */
-		int i, maxelem = cache->nelem[0];
-		idx = 0;
-		for (i = 0; i < nitems(cache->entries); i++) {
-			if (maxelem < cache->nelem[i]) {
-				idx = i;
-				maxelem = cache->nelem[i];
-			}
-		}
-	}
-
-	entry = TAILQ_LAST(&cache->entries[idx], got_object_idcache_head);
-	TAILQ_REMOVE(&cache->entries[idx], entry, entry);
-	if (data)
-		*data = entry->data;
-	free(entry);
-	cache->nelem[idx]--;
-	cache->totelem--;
-	return NULL;
-}
-
-int
-got_object_idcache_contains(struct got_object_idcache *cache,
-    struct got_object_id *id)
-{
-	struct got_object_idcache_element *entry;
-	uint8_t i = id->sha1[0];
-
-	TAILQ_FOREACH(entry, &cache->entries[i], entry) {
-		if (memcmp(&entry->id.sha1, id->sha1, SHA1_DIGEST_LENGTH) == 0)
-			return 1;
-	}
-
-	return 0;
-}
-
-void got_object_idcache_for_each(struct got_object_idcache *cache,
-    void (*cb)(struct got_object_id *, void *, void *), void *arg)
-{
-	struct got_object_idcache_element *entry;
-	int i;
-
-	for (i = 0; i < nitems(cache->entries); i++) {
-		TAILQ_FOREACH(entry, &cache->entries[i], entry)
-			cb(&entry->id, entry->data, arg);
-	}
-}
-
-int
-got_object_idcache_num_elements(struct got_object_idcache *cache)
-{
-	return cache->totelem;
-}
diff --git a/lib/object_idset.c b/lib/object_idset.c
index 09fe0cf..a3873c0 100644
--- a/lib/object_idset.c
+++ b/lib/object_idset.c
@@ -150,7 +150,10 @@ got_object_idset_remove(void **data, struct got_object_idset *set,
 	if (set->totelem == 0)
 		return got_error(GOT_ERR_NO_OBJ);
 
-	entry = find_element(set, id);
+	if (id == NULL)
+		entry = RBT_ROOT(got_object_idset_tree, &set->entries);
+	else
+		entry = find_element(set, id);
 	if (entry == NULL)
 		return got_error(GOT_ERR_NO_OBJ);
 
diff --git a/lib/object_parse.c b/lib/object_parse.c
index 6421da7..6ec3f47 100644
--- a/lib/object_parse.c
+++ b/lib/object_parse.c
@@ -62,6 +62,13 @@
 #define GOT_COMMIT_TAG_AUTHOR		"author "
 #define GOT_COMMIT_TAG_COMMITTER	"committer "
 
+int
+got_object_id_cmp(const struct got_object_id *id1,
+    const struct got_object_id *id2)
+{
+	return memcmp(id1->sha1, id2->sha1, SHA1_DIGEST_LENGTH);
+}
+
 const struct got_error *
 got_object_qid_alloc_partial(struct got_object_qid **qid)
 {
diff --git a/libexec/got-read-pack/Makefile b/libexec/got-read-pack/Makefile
index 1d11b5c..a583c3b 100644
--- a/libexec/got-read-pack/Makefile
+++ b/libexec/got-read-pack/Makefile
@@ -2,7 +2,7 @@
 
 PROG=		got-read-pack
 SRCS=		got-read-pack.c delta.c error.c inflate.c object_cache.c \
-		object_idcache.c object_parse.c opentemp.c pack.c path.c \
+		object_idset.c object_parse.c opentemp.c pack.c path.c \
 		privsep.c sha1.c
 
 CPPFLAGS = -I${.CURDIR}/../../include -I${.CURDIR}/../../lib
diff --git a/regress/idset/Makefile b/regress/idset/Makefile
index f2a6a6e..622918d 100644
--- a/regress/idset/Makefile
+++ b/regress/idset/Makefile
@@ -3,7 +3,7 @@
 PROG = idset_test
 SRCS = error.c object.c privsep.c sha1.c pack.c inflate.c path.c opentemp.c \
 	delta.c repository.c reference.c worktree.c fileindex.c object_cache.c \
-	object_idcache.c object_idset.c object_parse.c idset_test.c
+	object_idset.c object_parse.c idset_test.c
 
 CPPFLAGS = -I${.CURDIR}/../../include -I${.CURDIR}/../../lib
 LDADD = -lutil -lz
diff --git a/regress/repository/Makefile b/regress/repository/Makefile
index a1659fd..5da0a61 100644
--- a/regress/repository/Makefile
+++ b/regress/repository/Makefile
@@ -2,9 +2,9 @@
 
 PROG = repository_test
 SRCS = path.c repository.c error.c reference.c object.c object_cache.c \
-	object_idcache.c object_idset.c object_parse.c opentemp.c sha1.c \
-	diff.c diffreg.c pack.c privsep.c delta.c fileindex.c worktree.c \
-	inflate.c repository_test.c
+	object_idset.c object_parse.c opentemp.c sha1.c diff.c diffreg.c \
+	pack.c privsep.c delta.c fileindex.c worktree.c inflate.c \
+	repository_test.c
 
 CPPFLAGS = -I${.CURDIR}/../../include -I${.CURDIR}/../../lib \
 	-DGOT_LIBEXECDIR=${GOT_LIBEXECDIR}
diff --git a/regress/worktree/Makefile b/regress/worktree/Makefile
index 325c30c..967be5e 100644
--- a/regress/worktree/Makefile
+++ b/regress/worktree/Makefile
@@ -1,9 +1,9 @@
 .PATH:${.CURDIR}/../../lib
 
 PROG = worktree_test
-SRCS = worktree.c repository.c object.c object_cache.c object_idcache.c \
-	object_idset.c object_parse.c opentemp.c path.c error.c reference.c \
-	sha1.c pack.c privsep.c delta.c inflate.c fileindex.c worktree_test.c
+SRCS = worktree.c repository.c object.c object_cache.c object_idset.c \
+	object_parse.c opentemp.c path.c error.c reference.c sha1.c \
+	pack.c privsep.c delta.c inflate.c fileindex.c worktree_test.c
 
 CPPFLAGS = -I${.CURDIR}/../../include -I${.CURDIR}/../../lib \
 	-DGOT_LIBEXECDIR=${GOT_LIBEXECDIR}
diff --git a/tog/Makefile b/tog/Makefile
index 8b38788..72f8d6d 100644
--- a/tog/Makefile
+++ b/tog/Makefile
@@ -3,9 +3,9 @@
 PROG=		tog
 SRCS=		tog.c blame.c commit_graph.c delta.c diff.c diffoffset.c \
 		diffreg.c error.c fileindex.c object.c object_cache.c \
-		object_idcache.c object_idset.c object_parse.c opentemp.c \
-		path.c pack.c privsep.c reference.c repository.c sha1.c \
-		worktree.c utf8.c inflate.c
+		object_idset.c object_parse.c opentemp.c path.c pack.c \
+		privsep.c reference.c repository.c sha1.c worktree.c \
+		utf8.c inflate.c
 
 CPPFLAGS = -I${.CURDIR}/../include -I${.CURDIR}/../lib \
 	-DGOT_LIBEXECDIR=${GOT_LIBEXECDIR}