001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.commons.collections4.map;
018
019import java.io.IOException;
020import java.io.ObjectInputStream;
021import java.io.ObjectOutputStream;
022import java.lang.ref.Reference;
023import java.lang.ref.ReferenceQueue;
024import java.lang.ref.SoftReference;
025import java.lang.ref.WeakReference;
026import java.util.ArrayList;
027import java.util.Collection;
028import java.util.ConcurrentModificationException;
029import java.util.Iterator;
030import java.util.List;
031import java.util.Map;
032import java.util.NoSuchElementException;
033import java.util.Set;
034
035import org.apache.commons.collections4.MapIterator;
036import org.apache.commons.collections4.keyvalue.DefaultMapEntry;
037
038/**
039 * An abstract implementation of a hash-based map that allows the entries to
040 * be removed by the garbage collector.
041 * <p>
042 * This class implements all the features necessary for a subclass reference
043 * hash-based map. Key-value entries are stored in instances of the
044 * <code>ReferenceEntry</code> class which can be overridden and replaced.
045 * The iterators can similarly be replaced, without the need to replace the KeySet,
046 * EntrySet and Values view classes.
047 * <p>
048 * Overridable methods are provided to change the default hashing behaviour, and
049 * to change how entries are added to and removed from the map. Hopefully, all you
050 * need for unusual subclasses is here.
051 * <p>
052 * When you construct an <code>AbstractReferenceMap</code>, you can specify what
053 * kind of references are used to store the map's keys and values.
054 * If non-hard references are used, then the garbage collector can remove
055 * mappings if a key or value becomes unreachable, or if the JVM's memory is
056 * running low. For information on how the different reference types behave,
057 * see {@link Reference}.
058 * <p>
059 * Different types of references can be specified for keys and values.
060 * The keys can be configured to be weak but the values hard,
061 * in which case this class will behave like a
062 * <a href="http://java.sun.com/j2se/1.4/docs/api/java/util/WeakHashMap.html">
063 * <code>WeakHashMap</code></a>. However, you can also specify hard keys and
064 * weak values, or any other combination. The default constructor uses
065 * hard keys and soft values, providing a memory-sensitive cache.
066 * <p>
067 * This {@link Map} implementation does <i>not</i> allow null elements.
068 * Attempting to add a null key or value to the map will raise a
069 * <code>NullPointerException</code>.
070 * <p>
071 * All the available iterators can be reset back to the start by casting to
072 * <code>ResettableIterator</code> and calling <code>reset()</code>.
073 * <p>
074 * This implementation is not synchronized.
075 * You can use {@link java.util.Collections#synchronizedMap} to
076 * provide synchronized access to a <code>ReferenceMap</code>.
077 *
078 * @param <K> the type of the keys in this map
079 * @param <V> the type of the values in this map
080 *
081 * @see java.lang.ref.Reference
082 * @since 3.1 (extracted from ReferenceMap in 3.0)
083 */
084public abstract class AbstractReferenceMap<K, V> extends AbstractHashedMap<K, V> {
085
086    /**
087     * Reference type enum.
088     */
089    public enum ReferenceStrength {
090        HARD(0), SOFT(1), WEAK(2);
091
092        /** value */
093        public final int value;
094
095        /**
096         * Resolve enum from int.
097         * @param value  the int value
098         * @return ReferenceType
099         * @throws IllegalArgumentException if the specified value is invalid.
100         */
101        public static ReferenceStrength resolve(final int value) {
102            switch (value) {
103            case 0:
104                return HARD;
105            case 1:
106                return SOFT;
107            case 2:
108                return WEAK;
109            default:
110                throw new IllegalArgumentException();
111            }
112        }
113
114        private ReferenceStrength(final int value) {
115            this.value = value;
116        }
117
118    }
119
120    /**
121     * The reference type for keys.
122     */
123    private ReferenceStrength keyType;
124
125    /**
126     * The reference type for values.
127     */
128    private ReferenceStrength valueType;
129
130    /**
131     * Should the value be automatically purged when the associated key has been collected?
132     */
133    private boolean purgeValues;
134
135    /**
136     * ReferenceQueue used to eliminate stale mappings.
137     * See purge.
138     */
139    private transient ReferenceQueue<Object> queue;
140
141    //-----------------------------------------------------------------------
142    /**
143     * Constructor used during deserialization.
144     */
145    protected AbstractReferenceMap() {
146        super();
147    }
148
149    /**
150     * Constructs a new empty map with the specified reference types,
151     * load factor and initial capacity.
152     *
153     * @param keyType  the type of reference to use for keys;
154     *   must be {@link ReferenceStrength#HARD HARD},
155     *   {@link ReferenceStrength#SOFT SOFT},
156     *   {@link ReferenceStrength#WEAK WEAK}
157     * @param valueType  the type of reference to use for values;
158     *   must be {@link ReferenceStrength#HARD},
159     *   {@link ReferenceStrength#SOFT SOFT},
160     *   {@link ReferenceStrength#WEAK WEAK}
161     * @param capacity  the initial capacity for the map
162     * @param loadFactor  the load factor for the map
163     * @param purgeValues  should the value be automatically purged when the
164     *   key is garbage collected
165     */
166    protected AbstractReferenceMap(
167            final ReferenceStrength keyType, final ReferenceStrength valueType, final int capacity,
168            final float loadFactor, final boolean purgeValues) {
169        super(capacity, loadFactor);
170        this.keyType = keyType;
171        this.valueType = valueType;
172        this.purgeValues = purgeValues;
173    }
174
175    /**
176     * Initialise this subclass during construction, cloning or deserialization.
177     */
178    @Override
179    protected void init() {
180        queue = new ReferenceQueue<>();
181    }
182
183    //-----------------------------------------------------------------------
184    /**
185     * Gets the size of the map.
186     *
187     * @return the size
188     */
189    @Override
190    public int size() {
191        purgeBeforeRead();
192        return super.size();
193    }
194
195    /**
196     * Checks whether the map is currently empty.
197     *
198     * @return true if the map is currently size zero
199     */
200    @Override
201    public boolean isEmpty() {
202        purgeBeforeRead();
203        return super.isEmpty();
204    }
205
206    /**
207     * Checks whether the map contains the specified key.
208     *
209     * @param key  the key to search for
210     * @return true if the map contains the key
211     */
212    @Override
213    public boolean containsKey(final Object key) {
214        purgeBeforeRead();
215        final Entry<K, V> entry = getEntry(key);
216        if (entry == null) {
217            return false;
218        }
219        return entry.getValue() != null;
220    }
221
222    /**
223     * Checks whether the map contains the specified value.
224     *
225     * @param value  the value to search for
226     * @return true if the map contains the value
227     */
228    @Override
229    public boolean containsValue(final Object value) {
230        purgeBeforeRead();
231        if (value == null) {
232            return false;
233        }
234        return super.containsValue(value);
235    }
236
237    /**
238     * Gets the value mapped to the key specified.
239     *
240     * @param key  the key
241     * @return the mapped value, null if no match
242     */
243    @Override
244    public V get(final Object key) {
245        purgeBeforeRead();
246        final Entry<K, V> entry = getEntry(key);
247        if (entry == null) {
248            return null;
249        }
250        return entry.getValue();
251    }
252
253
254    /**
255     * Puts a key-value mapping into this map.
256     * Neither the key nor the value may be null.
257     *
258     * @param key  the key to add, must not be null
259     * @param value  the value to add, must not be null
260     * @return the value previously mapped to this key, null if none
261     * @throws NullPointerException if either the key or value is null
262     */
263    @Override
264    public V put(final K key, final V value) {
265        if (key == null) {
266            throw new NullPointerException("null keys not allowed");
267        }
268        if (value == null) {
269            throw new NullPointerException("null values not allowed");
270        }
271
272        purgeBeforeWrite();
273        return super.put(key, value);
274    }
275
276    /**
277     * Removes the specified mapping from this map.
278     *
279     * @param key  the mapping to remove
280     * @return the value mapped to the removed key, null if key not in map
281     */
282    @Override
283    public V remove(final Object key) {
284        if (key == null) {
285            return null;
286        }
287        purgeBeforeWrite();
288        return super.remove(key);
289    }
290
291    /**
292     * Clears this map.
293     */
294    @Override
295    public void clear() {
296        super.clear();
297        // drain the queue
298        while (queue.poll() != null) {} // NOPMD
299    }
300
301    //-----------------------------------------------------------------------
302    /**
303     * Gets a MapIterator over the reference map.
304     * The iterator only returns valid key/value pairs.
305     *
306     * @return a map iterator
307     */
308    @Override
309    public MapIterator<K, V> mapIterator() {
310        return new ReferenceMapIterator<>(this);
311    }
312
313    /**
314     * Returns a set view of this map's entries.
315     * An iterator returned entry is valid until <code>next()</code> is called again.
316     * The <code>setValue()</code> method on the <code>toArray</code> entries has no effect.
317     *
318     * @return a set view of this map's entries
319     */
320    @Override
321    public Set<Map.Entry<K, V>> entrySet() {
322        if (entrySet == null) {
323            entrySet = new ReferenceEntrySet<>(this);
324        }
325        return entrySet;
326    }
327
328    /**
329     * Returns a set view of this map's keys.
330     *
331     * @return a set view of this map's keys
332     */
333    @Override
334    public Set<K> keySet() {
335        if (keySet == null) {
336            keySet = new ReferenceKeySet<>(this);
337        }
338        return keySet;
339    }
340
341    /**
342     * Returns a collection view of this map's values.
343     *
344     * @return a set view of this map's values
345     */
346    @Override
347    public Collection<V> values() {
348        if (values == null) {
349            values = new ReferenceValues<>(this);
350        }
351        return values;
352    }
353
354    //-----------------------------------------------------------------------
355    /**
356     * Purges stale mappings from this map before read operations.
357     * <p>
358     * This implementation calls {@link #purge()} to maintain a consistent state.
359     */
360    protected void purgeBeforeRead() {
361        purge();
362    }
363
364    /**
365     * Purges stale mappings from this map before write operations.
366     * <p>
367     * This implementation calls {@link #purge()} to maintain a consistent state.
368     */
369    protected void purgeBeforeWrite() {
370        purge();
371    }
372
373    /**
374     * Purges stale mappings from this map.
375     * <p>
376     * Note that this method is not synchronized!  Special
377     * care must be taken if, for instance, you want stale
378     * mappings to be removed on a periodic basis by some
379     * background thread.
380     */
381    protected void purge() {
382        Reference<?> ref = queue.poll();
383        while (ref != null) {
384            purge(ref);
385            ref = queue.poll();
386        }
387    }
388
389    /**
390     * Purges the specified reference.
391     *
392     * @param ref  the reference to purge
393     */
394    protected void purge(final Reference<?> ref) {
395        // The hashCode of the reference is the hashCode of the
396        // mapping key, even if the reference refers to the
397        // mapping value...
398        final int hash = ref.hashCode();
399        final int index = hashIndex(hash, data.length);
400        HashEntry<K, V> previous = null;
401        HashEntry<K, V> entry = data[index];
402        while (entry != null) {
403            if (((ReferenceEntry<K, V>) entry).purge(ref)) {
404                if (previous == null) {
405                    data[index] = entry.next;
406                } else {
407                    previous.next = entry.next;
408                }
409                this.size--;
410                return;
411            }
412            previous = entry;
413            entry = entry.next;
414        }
415
416    }
417
418    //-----------------------------------------------------------------------
419    /**
420     * Gets the entry mapped to the key specified.
421     *
422     * @param key  the key
423     * @return the entry, null if no match
424     */
425    @Override
426    protected HashEntry<K, V> getEntry(final Object key) {
427        if (key == null) {
428            return null;
429        }
430        return super.getEntry(key);
431    }
432
433    /**
434     * Gets the hash code for a MapEntry.
435     * Subclasses can override this, for example to use the identityHashCode.
436     *
437     * @param key  the key to get a hash code for, may be null
438     * @param value  the value to get a hash code for, may be null
439     * @return the hash code, as per the MapEntry specification
440     */
441    protected int hashEntry(final Object key, final Object value) {
442        return (key == null ? 0 : key.hashCode()) ^
443               (value == null ? 0 : value.hashCode());
444    }
445
446    /**
447     * Compares two keys, in internal converted form, to see if they are equal.
448     * <p>
449     * This implementation converts the key from the entry to a real reference
450     * before comparison.
451     *
452     * @param key1  the first key to compare passed in from outside
453     * @param key2  the second key extracted from the entry via <code>entry.key</code>
454     * @return true if equal
455     */
456    @Override
457    @SuppressWarnings("unchecked")
458    protected boolean isEqualKey(final Object key1, Object key2) {
459        key2 = keyType == ReferenceStrength.HARD ? key2 : ((Reference<K>) key2).get();
460        return key1 == key2 || key1.equals(key2);
461    }
462
463    /**
464     * Creates a ReferenceEntry instead of a HashEntry.
465     *
466     * @param next  the next entry in sequence
467     * @param hashCode  the hash code to use
468     * @param key  the key to store
469     * @param value  the value to store
470     * @return the newly created entry
471     */
472    @Override
473    protected ReferenceEntry<K, V> createEntry(final HashEntry<K, V> next, final int hashCode,
474                                               final K key, final V value) {
475        return new ReferenceEntry<>(this, next, hashCode, key, value);
476    }
477
478    /**
479     * Creates an entry set iterator.
480     *
481     * @return the entrySet iterator
482     */
483    @Override
484    protected Iterator<Map.Entry<K, V>> createEntrySetIterator() {
485        return new ReferenceEntrySetIterator<>(this);
486    }
487
488    /**
489     * Creates an key set iterator.
490     *
491     * @return the keySet iterator
492     */
493    @Override
494    protected Iterator<K> createKeySetIterator() {
495        return new ReferenceKeySetIterator<>(this);
496    }
497
498    /**
499     * Creates an values iterator.
500     *
501     * @return the values iterator
502     */
503    @Override
504    protected Iterator<V> createValuesIterator() {
505        return new ReferenceValuesIterator<>(this);
506    }
507
508    //-----------------------------------------------------------------------
509    /**
510     * EntrySet implementation.
511     */
512    static class ReferenceEntrySet<K, V> extends EntrySet<K, V> {
513
514        protected ReferenceEntrySet(final AbstractHashedMap<K, V> parent) {
515            super(parent);
516        }
517
518        @Override
519        public Object[] toArray() {
520            return toArray(new Object[size()]);
521        }
522
523        @Override
524        public <T> T[] toArray(final T[] arr) {
525            // special implementation to handle disappearing entries
526            final ArrayList<Map.Entry<K, V>> list = new ArrayList<>(size());
527            for (final Map.Entry<K, V> entry : this) {
528                list.add(new DefaultMapEntry<>(entry));
529            }
530            return list.toArray(arr);
531        }
532    }
533
534    //-----------------------------------------------------------------------
535    /**
536     * KeySet implementation.
537     */
538    static class ReferenceKeySet<K> extends KeySet<K> {
539
540        protected ReferenceKeySet(final AbstractHashedMap<K, ?> parent) {
541            super(parent);
542        }
543
544        @Override
545        public Object[] toArray() {
546            return toArray(new Object[size()]);
547        }
548
549        @Override
550        public <T> T[] toArray(final T[] arr) {
551            // special implementation to handle disappearing keys
552            final List<K> list = new ArrayList<>(size());
553            for (final K key : this) {
554                list.add(key);
555            }
556            return list.toArray(arr);
557        }
558    }
559
560    //-----------------------------------------------------------------------
561    /**
562     * Values implementation.
563     */
564    static class ReferenceValues<V> extends Values<V> {
565
566        protected ReferenceValues(final AbstractHashedMap<?, V> parent) {
567            super(parent);
568        }
569
570        @Override
571        public Object[] toArray() {
572            return toArray(new Object[size()]);
573        }
574
575        @Override
576        public <T> T[] toArray(final T[] arr) {
577            // special implementation to handle disappearing values
578            final List<V> list = new ArrayList<>(size());
579            for (final V value : this) {
580                list.add(value);
581            }
582            return list.toArray(arr);
583        }
584    }
585
586    //-----------------------------------------------------------------------
587    /**
588     * A MapEntry implementation for the map.
589     * <p>
590     * If getKey() or getValue() returns null, it means
591     * the mapping is stale and should be removed.
592     *
593     * @since 3.1
594     */
595    protected static class ReferenceEntry<K, V> extends HashEntry<K, V> {
596        /** The parent map */
597        private final AbstractReferenceMap<K, V> parent;
598
599        /**
600         * Creates a new entry object for the ReferenceMap.
601         *
602         * @param parent  the parent map
603         * @param next  the next entry in the hash bucket
604         * @param hashCode  the hash code of the key
605         * @param key  the key
606         * @param value  the value
607         */
608        public ReferenceEntry(final AbstractReferenceMap<K, V> parent, final HashEntry<K, V> next,
609                              final int hashCode, final K key, final V value) {
610            super(next, hashCode, null, null);
611            this.parent = parent;
612            this.key = toReference(parent.keyType, key, hashCode);
613            this.value = toReference(parent.valueType, value, hashCode); // the key hashCode is passed in deliberately
614        }
615
616        /**
617         * Gets the key from the entry.
618         * This method dereferences weak and soft keys and thus may return null.
619         *
620         * @return the key, which may be null if it was garbage collected
621         */
622        @Override
623        @SuppressWarnings("unchecked")
624        public K getKey() {
625            return (K) (parent.keyType == ReferenceStrength.HARD ? key : ((Reference<K>) key).get());
626        }
627
628        /**
629         * Gets the value from the entry.
630         * This method dereferences weak and soft value and thus may return null.
631         *
632         * @return the value, which may be null if it was garbage collected
633         */
634        @Override
635        @SuppressWarnings("unchecked")
636        public V getValue() {
637            return (V) (parent.valueType == ReferenceStrength.HARD ? value : ((Reference<V>) value).get());
638        }
639
640        /**
641         * Sets the value of the entry.
642         *
643         * @param obj  the object to store
644         * @return the previous value
645         */
646        @Override
647        @SuppressWarnings("unchecked")
648        public V setValue(final V obj) {
649            final V old = getValue();
650            if (parent.valueType != ReferenceStrength.HARD) {
651                ((Reference<V>) value).clear();
652            }
653            value = toReference(parent.valueType, obj, hashCode);
654            return old;
655        }
656
657        /**
658         * Compares this map entry to another.
659         * <p>
660         * This implementation uses <code>isEqualKey</code> and
661         * <code>isEqualValue</code> on the main map for comparison.
662         *
663         * @param obj  the other map entry to compare to
664         * @return true if equal, false if not
665         */
666        @Override
667        public boolean equals(final Object obj) {
668            if (obj == this) {
669                return true;
670            }
671            if (obj instanceof Map.Entry == false) {
672                return false;
673            }
674
675            final Map.Entry<?, ?> entry = (Map.Entry<?, ?>)obj;
676            final Object entryKey = entry.getKey();  // convert to hard reference
677            final Object entryValue = entry.getValue();  // convert to hard reference
678            if (entryKey == null || entryValue == null) {
679                return false;
680            }
681            // compare using map methods, aiding identity subclass
682            // note that key is direct access and value is via method
683            return parent.isEqualKey(entryKey, key) &&
684                   parent.isEqualValue(entryValue, getValue());
685        }
686
687        /**
688         * Gets the hashcode of the entry using temporary hard references.
689         * <p>
690         * This implementation uses <code>hashEntry</code> on the main map.
691         *
692         * @return the hashcode of the entry
693         */
694        @Override
695        public int hashCode() {
696            return parent.hashEntry(getKey(), getValue());
697        }
698
699        /**
700         * Constructs a reference of the given type to the given referent.
701         * The reference is registered with the queue for later purging.
702         *
703         * @param <T> the type of the referenced object
704         * @param type  HARD, SOFT or WEAK
705         * @param referent  the object to refer to
706         * @param hash  the hash code of the <i>key</i> of the mapping;
707         *    this number might be different from referent.hashCode() if
708         *    the referent represents a value and not a key
709         * @return the reference to the object
710         */
711        protected <T> Object toReference(final ReferenceStrength type, final T referent, final int hash) {
712            if (type == ReferenceStrength.HARD) {
713                return referent;
714            }
715            if (type == ReferenceStrength.SOFT) {
716                return new SoftRef<>(hash, referent, parent.queue);
717            }
718            if (type == ReferenceStrength.WEAK) {
719                return new WeakRef<>(hash, referent, parent.queue);
720            }
721            throw new Error();
722        }
723
724        /**
725         * Purges the specified reference
726         * @param ref  the reference to purge
727         * @return true or false
728         */
729        boolean purge(final Reference<?> ref) {
730            boolean r = parent.keyType != ReferenceStrength.HARD && key == ref;
731            r = r || parent.valueType != ReferenceStrength.HARD && value == ref;
732            if (r) {
733                if (parent.keyType != ReferenceStrength.HARD) {
734                    ((Reference<?>) key).clear();
735                }
736                if (parent.valueType != ReferenceStrength.HARD) {
737                    ((Reference<?>) value).clear();
738                } else if (parent.purgeValues) {
739                    value = null;
740                }
741            }
742            return r;
743        }
744
745        /**
746         * Gets the next entry in the bucket.
747         *
748         * @return the next entry in the bucket
749         */
750        protected ReferenceEntry<K, V> next() {
751            return (ReferenceEntry<K, V>) next;
752        }
753    }
754
755    //-----------------------------------------------------------------------
756    /**
757     * Base iterator class.
758     */
759    static class ReferenceBaseIterator<K, V> {
760        /** The parent map */
761        final AbstractReferenceMap<K, V> parent;
762
763        // These fields keep track of where we are in the table.
764        int index;
765        ReferenceEntry<K, V> entry;
766        ReferenceEntry<K, V> previous;
767
768        // These Object fields provide hard references to the
769        // current and next entry; this assures that if hasNext()
770        // returns true, next() will actually return a valid element.
771        K currentKey, nextKey;
772        V currentValue, nextValue;
773
774        int expectedModCount;
775
776        public ReferenceBaseIterator(final AbstractReferenceMap<K, V> parent) {
777            super();
778            this.parent = parent;
779            index = parent.size() != 0 ? parent.data.length : 0;
780            // have to do this here!  size() invocation above
781            // may have altered the modCount.
782            expectedModCount = parent.modCount;
783        }
784
785        public boolean hasNext() {
786            checkMod();
787            while (nextNull()) {
788                ReferenceEntry<K, V> e = entry;
789                int i = index;
790                while (e == null && i > 0) {
791                    i--;
792                    e = (ReferenceEntry<K, V>) parent.data[i];
793                }
794                entry = e;
795                index = i;
796                if (e == null) {
797                    currentKey = null;
798                    currentValue = null;
799                    return false;
800                }
801                nextKey = e.getKey();
802                nextValue = e.getValue();
803                if (nextNull()) {
804                    entry = entry.next();
805                }
806            }
807            return true;
808        }
809
810        private void checkMod() {
811            if (parent.modCount != expectedModCount) {
812                throw new ConcurrentModificationException();
813            }
814        }
815
816        private boolean nextNull() {
817            return nextKey == null || nextValue == null;
818        }
819
820        protected ReferenceEntry<K, V> nextEntry() {
821            checkMod();
822            if (nextNull() && !hasNext()) {
823                throw new NoSuchElementException();
824            }
825            previous = entry;
826            entry = entry.next();
827            currentKey = nextKey;
828            currentValue = nextValue;
829            nextKey = null;
830            nextValue = null;
831            return previous;
832        }
833
834        protected ReferenceEntry<K, V> currentEntry() {
835            checkMod();
836            return previous;
837        }
838
839        public void remove() {
840            checkMod();
841            if (previous == null) {
842                throw new IllegalStateException();
843            }
844            parent.remove(currentKey);
845            previous = null;
846            currentKey = null;
847            currentValue = null;
848            expectedModCount = parent.modCount;
849        }
850    }
851
852    /**
853     * The EntrySet iterator.
854     */
855    static class ReferenceEntrySetIterator<K, V>
856            extends ReferenceBaseIterator<K, V> implements Iterator<Map.Entry<K, V>> {
857
858        public ReferenceEntrySetIterator(final AbstractReferenceMap<K, V> parent) {
859            super(parent);
860        }
861
862        @Override
863        public Map.Entry<K, V> next() {
864            return nextEntry();
865        }
866
867    }
868
869    /**
870     * The keySet iterator.
871     */
872    static class ReferenceKeySetIterator<K> extends ReferenceBaseIterator<K, Object> implements Iterator<K> {
873
874        @SuppressWarnings("unchecked")
875        ReferenceKeySetIterator(final AbstractReferenceMap<K, ?> parent) {
876            super((AbstractReferenceMap<K, Object>) parent);
877        }
878
879        @Override
880        public K next() {
881            return nextEntry().getKey();
882        }
883    }
884
885    /**
886     * The values iterator.
887     */
888    static class ReferenceValuesIterator<V> extends ReferenceBaseIterator<Object, V> implements Iterator<V> {
889
890        @SuppressWarnings("unchecked")
891        ReferenceValuesIterator(final AbstractReferenceMap<?, V> parent) {
892            super((AbstractReferenceMap<Object, V>) parent);
893        }
894
895        @Override
896        public V next() {
897            return nextEntry().getValue();
898        }
899    }
900
901    /**
902     * The MapIterator implementation.
903     */
904    static class ReferenceMapIterator<K, V> extends ReferenceBaseIterator<K, V> implements MapIterator<K, V> {
905
906        protected ReferenceMapIterator(final AbstractReferenceMap<K, V> parent) {
907            super(parent);
908        }
909
910        @Override
911        public K next() {
912            return nextEntry().getKey();
913        }
914
915        @Override
916        public K getKey() {
917            final HashEntry<K, V> current = currentEntry();
918            if (current == null) {
919                throw new IllegalStateException(AbstractHashedMap.GETKEY_INVALID);
920            }
921            return current.getKey();
922        }
923
924        @Override
925        public V getValue() {
926            final HashEntry<K, V> current = currentEntry();
927            if (current == null) {
928                throw new IllegalStateException(AbstractHashedMap.GETVALUE_INVALID);
929            }
930            return current.getValue();
931        }
932
933        @Override
934        public V setValue(final V value) {
935            final HashEntry<K, V> current = currentEntry();
936            if (current == null) {
937                throw new IllegalStateException(AbstractHashedMap.SETVALUE_INVALID);
938            }
939            return current.setValue(value);
940        }
941    }
942
943    //-----------------------------------------------------------------------
944    // These two classes store the hashCode of the key of
945    // of the mapping, so that after they're dequeued a quick
946    // lookup of the bucket in the table can occur.
947
948    /**
949     * A soft reference holder.
950     */
951    static class SoftRef<T> extends SoftReference<T> {
952        /** the hashCode of the key (even if the reference points to a value) */
953        private final int hash;
954
955        public SoftRef(final int hash, final T r, final ReferenceQueue<? super T> q) {
956            super(r, q);
957            this.hash = hash;
958        }
959
960        @Override
961        public int hashCode() {
962            return hash;
963        }
964    }
965
966    /**
967     * A weak reference holder.
968     */
969    static class WeakRef<T> extends WeakReference<T> {
970        /** the hashCode of the key (even if the reference points to a value) */
971        private final int hash;
972
973        public WeakRef(final int hash, final T r, final ReferenceQueue<? super T> q) {
974            super(r, q);
975            this.hash = hash;
976        }
977
978        @Override
979        public int hashCode() {
980            return hash;
981        }
982    }
983
984    //-----------------------------------------------------------------------
985    /**
986     * Replaces the superclass method to store the state of this class.
987     * <p>
988     * Serialization is not one of the JDK's nicest topics. Normal serialization will
989     * initialise the superclass before the subclass. Sometimes however, this isn't
990     * what you want, as in this case the <code>put()</code> method on read can be
991     * affected by subclass state.
992     * <p>
993     * The solution adopted here is to serialize the state data of this class in
994     * this protected method. This method must be called by the
995     * <code>writeObject()</code> of the first serializable subclass.
996     * <p>
997     * Subclasses may override if they have a specific field that must be present
998     * on read before this implementation will work. Generally, the read determines
999     * what must be serialized here, if anything.
1000     *
1001     * @param out  the output stream
1002     * @throws IOException if an error occurs while writing to the stream
1003     */
1004    @Override
1005    protected void doWriteObject(final ObjectOutputStream out) throws IOException {
1006        out.writeInt(keyType.value);
1007        out.writeInt(valueType.value);
1008        out.writeBoolean(purgeValues);
1009        out.writeFloat(loadFactor);
1010        out.writeInt(data.length);
1011        for (final MapIterator<K, V> it = mapIterator(); it.hasNext();) {
1012            out.writeObject(it.next());
1013            out.writeObject(it.getValue());
1014        }
1015        out.writeObject(null);  // null terminate map
1016        // do not call super.doWriteObject() as code there doesn't work for reference map
1017    }
1018
1019    /**
1020     * Replaces the superclass method to read the state of this class.
1021     * <p>
1022     * Serialization is not one of the JDK's nicest topics. Normal serialization will
1023     * initialise the superclass before the subclass. Sometimes however, this isn't
1024     * what you want, as in this case the <code>put()</code> method on read can be
1025     * affected by subclass state.
1026     * <p>
1027     * The solution adopted here is to deserialize the state data of this class in
1028     * this protected method. This method must be called by the
1029     * <code>readObject()</code> of the first serializable subclass.
1030     * <p>
1031     * Subclasses may override if the subclass has a specific field that must be present
1032     * before <code>put()</code> or <code>calculateThreshold()</code> will work correctly.
1033     *
1034     * @param in  the input stream
1035     * @throws IOException if an error occurs while reading from the stream
1036     * @throws ClassNotFoundException if an object read from the stream can not be loaded
1037     */
1038    @Override
1039    @SuppressWarnings("unchecked")
1040    protected void doReadObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
1041        this.keyType = ReferenceStrength.resolve(in.readInt());
1042        this.valueType = ReferenceStrength.resolve(in.readInt());
1043        this.purgeValues = in.readBoolean();
1044        this.loadFactor = in.readFloat();
1045        final int capacity = in.readInt();
1046        init();
1047        data = new HashEntry[capacity];
1048
1049        // COLLECTIONS-599: Calculate threshold before populating, otherwise it will be 0
1050        // when it hits AbstractHashedMap.checkCapacity() and so will unnecessarily
1051        // double up the size of the "data" array during population.
1052        //
1053        // NB: AbstractHashedMap.doReadObject() DOES calculate the threshold before populating.
1054        //
1055        threshold = calculateThreshold(data.length, loadFactor);
1056
1057        while (true) {
1058            final K key = (K) in.readObject();
1059            if (key == null) {
1060                break;
1061            }
1062            final V value = (V) in.readObject();
1063            put(key, value);
1064        }
1065        // do not call super.doReadObject() as code there doesn't work for reference map
1066    }
1067
1068    /**
1069     * Provided protected read-only access to the key type.
1070     * @param type the type to check against.
1071     * @return true if keyType has the specified type
1072     */
1073    protected boolean isKeyType(final ReferenceStrength type) {
1074        return this.keyType == type;
1075    }
1076}