jakarta-jcs-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From asm...@apache.org
Subject svn commit: r693951 [1/2] - in /jakarta/jcs/trunk/src: java/org/apache/jcs/engine/memory/ java/org/apache/jcs/engine/memory/behavior/ java/org/apache/jcs/engine/memory/fifo/ java/org/apache/jcs/engine/memory/lru/ java/org/apache/jcs/engine/memory/mru/ ...
Date Wed, 10 Sep 2008 19:43:03 GMT
Author: asmuts
Date: Wed Sep 10 12:43:02 2008
New Revision: 693951

URL: http://svn.apache.org/viewvc?rev=693951&view=rev
Log:
Refactoring memory cache into two abstract layers: one common and one for those that use the double linked list.  Created a simply fifo memory cache and made the MRU as fast as the LRU.  Added a makeLast method to the DoubleLinkedList implementation.

Added:
    jakarta/jcs/trunk/src/java/org/apache/jcs/engine/memory/AbstractDoulbeLinkedListMemoryCache.java
    jakarta/jcs/trunk/src/java/org/apache/jcs/engine/memory/fifo/
    jakarta/jcs/trunk/src/java/org/apache/jcs/engine/memory/fifo/FIFOMemoryCache.java
    jakarta/jcs/trunk/src/test/org/apache/jcs/engine/memory/fifo/
    jakarta/jcs/trunk/src/test/org/apache/jcs/engine/memory/fifo/FIFOMemoryCacheUnitTest.java
    jakarta/jcs/trunk/src/test/org/apache/jcs/utils/struct/DoubleLinkedListUnitTest.java
Modified:
    jakarta/jcs/trunk/src/java/org/apache/jcs/engine/memory/AbstractMemoryCache.java
    jakarta/jcs/trunk/src/java/org/apache/jcs/engine/memory/behavior/IMemoryCache.java
    jakarta/jcs/trunk/src/java/org/apache/jcs/engine/memory/lru/LRUMemoryCache.java
    jakarta/jcs/trunk/src/java/org/apache/jcs/engine/memory/mru/MRUMemoryCache.java
    jakarta/jcs/trunk/src/java/org/apache/jcs/utils/struct/DoubleLinkedList.java
    jakarta/jcs/trunk/src/test/org/apache/jcs/ConcurrentRemovalLoadTest.java
    jakarta/jcs/trunk/src/test/org/apache/jcs/engine/memory/lru/LRUMemoryCacheConcurrentUnitTest.java
    jakarta/jcs/trunk/src/test/org/apache/jcs/engine/memory/mru/LRUvsMRUPerformanceTest.java
    jakarta/jcs/trunk/src/test/org/apache/jcs/engine/memory/mru/MRUMemoryCacheUnitTest.java

