From ba3ca1edce70d9d2d0eea1ac69377ae786e9413a Mon Sep 17 00:00:00 2001 From: Derrick Stolee Date: Fri, 20 Jul 2018 16:33:13 +0000 Subject: commit-reach: move can_all_from_reach_with_flags There are several commit walks in the codebase. Group them together into a new commit-reach.c file and corresponding header. After we group these walks into one place, we can reduce duplicate logic by calling equivalent methods. The can_all_from_reach_with_flags method is used in a stateful way by upload-pack.c. The parameters are very flexible, so we will be able to use its commit walking logic for many other callers. Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano diff --git a/commit-reach.c b/commit-reach.c index 01d796f..d806291 100644 --- a/commit-reach.c +++ b/commit-reach.c @@ -10,6 +10,7 @@ #include "commit-reach.h" /* Remember to update object flag allocation in object.h */ +#define REACHABLE (1u<<15) #define PARENT1 (1u<<16) #define PARENT2 (1u<<17) #define STALE (1u<<18) @@ -532,3 +533,65 @@ int commit_contains(struct ref_filter *filter, struct commit *commit, return contains_tag_algo(commit, list, cache) == CONTAINS_YES; return is_descendant_of(commit, list); } + +int reachable(struct commit *from, unsigned int with_flag, + unsigned int assign_flag, time_t min_commit_date) +{ + struct prio_queue work = { compare_commits_by_commit_date }; + + prio_queue_put(&work, from); + while (work.nr) { + struct commit_list *list; + struct commit *commit = prio_queue_get(&work); + + if (commit->object.flags & with_flag) { + from->object.flags |= assign_flag; + break; + } + if (!commit->object.parsed) + parse_object(the_repository, &commit->object.oid); + if (commit->object.flags & REACHABLE) + continue; + commit->object.flags |= REACHABLE; + if (commit->date < min_commit_date) + continue; + for (list = commit->parents; list; list = list->next) { + struct commit *parent = list->item; + if (!(parent->object.flags & REACHABLE)) + prio_queue_put(&work, parent); + } + } + from->object.flags |= REACHABLE; + clear_commit_marks(from, REACHABLE); + clear_prio_queue(&work); + return (from->object.flags & assign_flag); +} + +int can_all_from_reach_with_flag(struct object_array *from, + unsigned int with_flag, + unsigned int assign_flag, + time_t min_commit_date) +{ + int i; + + for (i = 0; i < from->nr; i++) { + struct object *from_one = from->objects[i].item; + + if (from_one->flags & assign_flag) + continue; + from_one = deref_tag(the_repository, from_one, "a from object", 0); + if (!from_one || from_one->type != OBJ_COMMIT) { + /* no way to tell if this is reachable by + * looking at the ancestry chain alone, so + * leave a note to ourselves not to worry about + * this object anymore. + */ + from->objects[i].item->flags |= assign_flag; + continue; + } + if (!reachable((struct commit *)from_one, with_flag, assign_flag, + min_commit_date)) + return 0; + } + return 1; +} diff --git a/commit-reach.h b/commit-reach.h index 13dec25..b28bc22 100644 --- a/commit-reach.h +++ b/commit-reach.h @@ -59,4 +59,18 @@ define_commit_slab(contains_cache, enum contains_result); int commit_contains(struct ref_filter *filter, struct commit *commit, struct commit_list *list, struct contains_cache *cache); +int reachable(struct commit *from, unsigned int with_flag, + unsigned int assign_flag, time_t min_commit_date); + +/* + * Determine if every commit in 'from' can reach at least one commit + * that is marked with 'with_flag'. As we traverse, use 'assign_flag' + * as a marker for commits that are already visited. Do not walk + * commits with date below 'min_commit_date'. + */ +int can_all_from_reach_with_flag(struct object_array *from, + unsigned int with_flag, + unsigned int assign_flag, + time_t min_commit_date); + #endif diff --git a/object.h b/object.h index 18c2b07..b132944 100644 --- a/object.h +++ b/object.h @@ -60,12 +60,12 @@ struct object_array { * revision.h: 0---------10 26 * fetch-pack.c: 0----5 * walker.c: 0-2 - * upload-pack.c: 4 11----------------19 + * upload-pack.c: 4 11-----14 16-----19 * builtin/blame.c: 12-13 * bisect.c: 16 * bundle.c: 16 * http-push.c: 16-----19 - * commit-reach.c: 16-----19 + * commit-reach.c: 15-------19 * sha1-name.c: 20 * list-objects-filter.c: 21 * builtin/fsck.c: 0--3 diff --git a/upload-pack.c b/upload-pack.c index 427de46..11c4266 100644 --- a/upload-pack.c +++ b/upload-pack.c @@ -24,13 +24,13 @@ #include "quote.h" #include "upload-pack.h" #include "serve.h" +#include "commit-reach.h" /* Remember to update object flag allocation in object.h */ #define THEY_HAVE (1u << 11) #define OUR_REF (1u << 12) #define WANTED (1u << 13) #define COMMON_KNOWN (1u << 14) -#define REACHABLE (1u << 15) #define SHALLOW (1u << 16) #define NOT_SHALLOW (1u << 17) @@ -336,74 +336,6 @@ static int got_oid(const char *hex, struct object_id *oid) return 0; } -static int reachable(struct commit *from, unsigned int with_flag, - unsigned int assign_flag, time_t min_commit_date) -{ - struct prio_queue work = { compare_commits_by_commit_date }; - - prio_queue_put(&work, from); - while (work.nr) { - struct commit_list *list; - struct commit *commit = prio_queue_get(&work); - - if (commit->object.flags & with_flag) { - from->object.flags |= assign_flag; - break; - } - if (!commit->object.parsed) - parse_object(the_repository, &commit->object.oid); - if (commit->object.flags & REACHABLE) - continue; - commit->object.flags |= REACHABLE; - if (commit->date < min_commit_date) - continue; - for (list = commit->parents; list; list = list->next) { - struct commit *parent = list->item; - if (!(parent->object.flags & REACHABLE)) - prio_queue_put(&work, parent); - } - } - from->object.flags |= REACHABLE; - clear_commit_marks(from, REACHABLE); - clear_prio_queue(&work); - return (from->object.flags & assign_flag); -} - -/* - * Determine if every commit in 'from' can reach at least one commit - * that is marked with 'with_flag'. As we traverse, use 'assign_flag' - * as a marker for commits that are already visited. Do not walk - * commits with date below 'min_commit_date'. - */ -static int can_all_from_reach_with_flag(struct object_array *from, - unsigned int with_flag, - unsigned int assign_flag, - time_t min_commit_date) -{ - int i; - - for (i = 0; i < from->nr; i++) { - struct object *from_one = from->objects[i].item; - - if (from_one->flags & assign_flag) - continue; - from_one = deref_tag(the_repository, from_one, "a from object", 0); - if (!from_one || from_one->type != OBJ_COMMIT) { - /* no way to tell if this is reachable by - * looking at the ancestry chain alone, so - * leave a note to ourselves not to worry about - * this object anymore. - */ - from->objects[i].item->flags |= assign_flag; - continue; - } - if (!reachable((struct commit *)from_one, with_flag, assign_flag, - min_commit_date)) - return 0; - } - return 1; -} - static int ok_to_give_up(void) { if (!have_obj.nr) -- cgit v0.10.2-6-g49f6