[PATCH v2 12/21] bisect: replace clear_distance() by unique markers

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

clear_distance() was a O(#commits)-time function to clear the COUNTED
flag from commits counted in count_distance().
The functions count_distance() and clear_distance() were called for
each merge commit.

This commit gets rid of the clear_distance() function by making
count_distance() use unique marker ids that do not need to be
cleared afterwards. This speeds up the bisecting process on
large repositories with a huge amount of merges.

Signed-off-by: Stephan Beyer <s-beyer@gmx.net>
---
 bisect.c | 29 +++++++++++------------------
 1 file changed, 11 insertions(+), 18 deletions(-)

diff --git a/bisect.c b/bisect.c
index bc1bfbd..4209c75 100644
--- a/bisect.c
+++ b/bisect.c
@@ -23,13 +23,13 @@ static const char *argv_show_branch[] = {"show-branch", NULL, NULL};
 static const char *term_bad;
 static const char *term_good;
 
+static unsigned marker;
+
 struct node_data {
 	int weight;
+	unsigned marked;
 };
 
-/* Remember to update object flag allocation in object.h */
-#define COUNTED		(1u<<16)
-
 #define DEBUG_BISECT 0
 
 static inline struct node_data *node_data(struct commit *elem)
@@ -43,15 +43,17 @@ static int count_distance(struct commit_list *entry)
 	int nr = 0;
 	struct commit_list *todo = NULL;
 	commit_list_append(entry->item, &todo);
+	marker++;
 
 	while (todo) {
 		struct commit *commit = pop_commit(&todo);
 
-		if (!(commit->object.flags & (UNINTERESTING | COUNTED))) {
+		if (!(commit->object.flags & UNINTERESTING)
+		 && node_data(commit)->marked != marker) {
 			struct commit_list *p;
 			if (!(commit->object.flags & TREESAME))
 				nr++;
-			commit->object.flags |= COUNTED;
+			node_data(commit)->marked = marker;
 
 			for (p = commit->parents; p; p = p->next) {
 				commit_list_insert(p->item, &todo);
@@ -62,15 +64,6 @@ static int count_distance(struct commit_list *entry)
 	return nr;
 }
 
-static void clear_distance(struct commit_list *list)
-{
-	while (list) {
-		struct commit *commit = list->item;
-		commit->object.flags &= ~COUNTED;
-		list = list->next;
-	}
-}
-
 static int count_interesting_parents(struct commit *commit)
 {
 	struct commit_list *p;
@@ -123,10 +116,9 @@ static void show_list(const char *debug, int counted, int nr,
 		const char *subject_start;
 		int subject_len;
 
-		fprintf(stderr, "%c%c%c ",
+		fprintf(stderr, "%c%c ",
 			(flags & TREESAME) ? ' ' : 'T',
-			(flags & UNINTERESTING) ? 'U' : ' ',
-			(flags & COUNTED) ? 'C' : ' ');
+			(flags & UNINTERESTING) ? 'U' : ' ');
 		if (commit->util)
 			fprintf(stderr, "%3d", node_data(commit)->weight);
 		else
@@ -289,7 +281,6 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 		if (!(p->item->object.flags & UNINTERESTING)
 		 && (node_data(p->item)->weight == -2)) {
 			node_data(p->item)->weight = count_distance(p);
-			clear_distance(list);
 
 			/* Does it happen to be at exactly half-way? */
 			if (!find_all && halfway(p, nr))
@@ -351,6 +342,8 @@ struct commit_list *find_bisection(struct commit_list *list,
 	struct commit_list *p, *best, *next, *last;
 	struct node_data *weights;
 
+	marker = 0;
+
 	show_list("bisection 2 entry", 0, 0, list);
 
 	/*
-- 
2.8.1.137.g522756c