The ref_newer method is used by 'git push' to detect if a force-push is
requried. This method does not use any kind of cutoff when walking, so
in the case of a force-push will walk all reachable commits.
The is_descendant_of method already uses paint_down_to_common along with
cutoffs. By translating the ref_newer arguments into the commit and
commit_list required by is_descendant_of, we can have one fewer commit
walk and also improve our performance!
For a copy of the Linux repository, 'test-tool reach ref_newer' presents
the following improvements with the specified input.
Input
-----
A:v4.9
B:v3.19
Before: 0.11 s
After: 0.10 s
To test the negative case, add a new commit with parent v3.19,
regenerate the commit-graph, and then run with B pointing at that
commit.
Before: 0.52 s
After: 0.12 s
Signed-off-by: Derrick Stolee <dstolee@xxxxxxxxxxxxx>
---
commit-reach.c | 17 ++++-------------
commit.c | 7 +++++--
commit.h | 6 +++++-
fetch-pack.c | 3 ++-
sha1-name.c | 3 ++-
walker.c | 3 ++-
6 files changed, 20 insertions(+), 19 deletions(-)
diff --git a/commit-reach.c b/commit-reach.c
index 8e24455d9f..249e9a4fac 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -376,7 +376,7 @@ int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid)
{
struct object *o;
struct commit *old_commit, *new_commit;
- struct commit_list *list, *used;
+ struct commit_list *list = NULL;
int found = 0;
/*
@@ -396,18 +396,9 @@ int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid)
if (parse_commit(new_commit) < 0)
return 0;
- used = list = NULL;
- commit_list_insert(new_commit, &list);
- while (list) {
- new_commit = pop_most_recent_commit(&list, TMP_MARK);
- commit_list_insert(new_commit, &used);
- if (new_commit == old_commit) {
- found = 1;
- break;
- }
- }
- unmark_and_free(list, TMP_MARK);
- unmark_and_free(used, TMP_MARK);
+ commit_list_insert(old_commit, &list);
+ found = is_descendant_of(new_commit, list);
+ free_commit_list(list);
return found;
}
diff --git a/commit.c b/commit.c
index d4ddaf4879..9870682673 100644
--- a/commit.c
+++ b/commit.c
@@ -556,7 +556,8 @@ void commit_list_sort_by_date(struct commit_list **list)
}
struct commit *pop_most_recent_commit(struct commit_list **list,
- unsigned int mark)
+ unsigned int mark,
+ uint32_t min_generation)
{
struct commit *ret = pop_commit(list);
struct commit_list *parents = ret->parents;
@@ -565,7 +566,9 @@ struct commit *pop_most_recent_commit(struct commit_list **list,
struct commit *commit = parents->item;
if (!parse_commit(commit) && !(commit->object.flags & mark)) {
commit->object.flags |= mark;
- commit_list_insert_by_date(commit, list);
+
+ if (commit->generation >= min_generation)
+ commit_list_insert_by_date(commit, list);
}
parents = parents->next;
}
diff --git a/commit.h b/commit.h
index 7e0f273720..5eaeded5e2 100644
--- a/commit.h
+++ b/commit.h
@@ -159,9 +159,13 @@ extern const char *skip_blank_lines(const char *msg);
/** Removes the first commit from a list sorted by date, and adds all
* of its parents.
+ *
+ * The parents are not added if their generation number is strictly
+ * lower than min_generation.
**/
struct commit *pop_most_recent_commit(struct commit_list **list,
- unsigned int mark);
+ unsigned int mark,
+ uint32_t min_generation);
struct commit *pop_commit(struct commit_list **stack);
diff --git a/fetch-pack.c b/fetch-pack.c
index a320ce9872..351e3d4bcd 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -600,7 +600,8 @@ static void mark_recent_complete_commits(struct fetch_pack_args *args,
while (complete && cutoff <= complete->item->date) {
print_verbose(args, _("Marking %s as complete"),
oid_to_hex(&complete->item->object.oid));
- pop_most_recent_commit(&complete, COMPLETE);
+ pop_most_recent_commit(&complete, COMPLETE,
+ GENERATION_NUMBER_ZERO);
}
}
diff --git a/sha1-name.c b/sha1-name.c
index 60d9ef3c7e..471a54464d 100644
--- a/sha1-name.c
+++ b/sha1-name.c
@@ -1141,7 +1141,8 @@ static int get_oid_oneline(const char *prefix, struct object_id *oid,
struct commit *commit;
int matches;
- commit = pop_most_recent_commit(&list, ONELINE_SEEN);
+ commit = pop_most_recent_commit(&list, ONELINE_SEEN,
+ GENERATION_NUMBER_ZERO);
if (!parse_object(&commit->object.oid))
continue;
buf = get_commit_buffer(commit, NULL);
diff --git a/walker.c b/walker.c
index 0b162a09b9..e243fc8768 100644
--- a/walker.c
+++ b/walker.c
@@ -78,7 +78,8 @@ static int process_commit(struct walker *walker, struct commit *commit)
return -1;
while (complete && complete->item->date >= commit->date) {
- pop_most_recent_commit(&complete, COMPLETE);
+ pop_most_recent_commit(&complete, COMPLETE,
+ GENERATION_NUMBER_ZERO);
}
if (commit->object.flags & COMPLETE)
--
2.18.0.118.gd4f65b8d14
