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