rev-list --bisect: Fix "halfway" optimization.

If you have 5 commits in the set, commits that reach 2 or 3
commits are at halfway.  If you have 6 commits, only commits
that reach exactly 3 commits are at halfway.  The earlier one is
completely botched the math.

Signed-off-by: Junio C Hamano <junkio@cox.net>

diff --git a/builtin-rev-list.c b/builtin-rev-list.c
index 09e3a60bf6492a280baf4e09eaa29ede67c7c245..7075548e6b4d5e1c3c899e033339202d46726358 100644 (file)
--- a/builtin-rev-list.c
+++ b/builtin-rev-list.c
@@ -237,6 +237,27 @@ static int count_interesting_parents(struct commit_list *elem)
        return cnt;
 }
 
        return cnt;
 }
 

+static inline int halfway(struct commit_list *p, int distance, int nr)
+{
+       /*
+        * Don't short-cut something we are not going to return!
+        */
+       if (revs.prune_fn && !(p->item->object.flags & TREECHANGE))
+               return 0;
+
+       /*
+        * 2 and 3 are halfway of 5.
+        * 3 is halfway of 6 but 2 and 4 are not.
+        */
+       distance *= 2;
+       switch (distance - nr) {
+       case -1: case 0: case 1:
+               return 1;
+       default:
+               return 0;
+       }
+}
+

 static struct commit_list *find_bisection_2(struct commit_list *list,
                                            int *reaches, int *all)
 {
 static struct commit_list *find_bisection_2(struct commit_list *list,
                                            int *reaches, int *all)
 {


@@ -305,10 +326,9 @@ static struct commit_list *find_bisection_2(struct commit_list *list,
                weight_set(p, distance);
 
                /* Does it happen to be at exactly half-way? */
                weight_set(p, distance);
 
                /* Does it happen to be at exactly half-way? */

-               distance *= 2;
-               if (nr == distance || (nr+1) == distance) {
+               if (halfway(p, distance, nr)) {

                        p->next = NULL;
                        p->next = NULL;

-                       *reaches = weight(p);
+                       *reaches = distance;

                        free(weights);
                        return p;
                }
                        free(weights);
                        return p;
                }


@@ -330,10 +350,10 @@ static struct commit_list *find_bisection_2(struct commit_list *list,
                        counted++;
 
                        /* Does it happen to be at exactly half-way? */
                        counted++;
 
                        /* Does it happen to be at exactly half-way? */

-                       distance = weight(p) * 2;
-                       if (nr == distance || (nr+1) == distance) {
+                       distance = weight(p);
+                       if (halfway(p, distance, nr)) {

                                p->next = NULL;
                                p->next = NULL;

-                               *reaches = weight(p);
+                               *reaches = distance;

                                free(weights);
                                return p;
                        }
                                free(weights);
                                return p;
                        }