summaryrefslogtreecommitdiff
path: root/builtin-rev-list.c
diff options
context:
space:
mode:
authorJunio C Hamano <junkio@cox.net>2007-03-23 07:40:54 (GMT)
committerJunio C Hamano <junkio@cox.net>2007-03-24 06:38:32 (GMT)
commit2a4646904a3766abeca7741f15a481d79e97e9e7 (patch)
tree5fa67983978a16bc1e29f9fbd3ba4a7cdb4418c1 /builtin-rev-list.c
parent1c2c6112a4bf655faa768ddfca067945edf2809e (diff)
downloadgit-2a4646904a3766abeca7741f15a481d79e97e9e7.zip
git-2a4646904a3766abeca7741f15a481d79e97e9e7.tar.gz
git-2a4646904a3766abeca7741f15a481d79e97e9e7.tar.bz2
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>
Diffstat (limited to 'builtin-rev-list.c')
-rw-r--r--builtin-rev-list.c32
1 files changed, 26 insertions, 6 deletions
diff --git a/builtin-rev-list.c b/builtin-rev-list.c
index 09e3a60..7075548 100644
--- 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;
}
+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)
{
@@ -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? */
- distance *= 2;
- if (nr == distance || (nr+1) == distance) {
+ if (halfway(p, distance, nr)) {
p->next = NULL;
- *reaches = weight(p);
+ *reaches = distance;
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? */
- distance = weight(p) * 2;
- if (nr == distance || (nr+1) == distance) {
+ distance = weight(p);
+ if (halfway(p, distance, nr)) {
p->next = NULL;
- *reaches = weight(p);
+ *reaches = distance;
free(weights);
return p;
}