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