Change got_pathlist to use RB_tree instead of TAILQ

I must apologize for the broken patch, I completely forgot about gotd and gotwebd. Here is the updated diff: diff refs/heads/main refs/heads/got_pathtree commit - 88ba8f77592194a8eb9a70f68b25bc09d0355e97 commit + ee1b798e42fe64cd3c975d8acb5567a02da58985 blob - 9f093ace3cfdb472bce06ad93efc12cb9138a9e4 blob + f24778d4013fcf34695978d66c42b3619ebdf7bd --- cvg/cvg.c +++ cvg/cvg.c @@ -18,6 +18,7 @@ */ #include <sys/queue.h> +#include <sys/tree.h> #include <sys/time.h> #include <sys/types.h> #include <sys/stat.h> @@ -740,7 +741,7 @@ cmd_import(int argc, char *argv[]) int preserve_logmsg = 0; int *pack_fds = NULL; - TAILQ_INIT(&ignores); + RB_INIT(&ignores); #ifndef PROFILE if (pledge("stdio rpath wpath cpath fattr flock proc exec sendfd " @@ -1027,7 +1028,7 @@ fetch_progress(void *arg, const char *message, off_t p * we have all required information. */ if (a->create_configs && !a->configs_created && - !TAILQ_EMPTY(a->config_info.symrefs)) { + !RB_EMPTY(a->config_info.symrefs)) { err = create_config_files(a->config_info.proto, a->config_info.host, a->config_info.port, a->config_info.remote_repo_path, @@ -1121,14 +1122,14 @@ list_remote_refs(struct got_pathlist_head *symrefs, const struct got_error *err; struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, symrefs, entry) { + RB_FOREACH(pe, got_pathlist_head, symrefs) { const char *refname = pe->path; const char *targetref = pe->data; printf("%s: %s\n", refname, targetref); } - TAILQ_FOREACH(pe, refs, entry) { + RB_FOREACH(pe, got_pathlist_head, refs) { const char *refname = pe->path; struct got_object_id *id = pe->data; char *id_str; @@ -1201,7 +1202,7 @@ is_wanted_ref(struct got_pathlist_head *wanted_refs, c { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, wanted_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, wanted_refs) { if (match_wanted_ref(refname, pe->path)) return 1; } @@ -1243,9 +1244,9 @@ create_gotconfig(const char *proto, const char *host, char *branches = NULL, *refs = NULL; ssize_t n; - if (!fetch_all_branches && !TAILQ_EMPTY(wanted_branches)) { + if (!fetch_all_branches && !RB_EMPTY(wanted_branches)) { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, wanted_branches, entry) { + RB_FOREACH(pe, got_pathlist_head, wanted_branches) { char *s; branchname = pe->path; if (strncmp(branchname, "refs/heads/", 11) == 0) @@ -1267,9 +1268,9 @@ create_gotconfig(const char *proto, const char *host, goto done; } } - if (!TAILQ_EMPTY(wanted_refs)) { + if (!RB_EMPTY(wanted_refs)) { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, wanted_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, wanted_refs) { char *s; const char *refname = pe->path; if (strncmp(refname, "refs/", 5) == 0) @@ -1368,9 +1369,9 @@ create_gitconfig(const char *git_url, const char *defa err = got_error_from_errno("asprintf"); goto done; } - } else if (!TAILQ_EMPTY(wanted_branches)) { + } else if (!RB_EMPTY(wanted_branches)) { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, wanted_branches, entry) { + RB_FOREACH(pe, got_pathlist_head, wanted_branches) { char *s; branchname = pe->path; if (strncmp(branchname, "refs/heads/", 11) == 0) @@ -1420,9 +1421,9 @@ create_gitconfig(const char *git_url, const char *defa goto done; } } - if (!TAILQ_EMPTY(wanted_refs)) { + if (!RB_EMPTY(wanted_refs)) { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, wanted_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, wanted_refs) { char *s; const char *refname = pe->path; if (strncmp(refname, "refs/", 5) == 0) @@ -1486,12 +1487,12 @@ create_config_files(const char *proto, const char *hos * If we asked for a set of wanted branches then use the first * one of those. */ - if (!TAILQ_EMPTY(wanted_branches)) { - pe = TAILQ_FIRST(wanted_branches); + if (!RB_EMPTY(wanted_branches)) { + pe = RB_MIN(got_pathlist_head, wanted_branches); default_branch = pe->path; } else { /* First HEAD ref listed by server is the default branch. */ - TAILQ_FOREACH(pe, symrefs, entry) { + RB_FOREACH(pe, got_pathlist_head, symrefs) { const char *refname = pe->path; const char *target = pe->data; @@ -1536,10 +1537,10 @@ cmd_clone(int argc, char *argv[]) int *pack_fds = NULL; const char *jumphost = NULL; - TAILQ_INIT(&refs); - TAILQ_INIT(&symrefs); - TAILQ_INIT(&wanted_branches); - TAILQ_INIT(&wanted_refs); + RB_INIT(&refs); + RB_INIT(&symrefs); + RB_INIT(&wanted_branches); + RB_INIT(&wanted_refs); while ((ch = getopt(argc, argv, "ab:J:lmqR:v")) != -1) { switch (ch) { @@ -1585,16 +1586,16 @@ cmd_clone(int argc, char *argv[]) argc -= optind; argv += optind; - if (fetch_all_branches && !TAILQ_EMPTY(&wanted_branches)) + if (fetch_all_branches && !RB_EMPTY(&wanted_branches)) option_conflict('a', 'b'); if (list_refs_only) { - if (!TAILQ_EMPTY(&wanted_branches)) + if (!RB_EMPTY(&wanted_branches)) option_conflict('l', 'b'); if (fetch_all_branches) option_conflict('l', 'a'); if (mirror_references) option_conflict('l', 'm'); - if (!TAILQ_EMPTY(&wanted_refs)) + if (!RB_EMPTY(&wanted_refs)) option_conflict('l', 'R'); } @@ -1733,7 +1734,7 @@ cmd_clone(int argc, char *argv[]) free(id_str); /* Set up references provided with the pack file. */ - TAILQ_FOREACH(pe, &refs, entry) { + RB_FOREACH(pe, got_pathlist_head, &refs) { const char *refname = pe->path; struct got_object_id *id = pe->data; char *remote_refname; @@ -1771,7 +1772,7 @@ cmd_clone(int argc, char *argv[]) } /* Set the HEAD reference if the server provided one. */ - TAILQ_FOREACH(pe, &symrefs, entry) { + RB_FOREACH(pe, got_pathlist_head, &symrefs) { struct got_reference *target_ref; const char *refname = pe->path; const char *target = pe->data; @@ -1837,7 +1838,7 @@ cmd_clone(int argc, char *argv[]) * a set of wanted branches use the first of one of those * which could be fetched instead. */ - TAILQ_FOREACH(pe, &wanted_branches, entry) { + RB_FOREACH(pe, got_pathlist_head, &wanted_branches) { const char *target = pe->path; struct got_reference *target_ref; @@ -2194,7 +2195,7 @@ cmd_checkout(int argc, char *argv[]) struct got_checkout_progress_arg cpa; int *pack_fds = NULL; - TAILQ_INIT(&paths); + RB_INIT(&paths); #ifndef PROFILE if (pledge("stdio rpath wpath cpath fattr flock proc exec sendfd " @@ -2668,12 +2669,12 @@ cmd_update(int argc, char *argv[]) struct got_reference *head_ref = NULL; const char *jumphost = NULL; - TAILQ_INIT(&paths); - TAILQ_INIT(&refs); - TAILQ_INIT(&symrefs); + RB_INIT(&paths); + RB_INIT(&refs); + RB_INIT(&symrefs); TAILQ_INIT(&remote_refs); - TAILQ_INIT(&wanted_branches); - TAILQ_INIT(&wanted_refs); + RB_INIT(&wanted_branches); + RB_INIT(&wanted_refs); while ((ch = getopt(argc, argv, "c:J:qr:vX")) != -1) { switch (ch) { @@ -2907,7 +2908,7 @@ cmd_update(int argc, char *argv[]) } /* Update references provided with the pack file. */ - TAILQ_FOREACH(pe, &refs, entry) { + RB_FOREACH(pe, got_pathlist_head, &refs) { const char *refname = pe->path; struct got_object_id *id = pe->data; struct got_reference *ref; @@ -3410,7 +3411,7 @@ match_changed_paths(int *have_match, struct got_pathli *have_match = 0; - TAILQ_FOREACH(pe, changed_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, changed_paths) { if (regexec(regex, pe->path, 1, &regmatch, 0) == 0) { *have_match = 1; break; @@ -3600,7 +3601,7 @@ print_diffstat(struct got_diffstat_cb_arg *dsa, const if (header != NULL) printf("%s\n", header); - TAILQ_FOREACH(pe, dsa->paths, entry) { + RB_FOREACH(pe, got_pathlist_head, dsa->paths) { struct got_diff_changed_path *cp = pe->data; int pad = dsa->max_path_len - pe->path_len + 1; @@ -3722,7 +3723,7 @@ print_commit(struct got_commit_object *commit, struct if (changed_paths && diffstat == NULL) { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, changed_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, changed_paths) { struct got_diff_changed_path *cp = pe->data; printf(" %c %s\n", cp->status, pe->path); @@ -3784,7 +3785,7 @@ print_commits(struct got_object_id *root_id, struct go struct got_pathlist_head changed_paths; STAILQ_INIT(&reversed_commits); - TAILQ_INIT(&changed_paths); + RB_INIT(&changed_paths); if (search_pattern && regcomp(&regex, search_pattern, REG_EXTENDED | REG_NOSUB | REG_NEWLINE)) @@ -4492,8 +4493,8 @@ cmd_diff(int argc, char *argv[]) memset(&dsa, 0, sizeof(dsa)); TAILQ_INIT(&refs); - TAILQ_INIT(&paths); - TAILQ_INIT(&diffstat_paths); + RB_INIT(&paths); + RB_INIT(&diffstat_paths); #ifndef PROFILE if (pledge("stdio rpath wpath cpath flock proc exec sendfd unveil", @@ -5691,7 +5692,7 @@ cmd_status(int argc, char *argv[]) int ch, i, no_ignores = 0; int *pack_fds = NULL; - TAILQ_INIT(&paths); + RB_INIT(&paths); memset(&st, 0, sizeof(st)); st.status_codes = NULL; @@ -6478,7 +6479,7 @@ cmd_add(int argc, char *argv[]) int ch, can_recurse = 0, no_ignores = 0; int *pack_fds = NULL; - TAILQ_INIT(&paths); + RB_INIT(&paths); #ifndef PROFILE if (pledge("stdio rpath wpath cpath flock proc exec sendfd unveil", @@ -6540,7 +6541,7 @@ cmd_add(int argc, char *argv[]) if (!can_recurse) { char *ondisk_path; struct stat sb; - TAILQ_FOREACH(pe, &paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &paths) { if (asprintf(&ondisk_path, "%s/%s", got_worktree_get_root_path(worktree), pe->path) == -1) { @@ -6623,7 +6624,7 @@ cmd_remove(int argc, char *argv[]) int ignore_missing_paths = 0; int *pack_fds = NULL; - TAILQ_INIT(&paths); + RB_INIT(&paths); #ifndef PROFILE if (pledge("stdio rpath wpath cpath flock proc exec sendfd unveil", @@ -6705,7 +6706,7 @@ cmd_remove(int argc, char *argv[]) if (!can_recurse) { char *ondisk_path; struct stat sb; - TAILQ_FOREACH(pe, &paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &paths) { if (asprintf(&ondisk_path, "%s/%s", got_worktree_get_root_path(worktree), pe->path) == -1) { @@ -7166,7 +7167,7 @@ worktree_has_commitable_path(void *arg, unsigned char if (a->commit_paths != NULL) { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, a->commit_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, a->commit_paths) { if (strncmp(path, pe->path, pe->path_len) == 0) { *a->has_changes = 1; @@ -7198,7 +7199,7 @@ commit_path_changed_in_worktree(struct wt_commitable_p struct got_tree_object *tree = NULL, *ptree = NULL; struct got_object_qid *pid; - TAILQ_INIT(&paths); + RB_INIT(&paths); err = got_object_open_as_commit(&commit, repo, id); if (err) @@ -7349,7 +7350,7 @@ cmd_revert(int argc, char *argv[]) struct choose_patch_arg cpa; int *pack_fds = NULL; - TAILQ_INIT(&paths); + RB_INIT(&paths); #ifndef PROFILE if (pledge("stdio rpath wpath cpath fattr flock proc exec sendfd " @@ -7428,7 +7429,7 @@ cmd_revert(int argc, char *argv[]) if (!can_recurse) { char *ondisk_path; struct stat sb; - TAILQ_FOREACH(pe, &paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &paths) { if (asprintf(&ondisk_path, "%s/%s", got_worktree_get_root_path(worktree), pe->path) == -1) { @@ -7608,7 +7609,7 @@ collect_commit_logmsg(struct got_pathlist_head *commit goto done; } - TAILQ_FOREACH(pe, commitable_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, commitable_paths) { struct got_commitable *ct = pe->data; dprintf(fd, "# %c %s\n", got_commitable_get_status(ct), @@ -7815,7 +7816,7 @@ cmd_commit(int argc, char *argv[]) int i; TAILQ_INIT(&refs); - TAILQ_INIT(&paths); + RB_INIT(&paths); cl_arg.logmsg_path = NULL; #ifndef PROFILE @@ -8108,7 +8109,7 @@ process_logmsg_refs(const char *ref_prefix, size_t pre int found = 0; TAILQ_INIT(&refs); - TAILQ_INIT(&paths); + RB_INIT(&paths); err = got_ref_list(&refs, repo, NULL, got_ref_cmp_by_name, repo); if (err) @@ -8975,7 +8976,7 @@ print_path_info(void *arg, const char *path, mode_t mo * Clear error indication from any of the path arguments which * would cause this file index entry to be displayed. */ - TAILQ_FOREACH(pe, paths, entry) { + RB_FOREACH(pe, got_pathlist_head, paths) { if (got_path_cmp(path, pe->path, strlen(path), pe->path_len) == 0 || got_path_is_child(path, pe->path, pe->path_len)) @@ -9040,7 +9041,7 @@ cmd_info(int argc, char *argv[]) int ch, show_files = 0; int *pack_fds = NULL; - TAILQ_INIT(&paths); + RB_INIT(&paths); #ifndef PROFILE if (pledge("stdio rpath wpath cpath flock proc exec sendfd unveil", @@ -9126,7 +9127,7 @@ cmd_info(int argc, char *argv[]) if (show_files) { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, &paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &paths) { if (pe->path_len == 0) continue; /* @@ -9139,7 +9140,7 @@ cmd_info(int argc, char *argv[]) print_path_info, &paths, check_cancelled, NULL); if (error) goto done; - TAILQ_FOREACH(pe, &paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &paths) { if (pe->data != NULL) { const struct got_error *perr; blob - 211ce127da138b7f0ae6451335215737fabc1c1a blob + 5db2fdbc49f5f220d6a5c3ca99d509315c111ce3 --- gitwrapper/gitwrapper.c +++ gitwrapper/gitwrapper.c @@ -19,6 +19,7 @@ */ #include <sys/queue.h> +#include <sys/tree.h> #include <sys/types.h> #include <sys/uio.h> blob - 36655f1f322184d063373730e92b7dbf08b373a4 blob + 48358ad1144d94badb8e3747f30345948a74c02b --- got/got.c +++ got/got.c @@ -17,6 +17,7 @@ */ #include <sys/queue.h> +#include <sys/tree.h> #include <sys/time.h> #include <sys/types.h> #include <sys/stat.h> @@ -841,7 +842,7 @@ cmd_import(int argc, char *argv[]) int preserve_logmsg = 0; int *pack_fds = NULL; - TAILQ_INIT(&ignores); + RB_INIT(&ignores); #ifndef PROFILE if (pledge("stdio rpath wpath cpath fattr flock proc exec sendfd " @@ -1129,7 +1130,7 @@ fetch_progress(void *arg, const char *message, off_t p * we have all required information. */ if (a->create_configs && !a->configs_created && - !TAILQ_EMPTY(a->config_info.symrefs)) { + !RB_EMPTY(a->config_info.symrefs)) { err = create_config_files(a->config_info.proto, a->config_info.host, a->config_info.port, a->config_info.remote_repo_path, @@ -1223,14 +1224,14 @@ list_remote_refs(struct got_pathlist_head *symrefs, const struct got_error *err; struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, symrefs, entry) { + RB_FOREACH(pe, got_pathlist_head, symrefs) { const char *refname = pe->path; const char *targetref = pe->data; printf("%s: %s\n", refname, targetref); } - TAILQ_FOREACH(pe, refs, entry) { + RB_FOREACH(pe,got_pathlist_head, refs) { const char *refname = pe->path; struct got_object_id *id = pe->data; char *id_str; @@ -1303,7 +1304,7 @@ is_wanted_ref(struct got_pathlist_head *wanted_refs, c { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, wanted_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, wanted_refs) { if (match_wanted_ref(refname, pe->path)) return 1; } @@ -1345,9 +1346,9 @@ create_gotconfig(const char *proto, const char *host, char *branches = NULL, *refs = NULL; ssize_t n; - if (!fetch_all_branches && !TAILQ_EMPTY(wanted_branches)) { + if (!fetch_all_branches && !RB_EMPTY(wanted_branches)) { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, wanted_branches, entry) { + RB_FOREACH(pe, got_pathlist_head, wanted_branches) { char *s; branchname = pe->path; if (strncmp(branchname, "refs/heads/", 11) == 0) @@ -1369,9 +1370,9 @@ create_gotconfig(const char *proto, const char *host, goto done; } } - if (!TAILQ_EMPTY(wanted_refs)) { + if (!RB_EMPTY(wanted_refs)) { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, wanted_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, wanted_refs) { char *s; const char *refname = pe->path; if (strncmp(refname, "refs/", 5) == 0) @@ -1470,9 +1471,9 @@ create_gitconfig(const char *git_url, const char *defa err = got_error_from_errno("asprintf"); goto done; } - } else if (!TAILQ_EMPTY(wanted_branches)) { + } else if (!RB_EMPTY(wanted_branches)) { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, wanted_branches, entry) { + RB_FOREACH(pe, got_pathlist_head, wanted_branches) { char *s; branchname = pe->path; if (strncmp(branchname, "refs/heads/", 11) == 0) @@ -1522,9 +1523,9 @@ create_gitconfig(const char *git_url, const char *defa goto done; } } - if (!TAILQ_EMPTY(wanted_refs)) { + if (!RB_EMPTY(wanted_refs)) { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, wanted_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, wanted_refs) { char *s; const char *refname = pe->path; if (strncmp(refname, "refs/", 5) == 0) @@ -1588,12 +1589,12 @@ create_config_files(const char *proto, const char *hos * If we asked for a set of wanted branches then use the first * one of those. */ - if (!TAILQ_EMPTY(wanted_branches)) { - pe = TAILQ_FIRST(wanted_branches); + if (!RB_EMPTY(wanted_branches)) { + pe = RB_MIN(got_pathlist_head, wanted_branches); default_branch = pe->path; } else { /* First HEAD ref listed by server is the default branch. */ - TAILQ_FOREACH(pe, symrefs, entry) { + RB_FOREACH(pe, got_pathlist_head, symrefs) { const char *refname = pe->path; const char *target = pe->data; @@ -1638,10 +1639,10 @@ cmd_clone(int argc, char *argv[]) int bflag = 0, list_refs_only = 0; int *pack_fds = NULL; - TAILQ_INIT(&refs); - TAILQ_INIT(&symrefs); - TAILQ_INIT(&wanted_branches); - TAILQ_INIT(&wanted_refs); + RB_INIT(&refs); + RB_INIT(&symrefs); + RB_INIT(&wanted_branches); + RB_INIT(&wanted_refs); while ((ch = getopt(argc, argv, "ab:J:lmqR:v")) != -1) { switch (ch) { @@ -1687,16 +1688,16 @@ cmd_clone(int argc, char *argv[]) argc -= optind; argv += optind; - if (fetch_all_branches && !TAILQ_EMPTY(&wanted_branches)) + if (fetch_all_branches && !RB_EMPTY(&wanted_branches)) option_conflict('a', 'b'); if (list_refs_only) { - if (!TAILQ_EMPTY(&wanted_branches)) + if (!RB_EMPTY(&wanted_branches)) option_conflict('l', 'b'); if (fetch_all_branches) option_conflict('l', 'a'); if (mirror_references) option_conflict('l', 'm'); - if (!TAILQ_EMPTY(&wanted_refs)) + if (!RB_EMPTY(&wanted_refs)) option_conflict('l', 'R'); } @@ -1840,7 +1841,7 @@ cmd_clone(int argc, char *argv[]) free(id_str); /* Set up references provided with the pack file. */ - TAILQ_FOREACH(pe, &refs, entry) { + RB_FOREACH(pe, got_pathlist_head, &refs) { const char *refname = pe->path; struct got_object_id *id = pe->data; char *remote_refname; @@ -1878,7 +1879,7 @@ cmd_clone(int argc, char *argv[]) } /* Set the HEAD reference if the server provided one. */ - TAILQ_FOREACH(pe, &symrefs, entry) { + RB_FOREACH(pe, got_pathlist_head, &symrefs) { struct got_reference *target_ref; const char *refname = pe->path; const char *target = pe->data; @@ -1944,7 +1945,7 @@ cmd_clone(int argc, char *argv[]) * a set of wanted branches use the first of one of those * which could be fetched instead. */ - TAILQ_FOREACH(pe, &wanted_branches, entry) { + RB_FOREACH(pe, got_pathlist_head, &wanted_branches) { const char *target = pe->path; struct got_reference *target_ref; @@ -2229,14 +2230,14 @@ delete_missing_refs(struct got_pathlist_head *their_re their_refname = local_refname; } - TAILQ_FOREACH(pe, their_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, their_refs) { if (strcmp(their_refname, pe->path) == 0) break; } if (pe != NULL) continue; - TAILQ_FOREACH(pe, their_symrefs, entry) { + RB_FOREACH(pe, got_pathlist_head, their_symrefs) { if (strcmp(their_refname, pe->path) == 0) break; } @@ -2396,11 +2397,11 @@ cmd_fetch(int argc, char *argv[]) const char *remote_head = NULL, *worktree_branch = NULL; const char *jumphost = NULL; - TAILQ_INIT(&refs); - TAILQ_INIT(&symrefs); + RB_INIT(&refs); + RB_INIT(&symrefs); TAILQ_INIT(&remote_refs); - TAILQ_INIT(&wanted_branches); - TAILQ_INIT(&wanted_refs); + RB_INIT(&wanted_branches); + RB_INIT(&wanted_refs); while ((ch = getopt(argc, argv, "ab:dJ:lqR:r:tvX")) != -1) { switch (ch) { @@ -2459,10 +2460,10 @@ cmd_fetch(int argc, char *argv[]) argc -= optind; argv += optind; - if (fetch_all_branches && !TAILQ_EMPTY(&wanted_branches)) + if (fetch_all_branches && !RB_EMPTY(&wanted_branches)) option_conflict('a', 'b'); if (list_refs_only) { - if (!TAILQ_EMPTY(&wanted_branches)) + if (!RB_EMPTY(&wanted_branches)) option_conflict('l', 'b'); if (fetch_all_branches) option_conflict('l', 'a'); @@ -2474,13 +2475,13 @@ cmd_fetch(int argc, char *argv[]) if (delete_remote) { if (fetch_all_branches) option_conflict('X', 'a'); - if (!TAILQ_EMPTY(&wanted_branches)) + if (!RB_EMPTY(&wanted_branches)) option_conflict('X', 'b'); if (delete_refs) option_conflict('X', 'd'); if (replace_tags) option_conflict('X', 't'); - if (!TAILQ_EMPTY(&wanted_refs)) + if (!RB_EMPTY(&wanted_refs)) option_conflict('X', 'R'); } @@ -2583,7 +2584,7 @@ cmd_fetch(int argc, char *argv[]) goto done; } - if (TAILQ_EMPTY(&wanted_branches)) { + if (RB_EMPTY(&wanted_branches)) { if (!fetch_all_branches) fetch_all_branches = remote->fetch_all_branches; for (i = 0; i < remote->nfetch_branches; i++) { @@ -2593,7 +2594,7 @@ cmd_fetch(int argc, char *argv[]) goto done; } } - if (TAILQ_EMPTY(&wanted_refs)) { + if (RB_EMPTY(&wanted_refs)) { for (i = 0; i < remote->nfetch_refs; i++) { error = got_pathlist_insert(NULL, &wanted_refs, remote->fetch_refs[i], NULL); @@ -2742,7 +2743,7 @@ cmd_fetch(int argc, char *argv[]) } /* Update references provided with the pack file. */ - TAILQ_FOREACH(pe, &refs, entry) { + RB_FOREACH(pe, got_pathlist_head, &refs) { const char *refname = pe->path; struct got_object_id *id = pe->data; struct got_reference *ref; @@ -2829,7 +2830,7 @@ cmd_fetch(int argc, char *argv[]) if (!remote->mirror_references) { /* Update remote HEAD reference if the server provided one. */ - TAILQ_FOREACH(pe, &symrefs, entry) { + RB_FOREACH(pe, got_pathlist_head, &symrefs) { struct got_reference *target_ref; const char *refname = pe->path; const char *target = pe->data; @@ -3105,7 +3106,7 @@ cmd_checkout(int argc, char *argv[]) struct got_checkout_progress_arg cpa; int *pack_fds = NULL; - TAILQ_INIT(&paths); + RB_INIT(&paths); #ifndef PROFILE if (pledge("stdio rpath wpath cpath fattr flock proc exec sendfd " @@ -3625,7 +3626,7 @@ cmd_update(int argc, char *argv[]) struct got_update_progress_arg upa; int *pack_fds = NULL; - TAILQ_INIT(&paths); + RB_INIT(&paths); #ifndef PROFILE if (pledge("stdio rpath wpath cpath fattr flock proc exec sendfd " @@ -3741,7 +3742,7 @@ cmd_update(int argc, char *argv[]) if (branch_name) { struct got_object_id *head_commit_id; - TAILQ_FOREACH(pe, &paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &paths) { if (pe->path_len == 0) continue; error = got_error_msg(GOT_ERR_BAD_PATH, @@ -4188,7 +4189,7 @@ match_changed_paths(int *have_match, struct got_pathli *have_match = 0; - TAILQ_FOREACH(pe, changed_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, changed_paths) { if (regexec(regex, pe->path, 1, &regmatch, 0) == 0) { *have_match = 1; break; @@ -4378,7 +4379,7 @@ print_diffstat(struct got_diffstat_cb_arg *dsa, const if (header != NULL) printf("%s\n", header); - TAILQ_FOREACH(pe, dsa->paths, entry) { + RB_FOREACH(pe, got_pathlist_head, dsa->paths) { struct got_diff_changed_path *cp = pe->data; int pad = dsa->max_path_len - pe->path_len + 1; @@ -4500,7 +4501,7 @@ print_commit(struct got_commit_object *commit, struct if (changed_paths && diffstat == NULL) { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, changed_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, changed_paths) { struct got_diff_changed_path *cp = pe->data; printf(" %c %s\n", cp->status, pe->path); @@ -4562,7 +4563,7 @@ print_commits(struct got_object_id *root_id, struct go struct got_pathlist_head changed_paths; STAILQ_INIT(&reversed_commits); - TAILQ_INIT(&changed_paths); + RB_INIT(&changed_paths); if (search_pattern && regcomp(&regex, search_pattern, REG_EXTENDED | REG_NOSUB | REG_NEWLINE)) @@ -5325,8 +5326,8 @@ cmd_diff(int argc, char *argv[]) memset(&dsa, 0, sizeof(dsa)); TAILQ_INIT(&refs); - TAILQ_INIT(&paths); - TAILQ_INIT(&diffstat_paths); + RB_INIT(&paths); + RB_INIT(&diffstat_paths); #ifndef PROFILE if (pledge("stdio rpath wpath cpath flock proc exec sendfd unveil", @@ -6609,7 +6610,7 @@ cmd_status(int argc, char *argv[]) int ch, i, no_ignores = 0; int *pack_fds = NULL; - TAILQ_INIT(&paths); + RB_INIT(&paths); memset(&st, 0, sizeof(st)); st.status_codes = NULL; @@ -7260,7 +7261,7 @@ cmd_branch(int argc, char *argv[]) char *commit_id_str = NULL, *keyword_idstr = NULL;; int *pack_fds = NULL; - TAILQ_INIT(&paths); + RB_INIT(&paths); #ifndef PROFILE if (pledge("stdio rpath wpath cpath fattr flock proc exec " @@ -8156,7 +8157,7 @@ cmd_add(int argc, char *argv[]) int ch, can_recurse = 0, no_ignores = 0; int *pack_fds = NULL; - TAILQ_INIT(&paths); + RB_INIT(&paths); #ifndef PROFILE if (pledge("stdio rpath wpath cpath flock proc exec sendfd unveil", @@ -8218,7 +8219,7 @@ cmd_add(int argc, char *argv[]) if (!can_recurse) { char *ondisk_path; struct stat sb; - TAILQ_FOREACH(pe, &paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &paths) { if (asprintf(&ondisk_path, "%s/%s", got_worktree_get_root_path(worktree), pe->path) == -1) { @@ -8301,7 +8302,7 @@ cmd_remove(int argc, char *argv[]) int ignore_missing_paths = 0; int *pack_fds = NULL; - TAILQ_INIT(&paths); + RB_INIT(&paths); #ifndef PROFILE if (pledge("stdio rpath wpath cpath flock proc exec sendfd unveil", @@ -8383,7 +8384,7 @@ cmd_remove(int argc, char *argv[]) if (!can_recurse) { char *ondisk_path; struct stat sb; - TAILQ_FOREACH(pe, &paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &paths) { if (asprintf(&ondisk_path, "%s/%s", got_worktree_get_root_path(worktree), pe->path) == -1) { @@ -8858,7 +8859,7 @@ worktree_has_commitable_path(void *arg, unsigned char if (a->commit_paths != NULL) { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, a->commit_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, a->commit_paths) { if (strncmp(path, pe->path, pe->path_len) == 0) { *a->has_changes = 1; @@ -8890,7 +8891,7 @@ commit_path_changed_in_worktree(struct wt_commitable_p struct got_tree_object *tree = NULL, *ptree = NULL; struct got_object_qid *pid; - TAILQ_INIT(&paths); + RB_INIT(&paths); err = got_object_open_as_commit(&commit, repo, id); if (err) @@ -9041,7 +9042,7 @@ cmd_revert(int argc, char *argv[]) struct choose_patch_arg cpa; int *pack_fds = NULL; - TAILQ_INIT(&paths); + RB_INIT(&paths); #ifndef PROFILE if (pledge("stdio rpath wpath cpath fattr flock proc exec sendfd " @@ -9120,7 +9121,7 @@ cmd_revert(int argc, char *argv[]) if (!can_recurse) { char *ondisk_path; struct stat sb; - TAILQ_FOREACH(pe, &paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &paths) { if (asprintf(&ondisk_path, "%s/%s", got_worktree_get_root_path(worktree), pe->path) == -1) { @@ -9301,7 +9302,7 @@ collect_commit_logmsg(struct got_pathlist_head *commit goto done; } - TAILQ_FOREACH(pe, commitable_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, commitable_paths) { struct got_commitable *ct = pe->data; dprintf(fd, "# %c %s\n", got_commitable_get_status(ct), @@ -9494,7 +9495,7 @@ cmd_commit(int argc, char *argv[]) int *pack_fds = NULL; TAILQ_INIT(&refs); - TAILQ_INIT(&paths); + RB_INIT(&paths); cl_arg.logmsg_path = NULL; #ifndef PROFILE @@ -9769,7 +9770,7 @@ send_progress(void *arg, int ncolored, int nfound, int if (success) { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, a->delete_branches, entry) { + RB_FOREACH(pe, got_pathlist_head, a->delete_branches) { const char *branchname = pe->path; if (got_path_cmp(branchname, refname, strlen(branchname), strlen(refname)) == 0) { @@ -9936,12 +9937,12 @@ cmd_send(int argc, char *argv[]) int *pack_fds = NULL; const char *jumphost = NULL; - TAILQ_INIT(&branches); - TAILQ_INIT(&tags); + RB_INIT(&branches); + RB_INIT(&tags); TAILQ_INIT(&all_branches); TAILQ_INIT(&all_tags); - TAILQ_INIT(&delete_args); - TAILQ_INIT(&delete_branches); + RB_INIT(&delete_args); + RB_INIT(&delete_branches); while ((ch = getopt(argc, argv, "ab:d:fJ:qr:Tt:v")) != -1) { switch (ch) { @@ -9997,9 +9998,9 @@ cmd_send(int argc, char *argv[]) argc -= optind; argv += optind; - if (send_all_branches && !TAILQ_EMPTY(&branches)) + if (send_all_branches && !RB_EMPTY(&branches)) option_conflict('a', 'b'); - if (send_all_tags && !TAILQ_EMPTY(&tags)) + if (send_all_tags && !RB_EMPTY(&tags)) option_conflict('T', 't'); @@ -10171,7 +10172,7 @@ cmd_send(int argc, char *argv[]) * with 'got send -d'. * Deleting anything else requires local repository access or Git. */ - TAILQ_FOREACH(pe, &delete_args, entry) { + RB_FOREACH(pe, got_pathlist_head, &delete_args) { const char *branchname = pe->path; char *s; struct got_pathlist_entry *new; @@ -10314,7 +10315,7 @@ process_logmsg_refs(const char *ref_prefix, size_t pre int found = 0; TAILQ_INIT(&refs); - TAILQ_INIT(&paths); + RB_INIT(&paths); err = got_ref_list(&refs, repo, NULL, got_ref_cmp_by_name, repo); if (err) @@ -11518,7 +11519,7 @@ cmd_rebase(int argc, char *argv[]) int *pack_fds = NULL; STAILQ_INIT(&commits); - TAILQ_INIT(&merged_paths); + RB_INIT(&merged_paths); memset(&upa, 0, sizeof(upa)); #ifndef PROFILE @@ -11793,7 +11794,7 @@ cmd_rebase(int argc, char *argv[]) branch_head_commit_id); if (error) goto done; - TAILQ_INIT(&paths); + RB_INIT(&paths); error = got_pathlist_insert(NULL, &paths, "", NULL); if (error) goto done; @@ -12806,7 +12807,7 @@ cmd_histedit(int argc, char *argv[]) STAILQ_INIT(&commits); TAILQ_INIT(&histedit_cmds); - TAILQ_INIT(&merged_paths); + RB_INIT(&merged_paths); memset(&upa, 0, sizeof(upa)); #ifndef PROFILE @@ -13256,7 +13257,7 @@ cmd_histedit(int argc, char *argv[]) struct got_pathlist_head paths; int have_changes = 0; - TAILQ_INIT(&paths); + RB_INIT(&paths); error = got_pathlist_insert(NULL, &paths, "", NULL); if (error) goto done; @@ -13815,7 +13816,7 @@ cmd_merge(int argc, char *argv[]) branch_tip); if (error) goto done; - TAILQ_INIT(&paths); + RB_INIT(&paths); error = got_pathlist_insert(NULL, &paths, "", NULL); if (error) goto done; @@ -13983,7 +13984,7 @@ cmd_stage(int argc, char *argv[]) struct choose_patch_arg cpa; int *pack_fds = NULL; - TAILQ_INIT(&paths); + RB_INIT(&paths); #ifndef PROFILE if (pledge("stdio rpath wpath cpath fattr flock proc exec sendfd " @@ -14119,7 +14120,7 @@ cmd_unstage(int argc, char *argv[]) struct choose_patch_arg cpa; int *pack_fds = NULL; - TAILQ_INIT(&paths); + RB_INIT(&paths); #ifndef PROFILE if (pledge("stdio rpath wpath cpath fattr flock proc exec sendfd " @@ -14609,7 +14610,7 @@ print_path_info(void *arg, const char *path, mode_t mo * Clear error indication from any of the path arguments which * would cause this file index entry to be displayed. */ - TAILQ_FOREACH(pe, paths, entry) { + RB_FOREACH(pe, got_pathlist_head, paths) { if (got_path_cmp(path, pe->path, strlen(path), pe->path_len) == 0 || got_path_is_child(path, pe->path, pe->path_len)) @@ -14674,7 +14675,7 @@ cmd_info(int argc, char *argv[]) int *pack_fds = NULL; int ch, show_files = 0; - TAILQ_INIT(&paths); + RB_INIT(&paths); #ifndef PROFILE if (pledge("stdio rpath wpath cpath flock proc exec sendfd unveil", @@ -14760,7 +14761,7 @@ cmd_info(int argc, char *argv[]) if (show_files) { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, &paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &paths) { if (pe->path_len == 0) continue; /* @@ -14773,7 +14774,7 @@ cmd_info(int argc, char *argv[]) print_path_info, &paths, check_cancelled, NULL); if (error) goto done; - TAILQ_FOREACH(pe, &paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &paths) { if (pe->data != NULL) { const struct got_error *perr; blob - b4498d7b27edc861c011a977cef6c8b66603f09d blob + 5a8c2bc8ec21628c9260de98ee4077f5f878ff15 --- gotadmin/gotadmin.c +++ gotadmin/gotadmin.c @@ -15,6 +15,7 @@ */ #include <sys/queue.h> +#include <sys/tree.h> #include <sys/types.h> #include <ctype.h> @@ -728,7 +729,7 @@ cmd_pack(int argc, char *argv[]) struct got_reflist_entry *re, *new; int *pack_fds = NULL; - TAILQ_INIT(&exclude_args); + RB_INIT(&exclude_args); TAILQ_INIT(&exclude_refs); TAILQ_INIT(&include_refs); @@ -788,7 +789,7 @@ cmd_pack(int argc, char *argv[]) if (error) goto done; - TAILQ_FOREACH(pe, &exclude_args, entry) { + RB_FOREACH(pe, got_pathlist_head, &exclude_args) { const char *refname = pe->path; error = add_ref(&new, &exclude_refs, refname, repo); if (error) @@ -1435,7 +1436,7 @@ cmd_dump(int argc, char *argv[]) int verbosity = 0; int i, ch; - TAILQ_INIT(&exclude_args); + RB_INIT(&exclude_args); TAILQ_INIT(&exclude_refs); TAILQ_INIT(&include_refs); @@ -1487,7 +1488,7 @@ cmd_dump(int argc, char *argv[]) if (error) goto done; - TAILQ_FOREACH(pe, &exclude_args, entry) { + RB_FOREACH(pe, got_pathlist_head, &exclude_args) { refname = pe->path; error = add_ref(&new, &exclude_refs, refname, repo); if (error) @@ -1569,10 +1570,10 @@ is_wanted_ref(struct got_pathlist_head *wanted, const { struct got_pathlist_entry *pe; - if (TAILQ_EMPTY(wanted)) + if (RB_EMPTY(wanted)) return 1; - TAILQ_FOREACH(pe, wanted, entry) { + RB_FOREACH(pe, got_pathlist_head, wanted) { if (strcmp(pe->path, ref) == 0) return 1; } @@ -1685,8 +1686,8 @@ cmd_load(int argc, char *argv[]) int verbosity = 0; int ch, i; - TAILQ_INIT(&include_args); - TAILQ_INIT(&available_refs); + RB_INIT(&include_args); + RB_INIT(&available_refs); #ifndef PROFILE if (pledge("stdio rpath wpath cpath fattr flock proc exec " @@ -1766,7 +1767,7 @@ cmd_load(int argc, char *argv[]) goto done; if (list_refs_only) { - TAILQ_FOREACH(pe, &available_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, &available_refs) { const char *refname = pe->path; struct got_object_id *id = pe->data; char *idstr; @@ -1785,7 +1786,7 @@ cmd_load(int argc, char *argv[]) goto done; /* Update references */ - TAILQ_FOREACH(pe, &available_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, &available_refs) { const struct got_error *unlock_err; struct got_reference *ref; const char *refname = pe->path; blob - 8eb6f4396784abfa7a956c90fb3cc41e5d2b433f blob + 8b82d1907770f8ead09033b724fa42de69e518be --- gotctl/gotctl.c +++ gotctl/gotctl.c @@ -15,6 +15,7 @@ */ #include <sys/queue.h> +#include <sys/tree.h> #include <sys/socket.h> #include <sys/un.h> blob - 41f6842f800bb0722d2303a4924d74865b6d1fba blob + 8d274e36aa1f7805cbd23da72ff2b38109621dea --- gotd/auth.c +++ gotd/auth.c @@ -18,6 +18,7 @@ #include <sys/types.h> #include <sys/socket.h> #include <sys/queue.h> +#include <sys/tree.h> #include <sys/uio.h> #include <errno.h> blob - d0c3603547caa4335b08553a55a7113dfc613d21 blob + 8993f7756e9028f8ef050eefe400427e6566a59b --- gotd/imsg.c +++ gotd/imsg.c @@ -15,6 +15,7 @@ */ #include <sys/queue.h> +#include <sys/tree.h> #include <sys/types.h> #include <sys/uio.h> blob - 5dab7072d9c805c4247a01452c85875d4639f46e blob + 28fbaa765410499bebb4c75973c46de6655912a1 --- gotd/listen.c +++ gotd/listen.c @@ -16,6 +16,7 @@ #include <sys/types.h> #include <sys/queue.h> +#include <sys/tree.h> #include <sys/socket.h> #include <sys/uio.h> blob - b48a3fe7e6a07d8747d390f34683097289a4d6c2 blob + dd67229618c65cd823858180377b61bd8b02830e --- gotd/parse.y +++ gotd/parse.y @@ -25,6 +25,7 @@ #include <sys/time.h> #include <sys/types.h> #include <sys/queue.h> +#include <sys/tree.h> #include <sys/stat.h> #include <ctype.h> @@ -1329,12 +1330,12 @@ conf_new_repo(const char *name) fatalx("%s: calloc", __func__); STAILQ_INIT(&repo->rules); - TAILQ_INIT(&repo->protected_tag_namespaces); - TAILQ_INIT(&repo->protected_branch_namespaces); - TAILQ_INIT(&repo->protected_branches); - TAILQ_INIT(&repo->protected_branches); - TAILQ_INIT(&repo->notification_refs); - TAILQ_INIT(&repo->notification_ref_namespaces); + RB_INIT(&repo->protected_tag_namespaces); + RB_INIT(&repo->protected_branch_namespaces); + RB_INIT(&repo->protected_branches); + RB_INIT(&repo->protected_branches); + RB_INIT(&repo->notification_refs); + RB_INIT(&repo->notification_ref_namespaces); STAILQ_INIT(&repo->notification_targets); if (strlcpy(repo->name, name, sizeof(repo->name)) >= @@ -1423,7 +1424,7 @@ conf_protect_tag_namespace(struct gotd_repo *repo, cha namespace) == -1) return -1; - TAILQ_FOREACH(pe, &repo->protected_branch_namespaces, entry) { + RB_FOREACH(pe, got_pathlist_head, &repo->protected_branch_namespaces) { if (strcmp(pe->path, new) == 0) { yyerror("duplicate protected namespace %s", namespace); return -1; @@ -1443,7 +1444,7 @@ conf_protect_branch_namespace(struct gotd_repo *repo, &repo->protected_branch_namespaces, namespace) == -1) return -1; - TAILQ_FOREACH(pe, &repo->protected_tag_namespaces, entry) { + RB_FOREACH(pe, got_pathlist_head, &repo->protected_tag_namespaces) { if (strcmp(pe->path, new) == 0) { yyerror("duplicate protected namespace %s", namespace); return -1; blob - 77b067240f937a51ae13c32d0bbc9362d7796286 blob + cde254c906d136723be9be3524aa383c26132dad --- gotd/repo_imsg.c +++ gotd/repo_imsg.c @@ -16,6 +16,7 @@ #include <sys/types.h> #include <sys/queue.h> +#include <sys/tree.h> #include <sys/uio.h> #include <event.h> blob - f44eb26f2a6197c25f2795391a684fce6ef79b29 blob + 62e95bc3c4eee3e045d642b2b1a6496f839d03ce --- gotd/repo_read.c +++ gotd/repo_read.c @@ -15,6 +15,7 @@ */ #include <sys/queue.h> +#include <sys/tree.h> #include <sys/types.h> #include <event.h> blob - 00881c209db0d54b36e0c566e676b5446387618e blob + 8f92913331bd60b19ef2fd111b33c55e075f4a01 --- gotd/repo_write.c +++ gotd/repo_write.c @@ -1405,7 +1405,7 @@ verify_packfile(void) if (ref_update->delete_ref) continue; - TAILQ_FOREACH(pe, repo_write.protected_tag_namespaces, entry) { + RB_FOREACH(pe, got_pathlist_head, repo_write.protected_tag_namespaces) { err = protect_tag_namespace(pe->path, &client->pack, packidx, ref_update); if (err) @@ -1437,14 +1437,15 @@ verify_packfile(void) } } - TAILQ_FOREACH(pe, repo_write.protected_branch_namespaces, - entry) { + RB_FOREACH(pe, got_pathlist_head, repo_write.protected_branch_namespaces) + { err = protect_branch_namespace(pe->path, &client->pack, packidx, ref_update); if (err) goto done; } - TAILQ_FOREACH(pe, repo_write.protected_branches, entry) { + RB_FOREACH(pe, got_pathlist_head, repo_write.protected_branches) + { err = protect_branch(pe->path, &client->pack, packidx, ref_update); if (err) @@ -1477,20 +1478,22 @@ protect_refs_from_deletion(void) refname = got_ref_get_name(ref_update->ref); - TAILQ_FOREACH(pe, repo_write.protected_tag_namespaces, entry) { + RB_FOREACH(pe, got_pathlist_head, + repo_write.protected_tag_namespaces) { err = protect_ref_namespace(refname, pe->path); if (err) return err; } - TAILQ_FOREACH(pe, repo_write.protected_branch_namespaces, - entry) { + RB_FOREACH(pe, got_pathlist_head, + repo_write.protected_branch_namespaces) { err = protect_ref_namespace(refname, pe->path); if (err) return err; } - TAILQ_FOREACH(pe, repo_write.protected_branches, entry) { + RB_FOREACH(pe, got_pathlist_head, repo_write.protected_branches) + { if (strcmp(refname, pe->path) == 0) { return got_error_fmt(GOT_ERR_REF_PROTECTED, "%s", refname); @@ -1721,7 +1724,7 @@ print_diffstat(struct got_diffstat_cb_arg *dsa, int fd { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, dsa->paths, entry) { + RB_FOREACH(pe, got_pathlist_head, dsa->paths) { struct got_diff_changed_path *cp = pe->data; int pad = dsa->max_path_len - pe->path_len + 1; @@ -1884,7 +1887,7 @@ print_commits(struct got_object_id *root_id, struct go const int shortlog_threshold = 50; STAILQ_INIT(&reversed_commits); - TAILQ_INIT(&changed_paths); + RB_INIT(&changed_paths); /* XXX first-parent only for now */ err = got_commit_graph_open(&graph, "/", 1); blob - ce6a68ae4e3613742b57a1c5fafd1978318f2ff5 blob + 1c759a341683fe39614e0c779362809c3d1610e2 --- gotd/session_write.c +++ gotd/session_write.c @@ -428,14 +428,14 @@ queue_notification(struct got_object_id *old_id, struc STAILQ_EMPTY(&repo_cfg->notification_targets)) return NULL; /* notifications unused */ - TAILQ_FOREACH(pe, &repo_cfg->notification_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, &repo_cfg->notification_refs) { const char *refname = pe->path; if (strcmp(got_ref_get_name(ref), refname) == 0) break; } if (pe == NULL) { - TAILQ_FOREACH(pe, &repo_cfg->notification_ref_namespaces, - entry) { + RB_FOREACH(pe, got_pathlist_head, + &repo_cfg->notification_ref_namespaces) { const char *namespace = pe->path; err = validate_namespace(namespace); @@ -452,8 +452,8 @@ queue_notification(struct got_object_id *old_id, struc * configuration file then only send notifications if a match * was found. */ - if (pe == NULL && (!TAILQ_EMPTY(&repo_cfg->notification_refs) || - !TAILQ_EMPTY(&repo_cfg->notification_ref_namespaces))) + if (pe == NULL && (!RB_EMPTY(&repo_cfg->notification_refs) || + !RB_EMPTY(&repo_cfg->notification_ref_namespaces))) return NULL; notif = calloc(1, sizeof(*notif)); blob - c578f8cbb9a1c2672039a719cdba04b4eacdb8d9 blob + 13623bc34739f85f1e1611827992c048d0747d09 --- gotsh/gotsh.c +++ gotsh/gotsh.c @@ -15,6 +15,7 @@ */ #include <sys/queue.h> +#include <sys/tree.h> #include <sys/socket.h> #include <sys/un.h> blob - fa0ac810a87d9612d80f8ec79b2bd02e05585ee4 blob + 2a9b146bfbe9dc3e2c817db363f23b0f026365e2 --- gotwebd/got_operations.c +++ gotwebd/got_operations.c @@ -16,6 +16,7 @@ */ #include <sys/queue.h> +#include <sys/tree.h> #include <sys/socket.h> #include <sys/stat.h> blob - 8e2c5e8b2e3842ce24fdd4ba82b911248e36e8e7 blob + bd243664f8ab465eb64c32b988299bfe3b0fadb7 --- gotwebd/gotweb.c +++ gotwebd/gotweb.c @@ -21,6 +21,7 @@ #include <net/if.h> #include <netinet/in.h> #include <sys/queue.h> +#include <sys/tree.h> #include <sys/stat.h> #include <sys/types.h> blob - 1100e919033e225f9500e38d04dc8c9304369742 blob + 8232df1c967a331ed394daaa474c7547e2c93fda --- include/got_path.h +++ include/got_path.h @@ -61,19 +61,18 @@ int got_path_is_child(const char *, const char *, size */ int got_path_cmp(const char *, const char *, size_t, size_t); -/* - * Path lists allow for predictable concurrent iteration over multiple lists - * of paths obtained from disparate sources which don't all provide the same - * ordering guarantees (e.g. git trees, file index, and on-disk directories). - */ + struct got_pathlist_entry { - TAILQ_ENTRY(got_pathlist_entry) entry; + RB_ENTRY(got_pathlist_entry) entry; const char *path; size_t path_len; void *data; /* data pointer provided to got_pathlist_insert() */ }; -TAILQ_HEAD(got_pathlist_head, got_pathlist_entry); +int got_pathlist_cmp(const struct got_pathlist_entry * , const struct got_pathlist_entry *); +RB_HEAD(got_pathlist_head, got_pathlist_entry); +RB_PROTOTYPE(got_pathlist_head, got_pathlist_entry, entry, got_pathlist_cmp); + /* * Insert a path into the list of paths in a predictable order. * The caller should already have initialized the list head. This list stores blob - 1efd31bd7fbba8901c47aba134f6e6aa7381e4f5 blob + 520585806a2fff0f856abd6880e5c48cbacd6069 --- lib/commit_graph.c +++ lib/commit_graph.c @@ -17,6 +17,7 @@ #include <sys/types.h> #include <sys/stat.h> #include <sys/queue.h> +#include <sys/tree.h> #include <sys/stdint.h> #include <limits.h> blob - 11a24fdcbb22ef869c3b17bf02354c6f7a580e97 blob + 5ee4248318a070e5605e27ad3ee7e408896a2ce8 --- lib/deflate.c +++ lib/deflate.c @@ -15,6 +15,7 @@ */ #include <sys/queue.h> +#include <sys/tree.h> #include <errno.h> #include <stdio.h> blob - e43d98ae41c70e48398afaded344bc66a394b968 blob + 2c3f8c2ebcd41b76c90f5701a0b1ffc43fbdccc3 --- lib/delta.c +++ lib/delta.c @@ -15,6 +15,7 @@ */ #include <sys/queue.h> +#include <sys/tree.h> #include <stdio.h> #include <stdlib.h> blob - 6f47d70612b97fe473d6aba91f3907153a33dd56 blob + ca330996f861e3db0b6d6182071f7f81bb4b4144 --- lib/dial.c +++ lib/dial.c @@ -16,6 +16,7 @@ */ #include <sys/queue.h> +#include <sys/tree.h> #include <sys/types.h> #include <sys/socket.h> #include <sys/uio.h> blob - 705da341e0ac7d7a3ac8291c8c6ad8d46b365aee blob + 658c27563232e250780c4d2b9306e9643b58167f --- lib/diff.c +++ lib/diff.c @@ -15,6 +15,7 @@ */ #include <sys/queue.h> +#include <sys/tree.h> #include <sys/stat.h> #include <stdio.h> @@ -121,7 +122,7 @@ get_diffstat(struct got_diffstat_cb_arg *ds, const cha return err; } - pe = TAILQ_LAST(ds->paths, got_pathlist_head); + pe = RB_MAX(got_pathlist_head, ds->paths); diffstat_field_width(&ds->max_path_len, &ds->add_cols, &ds->rm_cols, pe->path_len, change->add, change->rm); @@ -1123,7 +1124,7 @@ diff_paths(struct got_tree_object *tree1, struct got_t struct got_tree_object *subtree1 = NULL, *subtree2 = NULL; struct got_blob_object *blob1 = NULL, *blob2 = NULL; - TAILQ_FOREACH(pe, paths, entry) { + RB_FOREACH(pe, got_pathlist_head, paths) { int type1 = GOT_OBJ_TYPE_ANY, type2 = GOT_OBJ_TYPE_ANY; mode_t mode1 = 0, mode2 = 0; @@ -1315,7 +1316,7 @@ diff_objects_as_trees(struct got_diff_line **lines, si arg.lines = NULL; arg.nlines = 0; } - if (paths == NULL || TAILQ_EMPTY(paths)) + if (paths == NULL || RB_EMPTY(paths)) err = got_diff_tree(tree1, tree2, f1, f2, fd1, fd2, label1, label2, repo, got_diff_blob_output_unidiff, &arg, 1); else blob - b64070e012cce8f1a3fb519298edb01b361b48eb blob + 4e0331d997a587a82491c0c1835d0ae523400561 --- lib/fetch.c +++ lib/fetch.c @@ -145,7 +145,7 @@ got_fetch_pack(struct got_object_id **pack_hash, struc * Prevent fetching of references that won't make any * sense outside of the remote repository's context. */ - TAILQ_FOREACH(pe, wanted_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, wanted_refs) { const char *refname = pe->path; if (strncmp(refname, "refs/got/", 9) == 0 || strncmp(refname, "got/", 4) == 0 || @@ -160,7 +160,7 @@ got_fetch_pack(struct got_object_id **pack_hash, struc for (i = 0; i < nitems(tmpfds); i++) tmpfds[i] = -1; - TAILQ_INIT(&have_refs); + RB_INIT(&have_refs); TAILQ_INIT(&my_refs); if (!list_refs_only) { blob - 6ddd929ab113d775d617c28c07573f2012ec924c blob + dbef298e12a03f1a40e8adf8a5cffe916aca0681 --- lib/fileindex.c +++ lib/fileindex.c @@ -1060,9 +1060,10 @@ have_tracked_file_in_dir(struct got_fileindex *fileind static const struct got_error * walk_dir(struct got_pathlist_entry **next, struct got_fileindex *fileindex, - struct got_fileindex_entry **ie, struct got_pathlist_entry *dle, int fd, - const char *path, const char *rootpath, struct got_repository *repo, - int ignore, struct got_fileindex_diff_dir_cb *cb, void *cb_arg) + struct got_fileindex_entry **ie, struct got_pathlist_entry *dle, + struct got_pathlist_head *dlh, int fd, const char *path, + const char *rootpath, struct got_repository *repo, int ignore, + struct got_fileindex_diff_dir_cb *cb, void *cb_arg) { const struct got_error *err = NULL; struct dirent *de = dle->data; @@ -1081,7 +1082,7 @@ walk_dir(struct got_pathlist_entry **next, struct got_ char *subdirpath; struct got_pathlist_head subdirlist; - TAILQ_INIT(&subdirlist); + RB_INIT(&subdirlist); if (asprintf(&subpath, "%s%s%s", path, path[0] == '\0' ? "" : "/", de->d_name) == -1) @@ -1096,7 +1097,7 @@ walk_dir(struct got_pathlist_entry **next, struct got_ O_RDONLY | O_NOFOLLOW | O_DIRECTORY | O_CLOEXEC); if (subdirfd == -1) { if (errno == EACCES) { - *next = TAILQ_NEXT(dle, entry); + *next = RB_NEXT(got_pathlist_head, dlh, dle); return NULL; } err = got_error_from_errno2("openat", subdirpath); @@ -1132,7 +1133,7 @@ walk_dir(struct got_pathlist_entry **next, struct got_ return err; } - *next = TAILQ_NEXT(dle, entry); + *next = RB_NEXT(got_pathlist_head, dlh, dle); return NULL; } @@ -1177,7 +1178,7 @@ diff_fileindex_dir(struct got_fileindex *fileindex, return err; } - dle = TAILQ_FIRST(dirlist); + dle = RB_MIN(got_pathlist_head, dirlist); while ((*ie && got_path_is_child((*ie)->path, path, path_len)) || dle) { if (dle && *ie) { char *de_path; @@ -1201,9 +1202,10 @@ diff_fileindex_dir(struct got_fileindex *fileindex, if (err) break; *ie = walk_fileindex(fileindex, *ie); - err = walk_dir(&dle, fileindex, ie, dle, dirfd, - path, rootpath, repo, 0, cb, cb_arg); - } else if (cmp < 0 ) { + err = walk_dir(&dle, fileindex, ie, dle, + dirlist, dirfd, path, rootpath, repo, 0, + cb, cb_arg); + } else if (cmp < 0) { err = cb->diff_old(cb_arg, *ie, path); if (err) break; @@ -1213,8 +1215,9 @@ diff_fileindex_dir(struct got_fileindex *fileindex, dirfd); if (err) break; - err = walk_dir(&dle, fileindex, ie, dle, dirfd, - path, rootpath, repo, ignore, cb, cb_arg); + err = walk_dir(&dle, fileindex, ie, dle, + dirlist, dirfd, path, rootpath, repo, + ignore, cb, cb_arg); } if (err) break; @@ -1231,8 +1234,8 @@ diff_fileindex_dir(struct got_fileindex *fileindex, err = cb->diff_new(&ignore, cb_arg, de, path, dirfd); if (err) break; - err = walk_dir(&dle, fileindex, ie, dle, dirfd, path, - rootpath, repo, ignore, cb, cb_arg); + err = walk_dir(&dle, fileindex, ie, dle, dirlist, + dirfd, path, rootpath, repo, ignore, cb, cb_arg); if (err) break; } @@ -1252,7 +1255,7 @@ got_fileindex_diff_dir(struct got_fileindex *fileindex int fd2; DIR *dir; - TAILQ_INIT(&dirlist); + RB_INIT(&dirlist); /* * Duplicate the file descriptor so we can call closedir() below blob - 7bf09a8a6503e2cf488f090ab7a98b0a0762ae04 blob + f8a58e05685c1a15956029d0833c3014e3008d78 --- lib/gitproto.c +++ lib/gitproto.c @@ -16,6 +16,7 @@ */ #include <sys/queue.h> +#include <sys/tree.h> #include <sys/types.h> #include <ctype.h> blob - e8f06f56c03a04d123c91c39f96c6bc046cb71d9 blob + 49f05411c2efb58063883962301c09d2319d19e6 --- lib/inflate.c +++ lib/inflate.c @@ -15,6 +15,7 @@ */ #include <sys/queue.h> +#include <sys/tree.h> #include <errno.h> #include <stdio.h> blob - 0af419be5282778934e8a5369c5793756c35ecd3 blob + 8a796d4d28606f8e51d7207a19b3cb470facba06 --- lib/lockfile.c +++ lib/lockfile.c @@ -16,6 +16,7 @@ #include <sys/stat.h> #include <sys/queue.h> +#include <sys/tree.h> #include <errno.h> #include <fcntl.h> blob - c3f64cf304de14ee32b20d2d42f888f38bec81a0 blob + 9d98158fc39b736def37140f6711f0da05badf51 --- lib/object_create.c +++ lib/object_create.c @@ -17,6 +17,7 @@ #include <sys/types.h> #include <sys/stat.h> #include <sys/queue.h> +#include <sys/tree.h> #include <sys/wait.h> #include <ctype.h> @@ -329,7 +330,7 @@ got_object_tree_create(struct got_object_id **id, return got_error_from_errno("calloc"); i = 0; - TAILQ_FOREACH(pe, paths, entry) + RB_FOREACH(pe, got_pathlist_head, paths) sorted_entries[i++] = pe->data; mergesort(sorted_entries, nentries, sizeof(struct got_tree_entry *), sort_tree_entries_the_way_git_likes_it); blob - 5b83d584098fac8855f9938cbe05d3425d7c6bde blob + ed36f2076d71d7ed6931ebfd54eac2aa82fc6264 --- lib/pack.c +++ lib/pack.c @@ -17,6 +17,7 @@ #include <sys/types.h> #include <sys/stat.h> #include <sys/queue.h> +#include <sys/tree.h> #include <sys/uio.h> #include <sys/mman.h> #include <sys/resource.h> blob - 51eb2fd9f78c26e8b8bdecf029482685172ecfe7 blob + c6787c3643ca1ced91d4ef5d2530f153f72bb6e0 --- lib/pack_create.c +++ lib/pack_create.c @@ -489,7 +489,7 @@ got_pack_find_pack_for_reuse(struct got_packidx **best *best_packidx = NULL; - TAILQ_FOREACH(pe, &repo->packidx_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &repo->packidx_paths) { const char *path_packidx = pe->path; struct got_packidx *packidx; int nobj; @@ -1142,7 +1142,7 @@ got_pack_find_pack_for_commit_painting(struct got_pack * Find the largest pack which contains at least some of the * commits we are interested in. */ - TAILQ_FOREACH(pe, &repo->packidx_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &repo->packidx_paths) { const char *path_packidx = pe->path; struct got_packidx *packidx; int nobj, idx, ncommits = 0; @@ -1278,7 +1278,7 @@ find_pack_for_enumeration(struct got_packidx **best_pa * Find the largest pack which contains at least some of the * commits and tags we are interested in. */ - TAILQ_FOREACH(pe, &repo->packidx_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &repo->packidx_paths) { const char *path_packidx = pe->path; struct got_packidx *packidx; int nobj, i, idx, ncommits = 0; blob - 0e7c4171ee06743bd3b8004b3c0b3158aa3118da blob + 1e2281754794ae39f794df658cc348bd6aaf1490 --- lib/patch.c +++ lib/patch.c @@ -22,6 +22,7 @@ #include <sys/types.h> #include <sys/queue.h> +#include <sys/tree.h> #include <sys/socket.h> #include <sys/stat.h> #include <sys/uio.h> blob - 8242bbe0f1553766e05f3b6750c7a283387e0907 blob + 19b5fc1b23828a64e772094208f1a08e0372df5a --- lib/path.c +++ lib/path.c @@ -17,6 +17,7 @@ */ #include <sys/queue.h> +#include <sys/tree.h> #include <sys/stat.h> #include <errno.h> @@ -213,43 +214,29 @@ got_path_cmp(const char *path1, const char *path2, siz return (unsigned char)path1[i] < (unsigned char)path2[i] ? -1 : 1; } +int +got_pathlist_cmp(const struct got_pathlist_entry *p1, + const struct got_pathlist_entry *p2) +{ + return got_path_cmp(p1->path, p2->path, p1->path_len, p2->path_len); +} + const struct got_error * got_pathlist_insert(struct got_pathlist_entry **inserted, struct got_pathlist_head *pathlist, const char *path, void *data) { - struct got_pathlist_entry *new, *pe; + struct got_pathlist_entry *new; size_t path_len = strlen(path); if (inserted) *inserted = NULL; - - /* - * Many callers will provide paths in a somewhat sorted order while - * constructing a path list from inputs such as tree objects or - * dirents. Iterating backwards from the tail of the list should - * be more efficient than traversing through the entire list each - * time an element is inserted. - */ - pe = TAILQ_LAST(pathlist, got_pathlist_head); - while (pe) { - int cmp = got_path_cmp(pe->path, path, pe->path_len, path_len); - if (cmp == 0) - return NULL; /* duplicate */ - else if (cmp < 0) - break; - pe = TAILQ_PREV(pe, got_pathlist_head, entry); - } - new = malloc(sizeof(*new)); if (new == NULL) return got_error_from_errno("malloc"); new->path = path; new->path_len = path_len; new->data = data; - if (pe) - TAILQ_INSERT_AFTER(pathlist, pe, new, entry); - else - TAILQ_INSERT_HEAD(pathlist, new, entry); + RB_INSERT(got_pathlist_head, pathlist, new); if (inserted) *inserted = new; return NULL; @@ -258,9 +245,9 @@ got_pathlist_insert(struct got_pathlist_entry **insert void got_pathlist_free(struct got_pathlist_head *pathlist, int freemask) { - struct got_pathlist_entry *pe; + struct got_pathlist_entry *pe, *temp; - while ((pe = TAILQ_FIRST(pathlist)) != NULL) { + RB_FOREACH_SAFE(pe, got_pathlist_head, pathlist, temp) { if (freemask & GOT_PATHLIST_FREE_PATH) { free((char *)pe->path); pe->path = NULL; @@ -269,7 +256,7 @@ got_pathlist_free(struct got_pathlist_head *pathlist, free(pe->data); pe->data = NULL; } - TAILQ_REMOVE(pathlist, pe, entry); + RB_REMOVE(got_pathlist_head, pathlist, pe); free(pe); } } @@ -549,3 +536,5 @@ got_path_move_file(const char *oldpath, const char *ne return NULL; } + +RB_GENERATE(got_pathlist_head, got_pathlist_entry, entry, got_pathlist_cmp); blob - 4d97f68370673cd0b8596deaab214d88a71a195b blob + 2c49d4419a4c395afafe7cca1614b53619d50ed5 --- lib/privsep.c +++ lib/privsep.c @@ -17,6 +17,7 @@ #include <sys/types.h> #include <sys/queue.h> +#include <sys/tree.h> #include <sys/uio.h> #include <sys/wait.h> @@ -595,11 +596,11 @@ got_privsep_send_fetch_req(struct imsgbuf *ibuf, int f fetchreq.worktree_branch_len = worktree_branch_len; if (remote_head != NULL) fetchreq.remote_head_len = remote_head_len; - TAILQ_FOREACH(pe, have_refs, entry) + RB_FOREACH(pe, got_pathlist_head, have_refs) fetchreq.n_have_refs++; - TAILQ_FOREACH(pe, wanted_branches, entry) + RB_FOREACH(pe, got_pathlist_head, wanted_branches) fetchreq.n_wanted_branches++; - TAILQ_FOREACH(pe, wanted_refs, entry) + RB_FOREACH(pe, got_pathlist_head, wanted_refs) fetchreq.n_wanted_refs++; if (imsg_add(wbuf, &fetchreq, sizeof(fetchreq)) == -1) return got_error_from_errno("imsg_add FETCH_REQUEST"); @@ -626,7 +627,7 @@ got_privsep_send_fetch_req(struct imsgbuf *ibuf, int f if (err) return err; - TAILQ_FOREACH(pe, have_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, have_refs) { const char *name = pe->path; size_t name_len = pe->path_len; struct got_object_id *id = pe->data; @@ -650,7 +651,7 @@ got_privsep_send_fetch_req(struct imsgbuf *ibuf, int f return err; } - TAILQ_FOREACH(pe, wanted_branches, entry) { + RB_FOREACH(pe, got_pathlist_head, wanted_branches) { const char *name = pe->path; size_t name_len = pe->path_len; @@ -675,7 +676,7 @@ got_privsep_send_fetch_req(struct imsgbuf *ibuf, int f return err; } - TAILQ_FOREACH(pe, wanted_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, wanted_refs) { const char *name = pe->path; size_t name_len = pe->path_len; @@ -899,9 +900,9 @@ got_privsep_send_send_req(struct imsgbuf *ibuf, int fd memset(&zero_id, 0, sizeof(zero_id)); memset(&sendreq, 0, sizeof(sendreq)); sendreq.verbosity = verbosity; - TAILQ_FOREACH(pe, have_refs, entry) + RB_FOREACH(pe, got_pathlist_head, have_refs) sendreq.nrefs++; - TAILQ_FOREACH(pe, delete_refs, entry) + RB_FOREACH(pe, got_pathlist_head, delete_refs) sendreq.nrefs++; if (imsg_compose(ibuf, GOT_IMSG_SEND_REQUEST, 0, 0, fd, &sendreq, sizeof(sendreq)) == -1) { @@ -915,7 +916,7 @@ got_privsep_send_send_req(struct imsgbuf *ibuf, int fd if (err) goto done; - TAILQ_FOREACH(pe, have_refs, entry) { + RB_FOREACH(pe, got_pathlist_head ,have_refs) { const char *name = pe->path; size_t name_len = pe->path_len; struct got_object_id *id = pe->data; @@ -924,7 +925,7 @@ got_privsep_send_send_req(struct imsgbuf *ibuf, int fd goto done; } - TAILQ_FOREACH(pe, delete_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, delete_refs) { const char *name = pe->path; size_t name_len = pe->path_len; err = send_send_ref(name, name_len, &zero_id, 1, ibuf); blob - b79065ff8ad9f1c2ab6d0c59c7cbb5c02c6b2467 blob + 6737bf650daa76886cbc9ad90d24404103479dd7 --- lib/reference.c +++ lib/reference.c @@ -16,6 +16,7 @@ #include <sys/types.h> #include <sys/queue.h> +#include <sys/tree.h> #include <sys/stat.h> #include <errno.h> blob - f50a14103f7f51da97f88f3efea4286d891e3e65 blob + 693866bdc86723dfd79e3579b540f1364d921c2e --- lib/repository.c +++ lib/repository.c @@ -712,7 +712,7 @@ got_repo_open(struct got_repository **repop, const cha return got_error_from_errno("calloc"); RB_INIT(&repo->packidx_bloom_filters); - TAILQ_INIT(&repo->packidx_paths); + RB_INIT(&repo->packidx_paths); for (i = 0; i < nitems(repo->privsep_children); i++) { memset(&repo->privsep_children[i], 0, @@ -1303,9 +1303,9 @@ purge_packidx_paths(struct got_pathlist_head *packidx_ { struct got_pathlist_entry *pe; - while (!TAILQ_EMPTY(packidx_paths)) { - pe = TAILQ_FIRST(packidx_paths); - TAILQ_REMOVE(packidx_paths, pe, entry); + while (!RB_EMPTY(packidx_paths)) { + pe = RB_MIN(got_pathlist_head, packidx_paths); + RB_REMOVE(got_pathlist_head, packidx_paths, pe); free((char *)pe->path); free(pe); } @@ -1327,7 +1327,7 @@ refresh_packidx_paths(struct got_repository *repo) err = got_error_from_errno2("stat", objects_pack_dir); goto done; } - } else if (TAILQ_EMPTY(&repo->packidx_paths) || + } else if (RB_EMPTY(&repo->packidx_paths) || sb.st_mtim.tv_sec != repo->pack_path_mtime.tv_sec || sb.st_mtim.tv_nsec != repo->pack_path_mtime.tv_nsec) { purge_packidx_paths(&repo->packidx_paths); @@ -1382,7 +1382,7 @@ got_repo_search_packidx(struct got_packidx **packidx, if (err) return err; - TAILQ_FOREACH(pe, &repo->packidx_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &repo->packidx_paths) { const char *path_packidx = pe->path; int is_cached = 0; @@ -1833,7 +1833,7 @@ retry: tv.tv_sec = repo->pack_path_mtime.tv_sec; tv.tv_nsec = repo->pack_path_mtime.tv_nsec; - TAILQ_FOREACH(pe, &repo->packidx_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &repo->packidx_paths) { const char *path_packidx; struct got_packidx *packidx; struct got_object_qid *qid; @@ -2355,7 +2355,7 @@ write_tree(struct got_object_id **new_tree_id, const c *new_tree_id = NULL; - TAILQ_INIT(&paths); + RB_INIT(&paths); dir = opendir(path_dir); if (dir == NULL) { @@ -2376,7 +2376,7 @@ write_tree(struct got_object_id **new_tree_id, const c if (err) goto done; - TAILQ_FOREACH(pe, ignores, entry) { + RB_FOREACH(pe, got_pathlist_head, ignores) { if (type == DT_DIR && pe->path_len > 0 && pe->path[pe->path_len - 1] == '/') { char stripped[PATH_MAX]; @@ -2421,13 +2421,13 @@ write_tree(struct got_object_id **new_tree_id, const c nentries++; } - if (TAILQ_EMPTY(&paths)) { + if (RB_EMPTY(&paths)) { err = got_error_msg(GOT_ERR_NO_TREE_ENTRY, "cannot create tree without any entries"); goto done; } - TAILQ_FOREACH(pe, &paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &paths) { struct got_tree_entry *te = pe->data; char *path; if (!S_ISREG(te->mode) && !S_ISLNK(te->mode)) blob - c09e9252dd552a6939292b6dd5653ee79ef2090b blob + 6c74bdbaad86d5fa1835fd9ad75731dd69cd638b --- lib/repository_admin.c +++ lib/repository_admin.c @@ -1345,7 +1345,7 @@ repo_purge_redundant_packfiles(struct got_repository * int remove, redundant_packs = 0; npacks = 0; - TAILQ_FOREACH(pe, &repo->packidx_paths, entry) + RB_FOREACH(pe, got_pathlist_head, &repo->packidx_paths) npacks++; if (npacks == 0) @@ -1356,7 +1356,7 @@ repo_purge_redundant_packfiles(struct got_repository * return got_error_from_errno("calloc"); i = 0; - TAILQ_FOREACH(pe, &repo->packidx_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &repo->packidx_paths) { err = got_repo_get_packidx(&packidx, pe->path, repo); if (err) goto done; blob - 348d1dbb26e60918ccd5c3ea7b3106ec92916e40 blob + 22ef7b9115f249c75e351c48ef60688e463dfa39 --- lib/send.c +++ lib/send.c @@ -266,16 +266,12 @@ realloc_ids(struct got_object_id ***ids, size_t *nallo static struct got_pathlist_entry * find_ref(struct got_pathlist_head *refs, const char *refname) { - struct got_pathlist_entry *pe; + struct got_pathlist_entry find; - TAILQ_FOREACH(pe, refs, entry) { - if (got_path_cmp(pe->path, refname, strlen(pe->path), - strlen(refname)) == 0) { - return pe; - } - } + find.path = refname; + find.path_len = strlen(refname); + return RB_FIND(got_pathlist_head, refs, &find); - return NULL; } static const struct got_error * @@ -366,14 +362,14 @@ got_send_pack(const char *remote_name, struct got_path FILE *delta_cache = NULL; char *s = NULL; - TAILQ_INIT(&have_refs); - TAILQ_INIT(&their_refs); + RB_INIT(&have_refs); + RB_INIT(&their_refs); if (got_repo_get_object_format(repo) != GOT_HASH_SHA1) return got_error_fmt(GOT_ERR_NOT_IMPL, "sha256 object IDs unsupported in network protocol"); - TAILQ_FOREACH(pe, branch_names, entry) { + RB_FOREACH(pe, got_pathlist_head, branch_names) { const char *branchname = pe->path; const char *targetname = pe->data; @@ -401,7 +397,7 @@ got_send_pack(const char *remote_name, struct got_path s = NULL; } - TAILQ_FOREACH(pe, delete_branches, entry) { + RB_FOREACH(pe, got_pathlist_head, delete_branches) { const char *branchname = pe->path; struct got_pathlist_entry *ref; if (strncmp(branchname, "refs/heads/", 11) != 0) { @@ -418,7 +414,7 @@ got_send_pack(const char *remote_name, struct got_path } } - TAILQ_FOREACH(pe, tag_names, entry) { + RB_FOREACH(pe, got_pathlist_head, tag_names) { const char *tagname = pe->path; if (strncmp(tagname, "refs/tags/", 10) != 0) { if (asprintf(&s, "refs/tags/%s", tagname) == -1) { @@ -441,7 +437,7 @@ got_send_pack(const char *remote_name, struct got_path s = NULL; } - if (TAILQ_EMPTY(&have_refs) && TAILQ_EMPTY(delete_branches)) { + if (RB_EMPTY(&have_refs) && RB_EMPTY(delete_branches)) { err = got_error(GOT_ERR_SEND_EMPTY); goto done; } @@ -492,7 +488,7 @@ got_send_pack(const char *remote_name, struct got_path * Prepare the array of our object IDs which * will be needed for generating a pack file. */ - TAILQ_FOREACH(pe, &have_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, &have_refs) { struct got_object_id *id = pe->data; err = realloc_ids(&our_ids, &nalloc_ours, nours + 1); @@ -517,7 +513,7 @@ got_send_pack(const char *remote_name, struct got_path * This array will be used to exclude objects which already * exist on the server from our pack file. */ - TAILQ_FOREACH(pe, &their_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, &their_refs) { const char *refname = pe->path; struct got_object_id *their_id = pe->data; int have_their_id; @@ -611,14 +607,14 @@ got_send_pack(const char *remote_name, struct got_path } /* Account for any new references we are going to upload. */ - TAILQ_FOREACH(pe, &have_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, &have_refs) { const char *refname = pe->path; if (find_ref(&their_refs, refname) == NULL) refs_to_send++; } /* Account for any existing references we are going to delete. */ - TAILQ_FOREACH(pe, delete_branches, entry) { + RB_FOREACH(pe, got_pathlist_head, delete_branches) { const char *branchname = pe->path; if (find_ref(&their_refs, branchname)) refs_to_delete++; blob - c8fe03020a4cf36fb6886cdd20c9f5c8c14ba2fd blob + 4a2bab0b7932ec20883e152b231992ed8b75e0f4 --- lib/serve.c +++ lib/serve.c @@ -16,6 +16,7 @@ #include <sys/types.h> #include <sys/queue.h> +#include <sys/tree.h> #include <sys/uio.h> #include <errno.h> blob - 936dc8f7691a930afed9b877b099366102eecf50 blob + df89f493b283c3c8957846b5f60994c98756d8ae --- lib/worktree.c +++ lib/worktree.c @@ -2833,7 +2833,7 @@ got_worktree_checkout_files(struct got_worktree *workt goto done; /* Map all specified paths to in-repository trees. */ - TAILQ_FOREACH(pe, paths, entry) { + RB_FOREACH(pe, got_pathlist_head, paths) { tpd = malloc(sizeof(*tpd)); if (tpd == NULL) { err = got_error_from_errno("malloc"); @@ -2873,7 +2873,7 @@ got_worktree_checkout_files(struct got_worktree *workt goto done; tpd = STAILQ_FIRST(&tree_paths); - TAILQ_FOREACH(pe, paths, entry) { + RB_FOREACH(pe, got_pathlist_head, paths) { struct bump_base_commit_id_arg bbc_arg; err = checkout_files(worktree, fileindex, tpd->relpath, @@ -3715,7 +3715,7 @@ free_ignores(struct got_pathlist_head *ignores) { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, ignores, entry) { + RB_FOREACH(pe, got_pathlist_head, ignores) { struct got_pathlist_head *ignorelist = pe->data; got_pathlist_free(ignorelist, GOT_PATHLIST_FREE_PATH); @@ -3736,7 +3736,7 @@ read_ignores(struct got_pathlist_head *ignores, const ignorelist = calloc(1, sizeof(*ignorelist)); if (ignorelist == NULL) return got_error_from_errno("calloc"); - TAILQ_INIT(ignorelist); + RB_INIT(ignorelist); while ((linelen = getline(&line, &linesize, f)) != -1) { if (linelen > 0 && line[linelen - 1] == '\n') @@ -3810,11 +3810,11 @@ match_ignores(struct got_pathlist_head *ignores, const struct got_pathlist_entry *pe; /* Handle patterns which match in all directories. */ - TAILQ_FOREACH(pe, ignores, entry) { + RB_FOREACH(pe, got_pathlist_head, ignores) { struct got_pathlist_head *ignorelist = pe->data; struct got_pathlist_entry *pi; - TAILQ_FOREACH(pi, ignorelist, entry) { + RB_FOREACH(pi, got_pathlist_head, ignorelist) { const char *p; if (pi->path_len < 3 || @@ -3842,12 +3842,12 @@ match_ignores(struct got_pathlist_head *ignores, const * parents, so we can find the most specific ignorelist by walking * ignores backwards. */ - pe = TAILQ_LAST(ignores, got_pathlist_head); + pe = RB_MAX(got_pathlist_head, ignores); while (pe) { if (got_path_is_child(path, pe->path, pe->path_len)) { struct got_pathlist_head *ignorelist = pe->data; struct got_pathlist_entry *pi; - TAILQ_FOREACH(pi, ignorelist, entry) { + RB_FOREACH(pi, got_pathlist_head, ignorelist) { int flags = FNM_LEADING_DIR; if (strstr(pi->path, "/**/") == NULL) flags |= FNM_PATHNAME; @@ -3857,7 +3857,7 @@ match_ignores(struct got_pathlist_head *ignores, const return 1; } } - pe = TAILQ_PREV(pe, got_pathlist_head, entry); + pe = RB_PREV(got_pathlist_head, ignores, pe); } return 0; @@ -4087,7 +4087,7 @@ report_children(struct got_pathlist_head *children, struct got_pathlist_entry *pe; char *ondisk_path = NULL; - TAILQ_FOREACH(pe, children, entry) { + RB_FOREACH(pe, got_pathlist_head, children) { if (cancel_cb) { err = cancel_cb(cancel_arg); if (err) @@ -4130,8 +4130,8 @@ worktree_status(struct got_worktree *worktree, const c struct got_pathlist_head ignores, missing_children; struct got_fileindex_entry *ie; - TAILQ_INIT(&ignores); - TAILQ_INIT(&missing_children); + RB_INIT(&ignores); + RB_INIT(&missing_children); if (asprintf(&ondisk_path, "%s%s%s", worktree->root_path, path[0] ? "/" : "", path) == -1) @@ -4168,7 +4168,7 @@ worktree_status(struct got_worktree *worktree, const c if (err) goto done; } - if (TAILQ_EMPTY(&missing_children)) { + if (RB_EMPTY(&missing_children)) { err = report_single_file_status(path, ondisk_path, fileindex, status_cb, status_arg, repo, @@ -4237,7 +4237,7 @@ got_worktree_status(struct got_worktree *worktree, if (err) return err; - TAILQ_FOREACH(pe, paths, entry) { + RB_FOREACH(pe, got_pathlist_head, paths) { err = worktree_status(worktree, pe->path, fileindex, repo, status_cb, status_arg, cancel_cb, cancel_arg, no_ignores, 0); @@ -4462,7 +4462,7 @@ got_worktree_schedule_add(struct got_worktree *worktre saa.progress_arg = progress_arg; saa.repo = repo; - TAILQ_FOREACH(pe, paths, entry) { + RB_FOREACH(pe, got_pathlist_head, paths) { err = worktree_status(worktree, pe->path, fileindex, repo, schedule_addition, &saa, NULL, NULL, no_ignores, 0); if (err) @@ -4657,7 +4657,7 @@ got_worktree_schedule_delete(struct got_worktree *work sda.ignore_missing_paths = ignore_missing_paths; sda.status_codes = status_codes; - TAILQ_FOREACH(pe, paths, entry) { + RB_FOREACH(pe, got_pathlist_head, paths) { char *ondisk_status_path; if (asprintf(&ondisk_status_path, "%s%s%s", @@ -5254,8 +5254,8 @@ revert_file(void *arg, unsigned char status, unsigned if (a->added_files_to_unlink) { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, a->added_files_to_unlink, - entry) { + RB_FOREACH(pe, got_pathlist_head, + a->added_files_to_unlink) { if (got_path_cmp(pe->path, relpath, pe->path_len, strlen(relpath))) continue; @@ -5438,7 +5438,7 @@ got_worktree_revert(struct got_worktree *worktree, rfa.patch_arg = patch_arg; rfa.repo = repo; rfa.unlink_added_files = 0; - TAILQ_FOREACH(pe, paths, entry) { + RB_FOREACH(pe, got_pathlist_head, paths) { err = worktree_status(worktree, pe->path, fileindex, repo, revert_file, &rfa, NULL, NULL, 1, 0); if (err) @@ -6042,7 +6042,7 @@ match_modified_subtree(int *modified, struct got_tree_ te->name) == -1) return got_error_from_errno("asprintf"); - TAILQ_FOREACH(pe, commitable_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, commitable_paths) { struct got_commitable *ct = pe->data; *modified = got_path_is_child(ct->in_repo_path, te_path, strlen(te_path)); @@ -6064,7 +6064,7 @@ match_deleted_or_modified_ct(struct got_commitable **c *ctp = NULL; - TAILQ_FOREACH(pe, commitable_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, commitable_paths) { struct got_commitable *ct = pe->data; char *ct_name = NULL; int path_matches; @@ -6164,11 +6164,11 @@ write_tree(struct got_object_id **new_tree_id, int *ne struct got_tree_entry *te, *new_te = NULL; struct got_pathlist_entry *pe; - TAILQ_INIT(&paths); + RB_INIT(&paths); *nentries = 0; /* Insert, and recurse into, newly added entries first. */ - TAILQ_FOREACH(pe, commitable_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, commitable_paths) { struct got_commitable *ct = pe->data; char *child_path = NULL, *slash; @@ -6326,7 +6326,7 @@ update_fileindex_after_commit(struct got_worktree *wor struct got_pathlist_entry *pe; char *relpath = NULL; - TAILQ_FOREACH(pe, commitable_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, commitable_paths) { struct got_fileindex_entry *ie; struct got_commitable *ct = pe->data; @@ -6478,7 +6478,7 @@ commit_worktree(struct got_object_id **new_commit_id, } /* Create blobs from added and modified files and record their IDs. */ - TAILQ_FOREACH(pe, commitable_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, commitable_paths) { struct got_commitable *ct = pe->data; char *ondisk_path; @@ -6585,7 +6585,7 @@ check_path_is_commitable(const char *path, struct got_pathlist_entry *cpe = NULL; size_t path_len = strlen(path); - TAILQ_FOREACH(cpe, commitable_paths, entry) { + RB_FOREACH(cpe, got_pathlist_head, commitable_paths) { struct got_commitable *ct = cpe->data; const char *ct_path = ct->path; @@ -6623,7 +6623,7 @@ check_non_staged_files(struct got_fileindex *fileindex struct got_pathlist_entry *pe; struct got_fileindex_entry *ie; - TAILQ_FOREACH(pe, paths, entry) { + RB_FOREACH(pe, got_pathlist_head, paths) { if (pe->path[0] == '\0') continue; ie = got_fileindex_entry_get(fileindex, pe->path, pe->path_len); @@ -6660,7 +6660,7 @@ got_worktree_commit(struct got_object_id **new_commit_ *new_commit_id = NULL; memset(&cc_arg, 0, sizeof(cc_arg)); - TAILQ_INIT(&commitable_paths); + RB_INIT(&commitable_paths); err = lock_worktree(worktree, LOCK_EX); if (err) @@ -6714,7 +6714,7 @@ got_worktree_commit(struct got_object_id **new_commit_ } } - TAILQ_FOREACH(pe, paths, entry) { + RB_FOREACH(pe, got_pathlist_head, paths) { err = worktree_status(worktree, pe->path, fileindex, repo, collect_commitables, &cc_arg, NULL, NULL, 0, 0); if (err) @@ -6728,18 +6728,18 @@ got_worktree_commit(struct got_object_id **new_commit_ } } - if (TAILQ_EMPTY(&commitable_paths)) { + if (RB_EMPTY(&commitable_paths)) { err = got_error(GOT_ERR_COMMIT_NO_CHANGES); goto done; } - TAILQ_FOREACH(pe, paths, entry) { + RB_FOREACH(pe, got_pathlist_head, paths) { err = check_path_is_commitable(pe->path, &commitable_paths); if (err) goto done; } - TAILQ_FOREACH(pe, &commitable_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &commitable_paths) { struct got_commitable *ct = pe->data; const char *ct_path = ct->in_repo_path; @@ -6772,7 +6772,7 @@ done: unlockerr = lock_worktree(worktree, LOCK_SH); if (unlockerr && err == NULL) err = unlockerr; - TAILQ_FOREACH(pe, &commitable_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &commitable_paths) { struct got_commitable *ct = pe->data; free_commitable(ct); @@ -7329,7 +7329,7 @@ rebase_commit(struct got_object_id **new_commit_id, char *logmsg = NULL; memset(&cc_arg, 0, sizeof(cc_arg)); - TAILQ_INIT(&commitable_paths); + RB_INIT(&commitable_paths); *new_commit_id = NULL; /* Work tree is locked/unlocked during rebase preparation/teardown. */ @@ -7356,7 +7356,7 @@ rebase_commit(struct got_object_id **new_commit_id, */ if (merged_paths) { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, merged_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, merged_paths) { err = worktree_status(worktree, pe->path, fileindex, repo, collect_commitables, &cc_arg, NULL, NULL, 1, 0); @@ -7370,7 +7370,7 @@ rebase_commit(struct got_object_id **new_commit_id, goto done; } - if (TAILQ_EMPTY(&commitable_paths)) { + if (RB_EMPTY(&commitable_paths)) { /* No-op change; commit will be elided. */ err = got_ref_delete(commit_ref, repo); if (err) @@ -7727,13 +7727,13 @@ get_paths_added_between_commits(struct got_pathlist_he struct got_pathlist_entry *pe; char *abspath = NULL, *wt_path = NULL; - TAILQ_INIT(&merged_paths); + RB_INIT(&merged_paths); err = get_paths_changed_between_commits(&merged_paths, id1, id2, repo); if (err) goto done; - TAILQ_FOREACH(pe, &merged_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &merged_paths) { struct got_diff_changed_path *change = pe->data; if (change->status != GOT_STATUS_ADD) @@ -7815,7 +7815,7 @@ got_worktree_rebase_abort(struct got_worktree *worktre struct got_object_id *tree_id = NULL; struct got_pathlist_head added_paths; - TAILQ_INIT(&added_paths); + RB_INIT(&added_paths); err = lock_worktree(worktree, LOCK_EX); if (err) @@ -8269,7 +8269,7 @@ got_worktree_histedit_abort(struct got_worktree *workt struct revert_file_args rfa; struct got_pathlist_head added_paths; - TAILQ_INIT(&added_paths); + RB_INIT(&added_paths); err = lock_worktree(worktree, LOCK_EX); if (err) @@ -8733,7 +8733,7 @@ got_worktree_merge_commit(struct got_object_id **new_c memset(&cc_arg, 0, sizeof(cc_arg)); *new_commit_id = NULL; - TAILQ_INIT(&commitable_paths); + RB_INIT(&commitable_paths); err = get_fileindex_path(&fileindex_path, worktree); if (err) @@ -8782,7 +8782,7 @@ got_worktree_merge_commit(struct got_object_id **new_c if (sync_err && err == NULL) err = sync_err; done: - TAILQ_FOREACH(pe, &commitable_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &commitable_paths) { struct got_commitable *ct = pe->data; free_commitable(ct); @@ -9093,7 +9093,7 @@ got_worktree_merge_abort(struct got_worktree *worktree struct got_object_id *tree_id = NULL; struct got_pathlist_head added_paths; - TAILQ_INIT(&added_paths); + RB_INIT(&added_paths); err = get_merge_commit_ref_name(&commit_ref_name, worktree); if (err) @@ -9453,7 +9453,7 @@ got_worktree_stage(struct got_worktree *worktree, oka.fileindex = fileindex; oka.repo = repo; oka.have_changes = 0; - TAILQ_FOREACH(pe, paths, entry) { + RB_FOREACH(pe, got_pathlist_head, paths) { err = worktree_status(worktree, pe->path, fileindex, repo, check_stage_ok, &oka, NULL, NULL, 1, 0); if (err) @@ -9473,7 +9473,7 @@ got_worktree_stage(struct got_worktree *worktree, spa.status_arg = status_arg; spa.staged_something = 0; spa.allow_bad_symlinks = allow_bad_symlinks; - TAILQ_FOREACH(pe, paths, entry) { + RB_FOREACH(pe, got_pathlist_head, paths) { err = worktree_status(worktree, pe->path, fileindex, repo, stage_path, &spa, NULL, NULL, 1, 0); if (err) @@ -10020,7 +10020,7 @@ got_worktree_unstage(struct got_worktree *worktree, upa.progress_arg = progress_arg; upa.patch_cb = patch_cb; upa.patch_arg = patch_arg; - TAILQ_FOREACH(pe, paths, entry) { + RB_FOREACH(pe, got_pathlist_head, paths) { err = worktree_status(worktree, pe->path, fileindex, repo, unstage_path, &upa, NULL, NULL, 1, 0); if (err) @@ -10066,7 +10066,7 @@ report_file_info(void *arg, struct got_fileindex_entry return err; } - TAILQ_FOREACH(pe, a->paths, entry) { + RB_FOREACH(pe, got_pathlist_head, a->paths) { if (pe->path_len == 0 || strcmp(pe->path, ie->path) == 0 || got_path_is_child(ie->path, pe->path, pe->path_len)) break; blob - b9abd5bf360259fba46644942a97cd1cc76f4b9f blob + 4518253bb1454bef6d43a7a09d1bdc0b73168086 --- lib/worktree_cvg.c +++ lib/worktree_cvg.c @@ -754,7 +754,7 @@ free_ignores(struct got_pathlist_head *ignores) { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, ignores, entry) { + RB_FOREACH(pe, got_pathlist_head, ignores) { struct got_pathlist_head *ignorelist = pe->data; got_pathlist_free(ignorelist, GOT_PATHLIST_FREE_PATH); @@ -775,7 +775,7 @@ read_ignores(struct got_pathlist_head *ignores, const ignorelist = calloc(1, sizeof(*ignorelist)); if (ignorelist == NULL) return got_error_from_errno("calloc"); - TAILQ_INIT(ignorelist); + RB_INIT(ignorelist); while ((linelen = getline(&line, &linesize, f)) != -1) { if (linelen > 0 && line[linelen - 1] == '\n') @@ -844,11 +844,11 @@ match_ignores(struct got_pathlist_head *ignores, const struct got_pathlist_entry *pe; /* Handle patterns which match in all directories. */ - TAILQ_FOREACH(pe, ignores, entry) { + RB_FOREACH(pe, got_pathlist_head, ignores) { struct got_pathlist_head *ignorelist = pe->data; struct got_pathlist_entry *pi; - TAILQ_FOREACH(pi, ignorelist, entry) { + RB_FOREACH(pi, got_pathlist_head, ignorelist) { const char *p; if (pi->path_len < 3 || @@ -876,12 +876,12 @@ match_ignores(struct got_pathlist_head *ignores, const * parents, so we can find the most specific ignorelist by walking * ignores backwards. */ - pe = TAILQ_LAST(ignores, got_pathlist_head); + pe = RB_MAX(got_pathlist_head, ignores); while (pe) { if (got_path_is_child(path, pe->path, pe->path_len)) { struct got_pathlist_head *ignorelist = pe->data; struct got_pathlist_entry *pi; - TAILQ_FOREACH(pi, ignorelist, entry) { + RB_FOREACH(pi, got_pathlist_head, ignorelist) { int flags = FNM_LEADING_DIR; if (strstr(pi->path, "/**/") == NULL) flags |= FNM_PATHNAME; @@ -891,7 +891,7 @@ match_ignores(struct got_pathlist_head *ignores, const return 1; } } - pe = TAILQ_PREV(pe, got_pathlist_head, entry); + pe = RB_PREV(got_pathlist_head, ignores, pe); } return 0; @@ -1121,7 +1121,7 @@ report_children(struct got_pathlist_head *children, struct got_pathlist_entry *pe; char *ondisk_path = NULL; - TAILQ_FOREACH(pe, children, entry) { + RB_FOREACH(pe, got_pathlist_head, children) { if (cancel_cb) { err = cancel_cb(cancel_arg); if (err) @@ -1164,8 +1164,8 @@ worktree_status(struct got_worktree *worktree, const c struct got_pathlist_head ignores, missing_children; struct got_fileindex_entry *ie; - TAILQ_INIT(&ignores); - TAILQ_INIT(&missing_children); + RB_INIT(&ignores); + RB_INIT(&missing_children); if (asprintf(&ondisk_path, "%s%s%s", worktree->root_path, path[0] ? "/" : "", path) == -1) @@ -1202,7 +1202,7 @@ worktree_status(struct got_worktree *worktree, const c if (err) goto done; } - if (TAILQ_EMPTY(&missing_children)) { + if (RB_EMPTY(&missing_children)) { err = report_single_file_status(path, ondisk_path, fileindex, status_cb, status_arg, repo, @@ -1838,7 +1838,7 @@ match_modified_subtree(int *modified, struct got_tree_ te->name) == -1) return got_error_from_errno("asprintf"); - TAILQ_FOREACH(pe, commitable_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, commitable_paths) { struct got_commitable *ct = pe->data; *modified = got_path_is_child(ct->in_repo_path, te_path, strlen(te_path)); @@ -1860,7 +1860,7 @@ match_deleted_or_modified_ct(struct got_commitable **c *ctp = NULL; - TAILQ_FOREACH(pe, commitable_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, commitable_paths) { struct got_commitable *ct = pe->data; char *ct_name = NULL; int path_matches; @@ -1960,11 +1960,11 @@ write_tree(struct got_object_id **new_tree_id, int *ne struct got_tree_entry *te, *new_te = NULL; struct got_pathlist_entry *pe; - TAILQ_INIT(&paths); + RB_INIT(&paths); *nentries = 0; /* Insert, and recurse into, newly added entries first. */ - TAILQ_FOREACH(pe, commitable_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, commitable_paths) { struct got_commitable *ct = pe->data; char *child_path = NULL, *slash; @@ -2122,7 +2122,7 @@ update_fileindex_after_commit(struct got_worktree *wor struct got_pathlist_entry *pe; char *relpath = NULL; - TAILQ_FOREACH(pe, commitable_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, commitable_paths) { struct got_fileindex_entry *ie; struct got_commitable *ct = pe->data; @@ -2270,7 +2270,7 @@ commit_worktree(struct got_object_id **new_commit_id, } /* Create blobs from added and modified files and record their IDs. */ - TAILQ_FOREACH(pe, commitable_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, commitable_paths) { struct got_commitable *ct = pe->data; char *ondisk_path; @@ -2337,7 +2337,7 @@ check_path_is_commitable(const char *path, struct got_pathlist_entry *cpe = NULL; size_t path_len = strlen(path); - TAILQ_FOREACH(cpe, commitable_paths, entry) { + RB_FOREACH(cpe, got_pathlist_head, commitable_paths) { struct got_commitable *ct = cpe->data; const char *ct_path = ct->path; @@ -2375,7 +2375,7 @@ check_non_staged_files(struct got_fileindex *fileindex struct got_pathlist_entry *pe; struct got_fileindex_entry *ie; - TAILQ_FOREACH(pe, paths, entry) { + RB_FOREACH(pe, got_pathlist_head, paths) { if (pe->path[0] == '\0') continue; ie = got_fileindex_entry_get(fileindex, pe->path, pe->path_len); @@ -2447,7 +2447,7 @@ send_progress(void *arg, int ncolored, int nfound, int if (success) { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, a->delete_branches, entry) { + RB_FOREACH(pe, got_pathlist_head, a->delete_branches) { const char *branchname = pe->path; if (got_path_cmp(branchname, refname, strlen(branchname), strlen(refname)) == 0) { @@ -2779,10 +2779,10 @@ fetch_updated_remote(const char *proto, const char *ho int fetchfd = -1; pid_t fetchpid = -1; - TAILQ_INIT(&learned_refs); - TAILQ_INIT(&symrefs); - TAILQ_INIT(&wanted_branches); - TAILQ_INIT(&wanted_refs); + RB_INIT(&learned_refs); + RB_INIT(&symrefs); + RB_INIT(&wanted_branches); + RB_INIT(&wanted_refs); err = got_pathlist_insert(NULL, &wanted_branches, head_refname, NULL); @@ -2807,7 +2807,7 @@ fetch_updated_remote(const char *proto, const char *ho goto done; /* Update references provided with the pack file. */ - TAILQ_FOREACH(pe, &learned_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, &learned_refs) { const char *refname = pe->path; struct got_object_id *id = pe->data; struct got_reference *ref; @@ -2831,7 +2831,7 @@ fetch_updated_remote(const char *proto, const char *ho } /* Set the HEAD reference if the server provided one. */ - TAILQ_FOREACH(pe, &symrefs, entry) { + RB_FOREACH(pe, got_pathlist_head, &symrefs) { struct got_reference *target_ref; const char *refname = pe->path; const char *target = pe->data; @@ -2938,10 +2938,10 @@ got_worktree_cvg_commit(struct got_object_id **new_com *new_commit_id = NULL; memset(&cc_arg, 0, sizeof(cc_arg)); - TAILQ_INIT(&commitable_paths); - TAILQ_INIT(&commit_reflist); - TAILQ_INIT(&tag_names); - TAILQ_INIT(&delete_branches); + RB_INIT(&commitable_paths); + RB_INIT(&commit_reflist); + RB_INIT(&tag_names); + RB_INIT(&delete_branches); err = lock_worktree(worktree, LOCK_EX); if (err) @@ -3007,7 +3007,7 @@ got_worktree_cvg_commit(struct got_object_id **new_com } } - TAILQ_FOREACH(pe, paths, entry) { + RB_FOREACH(pe, got_pathlist_head, paths) { err = worktree_status(worktree, pe->path, fileindex, repo, collect_commitables, &cc_arg, NULL, NULL, 0, 0); if (err) @@ -3021,18 +3021,18 @@ got_worktree_cvg_commit(struct got_object_id **new_com } } - if (TAILQ_EMPTY(&commitable_paths)) { + if (RB_EMPTY(&commitable_paths)) { err = got_error(GOT_ERR_COMMIT_NO_CHANGES); goto done; } - TAILQ_FOREACH(pe, paths, entry) { + RB_FOREACH(pe, got_pathlist_head, paths) { err = check_path_is_commitable(pe->path, &commitable_paths); if (err) goto done; } - TAILQ_FOREACH(pe, &commitable_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &commitable_paths) { struct got_commitable *ct = pe->data; const char *ct_path = ct->in_repo_path; @@ -3157,7 +3157,7 @@ done: unlockerr = lock_worktree(worktree, LOCK_SH); if (unlockerr && err == NULL) err = unlockerr; - TAILQ_FOREACH(pe, &commitable_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &commitable_paths) { struct got_commitable *ct = pe->data; free_commitable(ct); blob - 1855ba0c1a557ce16cfae9790d6cff44a4b71846 blob + 6ae0f96f5546d6f7eaac0b1b2d32dd6249c51d52 --- lib/worktree_open.c +++ lib/worktree_open.c @@ -16,6 +16,7 @@ #include <sys/stat.h> #include <sys/queue.h> +#include <sys/tree.h> #include <errno.h> #include <fcntl.h> blob - 235f88168eaa1209540cb280c17e4f55629259a4 blob + 6f0e0e861b6c26170d813b19ca2271295f30eb22 --- libexec/got-fetch-http/got-fetch-http.c +++ libexec/got-fetch-http/got-fetch-http.c @@ -17,6 +17,7 @@ #include <sys/types.h> #include <sys/queue.h> +#include <sys/tree.h> #include <sys/socket.h> #include <err.h> blob - 167dff0291b3356987b3f2dbe74509ad4a608813 blob + 941d899ffe34503cf9f82ba20f3e587581c384df --- libexec/got-fetch-pack/got-fetch-pack.c +++ libexec/got-fetch-pack/got-fetch-pack.c @@ -16,6 +16,7 @@ #include <sys/types.h> #include <sys/queue.h> +#include <sys/tree.h> #include <sys/uio.h> #include <sys/time.h> #include <sys/stat.h> @@ -82,7 +83,7 @@ match_remote_ref(struct got_pathlist_head *have_refs, * we should use a flag instead */ memset(my_id, 0, sizeof(*my_id)); - TAILQ_FOREACH(pe, have_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, have_refs) { struct got_object_id *id = pe->data; if (strcmp(pe->path, refname) == 0) { memcpy(my_id, id, sizeof(*my_id)); @@ -228,7 +229,7 @@ send_fetch_symrefs(struct imsgbuf *ibuf, struct got_pa struct got_pathlist_entry *pe; len = sizeof(struct got_imsg_fetch_symrefs); - TAILQ_FOREACH(pe, symrefs, entry) { + RB_FOREACH(pe, got_pathlist_head, symrefs) { const char *target = pe->data; len += sizeof(struct got_imsg_fetch_symref) + pe->path_len + strlen(target); @@ -246,7 +247,7 @@ send_fetch_symrefs(struct imsgbuf *ibuf, struct got_pa if (imsg_add(wbuf, &nsymrefs, sizeof(nsymrefs)) == -1) return got_error_from_errno("imsg_add FETCH_SYMREFS"); - TAILQ_FOREACH(pe, symrefs, entry) { + RB_FOREACH(pe, got_pathlist_head, symrefs) { const char *name = pe->path; size_t name_len = pe->path_len; const char *target = pe->data; @@ -357,7 +358,7 @@ fetch_pack(int fd, int packfd, uint8_t *pack_sha1, ssize_t w; struct got_ratelimit rl; - TAILQ_INIT(&symrefs); + RB_INIT(&symrefs); got_hash_init(&ctx, GOT_HASH_SHA1); got_ratelimit_init(&rl, 0, 500); @@ -423,7 +424,7 @@ fetch_pack(int fd, int packfd, uint8_t *pack_sha1, goto done; is_firstpkt = 0; if (!fetch_all_branches) { - TAILQ_FOREACH(pe, &symrefs, entry) { + RB_FOREACH(pe, got_pathlist_head, &symrefs) { const char *name = pe->path; const char *symref_target = pe->data; if (strcmp(name, GOT_REF_HEAD) != 0) @@ -467,7 +468,7 @@ fetch_pack(int fd, int packfd, uint8_t *pack_sha1, found_branch = 1; continue; } - TAILQ_FOREACH(pe, wanted_branches, entry) { + RB_FOREACH(pe, got_pathlist_head, wanted_branches) { if (match_branch(refname, pe->path)) break; } @@ -484,7 +485,7 @@ fetch_pack(int fd, int packfd, uint8_t *pack_sha1, getprogname(), refname); } } else { - TAILQ_FOREACH(pe, wanted_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, wanted_refs) { if (match_wanted_ref(refname, pe->path)) break; } @@ -532,7 +533,7 @@ fetch_pack(int fd, int packfd, uint8_t *pack_sha1, struct got_pathlist_entry *pe; static char msg[PATH_MAX + 33]; - pe = TAILQ_FIRST(wanted_branches); + pe = RB_MIN(got_pathlist_head, wanted_branches); if (pe) { snprintf(msg, sizeof(msg), "branch \"%s\" not found on server", pe->path); @@ -540,7 +541,7 @@ fetch_pack(int fd, int packfd, uint8_t *pack_sha1, goto done; } - pe = TAILQ_FIRST(wanted_refs); + pe = RB_MIN(got_pathlist_head, wanted_refs); if (pe) { snprintf(msg, sizeof(msg), "reference \"%s\" not found on server", pe->path); @@ -576,7 +577,7 @@ fetch_pack(int fd, int packfd, uint8_t *pack_sha1, if (nwant == 0) goto done; - TAILQ_FOREACH(pe, have_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, have_refs) { struct got_object_id *id = pe->data; got_object_id_hex(id, hashstr, sizeof(hashstr)); n = snprintf(buf, sizeof(buf), "have %s\n", hashstr); @@ -873,9 +874,9 @@ main(int argc, char **argv) sleep (1); #endif - TAILQ_INIT(&have_refs); - TAILQ_INIT(&wanted_branches); - TAILQ_INIT(&wanted_refs); + RB_INIT(&have_refs); + RB_INIT(&wanted_branches); + RB_INIT(&wanted_refs); if (imsgbuf_init(&ibuf, GOT_IMSG_FD_CHILD) == -1) { warn("imsgbuf_init"); blob - e7b041c41a36e5ab990a86d621f4e250a2599450 blob + 30b538316b641b0ebb47883992192f2d69452e31 --- libexec/got-index-pack/got-index-pack.c +++ libexec/got-index-pack/got-index-pack.c @@ -17,6 +17,7 @@ #include <sys/types.h> #include <sys/queue.h> +#include <sys/tree.h> #include <sys/mman.h> #include <sys/uio.h> blob - d822239702f0cb31d5d90a0204548fe0fa3b2568 blob + 6c4d37a796af1d8465d17690350100aa7f5a13ca --- libexec/got-read-gotconfig/got-read-gotconfig.c +++ libexec/got-read-gotconfig/got-read-gotconfig.c @@ -16,6 +16,7 @@ #include <sys/types.h> #include <sys/queue.h> +#include <sys/tree.h> #include <sys/uio.h> #include <sys/time.h> blob - 3193a744382b165f03043d74461855f87708c68a blob + 8b6314b53f27f1bb8782f89d99e0ce70f29e4d60 --- libexec/got-read-pack/got-read-pack.c +++ libexec/got-read-pack/got-read-pack.c @@ -17,6 +17,7 @@ #include <sys/stat.h> #include <sys/types.h> #include <sys/queue.h> +#include <sys/tree.h> #include <sys/uio.h> #include <sys/time.h> #include <sys/mman.h> blob - ebf6949188e7f189d1ca4bf3eb6652f668d4f96c blob + 417db9c87500ce3e9b5dcc9a6784d94fa465f657 --- libexec/got-read-tree/got-read-tree.c +++ libexec/got-read-tree/got-read-tree.c @@ -16,6 +16,7 @@ #include <sys/types.h> #include <sys/queue.h> +#include <sys/tree.h> #include <sys/uio.h> #include <sys/time.h> blob - a7c50b87c17ac2535d33e80601a9f5b054441d8f blob + 1f5f72593dca228e5752bbe2703e47723bda37c2 --- libexec/got-send-pack/got-send-pack.c +++ libexec/got-send-pack/got-send-pack.c @@ -17,6 +17,7 @@ #include <sys/types.h> #include <sys/queue.h> +#include <sys/tree.h> #include <sys/uio.h> #include <sys/time.h> #include <sys/stat.h> @@ -259,14 +260,14 @@ send_ref_status(struct imsgbuf *ibuf, const char *refn "unexpected message from server"); } - TAILQ_FOREACH(pe, refs, entry) { + RB_FOREACH(pe, got_pathlist_head, refs) { if (strcmp(refname, pe->path) == 0) { ref_valid = 1; break; } } if (!ref_valid) { - TAILQ_FOREACH(pe, delete_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, delete_refs) { if (strcmp(refname, pe->path) == 0) { ref_valid = 1; break; @@ -358,9 +359,9 @@ send_pack(int fd, struct got_pathlist_head *refs, struct got_pathlist_entry *pe; int sent_my_capabilites = 0; - TAILQ_INIT(&their_refs); + RB_INIT(&their_refs); - if (TAILQ_EMPTY(refs) && TAILQ_EMPTY(delete_refs)) + if (RB_EMPTY(refs) && RB_EMPTY(delete_refs)) return got_error(GOT_ERR_SEND_EMPTY); while (1) { @@ -441,7 +442,7 @@ send_pack(int fd, struct got_pathlist_head *refs, id = NULL; /* do not free; owned by their_refs */ } - if (!TAILQ_EMPTY(delete_refs)) { + if (!RB_EMPTY(delete_refs)) { if (my_capabilities == NULL || strstr(my_capabilities, GOT_CAPA_DELETE_REFS) == NULL) { err = got_error(GOT_ERR_CAPA_DELETE_REFS); @@ -449,12 +450,12 @@ send_pack(int fd, struct got_pathlist_head *refs, } } - TAILQ_FOREACH(pe, delete_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, delete_refs) { const char *refname = pe->path; struct got_pathlist_entry *their_pe; struct got_object_id *their_id = NULL; - TAILQ_FOREACH(their_pe, &their_refs, entry) { + RB_FOREACH(their_pe, got_pathlist_head, &their_refs) { const char *their_refname = their_pe->path; if (got_path_cmp(refname, their_refname, strlen(refname), strlen(their_refname)) == 0) { @@ -488,13 +489,13 @@ send_pack(int fd, struct got_pathlist_head *refs, nsent++; } - TAILQ_FOREACH(pe, refs, entry) { + RB_FOREACH(pe, got_pathlist_head, refs) { const char *refname = pe->path; struct got_object_id *id = pe->data; struct got_object_id *their_id = NULL; struct got_pathlist_entry *their_pe; - TAILQ_FOREACH(their_pe, &their_refs, entry) { + RB_FOREACH(their_pe, got_pathlist_head, &their_refs) { const char *their_refname = their_pe->path; if (got_path_cmp(refname, their_refname, strlen(refname), strlen(their_refname)) == 0) { @@ -626,8 +627,8 @@ main(int argc, char **argv) sleep (1); #endif - TAILQ_INIT(&refs); - TAILQ_INIT(&delete_refs); + RB_INIT(&refs); + RB_INIT(&delete_refs); if (imsgbuf_init(&ibuf, GOT_IMSG_FD_CHILD) == -1) { warn("imsgbuf_init"); blob - 377ea9cd19e22c07f1348e7110a49defd8cb974d blob + b0b1593dc092b51883cce8fc1caf672b00d56560 --- regress/delta/delta_test.c +++ regress/delta/delta_test.c @@ -15,6 +15,7 @@ */ #include <sys/queue.h> +#include <sys/tree.h> #include <stdio.h> #include <stdlib.h> blob - c024c69ae8a0fd18330ae5c8f6dc6b872026966e blob + e3b7eda734c43ae229647e428258d944538ab041 --- regress/fetch/fetch_test.c +++ regress/fetch/fetch_test.c @@ -15,6 +15,7 @@ */ #include <sys/queue.h> +#include <sys/tree.h> #include <limits.h> #include <stdarg.h> blob - fad15574f54715f8f62105579fbc58c1ca5d1bf1 blob + c4da368ef9fe5fb3b4c6ff3a0879637e0a4a2611 --- regress/path/path_test.c +++ regress/path/path_test.c @@ -15,6 +15,7 @@ */ #include <sys/queue.h> +#include <sys/tree.h> #include <string.h> #include <stdlib.h> @@ -141,7 +142,7 @@ path_list(void) struct got_pathlist_entry *pe; size_t i; - TAILQ_INIT(&paths); + RB_INIT(&paths); for (i = 0; i < nitems(path_list_input); i++) { err = got_pathlist_insert(NULL, &paths, path_list_input[i], NULL); @@ -152,7 +153,7 @@ path_list(void) } i = 0; - TAILQ_FOREACH(pe, &paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &paths) { test_printf("'%s' -- '%s'\n", pe->path, path_list_expected[i]); if (i >= nitems(path_list_expected)) { test_printf("too many elements on list\n"); @@ -177,7 +178,7 @@ path_list_reverse_input(void) struct got_pathlist_entry *pe; size_t i; - TAILQ_INIT(&paths); + RB_INIT(&paths); for (i = nitems(path_list_input); i > 0;) { err = got_pathlist_insert(NULL, &paths, path_list_input[--i], NULL); @@ -188,7 +189,7 @@ path_list_reverse_input(void) } i = 0; - TAILQ_FOREACH(pe, &paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &paths) { test_printf("'%s' -- '%s'\n", pe->path, path_list_expected_reverse[i]); if (i >= nitems(path_list_expected_reverse)) { blob - a09591e35e09e13fb23f7c13166a95b75ab02ffc blob + e5b6a27289781714067597b57322e12510368ce6 --- tog/tog.c +++ tog/tog.c @@ -15,6 +15,7 @@ */ #include <sys/queue.h> +#include <sys/tree.h> #include <sys/stat.h> #include <sys/ioctl.h> @@ -3175,7 +3176,7 @@ tog_worktree_status(struct tog_log_thread_args *ta) char *cwd = NULL; int wt_state = 0; - TAILQ_INIT(&paths); + RB_INIT(&paths); if (wt == NULL) { cwd = getcwd(NULL, 0); @@ -5822,7 +5823,7 @@ write_diffstat(FILE *outfile, struct got_diff_line **l } else offset = (*lines)[*nlines - 1].offset; - TAILQ_FOREACH(pe, dsa->paths, entry) { + RB_FOREACH(pe, got_pathlist_head, dsa->paths) { struct got_diff_changed_path *cp = pe->data; int pad = dsa->max_path_len - pe->path_len + 1; @@ -6330,7 +6331,7 @@ tog_diff_worktree(struct tog_diff_view_state *s, FILE struct got_pathlist_head pathlist; char *cwd, *id_str = NULL; - TAILQ_INIT(&pathlist); + RB_INIT(&pathlist); cwd = getcwd(NULL, 0); if (cwd == NULL) @@ -6518,7 +6519,7 @@ create_diff(struct tog_diff_view_state *s) struct got_diffstat_cb_arg dsa; size_t nlines = 0; - TAILQ_INIT(&changed_paths); + RB_INIT(&changed_paths); memset(&dsa, 0, sizeof(dsa)); dsa.paths = &changed_paths; dsa.diff_algo = tog_diff_algo; @@ -7401,7 +7402,7 @@ cmd_diff(int argc, char *argv[]) struct tog_view *view; int *pack_fds = NULL; - TAILQ_INIT(&paths); + RB_INIT(&paths); while ((ch = getopt(argc, argv, "aC:c:r:sw")) != -1) { switch (ch) { On Wednesday, December 18th, 2024 at 8:10 PM, Stefan Sperling <stsp@stsp.name> wrote: > > > On Tue, Dec 17, 2024 at 11:16:29PM +0000, Kyle Ackerman wrote: > > > Here is a patch to change the underlying data structure of > > got_pathlist from a TAILQ to a RB_tree, this enforces sorted order and > > provides faster lookup times. > > > > To improve review-ability, I have segmented the various parts into > > different commits. > > > After applying the combined diff attached to your message, it does > not build. One trivial error is in lib/send.c. Fix below. > > Pathlist conversion for gotd and gotwebd are missing from your diff > so these programs cannot be built with your diff applied. Given this, > we cannot commit this patch as it is. > > Apart from some whitespace and indentation issues (patch attached) I > did not spot any other issues. > > > /home/stsp/src/got/got/../lib/send.c:271:12: error: incompatible integer to pointer conversion assigning to 'const char *' from 'const char'; remove * [-Werror,-Wint-conversion] > find.path = *refname; > ^ ~~~~~~~~ > > M lib/send.c | 1+ 1- > > 1 file changed, 1 insertion(+), 1 deletion(-) > > commit - a9785d2b3cb1adb748f776e4be8ae56a9f32b17e > commit + b92a313ce8f7279c703da2bbcdcab5d0c1cf33f3 > blob - a3005ec8d8181a70ceed4025c3d8258a0e7909a7 > blob + bf4b1849698cbf61dd2fd31a6e637a15042c0c87 > --- lib/send.c > +++ lib/send.c > @@ -268,7 +268,7 @@ find_ref(struct got_pathlist_head *refs, const char *r > { > struct got_pathlist_entry find, *res; > > - find.path = *refname; > + find.path = refname; > find.path_len = strlen(refname); > res = RB_FIND(got_pathlist_head, refs, &find); > return res; diff refs/heads/main refs/heads/got_pathtree commit - 88ba8f77592194a8eb9a70f68b25bc09d0355e97 commit + ee1b798e42fe64cd3c975d8acb5567a02da58985 blob - 9f093ace3cfdb472bce06ad93efc12cb9138a9e4 blob + f24778d4013fcf34695978d66c42b3619ebdf7bd --- cvg/cvg.c +++ cvg/cvg.c @@ -18,6 +18,7 @@ */ #include <sys/queue.h> +#include <sys/tree.h> #include <sys/time.h> #include <sys/types.h> #include <sys/stat.h> @@ -740,7 +741,7 @@ cmd_import(int argc, char *argv[]) int preserve_logmsg = 0; int *pack_fds = NULL; - TAILQ_INIT(&ignores); + RB_INIT(&ignores); #ifndef PROFILE if (pledge("stdio rpath wpath cpath fattr flock proc exec sendfd " @@ -1027,7 +1028,7 @@ fetch_progress(void *arg, const char *message, off_t p * we have all required information. */ if (a->create_configs && !a->configs_created && - !TAILQ_EMPTY(a->config_info.symrefs)) { + !RB_EMPTY(a->config_info.symrefs)) { err = create_config_files(a->config_info.proto, a->config_info.host, a->config_info.port, a->config_info.remote_repo_path, @@ -1121,14 +1122,14 @@ list_remote_refs(struct got_pathlist_head *symrefs, const struct got_error *err; struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, symrefs, entry) { + RB_FOREACH(pe, got_pathlist_head, symrefs) { const char *refname = pe->path; const char *targetref = pe->data; printf("%s: %s\n", refname, targetref); } - TAILQ_FOREACH(pe, refs, entry) { + RB_FOREACH(pe, got_pathlist_head, refs) { const char *refname = pe->path; struct got_object_id *id = pe->data; char *id_str; @@ -1201,7 +1202,7 @@ is_wanted_ref(struct got_pathlist_head *wanted_refs, c { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, wanted_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, wanted_refs) { if (match_wanted_ref(refname, pe->path)) return 1; } @@ -1243,9 +1244,9 @@ create_gotconfig(const char *proto, const char *host, char *branches = NULL, *refs = NULL; ssize_t n; - if (!fetch_all_branches && !TAILQ_EMPTY(wanted_branches)) { + if (!fetch_all_branches && !RB_EMPTY(wanted_branches)) { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, wanted_branches, entry) { + RB_FOREACH(pe, got_pathlist_head, wanted_branches) { char *s; branchname = pe->path; if (strncmp(branchname, "refs/heads/", 11) == 0) @@ -1267,9 +1268,9 @@ create_gotconfig(const char *proto, const char *host, goto done; } } - if (!TAILQ_EMPTY(wanted_refs)) { + if (!RB_EMPTY(wanted_refs)) { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, wanted_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, wanted_refs) { char *s; const char *refname = pe->path; if (strncmp(refname, "refs/", 5) == 0) @@ -1368,9 +1369,9 @@ create_gitconfig(const char *git_url, const char *defa err = got_error_from_errno("asprintf"); goto done; } - } else if (!TAILQ_EMPTY(wanted_branches)) { + } else if (!RB_EMPTY(wanted_branches)) { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, wanted_branches, entry) { + RB_FOREACH(pe, got_pathlist_head, wanted_branches) { char *s; branchname = pe->path; if (strncmp(branchname, "refs/heads/", 11) == 0) @@ -1420,9 +1421,9 @@ create_gitconfig(const char *git_url, const char *defa goto done; } } - if (!TAILQ_EMPTY(wanted_refs)) { + if (!RB_EMPTY(wanted_refs)) { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, wanted_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, wanted_refs) { char *s; const char *refname = pe->path; if (strncmp(refname, "refs/", 5) == 0) @@ -1486,12 +1487,12 @@ create_config_files(const char *proto, const char *hos * If we asked for a set of wanted branches then use the first * one of those. */ - if (!TAILQ_EMPTY(wanted_branches)) { - pe = TAILQ_FIRST(wanted_branches); + if (!RB_EMPTY(wanted_branches)) { + pe = RB_MIN(got_pathlist_head, wanted_branches); default_branch = pe->path; } else { /* First HEAD ref listed by server is the default branch. */ - TAILQ_FOREACH(pe, symrefs, entry) { + RB_FOREACH(pe, got_pathlist_head, symrefs) { const char *refname = pe->path; const char *target = pe->data; @@ -1536,10 +1537,10 @@ cmd_clone(int argc, char *argv[]) int *pack_fds = NULL; const char *jumphost = NULL; - TAILQ_INIT(&refs); - TAILQ_INIT(&symrefs); - TAILQ_INIT(&wanted_branches); - TAILQ_INIT(&wanted_refs); + RB_INIT(&refs); + RB_INIT(&symrefs); + RB_INIT(&wanted_branches); + RB_INIT(&wanted_refs); while ((ch = getopt(argc, argv, "ab:J:lmqR:v")) != -1) { switch (ch) { @@ -1585,16 +1586,16 @@ cmd_clone(int argc, char *argv[]) argc -= optind; argv += optind; - if (fetch_all_branches && !TAILQ_EMPTY(&wanted_branches)) + if (fetch_all_branches && !RB_EMPTY(&wanted_branches)) option_conflict('a', 'b'); if (list_refs_only) { - if (!TAILQ_EMPTY(&wanted_branches)) + if (!RB_EMPTY(&wanted_branches)) option_conflict('l', 'b'); if (fetch_all_branches) option_conflict('l', 'a'); if (mirror_references) option_conflict('l', 'm'); - if (!TAILQ_EMPTY(&wanted_refs)) + if (!RB_EMPTY(&wanted_refs)) option_conflict('l', 'R'); } @@ -1733,7 +1734,7 @@ cmd_clone(int argc, char *argv[]) free(id_str); /* Set up references provided with the pack file. */ - TAILQ_FOREACH(pe, &refs, entry) { + RB_FOREACH(pe, got_pathlist_head, &refs) { const char *refname = pe->path; struct got_object_id *id = pe->data; char *remote_refname; @@ -1771,7 +1772,7 @@ cmd_clone(int argc, char *argv[]) } /* Set the HEAD reference if the server provided one. */ - TAILQ_FOREACH(pe, &symrefs, entry) { + RB_FOREACH(pe, got_pathlist_head, &symrefs) { struct got_reference *target_ref; const char *refname = pe->path; const char *target = pe->data; @@ -1837,7 +1838,7 @@ cmd_clone(int argc, char *argv[]) * a set of wanted branches use the first of one of those * which could be fetched instead. */ - TAILQ_FOREACH(pe, &wanted_branches, entry) { + RB_FOREACH(pe, got_pathlist_head, &wanted_branches) { const char *target = pe->path; struct got_reference *target_ref; @@ -2194,7 +2195,7 @@ cmd_checkout(int argc, char *argv[]) struct got_checkout_progress_arg cpa; int *pack_fds = NULL; - TAILQ_INIT(&paths); + RB_INIT(&paths); #ifndef PROFILE if (pledge("stdio rpath wpath cpath fattr flock proc exec sendfd " @@ -2668,12 +2669,12 @@ cmd_update(int argc, char *argv[]) struct got_reference *head_ref = NULL; const char *jumphost = NULL; - TAILQ_INIT(&paths); - TAILQ_INIT(&refs); - TAILQ_INIT(&symrefs); + RB_INIT(&paths); + RB_INIT(&refs); + RB_INIT(&symrefs); TAILQ_INIT(&remote_refs); - TAILQ_INIT(&wanted_branches); - TAILQ_INIT(&wanted_refs); + RB_INIT(&wanted_branches); + RB_INIT(&wanted_refs); while ((ch = getopt(argc, argv, "c:J:qr:vX")) != -1) { switch (ch) { @@ -2907,7 +2908,7 @@ cmd_update(int argc, char *argv[]) } /* Update references provided with the pack file. */ - TAILQ_FOREACH(pe, &refs, entry) { + RB_FOREACH(pe, got_pathlist_head, &refs) { const char *refname = pe->path; struct got_object_id *id = pe->data; struct got_reference *ref; @@ -3410,7 +3411,7 @@ match_changed_paths(int *have_match, struct got_pathli *have_match = 0; - TAILQ_FOREACH(pe, changed_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, changed_paths) { if (regexec(regex, pe->path, 1, &regmatch, 0) == 0) { *have_match = 1; break; @@ -3600,7 +3601,7 @@ print_diffstat(struct got_diffstat_cb_arg *dsa, const if (header != NULL) printf("%s\n", header); - TAILQ_FOREACH(pe, dsa->paths, entry) { + RB_FOREACH(pe, got_pathlist_head, dsa->paths) { struct got_diff_changed_path *cp = pe->data; int pad = dsa->max_path_len - pe->path_len + 1; @@ -3722,7 +3723,7 @@ print_commit(struct got_commit_object *commit, struct if (changed_paths && diffstat == NULL) { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, changed_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, changed_paths) { struct got_diff_changed_path *cp = pe->data; printf(" %c %s\n", cp->status, pe->path); @@ -3784,7 +3785,7 @@ print_commits(struct got_object_id *root_id, struct go struct got_pathlist_head changed_paths; STAILQ_INIT(&reversed_commits); - TAILQ_INIT(&changed_paths); + RB_INIT(&changed_paths); if (search_pattern && regcomp(&regex, search_pattern, REG_EXTENDED | REG_NOSUB | REG_NEWLINE)) @@ -4492,8 +4493,8 @@ cmd_diff(int argc, char *argv[]) memset(&dsa, 0, sizeof(dsa)); TAILQ_INIT(&refs); - TAILQ_INIT(&paths); - TAILQ_INIT(&diffstat_paths); + RB_INIT(&paths); + RB_INIT(&diffstat_paths); #ifndef PROFILE if (pledge("stdio rpath wpath cpath flock proc exec sendfd unveil", @@ -5691,7 +5692,7 @@ cmd_status(int argc, char *argv[]) int ch, i, no_ignores = 0; int *pack_fds = NULL; - TAILQ_INIT(&paths); + RB_INIT(&paths); memset(&st, 0, sizeof(st)); st.status_codes = NULL; @@ -6478,7 +6479,7 @@ cmd_add(int argc, char *argv[]) int ch, can_recurse = 0, no_ignores = 0; int *pack_fds = NULL; - TAILQ_INIT(&paths); + RB_INIT(&paths); #ifndef PROFILE if (pledge("stdio rpath wpath cpath flock proc exec sendfd unveil", @@ -6540,7 +6541,7 @@ cmd_add(int argc, char *argv[]) if (!can_recurse) { char *ondisk_path; struct stat sb; - TAILQ_FOREACH(pe, &paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &paths) { if (asprintf(&ondisk_path, "%s/%s", got_worktree_get_root_path(worktree), pe->path) == -1) { @@ -6623,7 +6624,7 @@ cmd_remove(int argc, char *argv[]) int ignore_missing_paths = 0; int *pack_fds = NULL; - TAILQ_INIT(&paths); + RB_INIT(&paths); #ifndef PROFILE if (pledge("stdio rpath wpath cpath flock proc exec sendfd unveil", @@ -6705,7 +6706,7 @@ cmd_remove(int argc, char *argv[]) if (!can_recurse) { char *ondisk_path; struct stat sb; - TAILQ_FOREACH(pe, &paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &paths) { if (asprintf(&ondisk_path, "%s/%s", got_worktree_get_root_path(worktree), pe->path) == -1) { @@ -7166,7 +7167,7 @@ worktree_has_commitable_path(void *arg, unsigned char if (a->commit_paths != NULL) { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, a->commit_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, a->commit_paths) { if (strncmp(path, pe->path, pe->path_len) == 0) { *a->has_changes = 1; @@ -7198,7 +7199,7 @@ commit_path_changed_in_worktree(struct wt_commitable_p struct got_tree_object *tree = NULL, *ptree = NULL; struct got_object_qid *pid; - TAILQ_INIT(&paths); + RB_INIT(&paths); err = got_object_open_as_commit(&commit, repo, id); if (err) @@ -7349,7 +7350,7 @@ cmd_revert(int argc, char *argv[]) struct choose_patch_arg cpa; int *pack_fds = NULL; - TAILQ_INIT(&paths); + RB_INIT(&paths); #ifndef PROFILE if (pledge("stdio rpath wpath cpath fattr flock proc exec sendfd " @@ -7428,7 +7429,7 @@ cmd_revert(int argc, char *argv[]) if (!can_recurse) { char *ondisk_path; struct stat sb; - TAILQ_FOREACH(pe, &paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &paths) { if (asprintf(&ondisk_path, "%s/%s", got_worktree_get_root_path(worktree), pe->path) == -1) { @@ -7608,7 +7609,7 @@ collect_commit_logmsg(struct got_pathlist_head *commit goto done; } - TAILQ_FOREACH(pe, commitable_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, commitable_paths) { struct got_commitable *ct = pe->data; dprintf(fd, "# %c %s\n", got_commitable_get_status(ct), @@ -7815,7 +7816,7 @@ cmd_commit(int argc, char *argv[]) int i; TAILQ_INIT(&refs); - TAILQ_INIT(&paths); + RB_INIT(&paths); cl_arg.logmsg_path = NULL; #ifndef PROFILE @@ -8108,7 +8109,7 @@ process_logmsg_refs(const char *ref_prefix, size_t pre int found = 0; TAILQ_INIT(&refs); - TAILQ_INIT(&paths); + RB_INIT(&paths); err = got_ref_list(&refs, repo, NULL, got_ref_cmp_by_name, repo); if (err) @@ -8975,7 +8976,7 @@ print_path_info(void *arg, const char *path, mode_t mo * Clear error indication from any of the path arguments which * would cause this file index entry to be displayed. */ - TAILQ_FOREACH(pe, paths, entry) { + RB_FOREACH(pe, got_pathlist_head, paths) { if (got_path_cmp(path, pe->path, strlen(path), pe->path_len) == 0 || got_path_is_child(path, pe->path, pe->path_len)) @@ -9040,7 +9041,7 @@ cmd_info(int argc, char *argv[]) int ch, show_files = 0; int *pack_fds = NULL; - TAILQ_INIT(&paths); + RB_INIT(&paths); #ifndef PROFILE if (pledge("stdio rpath wpath cpath flock proc exec sendfd unveil", @@ -9126,7 +9127,7 @@ cmd_info(int argc, char *argv[]) if (show_files) { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, &paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &paths) { if (pe->path_len == 0) continue; /* @@ -9139,7 +9140,7 @@ cmd_info(int argc, char *argv[]) print_path_info, &paths, check_cancelled, NULL); if (error) goto done; - TAILQ_FOREACH(pe, &paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &paths) { if (pe->data != NULL) { const struct got_error *perr; blob - 211ce127da138b7f0ae6451335215737fabc1c1a blob + 5db2fdbc49f5f220d6a5c3ca99d509315c111ce3 --- gitwrapper/gitwrapper.c +++ gitwrapper/gitwrapper.c @@ -19,6 +19,7 @@ */ #include <sys/queue.h> +#include <sys/tree.h> #include <sys/types.h> #include <sys/uio.h> blob - 36655f1f322184d063373730e92b7dbf08b373a4 blob + 48358ad1144d94badb8e3747f30345948a74c02b --- got/got.c +++ got/got.c @@ -17,6 +17,7 @@ */ #include <sys/queue.h> +#include <sys/tree.h> #include <sys/time.h> #include <sys/types.h> #include <sys/stat.h> @@ -841,7 +842,7 @@ cmd_import(int argc, char *argv[]) int preserve_logmsg = 0; int *pack_fds = NULL; - TAILQ_INIT(&ignores); + RB_INIT(&ignores); #ifndef PROFILE if (pledge("stdio rpath wpath cpath fattr flock proc exec sendfd " @@ -1129,7 +1130,7 @@ fetch_progress(void *arg, const char *message, off_t p * we have all required information. */ if (a->create_configs && !a->configs_created && - !TAILQ_EMPTY(a->config_info.symrefs)) { + !RB_EMPTY(a->config_info.symrefs)) { err = create_config_files(a->config_info.proto, a->config_info.host, a->config_info.port, a->config_info.remote_repo_path, @@ -1223,14 +1224,14 @@ list_remote_refs(struct got_pathlist_head *symrefs, const struct got_error *err; struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, symrefs, entry) { + RB_FOREACH(pe, got_pathlist_head, symrefs) { const char *refname = pe->path; const char *targetref = pe->data; printf("%s: %s\n", refname, targetref); } - TAILQ_FOREACH(pe, refs, entry) { + RB_FOREACH(pe,got_pathlist_head, refs) { const char *refname = pe->path; struct got_object_id *id = pe->data; char *id_str; @@ -1303,7 +1304,7 @@ is_wanted_ref(struct got_pathlist_head *wanted_refs, c { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, wanted_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, wanted_refs) { if (match_wanted_ref(refname, pe->path)) return 1; } @@ -1345,9 +1346,9 @@ create_gotconfig(const char *proto, const char *host, char *branches = NULL, *refs = NULL; ssize_t n; - if (!fetch_all_branches && !TAILQ_EMPTY(wanted_branches)) { + if (!fetch_all_branches && !RB_EMPTY(wanted_branches)) { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, wanted_branches, entry) { + RB_FOREACH(pe, got_pathlist_head, wanted_branches) { char *s; branchname = pe->path; if (strncmp(branchname, "refs/heads/", 11) == 0) @@ -1369,9 +1370,9 @@ create_gotconfig(const char *proto, const char *host, goto done; } } - if (!TAILQ_EMPTY(wanted_refs)) { + if (!RB_EMPTY(wanted_refs)) { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, wanted_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, wanted_refs) { char *s; const char *refname = pe->path; if (strncmp(refname, "refs/", 5) == 0) @@ -1470,9 +1471,9 @@ create_gitconfig(const char *git_url, const char *defa err = got_error_from_errno("asprintf"); goto done; } - } else if (!TAILQ_EMPTY(wanted_branches)) { + } else if (!RB_EMPTY(wanted_branches)) { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, wanted_branches, entry) { + RB_FOREACH(pe, got_pathlist_head, wanted_branches) { char *s; branchname = pe->path; if (strncmp(branchname, "refs/heads/", 11) == 0) @@ -1522,9 +1523,9 @@ create_gitconfig(const char *git_url, const char *defa goto done; } } - if (!TAILQ_EMPTY(wanted_refs)) { + if (!RB_EMPTY(wanted_refs)) { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, wanted_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, wanted_refs) { char *s; const char *refname = pe->path; if (strncmp(refname, "refs/", 5) == 0) @@ -1588,12 +1589,12 @@ create_config_files(const char *proto, const char *hos * If we asked for a set of wanted branches then use the first * one of those. */ - if (!TAILQ_EMPTY(wanted_branches)) { - pe = TAILQ_FIRST(wanted_branches); + if (!RB_EMPTY(wanted_branches)) { + pe = RB_MIN(got_pathlist_head, wanted_branches); default_branch = pe->path; } else { /* First HEAD ref listed by server is the default branch. */ - TAILQ_FOREACH(pe, symrefs, entry) { + RB_FOREACH(pe, got_pathlist_head, symrefs) { const char *refname = pe->path; const char *target = pe->data; @@ -1638,10 +1639,10 @@ cmd_clone(int argc, char *argv[]) int bflag = 0, list_refs_only = 0; int *pack_fds = NULL; - TAILQ_INIT(&refs); - TAILQ_INIT(&symrefs); - TAILQ_INIT(&wanted_branches); - TAILQ_INIT(&wanted_refs); + RB_INIT(&refs); + RB_INIT(&symrefs); + RB_INIT(&wanted_branches); + RB_INIT(&wanted_refs); while ((ch = getopt(argc, argv, "ab:J:lmqR:v")) != -1) { switch (ch) { @@ -1687,16 +1688,16 @@ cmd_clone(int argc, char *argv[]) argc -= optind; argv += optind; - if (fetch_all_branches && !TAILQ_EMPTY(&wanted_branches)) + if (fetch_all_branches && !RB_EMPTY(&wanted_branches)) option_conflict('a', 'b'); if (list_refs_only) { - if (!TAILQ_EMPTY(&wanted_branches)) + if (!RB_EMPTY(&wanted_branches)) option_conflict('l', 'b'); if (fetch_all_branches) option_conflict('l', 'a'); if (mirror_references) option_conflict('l', 'm'); - if (!TAILQ_EMPTY(&wanted_refs)) + if (!RB_EMPTY(&wanted_refs)) option_conflict('l', 'R'); } @@ -1840,7 +1841,7 @@ cmd_clone(int argc, char *argv[]) free(id_str); /* Set up references provided with the pack file. */ - TAILQ_FOREACH(pe, &refs, entry) { + RB_FOREACH(pe, got_pathlist_head, &refs) { const char *refname = pe->path; struct got_object_id *id = pe->data; char *remote_refname; @@ -1878,7 +1879,7 @@ cmd_clone(int argc, char *argv[]) } /* Set the HEAD reference if the server provided one. */ - TAILQ_FOREACH(pe, &symrefs, entry) { + RB_FOREACH(pe, got_pathlist_head, &symrefs) { struct got_reference *target_ref; const char *refname = pe->path; const char *target = pe->data; @@ -1944,7 +1945,7 @@ cmd_clone(int argc, char *argv[]) * a set of wanted branches use the first of one of those * which could be fetched instead. */ - TAILQ_FOREACH(pe, &wanted_branches, entry) { + RB_FOREACH(pe, got_pathlist_head, &wanted_branches) { const char *target = pe->path; struct got_reference *target_ref; @@ -2229,14 +2230,14 @@ delete_missing_refs(struct got_pathlist_head *their_re their_refname = local_refname; } - TAILQ_FOREACH(pe, their_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, their_refs) { if (strcmp(their_refname, pe->path) == 0) break; } if (pe != NULL) continue; - TAILQ_FOREACH(pe, their_symrefs, entry) { + RB_FOREACH(pe, got_pathlist_head, their_symrefs) { if (strcmp(their_refname, pe->path) == 0) break; } @@ -2396,11 +2397,11 @@ cmd_fetch(int argc, char *argv[]) const char *remote_head = NULL, *worktree_branch = NULL; const char *jumphost = NULL; - TAILQ_INIT(&refs); - TAILQ_INIT(&symrefs); + RB_INIT(&refs); + RB_INIT(&symrefs); TAILQ_INIT(&remote_refs); - TAILQ_INIT(&wanted_branches); - TAILQ_INIT(&wanted_refs); + RB_INIT(&wanted_branches); + RB_INIT(&wanted_refs); while ((ch = getopt(argc, argv, "ab:dJ:lqR:r:tvX")) != -1) { switch (ch) { @@ -2459,10 +2460,10 @@ cmd_fetch(int argc, char *argv[]) argc -= optind; argv += optind; - if (fetch_all_branches && !TAILQ_EMPTY(&wanted_branches)) + if (fetch_all_branches && !RB_EMPTY(&wanted_branches)) option_conflict('a', 'b'); if (list_refs_only) { - if (!TAILQ_EMPTY(&wanted_branches)) + if (!RB_EMPTY(&wanted_branches)) option_conflict('l', 'b'); if (fetch_all_branches) option_conflict('l', 'a'); @@ -2474,13 +2475,13 @@ cmd_fetch(int argc, char *argv[]) if (delete_remote) { if (fetch_all_branches) option_conflict('X', 'a'); - if (!TAILQ_EMPTY(&wanted_branches)) + if (!RB_EMPTY(&wanted_branches)) option_conflict('X', 'b'); if (delete_refs) option_conflict('X', 'd'); if (replace_tags) option_conflict('X', 't'); - if (!TAILQ_EMPTY(&wanted_refs)) + if (!RB_EMPTY(&wanted_refs)) option_conflict('X', 'R'); } @@ -2583,7 +2584,7 @@ cmd_fetch(int argc, char *argv[]) goto done; } - if (TAILQ_EMPTY(&wanted_branches)) { + if (RB_EMPTY(&wanted_branches)) { if (!fetch_all_branches) fetch_all_branches = remote->fetch_all_branches; for (i = 0; i < remote->nfetch_branches; i++) { @@ -2593,7 +2594,7 @@ cmd_fetch(int argc, char *argv[]) goto done; } } - if (TAILQ_EMPTY(&wanted_refs)) { + if (RB_EMPTY(&wanted_refs)) { for (i = 0; i < remote->nfetch_refs; i++) { error = got_pathlist_insert(NULL, &wanted_refs, remote->fetch_refs[i], NULL); @@ -2742,7 +2743,7 @@ cmd_fetch(int argc, char *argv[]) } /* Update references provided with the pack file. */ - TAILQ_FOREACH(pe, &refs, entry) { + RB_FOREACH(pe, got_pathlist_head, &refs) { const char *refname = pe->path; struct got_object_id *id = pe->data; struct got_reference *ref; @@ -2829,7 +2830,7 @@ cmd_fetch(int argc, char *argv[]) if (!remote->mirror_references) { /* Update remote HEAD reference if the server provided one. */ - TAILQ_FOREACH(pe, &symrefs, entry) { + RB_FOREACH(pe, got_pathlist_head, &symrefs) { struct got_reference *target_ref; const char *refname = pe->path; const char *target = pe->data; @@ -3105,7 +3106,7 @@ cmd_checkout(int argc, char *argv[]) struct got_checkout_progress_arg cpa; int *pack_fds = NULL; - TAILQ_INIT(&paths); + RB_INIT(&paths); #ifndef PROFILE if (pledge("stdio rpath wpath cpath fattr flock proc exec sendfd " @@ -3625,7 +3626,7 @@ cmd_update(int argc, char *argv[]) struct got_update_progress_arg upa; int *pack_fds = NULL; - TAILQ_INIT(&paths); + RB_INIT(&paths); #ifndef PROFILE if (pledge("stdio rpath wpath cpath fattr flock proc exec sendfd " @@ -3741,7 +3742,7 @@ cmd_update(int argc, char *argv[]) if (branch_name) { struct got_object_id *head_commit_id; - TAILQ_FOREACH(pe, &paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &paths) { if (pe->path_len == 0) continue; error = got_error_msg(GOT_ERR_BAD_PATH, @@ -4188,7 +4189,7 @@ match_changed_paths(int *have_match, struct got_pathli *have_match = 0; - TAILQ_FOREACH(pe, changed_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, changed_paths) { if (regexec(regex, pe->path, 1, &regmatch, 0) == 0) { *have_match = 1; break; @@ -4378,7 +4379,7 @@ print_diffstat(struct got_diffstat_cb_arg *dsa, const if (header != NULL) printf("%s\n", header); - TAILQ_FOREACH(pe, dsa->paths, entry) { + RB_FOREACH(pe, got_pathlist_head, dsa->paths) { struct got_diff_changed_path *cp = pe->data; int pad = dsa->max_path_len - pe->path_len + 1; @@ -4500,7 +4501,7 @@ print_commit(struct got_commit_object *commit, struct if (changed_paths && diffstat == NULL) { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, changed_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, changed_paths) { struct got_diff_changed_path *cp = pe->data; printf(" %c %s\n", cp->status, pe->path); @@ -4562,7 +4563,7 @@ print_commits(struct got_object_id *root_id, struct go struct got_pathlist_head changed_paths; STAILQ_INIT(&reversed_commits); - TAILQ_INIT(&changed_paths); + RB_INIT(&changed_paths); if (search_pattern && regcomp(&regex, search_pattern, REG_EXTENDED | REG_NOSUB | REG_NEWLINE)) @@ -5325,8 +5326,8 @@ cmd_diff(int argc, char *argv[]) memset(&dsa, 0, sizeof(dsa)); TAILQ_INIT(&refs); - TAILQ_INIT(&paths); - TAILQ_INIT(&diffstat_paths); + RB_INIT(&paths); + RB_INIT(&diffstat_paths); #ifndef PROFILE if (pledge("stdio rpath wpath cpath flock proc exec sendfd unveil", @@ -6609,7 +6610,7 @@ cmd_status(int argc, char *argv[]) int ch, i, no_ignores = 0; int *pack_fds = NULL; - TAILQ_INIT(&paths); + RB_INIT(&paths); memset(&st, 0, sizeof(st)); st.status_codes = NULL; @@ -7260,7 +7261,7 @@ cmd_branch(int argc, char *argv[]) char *commit_id_str = NULL, *keyword_idstr = NULL;; int *pack_fds = NULL; - TAILQ_INIT(&paths); + RB_INIT(&paths); #ifndef PROFILE if (pledge("stdio rpath wpath cpath fattr flock proc exec " @@ -8156,7 +8157,7 @@ cmd_add(int argc, char *argv[]) int ch, can_recurse = 0, no_ignores = 0; int *pack_fds = NULL; - TAILQ_INIT(&paths); + RB_INIT(&paths); #ifndef PROFILE if (pledge("stdio rpath wpath cpath flock proc exec sendfd unveil", @@ -8218,7 +8219,7 @@ cmd_add(int argc, char *argv[]) if (!can_recurse) { char *ondisk_path; struct stat sb; - TAILQ_FOREACH(pe, &paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &paths) { if (asprintf(&ondisk_path, "%s/%s", got_worktree_get_root_path(worktree), pe->path) == -1) { @@ -8301,7 +8302,7 @@ cmd_remove(int argc, char *argv[]) int ignore_missing_paths = 0; int *pack_fds = NULL; - TAILQ_INIT(&paths); + RB_INIT(&paths); #ifndef PROFILE if (pledge("stdio rpath wpath cpath flock proc exec sendfd unveil", @@ -8383,7 +8384,7 @@ cmd_remove(int argc, char *argv[]) if (!can_recurse) { char *ondisk_path; struct stat sb; - TAILQ_FOREACH(pe, &paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &paths) { if (asprintf(&ondisk_path, "%s/%s", got_worktree_get_root_path(worktree), pe->path) == -1) { @@ -8858,7 +8859,7 @@ worktree_has_commitable_path(void *arg, unsigned char if (a->commit_paths != NULL) { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, a->commit_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, a->commit_paths) { if (strncmp(path, pe->path, pe->path_len) == 0) { *a->has_changes = 1; @@ -8890,7 +8891,7 @@ commit_path_changed_in_worktree(struct wt_commitable_p struct got_tree_object *tree = NULL, *ptree = NULL; struct got_object_qid *pid; - TAILQ_INIT(&paths); + RB_INIT(&paths); err = got_object_open_as_commit(&commit, repo, id); if (err) @@ -9041,7 +9042,7 @@ cmd_revert(int argc, char *argv[]) struct choose_patch_arg cpa; int *pack_fds = NULL; - TAILQ_INIT(&paths); + RB_INIT(&paths); #ifndef PROFILE if (pledge("stdio rpath wpath cpath fattr flock proc exec sendfd " @@ -9120,7 +9121,7 @@ cmd_revert(int argc, char *argv[]) if (!can_recurse) { char *ondisk_path; struct stat sb; - TAILQ_FOREACH(pe, &paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &paths) { if (asprintf(&ondisk_path, "%s/%s", got_worktree_get_root_path(worktree), pe->path) == -1) { @@ -9301,7 +9302,7 @@ collect_commit_logmsg(struct got_pathlist_head *commit goto done; } - TAILQ_FOREACH(pe, commitable_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, commitable_paths) { struct got_commitable *ct = pe->data; dprintf(fd, "# %c %s\n", got_commitable_get_status(ct), @@ -9494,7 +9495,7 @@ cmd_commit(int argc, char *argv[]) int *pack_fds = NULL; TAILQ_INIT(&refs); - TAILQ_INIT(&paths); + RB_INIT(&paths); cl_arg.logmsg_path = NULL; #ifndef PROFILE @@ -9769,7 +9770,7 @@ send_progress(void *arg, int ncolored, int nfound, int if (success) { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, a->delete_branches, entry) { + RB_FOREACH(pe, got_pathlist_head, a->delete_branches) { const char *branchname = pe->path; if (got_path_cmp(branchname, refname, strlen(branchname), strlen(refname)) == 0) { @@ -9936,12 +9937,12 @@ cmd_send(int argc, char *argv[]) int *pack_fds = NULL; const char *jumphost = NULL; - TAILQ_INIT(&branches); - TAILQ_INIT(&tags); + RB_INIT(&branches); + RB_INIT(&tags); TAILQ_INIT(&all_branches); TAILQ_INIT(&all_tags); - TAILQ_INIT(&delete_args); - TAILQ_INIT(&delete_branches); + RB_INIT(&delete_args); + RB_INIT(&delete_branches); while ((ch = getopt(argc, argv, "ab:d:fJ:qr:Tt:v")) != -1) { switch (ch) { @@ -9997,9 +9998,9 @@ cmd_send(int argc, char *argv[]) argc -= optind; argv += optind; - if (send_all_branches && !TAILQ_EMPTY(&branches)) + if (send_all_branches && !RB_EMPTY(&branches)) option_conflict('a', 'b'); - if (send_all_tags && !TAILQ_EMPTY(&tags)) + if (send_all_tags && !RB_EMPTY(&tags)) option_conflict('T', 't'); @@ -10171,7 +10172,7 @@ cmd_send(int argc, char *argv[]) * with 'got send -d'. * Deleting anything else requires local repository access or Git. */ - TAILQ_FOREACH(pe, &delete_args, entry) { + RB_FOREACH(pe, got_pathlist_head, &delete_args) { const char *branchname = pe->path; char *s; struct got_pathlist_entry *new; @@ -10314,7 +10315,7 @@ process_logmsg_refs(const char *ref_prefix, size_t pre int found = 0; TAILQ_INIT(&refs); - TAILQ_INIT(&paths); + RB_INIT(&paths); err = got_ref_list(&refs, repo, NULL, got_ref_cmp_by_name, repo); if (err) @@ -11518,7 +11519,7 @@ cmd_rebase(int argc, char *argv[]) int *pack_fds = NULL; STAILQ_INIT(&commits); - TAILQ_INIT(&merged_paths); + RB_INIT(&merged_paths); memset(&upa, 0, sizeof(upa)); #ifndef PROFILE @@ -11793,7 +11794,7 @@ cmd_rebase(int argc, char *argv[]) branch_head_commit_id); if (error) goto done; - TAILQ_INIT(&paths); + RB_INIT(&paths); error = got_pathlist_insert(NULL, &paths, "", NULL); if (error) goto done; @@ -12806,7 +12807,7 @@ cmd_histedit(int argc, char *argv[]) STAILQ_INIT(&commits); TAILQ_INIT(&histedit_cmds); - TAILQ_INIT(&merged_paths); + RB_INIT(&merged_paths); memset(&upa, 0, sizeof(upa)); #ifndef PROFILE @@ -13256,7 +13257,7 @@ cmd_histedit(int argc, char *argv[]) struct got_pathlist_head paths; int have_changes = 0; - TAILQ_INIT(&paths); + RB_INIT(&paths); error = got_pathlist_insert(NULL, &paths, "", NULL); if (error) goto done; @@ -13815,7 +13816,7 @@ cmd_merge(int argc, char *argv[]) branch_tip); if (error) goto done; - TAILQ_INIT(&paths); + RB_INIT(&paths); error = got_pathlist_insert(NULL, &paths, "", NULL); if (error) goto done; @@ -13983,7 +13984,7 @@ cmd_stage(int argc, char *argv[]) struct choose_patch_arg cpa; int *pack_fds = NULL; - TAILQ_INIT(&paths); + RB_INIT(&paths); #ifndef PROFILE if (pledge("stdio rpath wpath cpath fattr flock proc exec sendfd " @@ -14119,7 +14120,7 @@ cmd_unstage(int argc, char *argv[]) struct choose_patch_arg cpa; int *pack_fds = NULL; - TAILQ_INIT(&paths); + RB_INIT(&paths); #ifndef PROFILE if (pledge("stdio rpath wpath cpath fattr flock proc exec sendfd " @@ -14609,7 +14610,7 @@ print_path_info(void *arg, const char *path, mode_t mo * Clear error indication from any of the path arguments which * would cause this file index entry to be displayed. */ - TAILQ_FOREACH(pe, paths, entry) { + RB_FOREACH(pe, got_pathlist_head, paths) { if (got_path_cmp(path, pe->path, strlen(path), pe->path_len) == 0 || got_path_is_child(path, pe->path, pe->path_len)) @@ -14674,7 +14675,7 @@ cmd_info(int argc, char *argv[]) int *pack_fds = NULL; int ch, show_files = 0; - TAILQ_INIT(&paths); + RB_INIT(&paths); #ifndef PROFILE if (pledge("stdio rpath wpath cpath flock proc exec sendfd unveil", @@ -14760,7 +14761,7 @@ cmd_info(int argc, char *argv[]) if (show_files) { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, &paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &paths) { if (pe->path_len == 0) continue; /* @@ -14773,7 +14774,7 @@ cmd_info(int argc, char *argv[]) print_path_info, &paths, check_cancelled, NULL); if (error) goto done; - TAILQ_FOREACH(pe, &paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &paths) { if (pe->data != NULL) { const struct got_error *perr; blob - b4498d7b27edc861c011a977cef6c8b66603f09d blob + 5a8c2bc8ec21628c9260de98ee4077f5f878ff15 --- gotadmin/gotadmin.c +++ gotadmin/gotadmin.c @@ -15,6 +15,7 @@ */ #include <sys/queue.h> +#include <sys/tree.h> #include <sys/types.h> #include <ctype.h> @@ -728,7 +729,7 @@ cmd_pack(int argc, char *argv[]) struct got_reflist_entry *re, *new; int *pack_fds = NULL; - TAILQ_INIT(&exclude_args); + RB_INIT(&exclude_args); TAILQ_INIT(&exclude_refs); TAILQ_INIT(&include_refs); @@ -788,7 +789,7 @@ cmd_pack(int argc, char *argv[]) if (error) goto done; - TAILQ_FOREACH(pe, &exclude_args, entry) { + RB_FOREACH(pe, got_pathlist_head, &exclude_args) { const char *refname = pe->path; error = add_ref(&new, &exclude_refs, refname, repo); if (error) @@ -1435,7 +1436,7 @@ cmd_dump(int argc, char *argv[]) int verbosity = 0; int i, ch; - TAILQ_INIT(&exclude_args); + RB_INIT(&exclude_args); TAILQ_INIT(&exclude_refs); TAILQ_INIT(&include_refs); @@ -1487,7 +1488,7 @@ cmd_dump(int argc, char *argv[]) if (error) goto done; - TAILQ_FOREACH(pe, &exclude_args, entry) { + RB_FOREACH(pe, got_pathlist_head, &exclude_args) { refname = pe->path; error = add_ref(&new, &exclude_refs, refname, repo); if (error) @@ -1569,10 +1570,10 @@ is_wanted_ref(struct got_pathlist_head *wanted, const { struct got_pathlist_entry *pe; - if (TAILQ_EMPTY(wanted)) + if (RB_EMPTY(wanted)) return 1; - TAILQ_FOREACH(pe, wanted, entry) { + RB_FOREACH(pe, got_pathlist_head, wanted) { if (strcmp(pe->path, ref) == 0) return 1; } @@ -1685,8 +1686,8 @@ cmd_load(int argc, char *argv[]) int verbosity = 0; int ch, i; - TAILQ_INIT(&include_args); - TAILQ_INIT(&available_refs); + RB_INIT(&include_args); + RB_INIT(&available_refs); #ifndef PROFILE if (pledge("stdio rpath wpath cpath fattr flock proc exec " @@ -1766,7 +1767,7 @@ cmd_load(int argc, char *argv[]) goto done; if (list_refs_only) { - TAILQ_FOREACH(pe, &available_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, &available_refs) { const char *refname = pe->path; struct got_object_id *id = pe->data; char *idstr; @@ -1785,7 +1786,7 @@ cmd_load(int argc, char *argv[]) goto done; /* Update references */ - TAILQ_FOREACH(pe, &available_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, &available_refs) { const struct got_error *unlock_err; struct got_reference *ref; const char *refname = pe->path; blob - 8eb6f4396784abfa7a956c90fb3cc41e5d2b433f blob + 8b82d1907770f8ead09033b724fa42de69e518be --- gotctl/gotctl.c +++ gotctl/gotctl.c @@ -15,6 +15,7 @@ */ #include <sys/queue.h> +#include <sys/tree.h> #include <sys/socket.h> #include <sys/un.h> blob - 41f6842f800bb0722d2303a4924d74865b6d1fba blob + 8d274e36aa1f7805cbd23da72ff2b38109621dea --- gotd/auth.c +++ gotd/auth.c @@ -18,6 +18,7 @@ #include <sys/types.h> #include <sys/socket.h> #include <sys/queue.h> +#include <sys/tree.h> #include <sys/uio.h> #include <errno.h> blob - d0c3603547caa4335b08553a55a7113dfc613d21 blob + 8993f7756e9028f8ef050eefe400427e6566a59b --- gotd/imsg.c +++ gotd/imsg.c @@ -15,6 +15,7 @@ */ #include <sys/queue.h> +#include <sys/tree.h> #include <sys/types.h> #include <sys/uio.h> blob - 5dab7072d9c805c4247a01452c85875d4639f46e blob + 28fbaa765410499bebb4c75973c46de6655912a1 --- gotd/listen.c +++ gotd/listen.c @@ -16,6 +16,7 @@ #include <sys/types.h> #include <sys/queue.h> +#include <sys/tree.h> #include <sys/socket.h> #include <sys/uio.h> blob - b48a3fe7e6a07d8747d390f34683097289a4d6c2 blob + dd67229618c65cd823858180377b61bd8b02830e --- gotd/parse.y +++ gotd/parse.y @@ -25,6 +25,7 @@ #include <sys/time.h> #include <sys/types.h> #include <sys/queue.h> +#include <sys/tree.h> #include <sys/stat.h> #include <ctype.h> @@ -1329,12 +1330,12 @@ conf_new_repo(const char *name) fatalx("%s: calloc", __func__); STAILQ_INIT(&repo->rules); - TAILQ_INIT(&repo->protected_tag_namespaces); - TAILQ_INIT(&repo->protected_branch_namespaces); - TAILQ_INIT(&repo->protected_branches); - TAILQ_INIT(&repo->protected_branches); - TAILQ_INIT(&repo->notification_refs); - TAILQ_INIT(&repo->notification_ref_namespaces); + RB_INIT(&repo->protected_tag_namespaces); + RB_INIT(&repo->protected_branch_namespaces); + RB_INIT(&repo->protected_branches); + RB_INIT(&repo->protected_branches); + RB_INIT(&repo->notification_refs); + RB_INIT(&repo->notification_ref_namespaces); STAILQ_INIT(&repo->notification_targets); if (strlcpy(repo->name, name, sizeof(repo->name)) >= @@ -1423,7 +1424,7 @@ conf_protect_tag_namespace(struct gotd_repo *repo, cha namespace) == -1) return -1; - TAILQ_FOREACH(pe, &repo->protected_branch_namespaces, entry) { + RB_FOREACH(pe, got_pathlist_head, &repo->protected_branch_namespaces) { if (strcmp(pe->path, new) == 0) { yyerror("duplicate protected namespace %s", namespace); return -1; @@ -1443,7 +1444,7 @@ conf_protect_branch_namespace(struct gotd_repo *repo, &repo->protected_branch_namespaces, namespace) == -1) return -1; - TAILQ_FOREACH(pe, &repo->protected_tag_namespaces, entry) { + RB_FOREACH(pe, got_pathlist_head, &repo->protected_tag_namespaces) { if (strcmp(pe->path, new) == 0) { yyerror("duplicate protected namespace %s", namespace); return -1; blob - 77b067240f937a51ae13c32d0bbc9362d7796286 blob + cde254c906d136723be9be3524aa383c26132dad --- gotd/repo_imsg.c +++ gotd/repo_imsg.c @@ -16,6 +16,7 @@ #include <sys/types.h> #include <sys/queue.h> +#include <sys/tree.h> #include <sys/uio.h> #include <event.h> blob - f44eb26f2a6197c25f2795391a684fce6ef79b29 blob + 62e95bc3c4eee3e045d642b2b1a6496f839d03ce --- gotd/repo_read.c +++ gotd/repo_read.c @@ -15,6 +15,7 @@ */ #include <sys/queue.h> +#include <sys/tree.h> #include <sys/types.h> #include <event.h> blob - 00881c209db0d54b36e0c566e676b5446387618e blob + 8f92913331bd60b19ef2fd111b33c55e075f4a01 --- gotd/repo_write.c +++ gotd/repo_write.c @@ -1405,7 +1405,7 @@ verify_packfile(void) if (ref_update->delete_ref) continue; - TAILQ_FOREACH(pe, repo_write.protected_tag_namespaces, entry) { + RB_FOREACH(pe, got_pathlist_head, repo_write.protected_tag_namespaces) { err = protect_tag_namespace(pe->path, &client->pack, packidx, ref_update); if (err) @@ -1437,14 +1437,15 @@ verify_packfile(void) } } - TAILQ_FOREACH(pe, repo_write.protected_branch_namespaces, - entry) { + RB_FOREACH(pe, got_pathlist_head, repo_write.protected_branch_namespaces) + { err = protect_branch_namespace(pe->path, &client->pack, packidx, ref_update); if (err) goto done; } - TAILQ_FOREACH(pe, repo_write.protected_branches, entry) { + RB_FOREACH(pe, got_pathlist_head, repo_write.protected_branches) + { err = protect_branch(pe->path, &client->pack, packidx, ref_update); if (err) @@ -1477,20 +1478,22 @@ protect_refs_from_deletion(void) refname = got_ref_get_name(ref_update->ref); - TAILQ_FOREACH(pe, repo_write.protected_tag_namespaces, entry) { + RB_FOREACH(pe, got_pathlist_head, + repo_write.protected_tag_namespaces) { err = protect_ref_namespace(refname, pe->path); if (err) return err; } - TAILQ_FOREACH(pe, repo_write.protected_branch_namespaces, - entry) { + RB_FOREACH(pe, got_pathlist_head, + repo_write.protected_branch_namespaces) { err = protect_ref_namespace(refname, pe->path); if (err) return err; } - TAILQ_FOREACH(pe, repo_write.protected_branches, entry) { + RB_FOREACH(pe, got_pathlist_head, repo_write.protected_branches) + { if (strcmp(refname, pe->path) == 0) { return got_error_fmt(GOT_ERR_REF_PROTECTED, "%s", refname); @@ -1721,7 +1724,7 @@ print_diffstat(struct got_diffstat_cb_arg *dsa, int fd { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, dsa->paths, entry) { + RB_FOREACH(pe, got_pathlist_head, dsa->paths) { struct got_diff_changed_path *cp = pe->data; int pad = dsa->max_path_len - pe->path_len + 1; @@ -1884,7 +1887,7 @@ print_commits(struct got_object_id *root_id, struct go const int shortlog_threshold = 50; STAILQ_INIT(&reversed_commits); - TAILQ_INIT(&changed_paths); + RB_INIT(&changed_paths); /* XXX first-parent only for now */ err = got_commit_graph_open(&graph, "/", 1); blob - ce6a68ae4e3613742b57a1c5fafd1978318f2ff5 blob + 1c759a341683fe39614e0c779362809c3d1610e2 --- gotd/session_write.c +++ gotd/session_write.c @@ -428,14 +428,14 @@ queue_notification(struct got_object_id *old_id, struc STAILQ_EMPTY(&repo_cfg->notification_targets)) return NULL; /* notifications unused */ - TAILQ_FOREACH(pe, &repo_cfg->notification_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, &repo_cfg->notification_refs) { const char *refname = pe->path; if (strcmp(got_ref_get_name(ref), refname) == 0) break; } if (pe == NULL) { - TAILQ_FOREACH(pe, &repo_cfg->notification_ref_namespaces, - entry) { + RB_FOREACH(pe, got_pathlist_head, + &repo_cfg->notification_ref_namespaces) { const char *namespace = pe->path; err = validate_namespace(namespace); @@ -452,8 +452,8 @@ queue_notification(struct got_object_id *old_id, struc * configuration file then only send notifications if a match * was found. */ - if (pe == NULL && (!TAILQ_EMPTY(&repo_cfg->notification_refs) || - !TAILQ_EMPTY(&repo_cfg->notification_ref_namespaces))) + if (pe == NULL && (!RB_EMPTY(&repo_cfg->notification_refs) || + !RB_EMPTY(&repo_cfg->notification_ref_namespaces))) return NULL; notif = calloc(1, sizeof(*notif)); blob - c578f8cbb9a1c2672039a719cdba04b4eacdb8d9 blob + 13623bc34739f85f1e1611827992c048d0747d09 --- gotsh/gotsh.c +++ gotsh/gotsh.c @@ -15,6 +15,7 @@ */ #include <sys/queue.h> +#include <sys/tree.h> #include <sys/socket.h> #include <sys/un.h> blob - fa0ac810a87d9612d80f8ec79b2bd02e05585ee4 blob + 2a9b146bfbe9dc3e2c817db363f23b0f026365e2 --- gotwebd/got_operations.c +++ gotwebd/got_operations.c @@ -16,6 +16,7 @@ */ #include <sys/queue.h> +#include <sys/tree.h> #include <sys/socket.h> #include <sys/stat.h> blob - 8e2c5e8b2e3842ce24fdd4ba82b911248e36e8e7 blob + bd243664f8ab465eb64c32b988299bfe3b0fadb7 --- gotwebd/gotweb.c +++ gotwebd/gotweb.c @@ -21,6 +21,7 @@ #include <net/if.h> #include <netinet/in.h> #include <sys/queue.h> +#include <sys/tree.h> #include <sys/stat.h> #include <sys/types.h> blob - 1100e919033e225f9500e38d04dc8c9304369742 blob + 8232df1c967a331ed394daaa474c7547e2c93fda --- include/got_path.h +++ include/got_path.h @@ -61,19 +61,18 @@ int got_path_is_child(const char *, const char *, size */ int got_path_cmp(const char *, const char *, size_t, size_t); -/* - * Path lists allow for predictable concurrent iteration over multiple lists - * of paths obtained from disparate sources which don't all provide the same - * ordering guarantees (e.g. git trees, file index, and on-disk directories). - */ + struct got_pathlist_entry { - TAILQ_ENTRY(got_pathlist_entry) entry; + RB_ENTRY(got_pathlist_entry) entry; const char *path; size_t path_len; void *data; /* data pointer provided to got_pathlist_insert() */ }; -TAILQ_HEAD(got_pathlist_head, got_pathlist_entry); +int got_pathlist_cmp(const struct got_pathlist_entry * , const struct got_pathlist_entry *); +RB_HEAD(got_pathlist_head, got_pathlist_entry); +RB_PROTOTYPE(got_pathlist_head, got_pathlist_entry, entry, got_pathlist_cmp); + /* * Insert a path into the list of paths in a predictable order. * The caller should already have initialized the list head. This list stores blob - 1efd31bd7fbba8901c47aba134f6e6aa7381e4f5 blob + 520585806a2fff0f856abd6880e5c48cbacd6069 --- lib/commit_graph.c +++ lib/commit_graph.c @@ -17,6 +17,7 @@ #include <sys/types.h> #include <sys/stat.h> #include <sys/queue.h> +#include <sys/tree.h> #include <sys/stdint.h> #include <limits.h> blob - 11a24fdcbb22ef869c3b17bf02354c6f7a580e97 blob + 5ee4248318a070e5605e27ad3ee7e408896a2ce8 --- lib/deflate.c +++ lib/deflate.c @@ -15,6 +15,7 @@ */ #include <sys/queue.h> +#include <sys/tree.h> #include <errno.h> #include <stdio.h> blob - e43d98ae41c70e48398afaded344bc66a394b968 blob + 2c3f8c2ebcd41b76c90f5701a0b1ffc43fbdccc3 --- lib/delta.c +++ lib/delta.c @@ -15,6 +15,7 @@ */ #include <sys/queue.h> +#include <sys/tree.h> #include <stdio.h> #include <stdlib.h> blob - 6f47d70612b97fe473d6aba91f3907153a33dd56 blob + ca330996f861e3db0b6d6182071f7f81bb4b4144 --- lib/dial.c +++ lib/dial.c @@ -16,6 +16,7 @@ */ #include <sys/queue.h> +#include <sys/tree.h> #include <sys/types.h> #include <sys/socket.h> #include <sys/uio.h> blob - 705da341e0ac7d7a3ac8291c8c6ad8d46b365aee blob + 658c27563232e250780c4d2b9306e9643b58167f --- lib/diff.c +++ lib/diff.c @@ -15,6 +15,7 @@ */ #include <sys/queue.h> +#include <sys/tree.h> #include <sys/stat.h> #include <stdio.h> @@ -121,7 +122,7 @@ get_diffstat(struct got_diffstat_cb_arg *ds, const cha return err; } - pe = TAILQ_LAST(ds->paths, got_pathlist_head); + pe = RB_MAX(got_pathlist_head, ds->paths); diffstat_field_width(&ds->max_path_len, &ds->add_cols, &ds->rm_cols, pe->path_len, change->add, change->rm); @@ -1123,7 +1124,7 @@ diff_paths(struct got_tree_object *tree1, struct got_t struct got_tree_object *subtree1 = NULL, *subtree2 = NULL; struct got_blob_object *blob1 = NULL, *blob2 = NULL; - TAILQ_FOREACH(pe, paths, entry) { + RB_FOREACH(pe, got_pathlist_head, paths) { int type1 = GOT_OBJ_TYPE_ANY, type2 = GOT_OBJ_TYPE_ANY; mode_t mode1 = 0, mode2 = 0; @@ -1315,7 +1316,7 @@ diff_objects_as_trees(struct got_diff_line **lines, si arg.lines = NULL; arg.nlines = 0; } - if (paths == NULL || TAILQ_EMPTY(paths)) + if (paths == NULL || RB_EMPTY(paths)) err = got_diff_tree(tree1, tree2, f1, f2, fd1, fd2, label1, label2, repo, got_diff_blob_output_unidiff, &arg, 1); else blob - b64070e012cce8f1a3fb519298edb01b361b48eb blob + 4e0331d997a587a82491c0c1835d0ae523400561 --- lib/fetch.c +++ lib/fetch.c @@ -145,7 +145,7 @@ got_fetch_pack(struct got_object_id **pack_hash, struc * Prevent fetching of references that won't make any * sense outside of the remote repository's context. */ - TAILQ_FOREACH(pe, wanted_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, wanted_refs) { const char *refname = pe->path; if (strncmp(refname, "refs/got/", 9) == 0 || strncmp(refname, "got/", 4) == 0 || @@ -160,7 +160,7 @@ got_fetch_pack(struct got_object_id **pack_hash, struc for (i = 0; i < nitems(tmpfds); i++) tmpfds[i] = -1; - TAILQ_INIT(&have_refs); + RB_INIT(&have_refs); TAILQ_INIT(&my_refs); if (!list_refs_only) { blob - 6ddd929ab113d775d617c28c07573f2012ec924c blob + dbef298e12a03f1a40e8adf8a5cffe916aca0681 --- lib/fileindex.c +++ lib/fileindex.c @@ -1060,9 +1060,10 @@ have_tracked_file_in_dir(struct got_fileindex *fileind static const struct got_error * walk_dir(struct got_pathlist_entry **next, struct got_fileindex *fileindex, - struct got_fileindex_entry **ie, struct got_pathlist_entry *dle, int fd, - const char *path, const char *rootpath, struct got_repository *repo, - int ignore, struct got_fileindex_diff_dir_cb *cb, void *cb_arg) + struct got_fileindex_entry **ie, struct got_pathlist_entry *dle, + struct got_pathlist_head *dlh, int fd, const char *path, + const char *rootpath, struct got_repository *repo, int ignore, + struct got_fileindex_diff_dir_cb *cb, void *cb_arg) { const struct got_error *err = NULL; struct dirent *de = dle->data; @@ -1081,7 +1082,7 @@ walk_dir(struct got_pathlist_entry **next, struct got_ char *subdirpath; struct got_pathlist_head subdirlist; - TAILQ_INIT(&subdirlist); + RB_INIT(&subdirlist); if (asprintf(&subpath, "%s%s%s", path, path[0] == '\0' ? "" : "/", de->d_name) == -1) @@ -1096,7 +1097,7 @@ walk_dir(struct got_pathlist_entry **next, struct got_ O_RDONLY | O_NOFOLLOW | O_DIRECTORY | O_CLOEXEC); if (subdirfd == -1) { if (errno == EACCES) { - *next = TAILQ_NEXT(dle, entry); + *next = RB_NEXT(got_pathlist_head, dlh, dle); return NULL; } err = got_error_from_errno2("openat", subdirpath); @@ -1132,7 +1133,7 @@ walk_dir(struct got_pathlist_entry **next, struct got_ return err; } - *next = TAILQ_NEXT(dle, entry); + *next = RB_NEXT(got_pathlist_head, dlh, dle); return NULL; } @@ -1177,7 +1178,7 @@ diff_fileindex_dir(struct got_fileindex *fileindex, return err; } - dle = TAILQ_FIRST(dirlist); + dle = RB_MIN(got_pathlist_head, dirlist); while ((*ie && got_path_is_child((*ie)->path, path, path_len)) || dle) { if (dle && *ie) { char *de_path; @@ -1201,9 +1202,10 @@ diff_fileindex_dir(struct got_fileindex *fileindex, if (err) break; *ie = walk_fileindex(fileindex, *ie); - err = walk_dir(&dle, fileindex, ie, dle, dirfd, - path, rootpath, repo, 0, cb, cb_arg); - } else if (cmp < 0 ) { + err = walk_dir(&dle, fileindex, ie, dle, + dirlist, dirfd, path, rootpath, repo, 0, + cb, cb_arg); + } else if (cmp < 0) { err = cb->diff_old(cb_arg, *ie, path); if (err) break; @@ -1213,8 +1215,9 @@ diff_fileindex_dir(struct got_fileindex *fileindex, dirfd); if (err) break; - err = walk_dir(&dle, fileindex, ie, dle, dirfd, - path, rootpath, repo, ignore, cb, cb_arg); + err = walk_dir(&dle, fileindex, ie, dle, + dirlist, dirfd, path, rootpath, repo, + ignore, cb, cb_arg); } if (err) break; @@ -1231,8 +1234,8 @@ diff_fileindex_dir(struct got_fileindex *fileindex, err = cb->diff_new(&ignore, cb_arg, de, path, dirfd); if (err) break; - err = walk_dir(&dle, fileindex, ie, dle, dirfd, path, - rootpath, repo, ignore, cb, cb_arg); + err = walk_dir(&dle, fileindex, ie, dle, dirlist, + dirfd, path, rootpath, repo, ignore, cb, cb_arg); if (err) break; } @@ -1252,7 +1255,7 @@ got_fileindex_diff_dir(struct got_fileindex *fileindex int fd2; DIR *dir; - TAILQ_INIT(&dirlist); + RB_INIT(&dirlist); /* * Duplicate the file descriptor so we can call closedir() below blob - 7bf09a8a6503e2cf488f090ab7a98b0a0762ae04 blob + f8a58e05685c1a15956029d0833c3014e3008d78 --- lib/gitproto.c +++ lib/gitproto.c @@ -16,6 +16,7 @@ */ #include <sys/queue.h> +#include <sys/tree.h> #include <sys/types.h> #include <ctype.h> blob - e8f06f56c03a04d123c91c39f96c6bc046cb71d9 blob + 49f05411c2efb58063883962301c09d2319d19e6 --- lib/inflate.c +++ lib/inflate.c @@ -15,6 +15,7 @@ */ #include <sys/queue.h> +#include <sys/tree.h> #include <errno.h> #include <stdio.h> blob - 0af419be5282778934e8a5369c5793756c35ecd3 blob + 8a796d4d28606f8e51d7207a19b3cb470facba06 --- lib/lockfile.c +++ lib/lockfile.c @@ -16,6 +16,7 @@ #include <sys/stat.h> #include <sys/queue.h> +#include <sys/tree.h> #include <errno.h> #include <fcntl.h> blob - c3f64cf304de14ee32b20d2d42f888f38bec81a0 blob + 9d98158fc39b736def37140f6711f0da05badf51 --- lib/object_create.c +++ lib/object_create.c @@ -17,6 +17,7 @@ #include <sys/types.h> #include <sys/stat.h> #include <sys/queue.h> +#include <sys/tree.h> #include <sys/wait.h> #include <ctype.h> @@ -329,7 +330,7 @@ got_object_tree_create(struct got_object_id **id, return got_error_from_errno("calloc"); i = 0; - TAILQ_FOREACH(pe, paths, entry) + RB_FOREACH(pe, got_pathlist_head, paths) sorted_entries[i++] = pe->data; mergesort(sorted_entries, nentries, sizeof(struct got_tree_entry *), sort_tree_entries_the_way_git_likes_it); blob - 5b83d584098fac8855f9938cbe05d3425d7c6bde blob + ed36f2076d71d7ed6931ebfd54eac2aa82fc6264 --- lib/pack.c +++ lib/pack.c @@ -17,6 +17,7 @@ #include <sys/types.h> #include <sys/stat.h> #include <sys/queue.h> +#include <sys/tree.h> #include <sys/uio.h> #include <sys/mman.h> #include <sys/resource.h> blob - 51eb2fd9f78c26e8b8bdecf029482685172ecfe7 blob + c6787c3643ca1ced91d4ef5d2530f153f72bb6e0 --- lib/pack_create.c +++ lib/pack_create.c @@ -489,7 +489,7 @@ got_pack_find_pack_for_reuse(struct got_packidx **best *best_packidx = NULL; - TAILQ_FOREACH(pe, &repo->packidx_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &repo->packidx_paths) { const char *path_packidx = pe->path; struct got_packidx *packidx; int nobj; @@ -1142,7 +1142,7 @@ got_pack_find_pack_for_commit_painting(struct got_pack * Find the largest pack which contains at least some of the * commits we are interested in. */ - TAILQ_FOREACH(pe, &repo->packidx_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &repo->packidx_paths) { const char *path_packidx = pe->path; struct got_packidx *packidx; int nobj, idx, ncommits = 0; @@ -1278,7 +1278,7 @@ find_pack_for_enumeration(struct got_packidx **best_pa * Find the largest pack which contains at least some of the * commits and tags we are interested in. */ - TAILQ_FOREACH(pe, &repo->packidx_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &repo->packidx_paths) { const char *path_packidx = pe->path; struct got_packidx *packidx; int nobj, i, idx, ncommits = 0; blob - 0e7c4171ee06743bd3b8004b3c0b3158aa3118da blob + 1e2281754794ae39f794df658cc348bd6aaf1490 --- lib/patch.c +++ lib/patch.c @@ -22,6 +22,7 @@ #include <sys/types.h> #include <sys/queue.h> +#include <sys/tree.h> #include <sys/socket.h> #include <sys/stat.h> #include <sys/uio.h> blob - 8242bbe0f1553766e05f3b6750c7a283387e0907 blob + 19b5fc1b23828a64e772094208f1a08e0372df5a --- lib/path.c +++ lib/path.c @@ -17,6 +17,7 @@ */ #include <sys/queue.h> +#include <sys/tree.h> #include <sys/stat.h> #include <errno.h> @@ -213,43 +214,29 @@ got_path_cmp(const char *path1, const char *path2, siz return (unsigned char)path1[i] < (unsigned char)path2[i] ? -1 : 1; } +int +got_pathlist_cmp(const struct got_pathlist_entry *p1, + const struct got_pathlist_entry *p2) +{ + return got_path_cmp(p1->path, p2->path, p1->path_len, p2->path_len); +} + const struct got_error * got_pathlist_insert(struct got_pathlist_entry **inserted, struct got_pathlist_head *pathlist, const char *path, void *data) { - struct got_pathlist_entry *new, *pe; + struct got_pathlist_entry *new; size_t path_len = strlen(path); if (inserted) *inserted = NULL; - - /* - * Many callers will provide paths in a somewhat sorted order while - * constructing a path list from inputs such as tree objects or - * dirents. Iterating backwards from the tail of the list should - * be more efficient than traversing through the entire list each - * time an element is inserted. - */ - pe = TAILQ_LAST(pathlist, got_pathlist_head); - while (pe) { - int cmp = got_path_cmp(pe->path, path, pe->path_len, path_len); - if (cmp == 0) - return NULL; /* duplicate */ - else if (cmp < 0) - break; - pe = TAILQ_PREV(pe, got_pathlist_head, entry); - } - new = malloc(sizeof(*new)); if (new == NULL) return got_error_from_errno("malloc"); new->path = path; new->path_len = path_len; new->data = data; - if (pe) - TAILQ_INSERT_AFTER(pathlist, pe, new, entry); - else - TAILQ_INSERT_HEAD(pathlist, new, entry); + RB_INSERT(got_pathlist_head, pathlist, new); if (inserted) *inserted = new; return NULL; @@ -258,9 +245,9 @@ got_pathlist_insert(struct got_pathlist_entry **insert void got_pathlist_free(struct got_pathlist_head *pathlist, int freemask) { - struct got_pathlist_entry *pe; + struct got_pathlist_entry *pe, *temp; - while ((pe = TAILQ_FIRST(pathlist)) != NULL) { + RB_FOREACH_SAFE(pe, got_pathlist_head, pathlist, temp) { if (freemask & GOT_PATHLIST_FREE_PATH) { free((char *)pe->path); pe->path = NULL; @@ -269,7 +256,7 @@ got_pathlist_free(struct got_pathlist_head *pathlist, free(pe->data); pe->data = NULL; } - TAILQ_REMOVE(pathlist, pe, entry); + RB_REMOVE(got_pathlist_head, pathlist, pe); free(pe); } } @@ -549,3 +536,5 @@ got_path_move_file(const char *oldpath, const char *ne return NULL; } + +RB_GENERATE(got_pathlist_head, got_pathlist_entry, entry, got_pathlist_cmp); blob - 4d97f68370673cd0b8596deaab214d88a71a195b blob + 2c49d4419a4c395afafe7cca1614b53619d50ed5 --- lib/privsep.c +++ lib/privsep.c @@ -17,6 +17,7 @@ #include <sys/types.h> #include <sys/queue.h> +#include <sys/tree.h> #include <sys/uio.h> #include <sys/wait.h> @@ -595,11 +596,11 @@ got_privsep_send_fetch_req(struct imsgbuf *ibuf, int f fetchreq.worktree_branch_len = worktree_branch_len; if (remote_head != NULL) fetchreq.remote_head_len = remote_head_len; - TAILQ_FOREACH(pe, have_refs, entry) + RB_FOREACH(pe, got_pathlist_head, have_refs) fetchreq.n_have_refs++; - TAILQ_FOREACH(pe, wanted_branches, entry) + RB_FOREACH(pe, got_pathlist_head, wanted_branches) fetchreq.n_wanted_branches++; - TAILQ_FOREACH(pe, wanted_refs, entry) + RB_FOREACH(pe, got_pathlist_head, wanted_refs) fetchreq.n_wanted_refs++; if (imsg_add(wbuf, &fetchreq, sizeof(fetchreq)) == -1) return got_error_from_errno("imsg_add FETCH_REQUEST"); @@ -626,7 +627,7 @@ got_privsep_send_fetch_req(struct imsgbuf *ibuf, int f if (err) return err; - TAILQ_FOREACH(pe, have_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, have_refs) { const char *name = pe->path; size_t name_len = pe->path_len; struct got_object_id *id = pe->data; @@ -650,7 +651,7 @@ got_privsep_send_fetch_req(struct imsgbuf *ibuf, int f return err; } - TAILQ_FOREACH(pe, wanted_branches, entry) { + RB_FOREACH(pe, got_pathlist_head, wanted_branches) { const char *name = pe->path; size_t name_len = pe->path_len; @@ -675,7 +676,7 @@ got_privsep_send_fetch_req(struct imsgbuf *ibuf, int f return err; } - TAILQ_FOREACH(pe, wanted_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, wanted_refs) { const char *name = pe->path; size_t name_len = pe->path_len; @@ -899,9 +900,9 @@ got_privsep_send_send_req(struct imsgbuf *ibuf, int fd memset(&zero_id, 0, sizeof(zero_id)); memset(&sendreq, 0, sizeof(sendreq)); sendreq.verbosity = verbosity; - TAILQ_FOREACH(pe, have_refs, entry) + RB_FOREACH(pe, got_pathlist_head, have_refs) sendreq.nrefs++; - TAILQ_FOREACH(pe, delete_refs, entry) + RB_FOREACH(pe, got_pathlist_head, delete_refs) sendreq.nrefs++; if (imsg_compose(ibuf, GOT_IMSG_SEND_REQUEST, 0, 0, fd, &sendreq, sizeof(sendreq)) == -1) { @@ -915,7 +916,7 @@ got_privsep_send_send_req(struct imsgbuf *ibuf, int fd if (err) goto done; - TAILQ_FOREACH(pe, have_refs, entry) { + RB_FOREACH(pe, got_pathlist_head ,have_refs) { const char *name = pe->path; size_t name_len = pe->path_len; struct got_object_id *id = pe->data; @@ -924,7 +925,7 @@ got_privsep_send_send_req(struct imsgbuf *ibuf, int fd goto done; } - TAILQ_FOREACH(pe, delete_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, delete_refs) { const char *name = pe->path; size_t name_len = pe->path_len; err = send_send_ref(name, name_len, &zero_id, 1, ibuf); blob - b79065ff8ad9f1c2ab6d0c59c7cbb5c02c6b2467 blob + 6737bf650daa76886cbc9ad90d24404103479dd7 --- lib/reference.c +++ lib/reference.c @@ -16,6 +16,7 @@ #include <sys/types.h> #include <sys/queue.h> +#include <sys/tree.h> #include <sys/stat.h> #include <errno.h> blob - f50a14103f7f51da97f88f3efea4286d891e3e65 blob + 693866bdc86723dfd79e3579b540f1364d921c2e --- lib/repository.c +++ lib/repository.c @@ -712,7 +712,7 @@ got_repo_open(struct got_repository **repop, const cha return got_error_from_errno("calloc"); RB_INIT(&repo->packidx_bloom_filters); - TAILQ_INIT(&repo->packidx_paths); + RB_INIT(&repo->packidx_paths); for (i = 0; i < nitems(repo->privsep_children); i++) { memset(&repo->privsep_children[i], 0, @@ -1303,9 +1303,9 @@ purge_packidx_paths(struct got_pathlist_head *packidx_ { struct got_pathlist_entry *pe; - while (!TAILQ_EMPTY(packidx_paths)) { - pe = TAILQ_FIRST(packidx_paths); - TAILQ_REMOVE(packidx_paths, pe, entry); + while (!RB_EMPTY(packidx_paths)) { + pe = RB_MIN(got_pathlist_head, packidx_paths); + RB_REMOVE(got_pathlist_head, packidx_paths, pe); free((char *)pe->path); free(pe); } @@ -1327,7 +1327,7 @@ refresh_packidx_paths(struct got_repository *repo) err = got_error_from_errno2("stat", objects_pack_dir); goto done; } - } else if (TAILQ_EMPTY(&repo->packidx_paths) || + } else if (RB_EMPTY(&repo->packidx_paths) || sb.st_mtim.tv_sec != repo->pack_path_mtime.tv_sec || sb.st_mtim.tv_nsec != repo->pack_path_mtime.tv_nsec) { purge_packidx_paths(&repo->packidx_paths); @@ -1382,7 +1382,7 @@ got_repo_search_packidx(struct got_packidx **packidx, if (err) return err; - TAILQ_FOREACH(pe, &repo->packidx_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &repo->packidx_paths) { const char *path_packidx = pe->path; int is_cached = 0; @@ -1833,7 +1833,7 @@ retry: tv.tv_sec = repo->pack_path_mtime.tv_sec; tv.tv_nsec = repo->pack_path_mtime.tv_nsec; - TAILQ_FOREACH(pe, &repo->packidx_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &repo->packidx_paths) { const char *path_packidx; struct got_packidx *packidx; struct got_object_qid *qid; @@ -2355,7 +2355,7 @@ write_tree(struct got_object_id **new_tree_id, const c *new_tree_id = NULL; - TAILQ_INIT(&paths); + RB_INIT(&paths); dir = opendir(path_dir); if (dir == NULL) { @@ -2376,7 +2376,7 @@ write_tree(struct got_object_id **new_tree_id, const c if (err) goto done; - TAILQ_FOREACH(pe, ignores, entry) { + RB_FOREACH(pe, got_pathlist_head, ignores) { if (type == DT_DIR && pe->path_len > 0 && pe->path[pe->path_len - 1] == '/') { char stripped[PATH_MAX]; @@ -2421,13 +2421,13 @@ write_tree(struct got_object_id **new_tree_id, const c nentries++; } - if (TAILQ_EMPTY(&paths)) { + if (RB_EMPTY(&paths)) { err = got_error_msg(GOT_ERR_NO_TREE_ENTRY, "cannot create tree without any entries"); goto done; } - TAILQ_FOREACH(pe, &paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &paths) { struct got_tree_entry *te = pe->data; char *path; if (!S_ISREG(te->mode) && !S_ISLNK(te->mode)) blob - c09e9252dd552a6939292b6dd5653ee79ef2090b blob + 6c74bdbaad86d5fa1835fd9ad75731dd69cd638b --- lib/repository_admin.c +++ lib/repository_admin.c @@ -1345,7 +1345,7 @@ repo_purge_redundant_packfiles(struct got_repository * int remove, redundant_packs = 0; npacks = 0; - TAILQ_FOREACH(pe, &repo->packidx_paths, entry) + RB_FOREACH(pe, got_pathlist_head, &repo->packidx_paths) npacks++; if (npacks == 0) @@ -1356,7 +1356,7 @@ repo_purge_redundant_packfiles(struct got_repository * return got_error_from_errno("calloc"); i = 0; - TAILQ_FOREACH(pe, &repo->packidx_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &repo->packidx_paths) { err = got_repo_get_packidx(&packidx, pe->path, repo); if (err) goto done; blob - 348d1dbb26e60918ccd5c3ea7b3106ec92916e40 blob + 22ef7b9115f249c75e351c48ef60688e463dfa39 --- lib/send.c +++ lib/send.c @@ -266,16 +266,12 @@ realloc_ids(struct got_object_id ***ids, size_t *nallo static struct got_pathlist_entry * find_ref(struct got_pathlist_head *refs, const char *refname) { - struct got_pathlist_entry *pe; + struct got_pathlist_entry find; - TAILQ_FOREACH(pe, refs, entry) { - if (got_path_cmp(pe->path, refname, strlen(pe->path), - strlen(refname)) == 0) { - return pe; - } - } + find.path = refname; + find.path_len = strlen(refname); + return RB_FIND(got_pathlist_head, refs, &find); - return NULL; } static const struct got_error * @@ -366,14 +362,14 @@ got_send_pack(const char *remote_name, struct got_path FILE *delta_cache = NULL; char *s = NULL; - TAILQ_INIT(&have_refs); - TAILQ_INIT(&their_refs); + RB_INIT(&have_refs); + RB_INIT(&their_refs); if (got_repo_get_object_format(repo) != GOT_HASH_SHA1) return got_error_fmt(GOT_ERR_NOT_IMPL, "sha256 object IDs unsupported in network protocol"); - TAILQ_FOREACH(pe, branch_names, entry) { + RB_FOREACH(pe, got_pathlist_head, branch_names) { const char *branchname = pe->path; const char *targetname = pe->data; @@ -401,7 +397,7 @@ got_send_pack(const char *remote_name, struct got_path s = NULL; } - TAILQ_FOREACH(pe, delete_branches, entry) { + RB_FOREACH(pe, got_pathlist_head, delete_branches) { const char *branchname = pe->path; struct got_pathlist_entry *ref; if (strncmp(branchname, "refs/heads/", 11) != 0) { @@ -418,7 +414,7 @@ got_send_pack(const char *remote_name, struct got_path } } - TAILQ_FOREACH(pe, tag_names, entry) { + RB_FOREACH(pe, got_pathlist_head, tag_names) { const char *tagname = pe->path; if (strncmp(tagname, "refs/tags/", 10) != 0) { if (asprintf(&s, "refs/tags/%s", tagname) == -1) { @@ -441,7 +437,7 @@ got_send_pack(const char *remote_name, struct got_path s = NULL; } - if (TAILQ_EMPTY(&have_refs) && TAILQ_EMPTY(delete_branches)) { + if (RB_EMPTY(&have_refs) && RB_EMPTY(delete_branches)) { err = got_error(GOT_ERR_SEND_EMPTY); goto done; } @@ -492,7 +488,7 @@ got_send_pack(const char *remote_name, struct got_path * Prepare the array of our object IDs which * will be needed for generating a pack file. */ - TAILQ_FOREACH(pe, &have_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, &have_refs) { struct got_object_id *id = pe->data; err = realloc_ids(&our_ids, &nalloc_ours, nours + 1); @@ -517,7 +513,7 @@ got_send_pack(const char *remote_name, struct got_path * This array will be used to exclude objects which already * exist on the server from our pack file. */ - TAILQ_FOREACH(pe, &their_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, &their_refs) { const char *refname = pe->path; struct got_object_id *their_id = pe->data; int have_their_id; @@ -611,14 +607,14 @@ got_send_pack(const char *remote_name, struct got_path } /* Account for any new references we are going to upload. */ - TAILQ_FOREACH(pe, &have_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, &have_refs) { const char *refname = pe->path; if (find_ref(&their_refs, refname) == NULL) refs_to_send++; } /* Account for any existing references we are going to delete. */ - TAILQ_FOREACH(pe, delete_branches, entry) { + RB_FOREACH(pe, got_pathlist_head, delete_branches) { const char *branchname = pe->path; if (find_ref(&their_refs, branchname)) refs_to_delete++; blob - c8fe03020a4cf36fb6886cdd20c9f5c8c14ba2fd blob + 4a2bab0b7932ec20883e152b231992ed8b75e0f4 --- lib/serve.c +++ lib/serve.c @@ -16,6 +16,7 @@ #include <sys/types.h> #include <sys/queue.h> +#include <sys/tree.h> #include <sys/uio.h> #include <errno.h> blob - 936dc8f7691a930afed9b877b099366102eecf50 blob + df89f493b283c3c8957846b5f60994c98756d8ae --- lib/worktree.c +++ lib/worktree.c @@ -2833,7 +2833,7 @@ got_worktree_checkout_files(struct got_worktree *workt goto done; /* Map all specified paths to in-repository trees. */ - TAILQ_FOREACH(pe, paths, entry) { + RB_FOREACH(pe, got_pathlist_head, paths) { tpd = malloc(sizeof(*tpd)); if (tpd == NULL) { err = got_error_from_errno("malloc"); @@ -2873,7 +2873,7 @@ got_worktree_checkout_files(struct got_worktree *workt goto done; tpd = STAILQ_FIRST(&tree_paths); - TAILQ_FOREACH(pe, paths, entry) { + RB_FOREACH(pe, got_pathlist_head, paths) { struct bump_base_commit_id_arg bbc_arg; err = checkout_files(worktree, fileindex, tpd->relpath, @@ -3715,7 +3715,7 @@ free_ignores(struct got_pathlist_head *ignores) { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, ignores, entry) { + RB_FOREACH(pe, got_pathlist_head, ignores) { struct got_pathlist_head *ignorelist = pe->data; got_pathlist_free(ignorelist, GOT_PATHLIST_FREE_PATH); @@ -3736,7 +3736,7 @@ read_ignores(struct got_pathlist_head *ignores, const ignorelist = calloc(1, sizeof(*ignorelist)); if (ignorelist == NULL) return got_error_from_errno("calloc"); - TAILQ_INIT(ignorelist); + RB_INIT(ignorelist); while ((linelen = getline(&line, &linesize, f)) != -1) { if (linelen > 0 && line[linelen - 1] == '\n') @@ -3810,11 +3810,11 @@ match_ignores(struct got_pathlist_head *ignores, const struct got_pathlist_entry *pe; /* Handle patterns which match in all directories. */ - TAILQ_FOREACH(pe, ignores, entry) { + RB_FOREACH(pe, got_pathlist_head, ignores) { struct got_pathlist_head *ignorelist = pe->data; struct got_pathlist_entry *pi; - TAILQ_FOREACH(pi, ignorelist, entry) { + RB_FOREACH(pi, got_pathlist_head, ignorelist) { const char *p; if (pi->path_len < 3 || @@ -3842,12 +3842,12 @@ match_ignores(struct got_pathlist_head *ignores, const * parents, so we can find the most specific ignorelist by walking * ignores backwards. */ - pe = TAILQ_LAST(ignores, got_pathlist_head); + pe = RB_MAX(got_pathlist_head, ignores); while (pe) { if (got_path_is_child(path, pe->path, pe->path_len)) { struct got_pathlist_head *ignorelist = pe->data; struct got_pathlist_entry *pi; - TAILQ_FOREACH(pi, ignorelist, entry) { + RB_FOREACH(pi, got_pathlist_head, ignorelist) { int flags = FNM_LEADING_DIR; if (strstr(pi->path, "/**/") == NULL) flags |= FNM_PATHNAME; @@ -3857,7 +3857,7 @@ match_ignores(struct got_pathlist_head *ignores, const return 1; } } - pe = TAILQ_PREV(pe, got_pathlist_head, entry); + pe = RB_PREV(got_pathlist_head, ignores, pe); } return 0; @@ -4087,7 +4087,7 @@ report_children(struct got_pathlist_head *children, struct got_pathlist_entry *pe; char *ondisk_path = NULL; - TAILQ_FOREACH(pe, children, entry) { + RB_FOREACH(pe, got_pathlist_head, children) { if (cancel_cb) { err = cancel_cb(cancel_arg); if (err) @@ -4130,8 +4130,8 @@ worktree_status(struct got_worktree *worktree, const c struct got_pathlist_head ignores, missing_children; struct got_fileindex_entry *ie; - TAILQ_INIT(&ignores); - TAILQ_INIT(&missing_children); + RB_INIT(&ignores); + RB_INIT(&missing_children); if (asprintf(&ondisk_path, "%s%s%s", worktree->root_path, path[0] ? "/" : "", path) == -1) @@ -4168,7 +4168,7 @@ worktree_status(struct got_worktree *worktree, const c if (err) goto done; } - if (TAILQ_EMPTY(&missing_children)) { + if (RB_EMPTY(&missing_children)) { err = report_single_file_status(path, ondisk_path, fileindex, status_cb, status_arg, repo, @@ -4237,7 +4237,7 @@ got_worktree_status(struct got_worktree *worktree, if (err) return err; - TAILQ_FOREACH(pe, paths, entry) { + RB_FOREACH(pe, got_pathlist_head, paths) { err = worktree_status(worktree, pe->path, fileindex, repo, status_cb, status_arg, cancel_cb, cancel_arg, no_ignores, 0); @@ -4462,7 +4462,7 @@ got_worktree_schedule_add(struct got_worktree *worktre saa.progress_arg = progress_arg; saa.repo = repo; - TAILQ_FOREACH(pe, paths, entry) { + RB_FOREACH(pe, got_pathlist_head, paths) { err = worktree_status(worktree, pe->path, fileindex, repo, schedule_addition, &saa, NULL, NULL, no_ignores, 0); if (err) @@ -4657,7 +4657,7 @@ got_worktree_schedule_delete(struct got_worktree *work sda.ignore_missing_paths = ignore_missing_paths; sda.status_codes = status_codes; - TAILQ_FOREACH(pe, paths, entry) { + RB_FOREACH(pe, got_pathlist_head, paths) { char *ondisk_status_path; if (asprintf(&ondisk_status_path, "%s%s%s", @@ -5254,8 +5254,8 @@ revert_file(void *arg, unsigned char status, unsigned if (a->added_files_to_unlink) { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, a->added_files_to_unlink, - entry) { + RB_FOREACH(pe, got_pathlist_head, + a->added_files_to_unlink) { if (got_path_cmp(pe->path, relpath, pe->path_len, strlen(relpath))) continue; @@ -5438,7 +5438,7 @@ got_worktree_revert(struct got_worktree *worktree, rfa.patch_arg = patch_arg; rfa.repo = repo; rfa.unlink_added_files = 0; - TAILQ_FOREACH(pe, paths, entry) { + RB_FOREACH(pe, got_pathlist_head, paths) { err = worktree_status(worktree, pe->path, fileindex, repo, revert_file, &rfa, NULL, NULL, 1, 0); if (err) @@ -6042,7 +6042,7 @@ match_modified_subtree(int *modified, struct got_tree_ te->name) == -1) return got_error_from_errno("asprintf"); - TAILQ_FOREACH(pe, commitable_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, commitable_paths) { struct got_commitable *ct = pe->data; *modified = got_path_is_child(ct->in_repo_path, te_path, strlen(te_path)); @@ -6064,7 +6064,7 @@ match_deleted_or_modified_ct(struct got_commitable **c *ctp = NULL; - TAILQ_FOREACH(pe, commitable_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, commitable_paths) { struct got_commitable *ct = pe->data; char *ct_name = NULL; int path_matches; @@ -6164,11 +6164,11 @@ write_tree(struct got_object_id **new_tree_id, int *ne struct got_tree_entry *te, *new_te = NULL; struct got_pathlist_entry *pe; - TAILQ_INIT(&paths); + RB_INIT(&paths); *nentries = 0; /* Insert, and recurse into, newly added entries first. */ - TAILQ_FOREACH(pe, commitable_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, commitable_paths) { struct got_commitable *ct = pe->data; char *child_path = NULL, *slash; @@ -6326,7 +6326,7 @@ update_fileindex_after_commit(struct got_worktree *wor struct got_pathlist_entry *pe; char *relpath = NULL; - TAILQ_FOREACH(pe, commitable_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, commitable_paths) { struct got_fileindex_entry *ie; struct got_commitable *ct = pe->data; @@ -6478,7 +6478,7 @@ commit_worktree(struct got_object_id **new_commit_id, } /* Create blobs from added and modified files and record their IDs. */ - TAILQ_FOREACH(pe, commitable_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, commitable_paths) { struct got_commitable *ct = pe->data; char *ondisk_path; @@ -6585,7 +6585,7 @@ check_path_is_commitable(const char *path, struct got_pathlist_entry *cpe = NULL; size_t path_len = strlen(path); - TAILQ_FOREACH(cpe, commitable_paths, entry) { + RB_FOREACH(cpe, got_pathlist_head, commitable_paths) { struct got_commitable *ct = cpe->data; const char *ct_path = ct->path; @@ -6623,7 +6623,7 @@ check_non_staged_files(struct got_fileindex *fileindex struct got_pathlist_entry *pe; struct got_fileindex_entry *ie; - TAILQ_FOREACH(pe, paths, entry) { + RB_FOREACH(pe, got_pathlist_head, paths) { if (pe->path[0] == '\0') continue; ie = got_fileindex_entry_get(fileindex, pe->path, pe->path_len); @@ -6660,7 +6660,7 @@ got_worktree_commit(struct got_object_id **new_commit_ *new_commit_id = NULL; memset(&cc_arg, 0, sizeof(cc_arg)); - TAILQ_INIT(&commitable_paths); + RB_INIT(&commitable_paths); err = lock_worktree(worktree, LOCK_EX); if (err) @@ -6714,7 +6714,7 @@ got_worktree_commit(struct got_object_id **new_commit_ } } - TAILQ_FOREACH(pe, paths, entry) { + RB_FOREACH(pe, got_pathlist_head, paths) { err = worktree_status(worktree, pe->path, fileindex, repo, collect_commitables, &cc_arg, NULL, NULL, 0, 0); if (err) @@ -6728,18 +6728,18 @@ got_worktree_commit(struct got_object_id **new_commit_ } } - if (TAILQ_EMPTY(&commitable_paths)) { + if (RB_EMPTY(&commitable_paths)) { err = got_error(GOT_ERR_COMMIT_NO_CHANGES); goto done; } - TAILQ_FOREACH(pe, paths, entry) { + RB_FOREACH(pe, got_pathlist_head, paths) { err = check_path_is_commitable(pe->path, &commitable_paths); if (err) goto done; } - TAILQ_FOREACH(pe, &commitable_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &commitable_paths) { struct got_commitable *ct = pe->data; const char *ct_path = ct->in_repo_path; @@ -6772,7 +6772,7 @@ done: unlockerr = lock_worktree(worktree, LOCK_SH); if (unlockerr && err == NULL) err = unlockerr; - TAILQ_FOREACH(pe, &commitable_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &commitable_paths) { struct got_commitable *ct = pe->data; free_commitable(ct); @@ -7329,7 +7329,7 @@ rebase_commit(struct got_object_id **new_commit_id, char *logmsg = NULL; memset(&cc_arg, 0, sizeof(cc_arg)); - TAILQ_INIT(&commitable_paths); + RB_INIT(&commitable_paths); *new_commit_id = NULL; /* Work tree is locked/unlocked during rebase preparation/teardown. */ @@ -7356,7 +7356,7 @@ rebase_commit(struct got_object_id **new_commit_id, */ if (merged_paths) { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, merged_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, merged_paths) { err = worktree_status(worktree, pe->path, fileindex, repo, collect_commitables, &cc_arg, NULL, NULL, 1, 0); @@ -7370,7 +7370,7 @@ rebase_commit(struct got_object_id **new_commit_id, goto done; } - if (TAILQ_EMPTY(&commitable_paths)) { + if (RB_EMPTY(&commitable_paths)) { /* No-op change; commit will be elided. */ err = got_ref_delete(commit_ref, repo); if (err) @@ -7727,13 +7727,13 @@ get_paths_added_between_commits(struct got_pathlist_he struct got_pathlist_entry *pe; char *abspath = NULL, *wt_path = NULL; - TAILQ_INIT(&merged_paths); + RB_INIT(&merged_paths); err = get_paths_changed_between_commits(&merged_paths, id1, id2, repo); if (err) goto done; - TAILQ_FOREACH(pe, &merged_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &merged_paths) { struct got_diff_changed_path *change = pe->data; if (change->status != GOT_STATUS_ADD) @@ -7815,7 +7815,7 @@ got_worktree_rebase_abort(struct got_worktree *worktre struct got_object_id *tree_id = NULL; struct got_pathlist_head added_paths; - TAILQ_INIT(&added_paths); + RB_INIT(&added_paths); err = lock_worktree(worktree, LOCK_EX); if (err) @@ -8269,7 +8269,7 @@ got_worktree_histedit_abort(struct got_worktree *workt struct revert_file_args rfa; struct got_pathlist_head added_paths; - TAILQ_INIT(&added_paths); + RB_INIT(&added_paths); err = lock_worktree(worktree, LOCK_EX); if (err) @@ -8733,7 +8733,7 @@ got_worktree_merge_commit(struct got_object_id **new_c memset(&cc_arg, 0, sizeof(cc_arg)); *new_commit_id = NULL; - TAILQ_INIT(&commitable_paths); + RB_INIT(&commitable_paths); err = get_fileindex_path(&fileindex_path, worktree); if (err) @@ -8782,7 +8782,7 @@ got_worktree_merge_commit(struct got_object_id **new_c if (sync_err && err == NULL) err = sync_err; done: - TAILQ_FOREACH(pe, &commitable_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &commitable_paths) { struct got_commitable *ct = pe->data; free_commitable(ct); @@ -9093,7 +9093,7 @@ got_worktree_merge_abort(struct got_worktree *worktree struct got_object_id *tree_id = NULL; struct got_pathlist_head added_paths; - TAILQ_INIT(&added_paths); + RB_INIT(&added_paths); err = get_merge_commit_ref_name(&commit_ref_name, worktree); if (err) @@ -9453,7 +9453,7 @@ got_worktree_stage(struct got_worktree *worktree, oka.fileindex = fileindex; oka.repo = repo; oka.have_changes = 0; - TAILQ_FOREACH(pe, paths, entry) { + RB_FOREACH(pe, got_pathlist_head, paths) { err = worktree_status(worktree, pe->path, fileindex, repo, check_stage_ok, &oka, NULL, NULL, 1, 0); if (err) @@ -9473,7 +9473,7 @@ got_worktree_stage(struct got_worktree *worktree, spa.status_arg = status_arg; spa.staged_something = 0; spa.allow_bad_symlinks = allow_bad_symlinks; - TAILQ_FOREACH(pe, paths, entry) { + RB_FOREACH(pe, got_pathlist_head, paths) { err = worktree_status(worktree, pe->path, fileindex, repo, stage_path, &spa, NULL, NULL, 1, 0); if (err) @@ -10020,7 +10020,7 @@ got_worktree_unstage(struct got_worktree *worktree, upa.progress_arg = progress_arg; upa.patch_cb = patch_cb; upa.patch_arg = patch_arg; - TAILQ_FOREACH(pe, paths, entry) { + RB_FOREACH(pe, got_pathlist_head, paths) { err = worktree_status(worktree, pe->path, fileindex, repo, unstage_path, &upa, NULL, NULL, 1, 0); if (err) @@ -10066,7 +10066,7 @@ report_file_info(void *arg, struct got_fileindex_entry return err; } - TAILQ_FOREACH(pe, a->paths, entry) { + RB_FOREACH(pe, got_pathlist_head, a->paths) { if (pe->path_len == 0 || strcmp(pe->path, ie->path) == 0 || got_path_is_child(ie->path, pe->path, pe->path_len)) break; blob - b9abd5bf360259fba46644942a97cd1cc76f4b9f blob + 4518253bb1454bef6d43a7a09d1bdc0b73168086 --- lib/worktree_cvg.c +++ lib/worktree_cvg.c @@ -754,7 +754,7 @@ free_ignores(struct got_pathlist_head *ignores) { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, ignores, entry) { + RB_FOREACH(pe, got_pathlist_head, ignores) { struct got_pathlist_head *ignorelist = pe->data; got_pathlist_free(ignorelist, GOT_PATHLIST_FREE_PATH); @@ -775,7 +775,7 @@ read_ignores(struct got_pathlist_head *ignores, const ignorelist = calloc(1, sizeof(*ignorelist)); if (ignorelist == NULL) return got_error_from_errno("calloc"); - TAILQ_INIT(ignorelist); + RB_INIT(ignorelist); while ((linelen = getline(&line, &linesize, f)) != -1) { if (linelen > 0 && line[linelen - 1] == '\n') @@ -844,11 +844,11 @@ match_ignores(struct got_pathlist_head *ignores, const struct got_pathlist_entry *pe; /* Handle patterns which match in all directories. */ - TAILQ_FOREACH(pe, ignores, entry) { + RB_FOREACH(pe, got_pathlist_head, ignores) { struct got_pathlist_head *ignorelist = pe->data; struct got_pathlist_entry *pi; - TAILQ_FOREACH(pi, ignorelist, entry) { + RB_FOREACH(pi, got_pathlist_head, ignorelist) { const char *p; if (pi->path_len < 3 || @@ -876,12 +876,12 @@ match_ignores(struct got_pathlist_head *ignores, const * parents, so we can find the most specific ignorelist by walking * ignores backwards. */ - pe = TAILQ_LAST(ignores, got_pathlist_head); + pe = RB_MAX(got_pathlist_head, ignores); while (pe) { if (got_path_is_child(path, pe->path, pe->path_len)) { struct got_pathlist_head *ignorelist = pe->data; struct got_pathlist_entry *pi; - TAILQ_FOREACH(pi, ignorelist, entry) { + RB_FOREACH(pi, got_pathlist_head, ignorelist) { int flags = FNM_LEADING_DIR; if (strstr(pi->path, "/**/") == NULL) flags |= FNM_PATHNAME; @@ -891,7 +891,7 @@ match_ignores(struct got_pathlist_head *ignores, const return 1; } } - pe = TAILQ_PREV(pe, got_pathlist_head, entry); + pe = RB_PREV(got_pathlist_head, ignores, pe); } return 0; @@ -1121,7 +1121,7 @@ report_children(struct got_pathlist_head *children, struct got_pathlist_entry *pe; char *ondisk_path = NULL; - TAILQ_FOREACH(pe, children, entry) { + RB_FOREACH(pe, got_pathlist_head, children) { if (cancel_cb) { err = cancel_cb(cancel_arg); if (err) @@ -1164,8 +1164,8 @@ worktree_status(struct got_worktree *worktree, const c struct got_pathlist_head ignores, missing_children; struct got_fileindex_entry *ie; - TAILQ_INIT(&ignores); - TAILQ_INIT(&missing_children); + RB_INIT(&ignores); + RB_INIT(&missing_children); if (asprintf(&ondisk_path, "%s%s%s", worktree->root_path, path[0] ? "/" : "", path) == -1) @@ -1202,7 +1202,7 @@ worktree_status(struct got_worktree *worktree, const c if (err) goto done; } - if (TAILQ_EMPTY(&missing_children)) { + if (RB_EMPTY(&missing_children)) { err = report_single_file_status(path, ondisk_path, fileindex, status_cb, status_arg, repo, @@ -1838,7 +1838,7 @@ match_modified_subtree(int *modified, struct got_tree_ te->name) == -1) return got_error_from_errno("asprintf"); - TAILQ_FOREACH(pe, commitable_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, commitable_paths) { struct got_commitable *ct = pe->data; *modified = got_path_is_child(ct->in_repo_path, te_path, strlen(te_path)); @@ -1860,7 +1860,7 @@ match_deleted_or_modified_ct(struct got_commitable **c *ctp = NULL; - TAILQ_FOREACH(pe, commitable_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, commitable_paths) { struct got_commitable *ct = pe->data; char *ct_name = NULL; int path_matches; @@ -1960,11 +1960,11 @@ write_tree(struct got_object_id **new_tree_id, int *ne struct got_tree_entry *te, *new_te = NULL; struct got_pathlist_entry *pe; - TAILQ_INIT(&paths); + RB_INIT(&paths); *nentries = 0; /* Insert, and recurse into, newly added entries first. */ - TAILQ_FOREACH(pe, commitable_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, commitable_paths) { struct got_commitable *ct = pe->data; char *child_path = NULL, *slash; @@ -2122,7 +2122,7 @@ update_fileindex_after_commit(struct got_worktree *wor struct got_pathlist_entry *pe; char *relpath = NULL; - TAILQ_FOREACH(pe, commitable_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, commitable_paths) { struct got_fileindex_entry *ie; struct got_commitable *ct = pe->data; @@ -2270,7 +2270,7 @@ commit_worktree(struct got_object_id **new_commit_id, } /* Create blobs from added and modified files and record their IDs. */ - TAILQ_FOREACH(pe, commitable_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, commitable_paths) { struct got_commitable *ct = pe->data; char *ondisk_path; @@ -2337,7 +2337,7 @@ check_path_is_commitable(const char *path, struct got_pathlist_entry *cpe = NULL; size_t path_len = strlen(path); - TAILQ_FOREACH(cpe, commitable_paths, entry) { + RB_FOREACH(cpe, got_pathlist_head, commitable_paths) { struct got_commitable *ct = cpe->data; const char *ct_path = ct->path; @@ -2375,7 +2375,7 @@ check_non_staged_files(struct got_fileindex *fileindex struct got_pathlist_entry *pe; struct got_fileindex_entry *ie; - TAILQ_FOREACH(pe, paths, entry) { + RB_FOREACH(pe, got_pathlist_head, paths) { if (pe->path[0] == '\0') continue; ie = got_fileindex_entry_get(fileindex, pe->path, pe->path_len); @@ -2447,7 +2447,7 @@ send_progress(void *arg, int ncolored, int nfound, int if (success) { struct got_pathlist_entry *pe; - TAILQ_FOREACH(pe, a->delete_branches, entry) { + RB_FOREACH(pe, got_pathlist_head, a->delete_branches) { const char *branchname = pe->path; if (got_path_cmp(branchname, refname, strlen(branchname), strlen(refname)) == 0) { @@ -2779,10 +2779,10 @@ fetch_updated_remote(const char *proto, const char *ho int fetchfd = -1; pid_t fetchpid = -1; - TAILQ_INIT(&learned_refs); - TAILQ_INIT(&symrefs); - TAILQ_INIT(&wanted_branches); - TAILQ_INIT(&wanted_refs); + RB_INIT(&learned_refs); + RB_INIT(&symrefs); + RB_INIT(&wanted_branches); + RB_INIT(&wanted_refs); err = got_pathlist_insert(NULL, &wanted_branches, head_refname, NULL); @@ -2807,7 +2807,7 @@ fetch_updated_remote(const char *proto, const char *ho goto done; /* Update references provided with the pack file. */ - TAILQ_FOREACH(pe, &learned_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, &learned_refs) { const char *refname = pe->path; struct got_object_id *id = pe->data; struct got_reference *ref; @@ -2831,7 +2831,7 @@ fetch_updated_remote(const char *proto, const char *ho } /* Set the HEAD reference if the server provided one. */ - TAILQ_FOREACH(pe, &symrefs, entry) { + RB_FOREACH(pe, got_pathlist_head, &symrefs) { struct got_reference *target_ref; const char *refname = pe->path; const char *target = pe->data; @@ -2938,10 +2938,10 @@ got_worktree_cvg_commit(struct got_object_id **new_com *new_commit_id = NULL; memset(&cc_arg, 0, sizeof(cc_arg)); - TAILQ_INIT(&commitable_paths); - TAILQ_INIT(&commit_reflist); - TAILQ_INIT(&tag_names); - TAILQ_INIT(&delete_branches); + RB_INIT(&commitable_paths); + RB_INIT(&commit_reflist); + RB_INIT(&tag_names); + RB_INIT(&delete_branches); err = lock_worktree(worktree, LOCK_EX); if (err) @@ -3007,7 +3007,7 @@ got_worktree_cvg_commit(struct got_object_id **new_com } } - TAILQ_FOREACH(pe, paths, entry) { + RB_FOREACH(pe, got_pathlist_head, paths) { err = worktree_status(worktree, pe->path, fileindex, repo, collect_commitables, &cc_arg, NULL, NULL, 0, 0); if (err) @@ -3021,18 +3021,18 @@ got_worktree_cvg_commit(struct got_object_id **new_com } } - if (TAILQ_EMPTY(&commitable_paths)) { + if (RB_EMPTY(&commitable_paths)) { err = got_error(GOT_ERR_COMMIT_NO_CHANGES); goto done; } - TAILQ_FOREACH(pe, paths, entry) { + RB_FOREACH(pe, got_pathlist_head, paths) { err = check_path_is_commitable(pe->path, &commitable_paths); if (err) goto done; } - TAILQ_FOREACH(pe, &commitable_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &commitable_paths) { struct got_commitable *ct = pe->data; const char *ct_path = ct->in_repo_path; @@ -3157,7 +3157,7 @@ done: unlockerr = lock_worktree(worktree, LOCK_SH); if (unlockerr && err == NULL) err = unlockerr; - TAILQ_FOREACH(pe, &commitable_paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &commitable_paths) { struct got_commitable *ct = pe->data; free_commitable(ct); blob - 1855ba0c1a557ce16cfae9790d6cff44a4b71846 blob + 6ae0f96f5546d6f7eaac0b1b2d32dd6249c51d52 --- lib/worktree_open.c +++ lib/worktree_open.c @@ -16,6 +16,7 @@ #include <sys/stat.h> #include <sys/queue.h> +#include <sys/tree.h> #include <errno.h> #include <fcntl.h> blob - 235f88168eaa1209540cb280c17e4f55629259a4 blob + 6f0e0e861b6c26170d813b19ca2271295f30eb22 --- libexec/got-fetch-http/got-fetch-http.c +++ libexec/got-fetch-http/got-fetch-http.c @@ -17,6 +17,7 @@ #include <sys/types.h> #include <sys/queue.h> +#include <sys/tree.h> #include <sys/socket.h> #include <err.h> blob - 167dff0291b3356987b3f2dbe74509ad4a608813 blob + 941d899ffe34503cf9f82ba20f3e587581c384df --- libexec/got-fetch-pack/got-fetch-pack.c +++ libexec/got-fetch-pack/got-fetch-pack.c @@ -16,6 +16,7 @@ #include <sys/types.h> #include <sys/queue.h> +#include <sys/tree.h> #include <sys/uio.h> #include <sys/time.h> #include <sys/stat.h> @@ -82,7 +83,7 @@ match_remote_ref(struct got_pathlist_head *have_refs, * we should use a flag instead */ memset(my_id, 0, sizeof(*my_id)); - TAILQ_FOREACH(pe, have_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, have_refs) { struct got_object_id *id = pe->data; if (strcmp(pe->path, refname) == 0) { memcpy(my_id, id, sizeof(*my_id)); @@ -228,7 +229,7 @@ send_fetch_symrefs(struct imsgbuf *ibuf, struct got_pa struct got_pathlist_entry *pe; len = sizeof(struct got_imsg_fetch_symrefs); - TAILQ_FOREACH(pe, symrefs, entry) { + RB_FOREACH(pe, got_pathlist_head, symrefs) { const char *target = pe->data; len += sizeof(struct got_imsg_fetch_symref) + pe->path_len + strlen(target); @@ -246,7 +247,7 @@ send_fetch_symrefs(struct imsgbuf *ibuf, struct got_pa if (imsg_add(wbuf, &nsymrefs, sizeof(nsymrefs)) == -1) return got_error_from_errno("imsg_add FETCH_SYMREFS"); - TAILQ_FOREACH(pe, symrefs, entry) { + RB_FOREACH(pe, got_pathlist_head, symrefs) { const char *name = pe->path; size_t name_len = pe->path_len; const char *target = pe->data; @@ -357,7 +358,7 @@ fetch_pack(int fd, int packfd, uint8_t *pack_sha1, ssize_t w; struct got_ratelimit rl; - TAILQ_INIT(&symrefs); + RB_INIT(&symrefs); got_hash_init(&ctx, GOT_HASH_SHA1); got_ratelimit_init(&rl, 0, 500); @@ -423,7 +424,7 @@ fetch_pack(int fd, int packfd, uint8_t *pack_sha1, goto done; is_firstpkt = 0; if (!fetch_all_branches) { - TAILQ_FOREACH(pe, &symrefs, entry) { + RB_FOREACH(pe, got_pathlist_head, &symrefs) { const char *name = pe->path; const char *symref_target = pe->data; if (strcmp(name, GOT_REF_HEAD) != 0) @@ -467,7 +468,7 @@ fetch_pack(int fd, int packfd, uint8_t *pack_sha1, found_branch = 1; continue; } - TAILQ_FOREACH(pe, wanted_branches, entry) { + RB_FOREACH(pe, got_pathlist_head, wanted_branches) { if (match_branch(refname, pe->path)) break; } @@ -484,7 +485,7 @@ fetch_pack(int fd, int packfd, uint8_t *pack_sha1, getprogname(), refname); } } else { - TAILQ_FOREACH(pe, wanted_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, wanted_refs) { if (match_wanted_ref(refname, pe->path)) break; } @@ -532,7 +533,7 @@ fetch_pack(int fd, int packfd, uint8_t *pack_sha1, struct got_pathlist_entry *pe; static char msg[PATH_MAX + 33]; - pe = TAILQ_FIRST(wanted_branches); + pe = RB_MIN(got_pathlist_head, wanted_branches); if (pe) { snprintf(msg, sizeof(msg), "branch \"%s\" not found on server", pe->path); @@ -540,7 +541,7 @@ fetch_pack(int fd, int packfd, uint8_t *pack_sha1, goto done; } - pe = TAILQ_FIRST(wanted_refs); + pe = RB_MIN(got_pathlist_head, wanted_refs); if (pe) { snprintf(msg, sizeof(msg), "reference \"%s\" not found on server", pe->path); @@ -576,7 +577,7 @@ fetch_pack(int fd, int packfd, uint8_t *pack_sha1, if (nwant == 0) goto done; - TAILQ_FOREACH(pe, have_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, have_refs) { struct got_object_id *id = pe->data; got_object_id_hex(id, hashstr, sizeof(hashstr)); n = snprintf(buf, sizeof(buf), "have %s\n", hashstr); @@ -873,9 +874,9 @@ main(int argc, char **argv) sleep (1); #endif - TAILQ_INIT(&have_refs); - TAILQ_INIT(&wanted_branches); - TAILQ_INIT(&wanted_refs); + RB_INIT(&have_refs); + RB_INIT(&wanted_branches); + RB_INIT(&wanted_refs); if (imsgbuf_init(&ibuf, GOT_IMSG_FD_CHILD) == -1) { warn("imsgbuf_init"); blob - e7b041c41a36e5ab990a86d621f4e250a2599450 blob + 30b538316b641b0ebb47883992192f2d69452e31 --- libexec/got-index-pack/got-index-pack.c +++ libexec/got-index-pack/got-index-pack.c @@ -17,6 +17,7 @@ #include <sys/types.h> #include <sys/queue.h> +#include <sys/tree.h> #include <sys/mman.h> #include <sys/uio.h> blob - d822239702f0cb31d5d90a0204548fe0fa3b2568 blob + 6c4d37a796af1d8465d17690350100aa7f5a13ca --- libexec/got-read-gotconfig/got-read-gotconfig.c +++ libexec/got-read-gotconfig/got-read-gotconfig.c @@ -16,6 +16,7 @@ #include <sys/types.h> #include <sys/queue.h> +#include <sys/tree.h> #include <sys/uio.h> #include <sys/time.h> blob - 3193a744382b165f03043d74461855f87708c68a blob + 8b6314b53f27f1bb8782f89d99e0ce70f29e4d60 --- libexec/got-read-pack/got-read-pack.c +++ libexec/got-read-pack/got-read-pack.c @@ -17,6 +17,7 @@ #include <sys/stat.h> #include <sys/types.h> #include <sys/queue.h> +#include <sys/tree.h> #include <sys/uio.h> #include <sys/time.h> #include <sys/mman.h> blob - ebf6949188e7f189d1ca4bf3eb6652f668d4f96c blob + 417db9c87500ce3e9b5dcc9a6784d94fa465f657 --- libexec/got-read-tree/got-read-tree.c +++ libexec/got-read-tree/got-read-tree.c @@ -16,6 +16,7 @@ #include <sys/types.h> #include <sys/queue.h> +#include <sys/tree.h> #include <sys/uio.h> #include <sys/time.h> blob - a7c50b87c17ac2535d33e80601a9f5b054441d8f blob + 1f5f72593dca228e5752bbe2703e47723bda37c2 --- libexec/got-send-pack/got-send-pack.c +++ libexec/got-send-pack/got-send-pack.c @@ -17,6 +17,7 @@ #include <sys/types.h> #include <sys/queue.h> +#include <sys/tree.h> #include <sys/uio.h> #include <sys/time.h> #include <sys/stat.h> @@ -259,14 +260,14 @@ send_ref_status(struct imsgbuf *ibuf, const char *refn "unexpected message from server"); } - TAILQ_FOREACH(pe, refs, entry) { + RB_FOREACH(pe, got_pathlist_head, refs) { if (strcmp(refname, pe->path) == 0) { ref_valid = 1; break; } } if (!ref_valid) { - TAILQ_FOREACH(pe, delete_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, delete_refs) { if (strcmp(refname, pe->path) == 0) { ref_valid = 1; break; @@ -358,9 +359,9 @@ send_pack(int fd, struct got_pathlist_head *refs, struct got_pathlist_entry *pe; int sent_my_capabilites = 0; - TAILQ_INIT(&their_refs); + RB_INIT(&their_refs); - if (TAILQ_EMPTY(refs) && TAILQ_EMPTY(delete_refs)) + if (RB_EMPTY(refs) && RB_EMPTY(delete_refs)) return got_error(GOT_ERR_SEND_EMPTY); while (1) { @@ -441,7 +442,7 @@ send_pack(int fd, struct got_pathlist_head *refs, id = NULL; /* do not free; owned by their_refs */ } - if (!TAILQ_EMPTY(delete_refs)) { + if (!RB_EMPTY(delete_refs)) { if (my_capabilities == NULL || strstr(my_capabilities, GOT_CAPA_DELETE_REFS) == NULL) { err = got_error(GOT_ERR_CAPA_DELETE_REFS); @@ -449,12 +450,12 @@ send_pack(int fd, struct got_pathlist_head *refs, } } - TAILQ_FOREACH(pe, delete_refs, entry) { + RB_FOREACH(pe, got_pathlist_head, delete_refs) { const char *refname = pe->path; struct got_pathlist_entry *their_pe; struct got_object_id *their_id = NULL; - TAILQ_FOREACH(their_pe, &their_refs, entry) { + RB_FOREACH(their_pe, got_pathlist_head, &their_refs) { const char *their_refname = their_pe->path; if (got_path_cmp(refname, their_refname, strlen(refname), strlen(their_refname)) == 0) { @@ -488,13 +489,13 @@ send_pack(int fd, struct got_pathlist_head *refs, nsent++; } - TAILQ_FOREACH(pe, refs, entry) { + RB_FOREACH(pe, got_pathlist_head, refs) { const char *refname = pe->path; struct got_object_id *id = pe->data; struct got_object_id *their_id = NULL; struct got_pathlist_entry *their_pe; - TAILQ_FOREACH(their_pe, &their_refs, entry) { + RB_FOREACH(their_pe, got_pathlist_head, &their_refs) { const char *their_refname = their_pe->path; if (got_path_cmp(refname, their_refname, strlen(refname), strlen(their_refname)) == 0) { @@ -626,8 +627,8 @@ main(int argc, char **argv) sleep (1); #endif - TAILQ_INIT(&refs); - TAILQ_INIT(&delete_refs); + RB_INIT(&refs); + RB_INIT(&delete_refs); if (imsgbuf_init(&ibuf, GOT_IMSG_FD_CHILD) == -1) { warn("imsgbuf_init"); blob - 377ea9cd19e22c07f1348e7110a49defd8cb974d blob + b0b1593dc092b51883cce8fc1caf672b00d56560 --- regress/delta/delta_test.c +++ regress/delta/delta_test.c @@ -15,6 +15,7 @@ */ #include <sys/queue.h> +#include <sys/tree.h> #include <stdio.h> #include <stdlib.h> blob - c024c69ae8a0fd18330ae5c8f6dc6b872026966e blob + e3b7eda734c43ae229647e428258d944538ab041 --- regress/fetch/fetch_test.c +++ regress/fetch/fetch_test.c @@ -15,6 +15,7 @@ */ #include <sys/queue.h> +#include <sys/tree.h> #include <limits.h> #include <stdarg.h> blob - fad15574f54715f8f62105579fbc58c1ca5d1bf1 blob + c4da368ef9fe5fb3b4c6ff3a0879637e0a4a2611 --- regress/path/path_test.c +++ regress/path/path_test.c @@ -15,6 +15,7 @@ */ #include <sys/queue.h> +#include <sys/tree.h> #include <string.h> #include <stdlib.h> @@ -141,7 +142,7 @@ path_list(void) struct got_pathlist_entry *pe; size_t i; - TAILQ_INIT(&paths); + RB_INIT(&paths); for (i = 0; i < nitems(path_list_input); i++) { err = got_pathlist_insert(NULL, &paths, path_list_input[i], NULL); @@ -152,7 +153,7 @@ path_list(void) } i = 0; - TAILQ_FOREACH(pe, &paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &paths) { test_printf("'%s' -- '%s'\n", pe->path, path_list_expected[i]); if (i >= nitems(path_list_expected)) { test_printf("too many elements on list\n"); @@ -177,7 +178,7 @@ path_list_reverse_input(void) struct got_pathlist_entry *pe; size_t i; - TAILQ_INIT(&paths); + RB_INIT(&paths); for (i = nitems(path_list_input); i > 0;) { err = got_pathlist_insert(NULL, &paths, path_list_input[--i], NULL); @@ -188,7 +189,7 @@ path_list_reverse_input(void) } i = 0; - TAILQ_FOREACH(pe, &paths, entry) { + RB_FOREACH(pe, got_pathlist_head, &paths) { test_printf("'%s' -- '%s'\n", pe->path, path_list_expected_reverse[i]); if (i >= nitems(path_list_expected_reverse)) { blob - a09591e35e09e13fb23f7c13166a95b75ab02ffc blob + e5b6a27289781714067597b57322e12510368ce6 --- tog/tog.c +++ tog/tog.c @@ -15,6 +15,7 @@ */ #include <sys/queue.h> +#include <sys/tree.h> #include <sys/stat.h> #include <sys/ioctl.h> @@ -3175,7 +3176,7 @@ tog_worktree_status(struct tog_log_thread_args *ta) char *cwd = NULL; int wt_state = 0; - TAILQ_INIT(&paths); + RB_INIT(&paths); if (wt == NULL) { cwd = getcwd(NULL, 0); @@ -5822,7 +5823,7 @@ write_diffstat(FILE *outfile, struct got_diff_line **l } else offset = (*lines)[*nlines - 1].offset; - TAILQ_FOREACH(pe, dsa->paths, entry) { + RB_FOREACH(pe, got_pathlist_head, dsa->paths) { struct got_diff_changed_path *cp = pe->data; int pad = dsa->max_path_len - pe->path_len + 1; @@ -6330,7 +6331,7 @@ tog_diff_worktree(struct tog_diff_view_state *s, FILE struct got_pathlist_head pathlist; char *cwd, *id_str = NULL; - TAILQ_INIT(&pathlist); + RB_INIT(&pathlist); cwd = getcwd(NULL, 0); if (cwd == NULL) @@ -6518,7 +6519,7 @@ create_diff(struct tog_diff_view_state *s) struct got_diffstat_cb_arg dsa; size_t nlines = 0; - TAILQ_INIT(&changed_paths); + RB_INIT(&changed_paths); memset(&dsa, 0, sizeof(dsa)); dsa.paths = &changed_paths; dsa.diff_algo = tog_diff_algo; @@ -7401,7 +7402,7 @@ cmd_diff(int argc, char *argv[]) struct tog_view *view; int *pack_fds = NULL; - TAILQ_INIT(&paths); + RB_INIT(&paths); while ((ch = getopt(argc, argv, "aC:c:r:sw")) != -1) { switch (ch) {

2024-12-17 23:16 Kyle Ackerman:
Change got_pathlist to use RB_tree instead of TAILQ
- 2024-12-19 02:10 Stefan Sperling:
  Change got_pathlist to use RB_tree instead of TAILQ
- - 2024-12-19 19:47 Kyle Ackerman:
    Change got_pathlist to use RB_tree instead of TAILQ