Clover coverage report - dom4j - 1.6.1
Coverage timestamp: ma mei 16 2005 14:23:01 GMT+01:00
Overview   Package   File
    FRAMES   NO FRAMES  
file stats: LOC: 1.284   Methods: 63
NCLOC: 535   Classes: 9
 
 Source file Conditionals Statements Methods TOTAL
ConcurrentReaderHashMap.java 27,8% 29,7% 17,5% 27,6%
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    * A version of Hashtable that supports mostly-concurrent reading, but exclusive
 45    * writing. Because reads are not limited to periods without writes, a
 46    * concurrent reader policy is weaker than a classic reader/writer policy, but
 47    * is generally faster and allows more concurrency. This class is a good choice
 48    * especially for tables that are mainly created by one thread during the
 49    * start-up phase of a program, and from then on, are mainly read (with perhaps
 50    * occasional additions or removals) in many threads. If you also need
 51    * concurrency among writes, consider instead using ConcurrentHashMap.
 52    * <p>
 53    *
 54    * Successful retrievals using get(key) and containsKey(key) usually run without
 55    * locking. Unsuccessful ones (i.e., when the key is not present) do involve
 56    * brief synchronization (locking). Also, the size and isEmpty methods are
 57    * always synchronized.
 58    *
 59    * <p>
 60    * Because retrieval operations can ordinarily overlap with writing operations
 61    * (i.e., put, remove, and their derivatives), retrievals can only be guaranteed
 62    * to return the results of the most recently <em>completed</em> operations
 63    * holding upon their onset. Retrieval operations may or may not return results
 64    * reflecting in-progress writing operations. However, the retrieval operations
 65    * do always return consistent results -- either those holding before any single
 66    * modification or after it, but never a nonsense result. For aggregate
 67    * operations such as putAll and clear, concurrent reads may reflect insertion
 68    * or removal of only some entries. In those rare contexts in which you use a
 69    * hash table to synchronize operations across threads (for example, to prevent
 70    * reads until after clears), you should either encase operations in
 71    * synchronized blocks, or instead use java.util.Hashtable.
 72    *
 73    * <p>
 74    *
 75    * This class also supports optional guaranteed exclusive reads, simply by
 76    * surrounding a call within a synchronized block, as in <br>
 77    * <code>ConcurrentReaderHashMap t; ... Object v; <br>
 78    * synchronized(t) { v = t.get(k); } </code><br>
 79    *
 80    * But this is not usually necessary in practice. For example, it is generally
 81    * inefficient to write:
 82    *
 83    * <pre>
 84    *
 85    *
 86    * ConcurrentReaderHashMap t; ... // Inefficient version
 87    * Object key; ...
 88    * Object value; ...
 89    * synchronized(t) {
 90    * if (!t.containsKey(key))
 91    * t.put(key, value);
 92    * // other code if not previously present
 93    * }
 94    * else {
 95    * // other code if it was previously present
 96    * }
 97    * }
 98    *
 99    *
 100    * </pre>
 101    *
 102    * Instead, if the values are intended to be the same in each case, just take
 103    * advantage of the fact that put returns null if the key was not previously
 104    * present:
 105    *
 106    * <pre>
 107    *
 108    *
 109    * ConcurrentReaderHashMap t; ... // Use this instead
 110    * Object key; ...
 111    * Object value; ...
 112    * Object oldValue = t.put(key, value);
 113    * if (oldValue == null) {
 114    * // other code if not previously present
 115    * }
 116    * else {
 117    * // other code if it was previously present
 118    * }
 119    *
 120    *
 121    * </pre>
 122    *
 123    * <p>
 124    *
 125    * Iterators and Enumerations (i.e., those returned by keySet().iterator(),
 126    * entrySet().iterator(), values().iterator(), keys(), and elements()) return
 127    * elements reflecting the state of the hash table at some point at or since the
 128    * creation of the iterator/enumeration. They will return at most one instance
 129    * of each element (via next()/nextElement()), but might or might not reflect
 130    * puts and removes that have been processed since they were created. They do
 131    * <em>not</em> throw ConcurrentModificationException. However, these
 132    * iterators are designed to be used by only one thread at a time. Sharing an
 133    * iterator across multiple threads may lead to unpredictable results if the
 134    * table is being concurrently modified. Again, you can ensure interference-free
 135    * iteration by enclosing the iteration in a synchronized block.
 136    * <p>
 137    *
 138    * This class may be used as a direct replacement for any use of
 139    * java.util.Hashtable that does not depend on readers being blocked during
 140    * updates. Like Hashtable but unlike java.util.HashMap, this class does NOT
 141    * allow <tt>null</tt> to be used as a key or value. This class is also
 142    * typically faster than ConcurrentHashMap when there is usually only one thread
 143    * updating the table, but possibly many retrieving values from it.
 144    * <p>
 145    *
 146    * Implementation note: A slightly faster implementation of this class will be
 147    * possible once planned Java Memory Model revisions are in place.
 148    *
 149    * <p>[ <a
 150    * href="http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html">
 151    * Introduction to this package. </a>]
 152    *
 153    */
 154   
 155    class ConcurrentReaderHashMap extends AbstractMap implements Map, Cloneable,
 156    Serializable {
 157   
 158    /*
 159    * The basic strategy is an optimistic-style scheme based on the guarantee
 160    * that the hash table and its lists are always kept in a consistent enough
 161    * 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 entry is
 165    * found, but not invalidated (value field null), it is returned. If not
 166    * found, operations must recheck (after a memory barrier) to make sure they
 167    * are using both the right list and the right table (which can change under
 168    * resizes). If invalidated, reads must acquire main update lock to wait out
 169    * the update, and then re-traverse.
 170    *
 171    * All list additions are at the front of each bin, making it easy to check
 172    * changes, and also fast to traverse. Entry next pointers are never
 173    * assigned. Remove() builds new nodes when necessary to preserve this.
 174    *
 175    * Remove() (also clear()) invalidates removed nodes to alert read
 176    * operations that they must wait out the full modifications.
 177    *
 178    */
 179   
 180    /** A Serializable class for barrier lock * */
 181    protected static class BarrierLock implements java.io.Serializable {
 182    }
 183   
 184    /**
 185    * Lock used only for its memory effects.
 186    */
 187    protected final BarrierLock barrierLock = new BarrierLock();
 188   
 189    /**
 190    * field written to only to guarantee lock ordering.
 191    */
 192   
 193    protected transient Object lastWrite;
 194   
 195    /**
 196    * Force a memory synchronization that will cause all readers to see table.
 197    * Call only when already holding main synch lock.
 198    */
 199  20624 protected final void recordModification(Object x) {
 200  20624 synchronized (barrierLock) {
 201  20624 lastWrite = x;
 202    }
 203    }
 204   
 205    /**
 206    * Get ref to table; the reference and the cells it accesses will be at
 207    * least as fresh as from last use of barrierLock
 208    */
 209  41248 protected final Entry[] getTableForReading() {
 210  41248 synchronized (barrierLock) {
 211  41248 return table;
 212    }
 213    }
 214   
 215    /**
 216    * The default initial number of table slots for this table (32). Used when
 217    * not otherwise specified in constructor.
 218    */
 219    public static int DEFAULT_INITIAL_CAPACITY = 32;
 220   
 221    /**
 222    * The minimum capacity, used if a lower value is implicitly specified by
 223    * either of the constructors with arguments. MUST be a power of two.
 224    */
 225    private static final int MINIMUM_CAPACITY = 4;
 226   
 227    /**
 228    * The maximum capacity, used if a higher value is implicitly specified by
 229    * either of the constructors with arguments. MUST be a power of two <= 1 <
 230    * <30.
 231    */
 232    private static final int MAXIMUM_CAPACITY = 1 << 30;
 233   
 234    /**
 235    * The default load factor for this table (1.0). Used when not otherwise
 236    * specified in constructor.
 237    */
 238   
 239    public static final float DEFAULT_LOAD_FACTOR = 0.75f;
 240   
 241    /**
 242    * The hash table data.
 243    */
 244    protected transient Entry[] table;
 245   
 246    /**
 247    * The total number of mappings in the hash table.
 248    */
 249    protected transient int count;
 250   
 251    /**
 252    * The table is rehashed when its size exceeds this threshold. (The value of
 253    * this field is always (int)(capacity * loadFactor).)
 254    *
 255    * @serial
 256    */
 257    protected int threshold;
 258   
 259    /**
 260    * The load factor for the hash table.
 261    *
 262    * @serial
 263    */
 264    protected float loadFactor;
 265   
 266    /**
 267    * Returns the appropriate capacity (power of two) for the specified initial
 268    * capacity argument.
 269    */
 270  10476 private int p2capacity(int initialCapacity) {
 271  10476 int cap = initialCapacity;
 272   
 273    // Compute the appropriate capacity
 274  10476 int result;
 275  10476 if (cap > MAXIMUM_CAPACITY || cap < 0) {
 276  0 result = MAXIMUM_CAPACITY;
 277    } else {
 278  10476 result = MINIMUM_CAPACITY;
 279  10476 while (result < cap)
 280  31428 result <<= 1;
 281    }
 282  10476 return result;
 283    }
 284   
 285    /**
 286    * Return hash code for Object x. Since we are using power-of-two tables, it
 287    * is worth the effort to improve hashcode via the same multiplicative
 288    * scheme as used in IdentityHashMap.
 289    */
 290  2283990 private static int hash(Object x) {
 291  2283990 int h = x.hashCode();
 292    // Multiply by 127 (quickly, via shifts), and mix in some high
 293    // bits to help guard against bunching of codes that are
 294    // consecutive or equally spaced.
 295  2283990 return ((h << 7) - h + (h >>> 9) + (h >>> 17));
 296    }
 297   
 298    /**
 299    * Check for equality of non-null references x and y.
 300    */
 301  2222118 protected boolean eq(Object x, Object y) {
 302  2222118 return x == y || x.equals(y);
 303    }
 304   
 305    /**
 306    * Constructs a new, empty map with the specified initial capacity and the
 307    * specified load factor.
 308    *
 309    * @param initialCapacity
 310    * the initial capacity The actual initial capacity is rounded to
 311    * the nearest power of two.
 312    * @param loadFactor
 313    * the load factor of the ConcurrentReaderHashMap
 314    * @throws IllegalArgumentException
 315    * if the initial maximum number of elements is less than zero,
 316    * or if the load factor is nonpositive.
 317    */
 318   
 319  10476 public ConcurrentReaderHashMap(int initialCapacity, float loadFactor) {
 320  10476 if (loadFactor <= 0)
 321  0 throw new IllegalArgumentException("Illegal Load factor: "
 322    + loadFactor);
 323  10476 this.loadFactor = loadFactor;
 324   
 325  10476 int cap = p2capacity(initialCapacity);
 326   
 327  10476 table = new Entry[cap];
 328  10476 threshold = (int) (cap * loadFactor);
 329    }
 330   
 331    /**
 332    * Constructs a new, empty map with the specified initial capacity and
 333    * default load factor.
 334    *
 335    * @param initialCapacity
 336    * the initial capacity of the ConcurrentReaderHashMap.
 337    * @throws IllegalArgumentException
 338    * if the initial maximum number of elements is less than zero.
 339    */
 340   
 341  0 public ConcurrentReaderHashMap(int initialCapacity) {
 342  0 this(initialCapacity, DEFAULT_LOAD_FACTOR);
 343    }
 344   
 345    /**
 346    * Constructs a new, empty map with a default initial capacity and load
 347    * factor.
 348    */
 349   
 350  10476 public ConcurrentReaderHashMap() {
 351  10476 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
 352    }
 353   
 354    /**
 355    * Constructs a new map with the same mappings as the given map. The map is
 356    * created with a capacity of twice the number of mappings in the given map
 357    * or 16 (whichever is greater), and a default load factor.
 358    */
 359   
 360  0 public ConcurrentReaderHashMap(Map t) {
 361  0 this(Math.max((int) (t.size() / DEFAULT_LOAD_FACTOR) + 1, 16),
 362    DEFAULT_LOAD_FACTOR);
 363  0 putAll(t);
 364    }
 365   
 366    /**
 367    * Returns the number of key-value mappings in this map.
 368    *
 369    * @return the number of key-value mappings in this map.
 370    */
 371   
 372  0 public synchronized int size() {
 373  0 return count;
 374    }
 375   
 376    /**
 377    * Returns <tt>true</tt> if this map contains no key-value mappings.
 378    *
 379    * @return <tt>true</tt> if this map contains no key-value mappings.
 380    */
 381   
 382  0 public synchronized boolean isEmpty() {
 383  0 return count == 0;
 384    }
 385   
 386    /**
 387    * Returns the value to which the specified key is mapped in this table.
 388    *
 389    * @param key
 390    * a key in the table.
 391    * @return the value to which the key is mapped in this table;
 392    * <code>null</code> if the key is not mapped to any value in this
 393    * table.
 394    * @exception NullPointerException
 395    * if the key is <code>null</code>.
 396    * @see #put(Object, Object)
 397    */
 398   
 399  2263360 public Object get(Object key) {
 400   
 401    // throw null pointer exception if key null
 402  2263360 int hash = hash(key);
 403   
 404    /*
 405    * Start off at the apparently correct bin. If entry is found, we need
 406    * to check after a barrier anyway. If not found, we need a barrier to
 407    * check if we are actually in right bin. So either way, we encounter
 408    * only one barrier unless we need to retry. And we only need to fully
 409    * synchronize if there have been concurrent modifications.
 410    */
 411   
 412  2263360 Entry[] tab = table;
 413  2263360 int index = hash & (tab.length - 1);
 414  2263360 Entry first = tab[index];
 415  2263360 Entry e = first;
 416   
 417  2263360 for (;;) {
 418  2272846 if (e == null) {
 419   
 420    // If key apparently not there, check to
 421    // make sure this was a valid read
 422   
 423  41248 Entry[] reread = getTableForReading();
 424  41248 if (tab == reread && first == tab[index])
 425  41248 return null;
 426    else {
 427    // Wrong list -- must restart traversal at new first
 428  0 tab = reread;
 429  0 e = first = tab[index = hash & (tab.length - 1)];
 430    }
 431   
 432    }
 433   
 434  2231598 else if (e.hash == hash && eq(key, e.key)) {
 435  2222112 Object value = e.value;
 436  2222112 if (value != null)
 437  2222112 return value;
 438   
 439    // Entry was invalidated during deletion. But it could
 440    // have been re-inserted, so we must retraverse.
 441    // To avoid useless contention, get lock to wait out
 442    // modifications
 443    // before retraversing.
 444   
 445  0 synchronized (this) {
 446  0 tab = table;
 447    }
 448  0 e = first = tab[index = hash & (tab.length - 1)];
 449   
 450    } else
 451  9486 e = e.next;
 452    }
 453    }
 454   
 455    /**
 456    * Tests if the specified object is a key in this table.
 457    *
 458    * @param key
 459    * possible key.
 460    * @return <code>true</code> if and only if the specified object is a key
 461    * in this table, as determined by the <tt>equals</tt> method;
 462    * <code>false</code> otherwise.
 463    * @exception NullPointerException
 464    * if the key is <code>null</code>.
 465    * @see #contains(Object)
 466    */
 467   
 468  0 public boolean containsKey(Object key) {
 469  0 return get(key) != null;
 470    }
 471   
 472    /**
 473    * Maps the specified <code>key</code> to the specified <code>value</code>
 474    * in this table. Neither the key nor the value can be <code>null</code>.
 475    * <p>
 476    *
 477    * The value can be retrieved by calling the <code>get</code> method with
 478    * a key that is equal to the original key.
 479    *
 480    * @param key
 481    * the table key.
 482    * @param value
 483    * the value.
 484    * @return the previous value of the specified key in this table, or
 485    * <code>null</code> if it did not have one.
 486    * @exception NullPointerException
 487    * if the key or value is <code>null</code>.
 488    * @see Object#equals(Object)
 489    * @see #get(Object)
 490    */
 491   
 492  20630 public Object put(Object key, Object value) {
 493  20630 if (value == null)
 494  0 throw new NullPointerException();
 495   
 496  20630 int hash = hash(key);
 497  20630 Entry[] tab = table;
 498  20630 i