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 <= 1343 * 1<<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}