rev-list: call new "filter_skip" function

This patch implements a new "filter_skip" function in C in
"bisect.c" that will later replace the existing implementation in
shell in "git-bisect.sh".

An array is used to store the skipped commits. But the array is
not yet fed anything.

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

3 files changed, 93 insertions, 6 deletions

diff --git a/bisect.c b/bisect.c
index 27def7dacf..9178a7a8e2 100644
--- a/bisect.c
+++ b/bisect.c
@@ -4,6 +4,9 @@
 #include "revision.h"
 #include "bisect.h"
 
+static unsigned char (*skipped_sha1)[20];
+static int skipped_sha1_nr;
+
 /* bits #0-15 in revision.h */
 
 #define COUNTED		(1u<<16)
@@ -386,3 +389,63 @@ struct commit_list *find_bisection(struct commit_list *list,
 	return best;
 }
 
+static int skipcmp(const void *a, const void *b)
+{
+	return hashcmp(a, b);
+}
+
+static void prepare_skipped(void)
+{
+	qsort(skipped_sha1, skipped_sha1_nr, sizeof(*skipped_sha1), skipcmp);
+}
+
+static int lookup_skipped(unsigned char *sha1)
+{
+	int lo, hi;
+	lo = 0;
+	hi = skipped_sha1_nr;
+	while (lo < hi) {
+		int mi = (lo + hi) / 2;
+		int cmp = hashcmp(sha1, skipped_sha1[mi]);
+		if (!cmp)
+			return mi;
+		if (cmp < 0)
+			hi = mi;
+		else
+			lo = mi + 1;
+	}
+	return -lo - 1;
+}
+
+struct commit_list *filter_skipped(struct commit_list *list,
+				   struct commit_list **tried,
+				   int show_all)
+{
+	struct commit_list *filtered = NULL, **f = &filtered;
+
+	*tried = NULL;
+
+	if (!skipped_sha1_nr)
+		return list;
+
+	prepare_skipped();
+
+	while (list) {
+		struct commit_list *next = list->next;
+		list->next = NULL;
+		if (0 <= lookup_skipped(list->item->object.sha1)) {
+			/* Move current to tried list */
+			*tried = list;
+			tried = &list->next;
+		} else {
+			if (!show_all)
+				return list;
+			/* Move current to filtered list */
+			*f = list;
+			f = &list->next;
+		}
+		list = next;
+	}
+
+	return filtered;
+}
diff --git a/bisect.h b/bisect.h
index 31c99fe5f4..2489630da0 100644
--- a/bisect.h
+++ b/bisect.h
@@ -5,7 +5,11 @@ extern struct commit_list *find_bisection(struct commit_list *list,
 					  int *reaches, int *all,
 					  int find_all);
 
+extern struct commit_list *filter_skipped(struct commit_list *list,
+					  struct commit_list **tried,
+					  int show_all);
+
 extern int show_bisect_vars(struct rev_info *revs, int reaches, int all,
-			    int show_all);
+			    int show_all, int show_tried);
 
 #endif
diff --git a/builtin-rev-list.c b/builtin-rev-list.c
index cdb0f9d913..925d64356c 100644
--- a/builtin-rev-list.c
+++ b/builtin-rev-list.c
@@ -226,14 +226,28 @@ static int estimate_bisect_steps(int all)
 	return (e < 3 * x) ? n : n - 1;
 }
 
-int show_bisect_vars(struct rev_info *revs, int reaches, int all, int show_all)
+static void show_tried_revs(struct commit_list *tried)
+{
+	printf("bisect_tried='");
+	for (;tried; tried = tried->next) {
+		char *format = tried->next ? "%s|" : "%s";
+		printf(format, sha1_to_hex(tried->item->object.sha1));
+	}
+	printf("'\n");
+}
+
+int show_bisect_vars(struct rev_info *revs, int reaches, int all,
+		     int show_all, int show_tried)
 {
 	int cnt;
-	char hex[41];
+	char hex[41] = "";
+	struct commit_list *tried;
 
-	if (!revs->commits)
+	if (!revs->commits && !show_tried)
 		return 1;
 
+	revs->commits = filter_skipped(revs->commits, &tried, show_all);
+
 	/*
 	 * revs->commits can reach "reaches" commits among
 	 * "all" commits.  If it is good, then there are
@@ -247,13 +261,16 @@ int show_bisect_vars(struct rev_info *revs, int reaches, int all, int show_all)
 	if (cnt < reaches)
 		cnt = reaches;
 
-	strcpy(hex, sha1_to_hex(revs->commits->item->object.sha1));
+	if (revs->commits)
+		strcpy(hex, sha1_to_hex(revs->commits->item->object.sha1));
 
 	if (show_all) {
 		traverse_commit_list(revs, show_commit, show_object);
 		printf("------\n");
 	}
 
+	if (show_tried)
+		show_tried_revs(tried);
 	printf("bisect_rev=%s\n"
 	       "bisect_nr=%d\n"
 	       "bisect_good=%d\n"
@@ -278,6 +295,7 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
 	int bisect_list = 0;
 	int bisect_show_vars = 0;
 	int bisect_find_all = 0;
+	int bisect_show_all = 0;
 	int quiet = 0;
 
 	git_config(git_default_config, NULL);
@@ -305,6 +323,7 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
 		if (!strcmp(arg, "--bisect-all")) {
 			bisect_list = 1;
 			bisect_find_all = 1;
+			bisect_show_all = 1;
 			revs.show_decorations = 1;
 			continue;
 		}
@@ -357,9 +376,10 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
 
 		revs.commits = find_bisection(revs.commits, &reaches, &all,
 					      bisect_find_all);
+
 		if (bisect_show_vars)
 			return show_bisect_vars(&revs, reaches, all,
-						bisect_find_all);
+						bisect_show_all, 0);
 	}
 
 	traverse_commit_list(&revs,