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 }