summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJunio C Hamano <gitster@pobox.com>2022-08-03 20:36:09 (GMT)
committerJunio C Hamano <gitster@pobox.com>2022-08-03 20:36:09 (GMT)
commit4e0d160bbc88c3486ff7ccae179e4730aab5dd28 (patch)
tree97786123608c06c4f2758c8c0396675e345d1201
parent87098a047be46ee69da056336109eee2139c1398 (diff)
parent0f1eb7d6e976c64c0016d4355200660ce2fdf1ec (diff)
downloadgit-4e0d160bbc88c3486ff7ccae179e4730aab5dd28.zip
git-4e0d160bbc88c3486ff7ccae179e4730aab5dd28.tar.gz
git-4e0d160bbc88c3486ff7ccae179e4730aab5dd28.tar.bz2
Merge branch 'rs/mergesort'
Make our mergesort implementation type-safe. * rs/mergesort: mergesort: remove llist_mergesort() packfile: use DEFINE_LIST_SORT fetch-pack: use DEFINE_LIST_SORT commit: use DEFINE_LIST_SORT blame: use DEFINE_LIST_SORT test-mergesort: use DEFINE_LIST_SORT test-mergesort: use DEFINE_LIST_SORT_DEBUG mergesort: add macros for typed sort of linked lists mergesort: tighten merge loop mergesort: unify ranks loops
-rw-r--r--Makefile1
-rw-r--r--blame.c30
-rw-r--r--commit.c20
-rw-r--r--fetch-pack.c8
-rw-r--r--mergesort.c84
-rw-r--r--mergesort.h108
-rw-r--r--packfile.c18
-rw-r--r--remote.c22
-rw-r--r--remote.h2
-rw-r--r--t/helper/test-mergesort.c34
-rwxr-xr-xt/perf/p0071-sort.sh4
-rwxr-xr-xt/t0071-sort.sh2
12 files changed, 134 insertions, 199 deletions
diff --git a/Makefile b/Makefile
index 1624471..2ec9b2d 100644
--- a/Makefile
+++ b/Makefile
@@ -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
diff --git a/blame.c b/blame.c
index da1052a..8bfeaa1 100644
--- a/blame.c
+++ b/blame.c
@@ -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;
diff --git a/commit.c b/commit.c
index 1fb1b2e..0db461f 100644
--- a/commit.c
+++ b/commit.c
@@ -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 cb6647d..e450377 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 bd9c6ef..0000000
--- 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 644cff1..7c36f08 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 ed69fe4..6b0eb90 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)
diff --git a/remote.c b/remote.c
index 1ee2b14..e90dca1 100644
--- a/remote.c
+++ b/remote.c
@@ -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)
diff --git a/remote.h b/remote.h
index 448675e..1c4621b 100644
--- a/remote.h
+++ b/remote.h
@@ -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 ebf68f7..202e54a 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 ed366e2..ae4ddac 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 6f9a501..ba8ad1d 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
'