Simplify topo-sort logic

.. by not using quite so much indirection.

This currently grows the "struct commit" a bit, which could be avoided by
using a union for "util" and "indegree" (the topo-sort used to use "util"
anyway, so you cannot use them together), but for now the goal of this was
to simplify, not optimize.

Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

1 files changed, 52 insertions, 98 deletions

diff --git a/commit.c b/commit.c
index 8262f6ac58..ab4eb8bdd1 100644
--- a/commit.c
+++ b/commit.c
@@ -9,22 +9,6 @@
 
 int save_commit_buffer = 1;
 
-struct sort_node
-{
-	/*
-	 * the number of children of the associated commit
-	 * that also occur in the list being sorted.
-	 */
-	unsigned int indegree;
-
-	/*
-	 * reference to original list item that we will re-use
-	 * on output.
-	 */
-	struct commit_list * list_item;
-
-};
-
 const char *commit_type = "commit";
 
 static struct cmt_fmt_map {
@@ -1149,69 +1133,38 @@ struct commit *pop_commit(struct commit_list **stack)
 	return item;
 }
 
-void topo_sort_default_setter(struct commit *c, void *data)
-{
-	c->util = data;
-}
-
-void *topo_sort_default_getter(struct commit *c)
-{
-	return c->util;
-}
-
 /*
  * Performs an in-place topological sort on the list supplied.
  */
 void sort_in_topological_order(struct commit_list ** list, int lifo)
 {
-	sort_in_topological_order_fn(list, lifo, topo_sort_default_setter,
-				     topo_sort_default_getter);
-}
-
-void sort_in_topological_order_fn(struct commit_list ** list, int lifo,
-				  topo_sort_set_fn_t setter,
-				  topo_sort_get_fn_t getter)
-{
-	struct commit_list * next = *list;
-	struct commit_list * work = NULL, **insert;
-	struct commit_list ** pptr = list;
-	struct sort_node * nodes;
-	struct sort_node * next_nodes;
-	int count = 0;
-
-	/* determine the size of the list */
-	while (next) {
-		next = next->next;
-		count++;
-	}
+	struct commit_list *next, *orig = *list;
+	struct commit_list *work, **insert;
+	struct commit_list **pptr;
 
-	if (!count)
+	if (!orig)
 		return;
-	/* allocate an array to help sort the list */
-	nodes = xcalloc(count, sizeof(*nodes));
-	/* link the list to the array */
-	next_nodes = nodes;
-	next=*list;
-	while (next) {
-		next_nodes->list_item = next;
-		setter(next->item, next_nodes);
-		next_nodes++;
-		next = next->next;
+	*list = NULL;
+
+	/* Mark them and clear the indegree */
+	for (next = orig; next; next = next->next) {
+		struct commit *commit = next->item;
+		commit->object.flags |= TOPOSORT;
+		commit->indegree = 0;
 	}
+
 	/* update the indegree */
-	next=*list;
-	while (next) {
+	for (next = orig; next; next = next->next) {
 		struct commit_list * parents = next->item->parents;
 		while (parents) {
-			struct commit * parent=parents->item;
-			struct sort_node * pn = (struct sort_node *) getter(parent);
+			struct commit *parent = parents->item;
 
-			if (pn)
-				pn->indegree++;
-			parents=parents->next;
+			if (parent->object.flags & TOPOSORT)
+				parent->indegree++;
+			parents = parents->next;
 		}
-		next=next->next;
 	}
+
 	/*
 	 * find the tips
 	 *
@@ -1219,55 +1172,56 @@ void sort_in_topological_order_fn(struct commit_list ** list, int lifo,
 	 *
 	 * the tips serve as a starting set for the work queue.
 	 */
-	next=*list;
+	work = NULL;
 	insert = &work;
-	while (next) {
-		struct sort_node * node = (struct sort_node *) getter(next->item);
+	for (next = orig; next; next = next->next) {
+		struct commit *commit = next->item;
 
-		if (node->indegree == 0) {
-			insert = &commit_list_insert(next->item, insert)->next;
-		}
-		next=next->next;
+		if (!commit->indegree)
+			insert = &commit_list_insert(commit, insert)->next;
 	}
 
 	/* process the list in topological order */
 	if (!lifo)
 		sort_by_date(&work);
+
+	pptr = list;
+	*list = NULL;
 	while (work) {
-		struct commit * work_item = pop_commit(&work);
-		struct sort_node * work_node = (struct sort_node *) getter(work_item);
-		struct commit_list * parents = work_item->parents;
+		struct commit *commit;
+		struct commit_list *parents, *work_item;
 
-		while (parents) {
-			struct commit * parent=parents->item;
-			struct sort_node * pn = (struct sort_node *) getter(parent);
-
-			if (pn) {
-				/*
-				 * parents are only enqueued for emission
-				 * when all their children have been emitted thereby
-				 * guaranteeing topological order.
-				 */
-				pn->indegree--;
-				if (!pn->indegree) {
-					if (!lifo)
-						insert_by_date(parent, &work);
-					else
-						commit_list_insert(parent, &work);
-				}
+		work_item = work;
+		work = work_item->next;
+		work_item->next = NULL;
+
+		commit = work_item->item;
+		for (parents = commit->parents; parents ; parents = parents->next) {
+			struct commit *parent=parents->item;
+
+			if (!(parent->object.flags & TOPOSORT))
+				continue;
+
+			/*
+			 * parents are only enqueued for emission
+			 * when all their children have been emitted thereby
+			 * guaranteeing topological order.
+			 */
+			if (!--parent->indegree) {
+				if (!lifo)
+					insert_by_date(parent, &work);
+				else
+					commit_list_insert(parent, &work);
 			}
-			parents=parents->next;
 		}
 		/*
 		 * work_item is a commit all of whose children
 		 * have already been emitted. we can emit it now.
 		 */
-		*pptr = work_node->list_item;
-		pptr = &(*pptr)->next;
-		*pptr = NULL;
-		setter(work_item, NULL);
+		commit->object.flags &= ~TOPOSORT;
+		*pptr = work_item;
+		pptr = &work_item->next;
 	}
-	free(nodes);
 }
 
 /* merge-base stuff */