1 /* 2 * Copyright (c) 2011, 2018, 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 25 package org.graalvm.compiler.graph; 26 27 import java.util.Arrays; 28 import java.util.Iterator; 29 import java.util.function.BiFunction; 30 31 import jdk.internal.vm.compiler.collections.EconomicMap; 32 import jdk.internal.vm.compiler.collections.MapCursor; 33 34 public class NodeMap<T> extends NodeIdAccessor implements EconomicMap<Node, T> { 35 36 private static final int MIN_REALLOC_SIZE = 16; 37 38 protected Object[] values; 39 40 public NodeMap(Graph graph) { 41 super(graph); 42 this.values = new Object[graph.nodeIdCount()]; 43 } 44 45 public NodeMap(NodeMap<T> copyFrom) { 46 super(copyFrom.graph); 47 this.values = Arrays.copyOf(copyFrom.values, copyFrom.values.length); 48 } 49 50 @Override 51 @SuppressWarnings("unchecked") 52 public T get(Node node) { 53 assert check(node); 54 return (T) values[getNodeId(node)]; 55 } 56 57 @SuppressWarnings("unchecked") 58 public T getAndGrow(Node node) { 59 checkAndGrow(node); 60 return (T) values[getNodeId(node)]; 61 } 62 63 private void checkAndGrow(Node node) { 64 if (isNew(node)) { 65 this.values = Arrays.copyOf(values, Math.max(MIN_REALLOC_SIZE, graph.nodeIdCount() * 3 / 2)); 66 } 67 assert check(node); 68 } 69 70 @Override 71 public boolean isEmpty() { 72 throw new UnsupportedOperationException("isEmpty() is not supported for performance reasons"); 73 } 74 75 @Override 76 public boolean containsKey(Node node) { 77 if (node.graph() == graph()) { 78 return get(node) != null; 79 } 80 return false; 81 } 82 83 public boolean containsValue(Object value) { 84 for (Object o : values) { 85 if (o == value) { 86 return true; 87 } 88 } 89 return false; 90 } 91 92 public Graph graph() { 93 return graph; 94 } 95 96 public void set(Node node, T value) { 97 assert check(node); 98 values[getNodeId(node)] = value; 99 } 100 101 public void setAndGrow(Node node, T value) { 102 checkAndGrow(node); 103 set(node, value); 104 } 105 106 /** 107 * @param i 108 * @return Return the key for the entry at index {@code i} 109 */ 110 protected Node getKey(int i) { 111 return graph.getNode(i); 112 } 113 114 @Override 115 public int size() { 116 throw new UnsupportedOperationException("size() is not supported for performance reasons"); 117 } 118 119 public int capacity() { 120 return values.length; 121 } 122 123 public boolean isNew(Node node) { 124 return getNodeId(node) >= capacity(); 125 } 126 127 private boolean check(Node node) { 128 assert node.graph() == graph : String.format("%s is not part of the graph", node); 129 assert !isNew(node) : "this node was added to the graph after creating the node map : " + node; 130 assert node.isAlive() : "this node is not alive: " + node; 131 return true; 132 } 133 134 @Override 135 public void clear() { 136 Arrays.fill(values, null); 137 } 138 139 @Override 140 public Iterable<Node> getKeys() { 141 return new Iterable<Node>() { 142 143 @Override 144 public Iterator<Node> iterator() { 145 return new Iterator<Node>() { 146 147 int i = 0; 148 149 @Override 150 public boolean hasNext() { 151 forward(); 152 return i < NodeMap.this.values.length; 153 } 154 155 @Override 156 public Node next() { 157 final int pos = i; 158 final Node key = NodeMap.this.getKey(pos); 159 i++; 160 forward(); 161 return key; 162 } 163 164 @Override 165 public void remove() { 166 throw new UnsupportedOperationException(); 167 } 168 169 private void forward() { 170 while (i < NodeMap.this.values.length && (NodeMap.this.getKey(i) == null || NodeMap.this.values[i] == null)) { 171 i++; 172 } 173 } 174 }; 175 } 176 }; 177 } 178 179 @Override 180 public MapCursor<Node, T> getEntries() { 181 return new MapCursor<Node, T>() { 182 183 int current = -1; 184 185 @Override 186 public boolean advance() { 187 current++; 188 while (current < NodeMap.this.values.length && (NodeMap.this.values[current] == null || NodeMap.this.getKey(current) == null)) { 189 current++; 190 } 191 return current < NodeMap.this.values.length; 192 } 193 194 @Override 195 public Node getKey() { 196 return NodeMap.this.getKey(current); 197 } 198 199 @SuppressWarnings("unchecked") 200 @Override 201 public T getValue() { 202 return (T) NodeMap.this.values[current]; 203 } 204 205 @Override 206 public void remove() { 207 assert NodeMap.this.values[current] != null; 208 NodeMap.this.values[current] = null; 209 } 210 }; 211 } 212 213 @Override 214 public Iterable<T> getValues() { 215 return new Iterable<T>() { 216 217 @Override 218 public Iterator<T> iterator() { 219 return new Iterator<T>() { 220 221 int i = 0; 222 223 @Override 224 public boolean hasNext() { 225 forward(); 226 return i < NodeMap.this.values.length; 227 } 228 229 @SuppressWarnings("unchecked") 230 @Override 231 public T next() { 232 final int pos = i; 233 final T value = (T) NodeMap.this.values[pos]; 234 i++; 235 forward(); 236 return value; 237 } 238 239 @Override 240 public void remove() { 241 throw new UnsupportedOperationException(); 242 } 243 244 private void forward() { 245 while (i < NodeMap.this.values.length && (NodeMap.this.getKey(i) == null || NodeMap.this.values[i] == null)) { 246 i++; 247 } 248 } 249 }; 250 } 251 }; 252 } 253 254 @Override 255 public String toString() { 256 MapCursor<Node, T> i = getEntries(); 257 if (!i.advance()) { 258 return "{}"; 259 } 260 261 StringBuilder sb = new StringBuilder(); 262 sb.append('{'); 263 while (true) { 264 Node key = i.getKey(); 265 T value = i.getValue(); 266 sb.append(key); 267 sb.append('='); 268 sb.append(value); 269 if (!i.advance()) { 270 return sb.append('}').toString(); 271 } 272 sb.append(',').append(' '); 273 } 274 } 275 276 @Override 277 public T put(Node key, T value) { 278 T result = get(key); 279 set(key, value); 280 return result; 281 } 282 283 @Override 284 public T removeKey(Node key) { 285 return put(key, null); 286 } 287 288 @Override 289 public void replaceAll(BiFunction<? super Node, ? super T, ? extends T> function) { 290 for (Node n : getKeys()) { 291 put(n, function.apply(n, get(n))); 292 } 293 } 294 }