    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 }