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