LinkedIdentityHashMap.java revision 12651:6ef01bd40ce2 
1279219Sken/*
2279219Sken * Copyright (c) 2014, Oracle and/or its affiliates. All rights reserved.
3279219Sken * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4279219Sken *
5279219Sken * This code is free software; you can redistribute it and/or modify it
6279219Sken * under the terms of the GNU General Public License version 2 only, as
7279219Sken * published by the Free Software Foundation.
8279219Sken *
9279219Sken * This code is distributed in the hope that it will be useful, but WITHOUT
10279219Sken * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11279219Sken * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
12279219Sken * version 2 for more details (a copy is included in the LICENSE file that
13279219Sken * 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 */
23package org.graalvm.compiler.core.common;
24
25import java.util.AbstractSet;
26import java.util.Collection;
27import java.util.IdentityHashMap;
28import java.util.Iterator;
29import java.util.LinkedHashMap;
30import java.util.Map;
31import java.util.Set;
32import java.util.Spliterator;
33import java.util.Spliterators;
34import 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 */
40final 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}
286