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 > > * > > *@return The createTime value > > */ > > public long getCreateTime(); > > > > } > > > > > > > > > > -- > > To unsubscribe, e-mail: <mailto:turbine-dev- > [EMAIL PROTECTED]> > > For additional commands, e-mail: <mailto:turbine-dev- > [EMAIL PROTECTED]> > > -- > To unsubscribe, e-mail: <mailto:turbine-dev- > [EMAIL PROTECTED]> > For additional commands, e-mail: <mailto:turbine-dev- > [EMAIL PROTECTED]> -- To unsubscribe, e-mail: <mailto:[EMAIL PROTECTED]> For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>
