{"thread":{"id":"9327","subject":"[PATCH 3/4] Move some bisection code into best_bisection.","startedAt":"2007-07-31T12:48:35Z","lastAt":"2007-07-31T12:48:42Z","messageCount":3,"participants":["Christian Couder"],"isPatch":true,"patchVersion":1,"patchTotal":4},"messages":[{"id":"49218","messageId":"20070731144835.0cbca678.chriscool@tuxfamily.org","threadId":"9327","inReplyTo":"20070731143602.a5ed0a04.chriscool@tuxfamily.org","subject":"[PATCH 2/4] Move finding bisection into do_find_bisection.","fromName":"Christian Couder","fromEmail":"chriscool@tuxfamily.org","sentAt":"2007-07-31T12:48:35Z","receivedAt":"2007-07-31T12:48:35Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"This factorises some code and make a big function smaller.\n\nSigned-off-by: Christian Couder <chriscool@tuxfamily.org>\n---\n builtin-rev-list.c |   40 +++++++++++++++++++++++++---------------\n 1 files changed, 25 insertions(+), 15 deletions(-)\n\ndiff --git a/builtin-rev-list.c b/builtin-rev-list.c\nindex 5bcafe4..4e2524a 100644\n--- a/builtin-rev-list.c\n+++ b/builtin-rev-list.c\n@@ -255,6 +255,9 @@ static void show_list(const char *debug, int counted, int nr,\n }\n #endif /* DEBUG_BISECT */\n \n+static struct commit_list *do_find_bisection(struct commit_list *list,\n+\t\t\t\t\t     int nr, int *weights);\n+\n /*\n  * zero or positive weight is the number of interesting commits it can\n  * reach, including itself.  Especially, weight = 0 means it does not\n@@ -272,7 +275,7 @@ static void show_list(const char *debug, int counted, int nr,\n static struct commit_list *find_bisection(struct commit_list *list,\n \t\t\t\t\t  int *reaches, int *all)\n {\n-\tint n, nr, on_list, counted, distance;\n+\tint nr, on_list;\n \tstruct commit_list *p, *best, *next, *last;\n \tint *weights;\n \n@@ -301,6 +304,25 @@ static struct commit_list *find_bisection(struct commit_list *list,\n \n \t*all = nr;\n \tweights = xcalloc(on_list, sizeof(int));\n+\n+\t/* Do the real work of finding bisection commit. */\n+\tbest = do_find_bisection(list, nr, weights);\n+\n+\tif (best)\n+\t\tbest->next = NULL;\n+\n+\t*reaches = weight(best);\n+\tfree(weights);\n+\n+\treturn best;\n+}\n+\n+static struct commit_list *do_find_bisection(struct commit_list *list,\n+\t\t\t\t\t     int nr, int *weights)\n+{\n+\tint n, counted, distance;\n+\tstruct commit_list *p, *best;\n+\n \tcounted = 0;\n \n \tfor (n = 0, p = list; p; p = p->next) {\n@@ -357,12 +379,8 @@ static struct commit_list *find_bisection(struct commit_list *list,\n \t\tweight_set(p, distance);\n \n \t\t/* Does it happen to be at exactly half-way? */\n-\t\tif (halfway(p, distance, nr)) {\n-\t\t\tp->next = NULL;\n-\t\t\t*reaches = distance;\n-\t\t\tfree(weights);\n+\t\tif (halfway(p, distance, nr))\n \t\t\treturn p;\n-\t\t}\n \t\tcounted++;\n \t}\n \n@@ -400,12 +418,8 @@ static struct commit_list *find_bisection(struct commit_list *list,\n \n \t\t\t/* Does it happen to be at exactly half-way? */\n \t\t\tdistance = weight(p);\n-\t\t\tif (halfway(p, distance, nr)) {\n-\t\t\t\tp->next = NULL;\n-\t\t\t\t*reaches = distance;\n-\t\t\t\tfree(weights);\n+\t\t\tif (halfway(p, distance, nr))\n \t\t\t\treturn p;\n-\t\t\t}\n \t\t}\n \t}\n \n@@ -425,12 +439,8 @@ static struct commit_list *find_bisection(struct commit_list *list,\n \t\tif (distance > counted) {\n \t\t\tbest = p;\n \t\t\tcounted = distance;\n-\t\t\t*reaches = weight(p);\n \t\t}\n \t}\n-\tif (best)\n-\t\tbest->next = NULL;\n-\tfree(weights);\n \treturn best;\n }\n \n-- \n1.5.2.1.144.gabc40\n"},{"id":"49216","messageId":"20070731144837.3bb2c9eb.chriscool@tuxfamily.org","threadId":"9327","inReplyTo":"20070731143602.a5ed0a04.chriscool@tuxfamily.org","subject":"[PATCH 3/4] Move some bisection code into best_bisection.","fromName":"Christian Couder","fromEmail":"chriscool@tuxfamily.org","sentAt":"2007-07-31T12:48:37Z","receivedAt":"2007-07-31T12:48:37Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"Signed-off-by: Christian Couder <chriscool@tuxfamily.org>\n---\n builtin-rev-list.c |   19 +++++++++++++++----\n 1 files changed, 15 insertions(+), 4 deletions(-)\n\ndiff --git a/builtin-rev-list.c b/builtin-rev-list.c\nindex 4e2524a..e5e8011 100644\n--- a/builtin-rev-list.c\n+++ b/builtin-rev-list.c\n@@ -258,6 +258,8 @@ static void show_list(const char *debug, int counted, int nr,\n static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\t\t\t\t     int nr, int *weights);\n \n+static struct commit_list *best_bisection(struct commit_list *list, int nr);\n+\n /*\n  * zero or positive weight is the number of interesting commits it can\n  * reach, including itself.  Especially, weight = 0 means it does not\n@@ -321,7 +323,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\t\t\t\t     int nr, int *weights)\n {\n \tint n, counted, distance;\n-\tstruct commit_list *p, *best;\n+\tstruct commit_list *p;\n \n \tcounted = 0;\n \n@@ -426,9 +428,17 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \tshow_list(\"bisection 2 counted all\", counted, nr, list);\n \n \t/* Then find the best one */\n-\tcounted = -1;\n+\treturn best_bisection(list, nr);\n+}\n+\n+static struct commit_list *best_bisection(struct commit_list *list, int nr)\n+{\n+\tstruct commit_list *p, *best;\n+\tint best_distance = -1;\n+\n \tbest = list;\n \tfor (p = list; p; p = p->next) {\n+\t\tint distance;\n \t\tunsigned flags = p->item->object.flags;\n \n \t\tif (revs.prune_fn && !(flags & TREECHANGE))\n@@ -436,11 +446,12 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\tdistance = weight(p);\n \t\tif (nr - distance < distance)\n \t\t\tdistance = nr - distance;\n-\t\tif (distance > counted) {\n+\t\tif (distance > best_distance) {\n \t\t\tbest = p;\n-\t\t\tcounted = distance;\n+\t\t\tbest_distance = distance;\n \t\t}\n \t}\n+\n \treturn best;\n }\n \n-- \n1.5.2.1.144.gabc40\n"},{"id":"49219","messageId":"20070731144842.fc7a0f89.chriscool@tuxfamily.org","threadId":"9327","inReplyTo":"20070731143602.a5ed0a04.chriscool@tuxfamily.org","subject":"[PATCH 4/4] Bisection \"distance\" clean up.","fromName":"Christian Couder","fromEmail":"chriscool@tuxfamily.org","sentAt":"2007-07-31T12:48:42Z","receivedAt":"2007-07-31T12:48:42Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"Signed-off-by: Christian Couder <chriscool@tuxfamily.org>\n---\n builtin-rev-list.c |   18 +++++++-----------\n 1 files changed, 7 insertions(+), 11 deletions(-)\n\ndiff --git a/builtin-rev-list.c b/builtin-rev-list.c\nindex e5e8011..38d7069 100644\n--- a/builtin-rev-list.c\n+++ b/builtin-rev-list.c\n@@ -189,7 +189,7 @@ static int count_interesting_parents(struct commit *commit)\n \treturn count;\n }\n \n-static inline int halfway(struct commit_list *p, int distance, int nr)\n+static inline int halfway(struct commit_list *p, int nr)\n {\n \t/*\n \t * Don't short-cut something we are not going to return!\n@@ -202,8 +202,7 @@ static inline int halfway(struct commit_list *p, int distance, int nr)\n \t * 2 and 3 are halfway of 5.\n \t * 3 is halfway of 6 but 2 and 4 are not.\n \t */\n-\tdistance *= 2;\n-\tswitch (distance - nr) {\n+\tswitch (2 * weight(p) - nr) {\n \tcase -1: case 0: case 1:\n \t\treturn 1;\n \tdefault:\n@@ -322,7 +321,7 @@ static struct commit_list *find_bisection(struct commit_list *list,\n static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\t\t\t\t     int nr, int *weights)\n {\n-\tint n, counted, distance;\n+\tint n, counted;\n \tstruct commit_list *p;\n \n \tcounted = 0;\n@@ -373,15 +372,13 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \tfor (p = list; p; p = p->next) {\n \t\tif (p->item->object.flags & UNINTERESTING)\n \t\t\tcontinue;\n-\t\tn = weight(p);\n-\t\tif (n != -2)\n+\t\tif (weight(p) != -2)\n \t\t\tcontinue;\n-\t\tdistance = count_distance(p);\n+\t\tweight_set(p, count_distance(p));\n \t\tclear_distance(list);\n-\t\tweight_set(p, distance);\n \n \t\t/* Does it happen to be at exactly half-way? */\n-\t\tif (halfway(p, distance, nr))\n+\t\tif (halfway(p, nr))\n \t\t\treturn p;\n \t\tcounted++;\n \t}\n@@ -419,8 +416,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\t\t\tweight_set(p, weight(q));\n \n \t\t\t/* Does it happen to be at exactly half-way? */\n-\t\t\tdistance = weight(p);\n-\t\t\tif (halfway(p, distance, nr))\n+\t\t\tif (halfway(p, nr))\n \t\t\t\treturn p;\n \t\t}\n \t}\n-- \n1.5.2.1.144.gabc40\n"}]}