commit d9dff0e5c658f1bef8647522dcb5b851b3f4734e from: Stefan Sperling date: Sat Dec 26 21:32:01 2020 UTC switch reflist to TAILQ; insert elements more efficiently for sorted input ok naddy 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;