From fbc08ea177f8284d10c62ad39de51edb21af88b0 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Ren=C3=A9=20Scharfe?= 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 +++++++++++++++ 1 file changed, 15 insertions(+) (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; -- cgit v1.2.3