Linear implementation of Tarjan's algorithm

[B. Blaser]

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