sun/misc/Cache.java

/*
 * 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
 */
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");
    }

}