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