< prev index next >

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

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

*** 33,43 **** 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; --- 33,42 ----
*** 74,93 **** */ 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()); Set<ResolvedModule> visited = new HashSet<>(); ! while (!deque.isEmpty()) { ! ResolvedModule rm = deque.pop(); ! if (!visited.contains(rm)) { ! visited.add(rm); builder.addNode(rm.name()); for (ResolvedModule dm : rm.reads()) { if (!visited.contains(dm)) { ! deque.push(dm); } builder.addEdge(rm.name(), dm.name()); } } } --- 73,91 ---- */ 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> todo = new ArrayDeque<>(configuration.modules()); Set<ResolvedModule> visited = new HashSet<>(); ! ResolvedModule rm; ! while ((rm = todo.poll()) != null) { ! if (visited.add(rm)) { builder.addNode(rm.name()); for (ResolvedModule dm : rm.reads()) { if (!visited.contains(dm)) { ! todo.push(dm); } builder.addEdge(rm.name(), dm.name()); } } }
*** 210,230 **** /** * Returns all nodes reachable from the given set of roots. */ public Set<T> dfs(Set<T> roots) { ! Deque<T> deque = new LinkedList<>(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); ! } } } return visited; } --- 208,225 ---- /** * Returns all nodes reachable from the given set of roots. */ public Set<T> dfs(Set<T> roots) { ! ArrayDeque<T> todo = new ArrayDeque<>(roots); Set<T> visited = new HashSet<>(); ! 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; }
*** 238,253 **** 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); edges.computeIfAbsent(node, _e -> new HashSet<>()); } public void addEdge(T u, T v) { addNode(u); addNode(v); edges.get(u).add(v); --- 233,246 ---- 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.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,310 **** /** * Topological sort */ private static class TopoSorter<T> { ! final Deque<T> result = new LinkedList<>(); ! final Deque<T> nodes; 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); } 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); ! } } } ! 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; } - visited.add(node); - graph.edges().get(node) - .forEach(x -> visit(x, visited, done)); - done.add(node); - result.addLast(node); } } } --- 254,298 ---- /** * Topological sort */ private static class TopoSorter<T> { ! final Deque<T> result = new ArrayDeque<>(); final Graph<T> graph; TopoSorter(Graph<T> graph) { this.graph = graph; sort(); } public void ordered(Consumer<T> action) { ! result.forEach(action); } public void reverse(Consumer<T> action) { result.descendingIterator().forEachRemaining(action); } private void sort() { ! 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, 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); } ! else if (stack.contains(node)) { ! throw new IllegalArgumentException( ! "Cycle detected: " + node + " -> " + children(node)); } } } }
< prev index next >