001    package railo.commons.collections;
002    
003    import java.io.IOException;
004    import java.util.AbstractCollection;
005    import java.util.AbstractSet;
006    import java.util.Collection;
007    import java.util.ConcurrentModificationException;
008    import java.util.Dictionary;
009    import java.util.Enumeration;
010    import java.util.Iterator;
011    import java.util.Map;
012    import java.util.NoSuchElementException;
013    import java.util.Set;
014    
015    /**
016     * This class implements a hashtable, which maps keys to values. Any 
017     * non-<code>null</code> object can be used as a key or as a value. <p>
018     *
019     * To successfully store and retrieve objects from a hashtable, the 
020     * objects used as keys must implement the <code>hashCode</code> 
021     * method and the <code>equals</code> method. <p>
022     *
023     * An instance of <code>Hashtable</code> has two parameters that affect its
024     * performance: <i>initial capacity</i> and <i>load factor</i>.  The
025     * <i>capacity</i> is the number of <i>buckets</i> in the hash table, and the
026     * <i>initial capacity</i> is simply the capacity at the time the hash table
027     * is created.  Note that the hash table is <i>open</i>: in the case a "hash
028     * collision", a single bucket stores multiple entries, which must be searched
029     * sequentially.  The <i>load factor</i> is a measure of how full the hash
030     * table is allowed to get before its capacity is automatically increased.
031     * When the number of entries in the hashtable exceeds the product of the load
032     * factor and the current capacity, the capacity is increased by calling the
033     * <code>rehash</code> method.<p>
034     *
035     * Generally, the default load factor (.75) offers a good tradeoff between
036     * time and space costs.  Higher values decrease the space overhead but
037     * increase the time cost to look up an entry (which is reflected in most
038     * <tt>Hashtable</tt> operations, including <tt>get</tt> and <tt>put</tt>).<p>
039     *
040     * The initial capacity controls a tradeoff between wasted space and the
041     * need for <code>rehash</code> operations, which are time-consuming.
042     * No <code>rehash</code> operations will <i>ever</i> occur if the initial
043     * capacity is greater than the maximum number of entries the
044     * <tt>Hashtable</tt> will contain divided by its load factor.  However,
045     * setting the initial capacity too high can waste space.<p>
046     *
047     * If many entries are to be made into a <code>Hashtable</code>, 
048     * creating it with a sufficiently large capacity may allow the 
049     * entries to be inserted more efficiently than letting it perform 
050     * automatic rehashing as needed to grow the table. <p>
051     *
052     * This example creates a hashtable of numbers. It uses the names of 
053     * the numbers as keys:
054     * <p><blockquote><pre>
055     *     Hashtable numbers = new Hashtable();
056     *     numbers.put("one", new Integer(1));
057     *     numbers.put("two", new Integer(2));
058     *     numbers.put("three", new Integer(3));
059     * </pre></blockquote>
060     * <p>
061     * To retrieve a number, use the following code: 
062     * <p><blockquote><pre>
063     *     Integer n = (Integer)numbers.get("two");
064     *     if (n != null) {
065     *         System.out.println("two = " + n);
066     *     }
067     * </pre></blockquote>
068     * <p>
069     * As of the Java 2 platform v1.2, this class has been retrofitted to
070     * implement Map, so that it becomes a part of Java's collection framework.
071     * Unlike the new collection implementations, Hashtable is synchronized.<p>
072     *
073     * The Iterators returned by the iterator and listIterator methods
074     * of the Collections returned by all of Hashtable's "collection view methods"
075     * are <em>fail-fast</em>: if the Hashtable is structurally modified
076     * at any time after the Iterator is created, in any way except through the
077     * Iterator's own remove or add methods, the Iterator will throw a
078     * ConcurrentModificationException.  Thus, in the face of concurrent
079     * modification, the Iterator fails quickly and cleanly, rather than risking
080     * arbitrary, non-deterministic behavior at an undetermined time in the future.
081     * The Enumerations returned by Hashtable's keys and values methods are
082     * <em>not</em> fail-fast.
083     *
084     * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
085     * as it is, generally speaking, impossible to make any hard guarantees in the
086     * presence of unsynchronized concurrent modification.  Fail-fast iterators
087     * throw <tt>ConcurrentModificationException</tt> on a best-effort basis. 
088     * Therefore, it would be wrong to write a program that depended on this
089     * exception for its correctness: <i>the fail-fast behavior of iterators
090     * should be used only to detect bugs.</i>
091     */
092    public final class HTNS extends Dictionary implements Map, Cloneable,
093                                                       java.io.Serializable {
094        /**
095         * The hash table data.
096         */
097        private transient Entry table[];
098    
099        /**
100         * The total number of entries in the hash table.
101         */
102        private transient int count;
103    
104        /**
105         * The table is rehashed when its size exceeds this threshold.  (The
106         * value of this field is (int)(capacity * loadFactor).)
107         *
108         * @serial
109         */
110        private int threshold;
111                                 
112        /**
113         * The load factor for the hashtable.
114         *
115         * @serial
116         */
117        private float loadFactor;
118    
119        /**
120         * The number of times this Hashtable has been structurally modified
121         * Structural modifications are those that change the number of entries in
122         * the Hashtable or otherwise modify its internal structure (e.g.,
123         * rehash).  This field is used to make iterators on Collection-views of
124         * the Hashtable fail-fast.  (See ConcurrentModificationException).
125         */
126        private transient int modCount = 0;
127    
128        /** use serialVersionUID from JDK 1.0.2 for interoperability */
129        private static final long serialVersionUID = 1421746759512286392L;
130    
131        /**
132         * Constructs a new, empty hashtable with the specified initial 
133         * capacity and the specified load factor.
134         *
135         * @param      initialCapacity   the initial capacity of the hashtable.
136         * @param      loadFactor        the load factor of the hashtable.
137         * @exception  IllegalArgumentException  if the initial capacity is less
138         *             than zero, or if the load factor is nonpositive.
139         */
140        public HTNS(int initialCapacity, float loadFactor) {
141        if (initialCapacity < 0)
142            throw new IllegalArgumentException("Illegal Capacity: "+
143                                                   initialCapacity);
144            if (loadFactor <= 0 || Float.isNaN(loadFactor))
145                throw new IllegalArgumentException("Illegal Load: "+loadFactor);
146    
147            if (initialCapacity==0)
148                initialCapacity = 1;
149        this.loadFactor = loadFactor;
150        table = new Entry[initialCapacity];
151        threshold = (int)(initialCapacity * loadFactor);
152        }
153    
154        /**
155         * Constructs a new, empty hashtable with the specified initial capacity
156         * and default load factor, which is <tt>0.75</tt>.
157         *
158         * @param     initialCapacity   the initial capacity of the hashtable.
159         * @exception IllegalArgumentException if the initial capacity is less
160         *              than zero.
161         */
162        public HTNS(int initialCapacity) {
163        this(initialCapacity, 0.75f);
164        }
165    
166        /**
167         * Constructs a new, empty hashtable with a default initial capacity (11)
168         * and load factor, which is <tt>0.75</tt>. 
169         */
170        public HTNS() {
171            this(11, 0.75f);
172        }
173    
174        /**
175         * Constructs a new hashtable with the same mappings as the given 
176         * Map.  The hashtable is created with an initial capacity sufficient to
177         * hold the mappings in the given Map and a default load factor, which is
178         * <tt>0.75</tt>.
179         *
180         * @param t the map whose mappings are to be placed in this map.
181         * @throws NullPointerException if the specified map is null.
182         *
183         */
184        public HTNS(Map t) {
185        this(Math.max(2*t.size(), 11), 0.75f);
186        putAll(t);
187        }
188    
189        /**
190         * Returns the number of keys in this hashtable.
191         *
192         * @return  the number of keys in this hashtable.
193         */
194        public int size() {
195        return count;
196        }
197    
198        /**
199         * Tests if this hashtable maps no keys to values.
200         *
201         * @return  <code>true</code> if this hashtable maps no keys to values;
202         *          <code>false</code> otherwise.
203         */
204        public boolean isEmpty() {
205        return count == 0;
206        }
207    
208        /**
209         * Returns an enumeration of the keys in this hashtable.
210         *
211         * @return  an enumeration of the keys in this hashtable.
212         * @see     Enumeration
213         * @see     #elements()
214         * @see #keySet()
215         * @see Map
216         */
217        public Enumeration keys() {
218        return getEnumeration(KEYS);
219        }
220    
221        /**
222         * Returns an enumeration of the values in this hashtable.
223         * Use the Enumeration methods on the returned object to fetch the elements
224         * sequentially.
225         *
226         * @return  an enumeration of the values in this hashtable.
227         * @see     java.util.Enumeration
228         * @see     #keys()
229         * @see #values()
230         * @see Map
231         */
232        public Enumeration elements() {
233        return getEnumeration(VALUES);
234        }
235    
236        /**
237         * Tests if some key maps into the specified value in this hashtable.
238         * This operation is more expensive than the <code>containsKey</code>
239         * method.<p>
240         *
241         * Note that this method is identical in functionality to containsValue,
242         * (which is part of the Map interface in the collections framework).
243         * 
244         * @param      value   a value to search for.
245         * @return     <code>true</code> if and only if some key maps to the
246         *             <code>value</code> argument in this hashtable as 
247         *             determined by the <tt>equals</tt> method;
248         *             <code>false</code> otherwise.
249         * @exception  NullPointerException  if the value is <code>null</code>.
250         * @see        #containsKey(Object)
251         * @see        #containsValue(Object)
252         * @see    Map
253         */
254        public boolean contains(Object value) {
255                if (value == null) {
256                    throw new NullPointerException();
257                }
258            
259                Entry tab[] = table;
260                for (int i = tab.length ; i-- > 0 ;) {
261                    for (Entry e = tab[i] ; e != null ; e = e.next) {
262                    if (e.value.equals(value)) {
263                        return true;
264                    }
265                    }
266                }
267                return false;
268        }
269    
270        /**
271         * Returns true if this Hashtable maps one or more keys to this value.<p>
272         *
273         * Note that this method is identical in functionality to contains
274         * (which predates the Map interface).
275         *
276         * @param value value whose presence in this Hashtable is to be tested.
277         * @return <tt>true</tt> if this map maps one or more keys to the
278         *         specified value.
279         * @see    Map
280    *
281         */
282        public boolean containsValue(Object value) {
283        return contains(value);
284        }
285    
286        /**
287         * Tests if the specified object is a key in this hashtable.
288         * 
289         * @param   key   possible key.
290         * @return  <code>true</code> if and only if the specified object 
291         *          is a key in this hashtable, as determined by the 
292         *          <tt>equals</tt> method; <code>false</code> otherwise.
293         * @see     #contains(Object)
294         */
295        public boolean containsKey(Object key) {
296        Entry tab[] = table;
297        int hash = key.hashCode();
298        int index = (hash & 0x7FFFFFFF) % tab.length;
299        for (Entry e = tab[index] ; e != null ; e = e.next) {
300            if ((e.hash == hash) && e.key.equals(key)) {
301            return true;
302            }
303        }
304        return false;
305        }
306    
307        /**
308         * Returns the value to which the specified key is mapped in this hashtable.
309         *
310         * @param   key   a key in the hashtable.
311         * @return  the value to which the key is mapped in this hashtable;
312         *          <code>null</code> if the key is not mapped to any value in
313         *          this hashtable.
314         * @see     #put(Object, Object)
315         */
316        public Object get(Object key) {
317                Entry tab[] = table;
318                int hash = key.hashCode();
319                //int index = (hash & 0x7FFFFFFF) % tab.length;
320                int index = (hash) % tab.length;
321                for (Entry e = tab[index] ; e != null ; e = e.next) {
322                    if ((e.hash == hash)) {
323                            return e.value;
324                    }
325                }
326                return null;
327        }
328    
329        /**
330         * Increases the capacity of and internally reorganizes this 
331         * hashtable, in order to accommodate and access its entries more 
332         * efficiently.  This method is called automatically when the 
333         * number of keys in the hashtable exceeds this hashtable's capacity 
334         * and load factor. 
335         */
336        protected void rehash() {
337        int oldCapacity = table.length;
338        Entry oldMap[] = table;
339    
340        int newCapacity = oldCapacity * 2 + 1;
341        Entry newMap[] = new Entry[newCapacity];
342    
343        modCount++;
344        threshold = (int)(newCapacity * loadFactor);
345        table = newMap;
346    
347        for (int i = oldCapacity ; i-- > 0 ;) {
348            for (Entry old = oldMap[i] ; old != null ; ) {
349            Entry e = old;
350            old = old.next;
351    
352            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
353            e.next = newMap[index];
354            newMap[index] = e;
355            }
356        }
357        }
358    
359        /**
360         * Maps the specified <code>key</code> to the specified 
361         * <code>value</code> in this hashtable. Neither the key nor the 
362         * value can be <code>null</code>. <p>
363         *
364         * The value can be retrieved by calling the <code>get</code> method 
365         * with a key that is equal to the original key. 
366         *
367         * @param      key     the hashtable key.
368         * @param      value   the value.
369         * @return     the previous value of the specified key in this hashtable,
370         *             or <code>null</code> if it did not have one.
371         * @exception  NullPointerException  if the key or value is
372         *               <code>null</code>.
373         * @see     Object#equals(Object)
374         * @see     #get(Object)
375         */
376        public Object put(Object key, Object value) {
377                // Make sure the value is not null
378                if (value == null) {
379                    return remove(key);
380                }
381            
382                // Makes sure the key is not already in the hashtable.
383                Entry tab[] = table;
384                int hash = key.hashCode();
385                int index = (hash & 0x7FFFFFFF) % tab.length;
386                for (Entry e = tab[index] ; e != null ; e = e.next) {
387                    if ((e.hash == hash) && e.key.equals(key)) {
388                    Object old = e.value;
389                    e.value = value;
390                    return old;
391                }
392        }
393    
394        modCount++;
395        if (count >= threshold) {
396            // Rehash the table if the threshold is exceeded
397            rehash();
398    
399                tab = table;
400                index = (hash & 0x7FFFFFFF) % tab.length;
401        } 
402    
403        // Creates the new entry.
404        Entry e = new Entry(hash, key, value, tab[index]);
405        tab[index] = e;
406        count++;
407        return null;
408        }
409    
410        /**
411         * Removes the key (and its corresponding value) from this 
412         * hashtable. This method does nothing if the key is not in the hashtable.
413         *
414         * @param   key   the key that needs to be removed.
415         * @return  the value to which the key had been mapped in this hashtable,
416         *          or <code>null</code> if the key did not have a mapping.
417         */
418        public Object remove(Object key) {
419        Entry tab[] = table;
420        int hash = key.hashCode();
421        int index = (hash & 0x7FFFFFFF) % tab.length;
422        for (Entry e = tab[index], prev = null ; e != null ; prev = e, e = e.next) {
423            if ((e.hash == hash) && e.key.equals(key)) {
424            modCount++;
425            if (prev != null) {
426                prev.next = e.next;
427            } else {
428                tab[index] = e.next;
429            }
430            count--;
431            Object oldValue = e.value;
432            e.value = null;
433            return oldValue;
434            }
435        }
436        return null;
437        }
438    
439        /**
440         * Copies all of the mappings from the specified Map to this Hashtable
441         * These mappings will replace any mappings that this Hashtable had for any
442         * of the keys currently in the specified Map. 
443         *
444         * @param t Mappings to be stored in this map.
445         * @throws NullPointerException if the specified map is null.
446    *
447         */
448        public void putAll(Map t) {
449        Iterator i = t.entrySet().iterator();
450        while (i.hasNext()) {
451            Map.Entry e = (Map.Entry) i.next();
452            put(e.getKey(), e.getValue());
453        }
454        }
455    
456        /**
457         * Clears this hashtable so that it contains no keys. 
458         */
459        public void clear() {
460        Entry tab[] = table;
461        modCount++;
462        for (int index = tab.length; --index >= 0; )
463            tab[index] = null;
464        count = 0;
465        }
466    
467        /**
468         * Creates a shallow copy of this hashtable. All the structure of the 
469         * hashtable itself is copied, but the keys and values are not cloned. 
470         * This is a relatively expensive operation.
471         *
472         * @return  a clone of the hashtable.
473         */
474        public Object clone() {
475        try { 
476            HTNS t = (HTNS)super.clone();
477            t.table = new Entry[table.length];
478            for (int i = table.length ; i-- > 0 ; ) {
479            t.table[i] = (table[i] != null) 
480                ? (Entry)table[i].clone() : null;
481            }
482            t.keySet = null;
483            t.entrySet = null;
484                t.values = null;
485            t.modCount = 0;
486            return t;
487        } catch (CloneNotSupportedException e) { 
488            // this shouldn't happen, since we are Cloneable
489            throw new InternalError();
490        }
491        }
492    
493        /**
494         * Returns a string representation of this <tt>Hashtable</tt> object 
495         * in the form of a set of entries, enclosed in braces and separated 
496         * by the ASCII characters "<tt>,&nbsp;</tt>" (comma and space). Each 
497         * entry is rendered as the key, an equals sign <tt>=</tt>, and the 
498         * associated element, where the <tt>toString</tt> method is used to 
499         * convert the key and element to strings. <p>Overrides to 
500         * <tt>toString</tt> method of <tt>Object</tt>.
501         *
502         * @return  a string representation of this hashtable.
503         */
504        public String toString() {
505        int max = size() - 1;
506        StringBuffer buf = new StringBuffer();
507        Iterator it = entrySet().iterator();
508    
509        buf.append("{");
510        for (int i = 0; i <= max; i++) {
511            Map.Entry e = (Map.Entry) (it.next());
512                Object key = e.getKey();
513                Object value = e.getValue();
514                buf.append((key   == this ? "(this Map)" : key) + "=" + 
515                           (value == this ? "(this Map)" : value));
516    
517            if (i < max)
518            buf.append(", ");
519        }
520        buf.append("}");
521        return buf.toString();
522        }
523    
524    
525        private Enumeration getEnumeration(int type) {
526            if (count == 0) {
527                return emptyEnumerator;
528            } 
529            return new Enumerator(type, false);
530            
531        }
532    
533        private Iterator getIterator(int type) {
534            if (count == 0) {
535                return emptyIterator;
536            } 
537            return new Enumerator(type, true);
538        }
539    
540        // Views
541    
542        /**
543         * Each of these fields are initialized to contain an instance of the
544         * appropriate view the first time this view is requested.  The views are
545         * stateless, so there's no reason to create more than one of each.
546         */
547        private transient volatile Set keySet = null;
548        private transient volatile Set entrySet = null;
549        private transient volatile Collection values = null;
550    
551        /**
552         * Returns a Set view of the keys contained in this Hashtable.  The Set
553         * is backed by the Hashtable, so changes to the Hashtable are reflected
554         * in the Set, and vice-versa.  The Set supports element removal
555         * (which removes the corresponding entry from the Hashtable), but not
556         * element addition.
557         *
558         * @return a set view of the keys contained in this map.
559    *
560         */
561        public Set keySet() {
562        if (keySet == null)
563            keySet = Collections.synchronizedSet(new KeySet(), this);
564        return keySet;
565        }
566    
567        private class KeySet extends AbstractSet {
568            /**
569             * @see java.util.Set#iterator()
570             */
571            public Iterator iterator() {
572            return getIterator(KEYS);
573            }
574            /**
575             * @see java.util.Set#size()
576             */
577            public int size() {
578                return count;
579            }
580            /**
581             * @see java.util.Set#contains(java.lang.Object)
582             */
583            public boolean contains(Object o) {
584                return containsKey(o);
585            }
586            /**
587             * @see java.util.Set#remove(java.lang.Object)
588             */
589            public boolean remove(Object o) {
590                return HTNS.this.remove(o) != null;
591            }
592            /**
593             * @see java.util.Set#clear()
594             */
595            public void clear() {
596                HTNS.this.clear();
597            }
598        }
599    
600        /**
601         * Returns a Set view of the entries contained in this Hashtable.
602         * Each element in this collection is a Map.Entry.  The Set is
603         * backed by the Hashtable, so changes to the Hashtable are reflected in
604         * the Set, and vice-versa.  The Set supports element removal
605         * (which removes the corresponding entry from the Hashtable),
606         * but not element addition.
607         *
608         * @return a set view of the mappings contained in this map.
609         * @see   Map.Entry
610    *
611         */
612        public Set entrySet() {
613        if (entrySet==null)
614            entrySet = Collections.synchronizedSet(new EntrySet(), this);
615        return entrySet;
616        }
617    
618        private class EntrySet extends AbstractSet {
619            /**
620             * @see java.util.Set#iterator()
621             */
622            public Iterator iterator() {
623            return getIterator(ENTRIES);
624            }
625    
626            /**
627             * @see java.util.Set#contains(java.lang.Object)
628             */
629            public boolean contains(Object o) {
630                if (!(o instanceof Map.Entry))
631                    return false;
632                Map.Entry entry = (Map.Entry)o;
633                Object key = entry.getKey();
634                Entry tab[] = table;
635                int hash = key.hashCode();
636                int index = (hash & 0x7FFFFFFF) % tab.length;
637    
638                for (Entry e = tab[index]; e != null; e = e.next)
639                    if (e.hash==hash && e.equals(entry))
640                        return true;
641                return false;
642            }
643    
644            /**
645             * @see java.util.Set#remove(java.lang.Object)
646             */
647            public boolean remove(Object o) {
648                if (!(o instanceof Map.Entry))
649                    return false;
650                Map.Entry entry = (Map.Entry)o;
651                Object key = entry.getKey();
652                Entry tab[] = table;
653                int hash = key.hashCode();
654                int index = (hash & 0x7FFFFFFF) % tab.length;
655    
656                for (Entry e = tab[index], prev = null; e != null;
657                     prev = e, e = e.next) {
658                    if (e.hash==hash && e.equals(entry)) {
659                        modCount++;
660                        if (prev != null)
661                            prev.next = e.next;
662                        else
663                            tab[index] = e.next;
664    
665                        count--;
666                        e.value = null;
667                        return true;
668                    }
669                }
670                return false;
671            }
672    
673            /**
674             * @see java.util.Set#size()
675             */
676            public int size() {
677                return count;
678            }
679    
680            /**
681             * @see java.util.Set#clear()
682             */
683            public void clear() {
684                HTNS.this.clear();
685            }
686        }
687    
688        /**
689         * Returns a Collection view of the values contained in this Hashtable.
690         * The Collection is backed by the Hashtable, so changes to the Hashtable
691         * are reflected in the Collection, and vice-versa.  The Collection
692         * supports element removal (which removes the corresponding entry from
693         * the Hashtable), but not element addition.
694         *
695         * @return a collection view of the values contained in this map.
696    *
697         */
698        public Collection values() {
699        if (values==null)
700            values = Collections.synchronizedCollection(new ValueCollection(),
701                                                            this);
702            return values;
703        }
704    
705        private class ValueCollection extends AbstractCollection {
706            /**
707             * @see java.util.AbstractCollection#iterator()
708             */
709            public Iterator iterator() {
710            return getIterator(VALUES);
711            }
712            /**
713             * @see java.util.AbstractCollection#size()
714             */
715            public int size() {
716                return count;
717            }
718            /**
719             * @see java.util.AbstractCollection#contains(java.lang.Object)
720             */
721            public boolean contains(Object o) {
722                return containsValue(o);
723            }
724            /**
725             * @see java.util.AbstractCollection#clear()
726             */
727            public void clear() {
728                HTNS.this.clear();
729            }
730        }
731    
732        // Comparison and hashing
733    
734        /**
735         * Compares the specified Object with this Map for equality,
736         * as per the definition in the Map interface.
737         *
738         * @param  o object to be compared for equality with this Hashtable
739         * @return true if the specified Object is equal to this Map.
740         * @see Map#equals(Object)
741    *
742         */
743        public boolean equals(Object o) {
744        if (o == this)
745            return true;
746    
747        if (!(o instanceof Map))
748            return false;
749        Map t = (Map) o;
750        if (t.size() != size())
751            return false;
752    
753            try {
754                Iterator i = entrySet().iterator();
755                while (i.hasNext()) {
756                    Map.Entry e = (Map.Entry) i.next();
757                    Object key = e.getKey();
758                    Object value = e.getValue();
759                    if (value == null) {
760                        if (!(t.get(key)==null && t.containsKey(key)))
761                            return false;
762                    } else {
763                        if (!value.equals(t.get(key)))
764                            return false;
765                    }
766                }
767            } catch(ClassCastException unused)   {
768                return false;
769            } catch(NullPointerException unused) {
770                return false;
771            }
772    
773        return true;
774        }
775    
776        /**
777         * Returns the hash code value for this Map as per the definition in the
778         * Map interface.
779         *
780         * @see Map#hashCode()
781    *
782         */
783        public int hashCode() {
784            /*
785             * This code detects the recursion caused by computing the hash code
786             * of a self-referential hash table and prevents the stack overflow
787             * that would otherwise result.  This allows certain 1.1-era
788             * applets with self-referential hash tables to work.  This code
789             * abuses the loadFactor field to do double-duty as a hashCode
790             * in progress flag, so as not to worsen the space performance.
791             * A negative load factor indicates that hash code computation is
792             * in progress.
793             */
794            int h = 0;
795            if (count == 0 || loadFactor < 0)
796                return h;  // Returns zero
797    
798            loadFactor = -loadFactor;  // Mark hashCode computation in progress
799            Entry tab[] = table;
800            for (int i = 0; i < tab.length; i++)
801                for (Entry e = tab[i]; e != null; e = e.next)
802                    h += e.key.hashCode() ^ e.value.hashCode();
803            loadFactor = -loadFactor;  // Mark hashCode computation complete
804    
805        return h;
806        }
807    
808        /**
809         * Save the state of the Hashtable to a stream (i.e., serialize it).
810         * @param s
811         * @throws IOException
812         *
813         * @serialData The <i>capacity</i> of the Hashtable (the length of the
814         *         bucket array) is emitted (int), followed  by the
815         *         <i>size</i> of the Hashtable (the number of key-value
816         *         mappings), followed by the key (Object) and value (Object)
817         *         for each key-value mapping represented by the Hashtable
818         *         The key-value mappings are emitted in no particular order.
819         */
820        private void writeObject(java.io.ObjectOutputStream s)
821            throws IOException
822        {
823        // Write out the length, threshold, loadfactor
824        s.defaultWriteObject();
825    
826        // Write out length, count of elements and then the key/value objects
827        s.writeInt(table.length);
828        s.writeInt(count);
829        for (int index = table.length-1; index >= 0; index--) {
830            Entry entry = table[index];
831    
832            while (entry != null) {
833            s.writeObject(entry.key);
834            s.writeObject(entry.value);
835            entry = entry.next;
836            }
837        }
838        }
839    
840        /**
841         * Reconstitute the Hashtable from a stream (i.e., deserialize it).
842         * @param s
843         * @throws IOException
844         * @throws ClassNotFoundException
845         */
846        private void readObject(java.io.ObjectInputStream s)
847             throws IOException, ClassNotFoundException
848        {
849        // Read in the length, threshold, and loadfactor
850        s.defaultReadObject();
851    
852        // Read the original length of the array and number of elements
853        int origlength = s.readInt();
854        int elements = s.readInt();
855    
856        // Compute new size with a bit of room 5% to grow but
857        // No larger than the original size.  Make the length
858        // odd if it's large enough, this helps distribute the entries.
859        // Guard against the length ending up zero, that's not valid.
860        int length = (int)(elements * loadFactor) + (elements / 20) + 3;
861        if (length > elements && (length & 1) == 0)
862            length--;
863        if (origlength > 0 && length > origlength)
864            length = origlength;
865    
866        table = new Entry[length];
867        count = 0;
868    
869        // Read the number of elements and then all the key/value objects
870        for (; elements > 0; elements--) {
871            Object key = s.readObject();
872            Object value = s.readObject();
873            put(key, value);
874        }
875        }
876    
877    
878        /**
879         * Hashtable collision list.
880         */
881        private static class Entry implements Map.Entry {
882        int hash;
883        Object key;
884        Object value;
885        Entry next;
886    
887        /**
888         * @param hash
889         * @param key
890         * @param value
891         * @param next
892         */
893        protected Entry(int hash, Object key, Object value, Entry next) {
894            this.hash = hash;
895            this.key = key;
896            this.value = value;
897            this.next = next;
898        }
899    
900        /**
901         * @see java.lang.Object#clone()
902         */
903        protected Object clone() {
904            return new Entry(hash, key, value,
905                     (next==null ? null : (Entry)next.clone()));
906        }
907    
908        // Map.Entry Ops 
909    
910        /**
911         * @see java.util.Map.Entry#getKey()
912         */
913        public Object getKey() {
914            return key;
915        }
916    
917        /**
918         * @see java.util.Map.Entry#getValue()
919         */
920        public Object getValue() {
921            return value;
922        }
923    
924        /**
925         * @see java.util.Map.Entry#setValue(java.lang.Object)
926         */
927        public Object setValue(Object value) {
928            if (value == null)
929            throw new NullPointerException();
930    
931            Object oldValue = this.value;
932            this.value = value;
933            return oldValue;
934        }
935    
936        /**
937         * @see java.util.Map.Entry#equals(java.lang.Object)
938         */
939        public boolean equals(Object o) {
940            if (!(o instanceof Map.Entry))
941            return false;
942            Map.Entry e = (Map.Entry)o;
943    
944            return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
945               (value==null ? e.getValue()==null : value.equals(e.getValue()));
946        }
947    
948        /**
949         * @see java.util.Map.Entry#hashCode()
950         */
951        public int hashCode() {
952            return hash ^ (value==null ? 0 : value.hashCode());
953        }
954    
955        /**
956         * @see java.lang.Object#toString()
957         */
958        public String toString() {
959            return key.toString()+"="+value.toString();
960        }
961        }
962    
963        // Types of Enumerations/Iterations
964        private static final int KEYS = 0;
965        private static final int VALUES = 1;
966        private static final int ENTRIES = 2;
967    
968        /**
969         * A hashtable enumerator class.  This class implements both the
970         * Enumeration and Iterator interfaces, but individual instances
971         * can be created with the Iterator methods disabled.  This is necessary
972         * to avoid unintentionally increasing the capabilities granted a user
973         * by passing an Enumeration.
974         */
975        private class Enumerator implements Enumeration, Iterator {
976        Entry[] table = HTNS.this.table;
977        int index = table.length;
978        Entry entry = null;
979        Entry lastReturned = null;
980        int type;
981    
982        /**
983         * Indicates whether this Enumerator is serving as an Iterator
984         * or an Enumeration.  (true -> Iterator).
985         */
986        boolean iterator;
987    
988        /**
989         * The modCount value that the iterator believes that the backing
990         * List should have.  If this expectation is violated, the iterator
991         * has detected concurrent modification.
992         */
993        protected int expectedModCount = modCount;
994    
995        Enumerator(int type, boolean iterator) {
996            this.type = type;
997            this.iterator = iterator;
998        }
999    
1000        /**
1001         * @see java.util.Enumeration#hasMoreElements()
1002         */
1003        public boolean hasMoreElements() {
1004            Entry e = entry;
1005            int i = index;
1006            Entry t[] = table;
1007            /* Use locals for faster loop iteration */
1008            while (e == null && i > 0) { 
1009            e = t[--i];
1010            }
1011            entry = e;
1012            index = i;
1013            return e != null;
1014        }
1015    
1016        /**
1017         * @see java.util.Enumeration#nextElement()
1018         */
1019        public Object nextElement() {
1020            Entry et = entry;
1021            int i = index;
1022            Entry t[] = table;
1023            /* Use locals for faster loop iteration */
1024            while (et == null && i > 0) { 
1025            et = t[--i];
1026            }
1027            entry = et;
1028            index = i;
1029            if (et != null) {
1030            Entry e = lastReturned = entry;
1031            entry = e.next;
1032            return type == KEYS ? e.key : (type == VALUES ? e.value : e);
1033            }
1034            throw new NoSuchElementException("Hashtable Enumerator");
1035        }
1036    
1037        /**
1038         * @see java.util.Iterator#hasNext()
1039         */
1040        // Iterator methods
1041        public boolean hasNext() {
1042            return hasMoreElements();
1043        }
1044    
1045        /**
1046         * @see java.util.Iterator#next()
1047         */
1048        public Object next() {
1049            if (modCount != expectedModCount)
1050            throw new ConcurrentModificationException();
1051            return nextElement();
1052        }
1053    
1054        /**
1055         * @see java.util.Iterator#remove()
1056         */
1057        public void remove() {
1058            if (!iterator)
1059            throw new UnsupportedOperationException();
1060            if (lastReturned == null)
1061            throw new IllegalStateException("Hashtable Enumerator");
1062            if (modCount != expectedModCount)
1063            throw new ConcurrentModificationException();
1064    
1065            synchronized(HTNS.this) {
1066            Entry[] tab = HTNS.this.table;
1067            int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length;
1068    
1069            for (Entry e = tab[index], prev = null; e != null;
1070                 prev = e, e = e.next) {
1071                if (e == lastReturned) {
1072                modCount++;
1073                expectedModCount++;
1074                if (prev == null)
1075                    tab[index] = e.next;
1076                else
1077                    prev.next = e.next;
1078                count--;
1079                lastReturned = null;
1080                return;
1081                }
1082            }
1083            throw new ConcurrentModificationException();
1084            }
1085        }
1086        }
1087    
1088       
1089        private static EmptyEnumerator emptyEnumerator = new EmptyEnumerator();
1090        private static EmptyIterator emptyIterator = new EmptyIterator();
1091    
1092        /**
1093         * A hashtable enumerator class for empty hash tables, specializes
1094         * the general Enumerator
1095         */
1096        private static class EmptyEnumerator implements Enumeration {
1097    
1098        EmptyEnumerator() {
1099        }
1100    
1101        /**
1102         * @see java.util.Enumeration#hasMoreElements()
1103         */
1104        public boolean hasMoreElements() {
1105            return false;
1106        }
1107    
1108        /**
1109         * @see java.util.Enumeration#nextElement()
1110         */
1111        public Object nextElement() {
1112            throw new NoSuchElementException("Hashtable Enumerator");
1113        }
1114        }
1115    
1116    
1117        /**
1118         * A hashtable iterator class for empty hash tables
1119         */
1120        private static class EmptyIterator implements Iterator {
1121    
1122        EmptyIterator() {
1123        }
1124    
1125        /**
1126         * @see java.util.Iterator#hasNext()
1127         */
1128        public boolean hasNext() {
1129            return false;
1130        }
1131    
1132        /**
1133         * @see java.util.Iterator#next()
1134         */
1135        public Object next() {
1136            throw new NoSuchElementException("Hashtable Iterator");
1137        }
1138    
1139        /**
1140         * @see java.util.Iterator#remove()
1141         */
1142        public void remove() {
1143            throw new IllegalStateException("Hashtable Iterator");
1144        }
1145    
1146        }
1147    
1148    }