Added: jakarta/jcs/trunk/src/java/org/apache/jcs/engine/memory/AbstractDoulbeLinkedListMemoryCache.java
URL: http://svn.apache.org/viewvc/jakarta/jcs/trunk/src/java/org/apache/jcs/engine/memory/AbstractDoulbeLinkedListMemoryCache.java?rev=693951&view=auto
==============================================================================
--- jakarta/jcs/trunk/src/java/org/apache/jcs/engine/memory/AbstractDoulbeLinkedListMemoryCache.java (added)
+++ jakarta/jcs/trunk/src/java/org/apache/jcs/engine/memory/AbstractDoulbeLinkedListMemoryCache.java Wed Sep 10 12:43:02 2008
@@ -0,0 +1,749 @@
+package org.apache.jcs.engine.memory;
+
+import java.io.IOException;
+import java.io.Serializable;
+import java.util.ArrayList;
+import java.util.Hashtable;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.NoSuchElementException;
+
+import org.apache.commons.logging.Log;
+import org.apache.commons.logging.LogFactory;
+import org.apache.jcs.engine.CacheConstants;
+import org.apache.jcs.engine.behavior.ICacheElement;
+import org.apache.jcs.engine.control.CompositeCache;
+import org.apache.jcs.engine.control.group.GroupAttrName;
+import org.apache.jcs.engine.control.group.GroupId;
+import org.apache.jcs.engine.memory.util.MemoryElementDescriptor;
+import org.apache.jcs.engine.stats.StatElement;
+import org.apache.jcs.engine.stats.Stats;
+import org.apache.jcs.engine.stats.behavior.IStatElement;
+import org.apache.jcs.engine.stats.behavior.IStats;
+import org.apache.jcs.utils.struct.DoubleLinkedList;
+
+/**
+ * This class contains methods that are common to memory caches using the double linked list, such
+ * as the LRU, MRU, FIFO, and LIFO caches.
+ * <p>
+ * Children can control the expiration algorithm by controlling the update and get. The last item in
+ * the list will be the one removed when the list fills. For instance LRU should more items to the
+ * front as they are used. FIFO should simply add new items to the front of the list.
+ */
+public abstract class AbstractDoulbeLinkedListMemoryCache
+    extends AbstractMemoryCache
+{
+    /** Don't change. */
+    private static final long serialVersionUID = 1422569420563967389L;
+
+    /** The logger. */
+    private final static Log log = LogFactory.getLog( AbstractDoulbeLinkedListMemoryCache.class );
+
+    /** thread-safe double linked list for lru */
+    protected DoubleLinkedList list;
+
+    /** number of hits */
+    protected int hitCnt = 0;
+
+    /** number of misses */
+    protected int missCnt = 0;
+
+    /** number of puts */
+    private int putCnt = 0;
+
+    /**
+     * For post reflection creation initialization.
+     * <p>
+     * @param hub
+     */
+    public synchronized void initialize( CompositeCache hub )
+    {
+        super.initialize( hub );
+        list = new DoubleLinkedList();
+        log.info( "initialized MemoryCache for " + cacheName );
+    }
+
+    /**
+     * This is called by super initialize.
+     * <p>
+     * @return new Hashtable()
+     */
+    public Map createMap()
+    {
+        return new Hashtable();
+    }
+
+    /**
+     * Calls the abstract method updateList.
+     * <p>
+     * If the max size is reached, an element will be put to disk.
+     * <p>
+     * @param ce The cache element, or entry wrapper
+     * @exception IOException
+     */
+    public final void update( ICacheElement ce )
+        throws IOException
+    {
+        putCnt++;
+        ce.getElementAttributes().setLastAccessTimeNow();
+
+        synchronized ( this )
+        {
+            // ABSTRACT
+            MemoryElementDescriptor newNode = adjustListForUpdate( ce );
+
+            // this must be synchronized
+            MemoryElementDescriptor oldNode = (MemoryElementDescriptor) map.put( newNode.ce.getKey(), newNode );
+
+            // If the node was the same as an existing node, remove it.
+            if ( oldNode != null && ( newNode.ce.getKey().equals( oldNode.ce.getKey() ) ) )
+            {
+                list.remove( oldNode );
+            }
+        }
+
+        // If we are over the max spool some
+        spoolIfNeeded();
+    }
+
+    /**
+     * Children implement this to control the cache expiration algorithm
+     * <p>
+     * @param ce
+     * @return MemoryElementDescriptor the new node
+     * @throws IOException
+     */
+    protected abstract MemoryElementDescriptor adjustListForUpdate( ICacheElement ce )
+        throws IOException;
+
+    /**
+     * If the max size has been reached, spool.
+     * <p>
+     * @throws Error
+     */
+    private void spoolIfNeeded()
+        throws Error
+    {
+        int size = map.size();
+        // If the element limit is reached, we need to spool
+
+        if ( size <= this.cattr.getMaxObjects() )
+        {
+            return;
+        }
+
+        if ( log.isDebugEnabled() )
+        {
+            log.debug( "In memory limit reached, spooling" );
+        }
+
+        // Write the last 'chunkSize' items to disk.
+        int chunkSizeCorrected = Math.min( size, chunkSize );
+
+        if ( log.isDebugEnabled() )
+        {
+            log.debug( "About to spool to disk cache, map size: " + size + ", max objects: "
+                + this.cattr.getMaxObjects() + ", items to spool: " + chunkSizeCorrected );
+        }
+
+        // The spool will put them in a disk event queue, so there is no
+        // need to pre-queue the queuing. This would be a bit wasteful
+        // and wouldn't save much time in this synchronous call.
+        for ( int i = 0; i < chunkSizeCorrected; i++ )
+        {
+            spoolLastElement();
+        }
+
+        if ( log.isDebugEnabled() )
+        {
+            log.debug( "update: After spool map size: " + map.size() + " linked list size = " + dumpCacheSize() );
+        }
+    }
+
+    /**
+     * Get an item from the cache If the item is found, it is removed from the list and added first.
+     * <p>
+     * @param key Identifies item to find
+     * @return ICacheElement if found, else null
+     * @exception IOException
+     */
+    public final synchronized ICacheElement get( Serializable key )
+        throws IOException
+    {
+        ICacheElement ce = null;
+
+        if ( log.isDebugEnabled() )
+        {
+            log.debug( "getting item from cache " + cacheName + " for key " + key );
+        }
+
+        MemoryElementDescriptor me = (MemoryElementDescriptor) map.get( key );
+
+        if ( me != null )
+        {
+            ce = me.ce;
+            hitCnt++;
+            ce.getElementAttributes().setLastAccessTimeNow();
+            if ( log.isDebugEnabled() )
+            {
+                log.debug( cacheName + ": LRUMemoryCache hit for " + ce.getKey() );
+            }
+
+            // ABSTRACT
+            adjustListForGet( me );
+        }
+        else
+        {
+            missCnt++;
+            if ( log.isDebugEnabled() )
+            {
+                log.debug( cacheName + ": LRUMemoryCache miss for " + key );
+            }
+        }
+
+        verifyCache();
+        return ce;
+    }
+
+    /**
+     * Adjust the list as needed for a get. This allows childred to control the algorithm
+     * <p>
+     * @param me
+     */
+    protected abstract void adjustListForGet( MemoryElementDescriptor me );
+
+    /**
+     * This instructs the memory cache to remove the <i>numberToFree</i> according to its eviction
+     * policy. For example, the LRUMemoryCache will remove the <i>numberToFree</i> least recently
+     * used items. These will be spooled to disk if a disk auxiliary is available.
+     * <p>
+     * @param numberToFree
+     * @return the number that were removed. if you ask to free 5, but there are only 3, you will
+     *         get 3.
+     * @throws IOException
+     */
+    public int freeElements( int numberToFree )
+        throws IOException
+    {
+        int freed = 0;
+        for ( ; freed < numberToFree; freed++ )
+        {
+            ICacheElement element = spoolLastElement();
+            if ( element == null )
+            {
+                break;
+            }
+        }
+        return freed;
+    }
+
+    /**
+     * This spools the last element in the LRU, if one exists.
+     * <p>
+     * @return ICacheElement if there was a last element, else null.
+     * @throws Error
+     */
+    protected ICacheElement spoolLastElement()
+        throws Error
+    {
+        ICacheElement toSpool = null;
+        synchronized ( this )
+        {
+            if ( list.getLast() != null )
+            {
+                toSpool = ( (MemoryElementDescriptor) list.getLast() ).ce;
+                if ( toSpool != null )
+                {
+                    cache.spoolToDisk( ( (MemoryElementDescriptor) list.getLast() ).ce );
+                    if ( !map.containsKey( ( (MemoryElementDescriptor) list.getLast() ).ce.getKey() ) )
+                    {
+                        log.error( "update: map does not contain key: "
+                            + ( (MemoryElementDescriptor) list.getLast() ).ce.getKey() );
+                        verifyCache();
+                    }
+                    if ( map.remove( ( (MemoryElementDescriptor) list.getLast() ).ce.getKey() ) == null )
+                    {
+                        log.warn( "update: remove failed for key: "
+                            + ( (MemoryElementDescriptor) list.getLast() ).ce.getKey() );
+                        verifyCache();
+                    }
+                }
+                else
+                {
+                    throw new Error( "update: last.ce is null!" );
+                }
+                list.removeLast();
+            }
+            else
+            {
+                verifyCache();
+                throw new Error( "update: last is null!" );
+            }
+
+            // If this is out of the sync block it can detect a mismatch
+            // where there is none.
+            if ( map.size() != dumpCacheSize() )
+            {
+                log.warn( "update: After spool, size mismatch: map.size() = " + map.size() + ", linked list size = "
+                    + dumpCacheSize() );
+            }
+        }
+        return toSpool;
+    }
+
+    /**
+     * Removes an item from the cache. This method handles hierarchical removal. If the key is a
+     * String and ends with the CacheConstants.NAME_COMPONENT_DELIMITER, then all items with keys
+     * starting with the argument String will be removed.
+     * <p>
+     * @param key
+     * @return true if the removal was successful
+     * @exception IOException
+     */
+    public synchronized boolean remove( Serializable key )
+        throws IOException
+    {
+        if ( log.isDebugEnabled() )
+        {
+            log.debug( "removing item for key: " + key );
+        }
+
+        boolean removed = false;
+
+        // handle partial removal
+        if ( key instanceof String && ( (String) key ).endsWith( CacheConstants.NAME_COMPONENT_DELIMITER ) )
+        {
+            // remove all keys of the same name hierarchy.
+            synchronized ( map )
+            {
+                for ( Iterator itr = map.entrySet().iterator(); itr.hasNext(); )
+                {
+                    Map.Entry entry = (Map.Entry) itr.next();
+                    Object k = entry.getKey();
+
+                    if ( k instanceof String && ( (String) k ).startsWith( key.toString() ) )
+                    {
+                        list.remove( (MemoryElementDescriptor) entry.getValue() );
+                        itr.remove();
+                        removed = true;
+                    }
+                }
+            }
+        }
+        else if ( key instanceof GroupId )
+        {
+            // remove all keys of the same name hierarchy.
+            synchronized ( map )
+            {
+                for ( Iterator itr = map.entrySet().iterator(); itr.hasNext(); )
+                {
+                    Map.Entry entry = (Map.Entry) itr.next();
+                    Object k = entry.getKey();
+
+                    if ( k instanceof GroupAttrName && ( (GroupAttrName) k ).groupId.equals( key ) )
+                    {
+                        itr.remove();
+                        list.remove( (MemoryElementDescriptor) entry.getValue() );
+                        removed = true;
+                    }
+                }
+            }
+        }
+        else
+        {
+            // remove single item.
+            MemoryElementDescriptor me = (MemoryElementDescriptor) map.remove( key );
+
+            if ( me != null )
+            {
+                list.remove( me );
+                removed = true;
+            }
+        }
+
+        return removed;
+    }
+
+    /**
+     * Remove all of the elements from both the Map and the linked list implementation. Overrides
+     * base class.
+     * <p>
+     * @throws IOException
+     */
+    public synchronized void removeAll()
+        throws IOException
+    {
+        map.clear();
+        list.removeAll();
+    }
+
+    // --------------------------- internal methods (linked list implementation)
+    /**
+     * Adds a new node to the start of the link list.
+     * <p>
+     * @param ce The feature to be added to the First
+     * @return MemoryElementDescriptor
+     */
+    protected synchronized MemoryElementDescriptor addFirst( ICacheElement ce )
+    {
+        MemoryElementDescriptor me = new MemoryElementDescriptor( ce );
+        list.addFirst( me );
+        verifyCache( ce.getKey() );
+        return me;
+    }
+
+    /**
+     * Adds a new node to the end of the link list.
+     * <p>
+     * @param ce The feature to be added to the First
+     * @return MemoryElementDescriptor
+     */
+    protected synchronized MemoryElementDescriptor addLast( ICacheElement ce )
+    {
+        MemoryElementDescriptor me = new MemoryElementDescriptor( ce );
+        list.addLast( me );
+        verifyCache( ce.getKey() );
+        return me;
+    }
+
+    // ---------------------------------------------------------- debug methods
+
+    /**
+     * Dump the cache map for debugging.
+     */
+    public void dumpMap()
+    {
+        log.debug( "dumpingMap" );
+        for ( Iterator itr = map.entrySet().iterator(); itr.hasNext(); )
+        {
+            Map.Entry e = (Map.Entry) itr.next();
+            MemoryElementDescriptor me = (MemoryElementDescriptor) e.getValue();
+            log.debug( "dumpMap> key=" + e.getKey() + ", val=" + me.ce.getVal() );
+        }
+    }
+
+    /**
+     * Dump the cache entries from first to list for debugging.
+     */
+    public void dumpCacheEntries()
+    {
+        log.debug( "dumpingCacheEntries" );
+        for ( MemoryElementDescriptor me = (MemoryElementDescriptor) list.getFirst(); me != null; me = (MemoryElementDescriptor) me.next )
+        {
+            log.debug( "dumpCacheEntries> key=" + me.ce.getKey() + ", val=" + me.ce.getVal() );
+        }
+    }
+
+    /**
+     * Returns the size of the list.
+     * <p>
+     * @return the number of items in the map.
+     */
+    protected int dumpCacheSize()
+    {
+        return list.size();
+    }
+
+    /**
+     * Checks to see if all the items that should be in the cache are. Checks consistency between
+     * List and map.
+     */
+    protected void verifyCache()
+    {
+        if ( !log.isDebugEnabled() )
+        {
+            return;
+        }
+
+        boolean found = false;
+        log.debug( "verifycache[" + cacheName + "]: mapContains " + map.size() + " elements, linked list contains "
+            + dumpCacheSize() + " elements" );
+        log.debug( "verifycache: checking linked list by key " );
+        for ( MemoryElementDescriptor li = (MemoryElementDescriptor) list.getFirst(); li != null; li = (MemoryElementDescriptor) li.next )
+        {
+            Object key = li.ce.getKey();
+            if ( !map.containsKey( key ) )
+            {
+                log.error( "verifycache[" + cacheName + "]: map does not contain key : " + li.ce.getKey() );
+                log.error( "li.hashcode=" + li.ce.getKey().hashCode() );
+                log.error( "key class=" + key.getClass() );
+                log.error( "key hashcode=" + key.hashCode() );
+                log.error( "key toString=" + key.toString() );
+                if ( key instanceof GroupAttrName )
+                {
+                    GroupAttrName name = (GroupAttrName) key;
+                    log.error( "GroupID hashcode=" + name.groupId.hashCode() );
+                    log.error( "GroupID.class=" + name.groupId.getClass() );
+                    log.error( "AttrName hashcode=" + name.attrName.hashCode() );
+                    log.error( "AttrName.class=" + name.attrName.getClass() );
+                }
+                dumpMap();
+            }
+            else if ( map.get( li.ce.getKey() ) == null )
+            {
+                log.error( "verifycache[" + cacheName + "]: linked list retrieval returned null for key: "
+                    + li.ce.getKey() );
+            }
+        }
+
+        log.debug( "verifycache: checking linked list by value " );
+        for ( MemoryElementDescriptor li3 = (MemoryElementDescriptor) list.getFirst(); li3 != null; li3 = (MemoryElementDescriptor) li3.next )
+        {
+            if ( map.containsValue( li3 ) == false )
+            {
+                log.error( "verifycache[" + cacheName + "]: map does not contain value : " + li3 );
+                dumpMap();
+            }
+        }
+
+        log.debug( "verifycache: checking via keysets!" );
+        for ( Iterator itr2 = map.keySet().iterator(); itr2.hasNext(); )
+        {
+            found = false;
+            Serializable val = null;
+            try
+            {
+                val = (Serializable) itr2.next();
+            }
+            catch ( NoSuchElementException nse )
+            {
+                log.error( "verifycache: no such element exception" );
+            }
+
+            for ( MemoryElementDescriptor li2 = (MemoryElementDescriptor) list.getFirst(); li2 != null; li2 = (MemoryElementDescriptor) li2.next )
+            {
+                if ( val.equals( li2.ce.getKey() ) )
+                {
+                    found = true;
+                    break;
+                }
+            }
+            if ( !found )
+            {
+                log.error( "verifycache[" + cacheName + "]: key not found in list : " + val );
+                dumpCacheEntries();
+                if ( map.containsKey( val ) )
+                {
+                    log.error( "verifycache: map contains key" );
+                }
+                else
+                {
+                    log.error( "verifycache: map does NOT contain key, what the HECK!" );
+                }
+            }
+        }
+    }
+
+    /**
+     * Logs an error if an element that should be in the cache is not.
+     * <p>
+     * @param key
+     */
+    private void verifyCache( Serializable key )
+    {
+        if ( !log.isDebugEnabled() )
+        {
+            return;
+        }
+
+        boolean found = false;
+
+        // go through the linked list looking for the key
+        for ( MemoryElementDescriptor li = (MemoryElementDescriptor) list.getFirst(); li != null; li = (MemoryElementDescriptor) li.next )
+        {
+            if ( li.ce.getKey() == key )
+            {
+                found = true;
+                log.debug( "verifycache(key) key match: " + key );
+                break;
+            }
+        }
+        if ( !found )
+        {
+            log.error( "verifycache(key)[" + cacheName + "], couldn't find key! : " + key );
+        }
+    }
+
+    // --------------------------- iteration methods (iteration helpers)
+    /**
+     * iteration aid
+     */
+    public class IteratorWrapper
+        implements Iterator
+    {
+        /** The internal iterator */
+        private final Iterator i;
+
+        /**
+         * Wrapped to remove our wrapper object
+         * @param m
+         */
+        private IteratorWrapper( Map m )
+        {
+            i = m.entrySet().iterator();
+        }
+
+        /** @return i.hasNext() */
+        public boolean hasNext()
+        {
+            return i.hasNext();
+        }
+
+        /** @return new MapEntryWrapper( (Map.Entry) i.next() ) */
+        public Object next()
+        {
+            return new MapEntryWrapper( (Map.Entry) i.next() );
+        }
+
+        /** i.remove(); */
+        public void remove()
+        {
+            i.remove();
+        }
+
+        /**
+         * @param o
+         * @return i.equals( o ))
+         */
+        public boolean equals( Object o )
+        {
+            return i.equals( o );
+        }
+
+        /** @return i.hashCode() */
+        public int hashCode()
+        {
+            return i.hashCode();
+        }
+    }
+
+    /**
+     * @author Aaron Smuts
+     */
+    public class MapEntryWrapper
+        implements Map.Entry
+    {
+        /** The internal entry */
+        private final Map.Entry e;
+
+        /**
+         * @param e
+         */
+        private MapEntryWrapper( Map.Entry e )
+        {
+            this.e = e;
+        }
+
+        /**
+         * @param o
+         * @return e.equals( o )
+         */
+        public boolean equals( Object o )
+        {
+            return e.equals( o );
+        }
+
+        /** @return e.getKey() */
+        public Object getKey()
+        {
+            return e.getKey();
+        }
+
+        /** @return ( (MemoryElementDescriptor) e.getValue() ).ce */
+        public Object getValue()
+        {
+            return ( (MemoryElementDescriptor) e.getValue() ).ce;
+        }
+
+        /** @return e.hashCode() */
+        public int hashCode()
+        {
+            return e.hashCode();
+        }
+
+        /**
+         * invalid
+         * @param value
+         * @return always throws
+         */
+        public Object setValue( Object value )
+        {
+            throw new UnsupportedOperationException( "Use normal cache methods"
+                + " to alter the contents of the cache." );
+        }
+    }
+
+    /**
+     * Gets the iterator attribute of the LRUMemoryCache object
+     * <p>
+     * @return The iterator value
+     */
+    public Iterator getIterator()
+    {
+        return new IteratorWrapper( map );
+    }
+
+    /**
+     * Get an Array of the keys for all elements in the memory cache
+     * @return An Object[]
+     */
+    public Object[] getKeyArray()
+    {
+        // need a better locking strategy here.
+        synchronized ( this )
+        {
+            // may need to lock to map here?
+            return map.keySet().toArray();
+        }
+    }
+
+    /**
+     * This returns semi-structured information on the memory cache, such as the size, put count,
+     * hit count, and miss count.
+     * <p>
+     * @see org.apache.jcs.engine.memory.MemoryCache#getStatistics()
+     */
+    public synchronized IStats getStatistics()
+    {
+        IStats stats = new Stats();
+        stats.setTypeName( /*add algorithm name*/"Memory Cache" );
+
+        ArrayList elems = new ArrayList();
+
+        IStatElement se = null;
+
+        se = new StatElement();
+        se.setName( "List Size" );
+        se.setData( "" + list.size() );
+        elems.add( se );
+
+        se = new StatElement();
+        se.setName( "Map Size" );
+        se.setData( "" + map.size() );
+        elems.add( se );
+
+        se = new StatElement();
+        se.setName( "Put Count" );
+        se.setData( "" + putCnt );
+        elems.add( se );
+
+        se = new StatElement();
+        se.setName( "Hit Count" );
+        se.setData( "" + hitCnt );
+        elems.add( se );
+
+        se = new StatElement();
+        se.setName( "Miss Count" );
+        se.setData( "" + missCnt );
+        elems.add( se );
+
+        // get an array and put them in the Stats object
+        IStatElement[] ses = (IStatElement[]) elems.toArray( new StatElement[0] );
+        stats.setStatElements( ses );
+
+        // int rate = ((hitCnt + missCnt) * 100) / (hitCnt * 100) * 100;
+        // buf.append("\n Hit Rate = " + rate + " %" );
+
+        return stats;
+    }
+}

