org.infinispan.container
Class FIFODataContainer

java.lang.Object
  org.infinispan.container.FIFODataContainer

All Implemented Interfaces:

Iterable<InternalCacheEntry>, DataContainer

Direct Known Subclasses:

LRUDataContainer

@ThreadSafe
public class FIFODataContainer
extends Object
implements DataContainer

A container that maintains order of entries based on when they were placed in the container. Iterators obtained from this container maintain this order.

This container offers constant-time operation for all public API methods.

This is implemented using a set of lockable segments, each of which is a hash table, not unlike the JDK's ConcurrentHashMap with the exception that each entry is also linked.

Links are maintained using techniques inspired by H. Sundell and P. Tsigas' 2008 paper, Lock Free Deques and Doubly Linked Lists, M. Michael's 2002 paper, High Performance Dynamic Lock-Free Hash Tables and List-Based Sets

This implementation uses a technique of delegating marker nodes similar to the technique used in Sun's ConcurrentSkipListMap, which is deemed more memory efficient and better performing than AtomicMarkableReferences.

Since:

4.0

Author:

Manik Surtani, Galder Zamarreño

Nested Class Summary

protected class	FIFODataContainer.EntryIterator
protected class	FIFODataContainer.EntrySet
protected class	FIFODataContainer.ImmutableEntryIterator
protected class	FIFODataContainer.KeyIterator
protected class	FIFODataContainer.KeySet
protected class	FIFODataContainer.LinkedIterator
protected class	FIFODataContainer.ValueIterator
protected class	FIFODataContainer.Values

Constructor Summary

FIFODataContainer(int concurrencyLevel)

Method Summary

void	clear() Removes all entries in the container
boolean	containsKey(Object k) Tests whether an entry exists in the container
protected org.infinispan.container.FIFODataContainer.LinkedEntry	correctPrev(org.infinispan.container.FIFODataContainer.LinkedEntry suggestedPreviousEntry, org.infinispan.container.FIFODataContainer.LinkedEntry currentEntry) Correct 'previous' links.
Set<InternalCacheEntry>	entrySet() Returns a mutable set of immutable cache entries exposed as immutable Map.Entry instances.
InternalCacheEntry	get(Object k) Retrieves a cached entry
protected org.infinispan.container.FIFODataContainer.LinkedEntry	getNext(org.infinispan.container.FIFODataContainer.LinkedEntry current) Retrieves the next entry after a given entry, skipping marked entries accordingly.
protected void	initLinks() Initializes links to an empty container
protected boolean	isMarkedForRemoval(org.infinispan.container.FIFODataContainer.LinkedEntry e) Tests whether a given linked entry is marked for deletion.
Iterator<InternalCacheEntry>	iterator()
Set<Object>	keySet() Returns a set of keys in the container.
protected void	linkAtEnd(org.infinispan.container.FIFODataContainer.LinkedEntry entry) Links a new entry at the end of the linked list.
protected boolean	markNextReference(org.infinispan.container.FIFODataContainer.LinkedEntry e) Places a removal marker the 'next' reference on the given entry.
protected boolean	markPrevReference(org.infinispan.container.FIFODataContainer.LinkedEntry e) Places a removal marker the 'previous' reference on the given entry.
InternalCacheEntry	peek(Object k) Retrieves a cache entry in the same way as DataContainer.get(Object)} except that it does not update or reorder any of the internal constructs.
void	purgeExpired() Purges entries that have passed their expiry time
void	put(Object k, Object v, long lifespan, long maxIdle) Puts an entry in the cache along with a lifespan and a maxIdle time
InternalCacheEntry	remove(Object k) Removes an entry from the cache
int	size()
protected void	unlink(org.infinispan.container.FIFODataContainer.LinkedEntry entry) Un-links an entry from the doubly linked list in a threadsafe, lock-free manner.
Collection<Object>	values()

Methods inherited from class java.lang.Object

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

Constructor Detail

FIFODataContainer

public FIFODataContainer(int concurrencyLevel)

Method Detail

isMarkedForRemoval

protected final boolean isMarkedForRemoval(org.infinispan.container.FIFODataContainer.LinkedEntry e)

Tests whether a given linked entry is marked for deletion. In this implementation, being "marked" means that it is of type Marker rather than LinkedEntry, but given the relative cost of an "instanceof" check, we prefer to test the state of the InternalCacheEntry referenced by the LinkedEntry. An InternalCacheEntry *always* exists so if it is null, then this is a marker (or possibly the head or tail dummy entry).

Parameters:

e - entry to test

Returns:

true if the entry is marked for removal. False if it is not, or if the entry is the head or tail dummy entry.

markPrevReference

protected final boolean markPrevReference(org.infinispan.container.FIFODataContainer.LinkedEntry e)

Places a removal marker the 'previous' reference on the given entry. Note that marking a reference does not mean that the reference pointed to is marked for removal, rather it means the LinkedEntry doing the referencing is the entry to be removed.

Parameters:

e - entry

Returns:

true if the marking was successful, false otherwise. Could return false if the reference is already marked, or if the CAS failed.

markNextReference

protected final boolean markNextReference(org.infinispan.container.FIFODataContainer.LinkedEntry e)

