--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/src/share/classes/sun/misc/Cache.java Sat Dec 01 00:00:00 2007 +0000
@@ -0,0 +1,346 @@
+/*
+ * Copyright 1995-1996 Sun Microsystems, Inc. All Rights Reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation. Sun designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Sun in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
+ * CA 95054 USA or visit www.sun.com if you need additional information or
+ * have any questions.
+ */
+
+package sun.misc;
+
+import java.util.Dictionary;
+import java.util.Enumeration;
+import java.util.NoSuchElementException;
+
+/**
+ * Caches the collision list.
+ */
+class CacheEntry extends Ref {
+ int hash;
+ Object key;
+ CacheEntry next;
+ public Object reconstitute() {
+ return null;
+ }
+}
+
+/**
+ * The Cache class. Maps keys to values. Any object can be used as
+ * a key and/or value. This is very similar to the Hashtable
+ * class, except that after putting an object into the Cache,
+ * it is not guaranteed that a subsequent get will return it.
+ * The Cache will automatically remove entries if memory is
+ * getting tight and if the entry is not referenced from outside
+ * the Cache.<p>
+ *
+ * To sucessfully store and retrieve objects from a hash table the
+ * object used as the key must implement the hashCode() and equals()
+ * methods.<p>
+ *
+ * This example creates a Cache of numbers. It uses the names of
+ * the numbers as keys:
+ * <pre>
+ * Cache numbers = new Cache();
+ * numbers.put("one", new Integer(1));
+ * numbers.put("two", new Integer(1));
+ * numbers.put("three", new Integer(1));
+ * </pre>
+ * To retrieve a number use:
+ * <pre>
+ * Integer n = (Integer)numbers.get("two");
+ * if (n != null) {
+ * System.out.println("two = " + n);
+ * }
+ * </pre>
+ *
+ * @see java.lang.Object#hashCode
+ * @see java.lang.Object#equals
+ * @see sun.misc.Ref
+ */
+public
+class Cache extends Dictionary {
+ /**
+ * The hash table data.
+ */
+ private CacheEntry table[];
+
+ /**
+ * The total number of entries in the hash table.
+ */
+ private int count;
+
+ /**
+ * Rehashes the table when count exceeds this threshold.
+ */
+ private int threshold;
+
+ /**
+ * The load factor for the hashtable.
+ */
+ private float loadFactor;
+
+ private void init(int initialCapacity, float loadFactor) {
+ if ((initialCapacity <= 0) || (loadFactor <= 0.0)) {
+ throw new IllegalArgumentException();
+ }
+ this.loadFactor = loadFactor;
+ table = new CacheEntry[initialCapacity];
+ threshold = (int) (initialCapacity * loadFactor);
+ }
+
+ /**
+ * Constructs a new, empty Cache with the specified initial
+ * capacity and the specified load factor.
+ * @param initialCapacity the initial number of buckets
+ * @param loadFactor a number between 0.0 and 1.0, it defines
+ * the threshold for rehashing the Cache into
+ * a bigger one.
+ * @exception IllegalArgumentException If the initial capacity
+ * is less than or equal to zero.
+ * @exception IllegalArgumentException If the load factor is
+ * less than or equal to zero.
+ */
+ public Cache (int initialCapacity, float loadFactor) {
+ init(initialCapacity, loadFactor);
+ }
+
+ /**
+ * Constructs a new, empty Cache with the specified initial
+ * capacity.
+ * @param initialCapacity the initial number of buckets
+ */
+ public Cache (int initialCapacity) {
+ init(initialCapacity, 0.75f);
+ }
+
+ /**
+ * Constructs a new, empty Cache. A default capacity and load factor
+ * is used. Note that the Cache will automatically grow when it gets
+ * full.
+ */
+ public Cache () {
+ try {
+ init(101, 0.75f);
+ } catch (IllegalArgumentException ex) {
+ // This should never happen
+ throw new Error("panic");
+ }
+ }
+
+ /**
+ * Returns the number of elements contained within the Cache.
+ */
+ public int size() {
+ return count;
+ }
+
+ /**
+ * Returns true if the Cache contains no elements.
+ */
+ public boolean isEmpty() {
+ return count == 0;
+ }
+
+ /**
+ * Returns an enumeration of the Cache's keys.
+ * @see Cache#elements
+ * @see Enumeration
+ */
+ public synchronized Enumeration keys() {
+ return new CacheEnumerator(table, true);
+ }
+
+ /**
+ * Returns an enumeration of the elements. Use the Enumeration methods
+ * on the returned object to fetch the elements sequentially.
+ * @see Cache#keys
+ * @see Enumeration
+ */
+ public synchronized Enumeration elements() {
+ return new CacheEnumerator(table, false);
+ }
+
+ /**
+ * Gets the object associated with the specified key in the Cache.
+ * @param key the key in the hash table
+ * @returns the element for the key or null if the key
+ * is not defined in the hash table.
+ * @see Cache#put
+ */
+ public synchronized Object get(Object key) {
+ CacheEntry tab[] = table;
+ int hash = key.hashCode();
+ int index = (hash & 0x7FFFFFFF) % tab.length;
+ for (CacheEntry e = tab[index]; e != null; e = e.next) {
+ if ((e.hash == hash) && e.key.equals(key)) {
+ return e.check();
+ }
+ }
+ return null;
+ }
+
+ /**
+ * Rehashes the contents of the table into a bigger table.
+ * This is method is called automatically when the Cache's
+ * size exceeds the threshold.
+ */
+ protected void rehash() {
+ int oldCapacity = table.length;
+ CacheEntry oldTable[] = table;
+
+ int newCapacity = oldCapacity * 2 + 1;
+ CacheEntry newTable[] = new CacheEntry[newCapacity];
+
+ threshold = (int) (newCapacity * loadFactor);
+ table = newTable;
+
+ // System.out.println("rehash old=" + oldCapacity + ", new=" +
+ // newCapacity + ", thresh=" + threshold + ", count=" + count);
+
+ for (int i = oldCapacity; i-- > 0;) {
+ for (CacheEntry old = oldTable[i]; old != null;) {
+ CacheEntry e = old;
+ old = old.next;
+ if (e.check() != null) {
+ int index = (e.hash & 0x7FFFFFFF) % newCapacity;
+ e.next = newTable[index];
+ newTable[index] = e;
+ } else
+ count--; /* remove entries that have disappeared */
+ }
+ }
+ }
+
+ /**
+ * Puts the specified element into the Cache, using the specified
+ * key. The element may be retrieved by doing a get() with the same
+ * key. The key and the element cannot be null.
+ * @param key the specified hashtable key
+ * @param value the specified element
+ * @return the old value of the key, or null if it did not have one.
+ * @exception NullPointerException If the value of the specified
+ * element is null.
+ * @see Cache#get
+ */
+ public synchronized Object put(Object key, Object value) {
+ // Make sure the value is not null
+ if (value == null) {
+ throw new NullPointerException();
+ }
+ // Makes sure the key is not already in the cache.
+ CacheEntry tab[] = table;
+ int hash = key.hashCode();
+ int index = (hash & 0x7FFFFFFF) % tab.length;
+ CacheEntry ne = null;
+ for (CacheEntry e = tab[index]; e != null; e = e.next) {
+ if ((e.hash == hash) && e.key.equals(key)) {
+ Object old = e.check();
+ e.setThing(value);
+ return old;
+ } else if (e.check() == null)
+ ne = e; /* reuse old flushed value */
+ }
+
+ if (count >= threshold) {
+ // Rehash the table if the threshold is exceeded
+ rehash();
+ return put(key, value);
+ }
+ // Creates the new entry.
+ if (ne == null) {
+ ne = new CacheEntry ();
+ ne.next = tab[index];
+ tab[index] = ne;
+ count++;
+ }
+ ne.hash = hash;
+ ne.key = key;
+ ne.setThing(value);
+ return null;
+ }
+
+ /**
+ * Removes the element corresponding to the key. Does nothing if the
+ * key is not present.
+ * @param key the key that needs to be removed
+ * @return the value of key, or null if the key was not found.
+ */
+ public synchronized Object remove(Object key) {
+ CacheEntry tab[] = table;
+ int hash = key.hashCode();
+ int index = (hash & 0x7FFFFFFF) % tab.length;
+ for (CacheEntry e = tab[index], prev = null; e != null; prev = e, e = e.next) {
+ if ((e.hash == hash) && e.key.equals(key)) {
+ if (prev != null) {
+ prev.next = e.next;
+ } else {
+ tab[index] = e.next;
+ }
+ count--;
+ return e.check();
+ }
+ }
+ return null;
+ }
+}
+
+/**
+ * A Cache enumerator class. This class should remain opaque
+ * to the client. It will use the Enumeration interface.
+ */
+class CacheEnumerator implements Enumeration {
+ boolean keys;
+ int index;
+ CacheEntry table[];
+ CacheEntry entry;
+
+ CacheEnumerator (CacheEntry table[], boolean keys) {
+ this.table = table;
+ this.keys = keys;
+ this.index = table.length;
+ }
+
+ public boolean hasMoreElements() {
+ while (index >= 0) {
+ while (entry != null)
+ if (entry.check() != null)
+ return true;
+ else
+ entry = entry.next;
+ while (--index >= 0 && (entry = table[index]) == null) ;
+ }
+ return false;
+ }
+
+ public Object nextElement() {
+ while (index >= 0) {
+ if (entry == null)
+ while (--index >= 0 && (entry = table[index]) == null) ;
+ if (entry != null) {
+ CacheEntry e = entry;
+ entry = e.next;
+ if (e.check() != null)
+ return keys ? e.key : e.check();
+ }
+ }
+ throw new NoSuchElementException("CacheEnumerator");
+ }
+
+}