    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 */
    017
    018/*
    019 * Copyright (c) 2008-2020, Hazelcast, Inc. All Rights Reserved.
    020 */
    021
    022package org.apache.commons.collections4.map;
    023
    024/*
    025 * Written by Doug Lea with assistance from members of JCP JSR-166
    026 * Expert Group and released to the public domain, as explained at
    027 * http://creativecommons.org/licenses/publicdomain
    028 */
    029
    030import java.lang.ref.Reference;
    031import java.lang.ref.ReferenceQueue;
    032import java.lang.ref.SoftReference;
    033import java.lang.ref.WeakReference;
    034import java.util.AbstractCollection;
    035import java.util.AbstractMap;
    036import java.util.AbstractSet;
    037import java.util.Arrays;
    038import java.util.Collection;
    039import java.util.ConcurrentModificationException;
    040import java.util.EnumSet;
    041import java.util.Enumeration;
    042import java.util.HashMap;
    043import java.util.Hashtable;
    044import java.util.IdentityHashMap;
    045import java.util.Iterator;
    046import java.util.Map;
    047import java.util.NoSuchElementException;
    048import java.util.Objects;
    049import java.util.Set;
    050import java.util.concurrent.ConcurrentMap;
    051import java.util.concurrent.locks.ReentrantLock;
    052import java.util.function.BiFunction;
    053import java.util.function.Function;
    054import java.util.function.Supplier;
    055
    056/**
    057 * An advanced hash map supporting configurable garbage collection semantics of keys and values, optional referential-equality, full concurrency of retrievals,
    058 * and adjustable expected concurrency for updates.
    059 * <p>
    060 * This map is designed around specific advanced use-cases. If there is any doubt whether this map is for you, you most likely should be using
    061 * {@link java.util.concurrent.ConcurrentHashMap} instead.
    062 * </p>
    063 * <p>
    064 * This map supports strong, weak, and soft keys and values. By default, keys are weak, and values are strong. Such a configuration offers similar behavior to
    065 * {@link java.util.WeakHashMap}, entries of this map are periodically removed once their corresponding keys are no longer referenced outside of this map. In
    066 * other words, this map will not prevent a key from being discarded by the garbage collector. Once a key has been discarded by the collector, the corresponding
    067 * entry is no longer visible to this map; however, the entry may occupy space until a future map operation decides to reclaim it. For this reason, summary
    068 * functions such as {@code size} and {@code isEmpty} might return a value greater than the observed number of entries. In order to support a high level of
    069 * concurrency, stale entries are only reclaimed during blocking (usually mutating) operations.
    070 * </p>
    071 * <p>
    072 * Enabling soft keys allows entries in this map to remain until their space is absolutely needed by the garbage collector. This is unlike weak keys which can
    073 * be reclaimed as soon as they are no longer referenced by a normal strong reference. The primary use case for soft keys is a cache, which ideally occupies
    074 * memory that is not in use for as long as possible.
    075 * </p>
    076 * <p>
    077 * By default, values are held using a normal strong reference. This provides the commonly desired guarantee that a value will always have at least the same
    078 * life-span as its key. For this reason, care should be taken to ensure that a value never refers, either directly or indirectly, to its key, thereby
    079 * preventing reclamation. If this is unavoidable, then it is recommended to use the same reference type in use for the key. However, it should be noted that
    080 * non-strong values may disappear before their corresponding key.
    081 * </p>
    082 * <p>
    083 * While this map does allow the use of both strong keys and values, it is recommended you use {@link java.util.concurrent.ConcurrentHashMap} for such a
    084 * configuration, since it is optimized for that case.
    085 * </p>
    086 * <p>
    087 * Just like {@link java.util.concurrent.ConcurrentHashMap}, this class obeys the same functional specification as {@link Hashtable}, and includes versions of
    088 * methods corresponding to each method of {@code Hashtable}. However, even though all operations are thread-safe, retrieval operations do <em>not</em> entail
    089 * locking, and there is <em>not</em> any support for locking the entire map in a way that prevents all access. This class is fully interoperable with
    090 * {@code Hashtable} in programs that rely on its thread safety but not on its synchronization details.
    091 * </p>
    092 * <p>
    093 * Retrieval operations (including {@code get}) generally do not block, so they may overlap with update operations (including {@code put} and {@code remove}).
    094 * Retrievals reflect the results of the most recently <em>completed</em> update operations holding upon their onset. For aggregate operations such as
    095 * {@code putAll} and {@code clear}, concurrent retrievals may reflect insertion or removal of only some entries. Similarly, Iterators and Enumerations return
    096 * elements reflecting the state of the hash map at some point at or since the creation of the iterator/enumeration. They do <em>not</em> throw
    097 * {@link ConcurrentModificationException}. However, iterators are designed to be used by only one thread at a time.
    098 * </p>
    099 * <p>
    100 * The allowed concurrency among update operations is guided by the optional {@code concurrencyLevel} constructor argument (default
    101 * {@value #DEFAULT_CONCURRENCY_LEVEL}), which is used as a hint for internal sizing. The map is internally partitioned to try to permit the indicated number of
    102 * concurrent updates without contention. Because placement in hash tables is essentially random, the actual concurrency will vary. Ideally, you should choose a
    103 * value to accommodate as many threads as will ever concurrently modify the map. Using a significantly higher value than you need can waste space and time, and
    104 * a significantly lower value can lead to thread contention. But overestimates and underestimates within an order of magnitude do not usually have much
    105 * noticeable impact. A value of one is appropriate when it is known that only one thread will modify and all others will only read. Also, resizing this or any
    106 * other kind of hash map is a relatively slow operation, so, when possible, it is a good idea that you provide estimates of expected map sizes in constructors.
    107 * </p>
    108 * <p>
    109 * This class and its views and iterators implement all of the <em>optional</em> methods of the {@link Map} and {@link Iterator} interfaces.
    110 * </p>
    111 * <p>
    112 * Like {@link Hashtable} but unlike {@link HashMap}, this class does <em>not</em> allow {@code null} to be used as a key or value.
    113 * </p>
    114 * <p>
    115 * Provenance: Copied and edited from Apache Groovy git master at commit 77dc80a7512ceb2168b1bc866c3d0c69b002fe11; via Doug Lea, Jason T. Greene, with
    116 * assistance from members of JCP JSR-166, and Hazelcast.
    117 * </p>
    118 *
    119 * @param <K> the type of keys maintained by this map.
    120 * @param <V> the type of mapped values.
    121 */
    122public class ConcurrentReferenceHashMap<K, V> extends AbstractMap<K, V> implements ConcurrentMap<K, V> {
    123
    124    /**
    125     * Builds new ConcurrentReferenceHashMap instances.
    126     * <p>
    127     * By default, keys are weak, and values are strong.
    128     * </p>
    129     * <p>
    130     * The default values are:
    131     * </p>
    132     * <ul>
    133     * <li>concurrency level: {@value #DEFAULT_CONCURRENCY_LEVEL}</li>
    134     * <li>initial capacity: {@value #DEFAULT_INITIAL_CAPACITY}</li>
    135     * <li>key reference type: {@link ReferenceType#WEAK}</li>
    136     * <li>load factor: {@value #DEFAULT_LOAD_FACTOR}</li>
    137     * <li>options: {@code null}</li>
    138     * <li>source map: {@code null}</li>
    139     * <li>value reference type: {@link ReferenceType#STRONG}</li>
    140     * </ul>
    141     *
    142     * @param <K> the type of keys.
    143     * @param <V> the type of values.
    144     */
    145    public static class Builder<K, V> implements Supplier<ConcurrentReferenceHashMap<K, V>> {
    146
    147        private static final Map<?, ?> DEFAULT_SOURCE_MAP = null;
    148
    149        private int initialCapacity = DEFAULT_INITIAL_CAPACITY;
    150        private float loadFactor = DEFAULT_LOAD_FACTOR;
    151        private int concurrencyLevel = DEFAULT_CONCURRENCY_LEVEL;
    152        private ReferenceType keyReferenceType = DEFAULT_KEY_TYPE;
    153        private ReferenceType valueReferenceType = DEFAULT_VALUE_TYPE;
    154        private EnumSet<Option> options = DEFAULT_OPTIONS;
    155        @SuppressWarnings("unchecked")
    156        private Map<? extends K, ? extends V> sourceMap = (Map<? extends K, ? extends V>) DEFAULT_SOURCE_MAP;
    157
    158        /**
    159         * Builds a new {@link ConcurrentReferenceHashMap}.
    160         * <p>
    161         * By default, keys are weak, and values are strong.
    162         * </p>
    163         * <p>
    164         * The default values are:
    165         * </p>
    166         * <ul>
    167         * <li>concurrency level: {@value #DEFAULT_CONCURRENCY_LEVEL}</li>
    168         * <li>initial capacity: {@value #DEFAULT_INITIAL_CAPACITY}</li>
    169         * <li>key reference type: {@link ReferenceType#WEAK}</li>
    170         * <li>load factor: {@value #DEFAULT_LOAD_FACTOR}</li>
    171         * <li>options: {@code null}</li>
    172         * <li>source map: {@code null}</li>
    173         * <li>value reference type: {@link ReferenceType#STRONG}</li>
    174         * </ul>
    175         */
    176        @Override
    177        public ConcurrentReferenceHashMap<K, V> get() {
    178            final ConcurrentReferenceHashMap<K, V> map = new ConcurrentReferenceHashMap<>(initialCapacity, loadFactor, concurrencyLevel, keyReferenceType,
    179                    valueReferenceType, options);
    180            if (sourceMap != null) {
    181                map.putAll(sourceMap);
    182            }
    183            return map;
    184        }
    185
    186        /**
    187         * Sets the estimated number of concurrently updating threads. The implementation performs internal sizing to try to accommodate this many threads.
    188         *
    189         * @param concurrencyLevel estimated number of concurrently updating threads
    190         * @return this instance.
    191         */
    192        public Builder<K, V> setConcurrencyLevel(final int concurrencyLevel) {
    193            this.concurrencyLevel = concurrencyLevel;
    194            return this;
    195        }
    196
    197        /**
    198         * Sets the initial capacity. The implementation performs internal sizing to accommodate this many elements.
    199         *
    200         * @param initialCapacity the initial capacity.
    201         * @return this instance.
    202         */
    203        public Builder<K, V> setInitialCapacity(final int initialCapacity) {
    204            this.initialCapacity = initialCapacity;
    205            return this;
    206        }
    207
    208        /**
    209         * Sets the reference type to use for keys.
    210         *
    211         * @param keyReferenceType the reference type to use for keys.
    212         * @return this instance.
    213         */
    214        public Builder<K, V> setKeyReferenceType(final ReferenceType keyReferenceType) {
    215            this.keyReferenceType = keyReferenceType;
    216            return this;
    217        }
    218
    219        /**
    220         * Sets the load factor factor, used to control resizing. Resizing may be performed when the average number of elements per bin exceeds this threshold.
    221         *
    222         * @param loadFactor the load factor factor, used to control resizing
    223         * @return this instance.
    224         */
    225        public Builder<K, V> setLoadFactor(final float loadFactor) {
    226            this.loadFactor = loadFactor;
    227            return this;
    228        }
    229
    230        /**
    231         * Sets the behavioral options.
    232         *
    233         * @param options the behavioral options.
    234         * @return this instance.
    235         */
    236        public Builder<K, V> setOptions(final EnumSet<Option> options) {
    237            this.options = options;
    238            return this;
    239        }
    240
    241        /**
    242         * Sets the values to load into a new map.
    243         *
    244         * @param sourceMap the values to load into a new map.
    245         * @return this instance.
    246         */
    247        public Builder<K, V> setSourceMap(final Map<? extends K, ? extends V> sourceMap) {
    248            this.sourceMap = sourceMap;
    249            return this;
    250        }
    251
    252        /**
    253         * Sets the reference type to use for values.
    254         *
    255         * @param valueReferenceType the reference type to use for values.
    256         * @return this instance.
    257         */
    258        public Builder<K, V> setValueReferenceType(final ReferenceType valueReferenceType) {
    259            this.valueReferenceType = valueReferenceType;
    260            return this;
    261        }
    262
    263        /**
    264         * Sets key reference type to {@link ReferenceType#SOFT}.
    265         *
    266         * @return this instance.
    267         */
    268        public Builder<K, V> softKeys() {
    269            setKeyReferenceType(ReferenceType.SOFT);
    270            return this;
    271        }
    272
    273        /**
    274         * Sets value reference type to {@link ReferenceType#SOFT}.
    275         *
    276         * @return this instance.
    277         */
    278        public Builder<K, V> softValues() {
    279            setValueReferenceType(ReferenceType.SOFT);
    280            return this;
    281        }
    282
    283        /**
    284         * Sets key reference type to {@link ReferenceType#STRONG}.
    285         *
    286         * @return this instance.
    287         */
    288        public Builder<K, V> strongKeys() {
    289            setKeyReferenceType(ReferenceType.STRONG);
    290            return this;
    291        }
    292
    293        /**
    294         * Sets value reference type to {@link ReferenceType#STRONG}.
    295         *
    296         * @return this instance.
    297         */
    298        public Builder<K, V> strongValues() {
    299            setValueReferenceType(ReferenceType.STRONG);
    300            return this;
    301        }
    302
    303        /**
    304         * Sets key reference type to {@link ReferenceType#WEAK}.
    305         *
    306         * @return this instance.
    307         */
    308        public Builder<K, V> weakKeys() {
    309            setKeyReferenceType(ReferenceType.WEAK);
    310            return this;
    311        }
    312
    313        /**
    314         * Sets value reference type to {@link ReferenceType#WEAK}.
    315         *
    316         * @return this instance.
    317         */
    318        public Builder<K, V> weakValues() {
    319            setValueReferenceType(ReferenceType.WEAK);
    320            return this;
    321        }
    322
    323    }
    324
    325    /**
    326     * The basic strategy is to subdivide the table among Segments, each of which itself is a concurrently readable hash table.
    327     */
    328    private final class CachedEntryIterator extends HashIterator implements Iterator<Entry<K, V>> {
    329        private final InitializableEntry<K, V> entry = new InitializableEntry<>();
    330
    331        @Override
    332        public Entry<K, V> next() {
    333            final HashEntry<K, V> e = super.nextEntry();
    334            return entry.init(e.key(), e.value());
    335        }
    336    }
    337
    338    private final class EntryIterator extends HashIterator implements Iterator<Entry<K, V>> {
    339        @Override
    340        public Entry<K, V> next() {
    341            final HashEntry<K, V> e = super.nextEntry();
    342            return new WriteThroughEntry(e.key(), e.value());
    343        }
    344    }
    345
    346    private final class EntrySet extends AbstractSet<Entry<K, V>> {
    347
    348        private final boolean cached;
    349
    350        private EntrySet(final boolean cached) {
    351            this.cached = cached;
    352        }
    353
    354        @Override
    355        public void clear() {
    356            ConcurrentReferenceHashMap.this.clear();
    357        }
    358
    359        @Override
    360        public boolean contains(final Object o) {
    361            if (!(o instanceof Map.Entry)) {
    362                return false;
    363            }
    364            final V v = ConcurrentReferenceHashMap.this.get(((Entry<?, ?>) o).getKey());
    365            return Objects.equals(v, ((Entry<?, ?>) o).getValue());
    366        }
    367
    368        @Override
    369        public boolean isEmpty() {
    370            return ConcurrentReferenceHashMap.this.isEmpty();
    371        }
    372
    373        @Override
    374        public Iterator<Entry<K, V>> iterator() {
    375            return cached ? new CachedEntryIterator() : new EntryIterator();
    376        }
    377
    378        @Override
    379        public boolean remove(final Object o) {
    380            if (!(o instanceof Map.Entry)) {
    381                return false;
    382            }
    383            final Entry<?, ?> e = (Entry<?, ?>) o;
    384            return ConcurrentReferenceHashMap.this.remove(e.getKey(), e.getValue());
    385        }
    386
    387        @Override
    388        public int size() {
    389            return ConcurrentReferenceHashMap.this.size();
    390        }
    391    }
    392
    393    /**
    394     * ConcurrentReferenceHashMap list entry. Note that this is never exported out as a user-visible Map.Entry.
    395     * <p>
    396     * Because the value field is volatile, not final, it is legal wrt the Java Memory Model for an unsynchronized reader to see null instead of initial value
    397     * when read via a data race. Although a reordering leading to this is not likely to ever actually occur, the Segment.readValueUnderLock method is used as a
    398     * backup in case a null (pre-initialized) value is ever seen in an unsynchronized access method.
    399     * </p>
    400     */
    401    private static final class HashEntry<K, V> {
    402
    403        @SuppressWarnings("unchecked")
    404        static <K, V> HashEntry<K, V>[] newArray(final int i) {
    405            return new HashEntry[i];
    406        }
    407
    408        private final Object keyRef;
    409        private final int hash;
    410        private volatile Object valueRef;
    411        private final HashEntry<K, V> next;
    412
    413        HashEntry(final K key, final int hash, final HashEntry<K, V> next, final V value, final ReferenceType keyType, final ReferenceType valueType,
    414                final ReferenceQueue<Object> refQueue) {
    415            this.hash = hash;
    416            this.next = next;
    417            this.keyRef = newKeyReference(key, keyType, refQueue);
    418            this.valueRef = newValueReference(value, valueType, refQueue);
    419        }
    420
    421        @SuppressWarnings("unchecked")
    422        V dereferenceValue(final Object value) {
    423            if (value instanceof KeyReference) {
    424                return ((Reference<V>) value).get();
    425            }
    426            return (V) value;
    427        }
    428
    429        @SuppressWarnings("unchecked")
    430        K key() {
    431            if (keyRef instanceof KeyReference) {
    432                return ((Reference<K>) keyRef).get();
    433            }
    434            return (K) keyRef;
    435        }
    436
    437        Object newKeyReference(final K key, final ReferenceType keyType, final ReferenceQueue<Object> refQueue) {
    438            if (keyType == ReferenceType.WEAK) {
    439                return new WeakKeyReference<>(key, hash, refQueue);
    440            }
    441            if (keyType == ReferenceType.SOFT) {
    442                return new SoftKeyReference<>(key, hash, refQueue);
    443            }
    444
    445            return key;
    446        }
    447
    448        Object newValueReference(final V value, final ReferenceType valueType, final ReferenceQueue<Object> refQueue) {
    449            if (valueType == ReferenceType.WEAK) {
    450                return new WeakValueReference<>(value, keyRef, hash, refQueue);
    451            }
    452            if (valueType == ReferenceType.SOFT) {
    453                return new SoftValueReference<>(value, keyRef, hash, refQueue);
    454            }
    455
    456            return value;
    457        }
    458
    459        void setValue(final V value, final ReferenceType valueType, final ReferenceQueue<Object> refQueue) {
    460            this.valueRef = newValueReference(value, valueType, refQueue);
    461        }
    462
    463        V value() {
    464            return dereferenceValue(valueRef);
    465        }
    466    }
    467
    468    private abstract class HashIterator {
    469        private int nextSegmentIndex;
    470        private int nextTableIndex;
    471        private HashEntry<K, V>[] currentTable;
    472        private HashEntry<K, V> nextEntry;
    473        private HashEntry<K, V> lastReturned;
    474        // Strong reference to weak key (prevents gc)
    475        private K currentKey;
    476
    477        private HashIterator() {
    478            nextSegmentIndex = segments.length - 1;
    479            nextTableIndex = -1;
    480            advance();
    481        }
    482
    483        final void advance() {
    484            if (nextEntry != null && (nextEntry = nextEntry.next) != null) {
    485                return;
    486            }
    487            while (nextTableIndex >= 0) {
    488                if ((nextEntry = currentTable[nextTableIndex--]) != null) {
    489                    return;
    490                }
    491            }
    492            while (nextSegmentIndex >= 0) {
    493                final Segment<K, V> seg = segments[nextSegmentIndex--];
    494                if (seg.count != 0) {
    495                    currentTable = seg.table;
    496                    for (int j = currentTable.length - 1; j >= 0; --j) {
    497                        if ((nextEntry = currentTable[j]) != null) {
    498                            nextTableIndex = j - 1;
    499                            return;
    500                        }
    501                    }
    502                }
    503            }
    504        }
    505
    506        public boolean hasMoreElements() {
    507            return hasNext();
    508        }
    509
    510        public boolean hasNext() {
    511            while (nextEntry != null) {
    512                if (nextEntry.key() != null) {
    513                    return true;
    514                }
    515                advance();
    516            }
    517            return false;
    518        }
    519
    520        HashEntry<K, V> nextEntry() {
    521            do {
    522                if (nextEntry == null) {
    523                    throw new NoSuchElementException();
    524                }
    525                lastReturned = nextEntry;
    526                currentKey = lastReturned.key();
    527                advance();
    528            } while /* Skip GC'd keys */ (currentKey == null);
    529            return lastReturned;
    530        }
    531
    532        public void remove() {
    533            if (lastReturned == null) {
    534                throw new IllegalStateException();
    535            }
    536            ConcurrentReferenceHashMap.this.remove(currentKey);
    537            lastReturned = null;
    538        }
    539    }
    540
    541    private static final class InitializableEntry<K, V> implements Entry<K, V> {
    542        private K key;
    543        private V value;
    544
    545        @Override
    546        public K getKey() {
    547            return key;
    548        }
    549
    550        @Override
    551        public V getValue() {
    552            return value;
    553        }
    554
    555        public Entry<K, V> init(final K key, final V value) {
    556            this.key = key;
    557            this.value = value;
    558            return this;
    559        }
    560
    561        @Override
    562        public V setValue(final V value) {
    563            throw new UnsupportedOperationException();
    564        }
    565    }
    566
    567    private final class KeyIterator extends HashIterator implements Iterator<K>, Enumeration<K> {
    568        @Override
    569        public K next() {
    570            return super.nextEntry().key();
    571        }
    572
    573        @Override
    574        public K nextElement() {
    575            return super.nextEntry().key();
    576        }
    577    }
    578
    579    private interface KeyReference {
    580        int keyHash();
    581
    582        Object keyRef();
    583    }
    584
    585    private final class KeySet extends AbstractSet<K> {
    586        @Override
    587        public void clear() {
    588            ConcurrentReferenceHashMap.this.clear();
    589        }
    590
    591        @Override
    592        public boolean contains(final Object o) {
    593            return ConcurrentReferenceHashMap.this.containsKey(o);
    594        }
    595
    596        @Override
    597        public boolean isEmpty() {
    598            return ConcurrentReferenceHashMap.this.isEmpty();
    599        }
    600
    601        @Override
    602        public Iterator<K> iterator() {
    603            return new KeyIterator();
    604        }
    605
    606        @Override
    607        public boolean remove(final Object o) {
    608            return ConcurrentReferenceHashMap.this.remove(o) != null;
    609        }
    610
    611        @Override
    612        public int size() {
    613            return ConcurrentReferenceHashMap.this.size();
    614        }
    615    }
    616
    617    /**
    618     * Behavior-changing configuration options for the map
    619     */
    620    public enum Option {
    621        /**
    622         * Indicates that referential-equality (== instead of .equals()) should be used when locating keys. This offers similar behavior to
    623         * {@link IdentityHashMap}
    624         */
    625        IDENTITY_COMPARISONS
    626    }
    627
    628    /**
    629     * An option specifying which Java reference type should be used to refer to a key and/or value.
    630     */
    631    public enum ReferenceType {
    632        /**
    633         * Indicates a normal Java strong reference should be used
    634         */
    635        STRONG,
    636        /**
    637         * Indicates a {@link WeakReference} should be used
    638         */
    639        WEAK,
    640        /**
    641         * Indicates a {@link SoftReference} should be used
    642         */
    643        SOFT
    644    }
    645
    646    /**
    647     * Segments are specialized versions of hash tables. This subclasses from ReentrantLock opportunistically, just to simplify some locking and avoid separate
    648     * construction.
    649     * <p>
    650     * Segments maintain a table of entry lists that are ALWAYS kept in a consistent state, so they can be read without locking. Next fields of nodes are
    651     * immutable (final). All list additions are performed at the front of each bin. This makes it easy to check changes, and also fast to traverse. When nodes
    652     * would otherwise be changed, new nodes are created to replace them. This works well for hash tables since the bin lists tend to be short. (The average
    653     * length is less than two for the default load factor threshold.)
    654     * </p>
    655     * <p>
    656     * Read operations can thus proceed without locking, but rely on selected uses of volatiles to ensure that completed write operations performed by other
    657     * threads are noticed. For most purposes, the "count" field, tracking the number of elements, serves as that volatile variable ensuring visibility. This is
    658     * convenient because this field needs to be read in many read operations anyway:
    659     * </p>
    660     * <ul>
    661     * <li>All (unsynchronized) read operations must first read the "count" field, and should not look at table entries if it is 0.</li>
    662     * <li>All (synchronized) write operations should write to the "count" field after structurally changing any bin. The operations must not take any action
    663     * that could even momentarily cause a concurrent read operation to see inconsistent data. This is made easier by the nature of the read operations in Map.
    664     * For example, no operation can reveal that the table has grown but the threshold has not yet been updated, so there are no atomicity requirements for this
    665     * with respect to reads.</li>
    666     * </ul>
    667     * <p>
    668     * As a guide, all critical volatile reads and writes to the count field are marked in code comments.
    669     * </p>
    670     *
    671     * @param <K> the type of keys maintained by this Segment.
    672     * @param <V> the type of mapped values.
    673     */
    674    private static final class Segment<K, V> extends ReentrantLock {
    675
    676        private static final long serialVersionUID = 1L;
    677
    678        @SuppressWarnings("unchecked")
    679        static <K, V> Segment<K, V>[] newArray(final int i) {
    680            return new Segment[i];
    681        }
    682
    683        /**
    684         * The number of elements in this segment's region.
    685         */
    686        // @SuppressFBWarnings(value = "SE_TRANSIENT_FIELD_NOT_RESTORED", justification =
    687        // "I trust Doug Lea's technical decision")
    688        private transient volatile int count;
    689
    690        /**
    691         * Number of updates that alter the size of the table. This is used during bulk-read methods to make sure they see a consistent snapshot: If modCounts
    692         * change during a traversal of segments computing size or checking containsValue, then we might have an inconsistent view of state so (usually) we must
    693         * retry.
    694         */
    695        // @SuppressFBWarnings(value = "SE_TRANSIENT_FIELD_NOT_RESTORED", justification =
    696        // "I trust Doug Lea's technical decision")
    697        private transient int modCount;
    698
    699        /**
    700         * The table is rehashed when its size exceeds this threshold. (The value of this field is always <code>(int)(capacity *
    701         * loadFactor)</code>.)
    702         */
    703        private transient int threshold;
    704
    705        /**
    706         * The per-segment table.
    707         */
    708        private transient volatile HashEntry<K, V>[] table;
    709
    710        /**
    711         * The load factor for the hash table. Even though this value is same for all segments, it is replicated to avoid needing links to outer object.
    712         */
    713        private final float loadFactor;
    714
    715        /**
    716         * The collected weak-key reference queue for this segment. This should be (re)initialized whenever table is assigned,
    717         */
    718        private transient volatile ReferenceQueue<Object> refQueue;
    719
    720        private final ReferenceType keyType;
    721
    722        private final ReferenceType valueType;
    723
    724        private final boolean identityComparisons;
    725
    726        Segment(final int initialCapacity, final float loadFactor, final ReferenceType keyType, final ReferenceType valueType,
    727                final boolean identityComparisons) {
    728            this.loadFactor = loadFactor;
    729            this.keyType = keyType;
    730            this.valueType = valueType;
    731            this.identityComparisons = identityComparisons;
    732            setTable(HashEntry.<K, V>newArray(initialCapacity));
    733        }
    734
    735        V apply(final K key, final int hash, final BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
    736            lock();
    737            try {
    738                final V oldValue = get(key, hash);
    739                final V newValue = remappingFunction.apply(key, oldValue);
    740
    741                if (newValue == null) {
    742                    // delete mapping
    743                    if (oldValue != null) {
    744                        // something to remove
    745                        removeInternal(key, hash, oldValue, false);
    746                    }
    747                    return null;
    748                }
    749                // add or replace old mapping
    750                putInternal(key, hash, newValue, null, false);
    751                return newValue;
    752            } finally {
    753                unlock();
    754            }
    755        }
    756
    757        V applyIfPresent(final K key, final int hash, final BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
    758            lock();
    759            try {
    760                final V oldValue = get(key, hash);
    761                if (oldValue == null) {
    762                    return null;
    763                }
    764
    765                final V newValue = remappingFunction.apply(key, oldValue);
    766
    767                if (newValue == null) {
    768                    removeInternal(key, hash, oldValue, false);
    769                    return null;
    770                }
    771                putInternal(key, hash, newValue, null, false);
    772                return newValue;
    773            } finally {
    774                unlock();
    775            }
    776        }
    777
    778        void clear() {
    779            if (count != 0) {
    780                lock();
    781                try {
    782                    final HashEntry<K, V>[] tab = table;
    783                    Arrays.fill(tab, null);
    784                    ++modCount;
    785                    // replace the reference queue to avoid unnecessary stale cleanups
    786                    refQueue = new ReferenceQueue<>();
    787                    // write-volatile
    788                    count = 0;
    789                } finally {
    790                    unlock();
    791                }
    792            }
    793        }
    794
    795        boolean containsKey(final Object key, final int hash) {
    796            // read-volatile
    797            if (count != 0) {
    798                HashEntry<K, V> e = getFirst(hash);
    799                while (e != null) {
    800                    if (e.hash == hash && keyEq(key, e.key())) {
    801                        return true;
    802                    }
    803                    e = e.next;
    804                }
    805            }
    806            return false;
    807        }
    808
    809        boolean containsValue(final Object value) {
    810            // read-volatile
    811            if (count != 0) {
    812                final HashEntry<K, V>[] tab = table;
    813                final int len = tab.length;
    814                for (int i = 0; i < len; i++) {
    815                    for (HashEntry<K, V> e = tab[i]; e != null; e = e.next) {
    816                        final Object opaque = e.valueRef;
    817                        V v;
    818                        if (opaque == null) {
    819                            // recheck
    820                            v = readValueUnderLock(e);
    821                        } else {
    822                            v = e.dereferenceValue(opaque);
    823                        }
    824                        if (Objects.equals(value, v)) {
    825                            return true;
    826                        }
    827                    }
    828                }
    829            }
    830            return false;
    831        }
    832
    833        /* Specialized implementations of map methods */
    834        V get(final Object key, final int hash) {
    835            // read-volatile
    836            if (count != 0) {
    837                HashEntry<K, V> e = getFirst(hash);
    838                while (e != null) {
    839                    if (e.hash == hash && keyEq(key, e.key())) {
    840                        final Object opaque = e.valueRef;
    841                        if (opaque != null) {
    842                            return e.dereferenceValue(opaque);
    843                        }
    844                        // recheck
    845                        return readValueUnderLock(e);
    846                    }
    847                    e = e.next;
    848                }
    849            }
    850            return null;
    851        }
    852
    853        /**
    854         * Gets properly casted first entry of bin for given hash.
    855         */
    856        HashEntry<K, V> getFirst(final int hash) {
    857            final HashEntry<K, V>[] tab = table;
    858            return tab[hash & tab.length - 1];
    859        }
    860
    861        V getValue(final K key, final V value, final Function<? super K, ? extends V> function) {
    862            return value != null ? value : function.apply(key);
    863        }
    864
    865        private boolean keyEq(final Object src, final Object dest) {
    866            return identityComparisons ? src == dest : Objects.equals(src, dest);
    867        }
    868
    869        HashEntry<K, V> newHashEntry(final K key, final int hash, final HashEntry<K, V> next, final V value) {
    870            return new HashEntry<>(key, hash, next, value, keyType, valueType, refQueue);
    871        }
    872
    873        /**
    874         * This method must be called with exactly one of <code>value</code> and <code>function</code> non-null.
    875         **/
    876        V put(final K key, final int hash, final V value, final Function<? super K, ? extends V> function, final boolean onlyIfAbsent) {
    877            lock();
    878            try {
    879                return putInternal(key, hash, value, function, onlyIfAbsent);
    880            } finally {
    881                unlock();
    882            }
    883        }
    884
    885        private V putInternal(final K key, final int hash, final V value, final Function<? super K, ? extends V> function, final boolean onlyIfAbsent) {
    886            removeStale();
    887            int c = count;
    888            // ensure capacity
    889            if (c++ > threshold) {
    890                final int reduced = rehash();
    891                // adjust from possible weak cleanups
    892                if (reduced > 0) {
    893                    // write-volatile
    894                    count = (c -= reduced) - 1;
    895                }
    896            }
    897            final HashEntry<K, V>[] tab = table;
    898            final int index = hash & tab.length - 1;
    899            final HashEntry<K, V> first = tab[index];
    900            HashEntry<K, V> e = first;
    901            while (e != null && (e.hash != hash || !keyEq(key, e.key()))) {
    902                e = e.next;
    903            }
    904            V resultValue;
    905            if (e != null) {
    906                resultValue = e.value();
    907                if (!onlyIfAbsent) {
    908                    e.setValue(getValue(key, value, function), valueType, refQueue);
    909                }
    910            } else {
    911                final V v = getValue(key, value, function);
    912                resultValue = function != null ? v : null;
    913
    914                if (v != null) {
    915                    ++modCount;
    916                    tab[index] = newHashEntry(key, hash, first, v);
    917                    // write-volatile
    918                    count = c;
    919                }
    920            }
    921            return resultValue;
    922        }
    923
    924        /**
    925         * Reads value field of an entry under lock. Called if value field ever appears to be null. This is possible only if a compiler happens to reorder a
    926         * HashEntry initialization with its table assignment, which is legal under memory model but is not known to ever occur.
    927         */
    928        V readValueUnderLock(final HashEntry<K, V> e) {
    929            lock();
    930            try {
    931                removeStale();
    932                return e.value();
    933            } finally {
    934                unlock();
    935            }
    936        }
    937
    938        int rehash() {
    939            final HashEntry<K, V>[] oldTable = table;
    940            final int oldCapacity = oldTable.length;
    941            if (oldCapacity >= MAXIMUM_CAPACITY) {
    942                return 0;
    943            }
    944            //
    945            // Reclassify nodes in each list to new Map. Because we are using power-of-two expansion, the elements from each bin must either stay at the same
    946            // index, or move with a power of two offset. We eliminate unnecessary node creation by catching cases where old nodes can be reused because their
    947            // next fields won't change. Statistically, at the default threshold, only about one-sixth of them need cloning when a table doubles. The nodes they
    948            // replace will be garbage collectable as soon as they are no longer referenced by any reader thread that may be in the midst of traversing table
    949            // right now.
    950            //
    951            final HashEntry<K, V>[] newTable = HashEntry.newArray(oldCapacity << 1);
    952            threshold = (int) (newTable.length * loadFactor);
    953            final int sizeMask = newTable.length - 1;
    954            int reduce = 0;
    955            for (int i = 0; i < oldCapacity; i++) {
    956                // We need to guarantee that any existing reads of old Map can
    957                // proceed. So we cannot yet null out each bin.
    958                final HashEntry<K, V> e = oldTable[i];
    959                if (e != null) {
    960                    final HashEntry<K, V> next = e.next;
    961                    final int idx = e.hash & sizeMask;
    962                    // Single node on list
    963                    if (next == null) {
    964                        newTable[idx] = e;
    965                    } else {
    966                        // Reuse trailing consecutive sequence at same slot
    967                        HashEntry<K, V> lastRun = e;
    968                        int lastIdx = idx;
    969                        for (HashEntry<K, V> last = next; last != null; last = last.next) {
    970                            final int k = last.hash & sizeMask;
    971                            if (k != lastIdx) {
    972                                lastIdx = k;
    973                                lastRun = last;
    974                            }
    975                        }
    976                        newTable[lastIdx] = lastRun;
    977                        // Clone all remaining nodes
    978                        for (HashEntry<K, V> p = e; p != lastRun; p = p.next) {
    979                            // Skip GC'd weak refs
    980                            final K key = p.key();
    981                            if (key == null) {
    982                                reduce++;
    983                                continue;
    984                            }
    985                            final int k = p.hash & sizeMask;
    986                            final HashEntry<K, V> n = newTable[k];
    987                            newTable[k] = newHashEntry(key, p.hash, n, p.value());
    988                        }
    989                    }
    990                }
    991            }
    992            table = newTable;
    993            return reduce;
    994        }
    995
    996        /**
    997         * Removes match on key only if value is null, else match both.
    998         */
    999        V remove(final Object key, final int hash, final Object value, final boolean refRemove) {
    1000            lock();
    1001            try {
    1002                return removeInternal(key, hash, value, refRemove);
    1003            } finally {
    1004                unlock();
    1005            }
    1006        }
    1007
    1008        private V removeInternal(final Object key, final int hash, final Object value, final boolean refRemove) {
    1009            if (!refRemove) {
    1010                removeStale();
    1011            }
    1012            int c = count - 1;
    1013            final HashEntry<K, V>[] tab = table;
    1014            final int index = hash & tab.length - 1;
    1015            final HashEntry<K, V> first = tab[index];
    1016            HashEntry<K, V> e = first;
    1017            // a ref remove operation compares the Reference instance
    1018            while (e != null && key != e.keyRef && (refRemove || hash != e.hash || !keyEq(key, e.key()))) {
    1019                e = e.next;
    1020            }
    1021
    1022            V oldValue = null;
    1023            if (e != null) {
    1024                final V v = e.value();
    1025                if (value == null || value.equals(v)) {
    1026                    oldValue = v;
    1027                    // All entries following removed node can stay
    1028                    // in list, but all preceding ones need to be
    1029                    // cloned.
    1030                    ++modCount;
    1031                    HashEntry<K, V> newFirst = e.next;
    1032                    for (HashEntry<K, V> p = first; p != e; p = p.next) {
    1033                        final K pKey = p.key();
    1034                        // Skip GC'd keys
    1035                        if (pKey == null) {
    1036                            c--;
    1037                            continue;
    1038                        }
    1039                        newFirst = newHashEntry(pKey, p.hash, newFirst, p.value());
    1040                    }
    1041                    tab[index] = newFirst;
    1042                    // write-volatile
    1043                    count = c;
    1044                }
    1045            }
    1046            return oldValue;
    1047        }
    1048
    1049        void removeStale() {
    1050            KeyReference ref;
    1051            while ((ref = (KeyReference) refQueue.poll()) != null) {
    1052                remove(ref.keyRef(), ref.keyHash(), null, true);
    1053            }
    1054        }
    1055
    1056        V replace(final K key, final int hash, final V newValue) {
    1057            lock();
    1058            try {
    1059                return replaceInternal(key, hash, newValue);
    1060            } finally {
    1061                unlock();
    1062            }
    1063        }
    1064
    1065        boolean replace(final K key, final int hash, final V oldValue, final V newValue) {
    1066            lock();
    1067            try {
    1068                return replaceInternal2(key, hash, oldValue, newValue);
    1069            } finally {
    1070                unlock();
    1071            }
    1072        }
    1073
    1074        private V replaceInternal(final K key, final int hash, final V newValue) {
    1075            removeStale();
    1076            HashEntry<K, V> e = getFirst(hash);
    1077            while (e != null && (e.hash != hash || !keyEq(key, e.key()))) {
    1078                e = e.next;
    1079            }
    1080            V oldValue = null;
    1081            if (e != null) {
    1082                oldValue = e.value();
    1083                e.setValue(newValue, valueType, refQueue);
    1084            }
    1085            return oldValue;
    1086        }
    1087
    1088        private boolean replaceInternal2(final K key, final int hash, final V oldValue, final V newValue) {
    1089            removeStale();
    1090            HashEntry<K, V> e = getFirst(hash);
    1091            while (e != null && (e.hash != hash || !keyEq(key, e.key()))) {
    1092                e = e.next;
    1093            }
    1094            boolean replaced = false;
    1095            if (e != null && Objects.equals(oldValue, e.value())) {
    1096                replaced = true;
    1097                e.setValue(newValue, valueType, refQueue);
    1098            }
    1099            return replaced;
    1100        }
    1101
    1102        /**
    1103         * Sets table to new HashEntry array. Call only while holding lock or in constructor.
    1104         */
    1105        void setTable(final HashEntry<K, V>[] newTable) {
    1106            threshold = (int) (newTable.length * loadFactor);
    1107            table = newTable;
    1108            refQueue = new ReferenceQueue<>();
    1109        }
    1110    }
    1111
    1112    private static class SimpleEntry<K, V> implements Entry<K, V> {
    1113
    1114        private static boolean eq(final Object o1, final Object o2) {
    1115            return Objects.equals(o1, o2);
    1116        }
    1117
    1118        private final K key;
    1119
    1120        private V value;
    1121
    1122        SimpleEntry(final K key, final V value) {
    1123            this.key = key;
    1124            this.value = value;
    1125        }
    1126
    1127        @Override
    1128        public boolean equals(final Object o) {
    1129            if (!(o instanceof Map.Entry)) {
    1130                return false;
    1131            }
    1132            final Entry<?, ?> e = (Entry<?, ?>) o;
    1133            return eq(key, e.getKey()) && eq(value, e.getValue());
    1134        }
    1135
    1136        @Override
    1137        public K getKey() {
    1138            return key;
    1139        }
    1140
    1141        @Override
    1142        public V getValue() {
    1143            return value;
    1144        }
    1145
    1146        @Override
    1147        public int hashCode() {
    1148            return (key == null ? 0 : key.hashCode()) ^ (value == null ? 0 : value.hashCode());
    1149        }
    1150
    1151        @Override
    1152        public V setValue(final V value) {
    1153            final V oldValue = this.value;
    1154            this.value = value;
    1155            return oldValue;
    1156        }
    1157
    1158        @Override
    1159        public String toString() {
    1160            return key + "=" + value;
    1161        }
    1162    }
    1163
    1164    /**
    1165     * A soft-key reference which stores the key hash needed for reclamation.
    1166     */
    1167    private static final class SoftKeyReference<K> extends SoftReference<K> implements KeyReference {
    1168
    1169        private final int hash;
    1170
    1171        SoftKeyReference(final K key, final int hash, final ReferenceQueue<Object> refQueue) {
    1172            super(key, refQueue);
    1173            this.hash = hash;
    1174        }
    1175
    1176        @Override
    1177        public int keyHash() {
    1178            return hash;
    1179        }
    1180
    1181        @Override
    1182        public Object keyRef() {
    1183            return this;
    1184        }
    1185    }
    1186
    1187    private static final class SoftValueReference<V> extends SoftReference<V> implements KeyReference {
    1188        private final Object keyRef;
    1189        private final int hash;
    1190
    1191        SoftValueReference(final V value, final Object keyRef, final int hash, final ReferenceQueue<Object> refQueue) {
    1192            super(value, refQueue);
    1193            this.keyRef = keyRef;
    1194            this.hash = hash;
    1195        }
    1196
    1197        @Override
    1198        public int keyHash() {
    1199            return hash;
    1200        }
    1201
    1202        @Override
    1203        public Object keyRef() {
    1204            return keyRef;
    1205        }
    1206    }
    1207
    1208    private final class ValueIterator extends HashIterator implements Iterator<V>, Enumeration<V> {
    1209        @Override
    1210        public V next() {
    1211            return super.nextEntry().value();
    1212        }
    1213
    1214        @Override
    1215        public V nextElement() {
    1216            return super.nextEntry().value();
    1217        }
    1218    }
    1219
    1220    private final class Values extends AbstractCollection<V> {
    1221        @Override
    1222        public void clear() {
    1223            ConcurrentReferenceHashMap.this.clear();
    1224        }
    1225
    1226        @Override
    1227        public boolean contains(final Object o) {
    1228            return ConcurrentReferenceHashMap.this.containsValue(o);
    1229        }
    1230
    1231        @Override
    1232        public boolean isEmpty() {
    1233            return ConcurrentReferenceHashMap.this.isEmpty();
    1234        }
    1235
    1236        @Override
    1237        public Iterator<V> iterator() {
    1238            return new ValueIterator();
    1239        }
    1240
    1241        @Override
    1242        public int size() {
    1243            return ConcurrentReferenceHashMap.this.size();
    1244        }
    1245    }
    1246
    1247    /**
    1248     * A weak-key reference which stores the key hash needed for reclamation.
    1249     */
    1250    private static final class WeakKeyReference<K> extends WeakReference<K> implements KeyReference {
    1251        private final int hash;
    1252
    1253        WeakKeyReference(final K key, final int hash, final ReferenceQueue<Object> refQueue) {
    1254            super(key, refQueue);
    1255            this.hash = hash;
    1256        }
    1257
    1258        @Override
    1259        public int keyHash() {
    1260            return hash;
    1261        }
    1262
    1263        @Override
    1264        public Object keyRef() {
    1265            return this;
    1266        }
    1267    }
    1268
    1269    private static final class WeakValueReference<V> extends WeakReference<V> implements KeyReference {
    1270        private final Object keyRef;
    1271        private final int hash;
    1272
    1273        WeakValueReference(final V value, final Object keyRef, final int hash, final ReferenceQueue<Object> refQueue) {
    1274            super(value, refQueue);
    1275            this.keyRef = keyRef;
    1276            this.hash = hash;
    1277        }
    1278
    1279        @Override
    1280        public int keyHash() {
    1281            return hash;
    1282        }
    1283
    1284        @Override
    1285        public Object keyRef() {
    1286            return keyRef;
    1287        }
    1288    }
    1289
    1290    /**
    1291     * Custom Entry class used by EntryIterator.next(), that relays setValue changes to the underlying map.
    1292     */
    1293    private final class WriteThroughEntry extends SimpleEntry<K, V> {
    1294
    1295        private WriteThroughEntry(final K k, final V v) {
    1296            super(k, v);
    1297        }
    1298
    1299        /**
    1300         * Set our entry's value and writes it through to the map. The value to return is somewhat arbitrary: since a WriteThroughEntry does not necessarily
    1301         * track asynchronous changes, the most recent "previous" value could be different from what we return (or could even have been removed in which case
    1302         * the put will re-establish). We do not and cannot guarantee more.
    1303         */
    1304        @Override
    1305        public V setValue(final V value) {
    1306            if (value == null) {
    1307                throw new NullPointerException();
    1308            }
    1309            final V v = super.setValue(value);
    1310            ConcurrentReferenceHashMap.this.put(getKey(), value);
    1311            return v;
    1312        }
    1313    }
    1314
    1315    static final ReferenceType DEFAULT_KEY_TYPE = ReferenceType.WEAK;
    1316
    1317    static final ReferenceType DEFAULT_VALUE_TYPE = ReferenceType.STRONG;
    1318
    1319    static final EnumSet<Option> DEFAULT_OPTIONS = null;
    1320
    1321    /**
    1322     * The default initial capacity for this table, used when not otherwise specified in a constructor.
    1323     */
    1324    static final int DEFAULT_INITIAL_CAPACITY = 16;
    1325
    1326    /**
    1327     * The default load factor for this table, used when not otherwise specified in a constructor.
    1328     */
    1329    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    1330
    1331    /**
    1332     * The default concurrency level for this table, used when not otherwise specified in a constructor.
    1333     */
    1334    static final int DEFAULT_CONCURRENCY_LEVEL = 16;
    1335
    1336    /**
    1337     * The maximum capacity, used if a higher value is implicitly specified by either of the constructors with arguments. MUST be a power of two &lt;=
    1338     * 1&lt;&lt;30 to ensure that entries are indexable using ints.
    1339     */
    1340    private static final int MAXIMUM_CAPACITY = 1 << 30;
    1341
    1342    /**
    1343     * The maximum number of segments to allow; used to bound constructor arguments.
    1344     */
    1345    private static final int MAX_SEGMENTS = 1 << 16;
    1346
    1347    /**
    1348     * Number of unsynchronized retries in size and containsValue methods before resorting to locking. This is used to avoid unbounded retries if tables undergo
    1349     * continuous modification which would make it impossible to obtain an accurate result.
    1350     */
    1351    private static final int RETRIES_BEFORE_LOCK = 2;
    1352
    1353    /**
    1354     * Creates a new Builder.
    1355     * <p>
    1356     * By default, keys are weak, and values are strong.
    1357     * </p>
    1358     * <p>
    1359     * The default values are:
    1360     * </p>
    1361     * <ul>
    1362     * <li>concurrency level: {@value #DEFAULT_CONCURRENCY_LEVEL}</li>
    1363     * <li>initial capacity: {@value #DEFAULT_INITIAL_CAPACITY}</li>
    1364     * <li>key reference type: {@link ReferenceType#WEAK}</li>
    1365     * <li>load factor: {@value #DEFAULT_LOAD_FACTOR}</li>
    1366     * <li>options: {@code null}</li>
    1367     * <li>source map: {@code null}</li>
    1368     * <li>value reference type: {@link ReferenceType#STRONG}</li>
    1369     * </ul>
    1370     *
    1371     * @param <K> the type of keys.
    1372     * @param <V> the type of values.
    1373     * @return a new Builder.
    1374     */
    1375    public static <K, V> Builder<K, V> builder() {
    1376        return new Builder<>();
    1377    }
    1378
    1379    /**
    1380     * Applies a supplemental hash function to a given hashCode, which defends against poor quality hash functions. This is critical because
    1381     * ConcurrentReferenceHashMap uses power-of-two length hash tables, that otherwise encounter collisions for hashCodes that do not differ in lower or upper
    1382     * bits.
    1383     */
    1384    private static int hash(int h) {
    1385        // Spread bits to regularize both segment and index locations,
    1386        // using variant of single-word Wang/Jenkins hash.
    1387        h += h << 15 ^ 0xffffcd7d;
    1388        h ^= h >>> 10;
    1389        h += h << 3;
    1390        h ^= h >>> 6;
    1391        h += (h << 2) + (h << 14);
    1392        return h ^ h >>> 16;
    1393    }
    1394
    1395    /**
    1396     * Mask value for indexing into segments. The upper bits of a key's hash code are used to choose the segment.
    1397     */
    1398    private final int segmentMask;
    1399
    1400    /**
    1401     * Shift value for indexing within segments.
    1402     */
    1403    private final int segmentShift;
    1404
    1405    /**
    1406     * The segments, each of which is a specialized hash table
    1407     */
    1408    private final Segment<K, V>[] segments;
    1409
    1410    private final boolean identityComparisons;
    1411
    1412    private transient Set<K> keySet;
    1413
    1414    private transient Set<Entry<K, V>> entrySet;
    1415
    1416    private transient Collection<V> values;
    1417
    1418    /**
    1419     * Creates a new, empty map with the specified initial capacity, reference types, load factor, and concurrency level.
    1420     * <p>
    1421     * Behavioral changing options such as {@link Option#IDENTITY_COMPARISONS} can also be specified.
    1422     * </p>
    1423     *
    1424     * @param initialCapacity  the initial capacity. The implementation performs internal sizing to accommodate this many elements.
    1425     * @param loadFactor       the load factor threshold, used to control resizing. Resizing may be performed when the average number of elements per bin
    1426     *                         exceeds this threshold.
    1427     * @param concurrencyLevel the estimated number of concurrently updating threads. The implementation performs internal sizing to try to accommodate this
    1428     *                         many threads.
    1429     * @param keyType          the reference type to use for keys.
    1430     * @param valueType        the reference type to use for values.
    1431     * @param options          the behavioral options.
    1432     * @throws IllegalArgumentException if the initial capacity is negative or the load factor or concurrencyLevel are nonpositive.
    1433     */
    1434    private ConcurrentReferenceHashMap(int initialCapacity, final float loadFactor, int concurrencyLevel, final ReferenceType keyType,
    1435            final ReferenceType valueType, final EnumSet<Option> options) {
    1436        if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0) {
    1437            throw new IllegalArgumentException();
    1438        }
    1439        if (concurrencyLevel > MAX_SEGMENTS) {
    1440            concurrencyLevel = MAX_SEGMENTS;
    1441        }
    1442        // Find power-of-two sizes best matching arguments
    1443        int sshift = 0;
    1444        int ssize = 1;
    1445        while (ssize < concurrencyLevel) {
    1446            ++sshift;
    1447            ssize <<= 1;
    1448        }
    1449        segmentShift = 32 - sshift;
    1450        segmentMask = ssize - 1;
    1451        this.segments = Segment.newArray(ssize);
    1452        if (initialCapacity > MAXIMUM_CAPACITY) {
    1453            initialCapacity = MAXIMUM_CAPACITY;
    1454        }
    1455        int c = initialCapacity / ssize;
    1456        if (c * ssize < initialCapacity) {
    1457            ++c;
    1458        }
    1459        int cap = 1;
    1460        while (cap < c) {
    1461            cap <<= 1;
    1462        }
    1463        identityComparisons = options != null && options.contains(Option.IDENTITY_COMPARISONS);
    1464        for (int i = 0; i < this.segments.length; ++i) {
    1465            this.segments[i] = new Segment<>(cap, loadFactor, keyType, valueType, identityComparisons);
    1466        }
    1467    }
    1468
    1469    /**
    1470     * Removes all of the mappings from this map.
    1471     */
    1472    @Override
    1473    public void clear() {
    1474        for (final Segment<K, V> segment : segments) {
    1475            segment.clear();
    1476        }
    1477    }
    1478
    1479    @Override
    1480    public V compute(final K key, final BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
    1481        Objects.requireNonNull(key);
    1482        Objects.requireNonNull(remappingFunction);
    1483
    1484        final int hash = hashOf(key);
    1485        final Segment<K, V> segment = segmentFor(hash);
    1486        return segment.apply(key, hash, remappingFunction);
    1487    }
    1488
    1489    /**
    1490     * The default implementation is equivalent to the following steps for this {@code map}, then returning the current value or {@code null} if now absent:
    1491     *
    1492     * <pre>{@code
    1493     * if (map.get(key) == null) {
    1494     *     V newValue = mappingFunction.apply(key);
    1495     *     if (newValue != null)
    1496     *         return map.putIfAbsent(key, newValue);
    1497     * }
    1498     * }</pre>
    1499     * <p>
    1500     * The default implementation may retry these steps when multiple threads attempt updates including potentially calling the mapping function multiple times.
    1501     * </p>
    1502     * <p>
    1503     * This implementation assumes that the ConcurrentMap cannot contain null values and {@code get()} returning null unambiguously means the key is absent.
    1504     * Implementations which support null values <strong>must</strong> override this default implementation.
    1505     * </p>
    1506     */
    1507    @Override
    1508    public V computeIfAbsent(final K key, final Function<? super K, ? extends V> mappingFunction) {
    1509        Objects.requireNonNull(key);
    1510        Objects.requireNonNull(mappingFunction);
    1511
    1512        final int hash = hashOf(key);
    1513        final Segment<K, V> segment = segmentFor(hash);
    1514        final V v = segment.get(key, hash);
    1515        return v == null ? segment.put(key, hash, null, mappingFunction, true) : v;
    1516    }
    1517
    1518    @Override
    1519    public V computeIfPresent(final K key, final BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
    1520        Objects.requireNonNull(key);
    1521        Objects.requireNonNull(remappingFunction);
    1522
    1523        final int hash = hashOf(key);
    1524        final Segment<K, V> segment = segmentFor(hash);
    1525        final V v = segment.get(key, hash);
    1526        if (v == null) {
    1527            return null;
    1528        }
    1529
    1530        return segmentFor(hash).applyIfPresent(key, hash, remappingFunction);
    1531    }
    1532
    1533    /**
    1534     * Tests if the specified object is a key in this table.
    1535     *
    1536     * @param key possible key
    1537     * @return {@code true} if and only if the specified object is a key in this table, as determined by the {@code equals} method; {@code false} otherwise.
    1538     * @throws NullPointerException if the specified key is null
    1539     */
    1540    @Override
    1541    public boolean containsKey(final Object key) {
    1542        final int hash = hashOf(key);
    1543        return segmentFor(hash).containsKey(key, hash);
    1544    }
    1545
    1546    /**
    1547     * Returns {@code true} if this map maps one or more keys to the specified value. Note: This method requires a full internal traversal of the hash table,
    1548     * therefore it is much slower than the method {@code containsKey}.
    1549     *
    1550     * @param value value whose presence in this map is to be tested
    1551     * @return {@code true} if this map maps one or more keys to the specified value
    1552     * @throws NullPointerException if the specified value is null
    1553     */
    1554    @Override
    1555    public boolean containsValue(final Object value) {
    1556        if (value == null) {
    1557            throw new NullPointerException();
    1558        }
    1559        // See explanation of modCount use above
    1560        final Segment<K, V>[] segments = this.segments;
    1561        final int[] mc = new int[segments.length];
    1562        // Try a few times without locking
    1563        for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) {
    1564            // final int sum = 0;
    1565            int mcsum = 0;
    1566            for (int i = 0; i < segments.length; ++i) {
    1567                // final int c = segments[i].count;
    1568                mcsum += mc[i] = segments[i].modCount;
    1569                if (segments[i].containsValue(value)) {
    1570                    return true;
    1571                }
    1572            }
    1573            boolean cleanSweep = true;
    1574            if (mcsum != 0) {
    1575                for (int i = 0; i < segments.length; ++i) {
    1576                    // final int c = segments[i].count;
    1577                    if (mc[i] != segments[i].modCount) {
    1578                        cleanSweep = false;
    1579                        break;
    1580                    }
    1581                }
    1582            }
    1583            if (cleanSweep) {
    1584                return false;
    1585            }
    1586        }
    1587        // Resort to locking all segments
    1588        for (final Segment<K, V> segment : segments) {
    1589            segment.lock();
    1590        }
    1591        boolean found = false;
    1592        try {
    1593            for (final Segment<K, V> segment : segments) {
    1594                if (segment.containsValue(value)) {
    1595                    found = true;
    1596                    break;
    1597                }
    1598            }
    1599        } finally {
    1600            for (final Segment<K, V> segment : segments) {
    1601                segment.unlock();
    1602            }
    1603        }
    1604        return found;
    1605    }
    1606
    1607    /**
    1608     * Returns a {@link Set} view of the mappings contained in this map. The set is backed by the map, so changes to the map are reflected in the set, and
    1609     * vice-versa. The set supports element removal, which removes the corresponding mapping from the map, via the {@code Iterator.remove}, {@code Set.remove},
    1610     * {@code removeAll}, {@code retainAll}, and {@code clear} operations. It does not support the {@code add} or {@code addAll} operations.
    1611     * <p>
    1612     * The view's {@code iterator} is a "weakly consistent" iterator that will never throw {@link ConcurrentModificationException}, and is guaranteed to
    1613     * traverse elements as they existed upon construction of the iterator, and may (but is not guaranteed to) reflect any modifications subsequent to
    1614     * construction.
    1615     * </p>
    1616     */
    1617    @Override
    1618    public Set<Entry<K, V>> entrySet() {
    1619        final Set<Entry<K, V>> es = entrySet;
    1620        return es != null ? es : (entrySet = new EntrySet(false));
    1621    }
    1622
    1623    /**
    1624     * Returns the value to which the specified key is mapped, or {@code null} if this map contains no mapping for the key.
    1625     * <p>
    1626     * If this map contains a mapping from a key {@code k} to a value {@code v} such that {@code key.equals(k)}, then this method returns {@code v}; otherwise
    1627     * it returns {@code null}. (There can be at most one such mapping.)
    1628     * </p>
    1629     *
    1630     * @throws NullPointerException if the specified key is null
    1631     */
    1632    @Override
    1633    public V get(final Object key) {
    1634        final int hash = hashOf(key);
    1635        return segmentFor(hash).get(key, hash);
    1636    }
    1637
    1638    private int hashOf(final Object key) {
    1639        return hash(identityComparisons ? System.identityHashCode(key) : key.hashCode());
    1640    }
    1641
    1642    /**
    1643     * Returns {@code true} if this map contains no key-value mappings.
    1644     *
    1645     * @return {@code true} if this map contains no key-value mappings
    1646     */
    1647    @Override
    1648    public boolean isEmpty() {
    1649        final Segment<K, V>[] segments = this.segments;
    1650        //
    1651        // We keep track of per-segment modCounts to avoid ABA problems in which an element in one segment was added and in another removed during traversal, in
    1652        // which case the table was never actually empty at any point. Note the similar use of modCounts in the size() and containsValue() methods, which are
    1653        // the only other methods also susceptible to ABA problems.
    1654        //
    1655        final int[] mc = new int[segments.length];
    1656        int mcsum = 0;
    1657        for (int i = 0; i < segments.length; ++i) {
    1658            if (segments[i].count != 0) {
    1659                return false;
    1660            }
    1661            mcsum += mc[i] = segments[i].modCount;
    1662        }
    1663        // If mcsum happens to be zero, then we know we got a snapshot
    1664        // before any modifications at all were made. This is
    1665        // probably common enough to bother tracking.
    1666        if (mcsum != 0) {
    1667            for (int i = 0; i < segments.length; ++i) {
    1668                if (segments[i].count != 0 || mc[i] != segments[i].modCount) {
    1669                    return false;
    1670                }
    1671            }
    1672        }
    1673        return true;
    1674    }
    1675
    1676    /**
    1677     * Returns a {@link Set} view of the keys contained in this map. The set is backed by the map, so changes to the map are reflected in the set, and
    1678     * vice-versa. The set supports element removal, which removes the corresponding mapping from this map, via the {@code Iterator.remove}, {@code Set.remove},
    1679     * {@code removeAll}, {@code retainAll}, and {@code clear} operations. It does not support the {@code add} or {@code addAll} operations.
    1680     * <p>
    1681     * The view's {@code iterator} is a "weakly consistent" iterator that will never throw {@link ConcurrentModificationException}, and guarantees to traverse
    1682     * elements as they existed upon construction of the iterator, and may (but is not guaranteed to) reflect any modifications subsequent to construction.
    1683     * </p>
    1684     */
    1685    @Override
    1686    public Set<K> keySet() {
    1687        final Set<K> ks = keySet;
    1688        return ks != null ? ks : (keySet = new KeySet());
    1689    }
    1690
    1691    /**
    1692     * Removes any stale entries whose keys have been finalized. Use of this method is normally not necessary since stale entries are automatically removed
    1693     * lazily, when blocking operations are required. However, there are some cases where this operation should be performed eagerly, such as cleaning up old
    1694     * references to a ClassLoader in a multi-classloader environment.
    1695     * <p>
    1696     * Note: this method will acquire locks one at a time across all segments of this table, so this method should be used sparingly.
    1697     * </p>
    1698     */
    1699    public void purgeStaleEntries() {
    1700        for (final Segment<K, V> segment : segments) {
    1701            segment.removeStale();
    1702        }
    1703    }
    1704
    1705    /**
    1706     * Maps the specified key to the specified value in this table. Neither the key nor the value can be null.
    1707     * <p>
    1708     * The value can be retrieved by calling the {@code get} method with a key that is equal to the original key.
    1709     * </p>
    1710     *
    1711     * @param key   key with which the specified value is to be associated
    1712     * @param value value to be associated with the specified key
    1713     * @return the previous value associated with {@code key}, or {@code null} if there was no mapping for {@code key}
    1714     * @throws NullPointerException if the specified key or value is null
    1715     */
    1716    @Override
    1717    public V put(final K key, final V value) {
    1718        if (key == null || value == null) {
    1719            throw new NullPointerException();
    1720        }
    1721        final int hash = hashOf(key);
    1722        return segmentFor(hash).put(key, hash, value, null, false);
    1723    }
    1724
    1725    /**
    1726     * Copies all of the mappings from the specified map to this one. These mappings replace any mappings that this map had for any of the keys currently in the
    1727     * specified map.
    1728     *
    1729     * @param m mappings to be stored in this map
    1730     */
    1731    @Override
    1732    public void putAll(final Map<? extends K, ? extends V> m) {
    1733        for (final Entry<? extends K, ? extends V> e : m.entrySet()) {
    1734            put(e.getKey(), e.getValue());
    1735        }
    1736    }
    1737
    1738    /**
    1739     * {@inheritDoc}
    1740     *
    1741     * @return the previous value associated with the specified key, or {@code null} if there was no mapping for the key
    1742     * @throws NullPointerException if the specified key or value is null
    1743     */
    1744    @Override
    1745    public V putIfAbsent(final K key, final V value) {
    1746        if (value == null) {
    1747            throw new NullPointerException();
    1748        }
    1749        final int hash = hashOf(key);
    1750        return segmentFor(hash).put(key, hash, value, null, true);
    1751    }
    1752
    1753    /**
    1754     * Removes the key (and its corresponding value) from this map. This method does nothing if the key is not in the map.
    1755     *
    1756     * @param key the key that needs to be removed
    1757     * @return the previous value associated with {@code key}, or {@code null} if there was no mapping for {@code key}
    1758     * @throws NullPointerException if the specified key is null
    1759     */
    1760    @Override
    1761    public V remove(final Object key) {
    1762        final int hash = hashOf(key);
    1763        return segmentFor(hash).remove(key, hash, null, false);
    1764    }
    1765
    1766    /**
    1767     * {@inheritDoc}
    1768     *
    1769     * @throws NullPointerException if the specified key is null
    1770     */
    1771    @Override
    1772    public boolean remove(final Object key, final Object value) {
    1773        final int hash = hashOf(key);
    1774        if (value == null) {
    1775            return false;
    1776        }
    1777        return segmentFor(hash).remove(key, hash, value, false) != null;
    1778    }
    1779
    1780    /**
    1781     * {@inheritDoc}
    1782     *
    1783     * @return the previous value associated with the specified key, or {@code null} if there was no mapping for the key
    1784     * @throws NullPointerException if the specified key or value is null
    1785     */
    1786    @Override
    1787    public V replace(final K key, final V value) {
    1788        if (value == null) {
    1789            throw new NullPointerException();
    1790        }
    1791        final int hash = hashOf(key);
    1792        return segmentFor(hash).replace(key, hash, value);
    1793    }
    1794
    1795    /**
    1796     * {@inheritDoc}
    1797     *
    1798     * @throws NullPointerException if any of the arguments are null
    1799     */
    1800    @Override
    1801    public boolean replace(final K key, final V oldValue, final V newValue) {
    1802        if (oldValue == null || newValue == null) {
    1803            throw new NullPointerException();
    1804        }
    1805        final int hash = hashOf(key);
    1806        return segmentFor(hash).replace(key, hash, oldValue, newValue);
    1807    }
    1808
    1809    /**
    1810     * Returns the segment that should be used for key with given hash
    1811     *
    1812     * @param hash the hash code for the key
    1813     * @return the segment
    1814     */
    1815    private Segment<K, V> segmentFor(final int hash) {
    1816        return segments[hash >>> segmentShift & segmentMask];
    1817    }
    1818
    1819    /**
    1820     * Returns the number of key-value mappings in this map. If the map contains more than {@code Integer.MAX_VALUE} elements, returns
    1821     * {@code Integer.MAX_VALUE}.
    1822     *
    1823     * @return the number of key-value mappings in this map
    1824     */
    1825    @Override
    1826    public int size() {
    1827        final Segment<K, V>[] segments = this.segments;
    1828        long sum = 0;
    1829        long check = 0;
    1830        final int[] mc = new int[segments.length];
    1831        // Try a few times to get accurate count. On failure due to
    1832        // continuous async changes in table, resort to locking.
    1833        for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) {
    1834            check = 0;
    1835            sum = 0;
    1836            int mcsum = 0;
    1837            for (int i = 0; i < segments.length; ++i) {
    1838                sum += segments[i].count;
    1839                mcsum += mc[i] = segments[i].modCount;
    1840            }
    1841            if (mcsum != 0) {
    1842                for (int i = 0; i < segments.length; ++i) {
    1843                    check += segments[i].count;
    1844                    if (mc[i] != segments[i].modCount) {
    1845                        // force retry
    1846                        check = -1;
    1847                        break;
    1848                    }
    1849                }
    1850            }
    1851            if (check == sum) {
    1852                break;
    1853            }
    1854        }
    1855        if (check != sum) {
    1856            // Resort to locking all segments
    1857            sum = 0;
    1858            for (final Segment<K, V> segment : segments) {
    1859                segment.lock();
    1860            }
    1861            for (final Segment<K, V> segment : segments) {
    1862                sum += segment.count;
    1863            }
    1864            for (final Segment<K, V> segment : segments) {
    1865                segment.unlock();
    1866            }
    1867        }
    1868        return sum > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int) sum;
    1869    }
    1870
    1871    /**
    1872     * Returns a {@link Collection} view of the values contained in this map. The collection is backed by the map, so changes to the map are reflected in the
    1873     * collection, and vice-versa. The collection supports element removal, which removes the corresponding mapping from this map, via the
    1874     * {@code Iterator.remove}, {@code Collection.remove}, {@code removeAll}, {@code retainAll}, and {@code clear} operations. It does not support the
    1875     * {@code add} or {@code addAll} operations.
    1876     * <p>
    1877     * The view's {@code iterator} is a "weakly consistent" iterator that will never throw {@link ConcurrentModificationException}, and guarantees to traverse
    1878     * elements as they existed upon construction of the iterator, and may (but is not guaranteed to) reflect any modifications subsequent to construction.
    1879     * </p>
    1880     */
    1881    @Override
    1882    public Collection<V> values() {
    1883        final Collection<V> vs = values;
    1884        return vs != null ? vs : (values = new Values());
    1885    }
    1886
    1887}