You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by as...@apache.org on 2002/02/17 00:12:34 UTC
cvs commit: jakarta-commons-sandbox/util/src/java/org/apache/commons/util/lru LRUStoreImp.java LRUStore.java LRUElementDescriptor.java LRUElement.java ILRUElement.java
asmuts 02/02/16 15:12:34
Added: util/src/java/org/apache/commons/util/lru LRUStoreImp.java
LRUStore.java LRUElementDescriptor.java
LRUElement.java ILRUElement.java
Log:
Added LRUStore. Should change to a map implementation later. Created sample implementation with a main testing method.
The create time recording in the LRUElement should be removed. A create element method should be created, so implementation can have their own element wrapper if they want. Every ILRUElement creation should be done via this one method of teh LRUStore.
Revision Changes Path
1.1 jakarta-commons-sandbox/util/src/java/org/apache/commons/util/lru/LRUStoreImp.java
Index: LRUStoreImp.java
===================================================================
package org.apache.commons.util.lru;
/*
* ====================================================================
* The Apache Software License, Version 1.1
*
* Copyright (c) 2001 The Apache Software Foundation. All rights
* reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
*
* 3. The end-user documentation included with the redistribution,
* if any, must include the following acknowledgment:
* "This product includes software developed by the
* Apache Software Foundation (http://www.apache.org/)."
* Alternately, this acknowledgment may appear in the software itself,
* if and wherever such third-party acknowledgments normally appear.
*
* 4. The names "Apache" and "Apache Software Foundation" and
* "Apache Commons" must not be used to endorse or promote products
* derived from this software without prior written permission. For
* written permission, please contact apache@apache.org.
*
* 5. Products derived from this software may not be called "Apache",
* "Apache Turbine", nor may "Apache" appear in their name, without
* prior written permission of the Apache Software Foundation.
*
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
* ====================================================================
*
* This software consists of voluntary contributions made by many
* individuals on behalf of the Apache Software Foundation. For more
* information on the Apache Software Foundation, please see
* <http://www.apache.org/>.
*/
/**
* Example implementation of LRUStore. Overrides the waterfall method.
*
*@author <a href="mailto:asmuts@yahoo.com">Aaron Smuts</a>
*@created February 16, 2002
*/
public class LRUStoreImp extends LRUStore
{
int numWaterfalled = 0;
/**
* Constructor for the LRUStoreImp object
*/
public LRUStoreImp()
{
super();
}
/**
* Constructor for the LRUStoreImp object
*
*@param max Description of the Parameter
*/
public LRUStoreImp( int max )
{
super( max );
}
/**
* Description of the Method
*
*@param obj Description of the Parameter
*/
public void waterfall( Object obj )
{
numWaterfalled++;
// example
System.out.println( numWaterfalled + " -- They are killing me! [" + obj.toString() + "]" );
System.out.println( "The LRUStore said that I was the least recently used item." );
System.out.println( "Put me on disk if you still want me." );
}
/**
* A junk test method for the sample LRUStoreImp. Puts 10 more than the
* specified size. If you have more than 1 cycle and there are any over,
* since the loop in this method start fromt he beginning to end, all puts
* int he subsequent cycles will cause waterfalling.
*
*@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" );
}
}
int over = 0;
if ( args.length > 2 )
{
try
{
over = Integer.parseInt( args[2] );
}
catch ( NumberFormatException e )
{
System.out.println( "arg 3 (number to put over the size) should be a number" );
}
}
boolean dump = false;
if ( args.length > 3 )
{
try
{
dump = Boolean.valueOf( args[3] ).booleanValue();
}
catch ( NumberFormatException e )
{
System.out.println( "arg 3 (dump) should be a boolean" );
}
}
System.out.println( "Size = " + size );
System.out.println( "cycles = " + cycles );
System.out.println( "over = " + over );
LRUStoreImp map = new LRUStoreImp( 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 + over; j++ )
{
map.put( "key" + j, "value" + j );
}
long endP = System.currentTimeMillis();
long deltaP = endP - startP;
System.out.println( "took " + deltaP + " ms. to put " + String.valueOf( size + over ) );
System.out.println( "\n" );
long startG = System.currentTimeMillis();
for ( int j = 0; j < size + over; 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 " + String.valueOf( size + over ) );
System.out.println( "\n" );
}
System.out.println( "Size = " + size );
System.out.println( "cycles = " + cycles );
System.out.println( "over = " + over );
System.out.println( "\n" );
if ( dump )
{
map.dumpMap();
System.out.println( "\n" );
map.dumpEntries();
}
}// end main
}
1.1 jakarta-commons-sandbox/util/src/java/org/apache/commons/util/lru/LRUStore.java
Index: LRUStore.java
===================================================================
package org.apache.commons.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.commons.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. Will change
* into a map interface later. The LRUMemoryCache in JCS will eventually be
* a wrapper around this.
*
*@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 = 1;
////////////////////////////////////////////////////////////////////
// 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 chunkSize 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 last 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() );
}
}
///////////////////////////////////////////////////
/**
* Convenience method.
*
*@param s Description of the Parameter
*/
public static void p( String s )
{
System.out.println( "LRUStore: " + s );
}
}
// end LRUStore
1.1 jakarta-commons-sandbox/util/src/java/org/apache/commons/util/lru/LRUElementDescriptor.java
Index: LRUElementDescriptor.java
===================================================================
package org.apache.commons.util.lru;
import java.io.Serializable;
//////////////////////////////////////////////////////////////
/**
* Wraper to maintain the 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-commons-sandbox/util/src/java/org/apache/commons/util/lru/LRUElement.java
Index: LRUElement.java
===================================================================
package org.apache.commons.util.lru;
import java.io.Serializable;
import org.apache.commons.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 key Description of the Parameter
*@param val Description of the Parameter
*/
public LRUElement( Serializable key, Serializable val )
{
this.key = key;
this.val = val;
// may want to disable this.
createTime = System.currentTimeMillis();
}
//////////////////////////////////////////
/**
* Constructor for the LRUElement object
*
*@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;
}
///////////////////////////////////////////////////////////
/**
* Description of the Method
*
*@return Description of the Return Value
*/
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-commons-sandbox/util/src/java/org/apache/commons/util/lru/ILRUElement.java
Index: ILRUElement.java
===================================================================
package org.apache.commons.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-commons-sandbox/util/src/java/org/apache/commons/util/lru LRUStoreImp.java LRUStore.java LRUElementDescriptor.java LRUElement.java ILRUElement.java (2/2)
Posted by Daniel Rall <dl...@finemaltcoding.com>.
> ///////////////////////////////////////////////////////////
> /**
> * Description of the Method
> *
> *@return Description of the Return Value
> */
> 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-commons-sandbox/util/src/java/org/apache/commons/util/lru/ILRUElement.java
>
> Index: ILRUElement.java
> ===================================================================
> package org.apache.commons.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>
Re: cvs commit: jakarta-commons-sandbox/util/src/java/org/apache/commons/util/lru LRUStoreImp.java LRUStore.java LRUElementDescriptor.java LRUElement.java ILRUElement.java (1/2)
Posted by Daniel Rall <dl...@finemaltcoding.com>.
Can this be merged with the existing LRUMap in Collections? I haven't
looked at this one yet, but Aaron gave some good numbers on it on
turbine-dev. Michael's implementation of SequencedHashMap may be
similar (not sure) -- I believe that both claim O(1) (which is great
guys!).
Dan
asmuts@apache.org writes:
> asmuts 02/02/16 15:12:34
>
> Added: util/src/java/org/apache/commons/util/lru LRUStoreImp.java
> LRUStore.java LRUElementDescriptor.java
> LRUElement.java ILRUElement.java
> Log:
> Added LRUStore. Should change to a map implementation later. Created sample implementation with a main testing method.
>
> The create time recording in the LRUElement should be removed. A create element method should be created, so implementation can have their own element wrapper if they want. Every ILRUElement creation should be done via this one method of teh LRUStore.
>
> Revision Changes Path
> 1.1 jakarta-commons-sandbox/util/src/java/org/apache/commons/util/lru/LRUStoreImp.java
>
> Index: LRUStoreImp.java
> ===================================================================
> package org.apache.commons.util.lru;
>
> /*
> * ====================================================================
> * The Apache Software License, Version 1.1
> *
> * Copyright (c) 2001 The Apache Software Foundation. All rights
> * reserved.
> *
> * Redistribution and use in source and binary forms, with or without
> * modification, are permitted provided that the following conditions
> * are met:
> *
> * 1. Redistributions of source code must retain the above copyright
> * notice, this list of conditions and the following disclaimer.
> *
> * 2. Redistributions in binary form must reproduce the above copyright
> * notice, this list of conditions and the following disclaimer in
> * the documentation and/or other materials provided with the
> * distribution.
> *
> * 3. The end-user documentation included with the redistribution,
> * if any, must include the following acknowledgment:
> * "This product includes software developed by the
> * Apache Software Foundation (http://www.apache.org/)."
> * Alternately, this acknowledgment may appear in the software itself,
> * if and wherever such third-party acknowledgments normally appear.
> *
> * 4. The names "Apache" and "Apache Software Foundation" and
> * "Apache Commons" must not be used to endorse or promote products
> * derived from this software without prior written permission. For
> * written permission, please contact apache@apache.org.
> *
> * 5. Products derived from this software may not be called "Apache",
> * "Apache Turbine", nor may "Apache" appear in their name, without
> * prior written permission of the Apache Software Foundation.
> *
> * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
> * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
> * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
> * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
> * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
> * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
> * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
> * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
> * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
> * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
> * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
> * SUCH DAMAGE.
> * ====================================================================
> *
> * This software consists of voluntary contributions made by many
> * individuals on behalf of the Apache Software Foundation. For more
> * information on the Apache Software Foundation, please see
> * <http://www.apache.org/>.
> */
>
> /**
> * Example implementation of LRUStore. Overrides the waterfall method.
> *
> *@author <a href="mailto:asmuts@yahoo.com">Aaron Smuts</a>
> *@created February 16, 2002
> */
> public class LRUStoreImp extends LRUStore
> {
>
> int numWaterfalled = 0;
>
> /**
> * Constructor for the LRUStoreImp object
> */
> public LRUStoreImp()
> {
> super();
> }
>
> /**
> * Constructor for the LRUStoreImp object
> *
> *@param max Description of the Parameter
> */
> public LRUStoreImp( int max )
> {
> super( max );
> }
>
> /**
> * Description of the Method
> *
> *@param obj Description of the Parameter
> */
> public void waterfall( Object obj )
> {
> numWaterfalled++;
> // example
> System.out.println( numWaterfalled + " -- They are killing me! [" + obj.toString() + "]" );
> System.out.println( "The LRUStore said that I was the least recently used item." );
> System.out.println( "Put me on disk if you still want me." );
>
> }
>
>
> /**
> * A junk test method for the sample LRUStoreImp. Puts 10 more than the
> * specified size. If you have more than 1 cycle and there are any over,
> * since the loop in this method start fromt he beginning to end, all puts
> * int he subsequent cycles will cause waterfalling.
> *
> *@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" );
> }
> }
>
> int over = 0;
> if ( args.length > 2 )
> {
> try
> {
> over = Integer.parseInt( args[2] );
> }
> catch ( NumberFormatException e )
> {
> System.out.println( "arg 3 (number to put over the size) should be a number" );
> }
> }
>
> boolean dump = false;
> if ( args.length > 3 )
> {
> try
> {
> dump = Boolean.valueOf( args[3] ).booleanValue();
> }
> catch ( NumberFormatException e )
> {
> System.out.println( "arg 3 (dump) should be a boolean" );
> }
> }
>
> System.out.println( "Size = " + size );
> System.out.println( "cycles = " + cycles );
> System.out.println( "over = " + over );
>
> LRUStoreImp map = new LRUStoreImp( 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 + over; j++ )
> {
> map.put( "key" + j, "value" + j );
> }
> long endP = System.currentTimeMillis();
> long deltaP = endP - startP;
> System.out.println( "took " + deltaP + " ms. to put " + String.valueOf( size + over ) );
>
> System.out.println( "\n" );
>
> long startG = System.currentTimeMillis();
> for ( int j = 0; j < size + over; 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 " + String.valueOf( size + over ) );
>
> System.out.println( "\n" );
>
> }
>
> System.out.println( "Size = " + size );
> System.out.println( "cycles = " + cycles );
> System.out.println( "over = " + over );
>
> System.out.println( "\n" );
>
> if ( dump )
> {
> map.dumpMap();
>
> System.out.println( "\n" );
>
> map.dumpEntries();
> }
>
> }// end main
>
> }
>
>
>
> 1.1 jakarta-commons-sandbox/util/src/java/org/apache/commons/util/lru/LRUStore.java
>
> Index: LRUStore.java
> ===================================================================
> package org.apache.commons.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.commons.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. Will change
> * into a map interface later. The LRUMemoryCache in JCS will eventually be
> * a wrapper around this.
> *
> *@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 = 1;
>
>
> ////////////////////////////////////////////////////////////////////
> // 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 chunkSize 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 last 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() );
> }
> }
>
>
> ///////////////////////////////////////////////////
> /**
> * Convenience method.
> *
> *@param s Description of the Parameter
> */
> public static void p( String s )
> {
> System.out.println( "LRUStore: " + s );
> }
>
> }
> // end LRUStore
>
>
>
> 1.1 jakarta-commons-sandbox/util/src/java/org/apache/commons/util/lru/LRUElementDescriptor.java
>
> Index: LRUElementDescriptor.java
> ===================================================================
> package org.apache.commons.util.lru;
>
> import java.io.Serializable;
>
> //////////////////////////////////////////////////////////////
> /**
> * Wraper to maintain the 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-commons-sandbox/util/src/java/org/apache/commons/util/lru/LRUElement.java
>
> Index: LRUElement.java
> ===================================================================
> package org.apache.commons.util.lru;
>
> import java.io.Serializable;
>
> import org.apache.commons.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 key Description of the Parameter
> *@param val Description of the Parameter
> */
> public LRUElement( Serializable key, Serializable val )
> {
> this.key = key;
> this.val = val;
> // may want to disable this.
> createTime = System.currentTimeMillis();
> }
>
>
> //////////////////////////////////////////
> /**
> * Constructor for the LRUElement object
> *
> *@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;
> }
>
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>