diff options
| -rw-r--r-- | Makefile | 1 | ||||
| -rw-r--r-- | blame.c | 30 | ||||
| -rw-r--r-- | commit.c | 20 | ||||
| -rw-r--r-- | fetch-pack.c | 8 | ||||
| -rw-r--r-- | mergesort.c | 84 | ||||
| -rw-r--r-- | mergesort.h | 108 | ||||
| -rw-r--r-- | packfile.c | 18 | ||||
| -rw-r--r-- | remote.c | 22 | ||||
| -rw-r--r-- | remote.h | 2 | ||||
| -rw-r--r-- | t/helper/test-mergesort.c | 34 | ||||
| -rwxr-xr-x | t/perf/p0071-sort.sh | 4 | ||||
| -rwxr-xr-x | t/t0071-sort.sh | 2 |
12 files changed, 134 insertions, 199 deletions
@@ -992,7 +992,6 @@ LIB_OBJS += merge-ort.o LIB_OBJS += merge-ort-wrappers.o LIB_OBJS += merge-recursive.o LIB_OBJS += merge.o -LIB_OBJS += mergesort.o LIB_OBJS += midx.o LIB_OBJS += name-hash.o LIB_OBJS += negotiator/default.o @@ -1098,30 +1098,22 @@ static struct blame_entry *blame_merge(struct blame_entry *list1, } } -static void *get_next_blame(const void *p) -{ - return ((struct blame_entry *)p)->next; -} - -static void set_next_blame(void *p1, void *p2) -{ - ((struct blame_entry *)p1)->next = p2; -} +DEFINE_LIST_SORT(static, sort_blame_entries, struct blame_entry, next); /* * Final image line numbers are all different, so we don't need a * three-way comparison here. */ -static int compare_blame_final(const void *p1, const void *p2) +static int compare_blame_final(const struct blame_entry *e1, + const struct blame_entry *e2) { - return ((struct blame_entry *)p1)->lno > ((struct blame_entry *)p2)->lno - ? 1 : -1; + return e1->lno > e2->lno ? 1 : -1; } -static int compare_blame_suspect(const void *p1, const void *p2) +static int compare_blame_suspect(const struct blame_entry *s1, + const struct blame_entry *s2) { - const struct blame_entry *s1 = p1, *s2 = p2; /* * to allow for collating suspects, we sort according to the * respective pointer value as the primary sorting criterion. @@ -1138,8 +1130,7 @@ static int compare_blame_suspect(const void *p1, const void *p2) void blame_sort_final(struct blame_scoreboard *sb) { - sb->ent = llist_mergesort(sb->ent, get_next_blame, set_next_blame, - compare_blame_final); + sort_blame_entries(&sb->ent, compare_blame_final); } static int compare_commits_by_reverse_commit_date(const void *a, @@ -1964,9 +1955,7 @@ static void pass_blame_to_parent(struct blame_scoreboard *sb, parent, target, 0); *d.dstq = NULL; if (ignore_diffs) - newdest = llist_mergesort(newdest, get_next_blame, - set_next_blame, - compare_blame_suspect); + sort_blame_entries(&newdest, compare_blame_suspect); queue_blames(sb, parent, newdest); return; @@ -2383,8 +2372,7 @@ static int num_scapegoats(struct rev_info *revs, struct commit *commit, int reve */ static void distribute_blame(struct blame_scoreboard *sb, struct blame_entry *blamed) { - blamed = llist_mergesort(blamed, get_next_blame, set_next_blame, - compare_blame_suspect); + sort_blame_entries(&blamed, compare_blame_suspect); while (blamed) { struct blame_origin *porigin = blamed->suspect; @@ -642,10 +642,11 @@ struct commit_list * commit_list_insert_by_date(struct commit *item, struct comm return commit_list_insert(item, pp); } -static int commit_list_compare_by_date(const void *a, const void *b) +static int commit_list_compare_by_date(const struct commit_list *a, + const struct commit_list *b) { - timestamp_t a_date = ((const struct commit_list *)a)->item->date; - timestamp_t b_date = ((const struct commit_list *)b)->item->date; + timestamp_t a_date = a->item->date; + timestamp_t b_date = b->item->date; if (a_date < b_date) return 1; if (a_date > b_date) @@ -653,20 +654,11 @@ static int commit_list_compare_by_date(const void *a, const void *b) return 0; } -static void *commit_list_get_next(const void *a) -{ - return ((const struct commit_list *)a)->next; -} - -static void commit_list_set_next(void *a, void *next) -{ - ((struct commit_list *)a)->next = next; -} +DEFINE_LIST_SORT(static, commit_list_sort, struct commit_list, next); void commit_list_sort_by_date(struct commit_list **list) { - *list = llist_mergesort(*list, commit_list_get_next, commit_list_set_next, - commit_list_compare_by_date); + commit_list_sort(list, commit_list_compare_by_date); } struct commit *pop_most_recent_commit(struct commit_list **list, diff --git a/fetch-pack.c b/fetch-pack.c index cb6647d657..e4503774b5 100644 --- a/fetch-pack.c +++ b/fetch-pack.c @@ -26,6 +26,7 @@ #include "commit-reach.h" #include "commit-graph.h" #include "sigchain.h" +#include "mergesort.h" static int transfer_unpack_limit = -1; static int fetch_unpack_limit = -1; @@ -1025,6 +1026,13 @@ static int get_pack(struct fetch_pack_args *args, return 0; } +static int ref_compare_name(const struct ref *a, const struct ref *b) +{ + return strcmp(a->name, b->name); +} + +DEFINE_LIST_SORT(static, sort_ref_list, struct ref, next); + static int cmp_ref_by_name(const void *a_, const void *b_) { const struct ref *a = *((const struct ref **)a_); diff --git a/mergesort.c b/mergesort.c deleted file mode 100644 index bd9c6ef8ee..0000000000 --- a/mergesort.c +++ /dev/null @@ -1,84 +0,0 @@ -#include "cache.h" -#include "mergesort.h" - -/* Combine two sorted lists. Take from `list` on equality. */ -static void *llist_merge(void *list, void *other, - void *(*get_next_fn)(const void *), - void (*set_next_fn)(void *, void *), - int (*compare_fn)(const void *, const void *)) -{ - void *result = list, *tail; - - if (compare_fn(list, other) > 0) { - result = other; - goto other; - } - for (;;) { - do { - tail = list; - list = get_next_fn(list); - if (!list) { - set_next_fn(tail, other); - return result; - } - } while (compare_fn(list, other) <= 0); - set_next_fn(tail, other); - other: - do { - tail = other; - other = get_next_fn(other); - if (!other) { - set_next_fn(tail, list); - return result; - } - } while (compare_fn(list, other) > 0); - set_next_fn(tail, list); - } -} - -/* - * Perform an iterative mergesort using an array of sublists. - * - * n is the number of items. - * ranks[i] is undefined if n & 2^i == 0, and assumed empty. - * ranks[i] contains a sublist of length 2^i otherwise. - * - * The number of bits in a void pointer limits the number of objects - * that can be created, and thus the number of array elements necessary - * to be able to sort any valid list. - * - * Adding an item to this array is like incrementing a binary number; - * positional values for set bits correspond to sublist lengths. - */ -void *llist_mergesort(void *list, - void *(*get_next_fn)(const void *), - void (*set_next_fn)(void *, void *), - int (*compare_fn)(const void *, const void *)) -{ - void *ranks[bitsizeof(void *)]; - size_t n = 0; - int i; - - while (list) { - void *next = get_next_fn(list); - if (next) - set_next_fn(list, NULL); - for (i = 0; n & ((size_t)1 << i); i++) - list = llist_merge(ranks[i], list, get_next_fn, - set_next_fn, compare_fn); - n++; - ranks[i] = list; - list = next; - } - - for (i = 0; n; i++, n >>= 1) { - if (!(n & 1)) - continue; - if (list) - list = llist_merge(ranks[i], list, get_next_fn, - set_next_fn, compare_fn); - else - list = ranks[i]; - } - return list; -} diff --git a/mergesort.h b/mergesort.h index 644cff1f96..7c36f08bd5 100644 --- a/mergesort.h +++ b/mergesort.h @@ -1,17 +1,105 @@ #ifndef MERGESORT_H #define MERGESORT_H +/* Combine two sorted lists. Take from `list` on equality. */ +#define DEFINE_LIST_MERGE_INTERNAL(name, type) \ +static type *name##__merge(type *list, type *other, \ + int (*compare_fn)(const type *, const type *))\ +{ \ + type *result = list, *tail; \ + int prefer_list = compare_fn(list, other) <= 0; \ + \ + if (!prefer_list) { \ + result = other; \ + SWAP(list, other); \ + } \ + for (;;) { \ + do { \ + tail = list; \ + list = name##__get_next(list); \ + if (!list) { \ + name##__set_next(tail, other); \ + return result; \ + } \ + } while (compare_fn(list, other) < prefer_list); \ + name##__set_next(tail, other); \ + prefer_list ^= 1; \ + SWAP(list, other); \ + } \ +} + /* - * Sort linked list in place. - * - get_next_fn() returns the next element given an element of a linked list. - * - set_next_fn() takes two elements A and B, and makes B the "next" element - * of A on the list. - * - compare_fn() takes two elements A and B, and returns negative, 0, positive - * as the same sign as "subtracting" B from A. + * Perform an iterative mergesort using an array of sublists. + * + * n is the number of items. + * ranks[i] is undefined if n & 2^i == 0, and assumed empty. + * ranks[i] contains a sublist of length 2^i otherwise. + * + * The number of bits in a void pointer limits the number of objects + * that can be created, and thus the number of array elements necessary + * to be able to sort any valid list. + * + * Adding an item to this array is like incrementing a binary number; + * positional values for set bits correspond to sublist lengths. */ -void *llist_mergesort(void *list, - void *(*get_next_fn)(const void *), - void (*set_next_fn)(void *, void *), - int (*compare_fn)(const void *, const void *)); +#define DEFINE_LIST_SORT_INTERNAL(scope, name, type) \ +scope void name(type **listp, \ + int (*compare_fn)(const type *, const type *)) \ +{ \ + type *list = *listp; \ + type *ranks[bitsizeof(type *)]; \ + size_t n = 0; \ + \ + if (!list) \ + return; \ + \ + for (;;) { \ + int i; \ + size_t m; \ + type *next = name##__get_next(list); \ + if (next) \ + name##__set_next(list, NULL); \ + for (i = 0, m = n;; i++, m >>= 1) { \ + if (m & 1) { \ + list = name##__merge(ranks[i], list, \ + compare_fn); \ + } else if (next) { \ + break; \ + } else if (!m) { \ + *listp = list; \ + return; \ + } \ + } \ + n++; \ + ranks[i] = list; \ + list = next; \ + } \ +} + +#define DECLARE_LIST_SORT(scope, name, type) \ +scope void name(type **listp, \ + int (*compare_fn)(const type *, const type *)) + +#define DEFINE_LIST_SORT_DEBUG(scope, name, type, next_member, \ + on_get_next, on_set_next) \ + \ +static inline type *name##__get_next(const type *elem) \ +{ \ + on_get_next; \ + return elem->next_member; \ +} \ + \ +static inline void name##__set_next(type *elem, type *next) \ +{ \ + on_set_next; \ + elem->next_member = next; \ +} \ + \ +DEFINE_LIST_MERGE_INTERNAL(name, type) \ +DEFINE_LIST_SORT_INTERNAL(scope, name, type) \ +DECLARE_LIST_SORT(scope, name, type) + +#define DEFINE_LIST_SORT(scope, name, type, next_member) \ +DEFINE_LIST_SORT_DEBUG(scope, name, type, next_member, (void)0, (void)0) #endif diff --git a/packfile.c b/packfile.c index ed69fe457b..6b0eb9048e 100644 --- a/packfile.c +++ b/packfile.c @@ -941,20 +941,10 @@ unsigned long repo_approximate_object_count(struct repository *r) return r->objects->approximate_object_count; } -static void *get_next_packed_git(const void *p) -{ - return ((const struct packed_git *)p)->next; -} - -static void set_next_packed_git(void *p, void *next) -{ - ((struct packed_git *)p)->next = next; -} +DEFINE_LIST_SORT(static, sort_packs, struct packed_git, next); -static int sort_pack(const void *a_, const void *b_) +static int sort_pack(const struct packed_git *a, const struct packed_git *b) { - const struct packed_git *a = a_; - const struct packed_git *b = b_; int st; /* @@ -981,9 +971,7 @@ static int sort_pack(const void *a_, const void *b_) static void rearrange_packed_git(struct repository *r) { - r->objects->packed_git = llist_mergesort( - r->objects->packed_git, get_next_packed_git, - set_next_packed_git, sort_pack); + sort_packs(&r->objects->packed_git, sort_pack); } static void prepare_packed_git_mru(struct repository *r) @@ -11,7 +11,6 @@ #include "dir.h" #include "tag.h" #include "string-list.h" -#include "mergesort.h" #include "strvec.h" #include "commit-reach.h" #include "advice.h" @@ -1082,27 +1081,6 @@ void free_refs(struct ref *ref) } } -int ref_compare_name(const void *va, const void *vb) -{ - const struct ref *a = va, *b = vb; - return strcmp(a->name, b->name); -} - -static void *ref_list_get_next(const void *a) -{ - return ((const struct ref *)a)->next; -} - -static void ref_list_set_next(void *a, void *next) -{ - ((struct ref *)a)->next = next; -} - -void sort_ref_list(struct ref **l, int (*cmp)(const void *, const void *)) -{ - *l = llist_mergesort(*l, ref_list_get_next, ref_list_set_next, cmp); -} - int count_refspec_match(const char *pattern, struct ref *refs, struct ref **matched_ref) @@ -207,9 +207,7 @@ struct ref *find_ref_by_name(const struct ref *list, const char *name); struct ref *alloc_ref(const char *name); struct ref *copy_ref(const struct ref *ref); struct ref *copy_ref_list(const struct ref *ref); -void sort_ref_list(struct ref **, int (*cmp)(const void *, const void *)); int count_refspec_match(const char *, struct ref *refs, struct ref **matched_ref); -int ref_compare_name(const void *, const void *); int check_ref_type(const struct ref *ref, int flags); diff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c index ebf68f7de8..202e54a7ff 100644 --- a/t/helper/test-mergesort.c +++ b/t/helper/test-mergesort.c @@ -13,19 +13,10 @@ struct line { struct line *next; }; -static void *get_next(const void *a) -{ - return ((const struct line *)a)->next; -} - -static void set_next(void *a, void *b) -{ - ((struct line *)a)->next = b; -} +DEFINE_LIST_SORT(static, sort_lines, struct line, next); -static int compare_strings(const void *a, const void *b) +static int compare_strings(const struct line *x, const struct line *y) { - const struct line *x = a, *y = b; return strcmp(x->text, y->text); } @@ -47,7 +38,7 @@ static int sort_stdin(void) p = line; } - lines = llist_mergesort(lines, get_next, set_next, compare_strings); + sort_lines(&lines, compare_strings); while (lines) { puts(lines->text); @@ -273,21 +264,11 @@ struct number { struct number *next; }; -static void *get_next_number(const void *a) -{ - stats.get_next++; - return ((const struct number *)a)->next; -} - -static void set_next_number(void *a, void *b) -{ - stats.set_next++; - ((struct number *)a)->next = b; -} +DEFINE_LIST_SORT_DEBUG(static, sort_numbers, struct number, next, + stats.get_next++, stats.set_next++); -static int compare_numbers(const void *av, const void *bv) +static int compare_numbers(const struct number *an, const struct number *bn) { - const struct number *an = av, *bn = bv; int a = an->value, b = bn->value; stats.compare++; return (a > b) - (a < b); @@ -325,8 +306,7 @@ static int test(const struct dist *dist, const struct mode *mode, int n, int m) *tail = NULL; stats.get_next = stats.set_next = stats.compare = 0; - list = llist_mergesort(list, get_next_number, set_next_number, - compare_numbers); + sort_numbers(&list, compare_numbers); QSORT(arr, n, compare_ints); for (i = 0, curr = list; i < n && curr; i++, curr = curr->next) { diff --git a/t/perf/p0071-sort.sh b/t/perf/p0071-sort.sh index ed366e2e12..ae4ddac864 100755 --- a/t/perf/p0071-sort.sh +++ b/t/perf/p0071-sort.sh @@ -40,11 +40,11 @@ done for file in unsorted sorted reversed do - test_perf "llist_mergesort() $file" " + test_perf "DEFINE_LIST_SORT $file" " test-tool mergesort sort <$file >actual " - test_expect_success "llist_mergesort() $file sorts like sort(1)" " + test_expect_success "DEFINE_LIST_SORT $file sorts like sort(1)" " test_cmp_bin sorted actual " done diff --git a/t/t0071-sort.sh b/t/t0071-sort.sh index 6f9a501c72..ba8ad1d1ca 100755 --- a/t/t0071-sort.sh +++ b/t/t0071-sort.sh @@ -5,7 +5,7 @@ test_description='verify sort functions' TEST_PASSES_SANITIZE_LEAK=true . ./test-lib.sh -test_expect_success 'llist_mergesort()' ' +test_expect_success 'DEFINE_LIST_SORT_DEBUG' ' test-tool mergesort test ' |