    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}