net.yacy.cora.storage

Class ConcurrentARC<K,V>

java.lang.Object

java.util.AbstractMap<K,V>

net.yacy.cora.storage.ConcurrentARC<K,V>

All Implemented Interfaces:

java.lang.Iterable<java.util.Map.Entry<K,V>>, java.util.Map<K,V>, ARC<K,V>

public final class ConcurrentARC<K,V>
extends java.util.AbstractMap<K,V>
implements java.util.Map<K,V>, java.lang.Iterable<java.util.Map.Entry<K,V>>, ARC<K,V>

This is a simple cache using two generations of hashtables to store the content with a LFU strategy. The Algorithm is described in a slightly more complex version as Adaptive Replacement Cache, "ARC". For details see http://www.almaden.ibm.com/cs/people/dmodha/ARC.pdf or http://en.wikipedia.org/wiki/Adaptive_Replacement_Cache This version omits the ghost entry handling which is described in ARC, and keeps both cache levels at the same size.

Nested Class Summary

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

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

Nested classes/interfaces inherited from interface java.util.Map

java.util.Map.Entry<K,V>

Field Summary

Fields

Modifier and Type	Field and Description
private ARC<K,V>[]	arc
private int	mask

Constructor Summary

Constructors

Constructor and Description
ConcurrentARC(int cacheSize, int partitions) create a concurrent ARC based on a HashARC.
ConcurrentARC(int cacheSize, int partitions, java.util.Comparator<? super K> comparator) create a concurrent ARC based on a ComparableARC

Method Summary

Methods

Modifier and Type	Method and Description
void	clear() clear the cache
boolean	containsKey(java.lang.Object s) check if the map contains the key
java.util.Set<java.util.Map.Entry<K,V>>	entrySet() Return a Set view of the mappings contained in this map.
V	get(java.lang.Object s) get a value from the cache.
java.util.Collection<K>	getKeys(V value) check if the map contains the value
private int	getPartition(java.lang.Object x) return in which partition the Object belongs This function uses the objects hashCode() function except for byte[] keys
int	hashCode() a hash code for this ARC
void	insert(K s, V v) put a value to the cache.
void	insertIfAbsent(K s, V v) put a value to the cache if there was not an entry before do not return a previous content value
java.util.Iterator<java.util.Map.Entry<K,V>>	iterator() iterator implements the Iterable interface
static void	main(java.lang.String[] args)
V	put(K s, V v) put a value to the cache.
V	putIfAbsent(K s, V v) put a value to the cache if there was not an entry before return a previous content value
V	remove(java.lang.Object s) remove an entry from the cache
int	size() get the size of the ARC.

Methods inherited from class java.util.AbstractMap

clone, containsValue, equals, isEmpty, keySet, 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, isEmpty, keySet, putAll, values

Field Detail

mask

private final int mask

arc

private final ARC<K,V>[] arc

Constructor Detail

ConcurrentARC

public ConcurrentARC(int cacheSize,
             int partitions)

create a concurrent ARC based on a HashARC. The type of the key elements must implement a hashing function

Parameters:

cacheSize - the number of maximum entries

partitions - the number of partitions

ConcurrentARC

public ConcurrentARC(int cacheSize,
             int partitions,
             java.util.Comparator<? super K> comparator)

create a concurrent ARC based on a ComparableARC

Parameters:

cacheSize - the number of maximum entries

partitions - the number of partitions

comparator - a comparator for the key object which may be of type byte[]

Method Detail

insert

public final void insert(K s,
          V v)

put a value to the cache.

Specified by:

insert in interface ARC<K,V>

Parameters:

s -

v -

insertIfAbsent

public void insertIfAbsent(K s,
                  V v)

put a value to the cache if there was not an entry before do not return a previous content value

Specified by:

insertIfAbsent in interface ARC<K,V>

Parameters:

s -

v -

putIfAbsent

public V putIfAbsent(K s,
            V v)

put a value to the cache if there was not an entry before return a previous content value

Specified by:

putIfAbsent in interface ARC<K,V>

Parameters:

s -

v -

Returns:

the value before inserting the new value

put

public final V put(K s,
    V v)

put a value to the cache.

Specified by:

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

Specified by:

put in interface ARC<K,V>

Overrides:

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

Parameters:

s -

v -

get

public final V get(java.lang.Object s)

get a value from the cache.

Specified by:

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

Specified by:

get in interface ARC<K,V>

Overrides:

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

Parameters:

s -

Returns:

the value

getKeys

public java.util.Collection<K> getKeys(V value)

check if the map contains the value

Specified by:

getKeys in interface ARC<K,V>

Parameters:

value -

Returns:

the keys that have the given value

containsKey

public final boolean containsKey(java.lang.Object s)

check if the map contains the key

Specified by:

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

Specified by:

containsKey in interface ARC<K,V>

Overrides:

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

Parameters:

s -

Returns:

remove

public final V remove(java.lang.Object s)

remove an entry from the cache

Specified by:

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

Specified by:

remove in interface ARC<K,V>

Overrides:

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

Parameters:

s -

Returns:

the old value

clear

public final void clear()

clear the cache

Specified by:

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

Specified by:

clear in interface ARC<K,V>

Overrides:

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

size

public final int size()

get the size of the ARC.

Specified by:

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

Specified by:

size in interface ARC<K,V>

Overrides:

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

Returns:

the complete number of entries in the ARC cache

iterator

public java.util.Iterator<java.util.Map.Entry<K,V>> iterator()

iterator implements the Iterable interface

Specified by:

iterator in interface java.lang.Iterable<java.util.Map.Entry<K,V>>

Specified by:

iterator in interface ARC<K,V>

entrySet

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

Return a Set view of the mappings contained in this map. This method is the basis for all methods that are implemented by a AbstractMap implementation

Specified by:

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

Specified by:

entrySet in interface ARC<K,V>

Specified by:

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

Returns:

a set view of the mappings contained in this map

hashCode

public int hashCode()

a hash code for this ARC

Specified by:

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

Specified by:

hashCode in interface ARC<K,V>

Overrides:

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

Returns:

a hash code

getPartition

private int getPartition(java.lang.Object x)

return in which partition the Object belongs This function uses the objects hashCode() function except for byte[] keys

Returns:

the partition number

main

public static void main(java.lang.String[] args)