001    /* IdentityHashMap.java -- a class providing a hashtable data structure,
002       mapping Object --> Object, which uses object identity for hashing.
003       Copyright (C) 2001, 2002, 2004, 2005  Free Software Foundation, Inc.
004    
005    This file is part of GNU Classpath.
006    
007    GNU Classpath is free software; you can redistribute it and/or modify
008    it under the terms of the GNU General Public License as published by
009    the Free Software Foundation; either version 2, or (at your option)
010    any later version.
011    
012    GNU Classpath is distributed in the hope that it will be useful, but
013    WITHOUT ANY WARRANTY; without even the implied warranty of
014    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
015    General Public License for more details.
016    
017    You should have received a copy of the GNU General Public License
018    along with GNU Classpath; see the file COPYING.  If not, write to the
019    Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
020    02110-1301 USA.
021    
022    Linking this library statically or dynamically with other modules is
023    making a combined work based on this library.  Thus, the terms and
024    conditions of the GNU General Public License cover the whole
025    combination.
026    
027    As a special exception, the copyright holders of this library give you
028    permission to link this library with independent modules to produce an
029    executable, regardless of the license terms of these independent
030    modules, and to copy and distribute the resulting executable under
031    terms of your choice, provided that you also meet, for each linked
032    independent module, the terms and conditions of the license of that
033    module.  An independent module is a module which is not derived from
034    or based on this library.  If you modify this library, you may extend
035    this exception to your version of the library, but you are not
036    obligated to do so.  If you do not wish to do so, delete this
037    exception statement from your version. */
038    
039    package java.util;
040    
041    import java.io.IOException;
042    import java.io.ObjectInputStream;
043    import java.io.ObjectOutputStream;
044    import java.io.Serializable;
045    
046    /**
047     * This class provides a hashtable-backed implementation of the
048     * Map interface, but uses object identity to do its hashing.  In fact,
049     * it uses object identity for comparing values, as well. It uses a
050     * linear-probe hash table, which may have faster performance
051     * than the chaining employed by HashMap.
052     * <p>
053     *
054     * <em>WARNING: This is not a general purpose map. Because it uses
055     * System.identityHashCode and ==, instead of hashCode and equals, for
056     * comparison, it violated Map's general contract, and may cause
057     * undefined behavior when compared to other maps which are not
058     * IdentityHashMaps.  This is designed only for the rare cases when
059     * identity semantics are needed.</em> An example use is
060     * topology-preserving graph transformations, such as deep cloning,
061     * or as proxy object mapping such as in debugging.
062     * <p>
063     *
064     * This map permits <code>null</code> keys and values, and does not
065     * guarantee that elements will stay in the same order over time. The
066     * basic operations (<code>get</code> and <code>put</code>) take
067     * constant time, provided System.identityHashCode is decent. You can
068     * tune the behavior by specifying the expected maximum size. As more
069     * elements are added, the map may need to allocate a larger table,
070     * which can be expensive.
071     * <p>
072     *
073     * This implementation is unsynchronized.  If you want multi-thread
074     * access to be consistent, you must synchronize it, perhaps by using
075     * <code>Collections.synchronizedMap(new IdentityHashMap(...));</code>.
076     * The iterators are <i>fail-fast</i>, meaning that a structural modification
077     * made to the map outside of an iterator's remove method cause the
078     * iterator, and in the case of the entrySet, the Map.Entry, to
079     * fail with a {@link ConcurrentModificationException}.
080     *
081     * @author Tom Tromey (tromey@redhat.com)
082     * @author Eric Blake (ebb9@email.byu.edu)
083     * @see System#identityHashCode(Object)
084     * @see Collection
085     * @see Map
086     * @see HashMap
087     * @see TreeMap
088     * @see LinkedHashMap
089     * @see WeakHashMap
090     * @since 1.4
091     * @status updated to 1.4
092     */
093    public class IdentityHashMap<K,V> extends AbstractMap<K,V>
094      implements Map<K,V>, Serializable, Cloneable
095    {
096      /** The default capacity. */
097      private static final int DEFAULT_CAPACITY = 21;
098    
099      /**
100       * This object is used to mark a slot whose key or value is 'null'.
101       * This is more efficient than using a special value to mark an empty
102       * slot, because null entries are rare, empty slots are common, and
103       * the JVM will clear new arrays for us.
104       * Package visible for use by nested classes.
105       */
106      static final Object nullslot = new Object();
107    
108      /**
109       * Compatible with JDK 1.4.
110       */
111      private static final long serialVersionUID = 8188218128353913216L;
112    
113      /**
114       * The number of mappings in the table. Package visible for use by nested
115       * classes.
116       * @serial
117       */
118      int size;
119    
120      /**
121       * The table itself. Package visible for use by nested classes.
122       */
123      transient Object[] table;
124    
125      /**
126       * The number of structural modifications made so far. Package visible for
127       * use by nested classes.
128       */
129      transient int modCount;
130    
131      /**
132       * The cache for {@link #entrySet()}.
133       */
134      private transient Set<Map.Entry<K,V>> entries;
135    
136      /**
137       * The threshold for rehashing, which is 75% of (table.length / 2).
138       */
139      private transient int threshold;
140    
141      /**
142       * Create a new IdentityHashMap with the default capacity (21 entries).
143       */
144      public IdentityHashMap()
145      {
146        this(DEFAULT_CAPACITY);
147      }
148    
149      /**
150       * Create a new IdentityHashMap with the indicated number of
151       * entries.  If the number of elements added to this hash map
152       * exceeds this maximum, the map will grow itself; however, that
153       * incurs a performance penalty.
154       *
155       * @param max initial size
156       * @throws IllegalArgumentException if max is negative
157       */
158      public IdentityHashMap(int max)
159      {
160        if (max < 0)
161          throw new IllegalArgumentException();
162        // Need at least two slots, or hash() will break.
163        if (max < 2)
164          max = 2;
165        table = new Object[max << 1];
166        threshold = (max >> 2) * 3;
167      }
168    
169      /**
170       * Create a new IdentityHashMap whose contents are taken from the
171       * given Map.
172       *
173       * @param m The map whose elements are to be put in this map
174       * @throws NullPointerException if m is null
175       */
176      public IdentityHashMap(Map<? extends K, ? extends V> m)
177      {
178        this(Math.max(m.size() << 1, DEFAULT_CAPACITY));
179        putAll(m);
180      }
181    
182      /**
183       * Remove all mappings from this map.
184       */
185      public void clear()
186      {
187        if (size != 0)
188          {
189            modCount++;
190            Arrays.fill(table, null);
191            size = 0;
192          }
193      }
194    
195      /**
196       * Creates a shallow copy where keys and values are not cloned.
197       */
198      public Object clone()
199      {
200        try
201          {
202            IdentityHashMap copy = (IdentityHashMap) super.clone();
203            copy.table = (Object[]) table.clone();
204            copy.entries = null; // invalidate the cache
205            return copy;
206          }
207        catch (CloneNotSupportedException e)
208          {
209            // Can't happen.
210            return null;
211          }
212      }
213    
214      /**
215       * Tests whether the specified key is in this map.  Unlike normal Maps,
216       * this test uses <code>entry == key</code> instead of
217       * <code>entry == null ? key == null : entry.equals(key)</code>.
218       *
219       * @param key the key to look for
220       * @return true if the key is contained in the map
221       * @see #containsValue(Object)
222       * @see #get(Object)
223       */
224      public boolean containsKey(Object key)
225      {
226        key = xform(key);
227        return key == table[hash(key)];
228      }
229    
230      /**
231       * Returns true if this HashMap contains the value.  Unlike normal maps,
232       * this test uses <code>entry == value</code> instead of
233       * <code>entry == null ? value == null : entry.equals(value)</code>.
234       *
235       * @param value the value to search for in this HashMap
236       * @return true if at least one key maps to the value
237       * @see #containsKey(Object)
238       */
239      public boolean containsValue(Object value)
240      {
241        value = xform(value);
242        for (int i = table.length - 1; i > 0; i -= 2)
243          if (table[i] == value)
244            return true;
245        return false;
246      }
247    
248      /**
249       * Returns a "set view" of this Map's entries. The set is backed by
250       * the Map, so changes in one show up in the other.  The set supports
251       * element removal, but not element addition.
252       * <p>
253       *
254       * <em>The semantics of this set, and of its contained entries, are
255       * different from the contract of Set and Map.Entry in order to make
256       * IdentityHashMap work.  This means that while you can compare these
257       * objects between IdentityHashMaps, comparing them with regular sets
258       * or entries is likely to have undefined behavior.</em>  The entries
259       * in this set are reference-based, rather than the normal object
260       * equality.  Therefore, <code>e1.equals(e2)</code> returns
261       * <code>e1.getKey() == e2.getKey() && e1.getValue() == e2.getValue()</code>,
262       * and <code>e.hashCode()</code> returns
263       * <code>System.identityHashCode(e.getKey()) ^
264       *       System.identityHashCode(e.getValue())</code>.
265       * <p>
266       *
267       * Note that the iterators for all three views, from keySet(), entrySet(),
268       * and values(), traverse the Map in the same sequence.
269       *
270       * @return a set view of the entries
271       * @see #keySet()
272       * @see #values()
273       * @see Map.Entry
274       */
275      public Set<Map.Entry<K,V>> entrySet()
276      {
277        if (entries == null)
278          entries = new AbstractSet<Map.Entry<K,V>>()
279          {
280            public int size()
281            {
282              return size;
283            }
284    
285            public Iterator<Map.Entry<K,V>> iterator()
286            {
287              return new IdentityIterator<Map.Entry<K,V>>(ENTRIES);
288            }
289    
290            public void clear()
291            {
292              IdentityHashMap.this.clear();
293            }
294    
295            public boolean contains(Object o)
296            {
297              if (! (o instanceof Map.Entry))
298                return false;
299              Map.Entry m = (Map.Entry) o;
300              Object value = xform(m.getValue());
301              Object key = xform(m.getKey());
302              return value == table[hash(key) + 1];
303            }
304    
305            public int hashCode()
306            {
307              return IdentityHashMap.this.hashCode();
308            }
309    
310            public boolean remove(Object o)
311            {
312              if (! (o instanceof Map.Entry))
313                return false;
314              Object key = xform(((Map.Entry) o).getKey());
315              int h = hash(key);
316              if (table[h] == key)
317                {
318                  size--;
319                  modCount++;
320                  IdentityHashMap.this.removeAtIndex(h);
321                  return true;
322                }
323              return false;
324            }
325          };
326        return entries;
327      }
328    
329      /**
330       * Compares two maps for equality. This returns true only if both maps
331       * have the same reference-identity comparisons. While this returns
332       * <code>this.entrySet().equals(m.entrySet())</code> as specified by Map,
333       * this will not work with normal maps, since the entry set compares
334       * with == instead of .equals.
335       *
336       * @param o the object to compare to
337       * @return true if it is equal
338       */
339      public boolean equals(Object o)
340      {
341        // Why did Sun specify this one? The superclass does the right thing.
342        return super.equals(o);
343      }
344    
345      /**
346       * Return the value in this Map associated with the supplied key, or
347       * <code>null</code> if the key maps to nothing.
348       *
349       * <p>NOTE: Since the value could also be null, you must use
350       * containsKey to see if this key actually maps to something.
351       * Unlike normal maps, this tests for the key with <code>entry ==
352       * key</code> instead of <code>entry == null ? key == null :
353       * entry.equals(key)</code>.
354       *
355       * @param key the key for which to fetch an associated value
356       * @return what the key maps to, if present
357       * @see #put(Object, Object)
358       * @see #containsKey(Object)
359       */
360      public V get(Object key)
361      {
362        key = xform(key);
363        int h = hash(key);
364        return (V) (table[h] == key ? unxform(table[h + 1]) : null);
365      }
366    
367      /**
368       * Returns the hashcode of this map. This guarantees that two
369       * IdentityHashMaps that compare with equals() will have the same hash code,
370       * but may break with comparison to normal maps since it uses
371       * System.identityHashCode() instead of hashCode().
372       *
373       * @return the hash code
374       */
375      public int hashCode()
376      {
377        int hash = 0;
378        for (int i = table.length - 2; i >= 0; i -= 2)
379          {
380            Object key = table[i];
381            if (key == null)
382              continue;
383            // FIXME: this is a lame computation.
384            hash += (System.identityHashCode(unxform(key))
385                     ^ System.identityHashCode(unxform(table[i + 1])));
386          }
387        return hash;
388      }
389    
390      /**
391       * Returns true if there are no key-value mappings currently in this Map
392       * @return <code>size() == 0</code>
393       */
394      public boolean isEmpty()
395      {
396        return size == 0;
397      }
398    
399      /**
400       * Returns a "set view" of this Map's keys. The set is backed by the
401       * Map, so changes in one show up in the other.  The set supports
402       * element removal, but not element addition.
403       * <p>
404       *
405       * <em>The semantics of this set are different from the contract of Set
406       * in order to make IdentityHashMap work.  This means that while you can
407       * compare these objects between IdentityHashMaps, comparing them with
408       * regular sets is likely to have undefined behavior.</em>  The hashCode
409       * of the set is the sum of the identity hash codes, instead of the
410       * regular hashCodes, and equality is determined by reference instead
411       * of by the equals method.
412       * <p>
413       *
414       * @return a set view of the keys
415       * @see #values()
416       * @see #entrySet()
417       */
418      public Set<K> keySet()
419      {
420        if (keys == null)
421          keys = new AbstractSet<K>()
422          {
423            public int size()
424            {
425              return size;
426            }
427    
428            public Iterator<K> iterator()
429            {
430              return new IdentityIterator<K>(KEYS);
431            }
432    
433            public void clear()
434            {
435              IdentityHashMap.this.clear();
436            }
437    
438            public boolean contains(Object o)
439            {
440              return containsKey(o);
441            }
442    
443            public int hashCode()
444            {
445              int hash = 0;
446              for (int i = table.length - 2; i >= 0; i -= 2)
447                {
448                  Object key = table[i];
449                  if (key == null)
450                    continue;
451                  hash += System.identityHashCode(unxform(key));
452                }
453              return hash;
454            }
455    
456            public boolean remove(Object o)
457            {
458              o = xform(o);
459              int h = hash(o);
460              if (table[h] == o)
461                {
462                  size--;
463                  modCount++;
464                  removeAtIndex(h);
465                  return true;
466                }
467              return false;
468            }
469          };
470        return keys;
471      }
472    
473      /**
474       * Puts the supplied value into the Map, mapped by the supplied key.
475       * The value may be retrieved by any object which <code>equals()</code>
476       * this key. NOTE: Since the prior value could also be null, you must
477       * first use containsKey if you want to see if you are replacing the
478       * key's mapping.  Unlike normal maps, this tests for the key
479       * with <code>entry == key</code> instead of
480       * <code>entry == null ? key == null : entry.equals(key)</code>.
481       *
482       * @param key the key used to locate the value
483       * @param value the value to be stored in the HashMap
484       * @return the prior mapping of the key, or null if there was none
485       * @see #get(Object)
486       */
487      public V put(K key, V value)
488      {
489        key = (K) xform(key);
490        value = (V) xform(value);
491    
492        // We don't want to rehash if we're overwriting an existing slot.
493        int h = hash(key);
494        if (table[h] == key)
495          {
496            V r = (V) unxform(table[h + 1]);
497            table[h + 1] = value;
498            return r;
499          }
500    
501        // Rehash if the load factor is too high.
502        if (size > threshold)
503          {
504            Object[] old = table;
505            // This isn't necessarily prime, but it is an odd number of key/value
506            // slots, which has a higher probability of fewer collisions.
507            table = new Object[(old.length * 2) + 2];
508            size = 0;
509            threshold = (table.length >>> 3) * 3;
510    
511            for (int i = old.length - 2; i >= 0; i -= 2)
512              {
513                K oldkey = (K) old[i];
514                if (oldkey != null)
515                  {
516                    h = hash(oldkey);
517                    table[h] = oldkey;
518                    table[h + 1] = old[i + 1];
519                    ++size;
520                    // No need to update modCount here, we'll do it
521                    // just after the loop.
522                  }
523              }
524    
525            // Now that we've resize, recompute the hash value.
526            h = hash(key);
527          }
528    
529        // At this point, we add a new mapping.
530        modCount++;
531        size++;
532        table[h] = key;
533        table[h + 1] = value;
534        return null;
535      }
536    
537      /**
538       * Copies all of the mappings from the specified map to this. If a key
539       * is already in this map, its value is replaced.
540       *
541       * @param m the map to copy
542       * @throws NullPointerException if m is null
543       */
544      public void putAll(Map<? extends K, ? extends V> m)
545      {
546        // Why did Sun specify this one? The superclass does the right thing.
547        super.putAll(m);
548      }
549    
550      /**
551       * Remove the element at index and update the table to compensate.
552       * This is package-private for use by inner classes.
553       * @param i index of the removed element
554       */
555      final void removeAtIndex(int i)
556      {
557        // This is Algorithm R from Knuth, section 6.4.
558        // Variable names are taken directly from the text.
559        while (true)
560          {
561            table[i] = null;
562            table[i + 1] = null;
563            int j = i;
564            int r;
565            do
566              {
567                i -= 2;
568                if (i < 0)
569                  i = table.length - 2;
570                Object key = table[i];
571                if (key == null)
572                  return;
573                r = Math.abs(System.identityHashCode(key)
574                             % (table.length >> 1)) << 1;
575              }
576            while ((i <= r && r < j)
577                || (r < j && j < i)
578                || (j < i && i <= r));
579            table[j] = table[i];
580            table[j + 1] = table[i + 1];
581          }
582      }
583    
584      /**
585       * Removes from the HashMap and returns the value which is mapped by
586       * the supplied key. If the key maps to nothing, then the HashMap
587       * remains unchanged, and <code>null</code> is returned.
588       *
589       * NOTE: Since the value could also be null, you must use
590       * containsKey to see if you are actually removing a mapping.
591       * Unlike normal maps, this tests for the key with <code>entry ==
592       * key</code> instead of <code>entry == null ? key == null :
593       * entry.equals(key)</code>.
594       *
595       * @param key the key used to locate the value to remove
596       * @return whatever the key mapped to, if present
597       */
598      public V remove(Object key)
599      {
600        key = xform(key);
601        int h = hash(key);
602        if (table[h] == key)
603          {
604            modCount++;
605            size--;
606            Object r = unxform(table[h + 1]);
607            removeAtIndex(h);
608            return (V) r;
609          }
610        return null;
611      }
612    
613      /**
614       * Returns the number of kay-value mappings currently in this Map
615       * @return the size
616       */
617      public int size()
618      {
619        return size;
620      }
621    
622      /**
623       * Returns a "collection view" (or "bag view") of this Map's values.
624       * The collection is backed by the Map, so changes in one show up
625       * in the other.  The collection supports element removal, but not element
626       * addition.
627       * <p>
628       *
629       * <em>The semantics of this set are different from the contract of
630       * Collection in order to make IdentityHashMap work.  This means that
631       * while you can compare these objects between IdentityHashMaps, comparing
632       * them with regular sets is likely to have undefined behavior.</em>
633       * Likewise, contains and remove go by == instead of equals().
634       * <p>
635       *
636       * @return a bag view of the values
637       * @see #keySet()
638       * @see #entrySet()
639       */
640      public Collection<V> values()
641      {
642        if (values == null)
643          values = new AbstractCollection<V>()
644          {
645            public int size()
646            {
647              return size;
648            }
649    
650            public Iterator<V> iterator()
651            {
652              return new IdentityIterator<V>(VALUES);
653            }
654    
655            public void clear()
656            {
657              IdentityHashMap.this.clear();
658            }
659    
660            public boolean remove(Object o)
661            {
662              o = xform(o);
663              // This approach may look strange, but it is ok.
664              for (int i = table.length - 1; i > 0; i -= 2)
665                if (table[i] == o)
666                  {
667                    modCount++;
668                    size--;
669                    IdentityHashMap.this.removeAtIndex(i - 1);
670                    return true;
671                  }
672              return false;
673            }
674          };
675        return values;
676      }
677    
678      /**
679       * Transform a reference from its external form to its internal form.
680       * This is package-private for use by inner classes.
681       */
682      final Object xform(Object o)
683      {
684        if (o == null)
685          o = nullslot;
686        return o;
687      }
688    
689      /**
690       * Transform a reference from its internal form to its external form.
691       * This is package-private for use by inner classes.
692       */
693      final Object unxform(Object o)
694      {
695        if (o == nullslot)
696          o = null;
697        return o;
698      }
699    
700      /**
701       * Helper method which computes the hash code, then traverses the table
702       * until it finds the key, or the spot where the key would go.  the key
703       * must already be in its internal form.
704       *
705       * @param key the key to check
706       * @return the index where the key belongs
707       * @see #IdentityHashMap(int)
708       * @see #put(Object, Object)
709       */
710      // Package visible for use by nested classes.
711      final int hash(Object key)
712      {
713        int h = Math.abs(System.identityHashCode(key) % (table.length >> 1)) << 1;
714    
715        while (true)
716          {
717            // By requiring at least 2 key/value slots, and rehashing at 75%
718            // capacity, we guarantee that there will always be either an empty
719            // slot somewhere in the table.
720            if (table[h] == key || table[h] == null)
721              return h;
722            // We use linear probing as it is friendlier to the cache and
723            // it lets us efficiently remove entries.
724            h -= 2;
725            if (h < 0)
726              h = table.length - 2;
727          }
728      }
729    
730      /**
731       * This class allows parameterized iteration over IdentityHashMaps.  Based
732       * on its construction, it returns the key or value of a mapping, or
733       * creates the appropriate Map.Entry object with the correct fail-fast
734       * semantics and identity comparisons.
735       *
736       * @author Tom Tromey (tromey@redhat.com)
737       * @author Eric Blake (ebb9@email.byu.edu)
738       */
739      private class IdentityIterator<I> implements Iterator<I>
740      {
741        /**
742         * The type of this Iterator: {@link #KEYS}, {@link #VALUES},
743         * or {@link #ENTRIES}.
744         */
745        final int type;
746        /** The number of modifications to the backing Map that we know about. */
747        int knownMod = modCount;
748        /** The number of elements remaining to be returned by next(). */
749        int count = size;
750        /** Location in the table. */
751        int loc = table.length;
752    
753        /**
754         * Construct a new Iterator with the supplied type.
755         * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
756         */
757        IdentityIterator(int type)
758        {
759          this.type = type;
760        }
761    
762        /**
763         * Returns true if the Iterator has more elements.
764         * @return true if there are more elements
765         */
766        public boolean hasNext()
767        {
768          return count > 0;
769        }
770    
771        /**
772         * Returns the next element in the Iterator's sequential view.
773         * @return the next element
774         * @throws ConcurrentModificationException if the Map was modified
775         * @throws NoSuchElementException if there is none
776         */
777        public I next()
778        {
779          if (knownMod != modCount)
780            throw new ConcurrentModificationException();
781          if (count == 0)
782            throw new NoSuchElementException();
783          count--;
784    
785          Object key;
786          do
787            {
788              loc -= 2;
789              key = table[loc];
790            }
791          while (key == null);
792      
793          return (I) (type == KEYS ? unxform(key) 
794                      : (type == VALUES ? unxform(table[loc + 1])
795                         : new IdentityEntry(loc)));
796        }
797    
798        /**
799         * Removes from the backing Map the last element which was fetched
800         * with the <code>next()</code> method.
801         *
802         * @throws ConcurrentModificationException if the Map was modified
803         * @throws IllegalStateException if called when there is no last element
804         */
805        public void remove()
806        {
807          if (knownMod != modCount)
808            throw new ConcurrentModificationException();
809          if (loc == table.length)
810            throw new IllegalStateException();
811          modCount++;
812          size--;
813          removeAtIndex(loc);
814          knownMod++;
815        }
816      } // class IdentityIterator
817    
818      /**
819       * This class provides Map.Entry objects for IdentityHashMaps.  The entry
820       * is fail-fast, and will throw a ConcurrentModificationException if
821       * the underlying map is modified, or if remove is called on the iterator
822       * that generated this object.  It is identity based, so it violates
823       * the general contract of Map.Entry, and is probably unsuitable for
824       * comparison to normal maps; but it works among other IdentityHashMaps.
825       *
826       * @author Eric Blake (ebb9@email.byu.edu)
827       */
828      private final class IdentityEntry<EK,EV> implements Map.Entry<EK,EV>
829      {
830        /** The location of this entry. */
831        final int loc;
832        /** The number of modifications to the backing Map that we know about. */
833        final int knownMod = modCount;
834    
835        /**
836         * Constructs the Entry.
837         *
838         * @param loc the location of this entry in table
839         */
840        IdentityEntry(int loc)
841        {
842          this.loc = loc;
843        }
844    
845        /**
846         * Compares the specified object with this entry, using identity
847         * semantics. Note that this can lead to undefined results with
848         * Entry objects created by normal maps.
849         *
850         * @param o the object to compare
851         * @return true if it is equal
852         * @throws ConcurrentModificationException if the entry was invalidated
853         *         by modifying the Map or calling Iterator.remove()
854         */
855        public boolean equals(Object o)
856        {
857          if (knownMod != modCount)
858            throw new ConcurrentModificationException();
859          if (! (o instanceof Map.Entry))
860            return false;
861          Map.Entry e = (Map.Entry) o;
862          return table[loc] == xform(e.getKey())
863                 && table[loc + 1] == xform(e.getValue());
864        }
865    
866        /**
867         * Returns the key of this entry.
868         *
869         * @return the key
870         * @throws ConcurrentModificationException if the entry was invalidated
871         *         by modifying the Map or calling Iterator.remove()
872         */
873        public EK getKey()
874        {
875          if (knownMod != modCount)
876            throw new ConcurrentModificationException();
877          return (EK) unxform(table[loc]);
878        }
879    
880        /**
881         * Returns the value of this entry.
882         *
883         * @return the value
884         * @throws ConcurrentModificationException if the entry was invalidated
885         *         by modifying the Map or calling Iterator.remove()
886         */
887        public EV getValue()
888        {
889          if (knownMod != modCount)
890            throw new ConcurrentModificationException();
891          return (EV) unxform(table[loc + 1]);
892        }
893    
894        /**
895         * Returns the hashcode of the entry, using identity semantics.
896         * Note that this can lead to undefined results with Entry objects
897         * created by normal maps.
898         *
899         * @return the hash code
900         * @throws ConcurrentModificationException if the entry was invalidated
901         *         by modifying the Map or calling Iterator.remove()
902         */
903        public int hashCode()
904        {
905          if (knownMod != modCount)
906            throw new ConcurrentModificationException();
907          return (System.identityHashCode(unxform(table[loc]))
908                  ^ System.identityHashCode(unxform(table[loc + 1])));
909        }
910    
911        /**
912         * Replaces the value of this mapping, and returns the old value.
913         *
914         * @param value the new value
915         * @return the old value
916         * @throws ConcurrentModificationException if the entry was invalidated
917         *         by modifying the Map or calling Iterator.remove()
918         */
919        public EV setValue(EV value)
920        {
921          if (knownMod != modCount)
922            throw new ConcurrentModificationException();
923          EV r = (EV) unxform(table[loc + 1]);
924          table[loc + 1] = xform(value);
925          return r;
926        }
927    
928        /**
929         * This provides a string representation of the entry. It is of the form
930         * "key=value", where string concatenation is used on key and value.
931         *
932         * @return the string representation
933         * @throws ConcurrentModificationException if the entry was invalidated
934         *         by modifying the Map or calling Iterator.remove()
935         */
936        public String toString()
937        {
938          if (knownMod != modCount)
939            throw new ConcurrentModificationException();
940          return unxform(table[loc]) + "=" + unxform(table[loc + 1]);
941        }
942      } // class IdentityEntry
943    
944      /**
945       * Reads the object from a serial stream.
946       *
947       * @param s the stream to read from
948       * @throws ClassNotFoundException if the underlying stream fails
949       * @throws IOException if the underlying stream fails
950       * @serialData expects the size (int), followed by that many key (Object)
951       *             and value (Object) pairs, with the pairs in no particular
952       *             order
953       */
954      private void readObject(ObjectInputStream s)
955        throws IOException, ClassNotFoundException
956      {
957        s.defaultReadObject();
958    
959        int num = s.readInt();
960        table = new Object[Math.max(num << 1, DEFAULT_CAPACITY) << 1];
961        // Read key/value pairs.
962        while (--num >= 0)
963          put((K) s.readObject(), (V) s.readObject());
964      }
965    
966      /**
967       * Writes the object to a serial stream.
968       *
969       * @param s the stream to write to
970       * @throws IOException if the underlying stream fails
971       * @serialData outputs the size (int), followed by that many key (Object)
972       *             and value (Object) pairs, with the pairs in no particular
973       *             order
974       */
975      private void writeObject(ObjectOutputStream s)
976        throws IOException
977      {
978        s.defaultWriteObject();
979        s.writeInt(size);
980        for (int i = table.length - 2; i >= 0; i -= 2)
981          {
982            Object key = table[i];
983            if (key != null)
984              {
985                s.writeObject(unxform(key));
986                s.writeObject(unxform(table[i + 1]));
987              }
988          }
989      }
990    }