{"thread":{"id":"928","subject":"[PATCH 3/7] Rename epoch.c entry points as traverse_* methods/stuctures","startedAt":"2005-06-14T02:04:38Z","lastAt":"2005-06-14T02:04:38Z","messageCount":1,"participants":["Jon Seymour"],"isPatch":true,"patchVersion":1,"patchTotal":7},"messages":[{"id":"4931","messageId":"20050614020438.23292.qmail@blackcubes.dyndns.org","threadId":"928","inReplyTo":null,"subject":"[PATCH 3/7] Rename epoch.c entry points as traverse_* methods/stuctures","fromName":"Jon Seymour","fromEmail":"jon.seymour@gmail.com","sentAt":"2005-06-14T02:04:38Z","receivedAt":"2005-06-14T02:04:38Z","isPatch":true,"sender":{"key":"jon.seymour@gmail.com","avatar":"https://avatars.githubusercontent.com/u/207131?v=4"},"body":"\nThe entry points in epoch.c have been renamed to reflect the\nfact that they are actually traversal methods rather than\nsorting methods.\n\nAlso, struct epoch_methods has been renamed as struct traversal.\n\nA future change will rename epoch.[ch] as traversal.[ch]\n\nSigned-off-by: Jon Seymour <jon.seymour@gmail.com>\n---\n\n epoch.c    |  107 ++++++++++++++++++++++++++++++------------------------------\n epoch.h    |   32 +++++++++++-------\n rev-list.c |   12 +++----\n 3 files changed, 80 insertions(+), 71 deletions(-)\n\ndiff --git a/epoch.c b/epoch.c\n--- a/epoch.c\n+++ b/epoch.c\n@@ -200,14 +200,14 @@ static void free_mass_counter(struct mas\n /*\n  * This function calls the supplied commit_visitor method, if there is one.\n  */\n-static void visit_commit(struct epoch_methods * methods, struct commit * commit, int first_visit)\n+static void visit_commit(struct traversal * traversal, struct commit * commit, int first_visit)\n {\n \t/*\n \t * pre-condition:\n \t * \tfirst_visit => object.util == NULL\n \t */\n-\tif (methods->commit_visitor)\n-\t\t(*(methods->commit_visitor))(commit, first_visit);\n+\tif (traversal->commit_visitor)\n+\t\t(*(traversal->commit_visitor))(commit, first_visit);\n }\n \n /*\n@@ -216,15 +216,15 @@ static void visit_commit(struct epoch_me\n  * are offered about when this call will be made w.r.t. to the call\n  * to visit_commit(..., to, 1)\n  */\n-static void visit_edge(struct epoch_methods * methods, struct commit * from, struct commit * to)\n+static void visit_edge(struct traversal * traversal, struct commit * from, struct commit * to)\n {\n \t/*\n \t * pre-condition:\n \t * \tfrom->object.flags & VISITED &&\n \t * \tto->object.util => (to->object.flags & VISITED)\n \t */ \n-\tif (methods->edge_visitor)\n-\t\t(*(methods->edge_visitor))(from, to);\n+\tif (traversal->edge_visitor)\n+\t\t(*(traversal->edge_visitor))(from, to);\n }\n \n /*\n@@ -235,19 +235,19 @@ static void visit_edge(struct epoch_meth\n  * It is the implementer's responsibility to perform output limiting if \n  * that is required.\n  */\n-static int emit_commit(struct epoch_methods * methods, struct commit * commit)\n+static int emit_commit(struct traversal * traversal, struct commit * commit)\n {\n-\treturn (*(methods->emitter))(commit);\n+\treturn (*(traversal->emitter))(commit);\n }\n \n /*\n  * Invoke a call back method to allow the tactics to release and storage\n  * allocated during a previous visit_commit or visit_edge call.\n  */\n-static void clean_commit(struct epoch_methods * methods, struct commit * commit)\n+static void clean_commit(struct traversal * traversal, struct commit * commit)\n {\n-\tif (methods->clean)\n-\t\t(*(methods->clean))(commit);\n+\tif (traversal->clean)\n+\t\t(*(traversal->clean))(commit);\n \tcommit->object.util = NULL;\n \tcommit->object.flags &= ~(EPOCH_FLAGS);\n \t/*\n@@ -256,9 +256,9 @@ static void clean_commit(struct epoch_me\n \t */\t\t\n }\n \n-void init_epoch_methods(struct epoch_methods * methods)\n+void init_traversal(struct traversal * traversal)\n {\n-\tmemset(methods, 0, sizeof(*methods));\n+\tmemset(traversal, 0, sizeof(*traversal));\n }\n \n /*\n@@ -475,14 +475,14 @@ static void mark_ancestors_uninteresting\n static void sort_unvisited(\n \tstruct commit *head, \n \tstruct commit_list **stack, \n-\tstruct epoch_methods * methods)\n+\tstruct traversal * traversal)\n {\n \tstruct commit_list *parents = NULL;\n         struct commit * top = *stack?(*stack)->item:NULL;\n \n \tif (IS_VISITED(head)) {\n \t\tif (!IS_BASE(head)) {\n-\t\t\tvisit_commit(methods, head, 0);\n+\t\t\tvisit_commit(traversal, head, 0);\n \t\t}\n \t\treturn;\n \t}\n@@ -496,15 +496,15 @@ static void sort_unvisited(\n \t\t\tparents = (struct commit_list *)head->object.util;\n                         head->object.util = NULL;\n \t\t}\n-\t\tvisit_commit(methods, head, 1);\n+\t\tvisit_commit(traversal, head, 1);\n \t\twhile (parents) {\n \t\t\tstruct commit *parent = pop_commit(&parents);\n \n \t\t\tif (IS_UNINTERESTING(head)) {\n \t\t\t\tmark_ancestors_uninteresting(parent);\n \t\t\t}\n-\t\t\tvisit_edge(methods, head, parent);\n-\t\t\tsort_unvisited(parent, stack, methods);\n+\t\t\tvisit_edge(traversal, head, parent);\n+\t\t\tsort_unvisited(parent, stack, traversal);\n \t\t}\t\t\n \t\ttop=(*stack)?(*stack)->item:NULL;\n \t\tif (top && !is_parent_of(top, head)) {\n@@ -519,15 +519,15 @@ static void sort_unvisited(\n  * The stack is freed and replaced by NULL.\n  * Sets the return value to STOP if the traversal should stop.\n  */\n-static int emit_stack(struct commit_list **stack, struct epoch_methods * methods)\n+static int emit_stack(struct commit_list **stack, struct traversal * traversal)\n {\n \tint stop = 0;\n \n \twhile (*stack) {\n \t\tstruct commit *next = pop_commit(stack);\n \t\t\n-\t\tstop = (emit_commit(methods, next)==STOP) || (next->object.flags & UNINTERESTING) || stop ;\n-\t\tclean_commit(methods, next);\n+\t\tstop = (emit_commit(traversal, next)==STOP) || (next->object.flags & UNINTERESTING) || stop ;\n+\t\tclean_commit(traversal, next);\n \t}\n \treturn stop ? STOP : CONTINUE;\n }\n@@ -573,13 +573,13 @@ static struct commit_list ** move(struct\n  * The return value contains LOCAL if any of the list is local or had a \n  * local ancestor.\n  */\n-static unsigned int sort_local_branches_first(struct commit_list ** list, struct epoch_methods * methods)\n+static unsigned int sort_local_branches_first(struct commit_list ** list, struct traversal * traversal)\n {\n \tstruct commit_list *local = NULL;\n \tstruct commit_list **local_tail = &local;\n \tstruct commit_list **non_local_ptr;\n \n-\tASSERT(methods->local_test, \"local_test method is defined\", NULL);\n+\tASSERT(traversal->local_test, \"local_test method is defined\", NULL);\n \tif (!*list) {\n \t\treturn 0;\n \t}\n@@ -593,11 +593,11 @@ static unsigned int sort_local_branches_\n \t\tif (!IS_BASE(item) && !item->object.util) {\n \t\t\tstruct commit_list ** copied;\n \t\t\t\n-\t\t\tif ((*(methods->local_test)) (item))\n+\t\t\tif ((*(traversal->local_test)) (item))\n \t\t\t\titem->object.flags |= LOCAL;\n \t\t\tcopied=copy_and_store_parents(item);\n \t\t\titem->object.flags \n-\t\t\t    |= sort_local_branches_first(copied, methods);\n+\t\t\t    |= sort_local_branches_first(copied, traversal);\n \t\t}\n \t\t/**\n \t\t * Move local items onto their own list.\n@@ -622,22 +622,22 @@ static unsigned int sort_local_branches_\n  * reach the base and emitting as we go. We don't emit the base\n  * now.\n  */\n-static int sort_maximal_linear_epoch(struct commit *head, struct epoch_methods * methods)\n+static int sort_maximal_linear_epoch(struct commit *head, struct traversal * traversal)\n {\n \tstruct commit * next;\n \tstruct commit * base;\n \tint stop = 0;\n \t\n \t/* invoke the visitors, if any */\n-\tif (methods->commit_visitor || methods->edge_visitor) {\n+\tif (traversal->commit_visitor || traversal->edge_visitor) {\n \t\tfor (next = head; !IS_BASE(next); next = next->parents->item) {\n-\t\t\tvisit_commit(methods, next, 1);\n-\t\t\tvisit_edge(methods, next, next->parents->item);\n+\t\t\tvisit_commit(traversal, next, 1);\n+\t\t\tvisit_edge(traversal, next, next->parents->item);\n \t\t}\n \t}\t\t\n \t/* now emit the nodes, and mark the base*/\n \tfor (next = head; !IS_BASE(next); next = next->parents->item) {\n-\t\tstop = (emit_commit(methods, next)==STOP) || stop;\n+\t\tstop = (emit_commit(traversal, next)==STOP) || stop;\n \t\tif (IS_UNINTERESTING(next)) {\n \t\t\tnext->parents->item->object.flags |= UNINTERESTING;\n \t\t\tstop = 1;\n@@ -646,7 +646,7 @@ static int sort_maximal_linear_epoch(str\n \tbase = next;\t\t\n \t/* then clean the nodes */\n \tfor (next = head; next != base; next = next->parents->item) \n-\t\tclean_commit(methods, next);\n+\t\tclean_commit(traversal, next);\n \t\t\n \treturn stop ? STOP : CONTINUE;\n }\n@@ -657,20 +657,20 @@ static int sort_maximal_linear_epoch(str\n  * parents of each commit in the epoch, if required, then emitting\n  * the stack.\n  */\n-static int sort_minimal_non_linear_epoch(struct commit *head, struct epoch_methods * methods)\n+static int sort_minimal_non_linear_epoch(struct commit *head, struct traversal * traversal)\n {\n \tstruct commit_list *stack = NULL;\t\n \n-\tif (methods->local_test) \n-\t\tsort_local_branches_first(copy_and_store_parents(head),\tmethods);\n-\tsort_unvisited(head, &stack, methods);\n-\treturn emit_stack(&stack, methods);\n+\tif (traversal->local_test) \n+\t\tsort_local_branches_first(copy_and_store_parents(head),\ttraversal);\n+\tsort_unvisited(head, &stack, traversal);\n+\treturn emit_stack(&stack, traversal);\n }\n+\n /*\n- * Sorts an arbitrary epoch into merge order by sorting each epoch\n- * of its epoch sequence into order.\n+ * see epoch.h\n  */\n-static int sort_in_merge_order(struct commit *head, struct epoch_methods * methods)\n+int traverse_from_head(struct commit *head, struct traversal * traversal)\n {\n \tstruct commit *next = head;\n \tint ret = 0;\n@@ -699,9 +699,9 @@ static int sort_in_merge_order(struct co\n \t\t\n \t\t/* sort with the optimal algorithm */\n \t\tif (HAS_EXACTLY_ONE_PARENT(next))\n-\t\t\tnext_action = sort_maximal_linear_epoch(next, methods);\n+\t\t\tnext_action = sort_maximal_linear_epoch(next, traversal);\n \t\telse\n-\t\t\tnext_action = sort_minimal_non_linear_epoch(next, methods);\n+\t\t\tnext_action = sort_minimal_non_linear_epoch(next, traversal);\n \t\t\t\n \t\t/* stop or iterate */\t\t\t\n \t\tif (next_action == STOP)\n@@ -710,26 +710,27 @@ static int sort_in_merge_order(struct co\n \t\t\tnext = base;\n \t}\n \tif (next)\n-\t\temit_commit(methods, next);\n+\t\temit_commit(traversal, next);\n \treturn 0;\n }\n \n /*\n- * Sorts the nodes reachable from a starting list in merge order, we\n+ * see epoch.h\n+ * Traverses the nodes reachable from a starting list in merge order, we\n  * first find the base for the starting list and then sort all nodes\n  * in this subgraph using the sort_unvisited algorithm. Once we have\n- * reached the base we can continue sorting using sort_in_merge_order.\n+ * reached the base we can continue sorting using traverse_from_head.\n  */\n-int sort_list_in_merge_order(struct commit_list *list, struct epoch_methods * methods)\n+int traverse_from_list(struct commit_list *list, struct traversal * traversal)\n {\n \tstruct commit_list *stack = NULL;\n \tstruct commit_list *filtered = NULL;\n \tstruct commit *base;\n \tint ret = 0;\n \n-\tif (!methods) \n-\t\tdie(\"methods argument must not be null\");\n-\tif (!methods->emitter)\n+\tif (!traversal) \n+\t\tdie(\"traversal argument must not be null\");\n+\tif (!traversal->emitter)\n \t\tdie(\"an emitter method must be supplied\");\n \t/**\n \t * Remove duplicates and uninteresting items.\n@@ -765,15 +766,15 @@ int sort_list_in_merge_order(struct comm\n \t\t\tbase->object.flags |= (BOUNDARY|BASE);\n \n \t\t/* sort local branches first, so they print last */\t\t\t\n-\t\tif (methods->local_test)\n-\t\t\tsort_local_branches_first(&filtered, methods);\t\t\t\n+\t\tif (traversal->local_test)\n+\t\t\tsort_local_branches_first(&filtered, traversal);\t\t\t\n \n \t\t/* sort the unvisited part of the epoch in merge order */\n \t\twhile (filtered)\n-\t\t\tsort_unvisited(pop_commit(&filtered), &stack, methods);\n+\t\t\tsort_unvisited(pop_commit(&filtered), &stack, traversal);\n \t\t\n \t\t/* output the stack */\n-\t\tif (emit_stack(&stack, methods) == STOP) \n+\t\tif (emit_stack(&stack, traversal) == STOP) \n \t\t\treturn STOP;\t\t\t\n \t} else {\n \t\t/*\n@@ -786,6 +787,6 @@ int sort_list_in_merge_order(struct comm\n \n         /* sort the rest with the sort_in_merge_order algorithm. */\n \tif (base)\n-\t\tret = sort_in_merge_order(base, methods);\n+\t\tret = traverse_from_head(base, traversal);\n \treturn ret;\n }\ndiff --git a/epoch.h b/epoch.h\n--- a/epoch.h\n+++ b/epoch.h\n@@ -22,11 +22,12 @@\n #define CONTINUE 1\n #define DO       2\n \n-struct epoch_methods {\n+struct traversal {\n \t/*\n \t * Returns 0 if traversal should stop, non-zero if it should continue.\n \t */\n \tint (*emitter)(struct commit *);\n+\n \t/* \n \t * Returns non-zero if the commit is regarded \"local\", 0 otherwise.\n \t */\n@@ -60,20 +61,27 @@ struct epoch_methods {\n ;\n \n /**\n- * Initializes an epoch_methods structure which\n+ * Initializes a traversal structure which\n  * may be customized by the caller by overriding any of the method pointers.\n  */\n-extern void init_epoch_methods(struct epoch_methods *);\n+extern void init_traversal(struct traversal *);\n+\n+/**\n+ * Traverses the commit graph from the commits listed. \n+ *\n+ * The traversal is performed in (optionally localised) merge order \n+ * which is defined by invariants specified in Documentation/git-rev-list.txt\n+ *\n+ * The tactics used during the traversal can be customized\n+ * by configuring the traversal structure with appropriately\n+ * defined method pointers.\n+\n+ */\n+extern int traverse_from_list(struct commit_list *list, struct traversal * traversal);\n \n /**\n- * Sorts the list of commits in merge order, using the methods specified\n- * to customize the tactics of the search.\n- * \n- * The prune points should be marked with the UNINTERESTING flags. \n- * \n- * Note: this algorithm is dirty in the sense that it leaves traces\n- * of its execution in the object.flags word of some or all of the commits\n- * visited.\n+ * Traverses the commit graph from the head commit listed. In other\n+ * respects, like traverse_from_list.\n  */\n-extern int sort_list_in_merge_order(struct commit_list *list, struct epoch_methods * methods);\n+extern int traverse_from_head(struct commit *head, struct traversal * traversal);\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@@ -179,9 +179,9 @@ static void mark_authors_own_uninteresti\n \n static void merge_order_traversal(struct commit_list * list)\n {\n-\tstruct epoch_methods methods;\n+\tstruct traversal traversal;\n \n-\tinit_epoch_methods(&methods);\n+\tinit_traversal(&traversal);\n \tif ((prune_at_author|wrt_author) && !local_author) {\n \t\tlocal_author = gitenv(\"GIT_AUTHOR_EMAIL\") ? : NULL;\t\t\t    \n \t\tif (!local_author)\n@@ -196,12 +196,12 @@ static void merge_order_traversal(struct\n \t\t    free(local_author);\n \t\t    local_author = tmp;\n \t}\t\t \n-\tmethods.emitter = &process_commit;\t\t  \n+\ttraversal.emitter = &process_commit;\t\t  \n \tif (wrt_author)\n-\t\tmethods.local_test = &is_local_author;\n+\t\ttraversal.local_test = &is_local_author;\n \tif (prune_at_author)\n-\t\tmethods.commit_visitor = &mark_authors_own_uninteresting;\n-\tif (sort_list_in_merge_order(list, &methods))\n+\t\ttraversal.commit_visitor = &mark_authors_own_uninteresting;\n+\tif (traverse_from_list(list, &traversal))\n \t\tdie(\"merge order sort failed\\n\");\n }\n \n------------\n"}]}