1 /*
2 * Copyright (c) 2011, 2019, 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 }