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