org.eclipse.californium.elements.util

Class LeastRecentlyUsedCache<K,V>

java.lang.Object

org.eclipse.californium.elements.util.LeastRecentlyUsedCache<K,V>

Type Parameters:

K - The type of the keys used in the cache.

V - The type of the values used in the cache.

public class LeastRecentlyUsedCache<K,V>
extends Object

An in-memory cache with a maximum capacity and support for evicting stale entries based on an LRU policy.

The cache keeps track of the values' last-access time automatically. Every time a value is read from or put to the store, the access-time is updated. This update may be suppressed for read access by updateOnReadAccess.

A value can be successfully added to the cache if any of the following conditions is met:

• The cache's remaining capacity is greater than zero.
• The cache contains at least one stale entry, i.e. an entry that has not been accessed for at least the cache's expiration threshold period. In such a case the least-recently accessed stale entry gets evicted from the cache to make place for the new value to be added.

Depending on evictOnReadAccess the read access may evict expired entries or returns them and updates the last-access time, if not suppressed by updateOnReadAccess.

This implementation uses a HashMap as its backing store. In addition to that the cache keeps a doubly-linked list of the entries in access-time order.

Access to the cache's entries (e.g. put, get, remove, find) is not thread safe. Clients should explicitly serialize access to the cache from multiple threads.

Insertion, lookup and removal of entries is done in O(log n).

Note: if the expiration threshold is 0, "stale" is not applied in get(Object) (otherwise that get would never return something).

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static interface	LeastRecentlyUsedCache.EvictionListener<V> A callback for getting notified about entries being evicted from the cache.
static interface	LeastRecentlyUsedCache.Predicate<V> A predicate to be applied to cache entries to determine the result set when searching for particular values.

Field Summary

Fields

Modifier and Type	Field and Description
static int	DEFAULT_CAPACITY The cache's default maximum capacity.
static int	DEFAULT_INITIAL_CAPACITY The cache's default initial capacity.
static long	DEFAULT_THRESHOLD_SECS The default number of seconds after which an entry is considered stale if it hasn't been accessed for that amount of time.

Constructor Summary

Constructors

Constructor and Description
LeastRecentlyUsedCache() Creates a cache with an initial capacity of DEFAULT_INITIAL_CAPACITY, a maximum capacity of DEFAULT_CAPACITY entries and an expiration threshold of DEFAULT_THRESHOLD_SECS seconds.
LeastRecentlyUsedCache(int initialCapacity, int maxCapacity, long threshold) Creates a cache based on given configuration parameters.
LeastRecentlyUsedCache(int capacity, long threshold) Creates a cache based on given configuration parameters.

Method Summary

Methods

Modifier and Type	Method and Description
void	addEvictionListener(LeastRecentlyUsedCache.EvictionListener<V> listener) Registers a listener to be notified about (stale) entries being evicted from the cache.
void	clear() Removes all entries from the cache.
V	find(LeastRecentlyUsedCache.Predicate<V> predicate) Finds a value based on a predicate.
V	find(LeastRecentlyUsedCache.Predicate<V> predicate, boolean unique) Finds a value based on a predicate.
V	get(K key) Gets a value from the cache.
int	getCapacity() Gets the maximum number of entries this cache can manage.
long	getExpirationThreshold() Gets the period of time after which an entry is considered stale if it hasn't be accessed.
boolean	isEvictingOnReadAccess() Get evict mode on read access.
boolean	isUpdatingOnReadAccess() Get update last-access time mode on read access.
boolean	put(K key, V value) Puts an entry to the cache.
int	remainingCapacity() Gets the number of entries that can be added to this cache without the need for removing stale entries.
V	remove(K key) Removes an entry from the cache.
V	remove(K key, V value) Removes provided entry from the cache.
void	setCapacity(int capacity) Sets the maximum number of entries this cache can manage.
void	setEvictingOnReadAccess(boolean evict) Set evict mode on read access.
void	setExpirationThreshold(long newThreshold) Sets the period of time after which an entry is to be considered stale if it hasn't be accessed.
void	setExpirationThreshold(long newThreshold, TimeUnit unit) Sets the period of time after which an entry is to be considered stale if it hasn't be accessed.
void	setUpdatingOnReadAccess(boolean update) Set update last-access time mode on read access.
int	size() Gets the cache's current number of entries.
boolean	update(K key) Update the last-access time.
Collection<V>	values() Gets all connections contained in this cache.
Iterator<V>	valuesIterator() Gets iterator over all connections contained in this cache.

