X-Draft-From: ("nnml+mail:apache.commons" 6745)
To: "Jakarta Commons Developers List" <[EMAIL PROTECTED]>
Subject: Re: cvs commit: jakarta-commons-sandbox/util/src/java/org/apache/commons/util/lru LRUStoreImp.java LRUStore.java LRUElementDescriptor.java LRUElement.java ILRUElement.java
References: <[EMAIL PROTECTED]>
Gcc: nnfolder+archive:mail.sent
Mime-Version: 1.0 (generated by tm-edit 1.7)
Content-Type: text/plain; charset=US-ASCIICan 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 [EMAIL PROTECTED] 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 [EMAIL PROTECTED] > * > * 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:[EMAIL PROTECTED]";>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: <mailto:[EMAIL PROTECTED]> For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>
