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