WeakIdentityHashMap


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