summaryrefslogtreecommitdiff
path: root/epoch.c
AgeCommit message (Collapse)AuthorFilesLines
2005-07-06[PATCH] Tidy up - remove use of (*f)() idiom from epoch.cLibravatar Jon Seymour1-3/+3
Replace (*f)() with f() where the former idiom was used in epoch.c Signed-off-by: Jon Seymour <jon.seymour@gmail.com> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2005-07-06[PATCH] Fixes a problem with --merge-order A B (A is linear descendent of a ↵Libravatar Jon Seymour1-1/+1
merge B) This patch passes the test case introduced by the previous patch. Signed-off-by: Jon Seymour <jon.seymour@gmail.com> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2005-07-06Remove insane overlapping bit ranges from epoch.cLibravatar Linus Torvalds1-8/+2
..and move the DUPCHECK to rev-list.c since both the merge-order and the upcoming topo-sort get confused by dups.
2005-07-06Make "insert_by_date()" match "commit_list_insert()"Libravatar Linus Torvalds1-2/+2
Same argument order, same return type. This allows us to use a function pointer to choose one over the other.
2005-07-03Fix sparse warnings.Libravatar Linus Torvalds1-4/+4
Mainly making a lot of local functions and variables be marked "static", but there was a "zero as NULL" warning in there too.
2005-06-29[PATCH] Fix for git-rev-list --merge-order B ^A (A,B share common base) [rev 2]Libravatar Jon Seymour1-5/+3
This patch makes --merge-order produce the same list as git-rev-list without --merge-order specified. In particular, if the graph looks like this: A | B |/ C | D The both git-rev-list B ^A and git-rev-list --merge-order will produce B. The unit tests have been changed to reflect the fact that the prune points are now formally part of the start list that is used to perform the --merge-order sort. That is: git-rev-list --merge-order A ^D used to produce = A | C It now produces: ^ A | C Signed-off-by: Jon Seymour <jon.seymour@gmail.com> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2005-06-29Remove bogus dup commit warning with --merge-orderLibravatar Linus Torvalds1-4/+1
It makes gitk unhappy, and besides, non-merge-order doesn't complain, so why do it here..
2005-06-22[PATCH] Fix to how --merge-order handles multiple rootsLibravatar Jon Seymour1-4/+7
This patch addresses the problem reported by Paul Mackerras such that --merge-order did not report the last root of a graph with merge of two independent roots. Signed-off-by: Jon Seymour <jon.seymour@gmail.com> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2005-06-22[PATCH] Fix --merge-order unit test breaks introduced by ↵Libravatar Jon Seymour1-12/+3
6c88be169881c9223532796bd225e79afaa115e1 The sensible cleanup of the in-memory storage order of commit parents broke the --merge-order code which was dependent on the previous behaviour of parse_commit(). This patch restores the correctness --merge-order behaviour by taking account of the new behaviour of parse_commit. Signed-off-by: Jon Seymour <jon.seymour@gmail.com> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2005-06-19[PATCH] Prevent git-rev-list --merge-order producing duplicates in the outputLibravatar Jon Seymour1-14/+21
If a is reachable from b, then git-rev-list --merge-order b a would produce a duplicate output of b. This causes a problem for an upcoming version of gitk since it breaks the --merge-order ordering invariant. This patch fixes the problem for the --merge-order switch. A subsequent patch will fix the problem for the non --merge-order switch. Signed-off-by: Jon Seymour <jon.seymour@gmail.com> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2005-06-19[PATCH] Relaxes error checking in epoch.c to allow duplicate parentsLibravatar Jon Seymour1-10/+6
Given that real trees in the wild include parents with duplicate parents, I have relaxed over-zealous error checking in epoch.c and dealt with the problem a different way - duplicate parents are now silently ignored. Signed-off-by: Jon Seymour <jon.seymour@gmail.com> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2005-06-19[PATCH] Fixes problem with --merge-order head ^headLibravatar Jon Seymour1-1/+3
git-rev-list --merge-order HEAD ^HEAD was faulting rather than generating an empty output. This patch fixes that problem. Signed-off-by: Jon Seymour <jon.seymour@gmail.com> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2005-06-19[PATCH] Tweaked --merge-order --show-breaks output in case specified head ↵Libravatar Jon Seymour1-0/+2
has no parent git-rev-list --merge-order --show-breaks root Was outputing: | root It now outputs: = root Which is consistent with the behaviour of other cases. Signed-off-by: Jon Seymour <jon.seymour@gmail.com> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2005-06-08[PATCH] Tidy up some rev-list-related stuffLibravatar Petr Baudis1-236/+193
This patch tidies up the git-rev-list documentation and epoch.c, which are in severe clash with the unwritten coding style now, and quite unreadable. It also fixes up compile failures with older compilers due to variable declarations after code. The patch mostly wraps lines before or on the 80th column, removes plenty of superfluous empty lines and changes comments from // to /* */. Signed-off-by: Petr Baudis <pasky@ucw.cz> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2005-06-08[PATCH] three --merge-order bug fixesLibravatar Jon Seymour1-3/+2
This patch fixes three bugs in --merge-order support * mark_ancestors_uninteresting was unnecessarily exponential which caused a problem when a commit with no parents was merged near the head of something like the linux kernel * removed a spurious statement from find_base which wasn't apparently causing problems now, but wasn't correct either. * removed an unnecessarily strict check from find_base_for_list that causes a problem if git-rev-list commit ^parent-of-commit is specified. * added some unit tests which were accidentally omitted from original merge-order patch The fix to mark_ancestors_uninteresting isn't an optimal fix - a full graph scan will still be performed in this case even though it is not strictly required. However, a full graph scan is linear and still no worse than git-rev-list HEAD which runs in less than 2 seconds on a warm cache. Signed-off-by: Jon Seymour <jon.seymour@gmail.com> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2005-06-06[PATCH] Modify git-rev-list to linearise the commit history in merge order.Libravatar jon@blackcubes.dyndns.org1-0/+693
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 337cb3fb8da45f10fe9a0c3cf571600f55ead2ce. 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: Jon Seymour <jon.seymour@gmail.com> Signed-off-by: Linus Torvalds <torvalds@osdl.org>