1 /*
2 * Copyright (c) 2011, 2011, 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.AbstractMap.SimpleEntry;
26 import java.util.Arrays;
27 import java.util.Iterator;
28 import java.util.Map.Entry;
29
30 public class NodeMap<T> extends NodeIdAccessor {
31
32 private static final int MIN_REALLOC_SIZE = 16;
33
34 protected Object[] values;
35
36 public NodeMap(Graph graph) {
37 super(graph);
38 this.values = new Object[graph.nodeIdCount()];
39 }
40
41 public NodeMap(NodeMap<T> copyFrom) {
42 super(copyFrom.graph);
43 this.values = Arrays.copyOf(copyFrom.values, copyFrom.values.length);
44 }
45
46 @SuppressWarnings("unchecked")
47 public T get(Node node) {
48 assert check(node);
49 return (T) values[getNodeId(node)];
50 }
51
52 @SuppressWarnings("unchecked")
53 public T getAndGrow(Node node) {
54 checkAndGrow(node);
55 return (T) values[getNodeId(node)];
56 }
57
58 private void checkAndGrow(Node node) {
59 if (isNew(node)) {
60 this.values = Arrays.copyOf(values, Math.max(MIN_REALLOC_SIZE, graph.nodeIdCount() * 3 / 2));
61 }
62 assert check(node);
63 }
64
65 public boolean isEmpty() {
66 return !entries().iterator().hasNext();
67 }
68
69 public boolean containsKey(Object key) {
70 if (key instanceof Node) {
71 Node node = (Node) key;
72 if (node.graph() == graph()) {
73 return get(node) != null;
74 }
75 }
76 return false;
77 }
78
79 public boolean containsValue(Object value) {
80 for (Object o : values) {
81 if (o == value) {
82 return true;
83 }
84 }
85 return false;
86 }
87
88 public Graph graph() {
89 return graph;
90 }
91
92 public void set(Node node, T value) {
93 assert check(node);
94 values[getNodeId(node)] = value;
95 }
96
97 public void setAndGrow(Node node, T value) {
98 checkAndGrow(node);
99 values[getNodeId(node)] = value;
100 }
101
102 /**
103 * @param i
104 * @return Return the key for the entry at index {@code i}
105 */
106 protected Node getKey(int i) {
107 return graph.getNode(i);
108 }
109
110 public int size() {
111 return values.length;
112 }
113
114 public boolean isNew(Node node) {
115 return getNodeId(node) >= size();
116 }
117
118 private boolean check(Node node) {
119 assert node.graph() == graph : String.format("%s is not part of the graph", node);
120 assert !isNew(node) : "this node was added to the graph after creating the node map : " + node;
121 return true;
122 }
123
124 public void clear() {
125 Arrays.fill(values, null);
126 }
127
128 public Iterable<Entry<Node, T>> entries() {
129 return new Iterable<Entry<Node, T>>() {
130
131 @Override
132 public Iterator<Entry<Node, T>> iterator() {
133 return new Iterator<Entry<Node, T>>() {
134
135 int i = 0;
136
137 @Override
138 public boolean hasNext() {
139 forward();
140 return i < NodeMap.this.values.length;
141 }
142
143 @SuppressWarnings("unchecked")
144 @Override
145 public Entry<Node, T> next() {
146 final int pos = i;
147 Node key = NodeMap.this.getKey(pos);
148 T value = (T) NodeMap.this.values[pos];
149 i++;
150 forward();
151 return new SimpleEntry<Node, T>(key, value) {
152
153 private static final long serialVersionUID = 7813842391085737738L;
154
155 @Override
156 public T setValue(T v) {
157 T oldv = super.setValue(v);
158 NodeMap.this.values[pos] = v;
159 return oldv;
160 }
161 };
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 String toString() {
181 Iterator<Entry<Node, T>> i = entries().iterator();
182 if (!i.hasNext()) {
183 return "{}";
184 }
185
186 StringBuilder sb = new StringBuilder();
187 sb.append('{');
188 while (true) {
189 Entry<Node, T> e = i.next();
190 Node key = e.getKey();
191 T value = e.getValue();
192 sb.append(key);
193 sb.append('=');
194 sb.append(value);
195 if (!i.hasNext()) {
196 return sb.append('}').toString();
197 }
198 sb.append(',').append(' ');
199 }
200 }
201 }