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