Methods inherited from class java.lang.Object

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

Field Detail

DEFAULT_INITIAL_CAPACITY

public static final int DEFAULT_INITIAL_CAPACITY

The cache's default initial capacity.

See Also:

Constant Field Values

DEFAULT_THRESHOLD_SECS

public static final long DEFAULT_THRESHOLD_SECS

The default number of seconds after which an entry is considered stale if it hasn't been accessed for that amount of time.

See Also:

Constant Field Values

DEFAULT_CAPACITY

public static final int DEFAULT_CAPACITY

The cache's default maximum capacity.

See Also:

Constant Field Values

Constructor Detail

LeastRecentlyUsedCache

public LeastRecentlyUsedCache()

Creates a cache with an initial capacity of DEFAULT_INITIAL_CAPACITY, a maximum capacity of DEFAULT_CAPACITY entries and an expiration threshold of DEFAULT_THRESHOLD_SECS seconds.

LeastRecentlyUsedCache

public LeastRecentlyUsedCache(int capacity,
                      long threshold)

Creates a cache based on given configuration parameters.

The cache's initial capacity is set to the lesser of DEFAULT_INITIAL_CAPACITY and capacity.

Parameters:

capacity - the maximum number of entries the cache can manage

threshold - the period of time of inactivity (in seconds) after which an entry is considered stale and can be evicted from the cache if a new entry is to be added to the cache

LeastRecentlyUsedCache

public LeastRecentlyUsedCache(int initialCapacity,
                      int maxCapacity,
                      long threshold)

Creates a cache based on given configuration parameters.

Parameters:

initialCapacity - The initial number of entries the cache will be initialized to support. The cache's capacity will be doubled dynamically every time 0.75 percent of its current capacity is used but it will never exceed maxCapacity.

maxCapacity - The maximum number of entries the cache can manage

threshold - The period of time of inactivity (in seconds) after which an entry is considered stale and can be evicted from the cache if a new entry is to be added to the cache

Method Detail

addEvictionListener

public void addEvictionListener(LeastRecentlyUsedCache.EvictionListener<V> listener)

Registers a listener to be notified about (stale) entries being evicted from the cache.

Parameters:

listener - the listener

isEvictingOnReadAccess

public boolean isEvictingOnReadAccess()

Get evict mode on read access.

Returns:

true, if entries are evicted on read access, when expired, false, if not.

setEvictingOnReadAccess

public void setEvictingOnReadAccess(boolean evict)

Set evict mode on read access.

Parameters:

evict - true, if entries are evicted on read access, when expired, false, if not.

isUpdatingOnReadAccess

public boolean isUpdatingOnReadAccess()

Get update last-access time mode on read access.

Returns:

true, if entries last-access time is updated on read access, false, if not.

setUpdatingOnReadAccess

public void setUpdatingOnReadAccess(boolean update)

Set update last-access time mode on read access.

Parameters:

update - true,if entries last-access time is updated on read access, false, if not.

getExpirationThreshold

public final long getExpirationThreshold()

Gets the period of time after which an entry is considered stale if it hasn't be accessed.

Returns:

the threshold in seconds

setExpirationThreshold

public final void setExpirationThreshold(long newThreshold)

Sets the period of time after which an entry is to be considered stale if it hasn't be accessed. NB: invoking this method after creation of the cache does not have an immediate effect, i.e. no (now stale) entries are purged from the cache. This happens only when a new entry is put to the cache or a stale entry is read from the cache.

Parameters:

newThreshold - the threshold in seconds

See Also:

put(Object, Object), get(Object), find(Predicate)

setExpirationThreshold

public final void setExpirationThreshold(long newThreshold,
                          TimeUnit unit)

