|
What this is
This file is included in the DevDaily.com
"Java Source Code
Warehouse" project. The intent of this project is to help you "Learn
Java by Example" TM.
Other links
The source code
/*
* Copyright 1999-2004 The Apache Software Foundation
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package org.apache.tomcat.util.collections;
import java.util.Enumeration;
/* **************************************** Stolen from Crimson ******************** */
/* From Crimson/Parser - in a perfect world we'll just have a common set of
utilities, and all apache project will just use those.
*/
// can't be replaced using a Java 2 "Collections" API
// since this package must also run on JDK 1.1
/**
* This class implements a special purpose hashtable. It works like a
* normal java.util.Hashtable except that:
*
* - Keys to "get" are strings which are known to be interned,
* so that "==" is used instead of "String.equals". (Interning
* could be document-relative instead of global.)
*
*
- It's not synchronized, since it's to be used only by
* one thread at a time.
*
*
- The keys () enumerator allocates no memory, with live
* updates to the data disallowed.
*
*
- It's got fewer bells and whistles: fixed threshold and
* load factor, no JDK 1.2 collection support, only keys can be
* enumerated, things can't be removed, simpler inheritance; more.
*
*
*
* The overall result is that it's less expensive to use these in
* performance-critical locations, in terms both of CPU and memory,
* than java.util.Hashtable instances. In this package
* it makes a significant difference when normalizing attributes,
* which is done for each start-element construct.
*
*/
public final class SimpleHashtable implements Enumeration
{
// entries ...
private Entry table[];
// currently enumerated key
private Entry current = null;
private int currentBucket = 0;
// number of elements in hashtable
private int count;
private int threshold;
private static final float loadFactor = 0.75f;
/**
* Constructs a new, empty hashtable with the specified initial
* capacity.
*
* @param initialCapacity the initial capacity of the hashtable.
*/
public SimpleHashtable(int initialCapacity) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
if (initialCapacity==0)
initialCapacity = 1;
table = new Entry[initialCapacity];
threshold = (int)(initialCapacity * loadFactor);
}
/**
* Constructs a new, empty hashtable with a default capacity.
*/
public SimpleHashtable() {
this(11);
}
/**
*/
public void clear ()
{
count = 0;
currentBucket = 0;
current = null;
for (int i = 0; i < table.length; i++)
table [i] = null;
}
/**
* Returns the number of keys in this hashtable.
*
* @return the number of keys in this hashtable.
*/
public int size() {
return count;
}
/**
* Returns an enumeration of the keys in this hashtable.
*
* @return an enumeration of the keys in this hashtable.
* @see Enumeration
*/
public Enumeration keys() {
currentBucket = 0;
current = null;
hasMoreElements();
return this;
}
/**
* Used to view this as an enumeration; returns true if there
* are more keys to be enumerated.
*/
public boolean hasMoreElements ()
{
if (current != null)
return true;
while (currentBucket < table.length) {
current = table [currentBucket++];
if (current != null)
return true;
}
return false;
}
/**
* Used to view this as an enumeration; returns the next key
* in the enumeration.
*/
public Object nextElement ()
{
Object retval;
if (current == null)
throw new IllegalStateException ();
retval = current.key;
current = current.next;
// Advance to the next position ( we may call next after next,
// without hasMore )
hasMoreElements();
return retval;
}
/**
* Returns the value to which the specified key is mapped in this hashtable.
*/
public Object getInterned (String key) {
Entry tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && (e.key == key))
return e.value;
}
return null;
}
/**
* Returns the value to which the specified key is mapped in this
* hashtable ... the key isn't necessarily interned, though.
*/
public Object get(String key) {
Entry tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key))
return e.value;
}
return null;
}
/**
* Increases the capacity of and internally reorganizes this
* hashtable, in order to accommodate and access its entries more
* efficiently. This method is called automatically when the
* number of keys in the hashtable exceeds this hashtable's capacity
* and load factor.
*/
private void rehash() {
int oldCapacity = table.length;
Entry oldMap[] = table;
int newCapacity = oldCapacity * 2 + 1;
Entry newMap[] = new Entry[newCapacity];
threshold = (int)(newCapacity * loadFactor);
table = newMap;
/*
System.out.pr intln("rehash old=" + oldCapacity
+ ", new=" + newCapacity
+ ", thresh=" + threshold
+ ", count=" + count);
*/
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry old = oldMap[i] ; old != null ; ) {
Entry e = old;
old = old.next;
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
e.next = newMap[index];
newMap[index] = e;
}
}
}
/**
* Maps the specified key to the specified
* value in this hashtable. Neither the key nor the
* value can be null .
*
* The value can be retrieved by calling the get method
* with a key that is equal to the original key.
*/
public 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 hashtable.
Entry tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry e = tab[index] ; e != null ; e = e.next) {
// if ((e.hash == hash) && e.key.equals(key)) {
if ((e.hash == hash) && (e.key == key)) {
Object old = e.value;
e.value = value;
return old;
}
}
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash();
tab = table;
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
Entry e = new Entry(hash, key, value, tab[index]);
tab[index] = e;
count++;
return null;
}
public Object remove(Object key) {
Entry tab[] = table;
Entry prev=null;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
if( dL > 0 ) d("Idx " + index + " " + tab[index] );
for (Entry e = tab[index] ; e != null ; prev=e, e = e.next) {
if( dL > 0 ) d("> " + prev + " " + e.next + " " + e + " " + e.key);
if ((e.hash == hash) && e.key.equals(key)) {
if( prev!=null ) {
prev.next=e.next;
} else {
tab[index]=e.next;
}
if( dL > 0 ) d("Removing from list " + tab[index] + " " + prev +
" " + e.value);
count--;
Object res=e.value;
e.value=null;
return res;
}
}
return null;
}
/**
* Hashtable collision list.
*/
private static class Entry {
int hash;
Object key;
Object value;
Entry next;
protected Entry(int hash, Object key, Object value, Entry next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
private static final int dL=0;
private void d(String s ) {
System.err.println( "SimpleHashtable: " + s );
}
}
|