org.h2.dev.store.btree
Class CacheLIRS<K,V>

java.lang.Object
  java.util.AbstractMap<K,V>
      org.h2.dev.store.btree.CacheLIRS<K,V>

Type Parameters:

K - the key type

V - the value type

All Implemented Interfaces:

java.util.Map<K,V>

public class CacheLIRS<K,V>
extends java.util.AbstractMap<K,V>
implements java.util.Map<K,V>

A scan resistant cache. It is meant to cache objects that are relatively costly to acquire, for example file content.

This implementation is not multi-threading save. Null keys or null values are not allowed. There is no guard against bad hash functions, so it is important to the hash function of the key is good. The map fill factor is at most 75%.

Each entry is assigned a distinct memory size, and the cache will try to use at most the specified amount of memory. The memory unit is not relevant, however it is suggested to use bytes as the unit.

This class implements the LIRS replacement algorithm invented by Xiaodong Zhang and Song Jiang as described in http://www.cse.ohio-state.edu/~zhang/lirs-sigmetrics-02.html with a few smaller changes: An additional queue for non-resident entries is used, to prevent unbound memory usage. The maximum size of this queue is at most the size of the rest of the stack. About 6.25% of the mapped entries are cold.

Nested Class Summary

Nested classes/interfaces inherited from class java.util.AbstractMap

java.util.AbstractMap.SimpleEntry<K,V>, java.util.AbstractMap.SimpleImmutableEntry<K,V>

Method Summary

void	clear() Clear the cache.
boolean	containsKey(java.lang.Object key) Check whether there is a resident entry for the given key.
java.util.Set<java.util.Map.Entry<K,V>>	entrySet() Get the entry set for all resident entries.
V	get(java.lang.Object key) Get the value for the given key if the entry is cached.
int	getAverageMemory() Get the average memory used per entry.
long	getMaxMemory() Get the maximum memory to use.
int	getMemory(K key) Get the memory used for the given key.
long	getUsedMemory() Get the currently used memory.
java.util.List<K>	keys(boolean cold, boolean nonResident) Get the list of keys.
java.util.Set<K>	keySet() Get the set of keys for resident entries.
static <K,V> CacheLIRS<K,V>	newInstance(int maxMemory, int averageMemory) Create a new cache with the given memory size.
V	peek(K key) Get the value for the given key if the entry is cached.
V	put(K key, V value) Add an entry to the cache using the average memory size.
V	put(K key, V value, int memory) Add an entry to the cache.
V	remove(java.lang.Object key) Remove an entry.
void	setAverageMemory(int averageMemory) Set the average memory used per entry.
void	setMaxMemory(long maxMemory) Set the maximum memory this cache should use.
int	size() Get the number of resident entries.
int	sizeHot() Get the number of hot entries in the cache.
int	sizeMapArray() Get the length of the internal map array.
int	sizeNonResident() Get the number of non-resident entries in the cache.

Methods inherited from class java.util.AbstractMap

clone, containsValue, equals, hashCode, isEmpty, putAll, toString, values

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Map

containsValue, equals, hashCode, isEmpty, putAll, values

Method Detail

newInstance

public static <K,V> CacheLIRS<K,V> newInstance(int maxMemory,
                                               int averageMemory)

Create a new cache with the given memory size. To just limit the number of entries, use the required number as the maximum memory, and an average size of 1.

Parameters:

maxMemory - the maximum memory to use (1 or larger)

averageMemory - the average memory (1 or larger)

Returns:

the cache

clear

public void clear()

Clear the cache. This method will clear all entries (including non-resident keys) and resize the internal array.

Specified by:

clear in interface java.util.Map<K,V>

Overrides:

clear in class java.util.AbstractMap<K,V>

peek

public V peek(K key)

Get the value for the given key if the entry is cached. This method does not modify the internal state.

Parameters:

key - the key (may not be null)

Returns:

the value, or null if there is no resident entry

getMemory

