concurrenthashmap.java

一个很好的微工作流内核

        for (int i = s; i < tab.length; i+= segments.length) {
          for (Entry e = tab[i]; e != null; e = e.next) 
            e.value = null; 
          tab[i] = null;
          seg.count = 0;
        }
      }
    }
  }

  /**
   * Returns a shallow copy of this 
   * <tt>ConcurrentHashMap</tt> instance: the keys and
   * values themselves are not cloned.
   *
   * @return a shallow copy of this map.
   */

  public Object clone() {
    // We cannot call super.clone, since it would share final segments array,
    // and there's no way to reassign finals.
    return new ConcurrentHashMap(this);
  }

  // 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 ConcurrentHashMap.this.size();
    }
    public boolean contains(Object o) {
      return ConcurrentHashMap.this.containsKey(o);
    }
    public boolean remove(Object o) {
      return ConcurrentHashMap.this.remove(o) != null;
    }
    public void clear() {
      ConcurrentHashMap.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 ConcurrentHashMap.this.size();
    }
    public boolean contains(Object o) {
      return ConcurrentHashMap.this.containsValue(o);
    }
    public void clear() {
      ConcurrentHashMap.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 = ConcurrentHashMap.this.get(entry.getKey());
      return v != null && v.equals(entry.getValue());
    }
    public boolean remove(Object o) {
      if (!(o instanceof Map.Entry))
        return false;
      Map.Entry e = (Map.Entry)o;
      return ConcurrentHashMap.this.remove(e.getKey(), e.getValue()) != null;
    }
    public int size() {
      return ConcurrentHashMap.this.size();
    }
    public void clear() {
      ConcurrentHashMap.this.clear();
    }
  }

  /**
   * 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();
  }

  /**
   * ConcurrentHashMap 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 Object key;
    protected volatile Object value;
    protected final int hash;
    protected final Entry next;

    Entry(int hash, Object key, Object value, Entry next) {
      this.value = value;
      this.hash = hash;
      this.key = key;
      this.next = next;
    }

    // Map.Entry Ops 

    public Object getKey() {
      return key;
    }

    /**
     * Get the value.  Note: In an entrySet or entrySet.iterator,
     * unless you can 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 you can 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() {
      // force all segments to synch
      synchronized(segments[0]) { tab = table; }
      for (int i = 1; i < segments.length; ++i) segments[i].synch();
      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();
      ConcurrentHashMap.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>ConcurrentHashMap</tt> 
   * instance to a stream (i.e.,
   * serialize it).
   *
   * @serialData  
   * An estimate of the table size, followed by
   * the key (Object) and value (Object)
   * for each key-value mapping, followed by a null pair.
   * The key-value mappings are emitted in no particular order.
   */

  private void writeObject(java.io.ObjectOutputStream s)
    throws IOException  {
    // Write out the loadfactor, and any hidden stuff
    s.defaultWriteObject();

    // Write out capacity estimate. It is OK if this
    // changes during the write, since it is only used by
    // readObject to set initial capacity, to avoid needless resizings.

    int cap;
    synchronized(segments[0]) { cap = table.length; }
    s.writeInt(cap);

    // Write out keys and values (alternating)
    for (int k = 0; k < segments.length; ++k) {
      Segment seg = segments[k];
      Entry[] tab;
      synchronized(seg) { tab = table; }
      for (int i = k; i < tab.length; i+= segments.length) {
        for (Entry e = tab[i]; e != null; e = e.next) {
          s.writeObject(e.key);
          s.writeObject(e.value);
        }
      }
    }

    s.writeObject(null);
    s.writeObject(null);
  }

  /**
   * Reconstitute the <tt>ConcurrentHashMap</tt> 
   * instance from a stream (i.e.,
   * deserialize it).
   */
  private void readObject(java.io.ObjectInputStream s)
    throws IOException, ClassNotFoundException  {
    // Read in the threshold, loadfactor, and any hidden stuff
    s.defaultReadObject();

    int cap = s.readInt();
    table = newTable(cap);
    for (int i = 0; i < segments.length; ++i) 
      segments[i] = new Segment();


    // Read the keys and values, and put the mappings in the table
    for (;;) {
      Object key = s.readObject();
      Object value = s.readObject();
      if (key == null)
        break;
      put(key, value);
    }
  }
}