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

Reply via email to