[PATCH v2 20/21] bisect: compute best bisection in compute_relevant_weights()

[Stephan Beyer <s-beyer@gmx.net>]

This commit gets rid of the O(#commits) extra overhead of
the best_bisection() function.

Signed-off-by: Stephan Beyer <s-beyer@gmx.net>
---

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