{"thread":{"id":"1067","subject":"[PATCH] Add a topological sort procedure to commit.c [rev 3]","startedAt":"2005-07-01T06:31:15Z","lastAt":"2005-07-01T06:31:15Z","messageCount":1,"participants":["Jon Seymour"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"5509","messageId":"20050701063115.1079.qmail@blackcubes.dyndns.org","threadId":"1067","inReplyTo":null,"subject":"[PATCH] Add a topological sort procedure to commit.c [rev 3]","fromName":"Jon Seymour","fromEmail":"jon.seymour@gmail.com","sentAt":"2005-07-01T06:31:15Z","receivedAt":"2005-07-01T06:31:15Z","isPatch":true,"sender":{"key":"jon.seymour@gmail.com","avatar":"https://avatars.githubusercontent.com/u/207131?v=4"},"body":"\nThis patch introduces an in-place topological sort procedure to commit.c.\n\nGiven a list of commits, sort_in_topological_order() will perform an in-place\ntopological sort of that list.\n\nThe invariant that applies to the resulting list is:\n\n       a reachable from b => ord(b) < ord(a)\n\nThis invariant is weaker than the --merge-order invariant, but is cheaper\nto calculate (assuming the list has been identified) and will serve any\npurpose where only a minimal topological order guarantee is required.\n\nSigned-off-by: Jon Seymour <jon.seymour@gmail.com>\n---\nNote: this patch currently has no observable consequences since nothing\nin this patch calls it. A future patch will use this algorithm to provide\nan O(n) bisection algorithm as a suggested replacement for the\nexisting O(n^2) bisection algorithm.\n\nThis patch is a complete replacement for earlier revisions of this patch.\n\n[rev 2]\n  * incorporates Junio's questions/comments as commentary,\n  * adds object.util save/restore functionality so that no\n    assumption is made about the pre-existing state of object.util\n    upon entry to the procedure.\n[rev 3]\n  * removed object.util save/restore\n  * added more documentation to header about pre-conditions\n---\n\n commit.c |  107 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n commit.h |   13 ++++++++\n 2 files changed, 120 insertions(+), 0 deletions(-)\n\n5213443ab584624c3ebcec9a6d2624615c934e5b\ndiff --git a/commit.c b/commit.c\n--- a/commit.c\n+++ b/commit.c\n@@ -3,6 +3,22 @@\n #include \"commit.h\"\n #include \"cache.h\"\n \n+struct sort_node\n+{\n+\t/*\n+         * the number of children of the associated commit\n+         * that also occur in the list being sorted.\n+         */\n+\tunsigned int indegree;\n+\n+\t/*\n+         * reference to original list item that we will re-use\n+         * on output.\n+         */\n+\tstruct commit_list * list_item;\n+\n+};\n+\n const char *commit_type = \"commit\";\n \n enum cmit_fmt get_commit_format(const char *arg)\n@@ -346,3 +362,94 @@ int count_parents(struct commit * commit\n         return count;\n }\n \n+/*\n+ * Performs an in-place topological sort on the list supplied.\n+ */\n+void sort_in_topological_order(struct commit_list ** list)\n+{\n+\tstruct commit_list * next = *list;\n+\tstruct commit_list * work = NULL;\n+\tstruct commit_list ** pptr = list;\n+\tstruct sort_node * nodes;\n+\tstruct sort_node * next_nodes;\n+\tint count = 0;\n+\n+\t/* determine the size of the list */\n+\twhile (next) {\n+\t\tnext = next->next;\n+\t\tcount++;\n+\t}\n+\t/* allocate an array to help sort the list */\n+\tnodes = xcalloc(count, sizeof(*nodes));\n+\t/* link the list to the array */\n+\tnext_nodes = nodes;\n+\tnext=*list;\n+\twhile (next) {\n+\t\tnext_nodes->list_item = next;\n+\t\tnext->item->object.util = next_nodes;\n+\t\tnext_nodes++;\n+\t\tnext = next->next;\n+\t}\n+\t/* update the indegree */\n+\tnext=*list;\n+\twhile (next) {\n+\t\tstruct commit_list * parents = next->item->parents;\n+\t\twhile (parents) {\n+\t\t\tstruct commit * parent=parents->item;\n+\t\t\tstruct sort_node * pn = (struct sort_node *)parent->object.util;\n+\t\t\t\n+\t\t\tif (pn)\n+\t\t\t\tpn->indegree++;\n+\t\t\tparents=parents->next;\n+\t\t}\n+\t\tnext=next->next;\n+\t}\n+\t/* \n+         * find the tips\n+         *\n+         * tips are nodes not reachable from any other node in the list \n+         * \n+         * the tips serve as a starting set for the work queue.\n+         */\n+\tnext=*list;\n+\twhile (next) {\n+\t\tstruct sort_node * node = (struct sort_node *)next->item->object.util;\n+\n+\t\tif (node->indegree == 0) {\n+\t\t\tcommit_list_insert(next->item, &work);\n+\t\t}\n+\t\tnext=next->next;\n+\t}\n+\t/* process the list in topological order */\n+\twhile (work) {\n+\t\tstruct commit * work_item = pop_commit(&work);\n+\t\tstruct sort_node * work_node = (struct sort_node *)work_item->object.util;\n+\t\tstruct commit_list * parents = work_item->parents;\n+\n+\t\twhile (parents) {\n+\t\t\tstruct commit * parent=parents->item;\n+\t\t\tstruct sort_node * pn = (struct sort_node *)parent->object.util;\n+\t\t\t\n+\t\t\tif (pn) {\n+\t\t\t\t/* \n+\t\t\t\t * parents are only enqueued for emission \n+                                 * when all their children have been emitted thereby\n+                                 * guaranteeing topological order.\n+                                 */\n+\t\t\t\tpn->indegree--;\n+\t\t\t\tif (!pn->indegree) \n+\t\t\t\t\tcommit_list_insert(parent, &work);\n+\t\t\t}\n+\t\t\tparents=parents->next;\n+\t\t}\n+\t\t/*\n+                 * work_item is a commit all of whose children\n+                 * have already been emitted. we can emit it now.\n+                 */\n+\t\t*pptr = work_node->list_item;\n+\t\tpptr = &(*pptr)->next;\n+\t\t*pptr = NULL;\n+\t\twork_item->object.util = NULL;\n+\t}\n+\tfree(nodes);\n+}\ndiff --git a/commit.h b/commit.h\n--- a/commit.h\n+++ b/commit.h\n@@ -55,4 +55,17 @@ struct commit *pop_most_recent_commit(st\n struct commit *pop_commit(struct commit_list **stack);\n \n int count_parents(struct commit * commit);\n+\n+/*\n+ * Performs an in-place topological sort of list supplied.\n+ *\n+ * Pre-conditions:\n+ *   all commits in input list and all parents of those\n+ *   commits must have object.util == NULL\n+ *        \n+ * Post-conditions: \n+ *   invariant of resulting list is:\n+ *      a reachable from b => ord(b) < ord(a)\n+ */\n+void sort_in_topological_order(struct commit_list ** list);\n #endif /* COMMIT_H */\n------------\n"}]}