1 /* 2 * Copyright (C) 2009 Google Inc. 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.google.common.collect; 18 19 import com.google.common.base.Function; 20 21 import java.io.IOException; 22 import java.io.Serializable; 23 import java.lang.reflect.Array; 24 import java.lang.reflect.Field; 25 import java.util.AbstractCollection; 26 import java.util.AbstractMap; 27 import java.util.AbstractSet; 28 import java.util.Collection; 29 import java.util.Iterator; 30 import java.util.Map; 31 import java.util.NoSuchElementException; 32 import java.util.Set; 33 import java.util.concurrent.ConcurrentHashMap; 34 import java.util.concurrent.ConcurrentMap; 35 import java.util.concurrent.atomic.AtomicReferenceArray; 36 import java.util.concurrent.locks.ReentrantLock; 37 38 import javax.annotation.Nullable; 39 40 /** 41 * A framework for concurrent hash map implementations. The 42 * CustomConcurrentHashMap class itself is not extensible and does not contain 43 * any methods. Use {@link Builder} to create a custom concurrent hash map 44 * instance. Client libraries implement {@link Strategy}, and this class 45 * provides the surrounding concurrent data structure which implements {@link 46 * ConcurrentMap}. Additionally supports implementing maps where {@link 47 * Map#get} atomically computes values on demand (see {@link 48 * Builder#buildComputingMap(CustomConcurrentHashMap.ComputingStrategy, 49 * Function)}). 50 * 51 * <p>The resulting hash table supports full concurrency of retrievals and 52 * adjustable expected concurrency for updates. Even though all operations are 53 * thread-safe, retrieval operations do <i>not</i> entail locking, 54 * and there is <i>not</i> any support for locking the entire table 55 * in a way that prevents all access. 56 * 57 * <p>Retrieval operations (including {@link Map#get}) generally do not 58 * block, so may overlap with update operations (including 59 * {@link Map#put} and {@link Map#remove}). Retrievals reflect the results 60 * of the most recently <i>completed</i> update operations holding 61 * upon their onset. For aggregate operations such as {@link Map#putAll} 62 * and {@link Map#clear}, concurrent retrievals may reflect insertion or 63 * removal of only some entries. Similarly, iterators return elements 64 * reflecting the state of the hash table at some point at or since the 65 * creation of the iterator. They do <i>not</i> throw 66 * {@link java.util.ConcurrentModificationException}. However, iterators can 67 * only be used by one thread at a time. 68 * 69 * <p>The resulting {@link ConcurrentMap} and its views and iterators implement 70 * all of the <i>optional</i> methods of the {@link java.util.Map} and {@link 71 * java.util.Iterator} interfaces. Partially reclaimed entries are never 72 * exposed through the views or iterators. 73 * 74 * <p>For example, the following strategy emulates the behavior of 75 * {@link java.util.concurrent.ConcurrentHashMap}: 76 * 77 * <pre> {@code 78 * class ConcurrentHashMapStrategy<K, V> 79 * implements CustomConcurrentHashMap.Strategy<K, V, 80 * InternalEntry<K, V>>, Serializable { 81 * public InternalEntry<K, V> newEntry(K key, int hash, 82 * InternalEntry<K, V> next) { 83 * return new InternalEntry<K, V>(key, hash, null, next); 84 * } 85 * public InternalEntry<K, V> copyEntry(K key, 86 * InternalEntry<K, V> original, InternalEntry<K, V> next) { 87 * return new InternalEntry<K, V>(key, original.hash, original.value, next); 88 * } 89 * public void setValue(InternalEntry<K, V> entry, V value) { 90 * entry.value = value; 91 * } 92 * public V getValue(InternalEntry<K, V> entry) { return entry.value; } 93 * public boolean equalKeys(K a, Object b) { return a.equals(b); } 94 * public boolean equalValues(V a, Object b) { return a.equals(b); } 95 * public int hashKey(Object key) { return key.hashCode(); } 96 * public K getKey(InternalEntry<K, V> entry) { return entry.key; } 97 * public InternalEntry<K, V> getNext(InternalEntry<K, V> entry) { 98 * return entry.next; 99 * } 100 * public int getHash(InternalEntry<K, V> entry) { return entry.hash; } 101 * public void setInternals(CustomConcurrentHashMap.Internals<K, V, 102 * InternalEntry<K, V>> internals) {} // ignored 103 * } 104 * 105 * class InternalEntry<K, V> { 106 * final K key; 107 * final int hash; 108 * volatile V value; 109 * final InternalEntry<K, V> next; 110 * InternalEntry(K key, int hash, V value, InternalEntry<K, V> next) { 111 * this.key = key; 112 * this.hash = hash; 113 * this.value = value; 114 * this.next = next; 115 * } 116 * } 117 * }</pre> 118 * 119 * To create a {@link java.util.concurrent.ConcurrentMap} using the strategy 120 * above: 121 * 122 * <pre>{@code 123 * ConcurrentMap<K, V> map = new CustomConcurrentHashMap.Builder() 124 * .build(new ConcurrentHashMapStrategy<K, V>()); 125 * }</pre> 126 * 127 * @author Bob Lee 128 * @author Doug Lea 129 */ 130 final class CustomConcurrentHashMap { 131 132 /** Prevents instantiation. */ 133 private CustomConcurrentHashMap() {} 134 135 /** 136 * Builds a custom concurrent hash map. 137 */ 138 static final class Builder { 139 private static final int DEFAULT_INITIAL_CAPACITY = 16; 140 private static final int DEFAULT_CONCURRENCY_LEVEL = 16; 141 142 private static final int UNSET_INITIAL_CAPACITY = -1; 143 private static final int UNSET_CONCURRENCY_LEVEL = -1; 144 145 int initialCapacity = UNSET_INITIAL_CAPACITY; 146 int concurrencyLevel = UNSET_CONCURRENCY_LEVEL; 147 148 /** 149 * Sets a custom initial capacity (defaults to 16). Resizing this or any 150 * other kind of hash table is a relatively slow operation, so, when 151 * possible, it is a good idea to provide estimates of expected table 152 * sizes. 153 * 154 * @throws IllegalArgumentException if initialCapacity < 0 155 */ 156 public Builder initialCapacity(int initialCapacity) { 157 if (this.initialCapacity != UNSET_INITIAL_CAPACITY) { 158 throw new IllegalStateException( 159 "initial capacity was already set to " + this.initialCapacity); 160 } 161 if (initialCapacity < 0) { 162 throw new IllegalArgumentException(); 163 } 164 this.initialCapacity = initialCapacity; 165 return this; 166 } 167 168 /** 169 * Guides the allowed concurrency among update operations. Used as a 170 * hint for internal sizing. The table is internally partitioned to try to 171 * permit the indicated number of concurrent updates without contention. 172 * Because placement in hash tables is essentially random, the actual 173 * concurrency will vary. Ideally, you should choose a value to accommodate 174 * as many threads as will ever concurrently modify the table. Using a 175 * significantly higher value than you need can waste space and time, 176 * and a significantly lower value can lead to thread contention. But 177 * overestimates and underestimates within an order of magnitude do 178 * not usually have much noticeable impact. A value of one is 179 * appropriate when it is known that only one thread will modify and 180 * all others will only read. Defaults to {@literal 16}. 181 * 182 * @throws IllegalArgumentException if concurrencyLevel < 0 183 */ 184 public Builder concurrencyLevel(int concurrencyLevel) { 185 if (this.concurrencyLevel != UNSET_CONCURRENCY_LEVEL) { 186 throw new IllegalStateException( 187 "concurrency level was already set to " + this.concurrencyLevel); 188 } 189 if (concurrencyLevel <= 0) { 190 throw new IllegalArgumentException(); 191 } 192 this.concurrencyLevel = concurrencyLevel; 193 return this; 194 } 195 196 /** 197 * Creates a new concurrent hash map backed by the given strategy. 198 * 199 * @param strategy used to implement and manipulate the entries 200 * 201 * @param <K> the type of keys to be stored in the returned map 202 * @param <V> the type of values to be stored in the returned map 203 * @param <E> the type of internal entry to be stored in the returned map 204 * 205 * @throws NullPointerException if strategy is null 206 */ 207 public <K, V, E> ConcurrentMap<K, V> buildMap(Strategy<K, V, E> strategy) { 208 if (strategy == null) { 209 throw new NullPointerException("strategy"); 210 } 211 return new Impl<K, V, E>(strategy, this); 212 } 213 214 /** 215 * Creates a {@link ConcurrentMap}, backed by the given strategy, that 216 * supports atomic, on-demand computation of values. {@link Map#get} 217 * returns the value corresponding to the given key, atomically computes 218 * it using the computer function passed to this builder, or waits for 219 * another thread to compute the value if necessary. Only one value will 220 * be computed for each key at a given time. 221 * 222 * <p>If an entry's value has not finished computing yet, query methods 223 * besides {@link java.util.Map#get} return immediately as if an entry 224 * doesn't exist. In other words, an entry isn't externally visible until 225 * the value's computation completes. 226 * 227 * <p>{@link Map#get} in the returned map implementation throws: 228 * <ul> 229 * <li>{@link NullPointerException} if the key is null or the 230 * computer returns null</li> 231 * <li>or {@link ComputationException} wrapping an exception thrown by the 232 * computation</li> 233 * </ul> 234 * 235 * <p><b>Note:</b> Callers of {@code get()} <i>must</i> ensure that the key 236 * argument is of type {@code K}. {@code Map.get()} takes {@code Object}, 237 * so the key type is not checked at compile time. Passing an object of 238 * a type other than {@code K} can result in that object being unsafely 239 * passed to the computer function as type {@code K} not to mention the 240 * unsafe key being stored in the map. 241 * 242 * @param strategy used to implement and manipulate the entries 243 * @param computer used to compute values for keys 244 * 245 * @param <K> the type of keys to be stored in the returned map 246 * @param <V> the type of values to be stored in the returned map 247 * @param <E> the type of internal entry to be stored in the returned map 248 * 249 * @throws NullPointerException if strategy or computer is null 250 */ 251 public <K, V, E> ConcurrentMap<K, V> buildComputingMap( 252 ComputingStrategy<K, V, E> strategy, 253 Function<? super K, ? extends V> computer) { 254 if (strategy == null) { 255 throw new NullPointerException("strategy"); 256 } 257 if (computer == null) { 258 throw new NullPointerException("computer"); 259 } 260 261 return new ComputingImpl<K, V, E>(strategy, this, computer); 262 } 263 264 int getInitialCapacity() { 265 return (initialCapacity == UNSET_INITIAL_CAPACITY) 266 ? DEFAULT_INITIAL_CAPACITY : initialCapacity; 267 } 268 269 int getConcurrencyLevel() { 270 return (concurrencyLevel == UNSET_CONCURRENCY_LEVEL) 271 ? DEFAULT_CONCURRENCY_LEVEL : concurrencyLevel; 272 } 273 } 274 275 /** 276 * Implements behavior specific to the client's concurrent hash map 277 * implementation. Used by the framework to create new entries and perform 278 * operations on them. 279 * 280 * <p>Method parameters are never null unless otherwise specified. 281 * 282 * <h3>Partially Reclaimed Entries</h3> 283 * 284 * <p>This class does <i>not</i> allow {@code null} to be used as a key. 285 * Setting values to null is not permitted, but entries may have null keys 286 * or values for various reasons. For example, the key or value may have 287 * been garbage collected or reclaimed through other means. 288 * CustomConcurrentHashMap treats entries with null keys and values as 289 * "partially reclaimed" and ignores them for the most part. Entries may 290 * enter a partially reclaimed state but they must not leave it. Partially 291 * reclaimed entries will not be copied over during table expansions, for 292 * example. Strategy implementations should proactively remove partially 293 * reclaimed entries so that {@link Map#isEmpty} and {@link Map#size()} 294 * return up-to-date results. 295 * 296 * @param <K> the type of keys to be stored in the returned map 297 * @param <V> the type of values to be stored in the returned map 298 * @param <E> internal entry type, not directly exposed to clients in map 299 * views 300 */ 301 public interface Strategy<K, V, E> { 302 303 /** 304 * Constructs a new entry for the given key with a pointer to the given 305 * next entry. 306 * 307 * <p>This method may return different entry implementations 308 * depending upon whether next is null or not. For example, if next is 309 * null (as will often be the case), this factory might use an entry 310 * class that doesn't waste memory on an unnecessary field. 311 * 312 * @param key for this entry 313 * @param hash of key returned by {@link #hashKey} 314 * @param next entry (used when implementing a hash bucket as a linked 315 * list, for example), possibly null 316 * @return a new entry 317 */ 318 abstract E newEntry(K key, int hash, E next); 319 320 /** 321 * Creates a copy of the given entry pointing to the given next entry. 322 * Copies the value and any other implementation-specific state from 323 * {@code original} to the returned entry. For example, 324 * CustomConcurrentHashMap might use this method when removing other 325 * entries or expanding the internal table. 326 * 327 * @param key for {@code original} as well as the returned entry. 328 * Explicitly provided here to prevent reclamation of the key at an 329 * inopportune time in implementations that don't otherwise keep 330 * a strong reference to the key. 331 * @param original entry from which the value and other 332 * implementation-specific state should be copied 333 * @param newNext the next entry the new entry should point to, possibly 334 * null 335 */ 336 E copyEntry(K key, E original, E newNext); 337 338 /** 339 * Sets the value of an entry using volatile semantics. Values are set 340 * synchronously on a per-entry basis. 341 * 342 * @param entry to set the value on 343 * @param value to set 344 */ 345 void setValue(E entry, V value); 346 347 /** 348 * Gets the value of an entry using volatile semantics. 349 * 350 * @param entry to get the value from 351 */ 352 V getValue(E entry); 353 354 /** 355 * Returns true if the two given keys are equal, false otherwise. Neither 356 * key will be null. 357 * 358 * @param a key from inside the map 359 * @param b key passed from caller, not necesarily of type K 360 * 361 * @see Object#equals the same contractual obligations apply here 362 */ 363 boolean equalKeys(K a, Object b); 364 365 /** 366 * Returns true if the two given values are equal, false otherwise. Neither 367 * value will be null. 368 * 369 * @param a value from inside the map 370 * @param b value passed from caller, not necesarily of type V 371 * 372 * @see Object#equals the same contractual obligations apply here 373 */ 374 boolean equalValues(V a, Object b); 375 376 /** 377 * Returns a hash code for the given key. 378 * 379 * @see Object#hashCode the same contractual obligations apply here 380 */ 381 int hashKey(Object key); 382 383 /** 384 * Gets the key for the given entry. This may return null (for example, 385 * if the key was reclaimed by the garbage collector). 386 * 387 * @param entry to get key from 388 * @return key from the given entry 389 */ 390 K getKey(E entry); 391 392 /** 393 * Gets the next entry relative to the given entry, the exact same entry 394 * that was provided to {@link Strategy#newEntry} when the given entry was 395 * created. 396 * 397 * @return the next entry or null if null was passed to 398 * {@link Strategy#newEntry} 399 */ 400 E getNext(E entry); 401 402 /** 403 * Returns the hash code that was passed to {@link Strategy#newEntry}) 404 * when the given entry was created. 405 */ 406 int getHash(E entry); 407 408 // TODO: 409 // /** 410 // * Notifies the strategy that an entry has been removed from the map. 411 // * 412 // * @param entry that was recently removed 413 // */ 414 // void remove(E entry); 415 416 /** 417 * Provides an API for interacting directly with the map's internal 418 * entries to this strategy. Invoked once when the map is created. 419 * Strategies that don't need access to the map's internal entries 420 * can simply ignore the argument. 421 * 422 * @param internals of the map, enables direct interaction with the 423 * internal entries 424 */ 425 void setInternals(Internals<K, V, E> internals); 426 } 427 428 /** 429 * Provides access to a map's internal entries. 430 */ 431 public interface Internals<K, V, E> { 432 433 // TODO: 434 // /** 435 // * Returns a set view of the internal entries. 436 // */ 437 // Set<E> entrySet(); 438 439 /** 440 * Returns the internal entry corresponding to the given key from the map. 441 * 442 * @param key to retrieve entry for 443 * 444 * @throws NullPointerException if key is null 445 */ 446 E getEntry(K key); 447 448 /** 449 * Removes the given entry from the map if the value of the entry in the 450 * map matches the given value. 451 * 452 * @param entry to remove 453 * @param value entry must have for the removal to succeed 454 * 455 * @throws NullPointerException if entry is null 456 */ 457 boolean removeEntry(E entry, @Nullable V value); 458 459 /** 460 * Removes the given entry from the map. 461 * 462 * @param entry to remove 463 * 464 * @throws NullPointerException if entry is null 465 */ 466 boolean removeEntry(E entry); 467 } 468 469 /** 470 * Extends {@link Strategy} to add support for computing values on-demand. 471 * Implementations should typically intialize the entry's value to a 472 * placeholder value in {@link #newEntry(Object, int, Object)} so that 473 * {@link #waitForValue(Object)} can tell the difference between a 474 * pre-intialized value and an in-progress computation. {@link 475 * #copyEntry(Object, Object, Object)} must detect and handle the case where 476 * an entry is copied in the middle of a computation. Implementations can 477 * throw {@link UnsupportedOperationException} in {@link #setValue(Object, 478 * Object)} if they wish to prevent users from setting values directly. 479 * 480 * @see Builder#buildComputingMap(CustomConcurrentHashMap.ComputingStrategy, 481 * Function) 482 */ 483 public interface ComputingStrategy<K, V, E> extends Strategy<K, V, E> { 484 485 /** 486 * Computes a value for the given key and stores it in the given entry. 487 * Called as a result of {@link Map#get}. If this method throws an 488 * exception, CustomConcurrentHashMap will remove the entry and retry 489 * the computation on subsequent requests. 490 * 491 * @param entry that was created 492 * @param computer passed to {@link Builder#buildMap} 493 * 494 * @throws ComputationException if the computation threw an exception 495 * @throws NullPointerException if the computer returned null 496 * 497 * @return the computed value 498 */ 499 V compute(K key, E entry, Function<? super K, ? extends V> computer); 500 501 /** 502 * Gets a value from an entry waiting for the value to be set by {@link 503 * #compute} if necessary. Returns null if a value isn't available at 504 * which point CustomConcurrentHashMap tries to compute a new value. 505 * 506 * @param entry to return value from 507 * @return stored value or null if the value isn't available 508 * 509 * @throws InterruptedException if the thread was interrupted while 510 * waiting 511 */ 512 V waitForValue(E entry) throws InterruptedException; 513 } 514 515 /** 516 * Applies a supplemental hash function to a given hash code, which defends 517 * against poor quality hash functions. This is critical when the 518 * concurrent hash map uses power-of-two length hash tables, that otherwise 519 * encounter collisions for hash codes that do not differ in lower or upper 520 * bits. 521 * 522 * @param h hash code 523 */ 524 private static int rehash(int h) { 525 // Spread bits to regularize both segment and index locations, 526 // using variant of single-word Wang/Jenkins hash. 527 h += (h << 15) ^ 0xffffcd7d; 528 h ^= (h >>> 10); 529 h += (h << 3); 530 h ^= (h >>> 6); 531 h += (h << 2) + (h << 14); 532 return h ^ (h >>> 16); 533 } 534 535 /** The concurrent hash map implementation. */ 536 static class Impl<K, V, E> extends AbstractMap<K, V> 537 implements ConcurrentMap<K, V>, Serializable { 538 539 /* 540 * The basic strategy is to subdivide the table among Segments, 541 * each of which itself is a concurrently readable hash table. 542 */ 543 544 /* ---------------- Constants -------------- */ 545 546 /** 547 * The maximum capacity, used if a higher value is implicitly specified by 548 * either of the constructors with arguments. MUST be a power of two <= 549 * 1<<30 to ensure that entries are indexable using ints. 550 */ 551 static final int MAXIMUM_CAPACITY = 1 << 30; 552 553 /** 554 * The maximum number of segments to allow; used to bound constructor 555 * arguments. 556 */ 557 static final int MAX_SEGMENTS = 1 << 16; // slightly conservative 558 559 /** 560 * Number of unsynchronized retries in size and containsValue methods before 561 * resorting to locking. This is used to avoid unbounded retries if tables 562 * undergo continuous modification which would make it impossible to obtain 563 * an accurate result. 564 */ 565 static final int RETRIES_BEFORE_LOCK = 2; 566 567 /* ---------------- Fields -------------- */ 568 569 /** 570 * The strategy used to implement this map. 571 */ 572 final Strategy<K, V, E> strategy; 573 574 /** 575 * Mask value for indexing into segments. The upper bits of a key's hash 576 * code are used to choose the segment. 577 */ 578 final int segmentMask; 579 580 /** 581 * Shift value for indexing within segments. Helps prevent entries that 582 * end up in the same segment from also ending up in the same bucket. 583 */ 584 final int segmentShift; 585 586 /** 587 * The segments, each of which is a specialized hash table 588 */ 589 final Segment[] segments; 590 591 /** 592 * Creates a new, empty map with the specified strategy, initial capacity, 593 * load factor and concurrency level. 594 */ 595 Impl(Strategy<K, V, E> strategy, Builder builder) { 596 int concurrencyLevel = builder.getConcurrencyLevel(); 597 int initialCapacity = builder.getInitialCapacity(); 598 599 if (concurrencyLevel > MAX_SEGMENTS) { 600 concurrencyLevel = MAX_SEGMENTS; 601 } 602 603 // Find power-of-two sizes best matching arguments 604 int segmentShift = 0; 605 int segmentCount = 1; 606 while (segmentCount < concurrencyLevel) { 607 ++segmentShift; 608 segmentCount <<= 1; 609 } 610 this.segmentShift = 32 - segmentShift; 611 segmentMask = segmentCount - 1; 612 this.segments = newSegmentArray(segmentCount); 613 614 if (initialCapacity > MAXIMUM_CAPACITY) { 615 initialCapacity = MAXIMUM_CAPACITY; 616 } 617 618 int segmentCapacity = initialCapacity / segmentCount; 619 if (segmentCapacity * segmentCount < initialCapacity) { 620 ++segmentCapacity; 621 } 622 623 int segmentSize = 1; 624 while (segmentSize < segmentCapacity) { 625 segmentSize <<= 1; 626 } 627 for (int i = 0; i < this.segments.length; ++i) { 628 this.segments[i] = new Segment(segmentSize); 629 } 630 631 this.strategy = strategy; 632 633 strategy.setInternals(new InternalsImpl()); 634 } 635 636 int hash(Object key) { 637 int h = strategy.hashKey(key); 638 return rehash(h); 639 } 640 641 class InternalsImpl implements Internals<K, V, E>, Serializable { 642 643 static final long serialVersionUID = 0; 644 645 public E getEntry(K key) { 646 if (key == null) { 647 throw new NullPointerException("key"); 648 } 649 int hash = hash(key); 650 return segmentFor(hash).getEntry(key, hash); 651 } 652 653 public boolean removeEntry(E entry, V value) { 654 if (entry == null) { 655 throw new NullPointerException("entry"); 656 } 657 int hash = strategy.getHash(entry); 658 return segmentFor(hash).removeEntry(entry, hash, value); 659 } 660 661 public boolean removeEntry(E entry) { 662 if (entry == null) { 663 throw new NullPointerException("entry"); 664 } 665 int hash = strategy.getHash(entry); 666 return segmentFor(hash).removeEntry(entry, hash); 667 } 668 } 669 670 @SuppressWarnings("unchecked") 671 Segment[] newSegmentArray(int ssize) { 672 // Note: This is the only way I could figure out how to create 673 // a segment array (the compile has a tough time with arrays of 674 // inner classes of generic types apparently). Safe because we're 675 // restricting what can go in the array and no one has an 676 // unrestricted reference. 677 return (Segment[]) Array.newInstance(Segment.class, ssize); 678 } 679 680 /* ---------------- Small Utilities -------------- */ 681 682 /** 683 * Returns the segment that should be used for key with given hash 684 * 685 * @param hash the hash code for the key 686 * @return the segment 687 */ 688 Segment segmentFor(int hash) { 689 return segments[(hash >>> segmentShift) & segmentMask]; 690 } 691 692 /* ---------------- Inner Classes -------------- */ 693 694 /** 695 * Segments are specialized versions of hash tables. This subclasses from 696 * ReentrantLock opportunistically, just to simplify some locking and avoid 697 * separate construction. 698 */ 699 @SuppressWarnings("serial") // This class is never serialized. 700 final class Segment extends ReentrantLock { 701 702 /* 703 * Segments maintain a table of entry lists that are ALWAYS 704 * kept in a consistent state, so can be read without locking. 705 * Next fields of nodes are immutable (final). All list 706 * additions are performed at the front of each bin. This 707 * makes it easy to check changes, and also fast to traverse. 708 * When nodes would otherwise be changed, new nodes are 709 * created to replace them. This works well for hash tables 710 * since the bin lists tend to be short. (The average length 711 * is less than two for the default load factor threshold.) 712 * 713 * Read operations can thus proceed without locking, but rely 714 * on selected uses of volatiles to ensure that completed 715 * write operations performed by other threads are 716 * noticed. For most purposes, the "count" field, tracking the 717 * number of elements, serves as that volatile variable 718 * ensuring visibility. This is convenient because this field 719 * needs to be read in many read operations anyway: 720 * 721 * - All (unsynchronized) read operations must first read the 722 * "count" field, and should not look at table entries if 723 * it is 0. 724 * 725 * - All (synchronized) write operations should write to 726 * the "count" field after structurally changing any bin. 727 * The operations must not take any action that could even 728 * momentarily cause a concurrent read operation to see 729 * inconsistent data. This is made easier by the nature of 730 * the read operations in Map. For example, no operation 731 * can reveal that the table has grown but the threshold 732 * has not yet been updated, so there are no atomicity 733 * requirements for this with respect to reads. 734 * 735 * As a guide, all critical volatile reads and writes to the 736 * count field are marked in code comments. 737 */ 738 739 /** 740 * The number of elements in this segment's region. 741 */ 742 volatile int count; 743 744 /** 745 * Number of updates that alter the size of the table. This is used 746 * during bulk-read methods to make sure they see a consistent snapshot: 747 * If modCounts change during a traversal of segments computing size or 748 * checking containsValue, then we might have an inconsistent view of 749 * state so (usually) must retry. 750 */ 751 int modCount; 752 753 /** 754 * The table is expanded when its size exceeds this threshold. (The 755 * value of this field is always {@code (int)(capacity * loadFactor)}.) 756 */ 757 int threshold; 758 759 /** 760 * The per-segment table. 761 */ 762 volatile AtomicReferenceArray<E> table; 763 764 Segment(int initialCapacity) { 765 setTable(newEntryArray(initialCapacity)); 766 } 767 768 AtomicReferenceArray<E> newEntryArray(int size) { 769 return new AtomicReferenceArray<E>(size); 770 } 771 772 /** 773 * Sets table to new HashEntry array. Call only while holding lock or in 774 * constructor. 775 */ 776 void setTable(AtomicReferenceArray<E> newTable) { 777 this.threshold = newTable.length() * 3 / 4; 778 this.table = newTable; 779 } 780 781 /** 782 * Returns properly casted first entry of bin for given hash. 783 */ 784 E getFirst(int hash) { 785 AtomicReferenceArray<E> table = this.table; 786 return table.get(hash & (table.length() - 1)); 787 } 788 789 /* Specialized implementations of map methods */ 790 791 public E getEntry(Object key, int hash) { 792 Strategy<K, V, E> s = Impl.this.strategy; 793 if (count != 0) { // read-volatile 794 for (E e = getFirst(hash); e != null; e = s.getNext(e)) { 795 if (s.getHash(e) != hash) { 796 continue; 797 } 798 799 K entryKey = s.getKey(e); 800 if (entryKey == null) { 801 continue; 802 } 803 804 if (s.equalKeys(entryKey, key)) { 805 return e; 806 } 807 } 808 } 809 810 return null; 811 } 812 813 V get(Object key, int hash) { 814 E entry = getEntry(key, hash); 815 if (entry == null) { 816 return null; 817 } 818 819 return strategy.getValue(entry); 820 } 821 822 boolean containsKey(Object key, int hash) { 823 Strategy<K, V, E> s = Impl.this.strategy; 824 if (count != 0) { // read-volatile 825 for (E e = getFirst(hash); e != null; e = s.getNext(e)) { 826 if (s.getHash(e) != hash) { 827 continue; 828 } 829 830 K entryKey = s.getKey(e); 831 if (entryKey == null) { 832 continue; 833 } 834 835 if (s.equalKeys(entryKey, key)) { 836 // Return true only if this entry has a value. 837 return s.getValue(e) != null; 838 } 839 } 840 } 841 842 return false; 843 } 844 845 boolean containsValue(Object value) { 846 Strategy<K, V, E> s = Impl.this.strategy; 847 if (count != 0) { // read-volatile 848 AtomicReferenceArray<E> table = this.table; 849 int length = table.length(); 850 for (int i = 0; i < length; i++) { 851 for (E e = table.get(i); e != null; e = s.getNext(e)) { 852 V entryValue = s.getValue(e); 853 854 // If the value disappeared, this entry is partially collected, 855 // and we should skip it. 856 if (entryValue == null) { 857 continue; 858 } 859 860 if (s.equalValues(entryValue, value)) { 861 return true; 862 } 863 } 864 } 865 } 866 867 return false; 868 } 869 870 boolean replace(K key, int hash, V oldValue, V newValue) { 871 Strategy<K, V, E> s = Impl.this.strategy; 872 lock(); 873 try { 874 for (E e = getFirst(hash); e != null; e = s.getNext(e)) { 875 K entryKey = s.getKey(e); 876 if (s.getHash(e) == hash && entryKey != null 877 && s.equalKeys(key, entryKey)) { 878 // If the value disappeared, this entry is partially collected, 879 // and we should pretend like it doesn't exist. 880 V entryValue = s.getValue(e); 881 if (entryValue == null) { 882 return false; 883 } 884 885 if (s.equalValues(entryValue, oldValue)) { 886 s.setValue(e, newValue); 887 return true; 888 } 889 } 890 } 891 892 return false; 893 } finally { 894 unlock(); 895 } 896 } 897 898 V replace(K key, int hash, V newValue) { 899 Strategy<K, V, E> s = Impl.this.strategy; 900 lock(); 901 try { 902 for (E e = getFirst(hash); e != null; e = s.getNext(e)) { 903 K entryKey = s.getKey(e); 904 if (s.getHash(e) == hash && entryKey != null 905 && s.equalKeys(key, entryKey)) { 906 // If the value disappeared, this entry is partially collected, 907 // and we should pretend like it doesn't exist. 908 V entryValue = s.getValue(e); 909 if (entryValue == null) { 910 return null; 911 } 912 913 s.setValue(e, newValue); 914 return entryValue; 915 } 916 } 917 918 return null; 919 } finally { 920 unlock(); 921 } 922 } 923 924 V put(K key, int hash, V value, boolean onlyIfAbsent) { 925 Strategy<K, V, E> s = Impl.this.strategy; 926 lock(); 927 try { 928 int count = this.count; 929 if (count++ > this.threshold) { // ensure capacity 930 expand(); 931 } 932 933 AtomicReferenceArray<E> table = this.table; 934 int index = hash & (table.length() - 1); 935 936 E first = table.get(index); 937 938 // Look for an existing entry. 939 for (E e = first; e != null; e = s.getNext(e)) { 940 K entryKey = s.getKey(e); 941 if (s.getHash(e) == hash && entryKey != null 942 && s.equalKeys(key, entryKey)) { 943 // We found an existing entry. 944 945 // If the value disappeared, this entry is partially collected, 946 // and we should pretend like it doesn't exist. 947 V entryValue = s.getValue(e); 948 if (onlyIfAbsent && entryValue != null) { 949 return entryValue; 950 } 951 952 s.setValue(e, value); 953 return entryValue; 954 } 955 } 956 957 // Create a new entry. 958 ++modCount; 959 E newEntry = s.newEntry(key, hash, first); 960 s.setValue(newEntry, value); 961 table.set(index, newEntry); 962 this.count = count; // write-volatile 963 return null; 964 } finally { 965 unlock(); 966 } 967 } 968 969 /** 970 * Expands the table if possible. 971 */ 972 void expand() { 973 AtomicReferenceArray<E> oldTable = table; 974 int oldCapacity = oldTable.length(); 975 if (oldCapacity >= MAXIMUM_CAPACITY) { 976 return; 977 } 978 979 /* 980 * Reclassify nodes in each list to new Map. Because we are 981 * using power-of-two expansion, the elements from each bin 982 * must either stay at same index, or move with a power of two 983 * offset. We eliminate unnecessary node creation by catching 984 * cases where old nodes can be reused because their next 985 * fields won't change. Statistically, at the default 986 * threshold, only about one-sixth of them need cloning when 987 * a table doubles. The nodes they replace will be garbage 988 * collectable as soon as they are no longer referenced by any 989 * reader thread that may be in the midst of traversing table 990 * right now. 991 */ 992 993 Strategy<K, V, E> s = Impl.this.strategy; 994 AtomicReferenceArray<E> newTable = newEntryArray(oldCapacity << 1); 995 threshold = newTable.length() * 3 / 4; 996 int newMask = newTable.length() - 1; 997 for (int oldIndex = 0; oldIndex < oldCapacity; oldIndex++) { 998 // We need to guarantee that any existing reads of old Map can 999 // proceed. So we cannot yet null out each bin. 1000 E head = oldTable.get(oldIndex); 1001 1002 if (head != null) { 1003 E next = s.getNext(head); 1004 int headIndex = s.getHash(head) & newMask; 1005 1006 // Single node on list 1007 if (next == null) { 1008 newTable.set(headIndex, head); 1009 } else { 1010 // Reuse the consecutive sequence of nodes with the same target 1011 // index from the end of the list. tail points to the first 1012 // entry in the reusable list. 1013 E tail = head; 1014 int tailIndex = headIndex; 1015 for (E last = next; last != null; last = s.getNext(last)) { 1016 int newIndex = s.getHash(last) & newMask; 1017 if (newIndex != tailIndex) { 1018 // The index changed. We'll need to copy the previous entry. 1019 tailIndex = newIndex; 1020 tail = last; 1021 } 1022 } 1023 newTable.set(tailIndex, tail); 1024 1025 // Clone nodes leading up to the tail. 1026 for (E e = head; e != tail; e = s.getNext(e)) { 1027 K key = s.getKey(e); 1028 if (key != null) { 1029 int newIndex = s.getHash(e) & newMask; 1030 E newNext = newTable.get(newIndex); 1031 newTable.set(newIndex, s.copyEntry(key, e, newNext)); 1032 } else { 1033 // Key was reclaimed. Skip entry. 1034 } 1035 } 1036 } 1037 } 1038 } 1039 table = newTable; 1040 } 1041 1042 V remove(Object key, int hash) { 1043 Strategy<K, V, E> s = Impl.this.strategy; 1044 lock(); 1045 try { 1046 int count = this.count - 1; 1047 AtomicReferenceArray<E> table = this.table; 1048 int index = hash & (table.length() - 1); 1049 E first = table.get(index); 1050 1051 for (E e = first; e != null; e = s.getNext(e)) { 1052 K entryKey = s.getKey(e); 1053 if (s.getHash(e) == hash && entryKey != null 1054 && s.equalKeys(entryKey, key)) { 1055 V entryValue = strategy.getValue(e); 1056 // All entries following removed node can stay 1057 // in list, but all preceding ones need to be 1058 // cloned. 1059 ++modCount; 1060 E newFirst = s.getNext(e); 1061 for (E p = first; p != e; p = s.getNext(p)) { 1062 K pKey = s.getKey(p); 1063 if (pKey != null) { 1064 newFirst = s.copyEntry(pKey, p, newFirst); 1065 } else { 1066 // Key was reclaimed. Skip entry. 1067 } 1068 } 1069 table.set(index, newFirst); 1070 this.count = count; // write-volatile 1071 return entryValue; 1072 } 1073 } 1074 1075 return null; 1076 } finally { 1077 unlock(); 1078 } 1079 } 1080 1081 boolean remove(Object key, int hash, Object value) { 1082 Strategy<K, V, E> s = Impl.this.strategy; 1083 lock(); 1084 try { 1085 int count = this.count - 1; 1086 AtomicReferenceArray<E> table = this.table; 1087 int index = hash & (table.length() - 1); 1088 E first = table.get(index); 1089 1090 for (E e = first; e != null; e = s.getNext(e)) { 1091 K entryKey = s.getKey(e); 1092 if (s.getHash(e) == hash && entryKey != null 1093 && s.equalKeys(entryKey, key)) { 1094 V entryValue = strategy.getValue(e); 1095 if (value == entryValue || (value != null && entryValue != null 1096 && s.equalValues(entryValue, value))) { 1097 // All entries following removed node can stay 1098 // in list, but all preceding ones need to be 1099 // cloned. 1100 ++modCount; 1101 E newFirst = s.getNext(e); 1102 for (E p = first; p != e; p = s.getNext(p)) { 1103 K pKey = s.getKey(p); 1104 if (pKey != null) { 1105 newFirst = s.copyEntry(pKey, p, newFirst); 1106 } else { 1107 // Key was reclaimed. Skip entry. 1108 } 1109 } 1110 table.set(index, newFirst); 1111 this.count = count; // write-volatile 1112 return true; 1113 } else { 1114 return false; 1115 } 1116 } 1117 } 1118 1119 return false; 1120 } finally { 1121 unlock(); 1122 } 1123 } 1124 1125 public boolean removeEntry(E entry, int hash, V value) { 1126 Strategy<K, V, E> s = Impl.this.strategy; 1127 lock(); 1128 try { 1129 int count = this.count - 1; 1130 AtomicReferenceArray<E> table = this.table; 1131 int index = hash & (table.length() - 1); 1132 E first = table.get(index); 1133 1134 for (E e = first; e != null; e = s.getNext(e)) { 1135 if (s.getHash(e) == hash && entry.equals(e)) { 1136 V entryValue = s.getValue(e); 1137 if (entryValue == value || (value != null 1138 && s.equalValues(entryValue, value))) { 1139 // All entries following removed node can stay 1140 // in list, but all preceding ones need to be 1141 // cloned. 1142 ++modCount; 1143 E newFirst = s.getNext(e); 1144 for (E p = first; p != e; p = s.getNext(p)) { 1145 K pKey = s.getKey(p); 1146 if (pKey != null) { 1147 newFirst = s.copyEntry(pKey, p, newFirst); 1148 } else { 1149 // Key was reclaimed. Skip entry. 1150 } 1151 } 1152 table.set(index, newFirst); 1153 this.count = count; // write-volatile 1154 return true; 1155 } else { 1156 return false; 1157 } 1158 } 1159 } 1160 1161 return false; 1162 } finally { 1163 unlock(); 1164 } 1165 } 1166 1167 public boolean removeEntry(E entry, int hash) { 1168 Strategy<K, V, E> s = Impl.this.strategy; 1169 lock(); 1170 try { 1171 int count = this.count - 1; 1172 AtomicReferenceArray<E> table = this.table; 1173 int index = hash & (table.length() - 1); 1174 E first = table.get(index); 1175 1176 for (E e = first; e != null; e = s.getNext(e)) { 1177 if (s.getHash(e) == hash && entry.equals(e)) { 1178 // All entries following removed node can stay 1179 // in list, but all preceding ones need to be 1180 // cloned. 1181 ++modCount; 1182 E newFirst = s.getNext(e); 1183 for (E p = first; p != e; p = s.getNext(p)) { 1184 K pKey = s.getKey(p); 1185 if (pKey != null) { 1186 newFirst = s.copyEntry(pKey, p, newFirst); 1187 } else { 1188 // Key was reclaimed. Skip entry. 1189 } 1190 } 1191 table.set(index, newFirst); 1192 this.count = count; // write-volatile 1193 return true; 1194 } 1195 } 1196 1197 return false; 1198 } finally { 1199 unlock(); 1200 } 1201 } 1202 1203 void clear() { 1204 if (count != 0) { 1205 lock(); 1206 try { 1207 AtomicReferenceArray<E> table = this.table; 1208 for (int i = 0; i < table.length(); i++) { 1209 table.set(i, null); 1210 } 1211 ++modCount; 1212 count = 0; // write-volatile 1213 } finally { 1214 unlock(); 1215 } 1216 } 1217 } 1218 } 1219 1220 /* ---------------- Public operations -------------- */ 1221 1222 /** 1223 * Returns {@code true} if this map contains no key-value mappings. 1224 * 1225 * @return {@code true} if this map contains no key-value mappings 1226 */ 1227 @Override public boolean isEmpty() { 1228 final Segment[] segments = this.segments; 1229 /* 1230 * We keep track of per-segment modCounts to avoid ABA 1231 * problems in which an element in one segment was added and 1232 * in another removed during traversal, in which case the 1233 * table was never actually empty at any point. Note the 1234 * similar use of modCounts in the size() and containsValue() 1235 * methods, which are the only other methods also susceptible 1236 * to ABA problems. 1237 */ 1238 int[] mc = new int[segments.length]; 1239 int mcsum = 0; 1240 for (int i = 0; i < segments.length; ++i) { 1241 if (segments[i].count != 0) { 1242 return false; 1243 } else { 1244 mcsum += mc[i] = segments[i].modCount; 1245 } 1246 } 1247 // If mcsum happens to be zero, then we know we got a snapshot 1248 // before any modifications at all were made. This is 1249 // probably common enough to bother tracking. 1250 if (mcsum != 0) { 1251 for (int i = 0; i < segments.length; ++i) { 1252 if (segments[i].count != 0 || 1253 mc[i] != segments[i].modCount) { 1254 return false; 1255 } 1256 } 1257 } 1258 return true; 1259 } 1260 1261 /** 1262 * Returns the number of key-value mappings in this map. If the map 1263 * contains more than {@code Integer.MAX_VALUE} elements, returns 1264 * {@code Integer.MAX_VALUE}. 1265 * 1266 * @return the number of key-value mappings in this map 1267 */ 1268 @Override public int size() { 1269 final Segment[] segments = this.segments; 1270 long sum = 0; 1271 long check = 0; 1272 int[] mc = new int[segments.length]; 1273 // Try a few times to get accurate count. On failure due to 1274 // continuous async changes in table, resort to locking. 1275 for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) { 1276 check = 0; 1277 sum = 0; 1278 int mcsum = 0; 1279 for (int i = 0; i < segments.length; ++i) { 1280 sum += segments[i].count; 1281 mcsum += mc[i] = segments[i].modCount; 1282 } 1283 if (mcsum != 0) { 1284 for (int i = 0; i < segments.length; ++i) { 1285 check += segments[i].count; 1286 if (mc[i] != segments[i].modCount) { 1287 check = -1; // force retry 1288 break; 1289 } 1290 } 1291 } 1292 if (check == sum) { 1293 break; 1294 } 1295 } 1296 if (check != sum) { // Resort to locking all segments 1297 sum = 0; 1298 for (Segment segment : segments) { 1299 segment.lock(); 1300 } 1301 for (Segment segment : segments) { 1302 sum += segment.count; 1303 } 1304 for (Segment segment : segments) { 1305 segment.unlock(); 1306 } 1307 } 1308 if (sum > Integer.MAX_VALUE) { 1309 return Integer.MAX_VALUE; 1310 } else { 1311 return (int) sum; 1312 } 1313 } 1314 1315 /** 1316 * Returns the value to which the specified key is mapped, or {@code null} 1317 * if this map contains no mapping for the key. 1318 * 1319 * <p>More formally, if this map contains a mapping from a key {@code k} to 1320 * a value {@code v} such that {@code key.equals(k)}, then this method 1321 * returns {@code v}; otherwise it returns {@code null}. (There can be at 1322 * most one such mapping.) 1323 * 1324 * @throws NullPointerException if the specified key is null 1325 */ 1326 @Override public V get(Object key) { 1327 if (key == null) { 1328 throw new NullPointerException("key"); 1329 } 1330 int hash = hash(key); 1331 return segmentFor(hash).get(key, hash); 1332 } 1333 1334 /** 1335 * Tests if the specified object is a key in this table. 1336 * 1337 * @param key possible key 1338 * @return {@code true} if and only if the specified object is a key in 1339 * this table, as determined by the {@code equals} method; 1340 * {@code false} otherwise. 1341 * @throws NullPointerException if the specified key is null 1342 */ 1343 @Override public boolean containsKey(Object key) { 1344 if (key == null) { 1345 throw new NullPointerException("key"); 1346 } 1347 int hash = hash(key); 1348 return segmentFor(hash).containsKey(key, hash); 1349 } 1350 1351 /** 1352 * Returns {@code true} if this map maps one or more keys to the specified 1353 * value. Note: This method requires a full internal traversal of the hash 1354 * table, and so is much slower than method {@code containsKey}. 1355 * 1356 * @param value value whose presence in this map is to be tested 1357 * @return {@code true} if this map maps one or more keys to the specified 1358 * value 1359 * @throws NullPointerException if the specified value is null 1360 */ 1361 @Override public boolean containsValue(Object value) { 1362 if (value == null) { 1363 throw new NullPointerException("value"); 1364 } 1365 1366 // See explanation of modCount use above 1367 1368 final Segment[] segments = this.segments; 1369 int[] mc = new int[segments.length]; 1370 1371 // Try a few times without locking 1372 for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) { 1373 int mcsum = 0; 1374 for (int i = 0; i < segments.length; ++i) { 1375 @SuppressWarnings("UnusedDeclaration") 1376 int c = segments[i].count; 1377 mcsum += mc[i] = segments[i].modCount; 1378 if (segments[i].containsValue(value)) { 1379 return true; 1380 } 1381 } 1382 boolean cleanSweep = true; 1383 if (mcsum != 0) { 1384 for (int i = 0; i < segments.length; ++i) { 1385 @SuppressWarnings("UnusedDeclaration") 1386 int c = segments[i].count; 1387 if (mc[i] != segments[i].modCount) { 1388 cleanSweep = false; 1389 break; 1390 } 1391 } 1392 } 1393 if (cleanSweep) { 1394 return false; 1395 } 1396 } 1397 // Resort to locking all segments 1398 for (Segment segment : segments) { 1399 segment.lock(); 1400 } 1401 boolean found = false; 1402 try { 1403 for (Segment segment : segments) { 1404 if (segment.containsValue(value)) { 1405 found = true; 1406 break; 1407 } 1408 } 1409 } finally { 1410 for (Segment segment : segments) { 1411 segment.unlock(); 1412 } 1413 } 1414 return found; 1415 } 1416 1417 /** 1418 * Maps the specified key to the specified value in this table. Neither the 1419 * key nor the value can be null. 1420 * 1421 * <p> The value can be retrieved by calling the {@code get} method with a 1422 * key that is equal to the original key. 1423 * 1424 * @param key key with which the specified value is to be associated 1425 * @param value value to be associated with the specified key 1426 * @return the previous value associated with {@code key}, or {@code null} 1427 * if there was no mapping for {@code key} 1428 * @throws NullPointerException if the specified key or value is null 1429 */ 1430 @Override public V put(K key, V value) { 1431 if (key == null) { 1432 throw new NullPointerException("key"); 1433 } 1434 if (value == null) { 1435 throw new NullPointerException("value"); 1436 } 1437 int hash = hash(key); 1438 return segmentFor(hash).put(key, hash, value, false); 1439 } 1440 1441 /** 1442 * {@inheritDoc} 1443 * 1444 * @return the previous value associated with the specified key, or 1445 * {@code null} if there was no mapping for the key 1446 * @throws NullPointerException if the specified key or value is null 1447 */ 1448 public V putIfAbsent(K key, V value) { 1449 if (key == null) { 1450 throw new NullPointerException("key"); 1451 } 1452 if (value == null) { 1453 throw new NullPointerException("value"); 1454 } 1455 int hash = hash(key); 1456 return segmentFor(hash).put(key, hash, value, true); 1457 } 1458 1459 /** 1460 * Copies all of the mappings from the specified map to this one. These 1461 * mappings replace any mappings that this map had for any of the keys 1462 * currently in the specified map. 1463 * 1464 * @param m mappings to be stored in this map 1465 */ 1466 @Override public void putAll(Map<? extends K, ? extends V> m) { 1467 for (Entry<? extends K, ? extends V> e : m.entrySet()) { 1468 put(e.getKey(), e.getValue()); 1469 } 1470 } 1471 1472 /** 1473 * Removes the key (and its corresponding value) from this map. This method 1474 * does nothing if the key is not in the map. 1475 * 1476 * @param key the key that needs to be removed 1477 * @return the previous value associated with {@code key}, or {@code null} 1478 * if there was no mapping for {@code key} 1479 * @throws NullPointerException if the specified key is null 1480 */ 1481 @Override public V remove(Object key) { 1482 if (key == null) { 1483 throw new NullPointerException("key"); 1484 } 1485 int hash = hash(key); 1486 return segmentFor(hash).remove(key, hash); 1487 } 1488 1489 /** 1490 * {@inheritDoc} 1491 * 1492 * @throws NullPointerException if the specified key is null 1493 */ 1494 public boolean remove(Object key, Object value) { 1495 if (key == null) { 1496 throw new NullPointerException("key"); 1497 } 1498 int hash = hash(key); 1499 return segmentFor(hash).remove(key, hash, value); 1500 } 1501 1502 /** 1503 * {@inheritDoc} 1504 * 1505 * @throws NullPointerException if any of the arguments are null 1506 */ 1507 public boolean replace(K key, V oldValue, V newValue) { 1508 if (key == null) { 1509 throw new NullPointerException("key"); 1510 } 1511 if (oldValue == null) { 1512 throw new NullPointerException("oldValue"); 1513 } 1514 if (newValue == null) { 1515 throw new NullPointerException("newValue"); 1516 } 1517 int hash = hash(key); 1518 return segmentFor(hash).replace(key, hash, oldValue, newValue); 1519 } 1520 1521 /** 1522 * {@inheritDoc} 1523 * 1524 * @return the previous value associated with the specified key, or 1525 * {@code null} if there was no mapping for the key 1526 * @throws NullPointerException if the specified key or value is null 1527 */ 1528 public V replace(K key, V value) { 1529 if (key == null) { 1530 throw new NullPointerException("key"); 1531 } 1532 if (value == null) { 1533 throw new NullPointerException("value"); 1534 } 1535 int hash = hash(key); 1536 return segmentFor(hash).replace(key, hash, value); 1537 } 1538 1539 /** 1540 * Removes all of the mappings from this map. 1541 */ 1542 @Override public void clear() { 1543 for (Segment segment : segments) { 1544 segment.clear(); 1545 } 1546 } 1547 1548 Set<K> keySet; 1549 1550 /** 1551 * Returns a {@link java.util.Set} view of the keys contained in this map. 1552 * The set is backed by the map, so changes to the map are reflected in the 1553 * set, and vice-versa. The set supports element removal, which removes the 1554 * corresponding mapping from this map, via the {@code Iterator.remove}, 1555 * {@code Set.remove}, {@code removeAll}, {@code retainAll}, and 1556 * {@code clear} operations. It does not support the {@code add} or 1557 * {@code addAll} operations. 1558 * 1559 * <p>The view's {@code iterator} is a "weakly consistent" iterator that 1560 * will never throw {@link java.util.ConcurrentModificationException}, and 1561 * guarantees to traverse elements as they existed upon construction of the 1562 * iterator, and may (but is not guaranteed to) reflect any modifications 1563 * subsequent to construction. 1564 */ 1565 @Override public Set<K> keySet() { 1566 Set<K> ks = keySet; 1567 return (ks != null) ? ks : (keySet = new KeySet()); 1568 } 1569 1570 Collection<V> values; 1571 1572 /** 1573 * Returns a {@link java.util.Collection} view of the values contained in 1574 * this map. The collection is backed by the map, so changes to the map are 1575 * reflected in the collection, and vice-versa. The collection supports 1576 * element removal, which removes the corresponding mapping from this map, 1577 * via the {@code Iterator.remove}, {@code Collection.remove}, 1578 * {@code removeAll}, {@code retainAll}, and {@code clear} operations. It 1579 * does not support the {@code add} or {@code addAll} operations. 1580 * 1581 * <p>The view's {@code iterator} is a "weakly consistent" iterator that 1582 * will never throw {@link java.util.ConcurrentModificationException}, and 1583 * guarantees to traverse elements as they existed upon construction of the 1584 * iterator, and may (but is not guaranteed to) reflect any modifications 1585 * subsequent to construction. 1586 */ 1587 @Override public Collection<V> values() { 1588 Collection<V> vs = values; 1589 return (vs != null) ? vs : (values = new Values()); 1590 } 1591 1592 Set<Entry<K, V>> entrySet; 1593 1594 /** 1595 * Returns a {@link java.util.Set} view of the mappings contained in this 1596 * map. The set is backed by the map, so changes to the map are reflected in 1597 * the set, and vice-versa. The set supports element removal, which removes 1598 * the corresponding mapping from the map, via the {@code Iterator.remove}, 1599 * {@code Set.remove}, {@code removeAll}, {@code retainAll}, and 1600 * {@code clear} operations. It does not support the {@code add} or 1601 * {@code addAll} operations. 1602 * 1603 * <p>The view's {@code iterator} is a "weakly consistent" iterator that 1604 * will never throw {@link java.util.ConcurrentModificationException}, and 1605 * guarantees to traverse elements as they existed upon construction of the 1606 * iterator, and may (but is not guaranteed to) reflect any modifications 1607 * subsequent to construction. 1608 */ 1609 @Override public Set<Entry<K, V>> entrySet() { 1610 Set<Entry<K, V>> es = entrySet; 1611 return (es != null) ? es : (entrySet = new EntrySet()); 1612 } 1613 1614 /* ---------------- Iterator Support -------------- */ 1615 1616 abstract class HashIterator { 1617 1618 int nextSegmentIndex; 1619 int nextTableIndex; 1620 AtomicReferenceArray<E> currentTable; 1621 E nextEntry; 1622 WriteThroughEntry nextExternal; 1623 WriteThroughEntry lastReturned; 1624 1625 HashIterator() { 1626 nextSegmentIndex = segments.length - 1; 1627 nextTableIndex = -1; 1628 advance(); 1629 } 1630 1631 public boolean hasMoreElements() { 1632 return hasNext(); 1633 } 1634 1635 final void advance() { 1636 nextExternal = null; 1637 1638 if (nextInChain()) { 1639 return; 1640 } 1641 1642 if (nextInTable()) { 1643 return; 1644 } 1645 1646 while (nextSegmentIndex >= 0) { 1647 Segment seg = segments[nextSegmentIndex--]; 1648 if (seg.count != 0) { 1649 currentTable = seg.table; 1650 nextTableIndex = currentTable.length() - 1; 1651 if (nextInTable()) { 1652 return; 1653 } 1654 } 1655 } 1656 } 1657 1658 /** 1659 * Finds the next entry in the current chain. Returns true if an entry 1660 * was found. 1661 */ 1662 boolean nextInChain() { 1663 Strategy<K, V, E> s = Impl.this.strategy; 1664 if (nextEntry != null) { 1665 for (nextEntry = s.getNext(nextEntry); nextEntry != null; 1666 nextEntry = s.getNext(nextEntry)) { 1667 if (advanceTo(nextEntry)) { 1668 return true; 1669 } 1670 } 1671 } 1672 return false; 1673 } 1674 1675 /** 1676 * Finds the next entry in the current table. Returns true if an entry 1677 * was found. 1678 */ 1679 boolean nextInTable() { 1680 while (nextTableIndex >= 0) { 1681 if ((nextEntry = currentTable.get(nextTableIndex--)) != null) { 1682 if (advanceTo(nextEntry) || nextInChain()) { 1683 return true; 1684 } 1685 } 1686 } 1687 return false; 1688 } 1689 1690 /** 1691 * Advances to the given entry. Returns true if the entry was valid, 1692 * false if it should be skipped. 1693 */ 1694 boolean advanceTo(E entry) { 1695 Strategy<K, V, E> s = Impl.this.strategy; 1696 K key = s.getKey(entry); 1697 V value = s.getValue(entry); 1698 if (key != null && value != null) { 1699 nextExternal = new WriteThroughEntry(key, value); 1700 return true; 1701 } else { 1702 // Skip partially reclaimed entry. 1703 return false; 1704 } 1705 } 1706 1707 public boolean hasNext() { 1708 return nextExternal != null; 1709 } 1710 1711 WriteThroughEntry nextEntry() { 1712 if (nextExternal == null) { 1713 throw new NoSuchElementException(); 1714 } 1715 lastReturned = nextExternal; 1716 advance(); 1717 return lastReturned; 1718 } 1719 1720 public void remove() { 1721 if (lastReturned == null) { 1722 throw new IllegalStateException(); 1723 } 1724 Impl.this.remove(lastReturned.getKey()); 1725 lastReturned = null; 1726 } 1727 } 1728 1729 final class KeyIterator extends HashIterator implements Iterator<K> { 1730 1731 public K next() { 1732 return super.nextEntry().getKey(); 1733 } 1734 } 1735 1736 final class ValueIterator extends HashIterator implements Iterator<V> { 1737 1738 public V next() { 1739 return super.nextEntry().getValue(); 1740 } 1741 } 1742 1743 /** 1744 * Custom Entry class used by EntryIterator.next(), that relays setValue 1745 * changes to the underlying map. 1746 */ 1747 final class WriteThroughEntry extends AbstractMapEntry<K, V> { 1748 final K key; 1749 V value; 1750 1751 WriteThroughEntry(K key, V value) { 1752 this.key = key; 1753 this.value = value; 1754 } 1755 1756 @Override public K getKey() { 1757 return key; 1758 } 1759 1760 @Override public V getValue() { 1761 return value; 1762 } 1763 1764 /** 1765 * Set our entry's value and write through to the map. The value to 1766 * return is somewhat arbitrary here. Since a WriteThroughEntry does not 1767 * necessarily track asynchronous changes, the most recent "previous" 1768 * value could be different from what we return (or could even have been 1769 * removed in which case the put will re-establish). We do not and 1770 * cannot guarantee more. 1771 */ 1772 @Override public V setValue(V value) { 1773 if (value == null) { 1774 throw new NullPointerException(); 1775 } 1776 V oldValue = Impl.this.put(getKey(), value); 1777 this.value = value; 1778 return oldValue; 1779 } 1780 } 1781 1782 final class EntryIterator extends HashIterator 1783 implements Iterator<Entry<K, V>> { 1784 1785 public Entry<K, V> next() { 1786 return nextEntry(); 1787 } 1788 } 1789 1790 final class KeySet extends AbstractSet<K> { 1791 1792 @Override public Iterator<K> iterator() { 1793 return new KeyIterator(); 1794 } 1795 1796 @Override public int size() { 1797 return Impl.this.size(); 1798 } 1799 1800 @Override public boolean isEmpty() { 1801 return Impl.this.isEmpty(); 1802 } 1803 1804 @Override public boolean contains(Object o) { 1805 return Impl.this.containsKey(o); 1806 } 1807 1808 @Override public boolean remove(Object o) { 1809 return Impl.this.remove(o) != null; 1810 } 1811 1812 @Override public void clear() { 1813 Impl.this.clear(); 1814 } 1815 } 1816 1817 final class Values extends AbstractCollection<V> { 1818 1819 @Override public Iterator<V> iterator() { 1820 return new ValueIterator(); 1821 } 1822 1823 @Override public int size() { 1824 return Impl.this.size(); 1825 } 1826 1827 @Override public boolean isEmpty() { 1828 return Impl.this.isEmpty(); 1829 } 1830 1831 @Override public boolean contains(Object o) { 1832 return Impl.this.containsValue(o); 1833 } 1834 1835 @Override public void clear() { 1836 Impl.this.clear(); 1837 } 1838 } 1839 1840 final class EntrySet extends AbstractSet<Entry<K, V>> { 1841 1842 @Override public Iterator<Entry<K, V>> iterator() { 1843 return new EntryIterator(); 1844 } 1845 1846 @Override public boolean contains(Object o) { 1847 if (!(o instanceof Entry)) { 1848 return false; 1849 } 1850 Entry<?, ?> e = (Entry<?, ?>) o; 1851 Object key = e.getKey(); 1852 if (key == null) { 1853 return false; 1854 } 1855 V v = Impl.this.get(key); 1856 1857 return v != null && strategy.equalValues(v, e.getValue()); 1858 } 1859 1860 @Override public boolean remove(Object o) { 1861 if (!(o instanceof Entry)) { 1862 return false; 1863 } 1864 Entry<?, ?> e = (Entry<?, ?>) o; 1865 Object key = e.getKey(); 1866 return key != null && Impl.this.remove(key, e.getValue()); 1867 } 1868 1869 @Override public int size() { 1870 return Impl.this.size(); 1871 } 1872 1873 @Override public boolean isEmpty() { 1874 return Impl.this.isEmpty(); 1875 } 1876 1877 @Override public void clear() { 1878 Impl.this.clear(); 1879 } 1880 } 1881 1882 /* ---------------- Serialization Support -------------- */ 1883 1884 private static final long serialVersionUID = 1; 1885 1886 private void writeObject(java.io.ObjectOutputStream out) 1887 throws IOException { 1888 out.writeInt(size()); 1889 out.writeInt(segments.length); // concurrencyLevel 1890 out.writeObject(strategy); 1891 for (Entry<K, V> entry : entrySet()) { 1892 out.writeObject(entry.getKey()); 1893 out.writeObject(entry.getValue()); 1894 } 1895 out.writeObject(null); // terminate entries 1896 } 1897 1898 /** 1899 * Fields used during deserialization. We use a nested class so we don't 1900 * load them until we need them. We need to use reflection to set final 1901 * fields outside of the constructor. 1902 */ 1903 static class Fields { 1904 1905 static final Field segmentShift = findField("segmentShift"); 1906 static final Field segmentMask = findField("segmentMask"); 1907 static final Field segments = findField("segments"); 1908 static final Field strategy = findField("strategy"); 1909 1910 static Field findField(String name) { 1911 try { 1912 Field f = Impl.class.getDeclaredField(name); 1913 f.setAccessible(true); 1914 return f; 1915 } catch (NoSuchFieldException e) { 1916 throw new AssertionError(e); 1917 } 1918 } 1919 } 1920 1921 @SuppressWarnings("unchecked") 1922 private void readObject(java.io.ObjectInputStream in) 1923 throws IOException, ClassNotFoundException { 1924 try { 1925 int initialCapacity = in.readInt(); 1926 int concurrencyLevel = in.readInt(); 1927 Strategy<K, V, E> strategy = (Strategy<K, V, E>) in.readObject(); 1928 1929 if (concurrencyLevel > MAX_SEGMENTS) { 1930 concurrencyLevel = MAX_SEGMENTS; 1931 } 1932 1933 // Find power-of-two sizes best matching arguments 1934 int segmentShift = 0; 1935 int segmentCount = 1; 1936 while (segmentCount < concurrencyLevel) { 1937 ++segmentShift; 1938 segmentCount <<= 1; 1939 } 1940 Fields.segmentShift.set(this, 32 - segmentShift); 1941 Fields.segmentMask.set(this, segmentCount - 1); 1942 Fields.segments.set(this, newSegmentArray(segmentCount)); 1943 1944 if (initialCapacity > MAXIMUM_CAPACITY) { 1945 initialCapacity = MAXIMUM_CAPACITY; 1946 } 1947 1948 int segmentCapacity = initialCapacity / segmentCount; 1949 if (segmentCapacity * segmentCount < initialCapacity) { 1950 ++segmentCapacity; 1951 } 1952 1953 int segmentSize = 1; 1954 while (segmentSize < segmentCapacity) { 1955 segmentSize <<= 1; 1956 } 1957 for (int i = 0; i < this.segments.length; ++i) { 1958 this.segments[i] = new Segment(segmentSize); 1959 } 1960 1961 Fields.strategy.set(this, strategy); 1962 1963 while (true) { 1964 K key = (K) in.readObject(); 1965 if (key == null) { 1966 break; // terminator 1967 } 1968 V value = (V) in.readObject(); 1969 put(key, value); 1970 } 1971 } catch (IllegalAccessException e) { 1972 throw new AssertionError(e); 1973 } 1974 } 1975 } 1976 1977 static class ComputingImpl<K, V, E> extends Impl<K, V, E> { 1978 1979 static final long serialVersionUID = 0; 1980 1981 final ComputingStrategy<K, V, E> computingStrategy; 1982 final Function<? super K, ? extends V> computer; 1983 1984 /** 1985 * Creates a new, empty map with the specified strategy, initial capacity, 1986 * load factor and concurrency level. 1987 */ 1988 ComputingImpl(ComputingStrategy<K, V, E> strategy, Builder builder, 1989 Function<? super K, ? extends V> computer) { 1990 super(strategy, builder); 1991 this.computingStrategy = strategy; 1992 this.computer = computer; 1993 } 1994 1995 @Override public V get(Object k) { 1996 /* 1997 * This cast isn't safe, but we can rely on the fact that K is almost 1998 * always passed to Map.get(), and tools like IDEs and Findbugs can 1999 * catch situations where this isn't the case. 2000 * 2001 * The alternative is to add an overloaded method, but the chances of 2002 * a user calling get() instead of the new API and the risks inherent 2003 * in adding a new API outweigh this little hole. 2004 */ 2005 @SuppressWarnings("unchecked") 2006 K key = (K) k; 2007 2008 if (key == null) { 2009 throw new NullPointerException("key"); 2010 } 2011 2012 int hash = hash(key); 2013 Segment segment = segmentFor(hash); 2014 outer: while (true) { 2015 E entry = segment.getEntry(key, hash); 2016 if (entry == null) { 2017 boolean created = false; 2018 segment.lock(); 2019 try { 2020 // Try again--an entry could have materialized in the interim. 2021 entry = segment.getEntry(key, hash); 2022 if (entry == null) { 2023 // Create a new entry. 2024 created = true; 2025 int count = segment.count; 2026 if (count++ > segment.threshold) { // ensure capacity 2027 segment.expand(); 2028 } 2029 AtomicReferenceArray<E> table = segment.table; 2030 int index = hash & (table.length() - 1); 2031 E first = table.get(index); 2032 ++segment.modCount; 2033 entry = computingStrategy.newEntry(key, hash, first); 2034 table.set(index, entry); 2035 segment.count = count; // write-volatile 2036 } 2037 } finally { 2038 segment.unlock(); 2039 } 2040 2041 if (created) { 2042 // This thread solely created the entry. 2043 boolean success = false; 2044 try { 2045 V value = computingStrategy.compute(key, entry, computer); 2046 if (value == null) { 2047 throw new NullPointerException( 2048 "compute() returned null unexpectedly"); 2049 } 2050 success = true; 2051 return value; 2052 } finally { 2053 if (!success) { 2054 segment.removeEntry(entry, hash); 2055 } 2056 } 2057 } 2058 } 2059 2060 // The entry already exists. Wait for the computation. 2061 boolean interrupted = false; 2062 try { 2063 while (true) { 2064 try { 2065 V value = computingStrategy.waitForValue(entry); 2066 if (value == null) { 2067 // Purge entry and try again. 2068 segment.removeEntry(entry, hash); 2069 continue outer; 2070 } 2071 return value; 2072 } catch (InterruptedException e) { 2073 interrupted = true; 2074 } 2075 } 2076 } finally { 2077 if (interrupted) { 2078 Thread.currentThread().interrupt(); 2079 } 2080 } 2081 } 2082 } 2083 } 2084 2085 /** 2086 * A basic, no-frills implementation of {@code Strategy} using {@link 2087 * SimpleInternalEntry}. Intended to be subclassed to provide customized 2088 * behavior. For example, the following creates a map that uses byte arrays as 2089 * keys: <pre> {@code 2090 * 2091 * return new CustomConcurrentHashMap.Builder().buildMap( 2092 * new SimpleStrategy<byte[], V>() { 2093 * public int hashKey(Object key) { 2094 * return Arrays.hashCode((byte[]) key); 2095 * } 2096 * public boolean equalKeys(byte[] a, Object b) { 2097 * return Arrays.equals(a, (byte[]) b); 2098 * } 2099 * });}</pre> 2100 * 2101 * With nothing overridden, it yields map behavior equivalent to that of 2102 * {@link ConcurrentHashMap}. 2103 */ 2104 static class SimpleStrategy<K, V> 2105 implements Strategy<K, V, SimpleInternalEntry<K, V>> { 2106 public SimpleInternalEntry<K, V> newEntry( 2107 K key, int hash, SimpleInternalEntry<K, V> next) { 2108 return new SimpleInternalEntry<K, V>(key, hash, null, next); 2109 } 2110 public SimpleInternalEntry<K, V> copyEntry(K key, 2111 SimpleInternalEntry<K, V> original, SimpleInternalEntry<K, V> next) { 2112 return new SimpleInternalEntry<K, V>( 2113 key, original.hash, original.value, next); 2114 } 2115 public void setValue(SimpleInternalEntry<K, V> entry, V value) { 2116 entry.value = value; 2117 } 2118 public V getValue(SimpleInternalEntry<K, V> entry) { 2119 return entry.value; 2120 } 2121 public boolean equalKeys(K a, Object b) { 2122 return a.equals(b); 2123 } 2124 public boolean equalValues(V a, Object b) { 2125 return a.equals(b); 2126 } 2127 public int hashKey(Object key) { 2128 return key.hashCode(); 2129 } 2130 public K getKey(SimpleInternalEntry<K, V> entry) { 2131 return entry.key; 2132 } 2133 public SimpleInternalEntry<K, V> getNext(SimpleInternalEntry<K, V> entry) { 2134 return entry.next; 2135 } 2136 public int getHash(SimpleInternalEntry<K, V> entry) { 2137 return entry.hash; 2138 } 2139 public void setInternals( 2140 Internals<K, V, SimpleInternalEntry<K, V>> internals) { 2141 // ignore? 2142 } 2143 } 2144 2145 /** 2146 * A basic, no-frills entry class used by {@link SimpleInternalEntry}. 2147 */ 2148 static class SimpleInternalEntry<K, V> { 2149 final K key; 2150 final int hash; 2151 final SimpleInternalEntry<K, V> next; 2152 volatile V value; 2153 SimpleInternalEntry( 2154 K key, int hash, @Nullable V value, SimpleInternalEntry<K, V> next) { 2155 this.key = key; 2156 this.hash = hash; 2157 this.value = value; 2158 this.next = next; 2159 } 2160 } 2161 } 2162