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

[Jon Seymour <jon.seymour@gmail.com>]

On 6/30/05, Junio C Hamano <junkio@cox.net> wrote:
> 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.