Linear implementation of Tarjan's algorithm

[Remi Forax]

Please do not add a new class just for that, for a code as simple as this one, you can inline every methods.
Also, i think the compiler will create 8 methods for your class HashStack, you should declare the class and all the method package private (or wait for the compiler using the 18.3 as bootstrap JDK).

regards,
Rémi

----- Mail original -----
> De: "B. Blaser" <bsrbnd at gmail.com>
> À: "compiler-dev" <compiler-dev at openjdk.java.net>
> Envoyé: Dimanche 22 Octobre 2017 19:36:12
> Objet: Linear implementation of Tarjan's algorithm

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