com.goldencode.cache

Class LFUAgingCache<K,V>

java.lang.Object

com.goldencode.cache.ExpiryCache<K,V>

com.goldencode.cache.LFUAgingCache<K,V>

All Implemented Interfaces:

Cache<K,V>

public class LFUAgingCache<K,V>
extends ExpiryCache<K,V>

An implementation of a least-frequently-used (LFU) cache which additionally adjusts the importance of individual elements, based on the age of their last access. This will result in entries which may have been used frequently earlier in the history of the cache, followed by periods of inactivity, eventually being aged out of the cache.

Registered listeners are notified of each expiry event.

This implementation is not synchronized. Any access to the methods of this class which modify the internal state of the cache must be synchronized externally.

Note: this implementation is rather heavyweight, in that it does some expensive work on calls to ExpiryCache.get(Object) and when determining which elements to expire. It should only be chosen if the specific expiration policy is important to the logic of client code. Otherwise, LRUCache may be a better choice in terms of efficiency.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
private static class	LFUAgingCache.LFUEntry<K,V> A sortable entry containing the hashable key and value of a cache entry.

Nested classes/interfaces inherited from interface com.goldencode.cache.Cache

Cache.Entry<K,V>

Field Summary

Fields

Modifier and Type	Field and Description
private static double	CLEAN_RATIO Portion of cache limit to be expired when the cache is full and capacity is needed
private java.util.TreeSet<Cache.Entry<K,V>>	sorted Sorted set of key-value entries

Fields inherited from class com.goldencode.cache.ExpiryCache

cache, limit, log, name

Constructor Summary

Constructors

Constructor and Description
LFUAgingCache(int limit) Constructor.
LFUAgingCache(java.lang.String name, int limit) Constructor.

Method Summary

Modifier and Type	Method and Description
private void	ageEntries() Recompute the relevance of entries with older access ages.
protected Cache.Entry<K,V>	createEntry(K key, V value) Create an entry of the appropriate type for the given key and value.
protected void	ensureCapacity() Ensure there is sufficient capacity to add a new record to the cache, by expiring the least desirable element(s), according to the policy of the cache.
protected void	entryAccessed(Cache.Entry<K,V> entry) An entry in the cache was accessed by a call to ExpiryCache.get(Object).
protected void	entryAdded(Cache.Entry<K,V> entry) An entry in the cache was added by a call to ExpiryCache.put(Object, Object).
protected void	entryRemoved(Cache.Entry<K,V> entry) An entry in the cache was removed by a call to ExpiryCache.remove(Object), replaced by a call to ExpiryCache.put(Object, Object), or was removed due to its expiration.
protected int	getCleanLimit() Get the number of elements which will be expired from the cache each time it becomes full, and capacity is required for a new element.
java.util.Map<K,V>	getMFUEntries(int maxEntries) Retrieve the Most Frequently Used items out of cache.
protected Cache.Entry<K,V>	nextExpiredEntry() Get the next expired entry to be reaped.

Methods inherited from class com.goldencode.cache.ExpiryCache

addCacheExpiryListener, containsKey, entries, get, keys, put, putIfAbsent, remove, removeCacheExpiryListener, size, values

Methods inherited from class java.lang.Object

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

Field Detail

CLEAN_RATIO

private static final double CLEAN_RATIO

Portion of cache limit to be expired when the cache is full and capacity is needed

See Also:

Constant Field Values

sorted

private final java.util.TreeSet<Cache.Entry<K,V>> sorted

Sorted set of key-value entries

Constructor Detail

LFUAgingCache

public LFUAgingCache(int limit)

Constructor.

Parameters:

limit - Maximum number of elements allowed in the cache.

Throws:

java.lang.IllegalArgumentException - if the specified limit is less than one.

LFUAgingCache

public LFUAgingCache(java.lang.String name,
                     int limit)

Constructor.

Parameters:

name - Cache name, for debug and logging purposes.

limit - Maximum number of elements allowed in the cache.

Throws:

java.lang.IllegalArgumentException - if the specified limit is less than one.

Method Detail

getMFUEntries

public java.util.Map<K,V> getMFUEntries(int maxEntries)

Retrieve the Most Frequently Used items out of cache. Order of result is unimportant.

Parameters:

maxEntries - - maximum number of entries to return

Returns:

Most Frequently Used items out of cache

getCleanLimit

protected int getCleanLimit()

Get the number of elements which will be expired from the cache each time it becomes full, and capacity is required for a new element.

Specified by:

getCleanLimit in class ExpiryCache<K,V>

Returns:

Number of elements to expire on each clearing pass, in this case 1/8 of the cache's maximum capacity.

createEntry

protected Cache.Entry<K,V> createEntry(K key,
                                       V value)

Create an entry of the appropriate type for the given key and value.

Specified by:

createEntry in class ExpiryCache<K,V>

Parameters:

key - Hashable key.

value - Cached value.

Returns:

A sortable entry to store in the cache.

nextExpiredEntry

protected Cache.Entry<K,V> nextExpiredEntry()

Get the next expired entry to be reaped. The expiration test (if any) will be applied upon this entry.

Specified by:

nextExpiredEntry in class ExpiryCache<K,V>

Returns:

Entry which will expire next (pending a successful expiration test).

entryAdded

protected void entryAdded(Cache.Entry<K,V> entry)

An entry in the cache was added by a call to ExpiryCache.put(Object, Object). Add the entry to the sorted set.

Specified by:

entryAdded in class ExpiryCache<K,V>

Parameters:

entry - Entry which was added.

entryAccessed

protected void entryAccessed(Cache.Entry<K,V> entry)

An entry in the cache was accessed by a call to ExpiryCache.get(Object). Re-order the entry within the sorted set.

Specified by:

entryAccessed in class ExpiryCache<K,V>

Parameters:

entry - Entry which was accessed.

entryRemoved

protected void entryRemoved(Cache.Entry<K,V> entry)

An entry in the cache was removed by a call to ExpiryCache.remove(Object), replaced by a call to ExpiryCache.put(Object, Object), or was removed due to its expiration. Remove the entry from the sorted set.

Specified by:

entryRemoved in class ExpiryCache<K,V>

Parameters:

entry - Entry which was removed.

ensureCapacity

protected void ensureCapacity()

Ensure there is sufficient capacity to add a new record to the cache, by expiring the least desirable element(s), according to the policy of the cache. This cache's policy retains entries which have been most frequently used, however, the relevance of an entry which has been accessed previously degrades over time.

When elements are expired from the cache, a cache expiry event is sent to all registered listeners.

Overrides:

ensureCapacity in class ExpiryCache<K,V>

ageEntries

private void ageEntries()

Recompute the relevance of entries with older access ages. This may result in older entries having their hit counts reduced, to compensate for lack of recent activity.