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}