Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /*
    File: ConcurrentReaderHashMap
  
    Written by Doug Lea. Adapted and released, under explicit
    permission, 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.
   23jun2004  dl               Avoid bad array sizings in view toArray methods
   02jul2007  blackdrag        adaption of package name to Groovy project
  */
 
 package org.codehaus.groovy.runtime.metaclass;
 
 
This Map is a stripped down version of ConcurrentReaderHashMap with small modifications here and there. It is no full Map, it does have put/get/remove, but no iterators. This map is intended to hold values and keys as SoftReference. If one of value or key are removed, so will be complete entry. This map will not use the equals method to compare keys, think of it as a IdentityHashMap with features of concurrency and memory aware caching. As ConcurrentReaderHashMap also does this implementation prefere read operations and tries not to lock if possible. SoftReferenced values are only removed from the map if the map goes into a synchronization block on this. This may affect reads, but only in rare cases.
 
 public class MemoryAwareConcurrentReadMap {
 
 
     /*
     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() {
              = 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() {
            return 
        }
    }


    
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;
    
    private ReferenceQueue queue;
    
    
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 >  || cap < 0) {
            result = ;
        } else {
            result = ;
            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 referential equality, null allowed
    protected boolean eq(Object xObject y) {
        return x == y;
    }

    
Constructs a new, empty map with the specified initial capacity and the specified load factor.

Parameters:
initialCapacity the initial capacity The actual initial capacity is rounded to the nearest power of two.
loadFactor the load factor of the ConcurrentReaderHashMap
Throws:
java.lang.IllegalArgumentException if the initial maximum number of elements is less than zero, or if the load factor is nonpositive.
    public MemoryAwareConcurrentReadMap(int initialCapacityfloat loadFactor) {
        if (loadFactor <= 0)
            throw new IllegalArgumentException("Illegal Load factor: "+
                    loadFactor);
        this. = loadFactor;
        int cap = p2capacity(initialCapacity);
         = new Entry[cap];
         = (int)(cap * loadFactor);
        
         = new ReferenceQueue();
    }

    
Constructs a new, empty map with the specified initial capacity and default load factor.

Parameters:
initialCapacity the initial capacity of the ConcurrentReaderHashMap.
Throws:
java.lang.IllegalArgumentException if the initial maximum number of elements is less than zero.
    public MemoryAwareConcurrentReadMap(int initialCapacity) {
        this(initialCapacity);
    }

    
Constructs a new, empty map with a default initial capacity and load factor.
    public MemoryAwareConcurrentReadMap() {
    }

    
Returns the number of key-value mappings in this map.

Returns:
the number of key-value mappings in this map.
    public synchronized int size() {
        return ;
    }

    
Returns true if this map contains no key-value mappings.

Returns:
true if this map contains no key-value mappings.
    public synchronized boolean isEmpty() {
        return  == 0;
    }

    
Returns the value to which the specified key is mapped in this table.

Parameters:
key a key in the table.
Returns:
the value to which the key is mapped in this table; null if the key is not mapped to any value in this table.
Throws:
java.lang.NullPointerException if the key is null.
See also:
put(java.lang.Object,java.lang.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 = ;
        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)];
                }
                continue;
            }
            
            Object eKey = e.getKey();
            Object eValue = e.getValue();
            if (e.hash == hash && eq(keyeKey)) {
                if (e.value != return eValue;
                // 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) {
                    if (eKey==null && eValue==nullexpungeStaleEntries();
                    tab = ;
                }
                e = first = tab[index = hash & (tab.length-1)];
            } 
            else 
                e = e.next;
        }
    }
    
    
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.

Parameters:
key the table key.
value the value.
Returns:
the previous value of the specified key in this table, or null if it did not have one.
Throws:
java.lang.NullPointerException if the key or value is null.
See also:
get(java.lang.Object)
    public Object put(Object keyObject value) {
        if (value == null
            throw new NullPointerException();
        int hash = hash(key);
        Entry[] tab = ;
        int index = hash & (tab.length-1);
        Entry first = tab[index];
        Entry e;
        for (e = firste != nulle = e.next)
            if (e.hash == hash && eq(keye.getKey()))
                break;
        synchronized(this) {
            if (tab == ) {
                if (e == null) {
                    //  make sure we are adding to correct list
                    if (first == tab[index]) {
                        //  Add to front of list
                        Entry newEntry = new Entry(hashkeyvaluefirst);
                        tab[index] = newEntry;
                        if (++ >= rehash();
                        else recordModification(newEntry);
                        return null;
                    }
                }
                else {
                    Object oldValue = e.getValue();
                    if (first == tab[index] && oldValue != null) {
                        e.setValue(e.value);
                        return oldValue;
                    }
                }
            }
            // retry if wrong list or lost race against concurrent remove
            return sput(keyvaluehash);
        }
    }


    
Continuation of put(), called only when synch lock is held and interference has been detected.
    protected Object sput(Object keyObject valueint hash) { 
        expungeStaleEntries();
        Entry[] tab = ;
        int index = hash & (tab.length-1);
        Entry first = tab[index];
        Entry e = first;
        for (;;) {
            if (e == null) {
                Entry newEntry = new Entry(hashkeyvaluefirst);
                tab[index] = newEntry;
                if (++ >= rehash();
                else recordModification(newEntry);
                return null;
            }
            else if (e.hash == hash && eq(keye.getKey())) {
                Object oldValue = e.getValue(); 
                e.setValue(e.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 = ;
        int oldCapacity = oldTable.length;
        if (oldCapacity >= ) {
             = .// avoid retriggering
            return;
        }
        int newCapacity = oldCapacity << 1;
        int mask = newCapacity - 1;
         = (int)(newCapacity * );
        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 = nextlast != nulllast = last.next) {
                        int k = last.hash & mask;
                        if (k != lastIdx) {
                            lastIdx = k;
                            lastRun = last;
                        }
                    }
                    newTable[lastIdx] = lastRun;
                    // Clone all remaining nodes
                    for (Entry p = ep != lastRunp = p.next) {
                        int k = p.hash & mask;
                        newTable[k] = new Entry(p.hashp.getKey(), 
                                p.getValue(), newTable[k], );
                    }
                }
            }
        }
         = 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.

Parameters:
key the key that needs to be removed.
Returns:
the value to which the key had been mapped in this table, or null if the key did not have a mapping.
Throws:
java.lang.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 = ;
        int index = hash & (tab.length-1);
        Entry first = tab[index];
        Entry e = first;
        for (e = firste != nulle = e.next
            if (e.hash == hash && eq(keye.getKey())) 
                break;
        synchronized(this) {
            if (tab == ) {
                if (e == null) {
                    if (first == tab[index])
                        return null;
                }
                else {
                    Object oldValue = e.getValue();
                    if (first == tab[index] && oldValue != null) {
                        e.setValue(null);
                        --;
                        Entry head = e.next;
                        for (Entry p = firstp != ep = p.next
                            head = new Entry(p.hashp.keyp.valuehead);
                        tab[index] = head;
                        recordModification(head);
                        return oldValue;
                    }
                }
            }
            // Wrong list or interference
            return sremove(keyhash);
        }
    }

    
Continuation of remove(), called only when synch lock is held and interference has been detected.
    protected Object sremove(Object keyint hash) {
        expungeStaleEntries();
        
        Entry[] tab = ;
        int index = hash & (tab.length-1);
        Entry first = tab[index];
        for (Entry e = firste != nulle = e.next) {
            if (e.hash == hash && eq(keye.getKey())) {
                Object oldValue = e.getValue();
                e.setValue(null);
                --;
                Entry head = e.next;
                for (Entry p = firstp != ep = p.next
                    head = new Entry(p.hashp.getKey(), p.getValue(), head);
                tab[index] = head;
                recordModification(head);
                return oldValue;
            }
        }
        return null;
    }

    
Removes all mappings from this map.
    public synchronized void clear() {
        Entry tab[] = ;
        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 != nulle = e.next
                e.setValue(null); 
            tab[i] = null;
        }
         = 0;
        recordModification(tab);
    }

    
Removes entries from the ReferenceQueue for keys and values of this map. This method is thought to be called only with an already existing lock on "this". The method expects SoftRef instances in the queue. It uses the entry field to control if the Entry is already removed map. If the entry is null the removal is skipped.
    private void expungeStaleEntries() {
        SoftRef ref;
        Entry[] tab = ;
        
        while ((ref=(SoftRef).poll())!=null) {
            Entry entry = ref.entry;
            // if entry== null, then it is already deleted
            // form the map
            if (entry == nullcontinue;
            ref.entry = null;
            // if neither entry.key nor entry.value == ref then
            // the entry was reused, but the value has become invalid
            if (entry.key!=ref && entry.value!=refcontinue;
            int hash = entry.hash;
            int index = hash & (tab.length-1);
            Entry first = tab[index];
            for (Entry e = firste != nulle = e.next) {
                if (e==entry) {
                    entry.key.clear();
                    entry.setValue(null);
                    
                    --;
                    
                    Entry head = e.next;
                    for (Entry p = firstp != ep = p.next
                        head = new Entry(p.hashp.keyp.valuehead);
                    
                    tab[index] = head;
                    recordModification(head);
                    break;
                }
            } 
        }
    }
    
    
Reference class used to support get()
    private static interface Reference {
        Object get();
    }
    
    
A dummy to replace the SoftReference if needed
    private static class DummyRef implements Reference {
        public Object get() {
            return null;
        }
    }    
    
    // constant for DummyRef, no need to keep more than one
    // it is not critical if more than one is created here
    private static final Reference DUMMY_REF = new DummyRef();
    
    
A SoftReference representing a key or value of the map. The instance keeps a pointer to the entry it is sotring a key or value for. This is used to identify the entry we need to remove

See also:
CopyOfMemoryAwareConcurrentReadMap#expungeStaleEntries()
    private static class SoftRef extends SoftReference implements Reference {
        private volatile Entry entry;
        public SoftRef(Entry eObject vReferenceQueue q) {
            super(v,q);
             = e;
        }
        public void clear() {
            super.clear();
            =null;
        }
    }

    
ConcurrentReaderHashMap collision list entry.
    private static class 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. 
         */
        private final int hash;
        private final SoftRef key;
        private final Entry next;
        private volatile Reference value;
        Entry(int hashObject keyObject valueEntry nextReferenceQueue queue) {
            this. = hash;
            this. = new SoftRef(this,key,queue);
            this. = next;
            this. = new SoftRef(this,value,queue);
        }
        Entry(int hashSoftRef keyReference valueEntry next) {
            this. = hash;
            this. = key;
            key.entry = this;
            this. = next;
            this. = ;
            this.setValue(value);
        }
        
        // Map.Entry Ops 
        public Object getKey() {
            return .get();
        }
        public Object getValue() {
            return .get(); 
        }
        public Object setValue(Reference value) {
            Object oldValue = this..get();
            if (value == null || value == ) {
                this. = ;
            } else {
                SoftRef ref = (SoftRefvalue;
                ref.entry = this;
                this. = value;
            }
            return oldValue;
        }
    }
       
New to GrepCode? Check out our FAQ X