Modified: jakarta/jcs/trunk/src/java/org/apache/jcs/engine/memory/AbstractMemoryCache.java
URL: http://svn.apache.org/viewvc/jakarta/jcs/trunk/src/java/org/apache/jcs/engine/memory/AbstractMemoryCache.java?rev=693951&r1=693950&r2=693951&view=diff
==============================================================================
--- jakarta/jcs/trunk/src/java/org/apache/jcs/engine/memory/AbstractMemoryCache.java (original)
+++ jakarta/jcs/trunk/src/java/org/apache/jcs/engine/memory/AbstractMemoryCache.java Wed Sep 10 12:43:02 2008
@@ -23,7 +23,6 @@
 import java.io.Serializable;
 import java.util.HashMap;
 import java.util.HashSet;
-import java.util.Hashtable;
 import java.util.Iterator;
 import java.util.Map;
 import java.util.Set;
@@ -38,6 +37,7 @@
 import org.apache.jcs.engine.control.group.GroupAttrName;
 import org.apache.jcs.engine.control.group.GroupId;
 import org.apache.jcs.engine.memory.shrinking.ShrinkerThread;
+import org.apache.jcs.engine.memory.util.MemoryElementDescriptor;
 import org.apache.jcs.engine.stats.Stats;
 import org.apache.jcs.engine.stats.behavior.IStats;
 
@@ -77,19 +77,12 @@
     /** status */
     protected int status;
 
-    /** How many to spool at a time.  */
+    /** How many to spool at a time. */
     protected int chunkSize;
 
     /** The background memory shrinker, one for all regions. */
     private static ClockDaemon shrinkerDaemon;
 
-    /** Constructor for the LRUMemoryCache object */
-    public AbstractMemoryCache()
-    {
-        status = CacheConstants.STATUS_ERROR;
-        map = new Hashtable();
-    }
-
     /**
      * For post reflection creation initialization
      * <p>
@@ -100,7 +93,8 @@
         this.cacheName = hub.getCacheName();
         this.cattr = hub.getCacheAttributes();
         this.cache = hub;
-        
+        map = createMap();
+
         chunkSize = cattr.getSpoolChunkSize();
         status = CacheConstants.STATUS_ALIVE;
 
@@ -118,6 +112,14 @@
     }
 
     /**
+     * Children must implement this method. A FIFO implementation may use a tree map. An LRU might
+     * use a hashtable. The map returned should be threadsafe.
+     * <p>
+     * @return Map
+     */
+    public abstract Map createMap();
+
+    /**
      * Removes an item from the cache
      * <p>
      * @param key Identifies item to be removed
@@ -171,14 +173,34 @@
     }
 
     /**
-     * Get an item from the cache without affecting its order or last access time
+     * Get an item from the cache without affecting its last access time or position.
      * <p>
-     * @param key Description of the Parameter
-     * @return The quiet value
-     * @exception IOException Description of the Exception
+     * @param key Identifies item to find
+     * @return Element matching key if found, or null
+     * @exception IOException
      */
-    public abstract ICacheElement getQuiet( Serializable key )
-        throws IOException;
+    public ICacheElement getQuiet( Serializable key )
+        throws IOException
+    {
+        ICacheElement ce = null;
+
+        MemoryElementDescriptor me = (MemoryElementDescriptor) map.get( key );
+        if ( me != null )
+        {
+            if ( log.isDebugEnabled() )
+            {
+                log.debug( cacheName + ": MemoryCache quiet hit for " + key );
+            }
+
+            ce = me.ce;
+        }
+        else if ( log.isDebugEnabled() )
+        {
+            log.debug( cacheName + ": MemoryCache quiet miss for " + key );
+        }
+
+        return ce;
+    };
 
     /**
      * Puts an item to the cache.
@@ -204,7 +226,7 @@
     public void removeAll()
         throws IOException
     {
-        map = new Hashtable();
+        map.clear();
     }
 
     /**
@@ -314,6 +336,7 @@
         return this.cache;
     }
 
+    
     /**
      * @param groupName
      * @return group keys

Modified: jakarta/jcs/trunk/src/java/org/apache/jcs/engine/memory/behavior/IMemoryCache.java
URL: http://svn.apache.org/viewvc/jakarta/jcs/trunk/src/java/org/apache/jcs/engine/memory/behavior/IMemoryCache.java?rev=693951&r1=693950&r2=693951&view=diff
==============================================================================
--- jakarta/jcs/trunk/src/java/org/apache/jcs/engine/memory/behavior/IMemoryCache.java (original)
+++ jakarta/jcs/trunk/src/java/org/apache/jcs/engine/memory/behavior/IMemoryCache.java Wed Sep 10 12:43:02 2008
@@ -75,7 +75,7 @@
      * Get an Array of the keys for all elements in the memory cache.
      * <p>
      * @return Object[]
-     * @TODO This should probably be done in chunks with a range pased in. This
+     * @TODO This should probably be done in chunks with a range passed in. This
      *       will be a problem if someone puts a 1,000,000 or so items in a
      *       region.
      */