Places a removal marker the 'next' reference on the given entry. Note that marking a reference does not mean that the reference pointed to is marked for removal, rather it means the LinkedEntry doing the referencing is the entry to be removed.

Parameters:

e - entry

Returns:

true if the marking was successful, false otherwise. Could return false if the reference is already marked, or if the CAS failed.

initLinks

protected final void initLinks()

Initializes links to an empty container

unlink

protected final void unlink(org.infinispan.container.FIFODataContainer.LinkedEntry entry)

Un-links an entry from the doubly linked list in a threadsafe, lock-free manner. The entry is typically retrieved using Segment#locklessRemove() after locking the Segment.

Parameters:

entry - entry to unlink

linkAtEnd

protected final void linkAtEnd(org.infinispan.container.FIFODataContainer.LinkedEntry entry)

Links a new entry at the end of the linked list. Typically done when a put() creates a new entry, or if ordering needs to be updated based on access. If this entry already exists in the linked list, it should first be unlink(org.infinispan.container.FIFODataContainer.LinkedEntry)ed.

Parameters:

entry - entry to link at end

getNext

protected final org.infinispan.container.FIFODataContainer.LinkedEntry getNext(org.infinispan.container.FIFODataContainer.LinkedEntry current)

Retrieves the next entry after a given entry, skipping marked entries accordingly.

Parameters:

current - current entry to inspect

Returns:

the next valid entry, or null if we have reached the end of the list.

correctPrev

protected final org.infinispan.container.FIFODataContainer.LinkedEntry correctPrev(org.infinispan.container.FIFODataContainer.LinkedEntry suggestedPreviousEntry,
                                                                                   org.infinispan.container.FIFODataContainer.LinkedEntry currentEntry)

Correct 'previous' links. This 'helper' function is used if unable to properly set previous pointers (due to a concurrent update) and is used when traversing the list in reverse.

Parameters:

suggestedPreviousEntry - suggested previous entry

currentEntry - current entry

Returns:

the actual valid, previous entry. Links are also corrected in the process.

get

public InternalCacheEntry get(Object k)

Description copied from interface: DataContainer

Retrieves a cached entry

Specified by:

get in interface DataContainer

Parameters:

k - key under which entry is stored

Returns:

entry, if it exists and has not expired, or null if not

peek

public InternalCacheEntry peek(Object k)

Description copied from interface: DataContainer

Retrieves a cache entry in the same way as DataContainer.get(Object)} except that it does not update or reorder any of the internal constructs. I.e., expiration does not happen, and in the case of the LRU container, the entry is not moved to the end of the chain. This method should be used instead of DataContainer.get(Object)} when called while iterating through the data container using methods like DataContainer.keySet() to avoid changing the underlying collection's order.

Specified by:

peek in interface DataContainer

Parameters:

k - key under which entry is stored

Returns:

entry, if it exists, or null if not

put

public void put(Object k,
                Object v,
                long lifespan,
                long maxIdle)

Description copied from interface: DataContainer

Puts an entry in the cache along with a lifespan and a maxIdle time

Specified by:

put in interface DataContainer

Parameters:

k - key under which to store entry

v - value to store

lifespan - lifespan in milliseconds. -1 means immortal.

maxIdle - max idle time for which to store entry. -1 means forever.

containsKey

public boolean containsKey(Object k)

Description copied from interface: DataContainer

Tests whether an entry exists in the container

Specified by:

containsKey in interface DataContainer

Parameters:

k - key to test

Returns:

true if entry exists and has not expired; false otherwise

remove

public InternalCacheEntry remove(Object k)

Description copied from interface: DataContainer

Removes an entry from the cache

Specified by:

remove in interface DataContainer

Parameters:

k - key to remove

Returns:

entry removed, or null if it didn't exist or had expired

size

public int size()

Specified by:

size in interface DataContainer

Returns:

count of the number of entries in the container

clear

public void clear()

Description copied from interface: DataContainer

Removes all entries in the container

Specified by:

clear in interface DataContainer

keySet

public Set<Object> keySet()

Description copied from interface: DataContainer

Returns a set of keys in the container. When iterating through the container using this method, clients should never call #get() method but instead #peek(), in order to avoid changing the order of the underlying collection as a side of effect of iterating through it.

Specified by:

keySet in interface DataContainer

Returns:

a set of keys

values

public Collection<Object> values()

Specified by:

values in interface DataContainer

Returns:

a set of values contained in the container

entrySet

public Set<InternalCacheEntry> entrySet()

Description copied from interface: DataContainer

Returns a mutable set of immutable cache entries exposed as immutable Map.Entry instances. Clients of this method such as Cache.entrySet() operation implementors are free to convert the set into an immutable set if needed, which is the most common use case. If a client needs to iterate through a mutable set of mutable cache entries, it should iterate the container itself rather than iterating through the return of entrySet().

Specified by:

entrySet in interface DataContainer

Returns:

a set of immutable cache entries

purgeExpired

public void purgeExpired()

Description copied from interface: DataContainer

Purges entries that have passed their expiry time

Specified by:

purgeExpired in interface DataContainer

iterator

public Iterator<InternalCacheEntry> iterator()

Specified by:

iterator in interface Iterable<InternalCacheEntry>