{"thread":{"id":"18277","subject":"[PATCH 3/7] rev-list: move bisect related code into its own file","startedAt":"2009-03-12T07:51:17Z","lastAt":"2009-03-12T07:51:17Z","messageCount":1,"participants":["Christian Couder"],"isPatch":true,"patchVersion":1,"patchTotal":7},"messages":[{"id":"107774","messageId":"20090312085117.1a48ec1a.chriscool@tuxfamily.org","threadId":"18277","inReplyTo":null,"subject":"[PATCH 3/7] rev-list: move bisect related code into its own file","fromName":"Christian Couder","fromEmail":"chriscool@tuxfamily.org","sentAt":"2009-03-12T07:51:17Z","receivedAt":"2009-03-12T07:51:17Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"This patch creates new \"bisect.c\" and \"bisect.h\" files and move\nbisect related code into these files.\n\nWhile at it, we also remove some include directives that are not\nneeded any more from the beginning of \"builtin-rev-list.c\".\n\nSigned-off-by: Christian Couder <chriscool@tuxfamily.org>\n---\n Makefile           |    1 +\n bisect.c           |  388 ++++++++++++++++++++++++++++++++++++++++++++++++++++\n bisect.h           |    8 +\n builtin-rev-list.c |  388 +---------------------------------------------------\n 4 files changed, 398 insertions(+), 387 deletions(-)\n create mode 100644 bisect.c\n create mode 100644 bisect.h\n\ndiff --git a/Makefile b/Makefile\nindex 0675c43..9500c5e 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -414,6 +414,7 @@ LIB_OBJS += archive-tar.o\n LIB_OBJS += archive-zip.o\n LIB_OBJS += attr.o\n LIB_OBJS += base85.o\n+LIB_OBJS += bisect.o\n LIB_OBJS += blob.o\n LIB_OBJS += branch.o\n LIB_OBJS += bundle.o\ndiff --git a/bisect.c b/bisect.c\nnew file mode 100644\nindex 0000000..27def7d\n--- /dev/null\n+++ b/bisect.c\n@@ -0,0 +1,388 @@\n+#include \"cache.h\"\n+#include \"commit.h\"\n+#include \"diff.h\"\n+#include \"revision.h\"\n+#include \"bisect.h\"\n+\n+/* bits #0-15 in revision.h */\n+\n+#define COUNTED\t\t(1u<<16)\n+\n+/*\n+ * This is a truly stupid algorithm, but it's only\n+ * used for bisection, and we just don't care enough.\n+ *\n+ * We care just barely enough to avoid recursing for\n+ * non-merge entries.\n+ */\n+static int count_distance(struct commit_list *entry)\n+{\n+\tint nr = 0;\n+\n+\twhile (entry) {\n+\t\tstruct commit *commit = entry->item;\n+\t\tstruct commit_list *p;\n+\n+\t\tif (commit->object.flags & (UNINTERESTING | COUNTED))\n+\t\t\tbreak;\n+\t\tif (!(commit->object.flags & TREESAME))\n+\t\t\tnr++;\n+\t\tcommit->object.flags |= COUNTED;\n+\t\tp = commit->parents;\n+\t\tentry = p;\n+\t\tif (p) {\n+\t\t\tp = p->next;\n+\t\t\twhile (p) {\n+\t\t\t\tnr += count_distance(p);\n+\t\t\t\tp = p->next;\n+\t\t\t}\n+\t\t}\n+\t}\n+\n+\treturn nr;\n+}\n+\n+static void clear_distance(struct commit_list *list)\n+{\n+\twhile (list) {\n+\t\tstruct commit *commit = list->item;\n+\t\tcommit->object.flags &= ~COUNTED;\n+\t\tlist = list->next;\n+\t}\n+}\n+\n+#define DEBUG_BISECT 0\n+\n+static inline int weight(struct commit_list *elem)\n+{\n+\treturn *((int*)(elem->item->util));\n+}\n+\n+static inline void weight_set(struct commit_list *elem, int weight)\n+{\n+\t*((int*)(elem->item->util)) = weight;\n+}\n+\n+static int count_interesting_parents(struct commit *commit)\n+{\n+\tstruct commit_list *p;\n+\tint count;\n+\n+\tfor (count = 0, p = commit->parents; p; p = p->next) {\n+\t\tif (p->item->object.flags & UNINTERESTING)\n+\t\t\tcontinue;\n+\t\tcount++;\n+\t}\n+\treturn count;\n+}\n+\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+\t */\n+\tif (p->item->object.flags & TREESAME)\n+\t\treturn 0;\n+\tif (DEBUG_BISECT)\n+\t\treturn 0;\n+\t/*\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+\tswitch (2 * weight(p) - nr) {\n+\tcase -1: case 0: case 1:\n+\t\treturn 1;\n+\tdefault:\n+\t\treturn 0;\n+\t}\n+}\n+\n+#if !DEBUG_BISECT\n+#define show_list(a,b,c,d) do { ; } while (0)\n+#else\n+static void show_list(const char *debug, int counted, int nr,\n+\t\t      struct commit_list *list)\n+{\n+\tstruct commit_list *p;\n+\n+\tfprintf(stderr, \"%s (%d/%d)\\n\", debug, counted, nr);\n+\n+\tfor (p = list; p; p = p->next) {\n+\t\tstruct commit_list *pp;\n+\t\tstruct commit *commit = p->item;\n+\t\tunsigned flags = commit->object.flags;\n+\t\tenum object_type type;\n+\t\tunsigned long size;\n+\t\tchar *buf = read_sha1_file(commit->object.sha1, &type, &size);\n+\t\tchar *ep, *sp;\n+\n+\t\tfprintf(stderr, \"%c%c%c \",\n+\t\t\t(flags & TREESAME) ? ' ' : 'T',\n+\t\t\t(flags & UNINTERESTING) ? 'U' : ' ',\n+\t\t\t(flags & COUNTED) ? 'C' : ' ');\n+\t\tif (commit->util)\n+\t\t\tfprintf(stderr, \"%3d\", weight(p));\n+\t\telse\n+\t\t\tfprintf(stderr, \"---\");\n+\t\tfprintf(stderr, \" %.*s\", 8, sha1_to_hex(commit->object.sha1));\n+\t\tfor (pp = commit->parents; pp; pp = pp->next)\n+\t\t\tfprintf(stderr, \" %.*s\", 8,\n+\t\t\t\tsha1_to_hex(pp->item->object.sha1));\n+\n+\t\tsp = strstr(buf, \"\\n\\n\");\n+\t\tif (sp) {\n+\t\t\tsp += 2;\n+\t\t\tfor (ep = sp; *ep && *ep != '\\n'; ep++)\n+\t\t\t\t;\n+\t\t\tfprintf(stderr, \" %.*s\", (int)(ep - sp), sp);\n+\t\t}\n+\t\tfprintf(stderr, \"\\n\");\n+\t}\n+}\n+#endif /* DEBUG_BISECT */\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 (flags & TREESAME)\n+\t\t\tcontinue;\n+\t\tdistance = weight(p);\n+\t\tif (nr - distance < distance)\n+\t\t\tdistance = nr - distance;\n+\t\tif (distance > best_distance) {\n+\t\t\tbest = p;\n+\t\t\tbest_distance = distance;\n+\t\t}\n+\t}\n+\n+\treturn best;\n+}\n+\n+struct commit_dist {\n+\tstruct commit *commit;\n+\tint distance;\n+};\n+\n+static int compare_commit_dist(const void *a_, const void *b_)\n+{\n+\tstruct commit_dist *a, *b;\n+\n+\ta = (struct commit_dist *)a_;\n+\tb = (struct commit_dist *)b_;\n+\tif (a->distance != b->distance)\n+\t\treturn b->distance - a->distance; /* desc sort */\n+\treturn hashcmp(a->commit->object.sha1, b->commit->object.sha1);\n+}\n+\n+static struct commit_list *best_bisection_sorted(struct commit_list *list, int nr)\n+{\n+\tstruct commit_list *p;\n+\tstruct commit_dist *array = xcalloc(nr, sizeof(*array));\n+\tint cnt, i;\n+\n+\tfor (p = list, cnt = 0; p; p = p->next) {\n+\t\tint distance;\n+\t\tunsigned flags = p->item->object.flags;\n+\n+\t\tif (flags & TREESAME)\n+\t\t\tcontinue;\n+\t\tdistance = weight(p);\n+\t\tif (nr - distance < distance)\n+\t\t\tdistance = nr - distance;\n+\t\tarray[cnt].commit = p->item;\n+\t\tarray[cnt].distance = distance;\n+\t\tcnt++;\n+\t}\n+\tqsort(array, cnt, sizeof(*array), compare_commit_dist);\n+\tfor (p = list, i = 0; i < cnt; i++) {\n+\t\tstruct name_decoration *r = xmalloc(sizeof(*r) + 100);\n+\t\tstruct object *obj = &(array[i].commit->object);\n+\n+\t\tsprintf(r->name, \"dist=%d\", array[i].distance);\n+\t\tr->next = add_decoration(&name_decoration, obj, r);\n+\t\tp->item = array[i].commit;\n+\t\tp = p->next;\n+\t}\n+\tif (p)\n+\t\tp->next = NULL;\n+\tfree(array);\n+\treturn list;\n+}\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+ * reach any tree-changing commits (e.g. just above uninteresting one\n+ * but traversal is with pathspec).\n+ *\n+ * weight = -1 means it has one parent and its distance is yet to\n+ * be computed.\n+ *\n+ * weight = -2 means it has more than one parent and its distance is\n+ * unknown.  After running count_distance() first, they will get zero\n+ * or positive distance.\n+ */\n+static struct commit_list *do_find_bisection(struct commit_list *list,\n+\t\t\t\t\t     int nr, int *weights,\n+\t\t\t\t\t     int find_all)\n+{\n+\tint n, counted;\n+\tstruct commit_list *p;\n+\n+\tcounted = 0;\n+\n+\tfor (n = 0, p = list; p; p = p->next) {\n+\t\tstruct commit *commit = p->item;\n+\t\tunsigned flags = commit->object.flags;\n+\n+\t\tp->item->util = &weights[n++];\n+\t\tswitch (count_interesting_parents(commit)) {\n+\t\tcase 0:\n+\t\t\tif (!(flags & TREESAME)) {\n+\t\t\t\tweight_set(p, 1);\n+\t\t\t\tcounted++;\n+\t\t\t\tshow_list(\"bisection 2 count one\",\n+\t\t\t\t\t  counted, nr, list);\n+\t\t\t}\n+\t\t\t/*\n+\t\t\t * otherwise, it is known not to reach any\n+\t\t\t * tree-changing commit and gets weight 0.\n+\t\t\t */\n+\t\t\tbreak;\n+\t\tcase 1:\n+\t\t\tweight_set(p, -1);\n+\t\t\tbreak;\n+\t\tdefault:\n+\t\t\tweight_set(p, -2);\n+\t\t\tbreak;\n+\t\t}\n+\t}\n+\n+\tshow_list(\"bisection 2 initialize\", counted, nr, list);\n+\n+\t/*\n+\t * If you have only one parent in the resulting set\n+\t * then you can reach one commit more than that parent\n+\t * can reach.  So we do not have to run the expensive\n+\t * count_distance() for single strand of pearls.\n+\t *\n+\t * However, if you have more than one parents, you cannot\n+\t * just add their distance and one for yourself, since\n+\t * they usually reach the same ancestor and you would\n+\t * end up counting them twice that way.\n+\t *\n+\t * So we will first count distance of merges the usual\n+\t * way, and then fill the blanks using cheaper algorithm.\n+\t */\n+\tfor (p = list; p; p = p->next) {\n+\t\tif (p->item->object.flags & UNINTERESTING)\n+\t\t\tcontinue;\n+\t\tif (weight(p) != -2)\n+\t\t\tcontinue;\n+\t\tweight_set(p, count_distance(p));\n+\t\tclear_distance(list);\n+\n+\t\t/* Does it happen to be at exactly half-way? */\n+\t\tif (!find_all && halfway(p, nr))\n+\t\t\treturn p;\n+\t\tcounted++;\n+\t}\n+\n+\tshow_list(\"bisection 2 count_distance\", counted, nr, list);\n+\n+\twhile (counted < nr) {\n+\t\tfor (p = list; p; p = p->next) {\n+\t\t\tstruct commit_list *q;\n+\t\t\tunsigned flags = p->item->object.flags;\n+\n+\t\t\tif (0 <= weight(p))\n+\t\t\t\tcontinue;\n+\t\t\tfor (q = p->item->parents; q; q = q->next) {\n+\t\t\t\tif (q->item->object.flags & UNINTERESTING)\n+\t\t\t\t\tcontinue;\n+\t\t\t\tif (0 <= weight(q))\n+\t\t\t\t\tbreak;\n+\t\t\t}\n+\t\t\tif (!q)\n+\t\t\t\tcontinue;\n+\n+\t\t\t/*\n+\t\t\t * weight for p is unknown but q is known.\n+\t\t\t * add one for p itself if p is to be counted,\n+\t\t\t * otherwise inherit it from q directly.\n+\t\t\t */\n+\t\t\tif (!(flags & TREESAME)) {\n+\t\t\t\tweight_set(p, weight(q)+1);\n+\t\t\t\tcounted++;\n+\t\t\t\tshow_list(\"bisection 2 count one\",\n+\t\t\t\t\t  counted, nr, list);\n+\t\t\t}\n+\t\t\telse\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\tif (!find_all && halfway(p, nr))\n+\t\t\t\treturn p;\n+\t\t}\n+\t}\n+\n+\tshow_list(\"bisection 2 counted all\", counted, nr, list);\n+\n+\tif (!find_all)\n+\t\treturn best_bisection(list, nr);\n+\telse\n+\t\treturn best_bisection_sorted(list, nr);\n+}\n+\n+struct commit_list *find_bisection(struct commit_list *list,\n+\t\t\t\t\t  int *reaches, int *all,\n+\t\t\t\t\t  int find_all)\n+{\n+\tint nr, on_list;\n+\tstruct commit_list *p, *best, *next, *last;\n+\tint *weights;\n+\n+\tshow_list(\"bisection 2 entry\", 0, 0, list);\n+\n+\t/*\n+\t * Count the number of total and tree-changing items on the\n+\t * list, while reversing the list.\n+\t */\n+\tfor (nr = on_list = 0, last = NULL, p = list;\n+\t     p;\n+\t     p = next) {\n+\t\tunsigned flags = p->item->object.flags;\n+\n+\t\tnext = p->next;\n+\t\tif (flags & UNINTERESTING)\n+\t\t\tcontinue;\n+\t\tp->next = last;\n+\t\tlast = p;\n+\t\tif (!(flags & TREESAME))\n+\t\t\tnr++;\n+\t\ton_list++;\n+\t}\n+\tlist = last;\n+\tshow_list(\"bisection 2 sorted\", 0, nr, list);\n+\n+\t*all = nr;\n+\tweights = xcalloc(on_list, sizeof(*weights));\n+\n+\t/* Do the real work of finding bisection commit. */\n+\tbest = do_find_bisection(list, nr, weights, find_all);\n+\tif (best) {\n+\t\tif (!find_all)\n+\t\t\tbest->next = NULL;\n+\t\t*reaches = weight(best);\n+\t}\n+\tfree(weights);\n+\treturn best;\n+}\n+\ndiff --git a/bisect.h b/bisect.h\nnew file mode 100644\nindex 0000000..cce268d\n--- /dev/null\n+++ b/bisect.h\n@@ -0,0 +1,8 @@\n+#ifndef BISECT_H\n+#define BISECT_H\n+\n+struct commit_list *find_bisection(struct commit_list *list,\n+\t\t\t\t   int *reaches, int *all,\n+\t\t\t\t   int find_all);\n+\n+#endif\ndiff --git a/builtin-rev-list.c b/builtin-rev-list.c\nindex 28fe2dc..b1e8200 100644\n--- a/builtin-rev-list.c\n+++ b/builtin-rev-list.c\n@@ -1,20 +1,12 @@\n #include \"cache.h\"\n-#include \"refs.h\"\n-#include \"tag.h\"\n #include \"commit.h\"\n-#include \"tree.h\"\n-#include \"blob.h\"\n-#include \"tree-walk.h\"\n #include \"diff.h\"\n #include \"revision.h\"\n #include \"list-objects.h\"\n #include \"builtin.h\"\n #include \"log-tree.h\"\n #include \"graph.h\"\n-\n-/* bits #0-15 in revision.h */\n-\n-#define COUNTED\t\t(1u<<16)\n+#include \"bisect.h\"\n \n static const char rev_list_usage[] =\n \"git rev-list [OPTION] <commit-id>... [ -- paths... ]\\n\"\n@@ -195,384 +187,6 @@ static void show_edge(struct commit *commit)\n \tprintf(\"-%s\\n\", sha1_to_hex(commit->object.sha1));\n }\n \n-/*\n- * This is a truly stupid algorithm, but it's only\n- * used for bisection, and we just don't care enough.\n- *\n- * We care just barely enough to avoid recursing for\n- * non-merge entries.\n- */\n-static int count_distance(struct commit_list *entry)\n-{\n-\tint nr = 0;\n-\n-\twhile (entry) {\n-\t\tstruct commit *commit = entry->item;\n-\t\tstruct commit_list *p;\n-\n-\t\tif (commit->object.flags & (UNINTERESTING | COUNTED))\n-\t\t\tbreak;\n-\t\tif (!(commit->object.flags & TREESAME))\n-\t\t\tnr++;\n-\t\tcommit->object.flags |= COUNTED;\n-\t\tp = commit->parents;\n-\t\tentry = p;\n-\t\tif (p) {\n-\t\t\tp = p->next;\n-\t\t\twhile (p) {\n-\t\t\t\tnr += count_distance(p);\n-\t\t\t\tp = p->next;\n-\t\t\t}\n-\t\t}\n-\t}\n-\n-\treturn nr;\n-}\n-\n-static void clear_distance(struct commit_list *list)\n-{\n-\twhile (list) {\n-\t\tstruct commit *commit = list->item;\n-\t\tcommit->object.flags &= ~COUNTED;\n-\t\tlist = list->next;\n-\t}\n-}\n-\n-#define DEBUG_BISECT 0\n-\n-static inline int weight(struct commit_list *elem)\n-{\n-\treturn *((int*)(elem->item->util));\n-}\n-\n-static inline void weight_set(struct commit_list *elem, int weight)\n-{\n-\t*((int*)(elem->item->util)) = weight;\n-}\n-\n-static int count_interesting_parents(struct commit *commit)\n-{\n-\tstruct commit_list *p;\n-\tint count;\n-\n-\tfor (count = 0, p = commit->parents; p; p = p->next) {\n-\t\tif (p->item->object.flags & UNINTERESTING)\n-\t\t\tcontinue;\n-\t\tcount++;\n-\t}\n-\treturn count;\n-}\n-\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-\t */\n-\tif (p->item->object.flags & TREESAME)\n-\t\treturn 0;\n-\tif (DEBUG_BISECT)\n-\t\treturn 0;\n-\t/*\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-\tswitch (2 * weight(p) - nr) {\n-\tcase -1: case 0: case 1:\n-\t\treturn 1;\n-\tdefault:\n-\t\treturn 0;\n-\t}\n-}\n-\n-#if !DEBUG_BISECT\n-#define show_list(a,b,c,d) do { ; } while (0)\n-#else\n-static void show_list(const char *debug, int counted, int nr,\n-\t\t      struct commit_list *list)\n-{\n-\tstruct commit_list *p;\n-\n-\tfprintf(stderr, \"%s (%d/%d)\\n\", debug, counted, nr);\n-\n-\tfor (p = list; p; p = p->next) {\n-\t\tstruct commit_list *pp;\n-\t\tstruct commit *commit = p->item;\n-\t\tunsigned flags = commit->object.flags;\n-\t\tenum object_type type;\n-\t\tunsigned long size;\n-\t\tchar *buf = read_sha1_file(commit->object.sha1, &type, &size);\n-\t\tchar *ep, *sp;\n-\n-\t\tfprintf(stderr, \"%c%c%c \",\n-\t\t\t(flags & TREESAME) ? ' ' : 'T',\n-\t\t\t(flags & UNINTERESTING) ? 'U' : ' ',\n-\t\t\t(flags & COUNTED) ? 'C' : ' ');\n-\t\tif (commit->util)\n-\t\t\tfprintf(stderr, \"%3d\", weight(p));\n-\t\telse\n-\t\t\tfprintf(stderr, \"---\");\n-\t\tfprintf(stderr, \" %.*s\", 8, sha1_to_hex(commit->object.sha1));\n-\t\tfor (pp = commit->parents; pp; pp = pp->next)\n-\t\t\tfprintf(stderr, \" %.*s\", 8,\n-\t\t\t\tsha1_to_hex(pp->item->object.sha1));\n-\n-\t\tsp = strstr(buf, \"\\n\\n\");\n-\t\tif (sp) {\n-\t\t\tsp += 2;\n-\t\t\tfor (ep = sp; *ep && *ep != '\\n'; ep++)\n-\t\t\t\t;\n-\t\t\tfprintf(stderr, \" %.*s\", (int)(ep - sp), sp);\n-\t\t}\n-\t\tfprintf(stderr, \"\\n\");\n-\t}\n-}\n-#endif /* DEBUG_BISECT */\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 (flags & TREESAME)\n-\t\t\tcontinue;\n-\t\tdistance = weight(p);\n-\t\tif (nr - distance < distance)\n-\t\t\tdistance = nr - distance;\n-\t\tif (distance > best_distance) {\n-\t\t\tbest = p;\n-\t\t\tbest_distance = distance;\n-\t\t}\n-\t}\n-\n-\treturn best;\n-}\n-\n-struct commit_dist {\n-\tstruct commit *commit;\n-\tint distance;\n-};\n-\n-static int compare_commit_dist(const void *a_, const void *b_)\n-{\n-\tstruct commit_dist *a, *b;\n-\n-\ta = (struct commit_dist *)a_;\n-\tb = (struct commit_dist *)b_;\n-\tif (a->distance != b->distance)\n-\t\treturn b->distance - a->distance; /* desc sort */\n-\treturn hashcmp(a->commit->object.sha1, b->commit->object.sha1);\n-}\n-\n-static struct commit_list *best_bisection_sorted(struct commit_list *list, int nr)\n-{\n-\tstruct commit_list *p;\n-\tstruct commit_dist *array = xcalloc(nr, sizeof(*array));\n-\tint cnt, i;\n-\n-\tfor (p = list, cnt = 0; p; p = p->next) {\n-\t\tint distance;\n-\t\tunsigned flags = p->item->object.flags;\n-\n-\t\tif (flags & TREESAME)\n-\t\t\tcontinue;\n-\t\tdistance = weight(p);\n-\t\tif (nr - distance < distance)\n-\t\t\tdistance = nr - distance;\n-\t\tarray[cnt].commit = p->item;\n-\t\tarray[cnt].distance = distance;\n-\t\tcnt++;\n-\t}\n-\tqsort(array, cnt, sizeof(*array), compare_commit_dist);\n-\tfor (p = list, i = 0; i < cnt; i++) {\n-\t\tstruct name_decoration *r = xmalloc(sizeof(*r) + 100);\n-\t\tstruct object *obj = &(array[i].commit->object);\n-\n-\t\tsprintf(r->name, \"dist=%d\", array[i].distance);\n-\t\tr->next = add_decoration(&name_decoration, obj, r);\n-\t\tp->item = array[i].commit;\n-\t\tp = p->next;\n-\t}\n-\tif (p)\n-\t\tp->next = NULL;\n-\tfree(array);\n-\treturn list;\n-}\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- * reach any tree-changing commits (e.g. just above uninteresting one\n- * but traversal is with pathspec).\n- *\n- * weight = -1 means it has one parent and its distance is yet to\n- * be computed.\n- *\n- * weight = -2 means it has more than one parent and its distance is\n- * unknown.  After running count_distance() first, they will get zero\n- * or positive distance.\n- */\n-static struct commit_list *do_find_bisection(struct commit_list *list,\n-\t\t\t\t\t     int nr, int *weights,\n-\t\t\t\t\t     int find_all)\n-{\n-\tint n, counted;\n-\tstruct commit_list *p;\n-\n-\tcounted = 0;\n-\n-\tfor (n = 0, p = list; p; p = p->next) {\n-\t\tstruct commit *commit = p->item;\n-\t\tunsigned flags = commit->object.flags;\n-\n-\t\tp->item->util = &weights[n++];\n-\t\tswitch (count_interesting_parents(commit)) {\n-\t\tcase 0:\n-\t\t\tif (!(flags & TREESAME)) {\n-\t\t\t\tweight_set(p, 1);\n-\t\t\t\tcounted++;\n-\t\t\t\tshow_list(\"bisection 2 count one\",\n-\t\t\t\t\t  counted, nr, list);\n-\t\t\t}\n-\t\t\t/*\n-\t\t\t * otherwise, it is known not to reach any\n-\t\t\t * tree-changing commit and gets weight 0.\n-\t\t\t */\n-\t\t\tbreak;\n-\t\tcase 1:\n-\t\t\tweight_set(p, -1);\n-\t\t\tbreak;\n-\t\tdefault:\n-\t\t\tweight_set(p, -2);\n-\t\t\tbreak;\n-\t\t}\n-\t}\n-\n-\tshow_list(\"bisection 2 initialize\", counted, nr, list);\n-\n-\t/*\n-\t * If you have only one parent in the resulting set\n-\t * then you can reach one commit more than that parent\n-\t * can reach.  So we do not have to run the expensive\n-\t * count_distance() for single strand of pearls.\n-\t *\n-\t * However, if you have more than one parents, you cannot\n-\t * just add their distance and one for yourself, since\n-\t * they usually reach the same ancestor and you would\n-\t * end up counting them twice that way.\n-\t *\n-\t * So we will first count distance of merges the usual\n-\t * way, and then fill the blanks using cheaper algorithm.\n-\t */\n-\tfor (p = list; p; p = p->next) {\n-\t\tif (p->item->object.flags & UNINTERESTING)\n-\t\t\tcontinue;\n-\t\tif (weight(p) != -2)\n-\t\t\tcontinue;\n-\t\tweight_set(p, count_distance(p));\n-\t\tclear_distance(list);\n-\n-\t\t/* Does it happen to be at exactly half-way? */\n-\t\tif (!find_all && halfway(p, nr))\n-\t\t\treturn p;\n-\t\tcounted++;\n-\t}\n-\n-\tshow_list(\"bisection 2 count_distance\", counted, nr, list);\n-\n-\twhile (counted < nr) {\n-\t\tfor (p = list; p; p = p->next) {\n-\t\t\tstruct commit_list *q;\n-\t\t\tunsigned flags = p->item->object.flags;\n-\n-\t\t\tif (0 <= weight(p))\n-\t\t\t\tcontinue;\n-\t\t\tfor (q = p->item->parents; q; q = q->next) {\n-\t\t\t\tif (q->item->object.flags & UNINTERESTING)\n-\t\t\t\t\tcontinue;\n-\t\t\t\tif (0 <= weight(q))\n-\t\t\t\t\tbreak;\n-\t\t\t}\n-\t\t\tif (!q)\n-\t\t\t\tcontinue;\n-\n-\t\t\t/*\n-\t\t\t * weight for p is unknown but q is known.\n-\t\t\t * add one for p itself if p is to be counted,\n-\t\t\t * otherwise inherit it from q directly.\n-\t\t\t */\n-\t\t\tif (!(flags & TREESAME)) {\n-\t\t\t\tweight_set(p, weight(q)+1);\n-\t\t\t\tcounted++;\n-\t\t\t\tshow_list(\"bisection 2 count one\",\n-\t\t\t\t\t  counted, nr, list);\n-\t\t\t}\n-\t\t\telse\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\tif (!find_all && halfway(p, nr))\n-\t\t\t\treturn p;\n-\t\t}\n-\t}\n-\n-\tshow_list(\"bisection 2 counted all\", counted, nr, list);\n-\n-\tif (!find_all)\n-\t\treturn best_bisection(list, nr);\n-\telse\n-\t\treturn best_bisection_sorted(list, nr);\n-}\n-\n-static struct commit_list *find_bisection(struct commit_list *list,\n-\t\t\t\t\t  int *reaches, int *all,\n-\t\t\t\t\t  int find_all)\n-{\n-\tint nr, on_list;\n-\tstruct commit_list *p, *best, *next, *last;\n-\tint *weights;\n-\n-\tshow_list(\"bisection 2 entry\", 0, 0, list);\n-\n-\t/*\n-\t * Count the number of total and tree-changing items on the\n-\t * list, while reversing the list.\n-\t */\n-\tfor (nr = on_list = 0, last = NULL, p = list;\n-\t     p;\n-\t     p = next) {\n-\t\tunsigned flags = p->item->object.flags;\n-\n-\t\tnext = p->next;\n-\t\tif (flags & UNINTERESTING)\n-\t\t\tcontinue;\n-\t\tp->next = last;\n-\t\tlast = p;\n-\t\tif (!(flags & TREESAME))\n-\t\t\tnr++;\n-\t\ton_list++;\n-\t}\n-\tlist = last;\n-\tshow_list(\"bisection 2 sorted\", 0, nr, list);\n-\n-\t*all = nr;\n-\tweights = xcalloc(on_list, sizeof(*weights));\n-\n-\t/* Do the real work of finding bisection commit. */\n-\tbest = do_find_bisection(list, nr, weights, find_all);\n-\tif (best) {\n-\t\tif (!find_all)\n-\t\t\tbest->next = NULL;\n-\t\t*reaches = weight(best);\n-\t}\n-\tfree(weights);\n-\treturn best;\n-}\n-\n static inline int log2i(int n)\n {\n \tint log2 = 0;\n-- \n1.6.2.83.g012a16.dirty\n"}]}