Re: [PATCH 1/1] Add a topological sort procedure to commit.c
From: Jon Seymour <hidden>
Date: 2016-06-15 22:42:01
On 6/30/05, Junio C Hamano [off-list ref] wrote:
quoted hunk ↗ jump to 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.