1   /*
2    *  Copyright 2001-2004 The Apache Software Foundation
3    *
4    *  Licensed under the Apache License, Version 2.0 (the "License");
5    *  you may not use this file except in compliance with the License.
6    *  You may obtain a copy of the License at
7    *
8    *      http://www.apache.org/licenses/LICENSE-2.0
9    *
10   *  Unless required by applicable law or agreed to in writing, software
11   *  distributed under the License is distributed on an "AS IS" BASIS,
12   *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   *  See the License for the specific language governing permissions and
14   *  limitations under the License.
15   */
16  package org.apache.commons.collections;
17  
18  import java.io.IOException;
19  import java.io.ObjectInputStream;
20  import java.io.ObjectOutputStream;
21  import java.lang.ref.Reference;
22  import java.lang.ref.ReferenceQueue;
23  import java.lang.ref.SoftReference;
24  import java.lang.ref.WeakReference;
25  import java.util.AbstractCollection;
26  import java.util.AbstractMap;
27  import java.util.AbstractSet;
28  import java.util.ArrayList;
29  import java.util.Arrays;
30  import java.util.Collection;
31  import java.util.ConcurrentModificationException;
32  import java.util.Iterator;
33  import java.util.Map;
34  import java.util.NoSuchElementException;
35  import java.util.Set;
36  
37  import org.apache.commons.collections.keyvalue.DefaultMapEntry;
38  
39  /**
40   *  Hash-based {@link Map} implementation that allows
41   *  mappings to be removed by the garbage collector.<p>
42   *
43   *  When you construct a <code>ReferenceMap</code>, you can 
44   *  specify what kind of references are used to store the
45   *  map's keys and values.  If non-hard references are 
46   *  used, then the garbage collector can remove mappings
47   *  if a key or value becomes unreachable, or if the 
48   *  JVM's memory is running low.  For information on how
49   *  the different reference types behave, see
50   *  {@link Reference}.<p>
51   *
52   *  Different types of references can be specified for keys
53   *  and values.  The keys can be configured to be weak but
54   *  the values hard, in which case this class will behave
55   *  like a <a href="http://java.sun.com/j2se/1.4/docs/api/java/util/WeakHashMap.html">
56   *  <code>WeakHashMap</code></a>.  However, you
57   *  can also specify hard keys and weak values, or any other
58   *  combination.  The default constructor uses hard keys
59   *  and soft values, providing a memory-sensitive cache.<p>
60   *
61   *  The algorithms used are basically the same as those
62   *  in {@link java.util.HashMap}.  In particular, you 
63   *  can specify a load factor and capacity to suit your
64   *  needs.  All optional {@link Map} operations are 
65   *  supported.<p>
66   *
67   *  However, this {@link Map} implementation does <I>not</I>
68   *  allow null elements.  Attempting to add a null key or
69   *  or a null value to the map will raise a 
70   *  <code>NullPointerException</code>.<p>
71   *
72   *  As usual, this implementation is not synchronized.  You
73   *  can use {@link java.util.Collections#synchronizedMap} to 
74   *  provide synchronized access to a <code>ReferenceMap</code>.
75   *
76   * @see java.lang.ref.Reference
77   * 
78   * @deprecated Moved to map subpackage. Due to be removed in v4.0.
79   * @since Commons Collections 2.1
80   * @version $Revision: 1.1 $ $Date: 2004/05/10 19:52:42 $
81   * 
82   * @author Paul Jack
83   */
84  public class ReferenceMap extends AbstractMap {
85  
86      /**
87       *  For serialization.
88       */
89      final private static long serialVersionUID = -3370601314380922368L;
90  
91  
92      /**
93       *  Constant indicating that hard references should be used.
94       */
95      final public static int HARD = 0;
96  
97  
98      /**
99       *  Constant indicating that soft references should be used.
100      */
101     final public static int SOFT = 1;
102 
103 
104     /**
105      *  Constant indicating that weak references should be used.
106      */
107     final public static int WEAK = 2;
108 
109 
110     // --- serialized instance variables:
111 
112 
113     /**
114      *  The reference type for keys.  Must be HARD, SOFT, WEAK.
115      *  Note: I originally marked this field as final, but then this class
116      *   didn't compile under JDK1.2.2.
117      *  @serial
118      */
119     private int keyType;
120 
121 
122     /**
123      *  The reference type for values.  Must be HARD, SOFT, WEAK.
124      *  Note: I originally marked this field as final, but then this class
125      *   didn't compile under JDK1.2.2.
126      *  @serial
127      */
128     private int valueType;
129 
130 
131     /**
132      *  The threshold variable is calculated by multiplying
133      *  table.length and loadFactor.  
134      *  Note: I originally marked this field as final, but then this class
135      *   didn't compile under JDK1.2.2.
136      *  @serial
137      */
138     private float loadFactor;
139     
140     /**
141      * Should the value be automatically purged when the associated key has been collected?
142      */
143     private boolean purgeValues = false;
144 
145 
146     // -- Non-serialized instance variables
147 
148     /**
149      *  ReferenceQueue used to eliminate stale mappings.
150      *  See purge.
151      */
152     private transient ReferenceQueue queue = new ReferenceQueue();
153 
154 
155     /**
156      *  The hash table.  Its length is always a power of two.  
157      */
158     private transient Entry[] table;
159 
160 
161     /**
162      *  Number of mappings in this map.
163      */
164     private transient int size;
165 
166 
167     /**
168      *  When size reaches threshold, the map is resized.  
169      *  See resize().
170      */
171     private transient int threshold;
172 
173 
174     /**
175      *  Number of times this map has been modified.
176      */
177     private transient volatile int modCount;
178 
179 
180     /**
181      *  Cached key set.  May be null if key set is never accessed.
182      */
183     private transient Set keySet;
184 
185 
186     /**
187      *  Cached entry set.  May be null if entry set is never accessed.
188      */
189     private transient Set entrySet;
190 
191 
192     /**
193      *  Cached values.  May be null if values() is never accessed.
194      */
195     private transient Collection values;
196 
197 
198     /**
199      *  Constructs a new <code>ReferenceMap</code> that will
200      *  use hard references to keys and soft references to values.
201      */
202     public ReferenceMap() {
203         this(HARD, SOFT);
204     }
205 
206     /**
207      *  Constructs a new <code>ReferenceMap</code> that will
208      *  use the specified types of references.
209      *
210      *  @param keyType  the type of reference to use for keys;
211      *   must be {@link #HARD}, {@link #SOFT}, {@link #WEAK}
212      *  @param valueType  the type of reference to use for values;
213      *   must be {@link #HARD}, {@link #SOFT}, {@link #WEAK}
214      *  @param purgeValues should the value be automatically purged when the 
215      *   key is garbage collected 
216      */
217     public ReferenceMap(int keyType, int valueType, boolean purgeValues) {
218         this(keyType, valueType);
219         this.purgeValues = purgeValues;
220     }
221 
222     /**
223      *  Constructs a new <code>ReferenceMap</code> that will
224      *  use the specified types of references.
225      *
226      *  @param keyType  the type of reference to use for keys;
227      *   must be {@link #HARD}, {@link #SOFT}, {@link #WEAK}
228      *  @param valueType  the type of reference to use for values;
229      *   must be {@link #HARD}, {@link #SOFT}, {@link #WEAK}
230      */
231     public ReferenceMap(int keyType, int valueType) {
232         this(keyType, valueType, 16, 0.75f);
233     }
234 
235     /**
236      *  Constructs a new <code>ReferenceMap</code> with the
237      *  specified reference types, load factor and initial
238      *  capacity.
239      *
240      *  @param keyType  the type of reference to use for keys;
241      *   must be {@link #HARD}, {@link #SOFT}, {@link #WEAK}
242      *  @param valueType  the type of reference to use for values;
243      *   must be {@link #HARD}, {@link #SOFT}, {@link #WEAK}
244      *  @param capacity  the initial capacity for the map
245      *  @param loadFactor  the load factor for the map
246      *  @param purgeValues should the value be automatically purged when the 
247      *   key is garbage collected 
248      */
249     public ReferenceMap(
250                         int keyType, 
251                         int valueType, 
252                         int capacity, 
253                         float loadFactor, 
254                         boolean purgeValues) {
255         this(keyType, valueType, capacity, loadFactor);
256         this.purgeValues = purgeValues;
257     }
258 
259     /**
260      *  Constructs a new <code>ReferenceMap</code> with the
261      *  specified reference types, load factor and initial
262      *  capacity.
263      *
264      *  @param keyType  the type of reference to use for keys;
265      *   must be {@link #HARD}, {@link #SOFT}, {@link #WEAK}
266      *  @param valueType  the type of reference to use for values;
267      *   must be {@link #HARD}, {@link #SOFT}, {@link #WEAK}
268      *  @param capacity  the initial capacity for the map
269      *  @param loadFactor  the load factor for the map
270      */
271     public ReferenceMap(int keyType, int valueType, int capacity, float loadFactor) {
272         super();
273 
274         verify("keyType", keyType);
275         verify("valueType", valueType);
276 
277         if (capacity <= 0) {
278             throw new IllegalArgumentException("capacity must be positive");
279         }
280         if ((loadFactor <= 0.0f) || (loadFactor >= 1.0f)) {
281             throw new IllegalArgumentException("Load factor must be greater than 0 and less than 1.");
282         }
283 
284         this.keyType = keyType;
285         this.valueType = valueType;
286 
287         int v = 1;
288         while (v < capacity) v *= 2;
289 
290         this.table = new Entry[v];
291         this.loadFactor = loadFactor;
292         this.threshold = (int)(v * loadFactor);
293     }
294 
295 
296     // used by constructor
297     private static void verify(String name, int type) {
298         if ((type < HARD) || (type > WEAK)) {
299             throw new IllegalArgumentException(name + 
300                " must be HARD, SOFT, WEAK.");
301         }
302     }
303 
304 
305     /**
306      *  Writes this object to the given output stream.
307      *
308      *  @param out  the output stream to write to
309      *  @throws IOException  if the stream raises it
310      */
311     private void writeObject(ObjectOutputStream out) throws IOException {
312         out.defaultWriteObject();
313         out.writeInt(table.length);
314 
315         // Have to use null-terminated list because size might shrink
316         // during iteration
317 
318         for (Iterator iter = entrySet().iterator(); iter.hasNext();) {
319             Map.Entry entry = (Map.Entry)iter.next();
320             out.writeObject(entry.getKey());
321             out.writeObject(entry.getValue());
322         }
323         out.writeObject(null);
324     }
325 
326 
327     /**
328      *  Reads the contents of this object from the given input stream.
329      *
330      *  @param inp  the input stream to read from
331      *  @throws IOException  if the stream raises it
332      *  @throws ClassNotFoundException  if the stream raises it
333      */
334     private void readObject(ObjectInputStream inp) throws IOException, ClassNotFoundException {
335         inp.defaultReadObject();
336         table = new Entry[inp.readInt()];
337         threshold = (int)(table.length * loadFactor);
338         queue = new ReferenceQueue();
339         Object key = inp.readObject();
340         while (key != null) {
341             Object value = inp.readObject();
342             put(key, value);
343             key = inp.readObject();
344         }
345     }
346 
347 
348     /**
349      *  Constructs a reference of the given type to the given 
350      *  referent.  The reference is registered with the queue
351      *  for later purging.
352      *
353      *  @param type  HARD, SOFT or WEAK
354      *  @param referent  the object to refer to
355      *  @param hash  the hash code of the <I>key</I> of the mapping;
356      *    this number might be different from referent.hashCode() if
357      *    the referent represents a value and not a key
358      */
359     private Object toReference(int type, Object referent, int hash) {
360         switch (type) {
361             case HARD: return referent;
362             case SOFT: return new SoftRef(hash, referent, queue);
363             case WEAK: return new WeakRef(hash, referent, queue);
364             default: throw new Error();
365         }
366     }
367 
368 
369     /**
370      *  Returns the entry associated with the given key.
371      *
372      *  @param key  the key of the entry to look up
373      *  @return  the entry associated with that key, or null
374      *    if the key is not in this map
375      */
376     private Entry getEntry(Object key) {
377         if (key == null) return null;
378         int hash = key.hashCode();
379         int index = indexFor(hash);
380         for (Entry entry = table[index]; entry != null; entry = entry.next) {
381             if ((entry.hash == hash) && key.equals(entry.getKey())) {
382                 return entry;
383             }
384         }
385         return null;
386     }
387 
388 
389     /**
390      *  Converts the given hash code into an index into the
391      *  hash table.
392      */
393     private int indexFor(int hash) {
394         // mix the bits to avoid bucket collisions...
395         hash += ~(hash << 15);
396         hash ^= (hash >>> 10);
397         hash += (hash << 3);
398         hash ^= (hash >>> 6);
399         hash += ~(hash << 11);
400         hash ^= (hash >>> 16);
401         return hash & (table.length - 1);
402     }
403 
404 
405 
406     /**
407      *  Resizes this hash table by doubling its capacity.
408      *  This is an expensive operation, as entries must
409      *  be copied from the old smaller table to the new 
410      *  bigger table.
411      */
412     private void resize() {
413         Entry[] old = table;
414         table = new Entry[old.length * 2];
415 
416         for (int i = 0; i < old.length; i++) {
417             Entry next = old[i];
418             while (next != null) {
419                 Entry entry = next;
420                 next = next.next;
421                 int index = indexFor(entry.hash);
422                 entry.next = table[index];
423                 table[index] = entry;
424             }
425             old[i] = null;
426         }
427         threshold = (int)(table.length * loadFactor);
428     }
429 
430 
431 
432     /**
433      * Purges stale mappings from this map.
434      * <p>
435      * Ordinarily, stale mappings are only removed during
436      * a write operation, although this method is called for both
437      * read and write operations to maintain a consistent state.
438      * <p>
439      * Note that this method is not synchronized!  Special
440      * care must be taken if, for instance, you want stale
441      * mappings to be removed on a periodic basis by some
442      * background thread.
443      */
444     private void purge() {
445         Reference ref = queue.poll();
446         while (ref != null) {
447             purge(ref);
448             ref = queue.poll();
449         }
450     }
451 
452 
453     private void purge(Reference ref) {
454         // The hashCode of the reference is the hashCode of the
455         // mapping key, even if the reference refers to the 
456         // mapping value...
457         int hash = ref.hashCode();
458         int index = indexFor(hash);
459         Entry previous = null;
460         Entry entry = table[index];
461         while (entry != null) {
462             if (entry.purge(ref)) {
463                 if (previous == null) table[index] = entry.next;
464                 else previous.next = entry.next;
465                 this.size--;
466                 return;
467             }
468             previous = entry;
469             entry = entry.next;
470         }
471 
472     }
473 
474 
475     /**
476      *  Returns the size of this map.
477      *
478      *  @return  the size of this map
479      */
480     public int size() {
481         purge();
482         return size;
483     }
484 
485 
486     /**
487      *  Returns <code>true</code> if this map is empty.
488      *
489      *  @return <code>true</code> if this map is empty
490      */
491     public boolean isEmpty() {
492         purge();
493         return size == 0;
494     }
495 
496 
497     /**
498      *  Returns <code>true</code> if this map contains the given key.
499      *
500      *  @return true if the given key is in this map
501      */
502     public boolean containsKey(Object key) {
503         purge();
504         Entry entry = getEntry(key);
505         if (entry == null) return false;
506         return entry.getValue() != null;
507     }
508 
509 
510     /**
511      *  Returns the value associated with the given key, if any.
512      *
513      *  @return the value associated with the given key, or <code>null</code>
514      *   if the key maps to no value
515      */
516     public Object get(Object key) {
517         purge();
518         Entry entry = getEntry(key);
519         if (entry == null) return null;
520         return entry.getValue();
521     }
522 
523 
524     /**
525      *  Associates the given key with the given value.<p>
526      *  Neither the key nor the value may be null.
527      *
528      *  @param key  the key of the mapping
529      *  @param value  the value of the mapping
530      *  @return  the last value associated with that key, or 
531      *   null if no value was associated with the key
532      *  @throws NullPointerException if either the key or value
533      *   is null
534      */
535     public Object put(Object key, Object value) {
536         if (key == null) throw new NullPointerException("null keys not allowed");
537         if (value == null) throw new NullPointerException("null values not allowed");
538 
539         purge();
540         if (size + 1 > threshold) resize();
541 
542         int hash = key.hashCode();
543         int index = indexFor(hash);
544         Entry entry = table[index];
545         while (entry != null) {
546             if ((hash == entry.hash) && key.equals(entry.getKey())) {
547                 Object result = entry.getValue();
548                 entry.setValue(value);
549                 return result;
550             }
551             entry = entry.next;
552         }
553         this.size++; 
554         modCount++;
555         key = toReference(keyType, key, hash);
556         value = toReference(valueType, value, hash);
557         table[index] = new Entry(key, hash, value, table[index]);
558         return null;
559     }
560 
561 
562     /**
563      *  Removes the key and its associated value from this map.
564      *
565      *  @param key  the key to remove
566      *  @return the value associated with that key, or null if
567      *   the key was not in the map
568      */
569     public Object remove(Object key) {
570         if (key == null) return null;
571         purge();
572         int hash = key.hashCode();
573         int index = indexFor(hash);
574         Entry previous = null;
575         Entry entry = table[index];
576         while (entry != null) {
577             if ((hash == entry.hash) && key.equals(entry.getKey())) {
578                 if (previous == null) table[index] = entry.next;
579                 else previous.next = entry.next;
580                 this.size--;
581                 modCount++;
582                 return entry.getValue();
583             }
584             previous = entry;
585             entry = entry.next;
586         }
587         return null;
588     }
589 
590 
591     /**
592      *  Clears this map.
593      */
594     public void clear() {
595         Arrays.fill(table, null);
596         size = 0;
597         while (queue.poll() != null); // drain the queue
598     }
599 
600 
601     /**
602      *  Returns a set view of this map's entries.
603      *
604      *  @return a set view of this map's entries
605      */
606     public Set entrySet() {
607         if (entrySet != null) {
608             return entrySet;
609         } 
610         entrySet = new AbstractSet() {
611             public int size() {
612                 return ReferenceMap.this.size();
613             }
614 
615             public void clear() {
616                 ReferenceMap.this.clear();
617             }
618 
619             public boolean contains(Object o) {
620                 if (o == null) return false;
621                 if (!(o instanceof Map.Entry)) return false;
622                 Map.Entry e = (Map.Entry)o;
623                 Entry e2 = getEntry(e.getKey());
624                 return (e2 != null) && e.equals(e2);
625             }
626 
627             public boolean remove(Object o) {
628                 boolean r = contains(o);
629                 if (r) {
630                     Map.Entry e = (Map.Entry)o;
631                     ReferenceMap.this.remove(e.getKey());
632                 }
633                 return r;
634             }
635 
636             public Iterator iterator() {
637                 return new EntryIterator();
638             }
639 
640             public Object[] toArray() {
641                 return toArray(new Object[0]);
642             }
643 
644             public Object[] toArray(Object[] arr) {
645                 ArrayList list = new ArrayList();
646                 Iterator iterator = iterator();
647                 while (iterator.hasNext()) {
648                     Entry e = (Entry)iterator.next();
649                     list.add(new DefaultMapEntry(e.getKey(), e.getValue()));
650                 }
651                 return list.toArray(arr);
652             }
653         };
654         return entrySet;
655     }
656 
657 
658     /**
659      *  Returns a set view of this map's keys.
660      *
661      *  @return a set view of this map's keys
662      */
663     public Set keySet() {
664         if (keySet != null) return keySet;
665         keySet = new AbstractSet() {
666             public int size() {
667                 return ReferenceMap.this.size();
668             }
669 
670             public Iterator iterator() {
671                 return new KeyIterator();
672             }
673 
674             public boolean contains(Object o) {
675                 return containsKey(o);
676             }
677 
678 
679             public boolean remove(Object o) {
680                 Object r = ReferenceMap.this.remove(o);
681                 return r != null;
682             }
683 
684             public void clear() {
685                 ReferenceMap.this.clear();
686             }
687 
688             public Object[] toArray() {
689                 return toArray(new Object[0]);
690             }
691 
692             public Object[] toArray(Object[] array) {
693                 Collection c = new ArrayList(size());
694                 for (Iterator it = iterator(); it.hasNext(); ) {
695                     c.add(it.next());
696                 }
697                 return c.toArray(array);
698             }
699         };
700         return keySet;
701     }
702 
703 
704     /**
705      *  Returns a collection view of this map's values.
706      *
707      *  @return a collection view of this map's values.
708      */
709     public Collection values() {
710         if (values != null) return values;
711         values = new AbstractCollection()  {
712             public int size() {
713                 return ReferenceMap.this.size();
714             }
715 
716             public void clear() {
717                 ReferenceMap.this.clear();
718             }
719 
720             public Iterator iterator() {
721                 return new ValueIterator();
722             }
723 
724             public Object[] toArray() {
725                 return toArray(new Object[0]);
726             }
727 
728             public Object[] toArray(Object[] array) {
729                 Collection c = new ArrayList(size());
730                 for (Iterator it = iterator(); it.hasNext(); ) {
731                     c.add(it.next());
732                 }
733                 return c.toArray(array);
734             }
735         };
736         return values;
737     }
738 
739 
740     // If getKey() or getValue() returns null, it means
741     // the mapping is stale and should be removed.
742     private class Entry implements Map.Entry, KeyValue {
743 
744         Object key;
745         Object value;
746         int hash;
747         Entry next;
748 
749 
750         public Entry(Object key, int hash, Object value, Entry next) {
751             this.key = key;
752             this.hash = hash;
753             this.value = value;
754             this.next = next;
755         }
756 
757 
758         public Object getKey() {
759             return (keyType > HARD) ? ((Reference)key).get() : key;
760         }
761 
762 
763         public Object getValue() {
764             return (valueType > HARD) ? ((Reference)value).get() : value;
765         }
766 
767 
768         public Object setValue(Object object) {
769             Object old = getValue();
770             if (valueType > HARD) ((Reference)value).clear();
771             value = toReference(valueType, object, hash);
772             return old;
773         }
774 
775 
776         public boolean equals(Object o) {
777             if (o == null) return false;
778             if (o == this) return true;
779             if (!(o instanceof Map.Entry)) return false;
780             
781             Map.Entry entry = (Map.Entry)o;
782             Object key = entry.getKey();
783             Object value = entry.getValue();
784             if ((key == null) || (value == null)) return false;
785             return key.equals(getKey()) && value.equals(getValue());
786         }
787 
788 
789         public int hashCode() {
790             Object v = getValue();
791             return hash ^ ((v == null) ? 0 : v.hashCode());
792         }
793 
794 
795         public String toString() {
796             return getKey() + "=" + getValue();
797         }
798 
799 
800         boolean purge(Reference ref) {
801             boolean r = (keyType > HARD) && (key == ref);
802             r = r || ((valueType > HARD) && (value == ref));
803             if (r) {
804                 if (keyType > HARD) ((Reference)key).clear();
805                 if (valueType > HARD) {
806                     ((Reference)value).clear();
807                 } else if (purgeValues) {
808                     value = null;
809                 }
810             }
811             return r;
812         }
813     }
814 
815 
816     private class EntryIterator implements Iterator {
817         // These fields keep track of where we are in the table.
818         int index;
819         Entry entry;
820         Entry previous;
821 
822         // These Object fields provide hard references to the
823         // current and next entry; this assures that if hasNext()
824         // returns true, next() will actually return a valid element.
825         Object nextKey, nextValue;
826         Object currentKey, currentValue;
827 
828         int expectedModCount;
829 
830 
831         public EntryIterator() {
832             index = (size() != 0 ? table.length : 0);
833             // have to do this here!  size() invocation above
834             // may have altered the modCount.
835             expectedModCount = modCount;
836         }
837 
838 
839         public boolean hasNext() {
840             checkMod();
841             while (nextNull()) {
842                 Entry e = entry;
843                 int i = index;
844                 while ((e == null) && (i > 0)) {
845                     i--;
846                     e = table[i];
847                 }
848                 entry = e;
849                 index = i;
850                 if (e == null) {
851                     currentKey = null;
852                     currentValue = null;
853                     return false;
854                 }
855                 nextKey = e.getKey();
856                 nextValue = e.getValue();
857                 if (nextNull()) entry = entry.next;
858             }
859             return true;
860         }
861 
862 
863         private void checkMod() {
864             if (modCount != expectedModCount) {
865                 throw new ConcurrentModificationException();
866             }
867         }
868 
869 
870         private boolean nextNull() {
871             return (nextKey == null) || (nextValue == null);
872         }
873 
874         protected Entry nextEntry() {    
875             checkMod();
876             if (nextNull() && !hasNext()) throw new NoSuchElementException();
877             previous = entry;
878             entry = entry.next;
879             currentKey = nextKey;
880             currentValue = nextValue;
881             nextKey = null;
882             nextValue = null;
883             return previous;
884         }
885 
886 
887         public Object next() {
888             return nextEntry();
889         }
890 
891 
892         public void remove() {
893             checkMod();
894             if (previous == null) throw new IllegalStateException();
895             ReferenceMap.this.remove(currentKey);
896             previous = null;
897             currentKey = null;
898             currentValue = null;
899             expectedModCount = modCount;
900         }
901 
902     }
903 
904 
905     private class ValueIterator extends EntryIterator {
906         public Object next() {
907             return nextEntry().getValue();
908         }
909     }
910 
911 
912     private class KeyIterator extends EntryIterator {
913         public Object next() {
914             return nextEntry().getKey();
915         }
916     }
917 
918 
919 
920     // These two classes store the hashCode of the key of
921     // of the mapping, so that after they're dequeued a quick
922     // lookup of the bucket in the table can occur.
923 
924 
925     private static class SoftRef extends SoftReference {
926         private int hash;
927 
928 
929         public SoftRef(int hash, Object r, ReferenceQueue q) {
930             super(r, q);
931             this.hash = hash;
932         }
933 
934 
935         public int hashCode() {
936             return hash;
937         }
938     }
939 
940 
941     private static class WeakRef extends WeakReference {
942         private int hash;
943 
944 
945         public WeakRef(int hash, Object r, ReferenceQueue q) {
946             super(r, q);
947             this.hash = hash;
948         }
949 
950 
951         public int hashCode() {
952             return hash;
953         }
954     }
955 
956 
957 }