Game of Trees Repos

Commit Diff

Commit:: d9dff0e5c658f1bef8647522dcb5b851b3f4734e
From:: Stefan Sperling <stsp@stsp.name>
Date:: Sat Dec 26 21:32:01 2020 UTC
Message:: switch reflist to TAILQ; insert elements more efficiently for sorted input ok naddy
Actions:: Patch | Tree
commit - 87670572d0f25fb0137be54add50dd728195bb0d
commit + d9dff0e5c658f1bef8647522dcb5b851b3f4734e
blob - 5ae8df4581b3c8b1b606407a8243cf633db3b443
blob + 56ec3c84e79de939eeb6430d0588bfc77ac7d25d
--- got/got.c
+++ got/got.c
@@ -1881,7 +1881,7 @@ delete_missing_refs(struct got_pathlist_head *their_re
 	char *remote_namespace = NULL;
 	char *local_refname = NULL;
 
-	SIMPLEQ_INIT(&my_refs);
+	TAILQ_INIT(&my_refs);
 
 	if (asprintf(&remote_namespace, "refs/remotes/%s/", remote->name)
 	    == -1)
@@ -1891,7 +1891,7 @@ delete_missing_refs(struct got_pathlist_head *their_re
 	if (err)
 		goto done;
 
-	SIMPLEQ_FOREACH(re, &my_refs, entry) {
+	TAILQ_FOREACH(re, &my_refs, entry) {
 		const char *refname = got_ref_get_name(re->ref);
 
 		if (!remote->mirror_references) {
@@ -2744,7 +2744,7 @@ cmd_checkout(int argc, char *argv[])
 	if (commit_id_str) {
 		struct got_object_id *commit_id;
 		struct got_reflist_head refs;
-		SIMPLEQ_INIT(&refs);
+		TAILQ_INIT(&refs);
 		error = got_ref_list(&refs, repo, NULL, got_ref_cmp_by_name,
 		    NULL);
 		if (error)
@@ -3058,7 +3058,7 @@ cmd_update(int argc, char *argv[])
 			goto done;
 	} else {
 		struct got_reflist_head refs;
-		SIMPLEQ_INIT(&refs);
+		TAILQ_INIT(&refs);
 		error = got_ref_list(&refs, repo, NULL, got_ref_cmp_by_name,
 		    NULL);
 		if (error)
@@ -3416,7 +3416,7 @@ print_commit(struct got_commit_object *commit, struct 
 	char *refs_str = NULL;
 	struct got_reflist_entry *re;
 
-	SIMPLEQ_FOREACH(re, refs, entry) {
+	TAILQ_FOREACH(re, refs, entry) {
 		char *s;
 		const char *name;
 		struct got_tag_object *tag = NULL;
@@ -3716,7 +3716,7 @@ cmd_log(int argc, char *argv[])
 	const char *errstr;
 	struct got_reflist_head refs;
 
-	SIMPLEQ_INIT(&refs);
+	TAILQ_INIT(&refs);
 
 #ifndef PROFILE
 	if (pledge("stdio rpath wpath cpath flock proc exec sendfd unveil",
@@ -4130,7 +4130,7 @@ cmd_diff(int argc, char *argv[])
 	char *path = NULL;
 	struct got_reflist_head refs;
 
-	SIMPLEQ_INIT(&refs);
+	TAILQ_INIT(&refs);
 
 #ifndef PROFILE
 	if (pledge("stdio rpath wpath cpath flock proc exec sendfd unveil",
@@ -4582,7 +4582,7 @@ cmd_blame(int argc, char *argv[])
 			goto done;
 	} else {
 		struct got_reflist_head refs;
-		SIMPLEQ_INIT(&refs);
+		TAILQ_INIT(&refs);
 		error = got_ref_list(&refs, repo, NULL, got_ref_cmp_by_name,
 		    NULL);
 		if (error)
@@ -4925,7 +4925,7 @@ cmd_tree(int argc, char *argv[])
 			goto done;
 	} else {
 		struct got_reflist_head refs;
-		SIMPLEQ_INIT(&refs);
+		TAILQ_INIT(&refs);
 		error = got_ref_list(&refs, repo, NULL, got_ref_cmp_by_name,
 		    NULL);
 		if (error)
@@ -5090,12 +5090,12 @@ list_refs(struct got_repository *repo, const char *ref
 	struct got_reflist_head refs;
 	struct got_reflist_entry *re;
 
-	SIMPLEQ_INIT(&refs);
+	TAILQ_INIT(&refs);
 	err = got_ref_list(&refs, repo, refname, got_ref_cmp_by_name, NULL);
 	if (err)
 		return err;
 
-	SIMPLEQ_FOREACH(re, &refs, entry) {
+	TAILQ_FOREACH(re, &refs, entry) {
 		char *refstr;
 		refstr = got_ref_to_str(re->ref);
 		if (refstr == NULL)
@@ -5421,7 +5421,7 @@ list_branches(struct got_repository *repo, struct got_
 	struct got_reference *temp_ref = NULL;
 	int rebase_in_progress, histedit_in_progress;
 
-	SIMPLEQ_INIT(&refs);
+	TAILQ_INIT(&refs);
 
 	if (worktree) {
 		err = got_worktree_rebase_in_progress(&rebase_in_progress,
@@ -5449,7 +5449,7 @@ list_branches(struct got_repository *repo, struct got_
 	if (err)
 		return err;
 
-	SIMPLEQ_FOREACH(re, &refs, entry)
+	TAILQ_FOREACH(re, &refs, entry)
 		list_branch(repo, worktree, re->ref);
 
 	got_ref_list_free(&refs);
@@ -5646,7 +5646,7 @@ cmd_branch(int argc, char *argv[])
 		error = delete_branch(repo, worktree, delref);
 	else {
 		struct got_reflist_head refs;
-		SIMPLEQ_INIT(&refs);
+		TAILQ_INIT(&refs);
 		error = got_ref_list(&refs, repo, NULL, got_ref_cmp_by_name,
 		    NULL);
 		if (error)
@@ -5793,13 +5793,13 @@ list_tags(struct got_repository *repo, struct got_work
 	struct got_reflist_head refs;
 	struct got_reflist_entry *re;
 
-	SIMPLEQ_INIT(&refs);
+	TAILQ_INIT(&refs);
 
 	err = got_ref_list(&refs, repo, "refs/tags", got_ref_cmp_tags, repo);
 	if (err)
 		return err;
 
-	SIMPLEQ_FOREACH(re, &refs, entry) {
+	TAILQ_FOREACH(re, &refs, entry) {
 		const char *refname;
 		char *refstr, *tagmsg0, *tagmsg, *line, *id_str, *datestr;
 		char datebuf[26];
@@ -5976,7 +5976,7 @@ add_tag(struct got_repository *repo, struct got_worktr
 	int preserve_tagmsg = 0;
 	struct got_reflist_head refs;
 
-	SIMPLEQ_INIT(&refs);
+	TAILQ_INIT(&refs);
 
 	/*
 	 * Don't let the user create a tag name with a leading '-'.
@@ -9624,7 +9624,7 @@ cmd_cat(int argc, char *argv[])
 	int ch, obj_type, i, force_path = 0;
 	struct got_reflist_head refs;
 
-	SIMPLEQ_INIT(&refs);
+	TAILQ_INIT(&refs);
 
 #ifndef PROFILE
 	if (pledge("stdio rpath wpath cpath flock proc exec sendfd unveil",
blob - 53ce046986e836dd5050f4b5ede182d2d14a06e0
blob + b657ec5ba42677b92a8726bc24022c48ee71e23e
--- gotweb/gotweb.c
+++ gotweb/gotweb.c
@@ -2780,7 +2780,7 @@ gw_get_repo_age(char **repo_age, struct gw_trans *gw_t
 	time_t committer_time = 0, cmp_time = 0;
 
 	*repo_age = NULL;
-	SIMPLEQ_INIT(&refs);
+	TAILQ_INIT(&refs);
 
 	if (gw_trans->gw_conf->got_show_repo_age == 0)
 		return NULL;
@@ -2802,7 +2802,7 @@ gw_get_repo_age(char **repo_age, struct gw_trans *gw_t
 	 * Find the youngest branch tip in the repository, or the age of
 	 * the a specific branch tip if a name was provided by the caller.
 	 */
-	SIMPLEQ_FOREACH(re, &refs, entry) {
+	TAILQ_FOREACH(re, &refs, entry) {
 		struct got_object_id *id = NULL;
 
 		if (refname && strcmp(got_ref_get_name(re->ref), refname) != 0)
@@ -3015,14 +3015,14 @@ gw_output_repo_tags(struct gw_trans *gw_trans, struct 
 	int summary_header_displayed = 0, start_tag = 0, chk_next = 0;
 	int prev_set = 0, tag_count = 0;
 
-	SIMPLEQ_INIT(&refs);
+	TAILQ_INIT(&refs);
 
 	error = got_ref_list(&refs, gw_trans->repo, "refs/tags",
 	    got_ref_cmp_tags, gw_trans->repo);
 	if (error)
 		goto done;
 
-	SIMPLEQ_FOREACH(re, &refs, entry) {
+	TAILQ_FOREACH(re, &refs, entry) {
 		const char *refname;
 		const char *tagger;
 		const char *tag_commit;
@@ -3420,7 +3420,7 @@ gw_init_header()
 		return NULL;
 
 	header->path = NULL;
-	SIMPLEQ_INIT(&header->refs);
+	TAILQ_INIT(&header->refs);
 
 	header->refs_str = NULL;
 	header->commit_id = NULL;
@@ -3546,7 +3546,7 @@ gw_get_commit(struct gw_trans *gw_trans, struct gw_hea
 	char *commit_msg = NULL, *commit_msg0;
 
 	/*print commit*/
-	SIMPLEQ_FOREACH(re, &header->refs, entry) {
+	TAILQ_FOREACH(re, &header->refs, entry) {
 		char *s;
 		const char *name;
 		struct got_tag_object *tag = NULL;
@@ -4402,7 +4402,7 @@ gw_output_repo_heads(struct gw_trans *gw_trans)
 	char *href_commits = NULL;
 	enum kcgi_err kerr = KCGI_OK;
 
-	SIMPLEQ_INIT(&refs);
+	TAILQ_INIT(&refs);
 
 	error = got_ref_list(&refs, gw_trans->repo, "refs/heads",
 	    got_ref_cmp_by_name, NULL);
@@ -4428,7 +4428,7 @@ gw_output_repo_heads(struct gw_trans *gw_trans)
 	if (kerr != KCGI_OK)
 		goto done;
 
-	SIMPLEQ_FOREACH(re, &refs, entry) {
+	TAILQ_FOREACH(re, &refs, entry) {
 		const char *refname;
 
 		if (got_ref_is_symbolic(re->ref))
blob - 8a7ddd1fed280c5ace7be5e759d1b7ef2c6cc784
blob + eeeea20b67e66db6ea18f137afc56636198d5de4
--- include/got_reference.h
+++ include/got_reference.h
@@ -77,10 +77,10 @@ char *got_ref_to_str(struct got_reference *);
 
 /* List of references. */
 struct got_reflist_entry {
-	SIMPLEQ_ENTRY(got_reflist_entry) entry;
+	TAILQ_ENTRY(got_reflist_entry) entry;
 	struct got_reference *ref;
 };
-SIMPLEQ_HEAD(got_reflist_head, got_reflist_entry);
+TAILQ_HEAD(got_reflist_head, got_reflist_entry);
 
 /* Duplicate a reference list entry. Caller must dispose of it with free(3). */
 const struct got_error *got_reflist_entry_dup(struct got_reflist_entry **,
blob - 0aab76f5fc3a5dc2a5b75368480b9f3e9e512f59
blob + 134a933494056e53673c29dc390c0621d0fdb1c2
--- lib/fetch.c
+++ lib/fetch.c
@@ -408,7 +408,7 @@ got_fetch_pack(struct got_object_id **pack_hash, struc
 		tmpfds[i] = -1;
 
 	TAILQ_INIT(&have_refs);
-	SIMPLEQ_INIT(&my_refs);
+	TAILQ_INIT(&my_refs);
 
 	if (!mirror_references) {
 		if (asprintf(&ref_prefix, "refs/remotes/%s/",
@@ -424,7 +424,7 @@ got_fetch_pack(struct got_object_id **pack_hash, struc
 			goto done;
 	}
 
-	SIMPLEQ_FOREACH(re, &my_refs, entry) {
+	TAILQ_FOREACH(re, &my_refs, entry) {
 		struct got_object_id *id;
 		const char *refname;
 
blob - d9f1596591be3332b0a51e1ec4e6c77a90720fae
blob + 6dba390bae34718cc3dd29ba41787375e56e54da
--- lib/reference.c
+++ lib/reference.c
@@ -746,7 +746,7 @@ insert_ref(struct got_reflist_entry **newp, struct got
     got_ref_cmp_cb cmp_cb, void *cmp_arg)
 {
 	const struct got_error *err;
-	struct got_reflist_entry *new, *re, *prev = NULL;
+	struct got_reflist_entry *new, *re;
 	int cmp;
 
 	*newp = NULL;
@@ -762,8 +762,13 @@ insert_ref(struct got_reflist_entry **newp, struct got
 	 * contain redundant entries. On-disk refs take precedence.
 	 * This code assumes that on-disk revs are read before packed-refs.
 	 * We're iterating the list anyway, so insert elements sorted by name.
+	 *
+	 * Many callers will provide paths in a somewhat sorted order.
+	 * Iterating backwards from the tail of the list should be more
+	 * efficient than traversing through the entire list each time
+	 * an element is inserted.
 	 */
-	re = SIMPLEQ_FIRST(refs);
+	re = TAILQ_LAST(refs, got_reflist_head);
 	while (re) {
 		err = (*cmp_cb)(cmp_arg, &cmp, re->ref, new->ref);
 		if (err)
@@ -773,19 +778,14 @@ insert_ref(struct got_reflist_entry **newp, struct got
 			free(new);
 			*newp = NULL;
 			return NULL;
-		} else if (cmp > 0) {
-			if (prev)
-				SIMPLEQ_INSERT_AFTER(refs, prev, new, entry);
-			else
-				SIMPLEQ_INSERT_HEAD(refs, new, entry);
+		} else if (cmp < 0) {
+			TAILQ_INSERT_AFTER(refs, re, new, entry);
 			return NULL;
-		} else {
-			prev = re;
-			re = SIMPLEQ_NEXT(re, entry);
 		}
+		re = TAILQ_PREV(re, got_reflist_head, entry);
 	}
 
-	SIMPLEQ_INSERT_TAIL(refs, new, entry);
+	TAILQ_INSERT_HEAD(refs, new, entry);
 	return NULL;
 }
 
@@ -1012,10 +1012,8 @@ got_ref_list_free(struct got_reflist_head *refs)
 {
 	struct got_reflist_entry *re;
 
-	while (!SIMPLEQ_EMPTY(refs)) {
-		re = SIMPLEQ_FIRST(refs);
-		SIMPLEQ_REMOVE_HEAD(refs, entry);
-		got_ref_close(re->ref);
+	while ((re = TAILQ_FIRST(refs))) {
+		TAILQ_REMOVE(refs, re, entry);
 		free(re);
 	}
 
@@ -1184,7 +1182,7 @@ delete_packed_ref(struct got_reference *delref, struct
 	if (delref->flags & GOT_REF_IS_SYMBOLIC)
 		return got_error(GOT_ERR_BAD_REF_DATA);
 
-	SIMPLEQ_INIT(&refs);
+	TAILQ_INIT(&refs);
 
 	packed_refs_path = got_repo_get_path_packed_refs(repo);
 	if (packed_refs_path == NULL)
@@ -1253,7 +1251,7 @@ delete_packed_ref(struct got_reference *delref, struct
 			goto done;
 		}
 
-		SIMPLEQ_FOREACH(re, &refs, entry) {
+		TAILQ_FOREACH(re, &refs, entry) {
 			uint8_t hex[SHA1_DIGEST_STRING_LENGTH];
 
 			if (got_sha1_digest_to_str(re->ref->ref.ref.sha1, hex,
@@ -1430,7 +1428,7 @@ got_reflist_object_id_map_create(struct got_reflist_ob
 	}
 	(*map)->idset = idset;
 
-	SIMPLEQ_FOREACH(re, refs, entry) {
+	TAILQ_FOREACH(re, refs, entry) {
 		struct got_reflist_entry *new;
 		struct got_reflist_object_id_map_entry *ent;
 
@@ -1445,7 +1443,7 @@ got_reflist_object_id_map_create(struct got_reflist_ob
 				err = got_error_from_errno("malloc");
 				goto done;
 			}
-			SIMPLEQ_INIT(&ent->refs);
+			TAILQ_INIT(&ent->refs);
 			err = got_object_idset_add(idset, id, ent);
 			if (err)
 				goto done;
@@ -1454,7 +1452,7 @@ got_reflist_object_id_map_create(struct got_reflist_ob
 		err = got_reflist_entry_dup(&new, re);
 		if (err)
 			goto done;
-		SIMPLEQ_INSERT_TAIL(&ent->refs, new, entry);
+		TAILQ_INSERT_TAIL(&ent->refs, new, entry);
 		free(id);
 		id = NULL;
 	}
blob - bfbd39aabab2179cdbf0100c7d1b2534617f140e
blob + 4a6e13fd0afc2e6e9bb7a10467c39500a78a8734
--- lib/repository.c
+++ lib/repository.c
@@ -1538,7 +1538,7 @@ got_repo_object_match_tag(struct got_tag_object **tag,
 
 	*tag = NULL;
 
-	SIMPLEQ_FOREACH(re, refs, entry) {
+	TAILQ_FOREACH(re, refs, entry) {
 		const char *refname;
 		refname = got_ref_get_name(re->ref);
 		if (got_ref_is_symbolic(re->ref))
blob - 34ef25995f16190305230ec2b631d168e4ff50fd
blob + 2e23ae5edc382c67c6fbdef723418d445a2a24d3
--- tog/tog.c
+++ tog/tog.c
@@ -125,7 +125,7 @@ struct tog_color {
 };
 SIMPLEQ_HEAD(tog_colors, tog_color);
 
-static struct got_reflist_head tog_refs = SIMPLEQ_HEAD_INITIALIZER(tog_refs);
+static struct got_reflist_head tog_refs = TAILQ_HEAD_INITIALIZER(tog_refs);
 static struct got_reflist_object_id_map *tog_refs_idmap;
 
 static const struct got_error *
@@ -1248,7 +1248,7 @@ build_refs_str(char **refs_str, struct got_reflist_hea
 
 	*refs_str = NULL;
 
-	SIMPLEQ_FOREACH(re, refs, entry) {
+	TAILQ_FOREACH(re, refs, entry) {
 		struct got_tag_object *tag = NULL;
 		struct got_object_id *ref_id;
 		int cmp;
@@ -2757,7 +2757,7 @@ cmd_log(int argc, char *argv[])
 		goto done;
 
 	/* already loaded by tog_log_with_path()? */
-	if (SIMPLEQ_EMPTY(&tog_refs)) {
+	if (TAILQ_EMPTY(&tog_refs)) {
 		error = tog_load_refs(repo);
 		if (error)
 			goto done;
@@ -5621,7 +5621,7 @@ ref_view_load_refs(struct tog_ref_view_state *s)
 	struct tog_reflist_entry *re;
 
 	s->nrefs = 0;
-	SIMPLEQ_FOREACH(sre, &tog_refs, entry) {
+	TAILQ_FOREACH(sre, &tog_refs, entry) {
 		if (strncmp(got_ref_get_name(sre->ref), "refs/got/", 9) == 0)
 			continue;