thodg/got

diff --git a/got/Makefile b/got/Makefile
index 4ca05ec..8c76a73 100644
--- a/got/Makefile
+++ b/got/Makefile
@@ -2,8 +2,8 @@
 
 PROG=		got
 SRCS=		got.c blame.c commit_graph.c delta.c diff.c diffreg.c error.c \
-		fileindex.c object.c object_idset.c opentemp.c path.c \
-		pack.c privsep.c reference.c repository.c sha1.c \
+		fileindex.c object.c object_idcache.c object_idset.c opentemp.c \
+		path.c pack.c privsep.c reference.c repository.c sha1.c \
 		worktree.c zbuf.c
 
 CPPFLAGS = -I${.CURDIR}/../include -I${.CURDIR}/../lib
diff --git a/lib/got_lib_object_idcache.h b/lib/got_lib_object_idcache.h
new file mode 100644
index 0000000..7920666
--- /dev/null
+++ b/lib/got_lib_object_idcache.h
@@ -0,0 +1,31 @@
+/*
+ * 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.
+ */
+
+struct got_object_idcache;
+
+struct got_object_idcache *got_object_idcache_alloc(int);
+void got_object_idcache_free(struct got_object_idcache *);
+
+const struct got_error *got_object_idcache_add(struct got_object_idcache *,
+    struct got_object_id *, void *);
+void *got_object_idcache_get(struct got_object_idcache *, struct got_object_id *);
+const struct got_error *got_object_idcache_remove_least_used(void **,
+    struct got_object_idcache *);
+int got_object_idcache_contains(struct got_object_idcache *,
+    struct got_object_id *);
+void got_object_idcache_for_each(struct got_object_idcache *,
+    void (*cb)(struct got_object_id *, void *, void *), void *);
+int got_object_idcache_num_elements(struct got_object_idcache *);
diff --git a/lib/got_lib_repository.h b/lib/got_lib_repository.h
index 203dd23..24122e8 100644
--- a/lib/got_lib_repository.h
+++ b/lib/got_lib_repository.h
@@ -38,7 +38,7 @@ struct got_object_cache_entry {
 
 struct got_object_cache {
 	enum got_object_chache_type type;
-	struct got_object_idset *set;
+	struct got_object_idcache *idcache;
 	size_t size;
 	int cache_hit;
 	int cache_miss;
diff --git a/lib/object_idcache.c b/lib/object_idcache.c
new file mode 100644
index 0000000..2c206be
--- /dev/null
+++ b/lib/object_idcache.c
@@ -0,0 +1,170 @@
+/*
+ * 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_zbuf.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 {
+	struct got_object_idcache_head entries;
+	int nelem;
+	int maxelem;
+};
+
+struct got_object_idcache *
+got_object_idcache_alloc(int maxelem)
+{
+	struct got_object_idcache *cache;
+
+	cache = calloc(1, sizeof(*cache));
+	if (cache == NULL)
+		return NULL;
+
+	TAILQ_INIT(&cache->entries);
+	cache->maxelem = maxelem;
+	return cache;
+}
+
+void
+got_object_idcache_free(struct got_object_idcache *cache)
+{
+	struct got_object_idcache_element *entry;
+
+	while (!TAILQ_EMPTY(&cache->entries)) {
+		entry = TAILQ_FIRST(&cache->entries);
+		TAILQ_REMOVE(&cache->entries, 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;
+
+	if (cache->nelem >= cache->maxelem) {
+		entry = TAILQ_LAST(&cache->entries, got_object_idcache_head);
+		TAILQ_REMOVE(&cache->entries, entry, entry);
+		cache->nelem--;
+	}
+
+	entry = calloc(1, 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, entry, entry);
+	cache->nelem++;
+	return NULL;
+}
+
+void *
+got_object_idcache_get(struct got_object_idcache *cache, struct got_object_id *id)
+{
+	struct got_object_idcache_element *entry;
+
+	TAILQ_FOREACH(entry, &cache->entries, entry) {
+		if (got_object_id_cmp(&entry->id, id) != 0)
+			continue;
+		if (entry != TAILQ_FIRST(&cache->entries)) {
+			TAILQ_REMOVE(&cache->entries, entry, entry);
+			TAILQ_INSERT_HEAD(&cache->entries, entry, entry);
+		}
+		return entry->data;
+	}
+
+	return NULL;
+}
+
+const struct got_error *
+got_object_idcache_remove_least_used(void **data, struct got_object_idcache *cache)
+{
+	struct got_object_idcache_element *entry;
+
+	if (data)
+		*data = NULL;
+
+	if (cache->nelem == 0)
+		return got_error(GOT_ERR_NO_OBJ);
+
+	entry = TAILQ_LAST(&cache->entries, got_object_idcache_head);
+	TAILQ_REMOVE(&cache->entries, entry, entry);
+	if (data)
+		*data = entry->data;
+	free(entry);
+	cache->nelem--;
+	return NULL;
+}
+
+int
+got_object_idcache_contains(struct got_object_idcache *cache,
+    struct got_object_id *id)
+{
+	struct got_object_idcache_element *entry;
+
+	TAILQ_FOREACH(entry, &cache->entries, entry) {
+		if (got_object_id_cmp(&entry->id, id) == 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;
+
+	TAILQ_FOREACH(entry, &cache->entries, entry)
+		cb(&entry->id, entry->data, arg);
+}
+
+int
+got_object_idcache_num_elements(struct got_object_idcache *set)
+{
+	return set->nelem;
+}
diff --git a/lib/repository.c b/lib/repository.c
index 9f2643e..0293902 100644
--- a/lib/repository.c
+++ b/lib/repository.c
@@ -37,7 +37,7 @@
 #include "got_lib_pack.h"
 #include "got_lib_repository.h"
 #include "got_lib_worktree.h"
-#include "got_lib_object_idset.h"
+#include "got_lib_object_idcache.h"
 
 #ifndef nitems
 #define nitems(_a) (sizeof(_a) / sizeof((_a)[0]))
@@ -156,10 +156,10 @@ cache_add(struct got_object_cache *cache, struct got_object_id *id, void *item)
 	struct got_object_cache_entry *ce;
 	int nelem;
 
-	nelem = got_object_idset_num_elements(cache->set);
+	nelem = got_object_idcache_num_elements(cache->idcache);
 	if (nelem >= cache->size) {
-		err = got_object_idset_remove_random((void **)&ce,
-		    cache->set);
+		err = got_object_idcache_remove_least_used((void **)&ce,
+		    cache->idcache);
 		if (err)
 			return err;
 		switch (cache->type) {
@@ -191,7 +191,7 @@ cache_add(struct got_object_cache *cache, struct got_object_id *id, void *item)
 		ce->data.commit = (struct got_commit_object *)item;
 		break;
 	}
-	err = got_object_idset_add(NULL, cache->set, id, ce);
+	err = got_object_idcache_add(cache->idcache, id, ce);
 	if (err) {
 		if (err->code == GOT_ERR_OBJ_EXISTS) {
 			free(ce);
@@ -222,7 +222,7 @@ got_repo_get_cached_object(struct got_repository *repo,
 {
 	struct got_object_cache_entry *ce;
 
-	ce = got_object_idset_get(repo->objcache.set, id);
+	ce = got_object_idcache_get(repo->objcache.idcache, id);
 	if (ce) {
 		repo->objcache.cache_hit++;
 		return ce->data.obj;
@@ -252,7 +252,7 @@ got_repo_get_cached_tree(struct got_repository *repo,
 {
 	struct got_object_cache_entry *ce;
 
-	ce = got_object_idset_get(repo->treecache.set, id);
+	ce = got_object_idcache_get(repo->treecache.idcache, id);
 	if (ce) {
 		repo->treecache.cache_hit++;
 		return ce->data.tree;
@@ -282,7 +282,7 @@ got_repo_get_cached_commit(struct got_repository *repo,
 {
 	struct got_object_cache_entry *ce;
 
-	ce = got_object_idset_get(repo->commitcache.set, id);
+	ce = got_object_idcache_get(repo->commitcache.idcache, id);
 	if (ce) {
 		repo->commitcache.cache_hit++;
 		return ce->data.commit;
@@ -312,29 +312,31 @@ got_repo_open(struct got_repository **ret, const char *path)
 		goto done;
 	}
 
-	repo->objcache.set = got_object_idset_alloc();
-	if (repo->objcache.set == NULL) {
-		err = got_error_from_errno();
-		goto done;
-	}
 	repo->objcache.type = GOT_OBJECT_CACHE_TYPE_OBJ;
 	repo->objcache.size = GOT_OBJECT_CACHE_SIZE_OBJ;
-
-	repo->treecache.set = got_object_idset_alloc();
-	if (repo->treecache.set == NULL) {
+	repo->objcache.idcache = got_object_idcache_alloc(repo->objcache.size);
+	if (repo->objcache.idcache == NULL) {
 		err = got_error_from_errno();
 		goto done;
 	}
+
 	repo->treecache.type = GOT_OBJECT_CACHE_TYPE_TREE;
 	repo->treecache.size = GOT_OBJECT_CACHE_SIZE_TREE;
-
-	repo->commitcache.set = got_object_idset_alloc();
-	if (repo->commitcache.set == NULL) {
+	repo->treecache.idcache =
+	    got_object_idcache_alloc(repo->treecache.size);
+	if (repo->treecache.idcache == NULL) {
 		err = got_error_from_errno();
 		goto done;
 	}
+
 	repo->commitcache.type = GOT_OBJECT_CACHE_TYPE_COMMIT;
 	repo->commitcache.size = GOT_OBJECT_CACHE_SIZE_COMMIT;
+	repo->commitcache.idcache =
+	    got_object_idcache_alloc(repo->commitcache.size);
+	if (repo->commitcache.idcache == NULL) {
+		err = got_error_from_errno();
+		goto done;
+	}
 
 	repo->path = got_path_normalize(abspath);
 	if (repo->path == NULL) {
@@ -395,8 +397,8 @@ static void
 print_cache_stats(struct got_object_cache *cache, const char *name)
 {
 	fprintf(stderr, "%s cache: %d elements, %d hits, %d missed\n",
-	    name, got_object_idset_num_elements(cache->set), cache->cache_hit,
-	    cache->cache_miss);
+	    name, got_object_idcache_num_elements(cache->idcache),
+	    cache->cache_hit, cache->cache_miss);
 }
 
 void check_refcount(struct got_object_id *id, void *data, void *arg)
@@ -462,19 +464,19 @@ got_repo_close(struct got_repository *repo)
 	print_cache_stats(&repo->objcache, "object");
 	print_cache_stats(&repo->treecache, "tree");
 	print_cache_stats(&repo->commitcache, "commit");
-	got_object_idset_for_each(repo->objcache.set, check_refcount,
+	got_object_idcache_for_each(repo->objcache.idcache, check_refcount,
 	    &repo->objcache);
-	got_object_idset_for_each(repo->treecache.set, check_refcount,
+	got_object_idcache_for_each(repo->treecache.idcache, check_refcount,
 	    &repo->treecache);
-	got_object_idset_for_each(repo->commitcache.set, check_refcount,
+	got_object_idcache_for_each(repo->commitcache.idcache, check_refcount,
 	    &repo->commitcache);
 #endif
 
-	if (repo->objcache.set)
-		got_object_idset_free(repo->objcache.set);
-	if (repo->treecache.set)
-		got_object_idset_free(repo->treecache.set);
-	if (repo->commitcache.set)
-		got_object_idset_free(repo->commitcache.set);
+	if (repo->objcache.idcache)
+		got_object_idcache_free(repo->objcache.idcache);
+	if (repo->treecache.idcache)
+		got_object_idcache_free(repo->treecache.idcache);
+	if (repo->commitcache.idcache)
+		got_object_idcache_free(repo->commitcache.idcache);
 	free(repo);
 }
diff --git a/regress/idset/Makefile b/regress/idset/Makefile
index 957eace..7b2e4c1 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 zbuf.c path.c opentemp.c \
 	delta.c repository.c reference.c worktree.c fileindex.c \
-	object_idset.c idset_test.c
+	object_idcache.c object_idset.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 f8b2b59..c8f2d7e 100644
--- a/regress/repository/Makefile
+++ b/regress/repository/Makefile
@@ -1,9 +1,9 @@
 .PATH:${.CURDIR}/../../lib
 
 PROG = repository_test
-SRCS = path.c repository.c error.c reference.c object.c object_idset.c \
-	opentemp.c sha1.c diff.c diffreg.c pack.c privsep.c delta.c \
-	fileindex.c worktree.c zbuf.c repository_test.c
+SRCS = path.c repository.c error.c reference.c object.c object_idcache.c \
+	object_idset.c opentemp.c sha1.c diff.c diffreg.c pack.c privsep.c \
+	delta.c fileindex.c worktree.c zbuf.c repository_test.c
 
 CPPFLAGS = -I${.CURDIR}/../../include -I${.CURDIR}/../../lib
 LDADD = -lutil -lz
diff --git a/regress/worktree/Makefile b/regress/worktree/Makefile
index 9048749..4c90c64 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_idset.c opentemp.c path.c \
-	error.c reference.c sha1.c pack.c privsep.c delta.c zbuf.c \
-	fileindex.c worktree_test.c
+SRCS = worktree.c repository.c object.c object_idcache.c object_idset.c \
+	opentemp.c path.c error.c reference.c sha1.c pack.c privsep.c delta.c \
+	zbuf.c fileindex.c worktree_test.c
 
 CPPFLAGS = -I${.CURDIR}/../../include -I${.CURDIR}/../../lib
 LDADD = -lutil -lz
diff --git a/tog/Makefile b/tog/Makefile
index 4ffef6b..f3f5958 100644
--- a/tog/Makefile
+++ b/tog/Makefile
@@ -2,9 +2,9 @@
 
 PROG=		tog
 SRCS=		tog.c blame.c commit_graph.c delta.c diff.c diffreg.c error.c \
-		fileindex.c object.c object_idset.c opentemp.c path.c \
-		pack.c privsep.c reference.c repository.c sha1.c worktree.c \
-		utf8.c zbuf.c
+		fileindex.c object.c object_idcache.c object_idset.c \
+		opentemp.c path.c pack.c privsep.c reference.c repository.c \
+		sha1.c worktree.c utf8.c zbuf.c
 
 CPPFLAGS = -I${.CURDIR}/../include -I${.CURDIR}/../lib
 LDADD = -lpanel -lncursesw -lutil -lz