concurrentreaderhashmap.java

webwork source

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