[PATCH 14/14] tree-diff: make list tail-passing more explicit
- From
Jeff King <peff@peff.net>
- Date
- Jan 9, 2025, 08:57 UTC
- Message-ID
- <20250109085700.GN2748836@coredump.intra.peff.net>
- In-Reply-To
- <20250109082723.GA2748497@coredump.intra.peff.net>
The ll_diff_tree_paths() function and its helpers all take a pointer to a list tail, possibly add to it, and then return the new tail. This works but has two downsides:
- The top-level caller (diff_tree_paths() in this case) has to make a
fake combine_diff_path struct to act as the list head. This is
especially weird here, as it's a flexible-sized struct which will
have an empty FLEX_ARRAY field. That used to be a portability
problem, though these days it is legal because our FLEX_ARRAY macro
over-allocates if necessary. It's still kind of ugly, though. - Besides the name "tail", it's not immediately obvious that the entry
we pass around will not be examined by each function. Using a
pointer-to-pointer or similar makes it more obvious we only care
about the pointer itself, not its contents.We can solve both by passing around a pointer to the tail instead. That gets rid of the return value entirely, though note that because of the recursion we actually need a three-star pointer for this to work.
The result is fairly readable, as we only need to dereference the tail in one spot. If we wanted to make it simpler we could wrap the tail in a struct, which we pass around.
Another option is to convert combine_diff to use our generic list_head API. I tried that and found the result became much harder to read overall. It means that _all_ code that looks at combine_diff_path structs needs to be modified, since the "next" pointer is now inside a list_head which has to be dereferenced with list_entry(). And we lose some type safety, since we're just passing around a list_head struct everywhere, and everybody who looks at it has to specify the type to list_entry themselves.
Signed-off-by: Jeff King <peff@peff.net> --- tree-diff.c | 47 +++++++++++++++++++++-------------------------- 1 file changed, 21 insertions(+), 26 deletions(-)
diff --git a/tree-diff.c b/tree-diff.c index f5ec19113c..60c558c2b5 100644 --- a/tree-diff.c +++ b/tree-diff.c @@ -48,8 +48,8 @@ free((x)); \ } while(0) -static struct combine_diff_path *ll_diff_tree_paths( - struct combine_diff_path *tail, const struct object_id *oid, +static void ll_diff_tree_paths( + struct combine_diff_path ***tail, const struct object_id *oid, const struct object_id **parents_oid, int nparent, struct strbuf *base, struct diff_options *opt, int depth); @@ -134,10 +134,10 @@ static int emit_diff_first_parent_only(struct diff_options *opt, struct combine_ * t, tp -> path modified/added * (M for tp[i]=tp[imin], A otherwise) */ -static struct combine_diff_path *emit_path(struct combine_diff_path *tail, - struct strbuf *base, struct diff_options *opt, int nparent, - struct tree_desc *t, struct tree_desc *tp, - int imin, int depth) +static void emit_path(struct combine_diff_path ***tail, + struct strbuf *base, struct diff_options *opt, + int nparent, struct tree_desc *t, struct tree_desc *tp, + int imin, int depth) { unsigned short mode; const char *path; @@ -219,8 +219,8 @@ static struct combine_diff_path *emit_path(struct combine_diff_path *tail, keep = opt->pathchange(opt, p); if (keep) { - tail->next = p; - tail = p; + **tail = p; + *tail = &p->next; } else { free(p); } @@ -239,13 +239,12 @@ static struct combine_diff_path *emit_path(struct combine_diff_path *tail, strbuf_add(base, path, pathlen); strbuf_addch(base, '/'); - tail = ll_diff_tree_paths(tail, oid, parents_oid, nparent, base, opt, - depth + 1); + ll_diff_tree_paths(tail, oid, parents_oid, nparent, base, opt, + depth + 1); FAST_ARRAY_FREE(parents_oid, nparent); } strbuf_setlen(base, old_baselen); - return tail; } static void skip_uninteresting(struct tree_desc *t, struct strbuf *base, @@ -358,8 +357,8 @@ static inline void update_tp_entries(struct tree_desc *tp, int nparent) update_tree_entry(&tp[i]); } -static struct combine_diff_path *ll_diff_tree_paths( - struct combine_diff_path *tail, const struct object_id *oid, +static void ll_diff_tree_paths( + struct combine_diff_path ***tail, const struct object_id *oid, const struct object_id **parents_oid, int nparent, struct strbuf *base, struct diff_options *opt, int depth) @@ -463,8 +462,8 @@ static struct combine_diff_path *ll_diff_tree_paths( } /* D += {δ(t,pi) if pi=p[imin]; "+a" if pi > p[imin]} */ - tail = emit_path(tail, base, opt, nparent, - &t, tp, imin, depth); + emit_path(tail, base, opt, nparent, + &t, tp, imin, depth); skip_emit_t_tp: /* t↓, ∀ pi=p[imin] pi↓ */ @@ -475,8 +474,8 @@ static struct combine_diff_path *ll_diff_tree_paths( /* t < p[imin] */ else if (cmp < 0) { /* D += "+t" */ - tail = emit_path(tail, base, opt, nparent, - &t, /*tp=*/NULL, -1, depth); + emit_path(tail, base, opt, nparent, + &t, /*tp=*/NULL, -1, depth); /* t↓ */ update_tree_entry(&t); @@ -491,8 +490,8 @@ static struct combine_diff_path *ll_diff_tree_paths( goto skip_emit_tp; } - tail = emit_path(tail, base, opt, nparent, - /*t=*/NULL, tp, imin, depth); + emit_path(tail, base, opt, nparent, + /*t=*/NULL, tp, imin, depth); skip_emit_tp: /* ∀ pi=p[imin] pi↓ */ @@ -505,20 +504,16 @@ static struct combine_diff_path *ll_diff_tree_paths( free(tptree[i]); FAST_ARRAY_FREE(tptree, nparent); FAST_ARRAY_FREE(tp, nparent); - - return tail; } struct combine_diff_path *diff_tree_paths( const struct object_id *oid, const struct object_id **parents_oid, int nparent, struct strbuf *base, struct diff_options *opt) { - struct combine_diff_path head, *p; - /* fake list head, so worker can assume it is non-NULL */ - head.next = NULL; - p = ll_diff_tree_paths(&head, oid, parents_oid, nparent, base, opt, 0); - return p; + struct combine_diff_path *head = NULL, **tail = &head; + ll_diff_tree_paths(&tail, oid, parents_oid, nparent, base, opt, 0); + return head; } /*
-- 2.48.0.rc2.413.gc1c80375a3