001    package railo.commons.util.mod;
002    import java.lang.ref.ReferenceQueue;
003    import java.lang.ref.WeakReference;
004    import java.util.ArrayList;
005    import java.util.Arrays;
006    import java.util.Collection;
007    import java.util.ConcurrentModificationException;
008    import java.util.Iterator;
009    import java.util.List;
010    import java.util.Map;
011    import java.util.NoSuchElementException;
012    import java.util.Set;
013    
014    import railo.runtime.exp.PageException;
015    
016    public class WeakHashMapPro<K,V>
017        extends AbstractMapPro<K,V>
018        implements MapPro<K,V> {
019    
020        /**
021         * The default initial capacity -- MUST be a power of two.
022         */
023        private static final int DEFAULT_INITIAL_CAPACITY = 16;
024    
025        /**
026         * The maximum capacity, used if a higher value is implicitly specified
027         * by either of the constructors with arguments.
028         * MUST be a power of two <= 1<<30.
029         */
030        private static final int MAXIMUM_CAPACITY = 1 << 30;
031    
032        /**
033         * The load factor used when none specified in constructor.
034         */
035        private static final float DEFAULT_LOAD_FACTOR = 0.75f;
036    
037        /**
038         * The table, resized as necessary. Length MUST Always be a power of two.
039         */
040        Entry<K,V>[] table;
041    
042        /**
043         * The number of key-value mappings contained in this weak hash map.
044         */
045        private int size;
046    
047        /**
048         * The next size value at which to resize (capacity * load factor).
049         */
050        private int threshold;
051    
052        /**
053         * The load factor for the hash table.
054         */
055        private final float loadFactor;
056    
057        /**
058         * Reference queue for cleared WeakEntries
059         */
060        private final ReferenceQueue<Object> queue = new ReferenceQueue<Object>();
061    
062        
063        int modCount;
064    
065        /**
066         * The default threshold of map capacity above which alternative hashing is
067         * used for String keys. Alternative hashing reduces the incidence of
068         * collisions due to weak hash code calculation for String keys.
069         * <p/>
070         * This value may be overridden by defining the system property
071         * {@code jdk.map.althashing.threshold}. A property value of {@code 1}
072         * forces alternative hashing to be used at all times whereas
073         * {@code -1} value ensures that alternative hashing is never used.
074         */
075        static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
076    
077        /**
078         * holds values which can't be initialized until after VM is booted.
079         */
080        private static class Holder {
081    
082            /**
083             * Table capacity above which to switch to use alternative hashing.
084             */
085            static final int ALTERNATIVE_HASHING_THRESHOLD;
086    
087            static {
088                String altThreshold = java.security.AccessController.doPrivileged(
089                    new sun.security.action.GetPropertyAction(
090                        "jdk.map.althashing.threshold"));
091    
092                int threshold;
093                try {
094                    threshold = (null != altThreshold)
095                            ? Integer.parseInt(altThreshold)
096                            : ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;
097    
098                    // disable alternative hashing if -1
099                    if (threshold == -1) {
100                        threshold = Integer.MAX_VALUE;
101                    }
102    
103                    if (threshold < 0) {
104                        throw new IllegalArgumentException("value must be positive integer.");
105                    }
106                } catch(IllegalArgumentException failed) {
107                    throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
108                }
109                ALTERNATIVE_HASHING_THRESHOLD = threshold;
110            }
111        }
112    
113        /**
114         * If {@code true} then perform alternate hashing to reduce the incidence of
115         * collisions due to weak hash code calculation.
116         */
117        transient final boolean useAltHashing=false;
118    
119        /**
120         * A randomizing value associated with this instance that is applied to
121         * hash code of keys to make hash collisions harder to find.
122         */
123        transient final int hashSeed = Hashing.randomHashSeed(this);
124    
125        @SuppressWarnings("unchecked")
126        private Entry<K,V>[] newTable(int n) {
127            return  new Entry[n];
128        }
129    
130        /**
131         * Constructs a new, empty <tt>WeakHashMap</tt> with the given initial
132         * capacity and the given load factor.
133         *
134         * @param  initialCapacity The initial capacity of the <tt>WeakHashMap</tt>
135         * @param  loadFactor      The load factor of the <tt>WeakHashMap</tt>
136         * @throws IllegalArgumentException if the initial capacity is negative,
137         *         or if the load factor is nonpositive.
138         */
139        public WeakHashMapPro(int initialCapacity, float loadFactor) {
140            if (initialCapacity < 0)
141                throw new IllegalArgumentException("Illegal Initial Capacity: "+
142                                                   initialCapacity);
143            if (initialCapacity > MAXIMUM_CAPACITY)
144                initialCapacity = MAXIMUM_CAPACITY;
145    
146            if (loadFactor <= 0 || Float.isNaN(loadFactor))
147                throw new IllegalArgumentException("Illegal Load factor: "+
148                                                   loadFactor);
149            int capacity = 1;
150            while (capacity < initialCapacity)
151                capacity <<= 1;
152            table = newTable(capacity);
153            this.loadFactor = loadFactor;
154            threshold = (int)(capacity * loadFactor);
155            //useAltHashing = sun.misc.VM.isBooted() && (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
156        }
157    
158        /**
159         * Constructs a new, empty <tt>WeakHashMap</tt> with the given initial
160         * capacity and the default load factor (0.75).
161         *
162         * @param  initialCapacity The initial capacity of the <tt>WeakHashMap</tt>
163         * @throws IllegalArgumentException if the initial capacity is negative
164         */
165        public WeakHashMapPro(int initialCapacity) {
166            this(initialCapacity, DEFAULT_LOAD_FACTOR);
167        }
168    
169        /**
170         * Constructs a new, empty <tt>WeakHashMap</tt> with the default initial
171         * capacity (16) and load factor (0.75).
172         */
173        public WeakHashMapPro() {
174            this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
175        }
176    
177        /**
178         * Constructs a new <tt>WeakHashMap</tt> with the same mappings as the
179         * specified map.  The <tt>WeakHashMap</tt> is created with the default
180         * load factor (0.75) and an initial capacity sufficient to hold the
181         * mappings in the specified map.
182         *
183         * @param   m the map whose mappings are to be placed in this map
184         * @throws  NullPointerException if the specified map is null
185         * @since   1.3
186         */
187        public WeakHashMapPro(Map<? extends K, ? extends V> m) {
188            this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
189                    DEFAULT_INITIAL_CAPACITY),
190                 DEFAULT_LOAD_FACTOR);
191            putAll(m);
192        }
193    
194        // internal utilities
195    
196        /**
197         * Value representing null keys inside tables.
198         */
199        private static final Object NULL_KEY = new Object();
200    
201        /**
202         * Use NULL_KEY for key if it is null.
203         */
204        private static Object maskNull(Object key) {
205            return (key == null) ? NULL_KEY : key;
206        }
207    
208        /**
209         * Returns internal representation of null key back to caller as null.
210         */
211        static Object unmaskNull(Object key) {
212            return (key == NULL_KEY) ? null : key;
213        }
214    
215        /**
216         * Checks for equality of non-null reference x and possibly-null y.  By
217         * default uses Object.equals.
218         */
219        private static boolean eq(Object x, Object y) {
220            return x == y || x.equals(y);
221        }
222    
223        /**
224         * Retrieve object hash code and applies a supplemental hash function to the
225         * result hash, which defends against poor quality hash functions.  This is
226         * critical because HashMap uses power-of-two length hash tables, that
227         * otherwise encounter collisions for hashCodes that do not differ
228         * in lower bits.
229         */
230        int hash(Object k) {
231    
232            int h;
233            /*if (useAltHashing) {
234                h = hashSeed;
235                if (k instanceof String) {
236                    return Hashing.stringHash32((String) k);
237                } 
238                h ^= k.hashCode();
239                
240            } else  {
241                h = k.hashCode();
242            }*/
243            h = k.hashCode();
244    
245            // This function ensures that hashCodes that differ only by
246            // constant multiples at each bit position have a bounded
247            // number of collisions (approximately 8 at default load factor).
248            h ^= (h >>> 20) ^ (h >>> 12);
249            return h ^ (h >>> 7) ^ (h >>> 4);
250        }
251    
252        /**
253         * Returns index for hash code h.
254         */
255        private static int indexFor(int h, int length) {
256            return h & (length-1);
257        }
258    
259        /**
260         * Expunges stale entries from the table.
261         */
262        private void expungeStaleEntries() {
263            for (Object x; (x = queue.poll()) != null; ) {
264                synchronized (queue) {
265                    @SuppressWarnings("unchecked")
266                        Entry<K,V> e = (Entry<K,V>) x;
267                    int i = indexFor(e.hash, table.length);
268    
269                    Entry<K,V> prev = table[i];
270                    Entry<K,V> p = prev;
271                    while (p != null) {
272                        Entry<K,V> next = p.next;
273                        if (p == e) {
274                            if (prev == e)
275                                table[i] = next;
276                            else
277                                prev.next = next;
278                            // Must not null out e.next;
279                            // stale entries may be in use by a HashIterator
280                            e.value = null; // Help GC
281                            size--;
282                            break;
283                        }
284                        prev = p;
285                        p = next;
286                    }
287                }
288            }
289        }
290    
291        /**
292         * Returns the table after first expunging stale entries.
293         */
294        private Entry<K,V>[] getTable() {
295            expungeStaleEntries();
296            return table;
297        }
298    
299        /**
300         * Returns the number of key-value mappings in this map.
301         * This result is a snapshot, and may not reflect unprocessed
302         * entries that will be removed before next attempted access
303         * because they are no longer referenced.
304         */
305        public int size() {
306            if (size == 0)
307                return 0;
308            expungeStaleEntries();
309            return size;
310        }
311    
312        /**
313         * Returns <tt>true</tt> if this map contains no key-value mappings.
314         * This result is a snapshot, and may not reflect unprocessed
315         * entries that will be removed before next attempted access
316         * because they are no longer referenced.
317         */
318        public boolean isEmpty() {
319            return size() == 0;
320        }
321    
322        @Override
323        public V get(Object key) {
324            Object k = maskNull(key);
325            int h = hash(k);
326            Entry<K,V>[] tab = getTable();
327            int index = indexFor(h, tab.length);
328            Entry<K,V> e = tab[index];
329            while (e != null) {
330                if (e.hash == h && eq(k, e.get()))
331                    return e.value;
332                e = e.next;
333            }
334            return null;
335        }
336        
337        public V g(K key) throws PageException {
338            Object k = maskNull(key);
339            int h = hash(k);
340            Entry<K,V>[] tab = getTable();
341            int index = indexFor(h, tab.length);
342            Entry<K,V> e = tab[index];
343            while (e != null) {
344                if (e.hash == h && eq(k, e.get()))
345                    return e.value;
346                e = e.next;
347            }
348            throw invalidKey(this,key,false);
349        }
350        
351        public V g(K key, V defaultValue) {
352            Object k = maskNull(key);
353            int h = hash(k);
354            Entry<K,V>[] tab = getTable();
355            int index = indexFor(h, tab.length);
356            Entry<K,V> e = tab[index];
357            while (e != null) {
358                if (e.hash == h && eq(k, e.get()))
359                    return e.value;
360                e = e.next;
361            }
362            return defaultValue;
363        }
364    
365        /**
366         * Returns <tt>true</tt> if this map contains a mapping for the
367         * specified key.
368         *
369         * @param  key   The key whose presence in this map is to be tested
370         * @return <tt>true</tt> if there is a mapping for <tt>key</tt>;
371         *         <tt>false</tt> otherwise
372         */
373        public boolean containsKey(Object key) {
374            return getEntry(key) != null;
375        }
376    
377        /**
378         * Returns the entry associated with the specified key in this map.
379         * Returns null if the map contains no mapping for this key.
380         */
381        Entry<K,V> getEntry(Object key) {
382            Object k = maskNull(key);
383            int h = hash(k);
384            Entry<K,V>[] tab = getTable();
385            int index = indexFor(h, tab.length);
386            Entry<K,V> e = tab[index];
387            while (e != null && !(e.hash == h && eq(k, e.get())))
388                e = e.next;
389            return e;
390        }
391    
392        /**
393         * Associates the specified value with the specified key in this map.
394         * If the map previously contained a mapping for this key, the old
395         * value is replaced.
396         *
397         * @param key key with which the specified value is to be associated.
398         * @param value value to be associated with the specified key.
399         * @return the previous value associated with <tt>key</tt>, or
400         *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
401         *         (A <tt>null</tt> return can also indicate that the map
402         *         previously associated <tt>null</tt> with <tt>key</tt>.)
403         */
404        public V put(K key, V value) {
405            Object k = maskNull(key);
406            int h = hash(k);
407            Entry<K,V>[] tab = getTable();
408            int i = indexFor(h, tab.length);
409    
410            for (Entry<K,V> e = tab[i]; e != null; e = e.next) {
411                if (h == e.hash && eq(k, e.get())) {
412                    V oldValue = e.value;
413                    if (value != oldValue)
414                        e.value = value;
415                    return oldValue;
416                }
417            }
418    
419            modCount++;
420            Entry<K,V> e = tab[i];
421            tab[i] = new Entry<K,V>(k, value, queue, h, e);
422            if (++size >= threshold)
423                resize(tab.length * 2);
424            return null;
425        }
426    
427        /**
428         * Rehashes the contents of this map into a new array with a
429         * larger capacity.  This method is called automatically when the
430         * number of keys in this map reaches its threshold.
431         *
432         * If current capacity is MAXIMUM_CAPACITY, this method does not
433         * resize the map, but sets threshold to Integer.MAX_VALUE.
434         * This has the effect of preventing future calls.
435         *
436         * @param newCapacity the new capacity, MUST be a power of two;
437         *        must be greater than current capacity unless current
438         *        capacity is MAXIMUM_CAPACITY (in which case value
439         *        is irrelevant).
440         */
441        void resize(int newCapacity) {
442            Entry<K,V>[] oldTable = getTable();
443            int oldCapacity = oldTable.length;
444            if (oldCapacity == MAXIMUM_CAPACITY) {
445                threshold = Integer.MAX_VALUE;
446                return;
447            }
448    
449            Entry<K,V>[] newTable = newTable(newCapacity);
450            boolean oldAltHashing = useAltHashing;
451            //useAltHashing |= sun.misc.VM.isBooted() && (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
452            boolean rehash = oldAltHashing ^ useAltHashing;
453            transfer(oldTable, newTable, rehash);
454            table = newTable;
455    
456            /*
457             * If ignoring null elements and processing ref queue caused massive
458             * shrinkage, then restore old table.  This should be rare, but avoids
459             * unbounded expansion of garbage-filled tables.
460             */
461            if (size >= threshold / 2) {
462                threshold = (int)(newCapacity * loadFactor);
463            } else {
464                expungeStaleEntries();
465                transfer(newTable, oldTable, false);
466                table = oldTable;
467            }
468        }
469    
470        /** Transfers all entries from src to dest tables */
471        private void transfer(Entry<K,V>[] src, Entry<K,V>[] dest, boolean rehash) {
472            for (int j = 0; j < src.length; ++j) {
473                Entry<K,V> e = src[j];
474                src[j] = null;
475                while (e != null) {
476                    Entry<K,V> next = e.next;
477                    Object key = e.get();
478                    if (key == null) {
479                        e.next = null;  // Help GC
480                        e.value = null; //  "   "
481                        size--;
482                    } else {
483                        if (rehash) {
484                            e.hash = hash(key);
485                        }
486                        int i = indexFor(e.hash, dest.length);
487                        e.next = dest[i];
488                        dest[i] = e;
489                    }
490                    e = next;
491                }
492            }
493        }
494    
495        /**
496         * Copies all of the mappings from the specified map to this map.
497         * These mappings will replace any mappings that this map had for any
498         * of the keys currently in the specified map.
499         *
500         * @param m mappings to be stored in this map.
501         * @throws  NullPointerException if the specified map is null.
502         */
503        public void putAll(Map<? extends K, ? extends V> m) {
504            int numKeysToBeAdded = m.size();
505            if (numKeysToBeAdded == 0)
506                return;
507    
508            /*
509             * Expand the map if the map if the number of mappings to be added
510             * is greater than or equal to threshold.  This is conservative; the
511             * obvious condition is (m.size() + size) >= threshold, but this
512             * condition could result in a map with twice the appropriate capacity,
513             * if the keys to be added overlap with the keys already in this map.
514             * By using the conservative calculation, we subject ourself
515             * to at most one extra resize.
516             */
517            if (numKeysToBeAdded > threshold) {
518                int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
519                if (targetCapacity > MAXIMUM_CAPACITY)
520                    targetCapacity = MAXIMUM_CAPACITY;
521                int newCapacity = table.length;
522                while (newCapacity < targetCapacity)
523                    newCapacity <<= 1;
524                if (newCapacity > table.length)
525                    resize(newCapacity);
526            }
527    
528            for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
529                put(e.getKey(), e.getValue());
530        }
531    
532        /**
533         * Removes the mapping for a key from this weak hash map if it is present.
534         * More formally, if this map contains a mapping from key <tt>k</tt> to
535         * value <tt>v</tt> such that <code>(key==null ?  k==null :
536         * key.equals(k))</code>, that mapping is removed.  (The map can contain
537         * at most one such mapping.)
538         *
539         * <p>Returns the value to which this map previously associated the key,
540         * or <tt>null</tt> if the map contained no mapping for the key.  A
541         * return value of <tt>null</tt> does not <i>necessarily</i> indicate
542         * that the map contained no mapping for the key; it's also possible
543         * that the map explicitly mapped the key to <tt>null</tt>.
544         *
545         * <p>The map will not contain a mapping for the specified key once the
546         * call returns.
547         *
548         * @param key key whose mapping is to be removed from the map
549         * @return the previous value associated with <tt>key</tt>, or
550         *         <tt>null</tt> if there was no mapping for <tt>key</tt>
551         */
552        public V remove(Object key) {
553            Object k = maskNull(key);
554            int h = hash(k);
555            Entry<K,V>[] tab = getTable();
556            int i = indexFor(h, tab.length);
557            Entry<K,V> prev = tab[i];
558            Entry<K,V> e = prev;
559    
560            while (e != null) {
561                Entry<K,V> next = e.next;
562                if (h == e.hash && eq(k, e.get())) {
563                    modCount++;
564                    size--;
565                    if (prev == e)
566                        tab[i] = next;
567                    else
568                        prev.next = next;
569                    return e.value;
570                }
571                prev = e;
572                e = next;
573            }
574            return null;
575        }
576        
577        public V r(K key) throws PageException {
578            Object k = maskNull(key);
579            int h = hash(k);
580            Entry<K,V>[] tab = getTable();
581            int i = indexFor(h, tab.length);
582            Entry<K,V> prev = tab[i];
583            Entry<K,V> e = prev;
584    
585            while (e != null) {
586                Entry<K,V> next = e.next;
587                if (h == e.hash && eq(k, e.get())) {
588                    modCount++;
589                    size--;
590                    if (prev == e)
591                        tab[i] = next;
592                    else
593                        prev.next = next;
594                    return e.value;
595                }
596                prev = e;
597                e = next;
598            }
599            throw invalidKey(this, key, true);
600        }
601        
602        public V r(K key, V defaultValue) {
603            Object k = maskNull(key);
604            int h = hash(k);
605            Entry<K,V>[] tab = getTable();
606            int i = indexFor(h, tab.length);
607            Entry<K,V> prev = tab[i];
608            Entry<K,V> e = prev;
609    
610            while (e != null) {
611                Entry<K,V> next = e.next;
612                if (h == e.hash && eq(k, e.get())) {
613                    modCount++;
614                    size--;
615                    if (prev == e)
616                        tab[i] = next;
617                    else
618                        prev.next = next;
619                    return e.value;
620                }
621                prev = e;
622                e = next;
623            }
624            return defaultValue;
625        }
626    
627        /** Special version of remove needed by Entry set */
628        boolean removeMapping(Object o) {
629            if (!(o instanceof Map.Entry))
630                return false;
631            Entry<K,V>[] tab = getTable();
632            Map.Entry<?,?> entry = (Map.Entry<?,?>)o;
633            Object k = maskNull(entry.getKey());
634            int h = hash(k);
635            int i = indexFor(h, tab.length);
636            Entry<K,V> prev = tab[i];
637            Entry<K,V> e = prev;
638    
639            while (e != null) {
640                Entry<K,V> next = e.next;
641                if (h == e.hash && e.equals(entry)) {
642                    modCount++;
643                    size--;
644                    if (prev == e)
645                        tab[i] = next;
646                    else
647                        prev.next = next;
648                    return true;
649                }
650                prev = e;
651                e = next;
652            }
653    
654            return false;
655        }
656    
657        /**
658         * Removes all of the mappings from this map.
659         * The map will be empty after this call returns.
660         */
661        public void clear() {
662            // clear out ref queue. We don't need to expunge entries
663            // since table is getting cleared.
664            while (queue.poll() != null)
665                ;
666    
667            modCount++;
668            Arrays.fill(table, null);
669            size = 0;
670    
671            // Allocation of array may have caused GC, which may have caused
672            // additional entries to go stale.  Removing these entries from the
673            // reference queue will make them eligible for reclamation.
674            while (queue.poll() != null)
675                ;
676        }
677    
678        /**
679         * Returns <tt>true</tt> if this map maps one or more keys to the
680         * specified value.
681         *
682         * @param value value whose presence in this map is to be tested
683         * @return <tt>true</tt> if this map maps one or more keys to the
684         *         specified value
685         */
686        public boolean containsValue(Object value) {
687            if (value==null)
688                return containsNullValue();
689    
690            Entry<K,V>[] tab = getTable();
691            for (int i = tab.length; i-- > 0;)
692                for (Entry<K,V> e = tab[i]; e != null; e = e.next)
693                    if (value.equals(e.value))
694                        return true;
695            return false;
696        }
697    
698        /**
699         * Special-case code for containsValue with null argument
700         */
701        private boolean containsNullValue() {
702            Entry<K,V>[] tab = getTable();
703            for (int i = tab.length; i-- > 0;)
704                for (Entry<K,V> e = tab[i]; e != null; e = e.next)
705                    if (e.value==null)
706                        return true;
707            return false;
708        }
709    
710        /**
711         * The entries in this hash table extend WeakReference, using its main ref
712         * field as the key.
713         */
714        private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
715            V value;
716            int hash;
717            Entry<K,V> next;
718    
719            /**
720             * Creates new entry.
721             */
722            Entry(Object key, V value,
723                  ReferenceQueue<Object> queue,
724                  int hash, Entry<K,V> next) {
725                super(key, queue);
726                this.value = value;
727                this.hash  = hash;
728                this.next  = next;
729            }
730    
731            @SuppressWarnings("unchecked")
732            public K getKey() {
733                return (K) WeakHashMapPro.unmaskNull(get());
734            }
735    
736            public V getValue() {
737                return value;
738            }
739    
740            public V setValue(V newValue) {
741                V oldValue = value;
742                value = newValue;
743                return oldValue;
744            }
745    
746            public boolean equals(Object o) {
747                if (!(o instanceof Map.Entry))
748                    return false;
749                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
750                K k1 = getKey();
751                Object k2 = e.getKey();
752                if (k1 == k2 || (k1 != null && k1.equals(k2))) {
753                    V v1 = getValue();
754                    Object v2 = e.getValue();
755                    if (v1 == v2 || (v1 != null && v1.equals(v2)))
756                        return true;
757                }
758                return false;
759            }
760    
761            public int hashCode() {
762                K k = getKey();
763                V v = getValue();
764                return ((k==null ? 0 : k.hashCode()) ^
765                        (v==null ? 0 : v.hashCode()));
766            }
767    
768            public String toString() {
769                return getKey() + "=" + getValue();
770            }
771        }
772    
773        private abstract class HashIterator<T> implements Iterator<T> {
774            private int index;
775            private Entry<K,V> entry = null;
776            private Entry<K,V> lastReturned = null;
777            private int expectedModCount = modCount;
778    
779            /**
780             * Strong reference needed to avoid disappearance of key
781             * between hasNext and next
782             */
783            private Object nextKey = null;
784    
785            /**
786             * Strong reference needed to avoid disappearance of key
787             * between nextEntry() and any use of the entry
788             */
789            private Object currentKey = null;
790    
791            HashIterator() {
792                index = isEmpty() ? 0 : table.length;
793            }
794    
795            public boolean hasNext() {
796                Entry<K,V>[] t = table;
797    
798                while (nextKey == null) {
799                    Entry<K,V> e = entry;
800                    int i = index;
801                    while (e == null && i > 0)
802                        e = t[--i];
803                    entry = e;
804                    index = i;
805                    if (e == null) {
806                        currentKey = null;
807                        return false;
808                    }
809                    nextKey = e.get(); // hold on to key in strong ref
810                    if (nextKey == null)
811                        entry = entry.next;
812                }
813                return true;
814            }
815    
816            /** The common parts of next() across different types of iterators */
817            protected Entry<K,V> nextEntry() {
818                if (modCount != expectedModCount)
819                    throw new ConcurrentModificationException();
820                if (nextKey == null && !hasNext())
821                    throw new NoSuchElementException();
822    
823                lastReturned = entry;
824                entry = entry.next;
825                currentKey = nextKey;
826                nextKey = null;
827                return lastReturned;
828            }
829    
830            public void remove() {
831                if (lastReturned == null)
832                    throw new IllegalStateException();
833                if (modCount != expectedModCount)
834                    throw new ConcurrentModificationException();
835    
836                WeakHashMapPro.this.remove(currentKey);
837                expectedModCount = modCount;
838                lastReturned = null;
839                currentKey = null;
840            }
841    
842        }
843    
844        private class ValueIterator extends HashIterator<V> {
845            public V next() {
846                return nextEntry().value;
847            }
848        }
849    
850        private class KeyIterator extends HashIterator<K> {
851            public K next() {
852                return nextEntry().getKey();
853            }
854        }
855    
856        private class EntryIterator extends HashIterator<Map.Entry<K,V>> {
857            public Map.Entry<K,V> next() {
858                return nextEntry();
859            }
860        }
861    
862        // Views
863    
864        private transient Set<Map.Entry<K,V>> entrySet = null;
865    
866        /**
867         * Returns a {@link Set} view of the keys contained in this map.
868         * The set is backed by the map, so changes to the map are
869         * reflected in the set, and vice-versa.  If the map is modified
870         * while an iteration over the set is in progress (except through
871         * the iterator's own <tt>remove</tt> operation), the results of
872         * the iteration are undefined.  The set supports element removal,
873         * which removes the corresponding mapping from the map, via the
874         * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
875         * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
876         * operations.  It does not support the <tt>add</tt> or <tt>addAll</tt>
877         * operations.
878         */
879        public Set<K> keySet() {
880            Set<K> ks = keySet;
881            return (ks != null ? ks : (keySet = new KeySet()));
882        }
883    
884        private class KeySet extends AbstractSet<K> {
885            public Iterator<K> iterator() {
886                return new KeyIterator();
887            }
888    
889            public int size() {
890                return WeakHashMapPro.this.size();
891            }
892    
893            public boolean contains(Object o) {
894                return containsKey(o);
895            }
896    
897            public boolean remove(Object o) {
898                if (containsKey(o)) {
899                    WeakHashMapPro.this.remove(o);
900                    return true;
901                }
902                return false;
903            }
904    
905            public void clear() {
906                WeakHashMapPro.this.clear();
907            }
908        }
909    
910        /**
911         * Returns a {@link Collection} view of the values contained in this map.
912         * The collection is backed by the map, so changes to the map are
913         * reflected in the collection, and vice-versa.  If the map is
914         * modified while an iteration over the collection is in progress
915         * (except through the iterator's own <tt>remove</tt> operation),
916         * the results of the iteration are undefined.  The collection
917         * supports element removal, which removes the corresponding
918         * mapping from the map, via the <tt>Iterator.remove</tt>,
919         * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
920         * <tt>retainAll</tt> and <tt>clear</tt> operations.  It does not
921         * support the <tt>add</tt> or <tt>addAll</tt> operations.
922         */
923        public Collection<V> values() {
924            Collection<V> vs = values;
925            return (vs != null) ? vs : (values = new Values());
926        }
927    
928        private class Values extends AbstractCollection<V> {
929            public Iterator<V> iterator() {
930                return new ValueIterator();
931            }
932    
933            public int size() {
934                return WeakHashMapPro.this.size();
935            }
936    
937            public boolean contains(Object o) {
938                return containsValue(o);
939            }
940    
941            public void clear() {
942                WeakHashMapPro.this.clear();
943            }
944        }
945    
946        /**
947         * Returns a {@link Set} view of the mappings contained in this map.
948         * The set is backed by the map, so changes to the map are
949         * reflected in the set, and vice-versa.  If the map is modified
950         * while an iteration over the set is in progress (except through
951         * the iterator's own <tt>remove</tt> operation, or through the
952         * <tt>setValue</tt> operation on a map entry returned by the
953         * iterator) the results of the iteration are undefined.  The set
954         * supports element removal, which removes the corresponding
955         * mapping from the map, via the <tt>Iterator.remove</tt>,
956         * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
957         * <tt>clear</tt> operations.  It does not support the
958         * <tt>add</tt> or <tt>addAll</tt> operations.
959         */
960        public Set<Map.Entry<K,V>> entrySet() {
961            Set<Map.Entry<K,V>> es = entrySet;
962            return es != null ? es : (entrySet = new EntrySet());
963        }
964    
965        private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
966            public Iterator<Map.Entry<K,V>> iterator() {
967                return new EntryIterator();
968            }
969    
970            public boolean contains(Object o) {
971                if (!(o instanceof Map.Entry))
972                    return false;
973                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
974                Entry<K,V> candidate = getEntry(e.getKey());
975                return candidate != null && candidate.equals(e);
976            }
977    
978            public boolean remove(Object o) {
979                return removeMapping(o);
980            }
981    
982            public int size() {
983                return WeakHashMapPro.this.size();
984            }
985    
986            public void clear() {
987                WeakHashMapPro.this.clear();
988            }
989    
990            private List<Map.Entry<K,V>> deepCopy() {
991                List<Map.Entry<K,V>> list = new ArrayList<Map.Entry<K,V>>(size());
992                for (Map.Entry<K,V> e : this)
993                    list.add(new AbstractMapPro.SimpleEntry<K,V>(e));
994                return list;
995            }
996    
997            public Object[] toArray() {
998                return deepCopy().toArray();
999            }
1000    
1001            public <T> T[] toArray(T[] a) {
1002                return deepCopy().toArray(a);
1003            }
1004        }
1005    }