]> source.dussan.org Git - jgit.git/commit
BitmappedReachabilityChecker: Reachability check using bitmaps 58/140958/10
authorIvan Frade <ifrade@google.com>
Mon, 22 Apr 2019 22:38:45 +0000 (15:38 -0700)
committerIvan Frade <ifrade@google.com>
Wed, 15 May 2019 23:36:20 +0000 (16:36 -0700)
commit601b0ae577014e18929961f03a1940bc192d4ef4
tree49369edb61b1a3caeed938285e769566315328af
parentb6da4b34cccc39a253d34e159a13cc2fd79a46bf
BitmappedReachabilityChecker: Reachability check using bitmaps

The "basic" reachability check walks the graph starting from the tips
marking things as "uninteresting". If the target commit is marked as
"uninteresting" it was reached; it is reachable from those tips.

This requires a lot of walking and can be solved directly with bitmaps.
Most of the time the bitmaps are already calculated or a short walk
away.

This should improve the performance of reachability checks, for example
in Gitiles.

Change-Id: I83d33271f58d95d2dc9ed151967b3eda513c99f7
Signed-off-by: Ivan Frade <ifrade@google.com>
org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/BitmappedReachabilityCheckerTest.java [new file with mode: 0644]
org.eclipse.jgit/src/org/eclipse/jgit/revwalk/BitmappedReachabilityChecker.java [new file with mode: 0644]