commit d54f52f450beca49be8a5f8af3094bdbbd2355d6
from: Stefan Sperling <stsp@stsp.name>
date: Sat Jul 07 14:50:10 2018 UTC

store recently accessed objects at front of cache lists

commit - dd031dc0f32a6e39337331580ed937aa466d05cf
commit + d54f52f450beca49be8a5f8af3094bdbbd2355d6
blob - 4023b5de72d091b968bdf6942e5153a6055d06f2
blob + a01adb668268cd8751b7e4ee306c93866af410ac
--- lib/commit_graph.c
+++ 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);
blob - 7d98296142abd2f7a34aef5776b35c41a97a36d0
blob + 4ce7735194c446f4ad4b165ff43e24182f14aaf8
--- lib/got_lib_object_idset.h
+++ 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 **,
blob - 2c7c696978afa9567d80dfffd1a651122ec6bad9
blob + 55fb1fc0f2b60c45b2b441119ec66c788dd8b88a
--- lib/object_idset.c
+++ 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;
blob - 9f2643e160d80e60579fdc434640f570194ec4ca
blob + de7c434d04ee947428398ffe12ecc547fc1c0b78
--- lib/repository.c
+++ lib/repository.c
@@ -312,7 +312,8 @@ got_repo_open(struct got_repository **ret, const char 
 		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 
 	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 
 	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;