1/*
2 *  Licensed to the Apache Software Foundation (ASF) under one or more
3 *  contributor license agreements.  See the NOTICE file distributed with
4 *  this work for additional information regarding copyright ownership.
5 *  The ASF licenses this file to You under the Apache License, Version 2.0
6 *  (the "License"); you may not use this file except in compliance with
7 *  the License.  You may obtain a copy of the License at
8 *
9 *     http://www.apache.org/licenses/LICENSE-2.0
10 *
11 *  Unless required by applicable law or agreed to in writing, software
12 *  distributed under the License is distributed on an "AS IS" BASIS,
13 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 *  See the License for the specific language governing permissions and
15 *  limitations under the License.
16 */
17
18package java.util;
19
20import java.io.IOException;
21import java.io.ObjectInputStream;
22import java.io.ObjectOutputStream;
23import java.io.Serializable;
24
25/**
26 * IdentityHashMap is a variant on HashMap which tests equality by reference
27 * instead of equality by value. Basically, keys and values are compared for
28 * equality by checking if their references are equal rather than by calling the
29 * "equals" function.
30 * <p>
31 * <b>Note: This class intentionally violates the general contract of {@code
32 * Map}'s on comparing objects by their {@code equals} method.</b>
33 * <p>
34 * IdentityHashMap uses open addressing (linear probing in particular) for
35 * collision resolution. This is different from HashMap which uses Chaining.
36 * <p>
37 * Like HashMap, IdentityHashMap is not thread safe, so access by multiple
38 * threads must be synchronized by an external mechanism such as
39 * Collections.synchronizedMap.
40 *
41 * @since 1.4
42 */
43public class IdentityHashMap<K, V> extends AbstractMap<K, V> implements
44        Map<K, V>, Serializable, Cloneable {
45
46    private static final long serialVersionUID = 8188218128353913216L;
47
48    /*
49     * The internal data structure to hold key value pairs This array holds keys
50     * and values in an alternating fashion.
51     */
52    transient Object[] elementData;
53
54    /* Actual number of key-value pairs. */
55    int size;
56
57    /*
58     * maximum number of elements that can be put in this map before having to
59     * rehash.
60     */
61    transient int threshold;
62
63    /*
64     * default threshold value that an IdentityHashMap created using the default
65     * constructor would have.
66     */
67    private static final int DEFAULT_MAX_SIZE = 21;
68
69    /* Default load factor of 0.75; */
70    private static final int loadFactor = 7500;
71
72    /*
73     * modification count, to keep track of structural modifications between the
74     * IdentityHashMap and the iterator
75     */
76    transient int modCount = 0;
77
78    /*
79     * Object used to represent null keys and values. This is used to
80     * differentiate a literal 'null' key value pair from an empty spot in the
81     * map.
82     */
83    private static final Object NULL_OBJECT = new Object();  //$NON-LOCK-1$
84
85    static class IdentityHashMapEntry<K, V> extends MapEntry<K, V> {
86        private final IdentityHashMap<K,V> map;
87
88        IdentityHashMapEntry(IdentityHashMap<K,V> map, K theKey, V theValue) {
89            super(theKey, theValue);
90            this.map = map;
91        }
92
93        @Override
94        public Object clone() {
95            return super.clone();
96        }
97
98        @Override
99        public boolean equals(Object object) {
100            if (this == object) {
101                return true;
102            }
103            if (object instanceof Map.Entry) {
104                Map.Entry<?, ?> entry = (Map.Entry) object;
105                return (key == entry.getKey()) && (value == entry.getValue());
106            }
107            return false;
108        }
109
110        @Override
111        public int hashCode() {
112            return System.identityHashCode(key)
113                    ^ System.identityHashCode(value);
114        }
115
116        @Override
117        public String toString() {
118            return key + "=" + value;
119        }
120
121        @Override
122        public V setValue(V object) {
123            V result = super.setValue(object);
124            map.put(key, object);
125            return result;
126        }
127    }
128
129    static class IdentityHashMapIterator<E, KT, VT> implements Iterator<E> {
130        private int position = 0; // the current position
131
132        // the position of the entry that was last returned from next()
133        private int lastPosition = 0;
134
135        final IdentityHashMap<KT, VT> associatedMap;
136
137        int expectedModCount;
138
139        final MapEntry.Type<E, KT, VT> type;
140
141        boolean canRemove = false;
142
143        IdentityHashMapIterator(MapEntry.Type<E, KT, VT> value,
144                IdentityHashMap<KT, VT> hm) {
145            associatedMap = hm;
146            type = value;
147            expectedModCount = hm.modCount;
148        }
149
150        public boolean hasNext() {
151            while (position < associatedMap.elementData.length) {
152                // if this is an empty spot, go to the next one
153                if (associatedMap.elementData[position] == null) {
154                    position += 2;
155                } else {
156                    return true;
157                }
158            }
159            return false;
160        }
161
162        void checkConcurrentMod() throws ConcurrentModificationException {
163            if (expectedModCount != associatedMap.modCount) {
164                throw new ConcurrentModificationException();
165            }
166        }
167
168        public E next() {
169            checkConcurrentMod();
170            if (!hasNext()) {
171                throw new NoSuchElementException();
172            }
173
174            IdentityHashMapEntry<KT, VT> result = associatedMap
175                    .getEntry(position);
176            lastPosition = position;
177            position += 2;
178
179            canRemove = true;
180            return type.get(result);
181        }
182
183        public void remove() {
184            checkConcurrentMod();
185            if (!canRemove) {
186                throw new IllegalStateException();
187            }
188
189            canRemove = false;
190            associatedMap.remove(associatedMap.elementData[lastPosition]);
191            position = lastPosition;
192            expectedModCount++;
193        }
194    }
195
196    static class IdentityHashMapEntrySet<KT, VT> extends
197            AbstractSet<Map.Entry<KT, VT>> {
198        private final IdentityHashMap<KT, VT> associatedMap;
199
200        public IdentityHashMapEntrySet(IdentityHashMap<KT, VT> hm) {
201            associatedMap = hm;
202        }
203
204        IdentityHashMap<KT, VT> hashMap() {
205            return associatedMap;
206        }
207
208        @Override
209        public int size() {
210            return associatedMap.size;
211        }
212
213        @Override
214        public void clear() {
215            associatedMap.clear();
216        }
217
218        @Override
219        public boolean remove(Object object) {
220            if (contains(object)) {
221                associatedMap.remove(((Map.Entry) object).getKey());
222                return true;
223            }
224            return false;
225        }
226
227        @Override
228        public boolean contains(Object object) {
229            if (object instanceof Map.Entry) {
230                IdentityHashMapEntry<?, ?> entry = associatedMap
231                        .getEntry(((Map.Entry) object).getKey());
232                // we must call equals on the entry obtained from "this"
233                return entry != null && entry.equals(object);
234            }
235            return false;
236        }
237
238        @Override
239        public Iterator<Map.Entry<KT, VT>> iterator() {
240            return new IdentityHashMapIterator<Map.Entry<KT, VT>, KT, VT>(
241                    new MapEntry.Type<Map.Entry<KT, VT>, KT, VT>() {
242                        public Map.Entry<KT, VT> get(MapEntry<KT, VT> entry) {
243                            return entry;
244                        }
245                    }, associatedMap);
246        }
247    }
248
249    /**
250     * Creates an IdentityHashMap with default expected maximum size.
251     */
252    public IdentityHashMap() {
253        this(DEFAULT_MAX_SIZE);
254    }
255
256    /**
257     * Creates an IdentityHashMap with the specified maximum size parameter.
258     *
259     * @param maxSize
260     *            The estimated maximum number of entries that will be put in
261     *            this map.
262     */
263    public IdentityHashMap(int maxSize) {
264        if (maxSize < 0) {
265            throw new IllegalArgumentException("maxSize < 0: " + maxSize);
266        }
267        size = 0;
268        threshold = getThreshold(maxSize);
269        elementData = newElementArray(computeElementArraySize());
270    }
271
272    private int getThreshold(int maxSize) {
273        // assign the threshold to maxSize initially, this will change to a
274        // higher value if rehashing occurs.
275        return maxSize > 3 ? maxSize : 3;
276    }
277
278    private int computeElementArraySize() {
279        int arraySize = (int) (((long) threshold * 10000) / loadFactor) * 2;
280        // ensure arraySize is positive, the above cast from long to int type
281        // leads to overflow and negative arraySize if threshold is too big
282        return arraySize < 0 ? -arraySize : arraySize;
283    }
284
285    /**
286     * Create a new element array
287     *
288     * @param s
289     *            the number of elements
290     * @return Reference to the element array
291     */
292    private Object[] newElementArray(int s) {
293        return new Object[s];
294    }
295
296    /**
297     * Creates an IdentityHashMap using the given map as initial values.
298     *
299     * @param map
300     *            A map of (key,value) pairs to copy into the IdentityHashMap.
301     */
302    public IdentityHashMap(Map<? extends K, ? extends V> map) {
303        this(map.size() < 6 ? 11 : map.size() * 2);
304        putAllImpl(map);
305    }
306
307    @SuppressWarnings("unchecked")
308    private V massageValue(Object value) {
309        return (V) ((value == NULL_OBJECT) ? null : value);
310    }
311
312    /**
313     * Removes all elements from this map, leaving it empty.
314     *
315     * @see #isEmpty()
316     * @see #size()
317     */
318    @Override
319    public void clear() {
320        size = 0;
321        for (int i = 0; i < elementData.length; i++) {
322            elementData[i] = null;
323        }
324        modCount++;
325    }
326
327    /**
328     * Returns whether this map contains the specified key.
329     *
330     * @param key
331     *            the key to search for.
332     * @return {@code true} if this map contains the specified key,
333     *         {@code false} otherwise.
334     */
335    @Override
336    public boolean containsKey(Object key) {
337        if (key == null) {
338            key = NULL_OBJECT;
339        }
340
341        int index = findIndex(key, elementData);
342        return elementData[index] == key;
343    }
344
345    /**
346     * Returns whether this map contains the specified value.
347     *
348     * @param value
349     *            the value to search for.
350     * @return {@code true} if this map contains the specified value,
351     *         {@code false} otherwise.
352     */
353    @Override
354    public boolean containsValue(Object value) {
355        if (value == null) {
356            value = NULL_OBJECT;
357        }
358
359        for (int i = 1; i < elementData.length; i = i + 2) {
360            if (elementData[i] == value) {
361                return true;
362            }
363        }
364        return false;
365    }
366
367    /**
368     * Returns the value of the mapping with the specified key.
369     *
370     * @param key
371     *            the key.
372     * @return the value of the mapping with the specified key.
373     */
374    @Override
375    public V get(Object key) {
376        if (key == null) {
377            key = NULL_OBJECT;
378        }
379
380        int index = findIndex(key, elementData);
381
382        if (elementData[index] == key) {
383            Object result = elementData[index + 1];
384            return massageValue(result);
385        }
386
387        return null;
388    }
389
390    private IdentityHashMapEntry<K, V> getEntry(Object key) {
391        if (key == null) {
392            key = NULL_OBJECT;
393        }
394
395        int index = findIndex(key, elementData);
396        if (elementData[index] == key) {
397            return getEntry(index);
398        }
399
400        return null;
401    }
402
403    /**
404     * Convenience method for getting the IdentityHashMapEntry without the
405     * NULL_OBJECT elements
406     */
407    @SuppressWarnings("unchecked")
408    private IdentityHashMapEntry<K, V> getEntry(int index) {
409        Object key = elementData[index];
410        Object value = elementData[index + 1];
411
412        if (key == NULL_OBJECT) {
413            key = null;
414        }
415        if (value == NULL_OBJECT) {
416            value = null;
417        }
418
419        return new IdentityHashMapEntry<K, V>(this, (K) key, (V) value);
420    }
421
422    /**
423     * Returns the index where the key is found at, or the index of the next
424     * empty spot if the key is not found in this table.
425     */
426    private int findIndex(Object key, Object[] array) {
427        int length = array.length;
428        int index = getModuloHash(key, length);
429        int last = (index + length - 2) % length;
430        while (index != last) {
431            if (array[index] == key || (array[index] == null)) {
432                /*
433                 * Found the key, or the next empty spot (which means key is not
434                 * in the table)
435                 */
436                break;
437            }
438            index = (index + 2) % length;
439        }
440        return index;
441    }
442
443    private int getModuloHash(Object key, int length) {
444        return ((Collections.secondaryIdentityHash(key) & 0x7FFFFFFF) % (length / 2)) * 2;
445    }
446
447    /**
448     * Maps the specified key to the specified value.
449     *
450     * @param key
451     *            the key.
452     * @param value
453     *            the value.
454     * @return the value of any previous mapping with the specified key or
455     *         {@code null} if there was no such mapping.
456     */
457    @Override
458    public V put(K key, V value) {
459        Object _key = key;
460        Object _value = value;
461        if (_key == null) {
462            _key = NULL_OBJECT;
463        }
464
465        if (_value == null) {
466            _value = NULL_OBJECT;
467        }
468
469        int index = findIndex(_key, elementData);
470
471        // if the key doesn't exist in the table
472        if (elementData[index] != _key) {
473            modCount++;
474            if (++size > threshold) {
475                rehash();
476                index = findIndex(_key, elementData);
477            }
478
479            // insert the key and assign the value to null initially
480            elementData[index] = _key;
481            elementData[index + 1] = null;
482        }
483
484        // insert value to where it needs to go, return the old value
485        Object result = elementData[index + 1];
486        elementData[index + 1] = _value;
487
488        return massageValue(result);
489    }
490
491    /**
492     * Copies all the mappings in the specified map to this map. These mappings
493     * will replace all mappings that this map had for any of the keys currently
494     * in the given map.
495     *
496     * @param map
497     *            the map to copy mappings from.
498     * @throws NullPointerException
499     *             if {@code map} is {@code null}.
500     */
501    @Override
502    public void putAll(Map<? extends K, ? extends V> map) {
503        putAllImpl(map);
504    }
505
506    private void rehash() {
507        int newlength = elementData.length * 2;
508        if (newlength == 0) {
509            newlength = 1;
510        }
511        Object[] newData = newElementArray(newlength);
512        for (int i = 0; i < elementData.length; i = i + 2) {
513            Object key = elementData[i];
514            if (key != null) {
515                // if not empty
516                int index = findIndex(key, newData);
517                newData[index] = key;
518                newData[index + 1] = elementData[i + 1];
519            }
520        }
521        elementData = newData;
522        computeMaxSize();
523    }
524
525    private void computeMaxSize() {
526        threshold = (int) ((long) (elementData.length / 2) * loadFactor / 10000);
527    }
528
529    /**
530     * Removes the mapping with the specified key from this map.
531     *
532     * @param key
533     *            the key of the mapping to remove.
534     * @return the value of the removed mapping, or {@code null} if no mapping
535     *         for the specified key was found.
536     */
537    @Override
538    public V remove(Object key) {
539        if (key == null) {
540            key = NULL_OBJECT;
541        }
542
543        boolean hashedOk;
544        int index, next, hash;
545        Object result, object;
546        index = next = findIndex(key, elementData);
547
548        if (elementData[index] != key) {
549            return null;
550        }
551
552        // store the value for this key
553        result = elementData[index + 1];
554
555        // shift the following elements up if needed
556        // until we reach an empty spot
557        int length = elementData.length;
558        while (true) {
559            next = (next + 2) % length;
560            object = elementData[next];
561            if (object == null) {
562                break;
563            }
564
565            hash = getModuloHash(object, length);
566            hashedOk = hash > index;
567            if (next < index) {
568                hashedOk = hashedOk || (hash <= next);
569            } else {
570                hashedOk = hashedOk && (hash <= next);
571            }
572            if (!hashedOk) {
573                elementData[index] = object;
574                elementData[index + 1] = elementData[next + 1];
575                index = next;
576            }
577        }
578
579        size--;
580        modCount++;
581
582        // clear both the key and the value
583        elementData[index] = null;
584        elementData[index + 1] = null;
585
586        return massageValue(result);
587    }
588
589    /**
590     * Returns a set containing all of the mappings in this map. Each mapping is
591     * an instance of {@link Map.Entry}. As the set is backed by this map,
592     * changes in one will be reflected in the other.
593     *
594     * @return a set of the mappings.
595     */
596    @Override
597    public Set<Map.Entry<K, V>> entrySet() {
598        return new IdentityHashMapEntrySet<K, V>(this);
599    }
600
601    /**
602     * Returns a set of the keys contained in this map. The set is backed by
603     * this map so changes to one are reflected by the other. The set does not
604     * support adding.
605     *
606     * @return a set of the keys.
607     */
608    @Override
609    public Set<K> keySet() {
610        if (keySet == null) {
611            keySet = new AbstractSet<K>() {
612                @Override
613                public boolean contains(Object object) {
614                    return containsKey(object);
615                }
616
617                @Override
618                public int size() {
619                    return IdentityHashMap.this.size();
620                }
621
622                @Override
623                public void clear() {
624                    IdentityHashMap.this.clear();
625                }
626
627                @Override
628                public boolean remove(Object key) {
629                    if (containsKey(key)) {
630                        IdentityHashMap.this.remove(key);
631                        return true;
632                    }
633                    return false;
634                }
635
636                @Override
637                public Iterator<K> iterator() {
638                    return new IdentityHashMapIterator<K, K, V>(
639                            new MapEntry.Type<K, K, V>() {
640                                public K get(MapEntry<K, V> entry) {
641                                    return entry.key;
642                                }
643                            }, IdentityHashMap.this);
644                }
645            };
646        }
647        return keySet;
648    }
649
650    /**
651     * Returns a collection of the values contained in this map. The collection
652     * is backed by this map so changes to one are reflected by the other. The
653     * collection supports remove, removeAll, retainAll and clear operations,
654     * and it does not support add or addAll operations.
655     * <p>
656     * This method returns a collection which is the subclass of
657     * AbstractCollection. The iterator method of this subclass returns a
658     * "wrapper object" over the iterator of map's entrySet(). The {@code size}
659     * method wraps the map's size method and the {@code contains} method wraps
660     * the map's containsValue method.
661     * <p>
662     * The collection is created when this method is called for the first time
663     * and returned in response to all subsequent calls. This method may return
664     * different collections when multiple concurrent calls occur, since no
665     * synchronization is performed.
666     *
667     * @return a collection of the values contained in this map.
668     */
669    @Override
670    public Collection<V> values() {
671        if (valuesCollection == null) {
672            valuesCollection = new AbstractCollection<V>() {
673                @Override
674                public boolean contains(Object object) {
675                    return containsValue(object);
676                }
677
678                @Override
679                public int size() {
680                    return IdentityHashMap.this.size();
681                }
682
683                @Override
684                public void clear() {
685                    IdentityHashMap.this.clear();
686                }
687
688                @Override
689                public Iterator<V> iterator() {
690                    return new IdentityHashMapIterator<V, K, V>(
691                            new MapEntry.Type<V, K, V>() {
692                                public V get(MapEntry<K, V> entry) {
693                                    return entry.value;
694                                }
695                            }, IdentityHashMap.this);
696                }
697
698                @Override
699                public boolean remove(Object object) {
700                    Iterator<?> it = iterator();
701                    while (it.hasNext()) {
702                        if (object == it.next()) {
703                            it.remove();
704                            return true;
705                        }
706                    }
707                    return false;
708                }
709            };
710        }
711        return valuesCollection;
712    }
713
714    /**
715     * Compares this map with other objects. This map is equal to another map is
716     * it represents the same set of mappings. With this map, two mappings are
717     * the same if both the key and the value are equal by reference. When
718     * compared with a map that is not an IdentityHashMap, the equals method is
719     * neither necessarily symmetric (a.equals(b) implies b.equals(a)) nor
720     * transitive (a.equals(b) and b.equals(c) implies a.equals(c)).
721     *
722     * @param object
723     *            the object to compare to.
724     * @return whether the argument object is equal to this object.
725     */
726    @Override
727    public boolean equals(Object object) {
728        /*
729         * We need to override the equals method in AbstractMap because
730         * AbstractMap.equals will call ((Map) object).entrySet().contains() to
731         * determine equality of the entries, so it will defer to the argument
732         * for comparison, meaning that reference-based comparison will not take
733         * place. We must ensure that all comparison is implemented by methods
734         * in this class (or in one of our inner classes) for reference-based
735         * comparison to take place.
736         */
737        if (this == object) {
738            return true;
739        }
740        if (object instanceof Map) {
741            Map<?, ?> map = (Map) object;
742            if (size() != map.size()) {
743                return false;
744            }
745
746            Set<Map.Entry<K, V>> set = entrySet();
747            // ensure we use the equals method of the set created by "this"
748            return set.equals(map.entrySet());
749        }
750        return false;
751    }
752
753    /**
754     * Returns a new IdentityHashMap with the same mappings and size as this
755     * one.
756     *
757     * @return a shallow copy of this IdentityHashMap.
758     * @see java.lang.Cloneable
759     */
760    @Override
761    public Object clone() {
762        try {
763            IdentityHashMap<K, V> cloneHashMap = (IdentityHashMap<K, V>) super.clone();
764            cloneHashMap.elementData = newElementArray(elementData.length);
765            System.arraycopy(elementData, 0, cloneHashMap.elementData, 0, elementData.length);
766            return cloneHashMap;
767        } catch (CloneNotSupportedException e) {
768            throw new AssertionError(e);
769        }
770    }
771
772    /**
773     * Returns whether this IdentityHashMap has no elements.
774     *
775     * @return {@code true} if this IdentityHashMap has no elements,
776     *         {@code false} otherwise.
777     * @see #size()
778     */
779    @Override
780    public boolean isEmpty() {
781        return size == 0;
782    }
783
784    /**
785     * Returns the number of mappings in this IdentityHashMap.
786     *
787     * @return the number of mappings in this IdentityHashMap.
788     */
789    @Override
790    public int size() {
791        return size;
792    }
793
794    private void writeObject(ObjectOutputStream stream) throws IOException {
795        stream.defaultWriteObject();
796        stream.writeInt(size);
797        Iterator<?> iterator = entrySet().iterator();
798        while (iterator.hasNext()) {
799            MapEntry<?, ?> entry = (MapEntry) iterator.next();
800            stream.writeObject(entry.key);
801            stream.writeObject(entry.value);
802        }
803    }
804
805    @SuppressWarnings("unchecked")
806    private void readObject(ObjectInputStream stream) throws IOException,
807            ClassNotFoundException {
808        stream.defaultReadObject();
809        int savedSize = stream.readInt();
810        threshold = getThreshold(DEFAULT_MAX_SIZE);
811        elementData = newElementArray(computeElementArraySize());
812        for (int i = savedSize; --i >= 0;) {
813            K key = (K) stream.readObject();
814            put(key, (V) stream.readObject());
815        }
816        size = savedSize;
817    }
818
819    private void putAllImpl(Map<? extends K, ? extends V> map) {
820        if (map.entrySet() != null) {
821            super.putAll(map);
822        }
823    }
824}
825