You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@turbine.apache.org by as...@apache.org on 2002/02/01 04:55:54 UTC
cvs commit: jakarta-turbine-stratum/src/java/org/apache/stratum/util/lru LRUStore.java LRUElementDescriptor.java LRUElement.java ILRUElement.java
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: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
Re: cvs commit: jakarta-turbine-stratum/src/java/org/apache/stratum/util/lru LRUStore.java LRUElementDescriptor.java LRUElement.java ILRUElement.java (1/2)
Posted by Daniel Rall <dl...@finemaltcoding.com>.
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>
Re: cvs commit: jakarta-turbine-stratum/src/java/org/apache/stratum/util/lru LRUStore.java LRUElementDescriptor.java LRUElement.java ILRUElement.java (2/2)
Posted by Daniel Rall <dl...@finemaltcoding.com>.
>> > *
>> > *@return The createTime value
>> > */
>> > public long getCreateTime();
>> >
>> > }
>> >
>> >
>> >
>> >
>> > --
>> > To unsubscribe, e-mail: <mailto:turbine-dev-
>> unsubscribe@jakarta.apache.org>
>> > For additional commands, e-mail: <mailto:turbine-dev-
>> help@jakarta.apache.org>
>>
>> --
>> To unsubscribe, e-mail: <mailto:turbine-dev-
>> unsubscribe@jakarta.apache.org>
>> For additional commands, e-mail: <mailto:turbine-dev-
>> help@jakarta.apache.org>
>
>
> --
> To unsubscribe, e-mail: <ma...@jakarta.apache.org>
> For additional commands, e-mail: <ma...@jakarta.apache.org>
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
RE: cvs commit: jakarta-turbine-stratum/src/java/org/apache/stratum/util/lru LRUStore.java LRUElementDescriptor.java LRUElement.java ILRUElement.java
Posted by Aaron Smuts <aa...@verizon.net>.
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
> > *
> > *@return The createTime value
> > */
> > public long getCreateTime();
> >
> > }
> >
> >
> >
> >
> > --
> > To unsubscribe, e-mail: <mailto:turbine-dev-
> unsubscribe@jakarta.apache.org>
> > For additional commands, e-mail: <mailto:turbine-dev-
> help@jakarta.apache.org>
>
> --
> To unsubscribe, e-mail: <mailto:turbine-dev-
> unsubscribe@jakarta.apache.org>
> For additional commands, e-mail: <mailto:turbine-dev-
> help@jakarta.apache.org>
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
Re: cvs commit: jakarta-turbine-stratum/src/java/org/apache/stratum/util/lru LRUStore.java LRUElementDescriptor.java LRUElement.java ILRUElement.java
Posted by Daniel Rall <dl...@finemaltcoding.com>.
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
> *
> *@return The createTime value
> */
> public long getCreateTime();
>
> }
>
>
>
>
> --
> To unsubscribe, e-mail: <ma...@jakarta.apache.org>
> For additional commands, e-mail: <ma...@jakarta.apache.org>
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>