This is a preparation commit with copy-and-paste involved. The function do_find_bisection() is changed and copied to two almost similar functions compute_all_weights() and compute_relevant_weights().
The function compute_relevant_weights() stops when a "halfway" commit is found. To keep the code clean, the halfway commit is not returned and has to be found by best_bisection() afterwards. This results in a singular additional O(#commits)-time overhead but this will be outweighed by the following changes to compute_relevant_weights(). It is necessary to keep compute_all_weights() for the "git rev-list --bisect-all" command. All other bisect-related commands will use compute_relevant_weights(). Signed-off-by: Stephan Beyer <s-be...@gmx.net> --- bisect.c | 116 ++++++++++++++++++++++++++++++++++++++++++++++++++++----------- 1 file changed, 97 insertions(+), 19 deletions(-) diff --git a/bisect.c b/bisect.c index a254f28..c6bad43 100644 --- a/bisect.c +++ b/bisect.c @@ -179,6 +179,7 @@ static struct commit_list *best_bisection(struct commit_list *list) } } + best->next = NULL; return best; } @@ -245,9 +246,8 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list) * unknown. After running compute_weight() first, they will get zero * or positive distance. */ -static struct commit_list *do_find_bisection(struct commit_list *list, - struct node_data *weights, - int find_all) +static void compute_all_weights(struct commit_list *list, + struct node_data *weights) { int n, counted; struct commit_list *p; @@ -301,10 +301,88 @@ static struct commit_list *do_find_bisection(struct commit_list *list, if (!(p->item->object.flags & UNINTERESTING) && (node_data(p->item)->weight == -2)) { compute_weight(p->item); + counted++; + } + } + + show_list("bisection 2 compute_weight", counted, list); + + while (counted < total) { + for (p = list; p; p = p->next) { + struct commit_list *q; + unsigned flags = p->item->object.flags; + + if (0 <= node_data(p->item)->weight) + continue; + for (q = p->item->parents; q; q = q->next) { + if (q->item->object.flags & UNINTERESTING) + continue; + if (0 <= node_data(q->item)->weight) + break; + } + if (!q) + continue; + + /* + * weight for p is unknown but q is known. + * add one for p itself if p is to be counted, + * otherwise inherit it from q directly. + */ + node_data(p->item)->weight = node_data(q->item)->weight; + if (!(flags & TREESAME)) { + node_data(p->item)->weight++; + counted++; + show_list("bisection 2 count one", + counted, list); + } + } + } + show_list("bisection 2 counted all", counted, list); +} + +/* At the moment this is basically the same as compute_all_weights() + * but with a halfway shortcut */ +static void compute_relevant_weights(struct commit_list *list, + struct node_data *weights) +{ + int n, counted; + struct commit_list *p; + + counted = 0; + + for (n = 0, p = list; p; p = p->next) { + struct commit *commit = p->item; + unsigned flags = commit->object.flags; + + commit->util = &weights[n++]; + switch (count_interesting_parents(commit)) { + case 0: + if (!(flags & TREESAME)) { + node_data(commit)->weight = 1; + counted++; + show_list("bisection 2 count one", + counted, list); + } + break; + case 1: + node_data(commit)->weight = -1; + break; + default: + node_data(commit)->weight = -2; + break; + } + } + + show_list("bisection 2 initialize", counted, list); + + for (p = list; p; p = p->next) { + if (!(p->item->object.flags & UNINTERESTING) + && (node_data(p->item)->weight == -2)) { + compute_weight(p->item); /* Does it happen to be at exactly half-way? */ - if (!find_all && halfway(p->item)) - return p; + if (halfway(p->item)) + return; counted++; } } @@ -341,17 +419,11 @@ static struct commit_list *do_find_bisection(struct commit_list *list, } /* Does it happen to be at exactly half-way? */ - if (!find_all && halfway(p->item)) - return p; + if (halfway(p->item)) + return; } } - show_list("bisection 2 counted all", counted, list); - - if (!find_all) - return best_bisection(list); - else - return best_bisection_sorted(list); } struct commit_list *find_bisection(struct commit_list *list, @@ -365,6 +437,9 @@ struct commit_list *find_bisection(struct commit_list *list, total = 0; marker = 0; + if (!list) + return NULL; + show_list("bisection 2 entry", 0, list); /* @@ -391,13 +466,16 @@ struct commit_list *find_bisection(struct commit_list *list, *all = total; weights = (struct node_data *)xcalloc(on_list, sizeof(*weights)); - /* Do the real work of finding bisection commit. */ - best = do_find_bisection(list, weights, find_all); - if (best) { - if (!find_all) - best->next = NULL; - *reaches = node_data(best->item)->weight; + if (find_all) { + compute_all_weights(list, weights); + best = best_bisection_sorted(list); + } else { + compute_relevant_weights(list, weights); + best = best_bisection(list); } + assert(best); + *reaches = node_data(best->item)->weight; + free(weights); return best; -- 2.8.1.137.g522756c -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html