View Javadoc
1   /*
2    * reserved comment block
3    * DO NOT REMOVE OR ALTER!
4    */
5   /*
6    * Copyright 2001-2004 The Apache Software Foundation.
7    *
8    * Licensed under the Apache License, Version 2.0 (the "License");
9    * you may not use this file except in compliance with the License.
10   * You may obtain a copy of the License at
11   *
12   *     http://www.apache.org/licenses/LICENSE-2.0
13   *
14   * Unless required by applicable law or agreed to in writing, software
15   * distributed under the License is distributed on an "AS IS" BASIS,
16   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
17   * See the License for the specific language governing permissions and
18   * limitations under the License.
19   */
20  /*
21   * $Id: Hashtable.java,v 1.2.4.1 2005/09/06 11:05:18 pvedula Exp $
22   */
23  
24  package com.sun.org.apache.xalan.internal.xsltc.runtime;
25  
26  import java.util.Enumeration;
27  
28  /**
29   * IMPORTANT NOTE:
30   * This code was taken from Sun's Java1.1 JDK java.util.HashTable.java
31   * All "synchronized" keywords and some methods we do not need have been
32   * all been removed.
33   */
34  
35  /**
36   * Object that wraps entries in the hash-table
37   * @author Morten Jorgensen
38   */
39  class HashtableEntry {
40      int hash;
41      Object key;
42      Object value;
43      HashtableEntry next;
44  
45      protected Object clone() {
46          HashtableEntry entry = new HashtableEntry();
47          entry.hash = hash;
48          entry.key = key;
49          entry.value = value;
50          entry.next = (next != null) ? (HashtableEntry)next.clone() : null;
51          return entry;
52      }
53  }
54  
55  /**
56   * The main hash-table implementation
57   */
58  public class Hashtable {
59  
60      private transient HashtableEntry table[]; // hash-table entries
61      private transient int count;              // number of entries
62      private int threshold;                    // current size of hash-tabke
63      private float loadFactor;                 // load factor
64  
65      /**
66       * Constructs a new, empty hashtable with the specified initial
67       * capacity and the specified load factor.
68       */
69      public Hashtable(int initialCapacity, float loadFactor) {
70          if (initialCapacity <= 0) initialCapacity = 11;
71          if (loadFactor <= 0.0) loadFactor = 0.75f;
72          this.loadFactor = loadFactor;
73          table = new HashtableEntry[initialCapacity];
74          threshold = (int)(initialCapacity * loadFactor);
75      }
76  
77      /**
78       * Constructs a new, empty hashtable with the specified initial capacity
79       * and default load factor.
80       */
81      public Hashtable(int initialCapacity) {
82          this(initialCapacity, 0.75f);
83      }
84  
85      /**
86       * Constructs a new, empty hashtable with a default capacity and load
87       * factor.
88       */
89      public Hashtable() {
90          this(101, 0.75f);
91      }
92  
93      /**
94       * Returns the number of keys in this hashtable.
95       */
96      public int size() {
97          return count;
98      }
99  
100     /**
101      * Tests if this hashtable maps no keys to values.
102      */
103     public boolean isEmpty() {
104         return count == 0;
105     }
106 
107     /**
108      * Returns an enumeration of the keys in this hashtable.
109      */
110     public Enumeration keys() {
111         return new HashtableEnumerator(table, true);
112     }
113 
114     /**
115      * Returns an enumeration of the values in this hashtable.
116      * Use the Enumeration methods on the returned object to fetch the elements
117      * sequentially.
118      */
119     public Enumeration elements() {
120         return new HashtableEnumerator(table, false);
121     }
122 
123     /**
124      * Tests if some key maps into the specified value in this hashtable.
125      * This operation is more expensive than the <code>containsKey</code>
126      * method.
127      */
128     public boolean contains(Object value) {
129 
130         if (value == null) 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) throw new NullPointerException();
218 
219         // Makes sure the key is not already in the hashtable.
220         HashtableEntry e;
221         HashtableEntry tab[] = table;
222         int hash = key.hashCode();
223         int index = (hash & 0x7FFFFFFF) % tab.length;
224 
225         for (e = tab[index] ; e != null ; e = e.next) {
226             if ((e.hash == hash) && e.key.equals(key)) {
227                 Object old = e.value;
228                 e.value = value;
229                 return old;
230             }
231         }
232 
233         // Rehash the table if the threshold is exceeded
234         if (count >= threshold) {
235             rehash();
236             return put(key, value);
237         }
238 
239         // Creates the new entry.
240         e = new HashtableEntry();
241         e.hash = hash;
242         e.key = key;
243         e.value = value;
244         e.next = tab[index];
245         tab[index] = e;
246         count++;
247         return null;
248     }
249 
250     /**
251      * Removes the key (and its corresponding value) from this
252      * hashtable. This method does nothing if the key is not in the hashtable.
253      */
254     public Object remove(Object key) {
255         HashtableEntry e, prev;
256         HashtableEntry tab[] = table;
257         int hash = key.hashCode();
258         int index = (hash & 0x7FFFFFFF) % tab.length;
259         for (e = tab[index], prev = null ; e != null ; prev = e, e = e.next) {
260             if ((e.hash == hash) && e.key.equals(key)) {
261                 if (prev != null)
262                     prev.next = e.next;
263                 else
264                     tab[index] = e.next;
265                 count--;
266                 return e.value;
267             }
268         }
269         return null;
270     }
271 
272     /**
273      * Clears this hashtable so that it contains no keys.
274      */
275     public void clear() {
276         HashtableEntry tab[] = table;
277         for (int index = tab.length; --index >= 0; )
278             tab[index] = null;
279         count = 0;
280     }
281 
282     /**
283      * Returns a rather long string representation of this hashtable.
284      * Handy for debugging - leave it here!!!
285      */
286     public String toString() {
287         int i;
288         int max = size() - 1;
289         StringBuffer buf = new StringBuffer();
290         Enumeration k = keys();
291         Enumeration e = elements();
292         buf.append("{");
293 
294         for (i = 0; i <= max; i++) {
295             String s1 = k.nextElement().toString();
296             String s2 = e.nextElement().toString();
297             buf.append(s1).append('=').append(s2);
298             if (i < max) buf.append(", ");
299         }
300         buf.append("}");
301         return buf.toString();
302     }
303 
304     /**
305      * A hashtable enumerator class.  This class should remain opaque
306      * to the client. It will use the Enumeration interface.
307      */
308     class HashtableEnumerator implements Enumeration {
309         boolean keys;
310         int index;
311         HashtableEntry table[];
312         HashtableEntry entry;
313 
314         HashtableEnumerator(HashtableEntry table[], boolean keys) {
315             this.table = table;
316             this.keys = keys;
317             this.index = table.length;
318         }
319 
320         public boolean hasMoreElements() {
321             if (entry != null) {
322                 return true;
323             }
324             while (index-- > 0) {
325                 if ((entry = table[index]) != null) {
326                     return true;
327                 }
328             }
329             return false;
330         }
331 
332         public Object nextElement() {
333             if (entry == null) {
334                 while ((index-- > 0) && ((entry = table[index]) == null));
335             }
336             if (entry != null) {
337                 HashtableEntry e = entry;
338                 entry = e.next;
339                 return keys ? e.key : e.value;
340             }
341             return null;
342         }
343     }
344 
345 }