{"thread":{"id":"1075","subject":"[PATCH] Removes support for O(n^2) algorithm from git-rev-list completely","startedAt":"2005-07-01T06:31:16Z","lastAt":"2005-07-01T06:31:16Z","messageCount":1,"participants":["Jon Seymour"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"5517","messageId":"20050701063116.1176.qmail@blackcubes.dyndns.org","threadId":"1075","inReplyTo":null,"subject":"[PATCH] Removes support for O(n^2) algorithm from git-rev-list completely","fromName":"Jon Seymour","fromEmail":"jon.seymour@gmail.com","sentAt":"2005-07-01T06:31:16Z","receivedAt":"2005-07-01T06:31:16Z","isPatch":true,"sender":{"key":"jon.seymour@gmail.com","avatar":"https://avatars.githubusercontent.com/u/207131?v=4"},"body":"\nThis patch completely removes support for the O(n^2) bisection\nalgorithm from commit.c, commit.h and rev-list.c\n\nSigned-off-by: Jon Seymour <jon.seymour@gmail.com>\n---\nLinus: I have included this patch to allow you to easily remove the O(n^2)\nalgorithm if that is your choice. I am not expecting you to do so.\n---\n\n commit.c                   |   31 -------------------------------\n commit.h                   |    7 -------\n rev-list.c                 |    7 -------\n t/t6002-rev-list-bisect.sh |    1 -\n 4 files changed, 0 insertions(+), 46 deletions(-)\n\nfa36c577acce519d1ef17bd807ab1486e1aa365a\ndiff --git a/commit.c b/commit.c\n--- a/commit.c\n+++ b/commit.c\n@@ -504,37 +504,6 @@ static void clear_distance(struct commit\n \t}\n }\n \n-struct commit_list *find_bisection(struct commit_list *list)\n-{\n-\tint nr, closest;\n-\tstruct commit_list *p, *best;\n-\n-\tnr = 0;\n-\tp = list;\n-\twhile (p) {\n-\t\tnr++;\n-\t\tp = p->next;\n-\t}\n-\tclosest = 0;\n-\tbest = list;\n-\n-\tp = list;\n-\twhile (p) {\n-\t\tint distance = count_distance(p);\n-\t\tclear_distance(list);\n-\t\tif (nr - distance < distance)\n-\t\t\tdistance = nr - distance;\n-\t\tif (distance > closest) {\n-\t\t\tbest = p;\n-\t\t\tclosest = distance;\n-\t\t}\n-\t\tp = p->next;\n-\t}\n-\tif (best)\n-\t\tbest->next = NULL;\n-\treturn best;\n-}\n-\n static inline struct bisect_by_cut_node * get_bisect_by_cut_node(struct commit * commit)\n {\n \treturn (struct bisect_by_cut_node *)commit->object.util;\ndiff --git a/commit.h b/commit.h\n--- a/commit.h\n+++ b/commit.h\n@@ -74,13 +74,6 @@ int count_parents(struct commit * commit\n void sort_in_topological_order(struct commit_list ** list);\n \n /*\n- * Uses an O(n^2) algorithm to find the commit that bisects \n- * the subgraph represented by the list of commits. The boundaries\n- * of the subgraph are delimited by adjacent nodes that have\n- */\n-struct commit_list *find_bisection(struct commit_list *list);\n-\n-/*\n  * Uses O(n) to find the bisection of a list of commits\n  * which is already sorted in topological order.\n  */\ndiff --git a/rev-list.c b/rev-list.c\n--- a/rev-list.c\n+++ b/rev-list.c\n@@ -19,7 +19,6 @@ static const char rev_list_usage[] =\n                       \"  --bisect\\n\"\n \t\t      \"  --merge-order [ --show-breaks ]\";\n \n-static int bisect_list = 0;\n static int tag_objects = 0;\n static int tree_objects = 0;\n static int blob_objects = 0;\n@@ -252,8 +251,6 @@ struct commit_list *limit_list(struct co\n \t\t}\n \t\tp = &commit_list_insert(commit, p)->next;\n \t}\n-\tif (bisect_list)\n-\t\tnewlist = find_bisection(newlist);\n \treturn newlist;\n }\n \n@@ -370,10 +367,6 @@ int main(int argc, char **argv)\n \t\t\tbisect_by_cut_option = 1;\n \t\t\tcontinue;\n \t\t}\n-\t\tif (!strcmp(arg, \"--bisect-orig\")) {\n-\t\t\tbisect_list = 1;\n-\t\t\tcontinue;\n-\t\t}\n \t\tif (!strcmp(arg, \"--objects\")) {\n \t\t\ttag_objects = 1;\n \t\t\ttree_objects = 1;\ndiff --git a/t/t6002-rev-list-bisect.sh b/t/t6002-rev-list-bisect.sh\n--- a/t/t6002-rev-list-bisect.sh\n+++ b/t/t6002-rev-list-bisect.sh\n@@ -241,7 +241,6 @@ EOF\n }\n \n test_sequence \"--bisect\"\n-test_sequence \"--bisect-by-cut\"\n \n #\n #\n------------\n"}]}