< prev index next >

src/java.base/share/classes/jdk/internal/module/ModuleHashesBuilder.java

Print this page
8200134: Improve ModuleHashesBuilder
Reviewed-by: mchung, alanb

@@ -33,11 +33,10 @@
 import java.util.ArrayDeque;
 import java.util.Collections;
 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;
 import java.util.function.Function;
 import java.util.stream.Stream;

@@ -74,20 +73,19 @@
      */
     public Map<String, ModuleHashes> computeHashes(Set<String> roots) {
         // 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());
                 }
             }
         }

@@ -210,21 +208,18 @@
 
         /**
          * 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)) {
+            T u;
+            while ((u = todo.poll()) != null) {
+                if (visited.add(u) && contains(u)) {
                         adjacentNodes(u).stream()
                             .filter(v -> !visited.contains(v))
-                            .forEach(deque::push);
-                    }
+                        .forEach(todo::push);
                 }
             }
             return visited;
         }
 

@@ -238,16 +233,14 @@
         static class Builder<T> {
             final Set<T> nodes = new HashSet<>();
             final Map<T, Set<T>> edges = new HashMap<>();
 
             public void addNode(T node) {
-                if (nodes.contains(node)) {
-                    return;
-                }
-                nodes.add(node);
+                if (nodes.add(node)) {
                 edges.computeIfAbsent(node, _e -> new HashSet<>());
             }
+            }
 
             public void addEdge(T u, T v) {
                 addNode(u);
                 addNode(v);
                 edges.get(u).add(v);

@@ -261,50 +254,45 @@
 
     /**
      * 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) {
             result.descendingIterator().forEachRemaining(action);
         }
 
         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 Set<T> children(T node) {
+            return graph.edges().get(node);
         }
 
-        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));
+        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);
                 }
-                return;
+            else if (stack.contains(node)) {
+                throw new IllegalArgumentException(
+                    "Cycle detected: " + node + " -> " + children(node));
             }
-            visited.add(node);
-            graph.edges().get(node)
-                .forEach(x -> visit(x, visited, done));
-            done.add(node);
-            result.addLast(node);
         }
     }
 }
< prev index next >