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