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