Sets the period of time after which an entry is to be considered stale if it hasn't be accessed. NB: invoking this method after creation of the cache does not have an immediate effect, i.e. no (now stale) entries are purged from the cache. This happens only when a new entry is put to the cache or a stale entry is read from the cache.

Parameters:

newThreshold - the threshold

unit - TimeUnit for threshold

See Also:

put(Object, Object), get(Object), find(Predicate)

getCapacity

public final int getCapacity()

Gets the maximum number of entries this cache can manage.

Returns:

the number of entries

setCapacity

public final void setCapacity(int capacity)

Sets the maximum number of entries this cache can manage. NB: invoking this method after creation of the cache does not have an immediate effect, i.e. no entries are purged from the cache. This happens only when a new entry is put to the cache or a stale entry is read from the cache.

Parameters:

capacity - the maximum number of entries the cache can manage

See Also:

put(Object, Object), get(Object)

size

public final int size()

Gets the cache's current number of entries.

Returns:

the size

remainingCapacity

public final int remainingCapacity()

Gets the number of entries that can be added to this cache without the need for removing stale entries.

Returns:

The number of entries.

clear

public final void clear()

Removes all entries from the cache.

put

public final boolean put(K key,
          V value)

Puts an entry to the cache. An entry can be successfully added to the cache if any of the following conditions are met:

• The cache's remaining capacity is greater than zero.
• The cache contains at least one stale entry, i.e. an entry that has not been accessed for at least the cache's expiration threshold period. In such a case the least- recently accessed stale entry gets evicted from the cache to make place for the new entry to be added.

If an entry is evicted this method notifies all registered EvictionListeners.

Parameters:

key - the key to store the value under

value - the value to store

Returns:

true if the entry could be added to the cache, false otherwise, e.g. because the cache's remaining capacity is zero and no stale entries can be evicted

See Also:

addEvictionListener(EvictionListener)

get

public final V get(K key)

Gets a value from the cache.

Parameters:

key - the key to look up in the cache

Returns:

the value if the key has been found in the cache and the value is not stale, null otherwise

update

public final boolean update(K key)

Update the last-access time. Intended to be used, if automatic updating the last-access time on read-access is suppressed by updateOnReadAccess.

Parameters:

key - the key to update the last-access time.

Returns:

true, if updated, false, otherwise.

remove

public final V remove(K key)

Removes an entry from the cache. Doesn't call EvictionListeners.

Parameters:

key - the key of the entry to remove

Returns:

the removed value or null, if the cache does not contain the key

remove

public final V remove(K key,
       V value)

Removes provided entry from the cache. Doesn't call EvictionListeners.

Parameters:

key - the key of the entry to remove

value - value of the entry to remove

Returns:

the removed value or null, if the cache does not contain the key or entry

find

public final V find(LeastRecentlyUsedCache.Predicate<V> predicate)

Finds a value based on a predicate.

Parameters:

predicate - the condition to match. Assumed to match entries in a unique manner.

Returns:

the first value from the cache that matches according to the given predicate, or null, if no value matches

find

public final V find(LeastRecentlyUsedCache.Predicate<V> predicate,
     boolean unique)

Finds a value based on a predicate. Returns the first matching value applying the evictOnReadAccess setting.

Parameters:

predicate - the condition to match

unique - true, if the predicate matches entries in a unique manner, false, if more entries may be matched.

Returns:

the first value from the cache that matches according to the given predicate, or null, if no value matches

valuesIterator

public final Iterator<V> valuesIterator()

Gets iterator over all connections contained in this cache.

The iterator returned is directly backed by this cache's underlying map. If the cache is modified while an iteration over the values is in progress, the results of the iteration are undefined.

Removal of connections from the iterator is unsupported.

Returns:

an iterator over all connections backed by the underlying map.

values

public final Collection<V> values()

Gets all connections contained in this cache. The returned collection is intended to be used as read access, therefore the modifying methods will throw a UnsupportedOperationException. Note: the evictOnReadAccess feature may alter the underlying map even for read access. Therefore the clients should explicitly serialize access to the returned collection from multiple threads. The returned size doesn't reflect potential eviction on read-access.

Returns:

an collection of all connections backed by the underlying map.