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

[Junio C Hamano <gitster@pobox.com>]

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/;

>> 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 */