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