001: /*
002: * Copyright 2001-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: * $Id: Hashtable.java,v 1.4 2004/02/16 22:55:54 minchau Exp $
018: */
019:
020: package org.apache.xalan.xsltc.runtime;
021:
022: import java.util.Enumeration;
023:
024: /**
025: * IMPORTANT NOTE:
026: * This code was taken from Sun's Java1.1 JDK java.util.HashTable.java
027: * All "synchronized" keywords and some methods we do not need have been
028: * all been removed.
029: */
030:
031: /**
032: * Object that wraps entries in the hash-table
033: * @author Morten Jorgensen
034: */
035: class HashtableEntry {
036: int hash;
037: Object key;
038: Object value;
039: HashtableEntry next;
040:
041: protected Object clone() {
042: HashtableEntry entry = new HashtableEntry();
043: entry.hash = hash;
044: entry.key = key;
045: entry.value = value;
046: entry.next = (next != null) ? (HashtableEntry) next.clone()
047: : null;
048: return entry;
049: }
050: }
051:
052: /**
053: * The main hash-table implementation
054: */
055: public class Hashtable {
056:
057: private transient HashtableEntry table[]; // hash-table entries
058: private transient int count; // number of entries
059: private int threshold; // current size of hash-tabke
060: private float loadFactor; // load factor
061:
062: /**
063: * Constructs a new, empty hashtable with the specified initial
064: * capacity and the specified load factor.
065: */
066: public Hashtable(int initialCapacity, float loadFactor) {
067: if (initialCapacity <= 0)
068: initialCapacity = 11;
069: if (loadFactor <= 0.0)
070: loadFactor = 0.75f;
071: this .loadFactor = loadFactor;
072: table = new HashtableEntry[initialCapacity];
073: threshold = (int) (initialCapacity * loadFactor);
074: }
075:
076: /**
077: * Constructs a new, empty hashtable with the specified initial capacity
078: * and default load factor.
079: */
080: public Hashtable(int initialCapacity) {
081: this (initialCapacity, 0.75f);
082: }
083:
084: /**
085: * Constructs a new, empty hashtable with a default capacity and load
086: * factor.
087: */
088: public Hashtable() {
089: this (101, 0.75f);
090: }
091:
092: /**
093: * Returns the number of keys in this hashtable.
094: */
095: public int size() {
096: return count;
097: }
098:
099: /**
100: * Tests if this hashtable maps no keys to values.
101: */
102: public boolean isEmpty() {
103: return count == 0;
104: }
105:
106: /**
107: * Returns an enumeration of the keys in this hashtable.
108: */
109: public Enumeration keys() {
110: return new HashtableEnumerator(table, true);
111: }
112:
113: /**
114: * Returns an enumeration of the values in this hashtable.
115: * Use the Enumeration methods on the returned object to fetch the elements
116: * sequentially.
117: */
118: public Enumeration elements() {
119: return new HashtableEnumerator(table, false);
120: }
121:
122: /**
123: * Tests if some key maps into the specified value in this hashtable.
124: * This operation is more expensive than the <code>containsKey</code>
125: * method.
126: */
127: public boolean contains(Object value) {
128:
129: if (value == null)
130: throw new NullPointerException();
131:
132: int i;
133: HashtableEntry e;
134: HashtableEntry tab[] = table;
135:
136: for (i = tab.length; i-- > 0;) {
137: for (e = tab[i]; e != null; e = e.next) {
138: if (e.value.equals(value)) {
139: return true;
140: }
141: }
142: }
143: return false;
144: }
145:
146: /**
147: * Tests if the specified object is a key in this hashtable.
148: */
149: public boolean containsKey(Object key) {
150: HashtableEntry e;
151: HashtableEntry tab[] = table;
152: int hash = key.hashCode();
153: int index = (hash & 0x7FFFFFFF) % tab.length;
154:
155: for (e = tab[index]; e != null; e = e.next)
156: if ((e.hash == hash) && e.key.equals(key))
157: return true;
158:
159: return false;
160: }
161:
162: /**
163: * Returns the value to which the specified key is mapped in this hashtable.
164: */
165: public Object get(Object key) {
166: HashtableEntry e;
167: HashtableEntry tab[] = table;
168: int hash = key.hashCode();
169: int index = (hash & 0x7FFFFFFF) % tab.length;
170:
171: for (e = tab[index]; e != null; e = e.next)
172: if ((e.hash == hash) && e.key.equals(key))
173: return e.value;
174:
175: return null;
176: }
177:
178: /**
179: * Rehashes the contents of the hashtable into a hashtable with a
180: * larger capacity. This method is called automatically when the
181: * number of keys in the hashtable exceeds this hashtable's capacity
182: * and load factor.
183: */
184: protected void rehash() {
185: HashtableEntry e, old;
186: int i, index;
187: int oldCapacity = table.length;
188: HashtableEntry oldTable[] = table;
189:
190: int newCapacity = oldCapacity * 2 + 1;
191: HashtableEntry newTable[] = new HashtableEntry[newCapacity];
192:
193: threshold = (int) (newCapacity * loadFactor);
194: table = newTable;
195:
196: for (i = oldCapacity; i-- > 0;) {
197: for (old = oldTable[i]; old != null;) {
198: e = old;
199: old = old.next;
200: index = (e.hash & 0x7FFFFFFF) % newCapacity;
201: e.next = newTable[index];
202: newTable[index] = e;
203: }
204: }
205: }
206:
207: /**
208: * Maps the specified <code>key</code> to the specified
209: * <code>value</code> in this hashtable. Neither the key nor the
210: * value can be <code>null</code>.
211: * <p>
212: * The value can be retrieved by calling the <code>get</code> method
213: * with a key that is equal to the original key.
214: */
215: public Object put(Object key, Object value) {
216: // Make sure the value is not null
217: if (value == null)
218: throw new NullPointerException();
219:
220: // Makes sure the key is not already in the hashtable.
221: HashtableEntry e;
222: HashtableEntry tab[] = table;
223: int hash = key.hashCode();
224: int index = (hash & 0x7FFFFFFF) % tab.length;
225:
226: for (e = tab[index]; e != null; e = e.next) {
227: if ((e.hash == hash) && e.key.equals(key)) {
228: Object old = e.value;
229: e.value = value;
230: return old;
231: }
232: }
233:
234: // Rehash the table if the threshold is exceeded
235: if (count >= threshold) {
236: rehash();
237: return put(key, value);
238: }
239:
240: // Creates the new entry.
241: e = new HashtableEntry();
242: e.hash = hash;
243: e.key = key;
244: e.value = value;
245: e.next = tab[index];
246: tab[index] = e;
247: count++;
248: return null;
249: }
250:
251: /**
252: * Removes the key (and its corresponding value) from this
253: * hashtable. This method does nothing if the key is not in the hashtable.
254: */
255: public Object remove(Object key) {
256: HashtableEntry e, prev;
257: HashtableEntry tab[] = table;
258: int hash = key.hashCode();
259: int index = (hash & 0x7FFFFFFF) % tab.length;
260: for (e = tab[index], prev = null; e != null; prev = e, e = e.next) {
261: if ((e.hash == hash) && e.key.equals(key)) {
262: if (prev != null)
263: prev.next = e.next;
264: else
265: tab[index] = e.next;
266: count--;
267: return e.value;
268: }
269: }
270: return null;
271: }
272:
273: /**
274: * Clears this hashtable so that it contains no keys.
275: */
276: public void clear() {
277: HashtableEntry tab[] = table;
278: for (int index = tab.length; --index >= 0;)
279: tab[index] = null;
280: count = 0;
281: }
282:
283: /**
284: * Returns a rather long string representation of this hashtable.
285: * Handy for debugging - leave it here!!!
286: */
287: public String toString() {
288: int i;
289: int max = size() - 1;
290: StringBuffer buf = new StringBuffer();
291: Enumeration k = keys();
292: Enumeration e = elements();
293: buf.append("{");
294:
295: for (i = 0; i <= max; i++) {
296: String s1 = k.nextElement().toString();
297: String s2 = e.nextElement().toString();
298: buf.append(s1 + "=" + s2);
299: if (i < max)
300: buf.append(", ");
301: }
302: buf.append("}");
303: return buf.toString();
304: }
305:
306: /**
307: * A hashtable enumerator class. This class should remain opaque
308: * to the client. It will use the Enumeration interface.
309: */
310: class HashtableEnumerator implements Enumeration {
311: boolean keys;
312: int index;
313: HashtableEntry table[];
314: HashtableEntry entry;
315:
316: HashtableEnumerator(HashtableEntry table[], boolean keys) {
317: this .table = table;
318: this .keys = keys;
319: this .index = table.length;
320: }
321:
322: public boolean hasMoreElements() {
323: if (entry != null) {
324: return true;
325: }
326: while (index-- > 0) {
327: if ((entry = table[index]) != null) {
328: return true;
329: }
330: }
331: return false;
332: }
333:
334: public Object nextElement() {
335: if (entry == null) {
336: while ((index-- > 0)
337: && ((entry = table[index]) == null))
338: ;
339: }
340: if (entry != null) {
341: HashtableEntry e = entry;
342: entry = e.next;
343: return keys ? e.key : e.value;
344: }
345: return null;
346: }
347: }
348:
349: }
|