001: /*
002: * Copyright 1999-2004 The Apache Software Foundation
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License");
005: * you may not use this file except in compliance with the License.
006: * You may obtain a copy of the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS,
012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013: * See the License for the specific language governing permissions and
014: * limitations under the License.
015: */
016:
017: package org.apache.tomcat.util.collections;
018:
019: import java.util.Enumeration;
020:
021: /* **************************************** Stolen from Crimson ******************** */
022: /* From Crimson/Parser - in a perfect world we'll just have a common set of
023: utilities, and all apache project will just use those.
024:
025: */
026:
027: // can't be replaced using a Java 2 "Collections" API
028: // since this package must also run on JDK 1.1
029:
030: /**
031: * This class implements a special purpose hashtable. It works like a
032: * normal <code>java.util.Hashtable</code> except that: <OL>
033: *
034: * <LI> Keys to "get" are strings which are known to be interned,
035: * so that "==" is used instead of "String.equals". (Interning
036: * could be document-relative instead of global.)
037: *
038: * <LI> It's not synchronized, since it's to be used only by
039: * one thread at a time.
040: *
041: * <LI> The keys () enumerator allocates no memory, with live
042: * updates to the data disallowed.
043: *
044: * <LI> It's got fewer bells and whistles: fixed threshold and
045: * load factor, no JDK 1.2 collection support, only keys can be
046: * enumerated, things can't be removed, simpler inheritance; more.
047: *
048: * </OL>
049: *
050: * <P> The overall result is that it's less expensive to use these in
051: * performance-critical locations, in terms both of CPU and memory,
052: * than <code>java.util.Hashtable</code> instances. In this package
053: * it makes a significant difference when normalizing attributes,
054: * which is done for each start-element construct.
055: *
056: */
057: public final class SimpleHashtable implements Enumeration {
058: // entries ...
059: private Entry table[];
060:
061: // currently enumerated key
062: private Entry current = null;
063: private int currentBucket = 0;
064:
065: // number of elements in hashtable
066: private int count;
067: private int threshold;
068:
069: private static final float loadFactor = 0.75f;
070:
071: /**
072: * Constructs a new, empty hashtable with the specified initial
073: * capacity.
074: *
075: * @param initialCapacity the initial capacity of the hashtable.
076: */
077: public SimpleHashtable(int initialCapacity) {
078: if (initialCapacity < 0)
079: throw new IllegalArgumentException("Illegal Capacity: "
080: + initialCapacity);
081: if (initialCapacity == 0)
082: initialCapacity = 1;
083: table = new Entry[initialCapacity];
084: threshold = (int) (initialCapacity * loadFactor);
085: }
086:
087: /**
088: * Constructs a new, empty hashtable with a default capacity.
089: */
090: public SimpleHashtable() {
091: this (11);
092: }
093:
094: /**
095: */
096: public void clear() {
097: count = 0;
098: currentBucket = 0;
099: current = null;
100: for (int i = 0; i < table.length; i++)
101: table[i] = null;
102: }
103:
104: /**
105: * Returns the number of keys in this hashtable.
106: *
107: * @return the number of keys in this hashtable.
108: */
109: public int size() {
110: return count;
111: }
112:
113: /**
114: * Returns an enumeration of the keys in this hashtable.
115: *
116: * @return an enumeration of the keys in this hashtable.
117: * @see Enumeration
118: */
119: public Enumeration keys() {
120: currentBucket = 0;
121: current = null;
122: hasMoreElements();
123: return this ;
124: }
125:
126: /**
127: * Used to view this as an enumeration; returns true if there
128: * are more keys to be enumerated.
129: */
130: public boolean hasMoreElements() {
131: if (current != null)
132: return true;
133: while (currentBucket < table.length) {
134: current = table[currentBucket++];
135: if (current != null)
136: return true;
137: }
138: return false;
139: }
140:
141: /**
142: * Used to view this as an enumeration; returns the next key
143: * in the enumeration.
144: */
145: public Object nextElement() {
146: Object retval;
147:
148: if (current == null)
149: throw new IllegalStateException();
150: retval = current.key;
151: current = current.next;
152: // Advance to the next position ( we may call next after next,
153: // without hasMore )
154: hasMoreElements();
155: return retval;
156: }
157:
158: /**
159: * Returns the value to which the specified key is mapped in this hashtable.
160: */
161: public Object getInterned(String key) {
162: Entry tab[] = table;
163: int hash = key.hashCode();
164: int index = (hash & 0x7FFFFFFF) % tab.length;
165: for (Entry e = tab[index]; e != null; e = e.next) {
166: if ((e.hash == hash) && (e.key == key))
167: return e.value;
168: }
169: return null;
170: }
171:
172: /**
173: * Returns the value to which the specified key is mapped in this
174: * hashtable ... the key isn't necessarily interned, though.
175: */
176: public Object get(String key) {
177: Entry tab[] = table;
178: int hash = key.hashCode();
179: int index = (hash & 0x7FFFFFFF) % tab.length;
180: for (Entry e = tab[index]; e != null; e = e.next) {
181: if ((e.hash == hash) && e.key.equals(key))
182: return e.value;
183: }
184: return null;
185: }
186:
187: /**
188: * Increases the capacity of and internally reorganizes this
189: * hashtable, in order to accommodate and access its entries more
190: * efficiently. This method is called automatically when the
191: * number of keys in the hashtable exceeds this hashtable's capacity
192: * and load factor.
193: */
194: private void rehash() {
195: int oldCapacity = table.length;
196: Entry oldMap[] = table;
197:
198: int newCapacity = oldCapacity * 2 + 1;
199: Entry newMap[] = new Entry[newCapacity];
200:
201: threshold = (int) (newCapacity * loadFactor);
202: table = newMap;
203:
204: /*
205: System.out.pr intln("rehash old=" + oldCapacity
206: + ", new=" + newCapacity
207: + ", thresh=" + threshold
208: + ", count=" + count);
209: */
210:
211: for (int i = oldCapacity; i-- > 0;) {
212: for (Entry old = oldMap[i]; old != null;) {
213: Entry e = old;
214: old = old.next;
215:
216: int index = (e.hash & 0x7FFFFFFF) % newCapacity;
217: e.next = newMap[index];
218: newMap[index] = e;
219: }
220: }
221: }
222:
223: /**
224: * Maps the specified <code>key</code> to the specified
225: * <code>value</code> in this hashtable. Neither the key nor the
226: * value can be <code>null</code>.
227: *
228: * <P>The value can be retrieved by calling the <code>get</code> method
229: * with a key that is equal to the original key.
230: */
231: public Object put(Object key, Object value) {
232: // Make sure the value is not null
233: if (value == null) {
234: throw new NullPointerException();
235: }
236:
237: // Makes sure the key is not already in the hashtable.
238: Entry tab[] = table;
239: int hash = key.hashCode();
240: int index = (hash & 0x7FFFFFFF) % tab.length;
241: for (Entry e = tab[index]; e != null; e = e.next) {
242: // if ((e.hash == hash) && e.key.equals(key)) {
243: if ((e.hash == hash) && (e.key == key)) {
244: Object old = e.value;
245: e.value = value;
246: return old;
247: }
248: }
249:
250: if (count >= threshold) {
251: // Rehash the table if the threshold is exceeded
252: rehash();
253:
254: tab = table;
255: index = (hash & 0x7FFFFFFF) % tab.length;
256: }
257:
258: // Creates the new entry.
259: Entry e = new Entry(hash, key, value, tab[index]);
260: tab[index] = e;
261: count++;
262: return null;
263: }
264:
265: public Object remove(Object key) {
266: Entry tab[] = table;
267: Entry prev = null;
268: int hash = key.hashCode();
269: int index = (hash & 0x7FFFFFFF) % tab.length;
270: if (dL > 0)
271: d("Idx " + index + " " + tab[index]);
272: for (Entry e = tab[index]; e != null; prev = e, e = e.next) {
273: if (dL > 0)
274: d("> " + prev + " " + e.next + " " + e + " " + e.key);
275: if ((e.hash == hash) && e.key.equals(key)) {
276: if (prev != null) {
277: prev.next = e.next;
278: } else {
279: tab[index] = e.next;
280: }
281: if (dL > 0)
282: d("Removing from list " + tab[index] + " " + prev
283: + " " + e.value);
284: count--;
285: Object res = e.value;
286: e.value = null;
287: return res;
288: }
289: }
290: return null;
291: }
292:
293: /**
294: * Hashtable collision list.
295: */
296: private static class Entry {
297: int hash;
298: Object key;
299: Object value;
300: Entry next;
301:
302: protected Entry(int hash, Object key, Object value, Entry next) {
303: this .hash = hash;
304: this .key = key;
305: this .value = value;
306: this .next = next;
307: }
308: }
309:
310: private static final int dL = 0;
311:
312: private void d(String s) {
313: System.err.println("SimpleHashtable: " + s);
314: }
315: }
|