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