commit - 5df4932d8e7905f8e04dbf16e3879da18a091cec
commit + d83eb5cd1cc329e58e94aa0b17aa348f4df65734
blob - 79206665203625b474ebdbb75bc88916a1593301
blob + 20d9f5cca727758161b7d4f73321ba3f1b271e88
--- lib/got_lib_object_idcache.h
+++ lib/got_lib_object_idcache.h
@@ -22,8 +22,8 @@ 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 *);
+const struct got_error *got_object_idcache_remove_one(void **,
+    struct got_object_idcache *, struct got_object_id *);
 int got_object_idcache_contains(struct got_object_idcache *,
     struct got_object_id *);
 void got_object_idcache_for_each(struct got_object_idcache *,
blob - 7957b39b0d062a400041ff34791a06d38d694832
blob + f4766bb8930bb4f090f7673b33c60c3aed5a0ff0
--- lib/object_cache.c
+++ lib/object_cache.c
@@ -73,8 +73,8 @@ got_object_cache_add(struct got_object_cache *cache, s
 
 	nelem = got_object_idcache_num_elements(cache->idcache);
 	if (nelem >= cache->size) {
-		err = got_object_idcache_remove_least_used((void **)&ce,
-		    cache->idcache);
+		err = got_object_idcache_remove_one((void **)&ce,
+		    cache->idcache, id);
 		if (err)
 			return err;
 		switch (cache->type) {
blob - 763294310f44316f6e4616536eae3bc35e3f70d0
blob + 3206b9e9b4efd15c8f08b21fc609d788c1a658ea
--- lib/object_idcache.c
+++ lib/object_idcache.c
@@ -132,10 +132,11 @@ got_object_idcache_get(struct got_object_idcache *cach
 }
 
 const struct got_error *
-got_object_idcache_remove_least_used(void **data, struct got_object_idcache *cache)
+got_object_idcache_remove_one(void **data, struct got_object_idcache *cache,
+    struct got_object_id *id)
 {
 	struct got_object_idcache_element *entry;
-	int i, idx = 0, maxelem = cache->nelem[0];
+	uint8_t idx = id->sha1[0];
 
 	if (data)
 		*data = NULL;
@@ -143,13 +144,18 @@ got_object_idcache_remove_least_used(void **data, stru
 	if (cache->totelem == 0)
 		return got_error(GOT_ERR_NO_OBJ);
 
-	/* Remove least used element from longest list. */
-	for (i = 0; i < nitems(cache->entries); i++) {
-		if (maxelem < cache->nelem[i]) {
-			idx = i;
-			maxelem = cache->nelem[i];
+	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)