001 package railo.commons.util.mod; 002 import java.util.concurrent.ConcurrentMap; 003 import java.util.concurrent.locks.*; 004 import java.util.*; 005 import java.io.Serializable; 006 import java.io.IOException; 007 import java.io.ObjectInputStream; 008 import java.io.ObjectOutputStream; 009 010 import railo.runtime.exp.PageException; 011 import railo.runtime.type.Null; 012 013 /** 014 * A hash table supporting full concurrency of retrievals and 015 * adjustable expected concurrency for updates. This class obeys the 016 * same functional specification as {@link java.util.Hashtable}, and 017 * includes versions of methods corresponding to each method of 018 * <tt>Hashtable</tt>. However, even though all operations are 019 * thread-safe, retrieval operations do <em>not</em> entail locking, 020 * and there is <em>not</em> any support for locking the entire table 021 * in a way that prevents all access. This class is fully 022 * interoperable with <tt>Hashtable</tt> in programs that rely on its 023 * thread safety but not on its synchronization details. 024 * 025 * <p> Retrieval operations (including <tt>get</tt>) generally do not 026 * block, so may overlap with update operations (including 027 * <tt>put</tt> and <tt>remove</tt>). Retrievals reflect the results 028 * of the most recently <em>completed</em> update operations holding 029 * upon their onset. For aggregate operations such as <tt>putAll</tt> 030 * and <tt>clear</tt>, concurrent retrievals may reflect insertion or 031 * removal of only some entries. Similarly, Iterators and 032 * Enumerations return elements reflecting the state of the hash table 033 * at some point at or since the creation of the iterator/enumeration. 034 * They do <em>not</em> throw {@link ConcurrentModificationException}. 035 * However, iterators are designed to be used by only one thread at a time. 036 * 037 * <p> The allowed concurrency among update operations is guided by 038 * the optional <tt>concurrencyLevel</tt> constructor argument 039 * (default <tt>16</tt>), which is used as a hint for internal sizing. The 040 * table is internally partitioned to try to permit the indicated 041 * number of concurrent updates without contention. Because placement 042 * in hash tables is essentially random, the actual concurrency will 043 * vary. Ideally, you should choose a value to accommodate as many 044 * threads as will ever concurrently modify the table. Using a 045 * significantly higher value than you need can waste space and time, 046 * and a significantly lower value can lead to thread contention. But 047 * overestimates and underestimates within an order of magnitude do 048 * not usually have much noticeable impact. A value of one is 049 * appropriate when it is known that only one thread will modify and 050 * all others will only read. Also, resizing this or any other kind of 051 * hash table is a relatively slow operation, so, when possible, it is 052 * a good idea to provide estimates of expected table sizes in 053 * constructors. 054 * 055 * <p>This class and its views and iterators implement all of the 056 * <em>optional</em> methods of the {@link Map} and {@link Iterator} 057 * interfaces. 058 * 059 * <p> Like {@link Hashtable} but unlike {@link HashMap}, this class 060 * does <em>not</em> allow <tt>null</tt> to be used as a key or value. 061 * 062 * <p>This class is a member of the 063 * <a href="{@docRoot}/../technotes/guides/collections/index.html"> 064 * Java Collections Framework</a>. 065 * 066 * @since 1.5 067 * @author Doug Lea 068 * @param <K> the type of keys maintained by this map 069 * @param <V> the type of mapped values 070 */ 071 public class ConcurrentHashMapPro<K, V> extends AbstractMapPro<K, V> 072 implements Serializable { 073 private static final long serialVersionUID = 7249069246763182397L; 074 075 /* 076 * The basic strategy is to subdivide the table among Segments, 077 * each of which itself is a concurrently readable hash table. 078 */ 079 080 /* ---------------- Constants -------------- */ 081 082 /** 083 * The default initial capacity for this table, 084 * used when not otherwise specified in a constructor. 085 */ 086 static final int DEFAULT_INITIAL_CAPACITY = 16; 087 088 /** 089 * The default load factor for this table, used when not 090 * otherwise specified in a constructor. 091 */ 092 static final float DEFAULT_LOAD_FACTOR = 0.75f; 093 094 /** 095 * The default concurrency level for this table, used when not 096 * otherwise specified in a constructor. 097 */ 098 static final int DEFAULT_CONCURRENCY_LEVEL = 16; 099 100 /** 101 * The maximum capacity, used if a higher value is implicitly 102 * specified by either of the constructors with arguments. MUST 103 * be a power of two <= 1<<30 to ensure that entries are indexable 104 * using ints. 105 */ 106 static final int MAXIMUM_CAPACITY = 1 << 30; 107 108 /** 109 * The maximum number of segments to allow; used to bound 110 * constructor arguments. 111 */ 112 static final int MAX_SEGMENTS = 1 << 16; // slightly conservative 113 114 /** 115 * Number of unsynchronized retries in size and containsValue 116 * methods before resorting to locking. This is used to avoid 117 * unbounded retries if tables undergo continuous modification 118 * which would make it impossible to obtain an accurate result. 119 */ 120 static final int RETRIES_BEFORE_LOCK = 2; 121 122 /* ---------------- Fields -------------- */ 123 124 /** 125 * Mask value for indexing into segments. The upper bits of a 126 * key's hash code are used to choose the segment. 127 */ 128 final int segmentMask; 129 130 /** 131 * Shift value for indexing within segments. 132 */ 133 final int segmentShift; 134 135 /** 136 * The segments, each of which is a specialized hash table 137 */ 138 final Segment<K,V>[] segments; 139 140 transient Set<K> keySet; 141 transient Set<Map.Entry<K,V>> entrySet; 142 transient Collection<V> values; 143 144 /* ---------------- Small Utilities -------------- */ 145 146 /** 147 * Applies a supplemental hash function to a given hashCode, which 148 * defends against poor quality hash functions. This is critical 149 * because ConcurrentHashMap uses power-of-two length hash tables, 150 * that otherwise encounter collisions for hashCodes that do not 151 * differ in lower or upper bits. 152 */ 153 private static int hash(int h) { 154 // Spread bits to regularize both segment and index locations, 155 // using variant of single-word Wang/Jenkins hash. 156 h += (h << 15) ^ 0xffffcd7d; 157 h ^= (h >>> 10); 158 h += (h << 3); 159 h ^= (h >>> 6); 160 h += (h << 2) + (h << 14); 161 return h ^ (h >>> 16); 162 } 163 164 /** 165 * Returns the segment that should be used for key with given hash 166 * @param hash the hash code for the key 167 * @return the segment 168 */ 169 final Segment<K,V> segmentFor(int hash) { 170 return segments[(hash >>> segmentShift) & segmentMask]; 171 } 172 173 /* ---------------- Inner Classes -------------- */ 174 175 /** 176 * ConcurrentHashMap list entry. Note that this is never exported 177 * out as a user-visible Map.Entry. 178 * 179 * Because the value field is volatile, not final, it is legal wrt 180 * the Java Memory Model for an unsynchronized reader to see null 181 * instead of initial value when read via a data race. Although a 182 * reordering leading to this is not likely to ever actually 183 * occur, the Segment.readValueUnderLock method is used as a 184 * backup in case a null (pre-initialized) value is ever seen in 185 * an unsynchronized access method. 186 */ 187 static final class HashEntry<K,V> { 188 final K key; 189 final int hash; 190 volatile V value; 191 final HashEntry<K,V> next; 192 193 HashEntry(K key, int hash, HashEntry<K,V> next, V value) { 194 this.key = key; 195 this.hash = hash; 196 this.next = next; 197 this.value = value; 198 } 199 200 @SuppressWarnings("unchecked") 201 static final <K,V> HashEntry<K,V>[] newArray(int i) { 202 return new HashEntry[i]; 203 } 204 } 205 206 /** 207 * Segments are specialized versions of hash tables. This 208 * subclasses from ReentrantLock opportunistically, just to 209 * simplify some locking and avoid separate construction. 210 */ 211 static final class Segment<K,V> extends ReentrantLock implements Serializable { 212 /* 213 * Segments maintain a table of entry lists that are ALWAYS 214 * kept in a consistent state, so can be read without locking. 215 * Next fields of nodes are immutable (final). All list 216 * additions are performed at the front of each bin. This 217 * makes it easy to check changes, and also fast to traverse. 218 * When nodes would otherwise be changed, new nodes are 219 * created to replace them. This works well for hash tables 220 * since the bin lists tend to be short. (The average length 221 * is less than two for the default load factor threshold.) 222 * 223 * Read operations can thus proceed without locking, but rely 224 * on selected uses of volatiles to ensure that completed 225 * write operations performed by other threads are 226 * noticed. For most purposes, the "count" field, tracking the 227 * number of elements, serves as that volatile variable 228 * ensuring visibility. This is convenient because this field 229 * needs to be read in many read operations anyway: 230 * 231 * - All (unsynchronized) read operations must first read the 232 * "count" field, and should not look at table entries if 233 * it is 0. 234 * 235 * - All (synchronized) write operations should write to 236 * the "count" field after structurally changing any bin. 237 * The operations must not take any action that could even 238 * momentarily cause a concurrent read operation to see 239 * inconsistent data. This is made easier by the nature of 240 * the read operations in Map. For example, no operation 241 * can reveal that the table has grown but the threshold 242 * has not yet been updated, so there are no atomicity 243 * requirements for this with respect to reads. 244 * 245 * As a guide, all critical volatile reads and writes to the 246 * count field are marked in code comments. 247 */ 248 249 private static final long serialVersionUID = 2249069246763182397L; 250 251 /** 252 * The number of elements in this segment's region. 253 */ 254 transient volatile int count; 255 256 /** 257 * Number of updates that alter the size of the table. This is 258 * used during bulk-read methods to make sure they see a 259 * consistent snapshot: If modCounts change during a traversal 260 * of segments computing size or checking containsValue, then 261 * we might have an inconsistent view of state so (usually) 262 * must retry. 263 */ 264 transient int modCount; 265 266 /** 267 * The table is rehashed when its size exceeds this threshold. 268 * (The value of this field is always <tt>(int)(capacity * 269 * loadFactor)</tt>.) 270 */ 271 transient int threshold; 272 273 /** 274 * The per-segment table. 275 */ 276 transient volatile HashEntry<K,V>[] table; 277 278 /** 279 * The load factor for the hash table. Even though this value 280 * is same for all segments, it is replicated to avoid needing 281 * links to outer object. 282 * @serial 283 */ 284 final float loadFactor; 285 286 Segment(int initialCapacity, float lf) { 287 loadFactor = lf; 288 setTable(HashEntry.<K,V>newArray(initialCapacity)); 289 } 290 291 @SuppressWarnings("unchecked") 292 static final <K,V> Segment<K,V>[] newArray(int i) { 293 return new Segment[i]; 294 } 295 296 /** 297 * Sets table to new HashEntry array. 298 * Call only while holding lock or in constructor. 299 */ 300 void setTable(HashEntry<K,V>[] newTable) { 301 threshold = (int)(newTable.length * loadFactor); 302 table = newTable; 303 } 304 305 /** 306 * Returns properly casted first entry of bin for given hash. 307 */ 308 HashEntry<K,V> getFirst(int hash) { 309 HashEntry<K,V>[] tab = table; 310 return tab[hash & (tab.length - 1)]; 311 } 312 313 /** 314 * Reads value field of an entry under lock. Called if value 315 * field ever appears to be null. This is possible only if a 316 * compiler happens to reorder a HashEntry initialization with 317 * its table assignment, which is legal under memory model 318 * but is not known to ever occur. 319 */ 320 V readValueUnderLock(HashEntry<K,V> e) { 321 lock(); 322 try { 323 return e.value; 324 } finally { 325 unlock(); 326 } 327 } 328 329 /* Specialized implementations of map methods */ 330 331 V get(Object key, int hash) { 332 return get(key, hash, null); 333 } 334 335 V get(Object key, int hash, V defaultValue) { 336 if (count != 0) { // read-volatile 337 HashEntry<K,V> e = getFirst(hash); 338 while (e != null) { 339 if (e.hash == hash && key.equals(e.key)) { 340 V v = e.value; 341 if (v != null) 342 return v; 343 return readValueUnderLock(e); // recheck; possible unnecessary double check then value can be null 344 } 345 e = e.next; 346 } 347 } 348 return defaultValue; 349 } 350 351 V getE(Map map,Object key, int hash) throws PageException { 352 if (count != 0) { // read-volatile 353 HashEntry<K,V> e = getFirst(hash); 354 while (e != null) { 355 if (e.hash == hash && key.equals(e.key)) { 356 V v = e.value; 357 if (v != null) 358 return v; 359 return readValueUnderLock(e); // recheck; possible unnecessary double check then value can be null 360 } 361 e = e.next; 362 } 363 } 364 throw HashMapPro.invalidKey(map, key,false); 365 } 366 367 368 369 370 371 boolean containsKey(Object key, int hash) { 372 if (count != 0) { // read-volatile 373 HashEntry<K,V> e = getFirst(hash); 374 while (e != null) { 375 if (e.hash == hash && key.equals(e.key)) 376 return true; 377 e = e.next; 378 } 379 } 380 return false; 381 } 382 383 boolean containsValue(Object value) { 384 if (count != 0) { // read-volatile 385 HashEntry<K,V>[] tab = table; 386 int len = tab.length; 387 for (int i = 0 ; i < len; i++) { 388 for (HashEntry<K,V> e = tab[i]; e != null; e = e.next) { 389 V v = e.value; 390 if (v == null) // recheck ; possible unnecessary double check then value can be null 391 v = readValueUnderLock(e); 392 if(value==null){ 393 if(v==null) return true; 394 } 395 else if (value.equals(v)) 396 return true; 397 } 398 } 399 } 400 return false; 401 } 402 403 boolean replace(K key, int hash, V oldValue, V newValue) { 404 lock(); 405 try { 406 HashEntry<K,V> e = getFirst(hash); 407 while (e != null && (e.hash != hash || !key.equals(e.key))) 408 e = e.next; 409 410 boolean replaced = false; 411 if (e != null && oldValue.equals(e.value)) { 412 replaced = true; 413 e.value = newValue; 414 } 415 return replaced; 416 } finally { 417 unlock(); 418 } 419 } 420 421 V replace(K key, int hash, V newValue) { 422 lock(); 423 try { 424 HashEntry<K,V> e = getFirst(hash); 425 while (e != null && (e.hash != hash || !key.equals(e.key))) 426 e = e.next; 427 428 V oldValue = null; 429 if (e != null) { 430 oldValue = e.value; 431 e.value = newValue; 432 } 433 return oldValue; 434 } finally { 435 unlock(); 436 } 437 } 438 439 440 V put(K key, int hash, V value, boolean onlyIfAbsent) { 441 lock(); 442 try { 443 int c = count; 444 if (c++ > threshold) // ensure capacity 445 rehash(); 446 HashEntry<K,V>[] tab = table; 447 int index = hash & (tab.length - 1); 448 HashEntry<K,V> first = tab[index]; 449 HashEntry<K,V> e = first; 450 while (e != null && (e.hash != hash || !key.equals(e.key))) 451 e = e.next; 452 453 V oldValue; 454 if (e != null) { 455 oldValue = e.value; 456 if (!onlyIfAbsent) 457 e.value = value; 458 } 459 else { 460 oldValue = null; 461 ++modCount; 462 tab[index] = new HashEntry<K,V>(key, hash, first, value); 463 count = c; // write-volatile 464 } 465 return oldValue; 466 } finally { 467 unlock(); 468 } 469 } 470 471 void rehash() { 472 HashEntry<K,V>[] oldTable = table; 473 int oldCapacity = oldTable.length; 474 if (oldCapacity >= MAXIMUM_CAPACITY) 475 return; 476 477 /* 478 * Reclassify nodes in each list to new Map. Because we are 479 * using power-of-two expansion, the elements from each bin 480 * must either stay at same index, or move with a power of two 481 * offset. We eliminate unnecessary node creation by catching 482 * cases where old nodes can be reused because their next 483 * fields won't change. Statistically, at the default 484 * threshold, only about one-sixth of them need cloning when 485 * a table doubles. The nodes they replace will be garbage 486 * collectable as soon as they are no longer referenced by any 487 * reader thread that may be in the midst of traversing table 488 * right now. 489 */ 490 491 HashEntry<K,V>[] newTable = HashEntry.newArray(oldCapacity<<1); 492 threshold = (int)(newTable.length * loadFactor); 493 int sizeMask = newTable.length - 1; 494 for (int i = 0; i < oldCapacity ; i++) { 495 // We need to guarantee that any existing reads of old Map can 496 // proceed. So we cannot yet null out each bin. 497 HashEntry<K,V> e = oldTable[i]; 498 499 if (e != null) { 500 HashEntry<K,V> next = e.next; 501 int idx = e.hash & sizeMask; 502 503 // Single node on list 504 if (next == null) 505 newTable[idx] = e; 506 507 else { 508 // Reuse trailing consecutive sequence at same slot 509 HashEntry<K,V> lastRun = e; 510 int lastIdx = idx; 511 for (HashEntry<K,V> last = next; 512 last != null; 513 last = last.next) { 514 int k = last.hash & sizeMask; 515 if (k != lastIdx) { 516 lastIdx = k; 517 lastRun = last; 518 } 519 } 520 newTable[lastIdx] = lastRun; 521 522 // Clone all remaining nodes 523 for (HashEntry<K,V> p = e; p != lastRun; p = p.next) { 524 int k = p.hash & sizeMask; 525 HashEntry<K,V> n = newTable[k]; 526 newTable[k] = new HashEntry<K,V>(p.key, p.hash, 527 n, p.value); 528 } 529 } 530 } 531 } 532 table = newTable; 533 } 534 535 /** 536 * Remove; match on key only if value null, else match both. 537 */ 538 Object _remove(Object key, int hash, Object value, Object defaultValue) { 539 lock(); 540 try { 541 int c = count - 1; 542 HashEntry<K,V>[] tab = table; 543 int index = hash & (tab.length - 1); 544 HashEntry<K,V> first = tab[index]; 545 HashEntry<K,V> e = first; 546 while (e != null && (e.hash != hash || !key.equals(e.key))) 547 e = e.next; 548 549 if (e == null) return defaultValue; 550 551 V v = e.value; 552 if ((value == null && v==null) || value.equals(v)) { 553 ++modCount; 554 HashEntry<K,V> newFirst = e.next; 555 for (HashEntry<K,V> p = first; p != e; p = p.next) 556 newFirst = new HashEntry<K,V>(p.key, p.hash, 557 newFirst, p.value); 558 tab[index] = newFirst; 559 count = c; // write-volatile 560 return v; 561 } 562 return defaultValue; 563 } 564 finally { 565 unlock(); 566 } 567 } 568 569 V r(Object key, int hash, V defaultValue) { 570 lock(); 571 try { 572 int c = count - 1; 573 HashEntry<K,V>[] tab = table; 574 int index = hash & (tab.length - 1); 575 HashEntry<K,V> first = tab[index]; 576 HashEntry<K,V> e = first; 577 while (e != null && (e.hash != hash || !key.equals(e.key))) 578 e = e.next; 579 580 if (e == null) return defaultValue; 581 V v = e.value; 582 V oldValue = v; 583 ++modCount; 584 HashEntry<K,V> newFirst = e.next; 585 for (HashEntry<K,V> p = first; p != e; p = p.next) 586 newFirst = new HashEntry<K,V>(p.key, p.hash, 587 newFirst, p.value); 588 tab[index] = newFirst; 589 count = c; // write-volatile 590 return oldValue; 591 } 592 finally { 593 unlock(); 594 } 595 } 596 597 V r(Map map,Object key, int hash) throws PageException { 598 lock(); 599 try { 600 int c = count - 1; 601 HashEntry<K,V>[] tab = table; 602 int index = hash & (tab.length - 1); 603 HashEntry<K,V> first = tab[index]; 604 HashEntry<K,V> e = first; 605 while (e != null && (e.hash != hash || !key.equals(e.key))) 606 e = e.next; 607 608 if (e == null) throw HashMapPro.invalidKey(map, key,false); 609 V v = e.value; 610 V oldValue = v; 611 ++modCount; 612 HashEntry<K,V> newFirst = e.next; 613 for (HashEntry<K,V> p = first; p != e; p = p.next) 614 newFirst = new HashEntry<K,V>(p.key, p.hash, 615 newFirst, p.value); 616 tab[index] = newFirst; 617 count = c; // write-volatile 618 return oldValue; 619 } 620 finally { 621 unlock(); 622 } 623 } 624 625 void clear() { 626 if (count != 0) { 627 lock(); 628 try { 629 HashEntry<K,V>[] tab = table; 630 for (int i = 0; i < tab.length ; i++) 631 tab[i] = null; 632 ++modCount; 633 count = 0; // write-volatile 634 } finally { 635 unlock(); 636 } 637 } 638 } 639 } 640 641 642 643 /* ---------------- Public operations -------------- */ 644 645 /** 646 * Creates a new, empty map with the specified initial 647 * capacity, load factor and concurrency level. 648 * 649 * @param initialCapacity the initial capacity. The implementation 650 * performs internal sizing to accommodate this many elements. 651 * @param loadFactor the load factor threshold, used to control resizing. 652 * Resizing may be performed when the average number of elements per 653 * bin exceeds this threshold. 654 * @param concurrencyLevel the estimated number of concurrently 655 * updating threads. The implementation performs internal sizing 656 * to try to accommodate this many threads. 657 * @throws IllegalArgumentException if the initial capacity is 658 * negative or the load factor or concurrencyLevel are 659 * nonpositive. 660 */ 661 public ConcurrentHashMapPro(int initialCapacity, 662 float loadFactor, int concurrencyLevel) { 663 if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0) 664 throw new IllegalArgumentException(); 665 666 if (concurrencyLevel > MAX_SEGMENTS) 667 concurrencyLevel = MAX_SEGMENTS; 668 669 // Find power-of-two sizes best matching arguments 670 int sshift = 0; 671 int ssize = 1; 672 while (ssize < concurrencyLevel) { 673 ++sshift; 674 ssize <<= 1; 675 } 676 segmentShift = 32 - sshift; 677 segmentMask = ssize - 1; 678 this.segments = Segment.newArray(ssize); 679 680 if (initialCapacity > MAXIMUM_CAPACITY) 681 initialCapacity = MAXIMUM_CAPACITY; 682 int c = initialCapacity / ssize; 683 if (c * ssize < initialCapacity) 684 ++c; 685 int cap = 1; 686 while (cap < c) 687 cap <<= 1; 688 689 for (int i = 0; i < this.segments.length; ++i) 690 this.segments[i] = new Segment<K,V>(cap, loadFactor); 691 } 692 693 /** 694 * Creates a new, empty map with the specified initial capacity 695 * and load factor and with the default concurrencyLevel (16). 696 * 697 * @param initialCapacity The implementation performs internal 698 * sizing to accommodate this many elements. 699 * @param loadFactor the load factor threshold, used to control resizing. 700 * Resizing may be performed when the average number of elements per 701 * bin exceeds this threshold. 702 * @throws IllegalArgumentException if the initial capacity of 703 * elements is negative or the load factor is nonpositive 704 * 705 * @since 1.6 706 */ 707 public ConcurrentHashMapPro(int initialCapacity, float loadFactor) { 708 this(initialCapacity, loadFactor, DEFAULT_CONCURRENCY_LEVEL); 709 } 710 711 /** 712 * Creates a new, empty map with the specified initial capacity, 713 * and with default load factor (0.75) and concurrencyLevel (16). 714 * 715 * @param initialCapacity the initial capacity. The implementation 716 * performs internal sizing to accommodate this many elements. 717 * @throws IllegalArgumentException if the initial capacity of 718 * elements is negative. 719 */ 720 public ConcurrentHashMapPro(int initialCapacity) { 721 this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL); 722 } 723 724 /** 725 * Creates a new, empty map with a default initial capacity (16), 726 * load factor (0.75) and concurrencyLevel (16). 727 */ 728 public ConcurrentHashMapPro() { 729 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL); 730 } 731 732 /** 733 * Creates a new map with the same mappings as the given map. 734 * The map is created with a capacity of 1.5 times the number 735 * of mappings in the given map or 16 (whichever is greater), 736 * and a default load factor (0.75) and concurrencyLevel (16). 737 * 738 * @param m the map 739 */ 740 public ConcurrentHashMapPro(Map<? extends K, ? extends V> m) { 741 this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, 742 DEFAULT_INITIAL_CAPACITY), 743 DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL); 744 putAll(m); 745 } 746 747 /** 748 * Returns <tt>true</tt> if this map contains no key-value mappings. 749 * 750 * @return <tt>true</tt> if this map contains no key-value mappings 751 */ 752 public boolean isEmpty() { 753 final Segment<K,V>[] segments = this.segments; 754 /* 755 * We keep track of per-segment modCounts to avoid ABA 756 * problems in which an element in one segment was added and 757 * in another removed during traversal, in which case the 758 * table was never actually empty at any point. Note the 759 * similar use of modCounts in the size() and containsValue() 760 * methods, which are the only other methods also susceptible 761 * to ABA problems. 762 */ 763 int[] mc = new int[segments.length]; 764 int mcsum = 0; 765 for (int i = 0; i < segments.length; ++i) { 766 if (segments[i].count != 0) 767 return false; 768 mcsum += mc[i] = segments[i].modCount; 769 } 770 // If mcsum happens to be zero, then we know we got a snapshot 771 // before any modifications at all were made. This is 772 // probably common enough to bother tracking. 773 if (mcsum != 0) { 774 for (int i = 0; i < segments.length; ++i) { 775 if (segments[i].count != 0 || 776 mc[i] != segments[i].modCount) 777 return false; 778 } 779 } 780 return true; 781 } 782 783 /** 784 * Returns the number of key-value mappings in this map. If the 785 * map contains more than <tt>Integer.MAX_VALUE</tt> elements, returns 786 * <tt>Integer.MAX_VALUE</tt>. 787 * 788 * @return the number of key-value mappings in this map 789 */ 790 public int size() { 791 final Segment<K,V>[] segments = this.segments; 792 long sum = 0; 793 long check = 0; 794 int[] mc = new int[segments.length]; 795 // Try a few times to get accurate count. On failure due to 796 // continuous async changes in table, resort to locking. 797 for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) { 798 check = 0; 799 sum = 0; 800 int mcsum = 0; 801 for (int i = 0; i < segments.length; ++i) { 802 sum += segments[i].count; 803 mcsum += mc[i] = segments[i].modCount; 804 } 805 if (mcsum != 0) { 806 for (int i = 0; i < segments.length; ++i) { 807 check += segments[i].count; 808 if (mc[i] != segments[i].modCount) { 809 check = -1; // force retry 810 break; 811 } 812 } 813 } 814 if (check == sum) 815 break; 816 } 817 if (check != sum) { // Resort to locking all segments 818 sum = 0; 819 for (int i = 0; i < segments.length; ++i) 820 segments[i].lock(); 821 for (int i = 0; i < segments.length; ++i) 822 sum += segments[i].count; 823 for (int i = 0; i < segments.length; ++i) 824 segments[i].unlock(); 825 } 826 if (sum > Integer.MAX_VALUE) 827 return Integer.MAX_VALUE; 828 return (int)sum; 829 } 830 831 /** 832 * Returns the value to which the specified key is mapped, 833 * or {@code null} if this map contains no mapping for the key. 834 * 835 * <p>More formally, if this map contains a mapping from a key 836 * {@code k} to a value {@code v} such that {@code key.equals(k)}, 837 * then this method returns {@code v}; otherwise it returns 838 * {@code null}. (There can be at most one such mapping.) 839 * 840 * @throws NullPointerException if the specified key is null 841 */ 842 public V get(Object key) { 843 int hash = hash(key.hashCode()); 844 return segmentFor(hash).get(key, hash); 845 } 846 847 @Override 848 public V g(K key) throws PageException { 849 int hash = hash(key.hashCode()); 850 return segmentFor(hash).getE(this,key, hash); 851 } 852 private V ge(Object key) throws PageException { 853 int hash = hash(key.hashCode()); 854 return segmentFor(hash).getE(this,key, hash); 855 } 856 857 @Override 858 public V g(K key, V defaultValue) { 859 int hash = hash(key.hashCode()); 860 return segmentFor(hash).get(key, hash,defaultValue); 861 } 862 863 864 865 /** 866 * Tests if the specified object is a key in this table. 867 * 868 * @param key possible key 869 * @return <tt>true</tt> if and only if the specified object 870 * is a key in this table, as determined by the 871 * <tt>equals</tt> method; <tt>false</tt> otherwise. 872 * @throws NullPointerException if the specified key is null 873 */ 874 public boolean containsKey(Object key) { 875 int hash = hash(key.hashCode()); 876 return segmentFor(hash).containsKey(key, hash); 877 } 878 879 /** 880 * Returns <tt>true</tt> if this map maps one or more keys to the 881 * specified value. Note: This method requires a full internal 882 * traversal of the hash table, and so is much slower than 883 * method <tt>containsKey</tt>. 884 * 885 * @param value value whose presence in this map is to be tested 886 * @return <tt>true</tt> if this map maps one or more keys to the 887 * specified value 888 * @throws NullPointerException if the specified value is null 889 */ 890 public boolean containsValue(Object value) { 891 892 final Segment<K,V>[] segments = this.segments; 893 int[] mc = new int[segments.length]; 894 895 // Try a few times without locking 896 for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) { 897 int sum = 0; 898 int mcsum = 0; 899 for (int i = 0; i < segments.length; ++i) { 900 int c = segments[i].count; 901 mcsum += mc[i] = segments[i].modCount; 902 if (segments[i].containsValue(value)) 903 return true; 904 } 905 boolean cleanSweep = true; 906 if (mcsum != 0) { 907 for (int i = 0; i < segments.length; ++i) { 908 int c = segments[i].count; 909 if (mc[i] != segments[i].modCount) { 910 cleanSweep = false; 911 break; 912 } 913 } 914 } 915 if (cleanSweep) 916 return false; 917 } 918 // Resort to locking all segments 919 for (int i = 0; i < segments.length; ++i) 920 segments[i].lock(); 921 boolean found = false; 922 try { 923 for (int i = 0; i < segments.length; ++i) { 924 if (segments[i].containsValue(value)) { 925 found = true; 926 break; 927 } 928 } 929 } finally { 930 for (int i = 0; i < segments.length; ++i) 931 segments[i].unlock(); 932 } 933 return found; 934 } 935 936 /** 937 * Legacy method testing if some key maps into the specified value 938 * in this table. This method is identical in functionality to 939 * {@link #containsValue}, and exists solely to ensure 940 * full compatibility with class {@link java.util.Hashtable}, 941 * which supported this method prior to introduction of the 942 * Java Collections framework. 943 944 * @param value a value to search for 945 * @return <tt>true</tt> if and only if some key maps to the 946 * <tt>value</tt> argument in this table as 947 * determined by the <tt>equals</tt> method; 948 * <tt>false</tt> otherwise 949 * @throws NullPointerException if the specified value is null 950 */ 951 public boolean contains(Object value) { 952 return containsValue(value); 953 } 954 955 /** 956 * Maps the specified key to the specified value in this table. 957 * Neither the key nor the value can be null. 958 * 959 * <p> The value can be retrieved by calling the <tt>get</tt> method 960 * with a key that is equal to the original key. 961 * 962 * @param key key with which the specified value is to be associated 963 * @param value value to be associated with the specified key 964 * @return the previous value associated with <tt>key</tt>, or 965 * <tt>null</tt> if there was no mapping for <tt>key</tt> 966 * @throws NullPointerException if the specified key or value is null 967 */ 968 public V put(K key, V value) { 969 int hash = hash(key.hashCode()); 970 return segmentFor(hash).put(key, hash, value, false); 971 } 972 973 /** 974 * Copies all of the mappings from the specified map to this one. 975 * These mappings replace any mappings that this map had for any of the 976 * keys currently in the specified map. 977 * 978 * @param m mappings to be stored in this map 979 */ 980 public void putAll(Map<? extends K, ? extends V> m) { 981 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) 982 put(e.getKey(), e.getValue()); 983 } 984 985 /** 986 * Removes the key (and its corresponding value) from this map. 987 * This method does nothing if the key is not in the map. 988 * 989 * @param key the key that needs to be removed 990 * @return the previous value associated with <tt>key</tt>, or 991 * <tt>null</tt> if there was no mapping for <tt>key</tt> 992 * @throws NullPointerException if the specified key is null 993 */ 994 public V remove(Object key) { 995 int hash = hash(key.hashCode()); 996 return segmentFor(hash).r(key, hash, null); 997 } 998 999 1000 @Override 1001 public V r(K key) throws PageException { 1002 int hash = hash(key.hashCode()); 1003 return segmentFor(hash).r(this,key, hash); 1004 } 1005 1006 public V rem(Object key) throws PageException { 1007 int hash = hash(key.hashCode()); 1008 return segmentFor(hash).r(this,key, hash); 1009 } 1010 1011 @Override 1012 public V r(K key, V defaultValue) { 1013 int hash = hash(key.hashCode()); 1014 return segmentFor(hash).r(key, hash, defaultValue); 1015 } 1016 1017 private boolean remove(Map.Entry e) { 1018 Object k = e.getKey(); 1019 Object v = e.getValue(); 1020 int hash = hash(k.hashCode()); 1021 return segmentFor(hash)._remove(k, hash, v,Null.NULL) != Null.NULL; 1022 } 1023 1024 /** 1025 * Removes all of the mappings from this map. 1026 */ 1027 public void clear() { 1028 for (int i = 0; i < segments.length; ++i) 1029 segments[i].clear(); 1030 } 1031 1032 /** 1033 * Returns a {@link Set} view of the keys contained in this map. 1034 * The set is backed by the map, so changes to the map are 1035 * reflected in the set, and vice-versa. The set supports element 1036 * removal, which removes the corresponding mapping from this map, 1037 * via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, 1038 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> 1039 * operations. It does not support the <tt>add</tt> or 1040 * <tt>addAll</tt> operations. 1041 * 1042 * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator 1043 * that will never throw {@link ConcurrentModificationException}, 1044 * and guarantees to traverse elements as they existed upon 1045 * construction of the iterator, and may (but is not guaranteed to) 1046 * reflect any modifications subsequent to construction. 1047 */ 1048 public Set<K> keySet() { 1049 Set<K> ks = keySet; 1050 return (ks != null) ? ks : (keySet = new KeySet()); 1051 } 1052 1053 /** 1054 * Returns a {@link Collection} view of the values contained in this map. 1055 * The collection is backed by the map, so changes to the map are 1056 * reflected in the collection, and vice-versa. The collection 1057 * supports element removal, which removes the corresponding 1058 * mapping from this map, via the <tt>Iterator.remove</tt>, 1059 * <tt>Collection.remove</tt>, <tt>removeAll</tt>, 1060 * <tt>retainAll</tt>, and <tt>clear</tt> operations. It does not 1061 * support the <tt>add</tt> or <tt>addAll</tt> operations. 1062 * 1063 * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator 1064 * that will never throw {@link ConcurrentModificationException}, 1065 * and guarantees to traverse elements as they existed upon 1066 * construction of the iterator, and may (but is not guaranteed to) 1067 * reflect any modifications subsequent to construction. 1068 */ 1069 public Collection<V> values() { 1070 Collection<V> vs = values; 1071 return (vs != null) ? vs : (values = new Values()); 1072 } 1073 1074 /** 1075 * Returns a {@link Set} view of the mappings contained in this map. 1076 * The set is backed by the map, so changes to the map are 1077 * reflected in the set, and vice-versa. The set supports element 1078 * removal, which removes the corresponding mapping from the map, 1079 * via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, 1080 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> 1081 * operations. It does not support the <tt>add</tt> or 1082 * <tt>addAll</tt> operations. 1083 * 1084 * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator 1085 * that will never throw {@link ConcurrentModificationException}, 1086 * and guarantees to traverse elements as they existed upon 1087 * construction of the iterator, and may (but is not guaranteed to) 1088 * reflect any modifications subsequent to construction. 1089 */ 1090 public Set<Map.Entry<K,V>> entrySet() { 1091 Set<Map.Entry<K,V>> es = entrySet; 1092 return (es != null) ? es : (entrySet = new EntrySet()); 1093 } 1094 1095 /** 1096 * Returns an enumeration of the keys in this table. 1097 * 1098 * @return an enumeration of the keys in this table 1099 * @see #keySet() 1100 */ 1101 public Enumeration<K> keys() { 1102 return new KeyIterator(); 1103 } 1104 1105 /** 1106 * Returns an enumeration of the values in this table. 1107 * 1108 * @return an enumeration of the values in this table 1109 * @see #values() 1110 */ 1111 public Enumeration<V> elements() { 1112 return new ValueIterator(); 1113 } 1114 1115 /* ---------------- Iterator Support -------------- */ 1116 1117 abstract class HashIterator { 1118 int nextSegmentIndex; 1119 int nextTableIndex; 1120 HashEntry<K,V>[] currentTable; 1121 HashEntry<K, V> nextEntry; 1122 HashEntry<K, V> lastReturned; 1123 1124 HashIterator() { 1125 nextSegmentIndex = segments.length - 1; 1126 nextTableIndex = -1; 1127 advance(); 1128 } 1129 1130 public boolean hasMoreElements() { return hasNext(); } 1131 1132 final void advance() { 1133 if (nextEntry != null && (nextEntry = nextEntry.next) != null) 1134 return; 1135 1136 while (nextTableIndex >= 0) { 1137 if ( (nextEntry = currentTable[nextTableIndex--]) != null) 1138 return; 1139 } 1140 1141 while (nextSegmentIndex >= 0) { 1142 Segment<K,V> seg = segments[nextSegmentIndex--]; 1143 if (seg.count != 0) { 1144 currentTable = seg.table; 1145 for (int j = currentTable.length - 1; j >= 0; --j) { 1146 if ( (nextEntry = currentTable[j]) != null) { 1147 nextTableIndex = j - 1; 1148 return; 1149 } 1150 } 1151 } 1152 } 1153 } 1154 1155 public boolean hasNext() { return nextEntry != null; } 1156 1157 HashEntry<K,V> nextEntry() { 1158 if (nextEntry == null) 1159 throw new NoSuchElementException(); 1160 lastReturned = nextEntry; 1161 advance(); 1162 return lastReturned; 1163 } 1164 1165 public void remove() { 1166 if (lastReturned == null) 1167 throw new IllegalStateException(); 1168 ConcurrentHashMapPro.this.remove(lastReturned.key); 1169 lastReturned = null; 1170 } 1171 } 1172 1173 final class KeyIterator 1174 extends HashIterator 1175 implements Iterator<K>, Enumeration<K> 1176 { 1177 public K next() { return super.nextEntry().key; } 1178 public K nextElement() { return super.nextEntry().key; } 1179 } 1180 1181 final class ValueIterator 1182 extends HashIterator 1183 implements Iterator<V>, Enumeration<V> 1184 { 1185 public V next() { return super.nextEntry().value; } 1186 public V nextElement() { return super.nextEntry().value; } 1187 } 1188 1189 /** 1190 * Custom Entry class used by EntryIterator.next(), that relays 1191 * setValue changes to the underlying map. 1192 */ 1193 final class WriteThroughEntry 1194 extends AbstractMap.SimpleEntry<K,V> 1195 { 1196 WriteThroughEntry(K k, V v) { 1197 super(k,v); 1198 } 1199 1200 /** 1201 * Set our entry's value and write through to the map. The 1202 * value to return is somewhat arbitrary here. Since a 1203 * WriteThroughEntry does not necessarily track asynchronous 1204 * changes, the most recent "previous" value could be 1205 * different from what we return (or could even have been 1206 * removed in which case the put will re-establish). We do not 1207 * and cannot guarantee more. 1208 */ 1209 public V setValue(V value) { 1210 V v = super.setValue(value); 1211 ConcurrentHashMapPro.this.put(getKey(), value); 1212 return v; 1213 } 1214 } 1215 1216 final class EntryIterator 1217 extends HashIterator 1218 implements Iterator<Entry<K,V>> 1219 { 1220 public Map.Entry<K,V> next() { 1221 HashEntry<K,V> e = super.nextEntry(); 1222 return new WriteThroughEntry(e.key, e.value); 1223 } 1224 } 1225 1226 final class KeySet extends AbstractSet<K> { 1227 public Iterator<K> iterator() { 1228 return new KeyIterator(); 1229 } 1230 public int size() { 1231 return ConcurrentHashMapPro.this.size(); 1232 } 1233 public boolean isEmpty() { 1234 return ConcurrentHashMapPro.this.isEmpty(); 1235 } 1236 public boolean contains(Object o) { 1237 return ConcurrentHashMapPro.this.containsKey(o); 1238 } 1239 public boolean remove(Object o) { 1240 try{ 1241 ConcurrentHashMapPro.this.rem(o); 1242 return true; 1243 } 1244 catch(Throwable t){ 1245 return false; 1246 } 1247 } 1248 public void clear() { 1249 ConcurrentHashMapPro.this.clear(); 1250 } 1251 } 1252 1253 final class Values extends AbstractCollection<V> { 1254 public Iterator<V> iterator() { 1255 return new ValueIterator(); 1256 } 1257 public int size() { 1258 return ConcurrentHashMapPro.this.size(); 1259 } 1260 public boolean isEmpty() { 1261 return ConcurrentHashMapPro.this.isEmpty(); 1262 } 1263 public boolean contains(Object o) { 1264 return ConcurrentHashMapPro.this.containsValue(o); 1265 } 1266 public void clear() { 1267 ConcurrentHashMapPro.this.clear(); 1268 } 1269 } 1270 1271 final class EntrySet extends AbstractSet<Map.Entry<K,V>> { 1272 public Iterator<Map.Entry<K,V>> iterator() { 1273 return new EntryIterator(); 1274 } 1275 public boolean contains(Object o) { 1276 if (!(o instanceof Map.Entry)) 1277 return false; 1278 Map.Entry<?,?> e = (Map.Entry<?,?>)o; 1279 try { 1280 V v = ConcurrentHashMapPro.this.ge(e.getKey()); 1281 if(v==null) { 1282 return e.getValue()==null; 1283 } 1284 return v.equals(e.getValue()); 1285 } 1286 catch(Throwable t){ 1287 return false; 1288 } 1289 } 1290 public boolean remove(Object o) { 1291 if (!(o instanceof Map.Entry)) 1292 return false; 1293 Map.Entry<?,?> e = (Map.Entry<?,?>)o; 1294 return ConcurrentHashMapPro.this.remove(e); 1295 } 1296 public int size() { 1297 return ConcurrentHashMapPro.this.size(); 1298 } 1299 public boolean isEmpty() { 1300 return ConcurrentHashMapPro.this.isEmpty(); 1301 } 1302 public void clear() { 1303 ConcurrentHashMapPro.this.clear(); 1304 } 1305 } 1306 1307 /* ---------------- Serialization Support -------------- */ 1308 1309 /** 1310 * Save the state of the <tt>ConcurrentHashMap</tt> instance to a 1311 * stream (i.e., serialize it). 1312 * @param s the stream 1313 * @serialData 1314 * the key (Object) and value (Object) 1315 * for each key-value mapping, followed by a null pair. 1316 * The key-value mappings are emitted in no particular order. 1317 */ 1318 private void writeObject(java.io.ObjectOutputStream s) throws IOException { 1319 s.defaultWriteObject(); 1320 1321 for (int k = 0; k < segments.length; ++k) { 1322 Segment<K,V> seg = segments[k]; 1323 seg.lock(); 1324 try { 1325 HashEntry<K,V>[] tab = seg.table; 1326 for (int i = 0; i < tab.length; ++i) { 1327 for (HashEntry<K,V> e = tab[i]; e != null; e = e.next) { 1328 s.writeObject(e.key); 1329 s.writeObject(e.value); 1330 } 1331 } 1332 } finally { 1333 seg.unlock(); 1334 } 1335 } 1336 s.writeObject(null); 1337 s.writeObject(null); 1338 } 1339 1340 /** 1341 * Reconstitute the <tt>ConcurrentHashMap</tt> instance from a 1342 * stream (i.e., deserialize it). 1343 * @param s the stream 1344 */ 1345 private void readObject(java.io.ObjectInputStream s) 1346 throws IOException, ClassNotFoundException { 1347 s.defaultReadObject(); 1348 1349 // Initialize each segment to be minimally sized, and let grow. 1350 for (int i = 0; i < segments.length; ++i) { 1351 segments[i].setTable(new HashEntry[1]); 1352 } 1353 1354 // Read the keys and values, and put the mappings in the table 1355 for (;;) { 1356 K key = (K) s.readObject(); 1357 V value = (V) s.readObject(); 1358 if (key == null) 1359 break; 1360 put(key, value); 1361 } 1362 } 1363 }