001: // LruHashtable - a Hashtable that expires least-recently-used objects
002: //
003: // Copyright (C) 1996 by Jef Poskanzer <jef@acme.com>. All rights reserved.
004: //
005: // Redistribution and use in source and binary forms, with or without
006: // modification, are permitted provided that the following conditions
007: // are met:
008: // 1. Redistributions of source code must retain the above copyright
009: // notice, this list of conditions and the following disclaimer.
010: // 2. Redistributions in binary form must reproduce the above copyright
011: // notice, this list of conditions and the following disclaimer in the
012: // documentation and/or other materials provided with the distribution.
013: //
014: // THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
015: // ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
016: // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
017: // ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
018: // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
019: // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
020: // OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
021: // HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
022: // LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
023: // OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
024: // SUCH DAMAGE.
025: //
026: // Visit the ACME Labs Java page for up-to-date versions of this and other
027: // fine Java utilities: http://www.acme.com/java/
028:
029: //
030: // moved to the net.matuschek.util package by Daniel Matuschek
031: //
032:
033: package net.matuschek.util;
034:
035: import java.util.Enumeration;
036: import java.util.Hashtable;
037:
038: /**
039: * A Hashtable that expires least-recently-used objects.
040: *
041: * <p>Use just like java.util.Hashtable, except that the initial-capacity
042: * parameter is required. Instead of growing bigger than that size,
043: * it will throw out objects that haven't been looked at in a while.
044: * </p>
045: *
046: * @author Jef Poskanzer
047: * @author Daniel Matuschek
048: * @version $Id: LruHashtable.java,v 1.3 2002/05/31 14:45:56 matuschd Exp $
049: *
050: * @see java.util.Hashtable
051: */
052:
053: public class LruHashtable extends Hashtable {
054:
055: // Number of buckets.
056: private static final int nBuckets = 2;
057:
058: // Load factor.
059: private float loadFactor;
060:
061: // When count exceeds this threshold, expires the old table.
062: private int threshold;
063:
064: // Capacity of each bucket.
065: private int eachCapacity;
066:
067: // The tables.
068: private Hashtable oldTable;
069: private Hashtable newTable;
070:
071: /// Constructs a new, empty hashtable with the specified initial
072: // capacity and the specified load factor.
073: // Unlike a plain Hashtable, an LruHashtable will never grow or
074: // shrink from this initial capacity.
075: // @param initialCapacity the initial number of buckets
076: // @param loadFactor a number between 0.0 and 1.0, it defines
077: // the threshold for expiring old entries
078: // @exception IllegalArgumentException If the initial capacity
079: // is less than or equal to zero.
080: // @exception IllegalArgumentException If the load factor is
081: // less than or equal to zero.
082: public LruHashtable(int initialCapacity, float loadFactor) {
083: // We have to call a superclass constructor, but we're not actually
084: // going to use it at all. The only reason we want to extend Hashtable
085: // is for type conformance. So, make a parent hash table of minimum
086: // size and then ignore it.
087: super (1);
088:
089: if (initialCapacity <= 0 || loadFactor <= 0.0)
090: throw new IllegalArgumentException();
091: this .loadFactor = loadFactor;
092: threshold = (int) (initialCapacity * loadFactor) - 1;
093: eachCapacity = initialCapacity / nBuckets + 1;
094: oldTable = new Hashtable(eachCapacity, loadFactor);
095: newTable = new Hashtable(eachCapacity, loadFactor);
096: }
097:
098: /// Constructs a new, empty hashtable with the specified initial
099: // capacity.
100: // Unlike a plain Hashtable, an LruHashtable will never grow or
101: // shrink from this initial capacity.
102: // @param initialCapacity the initial number of buckets
103: public LruHashtable(int initialCapacity) {
104: this (initialCapacity, 0.75F);
105: }
106:
107: /// Returns the number of elements contained in the hashtable.
108: public int size() {
109: return newTable.size() + oldTable.size();
110: }
111:
112: /// Returns true if the hashtable contains no elements.
113: public boolean isEmpty() {
114: return size() == 0;
115: }
116:
117: /// Returns an enumeration of the hashtable's keys.
118: // @see LruHashtable#elements
119: // @see Enumeration
120: public synchronized Enumeration keys() {
121: return new LruHashtableEnumerator(oldTable, newTable, true);
122: }
123:
124: /// Returns an enumeration of the elements. Use the Enumeration methods
125: // on the returned object to fetch the elements sequentially.
126: // @see LruHashtable#keys
127: // @see Enumeration
128: public synchronized Enumeration elements() {
129: return new LruHashtableEnumerator(oldTable, newTable, false);
130: }
131:
132: /// Returns true if the specified object is an element of the hashtable.
133: // This operation is more expensive than the containsKey() method.
134: // @param value the value that we are looking for
135: // @exception NullPointerException If the value being searched
136: // for is equal to null.
137: // @see LruHashtable#containsKey
138: public synchronized boolean contains(Object value) {
139: if (newTable.contains(value))
140: return true;
141: if (oldTable.contains(value)) {
142: // We would like to move the object from the old table to the
143: // new table. However, we need keys to re-add the objects, and
144: // there's no good way to find all the keys for the given object.
145: // We'd have to enumerate through all the keys and check each
146: // one. Yuck. For now we just punt. Anyway, contains() is
147: // probably not a commonly-used operation.
148: return true;
149: }
150: return false;
151: }
152:
153: /// Returns true if the collection contains an element for the key.
154: // @param key the key that we are looking for
155: // @see LruHashtable#contains
156: public synchronized boolean containsKey(Object key) {
157: if (newTable.containsKey(key))
158: return true;
159: if (oldTable.containsKey(key)) {
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: Object value;
177: value = newTable.get(key);
178: if (value != null)
179: return value;
180: value = oldTable.get(key);
181: if (value != null) {
182: // Move object from old table to new table.
183: newTable.put(key, value);
184: oldTable.remove(key);
185: return value;
186: }
187: return null;
188: }
189:
190: /// Puts the specified element into the hashtable, using the specified
191: // key. The element may be retrieved by doing a get() with the same key.
192: // The key and the element cannot be null.
193: // @param key the specified key in the hashtable
194: // @param value the specified element
195: // @exception NullPointerException If the value of the element
196: // is equal to null.
197: // @see LruHashtable#get
198: // @return the old value of the key, or null if it did not have one.
199: public synchronized Object put(Object key, Object value) {
200: Object oldValue = newTable.put(key, value);
201: if (oldValue != null)
202: return oldValue;
203: oldValue = oldTable.get(key);
204: if (oldValue != null)
205: oldTable.remove(key);
206: else {
207: if (size() >= threshold) {
208: // Rotate the tables.
209: oldTable = newTable;
210: newTable = new Hashtable(eachCapacity, loadFactor);
211: }
212: }
213: return oldValue;
214: }
215:
216: /// Removes the element corresponding to the key. Does nothing if the
217: // key is not present.
218: // @param key the key that needs to be removed
219: // @return the value of key, or null if the key was not found.
220: public synchronized Object remove(Object key) {
221: Object oldValue = newTable.remove(key);
222: if (oldValue == null)
223: oldValue = oldTable.remove(key);
224: return oldValue;
225: }
226:
227: /// Clears the hash table so that it has no more elements in it.
228: public synchronized void clear() {
229: newTable.clear();
230: oldTable.clear();
231: }
232:
233: /// Creates a clone of the hashtable. A shallow copy is made,
234: // the keys and elements themselves are NOT cloned. This is a
235: // relatively expensive operation.
236: public synchronized Object clone() {
237: LruHashtable n = (LruHashtable) super .clone();
238: n.newTable = (Hashtable) n.newTable.clone();
239: n.oldTable = (Hashtable) n.oldTable.clone();
240: return n;
241: }
242:
243: // toString() can be inherited.
244:
245: }
246:
247: class LruHashtableEnumerator implements Enumeration {
248: Enumeration oldEnum;
249: Enumeration newEnum;
250: boolean old;
251:
252: LruHashtableEnumerator(Hashtable oldTable, Hashtable newTable,
253: boolean keys) {
254: if (keys) {
255: oldEnum = oldTable.keys();
256: newEnum = newTable.keys();
257: } else {
258: oldEnum = oldTable.elements();
259: newEnum = newTable.elements();
260: }
261: old = true;
262: }
263:
264: public boolean hasMoreElements() {
265: boolean r;
266: if (old) {
267: r = oldEnum.hasMoreElements();
268: if (!r) {
269: old = false;
270: r = newEnum.hasMoreElements();
271: }
272: } else
273: r = newEnum.hasMoreElements();
274: return r;
275: }
276:
277: public Object nextElement() {
278: if (old)
279: return oldEnum.nextElement();
280: return newEnum.nextElement();
281: }
282:
283: }
|