LruHashtable


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  //
30  // moved to the net.matuschek.util package by Daniel Matuschek
31  //
32  
33  package net.matuschek.util;
34  
35  import java.util.Enumeration  ;
36  import java.util.Hashtable  ;
37  
38  /** 
39   * A Hashtable that expires least-recently-used objects.
40   * 
41   * <p>Use just like java.util.Hashtable, except that the initial-capacity
42   * parameter is required.  Instead of growing bigger than that size,
43   * it will throw out objects that haven't been looked at in a while.
44   * </p>
45   *
46   * @author Jef Poskanzer
47   * @author Daniel Matuschek
48   * @version $Id: LruHashtable.java,v 1.3 2002/05/31 14:45:56 matuschd Exp $
49   *
50   * @see java.util.Hashtable
51   */
52  
53  public class LruHashtable extends Hashtable  
54  {
55    
56    // Number of buckets.
57    private static final int nBuckets = 2;
58    
59    // Load factor.
60    private float loadFactor;
61    
62    // When count exceeds this threshold, expires the old table.
63    private int threshold;
64    
65    // Capacity of each bucket.
66    private int eachCapacity;
67    
68    // The tables.
69    private Hashtable   oldTable;
70    private Hashtable   newTable;
71    
72    /// Constructs a new, empty hashtable with the specified initial 
73    // capacity and the specified load factor.
74    // Unlike a plain Hashtable, an LruHashtable will never grow or
75    // shrink from this initial capacity.
76    // @param initialCapacity the initial number of buckets
77    // @param loadFactor a number between 0.0 and 1.0, it defines
78    //        the threshold for expiring old entries
79    // @exception IllegalArgumentException If the initial capacity
80    // is less than or equal to zero.
81    // @exception IllegalArgumentException If the load factor is
82    // less than or equal to zero.
83    public LruHashtable( int initialCapacity, float loadFactor )
84    {
85      // We have to call a superclass constructor, but we're not actually
86      // going to use it at all.  The only reason we want to extend Hashtable
87      // is for type conformance.  So, make a parent hash table of minimum
88      // size and then ignore it.
89      super( 1 );
90      
91      if ( initialCapacity <= 0 || loadFactor <= 0.0 )
92        throw new IllegalArgumentException  ();
93      this.loadFactor = loadFactor;
94      threshold = (int) ( initialCapacity * loadFactor ) - 1;
95      eachCapacity = initialCapacity / nBuckets + 1;
96      oldTable = new Hashtable  ( eachCapacity, loadFactor );
97      newTable = new Hashtable  ( eachCapacity, loadFactor );
98    }
99    
100   /// Constructs a new, empty hashtable with the specified initial 
101   // capacity.
102   // Unlike a plain Hashtable, an LruHashtable will never grow or
103   // shrink from this initial capacity.
104   // @param initialCapacity the initial number of buckets
105   public LruHashtable( int initialCapacity )
106   {
107     this( initialCapacity, 0.75F );
108   }
109   
110   /// Returns the number of elements contained in the hashtable. 
111   public int size()
112   {
113     return newTable.size() + oldTable.size();
114   }
115   
116   /// Returns true if the hashtable contains no elements.
117   public boolean isEmpty()
118   {
119     return size() == 0;
120   }
121   
122   /// Returns an enumeration of the hashtable's keys.
123   // @see LruHashtable#elements
124   // @see Enumeration
125   public synchronized Enumeration   keys()
126   {
127     return new LruHashtableEnumerator( oldTable, newTable, true );
128   }
129   
130   /// Returns an enumeration of the elements. Use the Enumeration methods 
131   // on the returned object to fetch the elements sequentially.
132   // @see LruHashtable#keys
133   // @see Enumeration
134   public synchronized Enumeration   elements()
135   {
136     return new LruHashtableEnumerator( oldTable, newTable, false );
137   }
138   
139   /// Returns true if the specified object is an element of the hashtable.
140   // This operation is more expensive than the containsKey() method.
141   // @param value the value that we are looking for
142   // @exception NullPointerException If the value being searched 
143   // for is equal to null.
144   // @see LruHashtable#containsKey
145   public synchronized boolean contains( Object   value )
146   {
147     if ( newTable.contains( value ) )
148       return true;
149     if ( oldTable.contains( value ) )
150       {
151     // We would like to move the object from the old table to the
152     // new table.  However, we need keys to re-add the objects, and
153     // there's no good way to find all the keys for the given object.
154     // We'd have to enumerate through all the keys and check each
155     // one.  Yuck.  For now we just punt.  Anyway, contains() is
156     // probably not a commonly-used operation.
157     return true;
158       }
159     return false;
160   }
161   
162   /// Returns true if the collection contains an element for the key.
163   // @param key the key that we are looking for
164   // @see LruHashtable#contains
165   public synchronized boolean containsKey( Object   key )
166   {
167     if ( newTable.containsKey( key ) )
168       return true;
169     if ( oldTable.containsKey( key ) )
170       {
171     // Move object from old table to new table.
172     Object   value = oldTable.get( key );
173     newTable.put( key, value );
174     oldTable.remove( key );
175     return true;
176       }
177     return false;
178   }
179   
180   /// Gets the object associated with the specified key in the 
181   // hashtable.
182   // @param key the specified key
183   // @returns the element for the key or null if the key
184   //        is not defined in the hash table.
185   // @see LruHashtable#put
186   public synchronized Object   get( Object   key )
187   {
188     Object   value;
189     value = newTable.get( key );
190     if ( value != null )
191       return value;
192     value = oldTable.get( key );
193     if ( value != null )
194       {
195     // Move object from old table to new table.
196     newTable.put( key, value );
197     oldTable.remove( key );
198     return value;
199       }
200     return null;
201   }
202   
203   /// Puts the specified element into the hashtable, using the specified
204   // key.  The element may be retrieved by doing a get() with the same key.
205   // The key and the element cannot be null. 
206   // @param key the specified key in the hashtable
207   // @param value the specified element
208   // @exception NullPointerException If the value of the element 
209   // is equal to null.
210   // @see LruHashtable#get
211   // @return the old value of the key, or null if it did not have one.
212   public synchronized Object   put( Object   key, Object   value )
213   {
214     Object   oldValue = newTable.put( key, value );
215     if ( oldValue != null )
216       return oldValue;
217     oldValue = oldTable.get( key );
218     if ( oldValue != null )
219       oldTable.remove( key );
220     else
221       {
222     if ( size() >= threshold )
223       {
224         // Rotate the tables.
225         oldTable = newTable;
226         newTable = new Hashtable  ( eachCapacity, loadFactor );
227       } 
228       }
229     return oldValue;
230   }
231   
232   /// Removes the element corresponding to the key. Does nothing if the
233   // key is not present.
234   // @param key the key that needs to be removed
235   // @return the value of key, or null if the key was not found.
236   public synchronized Object   remove( Object   key )
237   {
238     Object   oldValue = newTable.remove( key );
239     if ( oldValue == null )
240       oldValue = oldTable.remove( key );
241     return oldValue;
242   }
243   
244   /// Clears the hash table so that it has no more elements in it.
245   public synchronized void clear()
246   {
247     newTable.clear();
248     oldTable.clear();
249   }
250   
251   /// Creates a clone of the hashtable. A shallow copy is made,
252   // the keys and elements themselves are NOT cloned. This is a
253   // relatively expensive operation.
254   public synchronized Object   clone()
255   {
256     LruHashtable n = (LruHashtable) super.clone();
257     n.newTable = (Hashtable  ) n.newTable.clone();
258     n.oldTable = (Hashtable  ) n.oldTable.clone();
259     return n;
260   }
261   
262   // toString() can be inherited.
263   
264 }
265 
266 
267 class LruHashtableEnumerator implements Enumeration  
268 {
269   Enumeration   oldEnum;
270   Enumeration   newEnum;
271   boolean old;
272   
273   LruHashtableEnumerator( Hashtable   oldTable, Hashtable   newTable, boolean keys )
274   {
275     if ( keys )
276       {
277     oldEnum = oldTable.keys();
278     newEnum = newTable.keys();
279       }
280     else
281       {
282     oldEnum = oldTable.elements();
283     newEnum = newTable.elements();
284       }
285     old = true;
286   }
287   
288   public boolean hasMoreElements()
289   {
290     boolean r;
291     if ( old )
292       {
293     r = oldEnum.hasMoreElements();
294     if ( ! r )
295       {
296         old = false;
297         r = newEnum.hasMoreElements();
298       }
299       }
300     else
301       r = newEnum.hasMoreElements();
302     return r;
303   }
304   
305   public Object   nextElement()
306   {
307     if ( old )
308       return oldEnum.nextElement();
309     return newEnum.nextElement();
310   }
311   
312 }
313 
314
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags