Re: [PATCH 1/1] Add a topological sort procedure to commit.c

Interesting idea.  Help me understand the code.

@@ -346,3 +352,79 @@ int count_parents(struct commit * commit
         return count;
 }
 
+/*
+ * Performs an in-place topological sort on the list supplied
+ */
+void sort_in_topological_order(struct commit_list ** list)
+{
+	...
+	/* allocate an array to help sort the list */
+	nodes = xmalloc(sizeof(*nodes) * count);
+	/* link the list to the array */
+	next_nodes = nodes;
+	next=*list;
+	while (next) {
+		next_nodes->list_item = next;
+		next->item->object.util = next_nodes;
+		next_nodes++;
+		next = next->next;
+	}
+	/* update the indegree */

Don't you want to initialize before update?  Either in the above
while(next) loop or just after xmalloc() with a single
memset(0), or xcalloc()?

+	next=*list;
+	while (next) {
+		struct commit_list * parents = next->item->parents;
+		while (parents) {
+			struct commit * parent=parents->item;
+			struct sort_node * pn = (struct sort_node *)parent->object.util;
+			
+			if (pn)
+				pn->indegree++;

I take this to mean that not all commits are on *list and such
commits not on *list have object.util set to NULL.  Who
initializes object.util (this is not a nitpick but a question as
a user)?   commit.c::lookup_commit() uses memset(0) and when
sort_in_topological_order() function is called everybody (not
limited to the ones on *list but all commits reachable from
them) are supposed to have object.util set to NULL?

So sort_node->indegree means how many children of it are on the
*list.  Am I reading you correctly so far?

+			parents=parents->next;
+		}
+		next=next->next;
+	}
+	/* find the roots */
+	next=*list;
+	while (next) {
+		struct sort_node * node = (struct sort_node *)next->item->object.util;
+
+		if (node->indegree == 0) {
+			commit_list_insert(next->item, &work);
+		}
+		next=next->next;
+	}

You say "find the roots", but this sounds more like finding the
tips of forests.  You are finding people without children,
right (again, not a nitpick but trying to understand the code)?

+	/* process the list in topological order */
+	while (work) {
+		struct commit * work_item = pop_commit(&work);
+		struct sort_node * work_node = (struct sort_node *)work_item->object.util;
+		struct commit_list * parents = work_item->parents;
+
+		while (parents) {
+			struct commit * parent=parents->item;
+			struct sort_node * pn = (struct sort_node *)parent->object.util;
+			
+			if (pn) {
+				pn->indegree--;
+				if (!pn->indegree) 
+					commit_list_insert(parent, &work);

And when you look at each parent, and push the parent into work
queue when you have seen all its children.

+			}
+			parents=parents->next;
+		}

And at this point work_item, popped from your work queue, is
guaranteed to be a commit all of whose children have been
processed (i.e. pushed into the original *list).

+		*pptr = work_node->list_item;
+		work_node->list_item->next = NULL;
+		pptr = &(*pptr)->next;
+		work_item->object.util = NULL;

+	}
+	free(nodes);
+}

By the way, you seem to be using "git format-patch".  Do you
want to help me pushing it upstream ;-)?


-
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html