An in-memory LRU cache is so often needed that I figured it would make
sense to have a dedicated implementation. Combining the CacheStore and
ReplacementPolicy allows for better optimized implementations for
special cases, such as this.
Feel free to include it if you find it useful.
(: A ;)
--
Antti Koivunen (Mr.) <[EMAIL PROTECTED]>
---------------------------------------------
The song of life might not be a simple one,
but there's plenty of room for improvisation.
---------------------------------------------
/*
* Copyright (C) The Apache Software Foundation. All rights reserved.
*
* This software is published under the terms of the Apache Software License
* version 1.1, a copy of which has been included with this distribution in
* the LICENSE.txt file.
*/
package org.apache.avalon.excalibur.cache;
import java.util.HashMap;
/**
* An in-memory LRU (least recently used) cache implementation that allows its
* capacity to be dynamically adjusted. Two alternative methods for ordering the
* entries are supported, <code>BUBBLE</code> and <code>MOVE_TO_TOP</code>. In
* the former, each successful call to the method {@link #get get(Object key)}
* will cause the object to 'bubble' up one entry away from the 'drop zone', and
* in the latter, the object will be literally moved to the top.
* <p>
* This implementation uses a custom linked list for maintaining the element
* order, backed by a HashMap for quick lookups. The ordering is performed
* entirely by passing variable references, so the performance should be fairly
* close to that of HashMap (although put operations include an extra object
* instantiation).
* <p>
* <b>This implementation is not synchronized.</b> If multiple threads
* access the same instance concurrently, it <b>must</b> be externally
* synchronized, e.g. by wrapping it inside a {@link SynchronizedCache}.
*
* @author <a href="mailto:[EMAIL PROTECTED]";>Antti Koivunen</a>
* @version $Revision: $ $Date: $
*/
public class LRUMemoryCache extends AbstractCache
{
/**
* The constant indicating that the method 'bubble' should be used for
* element ordering.
*/
public static final int BUBBLE = 1;
/**
* The constant indicating that the method 'move to top' should be used for
* element ordering.
*/
public static final int MOVE_TO_TOP = 2;
private HashMap m_entries;
private int m_capacity;
private int m_mode;
private Entry m_head = new Entry( null, null, null, null );
/**
* Creates a new instance of <code>LRUMemoryCache</code> with the specified
* (initial) capacity and mode (either BUBBLE or MOVE_TO_TOP).
*
* @throws IllegalArgumentException if <code>capacity</code> is less than
* zero or if <code>mode</code> is not BUBBLE or MOVE_TO_TOP.
*/
public LRUMemoryCache( final int capacity, final int mode )
{
if ( capacity < 0 )
{
throw new IllegalArgumentException("The capacity cannot be negative.");
}
if ( mode != BUBBLE && mode != MOVE_TO_TOP )
{
throw new IllegalArgumentException("Unsupported mode.");
}
m_capacity = capacity;
m_entries = new HashMap( capacity );
m_mode = mode;
m_head.prev = m_head.next = m_head;
}
/**
* Stores the specified object in the cache and associates it with the
* specified key.
*
* @param key The key to be associated with the specified object.
* @param value The object to be cached.
* @return Previous value associated with the specified key, or
* <code>null</code> if not found.
*/
public Object put( final Object key, final Object value )
{
final Entry entry = addEntryBefore( key, value, m_head.next );
final Entry old = (Entry) m_entries.put( key, entry );
trimToCapacity();
notifyAdded( key, value );
if ( old != null )
{
return old.value;
}
return null;
}
/**
* Returns the object associated with the specified key.
*
* @param key The key.
* @return The cached object or <code>null</code> if not found.
*/
public Object get( final Object key )
{
final Entry entry = (Entry) m_entries.get( key );
if ( entry == null )
{
return null;
}
recordHit( entry );
return entry.value;
}
/**
* Removes the object associated with the specified key.
*
* @param key The cache key.
* @return Previous value associated with the specified key, or
* <code>null</code> if not found.
*/
public Object remove( final Object key )
{
final Entry entry = (Entry) m_entries.remove( key );
if ( entry == null )
{
return null;
}
removeEntry( entry );
return entry.value;
}
/**
* Returns <code>true</code> if this cache contains an object associated
* with the specified key.
*
* @param key The key.
* @return <code>true</code> if this cache contains an object associated
* with the specified key.
*/
public boolean containsKey( final Object key )
{
return m_entries.containsKey( key );
}
/**
* Returns the number of objects currently cached.
*/
public int size()
{
return m_entries.size();
}
/**
* Returns the maximum number of objects to be cached.
*/
public int capacity()
{
return m_capacity;
}
/**
* Removes all cache entries, but does not modify the capacity.
*/
public void clear()
{
m_head.next = m_head.prev = m_head;
m_entries.clear();
}
/**
* Sets the maximum number of objects to be cached. The cache size will be
* trimmed down to the new capacity, if necessary.
*
* @param key The new capacity.
* @throws IllegalArgumentException if <code>capacity < 0</code>.
*/
public void setCapacity( final int capacity )
{
if ( capacity < 0 )
{
throw new IllegalArgumentException("The capacity cannot be negative.");
}
m_capacity = capacity;
trimToCapacity();
}
/**
* Returns a string representation of this cache.
*/
public String toString()
{
StringBuffer sb = new StringBuffer("[")
.append(getClass().getName()).append(": ")
.append("size = ").append(size()).append(", ")
.append("capacity = ").append(capacity())
.append("]");
return sb.toString();
}
private void trimToCapacity()
{
while ( size() > capacity() )
{
removeLRU();
}
}
/**
* Removes the least recently used cache entry.
*/
private void removeLRU()
{
if ( m_head == m_head.prev )
{
return; // Cache empty
}
m_entries.remove( m_head.prev.key );
removeEntry( m_head.prev );
}
private void recordHit( final Entry entry )
{
if ( m_mode == MOVE_TO_TOP )
{
moveToTop( entry );
}
else
{
bubble( entry );
}
}
private void moveToTop( final Entry entry )
{
removeEntry( entry );
insertEntryBefore( entry, m_head.next );
}
private void bubble( final Entry entry )
{
removeEntry( entry );
insertEntryBefore( entry, entry.prev );
}
private Entry addEntryBefore( final Object key,
final Object value,
final Entry refEntry )
{
final Entry entry = new Entry( key, value, refEntry.prev, refEntry );
entry.prev.next = entry;
entry.next.prev = entry;
return entry;
}
private void insertEntryBefore( final Entry entry, final Entry refEntry )
{
entry.prev = refEntry.prev;
entry.next = refEntry;
entry.prev.next = entry;
entry.next.prev = entry;
}
private void removeEntry( final Entry entry )
{
entry.prev.next = entry.next;
entry.next.prev = entry.prev;
notifyRemoved( entry.key, entry.value );
}
/**
* Entry in the linked list that maintains the LRU element order.
*/
private static class Entry
{
Object key;
Object value;
Entry prev;
Entry next;
Entry( final Object key, final Object value,
final Entry prev, final Entry next )
{
this.key = key;
this.value = value;
this.prev = prev;
this.next = next;
}
}
}
--
To unsubscribe, e-mail: <mailto:[EMAIL PROTECTED]>
For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>
