jdk/src/share/classes/sun/misc/Cache.java
changeset 2 90ce3da70b43
child 5506 202f599c92aa
--- /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");
+    }
+
+}