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