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