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