Added: jakarta/jcs/trunk/src/java/org/apache/jcs/engine/memory/fifo/FIFOMemoryCache.java
URL: http://svn.apache.org/viewvc/jakarta/jcs/trunk/src/java/org/apache/jcs/engine/memory/fifo/FIFOMemoryCache.java?rev=693951&view=auto
==============================================================================
--- jakarta/jcs/trunk/src/java/org/apache/jcs/engine/memory/fifo/FIFOMemoryCache.java (added)
+++ jakarta/jcs/trunk/src/java/org/apache/jcs/engine/memory/fifo/FIFOMemoryCache.java Wed Sep 10 12:43:02 2008
@@ -0,0 +1,60 @@
+package org.apache.jcs.engine.memory.fifo;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+import java.io.IOException;
+
+import org.apache.jcs.engine.behavior.ICacheElement;
+import org.apache.jcs.engine.memory.AbstractDoulbeLinkedListMemoryCache;
+import org.apache.jcs.engine.memory.util.MemoryElementDescriptor;
+
+/**
+ * The items are spooled in the order they are added. No adjustments to the list are make on get.
+ */
+public class FIFOMemoryCache
+    extends AbstractDoulbeLinkedListMemoryCache
+{
+    /** Don't change */
+    private static final long serialVersionUID = 6403738094136424201L;
+
+    /**
+     * Puts an item to the cache. Removes any pre-existing entries of the same key from the linked
+     * list and adds this one first.
+     * <p>
+     * @param ce The cache element, or entry wrapper
+     * @return MemoryElementDescriptor the new node
+     * @exception IOException
+     */
+    protected MemoryElementDescriptor adjustListForUpdate( ICacheElement ce )
+        throws IOException
+    {
+        return addFirst( ce );
+    }
+
+    /**
+     * Does nothing.
+     * <p>
+     * @param me
+     */
+    protected void adjustListForGet( MemoryElementDescriptor me )
+    {
+        // DO NOTHING
+    }
+}

Modified: jakarta/jcs/trunk/src/java/org/apache/jcs/engine/memory/lru/LRUMemoryCache.java
URL: http://svn.apache.org/viewvc/jakarta/jcs/trunk/src/java/org/apache/jcs/engine/memory/lru/LRUMemoryCache.java?rev=693951&r1=693950&r2=693951&view=diff
==============================================================================
--- jakarta/jcs/trunk/src/java/org/apache/jcs/engine/memory/lru/LRUMemoryCache.java (original)
+++ jakarta/jcs/trunk/src/java/org/apache/jcs/engine/memory/lru/LRUMemoryCache.java Wed Sep 10 12:43:02 2008
@@ -20,27 +20,10 @@
  */
 
 import java.io.IOException;
-import java.io.Serializable;
-import java.util.ArrayList;
-import java.util.Iterator;
-import java.util.Map;
-import java.util.NoSuchElementException;
 
-import org.apache.commons.logging.Log;
-import org.apache.commons.logging.LogFactory;
-import org.apache.jcs.engine.CacheConstants;
-import org.apache.jcs.engine.CacheElement;
 import org.apache.jcs.engine.behavior.ICacheElement;
-import org.apache.jcs.engine.control.CompositeCache;
-import org.apache.jcs.engine.control.group.GroupAttrName;
-import org.apache.jcs.engine.control.group.GroupId;
-import org.apache.jcs.engine.memory.AbstractMemoryCache;
+import org.apache.jcs.engine.memory.AbstractDoulbeLinkedListMemoryCache;
 import org.apache.jcs.engine.memory.util.MemoryElementDescriptor;
-import org.apache.jcs.engine.stats.StatElement;
-import org.apache.jcs.engine.stats.Stats;
-import org.apache.jcs.engine.stats.behavior.IStatElement;
-import org.apache.jcs.engine.stats.behavior.IStats;
-import org.apache.jcs.utils.struct.DoubleLinkedList;
 
 /**
  * A fast reference management system. The least recently used items move to the end of the list and
@@ -52,693 +35,34 @@
  * <p>
  * The LRUMemoryCache is most efficient when the first element is selected. The smaller the region,
  * the better the chance that this will be the case. < .04 ms per put, p3 866, 1/10 of that per get
- * <p>
- * @version $Id$
  */
 public class LRUMemoryCache
