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 return true; 131 } 132 133 @Override 134 public void clear() { 135 Arrays.fill(values, null); 136 } 137 138 @Override 139 public Iterable<Node> getKeys() { 140 return new Iterable<Node>() { 141 142 @Override 143 public Iterator<Node> iterator() { 144 return new Iterator<Node>() { 145 146 int i = 0; 147 148 @Override 149 public boolean hasNext() { 150 forward(); 151 return i < NodeMap.this.values.length; 152 } 153 154 @Override 155 public Node next() { 156 final int pos = i; 157 final Node key = NodeMap.this.getKey(pos); 158 i++; 159 forward(); 160 return key; 161 } 162 163 @Override 164 public void remove() { 165 throw new UnsupportedOperationException(); 166 } 167 168 private void forward() { 169 while (i < NodeMap.this.values.length && (NodeMap.this.getKey(i) == null || NodeMap.this.values[i] == null)) { 170 i++; 171 } 172 } 173 }; 174 } 175 }; 176 } 177 178 @Override 179 public MapCursor<Node, T> getEntries() { 180 return new MapCursor<Node, T>() { 181 182 int current = -1; 183 184 @Override 185 public boolean advance() { 186 current++; 187 while (current < NodeMap.this.values.length && (NodeMap.this.values[current] == null || NodeMap.this.getKey(current) == null)) { 188 current++; 189 } 190 return current < NodeMap.this.values.length; 191 } 192 193 @Override 194 public Node getKey() { 195 return NodeMap.this.getKey(current); 196 } 197 198 @SuppressWarnings("unchecked") 199 @Override 200 public T getValue() { 201 return (T) NodeMap.this.values[current]; 202 } 203 204 @Override 205 public void remove() { 206 assert NodeMap.this.values[current] != null; 207 NodeMap.this.values[current] = null; 208 } 209 }; 210 } 211 212 @Override 213 public Iterable<T> getValues() { 214 return new Iterable<T>() { 215 216 @Override 217 public Iterator<T> iterator() { 218 return new Iterator<T>() { 219 220 int i = 0; 221 222 @Override 223 public boolean hasNext() { 224 forward(); 225 return i < NodeMap.this.values.length; 226 } 227 228 @SuppressWarnings("unchecked") 229 @Override 230 public T next() { 231 final int pos = i; 232 final T value = (T) NodeMap.this.values[pos]; 233 i++; 234 forward(); 235 return value; 236 } 237 238 @Override 239 public void remove() { 240 throw new UnsupportedOperationException(); 241 } 242 243 private void forward() { 244 while (i < NodeMap.this.values.length && (NodeMap.this.getKey(i) == null || NodeMap.this.values[i] == null)) { 245 i++; 246 } 247 } 248 }; 249 } 250 }; 251 } 252 253 @Override 254 public String toString() { 255 MapCursor<Node, T> i = getEntries(); 256 if (!i.advance()) { 257 return "{}"; 258 } 259 260 StringBuilder sb = new StringBuilder(); 261 sb.append('{'); 262 while (true) { 263 Node key = i.getKey(); 264 T value = i.getValue(); 265 sb.append(key); 266 sb.append('='); 267 sb.append(value); 268 if (!i.advance()) { 269 return sb.append('}').toString(); 270 } 271 sb.append(',').append(' '); 272 } 273 } 274 275 @Override 276 public T put(Node key, T value) { 277 T result = get(key); 278 set(key, value); 279 return result; 280 } 281 282 @Override 283 public T removeKey(Node key) { 284 return put(key, null); 285 } 286 287 @Override 288 public void replaceAll(BiFunction<? super Node, ? super T, ? extends T> function) { 289 for (Node n : getKeys()) { 290 put(n, function.apply(n, get(n))); 291 } 292 } 293 }