You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Daniel Rall <dl...@finemaltcoding.com> on 2002/02/21 04:04:34 UTC
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)
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>