From 46905893b20ac2a044c06a0eecc12425a8405e69 Mon Sep 17 00:00:00 2001 From: René Scharfe Date: Sun, 1 Apr 2012 00:10:39 +0200 Subject: commit: use mergesort() in commit_list_sort_by_date() Replace the insertion sort in commit_list_sort_by_date() with a call to the generic mergesort function. This sets the stage for using commit_list_sort_by_date() for larger lists, as shown in the next patch. Signed-off-by: Rene Scharfe Signed-off-by: Junio C Hamano --- commit.c | 29 +++++++++++++++++++++++------ 1 file changed, 23 insertions(+), 6 deletions(-) (limited to 'commit.c') diff --git a/commit.c b/commit.c index 35af4988f0..b9ce569442 100644 --- a/commit.c +++ b/commit.c @@ -7,6 +7,7 @@ #include "revision.h" #include "notes.h" #include "gpg-interface.h" +#include "mergesort.h" int save_commit_buffer = 1; @@ -390,15 +391,31 @@ 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) +{ + unsigned long a_date = ((const struct commit_list *)a)->item->date; + unsigned long b_date = ((const struct commit_list *)b)->item->date; + if (a_date < b_date) + return 1; + if (a_date > b_date) + return -1; + 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; +} void commit_list_sort_by_date(struct commit_list **list) { - struct commit_list *ret = NULL; - while (*list) { - commit_list_insert_by_date((*list)->item, &ret); - *list = (*list)->next; - } - *list = ret; + *list = mergesort(*list, commit_list_get_next, commit_list_set_next, + commit_list_compare_by_date); } struct commit *pop_most_recent_commit(struct commit_list **list, -- cgit 1.2.3-korg From fbc08ea177f8284d10c62ad39de51edb21af88b0 Mon Sep 17 00:00:00 2001 From: René Scharfe Date: Sun, 1 Apr 2012 00:11:01 +0200 Subject: revision: insert unsorted, then sort in prepare_revision_walk() Speed up prepare_revision_walk() by adding commits without sorting to the commit_list and at the end sort the list in one go. Thanks to mergesort() working behind the scenes, this is a lot faster for large numbers of commits than the current insert sort. Also introduce and use commit_list_reverse(), to keep the ordering of commits sharing the same commit date unchanged. That's because commit_list_insert_by_date() sorts commits with descending date, but adds later entries with the same date entries last, while commit_list_insert() always inserts entries at the top. The following commit_list_sort_by_date() keeps the order of entries sharing the same date. Jeff's test case, in a repo with lots of refs, was to run: # make a new commit on top of HEAD, but not yet referenced sha1=`git commit-tree HEAD^{tree} -p HEAD Signed-off-by: Junio C Hamano --- commit.c | 15 +++++++++++++++ commit.h | 1 + revision.c | 4 +++- 3 files changed, 19 insertions(+), 1 deletion(-) (limited to 'commit.c') diff --git a/commit.c b/commit.c index b9ce569442..0759b2ca65 100644 --- a/commit.c +++ b/commit.c @@ -361,6 +361,21 @@ struct commit_list *commit_list_insert(struct commit *item, struct commit_list * return new_list; } +void commit_list_reverse(struct commit_list **list_p) +{ + struct commit_list *prev = NULL, *curr = *list_p, *next; + + if (!list_p) + return; + while (curr) { + next = curr->next; + curr->next = prev; + prev = curr; + curr = next; + } + *list_p = prev; +} + unsigned commit_list_count(const struct commit_list *l) { unsigned c = 0; diff --git a/commit.h b/commit.h index 154c0e34ff..f8d250d6f6 100644 --- a/commit.h +++ b/commit.h @@ -57,6 +57,7 @@ unsigned commit_list_count(const struct commit_list *l); struct commit_list *commit_list_insert_by_date(struct commit *item, struct commit_list **list); void commit_list_sort_by_date(struct commit_list **list); +void commit_list_reverse(struct commit_list **list_p); void free_commit_list(struct commit_list *list); diff --git a/revision.c b/revision.c index 064e351084..a75a1d7201 100644 --- a/revision.c +++ b/revision.c @@ -2054,11 +2054,13 @@ int prepare_revision_walk(struct rev_info *revs) if (commit) { if (!(commit->object.flags & SEEN)) { commit->object.flags |= SEEN; - commit_list_insert_by_date(commit, &revs->commits); + commit_list_insert(commit, &revs->commits); } } e++; } + commit_list_reverse(&revs->commits); + commit_list_sort_by_date(&revs->commits); if (!revs->leak_pending) free(list); -- cgit 1.2.3-korg From 7365c95d2d67cbbb74c2040918d2ecde06231d93 Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Tue, 17 Apr 2012 11:07:01 -0700 Subject: mergesort: rename it to llist_mergesort() Even though the function is generic enough, sort() inherits connotations from the standard function qsort() that sorts an array. Rename it to llist_mergesort() and describe the external interface in its header file. This incidentally avoids name clashes with mergesort() some platforms declare in, and contaminate user namespace with, their . Reported-by: Brian Gernhardt Signed-off-by: Junio C Hamano --- commit.c | 4 ++-- mergesort.c | 8 ++++---- mergesort.h | 16 ++++++++++++---- test-mergesort.c | 2 +- 4 files changed, 19 insertions(+), 11 deletions(-) (limited to 'commit.c') diff --git a/commit.c b/commit.c index 0759b2ca65..84304c00ff 100644 --- a/commit.c +++ b/commit.c @@ -429,8 +429,8 @@ static void commit_list_set_next(void *a, void *next) void commit_list_sort_by_date(struct commit_list **list) { - *list = mergesort(*list, commit_list_get_next, commit_list_set_next, - commit_list_compare_by_date); + *list = llist_mergesort(*list, commit_list_get_next, commit_list_set_next, + commit_list_compare_by_date); } struct commit *pop_most_recent_commit(struct commit_list **list, diff --git a/mergesort.c b/mergesort.c index d084c602d5..e5fdf2ee4a 100644 --- a/mergesort.c +++ b/mergesort.c @@ -23,10 +23,10 @@ static void *pop_item(struct mergesort_sublist *l, return p; } -void *mergesort(void *list, - void *(*get_next_fn)(const void *), - void (*set_next_fn)(void *, void *), - int (*compare_fn)(const void *, const void *)) +void *llist_mergesort(void *list, + void *(*get_next_fn)(const void *), + void (*set_next_fn)(void *, void *), + int (*compare_fn)(const void *, const void *)) { unsigned long l; diff --git a/mergesort.h b/mergesort.h index d6e5f4a732..644cff1f96 100644 --- a/mergesort.h +++ b/mergesort.h @@ -1,9 +1,17 @@ #ifndef MERGESORT_H #define MERGESORT_H -void *mergesort(void *list, - void *(*get_next_fn)(const void *), - void (*set_next_fn)(void *, void *), - int (*compare_fn)(const void *, const void *)); +/* + * 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. + */ +void *llist_mergesort(void *list, + void *(*get_next_fn)(const void *), + void (*set_next_fn)(void *, void *), + int (*compare_fn)(const void *, const void *)); #endif diff --git a/test-mergesort.c b/test-mergesort.c index 1dd82fd67f..3f388b4ce0 100644 --- a/test-mergesort.c +++ b/test-mergesort.c @@ -42,7 +42,7 @@ int main(int argc, const char **argv) p = line; } - lines = mergesort(lines, get_next, set_next, compare_strings); + lines = llist_mergesort(lines, get_next, set_next, compare_strings); while (lines) { printf("%s", lines->text); -- cgit 1.2.3-korg