concurrentreaderhashmap.java

webwork source

    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;