commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From asm...@apache.org
Subject cvs commit: jakarta-commons-sandbox/util/src/java/org/apache/commons/util/lru LRUStoreImp.java LRUStore.java LRUElementDescriptor.java LRUElement.java ILRUElement.java
Date Sat, 16 Feb 2002 23:12:34 GMT
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:   <mailto:commons-dev-unsubscribe@jakarta.apache.org>
For additional commands, e-mail: <mailto:commons-dev-help@jakarta.apache.org>


Mime
View raw message