Change got_pathlist to use RB_tree instead of TAILQ

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. ----------------------------------------------- commit 18bd25124d83d42bf023651e1ae8b450d660b093 (got_pathtree) from: Kyle Ackerman <kack@kyleackerman.net> date: Tue Dec 17 21:11:06 2024 UTC Make everything treat got_pathlist as a RB_TREE diff 05baa9bad111d24487e962de7bfd97485352a7cf 18bd25124d83d42bf023651e1ae8b450d660b093 commit - 05baa9bad111d24487e962de7bfd97485352a7cf commit + 18bd25124d83d42bf023651e1ae8b450d660b093 blob - 5cacf0312aa5369059a9cb068b2b422740919df3 blob + ccf02d6c50db66904986dfd388f7aac30a6edd40 --- cvg/cvg.c +++ cvg/cvg.c @@ -741,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 " @@ -1028,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, @@ -1122,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; @@ -1202,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; } @@ -1244,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) @@ -1268,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) @@ -1369,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) @@ -1421,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) @@ -1487,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 +1536,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:lmqR:v")) != -1) { switch (ch) { @@ -1582,16 +1582,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'); } @@ -1730,7 +1730,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; @@ -1768,7 +1768,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; @@ -1834,7 +1834,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; @@ -2191,7 +2191,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 " @@ -2664,12 +2664,12 @@ cmd_update(int argc, char *argv[]) const char *refname; struct got_reference *head_ref = 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:qr:vX")) != -1) { switch (ch) { @@ -2900,7 +2900,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; @@ -3403,7 +3403,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; @@ -3593,7 +3593,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; @@ -3715,7 +3715,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); @@ -3777,7 +3777,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)) @@ -4485,8 +4485,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", @@ -5684,7 +5684,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; @@ -6471,7 +6471,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", @@ -6533,7 +6533,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) { @@ -6616,7 +6616,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", @@ -6698,7 +6698,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) { @@ -7159,7 +7159,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; @@ -7191,7 +7191,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) @@ -7342,7 +7342,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 " @@ -7421,7 +7421,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) { @@ -7601,7 +7601,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), @@ -7808,7 +7808,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 @@ -8100,7 +8100,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) @@ -8967,7 +8967,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)) @@ -9032,7 +9032,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", @@ -9118,7 +9118,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; /* @@ -9131,7 +9131,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 - 87817f91a3c3799c45895450debd1f257aba6645 blob + 494c41cbb59b318721d727272ed966fd920ab80f --- got/got.c +++ got/got.c @@ -842,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 " @@ -1130,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, @@ -1224,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; @@ -1304,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; } @@ -1346,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) @@ -1370,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) @@ -1471,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) @@ -1523,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) @@ -1589,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 +1638,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:lmqR:v")) != -1) { switch (ch) { @@ -1684,16 +1684,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'); } @@ -1837,7 +1837,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; @@ -1875,7 +1875,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; @@ -1941,7 +1941,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; @@ -2226,14 +2226,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; } @@ -2392,11 +2392,11 @@ cmd_fetch(int argc, char *argv[]) int *pack_fds = NULL, have_bflag = 0; const char *remote_head = NULL, *worktree_branch = 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:dlqR:r:tvX")) != -1) { switch (ch) { @@ -2452,10 +2452,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'); @@ -2467,13 +2467,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'); } @@ -2576,7 +2576,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++) { @@ -2586,7 +2586,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); @@ -2735,7 +2735,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; @@ -2822,7 +2822,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; @@ -3098,7 +3098,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 " @@ -3618,7 +3618,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 " @@ -3734,7 +3734,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, @@ -4181,7 +4181,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; @@ -4371,7 +4371,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; @@ -4493,7 +4493,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); @@ -4555,7 +4555,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)) @@ -5318,8 +5318,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", @@ -6602,7 +6602,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; @@ -7253,7 +7253,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 " @@ -8149,7 +8149,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", @@ -8211,7 +8211,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) { @@ -8294,7 +8294,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", @@ -8376,7 +8376,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) { @@ -8851,7 +8851,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; @@ -8883,7 +8883,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) @@ -9034,7 +9034,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 " @@ -9113,7 +9113,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) { @@ -9294,7 +9294,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), @@ -9487,7 +9487,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 @@ -9762,7 +9762,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) { @@ -9928,12 +9928,12 @@ cmd_send(int argc, char *argv[]) struct got_reference *ref = NULL; int *pack_fds = 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:fqr:Tt:v")) != -1) { switch (ch) { @@ -9986,9 +9986,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'); @@ -10160,7 +10160,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; @@ -10303,7 +10303,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) @@ -11507,7 +11507,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 @@ -11782,7 +11782,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; @@ -12795,7 +12795,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 @@ -13245,7 +13245,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; @@ -13804,7 +13804,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; @@ -13972,7 +13972,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 " @@ -14108,7 +14108,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 " @@ -14598,7 +14598,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)) @@ -14663,7 +14663,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", @@ -14749,7 +14749,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; /* @@ -14762,7 +14762,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 - 0334cdd84e5cecec012418b24b95cb26e09c531d blob + 5a8c2bc8ec21628c9260de98ee4077f5f878ff15 --- gotadmin/gotadmin.c +++ gotadmin/gotadmin.c @@ -729,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); @@ -789,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) @@ -1436,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); @@ -1488,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) @@ -1570,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; } @@ -1686,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 " @@ -1767,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; @@ -1786,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 - 1be4750ce54f2336567c540b8beac6d486c95e94 blob + c9aff1c163d5229c9b5576ac29336099a3951479 --- include/got_path.h +++ include/got_path.h @@ -68,12 +68,11 @@ struct got_pathlist_entry { size_t path_len; void *data; /* data pointer provided to got_pathlist_insert() */ }; -int got_pathlist_cmp(const struct got_pathtree_entry * , const struct got_pathtree_entry *); +int got_pathlist_cmp(const struct got_pathlist_entry * , const struct got_pathlist_entry *); -RB_HEAD(got_pathtree, got_pathtree_entry); -RB_PROTOTYPE(got_pathlist, got_pathtree_entry, entry, got_pathtree_cmp); +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 - 56a06bc9df3b4aa91dd6839c4ba29b20e6ebe99e blob + 658c27563232e250780c4d2b9306e9643b58167f --- lib/diff.c +++ lib/diff.c @@ -122,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); @@ -1124,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; @@ -1316,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 - 7c67b8bd27d8f0b14c6c6ab064426ba9ca064259 blob + 9cb36d14358a2752cfe60a63943dd8087a7837a0 --- lib/fetch.c +++ lib/fetch.c @@ -144,7 +144,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 || @@ -159,7 +159,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 + e3389e9f3393661dbd1d58d730bab432f00865d2 --- 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,9 @@ 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 +1214,8 @@ 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 +1232,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 +1253,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 - f9e780471a1fdecb54382af4af19d014f1100932 blob + 9d98158fc39b736def37140f6711f0da05badf51 --- lib/object_create.c +++ lib/object_create.c @@ -330,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 - 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 - 11dd50089be03d7956b375ffea58c476b7093e94 blob + b838d60e43481351c8b1afc2f2e9cb599022c167 --- lib/path.c +++ lib/path.c @@ -214,43 +214,27 @@ 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; @@ -259,9 +243,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; @@ -270,7 +254,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); } } @@ -550,3 +534,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 - 41968aca9515852e68d0701601c30623f6bf332b blob + 2c49d4419a4c395afafe7cca1614b53619d50ed5 --- lib/privsep.c +++ lib/privsep.c @@ -596,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"); @@ -627,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; @@ -651,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; @@ -676,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; @@ -900,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) { @@ -916,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; @@ -925,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 - 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 - f8e87fabb17857a5abf28d64d34330a17b6aefc7 blob + e23a1ebbd33fde03ae9da92905cbb3f3d6e57938 --- lib/send.c +++ lib/send.c @@ -265,16 +265,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, *res; - TAILQ_FOREACH(pe, refs, entry) { - if (got_path_cmp(pe->path, refname, strlen(pe->path), - strlen(refname)) == 0) { - return pe; - } - } - - return NULL; + find.path = *refname; + find.path_len = strlen(refname); + res = RB_FIND(got_pathlist_head, refs, &find); + return res; } static const struct got_error * @@ -365,14 +361,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; @@ -400,7 +396,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) { @@ -417,7 +413,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) { @@ -440,7 +436,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; } @@ -491,7 +487,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); @@ -516,7 +512,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; @@ -610,14 +606,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 - 936dc8f7691a930afed9b877b099366102eecf50 blob + 379963270df17e1f835a26d75ba446d56c396996 --- 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 - e385e250cc75d449167dd82181f0654e2dcdf4e5 blob + 1a879c6ff886cd28262c2891e78edd9bed63baa0 --- 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 - 20179ae95ef1611e03762d9834c7627b5c9d95b8 blob + 941d899ffe34503cf9f82ba20f3e587581c384df --- libexec/got-fetch-pack/got-fetch-pack.c +++ libexec/got-fetch-pack/got-fetch-pack.c @@ -83,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)); @@ -229,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); @@ -247,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; @@ -358,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); @@ -424,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) @@ -468,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; } @@ -485,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; } @@ -533,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); @@ -541,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); @@ -577,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); @@ -874,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 - e81e7837a064d76ff2e1e0bb7634023c1f5b6b5c blob + 1f5f72593dca228e5752bbe2703e47723bda37c2 --- libexec/got-send-pack/got-send-pack.c +++ libexec/got-send-pack/got-send-pack.c @@ -260,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; @@ -359,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) { @@ -442,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); @@ -450,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) { @@ -489,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) { @@ -627,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 - bdf8f52499f3ff3ea50a58b637e8f5a56a31305f blob + c4da368ef9fe5fb3b4c6ff3a0879637e0a4a2611 --- regress/path/path_test.c +++ regress/path/path_test.c @@ -142,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); @@ -153,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"); @@ -178,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); @@ -189,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 - 2968cc435be8c4f98d08b83c14a042c91361d304 blob + e5b6a27289781714067597b57322e12510368ce6 --- tog/tog.c +++ tog/tog.c @@ -3176,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); @@ -5823,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; @@ -6331,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) @@ -6519,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; @@ -7402,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) { ----------------------------------------------- commit 05baa9bad111d24487e962de7bfd97485352a7cf from: Kyle Ackerman <kack@kyleackerman.net> date: Tue Dec 17 21:11:00 2024 UTC Changing got_pathlist to use RB_tree diff 062b6633443ffe592b38b584f1aff39b6ffa856c 05baa9bad111d24487e962de7bfd97485352a7cf commit - 062b6633443ffe592b38b584f1aff39b6ffa856c commit + 05baa9bad111d24487e962de7bfd97485352a7cf blob - 1100e919033e225f9500e38d04dc8c9304369742 blob + 1be4750ce54f2336567c540b8beac6d486c95e94 --- include/got_path.h +++ include/got_path.h @@ -61,19 +61,19 @@ 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_pathtree_entry * , const struct got_pathtree_entry *); +RB_HEAD(got_pathtree, got_pathtree_entry); +RB_PROTOTYPE(got_pathlist, got_pathtree_entry, entry, got_pathtree_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 @@ -138,3 +138,4 @@ const struct got_error *got_path_create_file(const cha * (Cross-mount-point moves are not yet implemented.) */ const struct got_error *got_path_move_file(const char *, const char *); + ----------------------------------------------- commit 062b6633443ffe592b38b584f1aff39b6ffa856c from: Kyle Ackerman <kack@kyleackerman.net> date: Tue Dec 17 15:20:28 2024 UTC Including <sys/tree.h> diff e278a869d0de428a352943747454613de10b132f 062b6633443ffe592b38b584f1aff39b6ffa856c commit - e278a869d0de428a352943747454613de10b132f commit + 062b6633443ffe592b38b584f1aff39b6ffa856c blob - 14f6f69962facd1f76c094458fd23bec1fabb9f1 blob + 5cacf0312aa5369059a9cb068b2b422740919df3 --- 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> blob - 5493a5339d1cfcb92aac6c450ddb5cfa5578f40c blob + 87817f91a3c3799c45895450debd1f257aba6645 --- 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> blob - b4498d7b27edc861c011a977cef6c8b66603f09d blob + 0334cdd84e5cecec012418b24b95cb26e09c531d --- 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> 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 - 88b600b1f00ec7c68d10041e64ae7ef76b9baac2 blob + 36cd4ca4c569f4c7596ec6b4918e99d25ba5288b --- 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 + 56a06bc9df3b4aa91dd6839c4ba29b20e6ebe99e --- 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> 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 + f9e780471a1fdecb54382af4af19d014f1100932 --- 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> 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 - 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 + 11dd50089be03d7956b375ffea58c476b7093e94 --- 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> blob - 4d97f68370673cd0b8596deaab214d88a71a195b blob + 41968aca9515852e68d0701601c30623f6bf332b --- 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> 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 - 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 + 20179ae95ef1611e03762d9834c7627b5c9d95b8 --- 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> 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 + e81e7837a064d76ff2e1e0bb7634023c1f5b6b5c --- 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> 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 + bdf8f52499f3ff3ea50a58b637e8f5a56a31305f --- 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> blob - a09591e35e09e13fb23f7c13166a95b75ab02ffc blob + 2968cc435be8c4f98d08b83c14a042c91361d304 --- 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> All regressions have passed on my end. Suggestions/Thoughts/Comments? diff refs/heads/main refs/heads/got_pathtree commit - e278a869d0de428a352943747454613de10b132f commit + 18bd25124d83d42bf023651e1ae8b450d660b093 blob - 14f6f69962facd1f76c094458fd23bec1fabb9f1 blob + ccf02d6c50db66904986dfd388f7aac30a6edd40 --- 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; @@ -1535,10 +1536,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:lmqR:v")) != -1) { switch (ch) { @@ -1581,16 +1582,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'); } @@ -1729,7 +1730,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; @@ -1767,7 +1768,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; @@ -1833,7 +1834,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; @@ -2190,7 +2191,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 " @@ -2663,12 +2664,12 @@ cmd_update(int argc, char *argv[]) const char *refname; struct got_reference *head_ref = 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:qr:vX")) != -1) { switch (ch) { @@ -2899,7 +2900,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; @@ -3402,7 +3403,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; @@ -3592,7 +3593,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; @@ -3714,7 +3715,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); @@ -3776,7 +3777,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)) @@ -4484,8 +4485,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", @@ -5683,7 +5684,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; @@ -6470,7 +6471,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", @@ -6532,7 +6533,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) { @@ -6615,7 +6616,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", @@ -6697,7 +6698,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) { @@ -7158,7 +7159,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; @@ -7190,7 +7191,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) @@ -7341,7 +7342,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 " @@ -7420,7 +7421,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) { @@ -7600,7 +7601,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), @@ -7807,7 +7808,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 @@ -8099,7 +8100,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) @@ -8966,7 +8967,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)) @@ -9031,7 +9032,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", @@ -9117,7 +9118,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; /* @@ -9130,7 +9131,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 - 5493a5339d1cfcb92aac6c450ddb5cfa5578f40c blob + 494c41cbb59b318721d727272ed966fd920ab80f --- 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; @@ -1637,10 +1638,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:lmqR:v")) != -1) { switch (ch) { @@ -1683,16 +1684,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'); } @@ -1836,7 +1837,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; @@ -1874,7 +1875,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; @@ -1940,7 +1941,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; @@ -2225,14 +2226,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; } @@ -2391,11 +2392,11 @@ cmd_fetch(int argc, char *argv[]) int *pack_fds = NULL, have_bflag = 0; const char *remote_head = NULL, *worktree_branch = 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:dlqR:r:tvX")) != -1) { switch (ch) { @@ -2451,10 +2452,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'); @@ -2466,13 +2467,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'); } @@ -2575,7 +2576,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++) { @@ -2585,7 +2586,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); @@ -2734,7 +2735,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; @@ -2821,7 +2822,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; @@ -3097,7 +3098,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 " @@ -3617,7 +3618,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 " @@ -3733,7 +3734,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, @@ -4180,7 +4181,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; @@ -4370,7 +4371,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; @@ -4492,7 +4493,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); @@ -4554,7 +4555,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)) @@ -5317,8 +5318,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", @@ -6601,7 +6602,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; @@ -7252,7 +7253,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 " @@ -8148,7 +8149,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", @@ -8210,7 +8211,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) { @@ -8293,7 +8294,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", @@ -8375,7 +8376,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) { @@ -8850,7 +8851,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; @@ -8882,7 +8883,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) @@ -9033,7 +9034,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 " @@ -9112,7 +9113,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) { @@ -9293,7 +9294,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), @@ -9486,7 +9487,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 @@ -9761,7 +9762,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) { @@ -9927,12 +9928,12 @@ cmd_send(int argc, char *argv[]) struct got_reference *ref = NULL; int *pack_fds = 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:fqr:Tt:v")) != -1) { switch (ch) { @@ -9985,9 +9986,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'); @@ -10159,7 +10160,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; @@ -10302,7 +10303,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) @@ -11506,7 +11507,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 @@ -11781,7 +11782,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; @@ -12794,7 +12795,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 @@ -13244,7 +13245,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; @@ -13803,7 +13804,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; @@ -13971,7 +13972,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 " @@ -14107,7 +14108,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 " @@ -14597,7 +14598,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)) @@ -14662,7 +14663,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", @@ -14748,7 +14749,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; /* @@ -14761,7 +14762,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 - 1100e919033e225f9500e38d04dc8c9304369742 blob + c9aff1c163d5229c9b5576ac29336099a3951479 --- 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 @@ -138,3 +137,4 @@ const struct got_error *got_path_create_file(const cha * (Cross-mount-point moves are not yet implemented.) */ const struct got_error *got_path_move_file(const char *, const char *); + 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 - 88b600b1f00ec7c68d10041e64ae7ef76b9baac2 blob + 36cd4ca4c569f4c7596ec6b4918e99d25ba5288b --- 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 - 7c67b8bd27d8f0b14c6c6ab064426ba9ca064259 blob + 9cb36d14358a2752cfe60a63943dd8087a7837a0 --- lib/fetch.c +++ lib/fetch.c @@ -144,7 +144,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 || @@ -159,7 +159,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 + e3389e9f3393661dbd1d58d730bab432f00865d2 --- 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,9 @@ 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 +1214,8 @@ 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 +1232,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 +1253,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 + b838d60e43481351c8b1afc2f2e9cb599022c167 --- 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,27 @@ 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 +243,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 +254,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 +534,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 - f8e87fabb17857a5abf28d64d34330a17b6aefc7 blob + e23a1ebbd33fde03ae9da92905cbb3f3d6e57938 --- lib/send.c +++ lib/send.c @@ -265,16 +265,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, *res; - TAILQ_FOREACH(pe, refs, entry) { - if (got_path_cmp(pe->path, refname, strlen(pe->path), - strlen(refname)) == 0) { - return pe; - } - } - - return NULL; + find.path = *refname; + find.path_len = strlen(refname); + res = RB_FIND(got_pathlist_head, refs, &find); + return res; } static const struct got_error * @@ -365,14 +361,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; @@ -400,7 +396,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) { @@ -417,7 +413,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) { @@ -440,7 +436,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; } @@ -491,7 +487,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); @@ -516,7 +512,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; @@ -610,14 +606,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 - 936dc8f7691a930afed9b877b099366102eecf50 blob + 379963270df17e1f835a26d75ba446d56c396996 --- 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 - e385e250cc75d449167dd82181f0654e2dcdf4e5 blob + 1a879c6ff886cd28262c2891e78edd9bed63baa0 --- 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