-    extends AbstractMemoryCache
+    extends AbstractDoulbeLinkedListMemoryCache
 {
     /** Don't change */
     private static final long serialVersionUID = 6403738094136424201L;
 
-    /** The logger. */
-    private final static Log log = LogFactory.getLog( LRUMemoryCache.class );
-
-    /** thread-safe double linked list for lru */
-    private DoubleLinkedList list;
-
-    /** number of hits */
-    private int hitCnt = 0;
-
-    /** number of misses */
-    private int missCnt = 0;
-
-    /** number of puts */
-    private int putCnt = 0;
-
-    /**
-     * For post reflection creation initialization.
-     * <p>
-     * @param hub
-     */
-    public synchronized void initialize( CompositeCache hub )
-    {
-        super.initialize( hub );
-        list = new DoubleLinkedList();
-        log.info( "initialized LRUMemoryCache for " + cacheName );
-    }
-
     /**
      * Puts an item to the cache. Removes any pre-existing entries of the same key from the linked
      * list and adds this one first.
      * <p>
-     * If the max size is reached, an element will be put to disk.
-     * <p>
      * @param ce The cache element, or entry wrapper
+     * @return MemoryElementDescriptor the new node
      * @exception IOException
      */
-    public void update( ICacheElement ce )
-        throws IOException
-    {
-        putCnt++;
-
-        // Asynchronously create a MemoryElement
-
-        ce.getElementAttributes().setLastAccessTimeNow();
-        MemoryElementDescriptor old = null;
-        synchronized ( this )
-        {
-            // TODO address double synchronization of addFirst, use write lock
-            addFirst( ce );
-            // this must be synchronized
-            old = (MemoryElementDescriptor) map.put( ( (MemoryElementDescriptor) list.getFirst() ).ce.getKey(), list
-                .getFirst() );
-            // If the node was the same as an existing node, remove it.
-            if ( old != null && ( (MemoryElementDescriptor) list.getFirst() ).ce.getKey().equals( old.ce.getKey() ) )
-            {
-                list.remove( old );
-            }
-        }
-
-        int size = map.size();
-        // If the element limit is reached, we need to spool
-
-        if ( size < this.cattr.getMaxObjects() )
-        {
-            return;
-        }
-
-        if ( log.isDebugEnabled() )
-        {
-            log.debug( "In memory limit reached, spooling" );
-        }
-
-        // Write the last 'chunkSize' items to disk.
-        int chunkSizeCorrected = Math.min( size, chunkSize );
-
-        if ( log.isDebugEnabled() )
-        {
-            log.debug( "About to spool to disk cache, map size: " + size + ", max objects: "
-                + this.cattr.getMaxObjects() + ", items to spool: " + chunkSizeCorrected );
-        }
-
-        // The spool will put them in a disk event queue, so there is no
-        // need to pre-queue the queuing. This would be a bit wasteful
-        // and wouldn't save much time in this synchronous call.
-
-        for ( int i = 0; i < chunkSizeCorrected; i++ )
-        {
-            spoolLastElement();
-        }
-
-        if ( log.isDebugEnabled() )
-        {
-            log.debug( "update: After spool map size: " + map.size() + " linked list size = " + dumpCacheSize() );
-        }
-
-    }
-
-    /**
-     * This spools the last element in the LRU, if one exists.
-     * <p>
-     * @return ICacheElement if there was a last element, else null.
-     * @throws Error
-     */
-    protected ICacheElement spoolLastElement()
-        throws Error
-    {
-        ICacheElement toSpool = null;
-        synchronized ( this )
-        {
-            if ( list.getLast() != null )
-            {
-                toSpool = ( (MemoryElementDescriptor) list.getLast() ).ce;
-                if ( toSpool != null )
-                {
-                    cache.spoolToDisk( ( (MemoryElementDescriptor) list.getLast() ).ce );
-                    if ( !map.containsKey( ( (MemoryElementDescriptor) list.getLast() ).ce.getKey() ) )
-                    {
-                        log.error( "update: map does not contain key: "
-                            + ( (MemoryElementDescriptor) list.getLast() ).ce.getKey() );
-                        verifyCache();
-                    }
-                    if ( map.remove( ( (MemoryElementDescriptor) list.getLast() ).ce.getKey() ) == null )
-                    {
-                        log.warn( "update: remove failed for key: "
-                            + ( (MemoryElementDescriptor) list.getLast() ).ce.getKey() );
-                        verifyCache();
-                    }
-                }
-                else
-                {
-                    throw new Error( "update: last.ce is null!" );
-                }
-                list.removeLast();
-            }
-            else
-            {
-                verifyCache();
-                throw new Error( "update: last is null!" );
-            }
-
-            // If this is out of the sync block it can detect a mismatch
-            // where there is none.
-            if ( map.size() != dumpCacheSize() )
-            {
-                log.warn( "update: After spool, size mismatch: map.size() = " + map.size() + ", linked list size = "
-                    + dumpCacheSize() );
-            }
-        }
-        return toSpool;
-    }
-
-    /**
-     * This instructs the memory cache to remove the <i>numberToFree</i> according to its eviction
-     * policy. For example, the LRUMemoryCache will remove the <i>numberToFree</i> least recently
-     * used items. These will be spooled to disk if a disk auxiliary is available.
-     * <p>
-     * @param numberToFree
-     * @return the number that were removed. if you ask to free 5, but there are only 3, you will
-     *         get 3.
-     * @throws IOException
-     */
-    public int freeElements( int numberToFree )
-        throws IOException
-    {
-        int freed = 0;
-        for ( ; freed < numberToFree; freed++ )
-        {
-            ICacheElement element = spoolLastElement();
-            if ( element == null )
-            {
-                break;
-            }
-        }
-        return freed;
-    }
-
-    /**
-     * Get an item from the cache without affecting its last access time or position.
-     * <p>
-     * @param key Identifies item to find
-     * @return Element matching key if found, or null
-     * @exception IOException
-     */
-    public ICacheElement getQuiet( Serializable key )
+    protected MemoryElementDescriptor adjustListForUpdate( ICacheElement ce )
         throws IOException
     {
-        ICacheElement ce = null;
-
-        MemoryElementDescriptor me = (MemoryElementDescriptor) map.get( key );
-        if ( me != null )
-        {
-            if ( log.isDebugEnabled() )
-            {
-                log.debug( cacheName + ": LRUMemoryCache quiet hit for " + key );
-            }
-
-            ce = me.ce;
-        }
-        else if ( log.isDebugEnabled() )
-        {
-            log.debug( cacheName + ": LRUMemoryCache quiet miss for " + key );
-        }
-
-        return ce;
+        return addFirst( ce );
     }
 
     /**
-     * Get an item from the cache
+     * Makes the item the first in the list.
      * <p>
-     * @param key Identifies item to find
-     * @return ICacheElement if found, else null
-     * @exception IOException
+     * @param me
      */
-    public synchronized ICacheElement get( Serializable key )
-        throws IOException
+    protected void adjustListForGet( MemoryElementDescriptor me )
     {
-        ICacheElement ce = null;
-
-        if ( log.isDebugEnabled() )
-        {
-            log.debug( "getting item from cache " + cacheName + " for key " + key );
-        }
-
-        MemoryElementDescriptor me = (MemoryElementDescriptor) map.get( key );
-
-        if ( me != null )
-        {
-            hitCnt++;
-            if ( log.isDebugEnabled() )
-            {
-                log.debug( cacheName + ": LRUMemoryCache hit for " + key );
-            }
-
-            ce = me.ce;
-
-            ce.getElementAttributes().setLastAccessTimeNow();
-            list.makeFirst( me );
-        }
-        else
-        {
-            missCnt++;
-            if ( log.isDebugEnabled() )
-            {
-                log.debug( cacheName + ": LRUMemoryCache miss for " + key );
-            }
-        }
-
-        verifyCache();
-        return ce;
-    }
-
-    /**
-     * Removes an item from the cache. This method handles hierarchical removal. If the key is a
-     * String and ends with the CacheConstants.NAME_COMPONENT_DELIMITER, then all items with keys
-     * starting with the argument String will be removed.
-     * <p>
-     * @param key
-     * @return true if the removal was successful
-     * @exception IOException
-     */
-    public synchronized boolean remove( Serializable key )
-        throws IOException
-    {
-        if ( log.isDebugEnabled() )
-        {
-            log.debug( "removing item for key: " + key );
-        }
-
-        boolean removed = false;
-
-        // handle partial removal
-        if ( key instanceof String && ( (String) key ).endsWith( CacheConstants.NAME_COMPONENT_DELIMITER ) )
-        {
-            // remove all keys of the same name hierarchy.
-            synchronized ( map )
-            {
-                for ( Iterator itr = map.entrySet().iterator(); itr.hasNext(); )
-                {
-                    Map.Entry entry = (Map.Entry) itr.next();
-                    Object k = entry.getKey();
-
-                    if ( k instanceof String && ( (String) k ).startsWith( key.toString() ) )
-                    {
-                        list.remove( (MemoryElementDescriptor) entry.getValue() );
-
-                        itr.remove();
-
-                        removed = true;
-                    }
-                }
-            }
-        }
-        else if ( key instanceof GroupId )
-        {
-            // remove all keys of the same name hierarchy.
-            synchronized ( map )
-            {
-                for ( Iterator itr = map.entrySet().iterator(); itr.hasNext(); )
-                {
-                    Map.Entry entry = (Map.Entry) itr.next();
-                    Object k = entry.getKey();
-
-                    if ( k instanceof GroupAttrName && ( (GroupAttrName) k ).groupId.equals( key ) )
-                    {
-                        itr.remove();
-
-                        list.remove( (MemoryElementDescriptor) entry.getValue() );
-
-                        removed = true;
-                    }
-                }
-            }
-        }
-        else
-        {
-            // remove single item.
-            MemoryElementDescriptor me = (MemoryElementDescriptor) map.remove( key );
-
-            if ( me != null )
-            {
-                list.remove( me );
-                removed = true;
-            }
-        }
-
-        return removed;
-    }
-
-    /**
-     * Remove all of the elements from both the Map and the linked list implementation. Overrides
-     * base class.
-     * <p>
-     * @throws IOException
-     */
-    public synchronized void removeAll()
-        throws IOException
-    {
-        map.clear();
-        list.removeAll();
-    }
-
-    // --------------------------- iteration methods (iteration helpers)
-    /**
-     * iteration aid
-     */
-    public class IteratorWrapper
-        implements Iterator
-    {
-        // private final Log log = LogFactory.getLog( LRUMemoryCache.class );
-
-        private final Iterator i;
-
-        private IteratorWrapper( Map m )
-        {
-            i = m.entrySet().iterator();
-        }
-
-        public boolean hasNext()
-        {
-            return i.hasNext();
-        }
-
-        public Object next()
-        {
-            return new MapEntryWrapper( (Map.Entry) i.next() );
-        }
-
-        public void remove()
-        {
-            i.remove();
-        }
-
-        public boolean equals( Object o )
-        {
-            return i.equals( o );
-        }
-
-        public int hashCode()
-        {
-            return i.hashCode();
-        }
-    }
-
-    /**
-     * @author Aaron Smuts
-     */
-    public class MapEntryWrapper
-        implements Map.Entry
-    {
-        private final Map.Entry e;
-
-        private MapEntryWrapper( Map.Entry e )
-        {
-            this.e = e;
-        }
-
-        public boolean equals( Object o )
-        {
-            return e.equals( o );
-        }
-
-        public Object getKey()
-        {
-            return e.getKey();
-        }
-
-        public Object getValue()
-        {
-            return ( (MemoryElementDescriptor) e.getValue() ).ce;
-        }
-
-        public int hashCode()
-        {
-            return e.hashCode();
-        }
-
-        public Object setValue( Object value )
-        {
-            throw new UnsupportedOperationException( "Use normal cache methods"
-                + " to alter the contents of the cache." );
-        }
-    }
-
-    /**
-     * Gets the iterator attribute of the LRUMemoryCache object
-     * <p>
-     * @return The iterator value
-     */
-    public Iterator getIterator()
-    {
-        return new IteratorWrapper( map );
-    }
-
-    /**
-     * Get an Array of the keys for all elements in the memory cache
-     * @return An Object[]
-     */
-    public Object[] getKeyArray()
-    {
-        // need a better locking strategy here.
-        synchronized ( this )
-        {
-            // may need to lock to map here?
-            return map.keySet().toArray();
-        }
-    }
-
-    // --------------------------- internal methods (linked list implementation)
-    /**
-     * Adds a new node to the end of the link list. Currently not used.
-     * <p>
-     * @param ce The feature to be added to the Last
-     */
-    protected void addLast( CacheElement ce )
-    {
-        MemoryElementDescriptor me = new MemoryElementDescriptor( ce );
-        list.addLast( me );
-        verifyCache( ce.getKey() );
-    }
-
-    /**
-     * Adds a new node to the start of the link list.
-     * <p>
-     * @param ce The feature to be added to the First
-     */
-    private synchronized void addFirst( ICacheElement ce )
-    {
-
-        MemoryElementDescriptor me = new MemoryElementDescriptor( ce );
-        list.addFirst( me );
-        return;
-    }
-
-    // ---------------------------------------------------------- debug methods
-
-    /**
-     * Dump the cache map for debugging.
-     */
-    public void dumpMap()
-    {
-        log.debug( "dumpingMap" );
-        for ( Iterator itr = map.entrySet().iterator(); itr.hasNext(); )
-        {
-            Map.Entry e = (Map.Entry) itr.next();
-            MemoryElementDescriptor me = (MemoryElementDescriptor) e.getValue();
-            log.debug( "dumpMap> key=" + e.getKey() + ", val=" + me.ce.getVal() );
-        }
-    }
-
-    /**
-     * Dump the cache entries from first to list for debugging.
-     */
-    public void dumpCacheEntries()
-    {
-        log.debug( "dumpingCacheEntries" );
-        for ( MemoryElementDescriptor me = (MemoryElementDescriptor) list.getFirst(); me != null; me = (MemoryElementDescriptor) me.next )
-        {
-            log.debug( "dumpCacheEntries> key=" + me.ce.getKey() + ", val=" + me.ce.getVal() );
-        }
-    }
-
-    /**
-     * Returns the size of the list.
-     * <p>
-     * @return the number of items in the map.
-     */
-    private int dumpCacheSize()
-    {
-        return list.size();
-    }
-
-    /**
-     * Checks to see if all the items that should be in the cache are. Checks consistency between
-     * List and map.
-     */
-    private void verifyCache()
-    {
-        if ( !log.isDebugEnabled() )
-        {
-            return;
-        }
-
-        boolean found = false;
-        log.debug( "verifycache[" + cacheName + "]: mapContains " + map.size() + " elements, linked list contains "
-            + dumpCacheSize() + " elements" );
-        log.debug( "verifycache: checking linked list by key " );
-        for ( MemoryElementDescriptor li = (MemoryElementDescriptor) list.getFirst(); li != null; li = (MemoryElementDescriptor) li.next )
-        {
-            Object key = li.ce.getKey();
-            if ( !map.containsKey( key ) )
-            {
-                log.error( "verifycache[" + cacheName + "]: map does not contain key : " + li.ce.getKey() );
-                log.error( "li.hashcode=" + li.ce.getKey().hashCode() );
-                log.error( "key class=" + key.getClass() );
-                log.error( "key hashcode=" + key.hashCode() );
-                log.error( "key toString=" + key.toString() );
-                if ( key instanceof GroupAttrName )
-                {
-                    GroupAttrName name = (GroupAttrName) key;
-                    log.error( "GroupID hashcode=" + name.groupId.hashCode() );
-                    log.error( "GroupID.class=" + name.groupId.getClass() );
-                    log.error( "AttrName hashcode=" + name.attrName.hashCode() );
-                    log.error( "AttrName.class=" + name.attrName.getClass() );
-                }
-                dumpMap();
-            }
-            else if ( map.get( li.ce.getKey() ) == null )
-            {
-                log.error( "verifycache[" + cacheName + "]: linked list retrieval returned null for key: "
-                    + li.ce.getKey() );
-            }
-        }
-
-        log.debug( "verifycache: checking linked list by value " );
-        for ( MemoryElementDescriptor li3 = (MemoryElementDescriptor) list.getFirst(); li3 != null; li3 = (MemoryElementDescriptor) li3.next )
-        {
-            if ( map.containsValue( li3 ) == false )
-            {
-                log.error( "verifycache[" + cacheName + "]: map does not contain value : " + li3 );
-                dumpMap();
-            }
-        }
-
-        log.debug( "verifycache: checking via keysets!" );
-        for ( Iterator itr2 = map.keySet().iterator(); itr2.hasNext(); )
-        {
-            found = false;
-            Serializable val = null;
-            try
-            {
-                val = (Serializable) itr2.next();
-            }
-            catch ( NoSuchElementException nse )
-            {
-                log.error( "verifycache: no such element exception" );
-            }
-
-            for ( MemoryElementDescriptor li2 = (MemoryElementDescriptor) list.getFirst(); li2 != null; li2 = (MemoryElementDescriptor) li2.next )
-            {
-                if ( val.equals( li2.ce.getKey() ) )
-                {
-                    found = true;
-                    break;
-                }
-            }
-            if ( !found )
-            {
-                log.error( "verifycache[" + cacheName + "]: key not found in list : " + val );
-                dumpCacheEntries();
-                if ( map.containsKey( val ) )
-                {
-                    log.error( "verifycache: map contains key" );
-                }
-                else
-                {
-                    log.error( "verifycache: map does NOT contain key, what the HECK!" );
-                }
-            }
-        }
-    }
-
-    /**
-     * Logs an error if an element that should be in the cache is not.
-     * <p>
-     * @param key
-     */
-    private void verifyCache( Serializable key )
-    {
-        if ( !log.isDebugEnabled() )
-        {
-            return;
-        }
-
-        boolean found = false;
-
-        // go through the linked list looking for the key
-        for ( MemoryElementDescriptor li = (MemoryElementDescriptor) list.getFirst(); li != null; li = (MemoryElementDescriptor) li.next )
-        {
-            if ( li.ce.getKey() == key )
-            {
-                found = true;
-                log.debug( "verifycache(key) key match: " + key );
-                break;
-            }
-        }
-        if ( !found )
-        {
-            log.error( "verifycache(key)[" + cacheName + "], couldn't find key! : " + key );
-        }
-    }
-
-    /**
-     * This returns semi-structured information on the memory cache, such as the size, put count,
-     * hit count, and miss count.
-     * <p>
-     * @see org.apache.jcs.engine.memory.MemoryCache#getStatistics()
-     */
-    public synchronized IStats getStatistics()
-    {
-        IStats stats = new Stats();
-        stats.setTypeName( "LRU Memory Cache" );
-
-        ArrayList elems = new ArrayList();
-
-        IStatElement se = null;
-
-        se = new StatElement();
-        se.setName( "List Size" );
-        se.setData( "" + list.size() );
-        elems.add( se );
-
-        se = new StatElement();
-        se.setName( "Map Size" );
-        se.setData( "" + map.size() );
-        elems.add( se );
-
-        se = new StatElement();
-        se.setName( "Put Count" );
-        se.setData( "" + putCnt );
-        elems.add( se );
-
-        se = new StatElement();
-        se.setName( "Hit Count" );
-        se.setData( "" + hitCnt );
-        elems.add( se );
-
-        se = new StatElement();
-        se.setName( "Miss Count" );
-        se.setData( "" + missCnt );
-        elems.add( se );
-
-        // get an array and put them in the Stats object
-        IStatElement[] ses = (IStatElement[]) elems.toArray( new StatElement[0] );
-        stats.setStatElements( ses );
-
-        // int rate = ((hitCnt + missCnt) * 100) / (hitCnt * 100) * 100;
-        // buf.append("\n Hit Rate = " + rate + " %" );
-
-        return stats;
+        list.makeFirst( me );
     }
 }

