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 ;-)?
On 6/30/05, Junio C Hamano [off-list ref] wrote:
quoted hunk
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()?
Oops, yes I do.
+ 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?
Yes, that is the current assumption. Alternatively, I could save the current
version of object.util in the temporary structure and restore it when done.
Perhaps I'll do that.
So sort_node->indegree means how many children of it are on the
*list. Am I reading you correctly so far?
Correct.
+ 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)?
True. Should reword the comment to find the tips.
+ /* 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.
Correct.
+ }
+ 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).
Yep.
+ *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 ;-)?
Yep, but can you fix the PATCH 1/1 thing first :-)
I'll rework the patch, incorporating answers to your questions into the comment.
Regards,
jon.