1 /*
2 * Copyright (c) 2014, 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.core.common;
24
25 import java.util.AbstractSet;
26 import java.util.Collection;
27 import java.util.IdentityHashMap;
28 import java.util.Iterator;
29 import java.util.LinkedHashMap;
30 import java.util.Map;
31 import java.util.Set;
32 import java.util.Spliterator;
33 import java.util.Spliterators;
34 import java.util.function.Consumer;
35
36 /**
37 * A map that combines {@link IdentityHashMap} with {@link LinkedHashMap} for the purpose of
38 * ensuring a deterministic execution order during a capturing compilation.
39 */
40 final class LinkedIdentityHashMap<K, V> implements Map<K, V> {
41
42 private final LinkedHashMap<Id<K>, V> map;
43
44 LinkedIdentityHashMap() {
45 map = new LinkedHashMap<>();
46 }
47
48 LinkedIdentityHashMap(Map<K, V> m) {
49 map = new LinkedHashMap<>(m.size());
50 putAll(m);
51 }
52
53 LinkedIdentityHashMap(int expectedMaxSize) {
54 map = new LinkedHashMap<>(expectedMaxSize);
55 }
56
57 /**
58 * Wrapper for an object that gives uses the object's identity for the purpose of equality
59 * comparisons and computing a hash code.
60 */
61 static final class Id<T> {
62 final T object;
63
64 Id(T object) {
65 assert object != null;
66 this.object = object;
67 }
68
69 @SuppressWarnings("unchecked")
70 @Override
71 public boolean equals(Object obj) {
72 return obj instanceof Id && ((Id<T>) obj).object == object;
73 }
74
75 @Override
76 public int hashCode() {
77 return System.identityHashCode(object);
78 }
79 }
80
81 @Override
82 public int size() {
83 return map.size();
84 }
85
86 @Override
87 public boolean isEmpty() {
88 return map.isEmpty();
89 }
90
91 @Override
92 public boolean containsKey(Object key) {
93 return map.containsKey(id(key));
94 }
95
96 @SuppressWarnings("unchecked")
97 private Id<K> id(Object key) {
98 if (key == null) {
99 return null;
100 }
101 return new Id<>((K) key);
102 }
103
104 @Override
105 public boolean containsValue(Object value) {
106 return map.containsValue(value);
107 }
108
109 @Override
110 public V get(Object key) {
111 return map.get(id(key));
112 }
113
114 @Override
115 public V put(K key, V value) {
116 return map.put(id(key), value);
117 }
118
119 @Override
120 public V remove(Object key) {
121 return map.remove(id(key));
122 }
123
124 @Override
125 @SuppressWarnings("unchecked")
126 public void putAll(Map<? extends K, ? extends V> m) {
127 if (m == null) {
128 throw new NullPointerException();
129 }
130 if (m.getClass() == getClass()) {
131 LinkedIdentityHashMap<K, V> that = (LinkedIdentityHashMap<K, V>) m;
132 map.putAll(that.map);
133
134 } else {
135 for (K key : m.keySet()) {
136 map.put(id(key), m.get(key));
137 }
138 }
139 }
140
141 @Override
142 public void clear() {
143 map.clear();
144 }
145
146 final class KeySet extends AbstractSet<K> {
147 @Override
148 public int size() {
149 return map.size();
150 }
151
152 @Override
153 public void clear() {
154 map.clear();
155 }
156
157 @Override
158 public Iterator<K> iterator() {
159 return new Iterator<K>() {
160 final Iterator<Id<K>> i = map.keySet().iterator();
161
162 @Override
163 public boolean hasNext() {
164 return i.hasNext();
165 }
166
167 @Override
168 public K next() {
169 return i.next().object;
170 }
171
172 @Override
173 public void remove() {
174 i.remove();
175 }
176 };
177 }
178
179 @Override
180 public boolean contains(Object o) {
181 return containsKey(o);
182 }
183
184 @Override
185 public boolean remove(Object o) {
186 return LinkedIdentityHashMap.this.remove(o) != null;
187 }
188
189 @Override
190 public Spliterator<K> spliterator() {
191 return Spliterators.spliterator(this, Spliterator.SIZED | Spliterator.ORDERED | Spliterator.DISTINCT);
192 }
193
194 @Override
195 public void forEach(Consumer<? super K> action) {
196 throw new UnsupportedOperationException();
197 }
198 }
199
200 @Override
201 public Set<K> keySet() {
202 return new KeySet();
203 }
204
205 @Override
206 public Collection<V> values() {
207 return map.values();
208 }
209
210 final class EntrySet extends AbstractSet<Map.Entry<K, V>> {
211 @Override
212 public int size() {
213 return map.size();
214 }
215
216 @Override
217 public void clear() {
218 map.clear();
219 }
220
221 @Override
222 public Iterator<Map.Entry<K, V>> iterator() {
223 return new Iterator<Map.Entry<K, V>>() {
224 final Iterator<Map.Entry<Id<K>, V>> i = map.entrySet().iterator();
225
226 @Override
227 public boolean hasNext() {
228 return i.hasNext();
229 }
230
231 @Override
232 public Map.Entry<K, V> next() {
233 Map.Entry<Id<K>, V> e = i.next();
234 return new Map.Entry<K, V>() {
235
236 @Override
237 public K getKey() {
238 return e.getKey().object;
239 }
240
241 @Override
242 public V getValue() {
243 return e.getValue();
244 }
245
246 @Override
247 public V setValue(V value) {
248 return e.setValue(value);
249 }
250 };
251 }
252
253 @Override
254 public void remove() {
255 i.remove();
256 }
257 };
258 }
259
260 @Override
261 public boolean contains(Object o) {
262 throw new UnsupportedOperationException();
263 }
264
265 @Override
266 public boolean remove(Object o) {
267 throw new UnsupportedOperationException();
268 }
269
270 @Override
271 public Spliterator<Map.Entry<K, V>> spliterator() {
272 throw new UnsupportedOperationException();
273 }
274
275 @Override
276 public void forEach(Consumer<? super Map.Entry<K, V>> action) {
277 throw new UnsupportedOperationException();
278 }
279 }
280
281 @Override
282 public Set<Map.Entry<K, V>> entrySet() {
283 return new EntrySet();
284 }
285 }