You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@turbine.apache.org by Daniel Rall <dl...@finemaltcoding.com> on 2002/02/07 04:14:22 UTC
Re: cvs commit: jakarta-turbine-stratum/src/java/org/apache/stratum/util/lru LRUStore.java LRUElementDescriptor.java LRUElement.java ILRUElement.java (1/2)
Start submitting your utilities and I'm sure they'll hook you up with
commit eventually. I do not have commit to the Commons, but every
Jakarta commiter has a right to commit access to the Commons Sandbox
(where Commons Util currently resides). Send mail to root@apache.org
and request commit to the Commons Sandbox. Your utilities are best
placed in either Util (which you'll have commit to), or Collections.
Dan
"Aaron Smuts" <aa...@verizon.net> writes:
> Can I get commit access to commons? I have lots of utilities that might
> be better off there.
>
> Aaron
>
>> -----Original Message-----
>> From: dlr@despot.finemaltcoding.com
> [mailto:dlr@despot.finemaltcoding.com]
> > On Behalf Of Daniel Rall
>> Sent: Wednesday, February 06, 2002 12:40 PM
>> To: Turbine Developers List
>> Subject: Re: cvs commit: jakarta-turbine-
>> stratum/src/java/org/apache/stratum/util/lru LRUStore.java
>> LRUElementDescriptor.java LRUElement.java ILRUElement.java
>>
>> 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
>>
>> asmuts@apache.org 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
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>