Linear implementation of Tarjan's algorithm
B. Blaser
bsrbnd at gmail.com
Sun Oct 22 17:36:12 UTC 2017
Hi,
As briefly mentioned in [1], the current implementation of Tarjan's
algorithm performs a linear scan of the stack while iterating on the
node dependencies which might be avoided...
Next is an attempt to make the whole implementation more linear using
a 'HashStack' that provides all operations in constant time,
especially 'contains()'.
What do you think?
Thanks,
Bernard
[1] http://mail.openjdk.java.net/pipermail/compiler-dev/2017-October/011226.html
diff --git a/src/jdk.compiler/share/classes/com/sun/tools/javac/util/GraphUtils.java
b/src/jdk.compiler/share/classes/com/sun/tools/javac/util/GraphUtils.java
--- a/src/jdk.compiler/share/classes/com/sun/tools/javac/util/GraphUtils.java
+++ b/src/jdk.compiler/share/classes/com/sun/tools/javac/util/GraphUtils.java
@@ -28,6 +28,7 @@
import java.util.ArrayList;
import java.util.Collection;
import java.util.Properties;
+import java.util.HashSet;
/** <p><b>This is NOT part of any supported API.
* If you write code that depends on this, you do so at your own risk.
@@ -164,7 +165,28 @@
ListBuffer<List<N>> sccs = new ListBuffer<>();
/** Stack of all reacheable nodes from given root. */
- ListBuffer<N> stack = new ListBuffer<>();
+ HashStack<N> stack = new HashStack<>();
+ //where
+ private static class HashStack<N> {
+ HashSet<N> set = new HashSet<>();
+ List<N> stack = List.nil();
+
+ private void push(N n) {
+ set.add(n);
+ stack = stack.prepend(n);
+ }
+
+ private N pop() {
+ N n = stack.head;
+ set.remove(n);
+ stack = stack.tail;
+ return n;
+ }
+
+ private boolean contains(N n) {
+ return set.contains(n);
+ }
+ }
private List<? extends List<? extends N>> findSCC(Iterable<?
extends N> nodes) {
for (N node : nodes) {
@@ -197,7 +219,7 @@
n.index = index;
n.lowlink = index;
index++;
- stack.prepend(n);
+ stack.push(n);
n.active = true;
}
@@ -205,7 +227,7 @@
N n;
ListBuffer<N> cycle = new ListBuffer<>();
do {
- n = stack.remove();
+ n = stack.pop();
n.active = false;
cycle.add(n);
} while (n != v);
More information about the compiler-dev
mailing list