thodg/got

diff --git a/lib/commit_graph.c b/lib/commit_graph.c
index 4023b5d..a01adb6 100644
--- a/lib/commit_graph.c
+++ b/lib/commit_graph.c
@@ -100,13 +100,15 @@ alloc_graph(void)
 	if (graph == NULL)
 		return NULL;
 
-	graph->node_ids = got_object_idset_alloc();
+	graph->node_ids = got_object_idset_alloc(
+	    GOT_OBJECT_IDSET_ITERATE_BY_OBJECT_ID);
 	if (graph->node_ids == NULL) {
 		free(graph);
 		return NULL;
 	}
 
-	graph->open_branches = got_object_idset_alloc();
+	graph->open_branches = got_object_idset_alloc(
+	     GOT_OBJECT_IDSET_ITERATE_BY_OBJECT_ID);
 	if (graph->open_branches == NULL) {
 		got_object_idset_free(graph->node_ids);
 		free(graph);
diff --git a/lib/got_lib_object_idset.h b/lib/got_lib_object_idset.h
index 7d98296..4ce7735 100644
--- a/lib/got_lib_object_idset.h
+++ b/lib/got_lib_object_idset.h
@@ -16,7 +16,13 @@
 
 struct got_object_idset;
 
-struct got_object_idset *got_object_idset_alloc(void);
+enum got_object_idset_iteration_order {
+	GOT_OBJECT_IDSET_ITERATE_BY_OBJECT_ID,
+	GOT_OBJECT_IDSET_ITERATE_RECENTLY_USED,
+};
+
+struct got_object_idset *got_object_idset_alloc(
+    enum got_object_idset_iteration_order);
 void got_object_idset_free(struct got_object_idset *);
 
 const struct got_error *got_object_idset_add(void **,
diff --git a/lib/object_idset.c b/lib/object_idset.c
index 2c7c696..55fb1fc 100644
--- a/lib/object_idset.c
+++ b/lib/object_idset.c
@@ -52,10 +52,11 @@ struct got_object_idset {
 	int nelem[0xff + 1];
 	int totelem;
 #define GOT_OBJECT_IDSET_MAX_ELEM INT_MAX
+	enum got_object_idset_iteration_order order;
 };
 
 struct got_object_idset *
-got_object_idset_alloc(void)
+got_object_idset_alloc(enum got_object_idset_iteration_order order)
 {
 	struct got_object_idset *set;
 	int i;
@@ -64,6 +65,7 @@ got_object_idset_alloc(void)
 	if (set == NULL)
 		return NULL;
 
+	set->order = order;
 	for (i = 0; i < nitems(set->entries); i++)
 		TAILQ_INIT(&set->entries[i]);
 
@@ -107,7 +109,8 @@ got_object_idset_add(void **existing_data,
 	memcpy(&new->id, id, sizeof(new->id));
 	new->data = data;
 
-	if (TAILQ_EMPTY(&set->entries[i])) {
+	if (TAILQ_EMPTY(&set->entries[i]) ||
+	    set->order == GOT_OBJECT_IDSET_ITERATE_RECENTLY_USED) {
 		TAILQ_INSERT_HEAD(&set->entries[i], new, entry);
 		set->nelem[i]++;
 		set->totelem++;
@@ -154,12 +157,18 @@ got_object_idset_add(void **existing_data,
 void *
 got_object_idset_get(struct got_object_idset *set, struct got_object_id *id)
 {
-	struct got_object_idset_element *entry;
+	struct got_object_idset_element *entry, *tmp;
 	uint8_t i = id->sha1[0];
 
-	TAILQ_FOREACH(entry, &set->entries[i], entry) {
-		if (got_object_id_cmp(&entry->id, id) == 0)
-			return entry->data;
+	TAILQ_FOREACH_SAFE(entry, &set->entries[i], entry, tmp) {
+		if (got_object_id_cmp(&entry->id, id) != 0)
+			continue;
+		if (set->order == GOT_OBJECT_IDSET_ITERATE_RECENTLY_USED &&
+		    entry != TAILQ_FIRST(&set->entries[i])) {
+			TAILQ_REMOVE(&set->entries[i], entry, entry);
+			TAILQ_INSERT_HEAD(&set->entries[i], entry, entry);
+		}
+		return entry->data;
 	}
 
 	return NULL;
diff --git a/lib/repository.c b/lib/repository.c
index 9f2643e..de7c434 100644
--- a/lib/repository.c
+++ b/lib/repository.c
@@ -312,7 +312,8 @@ got_repo_open(struct got_repository **ret, const char *path)
 		goto done;
 	}
 
-	repo->objcache.set = got_object_idset_alloc();
+	repo->objcache.set = got_object_idset_alloc(
+	    GOT_OBJECT_IDSET_ITERATE_RECENTLY_USED);
 	if (repo->objcache.set == NULL) {
 		err = got_error_from_errno();
 		goto done;
@@ -320,7 +321,8 @@ got_repo_open(struct got_repository **ret, const char *path)
 	repo->objcache.type = GOT_OBJECT_CACHE_TYPE_OBJ;
 	repo->objcache.size = GOT_OBJECT_CACHE_SIZE_OBJ;
 
-	repo->treecache.set = got_object_idset_alloc();
+	repo->treecache.set = got_object_idset_alloc(
+	    GOT_OBJECT_IDSET_ITERATE_RECENTLY_USED);
 	if (repo->treecache.set == NULL) {
 		err = got_error_from_errno();
 		goto done;
@@ -328,7 +330,8 @@ got_repo_open(struct got_repository **ret, const char *path)
 	repo->treecache.type = GOT_OBJECT_CACHE_TYPE_TREE;
 	repo->treecache.size = GOT_OBJECT_CACHE_SIZE_TREE;
 
-	repo->commitcache.set = got_object_idset_alloc();
+	repo->commitcache.set = got_object_idset_alloc(
+	    GOT_OBJECT_IDSET_ITERATE_RECENTLY_USED);
 	if (repo->commitcache.set == NULL) {
 		err = got_error_from_errno();
 		goto done;