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
005This file is part of GNU Classpath.
006
007GNU Classpath is free software; you can redistribute it and/or modify
008it under the terms of the GNU General Public License as published by
009the Free Software Foundation; either version 2, or (at your option)
010any later version.
011
012GNU Classpath is distributed in the hope that it will be useful, but
013WITHOUT ANY WARRANTY; without even the implied warranty of
014MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
015General Public License for more details.
016
017You should have received a copy of the GNU General Public License
018along with GNU Classpath; see the file COPYING.  If not, write to the
019Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02002110-1301 USA.
021
022Linking this library statically or dynamically with other modules is
023making a combined work based on this library.  Thus, the terms and
024conditions of the GNU General Public License cover the whole
025combination.
026
027As a special exception, the copyright holders of this library give you
028permission to link this library with independent modules to produce an
029executable, regardless of the license terms of these independent
030modules, and to copy and distribute the resulting executable under
031terms of your choice, provided that you also meet, for each linked
032independent module, the terms and conditions of the license of that
033module.  An independent module is a module which is not derived from
034or based on this library.  If you modify this library, you may extend
035this exception to your version of the library, but you are not
036obligated to do so.  If you do not wish to do so, delete this
037exception statement from your version. */
038
039package java.util;
040
041import java.io.IOException;
042import java.io.ObjectInputStream;
043import java.io.ObjectOutputStream;
044import 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 */
093public 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}