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