com.bigdata.cache
Class ConcurrentWeakValueCache<K,V>

java.lang.Object
  com.bigdata.cache.ConcurrentWeakValueCache<K,V>

Type Parameters:

K - The generic type of the keys.

V - The generic type of the values.

All Implemented Interfaces:

IConcurrentWeakValueCache<K,V>

Direct Known Subclasses:

ConcurrentWeakValueCacheWithTimeout

public class ConcurrentWeakValueCache<K,V>
extends Object
implements IConcurrentWeakValueCache<K,V>

A low-contention/high concurrency weak value cache. This class can offer substantially less lock contention and hence greater performance than the WeakValueCache.

The role of the HardReferenceQueue is to place a minimum upper bound on the #of objects in the cache. If the application holds hard references to more than this many objects, e.g., in various threads, collections, etc., then the cache size can be larger than the queue capacity. Likewise, if the JVM takes too long to finalize weakly reachable references, then the cache size can exceed this limit even if the application does not hold ANY hard references to the objects in the cache. For these reasons, this class uses an initialCapacity for the inner ConcurrentHashMap that is larger than the queueCapacity. This helps to prevent resizing the ConcurrentHashMap which is a relatively expensive operation.

Version:

$Id: ConcurrentWeakValueCache.java 2265 2009-10-26 12:51:06Z thompsonbry $

Author:

Bryan Thompson

Nested Class Summary

static class

ConcurrentWeakValueCache.WeakRef<K,V> Adds the key to the weak reference.

Field Summary

protected static boolean	DEBUG
protected static boolean	INFO
protected static org.apache.log4j.Logger	log

Constructor Summary

ConcurrentWeakValueCache()
Uses the default queue capacity (16), load factor (0.75) and concurrency level (16).

ConcurrentWeakValueCache(IHardReferenceQueue<V> queue, float loadFactor, int concurrencyLevel, boolean removeClearedReferences)
Defaults the initial capacity of the map based on the capacity of the optional IHardReferenceQueue and uses the Java default of 16 if there is no queue.

ConcurrentWeakValueCache(IHardReferenceQueue<V> queue, int initialCapacity, float loadFactor, int concurrencyLevel, boolean removeClearedReferences)
Uses the specified values.

ConcurrentWeakValueCache(int queueCapacity)
Uses the default load factor (0.75) and concurrency level (16).

ConcurrentWeakValueCache(int queueCapacity, float loadFactor, int concurrencyLevel)
Uses the specified values.

ConcurrentWeakValueCache(int queueCapacity, float loadFactor, int concurrencyLevel, boolean removeClearedReferences)
Uses the specified values and creates a HardReferenceQueue without a timeout.

Method Summary

int	capacity() The capacity of the backing hard reference queue.
void	clear() Clear all entries in the map.
boolean	containsKey(K k) Return true iff the map contains an entry for the key whose weak reference has not been cleared.
protected void	didUpdate(K k, WeakReference<V> newRef, WeakReference<V> oldRef) Notification method is invoked if a map entry is inserted or updated by put(Object, Object) or putIfAbsent(Object, Object).
Iterator<Map.Entry<K,WeakReference<V>>>	entryIterator() An iterator that visits the entries in the map.
V	get(K k) Returns the value for the key.
boolean	isRemoveClearedReferences() Return true iff a ReferenceQueue is being maintained and entries will be removed from the map once the corresponding WeakReference has been cleared.
Iterator<WeakReference<V>>	iterator() An iterator that visits the weak reference values in the map.
protected WeakReference<V>	newWeakRef(K k, V v, ReferenceQueue<V> referenceQueue) Factory for new weak references.
V	put(K k, V v) Adds the key-value mapping to the cache.
V	putIfAbsent(K k, V v) Adds the key-value mapping to the cache iff there is no entry for that key.
V	remove(K k) Remove the entry for the key.
protected void	removeClearedEntries() Remove any entries whose weak reference has been cleared from the map.
protected WeakReference<V>	removeMapEntry(K k) Invoked when a reference needs to be removed from the map.
int	size() Returns the approximate number of keys in the map.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

