Back to index...

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

	}

Back to index...