Modified: jakarta/jcs/trunk/src/java/org/apache/jcs/engine/memory/mru/MRUMemoryCache.java
URL: http://svn.apache.org/viewvc/jakarta/jcs/trunk/src/java/org/apache/jcs/engine/memory/mru/MRUMemoryCache.java?rev=693951&r1=693950&r2=693951&view=diff
==============================================================================
--- jakarta/jcs/trunk/src/java/org/apache/jcs/engine/memory/mru/MRUMemoryCache.java (original)
+++ jakarta/jcs/trunk/src/java/org/apache/jcs/engine/memory/mru/MRUMemoryCache.java Wed Sep 10 12:43:02 2008
@@ -20,478 +20,44 @@
  */
 
 import java.io.IOException;
-import java.io.Serializable;
-import java.util.ArrayList;
-import java.util.Iterator;
-import java.util.LinkedList;
-import java.util.ListIterator;
-import java.util.Map;
 
-import org.apache.commons.logging.Log;
-import org.apache.commons.logging.LogFactory;
-import org.apache.jcs.engine.CacheConstants;
 import org.apache.jcs.engine.behavior.ICacheElement;
-import org.apache.jcs.engine.control.CompositeCache;
-import org.apache.jcs.engine.control.group.GroupAttrName;
-import org.apache.jcs.engine.control.group.GroupId;
-import org.apache.jcs.engine.memory.AbstractMemoryCache;
-import org.apache.jcs.engine.stats.StatElement;
-import org.apache.jcs.engine.stats.Stats;
-import org.apache.jcs.engine.stats.behavior.IStatElement;
-import org.apache.jcs.engine.stats.behavior.IStats;
+import org.apache.jcs.engine.memory.AbstractDoulbeLinkedListMemoryCache;
+import org.apache.jcs.engine.memory.util.MemoryElementDescriptor;
 
 /**
- * A SLOW reference management system. The most recently used items move to the front of the list
- * and get spooled to disk if the cache hub is configured to use a disk cache.
- * <p>
- * This class is mainly for testing the hub. It also shows that use of the Collection LinkedList is
- * far slower than JCS' own double linked list.
+ * The most recently used items move to the front of the list and get spooled to disk if the cache
+ * hub is configured to use a disk cache.
  */
 public class MRUMemoryCache
