This introduces an in-place topological sort procedure to commit.c.

Given a list of commits, sort_in_topological_order() will perform an in-place
topological sort of that list.

The invariant that applies to the resulting list is:

       a reachable from b => ord(b) < ord(a)

This invariant is weaker than the --merge-order invariant, but is cheaper
to calculate (assuming the list has been identified) and will serve any
purpose where only a minimal topological order guarantee is required.
Signed-off-by: NJon Seymour <jon.seymour@gmail.com>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

Same argument order, same return type.  This allows us to use a function
pointer to choose one over the other.

Also move the common implementation of parsing the --pretty argument
format into commit.c rather than having duplicates in diff-tree.c and
rev-list.c.

Make 'sha1' parameters const where possible
Signed-off-by: NJason McMullan <jason.mcmullan@timesys.com>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

This patch linearises the GIT commit history graph into merge order
which is defined by invariants specified in Documentation/git-rev-list.txt.

The linearisation produced by this patch is superior in an objective sense
to that produced by the existing git-rev-list implementation in that
the linearisation produced is guaranteed to have the minimum number of
discontinuities, where a discontinuity is defined as an adjacent pair of
commits in the output list which are not related in a direct child-parent
relationship.

With this patch a graph like this:

	a4 ---
	| \   \
	|  b4 |
	|/ |  |
	a3 |  |
	|  |  |
	a2 |  |
	|  |  c3
	|  |  |
	|  |  c2
	|  b3 |
	|  | /|
	|  b2 |
	|  |  c1
	|  | /
	|  b1
	a1 |
	|  |
	a0 |
	| /
	root

Sorts like this:

	= a4
	| c3
	| c2
	| c1
	^ b4
	| b3
	| b2
	| b1
	^ a3
	| a2
	| a1
	| a0
	= root

Instead of this:

	= a4
	| c3
	^ b4
	| a3
	^ c2
	^ b3
	^ a2
	^ b2
	^ c1
	^ a1
	^ b1
	^ a0
	= root

A test script, t/t6000-rev-list.sh, includes a test which demonstrates
that the linearisation produced by --merge-order has less discontinuities
than the linearisation produced by git-rev-list without the --merge-order
flag specified. To see this, do the following:

	cd t
	./t6000-rev-list.sh
	cd trash
	cat actual-default-order
	cat actual-merge-order

The existing behaviour of git-rev-list is preserved, by default. To obtain
the modified behaviour, specify --merge-order or --merge-order --show-breaks
on the command line.

This version of the patch has been tested on the git repository and also on the linux-2.6
repository and has reasonable performance on both - ~50-100% slower than the original algorithm.

This version of the patch has incorporated a functional equivalent of the Linus' output limiting
algorithm into the merge-order algorithm itself. This operates per the notes associated
with Linus' commit 337cb3fb.

This version has incorporated Linus' feedback regarding proposed changes to rev-list.c.
(see: [PATCH] Factor out filtering in rev-list.c)

This version has improved the way sort_first_epoch marks commits as uninteresting.

For more details about this change, refer to Documentation/git-rev-list.txt
and http://blackcubes.dyndns.org/epoch/.
Signed-off-by: NJon Seymour <jon.seymour@gmail.com>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

You can ask to print out "raw" format (full headers, full body),
"medium" format (author and date, full body) or "short" format
(author only, condensed body).

Use "git-rev-list --pretty=short HEAD | less -S" for an example.

It's really just the header printign function from diff-tree.c,
and it's usable for other things too.

This is useful for when we want to insert the next one after
this new one, for example.

And teach fsck to free it to save memory.

object.

A fair number of the users potentially want to look at the
commit objects more closely, and if you worry about memory
leaking in certain applications, you can always do a

	free(commit->buffer);
	commit->buffer = NULL;

by hand after parsing them.

It's pretty much the same as "lookup_commit()", but it will take
tags too, and look up the commit (if any) associated with them.

It turns out that parse_object() is loading and decompressing given
object to free it just before calling the specific object parsing
function which does mmap and decompress the same object again. This
patch introduces the ability to parse specific objects directly from a
memory buffer.

Without this patch, running git-fsck-cache on the kernel repositorytake:

	real    0m13.006s
	user    0m11.421s
	sys     0m1.218s

With this patch applied:

	real    0m8.060s
	user    0m7.071s
	sys     0m0.710s

The performance increase is significant, and this is kind of a
prerequisite for sane delta object support with fsck.
Signed-off-by: NNicolas Pitre <nico@cam.org>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

Make pop_most_recent_commit() return the same objects multiple times, but only
if called with different bits to mark.

This is necessary to make merge-base work again.
Signed-Off-By: NDaniel Barkalow <barkalow@iabervon.org>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

This adds a function for inserting an item in a commit list, a function
for sorting a commit list by date, and a function for progressively
scanning a commit history from most recent to least recent.
Signed-Off-By: NDaniel Barkalow <barkalow@iabervon.org>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

This adds the structs and function declarations for parsing git objects.
Signed-Off-By: NDaniel Barkalow <barkalow@iabervon.org>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>