001/* 002 * Copyright 2002-2020 the original author or authors. 003 * 004 * Licensed under the Apache License, Version 2.0 (the "License"); 005 * you may not use this file except in compliance with the License. 006 * You may obtain a copy of the License at 007 * 008 * https://www.apache.org/licenses/LICENSE-2.0 009 * 010 * Unless required by applicable law or agreed to in writing, software 011 * distributed under the License is distributed on an "AS IS" BASIS, 012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 013 * See the License for the specific language governing permissions and 014 * limitations under the License. 015 */ 016 017package org.springframework.util; 018 019import java.lang.ref.ReferenceQueue; 020import java.lang.ref.SoftReference; 021import java.lang.ref.WeakReference; 022import java.lang.reflect.Array; 023import java.util.AbstractMap; 024import java.util.AbstractSet; 025import java.util.Collections; 026import java.util.EnumSet; 027import java.util.HashSet; 028import java.util.Iterator; 029import java.util.Map; 030import java.util.NoSuchElementException; 031import java.util.Set; 032import java.util.concurrent.ConcurrentHashMap; 033import java.util.concurrent.ConcurrentMap; 034import java.util.concurrent.atomic.AtomicInteger; 035import java.util.concurrent.locks.ReentrantLock; 036 037import org.springframework.lang.Nullable; 038 039/** 040 * A {@link ConcurrentHashMap} that uses {@link ReferenceType#SOFT soft} or 041 * {@linkplain ReferenceType#WEAK weak} references for both {@code keys} and {@code values}. 042 * 043 * <p>This class can be used as an alternative to 044 * {@code Collections.synchronizedMap(new WeakHashMap<K, Reference<V>>())} in order to 045 * support better performance when accessed concurrently. This implementation follows the 046 * same design constraints as {@link ConcurrentHashMap} with the exception that 047 * {@code null} values and {@code null} keys are supported. 048 * 049 * <p><b>NOTE:</b> The use of references means that there is no guarantee that items 050 * placed into the map will be subsequently available. The garbage collector may discard 051 * references at any time, so it may appear that an unknown thread is silently removing 052 * entries. 053 * 054 * <p>If not explicitly specified, this implementation will use 055 * {@linkplain SoftReference soft entry references}. 056 * 057 * @author Phillip Webb 058 * @author Juergen Hoeller 059 * @since 3.2 060 * @param <K> the key type 061 * @param <V> the value type 062 */ 063public class ConcurrentReferenceHashMap<K, V> extends AbstractMap<K, V> implements ConcurrentMap<K, V> { 064 065 private static final int DEFAULT_INITIAL_CAPACITY = 16; 066 067 private static final float DEFAULT_LOAD_FACTOR = 0.75f; 068 069 private static final int DEFAULT_CONCURRENCY_LEVEL = 16; 070 071 private static final ReferenceType DEFAULT_REFERENCE_TYPE = ReferenceType.SOFT; 072 073 private static final int MAXIMUM_CONCURRENCY_LEVEL = 1 << 16; 074 075 private static final int MAXIMUM_SEGMENT_SIZE = 1 << 30; 076 077 078 /** 079 * Array of segments indexed using the high order bits from the hash. 080 */ 081 private final Segment[] segments; 082 083 /** 084 * When the average number of references per table exceeds this value resize will be attempted. 085 */ 086 private final float loadFactor; 087 088 /** 089 * The reference type: SOFT or WEAK. 090 */ 091 private final ReferenceType referenceType; 092 093 /** 094 * The shift value used to calculate the size of the segments array and an index from the hash. 095 */ 096 private final int shift; 097 098 /** 099 * Late binding entry set. 100 */ 101 @Nullable 102 private volatile Set<Map.Entry<K, V>> entrySet; 103 104 105 /** 106 * Create a new {@code ConcurrentReferenceHashMap} instance. 107 */ 108 public ConcurrentReferenceHashMap() { 109 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL, DEFAULT_REFERENCE_TYPE); 110 } 111 112 /** 113 * Create a new {@code ConcurrentReferenceHashMap} instance. 114 * @param initialCapacity the initial capacity of the map 115 */ 116 public ConcurrentReferenceHashMap(int initialCapacity) { 117 this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL, DEFAULT_REFERENCE_TYPE); 118 } 119 120 /** 121 * Create a new {@code ConcurrentReferenceHashMap} instance. 122 * @param initialCapacity the initial capacity of the map 123 * @param loadFactor the load factor. When the average number of references per table 124 * exceeds this value resize will be attempted 125 */ 126 public ConcurrentReferenceHashMap(int initialCapacity, float loadFactor) { 127 this(initialCapacity, loadFactor, DEFAULT_CONCURRENCY_LEVEL, DEFAULT_REFERENCE_TYPE); 128 } 129 130 /** 131 * Create a new {@code ConcurrentReferenceHashMap} instance. 132 * @param initialCapacity the initial capacity of the map 133 * @param concurrencyLevel the expected number of threads that will concurrently 134 * write to the map 135 */ 136 public ConcurrentReferenceHashMap(int initialCapacity, int concurrencyLevel) { 137 this(initialCapacity, DEFAULT_LOAD_FACTOR, concurrencyLevel, DEFAULT_REFERENCE_TYPE); 138 } 139 140 /** 141 * Create a new {@code ConcurrentReferenceHashMap} instance. 142 * @param initialCapacity the initial capacity of the map 143 * @param referenceType the reference type used for entries (soft or weak) 144 */ 145 public ConcurrentReferenceHashMap(int initialCapacity, ReferenceType referenceType) { 146 this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL, referenceType); 147 } 148 149 /** 150 * Create a new {@code ConcurrentReferenceHashMap} instance. 151 * @param initialCapacity the initial capacity of the map 152 * @param loadFactor the load factor. When the average number of references per 153 * table exceeds this value, resize will be attempted. 154 * @param concurrencyLevel the expected number of threads that will concurrently 155 * write to the map 156 */ 157 public ConcurrentReferenceHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) { 158 this(initialCapacity, loadFactor, concurrencyLevel, DEFAULT_REFERENCE_TYPE); 159 } 160 161 /** 162 * Create a new {@code ConcurrentReferenceHashMap} instance. 163 * @param initialCapacity the initial capacity of the map 164 * @param loadFactor the load factor. When the average number of references per 165 * table exceeds this value, resize will be attempted. 166 * @param concurrencyLevel the expected number of threads that will concurrently 167 * write to the map 168 * @param referenceType the reference type used for entries (soft or weak) 169 */ 170 @SuppressWarnings("unchecked") 171 public ConcurrentReferenceHashMap( 172 int initialCapacity, float loadFactor, int concurrencyLevel, ReferenceType referenceType) { 173 174 Assert.isTrue(initialCapacity >= 0, "Initial capacity must not be negative"); 175 Assert.isTrue(loadFactor > 0f, "Load factor must be positive"); 176 Assert.isTrue(concurrencyLevel > 0, "Concurrency level must be positive"); 177 Assert.notNull(referenceType, "Reference type must not be null"); 178 this.loadFactor = loadFactor; 179 this.shift = calculateShift(concurrencyLevel, MAXIMUM_CONCURRENCY_LEVEL); 180 int size = 1 << this.shift; 181 this.referenceType = referenceType; 182 int roundedUpSegmentCapacity = (int) ((initialCapacity + size - 1L) / size); 183 int initialSize = 1 << calculateShift(roundedUpSegmentCapacity, MAXIMUM_SEGMENT_SIZE); 184 Segment[] segments = (Segment[]) Array.newInstance(Segment.class, size); 185 int resizeThreshold = (int) (initialSize * getLoadFactor()); 186 for (int i = 0; i < segments.length; i++) { 187 segments[i] = new Segment(initialSize, resizeThreshold); 188 } 189 this.segments = segments; 190 } 191 192 193 protected final float getLoadFactor() { 194 return this.loadFactor; 195 } 196 197 protected final int getSegmentsSize() { 198 return this.segments.length; 199 } 200 201 protected final Segment getSegment(int index) { 202 return this.segments[index]; 203 } 204 205 /** 206 * Factory method that returns the {@link ReferenceManager}. 207 * This method will be called once for each {@link Segment}. 208 * @return a new reference manager 209 */ 210 protected ReferenceManager createReferenceManager() { 211 return new ReferenceManager(); 212 } 213 214 /** 215 * Get the hash for a given object, apply an additional hash function to reduce 216 * collisions. This implementation uses the same Wang/Jenkins algorithm as 217 * {@link ConcurrentHashMap}. Subclasses can override to provide alternative hashing. 218 * @param o the object to hash (may be null) 219 * @return the resulting hash code 220 */ 221 protected int getHash(@Nullable Object o) { 222 int hash = (o != null ? o.hashCode() : 0); 223 hash += (hash << 15) ^ 0xffffcd7d; 224 hash ^= (hash >>> 10); 225 hash += (hash << 3); 226 hash ^= (hash >>> 6); 227 hash += (hash << 2) + (hash << 14); 228 hash ^= (hash >>> 16); 229 return hash; 230 } 231 232 @Override 233 @Nullable 234 public V get(@Nullable Object key) { 235 Reference<K, V> ref = getReference(key, Restructure.WHEN_NECESSARY); 236 Entry<K, V> entry = (ref != null ? ref.get() : null); 237 return (entry != null ? entry.getValue() : null); 238 } 239 240 @Override 241 @Nullable 242 public V getOrDefault(@Nullable Object key, @Nullable V defaultValue) { 243 Reference<K, V> ref = getReference(key, Restructure.WHEN_NECESSARY); 244 Entry<K, V> entry = (ref != null ? ref.get() : null); 245 return (entry != null ? entry.getValue() : defaultValue); 246 } 247 248 @Override 249 public boolean containsKey(@Nullable Object key) { 250 Reference<K, V> ref = getReference(key, Restructure.WHEN_NECESSARY); 251 Entry<K, V> entry = (ref != null ? ref.get() : null); 252 return (entry != null && ObjectUtils.nullSafeEquals(entry.getKey(), key)); 253 } 254 255 /** 256 * Return a {@link Reference} to the {@link Entry} for the specified {@code key}, 257 * or {@code null} if not found. 258 * @param key the key (can be {@code null}) 259 * @param restructure types of restructure allowed during this call 260 * @return the reference, or {@code null} if not found 261 */ 262 @Nullable 263 protected final Reference<K, V> getReference(@Nullable Object key, Restructure restructure) { 264 int hash = getHash(key); 265 return getSegmentForHash(hash).getReference(key, hash, restructure); 266 } 267 268 @Override 269 @Nullable 270 public V put(@Nullable K key, @Nullable V value) { 271 return put(key, value, true); 272 } 273 274 @Override 275 @Nullable 276 public V putIfAbsent(@Nullable K key, @Nullable V value) { 277 return put(key, value, false); 278 } 279 280 @Nullable 281 private V put(@Nullable final K key, @Nullable final V value, final boolean overwriteExisting) { 282 return doTask(key, new Task<V>(TaskOption.RESTRUCTURE_BEFORE, TaskOption.RESIZE) { 283 @Override 284 @Nullable 285 protected V execute(@Nullable Reference<K, V> ref, @Nullable Entry<K, V> entry, @Nullable Entries<V> entries) { 286 if (entry != null) { 287 V oldValue = entry.getValue(); 288 if (overwriteExisting) { 289 entry.setValue(value); 290 } 291 return oldValue; 292 } 293 Assert.state(entries != null, "No entries segment"); 294 entries.add(value); 295 return null; 296 } 297 }); 298 } 299 300 @Override 301 @Nullable 302 public V remove(Object key) { 303 return doTask(key, new Task<V>(TaskOption.RESTRUCTURE_AFTER, TaskOption.SKIP_IF_EMPTY) { 304 @Override 305 @Nullable 306 protected V execute(@Nullable Reference<K, V> ref, @Nullable Entry<K, V> entry) { 307 if (entry != null) { 308 if (ref != null) { 309 ref.release(); 310 } 311 return entry.value; 312 } 313 return null; 314 } 315 }); 316 } 317 318 @Override 319 public boolean remove(Object key, final Object value) { 320 Boolean result = doTask(key, new Task<Boolean>(TaskOption.RESTRUCTURE_AFTER, TaskOption.SKIP_IF_EMPTY) { 321 @Override 322 protected Boolean execute(@Nullable Reference<K, V> ref, @Nullable Entry<K, V> entry) { 323 if (entry != null && ObjectUtils.nullSafeEquals(entry.getValue(), value)) { 324 if (ref != null) { 325 ref.release(); 326 } 327 return true; 328 } 329 return false; 330 } 331 }); 332 return (Boolean.TRUE.equals(result)); 333 } 334 335 @Override 336 public boolean replace(K key, final V oldValue, final V newValue) { 337 Boolean result = doTask(key, new Task<Boolean>(TaskOption.RESTRUCTURE_BEFORE, TaskOption.SKIP_IF_EMPTY) { 338 @Override 339 protected Boolean execute(@Nullable Reference<K, V> ref, @Nullable Entry<K, V> entry) { 340 if (entry != null && ObjectUtils.nullSafeEquals(entry.getValue(), oldValue)) { 341 entry.setValue(newValue); 342 return true; 343 } 344 return false; 345 } 346 }); 347 return (Boolean.TRUE.equals(result)); 348 } 349 350 @Override 351 @Nullable 352 public V replace(K key, final V value) { 353 return doTask(key, new Task<V>(TaskOption.RESTRUCTURE_BEFORE, TaskOption.SKIP_IF_EMPTY) { 354 @Override 355 @Nullable 356 protected V execute(@Nullable Reference<K, V> ref, @Nullable Entry<K, V> entry) { 357 if (entry != null) { 358 V oldValue = entry.getValue(); 359 entry.setValue(value); 360 return oldValue; 361 } 362 return null; 363 } 364 }); 365 } 366 367 @Override 368 public void clear() { 369 for (Segment segment : this.segments) { 370 segment.clear(); 371 } 372 } 373 374 /** 375 * Remove any entries that have been garbage collected and are no longer referenced. 376 * Under normal circumstances garbage collected entries are automatically purged as 377 * items are added or removed from the Map. This method can be used to force a purge, 378 * and is useful when the Map is read frequently but updated less often. 379 */ 380 public void purgeUnreferencedEntries() { 381 for (Segment segment : this.segments) { 382 segment.restructureIfNecessary(false); 383 } 384 } 385 386 387 @Override 388 public int size() { 389 int size = 0; 390 for (Segment segment : this.segments) { 391 size += segment.getCount(); 392 } 393 return size; 394 } 395 396 @Override 397 public boolean isEmpty() { 398 for (Segment segment : this.segments) { 399 if (segment.getCount() > 0) { 400 return false; 401 } 402 } 403 return true; 404 } 405 406 @Override 407 public Set<Map.Entry<K, V>> entrySet() { 408 Set<Map.Entry<K, V>> entrySet = this.entrySet; 409 if (entrySet == null) { 410 entrySet = new EntrySet(); 411 this.entrySet = entrySet; 412 } 413 return entrySet; 414 } 415 416 @Nullable 417 private <T> T doTask(@Nullable Object key, Task<T> task) { 418 int hash = getHash(key); 419 return getSegmentForHash(hash).doTask(hash, key, task); 420 } 421 422 private Segment getSegmentForHash(int hash) { 423 return this.segments[(hash >>> (32 - this.shift)) & (this.segments.length - 1)]; 424 } 425 426 /** 427 * Calculate a shift value that can be used to create a power-of-two value between 428 * the specified maximum and minimum values. 429 * @param minimumValue the minimum value 430 * @param maximumValue the maximum value 431 * @return the calculated shift (use {@code 1 << shift} to obtain a value) 432 */ 433 protected static int calculateShift(int minimumValue, int maximumValue) { 434 int shift = 0; 435 int value = 1; 436 while (value < minimumValue && value < maximumValue) { 437 value <<= 1; 438 shift++; 439 } 440 return shift; 441 } 442 443 444 /** 445 * Various reference types supported by this map. 446 */ 447 public enum ReferenceType { 448 449 /** Use {@link SoftReference SoftReferences}. */ 450 SOFT, 451 452 /** Use {@link WeakReference WeakReferences}. */ 453 WEAK 454 } 455 456 457 /** 458 * A single segment used to divide the map to allow better concurrent performance. 459 */ 460 @SuppressWarnings("serial") 461 protected final class Segment extends ReentrantLock { 462 463 private final ReferenceManager referenceManager; 464 465 private final int initialSize; 466 467 /** 468 * Array of references indexed using the low order bits from the hash. 469 * This property should only be set along with {@code resizeThreshold}. 470 */ 471 private volatile Reference<K, V>[] references; 472 473 /** 474 * The total number of references contained in this segment. This includes chained 475 * references and references that have been garbage collected but not purged. 476 */ 477 private final AtomicInteger count = new AtomicInteger(0); 478 479 /** 480 * The threshold when resizing of the references should occur. When {@code count} 481 * exceeds this value references will be resized. 482 */ 483 private int resizeThreshold; 484 485 public Segment(int initialSize, int resizeThreshold) { 486 this.referenceManager = createReferenceManager(); 487 this.initialSize = initialSize; 488 this.references = createReferenceArray(initialSize); 489 this.resizeThreshold = resizeThreshold; 490 } 491 492 @Nullable 493 public Reference<K, V> getReference(@Nullable Object key, int hash, Restructure restructure) { 494 if (restructure == Restructure.WHEN_NECESSARY) { 495 restructureIfNecessary(false); 496 } 497 if (this.count.get() == 0) { 498 return null; 499 } 500 // Use a local copy to protect against other threads writing 501 Reference<K, V>[] references = this.references; 502 int index = getIndex(hash, references); 503 Reference<K, V> head = references[index]; 504 return findInChain(head, key, hash); 505 } 506 507 /** 508 * Apply an update operation to this segment. 509 * The segment will be locked during the update. 510 * @param hash the hash of the key 511 * @param key the key 512 * @param task the update operation 513 * @return the result of the operation 514 */ 515 @Nullable 516 public <T> T doTask(final int hash, @Nullable final Object key, final Task<T> task) { 517 boolean resize = task.hasOption(TaskOption.RESIZE); 518 if (task.hasOption(TaskOption.RESTRUCTURE_BEFORE)) { 519 restructureIfNecessary(resize); 520 } 521 if (task.hasOption(TaskOption.SKIP_IF_EMPTY) && this.count.get() == 0) { 522 return task.execute(null, null, null); 523 } 524 lock(); 525 try { 526 final int index = getIndex(hash, this.references); 527 final Reference<K, V> head = this.references[index]; 528 Reference<K, V> ref = findInChain(head, key, hash); 529 Entry<K, V> entry = (ref != null ? ref.get() : null); 530 Entries<V> entries = value -> { 531 @SuppressWarnings("unchecked") 532 Entry<K, V> newEntry = new Entry<>((K) key, value); 533 Reference<K, V> newReference = Segment.this.referenceManager.createReference(newEntry, hash, head); 534 Segment.this.references[index] = newReference; 535 Segment.this.count.incrementAndGet(); 536 }; 537 return task.execute(ref, entry, entries); 538 } 539 finally { 540 unlock(); 541 if (task.hasOption(TaskOption.RESTRUCTURE_AFTER)) { 542 restructureIfNecessary(resize); 543 } 544 } 545 } 546 547 /** 548 * Clear all items from this segment. 549 */ 550 public void clear() { 551 if (this.count.get() == 0) { 552 return; 553 } 554 lock(); 555 try { 556 this.references = createReferenceArray(this.initialSize); 557 this.resizeThreshold = (int) (this.references.length * getLoadFactor()); 558 this.count.set(0); 559 } 560 finally { 561 unlock(); 562 } 563 } 564 565 /** 566 * Restructure the underlying data structure when it becomes necessary. This 567 * method can increase the size of the references table as well as purge any 568 * references that have been garbage collected. 569 * @param allowResize if resizing is permitted 570 */ 571 protected final void restructureIfNecessary(boolean allowResize) { 572 int currCount = this.count.get(); 573 boolean needsResize = allowResize && (currCount > 0 && currCount >= this.resizeThreshold); 574 Reference<K, V> ref = this.referenceManager.pollForPurge(); 575 if (ref != null || (needsResize)) { 576 restructure(allowResize, ref); 577 } 578 } 579 580 private void restructure(boolean allowResize, @Nullable Reference<K, V> ref) { 581 boolean needsResize; 582 lock(); 583 try { 584 int countAfterRestructure = this.count.get(); 585 Set<Reference<K, V>> toPurge = Collections.emptySet(); 586 if (ref != null) { 587 toPurge = new HashSet<>(); 588 while (ref != null) { 589 toPurge.add(ref); 590 ref = this.referenceManager.pollForPurge(); 591 } 592 } 593 countAfterRestructure -= toPurge.size(); 594 595 // Recalculate taking into account count inside lock and items that 596 // will be purged 597 needsResize = (countAfterRestructure > 0 && countAfterRestructure >= this.resizeThreshold); 598 boolean resizing = false; 599 int restructureSize = this.references.length; 600 if (allowResize && needsResize && restructureSize < MAXIMUM_SEGMENT_SIZE) { 601 restructureSize <<= 1; 602 resizing = true; 603 } 604 605 // Either create a new table or reuse the existing one 606 Reference<K, V>[] restructured = 607 (resizing ? createReferenceArray(restructureSize) : this.references); 608 609 // Restructure 610 for (int i = 0; i < this.references.length; i++) { 611 ref = this.references[i]; 612 if (!resizing) { 613 restructured[i] = null; 614 } 615 while (ref != null) { 616 if (!toPurge.contains(ref)) { 617 Entry<K, V> entry = ref.get(); 618 if (entry != null) { 619 int index = getIndex(ref.getHash(), restructured); 620 restructured[index] = this.referenceManager.createReference( 621 entry, ref.getHash(), restructured[index]); 622 } 623 } 624 ref = ref.getNext(); 625 } 626 } 627 628 // Replace volatile members 629 if (resizing) { 630 this.references = restructured; 631 this.resizeThreshold = (int) (this.references.length * getLoadFactor()); 632 } 633 this.count.set(Math.max(countAfterRestructure, 0)); 634 } 635 finally { 636 unlock(); 637 } 638 } 639 640 @Nullable 641 private Reference<K, V> findInChain(Reference<K, V> ref, @Nullable Object key, int hash) { 642 Reference<K, V> currRef = ref; 643 while (currRef != null) { 644 if (currRef.getHash() == hash) { 645 Entry<K, V> entry = currRef.get(); 646 if (entry != null) { 647 K entryKey = entry.getKey(); 648 if (ObjectUtils.nullSafeEquals(entryKey, key)) { 649 return currRef; 650 } 651 } 652 } 653 currRef = currRef.getNext(); 654 } 655 return null; 656 } 657 658 @SuppressWarnings({"rawtypes", "unchecked"}) 659 private Reference<K, V>[] createReferenceArray(int size) { 660 return new Reference[size]; 661 } 662 663 private int getIndex(int hash, Reference<K, V>[] references) { 664 return (hash & (references.length - 1)); 665 } 666 667 /** 668 * Return the size of the current references array. 669 */ 670 public final int getSize() { 671 return this.references.length; 672 } 673 674 /** 675 * Return the total number of references in this segment. 676 */ 677 public final int getCount() { 678 return this.count.get(); 679 } 680 } 681 682 683 /** 684 * A reference to an {@link Entry} contained in the map. Implementations are usually 685 * wrappers around specific Java reference implementations (e.g., {@link SoftReference}). 686 * @param <K> the key type 687 * @param <V> the value type 688 */ 689 protected interface Reference<K, V> { 690 691 /** 692 * Return the referenced entry, or {@code null} if the entry is no longer available. 693 */ 694 @Nullable 695 Entry<K, V> get(); 696 697 /** 698 * Return the hash for the reference. 699 */ 700 int getHash(); 701 702 /** 703 * Return the next reference in the chain, or {@code null} if none. 704 */ 705 @Nullable 706 Reference<K, V> getNext(); 707 708 /** 709 * Release this entry and ensure that it will be returned from 710 * {@code ReferenceManager#pollForPurge()}. 711 */ 712 void release(); 713 } 714 715 716 /** 717 * A single map entry. 718 * @param <K> the key type 719 * @param <V> the value type 720 */ 721 protected static final class Entry<K, V> implements Map.Entry<K, V> { 722 723 @Nullable 724 private final K key; 725 726 @Nullable 727 private volatile V value; 728 729 public Entry(@Nullable K key, @Nullable V value) { 730 this.key = key; 731 this.value = value; 732 } 733 734 @Override 735 @Nullable 736 public K getKey() { 737 return this.key; 738 } 739 740 @Override 741 @Nullable 742 public V getValue() { 743 return this.value; 744 } 745 746 @Override 747 @Nullable 748 public V setValue(@Nullable V value) { 749 V previous = this.value; 750 this.value = value; 751 return previous; 752 } 753 754 @Override 755 public String toString() { 756 return (this.key + "=" + this.value); 757 } 758 759 @Override 760 @SuppressWarnings("rawtypes") 761 public final boolean equals(@Nullable Object other) { 762 if (this == other) { 763 return true; 764 } 765 if (!(other instanceof Map.Entry)) { 766 return false; 767 } 768 Map.Entry otherEntry = (Map.Entry) other; 769 return (ObjectUtils.nullSafeEquals(getKey(), otherEntry.getKey()) && 770 ObjectUtils.nullSafeEquals(getValue(), otherEntry.getValue())); 771 } 772 773 @Override 774 public final int hashCode() { 775 return (ObjectUtils.nullSafeHashCode(this.key) ^ ObjectUtils.nullSafeHashCode(this.value)); 776 } 777 } 778 779 780 /** 781 * A task that can be {@link Segment#doTask run} against a {@link Segment}. 782 */ 783 private abstract class Task<T> { 784 785 private final EnumSet<TaskOption> options; 786 787 public Task(TaskOption... options) { 788 this.options = (options.length == 0 ? EnumSet.noneOf(TaskOption.class) : EnumSet.of(options[0], options)); 789 } 790 791 public boolean hasOption(TaskOption option) { 792 return this.options.contains(option); 793 } 794 795 /** 796 * Execute the task. 797 * @param ref the found reference (or {@code null}) 798 * @param entry the found entry (or {@code null}) 799 * @param entries access to the underlying entries 800 * @return the result of the task 801 * @see #execute(Reference, Entry) 802 */ 803 @Nullable 804 protected T execute(@Nullable Reference<K, V> ref, @Nullable Entry<K, V> entry, @Nullable Entries<V> entries) { 805 return execute(ref, entry); 806 } 807 808 /** 809 * Convenience method that can be used for tasks that do not need access to {@link Entries}. 810 * @param ref the found reference (or {@code null}) 811 * @param entry the found entry (or {@code null}) 812 * @return the result of the task 813 * @see #execute(Reference, Entry, Entries) 814 */ 815 @Nullable 816 protected T execute(@Nullable Reference<K, V> ref, @Nullable Entry<K, V> entry) { 817 return null; 818 } 819 } 820 821 822 /** 823 * Various options supported by a {@code Task}. 824 */ 825 private enum TaskOption { 826 827 RESTRUCTURE_BEFORE, RESTRUCTURE_AFTER, SKIP_IF_EMPTY, RESIZE 828 } 829 830 831 /** 832 * Allows a task access to {@link ConcurrentReferenceHashMap.Segment} entries. 833 */ 834 private interface Entries<V> { 835 836 /** 837 * Add a new entry with the specified value. 838 * @param value the value to add 839 */ 840 void add(@Nullable V value); 841 } 842 843 844 /** 845 * Internal entry-set implementation. 846 */ 847 private class EntrySet extends AbstractSet<Map.Entry<K, V>> { 848 849 @Override 850 public Iterator<Map.Entry<K, V>> iterator() { 851 return new EntryIterator(); 852 } 853 854 @Override 855 public boolean contains(@Nullable Object o) { 856 if (o instanceof Map.Entry<?, ?>) { 857 Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o; 858 Reference<K, V> ref = ConcurrentReferenceHashMap.this.getReference(entry.getKey(), Restructure.NEVER); 859 Entry<K, V> otherEntry = (ref != null ? ref.get() : null); 860 if (otherEntry != null) { 861 return ObjectUtils.nullSafeEquals(otherEntry.getValue(), otherEntry.getValue()); 862 } 863 } 864 return false; 865 } 866 867 @Override 868 public boolean remove(Object o) { 869 if (o instanceof Map.Entry<?, ?>) { 870 Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o; 871 return ConcurrentReferenceHashMap.this.remove(entry.getKey(), entry.getValue()); 872 } 873 return false; 874 } 875 876 @Override 877 public int size() { 878 return ConcurrentReferenceHashMap.this.size(); 879 } 880 881 @Override 882 public void clear() { 883 ConcurrentReferenceHashMap.this.clear(); 884 } 885 } 886 887 888 /** 889 * Internal entry iterator implementation. 890 */ 891 private class EntryIterator implements Iterator<Map.Entry<K, V>> { 892 893 private int segmentIndex; 894 895 private int referenceIndex; 896 897 @Nullable 898 private Reference<K, V>[] references; 899 900 @Nullable 901 private Reference<K, V> reference; 902 903 @Nullable 904 private Entry<K, V> next; 905 906 @Nullable 907 private Entry<K, V> last; 908 909 public EntryIterator() { 910 moveToNextSegment(); 911 } 912 913 @Override 914 public boolean hasNext() { 915 getNextIfNecessary(); 916 return (this.next != null); 917 } 918 919 @Override 920 public Entry<K, V> next() { 921 getNextIfNecessary(); 922 if (this.next == null) { 923 throw new NoSuchElementException(); 924 } 925 this.last = this.next; 926 this.next = null; 927 return this.last; 928 } 929 930 private void getNextIfNecessary() { 931 while (this.next == null) { 932 moveToNextReference(); 933 if (this.reference == null) { 934 return; 935 } 936 this.next = this.reference.get(); 937 } 938 } 939 940 private void moveToNextReference() { 941 if (this.reference != null) { 942 this.reference = this.reference.getNext(); 943 } 944 while (this.reference == null && this.references != null) { 945 if (this.referenceIndex >= this.references.length) { 946 moveToNextSegment(); 947 this.referenceIndex = 0; 948 } 949 else { 950 this.reference = this.references[this.referenceIndex]; 951 this.referenceIndex++; 952 } 953 } 954 } 955 956 private void moveToNextSegment() { 957 this.reference = null; 958 this.references = null; 959 if (this.segmentIndex < ConcurrentReferenceHashMap.this.segments.length) { 960 this.references = ConcurrentReferenceHashMap.this.segments[this.segmentIndex].references; 961 this.segmentIndex++; 962 } 963 } 964 965 @Override 966 public void remove() { 967 Assert.state(this.last != null, "No element to remove"); 968 ConcurrentReferenceHashMap.this.remove(this.last.getKey()); 969 } 970 } 971 972 973 /** 974 * The types of restructuring that can be performed. 975 */ 976 protected enum Restructure { 977 978 WHEN_NECESSARY, NEVER 979 } 980 981 982 /** 983 * Strategy class used to manage {@link Reference References}. 984 * This class can be overridden if alternative reference types need to be supported. 985 */ 986 protected class ReferenceManager { 987 988 private final ReferenceQueue<Entry<K, V>> queue = new ReferenceQueue<>(); 989 990 /** 991 * Factory method used to create a new {@link Reference}. 992 * @param entry the entry contained in the reference 993 * @param hash the hash 994 * @param next the next reference in the chain, or {@code null} if none 995 * @return a new {@link Reference} 996 */ 997 public Reference<K, V> createReference(Entry<K, V> entry, int hash, @Nullable Reference<K, V> next) { 998 if (ConcurrentReferenceHashMap.this.referenceType == ReferenceType.WEAK) { 999 return new WeakEntryReference<>(entry, hash, next, this.queue); 1000 } 1001 return new SoftEntryReference<>(entry, hash, next, this.queue); 1002 } 1003 1004 /** 1005 * Return any reference that has been garbage collected and can be purged from the 1006 * underlying structure or {@code null} if no references need purging. This 1007 * method must be thread safe and ideally should not block when returning 1008 * {@code null}. References should be returned once and only once. 1009 * @return a reference to purge or {@code null} 1010 */ 1011 @SuppressWarnings("unchecked") 1012 @Nullable 1013 public Reference<K, V> pollForPurge() { 1014 return (Reference<K, V>) this.queue.poll(); 1015 } 1016 } 1017 1018 1019 /** 1020 * Internal {@link Reference} implementation for {@link SoftReference SoftReferences}. 1021 */ 1022 private static final class SoftEntryReference<K, V> extends SoftReference<Entry<K, V>> implements Reference<K, V> { 1023 1024 private final int hash; 1025 1026 @Nullable 1027 private final Reference<K, V> nextReference; 1028 1029 public SoftEntryReference(Entry<K, V> entry, int hash, @Nullable Reference<K, V> next, 1030 ReferenceQueue<Entry<K, V>> queue) { 1031 1032 super(entry, queue); 1033 this.hash = hash; 1034 this.nextReference = next; 1035 } 1036 1037 @Override 1038 public int getHash() { 1039 return this.hash; 1040 } 1041 1042 @Override 1043 @Nullable 1044 public Reference<K, V> getNext() { 1045 return this.nextReference; 1046 } 1047 1048 @Override 1049 public void release() { 1050 enqueue(); 1051 clear(); 1052 } 1053 } 1054 1055 1056 /** 1057 * Internal {@link Reference} implementation for {@link WeakReference WeakReferences}. 1058 */ 1059 private static final class WeakEntryReference<K, V> extends WeakReference<Entry<K, V>> implements Reference<K, V> { 1060 1061 private final int hash; 1062 1063 @Nullable 1064 private final Reference<K, V> nextReference; 1065 1066 public WeakEntryReference(Entry<K, V> entry, int hash, @Nullable Reference<K, V> next, 1067 ReferenceQueue<Entry<K, V>> queue) { 1068 1069 super(entry, queue); 1070 this.hash = hash; 1071 this.nextReference = next; 1072 } 1073 1074 @Override 1075 public int getHash() { 1076 return this.hash; 1077 } 1078 1079 @Override 1080 @Nullable 1081 public Reference<K, V> getNext() { 1082 return this.nextReference; 1083 } 1084 1085 @Override 1086 public void release() { 1087 enqueue(); 1088 clear(); 1089 } 1090 } 1091 1092}