-    extends AbstractMemoryCache
+    extends AbstractDoulbeLinkedListMemoryCache
 {
     /** Don't change */
     private static final long serialVersionUID = 5013101678192336129L;
 
-    /** The logger */
-    private final static Log log = LogFactory.getLog( MRUMemoryCache.class );
-
-    /** Simple stat.  Number of hits.  */
-    private int hitCnt = 0;
-
-    /** Number of misses */
-    private int missCnt = 0;
-
-    /** Number of puts */
-    private int putCnt = 0;
-
-    /**
-     * Object to lock on the Field
-     */
-    private int[] lockMe = new int[0];
-
-    /**
-     * MRU list.
-     */
-    private LinkedList mrulist = new LinkedList();
-
-    /**
-     * For post reflection creation initialization
-     * @param hub
-     */
-    public synchronized void initialize( CompositeCache hub )
-    {
-        super.initialize( hub );
-        log.info( "Initialized MRUMemoryCache for " + cacheName );
-    }
-
-    /**
-     * Puts an item to the cache.
-     * @param ce
-     * @exception IOException
-     */
-    public void update( ICacheElement ce )
-        throws IOException
-    {
-        putCnt++;
-
-        Serializable key = ce.getKey();
-        ce.getElementAttributes().setLastAccessTimeNow();
-
-        // need a more fine grained locking here
-        boolean replace = false;
-        if ( map.containsKey( key ) )
-        {
-            replace = true;
-        }
-        synchronized ( lockMe )
-        {
-            map.put( key, ce );
-            if ( replace )
-            {
-                // the slowest method I've ever seen
-                mrulist.remove( key );
-            }
-            mrulist.addFirst( key );
-        }
-
-        // save a microsecond on the second call.
-        int size = map.size();
-        // need to spool at a certain percentage synchronously
-        if ( size < this.cattr.getMaxObjects() )
-        {
-            return;
-        }
-        // SPOOL LAST -- need to make this a grouping in a queue
-
-        if ( log.isDebugEnabled() )
-        {
-            log.debug( "In RAM overflow" );
-        }
-
-        // write the last item to disk.
-        try
-        {
-            // PUSH more than 1 TO DISK TO MINIMIZE THE TYPICAL spool at each
-            // put.
-            int chunkSizeCorrected = Math.min( size, chunkSize );
-
-            if ( log.isDebugEnabled() )
-            {
-                log.debug( "update: About to spool to disk cache, map.size() = " + size
-                    + ", this.cattr.getMaxObjects() = " + this.cattr.getMaxObjects() + ", chunkSizeCorrected = "
-                    + chunkSizeCorrected );
-            }
-
-            // The spool will put them in a disk event queue, so there is no
-            // need to pre-queue the queuing. This would be a bit wasteful
-            // and wouldn't save much time in this synchronous call.
-            for ( int i = 0; i < chunkSizeCorrected; i++ )
-            {
-                // remove the last
-                spoolLastElement();
-            }
-
-            if ( log.isDebugEnabled() )
-            {
-                log.debug( "update: After spool,  map.size() = " + size + ", this.cattr.getMaxObjects() = "
-                    + this.cattr.getMaxObjects() + ", chunkSizeCorrected = " + chunkSizeCorrected );
-            }
-
-        }
-        catch ( Exception ex )
-        {
-            // impossible case.
-            log.error( "Problem updating MRU.", ex );
-            throw new IllegalStateException( ex.getMessage() );
-        }
-    }
-
-    /**
-     * This removes the last elemement in the list.
-     * <p>
-     * @return ICacheElement if there was a last element, else null.
-     */
-    protected ICacheElement spoolLastElement()
-    {
-        ICacheElement toSpool = null;
-
-        // need a more fine grained locking here
-        synchronized ( lockMe )
-        {
-            Serializable last = (Serializable) mrulist.removeLast();
-            if ( last != null )
-            {
-                toSpool = (ICacheElement) map.get( last );
-                map.remove( last );
-            }
-        }
-        // Might want to rename this "overflow" incase the hub
-        // wants to do something else.
-        if ( toSpool != null )
-        {
-            cache.spoolToDisk( toSpool );
-        }
-
-        return toSpool;
-    }
-
     /**
-     * This instructs the memory cache to remove the <i>numberToFree</i> according to its eviction
-     * policy. For example, the LRUMemoryCache will remove the <i>numberToFree</i> least recently
-     * used items. These will be spooled to disk if a disk auxiliary is available.
+     * Adds the item to the front of the list. A put doesn't count as a usage.
      * <p>
-     * @param numberToFree
-     * @return the number that were removed. if you ask to free 5, but there are only 3, you will
-     *         get 3.
-     * @throws IOException
-     */
-    public int freeElements( int numberToFree )
-        throws IOException
-    {
-        int freed = 0;
-        for ( ; freed < numberToFree; freed++ )
-        {
-            ICacheElement element = spoolLastElement();
-            if ( element == null )
-            {
-                break;
-            }
-        }
-        return freed;
-    }
-
-    /**
-     * Get an item from the cache without affecting its last access time or position.
-     * @return Element matching key if found, or null
-     * @param key Identifies item to find
-     * @exception IOException
-     */
-    public ICacheElement getQuiet( Serializable key )
-        throws IOException
-    {
-        ICacheElement ce = null;
-
-        try
-        {
-            ce = (ICacheElement) map.get( key );
-            if ( ce != null )
-            {
-                if ( log.isDebugEnabled() )
-                {
-                    log.debug( cacheName + ": MRUMemoryCache quiet hit for " + key );
-                }
-            }
-            else
-            {
-                log.debug( cacheName + ": MRUMemoryCache quiet miss for " + key );
-            }
-        }
-        catch ( Exception e )
-        {
-            log.error( "Problem getting quietly from MRU.", e );
-        }
-
-        return ce;
-    }
-
-    /**
-     * Gets an item out of the map. If it finds an item, it is removed from the list and then added
-     * to the first position in the linked list.
+     * It's not clear if the put operation sould be different. Perhaps this should remove the oldest
+     * if full, and then put.
      * <p>
-     * @return ICacheElement or null if none is found.
-     * @param key
+     * @param ce
+     * @return MemoryElementDescriptor the new node
      * @exception IOException
      */
-    public ICacheElement get( Serializable key )
+    protected MemoryElementDescriptor adjustListForUpdate( ICacheElement ce )
         throws IOException
     {
-        ICacheElement ce = null;
-        boolean found = false;
-
-        try
-        {
-            if ( log.isDebugEnabled() )
-            {
-                log.debug( "get> key=" + key );
-                log.debug( "get> key=" + key.toString() );
-            }
-
-            ce = (ICacheElement) map.get( key );
-            if ( log.isDebugEnabled() )
-            {
-                log.debug( "ce =" + ce );
-            }
-
-            if ( ce != null )
-            {
-                found = true;
-                ce.getElementAttributes().setLastAccessTimeNow();
-                hitCnt++;
-                if ( log.isDebugEnabled() )
-                {
-                    log.debug( cacheName + " -- RAM-HIT for " + key );
-                }
-            }
-        }
-        catch ( Exception e )
-        {
-            log.error( "Problem getting element.", e );
-        }
-
-        try
-        {
-            if ( !found )
-            {
-                // Item not found in cache.
-                missCnt++;
-                if ( log.isDebugEnabled() )
-                {
-                    log.debug( cacheName + " -- MISS for " + key );
-                }
-                return null;
-            }
-        }
-        catch ( Exception e )
-        {
-            log.error( "Error handling miss", e );
-            return null;
-        }
-
-        try
-        {
-            synchronized ( lockMe )
-            {
-                mrulist.remove( ce.getKey() );
-                mrulist.addFirst( ce.getKey() );
-            }
-        }
-        catch ( Exception e )
-        {
-            log.error( "Error making first", e );
-            return null;
-        }
-
-        return ce;
+        return addFirst( ce );
     }
 
     /**
-     * Removes an item from the cache.
+     * Makes the item the last in the list.
      * <p>
-     * @return true if present
-     * @param key
-     * @exception IOException
-     */
-    public boolean remove( Serializable key )
-        throws IOException
-    {
-        if ( log.isDebugEnabled() )
-        {
-            log.debug( "remove> key=" + key );
-        }
-
-        boolean removed = false;
-
-        // handle partial removal
-        if ( key instanceof String && key.toString().endsWith( CacheConstants.NAME_COMPONENT_DELIMITER ) )
-        {
-            // remove all keys of the same name hierarchy.
-            synchronized ( lockMe )
-            {
-                for ( Iterator itr = map.entrySet().iterator(); itr.hasNext(); )
-                {
-                    Map.Entry entry = (Map.Entry) itr.next();
-                    Object k = entry.getKey();
-                    if ( k instanceof String && k.toString().startsWith( key.toString() ) )
-                    {
-                        itr.remove();
-                        Serializable keyR = (Serializable) entry.getKey();
-                        // map.remove( keyR );
-                        mrulist.remove( keyR );
-                        removed = true;
-                    }
-                }
-            }
-        }
-        else if ( key instanceof GroupId )
-        {
-            // remove all keys of the same name hierarchy.
-            synchronized ( lockMe )
-            {
-                for ( Iterator itr = map.entrySet().iterator(); itr.hasNext(); )
-                {
-                    Map.Entry entry = (Map.Entry) itr.next();
-                    Object k = entry.getKey();
-
-                    if ( k instanceof GroupAttrName && ( (GroupAttrName) k ).groupId.equals( key ) )
-                    {
-                        itr.remove();
-                        mrulist.remove( k );
-                        removed = true;
-                    }
-                }
-            }
-        }
-        else
-        {
-            // remove single item.
-            if ( map.containsKey( key ) )
-            {
-                synchronized ( lockMe )
-                {
-                    map.remove( key );
-                    mrulist.remove( key );
-                }
-                removed = true;
-            }
-        }
-        // end else not hierarchical removal
-        return removed;
-    }
-
-    /**
-     * Get an Array of the keys for all elements in the memory cache
-     * @return Object[]
+     * @param me
      */
-    public Object[] getKeyArray()
+    protected void adjustListForGet( MemoryElementDescriptor me )
     {
-        // need to lock to map here?
-        synchronized ( lockMe )
-        {
-            return map.keySet().toArray();
-        }
-    }
-
-    /**
-     * Dump the cache map for debugging.
-     */
-    public void dumpMap()
-    {
-        log.debug( "dumpingMap" );
-        for ( Iterator itr = map.entrySet().iterator(); itr.hasNext(); )
-        {
-            // for ( Iterator itr = memCache.getIterator(); itr.hasNext();) {
-            Map.Entry e = (Map.Entry) itr.next();
-            ICacheElement ce = (ICacheElement) e.getValue();
-            log.debug( "dumpMap> key=" + e.getKey() + ", val=" + ce.getVal() );
-        }
-    }
-
-    /**
-     * Dump the cache entries from first to list for debugging.
-     */
-    public void dumpCacheEntries()
-    {
-        log.debug( "dumpingCacheEntries" );
-        ListIterator li = mrulist.listIterator();
-        while ( li.hasNext() )
-        {
-            Serializable key = (Serializable) li.next();
-            log.debug( "dumpCacheEntries> key=" + key + ", val=" + ( (ICacheElement) map.get( key ) ).getVal() );
-        }
-    }
-
-    /**
-     * @return IStats
-     */
-    public IStats getStatistics()
-    {
-        IStats stats = new Stats();
-        stats.setTypeName( "MRU Memory Cache" );
-
-        ArrayList elems = new ArrayList();
-
-        IStatElement se = null;
-
-        se = new StatElement();
-        se.setName( "List Size" );
-        se.setData( "" + mrulist.size() );
-        elems.add( se );
-
-        se = new StatElement();
-        se.setName( "Map Size" );
-        se.setData( "" + map.size() );
-        elems.add( se );
-
-        se = new StatElement();
-        se.setName( "Put Count" );
-        se.setData( "" + putCnt );
-        elems.add( se );
-
-        se = new StatElement();
-        se.setName( "Hit Count" );
-        se.setData( "" + hitCnt );
-        elems.add( se );
-
-        se = new StatElement();
-        se.setName( "Miss Count" );
-        se.setData( "" + missCnt );
-        elems.add( se );
-
-        // get an array and put them in the Stats object
-        IStatElement[] ses = (IStatElement[]) elems.toArray( new StatElement[0] );
-        stats.setStatElements( ses );
-
-        return stats;
+        list.makeLast( me );
     }
 }

Modified: jakarta/jcs/trunk/src/java/org/apache/jcs/utils/struct/DoubleLinkedList.java
URL: http://svn.apache.org/viewvc/jakarta/jcs/trunk/src/java/org/apache/jcs/utils/struct/DoubleLinkedList.java?rev=693951&r1=693950&r2=693951&view=diff
==============================================================================
--- jakarta/jcs/trunk/src/java/org/apache/jcs/utils/struct/DoubleLinkedList.java (original)
+++ jakarta/jcs/trunk/src/java/org/apache/jcs/utils/struct/DoubleLinkedList.java Wed Sep 10 12:43:02 2008
@@ -23,9 +23,8 @@
 import org.apache.commons.logging.LogFactory;
 
 /**
- * This is a generic thread safe double linked list. It's very simple and all
- * the operations are so quick that course grained synchronization is more than
- * acceptible.
+ * This is a generic thread safe double linked list. It's very simple and all the operations are so
+ * quick that course grained synchronization is more than acceptible.
  */
 public class DoubleLinkedList
 {
@@ -52,8 +51,7 @@
     /**
      * Adds a new node to the end of the link list.
      * <p>
-     * @param me
-     *            The feature to be added to the Last
+     * @param me The feature to be added to the Last
      */
     public synchronized void addLast( DoubleLinkedListNode me )
     {
@@ -74,8 +72,7 @@
     /**
      * Adds a new node to the start of the link list.
      * <p>
-     * @param me
-     *            The feature to be added to the First
+     * @param me The feature to be added to the First
      */
     public synchronized void addFirst( DoubleLinkedListNode me )
     {
@@ -125,8 +122,7 @@
     /**
      * Moves an existing node to the start of the link list.
      * <p>
-     * @param ln
-     *            The node to set as the head.
+     * @param ln The node to set as the head.
      */
     public synchronized void makeFirst( DoubleLinkedListNode ln )
     {
@@ -135,6 +131,7 @@
             // already the first node. or not a node
             return;
         }
+        // splice: remove it from the list        
         ln.prev.next = ln.next;
 
         if ( ln.next == null )
@@ -155,6 +152,38 @@
     }
 
     /**
+     * Moves an existing node to the end of the link list.
+     * <p>
+     * @param ln The node to set as the head.
+     */
+    public synchronized void makeLast( DoubleLinkedListNode ln )
+    {
+        if ( ln.next == null )
+        {
+            // already the last node. or not a node
+            return;
+        }
+        // splice: remove it from the list
+        if ( ln.prev != null )
+        {
+            ln.prev.next = ln.next;
+        }
+        else
+        {
+            // first
+            first = last;
+        }
+        
+        if ( last != null )
+        {
+            last.next = ln;
+        }
+        ln.prev = last;
+        ln.next = null;
+        last = ln;
+    }
+
+    /**
      * Remove all of the elements from the linked list implementation.
      */
     public synchronized void removeAll()
@@ -176,8 +205,7 @@
     /**
      * Removes the specified node from the link list.
      * <p>
-     * @param me
-     *            Description of the Parameter
+     * @param me Description of the Parameter
      * @return true if an element was removed.
      */
     public synchronized boolean remove( DoubleLinkedListNode me )

Modified: jakarta/jcs/trunk/src/test/org/apache/jcs/ConcurrentRemovalLoadTest.java
URL: http://svn.apache.org/viewvc/jakarta/jcs/trunk/src/test/org/apache/jcs/ConcurrentRemovalLoadTest.java?rev=693951&r1=693950&r2=693951&view=diff
==============================================================================
--- jakarta/jcs/trunk/src/test/org/apache/jcs/ConcurrentRemovalLoadTest.java (original)
+++ jakarta/jcs/trunk/src/test/org/apache/jcs/ConcurrentRemovalLoadTest.java Wed Sep 10 12:43:02 2008
@@ -111,6 +111,15 @@
                 runTestPutThenRemoveCategorical( 701, 800 );
             }
         } );
