Home » openjdk-7 » java » util » [javadoc | source]

    1   /*
    2    * Copyright (c) 1998, 2010, Oracle and/or its affiliates. All rights reserved.
    3    * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
    4    *
    5    * This code is free software; you can redistribute it and/or modify it
    6    * under the terms of the GNU General Public License version 2 only, as
    7    * published by the Free Software Foundation.  Oracle designates this
    8    * particular file as subject to the "Classpath" exception as provided
    9    * by Oracle in the LICENSE file that accompanied this code.
   10    *
   11    * This code is distributed in the hope that it will be useful, but WITHOUT
   12    * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
   13    * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
   14    * version 2 for more details (a copy is included in the LICENSE file that
   15    * accompanied this code).
   16    *
   17    * You should have received a copy of the GNU General Public License version
   18    * 2 along with this work; if not, write to the Free Software Foundation,
   19    * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
   20    *
   21    * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
   22    * or visit www.oracle.com if you need additional information or have any
   23    * questions.
   24    */
   25   
   26   package java.util;
   27   import java.lang.ref.WeakReference;
   28   import java.lang.ref.ReferenceQueue;
   29   
   30   
   31   /**
   32    * Hash table based implementation of the <tt>Map</tt> interface, with
   33    * <em>weak keys</em>.
   34    * An entry in a <tt>WeakHashMap</tt> will automatically be removed when
   35    * its key is no longer in ordinary use.  More precisely, the presence of a
   36    * mapping for a given key will not prevent the key from being discarded by the
   37    * garbage collector, that is, made finalizable, finalized, and then reclaimed.
   38    * When a key has been discarded its entry is effectively removed from the map,
   39    * so this class behaves somewhat differently from other <tt>Map</tt>
   40    * implementations.
   41    *
   42    * <p> Both null values and the null key are supported. This class has
   43    * performance characteristics similar to those of the <tt>HashMap</tt>
   44    * class, and has the same efficiency parameters of <em>initial capacity</em>
   45    * and <em>load factor</em>.
   46    *
   47    * <p> Like most collection classes, this class is not synchronized.
   48    * A synchronized <tt>WeakHashMap</tt> may be constructed using the
   49    * {@link Collections#synchronizedMap Collections.synchronizedMap}
   50    * method.
   51    *
   52    * <p> This class is intended primarily for use with key objects whose
   53    * <tt>equals</tt> methods test for object identity using the
   54    * <tt>==</tt> operator.  Once such a key is discarded it can never be
   55    * recreated, so it is impossible to do a lookup of that key in a
   56    * <tt>WeakHashMap</tt> at some later time and be surprised that its entry
   57    * has been removed.  This class will work perfectly well with key objects
   58    * whose <tt>equals</tt> methods are not based upon object identity, such
   59    * as <tt>String</tt> instances.  With such recreatable key objects,
   60    * however, the automatic removal of <tt>WeakHashMap</tt> entries whose
   61    * keys have been discarded may prove to be confusing.
   62    *
   63    * <p> The behavior of the <tt>WeakHashMap</tt> class depends in part upon
   64    * the actions of the garbage collector, so several familiar (though not
   65    * required) <tt>Map</tt> invariants do not hold for this class.  Because
   66    * the garbage collector may discard keys at any time, a
   67    * <tt>WeakHashMap</tt> may behave as though an unknown thread is silently
   68    * removing entries.  In particular, even if you synchronize on a
   69    * <tt>WeakHashMap</tt> instance and invoke none of its mutator methods, it
   70    * is possible for the <tt>size</tt> method to return smaller values over
   71    * time, for the <tt>isEmpty</tt> method to return <tt>false</tt> and
   72    * then <tt>true</tt>, for the <tt>containsKey</tt> method to return
   73    * <tt>true</tt> and later <tt>false</tt> for a given key, for the
   74    * <tt>get</tt> method to return a value for a given key but later return
   75    * <tt>null</tt>, for the <tt>put</tt> method to return
   76    * <tt>null</tt> and the <tt>remove</tt> method to return
   77    * <tt>false</tt> for a key that previously appeared to be in the map, and
   78    * for successive examinations of the key set, the value collection, and
   79    * the entry set to yield successively smaller numbers of elements.
   80    *
   81    * <p> Each key object in a <tt>WeakHashMap</tt> is stored indirectly as
   82    * the referent of a weak reference.  Therefore a key will automatically be
   83    * removed only after the weak references to it, both inside and outside of the
   84    * map, have been cleared by the garbage collector.
   85    *
   86    * <p> <strong>Implementation note:</strong> The value objects in a
   87    * <tt>WeakHashMap</tt> are held by ordinary strong references.  Thus care
   88    * should be taken to ensure that value objects do not strongly refer to their
   89    * own keys, either directly or indirectly, since that will prevent the keys
   90    * from being discarded.  Note that a value object may refer indirectly to its
   91    * key via the <tt>WeakHashMap</tt> itself; that is, a value object may
   92    * strongly refer to some other key object whose associated value object, in
   93    * turn, strongly refers to the key of the first value object.  One way
   94    * to deal with this is to wrap values themselves within
   95    * <tt>WeakReferences</tt> before
   96    * inserting, as in: <tt>m.put(key, new WeakReference(value))</tt>,
   97    * and then unwrapping upon each <tt>get</tt>.
   98    *
   99    * <p>The iterators returned by the <tt>iterator</tt> method of the collections
  100    * returned by all of this class's "collection view methods" are
  101    * <i>fail-fast</i>: if the map is structurally modified at any time after the
  102    * iterator is created, in any way except through the iterator's own
  103    * <tt>remove</tt> method, the iterator will throw a {@link
  104    * ConcurrentModificationException}.  Thus, in the face of concurrent
  105    * modification, the iterator fails quickly and cleanly, rather than risking
  106    * arbitrary, non-deterministic behavior at an undetermined time in the future.
  107    *
  108    * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
  109    * as it is, generally speaking, impossible to make any hard guarantees in the
  110    * presence of unsynchronized concurrent modification.  Fail-fast iterators
  111    * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
  112    * Therefore, it would be wrong to write a program that depended on this
  113    * exception for its correctness:  <i>the fail-fast behavior of iterators
  114    * should be used only to detect bugs.</i>
  115    *
  116    * <p>This class is a member of the
  117    * <a href="{@docRoot}/../technotes/guides/collections/index.html">
  118    * Java Collections Framework</a>.
  119    *
  120    * @param <K> the type of keys maintained by this map
  121    * @param <V> the type of mapped values
  122    *
  123    * @author      Doug Lea
  124    * @author      Josh Bloch
  125    * @author      Mark Reinhold
  126    * @since       1.2
  127    * @see         java.util.HashMap
  128    * @see         java.lang.ref.WeakReference
  129    */
  130   public class WeakHashMap<K,V>
  131       extends AbstractMap<K,V>
  132       implements Map<K,V> {
  133   
  134       /**
  135        * The default initial capacity -- MUST be a power of two.
  136        */
  137       private static final int DEFAULT_INITIAL_CAPACITY = 16;
  138   
  139       /**
  140        * The maximum capacity, used if a higher value is implicitly specified
  141        * by either of the constructors with arguments.
  142        * MUST be a power of two <= 1<<30.
  143        */
  144       private static final int MAXIMUM_CAPACITY = 1 << 30;
  145   
  146       /**
  147        * The load factor used when none specified in constructor.
  148        */
  149       private static final float DEFAULT_LOAD_FACTOR = 0.75f;
  150   
  151       /**
  152        * The table, resized as necessary. Length MUST Always be a power of two.
  153        */
  154       Entry<K,V>[] table;
  155   
  156       /**
  157        * The number of key-value mappings contained in this weak hash map.
  158        */
  159       private int size;
  160   
  161       /**
  162        * The next size value at which to resize (capacity * load factor).
  163        */
  164       private int threshold;
  165   
  166       /**
  167        * The load factor for the hash table.
  168        */
  169       private final float loadFactor;
  170   
  171       /**
  172        * Reference queue for cleared WeakEntries
  173        */
  174       private final ReferenceQueue<Object> queue = new ReferenceQueue<>();
  175   
  176       /**
  177        * The number of times this WeakHashMap has been structurally modified.
  178        * Structural modifications are those that change the number of
  179        * mappings in the map or otherwise modify its internal structure
  180        * (e.g., rehash).  This field is used to make iterators on
  181        * Collection-views of the map fail-fast.
  182        *
  183        * @see ConcurrentModificationException
  184        */
  185       int modCount;
  186   
  187       @SuppressWarnings("unchecked")
  188       private Entry<K,V>[] newTable(int n) {
  189           return (Entry<K,V>[]) new Entry[n];
  190       }
  191   
  192       /**
  193        * Constructs a new, empty <tt>WeakHashMap</tt> with the given initial
  194        * capacity and the given load factor.
  195        *
  196        * @param  initialCapacity The initial capacity of the <tt>WeakHashMap</tt>
  197        * @param  loadFactor      The load factor of the <tt>WeakHashMap</tt>
  198        * @throws IllegalArgumentException if the initial capacity is negative,
  199        *         or if the load factor is nonpositive.
  200        */
  201       public WeakHashMap(int initialCapacity, float loadFactor) {
  202           if (initialCapacity < 0)
  203               throw new IllegalArgumentException("Illegal Initial Capacity: "+
  204                                                  initialCapacity);
  205           if (initialCapacity > MAXIMUM_CAPACITY)
  206               initialCapacity = MAXIMUM_CAPACITY;
  207   
  208           if (loadFactor <= 0 || Float.isNaN(loadFactor))
  209               throw new IllegalArgumentException("Illegal Load factor: "+
  210                                                  loadFactor);
  211           int capacity = 1;
  212           while (capacity < initialCapacity)
  213               capacity <<= 1;
  214           table = newTable(capacity);
  215           this.loadFactor = loadFactor;
  216           threshold = (int)(capacity * loadFactor);
  217       }
  218   
  219       /**
  220        * Constructs a new, empty <tt>WeakHashMap</tt> with the given initial
  221        * capacity and the default load factor (0.75).
  222        *
  223        * @param  initialCapacity The initial capacity of the <tt>WeakHashMap</tt>
  224        * @throws IllegalArgumentException if the initial capacity is negative
  225        */
  226       public WeakHashMap(int initialCapacity) {
  227           this(initialCapacity, DEFAULT_LOAD_FACTOR);
  228       }
  229   
  230       /**
  231        * Constructs a new, empty <tt>WeakHashMap</tt> with the default initial
  232        * capacity (16) and load factor (0.75).
  233        */
  234       public WeakHashMap() {
  235           this.loadFactor = DEFAULT_LOAD_FACTOR;
  236           threshold = DEFAULT_INITIAL_CAPACITY;
  237           table = newTable(DEFAULT_INITIAL_CAPACITY);
  238       }
  239   
  240       /**
  241        * Constructs a new <tt>WeakHashMap</tt> with the same mappings as the
  242        * specified map.  The <tt>WeakHashMap</tt> is created with the default
  243        * load factor (0.75) and an initial capacity sufficient to hold the
  244        * mappings in the specified map.
  245        *
  246        * @param   m the map whose mappings are to be placed in this map
  247        * @throws  NullPointerException if the specified map is null
  248        * @since   1.3
  249        */
  250       public WeakHashMap(Map<? extends K, ? extends V> m) {
  251           this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, 16),
  252                DEFAULT_LOAD_FACTOR);
  253           putAll(m);
  254       }
  255   
  256       // internal utilities
  257   
  258       /**
  259        * Value representing null keys inside tables.
  260        */
  261       private static final Object NULL_KEY = new Object();
  262   
  263       /**
  264        * Use NULL_KEY for key if it is null.
  265        */
  266       private static Object maskNull(Object key) {
  267           return (key == null) ? NULL_KEY : key;
  268       }
  269   
  270       /**
  271        * Returns internal representation of null key back to caller as null.
  272        */
  273       static Object unmaskNull(Object key) {
  274           return (key == NULL_KEY) ? null : key;
  275       }
  276   
  277       /**
  278        * Checks for equality of non-null reference x and possibly-null y.  By
  279        * default uses Object.equals.
  280        */
  281       private static boolean eq(Object x, Object y) {
  282           return x == y || x.equals(y);
  283       }
  284   
  285       /**
  286        * Returns index for hash code h.
  287        */
  288       private static int indexFor(int h, int length) {
  289           return h & (length-1);
  290       }
  291   
  292       /**
  293        * Expunges stale entries from the table.
  294        */
  295       private void expungeStaleEntries() {
  296           for (Object x; (x = queue.poll()) != null; ) {
  297               synchronized (queue) {
  298                   @SuppressWarnings("unchecked")
  299                       Entry<K,V> e = (Entry<K,V>) x;
  300                   int i = indexFor(e.hash, table.length);
  301   
  302                   Entry<K,V> prev = table[i];
  303                   Entry<K,V> p = prev;
  304                   while (p != null) {
  305                       Entry<K,V> next = p.next;
  306                       if (p == e) {
  307                           if (prev == e)
  308                               table[i] = next;
  309                           else
  310                               prev.next = next;
  311                           // Must not null out e.next;
  312                           // stale entries may be in use by a HashIterator
  313                           e.value = null; // Help GC
  314                           size--;
  315                           break;
  316                       }
  317                       prev = p;
  318                       p = next;
  319                   }
  320               }
  321           }
  322       }
  323   
  324       /**
  325        * Returns the table after first expunging stale entries.
  326        */
  327       private Entry<K,V>[] getTable() {
  328           expungeStaleEntries();
  329           return table;
  330       }
  331   
  332       /**
  333        * Returns the number of key-value mappings in this map.
  334        * This result is a snapshot, and may not reflect unprocessed
  335        * entries that will be removed before next attempted access
  336        * because they are no longer referenced.
  337        */
  338       public int size() {
  339           if (size == 0)
  340               return 0;
  341           expungeStaleEntries();
  342           return size;
  343       }
  344   
  345       /**
  346        * Returns <tt>true</tt> if this map contains no key-value mappings.
  347        * This result is a snapshot, and may not reflect unprocessed
  348        * entries that will be removed before next attempted access
  349        * because they are no longer referenced.
  350        */
  351       public boolean isEmpty() {
  352           return size() == 0;
  353       }
  354   
  355       /**
  356        * Returns the value to which the specified key is mapped,
  357        * or {@code null} if this map contains no mapping for the key.
  358        *
  359        * <p>More formally, if this map contains a mapping from a key
  360        * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
  361        * key.equals(k))}, then this method returns {@code v}; otherwise
  362        * it returns {@code null}.  (There can be at most one such mapping.)
  363        *
  364        * <p>A return value of {@code null} does not <i>necessarily</i>
  365        * indicate that the map contains no mapping for the key; it's also
  366        * possible that the map explicitly maps the key to {@code null}.
  367        * The {@link #containsKey containsKey} operation may be used to
  368        * distinguish these two cases.
  369        *
  370        * @see #put(Object, Object)
  371        */
  372       public V get(Object key) {
  373           Object k = maskNull(key);
  374           int h = HashMap.hash(k.hashCode());
  375           Entry<K,V>[] tab = getTable();
  376           int index = indexFor(h, tab.length);
  377           Entry<K,V> e = tab[index];
  378           while (e != null) {
  379               if (e.hash == h && eq(k, e.get()))
  380                   return e.value;
  381               e = e.next;
  382           }
  383           return null;
  384       }
  385   
  386       /**
  387        * Returns <tt>true</tt> if this map contains a mapping for the
  388        * specified key.
  389        *
  390        * @param  key   The key whose presence in this map is to be tested
  391        * @return <tt>true</tt> if there is a mapping for <tt>key</tt>;
  392        *         <tt>false</tt> otherwise
  393        */
  394       public boolean containsKey(Object key) {
  395           return getEntry(key) != null;
  396       }
  397   
  398       /**
  399        * Returns the entry associated with the specified key in this map.
  400        * Returns null if the map contains no mapping for this key.
  401        */
  402       Entry<K,V> getEntry(Object key) {
  403           Object k = maskNull(key);
  404           int h = HashMap.hash(k.hashCode());
  405           Entry<K,V>[] tab = getTable();
  406           int index = indexFor(h, tab.length);
  407           Entry<K,V> e = tab[index];
  408           while (e != null && !(e.hash == h && eq(k, e.get())))
  409               e = e.next;
  410           return e;
  411       }
  412   
  413       /**
  414        * Associates the specified value with the specified key in this map.
  415        * If the map previously contained a mapping for this key, the old
  416        * value is replaced.
  417        *
  418        * @param key key with which the specified value is to be associated.
  419        * @param value value to be associated with the specified key.
  420        * @return the previous value associated with <tt>key</tt>, or
  421        *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
  422        *         (A <tt>null</tt> return can also indicate that the map
  423        *         previously associated <tt>null</tt> with <tt>key</tt>.)
  424        */
  425       public V put(K key, V value) {
  426           Object k = maskNull(key);
  427           int h = HashMap.hash(k.hashCode());
  428           Entry<K,V>[] tab = getTable();
  429           int i = indexFor(h, tab.length);
  430   
  431           for (Entry<K,V> e = tab[i]; e != null; e = e.next) {
  432               if (h == e.hash && eq(k, e.get())) {
  433                   V oldValue = e.value;
  434                   if (value != oldValue)
  435                       e.value = value;
  436                   return oldValue;
  437               }
  438           }
  439   
  440           modCount++;
  441           Entry<K,V> e = tab[i];
  442           tab[i] = new Entry<>(k, value, queue, h, e);
  443           if (++size >= threshold)
  444               resize(tab.length * 2);
  445           return null;
  446       }
  447   
  448       /**
  449        * Rehashes the contents of this map into a new array with a
  450        * larger capacity.  This method is called automatically when the
  451        * number of keys in this map reaches its threshold.
  452        *
  453        * If current capacity is MAXIMUM_CAPACITY, this method does not
  454        * resize the map, but sets threshold to Integer.MAX_VALUE.
  455        * This has the effect of preventing future calls.
  456        *
  457        * @param newCapacity the new capacity, MUST be a power of two;
  458        *        must be greater than current capacity unless current
  459        *        capacity is MAXIMUM_CAPACITY (in which case value
  460        *        is irrelevant).
  461        */
  462       void resize(int newCapacity) {
  463           Entry<K,V>[] oldTable = getTable();
  464           int oldCapacity = oldTable.length;
  465           if (oldCapacity == MAXIMUM_CAPACITY) {
  466               threshold = Integer.MAX_VALUE;
  467               return;
  468           }
  469   
  470           Entry<K,V>[] newTable = newTable(newCapacity);
  471           transfer(oldTable, newTable);
  472           table = newTable;
  473   
  474           /*
  475            * If ignoring null elements and processing ref queue caused massive
  476            * shrinkage, then restore old table.  This should be rare, but avoids
  477            * unbounded expansion of garbage-filled tables.
  478            */
  479           if (size >= threshold / 2) {
  480               threshold = (int)(newCapacity * loadFactor);
  481           } else {
  482               expungeStaleEntries();
  483               transfer(newTable, oldTable);
  484               table = oldTable;
  485           }
  486       }
  487   
  488       /** Transfers all entries from src to dest tables */
  489       private void transfer(Entry<K,V>[] src, Entry<K,V>[] dest) {
  490           for (int j = 0; j < src.length; ++j) {
  491               Entry<K,V> e = src[j];
  492               src[j] = null;
  493               while (e != null) {
  494                   Entry<K,V> next = e.next;
  495                   Object key = e.get();
  496                   if (key == null) {
  497                       e.next = null;  // Help GC
  498                       e.value = null; //  "   "
  499                       size--;
  500                   } else {
  501                       int i = indexFor(e.hash, dest.length);
  502                       e.next = dest[i];
  503                       dest[i] = e;
  504                   }
  505                   e = next;
  506               }
  507           }
  508       }
  509   
  510       /**
  511        * Copies all of the mappings from the specified map to this map.
  512        * These mappings will replace any mappings that this map had for any
  513        * of the keys currently in the specified map.
  514        *
  515        * @param m mappings to be stored in this map.
  516        * @throws  NullPointerException if the specified map is null.
  517        */
  518       public void putAll(Map<? extends K, ? extends V> m) {
  519           int numKeysToBeAdded = m.size();
  520           if (numKeysToBeAdded == 0)
  521               return;
  522   
  523           /*
  524            * Expand the map if the map if the number of mappings to be added
  525            * is greater than or equal to threshold.  This is conservative; the
  526            * obvious condition is (m.size() + size) >= threshold, but this
  527            * condition could result in a map with twice the appropriate capacity,
  528            * if the keys to be added overlap with the keys already in this map.
  529            * By using the conservative calculation, we subject ourself
  530            * to at most one extra resize.
  531            */
  532           if (numKeysToBeAdded > threshold) {
  533               int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
  534               if (targetCapacity > MAXIMUM_CAPACITY)
  535                   targetCapacity = MAXIMUM_CAPACITY;
  536               int newCapacity = table.length;
  537               while (newCapacity < targetCapacity)
  538                   newCapacity <<= 1;
  539               if (newCapacity > table.length)
  540                   resize(newCapacity);
  541           }
  542   
  543           for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
  544               put(e.getKey(), e.getValue());
  545       }
  546   
  547       /**
  548        * Removes the mapping for a key from this weak hash map if it is present.
  549        * More formally, if this map contains a mapping from key <tt>k</tt> to
  550        * value <tt>v</tt> such that <code>(key==null ?  k==null :
  551        * key.equals(k))</code>, that mapping is removed.  (The map can contain
  552        * at most one such mapping.)
  553        *
  554        * <p>Returns the value to which this map previously associated the key,
  555        * or <tt>null</tt> if the map contained no mapping for the key.  A
  556        * return value of <tt>null</tt> does not <i>necessarily</i> indicate
  557        * that the map contained no mapping for the key; it's also possible
  558        * that the map explicitly mapped the key to <tt>null</tt>.
  559        *
  560        * <p>The map will not contain a mapping for the specified key once the
  561        * call returns.
  562        *
  563        * @param key key whose mapping is to be removed from the map
  564        * @return the previous value associated with <tt>key</tt>, or
  565        *         <tt>null</tt> if there was no mapping for <tt>key</tt>
  566        */
  567       public V remove(Object key) {
  568           Object k = maskNull(key);
  569           int h = HashMap.hash(k.hashCode());
  570           Entry<K,V>[] tab = getTable();
  571           int i = indexFor(h, tab.length);
  572           Entry<K,V> prev = tab[i];
  573           Entry<K,V> e = prev;
  574   
  575           while (e != null) {
  576               Entry<K,V> next = e.next;
  577               if (h == e.hash && eq(k, e.get())) {
  578                   modCount++;
  579                   size--;
  580                   if (prev == e)
  581                       tab[i] = next;
  582                   else
  583                       prev.next = next;
  584                   return e.value;
  585               }
  586               prev = e;
  587               e = next;
  588           }
  589   
  590           return null;
  591       }
  592   
  593       /** Special version of remove needed by Entry set */
  594       boolean removeMapping(Object o) {
  595           if (!(o instanceof Map.Entry))
  596               return false;
  597           Entry<K,V>[] tab = getTable();
  598           Map.Entry<?,?> entry = (Map.Entry<?,?>)o;
  599           Object k = maskNull(entry.getKey());
  600           int h = HashMap.hash(k.hashCode());
  601           int i = indexFor(h, tab.length);
  602           Entry<K,V> prev = tab[i];
  603           Entry<K,V> e = prev;
  604   
  605           while (e != null) {
  606               Entry<K,V> next = e.next;
  607               if (h == e.hash && e.equals(entry)) {
  608                   modCount++;
  609                   size--;
  610                   if (prev == e)
  611                       tab[i] = next;
  612                   else
  613                       prev.next = next;
  614                   return true;
  615               }
  616               prev = e;
  617               e = next;
  618           }
  619   
  620           return false;
  621       }
  622   
  623       /**
  624        * Removes all of the mappings from this map.
  625        * The map will be empty after this call returns.
  626        */
  627       public void clear() {
  628           // clear out ref queue. We don't need to expunge entries
  629           // since table is getting cleared.
  630           while (queue.poll() != null)
  631               ;
  632   
  633           modCount++;
  634           Arrays.fill(table, null);
  635           size = 0;
  636   
  637           // Allocation of array may have caused GC, which may have caused
  638           // additional entries to go stale.  Removing these entries from the
  639           // reference queue will make them eligible for reclamation.
  640           while (queue.poll() != null)
  641               ;
  642       }
  643   
  644       /**
  645        * Returns <tt>true</tt> if this map maps one or more keys to the
  646        * specified value.
  647        *
  648        * @param value value whose presence in this map is to be tested
  649        * @return <tt>true</tt> if this map maps one or more keys to the
  650        *         specified value
  651        */
  652       public boolean containsValue(Object value) {
  653           if (value==null)
  654               return containsNullValue();
  655   
  656           Entry<K,V>[] tab = getTable();
  657           for (int i = tab.length; i-- > 0;)
  658               for (Entry<K,V> e = tab[i]; e != null; e = e.next)
  659                   if (value.equals(e.value))
  660                       return true;
  661           return false;
  662       }
  663   
  664       /**
  665        * Special-case code for containsValue with null argument
  666        */
  667       private boolean containsNullValue() {
  668           Entry<K,V>[] tab = getTable();
  669           for (int i = tab.length; i-- > 0;)
  670               for (Entry<K,V> e = tab[i]; e != null; e = e.next)
  671                   if (e.value==null)
  672                       return true;
  673           return false;
  674       }
  675   
  676       /**
  677        * The entries in this hash table extend WeakReference, using its main ref
  678        * field as the key.
  679        */
  680       private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
  681           V value;
  682           final int hash;
  683           Entry<K,V> next;
  684   
  685           /**
  686            * Creates new entry.
  687            */
  688           Entry(Object key, V value,
  689                 ReferenceQueue<Object> queue,
  690                 int hash, Entry<K,V> next) {
  691               super(key, queue);
  692               this.value = value;
  693               this.hash  = hash;
  694               this.next  = next;
  695           }
  696   
  697           @SuppressWarnings("unchecked")
  698           public K getKey() {
  699               return (K) WeakHashMap.unmaskNull(get());
  700           }
  701   
  702           public V getValue() {
  703               return value;
  704           }
  705   
  706           public V setValue(V newValue) {
  707               V oldValue = value;
  708               value = newValue;
  709               return oldValue;
  710           }
  711   
  712           public boolean equals(Object o) {
  713               if (!(o instanceof Map.Entry))
  714                   return false;
  715               Map.Entry<?,?> e = (Map.Entry<?,?>)o;
  716               K k1 = getKey();
  717               Object k2 = e.getKey();
  718               if (k1 == k2 || (k1 != null && k1.equals(k2))) {
  719                   V v1 = getValue();
  720                   Object v2 = e.getValue();
  721                   if (v1 == v2 || (v1 != null && v1.equals(v2)))
  722                       return true;
  723               }
  724               return false;
  725           }
  726   
  727           public int hashCode() {
  728               K k = getKey();
  729               V v = getValue();
  730               return ((k==null ? 0 : k.hashCode()) ^
  731                       (v==null ? 0 : v.hashCode()));
  732           }
  733   
  734           public String toString() {
  735               return getKey() + "=" + getValue();
  736           }
  737       }
  738   
  739       private abstract class HashIterator<T> implements Iterator<T> {
  740           private int index;
  741           private Entry<K,V> entry = null;
  742           private Entry<K,V> lastReturned = null;
  743           private int expectedModCount = modCount;
  744   
  745           /**
  746            * Strong reference needed to avoid disappearance of key
  747            * between hasNext and next
  748            */
  749           private Object nextKey = null;
  750   
  751           /**
  752            * Strong reference needed to avoid disappearance of key
  753            * between nextEntry() and any use of the entry
  754            */
  755           private Object currentKey = null;
  756   
  757           HashIterator() {
  758               index = isEmpty() ? 0 : table.length;
  759           }
  760   
  761           public boolean hasNext() {
  762               Entry<K,V>[] t = table;
  763   
  764               while (nextKey == null) {
  765                   Entry<K,V> e = entry;
  766                   int i = index;
  767                   while (e == null && i > 0)
  768                       e = t[--i];
  769                   entry = e;
  770                   index = i;
  771                   if (e == null) {
  772                       currentKey = null;
  773                       return false;
  774                   }
  775                   nextKey = e.get(); // hold on to key in strong ref
  776                   if (nextKey == null)
  777                       entry = entry.next;
  778               }
  779               return true;
  780           }
  781   
  782           /** The common parts of next() across different types of iterators */
  783           protected Entry<K,V> nextEntry() {
  784               if (modCount != expectedModCount)
  785                   throw new ConcurrentModificationException();
  786               if (nextKey == null && !hasNext())
  787                   throw new NoSuchElementException();
  788   
  789               lastReturned = entry;
  790               entry = entry.next;
  791               currentKey = nextKey;
  792               nextKey = null;
  793               return lastReturned;
  794           }
  795   
  796           public void remove() {
  797               if (lastReturned == null)
  798                   throw new IllegalStateException();
  799               if (modCount != expectedModCount)
  800                   throw new ConcurrentModificationException();
  801   
  802               WeakHashMap.this.remove(currentKey);
  803               expectedModCount = modCount;
  804               lastReturned = null;
  805               currentKey = null;
  806           }
  807   
  808       }
  809   
  810       private class ValueIterator extends HashIterator<V> {
  811           public V next() {
  812               return nextEntry().value;
  813           }
  814       }
  815   
  816       private class KeyIterator extends HashIterator<K> {
  817           public K next() {
  818               return nextEntry().getKey();
  819           }
  820       }
  821   
  822       private class EntryIterator extends HashIterator<Map.Entry<K,V>> {
  823           public Map.Entry<K,V> next() {
  824               return nextEntry();
  825           }
  826       }
  827   
  828       // Views
  829   
  830       private transient Set<Map.Entry<K,V>> entrySet = null;
  831   
  832       /**
  833        * Returns a {@link Set} view of the keys contained in this map.
  834        * The set is backed by the map, so changes to the map are
  835        * reflected in the set, and vice-versa.  If the map is modified
  836        * while an iteration over the set is in progress (except through
  837        * the iterator's own <tt>remove</tt> operation), the results of
  838        * the iteration are undefined.  The set supports element removal,
  839        * which removes the corresponding mapping from the map, via the
  840        * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
  841        * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
  842        * operations.  It does not support the <tt>add</tt> or <tt>addAll</tt>
  843        * operations.
  844        */
  845       public Set<K> keySet() {
  846           Set<K> ks = keySet;
  847           return (ks != null ? ks : (keySet = new KeySet()));
  848       }
  849   
  850       private class KeySet extends AbstractSet<K> {
  851           public Iterator<K> iterator() {
  852               return new KeyIterator();
  853           }
  854   
  855           public int size() {
  856               return WeakHashMap.this.size();
  857           }
  858   
  859           public boolean contains(Object o) {
  860               return containsKey(o);
  861           }
  862   
  863           public boolean remove(Object o) {
  864               if (containsKey(o)) {
  865                   WeakHashMap.this.remove(o);
  866                   return true;
  867               }
  868               else
  869                   return false;
  870           }
  871   
  872           public void clear() {
  873               WeakHashMap.this.clear();
  874           }
  875       }
  876   
  877       /**
  878        * Returns a {@link Collection} view of the values contained in this map.
  879        * The collection is backed by the map, so changes to the map are
  880        * reflected in the collection, and vice-versa.  If the map is
  881        * modified while an iteration over the collection is in progress
  882        * (except through the iterator's own <tt>remove</tt> operation),
  883        * the results of the iteration are undefined.  The collection
  884        * supports element removal, which removes the corresponding
  885        * mapping from the map, via the <tt>Iterator.remove</tt>,
  886        * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
  887        * <tt>retainAll</tt> and <tt>clear</tt> operations.  It does not
  888        * support the <tt>add</tt> or <tt>addAll</tt> operations.
  889        */
  890       public Collection<V> values() {
  891           Collection<V> vs = values;
  892           return (vs != null) ? vs : (values = new Values());
  893       }
  894   
  895       private class Values extends AbstractCollection<V> {
  896           public Iterator<V> iterator() {
  897               return new ValueIterator();
  898           }
  899   
  900           public int size() {
  901               return WeakHashMap.this.size();
  902           }
  903   
  904           public boolean contains(Object o) {
  905               return containsValue(o);
  906           }
  907   
  908           public void clear() {
  909               WeakHashMap.this.clear();
  910           }
  911       }
  912   
  913       /**
  914        * Returns a {@link Set} view of the mappings contained in this map.
  915        * The set is backed by the map, so changes to the map are
  916        * reflected in the set, and vice-versa.  If the map is modified
  917        * while an iteration over the set is in progress (except through
  918        * the iterator's own <tt>remove</tt> operation, or through the
  919        * <tt>setValue</tt> operation on a map entry returned by the
  920        * iterator) the results of the iteration are undefined.  The set
  921        * supports element removal, which removes the corresponding
  922        * mapping from the map, via the <tt>Iterator.remove</tt>,
  923        * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
  924        * <tt>clear</tt> operations.  It does not support the
  925        * <tt>add</tt> or <tt>addAll</tt> operations.
  926        */
  927       public Set<Map.Entry<K,V>> entrySet() {
  928           Set<Map.Entry<K,V>> es = entrySet;
  929           return es != null ? es : (entrySet = new EntrySet());
  930       }
  931   
  932       private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
  933           public Iterator<Map.Entry<K,V>> iterator() {
  934               return new EntryIterator();
  935           }
  936   
  937           public boolean contains(Object o) {
  938               if (!(o instanceof Map.Entry))
  939                   return false;
  940               Map.Entry<?,?> e = (Map.Entry<?,?>)o;
  941               Entry<K,V> candidate = getEntry(e.getKey());
  942               return candidate != null && candidate.equals(e);
  943           }
  944   
  945           public boolean remove(Object o) {
  946               return removeMapping(o);
  947           }
  948   
  949           public int size() {
  950               return WeakHashMap.this.size();
  951           }
  952   
  953           public void clear() {
  954               WeakHashMap.this.clear();
  955           }
  956   
  957           private List<Map.Entry<K,V>> deepCopy() {
  958               List<Map.Entry<K,V>> list = new ArrayList<>(size());
  959               for (Map.Entry<K,V> e : this)
  960                   list.add(new AbstractMap.SimpleEntry<>(e));
  961               return list;
  962           }
  963   
  964           public Object[] toArray() {
  965               return deepCopy().toArray();
  966           }
  967   
  968           public <T> T[] toArray(T[] a) {
  969               return deepCopy().toArray(a);
  970           }
  971       }
  972   }

Home » openjdk-7 » java » util » [javadoc | source]