| ||||
| ||||
| ||||
Code - Class EDU.oswego.cs.dl.util.concurrent.ConcurrentReaderHashMap1 /* 2 File: ConcurrentReaderHashMap 3 4 Written by Doug Lea. Adapted and released, under explicit 5 permission, from JDK1.2 HashMap.java and Hashtable.java which 6 carries the following copyright: 7 8 * Copyright 1997 by Sun Microsystems, Inc., 9 * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A. 10 * All rights reserved. 11 * 12 * This software is the confidential and proprietary information 13 * of Sun Microsystems, Inc. ("Confidential Information"). You 14 * shall not disclose such Confidential Information and shall use 15 * it only in accordance with the terms of the license agreement 16 * you entered into with Sun. 17 18 History: 19 Date Who What 20 28oct1999 dl Created 21 14dec1999 dl jmm snapshot 22 19apr2000 dl use barrierLock 23 12jan2001 dl public release 24 17nov2001 dl Minor tunings 25 20may2002 dl BarrierLock can now be serialized. 26 09dec2002 dl Fix interference checks. 27 */ 28 29 package EDU.oswego.cs.dl.util.concurrent; 30 31 import java.util.Map; 32 import java.util.AbstractMap; 33 import java.util.AbstractSet; 34 import java.util.AbstractCollection; 35 import java.util.Collection; 36 import java.util.Set; 37 import java.util.Iterator; 38 import java.util.Enumeration; 39 import java.util.ConcurrentModificationException; 40 import java.util.NoSuchElementException; 41 42 import java.io.Serializable; 43 import java.io.IOException; 44 import java.io.ObjectInputStream; 45 import java.io.ObjectOutputStream; 46 47 48 /** 49 * A version of Hashtable that supports mostly-concurrent reading, but 50 * exclusive writing. Because reads are not limited to periods 51 * without writes, a concurrent reader policy is weaker than a classic 52 * reader/writer policy, but is generally faster and allows more 53 * concurrency. This class is a good choice especially for tables that 54 * are mainly created by one thread during the start-up phase of a 55 * program, and from then on, are mainly read (with perhaps occasional 56 * additions or removals) in many threads. If you also need concurrency 57 * among writes, consider instead using ConcurrentHashMap. 58 * <p> 59 * 60 * Successful retrievals using get(key) and containsKey(key) usually 61 * run without locking. Unsuccessful ones (i.e., when the key is not 62 * present) do involve brief synchronization (locking). Also, the 63 * size and isEmpty methods are always synchronized. 64 * 65 * <p> Because retrieval operations can ordinarily overlap with 66 * writing operations (i.e., put, remove, and their derivatives), 67 * retrievals can only be guaranteed to return the results of the most 68 * recently <em>completed</em> operations holding upon their 69 * onset. Retrieval operations may or may not return results 70 * reflecting in-progress writing operations. However, the retrieval 71 * operations do always return consistent results -- either those 72 * holding before any single modification or after it, but never a 73 * nonsense result. For aggregate operations such as putAll and 74 * clear, concurrent reads may reflect insertion or removal of only 75 * some entries. In those rare contexts in which you use a hash table 76 * to synchronize operations across threads (for example, to prevent 77 * reads until after clears), you should either encase operations 78 * in synchronized blocks, or instead use java.util.Hashtable. 79 * 80 * <p> 81 * 82 * This class also supports optional guaranteed 83 * exclusive reads, simply by surrounding a call within a synchronized 84 * block, as in <br> 85 * <code>ConcurrentReaderHashMap t; ... Object v; <br> 86 * synchronized(t) { v = t.get(k); } </code> <br> 87 * 88 * But this is not usually necessary in practice. For 89 * example, it is generally inefficient to write: 90 * 91 * <pre> 92 * ConcurrentReaderHashMap t; ... // Inefficient version 93 * Object key; ... 94 * Object value; ... 95 * synchronized(t) { 96 * if (!t.containsKey(key)) 97 * t.put(key, value); 98 * // other code if not previously present 99 * } 100 * else { 101 * // other code if it was previously present 102 * } 103 * } 104 *</pre> 105 * Instead, if the values are intended to be the same in each case, just take advantage of the fact that put returns 106 * null if the key was not previously present: 107 * <pre> 108 * ConcurrentReaderHashMap t; ... // Use this instead 109 * Object key; ... 110 * Object value; ... 111 * Object oldValue = t.put(key, value); 112 * if (oldValue == null) { 113 * // other code if not previously present 114 * } 115 * else { 116 * // other code if it was previously present 117 * } 118 *</pre> 119 * <p> 120 * 121 * Iterators and Enumerations (i.e., those returned by 122 * keySet().iterator(), entrySet().iterator(), values().iterator(), 123 * keys(), and elements()) return elements reflecting the state of the 124 * hash table at some point at or since the creation of the 125 * iterator/enumeration. They will return at most one instance of 126 * each element (via next()/nextElement()), but might or might not 127 * reflect puts and removes that have been processed since they were 128 * created. They do <em>not</em> throw ConcurrentModificationException. 129 * However, these iterators are designed to be used by only one 130 * thread at a time. Sharing an iterator across multiple threads may 131 * lead to unpredictable results if the table is being concurrently 132 * modified. Again, you can ensure interference-free iteration by 133 * enclosing the iteration in a synchronized block. <p> 134 * 135 * This class may be used as a direct replacement for any use of 136 * java.util.Hashtable that does not depend on readers being blocked 137 * during updates. Like Hashtable but unlike java.util.HashMap, 138 * this class does NOT allow <tt>null</tt> to be used as a key or 139 * value. This class is also typically faster than ConcurrentHashMap 140 * when there is usually only one thread updating the table, but 141 * possibly many retrieving values from it. 142 * <p> 143 * 144 * Implementation note: A slightly faster implementation of 145 * this class will be possible once planned Java Memory Model 146 * revisions are in place. 147 * 148 * <p>[<a HREF="http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html"> Introduction to this package. </a>] 149 150 **/ 151 152 153 public class ConcurrentReaderHashMap 154 extends AbstractMap 155 implements Map, Cloneable, Serializable { 156 157 158 /* 159 The basic strategy is an optimistic-style scheme based on 160 the guarantee that the hash table and its lists are always 161 kept in a consistent enough state to be read without locking: 162 163 * Read operations first proceed without locking, by traversing the 164 apparently correct list of the apparently correct bin. If an 165 entry is found, but not invalidated (value field null), it is 166 returned. If not found, operations must recheck (after a memory 167 barrier) to make sure they are using both the right list and 168 the right table (which can change under resizes). If 169 invalidated, reads must acquire main update lock to wait out 170 the update, and then re-traverse. 171 172 * All list additions are at the front of each bin, making it easy 173 to check changes, and also fast to traverse. Entry next 174 pointers are never assigned. Remove() builds new nodes when 175 necessary to preserve this. 176 177 * Remove() (also clear()) invalidates removed nodes to alert read 178 operations that they must wait out the full modifications. 179 180 */ 181 182 /** A Serializable class for barrier lock **/ 183 protected static class BarrierLock implements java.io.Serializable { } 184 185 /** 186 * Lock used only for its memory effects. 187 **/ 188 protected final BarrierLock barrierLock = new BarrierLock(); 189 190 /** 191 * field written to only to guarantee lock ordering. 192 **/ 193 194 protected transient Object lastWrite; 195 196 /** 197 * Force a memory synchronization that will cause 198 * all readers to see table. Call only when already 199 * holding main synch lock. 200 **/ 201 protected final void recordModification(Object x) { 202 synchronized(barrierLock) { 203 lastWrite = x; 204 } 205 } 206 207 /** 208 * Get ref to table; the reference and the cells it 209 * accesses will be at least as fresh as from last 210 * use of barrierLock 211 **/ 212 protected final Entry[] getTableForReading() { 213 synchronized(barrierLock) { 214 return table; 215 } 216 } 217 218 219 /** 220 * The default initial number of table slots for this table (32). 221 * Used when not otherwise specified in constructor. 222 **/ 223 public static int DEFAULT_INITIAL_CAPACITY = 32; 224 225 226 /** 227 * The minimum capacity, used if a lower value is implicitly specified 228 * by either of the constructors with arguments. 229 * MUST be a power of two. 230 */ 231 private static final int MINIMUM_CAPACITY = 4; 232 233 /** 234 * The maximum capacity, used if a higher value is implicitly specified 235 * by either of the constructors with arguments. 236 * MUST be a power of two <= 1<<30. 237 */ 238 private static final int MAXIMUM_CAPACITY = 1 << 30; 239 240 /** 241 * The default load factor for this table (1.0). 242 * Used when not otherwise specified in constructor. 243 **/ 244 245 public static final float DEFAULT_LOAD_FACTOR = 0.75f; 246 247 248 /** 249 * The hash table data. 250 */ 251 protected transient Entry[] table; 252 253 /** 254 * The total number of mappings in the hash table. 255 */ 256 protected transient int count; 257 258 /** 259 * The table is rehashed when its size exceeds this threshold. (The 260 * value of this field is always (int)(capacity * loadFactor).) 261 * 262 * @serial 263 */ 264 protected int threshold; 265 266 /** 267 * The load factor for the hash table. 268 * 269 * @serial 270 */ 271 protected float loadFactor; 272 273 /** 274 * Returns the appropriate capacity (power of two) for the specified 275 * initial capacity argument. 276 */ 277 private int p2capacity(int initialCapacity) { 278 int cap = initialCapacity; 279 280 // Compute the appropriate capacity 281 int result; 282 if (cap > MAXIMUM_CAPACITY || cap < 0) { 283 result = MAXIMUM_CAPACITY; 284 } else { 285 result = MINIMUM_CAPACITY; 286 while (result < cap) 287 result <<= 1; 288 } 289 return result; 290 } 291 292 /** 293 * Return hash code for Object x. Since we are using power-of-two 294 * tables, it is worth the effort to improve hashcode via 295 * the same multiplicative scheme as used in IdentityHashMap. 296 */ 297 private static int hash(Object x) { 298 int h = x.hashCode(); 299 // Multiply by 127 (quickly, via shifts), and mix in some high 300 // bits to help guard against bunching of codes that are 301 // consecutive or equally spaced. 302 return ((h << 7) - h + (h >>> 9) + (h >>> 17)); 303 } 304 305 /** 306 * Check for equality of non-null references x and y. 307 **/ 308 protected boolean eq(Object x, Object y) { 309 return x == y || x.equals(y); 310 } 311 312 /** 313 * Constructs a new, empty map with the specified initial 314 * capacity and the specified load factor. 315 * 316 * @param initialCapacity the initial capacity 317 * The actual initial capacity is rounded to the nearest power of two. 318 * @param loadFactor the load factor of the ConcurrentReaderHashMap 319 * @throws IllegalArgumentException if the initial maximum number 320 * of elements is less 321 * than zero, or if the load factor is nonpositive. 322 */ 323 324 public ConcurrentReaderHashMap(int initialCapacity, float loadFactor) { 325 if (loadFactor <= 0) 326 throw new IllegalArgumentException("Illegal Load factor: "+ 327 loadFactor); 328 this.loadFactor = loadFactor; 329 330 int cap = p2capacity(initialCapacity); 331 332 table = new Entry[cap]; 333 threshold = (int)(cap * loadFactor); 334 } 335 336 /** 337 * Constructs a new, empty map with the specified initial 338 * capacity and default load factor. 339 * 340 * @param initialCapacity the initial capacity of the 341 * ConcurrentReaderHashMap. 342 * @throws IllegalArgumentException if the initial maximum number 343 * of elements is less 344 * than zero. 345 */ 346 347 public ConcurrentReaderHashMap(int initialCapacity) { 348 this(initialCapacity, DEFAULT_LOAD_FACTOR); 349 } 350 351 /** 352 * Constructs a new, empty map with a default initial capacity 353 * and load factor. 354 */ 355 356 public ConcurrentReaderHashMap() { 357 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); 358 } 359 360 /** 361 * Constructs a new map with the same mappings as the given map. The 362 * map is created with a capacity of twice the number of mappings in 363 * the given map or 16 (whichever is greater), and a default load factor. 364 */ 365 366 public ConcurrentReaderHashMap(Map t) { 367 this(Math.max((int) (t.size() / DEFAULT_LOAD_FACTOR) + 1, 16), 368 DEFAULT_LOAD_FACTOR); 369 putAll(t); 370 } 371 372 /** 373 * Returns the number of key-value mappings in this map. 374 * 375 * @return the number of key-value mappings in this map. 376 */ 377 378 public synchronized int size() { 379 return count; 380 } 381 382 /** 383 * Returns <tt>true</tt> if this map contains no key-value mappings. 384 * 385 * @return <tt>true</tt> if this map contains no key-value mappings. 386 */ 387 388 public synchronized boolean isEmpty() { 389 return count == 0; 390 } 391 392 393 394 /** 395 * Returns the value to which the specified key is mapped in this table. 396 * 397 * @param key a key in the table. 398 * @return the value to which the key is mapped in this table; 399 * <code>null</code> if the key is not mapped to any value in 400 * this table. 401 * @exception NullPointerException if the key is 402 * <code>null</code>. 403 * @see #put(Object, Object) 404 */ 405 406 407 public Object get(Object key) { 408 409 // throw null pointer exception if key null 410 int hash = hash(key); 411 412 /* 413 Start off at the apparently correct bin. If entry is found, we 414 need to check after a barrier anyway. If not found, we need a 415 barrier to check if we are actually in right bin. So either 416 way, we encounter only one barrier unless we need to retry. 417 And we only need to fully synchronize if there have been 418 concurrent modifications. 419 */ 420 421 Entry[] tab = table; 422 int index = hash & (tab.length - 1); 423 Entry first = tab[index]; 424 Entry e = first; 425 426 for (;;) { 427 if (e == null) { 428 429 // If key apparently not there, check to 430 // make sure this was a valid read 431 432 Entry[] reread = getTableForReading(); 433 if (tab == reread && first == tab[index]) 434 return null; 435 else { 436 // Wrong list -- must restart traversal at new first 437 tab = reread; 438 e = first = tab[index = hash & (tab.length-1)]; 439 } 440 441 } 442 443 else if (e.hash == hash && eq(key, e.key)) { 444 Object value = e.value; 445 if (value != null) 446 return value; 447 448 // Entry was invalidated during deletion. But it could 449 // have been re-inserted, so we must retraverse. 450 // To avoid useless contention, get lock to wait out modifications 451 // before retraversing. 452 453 synchronized(this) { 454 tab = table; 455 } 456 e = first = tab[index = hash & (tab.length-1)]; 457 458 } 459 else 460 e = e.next; 461 } 462 } 463 464 465 /** 466 * Tests if the specified object is a key in this table. 467 * 468 * @param key possible key. 469 * @return <code>true</code> if and only if the specified object 470 * is a key in this table, as determined by the 471 * <tt>equals</tt> method; <code>false</code> otherwise. 472 * @exception NullPointerException if the key is 473 * <code>null</code>. 474 * @see #contains(Object) 475 */ 476 477 478 public boolean containsKey(Object key) { 479 return get(key) != null; 480 } 481 482 /** 483 * Maps the specified <code>key</code> to the specified 484 * <code>value</code> in this table. Neither the key nor the 485 * value can be <code>null</code>. <p> 486 * 487 * The value can be retrieved by calling the <code>get</code> method 488 * with a key that is equal to the original key. 489 * 490 * @param key the table key. 491 * @param value the value. 492 * @return the previous value of the specified key in this table, 493 * or <code>null</code> if it did not have one. 494 * @exception NullPointerException if the key or value is 495 * <code>null</code>. 496 * @see Object#equals(Object) 497 * @see #get(Object) 498 */ 499 500 public Object put(Object key, Object value) { 501 if (value == null) 502 throw new NullPointerException(); 503 504 int hash = hash(key); 505 Entry[] tab = table; 506 int index = hash & (tab.length-1); 507 Entry first = tab[index]; 508 Entry e; 509 510 for (e = first; e != null; e = e.next) 511 if (e.hash == hash && eq(key, e.key)) 512 break; 513 514 synchronized(this) { 515 if (tab == table) { 516 if (e == null) { 517 // make sure we are adding to correct list 518 if (first == tab[index]) { 519 // Add to front of list 520 Entry newEntry = new Entry(hash, key, value, first); 521 tab[index] = newEntry; 522 if (++count >= threshold) rehash(); 523 else recordModification(newEntry); 524 return null; 525 } 526 } 527 else { 528 Object oldValue = e.value; 529 if (first == tab[index] && oldValue != null) { 530 e.value = value; 531 return oldValue; 532 } 533 } 534 } 535 536 // retry if wrong list or lost race against concurrent remove 537 return sput(key, value, hash); 538 } 539 } 540 541 542 /** 543 * Continuation of put(), called only when synch lock is 544 * held and interference has been detected. 545 **/ 546 protected Object sput(Object key, Object value, int hash) { 547 548 Entry[] tab = table; 549 int index = hash & (tab.length-1); 550 Entry first = tab[index]; 551 Entry e = first; 552 553 for (;;) { 554 if (e == null) { 555 Entry newEntry = new Entry(hash, key, value, first); 556 tab[index] = newEntry; 557 if (++count >= threshold) rehash(); 558 else recordModification(newEntry); 559 return null; 560 } 561 else if (e.hash == hash && eq(key, e.key)) { 562 Object oldValue = e.value; 563 e.value = value; 564 return oldValue; 565 } 566 else 567 e = e.next; 568 } 569 } 570 571 572 /** 573 * Rehashes the contents of this map into a new table 574 * with a larger capacity. This method is called automatically when the 575 * number of keys in this map exceeds its capacity and load factor. 576 */ 577 protected void rehash() { 578 Entry[] oldTable = table; 579 int oldCapacity = oldTable.length; 580 if (oldCapacity >= MAXIMUM_CAPACITY) { 581 threshold = Integer.MAX_VALUE; // avoid retriggering 582 return; 583 } 584 585 int newCapacity = oldCapacity << 1; 586 int mask = newCapacity - 1; 587 threshold = (int)(newCapacity * loadFactor); 588 589 Entry[] newTable = new Entry[newCapacity]; 590 /* 591 * Reclassify nodes in each list to new Map. Because we are 592 * using power-of-two expansion, the elements from each bin 593 * must either stay at same index, or move to 594 * oldCapacity+index. We also eliminate unnecessary node 595 * creation by catching cases where old nodes can be reused 596 * because their next fields won't change. Statistically, at 597 * the default threshhold, only about one-sixth of them need 598 * cloning. (The nodes they replace will be garbage 599 * collectable as soon as they are no longer referenced by any 600 * reader thread that may be in the midst of traversing table 601 * right now.) 602 */ 603 604 for (int i = 0; i < oldCapacity ; i++) { 605 // We need to guarantee that any existing reads of old Map can 606 // proceed. So we cannot yet null out each bin. 607 Entry e = oldTable[i]; 608 609 if (e != null) { 610 int idx = e.hash & mask; 611 Entry next = e.next; 612 613 // Single node on list 614 if (next == null) 615 newTable[idx] = e; 616 617 else { 618 // Reuse trailing consecutive sequence of all same bit 619 Entry lastRun = e; 620 int lastIdx = idx; 621 for (Entry last = next; last != null; last = last.next) { 622 int k = last.hash & mask; 623 if (k != lastIdx) { 624 lastIdx = k; 625 lastRun = last; 626 } 627 } 628 newTable[lastIdx] = lastRun; 629 630 // Clone all remaining nodes 631 for (Entry p = e; p != lastRun; p = p.next) { 632 int k = p.hash & mask; 633 newTable[k] = new Entry(p.hash, p.key, 634 p.value, newTable[k]); 635 } 636 } 637 } 638 } 639 640 table = newTable; 641 recordModification(newTable); 642 } 643 644 /** 645 * Removes the key (and its corresponding value) from this 646 * table. This method does nothing if the key is not in the table. 647 * 648 * @param key the key that needs to be removed. 649 * @return the value to which the key had been mapped in this table, 650 * or <code>null</code> if the key did not have a mapping. 651 * @exception NullPointerException if the key is 652 * <code>null</code>. 653 */ 654 655 public Object remove(Object key) { 656 /* 657 Find the entry, then 658 1. Set value field to null, to force get() to retry 659 2. Rebuild the list without this entry. 660 All entries following removed node can stay in list, but 661 all preceeding ones need to be cloned. Traversals rely 662 on this strategy to ensure that elements will not be 663 repeated during iteration. 664 */ 665 666 667 int hash = hash(key); 668 Entry[] tab = table; 669 int index = hash & (tab.length-1); 670 Entry first = tab[index]; 671 Entry e = first; 672 673 for (e = first; e != null; e = e.next) 674 if (e.hash == hash && eq(key, e.key)) 675 break; 676 677 678 synchronized(this) { 679 if (tab == table) { 680 if (e == null) { 681 if (first == tab[index]) 682 return null; 683 } 684 else { 685 Object oldValue = e.value; 686 if (first == tab[index] && oldValue != null) { 687 e.value = null; 688 count--; 689 690 Entry head = e.next; 691 for (Entry p = first; p != e; p = p.next) 692 head = new Entry(p.hash, p.key, p.value, head); 693 694 tab[index] = head; 695 recordModification(head); 696 return oldValue; 697 } 698 } 699 } 700 701 // Wrong list or interference 702 return sremove(key, hash); 703 } 704 } 705 706 /** 707 * Continuation of remove(), called only when synch lock is 708 * held and interference has been detected. 709 **/ 710 711 protected Object sremove(Object key, int hash) { 712 Entry[] tab = table; 713 int index = hash & (tab.length-1); 714 Entry first = tab[index]; 715 716 for (Entry e = first; e != null; e = e.next) { 717 if (e.hash == hash && eq(key, e.key)) { 718 Object oldValue = e.value; 719 e.value = null; 720 count--; 721 Entry head = e.next; 722 for (Entry p = first; p != e; p = p.next) 723 head = new Entry(p.hash, p.key, p.value, head); 724 725 tab[index] = head; 726 recordModification(head); 727 return oldValue; 728 } 729 } 730 return null; 731 } 732 733 734 /** 735 * Returns <tt>true</tt> if this map maps one or more keys to the 736 * specified value. Note: This method requires a full internal 737 * traversal of the hash table, and so is much slower than 738 * method <tt>containsKey</tt>. 739 * 740 * @param value value whose presence in this map is to be tested. 741 * @return <tt>true</tt> if this map maps one or more keys to the 742 * specified value. 743 * @exception NullPointerException if the value is <code>null</code>. 744 */ 745 746 public boolean containsValue(Object value) { 747 if (value == null) throw new NullPointerException(); 748 749 Entry tab[] = getTableForReading(); 750 751 for (int i = 0 ; i < tab.length; ++i) { 752 for (Entry e = tab[i] ; e != null ; e = e.next) 753 if (value.equals(e.value)) 754 return true; 755 } 756 757 return false; 758 } 759 760 /** 761 * Tests if some key maps into the specified value in this table. 762 * This operation is more expensive than the <code>containsKey</code> 763 * method.<p> 764 * 765 * Note that this method is identical in functionality to containsValue, 766 * (which is part of the Map interface in the collections framework). 767 * 768 * @param value a value to search for. 769 * @return <code>true</code> if and only if some key maps to the 770 * <code>value</code> argument in this table as 771 * determined by the <tt>equals</tt> method; 772 * <code>false</code> otherwise. 773 * @exception NullPointerException if the value is <code>null</code>. 774 * @see #containsKey(Object) 775 * @see #containsValue(Object) 776 * @see Map 777 */ 778 779 public boolean contains(Object value) { 780 return containsValue(value); 781 } 782 783 784 /** 785 * Copies all of the mappings from the specified map to this one. 786 * 787 * These mappings replace any mappings that this map had for any of the 788 * keys currently in the specified Map. 789 * 790 * @param t Mappings to be stored in this map. 791 */ 792 793 public synchronized void putAll(Map t) { 794 int n = t.size(); 795 if (n == 0) 796 return; 797 798 // Expand enough to hold at least n elements without resizing. 799 // We can only resize table by factor of two at a time. 800 // It is faster to rehash with fewer elements, so do it now. 801 while (n >= threshold) 802 rehash(); 803 804 for (Iterator it = t.entrySet().iterator(); it.hasNext();) { 805 Map.Entry entry = (Map.Entry) it.next(); 806 Object key = entry.getKey(); 807 Object value = entry.getValue(); 808 put(key, value); 809 } 810 } 811 812 813 /** 814 * Removes all mappings from this map. 815 */ 816 public synchronized void clear() { 817 Entry tab[] = table; 818 for (int i = 0; i < tab.length ; ++i) { 819 820 // must invalidate all to force concurrent get's to wait and then retry 821 for (Entry e = tab[i]; e != null; e = e.next) 822 e.value = null; 823 824 tab[i] = null; 825 } 826 count = 0; 827 recordModification(tab); 828 } 829 830 /** 831 * Returns a shallow copy of this 832 * <tt>ConcurrentReaderHashMap</tt> instance: the keys and 833 * values themselves are not cloned. 834 * 835 * @return a shallow copy of this map. 836 */ 837 838 public synchronized Object clone() { 839 try { 840 ConcurrentReaderHashMap t = (ConcurrentReaderHashMap)super.clone(); 841 842 t.keySet = null; 843 t.entrySet = null; 844 t.values = null; 845 846 Entry[] tab = table; 847 t.table = new Entry[tab.length]; 848 Entry[] ttab = t.table; 849 850 for (int i = 0; i < tab.length; ++i) { 851 Entry first = null; 852 for (Entry e = tab[i]; e != null; e = e.next) 853 first = new Entry(e.hash, e.key, e.value, first); 854 ttab[i] = first; 855 } 856 857 return t; 858 } 859 catch (CloneNotSupportedException e) { 860 // this shouldn't happen, since we are Cloneable 861 throw new InternalError(); 862 } 863 } 864 865 // Views 866 867 protected transient Set keySet = null; 868 protected transient Set entrySet = null; 869 protected transient Collection values = null; 870 871 /** 872 * Returns a set view of the keys contained in this map. The set is 873 * backed by the map, so changes to the map are reflected in the set, and 874 * vice-versa. The set supports element removal, which removes the 875 * corresponding mapping from this map, via the <tt>Iterator.remove</tt>, 876 * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and 877 * <tt>clear</tt> operations. It does not support the <tt>add</tt> or 878 * <tt>addAll</tt> operations. 879 * 880 * @return a set view of the keys contained in this map. 881 */ 882 883 public Set keySet() { 884 Set ks = keySet; 885 return (ks != null)? ks : (keySet = new KeySet()); 886 } 887 888 private class KeySet extends AbstractSet { 889 public Iterator iterator() { 890 return new KeyIterator(); 891 } 892 public int size() { 893 return ConcurrentReaderHashMap.this.size(); 894 } 895 public boolean contains(Object o) { 896 return ConcurrentReaderHashMap.this.containsKey(o); 897 } 898 public boolean remove(Object o) { 899 return ConcurrentReaderHashMap.this.remove(o) != null; 900 } 901 public void clear() { 902 ConcurrentReaderHashMap.this.clear(); 903 } 904 } 905 906 /** 907 * Returns a collection view of the values contained in this map. The 908 * collection is backed by the map, so changes to the map are reflected in 909 * the collection, and vice-versa. The collection supports element 910 * removal, which removes the corresponding mapping from this map, via the 911 * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>, 912 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations. 913 * It does not support the <tt>add</tt> or <tt>addAll</tt> operations. 914 * 915 * @return a collection view of the values contained in this map. 916 */ 917 918 public Collection values() { 919 Collection vs = values; 920 return (vs != null)? vs : (values = new Values()); 921 } 922 923 private class Values extends AbstractCollection { 924 public Iterator iterator() { 925 return new ValueIterator(); 926 } 927 public int size() { 928 return ConcurrentReaderHashMap.this.size(); 929 } 930 public boolean contains(Object o) { 931 return ConcurrentReaderHashMap.this.containsValue(o); 932 } 933 public void clear() { 934 ConcurrentReaderHashMap.this.clear(); 935 } 936 } 937 938 /** 939 * Returns a collection view of the mappings contained in this map. Each 940 * element in the returned collection is a <tt>Map.Entry</tt>. The 941 * collection is backed by the map, so changes to the map are reflected in 942 * the collection, and vice-versa. The collection supports element 943 * removal, which removes the corresponding mapping from the map, via the 944 * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>, 945 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations. 946 * It does not support the <tt>add</tt> or <tt>addAll</tt> operations. 947 * 948 * @return a collection view of the mappings contained in this map. 949 */ 950 951 public Set entrySet() { 952 Set es = entrySet; 953 return (es != null) ? es : (entrySet = new EntrySet()); 954 } 955 956 private class EntrySet extends AbstractSet { 957 public Iterator iterator() { 958 return new HashIterator(); 959 } 960 public boolean contains(Object o) { 961 if (!(o instanceof Map.Entry)) 962 return false; 963 Map.Entry entry = (Map.Entry)o; 964 Object v = ConcurrentReaderHashMap.this.get(entry.getKey()); 965 return v != null && v.equals(entry.getValue()); 966 } 967 public boolean remove(Object o) { 968 if (!(o instanceof Map.Entry)) 969 return false; 970 return ConcurrentReaderHashMap.this.findAndRemoveEntry((Map.Entry)o); 971 } 972 public int size() { 973 return ConcurrentReaderHashMap.this.size(); 974 } 975 public void clear() { 976 ConcurrentReaderHashMap.this.clear(); 977 } 978 } 979 980 /** 981 * Helper method for entrySet.remove 982 **/ 983 protected synchronized boolean findAndRemoveEntry(Map.Entry entry) { 984 Object key = entry.getKey(); 985 Object v = get(key); 986 if (v != null && v.equals(entry.getValue())) { 987 remove(key); 988 return true; 989 } 990 else 991 return false; 992 } 993 994 /** 995 * Returns an enumeration of the keys in this table. 996 * 997 * @return an enumeration of the keys in this table. 998 * @see Enumeration 999 * @see #elements() 1000 * @see #keySet() 1001 * @see Map 1002 */ 1003 public Enumeration keys() { 1004 return new KeyIterator(); 1005 } 1006 1007 /** 1008 * Returns an enumeration of the values in this table. 1009 * Use the Enumeration methods on the returned object to fetch the elements 1010 * sequentially. 1011 * 1012 * @return an enumeration of the values in this table. 1013 * @see java.util.Enumeration 1014 * @see #keys() 1015 * @see #values() 1016 * @see Map 1017 */ 1018 1019 public Enumeration elements() { 1020 return new ValueIterator(); 1021 } 1022 1023 1024 /** 1025 * ConcurrentReaderHashMap collision list entry. 1026 */ 1027 1028 protected static class Entry implements Map.Entry { 1029 1030 /* 1031 The use of volatile for value field ensures that 1032 we can detect status changes without synchronization. 1033 The other fields are never changed, and are 1034 marked as final. 1035 */ 1036 1037 protected final int hash; 1038 protected final Object key; 1039 protected final Entry next; 1040 protected volatile Object value; 1041 1042 Entry(int hash, Object key, Object value, Entry next) { 1043 this.hash = hash; 1044 this.key = key; 1045 this.next = next; 1046 this.value = value; 1047 } 1048 1049 // Map.Entry Ops 1050 1051 public Object getKey() { 1052 return key; 1053 } 1054 1055 /** 1056 * Get the value. Note: In an entrySet or entrySet.iterator, 1057 * unless the set or iterator is used under synchronization of the 1058 * table as a whole (or you can otherwise guarantee lack of 1059 * concurrent modification), <tt>getValue</tt> <em>might</em> 1060 * return null, reflecting the fact that the entry has been 1061 * concurrently removed. However, there are no assurances that 1062 * concurrent removals will be reflected using this method. 1063 * 1064 * @return the current value, or null if the entry has been 1065 * detectably removed. 1066 **/ 1067 public Object getValue() { 1068 return value; 1069 } 1070 1071 /** 1072 * Set the value of this entry. Note: In an entrySet or 1073 * entrySet.iterator), unless the set or iterator is used under 1074 * synchronization of the table as a whole (or you can otherwise 1075 * guarantee lack of concurrent modification), <tt>setValue</tt> 1076 * is not strictly guaranteed to actually replace the value field 1077 * obtained via the <tt>get</tt> operation of the underlying hash 1078 * table in multithreaded applications. If iterator-wide 1079 * synchronization is not used, and any other concurrent 1080 * <tt>put</tt> or <tt>remove</tt> operations occur, sometimes 1081 * even to <em>other</em> entries, then this change is not 1082 * guaranteed to be reflected in the hash table. (It might, or it 1083 * might not. There are no assurances either way.) 1084 * 1085 * @param value the new value. 1086 * @return the previous value, or null if entry has been detectably 1087 * removed. 1088 * @exception NullPointerException if the value is <code>null</code>. 1089 * 1090 **/ 1091 1092 public Object setValue(Object value) { 1093 if (value == null) 1094 throw new NullPointerException(); 1095 Object oldValue = this.value; 1096 this.value = value; 1097 return oldValue; 1098 } 1099 1100 public boolean equals(Object o) { 1101 if (!(o instanceof Map.Entry)) 1102 return false; 1103 Map.Entry e = (Map.Entry)o; 1104 return (key.equals(e.getKey()) && value.equals(e.getValue())); 1105 } 1106 1107 public int hashCode() { 1108 return key.hashCode() ^ value.hashCode(); 1109 } 1110 1111 public String toString() { 1112 return key + "=" + value; 1113 } 1114 1115 } 1116 1117 protected class HashIterator implements Iterator, Enumeration { 1118 protected final Entry[] tab; // snapshot of table 1119 protected int index; // current slot 1120 protected Entry entry = null; // current node of slot 1121 protected Object currentKey; // key for current node 1122 protected Object currentValue; // value for current node 1123 protected Entry lastReturned = null; // last node returned by next 1124 1125 protected HashIterator() { 1126 tab = ConcurrentReaderHashMap.this.getTableForReading(); 1127 index = tab.length - 1; 1128 } 1129 1130 public boolean hasMoreElements() { return hasNext(); } 1131 public Object nextElement() { return next(); } 1132 1133 1134 public boolean hasNext() { 1135 1136 /* 1137 currentkey and currentValue are set here to ensure that next() 1138 returns normally if hasNext() returns true. This avoids 1139 surprises especially when final element is removed during 1140 traversal -- instead, we just ignore the removal during 1141 current traversal. 1142 */ 1143 1144 for (;;) { 1145 if (entry != null) { 1146 Object v = entry.value; 1147 if (v != null) { 1148 currentKey = entry.key; 1149 currentValue = v; 1150 return true; 1151 } 1152 else 1153 entry = entry.next; 1154 } 1155 1156 while (entry == null && index >= 0) 1157 entry = tab[index--]; 1158 1159 if (entry == null) { 1160 currentKey = currentValue = null; 1161 return false; 1162 } 1163 } 1164 } 1165 1166 protected Object returnValueOfNext() { return entry; } 1167 1168 public Object next() { 1169 if (currentKey == null && !hasNext()) 1170 throw new NoSuchElementException(); 1171 1172 Object result = returnValueOfNext(); 1173 lastReturned = entry; 1174 currentKey = currentValue = null; 1175 entry = entry.next; 1176 return result; 1177 } 1178 1179 public void remove() { 1180 if (lastReturned == null) 1181 throw new IllegalStateException(); 1182 ConcurrentReaderHashMap.this.remove(lastReturned.key); 1183 lastReturned = null; 1184 } 1185 1186 } 1187 1188 1189 protected class KeyIterator extends HashIterator { 1190 protected Object returnValueOfNext() { return currentKey; } 1191 } 1192 1193 protected class ValueIterator extends HashIterator { 1194 protected Object returnValueOfNext() { return currentValue; } 1195 } 1196 1197 1198 1199 /** 1200 * Save the state of the <tt>ConcurrentReaderHashMap</tt> 1201 * instance to a stream (i.e., 1202 * serialize it). 1203 * 1204 * @serialData The <i>capacity</i> of the 1205 * ConcurrentReaderHashMap (the length of the 1206 * bucket array) is emitted (int), followed by the 1207 * <i>size</i> of the ConcurrentReaderHashMap (the number of key-value 1208 * mappings), followed by the key (Object) and value (Object) 1209 * for each key-value mapping represented by the ConcurrentReaderHashMap 1210 * The key-value mappings are emitted in no particular order. 1211 */ 1212 1213 private synchronized void writeObject(java.io.ObjectOutputStream s) 1214 throws IOException { 1215 // Write out the threshold, loadfactor, and any hidden stuff 1216 s.defaultWriteObject(); 1217 1218 // Write out number of buckets 1219 s.writeInt(table.length); 1220 1221 // Write out size (number of Mappings) 1222 s.writeInt(count); 1223 1224 // Write out keys and values (alternating) 1225 for (int index = table.length-1; index >= 0; index--) { 1226 Entry entry = table[index]; 1227 1228 while (entry != null) { 1229 s.writeObject(entry.key); 1230 s.writeObject(entry.value); 1231 entry = entry.next; 1232 } 1233 } 1234 } 1235 1236 /** 1237 * Reconstitute the <tt>ConcurrentReaderHashMap</tt> 1238 * instance from a stream (i.e., 1239 * deserialize it). 1240 */ 1241 private synchronized void readObject(java.io.ObjectInputStream s) 1242 throws IOException, ClassNotFoundException { 1243 // Read in the threshold, loadfactor, and any hidden stuff 1244 s.defaultReadObject(); 1245 1246 // Read in number of buckets and allocate the bucket array; 1247 int numBuckets = s.readInt(); 1248 table = new Entry[numBuckets]; 1249 1250 // Read in size (number of Mappings) 1251 int size = s.readInt(); 1252 1253 // Read the keys and values, and put the mappings in the table 1254 for (int i=0; i<size; i++) { 1255 Object key = s.readObject(); 1256 Object value = s.readObject(); 1257 put(key, value); 1258 } 1259 } 1260 1261 /** 1262 * Return the number of slots in this table 1263 **/ 1264 1265 public synchronized int capacity() { 1266 return table.length; 1267 } 1268 1269 /** 1270 * Return the load factor 1271 **/ 1272 public float loadFactor() { 1273 return loadFactor; 1274 } 1275} 1276 |
||||
Bookmark
|digg
|del.icio.us
|furl
|spurl
|blinklist
|reddit
|yahoo
|blinkbits
|blogmarks
|de.lirio.us
|smarking
| | ||||
Java API By Example, From Geeks To Geeks. |
Conditions of Use |
About Us
© 2002 - 2005, KickJava.com, or its affiliates
|