Re: [PATCH] toposort: rename "lifo" field

From: Junio C Hamano <gitster@pobox.com>
Date: Jun 7, 2013, 01:25 UTC
Message-ID: <7vfvwuww39.fsf@alter.siamese.dyndns.org>
In-Reply-To: <7vppvyx1mv.fsf_-_@alter.siamese.dyndns.org>

Junio C Hamano <gitster@pobox.com> writes:

> When sorting commits topologically, the primary invariant is to emit
> all children before its parent is emitted.  When traversing a forked

s/its/their/;

Show 5 quoted lines

>> As I needed to have an excuse to push jk/commit-info-slab topic
>> further (I have an unpublished show-branch rewrite on top of it),
>> I may take a look at doing this myself if/when I find some time.
>
>   So this is the first step, applies on top of jk/commit-info-slab.

The next step will be to replace the use of commit_list in this function with a priority queue, whose API may look like what is at the end of this message.

Then write a compare function that looks at commit->date field to compare committer timestamp, and set it to commit_queue->compare when REV_SORT_BY_COMMIT_DATE is asked for. When doing the graph traversal order, set compare function to NULL when initializing the commit_queue and use it as a LIFO stack.

And the step after that will be to add an author-date field to the commit-info-slab we currently use to keep track of indegree, grab author timestamp from commits as we encounter them, and write another comparison function to use that information (using the cb_data field of commit_queue to point at the info slab) to implement REV_SORT_BY_AUTHOR_DATE. That step can also implement the command line option parsing for the new --author-date-order option (or alternatively, --date-order={author,committer}).

#ifndef COMMIT_QUEUE_H #define COMMIT_QUEUE_H

/*
 * Compare two commits; the third parameter is cb_data in the
 * commit_queue structure.
 */
typedef int (*commit_compare_fn)(struct commit *, struct commit *, void *);

struct commit_queue {
	commit_compare_fn compare;
	void *cb_data;
	int alloc, nr;
	struct commit **array;
};

/*
 * Add the commit to the queue
 */
struct commit *commit_queue_put(struct commit_queue *, struct commit *);

/*
 * Extract the commit that compares the smallest out of the queue,
 * or NULL.  If compare function is NULL, the queue acts as a LIFO
 * stack.
 */
struct commit *commit_queue_get(struct commit_queue *);

#endif /* COMMIT_QUEUE_H */