changeset 49539:745ce8f5efc8

8200134: Improve ModuleHashesBuilder Reviewed-by: mchung, alanb
author martin
date Thu, 05 Apr 2018 09:38:30 -0700
parents e8ada9b2dd89
children 0eaddc72d8f4 6d59b3bb3f5f
files src/java.base/share/classes/jdk/internal/module/ModuleHashesBuilder.java
diffstat 1 files changed, 33 insertions(+), 45 deletions(-) [+]
line wrap: on
line diff
--- a/src/java.base/share/classes/jdk/internal/module/ModuleHashesBuilder.java	Thu Apr 05 09:37:19 2018 -0700
+++ b/src/java.base/share/classes/jdk/internal/module/ModuleHashesBuilder.java	Thu Apr 05 09:38:30 2018 -0700
@@ -35,7 +35,6 @@
 import java.util.Deque;
 import java.util.HashMap;
 import java.util.HashSet;
-import java.util.LinkedList;
 import java.util.Map;
 import java.util.Set;
 import java.util.function.Consumer;
@@ -76,16 +75,15 @@
         // build a graph containing the packaged modules and
         // its transitive dependences matching --hash-modules
         Graph.Builder<String> builder = new Graph.Builder<>();
-        Deque<ResolvedModule> deque = new ArrayDeque<>(configuration.modules());
+        Deque<ResolvedModule> todo = new ArrayDeque<>(configuration.modules());
         Set<ResolvedModule> visited = new HashSet<>();
-        while (!deque.isEmpty()) {
-            ResolvedModule rm = deque.pop();
-            if (!visited.contains(rm)) {
-                visited.add(rm);
+        ResolvedModule rm;
+        while ((rm = todo.poll()) != null) {
+            if (visited.add(rm)) {
                 builder.addNode(rm.name());
                 for (ResolvedModule dm : rm.reads()) {
                     if (!visited.contains(dm)) {
-                        deque.push(dm);
+                        todo.push(dm);
                     }
                     builder.addEdge(rm.name(), dm.name());
                 }
@@ -212,17 +210,14 @@
          * Returns all nodes reachable from the given set of roots.
          */
         public Set<T> dfs(Set<T> roots) {
-            Deque<T> deque = new LinkedList<>(roots);
+            ArrayDeque<T> todo = new ArrayDeque<>(roots);
             Set<T> visited = new HashSet<>();
-            while (!deque.isEmpty()) {
-                T u = deque.pop();
-                if (!visited.contains(u)) {
-                    visited.add(u);
-                    if (contains(u)) {
-                        adjacentNodes(u).stream()
-                            .filter(v -> !visited.contains(v))
-                            .forEach(deque::push);
-                    }
+            T u;
+            while ((u = todo.poll()) != null) {
+                if (visited.add(u) && contains(u)) {
+                    adjacentNodes(u).stream()
+                        .filter(v -> !visited.contains(v))
+                        .forEach(todo::push);
                 }
             }
             return visited;
@@ -240,11 +235,9 @@
             final Map<T, Set<T>> edges = new HashMap<>();
 
             public void addNode(T node) {
-                if (nodes.contains(node)) {
-                    return;
+                if (nodes.add(node)) {
+                    edges.computeIfAbsent(node, _e -> new HashSet<>());
                 }
-                nodes.add(node);
-                edges.computeIfAbsent(node, _e -> new HashSet<>());
             }
 
             public void addEdge(T u, T v) {
@@ -263,18 +256,16 @@
      * Topological sort
      */
     private static class TopoSorter<T> {
-        final Deque<T> result = new LinkedList<>();
-        final Deque<T> nodes;
+        final Deque<T> result = new ArrayDeque<>();
         final Graph<T> graph;
 
         TopoSorter(Graph<T> graph) {
             this.graph = graph;
-            this.nodes = new LinkedList<>(graph.nodes);
             sort();
         }
 
         public void ordered(Consumer<T> action) {
-            result.iterator().forEachRemaining(action);
+            result.forEach(action);
         }
 
         public void reverse(Consumer<T> action) {
@@ -282,29 +273,26 @@
         }
 
         private void sort() {
-            Deque<T> visited = new LinkedList<>();
-            Deque<T> done = new LinkedList<>();
-            T node;
-            while ((node = nodes.poll()) != null) {
-                if (!visited.contains(node)) {
-                    visit(node, visited, done);
-                }
-            }
+            Set<T> visited = new HashSet<>();
+            Deque<T> stack = new ArrayDeque<>();
+            graph.nodes.forEach(node -> visit(node, visited, stack));
         }
 
-        private void visit(T node, Deque<T> visited, Deque<T> done) {
-            if (visited.contains(node)) {
-                if (!done.contains(node)) {
-                    throw new IllegalArgumentException("Cyclic detected: " +
-                        node + " " + graph.edges().get(node));
-                }
-                return;
+        private Set<T> children(T node) {
+            return graph.edges().get(node);
+        }
+
+        private void visit(T node, Set<T> visited, Deque<T> stack) {
+            if (visited.add(node)) {
+                stack.push(node);
+                children(node).forEach(child -> visit(child, visited, stack));
+                stack.pop();
+                result.addLast(node);
             }
-            visited.add(node);
-            graph.edges().get(node)
-                .forEach(x -> visit(x, visited, done));
-            done.add(node);
-            result.addLast(node);
+            else if (stack.contains(node)) {
+                throw new IllegalArgumentException(
+                    "Cycle detected: " + node + " -> " + children(node));
+            }
         }
     }
 }