Collections Data Structure Java

 * 
 * 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.
 * 
 * 

 * 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 completed 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.
 * 
 * 

 * 
 * This class also supports optional guaranteed exclusive reads, simply by
 * surrounding a call within a synchronized block, as in 

 * ConcurrentReaderHashMap t; ... Object v; 

 * synchronized(t) { v = t.get(k); }  

 * 
 * But this is not usually necessary in practice. For example, it is generally
 * inefficient to write:
 * 
 * 

 *             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
 *               }
 *             }
 * 

 *             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
 *             }
 * 

 * 
 * 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
 * not 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.
 * 

 * 
 * 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 null 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.
 * 

 * 
 * Implementation note: A slightly faster implementation of this class will be
 * possible once planned Java Memory Model revisions are in place.
 * 
 * 

[ * href="http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html">
 * Introduction to this package. ]
 * 
 */
public class ConcurrentReaderHashMap extends AbstractMap implements Map, Cloneable, Serializable
{
  private static final long serialVersionUID = 1L;
  /*
   * 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
  {
    private static final long serialVersionUID = 1L;
  }
  /**
   * 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.
   * @param x 
   */
  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
   * @return table cells
   */
  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 final 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.
   * @param initialCapacity
   * @return appropriate capacity
   */
  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.
   * @param x 
   * @return hash code
   */
  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.
   * @param x 
   * @param y 
   * @return equality
   */
  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.
   * @param t 
   */
  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 true if this map contains no key-value mappings.
   * 
   * @return true 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;
   *         null if the key is not mapped to any value in this
   *         table.
   * @exception NullPointerException
   *                if the key is null.
   * @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 true if and only if the specified object is a key
   *         in this table, as determined by the equals method;
   *         false otherwise.
   * @exception NullPointerException
   *                if the key is null.
   * @see #contains(Object)
   */
  public boolean containsKey(Object key)
  {
    return get(key) != null;
  }
  /**
   * Maps the specified key to the specified value
   * in this table. Neither the key nor the value can be null.
   * 

   * 
   * The value can be retrieved by calling the get 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
   *         null if it did not have one.
   * @exception NullPointerException
   *                if the key or value is null.
   * @see Object#equals(Object)
   * @see #get(Object)
   */
  public Object put(Object key, Object value)
  {
    if (value == null)
    {
      throw new IllegalArgumentException("Value must not be null");
    }
    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.
   * @param key 
   * @param value 
   * @param hash 
   * @return continuation object
   */
  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
   *         null if the key did not have a mapping.
   * @exception NullPointerException
   *                if the key is null.
   */
  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.
   * @param key 
   * @param hash 
   * @return continuation object
   */
  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 true 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 containsKey.
   * 
   * @param value
   *            value whose presence in this map is to be tested.
   * @return true if this map maps one or more keys to the
   *         specified value.
   * @exception NullPointerException
   *                if the value is null.
   */
  public boolean containsValue(Object value)
  {
    if (value == null)
    {
      throw new IllegalArgumentException("Value must not be null");
    }
    
    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 containsKey method.
   *