/*

 * 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

    /**

     * 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

     */

        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

     */

        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.

 */

    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");

    }

}