home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: Java / Java.zip / jload18.zip / LruHashtable.java < prev    next >
Text File  |  1999-01-22  |  10KB  |  302 lines
  1. // LruHashtable - a Hashtable that expires least-recently-used objects
  2. //
  3. // Copyright (C) 1996 by Jef Poskanzer <jef@acme.com>.  All rights reserved.
  4. //
  5. // Redistribution and use in source and binary forms, with or without
  6. // modification, are permitted provided that the following conditions
  7. // are met:
  8. // 1. Redistributions of source code must retain the above copyright
  9. //    notice, this list of conditions and the following disclaimer.
  10. // 2. Redistributions in binary form must reproduce the above copyright
  11. //    notice, this list of conditions and the following disclaimer in the
  12. //    documentation and/or other materials provided with the distribution.
  13. //
  14. // THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  15. // ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  16. // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  17. // ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  18. // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  19. // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  20. // OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  21. // HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  22. // LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  23. // OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  24. // SUCH DAMAGE.
  25. //
  26. // Visit the ACME Labs Java page for up-to-date versions of this and other
  27. // fine Java utilities: http://www.acme.com/java/
  28.  
  29. import java.util.*;
  30.  
  31. /// A Hashtable that expires least-recently-used objects.
  32. // <P>
  33. // Use just like java.util.Hashtable, except that the initial-capacity
  34. // parameter is required.  Instead of growing bigger than that size,
  35. // it will throw out objects that haven't been looked at in a while.
  36. // <P>
  37. // <A HREF="/resources/classes/Acme/LruHashtable.java">Fetch the software.</A><BR>
  38. // <A HREF="/resources/classes/Acme.tar.Z">Fetch the entire Acme package.</A>
  39. // <P>
  40. // @see java.util.Hashtable
  41.  
  42. public class LruHashtable extends Hashtable
  43.     {
  44.  
  45.     // Number of buckets.
  46.     private static final int nBuckets = 2;
  47.  
  48.     // Load factor.
  49.     private float loadFactor;
  50.  
  51.     // When count exceeds this threshold, expires the old table.
  52.     private int threshold;
  53.  
  54.     // Capacity of each bucket.
  55.     private int eachCapacity;
  56.  
  57.     // The tables.
  58.     private Hashtable oldTable;
  59.     private Hashtable newTable;
  60.  
  61.     /// Constructs a new, empty hashtable with the specified initial 
  62.     // capacity and the specified load factor.
  63.     // Unlike a plain Hashtable, an LruHashtable will never grow or
  64.     // shrink from this initial capacity.
  65.     // @param initialCapacity the initial number of buckets
  66.     // @param loadFactor a number between 0.0 and 1.0, it defines
  67.     //        the threshold for expiring old entries
  68.     // @exception IllegalArgumentException If the initial capacity
  69.     // is less than or equal to zero.
  70.     // @exception IllegalArgumentException If the load factor is
  71.     // less than or equal to zero.
  72.     public LruHashtable( int initialCapacity, float loadFactor )
  73.     {
  74.     // We have to call a superclass constructor, but we're not actually
  75.     // going to use it at all.  The only reason we want to extend Hashtable
  76.     // is for type conformance.  So, make a parent hash table of minimum
  77.     // size and then ignore it.
  78.     super( 1 );
  79.  
  80.     if ( initialCapacity <= 0 || loadFactor <= 0.0 )
  81.         throw new IllegalArgumentException();
  82.     this.loadFactor = loadFactor;
  83.     threshold = (int) ( initialCapacity * loadFactor ) - 1;
  84.     eachCapacity = initialCapacity / nBuckets + 1;
  85.     oldTable = new Hashtable( eachCapacity, loadFactor );
  86.     newTable = new Hashtable( eachCapacity, loadFactor );
  87.     }
  88.  
  89.     /// Constructs a new, empty hashtable with the specified initial 
  90.     // capacity.
  91.     // Unlike a plain Hashtable, an LruHashtable will never grow or
  92.     // shrink from this initial capacity.
  93.     // @param initialCapacity the initial number of buckets
  94.     public LruHashtable( int initialCapacity )
  95.     {
  96.     this( initialCapacity, 0.75F );
  97.     }
  98.  
  99.     /// Returns the number of elements contained in the hashtable. 
  100.     public int size()
  101.     {
  102.     return newTable.size() + oldTable.size();
  103.     }
  104.  
  105.     /// Returns true if the hashtable contains no elements.
  106.     public boolean isEmpty()
  107.     {
  108.     return size() == 0;
  109.     }
  110.  
  111.     /// Returns an enumeration of the hashtable's keys.
  112.     // @see LruHashtable#elements
  113.     // @see Enumeration
  114.     public synchronized Enumeration keys()
  115.     {
  116.     return new LruHashtableEnumerator( oldTable, newTable, true );
  117.     }
  118.  
  119.     /// Returns an enumeration of the elements. Use the Enumeration methods 
  120.     // on the returned object to fetch the elements sequentially.
  121.     // @see LruHashtable#keys
  122.     // @see Enumeration
  123.     public synchronized Enumeration elements()
  124.     {
  125.     return new LruHashtableEnumerator( oldTable, newTable, false );
  126.     }
  127.  
  128.     /// Returns true if the specified object is an element of the hashtable.
  129.     // This operation is more expensive than the containsKey() method.
  130.     // @param value the value that we are looking for
  131.     // @exception NullPointerException If the value being searched 
  132.     // for is equal to null.
  133.     // @see LruHashtable#containsKey
  134.     public synchronized boolean contains( Object value )
  135.     {
  136.     if ( newTable.contains( value ) )
  137.         return true;
  138.     if ( oldTable.contains( value ) )
  139.         {
  140.         // We would like to move the object from the old table to the
  141.         // new table.  However, we need keys to re-add the objects, and
  142.         // there's no good way to find all the keys for the given object.
  143.         // We'd have to enumerate through all the keys and check each
  144.         // one.  Yuck.  For now we just punt.  Anyway, contains() is
  145.         // probably not a commonly-used operation.
  146.         return true;
  147.         }
  148.     return false;
  149.     }
  150.  
  151.     /// Returns true if the collection contains an element for the key.
  152.     // @param key the key that we are looking for
  153.     // @see LruHashtable#contains
  154.     public synchronized boolean containsKey( Object key )
  155.     {
  156.     if ( newTable.containsKey( key ) )
  157.         return true;
  158.     if ( oldTable.containsKey( key ) )
  159.         {
  160.         // Move object from old table to new table.
  161.         Object value = oldTable.get( key );
  162.         newTable.put( key, value );
  163.         oldTable.remove( key );
  164.         return true;
  165.         }
  166.     return false;
  167.     }
  168.  
  169.     /// Gets the object associated with the specified key in the 
  170.     // hashtable.
  171.     // @param key the specified key
  172.     // @returns the element for the key or null if the key
  173.     //         is not defined in the hash table.
  174.     // @see LruHashtable#put
  175.     public synchronized Object get( Object key )
  176.     {
  177.     Object value;
  178.     value = newTable.get( key );
  179.     if ( value != null )
  180.         return value;
  181.     value = oldTable.get( key );
  182.     if ( value != null )
  183.         {
  184.         // Move object from old table to new table.
  185.         newTable.put( key, value );
  186.         oldTable.remove( key );
  187.         return value;
  188.         }
  189.     return null;
  190.     }
  191.  
  192.     /// Puts the specified element into the hashtable, using the specified
  193.     // key.  The element may be retrieved by doing a get() with the same key.
  194.     // The key and the element cannot be null. 
  195.     // @param key the specified key in the hashtable
  196.     // @param value the specified element
  197.     // @exception NullPointerException If the value of the element 
  198.     // is equal to null.
  199.     // @see LruHashtable#get
  200.     // @return the old value of the key, or null if it did not have one.
  201.     public synchronized Object put( Object key, Object value )
  202.     {
  203.     Object oldValue = newTable.put( key, value );
  204.     if ( oldValue != null )
  205.         return oldValue;
  206.     oldValue = oldTable.get( key );
  207.     if ( oldValue != null )
  208.         oldTable.remove( key );
  209.     else
  210.         {
  211.         if ( size() >= threshold )
  212.         {
  213.         // Rotate the tables.
  214.         oldTable = newTable;
  215.         newTable = new Hashtable( eachCapacity, loadFactor );
  216.         } 
  217.         }
  218.     return oldValue;
  219.     }
  220.  
  221.     /// Removes the element corresponding to the key. Does nothing if the
  222.     // key is not present.
  223.     // @param key the key that needs to be removed
  224.     // @return the value of key, or null if the key was not found.
  225.     public synchronized Object remove( Object key )
  226.     {
  227.     Object oldValue = newTable.remove( key );
  228.     if ( oldValue == null )
  229.         oldValue = oldTable.remove( key );
  230.     return oldValue;
  231.     }
  232.  
  233.     /// Clears the hash table so that it has no more elements in it.
  234.     public synchronized void clear()
  235.     {
  236.     newTable.clear();
  237.     oldTable.clear();
  238.     }
  239.  
  240.     /// Creates a clone of the hashtable. A shallow copy is made,
  241.     // the keys and elements themselves are NOT cloned. This is a
  242.     // relatively expensive operation.
  243.     public synchronized Object clone()
  244.     {
  245.     LruHashtable n = (LruHashtable) super.clone();
  246.     n.newTable = (Hashtable) n.newTable.clone();
  247.     n.oldTable = (Hashtable) n.oldTable.clone();
  248.     return n;
  249.     }
  250.  
  251.     // toString() can be inherited.
  252.  
  253.     }
  254.  
  255.  
  256. class LruHashtableEnumerator implements Enumeration
  257.     {
  258.     Enumeration oldEnum;
  259.     Enumeration newEnum;
  260.     boolean old;
  261.  
  262.     LruHashtableEnumerator( Hashtable oldTable, Hashtable newTable, boolean keys )
  263.     {
  264.     if ( keys )
  265.         {
  266.         oldEnum = oldTable.keys();
  267.         newEnum = newTable.keys();
  268.         }
  269.     else
  270.         {
  271.         oldEnum = oldTable.elements();
  272.         newEnum = newTable.elements();
  273.         }
  274.     old = true;
  275.     }
  276.     
  277.     public boolean hasMoreElements()
  278.     {
  279.     boolean r;
  280.     if ( old )
  281.         {
  282.         r = oldEnum.hasMoreElements();
  283.         if ( ! r )
  284.         {
  285.         old = false;
  286.         r = newEnum.hasMoreElements();
  287.         }
  288.         }
  289.     else
  290.         r = newEnum.hasMoreElements();
  291.     return r;
  292.     }
  293.  
  294.     public Object nextElement()
  295.     {
  296.     if ( old )
  297.         return oldEnum.nextElement();
  298.     return newEnum.nextElement();
  299.     }
  300.             
  301.     }
  302.