1 /* 2 * Copyright (c) 2008, 2015, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. 8 * 9 * This code is distributed in the hope that it will be useful, but WITHOUT 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12 * version 2 for more details (a copy is included in the LICENSE file that 13 * accompanied this code). 14 * 15 * You should have received a copy of the GNU General Public License version 16 * 2 along with this work; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 * 23 */ 24 package com.sun.hotspot.igv.data; 25 26 import java.util.*; 27 28 /** 29 * 30 * @author Thomas Wuerthinger 31 */ 32 public class InputGraph extends Properties.Entity implements FolderElement { 33 34 private Map<Integer, InputNode> nodes; 35 private List<InputEdge> edges; 36 private Folder parent; 37 private Group parentGroup; 38 private Map<String, InputBlock> blocks; 39 private List<InputBlockEdge> blockEdges; 40 private Map<Integer, InputBlock> nodeToBlock; 41 InputGraph(String name)42 public InputGraph(String name) { 43 setName(name); 44 nodes = new LinkedHashMap<>(); 45 edges = new ArrayList<>(); 46 blocks = new LinkedHashMap<>(); 47 blockEdges = new ArrayList<>(); 48 nodeToBlock = new LinkedHashMap<>(); 49 } 50 51 @Override setParent(Folder parent)52 public void setParent(Folder parent) { 53 this.parent = parent; 54 if (parent instanceof Group) { 55 assert this.parentGroup == null; 56 this.parentGroup = (Group) parent; 57 } 58 } 59 addBlockEdge(InputBlock left, InputBlock right)60 public InputBlockEdge addBlockEdge(InputBlock left, InputBlock right) { 61 InputBlockEdge edge = new InputBlockEdge(left, right); 62 blockEdges.add(edge); 63 left.addSuccessor(right); 64 return edge; 65 } 66 findRootNodes()67 public List<InputNode> findRootNodes() { 68 List<InputNode> result = new ArrayList<>(); 69 Set<Integer> nonRoot = new HashSet<>(); 70 for(InputEdge curEdges : getEdges()) { 71 nonRoot.add(curEdges.getTo()); 72 } 73 74 for(InputNode node : getNodes()) { 75 if(!nonRoot.contains(node.getId())) { 76 result.add(node); 77 } 78 } 79 80 return result; 81 } 82 findAllOutgoingEdges()83 public Map<InputNode, List<InputEdge>> findAllOutgoingEdges() { 84 Map<InputNode, List<InputEdge>> result = new HashMap<>(getNodes().size()); 85 for(InputNode n : this.getNodes()) { 86 result.put(n, new ArrayList<InputEdge>()); 87 } 88 89 for(InputEdge e : this.edges) { 90 int from = e.getFrom(); 91 InputNode fromNode = this.getNode(from); 92 List<InputEdge> fromList = result.get(fromNode); 93 assert fromList != null; 94 fromList.add(e); 95 } 96 97 for(InputNode n : this.getNodes()) { 98 List<InputEdge> list = result.get(n); 99 Collections.sort(list, InputEdge.OUTGOING_COMPARATOR); 100 } 101 102 return result; 103 } 104 findAllIngoingEdges()105 public Map<InputNode, List<InputEdge>> findAllIngoingEdges() { 106 Map<InputNode, List<InputEdge>> result = new HashMap<>(getNodes().size()); 107 for(InputNode n : this.getNodes()) { 108 result.put(n, new ArrayList<InputEdge>()); 109 } 110 111 for(InputEdge e : this.edges) { 112 int to = e.getTo(); 113 InputNode toNode = this.getNode(to); 114 List<InputEdge> toList = result.get(toNode); 115 assert toList != null; 116 toList.add(e); 117 } 118 119 for(InputNode n : this.getNodes()) { 120 List<InputEdge> list = result.get(n); 121 Collections.sort(list, InputEdge.INGOING_COMPARATOR); 122 } 123 124 return result; 125 } 126 findOutgoingEdges(InputNode n)127 public List<InputEdge> findOutgoingEdges(InputNode n) { 128 List<InputEdge> result = new ArrayList<>(); 129 130 for(InputEdge e : this.edges) { 131 if(e.getFrom() == n.getId()) { 132 result.add(e); 133 } 134 } 135 136 Collections.sort(result, InputEdge.OUTGOING_COMPARATOR); 137 138 return result; 139 } 140 clearBlocks()141 public void clearBlocks() { 142 blocks.clear(); 143 nodeToBlock.clear(); 144 } 145 setEdge(int fromIndex, int toIndex, int from, int to)146 public void setEdge(int fromIndex, int toIndex, int from, int to) { 147 assert fromIndex == ((char)fromIndex) : "Downcast must be safe"; 148 assert toIndex == ((char)toIndex) : "Downcast must be safe"; 149 150 InputEdge edge = new InputEdge((char)fromIndex, (char)toIndex, from, to); 151 if(!this.getEdges().contains(edge)) { 152 this.addEdge(edge); 153 } 154 } 155 ensureNodesInBlocks()156 public void ensureNodesInBlocks() { 157 InputBlock noBlock = null; 158 Set<InputNode> scheduledNodes = new HashSet<>(); 159 160 for (InputBlock b : getBlocks()) { 161 for (InputNode n : b.getNodes()) { 162 assert !scheduledNodes.contains(n); 163 scheduledNodes.add(n); 164 } 165 } 166 167 for (InputNode n : this.getNodes()) { 168 assert nodes.get(n.getId()) == n; 169 if (!scheduledNodes.contains(n)) { 170 if (noBlock == null) { 171 noBlock = this.addBlock("(no block)"); 172 } 173 noBlock.addNode(n.getId()); 174 } 175 assert this.getBlock(n) != null; 176 } 177 } 178 setBlock(InputNode node, InputBlock block)179 public void setBlock(InputNode node, InputBlock block) { 180 nodeToBlock.put(node.getId(), block); 181 } 182 getBlock(int nodeId)183 public InputBlock getBlock(int nodeId) { 184 return nodeToBlock.get(nodeId); 185 } 186 getBlock(InputNode node)187 public InputBlock getBlock(InputNode node) { 188 assert nodes.containsKey(node.getId()); 189 assert nodes.get(node.getId()).equals(node); 190 return getBlock(node.getId()); 191 } 192 getNext()193 public InputGraph getNext() { 194 return parentGroup.getNext(this); 195 } 196 getPrev()197 public InputGraph getPrev() { 198 return parentGroup.getPrev(this); 199 } 200 setName(String name)201 private void setName(String name) { 202 this.getProperties().setProperty("name", name); 203 } 204 205 @Override getName()206 public String getName() { 207 return getProperties().get("name"); 208 } 209 getNodes()210 public Collection<InputNode> getNodes() { 211 return Collections.unmodifiableCollection(nodes.values()); 212 } 213 getNodesAsSet()214 public Set<Integer> getNodesAsSet() { 215 return Collections.unmodifiableSet(nodes.keySet()); 216 } 217 getBlocks()218 public Collection<InputBlock> getBlocks() { 219 return Collections.unmodifiableCollection(blocks.values()); 220 } 221 addNode(InputNode node)222 public void addNode(InputNode node) { 223 nodes.put(node.getId(), node); 224 } 225 getNode(int id)226 public InputNode getNode(int id) { 227 return nodes.get(id); 228 } 229 removeNode(int index)230 public InputNode removeNode(int index) { 231 return nodes.remove(index); 232 } 233 getEdges()234 public Collection<InputEdge> getEdges() { 235 return Collections.unmodifiableList(edges); 236 } 237 removeEdge(InputEdge c)238 public void removeEdge(InputEdge c) { 239 boolean removed = edges.remove(c); 240 assert removed; 241 } 242 addEdge(InputEdge c)243 public void addEdge(InputEdge c) { 244 edges.add(c); 245 } 246 getGroup()247 public Group getGroup() { 248 return parentGroup; 249 } 250 251 @Override toString()252 public String toString() { 253 StringBuilder sb = new StringBuilder(); 254 sb.append("Graph ").append(getName()).append(" ").append(getProperties().toString()).append("\n"); 255 for (InputNode n : nodes.values()) { 256 sb.append(n.toString()); 257 sb.append("\n"); 258 } 259 260 for (InputEdge c : edges) { 261 sb.append(c.toString()); 262 sb.append("\n"); 263 } 264 265 for (InputBlock b : getBlocks()) { 266 sb.append(b.toString()); 267 sb.append("\n"); 268 } 269 270 return sb.toString(); 271 } 272 addBlock(String name)273 public InputBlock addBlock(String name) { 274 final InputBlock b = new InputBlock(this, name); 275 blocks.put(b.getName(), b); 276 return b; 277 } 278 getBlock(String s)279 public InputBlock getBlock(String s) { 280 return blocks.get(s); 281 } 282 getBlockEdges()283 public Collection<InputBlockEdge> getBlockEdges() { 284 return Collections.unmodifiableList(blockEdges); 285 } 286 287 @Override getParent()288 public Folder getParent() { 289 return parent; 290 } 291 } 292