From: Stefan Sperling Subject: Re: Change got_pathlist to use RB_tree instead of TAILQ To: Kyle Ackerman Cc: "gameoftrees@openbsd.org" Date: Thu, 19 Dec 2024 03:10:32 +0100 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; M got/got.c | 1+ 1- M include/got_path.h | 0+ 1- M lib/fileindex.c | 11+ 9- M lib/path.c | 3+ 1- M lib/worktree.c | 2+ 2- 5 files changed, 17 insertions(+), 14 deletions(-) commit - 872f80ac1ef5edb1e7b2f75e012dc7b0b51b152b commit + a9785d2b3cb1adb748f776e4be8ae56a9f32b17e blob - d2c999a83f74755c515256f90a0df5cd342785a7 blob + 48358ad1144d94badb8e3747f30345948a74c02b --- got/got.c +++ got/got.c @@ -2237,7 +2237,7 @@ delete_missing_refs(struct got_pathlist_head *their_re if (pe != NULL) continue; - RB_FOREACH(pe, got_pathlist_head,their_symrefs) { + RB_FOREACH(pe, got_pathlist_head, their_symrefs) { if (strcmp(their_refname, pe->path) == 0) break; } blob - c9aff1c163d5229c9b5576ac29336099a3951479 blob + 8232df1c967a331ed394daaa474c7547e2c93fda --- include/got_path.h +++ include/got_path.h @@ -137,4 +137,3 @@ const struct got_error *got_path_create_file(const cha * (Cross-mount-point moves are not yet implemented.) */ const struct got_error *got_path_move_file(const char *, const char *); - blob - e3389e9f3393661dbd1d58d730bab432f00865d2 blob + dbef298e12a03f1a40e8adf8a5cffe916aca0681 --- lib/fileindex.c +++ lib/fileindex.c @@ -1061,9 +1061,9 @@ 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, - 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) + 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; @@ -1202,8 +1202,9 @@ diff_fileindex_dir(struct got_fileindex *fileindex, if (err) break; *ie = walk_fileindex(fileindex, *ie); - err = walk_dir(&dle, fileindex, ie, dle, dirlist, dirfd, - path, rootpath, repo, 0, cb, cb_arg); + 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) @@ -1214,8 +1215,9 @@ diff_fileindex_dir(struct got_fileindex *fileindex, dirfd); if (err) break; - err = walk_dir(&dle, fileindex, ie, dle, dirlist, 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; @@ -1232,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, dirlist, 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; } blob - b838d60e43481351c8b1afc2f2e9cb599022c167 blob + 19b5fc1b23828a64e772094208f1a08e0372df5a --- lib/path.c +++ lib/path.c @@ -215,7 +215,9 @@ got_path_cmp(const char *path1, const char *path2, siz } int -got_pathlist_cmp(const struct got_pathlist_entry *p1, const struct got_pathlist_entry *p2){ +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); } blob - 379963270df17e1f835a26d75ba446d56c396996 blob + df89f493b283c3c8957846b5f60994c98756d8ae --- lib/worktree.c +++ lib/worktree.c @@ -5255,7 +5255,7 @@ revert_file(void *arg, unsigned char status, unsigned struct got_pathlist_entry *pe; RB_FOREACH(pe, got_pathlist_head, - a->added_files_to_unlink) { + a->added_files_to_unlink) { if (got_path_cmp(pe->path, relpath, pe->path_len, strlen(relpath))) continue; @@ -6733,7 +6733,7 @@ got_worktree_commit(struct got_object_id **new_commit_ goto done; } - RB_FOREACH(pe, got_pathlist_head, paths) { + RB_FOREACH(pe, got_pathlist_head, paths) { err = check_path_is_commitable(pe->path, &commitable_paths); if (err) goto done;