public int getMemory(K key)

Get the memory used for the given key.

Parameters:

key - the key (may not be null)

Returns:

the memory, or 0 if there is no resident entry

get

public V get(java.lang.Object key)

Get the value for the given key if the entry is cached. This method adjusts the internal state of the cache, to ensure commonly used entries stay in the cache.

Specified by:

get in interface java.util.Map<K,V>

Overrides:

get in class java.util.AbstractMap<K,V>

Parameters:

key - the key (may not be null)

Returns:

the value, or null if there is no resident entry

put

public V put(K key,
             V value)

Add an entry to the cache using the average memory size.

Specified by:

put in interface java.util.Map<K,V>

Overrides:

put in class java.util.AbstractMap<K,V>

Parameters:

key - the key (may not be null)

value - the value (may not be null)

Returns:

the old value, or null if there is no resident entry

put

public V put(K key,
             V value,
             int memory)

Add an entry to the cache. The entry may or may not exist in the cache yet. This method will usually mark unknown entries as cold and known entries as hot.

Parameters:

key - the key (may not be null)

value - the value (may not be null)

memory - the memory used for the given entry

Returns:

the old value, or null if there is no resident entry

remove

public V remove(java.lang.Object key)

Remove an entry. Both resident and non-resident entries can be removed.

Specified by:

remove in interface java.util.Map<K,V>

Overrides:

remove in class java.util.AbstractMap<K,V>

Parameters:

key - the key (may not be null)

Returns:

the old value, or null if there is no resident entry

keys

public java.util.List<K> keys(boolean cold,
                              boolean nonResident)

Get the list of keys. This method allows to view the internal state of the cache.

Parameters:

cold - if true, only keys for the cold entries are returned

nonResident - true for non-resident entries

Returns:

the key list

size

public int size()

Get the number of resident entries.

Specified by:

size in interface java.util.Map<K,V>

Overrides:

size in class java.util.AbstractMap<K,V>

Returns:

the number of entries

containsKey

public boolean containsKey(java.lang.Object key)

Check whether there is a resident entry for the given key.

Specified by:

containsKey in interface java.util.Map<K,V>

Overrides:

containsKey in class java.util.AbstractMap<K,V>

Parameters:

key - the key (may not be null)

Returns:

true if there is a resident entry

keySet

public java.util.Set<K> keySet()

Get the set of keys for resident entries.

Specified by:

keySet in interface java.util.Map<K,V>

Overrides:

keySet in class java.util.AbstractMap<K,V>

Returns:

the set of keys

entrySet

public java.util.Set<java.util.Map.Entry<K,V>> entrySet()

Get the entry set for all resident entries.

Specified by:

entrySet in interface java.util.Map<K,V>

Specified by:

entrySet in class java.util.AbstractMap<K,V>

Returns:

the entry set

sizeHot

public int sizeHot()

Get the number of hot entries in the cache.

Returns:

the number of hot entries

sizeNonResident

public int sizeNonResident()

Get the number of non-resident entries in the cache.

Returns:

the number of non-resident entries

sizeMapArray

public int sizeMapArray()

Get the length of the internal map array.

Returns:

the size of the array

getUsedMemory

public long getUsedMemory()

Get the currently used memory.

Returns:

the used memory

setMaxMemory

public void setMaxMemory(long maxMemory)

Set the maximum memory this cache should use. This will not immediately cause entries to get removed however; it will only change the limit. To resize the internal array, call the clear method.

Parameters:

maxMemory - the maximum size (1 or larger)

getMaxMemory

public long getMaxMemory()

Get the maximum memory to use.

Returns:

the maximum memory

setAverageMemory

public void setAverageMemory(int averageMemory)

Set the average memory used per entry. It is used to calculate the length of the internal array.

Parameters:

averageMemory - the average memory used (1 or larger)

getAverageMemory

public int getAverageMemory()

Get the average memory used per entry.

Returns:

the average memory