net.sf.saxon.expr.sort

Class LFUCache<K,V>

java.lang.Object

net.sf.saxon.expr.sort.LFUCache<K,V>

public class LFUCache<K,V>
extends java.lang.Object

A "Least Frequently Used" cache. When the cache grows too large, we discard entries whose reference counters are below some threshold. This is cheaper than an LRU (least recently used) algorithm, because access to the map doesn't require any locking against concurrent activity. Unlike classic LFU algorithms where the cache size has a fixed upper bound, we allow it to grow beyond the target size and then do a bulk deletion of infrequently used entries. We delete all entries whose usage counter is below some threshold, learning the best threshold to apply from experience of previous reorganisations. There is no synchronization. The underlying map itself is thread-safe, but we make no attempt to prevent two concurrent threads garbage collecting at the same time: if this happens, no harm is caused, because it's only a cache and lost entries will simply be recomputed. Equally, the incrementing of counters isn't synchronized because they don't need to be exact.

Constructor Summary

Constructors

Constructor and Description
LFUCache(int cacheSize) Creates a new LCU cache, suitable for use only within a single thread.
LFUCache(int cacheSize, boolean concurrent) Creates a new LCU cache, with the option of making it thread-safe

Method Summary

Modifier and Type	Method and Description
void	clear() Clear the cache
boolean	containsKey(K key) Ask whether a given key is present in the cache. The usage count of the entry is incremented if the entry exists.
V	get(K key) Retrieves an entry from the cache. The usage count of the entry is incremented.
void	put(K key, V value) Adds an entry to this cache.
int	size() Get the number of entries in the cache

Methods inherited from class java.lang.Object

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

Constructor Detail

LFUCache

public LFUCache(int cacheSize)

Creates a new LCU cache, suitable for use only within a single thread.

Parameters:

cacheSize - the target number of entries to be kept in this cache.

LFUCache

public LFUCache(int cacheSize,
                boolean concurrent)

Creates a new LCU cache, with the option of making it thread-safe

Parameters:

cacheSize - the maximum number of entries that will be kept in this cache.

concurrent - set to true if concurrent access is required, so that the underlying map will be thread-safe

Method Detail

get

public V get(K key)

Retrieves an entry from the cache.
The usage count of the entry is incremented.

Parameters:

key - the key whose associated value is to be returned.

Returns:

the value associated to this key, or null if no value with this key exists in the cache.

containsKey

public boolean containsKey(K key)

Ask whether a given key is present in the cache.
The usage count of the entry is incremented if the entry exists.

Parameters:

key - the key to be tested

Returns:

true if the key is present

put

public void put(K key,
                V value)

Adds an entry to this cache. It is assumed that the caller has already checked that the cache doesn't already contain a suitable entry, so we treat each entry as a new one. If the cache is exceeds a threshold size of three times the target size, it is rebuilt with infrequently used entries purged.

Parameters:

key - the key with which the specified value is to be associated.

value - a value to be associated with the specified key.

clear

public void clear()

Clear the cache

size

public int size()

Get the number of entries in the cache

Returns:

the number of entries