--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/EDU/oswego/cs/dl/util/concurrent/ConcurrentReaderHashMap.java	Sat Mar 21 11:00:06 2009 +0000
@@ -0,0 +1,1274 @@
+/*
+  File: ConcurrentReaderHashMap
+
+  Written by Doug Lea. Adapted from JDK1.2 HashMap.java and Hashtable.java
+  which carries the following copyright:
+
+     * Copyright 1997 by Sun Microsystems, Inc.,
+     * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
+     * All rights reserved.
+     *
+     * This software is the confidential and proprietary information
+     * of Sun Microsystems, Inc. ("Confidential Information").  You
+     * shall not disclose such Confidential Information and shall use
+     * it only in accordance with the terms of the license agreement
+     * you entered into with Sun.
+
+  History:
+  Date       Who                What
+  28oct1999  dl               Created
+  14dec1999  dl               jmm snapshot
+  19apr2000  dl               use barrierLock
+  12jan2001  dl               public release
+  17nov2001  dl               Minor tunings
+  20may2002  dl               BarrierLock can now be serialized.
+  09dec2002  dl               Fix interference checks.
+*/
+
+package EDU.oswego.cs.dl.util.concurrent;
+
+import java.util.Map;
+import java.util.AbstractMap;
+import java.util.AbstractSet;
+import java.util.AbstractCollection;
+import java.util.Collection;
+import java.util.Set;
+import java.util.Iterator;
+import java.util.Enumeration;
+import java.util.ConcurrentModificationException;
+import java.util.NoSuchElementException;
+
+import java.io.Serializable;
+import java.io.IOException;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+
+
+/**
+ * A version of Hashtable that supports mostly-concurrent reading, but
+ * exclusive writing.  Because reads are not limited to periods
+ * without writes, a concurrent reader policy is weaker than a classic
+ * reader/writer policy, but is generally faster and allows more
+ * concurrency. This class is a good choice especially for tables that
+ * are mainly created by one thread during the start-up phase of a
+ * program, and from then on, are mainly read (with perhaps occasional
+ * additions or removals) in many threads.  If you also need concurrency
+ * among writes, consider instead using ConcurrentHashMap.
+ * <p>
+ *
+ * Successful retrievals using get(key) and containsKey(key) usually
+ * run without locking. Unsuccessful ones (i.e., when the key is not
+ * present) do involve brief synchronization (locking).  Also, the
+ * size and isEmpty methods are always synchronized.
+ *
+ * <p> Because retrieval operations can ordinarily overlap with
+ * writing operations (i.e., put, remove, and their derivatives),
+ * retrievals can only be guaranteed to return the results of the most
+ * recently <em>completed</em> operations holding upon their
+ * onset. Retrieval operations may or may not return results
+ * reflecting in-progress writing operations.  However, the retrieval
+ * operations do always return consistent results -- either those
+ * holding before any single modification or after it, but never a
+ * nonsense result.  For aggregate operations such as putAll and
+ * clear, concurrent reads may reflect insertion or removal of only
+ * some entries. In those rare contexts in which you use a hash table
+ * to synchronize operations across threads (for example, to prevent
+ * reads until after clears), you should either encase operations
+ * in synchronized blocks, or instead use java.util.Hashtable.
+ *
+ * <p>
+ *
+ * This class also supports optional guaranteed
+ * exclusive reads, simply by surrounding a call within a synchronized
+ * block, as in <br> 
+ * <code>ConcurrentReaderHashMap t; ... Object v; <br>
+ * synchronized(t) { v = t.get(k); } </code> <br>
+ *
+ * But this is not usually necessary in practice. For
+ * example, it is generally inefficient to write:
+ *
+ * <pre>
+ *   ConcurrentReaderHashMap t; ...            // Inefficient version
+ *   Object key; ...
+ *   Object value; ...
+ *   synchronized(t) { 
+ *     if (!t.containsKey(key))
+ *       t.put(key, value);
+ *       // other code if not previously present
+ *     }
+ *     else {
+ *       // other code if it was previously present
+ *     }
+ *   }
+ *</pre>
+ * Instead, if the values are intended to be the same in each case, just take advantage of the fact that put returns
+ * null if the key was not previously present:
+ * <pre>
+ *   ConcurrentReaderHashMap t; ...                // Use this instead
+ *   Object key; ...
+ *   Object value; ...
+ *   Object oldValue = t.put(key, value);
+ *   if (oldValue == null) {
+ *     // other code if not previously present
+ *   }
+ *   else {
+ *     // other code if it was previously present
+ *   }
+ *</pre>
+ * <p>
+ *
+ * Iterators and Enumerations (i.e., those returned by
+ * keySet().iterator(), entrySet().iterator(), values().iterator(),
+ * keys(), and elements()) return elements reflecting the state of the
+ * hash table at some point at or since the creation of the
+ * iterator/enumeration.  They will return at most one instance of
+ * each element (via next()/nextElement()), but might or might not
+ * reflect puts and removes that have been processed since they were
+ * created.  They do <em>not</em> throw ConcurrentModificationException.
+ * However, these iterators are designed to be used by only one
+ * thread at a time. Sharing an iterator across multiple threads may
+ * lead to unpredictable results if the table is being concurrently
+ * modified.  Again, you can ensure interference-free iteration by
+ * enclosing the iteration in a synchronized block.  <p>
+ *
+ * This class may be used as a direct replacement for any use of
+ * java.util.Hashtable that does not depend on readers being blocked
+ * during updates. Like Hashtable but unlike java.util.HashMap,
+ * this class does NOT allow <tt>null</tt> to be used as a key or
+ * value.  This class is also typically faster than ConcurrentHashMap
+ * when there is usually only one thread updating the table, but 
+ * possibly many retrieving values from it.
+ * <p>
+ *
+ * Implementation note: A slightly faster implementation of
+ * this class will be possible once planned Java Memory Model
+ * revisions are in place.
+ *
+ * <p>[<a href="http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html"> Introduction to this package. </a>]
+
+ **/
+
+
+public class ConcurrentReaderHashMap 
+  extends AbstractMap 
+  implements Map, Cloneable, Serializable {
+
+
+  /*
+    The basic strategy is an optimistic-style scheme based on
+    the guarantee that the hash table and its lists are always
+    kept in a consistent enough state to be read without locking:
+
+    * Read operations first proceed without locking, by traversing the
+       apparently correct list of the apparently correct bin. If an
+       entry is found, but not invalidated (value field null), it is
+       returned. If not found, operations must recheck (after a memory
+       barrier) to make sure they are using both the right list and
+       the right table (which can change under resizes). If
+       invalidated, reads must acquire main update lock to wait out
+       the update, and then re-traverse.
+
+    * All list additions are at the front of each bin, making it easy
+       to check changes, and also fast to traverse.  Entry next
+       pointers are never assigned. Remove() builds new nodes when
+       necessary to preserve this.
+
+    * Remove() (also clear()) invalidates removed nodes to alert read
+       operations that they must wait out the full modifications.
+ 
+  */
+
+  /** A Serializable class for barrier lock **/
+  protected static class BarrierLock implements java.io.Serializable { }
+
+  /**
+   * Lock used only for its memory effects.
+   **/
+  protected final BarrierLock barrierLock = new BarrierLock();
+
+  /**
+   * field written to only to guarantee lock ordering.
+   **/
+
+  protected transient Object lastWrite;
+
+  /**
+   * Force a memory synchronization that will cause
+   * all readers to see table. Call only when already
+   * holding main synch lock.
+   **/
+  protected final void recordModification(Object x) { 
+    synchronized(barrierLock) {
+      lastWrite = x;
+    }
+  }
+
+  /**
+   * Get ref to table; the reference and the cells it
+   * accesses will be at least as fresh as from last
+   * use of barrierLock
+   **/
+  protected final Entry[] getTableForReading() { 
+    synchronized(barrierLock) {
+      return table; 
+    }
+  }
+
+
+  /**
+   * The default initial number of table slots for this table (32).
+   * Used when not otherwise specified in constructor.
+   **/
+  public static int DEFAULT_INITIAL_CAPACITY = 32; 
+
+
+  /**
+   * The minimum capacity, used if a lower value is implicitly specified
+   * by either of the constructors with arguments.  
+   * MUST be a power of two.
+   */
+  private static final int MINIMUM_CAPACITY = 4;
+  
+  /**
+   * The maximum capacity, used if a higher value is implicitly specified
+   * by either of the constructors with arguments.
+   * MUST be a power of two <= 1<<30.
+   */
+  private static final int MAXIMUM_CAPACITY = 1 << 30;
+  
+  /**
+   * The default load factor for this table (1.0).
+   * Used when not otherwise specified in constructor.
+   **/
+
+  public static final float DEFAULT_LOAD_FACTOR = 0.75f; 
+
+
+  /**
+   * The hash table data.
+   */
+  protected transient Entry[] table;
+
+  /**
+   * The total number of mappings in the hash table.
+   */
+  protected transient int count;
+
+  /**
+   * The table is rehashed when its size exceeds this threshold.  (The
+   * value of this field is always (int)(capacity * loadFactor).)
+   *
+   * @serial
+   */
+  protected int threshold;
+
+  /**
+   * The load factor for the hash table.
+   *
+   * @serial
+   */
+  protected float loadFactor;
+
+  /**
+   * Returns the appropriate capacity (power of two) for the specified 
+   * initial capacity argument.
+   */
+  private int p2capacity(int initialCapacity) {
+    int cap = initialCapacity;
+    
+    // Compute the appropriate capacity
+    int result;
+    if (cap > MAXIMUM_CAPACITY || cap < 0) {
+      result = MAXIMUM_CAPACITY;
+    } else {
+      result = MINIMUM_CAPACITY;
+      while (result < cap)
+        result <<= 1;
+    }
+    return result;
+  }
+
+  /**
+   * Return hash code for Object x. Since we are using power-of-two
+   * tables, it is worth the effort to improve hashcode via
+   * the same multiplicative scheme as used in IdentityHashMap.
+   */
+  private static int hash(Object x) {
+    int h = x.hashCode();
+    // Multiply by 127 (quickly, via shifts), and mix in some high
+    // bits to help guard against bunching of codes that are
+    // consecutive or equally spaced.
+    return ((h << 7) - h + (h >>> 9) + (h >>> 17));
+  }
+
+  /** 
+   * Check for equality of non-null references x and y. 
+   **/
+  protected boolean eq(Object x, Object y) {
+    return x == y || x.equals(y);
+  }
+
+  /**
+   * Constructs a new, empty map with the specified initial 
+   * capacity and the specified load factor. 
+   *
+   * @param initialCapacity the initial capacity
+   *  The actual initial capacity is rounded to the nearest power of two.
+   * @param loadFactor  the load factor of the ConcurrentReaderHashMap
+   * @throws IllegalArgumentException  if the initial maximum number 
+   *               of elements is less
+   *               than zero, or if the load factor is nonpositive.
+   */
+
+  public ConcurrentReaderHashMap(int initialCapacity, float loadFactor) {
+    if (loadFactor <= 0)
+      throw new IllegalArgumentException("Illegal Load factor: "+
+                                         loadFactor);
+    this.loadFactor = loadFactor;
+
+    int cap = p2capacity(initialCapacity);
+
+    table = new Entry[cap];
+    threshold = (int)(cap * loadFactor);
+  }
+
+  /**
+   * Constructs a new, empty map with the specified initial 
+   * capacity and default load factor.
+   *
+   * @param   initialCapacity   the initial capacity of the 
+   *                            ConcurrentReaderHashMap.
+   * @throws    IllegalArgumentException if the initial maximum number 
+   *              of elements is less
+   *              than zero.
+   */
+
+  public ConcurrentReaderHashMap(int initialCapacity) {
+    this(initialCapacity, DEFAULT_LOAD_FACTOR);
+  }
+
+  /**
+   * Constructs a new, empty map with a default initial capacity
+   * and load factor.
+   */
+
+  public ConcurrentReaderHashMap() {
+    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
+  }
+
+  /**
+   * Constructs a new map with the same mappings as the given map.  The
+   * map is created with a capacity of twice the number of mappings in
+   * the given map or 16 (whichever is greater), and a default load factor.
+   */
+
+  public ConcurrentReaderHashMap(Map t) {
+        this(Math.max((int) (t.size() / DEFAULT_LOAD_FACTOR) + 1, 16),
+             DEFAULT_LOAD_FACTOR);
+    putAll(t);
+  }
+
+  /**
+   * Returns the number of key-value mappings in this map.
+   *
+   * @return the number of key-value mappings in this map.
+   */
+
+  public synchronized int size() {
+    return count;
+  }
+
+  /**
+   * Returns <tt>true</tt> if this map contains no key-value mappings.
+   *
+   * @return <tt>true</tt> if this map contains no key-value mappings.
+   */
+
+  public synchronized boolean isEmpty() {
+    return count == 0;
+  }
+  
+
+
+  /**
+   * Returns the value to which the specified key is mapped in this table.
+   *
+   * @param   key   a key in the table.
+   * @return  the value to which the key is mapped in this table;
+   *          <code>null</code> if the key is not mapped to any value in
+   *          this table.
+   * @exception  NullPointerException  if the key is
+   *               <code>null</code>.
+   * @see     #put(Object, Object)
+   */
+  
+
+  public Object get(Object key) {
+
+    // throw null pointer exception if key null
+    int hash = hash(key);
+
+    /* 
+       Start off at the apparently correct bin.  If entry is found, we
+       need to check after a barrier anyway.  If not found, we need a
+       barrier to check if we are actually in right bin. So either
+       way, we encounter only one barrier unless we need to retry.
+       And we only need to fully synchronize if there have been
+       concurrent modifications.
+    */
+
+    Entry[] tab = table;
+    int index = hash & (tab.length - 1);
+    Entry first = tab[index];
+    Entry e = first;
+
+    for (;;) {
+      if (e == null) {
+
+        // If key apparently not there, check to
+        // make sure this was a valid read
+
+        Entry[] reread = getTableForReading();
+        if (tab == reread && first == tab[index])
+          return null;
+        else {
+          // Wrong list -- must restart traversal at new first
+          tab = reread;
+          e = first = tab[index = hash & (tab.length-1)];
+        }
+
+      }
+
+      else if (e.hash == hash && eq(key, e.key)) {
+        Object value = e.value;
+        if (value != null) 
+          return value;
+
+        // Entry was invalidated during deletion. But it could
+        // have been re-inserted, so we must retraverse.
+        // To avoid useless contention, get lock to wait out modifications
+        // before retraversing.
+
+        synchronized(this) {
+          tab = table;
+        }
+        e = first = tab[index = hash & (tab.length-1)];
+
+      }
+      else
+        e = e.next;
+    }
+  }
+
+
+  /**
+   * Tests if the specified object is a key in this table.
+   * 
+   * @param   key   possible key.
+   * @return  <code>true</code> if and only if the specified object 
+   *          is a key in this table, as determined by the 
+   *          <tt>equals</tt> method; <code>false</code> otherwise.
+   * @exception  NullPointerException  if the key is
+   *               <code>null</code>.
+   * @see     #contains(Object)
+   */
+
+
+  public boolean containsKey(Object key) {
+    return get(key) != null;
+  }
+
+  /**
+   * Maps the specified <code>key</code> to the specified 
+   * <code>value</code> in this table. Neither the key nor the 
+   * value can be <code>null</code>. <p>
+   *
+   * The value can be retrieved by calling the <code>get</code> method 
+   * with a key that is equal to the original key. 
+   *
+   * @param      key     the table key.
+   * @param      value   the value.
+   * @return     the previous value of the specified key in this table,
+   *             or <code>null</code> if it did not have one.
+   * @exception  NullPointerException  if the key or value is
+   *               <code>null</code>.
+   * @see     Object#equals(Object)
+   * @see     #get(Object)
+   */
+
+  public Object put(Object key, Object value) {
+    if (value == null) 
+      throw new NullPointerException();
+    
+    int hash = hash(key);
+    Entry[] tab = table;
+    int index = hash & (tab.length-1);
+    Entry first = tab[index];
+    Entry e;
+
+    for (e = first; e != null; e = e.next)
+      if (e.hash == hash && eq(key, e.key))
+        break;
+
+    synchronized(this) {
+      if (tab == table) {
+        if (e == null) {
+          //  make sure we are adding to correct list
+          if (first == tab[index]) {
+            //  Add to front of list
+            Entry newEntry = new Entry(hash, key, value, first);
+            tab[index] = newEntry;
+            if (++count >= threshold) rehash();
+            else recordModification(newEntry);
+            return null;
+          }
+        }
+        else {
+          Object oldValue = e.value; 
+          if (first == tab[index] && oldValue != null) {
+            e.value = value;
+            return oldValue;
+          }
+        }
+      }
+      
+      // retry if wrong list or lost race against concurrent remove
+      return sput(key, value, hash);
+    }
+  }
+
+
+  /**
+   * Continuation of put(), called only when synch lock is
+   * held and interference has been detected.
+   **/
+  protected Object sput(Object key, Object value, int hash) { 
+
+    Entry[] tab = table;
+    int index = hash & (tab.length-1);
+    Entry first = tab[index];
+    Entry e = first;
+
+    for (;;) {
+      if (e == null) {
+        Entry newEntry = new Entry(hash, key, value, first);
+        tab[index] = newEntry;
+        if (++count >= threshold) rehash();
+        else recordModification(newEntry);
+        return null;
+      }
+      else if (e.hash == hash && eq(key, e.key)) {
+        Object oldValue = e.value; 
+        e.value = value;
+        return oldValue;
+      }
+      else
+        e = e.next;
+    }
+  }
+
+
+  /**
+   * Rehashes the contents of this map into a new table
+   * with a larger capacity. This method is called automatically when the
+   * number of keys in this map exceeds its capacity and load factor.
+   */
+  protected void rehash() { 
+    Entry[] oldTable = table;
+    int oldCapacity = oldTable.length;
+    if (oldCapacity >= MAXIMUM_CAPACITY) {
+      threshold = Integer.MAX_VALUE; // avoid retriggering
+      return;
+    }
+
+    int newCapacity = oldCapacity << 1;
+    int mask = newCapacity - 1;
+    threshold = (int)(newCapacity * loadFactor);
+
+    Entry[] newTable = new Entry[newCapacity];
+    /*
+     * Reclassify nodes in each list to new Map.  Because we are
+     * using power-of-two expansion, the elements from each bin
+     * must either stay at same index, or move to
+     * oldCapacity+index. We also eliminate unnecessary node
+     * creation by catching cases where old nodes can be reused
+     * because their next fields won't change. Statistically, at
+     * the default threshhold, only about one-sixth of them need
+     * cloning. (The nodes they replace will be garbage
+     * collectable as soon as they are no longer referenced by any
+     * reader thread that may be in the midst of traversing table
+     * right now.)
+     */
+    
+    for (int i = 0; i < oldCapacity ; i++) {
+      // We need to guarantee that any existing reads of old Map can
+      //  proceed. So we cannot yet null out each bin.  
+      Entry e = oldTable[i];
+      
+      if (e != null) {
+        int idx = e.hash & mask;
+        Entry next = e.next;
+        
+        //  Single node on list
+        if (next == null) 
+          newTable[idx] = e;
+        
+        else {    
+          // Reuse trailing consecutive sequence of all same bit
+          Entry lastRun = e;
+          int lastIdx = idx;
+          for (Entry last = next; last != null; last = last.next) {
+            int k = last.hash & mask;
+            if (k != lastIdx) {
+              lastIdx = k;
+              lastRun = last;
+            }
+          }
+          newTable[lastIdx] = lastRun;
+          
+          // Clone all remaining nodes
+          for (Entry p = e; p != lastRun; p = p.next) {
+            int k = p.hash & mask;
+            newTable[k] = new Entry(p.hash, p.key, 
+                                    p.value, newTable[k]);
+          }
+        }
+      }
+    }
+
+    table = newTable;
+    recordModification(newTable);
+  }
+
+  /**
+   * Removes the key (and its corresponding value) from this 
+   * table. This method does nothing if the key is not in the table.
+   *
+   * @param   key   the key that needs to be removed.
+   * @return  the value to which the key had been mapped in this table,
+   *          or <code>null</code> if the key did not have a mapping.
+   * @exception  NullPointerException  if the key is
+   *               <code>null</code>.
+   */
+
+  public Object remove(Object key) {
+    /*
+      Find the entry, then 
+        1. Set value field to null, to force get() to retry
+        2. Rebuild the list without this entry.
+           All entries following removed node can stay in list, but
+           all preceeding ones need to be cloned.  Traversals rely
+           on this strategy to ensure that elements will not be
+          repeated during iteration.
+    */
+          
+
+    int hash = hash(key);
+    Entry[] tab = table;
+    int index = hash & (tab.length-1);
+    Entry first = tab[index];
+    Entry e = first;
+      
+    for (e = first; e != null; e = e.next) 
+      if (e.hash == hash && eq(key, e.key)) 
+        break;
+
+
+    synchronized(this) {
+      if (tab == table) {
+        if (e == null) {
+          if (first == tab[index])
+            return null;
+        }
+        else {
+          Object oldValue = e.value;
+          if (first == tab[index] && oldValue != null) {
+            e.value = null;
+            count--;
+            
+            Entry head = e.next;
+            for (Entry p = first; p != e; p = p.next) 
+              head = new Entry(p.hash, p.key, p.value, head);
+            
+            tab[index] = head;
+            recordModification(head);
+            return oldValue;
+          }
+        }
+      }
+    
+      // Wrong list or interference
+      return sremove(key, hash);
+    }
+  }
+
+  /**
+   * Continuation of remove(), called only when synch lock is
+   * held and interference has been detected.
+   **/
+
+  protected Object sremove(Object key, int hash) {
+    Entry[] tab = table;
+    int index = hash & (tab.length-1);
+    Entry first = tab[index];
+      
+    for (Entry e = first; e != null; e = e.next) {
+      if (e.hash == hash && eq(key, e.key)) {
+        Object oldValue = e.value;
+        e.value = null;
+        count--;
+        Entry head = e.next;
+        for (Entry p = first; p != e; p = p.next) 
+          head = new Entry(p.hash, p.key, p.value, head);
+        
+        tab[index] = head;
+        recordModification(head);
+        return oldValue;
+      }
+    }
+    return null;
+  }
+
+
+  /**
+   * Returns <tt>true</tt> if this map maps one or more keys to the
+   * specified value. Note: This method requires a full internal
+   * traversal of the hash table, and so is much slower than
+   * method <tt>containsKey</tt>.
+   *
+   * @param value value whose presence in this map is to be tested.
+   * @return <tt>true</tt> if this map maps one or more keys to the
+   * specified value.  
+   * @exception  NullPointerException  if the value is <code>null</code>.
+   */
+
+  public boolean containsValue(Object value) {
+    if (value == null) throw new NullPointerException();
+
+    Entry tab[] = getTableForReading();
+    
+    for (int i = 0 ; i < tab.length; ++i) {
+      for (Entry e = tab[i] ; e != null ; e = e.next) 
+        if (value.equals(e.value))
+          return true;
+    }
+
+    return false;
+  }
+
+  /**
+   * Tests if some key maps into the specified value in this table.
+   * This operation is more expensive than the <code>containsKey</code>
+   * method.<p>
+   *
+   * Note that this method is identical in functionality to containsValue,
+   * (which is part of the Map interface in the collections framework).
+   * 
+   * @param      value   a value to search for.
+   * @return     <code>true</code> if and only if some key maps to the
+   *             <code>value</code> argument in this table as 
+   *             determined by the <tt>equals</tt> method;
+   *             <code>false</code> otherwise.
+   * @exception  NullPointerException  if the value is <code>null</code>.
+   * @see        #containsKey(Object)
+   * @see        #containsValue(Object)
+   * @see	   Map
+   */
+
+  public boolean contains(Object value) {
+    return containsValue(value);
+  }
+
+
+  /**
+   * Copies all of the mappings from the specified map to this one.
+   * 
+   * These mappings replace any mappings that this map had for any of the
+   * keys currently in the specified Map.
+   *
+   * @param t Mappings to be stored in this map.
+   */
+
+  public synchronized void putAll(Map t) {
+    int n = t.size();
+    if (n == 0)
+      return;
+
+    // Expand enough to hold at least n elements without resizing.
+    // We can only resize table by factor of two at a time.
+    // It is faster to rehash with fewer elements, so do it now.
+    while (n >= threshold)
+      rehash();
+
+    for (Iterator it = t.entrySet().iterator(); it.hasNext();) {
+      Map.Entry entry = (Map.Entry) it.next();
+      Object key = entry.getKey();
+      Object value = entry.getValue();
+      put(key, value);
+    }
+  }
+
+
+  /**
+   * Removes all mappings from this map.
+   */
+  public synchronized void clear() {
+    Entry tab[] = table;
+    for (int i = 0; i < tab.length ; ++i) { 
+
+      // must invalidate all to force concurrent get's to wait and then retry
+      for (Entry e = tab[i]; e != null; e = e.next) 
+        e.value = null; 
+
+      tab[i] = null;
+    }
+    count = 0;
+    recordModification(tab);
+  }
+
+  /**
+   * Returns a shallow copy of this 
+   * <tt>ConcurrentReaderHashMap</tt> instance: the keys and
+   * values themselves are not cloned.
+   *
+   * @return a shallow copy of this map.
+   */
+
+  public synchronized Object clone() {
+    try { 
+      ConcurrentReaderHashMap t = (ConcurrentReaderHashMap)super.clone();
+
+      t.keySet = null;
+      t.entrySet = null;
+      t.values = null;
+
+      Entry[] tab = table;
+      t.table = new Entry[tab.length];
+      Entry[] ttab = t.table;
+
+      for (int i = 0; i < tab.length; ++i) {
+        Entry first = null;
+        for (Entry e = tab[i]; e != null; e = e.next) 
+          first = new Entry(e.hash, e.key, e.value, first);
+        ttab[i] = first;
+      }
+
+      return t;
+    } 
+    catch (CloneNotSupportedException e) { 
+      // this shouldn't happen, since we are Cloneable
+      throw new InternalError();
+    }
+  }
+
+  // Views
+
+  protected transient Set keySet = null;
+  protected transient Set entrySet = null;
+  protected transient Collection values = null;
+
+  /**
+   * Returns a set view of the keys contained in this map.  The set is
+   * backed by the map, so changes to the map are reflected in the set, and
+   * vice-versa.  The set supports element removal, which removes the
+   * corresponding mapping from this map, via the <tt>Iterator.remove</tt>,
+   * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
+   * <tt>clear</tt> operations.  It does not support the <tt>add</tt> or
+   * <tt>addAll</tt> operations.
+   *
+   * @return a set view of the keys contained in this map.
+   */
+  
+  public Set keySet() {
+    Set ks = keySet;
+    return (ks != null)? ks : (keySet = new KeySet());
+  }
+  
+  private class KeySet extends AbstractSet {
+    public Iterator iterator() {
+      return new KeyIterator();
+    }
+    public int size() {
+      return ConcurrentReaderHashMap.this.size();
+    }
+    public boolean contains(Object o) {
+      return ConcurrentReaderHashMap.this.containsKey(o);
+    }
+    public boolean remove(Object o) {
+      return ConcurrentReaderHashMap.this.remove(o) != null;
+    }
+    public void clear() {
+      ConcurrentReaderHashMap.this.clear();
+    }
+  }
+
+  /**
+   * Returns a collection view of the values contained in this map.  The
+   * collection is backed by the map, so changes to the map are reflected in
+   * the collection, and vice-versa.  The collection supports element
+   * removal, which removes the corresponding mapping from this map, via the
+   * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
+   * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
+   * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
+   *
+   * @return a collection view of the values contained in this map.
+   */
+  
+  public Collection values() {
+    Collection vs = values;
+    return (vs != null)? vs : (values = new Values());
+  }
+  
+  private class Values extends AbstractCollection {
+    public Iterator iterator() {
+      return new ValueIterator();
+    }
+    public int size() {
+      return ConcurrentReaderHashMap.this.size();
+    }
+    public boolean contains(Object o) {
+      return ConcurrentReaderHashMap.this.containsValue(o);
+    }
+    public void clear() {
+      ConcurrentReaderHashMap.this.clear();
+    }
+  }
+
+  /**
+   * Returns a collection view of the mappings contained in this map.  Each
+   * element in the returned collection is a <tt>Map.Entry</tt>.  The
+   * collection is backed by the map, so changes to the map are reflected in
+   * the collection, and vice-versa.  The collection supports element
+   * removal, which removes the corresponding mapping from the map, via the
+   * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
+   * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
+   * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
+   *
+   * @return a collection view of the mappings contained in this map.
+   */
+  
+  public Set entrySet() {
+    Set es = entrySet;
+    return (es != null) ? es : (entrySet = new EntrySet());
+  }
+
+  private class EntrySet extends AbstractSet {
+    public Iterator iterator() {
+      return new HashIterator();
+    }
+    public boolean contains(Object o) {
+      if (!(o instanceof Map.Entry))
+        return false;
+      Map.Entry entry = (Map.Entry)o;
+      Object v = ConcurrentReaderHashMap.this.get(entry.getKey());
+      return v != null && v.equals(entry.getValue());
+    }
+    public boolean remove(Object o) {
+      if (!(o instanceof Map.Entry))
+        return false;
+      return ConcurrentReaderHashMap.this.findAndRemoveEntry((Map.Entry)o);
+    }
+    public int size() {
+      return ConcurrentReaderHashMap.this.size();
+    }
+    public void clear() {
+      ConcurrentReaderHashMap.this.clear();
+    }
+  }
+
+  /**
+   * Helper method for entrySet.remove
+   **/
+  protected synchronized boolean findAndRemoveEntry(Map.Entry entry) {
+    Object key = entry.getKey();
+    Object v = get(key);
+    if (v != null && v.equals(entry.getValue())) {
+      remove(key);
+      return true;
+    }
+    else
+      return false;
+  }
+
+  /**
+   * Returns an enumeration of the keys in this table.
+   *
+   * @return  an enumeration of the keys in this table.
+   * @see     Enumeration
+   * @see     #elements()
+   * @see	#keySet()
+   * @see	Map
+   */
+  public Enumeration keys() {
+    return new KeyIterator();
+  }
+
+  /**
+   * Returns an enumeration of the values in this table.
+   * Use the Enumeration methods on the returned object to fetch the elements
+   * sequentially.
+   *
+   * @return  an enumeration of the values in this table.
+   * @see     java.util.Enumeration
+   * @see     #keys()
+   * @see	#values()
+   * @see	Map
+   */
+  
+  public Enumeration elements() {
+    return new ValueIterator();
+  }
+
+
+  /**
+   * ConcurrentReaderHashMap collision list entry.
+   */
+
+  protected static class Entry implements Map.Entry {
+
+    /* 
+       The use of volatile for value field ensures that
+       we can detect status changes without synchronization.
+       The other fields are never changed, and are
+       marked as final. 
+    */
+
+    protected final int hash;
+    protected final Object key;
+    protected final Entry next;
+    protected volatile Object value;
+
+    Entry(int hash, Object key, Object value, Entry next) {
+      this.hash = hash;
+      this.key = key;
+      this.next = next;
+      this.value = value;
+    }
+
+    // Map.Entry Ops 
+
+    public Object getKey() {
+      return key;
+    }
+
+    /**
+     * Get the value.  Note: In an entrySet or entrySet.iterator,
+     * unless the set or iterator is used under synchronization of the
+     * table as a whole (or you can otherwise guarantee lack of
+     * concurrent modification), <tt>getValue</tt> <em>might</em>
+     * return null, reflecting the fact that the entry has been
+     * concurrently removed. However, there are no assurances that
+     * concurrent removals will be reflected using this method.
+     * 
+     * @return     the current value, or null if the entry has been 
+     * detectably removed.
+     **/
+    public Object getValue() {
+      return value; 
+    }
+
+    /**
+     * Set the value of this entry.  Note: In an entrySet or
+     * entrySet.iterator), unless the set or iterator is used under
+     * synchronization of the table as a whole (or you can otherwise
+     * guarantee lack of concurrent modification), <tt>setValue</tt>
+     * is not strictly guaranteed to actually replace the value field
+     * obtained via the <tt>get</tt> operation of the underlying hash
+     * table in multithreaded applications.  If iterator-wide
+     * synchronization is not used, and any other concurrent
+     * <tt>put</tt> or <tt>remove</tt> operations occur, sometimes
+     * even to <em>other</em> entries, then this change is not
+     * guaranteed to be reflected in the hash table. (It might, or it
+     * might not. There are no assurances either way.)
+     *
+     * @param      value   the new value.
+     * @return     the previous value, or null if entry has been detectably
+     * removed.
+     * @exception  NullPointerException  if the value is <code>null</code>.
+     * 
+     **/
+
+    public Object setValue(Object value) {
+      if (value == null)
+        throw new NullPointerException();
+      Object oldValue = this.value;
+      this.value = value;
+      return oldValue;
+    }
+
+    public boolean equals(Object o) {
+      if (!(o instanceof Map.Entry))
+        return false;
+      Map.Entry e = (Map.Entry)o;
+      return (key.equals(e.getKey()) && value.equals(e.getValue()));
+    }
+    
+    public int hashCode() {
+      return  key.hashCode() ^ value.hashCode();
+    }
+    
+    public String toString() {
+      return key + "=" + value;
+    }
+
+  }
+
+  protected class HashIterator implements Iterator, Enumeration {
+    protected final Entry[] tab;           // snapshot of table
+    protected int index;                   // current slot 
+    protected Entry entry = null;          // current node of slot
+    protected Object currentKey;           // key for current node
+    protected Object currentValue;         // value for current node
+    protected Entry lastReturned = null;   // last node returned by next
+
+    protected HashIterator() {
+      tab = ConcurrentReaderHashMap.this.getTableForReading();
+      index = tab.length - 1;
+    }
+
+    public boolean hasMoreElements() { return hasNext(); }
+    public Object nextElement() { return next(); }
+
+
+    public boolean hasNext() {
+
+      /*
+        currentkey and currentValue are set here to ensure that next()
+        returns normally if hasNext() returns true. This avoids
+        surprises especially when final element is removed during
+        traversal -- instead, we just ignore the removal during
+        current traversal.  
+      */
+
+      for (;;) {
+        if (entry != null) {
+          Object v = entry.value;
+          if (v != null) {
+            currentKey = entry.key;
+            currentValue = v;
+            return true;
+          }
+          else
+            entry = entry.next;
+        }
+
+        while (entry == null && index >= 0)
+          entry = tab[index--];
+
+        if (entry == null) {
+          currentKey = currentValue = null;
+          return false;
+        }
+      }
+    }
+
+    protected Object returnValueOfNext() { return entry; }
+
+    public Object next() {
+      if (currentKey == null && !hasNext())
+        throw new NoSuchElementException();
+
+      Object result = returnValueOfNext();
+      lastReturned = entry;
+      currentKey = currentValue = null;
+      entry = entry.next;
+      return result;
+    }
+
+    public void remove() {
+      if (lastReturned == null)
+        throw new IllegalStateException();
+      ConcurrentReaderHashMap.this.remove(lastReturned.key);
+      lastReturned = null;
+    }
+
+  }
+
+
+  protected class KeyIterator extends HashIterator {
+    protected Object returnValueOfNext() { return currentKey; }
+  }
+  
+  protected class ValueIterator extends HashIterator {
+    protected Object returnValueOfNext() { return currentValue; }
+  }
+  
+
+
+  /**
+   * Save the state of the <tt>ConcurrentReaderHashMap</tt> 
+   * instance to a stream (i.e.,
+   * serialize it).
+   *
+   * @serialData The <i>capacity</i> of the 
+   * ConcurrentReaderHashMap (the length of the
+   * bucket array) is emitted (int), followed  by the
+   * <i>size</i> of the ConcurrentReaderHashMap (the number of key-value
+   * mappings), followed by the key (Object) and value (Object)
+   * for each key-value mapping represented by the ConcurrentReaderHashMap
+   * The key-value mappings are emitted in no particular order.
+   */
+
+  private synchronized void writeObject(java.io.ObjectOutputStream s)
+    throws IOException  {
+    // Write out the threshold, loadfactor, and any hidden stuff
+    s.defaultWriteObject();
+    
+    // Write out number of buckets
+    s.writeInt(table.length);
+    
+    // Write out size (number of Mappings)
+    s.writeInt(count);
+    
+    // Write out keys and values (alternating)
+    for (int index = table.length-1; index >= 0; index--) {
+      Entry entry = table[index];
+      
+      while (entry != null) {
+        s.writeObject(entry.key);
+        s.writeObject(entry.value);
+        entry = entry.next;
+      }
+    }
+  }
+
+  /**
+   * Reconstitute the <tt>ConcurrentReaderHashMap</tt> 
+   * instance from a stream (i.e.,
+   * deserialize it).
+   */
+  private synchronized void readObject(java.io.ObjectInputStream s)
+    throws IOException, ClassNotFoundException  {
+    // Read in the threshold, loadfactor, and any hidden stuff
+    s.defaultReadObject();
+
+    // Read in number of buckets and allocate the bucket array;
+    int numBuckets = s.readInt();
+    table = new Entry[numBuckets];
+    
+    // Read in size (number of Mappings)
+    int size = s.readInt();
+    
+    // Read the keys and values, and put the mappings in the table
+    for (int i=0; i<size; i++) {
+      Object key = s.readObject();
+      Object value = s.readObject();
+      put(key, value);
+    }
+  }
+  
+  /** 
+   * Return the number of slots in this table 
+   **/
+
+  public synchronized int capacity() {
+    return table.length;
+  }
+
+  /** 
+   * Return the load factor 
+   **/
+  public float loadFactor() {
+    return loadFactor;
+  }
+}