Hey Aaron, it definitely belongs in the Jakarta Commons Collections
package (which Turbine/Fulcrum/Torque already depend upon). I believe
that Jason has commit, or you can just send it to the commons-dev list
directly.
Thanks, Dan
[EMAIL PROTECTED] writes:
> asmuts 02/01/31 19:55:54
>
> Added: src/java/org/apache/stratum/util/lru LRUStore.java
> LRUElementDescriptor.java LRUElement.java
> ILRUElement.java
> Log:
> Added this LRUStore pulled form JCS so it can be used by other programs.
> Not sure this is where it belongs, but it can be moved. It has O(1) performance
>degredation and doesn't suffer from the O(N) limitations of the LinkedList LRU
>implementations.
>
> It comes with a partial removal and a waterfall method. it can be overridden and
>so can the element wrapper, so the system is extendable. you could extend the
>wrapper, override the put and use the get(key,container) to get the wrapper if it had
>more info.
>
> Revision Changes Path
> 1.1
>jakarta-turbine-stratum/src/java/org/apache/stratum/util/lru/LRUStore.java
>
> Index: LRUStore.java
> ===================================================================
> package org.apache.stratum.util.lru;
>
> import java.io.IOException;
> import java.io.Serializable;
>
> import java.util.HashMap;
> import java.util.Hashtable;
> import java.util.Iterator;
> import java.util.Map;
> import java.util.Set;
>
> import java.util.Map.Entry;
>
> import org.apache.stratum.util.lru.LRUElementDescriptor;
>
> /////////////////////////////////////////////////////
> /**
> * Example LRU program with O(1) performance degredation. Partial removal has
> * O(N) performance. A fast reference management system. The least recently
> * used items move to the end of the list and get waterfalled.
> *
> * Pulled from JCS project. Based on several generic algorithm book examples.
> *
> *@author asmuts
> *@created January 31, 2002
> */
> public class LRUStore implements Serializable
> {
>
> private final static boolean debugcmd = false;
> // removal
> private final static boolean debugR = false;
> //true;
>
> private final static String NAME_COMPONENT_DELIMITER = ":";
>
> /**
> * Description of the Field
> */
> protected Map map = new Hashtable();
>
> // LRU double linked list
> private LRUElementDescriptor first;
> private LRUElementDescriptor last;
>
> private int max = 1000;
>
> // make configurable
> private int chunkSize = 5;
>
>
> ////////////////////////////////////////////////////////////////////
> // for reflection
> /**
> * Constructor for the LRUStore object
> */
> public LRUStore()
> {
> // might want to consider this an error state
> //status = this.STATUS_ERROR;
> }
>
> // should use this method
>
> /**
> * Constructor for the LRUStore object
> *
> *@param max Description of the Parameter
> */
> public LRUStore( int max )
> {
> initialize( max );
> }
>
>
> // for post reflection creation initialization
> /**
> * Description of the Method
> *
> *@param max Maximum number of elements in LRUStore
> */
> public void initialize( int max )
> {
> this.max = max;
> }
>
> /**
> * Puts an item to the LRUStore.
> *
> *@param ce Description of the Parameter
> */
> public void update( ILRUElement ce )
> {
>
> addFirst( ce );
> LRUElementDescriptor old = ( LRUElementDescriptor ) map.put( ce.getKey(),
>first );
>
> if ( first.equals( old ) )
> {
> // the same as an existing item.
> removeNode( old );
> }
>
> // save a microsecond on the second call.
> int size = map.size();
> // need to spool at a certain percentage synchronously
> if ( size < max )
> {
> return;
> }
> else
> {
>
> // SPOOL LAST -- need to make this a grouping in a queue
> if ( debugcmd )
> {
> p( "IN RAM overflow" );
> }
>
> // write the last item to disk.
> try
> {
>
> // PUSH 5 TO DISK TO MINIMIZE THE TYPICAL
> int chunkSizeCorrected = Math.min( size, chunkSize );
>
> if ( debugcmd )
> {
> p( "update: About to dump , map.size() = " + size + ", max = "
>+ max + ", 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++ )
> {
> // Might want to rename this "overflow" incase the hub
> // wants to do something else.
> waterfall( last.ce );
> map.remove( last.ce.getKey() );
> removeNode( last );
> }
>
> if ( debugcmd )
> {
> p( "update: After spool, put " + last.ce.getKey() + " on disk
>cache, map.size() = " + size + ", max) = " + this.max + ", chunkSizeCorrected = " +
>chunkSizeCorrected );
> }
>
> }
> catch ( Exception ex )
> {
> // impossible case.
> ex.printStackTrace();
> throw new IllegalStateException( ex.getMessage() );
> }
>
> }
>
> }
> // end update
>
> // TODO: Implement or modify interface, just implement
> // may need insert if we want to distinguish b/wn put and replace
> /**
> * Description of the Method
> *
> *@param key Description of the Parameter
> *@param val Description of the Parameter
> */
> public void put( Serializable key, Serializable val )
> {
> LRUElement le = new LRUElement( key, val );
> update( le );
> }
>
>
> /**
> * Gets an item from the cache.
> *
> *@param key Description of the Parameter
> *@return Description of the Return Value
> */
> public Serializable get( Serializable key )
> {
> return get( key, false );
> }
>
>
> /**
> * Description of the Method
> *
> *@param key Description of the Parameter
> *@param container Description of the Parameter
> *@return Description of the Return Value
> */
> public Serializable get( Serializable key, boolean container )
> {
>
> LRUElementDescriptor me = null;
> ILRUElement ce = null;
> boolean found = false;
>
> try
> {
>
> me = ( LRUElementDescriptor ) map.get( key );
>
> if ( me == null )
> {
>
> }
> else
> {
> found = true;
> ce = me.ce;
> }
>
> }
> catch ( Exception e )
> {
> //log.error( e );
> }
>
> try
> {
>
> if ( !found )
> {
> return null;
> }
> }
> catch ( Exception e )
> {
> //log.error( e, "Error handling miss" );
> return null;
> }
>
> try
> {
> makeFirst( me );
> }
> catch ( Exception e )
> {
> //log.error( e, "Error making first" );
> return null;
> }
>
> if ( container )
> {
> return ce;
> }
> else
> {
> return ce.getVal();
> }
>
> }
> // end get
>
> /**
> * Removes an item from the cache.
> *
> *@param key Description of the Parameter
> *@return Description of the Return Value
> *@exception IOException Description of the Exception
> */
> public boolean remove( Serializable key )
> throws IOException
> {
>
> //p("remove> key="+key+", nonLocal="+nonLocal);
> boolean removed = false;
>
> // handle partial removal
> if ( key instanceof String && key.toString().endsWith(
>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 && k.toString().startsWith(
>key.toString() ) )
> {
> itr.remove();
> removeNode( ( LRUElementDescriptor ) entry.getValue() );
> removed = true;
> }
> }
> }
> }
> else
> {
> // remove single item.
> LRUElementDescriptor ce = ( LRUElementDescriptor ) map.remove( key );
> if ( ce != null )
> {
> removeNode( ce );
> removed = true;
> }
> }
> // end else not hierarchical removal
> return removed;
> }
>
>
> /**
> * Removes all cached items from the cache.
> *
> *@exception IOException Description of the Exception
> */
> public void removeAll()
> throws IOException
> {
> map = new HashMap();
> }
>
>
> /**
> * Prepares for shutdown.
> *
> *@exception IOException Description of the Exception
> */
> public void dispose()
> throws IOException
> {
> }
>
>
> /**
> * Returns the cache statistics.
> *
> *@return The stats value
> */
> public String getStats()
> {
> return "";
> }
>
>
> /**
> * Returns the current cache size.
> *
> *@return The size value
> */
> public int getSize()
> {
> return this.map.size();
> }
>
>
> /**
> * Returns the cache status.
> *
> *@return The status value
> */
> public int getStatus()
> {
> //return this.status;
> return 0;
> }
>
>
> ///////////////////////////////////////////////
> /**
> * Gets the iterator attribute of the LRUStore object
> *
> *@return The iterator value
> */
> public Iterator getIterator()
> {
> //return Collections.enumeration(map.entrySet());
> return map.entrySet().iterator();
> }
>
> /////////////////////////////////////////////////////////////////////
> // internal mehods
> /**
> * Removes the specified node from the link list.
> *
> *@param me Description of the Parameter
> */
> private void removeNode( LRUElementDescriptor me )
> {
> if ( debugR )
> {
> p( "removing node " + me.ce.getKey() );
> }
>
> if ( me.next == null )
> {
> if ( me.prev == null )
> {
> // the only node.
> first = last = null;
> }
> else
> {
> // last but not the first.
> last = me.prev;
> last.next = null;
> me.prev = null;
> }
> }
> else if ( me.prev == null )
> {
> // first but not the last.
> first = me.next;
> first.prev = null;
> me.next = null;
> }
> else
> {
> // neither the first nor the last.
> me.prev.next = me.next;
> me.next.prev = me.prev;
> me.prev = me.next = null;
> }
> }
>
>
> /**
> * Adds a new node to the end of the link list. Currently not used.
> *
> *@param ce The feature to be added to the Last attribute
> */
> private void addLast( ILRUElement ce )
> {
>
> LRUElementDescriptor me = new LRUElementDescriptor( ce );
>
> if ( first == null )
> {
> // empty list.
> first = me;
> }
> else
> {
> last.next = me;
> me.prev = last;
> }
> last = me;
> return;
> }
>
>
> /**
> * Adds a new node to the start of the link list.
> *
> *@param ce The feature to be added to the First attribute
> */
> private void addFirst( ILRUElement ce )
> {
>
> LRUElementDescriptor me = new LRUElementDescriptor( ce );
>
> if ( last == null )
> {
> // empty list.
> last = me;
> }
> else
> {
> first.prev = me;
> me.next = first;
> }
> first = me;
> return;
> }
>
>
> /**
> * Moves an existing node to the start of the link list.
> *
> *@param ce Description of the Parameter
> */
> public synchronized void makeFirst( ILRUElement ce )
> {
> makeFirst( new LRUElementDescriptor( ce ) );
> }
>
>
> /**
> * Moves an existing node to the start of the link list.
> *
> *@param me Description of the Parameter
> */
> public synchronized void makeFirst( LRUElementDescriptor me )
> {
>
> try
> {
> if ( me.prev == null )
> {
> // already the first node.
> return;
> }
> me.prev.next = me.next;
>
> if ( me.next == null )
> {
> // last but not the first.
> last = me.prev;
> last.next = null;
> }
> else
> {
> // neither the last nor the first.
> me.next.prev = me.prev;
> }
> first.prev = me;
> me.next = first;
> me.prev = null;
> first = me;
> }
> catch ( Exception e )
> {
> //log.error( e, "Couldn't make first" );
> }
> return;
> }
>
>
> /**
> * By overridding this method you can do something with the run off.
> *
> *@param obj Description of the Parameter
> */
> public void waterfall( Object obj )
> {
> // an implementation should handle this if it wants to
> }
>
>
> /**
> * Dump the cache map for debugging.
> */
> public void dumpMap()
> {
> p( "dumpingMap" );
> for ( Iterator itr = map.entrySet().iterator(); itr.hasNext(); )
> {
> //for ( Iterator itr = memCache.getIterator(); itr.hasNext();) {
> Map.Entry e = ( Map.Entry ) itr.next();
> LRUElementDescriptor me = ( LRUElementDescriptor ) e.getValue();
> p( "dumpMap> key=" + e.getKey() + ", val=" + me.ce.getVal() );
> }
> }
>
>
> /**
> * Dump the cache entries from first to list for debugging.
> */
> public void dumpEntries()
> {
> p( "dumpingEntries" );
> for ( LRUElementDescriptor me = first; me != null; me = me.next )
> {
> p( "dumpEntries> key=" + me.ce.getKey() + ", val=" + me.ce.getVal() );
> }
> }
>
>
> ///////////////////////////////////////////////////
> /**
> * Description of the Method
> *
> *@param s Description of the Parameter
> */
> public static void p( String s )
> {
> System.out.println( "LRUStore: " + s );
> }
>
>
> /**
> * The main program for the LRUStore class. For testing.
> *
> *@param args The command line arguments
> */
> public static void main( String[] args )
> {
>
> int size = 1000;
> if ( args.length > 0 )
> {
> try
> {
> size = Integer.parseInt( args[0] );
> }
> catch ( NumberFormatException e )
> {
> System.out.println( "arg 1 (size) should be a number" );
> }
> }
>
> int cycles = 2;
> if ( args.length > 1 )
> {
> try
> {
> cycles = Integer.parseInt( args[1] );
> }
> catch ( NumberFormatException e )
> {
> System.out.println( "arg 2 (cycles) should be a number" );
> }
> }
>
> LRUStore map = new LRUStore( size );
>
> boolean show = false;
> if ( args.length > 2 )
> {
> try
> {
> show = Boolean.valueOf( args[2] ).booleanValue();
> ;
> }
> catch ( Exception e )
> {
> System.out.println( "arg 3 (show) should be true or false" );
> }
> }
>
> for ( int i = 0; i < cycles; i++ )
> {
> long startP = System.currentTimeMillis();
> for ( int j = 0; j <= size; j++ )
> {
> map.put( "key" + j, "value" + j );
> }
> long endP = System.currentTimeMillis();
> long deltaP = endP - startP;
> System.out.println( "took " + deltaP + " ms. to put " + size );
>
> long startG = System.currentTimeMillis();
> for ( int j = 0; j <= size; j++ )
> {
> String val = ( String ) map.get( "key" + j );
> if ( show )
> {
> System.out.println( val );
> }
> }
> long endG = System.currentTimeMillis();
> long deltaG = endG - startG;
> System.out.println( "took " + deltaG + " ms. to get " + size );
>
> }
>
> }// end main
>
> }
> // end LRUStore
>
>
>
> 1.1
>jakarta-turbine-stratum/src/java/org/apache/stratum/util/lru/LRUElementDescriptor.java
>
> Index: LRUElementDescriptor.java
> ===================================================================
> package org.apache.stratum.util.lru;
>
> import java.io.Serializable;
>
> //////////////////////////////////////////////////////////////
> /**
> * Wraper to maintaint he double linked list
> *
> * Pulled from JCS project for ease of use.
> *
> *@author asmuts
> *@created January 31, 2002
> */
> public class LRUElementDescriptor implements Serializable
> {
>
> /**
> * needed for memory cache element LRU linked lisk
> */
> public LRUElementDescriptor prev, next;
>
> /**
> * Description of the Field
> */
> public ILRUElement ce;
>
>
> /////////////////////////////////////
> /**
> * Constructor for the LRUElementDescriptor object
> *
> *@param ce Description of the Parameter
> */
> public LRUElementDescriptor( ILRUElement ce )
> {
> this.ce = ce;
> }
>
> }
>
>
>
> 1.1
>jakarta-turbine-stratum/src/java/org/apache/stratum/util/lru/LRUElement.java
>
> Index: LRUElement.java
> ===================================================================
> package org.apache.stratum.util.lru;
>
> import java.io.Serializable;
>
> import org.apache.stratum.jcs.engine.Attributes;
>
> import org.apache.stratum.util.lru.ILRUElement;
>
> /**
> * Generic element wrapper. Often stuffed inside another.
> * Can extend and use the LRUStore put method. Can get out
> * of the LRUStore with the wrapper on as well.
> *
> * Pulled from JCS project for ease of use.
> *
> *@author asmuts
> *@created January 15, 2002
> */
> public class LRUElement implements ILRUElement, Serializable
> {
>
> /**
> * Description of the Field
> */
> public final Serializable key;
> /**
> * Description of the Field
> */
> public final Serializable val;
> /**
> * Description of the Field
> */
> public final long createTime;
>
>
> //////////////////////////////////////////////////////////////////
> /**
> * Constructor for the LRUElement object
> *
> *@param cacheName Description of the Parameter
> *@param key Description of the Parameter
> *@param val Description of the Parameter
> */
> public LRUElement(Serializable key, Serializable val )
> {
> this.key = key;
> this.val = val;
> createTime = System.currentTimeMillis();
> }
>
>
> //////////////////////////////////////////
> /**
> * Constructor for the LRUElement object
> *
> *@param cacheName Description of the Parameter
> *@param key Description of the Parameter
> *@param val Description of the Parameter
> */
> public LRUElement( Serializable key, Object val )
> {
> this( key, ( Serializable ) val );
> }
>
>
> /////////////////////////////////////
> /**
> * Gets the key attribute of the LRUElement object
> *
> *@return The key value
> */
> public Serializable getKey()
> {
> return this.key;
> }
>
>
> //////////////////////////////////////
> /**
> * Gets the val attribute of the LRUElement object
> *
> *@return The val value
> */
> public Serializable getVal()
> {
> return this.val;
> }
>
>
>
> //////////////////////////////////////
> /**
> * Gets the createTime attribute of the LRUElement object
> *
> *@return The createTime value
> */
> public long getCreateTime()
> {
> return this.createTime;
> }
>
> ///////////////////////////////////////////////////////////
> public int hashCode()
> {
> return key.hashCode();
> }
>
>
> ///////////////////////////////////////////////////
> /**
> * Description of the Method
> *
> *@return Description of the Return Value
> */
> public String toString()
> {
> return "[key=" + key + ", val=" + val + "]";
> }
>
> }
> // end class
>
>
>
>
>
> 1.1
>jakarta-turbine-stratum/src/java/org/apache/stratum/util/lru/ILRUElement.java
>
> Index: ILRUElement.java
> ===================================================================
> package org.apache.stratum.util.lru;
>
> import java.io.Serializable;
>
> /**
> * Allows the element to be overriden and customized.
> *
> * Pulled from JCS project for ease of use.
> *
> *@author asmuts
> *@created January 15, 2002
> */
> public interface ILRUElement extends Serializable
> {
> /**
> * Gets the key attribute of the ILRUElement object
> *
> *@return The key value
> */
> public Serializable getKey();
>
>
> /**
> * Gets the val attribute of the ILRUElement object
> *
> *@return The val value
> */
> public Serializable getVal();
>
>
> /**
> * Gets the createTime attribute of the ILRUElement object
> *
> *@return The createTime value
> */
> public long getCreateTime();
>
> }
>
>
>
>
> --
> To unsubscribe, e-mail: <mailto:[EMAIL PROTECTED]>
> For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>
--
To unsubscribe, e-mail: <mailto:[EMAIL PROTECTED]>
For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>
