ojluni/src/main/java/sun/misc/Cache.java - platform/libcore.git - Git at Google

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

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

	}