View Javadoc

    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     protected final void recordModification(Object x) {
    200         synchronized (barrierLock) {
    201             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     protected final Entry[] getTableForReading() {
    210         synchronized (barrierLock) {
    211             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     private int p2capacity(int initialCapacity) {
    271         int cap = initialCapacity;
    272
    273         // Compute the appropriate capacity
    274         int result;
    275         if (cap > MAXIMUM_CAPACITY || cap < 0) {
    276             result = MAXIMUM_CAPACITY;
    277         } else {
    278             result = MINIMUM_CAPACITY;
    279             while (result < cap)
    280                 result <<= 1;
    281         }
    282         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     private static int hash(Object x) {
    291         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         return ((h << 7) - h + (h >>> 9) + (h >>> 17));
    296     }
    297
    298     /***
    299      * Check for equality of non-null references x and y.
    300      */
    301     protected boolean eq(Object x, Object y) {
    302         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     public ConcurrentReaderHashMap(int initialCapacity, float loadFactor) {
    320         if (loadFactor <= 0)
    321             throw new IllegalArgumentException("Illegal Load factor: "
    322                     + loadFactor);
    323         this.loadFactor = loadFactor;
    324
    325         int cap = p2capacity(initialCapacity);
    326
    327         table = new Entry[cap];
    328         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     public ConcurrentReaderHashMap(int initialCapacity) {
    342         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     public ConcurrentReaderHashMap() {
    351         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     public ConcurrentReaderHashMap(Map t) {
    361         this(Math.max((int) (t.size() / DEFAULT_LOAD_FACTOR) + 1, 16),
    362                 DEFAULT_LOAD_FACTOR);
    363         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     public synchronized int size() {
    373         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     public synchronized boolean isEmpty() {
    383         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     public Object get(Object key) {
    400
    401         // throw null pointer exception if key null
    402         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         Entry[] tab = table;
    413         int index = hash & (tab.length - 1);
    414         Entry first = tab[index];
    415         Entry e = first;
    416
    417         for (;;) {
    418             if (e == null) {
    419
    420                 // If key apparently not there, check to
    421                 // make sure this was a valid read
    422
    423                 Entry[] reread = getTableForReading();
    424                 if (tab == reread && first == tab[index])
    425                     return null;
    426                 else {
    427                     // Wrong list -- must restart traversal at new first
    428                     tab = reread;
    429                     e = first = tab[index = hash & (tab.length - 1)];
    430                 }
    431
    432             }
    433
    434             else if (e.hash == hash && eq(key, e.key)) {
    435                 Object value = e.value;
    436                 if (value != null)
    437                     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                 synchronized (this) {
    446                     tab = table;
    447                 }
    448                 e = first = tab[index = hash & (tab.length - 1)];
    449
    450             } else
    451                 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     public boolean containsKey(Object key) {
    469         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     public Object put(Object key, Object value) {
    493         if (value == null)
    494             throw new NullPointerException();
    495
    496         int hash = hash(key);
    497         Entry[] tab = table;
    498         int index = hash & (tab.length - 1);
    499         Entry first = tab[index];
    500         Entry e;
    501
    502         for (e = first; e != null; e = e.next)
    503             if (e.hash == hash && eq(key, e.key))
    504                 break;
    505
    506         synchronized (this) {
    507             if (tab == table) {
    508                 if (e == null) {
    509                     // make sure we are adding to correct list
    510                     if (first == tab[index]) {
    511                         // Add to front of list
    512                         Entry newEntry = new Entry(hash, key, value, first);
    513                         tab[index] = newEntry;
    514                         if (++count >= threshold)
    515                             rehash();
    516                         else
    517                             recordModification(newEntry);
    518                         return null;
    519                     }
    520                 } else {
    521                     Object oldValue = e.value;
    522                     if (first == tab[index] && oldValue != null) {
    523                         e.value = value;
    524                         return oldValue;
    525                     }
    526                 }
    527             }
    528
    529             // retry if wrong list or lost race against concurrent remove
    530             return sput(key, value, hash);
    531         }
    532     }
    533
    534     /***
    535      * Continuation of put(), called only when synch lock is held and
    536      * interference has been detected.
    537      */
    538     protected Object sput(Object key, Object value, int hash) {
    539
    540         Entry[] tab = table;
    541         int index = hash & (tab.length - 1);
    542         Entry first = tab[index];
    543         Entry e = first;
    544
    545         for (;;) {
    546             if (e == null) {
    547                 Entry newEntry = new Entry(hash, key, value, first);
    548                 tab[index] = newEntry;
    549                 if (++count >= threshold)
    550                     rehash();
    551                 else
    552                     recordModification(newEntry);
    553                 return null;
    554             } else if (e.hash == hash && eq(key, e.key)) {
    555                 Object oldValue = e.value;
    556                 e.value = value;
    557                 return oldValue;
    558             } else
    559                 e = e.next;
    560         }
    561     }
    562
    563     /***
    564      * Rehashes the contents of this map into a new table with a larger
    565      * capacity. This method is called automatically when the number of keys in
    566      * this map exceeds its capacity and load factor.
    567      */
    568     protected void rehash() {
    569         Entry[] oldTable = table;
    570         int oldCapacity = oldTable.length;
    571         if (oldCapacity >= MAXIMUM_CAPACITY) {
    572             threshold = Integer.MAX_VALUE; // avoid retriggering
    573             return;
    574         }
    575
    576         int newCapacity = oldCapacity << 1;
    577         int mask = newCapacity - 1;
    578         threshold = (int) (newCapacity * loadFactor);
    579
    580         Entry[] newTable = new Entry[newCapacity];
    581         /*
    582          * Reclassify nodes in each list to new Map. Because we are using
    583          * power-of-two expansion, the elements from each bin must either stay
    584          * at same index, or move to oldCapacity+index. We also eliminate
    585          * unnecessary node creation by catching cases where old nodes can be
    586          * reused because their next fields won't change. Statistically, at the
    587          * default threshhold, only about one-sixth of them need cloning. (The
    588          * nodes they replace will be garbage collectable as soon as they are no
    589          * longer referenced by any reader thread that may be in the midst of
    590          * traversing table right now.)
    591          */
    592
    593         for (int i = 0; i < oldCapacity; i++) {
    594             // We need to guarantee that any existing reads of old Map can
    595             // proceed. So we cannot yet null out each bin.
    596             Entry e = oldTable[i];
    597
    598             if (e != null) {
    599                 int idx = e.hash & mask;
    600                 Entry next = e.next;
    601
    602                 // Single node on list
    603                 if (next == null)
    604                     newTable[idx] = e;
    605
    606                 else {
    607                     // Reuse trailing consecutive sequence of all same bit
    608                     Entry lastRun = e;
    609                     int lastIdx = idx;
    610                     for (Entry last = next; last != null; last = last.next) {
    611                         int k = last.hash & mask;
    612                         if (k != lastIdx) {
    613                             lastIdx = k;
    614                             lastRun = last;
    615                         }
    616                     }
    617                     newTable[lastIdx] = lastRun;
    618
    619                     // Clone all remaining nodes
    620                     for (Entry p = e; p != lastRun; p = p.next) {
    621                         int k = p.hash & mask;
    622                         newTable[k] = new Entry(p.hash, p.key, p.value,
    623                                 newTable[k]);
    624                     }
    625                 }
    626             }
    627         }
    628
    629         table = newTable;
    630         recordModification(newTable);
    631     }
    632
    633     /***
    634      * Removes the key (and its corresponding value) from this table. This
    635      * method does nothing if the key is not in the table.
    636      *
    637      * @param key
    638      *            the key that needs to be removed.
    639      * @return the value to which the key had been mapped in this table, or
    640      *         <code>null</code> if the key did not have a mapping.
    641      * @exception NullPointerException
    642      *                if the key is <code>null</code>.
    643      */
    644
    645     public Object remove(Object key) {
    646         /*
    647          * Find the entry, then 1. Set value field to null, to force get() to
    648          * retry 2. Rebuild the list without this entry. All entries following
    649          * removed node can stay in list, but all preceeding ones need to be
    650          * cloned. Traversals rely on this strategy to ensure that elements will
    651          * not be repeated during iteration.
    652          */
    653
    654         int hash = hash(key);
    655         Entry[] tab = table;
    656         int index = hash & (tab.length - 1);
    657         Entry first = tab[index];
    658         Entry e = first;
    659
    660         for (e = first; e != null; e = e.next)
    661             if (e.hash == hash && eq(key, e.key))
    662                 break;
    663
    664         synchronized (this) {
    665             if (tab == table) {
    666                 if (e == null) {
    667                     if (first == tab[index])
    668                         return null;
    669                 } else {
    670                     Object oldValue = e.value;
    671                     if (first == tab[index] && oldValue != null) {
    672                         e.value = null;
    673                         count--;
    674
    675                         Entry head = e.next;
    676                         for (Entry p = first; p != e; p = p.next)
    677                             head = new Entry(p.hash, p.key, p.value, head);
    678
    679                         tab[index] = head;
    680                         recordModification(head);
    681                         return oldValue;
    682                     }
    683                 }
    684             }
    685
    686             // Wrong list or interference
    687             return sremove(key, hash);
    688         }
    689     }
    690
    691     /***
    692      * Continuation of remove(), called only when synch lock is held and
    693      * interference has been detected.
    694      */
    695
    696     protected Object sremove(Object key, int hash) {
    697         Entry[] tab = table;
    698         int index = hash & (tab.length - 1);
    699         Entry first = tab[index];
    700
    701         for (Entry e = first; e != null; e = e.next) {
    702             if (e.hash == hash && eq(key, e.key)) {
    703                 Object oldValue = e.value;
    704                 e.value = null;
    705                 count--;
    706                 Entry head = e.next;
    707                 for (Entry p = first; p != e; p = p.next)
    708                     head = new Entry(p.hash, p.key, p.value, head);
    709
    710                 tab[index] = head;
    711                 recordModification(head);
    712                 return oldValue;
    713             }
    714         }
    715         return null;
    716     }
    717
    718     /***
    719      * Returns <tt>true</tt> if this map maps one or more keys to the
    720      * specified value. Note: This method requires a full internal traversal of
    721      * the hash table, and so is much slower than method <tt>containsKey</tt>.
    722      *
    723      * @param value
    724      *            value whose presence in this map is to be tested.
    725      * @return <tt>true</tt> if this map maps one or more keys to the
    726      *         specified value.
    727      * @exception NullPointerException
    728      *                if the value is <code>null</code>.
    729      */
    730
    731     public boolean containsValue(Object value) {
    732         if (value == null)
    733             throw new NullPointerException();
    734
    735         Entry tab[] = getTableForReading();
    736
    737         for (int i = 0; i < tab.length; ++i) {
    738             for (Entry e = tab[i]; e != null; e = e.next)
    739                 if (value.equals(e.value))
    740                     return true;
    741         }
    742
    743         return false;
    744     }
    745
    746     /***
    747      * Tests if some key maps into the specified value in this table. This
    748      * operation is more expensive than the <code>containsKey</code> method.
    749      * <p>
    750      *
    751      * Note that this method is identical in functionality to containsValue,
    752      * (which is part of the Map interface in the collections framework).
    753      *
    754      * @param value
    755      *            a value to search for.
    756      * @return <code>true</code> if and only if some key maps to the
    757      *         <code>value</code> argument in this table as determined by the
    758      *         <tt>equals</tt> method; <code>false</code> otherwise.
    759      * @exception NullPointerException
    760      *                if the value is <code>null</code>.
    761      * @see #containsKey(Object)
    762      * @see #containsValue(Object)
    763      * @see Map
    764      */
    765
    766     public boolean contains(Object value) {
    767         return containsValue(value);
    768     }
    769
    770     /***
    771      * Copies all of the mappings from the specified map to this one.
    772      *
    773      * These mappings replace any mappings that this map had for any of the keys
    774      * currently in the specified Map.
    775      *
    776      * @param t
    777      *            Mappings to be stored in this map.
    778      */
    779
    780     public synchronized void putAll(Map t) {
    781         int n = t.size();
    782         if (n == 0)
    783             return;
    784
    785         // Expand enough to hold at least n elements without resizing.
    786         // We can only resize table by factor of two at a time.
    787         // It is faster to rehash with fewer elements, so do it now.
    788         while (n >= threshold)
    789             rehash();
    790
    791         for (Iterator it = t.entrySet().iterator(); it.hasNext();) {
    792             Map.Entry entry = (Map.Entry) it.next();
    793             Object key = entry.getKey();
    794             Object value = entry.getValue();
    795             put(key, value);
    796         }
    797     }
    798
    799     /***
    800      * Removes all mappings from this map.
    801      */
    802     public synchronized void clear() {
    803         Entry tab[] = table;
    804         for (int i = 0; i < tab.length; ++i) {
    805
    806             // must invalidate all to force concurrent get's to wait and then
    807             // retry
    808             for (Entry e = tab[i]; e != null; e = e.next)
    809                 e.value = null;
    810
    811             tab[i] = null;
    812         }
    813         count = 0;
    814         recordModification(tab);
    815     }
    816
    817     /***
    818      * Returns a shallow copy of this <tt>ConcurrentReaderHashMap</tt>
    819      * instance: the keys and values themselves are not cloned.
    820      *
    821      * @return a shallow copy of this map.
    822      */
    823
    824     public synchronized Object clone() {
    825         try {
    826             ConcurrentReaderHashMap t = (ConcurrentReaderHashMap) super.clone();
    827
    828             t.keySet = null;
    829             t.entrySet = null;
    830             t.values = null;
    831
    832             Entry[] tab = table;
    833             t.table = new Entry[tab.length];
    834             Entry[] ttab = t.table;
    835
    836             for (int i = 0; i < tab.length; ++i) {
    837                 Entry first = null;
    838                 for (Entry e = tab[i]; e != null; e = e.next)
    839                     first = new Entry(e.hash, e.key, e.value, first);
    840                 ttab[i] = first;
    841             }
    842
    843             return t;
    844         } catch (CloneNotSupportedException e) {
    845             // this shouldn't happen, since we are Cloneable
    846             throw new InternalError();
    847         }
    848     }
    849
    850     // Views
    851
    852     protected transient Set keySet = null;
    853
    854     protected transient Set entrySet = null;
    855
    856     protected transient Collection values = null;
    857
    858     /***
    859      * Returns a set view of the keys contained in this map. The set is backed
    860      * by the map, so changes to the map are reflected in the set, and
    861      * vice-versa. The set supports element removal, which removes the
    862      * corresponding mapping from this map, via the <tt>Iterator.remove</tt>,
    863      * <tt>Set.remove</tt>,<tt>removeAll</tt>,<tt>retainAll</tt>, and
    864      * <tt>clear</tt> operations. It does not support the <tt>add</tt> or
    865      * <tt>addAll</tt> operations.
    866      *
    867      * @return a set view of the keys contained in this map.
    868      */
    869
    870     public Set keySet() {
    871         Set ks = keySet;
    872         return (ks != null) ? ks : (keySet = new KeySet());
    873     }
    874
    875     private class KeySet extends AbstractSet {
    876         public Iterator iterator() {
    877             return new KeyIterator();
    878         }
    879
    880         public int size() {
    881             return ConcurrentReaderHashMap.this.size();
    882         }
    883
    884         public boolean contains(Object o) {
    885             return ConcurrentReaderHashMap.this.containsKey(o);
    886         }
    887
    888         public boolean remove(Object o) {
    889             return ConcurrentReaderHashMap.this.remove(o) != null;
    890         }
    891
    892         public void clear() {
    893             ConcurrentReaderHashMap.this.clear();
    894         }
    895     }
    896
    897     /***
    898      * Returns a collection view of the values contained in this map. The
    899      * collection is backed by the map, so changes to the map are reflected in
    900      * the collection, and vice-versa. The collection supports element removal,
    901      * which removes the corresponding mapping from this map, via the
    902      * <tt>Iterator.remove</tt>,<tt>Collection.remove</tt>,
    903      * <tt>removeAll</tt>,<tt>retainAll</tt>, and <tt>clear</tt>
    904      * operations. It does not support the <tt>add</tt> or <tt>addAll</tt>
    905      * operations.
    906      *
    907      * @return a collection view of the values contained in this map.
    908      */
    909
    910     public Collection values() {
    911         Collection vs = values;
    912         return (vs != null) ? vs : (values = new Values());
    913     }
    914
    915     private class Values extends AbstractCollection {
    916         public Iterator iterator() {
    917             return new ValueIterator();
    918         }
    919
    920         public int size() {
    921             return ConcurrentReaderHashMap.this.size();
    922         }
    923
    924         public boolean contains(Object o) {
    925             return ConcurrentReaderHashMap.this.containsValue(o);
    926         }
    927
    928         public void clear() {
    929             ConcurrentReaderHashMap.this.clear();
    930         }
    931     }
    932
    933     /***
    934      * Returns a collection view of the mappings contained in this map. Each
    935      * element in the returned collection is a <tt>Map.Entry</tt>. The
    936      * collection is backed by the map, so changes to the map are reflected in
    937      * the collection, and vice-versa. The collection supports element removal,
    938      * which removes the corresponding mapping from the map, via the
    939      * <tt>Iterator.remove</tt>,<tt>Collection.remove</tt>,
    940      * <tt>removeAll</tt>,<tt>retainAll</tt>, and <tt>clear</tt>
    941      * operations. It does not support the <tt>add</tt> or <tt>addAll</tt>
    942      * operations.
    943      *
    944      * @return a collection view of the mappings contained in this map.
    945      */
    946
    947     public Set entrySet() {
    948         Set es = entrySet;
    949         return (es != null) ? es : (entrySet = new EntrySet());
    950     }
    951
    952     private class EntrySet extends AbstractSet {
    953         public Iterator iterator() {
    954             return new HashIterator();
    955         }
    956
    957         public boolean contains(Object o) {
    958             if (!(o instanceof Map.Entry))
    959                 return false;
    960             Map.Entry entry = (Map.Entry) o;
    961             Object v = ConcurrentReaderHashMap.this.get(entry.getKey());
    962             return v != null && v.equals(entry.getValue());
    963         }
    964
    965         public boolean remove(Object o) {
    966             if (!(o instanceof Map.Entry))
    967                 return false;
    968             return ConcurrentReaderHashMap.this
    969                     .findAndRemoveEntry((Map.Entry) o);
    970         }
    971
    972         public int size() {
    973             return ConcurrentReaderHashMap.this.size();
    974         }
    975
    976         public void clear() {
    977             ConcurrentReaderHashMap.this.clear();
    978         }
    979     }
    980
    981     /***
    982      * Helper method for entrySet.remove
    983      */
    984     protected synchronized boolean findAndRemoveEntry(Map.Entry entry) {
    985         Object key = entry.getKey();
    986         Object v = get(key);
    987         if (v != null && v.equals(entry.getValue())) {
    988             remove(key);
    989             return true;
    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. Use the Enumeration
    1009      * methods on the returned object to fetch the elements sequentially.
    1010      *
    1011      * @return an enumeration of the values in this table.
    1012      * @see java.util.Enumeration
    1013      * @see #keys()
    1014      * @see #values()
    1015      * @see Map
    1016      */
    1017
    1018     public Enumeration elements() {
    1019         return new ValueIterator();
    1020     }
    1021
    1022     /***
    1023      * ConcurrentReaderHashMap collision list entry.
    1024      */
    1025
    1026     protected static class Entry implements Map.Entry {
    1027
    1028         /*
    1029          * The use of volatile for value field ensures that we can detect status
    1030          * changes without synchronization. The other fields are never changed,
    1031          * and are marked as final.
    1032          */
    1033
    1034         protected final int hash;
    1035
    1036         protected final Object key;
    1037
    1038         protected final Entry next;
    1039
    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, unless the
    1057          * set or iterator is used under synchronization of the table as a whole
    1058          * (or you can otherwise guarantee lack of concurrent modification),
    1059          * <tt>getValue</tt> <em>might</em> return null, reflecting the fact
    1060          * that the entry has been concurrently removed. However, there are no
    1061          * assurances that concurrent removals will be reflected using this
    1062          * method.
    1063          *
    1064          * @return the current value, or null if the entry has been detectably
    1065          *         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> is
    1076          * not strictly guaranteed to actually replace the value field obtained
    1077          * via the <tt>get</tt> operation of the underlying hash table in
    1078          * multithreaded applications. If iterator-wide synchronization is not
    1079          * used, and any other concurrent <tt>put</tt> or <tt>remove</tt>
    1080          * operations occur, sometimes even to <em>other</em> entries, then
    1081          * this change is not guaranteed to be reflected in the hash table. (It
    1082          * might, or it might not. There are no assurances either way.)
    1083          *
    1084          * @param value
    1085          *            the new value.
    1086          * @return the previous value, or null if entry has been detectably
    1087          *         removed.
    1088          * @exception NullPointerException
    1089          *                if the value is <code>null</code>.
    1090          *
    1091          */
    1092
    1093         public Object setValue(Object value) {
    1094             if (value == null)
    1095                 throw new NullPointerException();
    1096             Object oldValue = this.value;
    1097             this.value = value;
    1098             return oldValue;
    1099         }
    1100
    1101         public boolean equals(Object o) {
    1102             if (!(o instanceof Map.Entry))
    1103                 return false;
    1104             Map.Entry e = (Map.Entry) o;
    1105             return (key.equals(e.getKey()) && value.equals(e.getValue()));
    1106         }
    1107
    1108         public int hashCode() {
    1109             return key.hashCode() ^ value.hashCode();
    1110         }
    1111
    1112         public String toString() {
    1113             return key + "=" + value;
    1114         }
    1115
    1116     }
    1117
    1118     protected class HashIterator implements Iterator, Enumeration {
    1119         protected final Entry[] tab; // snapshot of table
    1120
    1121         protected int index; // current slot
    1122
    1123         protected Entry entry = null; // current node of slot
    1124
    1125         protected Object currentKey; // key for current node
    1126
    1127         protected Object currentValue; // value for current node
    1128
    1129         protected Entry lastReturned = null; // last node returned by next
    1130
    1131         protected HashIterator() {
    1132             tab = ConcurrentReaderHashMap.this.getTableForReading();
    1133             index = tab.length - 1;
    1134         }
    1135
    1136         public boolean hasMoreElements() {
    1137             return hasNext();
    1138         }
    1139
    1140         public Object nextElement() {
    1141             return next();
    1142         }
    1143
    1144         public boolean hasNext() {
    1145
    1146             /*
    1147              * currentkey and currentValue are set here to ensure that next()
    1148              * returns normally if hasNext() returns true. This avoids surprises
    1149              * especially when final element is removed during traversal --
    1150              * instead, we just ignore the removal during current traversal.
    1151              */
    1152
    1153             for (;;) {
    1154                 if (entry != null) {
    1155                     Object v = entry.value;
    1156                     if (v != null) {
    1157                         currentKey = entry.key;
    1158                         currentValue = v;
    1159                         return true;
    1160                     } else
    1161                         entry = entry.next;
    1162                 }
    1163
    1164                 while (entry == null && index >= 0)
    1165                     entry = tab[index--];
    1166
    1167                 if (entry == null) {
    1168                     currentKey = currentValue = null;
    1169                     return false;
    1170                 }
    1171             }
    1172         }
    1173
    1174         protected Object returnValueOfNext() {
    1175             return entry;
    1176         }
    1177
    1178         public Object next() {
    1179             if (currentKey == null && !hasNext())
    1180                 throw new NoSuchElementException();
    1181
    1182             Object result = returnValueOfNext();
    1183             lastReturned = entry;
    1184             currentKey = currentValue = null;
    1185             entry = entry.next;
    1186             return result;
    1187         }
    1188
    1189         public void remove() {
    1190             if (lastReturned == null)
    1191                 throw new IllegalStateException();
    1192             ConcurrentReaderHashMap.this.remove(lastReturned.key);
    1193             lastReturned = null;
    1194         }
    1195
    1196     }
    1197
    1198     protected class KeyIterator extends HashIterator {
    1199         protected Object returnValueOfNext() {
    1200             return currentKey;
    1201         }
    1202     }
    1203
    1204     protected class ValueIterator extends HashIterator {
    1205         protected Object returnValueOfNext() {
    1206             return currentValue;
    1207         }
    1208     }
    1209
    1210     /***
    1211      * Save the state of the <tt>ConcurrentReaderHashMap</tt> instance to a
    1212      * stream (i.e., serialize it).
    1213      *
    1214      * @serialData The <i>capacity </i> of the ConcurrentReaderHashMap (the
    1215      *             length of the bucket array) is emitted (int), followed by the
    1216      *             <i>size </i> of the ConcurrentReaderHashMap (the number of
    1217      *             key-value mappings), followed by the key (Object) and value
    1218      *             (Object) for each key-value mapping represented by the
    1219      *             ConcurrentReaderHashMap The key-value mappings are emitted in
    1220      *             no particular order.
    1221      */
    1222
    1223     private synchronized void writeObject(java.io.ObjectOutputStream s)
    1224             throws IOException {
    1225         // Write out the threshold, loadfactor, and any hidden stuff
    1226         s.defaultWriteObject();
    1227
    1228         // Write out number of buckets
    1229         s.writeInt(table.length);
    1230
    1231         // Write out size (number of Mappings)
    1232         s.writeInt(count);
    1233
    1234         // Write out keys and values (alternating)
    1235         for (int index = table.length - 1; index >= 0; index--) {
    1236             Entry entry = table[index];
    1237
    1238             while (entry != null) {
    1239                 s.writeObject(entry.key);
    1240                 s.writeObject(entry.value);
    1241                 entry = entry.next;
    1242             }
    1243         }
    1244     }
    1245
    1246     /***
    1247      * Reconstitute the <tt>ConcurrentReaderHashMap</tt> instance from a
    1248      * stream (i.e., deserialize it).
    1249      */
    1250     private synchronized void readObject(java.io.ObjectInputStream s)
    1251             throws IOException, ClassNotFoundException {
    1252         // Read in the threshold, loadfactor, and any hidden stuff
    1253         s.defaultReadObject();
    1254
    1255         // Read in number of buckets and allocate the bucket array;
    1256         int numBuckets = s.readInt();
    1257         table = new Entry[numBuckets];
    1258
    1259         // Read in size (number of Mappings)
    1260         int size = s.readInt();
    1261
    1262         // Read the keys and values, and put the mappings in the table
    1263         for (int i = 0; i < size; i++) {
    1264             Object key = s.readObject();
    1265             Object value = s.readObject();
    1266             put(key, value);
    1267         }
    1268     }
    1269
    1270     /***
    1271      * Return the number of slots in this table
    1272      */
    1273
    1274     public synchronized int capacity() {
    1275         return table.length;
    1276     }
    1277
    1278     /***
    1279      * Return the load factor
    1280      */
    1281     public float loadFactor() {
    1282         return loadFactor;
    1283     }
    1284 }