One small change,

This plugs a memory leak that is created in my previous diff.
Apply this on top of the previous. I can regenerate the entire
diff again if it is more convenient.
diff /home/kyle/src/test-got
path + /home/kyle/src/test-got
commit - 8ba7ab0c394137953de194f38ad581bbe97fa86e
blob - 19b5fc1b23828a64e772094208f1a08e0372df5a
file + lib/path.c
--- lib/path.c
+++ lib/path.c
@@ -236,7 +236,10 @@ got_pathlist_insert(struct got_pathlist_entry **insert
new->path = path;
new->path_len = path_len;
new->data = data;
- RB_INSERT(got_pathlist_head, pathlist, new);
+ if(RB_INSERT(got_pathlist_head, pathlist, new)){
+ free(new);
+ new = NULL;
+ }
if (inserted)
*inserted = new;
return NULL;

On Thursday, December 19th, 2024 at 1:47 PM, Kyle Ackerman <kack@kyleackerman.net> wrote:

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