log

protected static final transient org.apache.log4j.Logger log

INFO

protected static final transient boolean INFO

DEBUG

protected static final transient boolean DEBUG

Constructor Detail

ConcurrentWeakValueCache

public ConcurrentWeakValueCache()

Uses the default queue capacity (16), load factor (0.75) and concurrency level (16).

ConcurrentWeakValueCache

public ConcurrentWeakValueCache(int queueCapacity)

Uses the default load factor (0.75) and concurrency level (16).

Parameters:

queueCapacity - The IHardReferenceQueue capacity. When ZERO (0), there will not be a backing hard reference queue.

ConcurrentWeakValueCache

public ConcurrentWeakValueCache(int queueCapacity,
                                float loadFactor,
                                int concurrencyLevel)

Uses the specified values.

Parameters:

queueCapacity - The IHardReferenceQueue capacity. When ZERO (0), there will not be a backing hard reference queue.

loadFactor - The load factor.

concurrencyLevel - The concurrency level.

ConcurrentWeakValueCache

public ConcurrentWeakValueCache(int queueCapacity,
                                float loadFactor,
                                int concurrencyLevel,
                                boolean removeClearedReferences)

Uses the specified values and creates a HardReferenceQueue without a timeout.

Parameters:

queueCapacity - The HardReferenceQueue capacity. When ZERO (0), there will not be a backing hard reference queue.

loadFactor - The load factor.

concurrencyLevel - The concurrency level.

removeClearedReferences - When true the cache will remove entries for cleared references. When false those entries will remain in the cache.

ConcurrentWeakValueCache

public ConcurrentWeakValueCache(IHardReferenceQueue<V> queue,
                                float loadFactor,
                                int concurrencyLevel,
                                boolean removeClearedReferences)

Defaults the initial capacity of the map based on the capacity of the optional IHardReferenceQueue and uses the Java default of 16 if there is no queue.

Parameters:

queue - The IHardReferenceQueue (optional).

loadFactor - The load factor.

concurrencyLevel - The concurrency level.

removeClearedReferences - When true the cache will remove entries for cleared references. When false those entries will remain in the cache.

ConcurrentWeakValueCache

public ConcurrentWeakValueCache(IHardReferenceQueue<V> queue,
                                int initialCapacity,
                                float loadFactor,
                                int concurrencyLevel,
                                boolean removeClearedReferences)

Uses the specified values.

Parameters:

queue - The IHardReferenceQueue (optional).

initialCapacity - The initial capacity of the backing hash map.

loadFactor - The load factor.

concurrencyLevel - The concurrency level.

removeClearedReferences - When true the cache will remove entries for cleared references. When false those entries will remain in the cache.

Method Detail

isRemoveClearedReferences

public boolean isRemoveClearedReferences()

Return true iff a ReferenceQueue is being maintained and entries will be removed from the map once the corresponding WeakReference has been cleared. This behavior is controlled by a constructor option.

size

public int size()

Returns the approximate number of keys in the map. Cleared references are removed before reporting the size of the map, but the return value is still approximate as garbage collection by the JVM can cause references to be cleared at any time.

Specified by:

size in interface IConcurrentWeakValueCache<K,V>

capacity

public int capacity()

The capacity of the backing hard reference queue.

Specified by:

capacity in interface IConcurrentWeakValueCache<K,V>

clear

public void clear()

Description copied from interface: IConcurrentWeakValueCache

Clear all entries in the map.

Specified by:

clear in interface IConcurrentWeakValueCache<K,V>

get

public V get(K k)

Returns the value for the key.

Specified by:

get in interface IConcurrentWeakValueCache<K,V>

Parameters:

k - The key.

Returns:

The value.

See Also:

http://en.wikipedia.org/wiki/Lock-free_and_wait-free_algorithms, http://www.audiomulch.com/~rossb/code/lockfree/

TODO:

If we can locate a ConcurrentRingBuffer then we could further improve performance by removing synchronization on the hard reference queue in this method.

containsKey

public boolean containsKey(K k)

Return true iff the map contains an entry for the key whose weak reference has not been cleared.

