Re: [PATCH 15/16] commit-reach: make can_all_from_reach... linear
- From
René Scharfe <l.s.r@web.de>
- Date
- Oct 5, 2018, 18:48 UTC
- Message-ID
- <dca35e44-a763-bcf0-f457-b8dab53815cf@web.de>
- In-Reply-To
- <20181005165157.GC11254@sigill.intra.peff.net>
Am 05.10.2018 um 18:51 schrieb Jeff King:
Show 30 quoted lines
> On Fri, Oct 05, 2018 at 12:59:02AM +0200, René Scharfe wrote:
>
>> We could also do something like this to reduce the amount of manual
>> casting, but do we want to? (Macro at the bottom, three semi-random
>> examples at the top.)
>> [...]
>> diff --git a/git-compat-util.h b/git-compat-util.h
>> index 5f2e90932f..f9e78d69a2 100644
>> --- a/git-compat-util.h
>> +++ b/git-compat-util.h
>> @@ -1066,6 +1066,18 @@ static inline void sane_qsort(void *base, size_t nmemb, size_t size,
>> qsort(base, nmemb, size, compar);
>> }
>>
>> +#define DEFINE_SORT(name, elemtype, one, two, code) \
>> +static int name##_compare(const void *one##_v_, const void *two##_v_) \
>> +{ \
>> + elemtype const *one = one##_v_; \
>> + elemtype const *two = two##_v_; \
>> + code; \
>> +} \
>> +static void name(elemtype *array, size_t n) \
>> +{ \
>> + QSORT(array, n, name##_compare); \
>> +}
>
> Interesting. When I saw the callers of this macro, I first thought you
> were just removing the casts from the comparison function, but the real
> value here is the matching QSORT() wrapper which provides the type
> safety.Indeed.
> I'm not wild about declaring functions inside macros, just because it > makes tools like ctags like useful (but I have certainly been guilty of > it myself). I'd also worry that taking "code" as a macro parameter might > not scale (what happens if the code has a comma in it?)
It works fine, as long as the comma is surrounded by parentheses, so function calls with more than one parameter are fine without any change.
Show 22 quoted lines
> I think we can address that last part by switching the definition order.
> Like:
>
> #define DEFINE_SORT(name, elemtype, one, two) \
> static int name##_compare(const void *, const void *); \
> static void name(elemtype *array, size_t n) \
> { \
> QSORT(array, n, name##_compare); \
> } \
> static int name##_compare(const void *one##_v_, const void *two##_v_) \
> { \
> elemtype const *one = one##_v_; \
> elemtype const *two = two##_v_; \
>
> And then expecting the caller to do:
>
> DEFINE_SORT(foo, struct foo, a, b)
> /* code goes here */
> }
>
> The unbalanced braces are nasty, though (and likely to screw up editor
> formatting, highlighting, etc).Adding an extra pair of parentheses if needed is also not ideal, but has less downsides, I think.
Show 15 quoted lines
> I wonder if it would be possible to just declare the comparison function
> with its real types, and then teach QSORT() to do a type check. That
> would require typeof() at least, but it would be OK for the type-check
> to be available only to gcc/clang users, I think.
>
> I'm not quite sure what that type-check would look like, but I was
> thinking something along the lines of (inside the QSORT macro):
>
> do {
> /* this will yield a type mismatch if fed the wrong function */
> int (*check)(const typeof(array), const typeof(array)) = compar;
> sane_qsort(array, n, sizeof(*array), n);
> } while (0)
>
> I have no idea if that even comes close to compiling, though.If the comparison function has proper types then we need to declare a version with void pointer parameters as well to give to qsort(3). I think using cast function pointers is undefined. Perhaps like this?
--- bisect.c | 11 +++++------ commit-graph.c | 8 ++++---- commit-reach.c | 12 +++++++----- git-compat-util.h | 14 ++++++++++++++ 4 files changed, 30 insertions(+), 15 deletions(-)
diff --git a/bisect.c b/bisect.c index e8b17cf7e1..1fc6278c6b 100644 --- a/bisect.c +++ b/bisect.c @@ -192,17 +192,16 @@ struct commit_dist { int distance; }; -static int compare_commit_dist(const void *a_, const void *b_) +static int compare_commit_dist(const struct commit_dist *a, + const struct commit_dist *b) { - struct commit_dist *a, *b; - - a = (struct commit_dist *)a_; - b = (struct commit_dist *)b_; if (a->distance != b->distance) return b->distance - a->distance; /* desc sort */ return oidcmp(&a->commit->object.oid, &b->commit->object.oid); } +DEFINE_SORT(sort_by_commit_dist, struct commit_dist *, compare_commit_dist) + static struct commit_list *best_bisection_sorted(struct commit_list *list, int nr) { struct commit_list *p; @@ -223,7 +222,7 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n array[cnt].distance = distance; cnt++; } - QSORT(array, cnt, compare_commit_dist); + sort_by_commit_dist(array, cnt); for (p = list, i = 0; i < cnt; i++) { struct object *obj = &(array[i].commit->object); diff --git a/commit-graph.c b/commit-graph.c index 7f4519ec3b..07d302fefd 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -550,13 +550,13 @@ static void write_graph_chunk_large_edges(struct hashfile *f, } } -static int commit_compare(const void *_a, const void *_b) +static int commit_compare(const struct object_id *a, const struct object_id *b) { - const struct object_id *a = (const struct object_id *)_a; - const struct object_id *b = (const struct object_id *)_b; return oidcmp(a, b); } +DEFINE_SORT(sort_oids, struct object_id *, commit_compare) + struct packed_commit_list { struct commit **list; int nr; @@ -780,7 +780,7 @@ void write_commit_graph(const char *obj_dir, close_reachable(&oids); - QSORT(oids.list, oids.nr, commit_compare); + sort_oids(oids.list, oids.nr); count_distinct = 1; for (i = 1; i < oids.nr; i++) { diff --git a/commit-reach.c b/commit-reach.c index 2f5e592d16..496c4201af 100644 --- a/commit-reach.c +++ b/commit-reach.c @@ -527,11 +527,11 @@ int commit_contains(struct ref_filter *filter, struct commit *commit, return is_descendant_of(commit, list); } -static int compare_commits_by_gen(const void *_a, const void *_b) +static int compare_commits_by_gen(const struct commit * const *ap, + const struct commit * const *bp) { - const struct commit *a = *(const struct commit * const *)_a; - const struct commit *b = *(const struct commit * const *)_b; - + const struct commit *a = *ap; + const struct commit *b = *bp; if (a->generation < b->generation) return -1; if (a->generation > b->generation) @@ -539,6 +539,8 @@ static int compare_commits_by_gen(const void *_a, const void *_b) return 0; } +DEFINE_SORT(sort_commits_by_gen, struct commit **, compare_commits_by_gen) + int can_all_from_reach_with_flag(struct object_array *from, unsigned int with_flag, unsigned int assign_flag, @@ -580,7 +582,7 @@ int can_all_from_reach_with_flag(struct object_array *from, nr_commits++; } - QSORT(list, nr_commits, compare_commits_by_gen); + sort_commits_by_gen(list, nr_commits); for (i = 0; i < nr_commits; i++) { /* DFS from list[i] */ diff --git a/git-compat-util.h b/git-compat-util.h index 5f2e90932f..2462173790 100644 --- a/git-compat-util.h +++ b/git-compat-util.h @@ -1066,6 +1066,20 @@ static inline void sane_qsort(void *base, size_t nmemb, size_t size, qsort(base, nmemb, size, compar); } +#define DEFINE_SORT(name, type, compare) \ +static int compare##_void(const void *one, const void *two) \ +{ \ + return compare(one, two); \ +} \ +static void name(type base, size_t nmemb) \ +{ \ + const type dummy = NULL; \ + if (nmemb > 1) \ + qsort(base, nmemb, sizeof(base[0]), compare##_void); \ + else if (0) \ + compare(dummy, dummy); \ +} + #ifndef HAVE_ISO_QSORT_S int git_qsort_s(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *, void *), void *ctx);
-- 2.19.0