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