{"thread":{"id":"1073","subject":"[PATCH] Move bisection algorithms into commit.c","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":"5515","messageId":"20050701063116.1136.qmail@blackcubes.dyndns.org","threadId":"1073","inReplyTo":null,"subject":"[PATCH] Move bisection algorithms into commit.c","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 moves the bisection algorithms into commit.c.\n\nThe bisection algorithms are more lib'ish than tool'ish, so they\nhave been moved into commit.c.\n\nThis has required the definition of the UNINTERESTING and COUNTED\nflags to be moved into commit.h and the introduction of the\nthe LAST_COMMIT_FLAG into commit.h.\n\nSigned-off-by: Jon Seymour <jon.seymour@gmail.com>\n---\n\n commit.c   |  258 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n commit.h   |   17 ++++\n epoch.h    |   12 +--\n rev-list.c |  261 ------------------------------------------------------------\n 4 files changed, 281 insertions(+), 267 deletions(-)\n\n751d906f842fabd42d191fe7df7ab61d44765de7\ndiff --git a/commit.c b/commit.c\n--- a/commit.c\n+++ b/commit.c\n@@ -3,6 +3,15 @@\n #include \"commit.h\"\n #include \"cache.h\"\n \n+#define ABOVE        (1u<<1)\n+struct bisect_by_cut_node \n+{\n+\tunsigned int flags;\n+\tunsigned int count;\n+\tstruct commit_list * children;\n+\tstruct commit_list * visible_parents;\n+};\n+\n struct sort_node\n {\n \t/*\n@@ -453,3 +462,252 @@ void sort_in_topological_order(struct co\n \t}\n \tfree(nodes);\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\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}\t\t\t\n+\t\t}\n+\t}\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+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;\n+}\n+\n+/*\n+ * Find the best bisection point by cutting a topological order in two then\n+ * identifying a set of boundary nodes with a reachability known to be \n+ * less than the desired bisection point. The boundary is advanced until all nodes\n+ * in the boundary have a reachability greater than or equal to the desired \n+ * reachability.\n+ *\n+ * This algorithm is roughly O(kn) where k is a factor related to the typical\n+ * amount of parallel branching within the graph and is not related to n.\n+ *\n+ * The algorithm borrows the notion of making an arbitrary cut in the graph\n+ * from the Kernighan-Lin (1969) graph bisection algorithm but differs in\n+ * other respects. In particular, by using the topological order to make the\n+ * cut the width of the advancing boundary is reduced to some kind of minimum.\n+ * Full graph scans (e.g. calls to count_distance()) are avoided except where\n+ * absolutely necessary (i.e. a merge node is encountered).\n+ */\n+struct commit * bisect_by_cut(struct commit_list * topological_order)\n+{\n+\tunsigned int count=0;\n+\tunsigned int i;\n+\tstruct commit_list * next;\n+\tstruct commit_list * work = NULL;\n+\tstruct commit * best = topological_order->item;\n+\tstruct bisect_by_cut_node * nodes;\n+\tstruct bisect_by_cut_node * next_node;\n+\tstruct commit_list counter;\n+\tunsigned int fittest, goal;\n+\n+\tcounter.next=NULL;\n+\t/* count the size of the topological order */\n+\tnext=topological_order;\n+\twhile (next) {\n+\t\tcount++;\n+\t\tnext = next->next;\n+\t}\n+\tfittest=count;\n+\ti=(count+1)/2;\n+\tgoal=count/2;\n+\t/* allocate and initialize the bisect_by_cut_node structure */\n+\tnext_node=nodes=xmalloc(sizeof(*nodes)*count);\n+\tmemset(nodes, 0, sizeof(*nodes)*count);\n+\t/* \n+\t * initialize the structures for all nodes of interest\n+\t */\n+\tnext=topological_order;\n+\tnext_node=nodes;\n+\twhile (next) {\t\t\n+\t\tnext->item->object.util=next_node++;\n+\t\tnext=next->next;\n+\t}\n+\t/*\n+\t * Mark half the nodes as being above the boundary.\n+\t * Mark nodes that aren't in the topological order as uninteresting.\n+\t * Initialize lists of visible children and parents.\n+\t */\n+\tnext=topological_order;\n+\tnext_node=nodes;\n+\twhile (next) {\t\t\n+\t\tstruct commit * next_item = next->item;\n+\t\tstruct commit_list * parents;\n+\t\t\n+\t\tif (i > 0) {\n+\t\t\tnext_node->flags |= ABOVE;\n+\t\t\ti--;\n+\t\t}\t\t\t\n+\t\tparents=next_item->parents;\n+\t\twhile (parents) {\n+\t\t\tstruct commit * parent = parents->item;\n+\t\t\tstruct bisect_by_cut_node * pn = get_bisect_by_cut_node(parent);\n+\n+\t\t\tif (pn) {\n+\t\t\t\tcommit_list_insert(next_item, &pn->children);\n+\t\t\t\tcommit_list_insert(parent, &next_node->visible_parents);\n+\t\t\t} else \n+\t\t\t\tparent->object.flags |= UNINTERESTING;\n+\t\t\tparent->object.flags &= ~COUNTED;\n+\t\t\tparents=parents->next;\n+\t\t}\n+\t\tnext=next->next;\n+\t\tnext_node++;\n+\t}\n+\t/*\n+\t * Initialize the work queue with commits that are on the boundary\n+\t * and with < the desired reachability.\n+\t * \n+\t * We know these commits have less than the desired \n+\t * reachability because by the definition of the topological order\n+\t * nodes can only reach nodes to the right of them in the topological\n+\t * order and by construction, there there are no more than \n+\t * (count-1)/2 nodes to the right of each node in the boundary.\n+\t */\n+\tnext=topological_order;\n+\tnext_node=nodes;\n+\twhile (next) {\n+\t\tstruct commit_list * parents;\n+\n+\t\tparents=next_node->visible_parents;\n+\t\twhile (parents) {\n+\t\t\tstruct bisect_by_cut_node * pn = get_bisect_by_cut_node(parents->item);\n+\n+\t\t\tif ((next_node->flags & ABOVE) \n+\t\t\t     && !(pn->flags & ABOVE) \n+\t\t\t     && (pn->count == 0)) {\n+\t\t\t\tcounter.item=parents->item;\n+\t\t\t\tpn->count = count_distance(&counter);\n+\t\t\t\tclear_distance(topological_order);\n+\t\t\t\tcommit_list_insert(parents->item, &work);\n+\t\t\t}\n+\t\t\tparents=parents->next;\n+\t\t}\n+\t\tnext=next->next;\n+\t\tnext_node++;\n+\t}\n+\t/*\n+\t * Process the work queue until done.\n+\t */\n+\twhile (work) {\n+\t\tstruct commit * work_item = pop_commit(&work);\n+\t\tstruct bisect_by_cut_node * wn = get_bisect_by_cut_node(work_item);\n+\t\tstruct commit_list * children = wn->children;\n+\t\tunsigned int goal_test = wn->count;\n+\t        unsigned int fitness = (goal_test>goal)?(goal_test-goal):(goal-goal_test);\n+\n+\t\tif (fitness < fittest) {\n+\t\t\tbest = work_item;\n+\t\t\tfittest = fitness;\n+\t\t}\n+\t\tif (goal_test < goal) {\n+\t\t\twhile (children) {\n+\t\t\t\tstruct bisect_by_cut_node * cn \n+\t\t\t\t\t= get_bisect_by_cut_node(children->item);\n+\t\t\t\tif (cn->flags & ABOVE) {\n+\t\t\t\t\t/* move the boundary up */\n+\t\t\t\t\tcn->flags &= ~ABOVE;\n+\t\t\t\t\tif (cn->visible_parents && !cn->visible_parents->next)\n+\t\t\t\t\t\t/* \n+\t\t\t\t\t\t * If the child only has one visible parent\n+\t\t\t\t\t\t * the goal_test increases by one\n+\t\t\t\t\t\t */\n+\t\t\t\t\t\tcn->count = wn->count+1;\n+\t\t\t\t\telse {\n+\t\t\t\t\t\t/*\n+\t\t\t\t\t\t * Otherwise, we need to count it explicitly.\n+\t\t\t\t\t\t */\n+\t\t\t\t\t\tcounter.item=children->item;\n+\t\t\t\t\t\tcn->count = count_distance(&counter);\n+\t\t\t\t\t\tclear_distance(topological_order);\n+\t\t\t\t\t}\n+\t\t\t\t\tcommit_list_insert(children->item, &work);\n+\t\t\t\t}\n+\t\t\t\tchildren=children->next;\n+\t\t\t}\n+\t\t} else if (goal_test > goal)\n+\t\t\tcontinue;\n+\t\telse \n+\t\t\tbreak; /* can't do better than this */\n+\t}\n+\tif (work)\n+\t\tfree_commit_list(work);\n+\t/*\n+\t * reset the util pointers.\n+\t */\n+\tnext=topological_order;\n+\twhile (next) {\n+\t\tnext->item->object.util=NULL;\n+\t\tnext = next->next;\n+\t}\n+\tfree(nodes);\n+\treturn best;\n+}\ndiff --git a/commit.h b/commit.h\n--- a/commit.h\n+++ b/commit.h\n@@ -4,6 +4,10 @@\n #include \"object.h\"\n #include \"tree.h\"\n \n+#define UNINTERESTING    (1u<<0)\n+#define COUNTED          (1u<<1)\n+#define LAST_COMMIT_FLAG (COUNTED)\n+\n struct commit_list {\n \tstruct commit *item;\n \tstruct commit_list *next;\n@@ -68,4 +72,17 @@ int count_parents(struct commit * commit\n  *      a reachable from b => ord(b) < ord(a)\n  */\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+ */\n+struct commit * bisect_by_cut(struct commit_list * topological_order);\n #endif /* COMMIT_H */\ndiff --git a/epoch.h b/epoch.h\n--- a/epoch.h\n+++ b/epoch.h\n@@ -10,12 +10,10 @@ typedef int (*emitter_func) (struct comm\n \n int sort_list_in_merge_order(struct commit_list *list, emitter_func emitter);\n \n-#define UNINTERESTING   (1u<<2)\n-#define BOUNDARY        (1u<<3)\n-#define VISITED         (1u<<4)\n-#define DISCONTINUITY   (1u<<5)\n-#define DUPCHECK        (1u<<6)\n-#define LAST_EPOCH_FLAG (1u<<6)\n-\n+#define BOUNDARY        (LAST_COMMIT_FLAG<<1)\n+#define VISITED         (LAST_COMMIT_FLAG<<2)\n+#define DISCONTINUITY   (LAST_COMMIT_FLAG<<3)\n+#define DUPCHECK        (LAST_COMMIT_FLAG<<4)\n+#define LAST_EPOCH_FLAG (DUPCHECK)\n \n #endif\t/* EPOCH_H */\ndiff --git a/rev-list.c b/rev-list.c\n--- a/rev-list.c\n+++ b/rev-list.c\n@@ -5,19 +5,9 @@\n #include \"blob.h\"\n #include \"epoch.h\"\n \n-#define ABOVE        (1u<<1)\n-struct bisect_by_cut_node \n-{\n-\tunsigned int flags;\n-\tunsigned int count;\n-\tstruct commit_list * children;\n-\tstruct commit_list * visible_parents;\n-};\n-\n #define SEEN        (LAST_EPOCH_FLAG << 1)\n #define INTERESTING (LAST_EPOCH_FLAG << 2)\n-#define COUNTED     (LAST_EPOCH_FLAG << 3)\n-#define SHOWN       (LAST_EPOCH_FLAG << 4)\n+#define SHOWN       (LAST_EPOCH_FLAG << 3)\n \n static const char rev_list_usage[] =\n \t\"usage: git-rev-list [OPTION] commit-id <commit-id>\\n\"\n@@ -245,78 +235,6 @@ static int everybody_uninteresting(struc\n \treturn 1;\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\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}\t\t\t\n-\t\t}\n-\t}\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-static 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 struct commit_list *limit_list(struct commit_list *list)\n {\n \tstruct commit_list *newlist = NULL;\n@@ -410,183 +328,6 @@ static struct commit *get_commit_referen\n \tdie(\"%s is unknown object\", name);\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;\n-}\n-\n-/*\n- * Find the best bisection point by cutting a topological order in two then\n- * identifying a set of boundary nodes with a reachability known to be \n- * less than the desired bisection point. The boundary is advanced until all nodes\n- * in the boundary have a reachability greater than or equal to the desired \n- * reachability.\n- *\n- * This algorithm is roughly O(kn) where k is a factor related to the typical\n- * amount of parallel branching within the graph and is not related to n.\n- *\n- * The algorithm borrows the notion of making an arbitrary cut in the graph\n- * from the Kernighan-Lin (1969) graph bisection algorithm but differs in\n- * other respects. In particular, by using the topological order to make the\n- * cut the width of the advancing boundary is reduced to some kind of minimum.\n- * Full graph scans (e.g. calls to count_distance()) are avoided except where\n- * absolutely necessary (i.e. a merge node is encountered).\n- */\n-struct commit * bisect_by_cut(struct commit_list * topological_order)\n-{\n-\tunsigned int count=0;\n-\tunsigned int i;\n-\tstruct commit_list * next;\n-\tstruct commit_list * work = NULL;\n-\tstruct commit * best = topological_order->item;\n-\tstruct bisect_by_cut_node * nodes;\n-\tstruct bisect_by_cut_node * next_node;\n-\tstruct commit_list counter;\n-\tunsigned int fittest, goal;\n-\n-\tcounter.next=NULL;\n-\t/* count the size of the topological order */\n-\tnext=topological_order;\n-\twhile (next) {\n-\t\tcount++;\n-\t\tnext = next->next;\n-\t}\n-\tfittest=count;\n-\ti=(count+1)/2;\n-\tgoal=count/2;\n-\t/* allocate and initialize the bisect_by_cut_node structure */\n-\tnext_node=nodes=xmalloc(sizeof(*nodes)*count);\n-\tmemset(nodes, 0, sizeof(*nodes)*count);\n-\t/* \n-\t * initialize the structures for all nodes of interest\n-\t */\n-\tnext=topological_order;\n-\tnext_node=nodes;\n-\twhile (next) {\t\t\n-\t\tnext->item->object.util=next_node++;\n-\t\tnext=next->next;\n-\t}\n-\t/*\n-\t * Mark half the nodes as being above the boundary.\n-\t * Mark nodes that aren't in the topological order as uninteresting.\n-\t * Initialize lists of visible children and parents.\n-\t */\n-\tnext=topological_order;\n-\tnext_node=nodes;\n-\twhile (next) {\t\t\n-\t\tstruct commit * next_item = next->item;\n-\t\tstruct commit_list * parents;\n-\t\t\n-\t\tif (i > 0) {\n-\t\t\tnext_node->flags |= ABOVE;\n-\t\t\ti--;\n-\t\t}\t\t\t\n-\t\tparents=next_item->parents;\n-\t\twhile (parents) {\n-\t\t\tstruct commit * parent = parents->item;\n-\t\t\tstruct bisect_by_cut_node * pn = get_bisect_by_cut_node(parent);\n-\n-\t\t\tif (pn) {\n-\t\t\t\tcommit_list_insert(next_item, &pn->children);\n-\t\t\t\tcommit_list_insert(parent, &next_node->visible_parents);\n-\t\t\t} else \n-\t\t\t\tparent->object.flags |= UNINTERESTING;\n-\t\t\tparent->object.flags &= ~COUNTED;\n-\t\t\tparents=parents->next;\n-\t\t}\n-\t\tnext=next->next;\n-\t\tnext_node++;\n-\t}\n-\t/*\n-\t * Initialize the work queue with commits that are on the boundary\n-\t * and with < the desired reachability.\n-\t * \n-\t * We know these commits have less than the desired \n-\t * reachability because by the definition of the topological order\n-\t * nodes can only reach nodes to the right of them in the topological\n-\t * order and by construction, there there are no more than \n-\t * (count-1)/2 nodes to the right of each node in the boundary.\n-\t */\n-\tnext=topological_order;\n-\tnext_node=nodes;\n-\twhile (next) {\n-\t\tstruct commit_list * parents;\n-\n-\t\tparents=next_node->visible_parents;\n-\t\twhile (parents) {\n-\t\t\tstruct bisect_by_cut_node * pn = get_bisect_by_cut_node(parents->item);\n-\n-\t\t\tif ((next_node->flags & ABOVE) \n-\t\t\t     && !(pn->flags & ABOVE) \n-\t\t\t     && (pn->count == 0)) {\n-\t\t\t\tcounter.item=parents->item;\n-\t\t\t\tpn->count = count_distance(&counter);\n-\t\t\t\tclear_distance(topological_order);\n-\t\t\t\tcommit_list_insert(parents->item, &work);\n-\t\t\t}\n-\t\t\tparents=parents->next;\n-\t\t}\n-\t\tnext=next->next;\n-\t\tnext_node++;\n-\t}\n-\t/*\n-\t * Process the work queue until done.\n-\t */\n-\twhile (work) {\n-\t\tstruct commit * work_item = pop_commit(&work);\n-\t\tstruct bisect_by_cut_node * wn = get_bisect_by_cut_node(work_item);\n-\t\tstruct commit_list * children = wn->children;\n-\t\tunsigned int goal_test = wn->count;\n-\t        unsigned int fitness = (goal_test>goal)?(goal_test-goal):(goal-goal_test);\n-\n-\t\tif (fitness < fittest) {\n-\t\t\tbest = work_item;\n-\t\t\tfittest = fitness;\n-\t\t}\n-\t\tif (goal_test < goal) {\n-\t\t\twhile (children) {\n-\t\t\t\tstruct bisect_by_cut_node * cn \n-\t\t\t\t\t= get_bisect_by_cut_node(children->item);\n-\t\t\t\tif (cn->flags & ABOVE) {\n-\t\t\t\t\t/* move the boundary up */\n-\t\t\t\t\tcn->flags &= ~ABOVE;\n-\t\t\t\t\tif (cn->visible_parents && !cn->visible_parents->next)\n-\t\t\t\t\t\t/* \n-\t\t\t\t\t\t * If the child only has one visible parent\n-\t\t\t\t\t\t * the goal_test increases by one\n-\t\t\t\t\t\t */\n-\t\t\t\t\t\tcn->count = wn->count+1;\n-\t\t\t\t\telse {\n-\t\t\t\t\t\t/*\n-\t\t\t\t\t\t * Otherwise, we need to count it explicitly.\n-\t\t\t\t\t\t */\n-\t\t\t\t\t\tcounter.item=children->item;\n-\t\t\t\t\t\tcn->count = count_distance(&counter);\n-\t\t\t\t\t\tclear_distance(topological_order);\n-\t\t\t\t\t}\n-\t\t\t\t\tcommit_list_insert(children->item, &work);\n-\t\t\t\t}\n-\t\t\t\tchildren=children->next;\n-\t\t\t}\n-\t\t} else if (goal_test > goal)\n-\t\t\tcontinue;\n-\t\telse \n-\t\t\tbreak; /* can't do better than this */\n-\t}\n-\tif (work)\n-\t\tfree_commit_list(work);\n-\t/*\n-\t * reset the util pointers.\n-\t */\n-\tnext=topological_order;\n-\twhile (next) {\n-\t\tnext->item->object.util=NULL;\n-\t\tnext = next->next;\n-\t}\n-\tfree(nodes);\n-\treturn best;\n-}\n-\n int main(int argc, char **argv)\n {\n \tstruct commit_list *list = NULL;\n------------\n"}]}