com.bigdata.cache
Class LRUCache<K,T>

java.lang.Object
  com.bigdata.cache.LRUCache<K,T>

All Implemented Interfaces:

ICachePolicy<K,T>

public class LRUCache<K,T>
extends Object
implements ICachePolicy<K,T>

Hard reference hash map with Least Recently Used ordering over entries. The keys are object identifiers. The values are cache entries wrapping the identified objects.

Version:

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

Author:

Bryan Thompson

TODO:

Consider removing synchronization for use in a single threaded context., This can be replaced by a hard reference ring buffer that scans the last N entries to minimize churn. See HardReferenceQueue. This will change the delegation interfaces since the ring buffer does NOT support random access by the identifier.

Nested Class Summary

protected static interface

LRUCache.ICacheOrderChangeListener<K,T>

Field Summary

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

Constructor Summary

LRUCache(int capacity)
Create an LRU cache with a default load factor of 0.75.

LRUCache(int capacity, float loadFactor)
Create an LRU cache with the specific capacity and load factor.

Method Summary

protected void	addCacheOrderChangeListener(LRUCache.ICacheOrderChangeListener<K,T> l) Registers a listener for removeEntry events.
int	capacity() The capacity of the cache.
void	clear() Clear all objects from the cache.
Iterator<ICacheEntry<K,T>>	entryIterator() Visits entries in the cache in LRU ordering (the least recently used object is visited first).
protected void	finalize() Writes cache performance statistics.
T	get(K key) Return the indicated object from the cache or null if the object is not in cache.
ICacheListener<K,T>	getCacheListener() Return the cache eviction listener.
double	getHitRatio()
long	getInsertCount()
String	getStatistics()
long	getSuccessCount()
long	getTestCount()
Iterator<T>	iterator() Visits objects in the cache in LRU ordering (the least recently used object is visited first).
void	put(K key, T obj, boolean dirty) Add the object to the hash map under the key if it is not already there and update the entry ordering (this can be used to touch an entry).
T	remove(K key) Remove the indicated object from the cache.
protected void	removeCacheOrderChangeListener(LRUCache.ICacheOrderChangeListener<K,T> l) Unregister the listener.
void	resetStatistics()
void	setListener(ICacheListener<K,T> listener) Sets the cache eviction listener on the hard reference cache.
int	size() The #of entries in the cache.

Methods inherited from class java.lang.Object

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

Field Detail

log

protected static final org.apache.log4j.Logger log

INFO

protected static final boolean INFO

Constructor Detail

LRUCache

public LRUCache(int capacity)

Create an LRU cache with a default load factor of 0.75.

Parameters:

capacity - The capacity of the cache.

LRUCache

public LRUCache(int capacity,
                float loadFactor)

Create an LRU cache with the specific capacity and load factor.

Parameters:

capacity - The capacity of the cache (must be positive).

loadFactor - The load factor for the internal hash table.

Method Detail

getHitRatio

public double getHitRatio()

getInsertCount

public long getInsertCount()

getTestCount

public long getTestCount()

getSuccessCount

public long getSuccessCount()

setListener

public void setListener(ICacheListener<K,T> listener)

Description copied from interface: ICachePolicy

Sets the cache eviction listener on the hard reference cache. Eviction notices are fired when objects are evicted from the hard reference cache.

Specified by:

setListener in interface ICachePolicy<K,T>

Parameters:

listener - The listener or null to remove any listener.

getCacheListener

public ICacheListener<K,T> getCacheListener()

Description copied from interface: ICachePolicy

Return the cache eviction listener.

Specified by:

getCacheListener in interface ICachePolicy<K,T>

iterator

public Iterator<T> iterator()

Visits objects in the cache in LRU ordering (the least recently used object is visited first).

The returned iterator is NOT thread safe. It supports removal but does NOT support concurrent modification of the cache state. Normally the iterator is used during a commit and the framework guarantees that concurrent

Specified by:

iterator in interface ICachePolicy<K,T>

See Also:

ICachePolicy.entryIterator()

entryIterator

public Iterator<ICacheEntry<K,T>> entryIterator()

Visits entries in the cache in LRU ordering (the least recently used object is visited first).

The returned iterator is NOT thread safe. It supports removal but does NOT support concurrent modification of the cache state. Normally the iterator is used during a commit and the framework guarantees that concurrent

Specified by:

entryIterator in interface ICachePolicy<K,T>

Returns:

Iterator visiting ICacheEntry objects. If this is a weak reference cache, then the iterator visits the entries in the delegate hard reference cache.

See Also:

ICacheEntry, ICachePolicy.iterator()

clear

public void clear()

Description copied from interface: ICachePolicy

Clear all objects from the cache. This method may be used to reset the cache when a transaction is being rolled back. Cache eviction notices are NOT fired when this method is called.

Specified by:

clear in interface ICachePolicy<K,T>

resetStatistics

public void resetStatistics()

size

public int size()

The #of entries in the cache.

Specified by:

size in interface ICachePolicy<K,T>

Returns:

The #of entries in the hard reference cache.

capacity

public int capacity()

The capacity of the cache.

Specified by:

capacity in interface ICachePolicy<K,T>

Returns:

The capacity of the hard reference cache.

finalize

protected void finalize()
                 throws Throwable

Writes cache performance statistics.

Overrides:

finalize in class Object

Throws:

Throwable

getStatistics

public String getStatistics()

put

public void put(K key,
                T obj,
                boolean dirty)

Add the object to the hash map under the key if it is not already there and update the entry ordering (this can be used to touch an entry).

Cache evictions are only performed at or over capacity, but not for reentrant invocations. If a cache eviction causes a nested #put(long, Object, boolean) cache enters a temporary over capacity condition. The nested eviction is effectively deferred and a new cache entry is created for the incoming object rather than recycling the LRU cache entry. This temporary over capacity state exists until the primary eviction event has been handled, at which point entries are purged from the cache until it has one free entry. That free entry is then used to cache the incoming object which triggered the outer eviction event.

This is not the only coherent manner in which nested eviction events could be handled, but it is perhaps the simplest. This technique MUST NOT be used with an open array hash table since the temporary over capacity condition would not be supported.

Specified by:

put in interface ICachePolicy<K,T>

Parameters:

key - The object identifier.

obj - The object.

dirty - True iff the object is dirty.

get

public T get(K key)

Description copied from interface: ICachePolicy

Return the indicated object from the cache or null if the object is not in cache.

Specified by:

get in interface ICachePolicy<K,T>

Parameters:

key - The object identifier.

Returns:

The object or null iff it is not in cache.

remove

public T remove(K key)

Description copied from interface: ICachePolicy

Remove the indicated object from the cache.

Specified by:

remove in interface ICachePolicy<K,T>

Parameters:

key - The object identifier.

Returns:

The object in the cache for that object identifier or null if there was no object under that identifier.

addCacheOrderChangeListener

protected void addCacheOrderChangeListener(LRUCache.ICacheOrderChangeListener<K,T> l)

Registers a listener for removeEntry events. This is used by the LRUIterator to handle concurrent modifications of the cache ordering during traversal.

removeCacheOrderChangeListener

protected void removeCacheOrderChangeListener(LRUCache.ICacheOrderChangeListener<K,T> l)

Unregister the listener. This is safe to invoke when the listener is not registered.

Parameters:

l - The listener.