001: /*
002: * @(#)Cache.java 1.24 06/10/10
003: *
004: * Copyright 1990-2006 Sun Microsystems, Inc. All Rights Reserved.
005: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER
006: *
007: * This program is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU General Public License version
009: * 2 only, as published by the Free Software Foundation.
010: *
011: * This program is distributed in the hope that it will be useful, but
012: * WITHOUT ANY WARRANTY; without even the implied warranty of
013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014: * General Public License version 2 for more details (a copy is
015: * included at /legal/license.txt).
016: *
017: * You should have received a copy of the GNU General Public License
018: * version 2 along with this work; if not, write to the Free Software
019: * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
020: * 02110-1301 USA
021: *
022: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
023: * Clara, CA 95054 or visit www.sun.com if you need additional
024: * information or have any questions.
025: */
026:
027: package sun.misc;
028:
029: import java.util.Dictionary;
030: import java.util.Enumeration;
031: import java.util.NoSuchElementException;
032:
033: /**
034: * Caches the collision list.
035: */
036: class CacheEntry extends Ref {
037: int hash;
038: Object key;
039: CacheEntry next;
040:
041: public Object reconstitute() {
042: return null;
043: }
044: }
045:
046: /**
047: * The Cache class. Maps keys to values. Any object can be used as
048: * a key and/or value. This is very similar to the Hashtable
049: * class, except that after putting an object into the Cache,
050: * it is not guaranteed that a subsequent get will return it.
051: * The Cache will automatically remove entries if memory is
052: * getting tight and if the entry is not referenced from outside
053: * the Cache.<p>
054: *
055: * To sucessfully store and retrieve objects from a hash table the
056: * object used as the key must implement the hashCode() and equals()
057: * methods.<p>
058: *
059: * This example creates a Cache of numbers. It uses the names of
060: * the numbers as keys:
061: * <pre>
062: * Cache numbers = new Cache();
063: * numbers.put("one", new Integer(1));
064: * numbers.put("two", new Integer(1));
065: * numbers.put("three", new Integer(1));
066: * </pre>
067: * To retrieve a number use:
068: * <pre>
069: * Integer n = (Integer)numbers.get("two");
070: * if (n != null) {
071: * System.out.println("two = " + n);
072: * }
073: * </pre>
074: *
075: * @see java.lang.Object#hashCode
076: * @see java.lang.Object#equals
077: * @see sun.misc.Ref
078: * @version 1.18, 08/19/02
079: */
080: public class Cache extends Dictionary {
081: /**
082: * The hash table data.
083: */
084: private CacheEntry table[];
085: /**
086: * The total number of entries in the hash table.
087: */
088: private int count;
089: /**
090: * Rehashes the table when count exceeds this threshold.
091: */
092: private int threshold;
093: /**
094: * The load factor for the hashtable.
095: */
096: private float loadFactor;
097:
098: private void init(int initialCapacity, float loadFactor) {
099: if ((initialCapacity <= 0) || (loadFactor <= 0.0)) {
100: throw new IllegalArgumentException();
101: }
102: this .loadFactor = loadFactor;
103: table = new CacheEntry[initialCapacity];
104: threshold = (int) (initialCapacity * loadFactor);
105: }
106:
107: /**
108: * Constructs a new, empty Cache with the specified initial
109: * capacity and the specified load factor.
110: * @param initialCapacity the initial number of buckets
111: * @param loadFactor a number between 0.0 and 1.0, it defines
112: * the threshold for rehashing the Cache into
113: * a bigger one.
114: * @exception IllegalArgumentException If the initial capacity
115: * is less than or equal to zero.
116: * @exception IllegalArgumentException If the load factor is
117: * less than or equal to zero.
118: */
119: public Cache(int initialCapacity, float loadFactor) {
120: init(initialCapacity, loadFactor);
121: }
122:
123: /**
124: * Constructs a new, empty Cache with the specified initial
125: * capacity.
126: * @param initialCapacity the initial number of buckets
127: */
128: public Cache(int initialCapacity) {
129: init(initialCapacity, 0.75f);
130: }
131:
132: /**
133: * Constructs a new, empty Cache. A default capacity and load factor
134: * is used. Note that the Cache will automatically grow when it gets
135: * full.
136: */
137: public Cache() {
138: try {
139: init(101, 0.75f);
140: } catch (IllegalArgumentException ex) {
141: // This should never happen
142: throw new Error("panic");
143: }
144: }
145:
146: /**
147: * Returns the number of elements contained within the Cache.
148: */
149: public int size() {
150: return count;
151: }
152:
153: /**
154: * Returns true if the Cache contains no elements.
155: */
156: public boolean isEmpty() {
157: return count == 0;
158: }
159:
160: /**
161: * Returns an enumeration of the Cache's keys.
162: * @see Cache#elements
163: * @see Enumeration
164: */
165: public synchronized Enumeration keys() {
166: return new CacheEnumerator(table, true);
167: }
168:
169: /**
170: * Returns an enumeration of the elements. Use the Enumeration methods
171: * on the returned object to fetch the elements sequentially.
172: * @see Cache#keys
173: * @see Enumeration
174: */
175: public synchronized Enumeration elements() {
176: return new CacheEnumerator(table, false);
177: }
178:
179: /**
180: * Gets the object associated with the specified key in the Cache.
181: * @param key the key in the hash table
182: * @returns the element for the key or null if the key
183: * is not defined in the hash table.
184: * @see Cache#put
185: */
186: public synchronized Object get(Object key) {
187: CacheEntry tab[] = table;
188: int hash = key.hashCode();
189: int index = (hash & 0x7FFFFFFF) % tab.length;
190: for (CacheEntry e = tab[index]; e != null; e = e.next) {
191: if ((e.hash == hash) && e.key.equals(key)) {
192: return e.check();
193: }
194: }
195: return null;
196: }
197:
198: /**
199: * Rehashes the contents of the table into a bigger table.
200: * This is method is called automatically when the Cache's
201: * size exceeds the threshold.
202: */
203: protected void rehash() {
204: int oldCapacity = table.length;
205: CacheEntry oldTable[] = table;
206: int newCapacity = oldCapacity * 2 + 1;
207: CacheEntry newTable[] = new CacheEntry[newCapacity];
208: threshold = (int) (newCapacity * loadFactor);
209: table = newTable;
210: // System.out.println("rehash old=" + oldCapacity + ", new=" +
211: // newCapacity + ", thresh=" + threshold + ", count=" + count);
212:
213: for (int i = oldCapacity; i-- > 0;) {
214: for (CacheEntry old = oldTable[i]; old != null;) {
215: CacheEntry e = old;
216: old = old.next;
217: if (e.check() != null) {
218: int index = (e.hash & 0x7FFFFFFF) % newCapacity;
219: e.next = newTable[index];
220: newTable[index] = e;
221: } else
222: count--; /* remove entries that have disappeared */
223: }
224: }
225: }
226:
227: /**
228: * Puts the specified element into the Cache, using the specified
229: * key. The element may be retrieved by doing a get() with the same
230: * key. The key and the element cannot be null.
231: * @param key the specified hashtable key
232: * @param value the specified element
233: * @return the old value of the key, or null if it did not have one.
234: * @exception NullPointerException If the value of the specified
235: * element is null.
236: * @see Cache#get
237: */
238: public synchronized Object put(Object key, Object value) {
239: // Make sure the value is not null
240: if (value == null) {
241: throw new NullPointerException();
242: }
243: // Makes sure the key is not already in the cache.
244: CacheEntry tab[] = table;
245: int hash = key.hashCode();
246: int index = (hash & 0x7FFFFFFF) % tab.length;
247: CacheEntry ne = null;
248: for (CacheEntry e = tab[index]; e != null; e = e.next) {
249: if ((e.hash == hash) && e.key.equals(key)) {
250: Object old = e.check();
251: e.setThing(value);
252: return old;
253: } else if (e.check() == null)
254: ne = e; /* reuse old flushed value */
255: }
256: if (count >= threshold) {
257: // Rehash the table if the threshold is exceeded
258: rehash();
259: return put(key, value);
260: }
261: // Creates the new entry.
262: if (ne == null) {
263: ne = new CacheEntry();
264: ne.next = tab[index];
265: tab[index] = ne;
266: count++;
267: }
268: ne.hash = hash;
269: ne.key = key;
270: ne.setThing(value);
271: return null;
272: }
273:
274: /**
275: * Removes the element corresponding to the key. Does nothing if the
276: * key is not present.
277: * @param key the key that needs to be removed
278: * @return the value of key, or null if the key was not found.
279: */
280: public synchronized Object remove(Object key) {
281: CacheEntry tab[] = table;
282: int hash = key.hashCode();
283: int index = (hash & 0x7FFFFFFF) % tab.length;
284: for (CacheEntry e = tab[index], prev = null; e != null; prev = e, e = e.next) {
285: if ((e.hash == hash) && e.key.equals(key)) {
286: if (prev != null) {
287: prev.next = e.next;
288: } else {
289: tab[index] = e.next;
290: }
291: count--;
292: return e.check();
293: }
294: }
295: return null;
296: }
297: }
298:
299: /**
300: * A Cache enumerator class. This class should remain opaque
301: * to the client. It will use the Enumeration interface.
302: */
303: class CacheEnumerator implements Enumeration {
304: boolean keys;
305: int index;
306: CacheEntry table[];
307: CacheEntry entry;
308:
309: CacheEnumerator(CacheEntry table[], boolean keys) {
310: this .table = table;
311: this .keys = keys;
312: this .index = table.length;
313: }
314:
315: public boolean hasMoreElements() {
316: while (index >= 0) {
317: while (entry != null)
318: if (entry.check() != null)
319: return true;
320: else
321: entry = entry.next;
322: while (--index >= 0 && (entry = table[index]) == null)
323: ;
324: }
325: return false;
326: }
327:
328: public Object nextElement() {
329: while (index >= 0) {
330: if (entry == null)
331: while (--index >= 0 && (entry = table[index]) == null)
332: ;
333: if (entry != null) {
334: CacheEntry e = entry;
335: entry = e.next;
336: if (e.check() != null)
337: return keys ? e.key : e.check();
338: }
339: }
340: throw new NoSuchElementException("CacheEnumerator");
341: }
342: }
|