Commit 6f544140a097002fe5f15e43a4d3215c944140b7
2021-01-05T19:45:23
commit-graph: Introduce `git_commit_list_generation_cmp` This change makes calculations of merge-bases a bit faster when there are complex graphs and the commit times cause visiting nodes multiple times. This is done by visiting the nodes in the graph in reverse generation order when the generation number is available instead of commit timestamp. If the generation number is missing in any pair of commits, it can safely fall back to the old heuristic with no negative side-effects. Part of: #5757
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67
diff --git a/src/commit_list.c b/src/commit_list.c
index 11cc2e7..692b149 100644
--- a/src/commit_list.c
+++ b/src/commit_list.c
@@ -12,6 +12,24 @@
#include "odb.h"
#include "commit.h"
+int git_commit_list_generation_cmp(const void *a, const void *b)
+{
+ uint32_t generation_a = ((git_commit_list_node *) a)->generation;
+ uint32_t generation_b = ((git_commit_list_node *) b)->generation;
+
+ if (!generation_a || !generation_b) {
+ /* Fall back to comparing by timestamps if at least one commit lacks a generation. */
+ return git_commit_list_time_cmp(a, b);
+ }
+
+ if (generation_a < generation_b)
+ return 1;
+ if (generation_a > generation_b)
+ return -1;
+
+ return 0;
+}
+
int git_commit_list_time_cmp(const void *a, const void *b)
{
int64_t time_a = ((git_commit_list_node *) a)->time;
diff --git a/src/commit_list.h b/src/commit_list.h
index a323770..aad39f3 100644
--- a/src/commit_list.h
+++ b/src/commit_list.h
@@ -46,6 +46,7 @@ typedef struct git_commit_list {
} git_commit_list;
git_commit_list_node *git_commit_list_alloc_node(git_revwalk *walk);
+int git_commit_list_generation_cmp(const void *a, const void *b);
int git_commit_list_time_cmp(const void *a, const void *b);
void git_commit_list_free(git_commit_list **list_p);
git_commit_list *git_commit_list_insert(git_commit_list_node *item, git_commit_list **list_p);
diff --git a/src/graph.c b/src/graph.c
index df82f0f..45fae84 100644
--- a/src/graph.c
+++ b/src/graph.c
@@ -43,7 +43,7 @@ static int mark_parents(git_revwalk *walk, git_commit_list_node *one,
return 0;
}
- if (git_pqueue_init(&list, 0, 2, git_commit_list_time_cmp) < 0)
+ if (git_pqueue_init(&list, 0, 2, git_commit_list_generation_cmp) < 0)
return -1;
if (git_commit_list_parse(walk, one) < 0)
diff --git a/src/merge.c b/src/merge.c
index c29b40e..fe450b0 100644
--- a/src/merge.c
+++ b/src/merge.c
@@ -387,7 +387,7 @@ static int paint_down_to_common(
int error;
unsigned int i;
- if (git_pqueue_init(&list, 0, twos->length * 2, git_commit_list_time_cmp) < 0)
+ if (git_pqueue_init(&list, 0, twos->length * 2, git_commit_list_generation_cmp) < 0)
return -1;
one->flags |= PARENT1;