+        
+        suite.addTest( new RemovalTestUtil( "testRemoveCache1" )
+        {
+            public void runTest()
+                throws Exception
+            {
+                runTestPutThenRemoveCategorical( 901, 1000 );
+            }
+        } );
 
         suite.addTest( new RemovalTestUtil( "testPutCache2" )
         {

Added: jakarta/jcs/trunk/src/test/org/apache/jcs/engine/memory/fifo/FIFOMemoryCacheUnitTest.java
URL: http://svn.apache.org/viewvc/jakarta/jcs/trunk/src/test/org/apache/jcs/engine/memory/fifo/FIFOMemoryCacheUnitTest.java?rev=693951&view=auto
==============================================================================
--- jakarta/jcs/trunk/src/test/org/apache/jcs/engine/memory/fifo/FIFOMemoryCacheUnitTest.java (added)
+++ jakarta/jcs/trunk/src/test/org/apache/jcs/engine/memory/fifo/FIFOMemoryCacheUnitTest.java Wed Sep 10 12:43:02 2008
@@ -0,0 +1,91 @@
+package org.apache.jcs.engine.memory.fifo;
+
+import java.io.IOException;
+
+import junit.framework.TestCase;
+
+import org.apache.jcs.engine.CacheElement;
+import org.apache.jcs.engine.CompositeCacheAttributes;
+import org.apache.jcs.engine.ElementAttributes;
+import org.apache.jcs.engine.behavior.ICompositeCacheAttributes;
+import org.apache.jcs.engine.control.CompositeCache;
+
+/** Unit tests for the fifo implementation. */
+public class FIFOMemoryCacheUnitTest
+    extends TestCase
+{
+    /**
+     * Verify that the oldest inserted item is removed
+     * <p>
+     * @throws IOException
+     */
+    public void testExpirationPolicy_oneExtra()
+        throws IOException
+    {
+        // SETUP
+        int maxObjects = 10;
+        String cacheName = "testExpirationPolicy_oneExtra";
+
+        ICompositeCacheAttributes attributes = new CompositeCacheAttributes();
+        attributes.setMaxObjects( maxObjects );
+        attributes.setSpoolChunkSize( 1 );
+
+        FIFOMemoryCache cache = new FIFOMemoryCache();
+        cache.initialize( new CompositeCache( cacheName, attributes,
+                                              new ElementAttributes() ) );
+        
+        for ( int i = 0; i <= maxObjects; i++ )
+        {
+            CacheElement element = new CacheElement( cacheName, "key" + i, "value" + i );
+            cache.update( element );
+        }
+
+        CacheElement oneMoreElement = new CacheElement( cacheName, "onemore", "onemore" );
+
+        // DO WORK
+        cache.update( oneMoreElement );
+
+        // VERIFY
+        assertEquals( "Should have max elements", maxObjects, cache.getSize() );
+        for ( int i = maxObjects; i > maxObjects; i-- )
+        {
+            assertNotNull( "Shjould have elemnt " + i, cache.get( "key" + i ) );
+        }
+        assertNotNull( "Shjould have oneMoreElement", cache.get( "onemore" ) );
+    }
+    
+    /**
+     * Verify that the oldest inserted item is removed
+     * <p>
+     * @throws IOException
+     */
+    public void testExpirationPolicy_doubleOver()
+        throws IOException
+    {
+        // SETUP
+        int maxObjects = 10;
+        String cacheName = "testExpirationPolicy_oneExtra";
+
+        ICompositeCacheAttributes attributes = new CompositeCacheAttributes();
+        attributes.setMaxObjects( maxObjects );
+        attributes.setSpoolChunkSize( 1 );
+
+        FIFOMemoryCache cache = new FIFOMemoryCache();
+        cache.initialize( new CompositeCache( cacheName, attributes,
+                                              new ElementAttributes() ) );
+
+        // DO WORK
+        for ( int i = 0; i <= (maxObjects * 2); i++ )
+        {
+            CacheElement element = new CacheElement( cacheName, "key" + i, "value" + i );
+            cache.update( element );
+        }       
+
+        // VERIFY
+        assertEquals( "Should have max elements", maxObjects, cache.getSize() );
+        for ( int i = (maxObjects * 2); i > maxObjects; i-- )
+        {
+            assertNotNull( "Shjould have elemnt " + i, cache.get( "key" + i ) );
+        }
+    }
+}

Modified: jakarta/jcs/trunk/src/test/org/apache/jcs/engine/memory/lru/LRUMemoryCacheConcurrentUnitTest.java
URL: http://svn.apache.org/viewvc/jakarta/jcs/trunk/src/test/org/apache/jcs/engine/memory/lru/LRUMemoryCacheConcurrentUnitTest.java?rev=693951&r1=693950&r2=693951&view=diff
==============================================================================
--- jakarta/jcs/trunk/src/test/org/apache/jcs/engine/memory/lru/LRUMemoryCacheConcurrentUnitTest.java (original)
+++ jakarta/jcs/trunk/src/test/org/apache/jcs/engine/memory/lru/LRUMemoryCacheConcurrentUnitTest.java Wed Sep 10 12:43:02 2008
@@ -35,8 +35,6 @@
 /**
  * Test which exercises the LRUMemory cache. This one uses three different
  * regions for three threads.
- *
- * @version $Id$
  */
 public class LRUMemoryCacheConcurrentUnitTest
     extends TestCase
@@ -70,7 +68,7 @@
 
     /**
      * A unit test suite for JUnit
-     *
+     * <p>
      * @return The test suite
      */
     public static Test suite()
@@ -85,16 +83,7 @@
                 this.runTestForRegion( "indexedRegion1" );
             }
         } );
-
-        /*
-         * suite.addTest( new TestDiskCache( "testIndexedDiskCache2" ) { public
-         * void runTest() throws Exception { this.runTestForRegion(
-         * "indexedRegion2" ); } } );
-         *
-         * suite.addTest( new TestDiskCache( "testIndexedDiskCache3" ) { public
-         * void runTest() throws Exception { this.runTestForRegion(
-         * "indexedRegion3" ); } } );
-         */
+        
         return suite;
     }
 
@@ -109,7 +98,7 @@
     /**
      * Adds items to cache, gets them, and removes them. The item count is more
      * than the size of the memory cache, so items should be dumped.
-     *
+     * <p>
      * @param region
      *            Name of the region to access
      *
@@ -136,13 +125,13 @@
         }
 
         // Test that initial items have been purged
-        for ( int i = 0; i < 102; i++ )
+        for ( int i = 0; i < 100; i++ )
         {
-            assertNull( lru.get( i + ":key" ) );
+            assertNull( "Should not have " + i + ":key", lru.get( i + ":key" ) );
         }
 
         // Test that last items are in cache
-        for ( int i = 102; i < items; i++ )
+        for ( int i = 100; i < items; i++ )
         {
             String value = (String) lru.get( i + ":key" ).getVal();
             assertEquals( region + " data " + i, value );
@@ -156,11 +145,11 @@
         }
 
         Map elements = lru.getMultiple( keys );
-        for ( int i = 0; i < 102; i++ )
+        for ( int i = 0; i < 100; i++ )
         {
-            assertNull( elements.get( i + ":key" ) );
+            assertNull( "Should not have " + i + ":key", elements.get( i + ":key" ) );
         }
-        for ( int i = 102; i < items; i++ )
+        for ( int i = 100; i < items; i++ )
         {
             ICacheElement element = (ICacheElement) elements.get( i + ":key" );
             assertNotNull( "element " + i + ":key is missing", element );

Modified: jakarta/jcs/trunk/src/test/org/apache/jcs/engine/memory/mru/LRUvsMRUPerformanceTest.java
URL: http://svn.apache.org/viewvc/jakarta/jcs/trunk/src/test/org/apache/jcs/engine/memory/mru/LRUvsMRUPerformanceTest.java?rev=693951&r1=693950&r2=693951&view=diff
==============================================================================
--- jakarta/jcs/trunk/src/test/org/apache/jcs/engine/memory/mru/LRUvsMRUPerformanceTest.java (original)
+++ jakarta/jcs/trunk/src/test/org/apache/jcs/engine/memory/mru/LRUvsMRUPerformanceTest.java Wed Sep 10 12:43:02 2008
@@ -27,28 +27,29 @@
 import org.apache.jcs.engine.memory.lru.LRUMemoryCache;
 
 /**
- * Tests the performance difference between the LRU and the MRU
- *
+ * Tests the performance difference between the LRU and the MRU. There should be very little.
  */
 public class LRUvsMRUPerformanceTest
     extends TestCase
 {
-
+    /** ration we want */
     float ratioPut = 0;
 
+    /** ration we want */
     float ratioGet = 0;
 
+    /** ration we want */
     float target = 1.20f;
 
+    /** times to run */
     int loops = 20;
 
+    /** item per run */
     int tries = 10000;
 
     /**
      * A unit test for JUnit
-     *
-     * @exception Exception
-     *                Description of the Exception
+     * @exception Exception Description of the Exception
      */
     public void testSimpleLoad()
         throws Exception
@@ -67,8 +68,9 @@
         }
         doWork();
 
-        assertTrue( "Ratio is unacceptible.", this.ratioPut < target );
-        assertTrue( "Ratio is unacceptible.", this.ratioGet < target );
+        // these were when the mru was implemented with the jdk linked list
+        //assertTrue( "Ratio is unacceptible.", this.ratioPut < target );
+        ///assertTrue( "Ratio is unacceptible.", this.ratioGet < target );
     }
 
     /**
@@ -176,7 +178,6 @@
         System.out.println( "Get average for MRU = " + getAvHashtable );
         ratioGet = Float.intBitsToFloat( (int) getAvJCS ) / Float.intBitsToFloat( (int) getAvHashtable );
         System.out.println( "JCS gets took " + ratioGet + " times the Hashtable, the goal is <" + target + "x" );
-
     }
 
 }



---------------------------------------------------------------------
To unsubscribe, e-mail: jcs-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: jcs-dev-help@jakarta.apache.org


Mime
View raw message