This commit gets rid of the O(#commits) extra overhead of the best_bisection() function.
Signed-off-by: Stephan Beyer <[email protected]> --- Notes: I made the best_bisection structure be allocated on the heap because it will get free()d when the code is invoked by git rev-list --bisect ... The old code crashed in this case. bisect.c | 44 +++++++++++++++++++------------------------- 1 file changed, 19 insertions(+), 25 deletions(-) diff --git a/bisect.c b/bisect.c index 9487ba9..9f51d73 100644 --- a/bisect.c +++ b/bisect.c @@ -27,6 +27,8 @@ static int total; static unsigned marker; +static struct commit_list *best_bisection; + struct node_data { int weight; unsigned marked; @@ -73,6 +75,14 @@ static inline int distance_direction(struct commit *commit) return 0; } +static inline void update_best_bisection(struct commit *commit) +{ + if (distance_direction(commit) >= 0 + && node_data(commit)->weight > node_data(best_bisection->item)->weight) { + best_bisection->item = commit; + } +} + static int compute_weight(struct commit *elem) { int nr = 0; @@ -153,29 +163,6 @@ static void show_list(const char *debug, int counted, } #endif /* DEBUG_BISECT */ -static struct commit_list *best_bisection(struct commit_list *list) -{ - struct commit_list *p, *best; - int best_distance = -1; - - best = list; - for (p = list; p; p = p->next) { - int distance; - unsigned flags = p->item->object.flags; - - if (flags & TREESAME) - continue; - distance = get_distance(p->item); - if (distance > best_distance) { - best = p; - best_distance = distance; - } - } - - best->next = NULL; - return best; -} - struct commit_dist { struct commit *commit; int distance; @@ -402,6 +389,8 @@ static void traversal_up_to_merges(struct commit_list *queue, } } } + + update_best_bisection(top); } } @@ -457,8 +446,10 @@ static inline int find_new_queue_from_merges(struct commit_list **queue, static inline void compute_merge_weights(struct commit_list *merges) { struct commit_list *p; - for (p = merges; p; p = p->next) + for (p = merges; p; p = p->next) { compute_weight(p->item); + update_best_bisection(p->item); + } } static void bottom_up_traversal(struct commit_list *queue) @@ -490,6 +481,9 @@ static void compute_relevant_weights(struct commit_list *list, struct commit_list *p; struct commit_list *sources = build_reversed_dag(list, weights); + best_bisection = (struct commit_list *)xcalloc(1, sizeof(*best_bisection)); + best_bisection->item = sources->item; + for (p = sources; p; p = p->next) node_data(p->item)->weight = 1; bottom_up_traversal(sources); @@ -543,7 +537,7 @@ struct commit_list *find_bisection(struct commit_list *list, } else { int i; compute_relevant_weights(list, weights); - best = best_bisection(list); + best = best_bisection; for (i = 0; i < on_list; i++) /* cleanup */ free_commit_list(weights[i].children); } -- 2.8.1.137.g522756c -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html
