/* * Copyright (c) 1995, 1996, Oracle and/or its affiliates. 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.  Oracle designates this * particular file as subject to the "Classpath" exception as provided * by Oracle 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA * or visit www.oracle.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 */publicclass 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");    } }