Specified by:

containsKey in interface IConcurrentWeakValueCache<K,V>

Parameters:

k - The key.

Returns:

true iff the map contains an entry for that key whose weak reference has not been cleared.

put

public V put(K k,
             V v)

Adds the key-value mapping to the cache.

Specified by:

put in interface IConcurrentWeakValueCache<K,V>

Parameters:

k - The key.

v - The value.

Returns:

The old value under the key -or- null if there is no entry under the key or if the entry under the key has has its reference cleared.

putIfAbsent

public V putIfAbsent(K k,
                     V v)

Adds the key-value mapping to the cache iff there is no entry for that key. Note that a cleared reference under a key is treated in exactly the same manner as if there were no entry under the key (the entry under the key is replaced atomically).

Specified by:

putIfAbsent in interface IConcurrentWeakValueCache<K,V>

Parameters:

k - The key.

v - The value.

Returns:

the previous value associated with the specified key, or null if there was no mapping for the key or if the entry under the key has has its reference cleared.

didUpdate

protected void didUpdate(K k,
                         WeakReference<V> newRef,
                         WeakReference<V> oldRef)

Notification method is invoked if a map entry is inserted or updated by put(Object, Object) or putIfAbsent(Object, Object). This method IS NOT invoked if putIfAbsent(Object, Object) did not update the map.

Parameters:

k - The key.

newRef - The WeakReference for the new value. This was generated using newWeakRef(Object, Object, ReferenceQueue). Reference.get() will always return the value inserted into the map since it is on the stack and hence can not have been cleared during this callback.

oldRef - The WeakReference for the old value. This will be null if there was no entry under the key for the map. If the entry for a cleared reference is updated then Reference.get() will return null for the oldRef.

remove

public V remove(K k)

Description copied from interface: IConcurrentWeakValueCache

Remove the entry for the key.

Specified by:

remove in interface IConcurrentWeakValueCache<K,V>

Parameters:

k - The key.

Returns:

The previous value associated with the key, or null if there was no mapping for the key or if the entry under the key has has its reference cleared.

removeClearedEntries

protected void removeClearedEntries()

Remove any entries whose weak reference has been cleared from the map. This method does not block and only polls the ReferenceQueue.

Note: This method does not clear entries from the hard reference queue because it is not possible to have a weak or soft reference cleared by the JVM while a hard reference exists, so it is not possible to have an entry in the hard reference queue for a reference that is being cleared here.

removeMapEntry

protected WeakReference<V> removeMapEntry(K k)

Invoked when a reference needs to be removed from the map.

Parameters:

k - The key.

iterator

public Iterator<WeakReference<V>> iterator()

An iterator that visits the weak reference values in the map. You must test each weak reference in order to determine whether its value has been cleared as of the moment that you request that value. The entries visited by the iterator are not "touched" so the use of the iterator will not cause them to be retained any longer than they otherwise would have been retained.

Specified by:

iterator in interface IConcurrentWeakValueCache<K,V>

entryIterator

public Iterator<Map.Entry<K,WeakReference<V>>> entryIterator()

An iterator that visits the entries in the map. You must test the weak reference for each entry in order to determine whether its value has been cleared as of the moment that you request that value. The entries visited by the iterator are not "touched" so the use of the iterator will not cause them to be retained any longer than they otherwise would have been retained.

Specified by:

entryIterator in interface IConcurrentWeakValueCache<K,V>

newWeakRef

protected WeakReference<V> newWeakRef(K k,
                                      V v,
                                      ReferenceQueue<V> referenceQueue)

Factory for new weak references. The default implementation uses a WeakReference unless referenceQueue!=null, in which case it uses ConcurrentWeakValueCache.WeakRef to pair the key with the WeakReference. This may be extended if you need to track additional information in the map entries.

Parameters:

k - The key.

v - The value.

referenceQueue - The ReferenceQueue used to remove map entries whose WeakReferences have been cleared (optional).

Returns:

An instance of a class extending WeakReference -or- an instance of a class extending ConcurrentWeakValueCache.WeakRef if referenceQueue!=null.