Source for java.util.IdentityHashMap

   1: /* IdentityHashMap.java -- a class providing a hashtable data structure,
   2:    mapping Object --> Object, which uses object identity for hashing.
   3:    Copyright (C) 2001, 2002, 2004, 2005  Free Software Foundation, Inc.
   4: 
   5: This file is part of GNU Classpath.
   6: 
   7: GNU Classpath is free software; you can redistribute it and/or modify
   8: it under the terms of the GNU General Public License as published by
   9: the Free Software Foundation; either version 2, or (at your option)
  10: any later version.
  11: 
  12: GNU Classpath is distributed in the hope that it will be useful, but
  13: WITHOUT ANY WARRANTY; without even the implied warranty of
  14: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15: General Public License for more details.
  16: 
  17: You should have received a copy of the GNU General Public License
  18: along with GNU Classpath; see the file COPYING.  If not, write to the
  19: Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  20: 02110-1301 USA.
  21: 
  22: Linking this library statically or dynamically with other modules is
  23: making a combined work based on this library.  Thus, the terms and
  24: conditions of the GNU General Public License cover the whole
  25: combination.
  26: 
  27: As a special exception, the copyright holders of this library give you
  28: permission to link this library with independent modules to produce an
  29: executable, regardless of the license terms of these independent
  30: modules, and to copy and distribute the resulting executable under
  31: terms of your choice, provided that you also meet, for each linked
  32: independent module, the terms and conditions of the license of that
  33: module.  An independent module is a module which is not derived from
  34: or based on this library.  If you modify this library, you may extend
  35: this exception to your version of the library, but you are not
  36: obligated to do so.  If you do not wish to do so, delete this
  37: exception statement from your version. */
  38: 
  39: package java.util;
  40: 
  41: import java.io.IOException;
  42: import java.io.ObjectInputStream;
  43: import java.io.ObjectOutputStream;
  44: import java.io.Serializable;
  45: 
  46: /**
  47:  * This class provides a hashtable-backed implementation of the
  48:  * Map interface, but uses object identity to do its hashing.  In fact,
  49:  * it uses object identity for comparing values, as well. It uses a
  50:  * linear-probe hash table, which may have faster performance
  51:  * than the chaining employed by HashMap.
  52:  * <p>
  53:  *
  54:  * <em>WARNING: This is not a general purpose map. Because it uses
  55:  * System.identityHashCode and ==, instead of hashCode and equals, for
  56:  * comparison, it violated Map's general contract, and may cause
  57:  * undefined behavior when compared to other maps which are not
  58:  * IdentityHashMaps.  This is designed only for the rare cases when
  59:  * identity semantics are needed.</em> An example use is
  60:  * topology-preserving graph transformations, such as deep cloning,
  61:  * or as proxy object mapping such as in debugging.
  62:  * <p>
  63:  *
  64:  * This map permits <code>null</code> keys and values, and does not
  65:  * guarantee that elements will stay in the same order over time. The
  66:  * basic operations (<code>get</code> and <code>put</code>) take
  67:  * constant time, provided System.identityHashCode is decent. You can
  68:  * tune the behavior by specifying the expected maximum size. As more
  69:  * elements are added, the map may need to allocate a larger table,
  70:  * which can be expensive.
  71:  * <p>
  72:  *
  73:  * This implementation is unsynchronized.  If you want multi-thread
  74:  * access to be consistent, you must synchronize it, perhaps by using
  75:  * <code>Collections.synchronizedMap(new IdentityHashMap(...));</code>.
  76:  * The iterators are <i>fail-fast</i>, meaning that a structural modification
  77:  * made to the map outside of an iterator's remove method cause the
  78:  * iterator, and in the case of the entrySet, the Map.Entry, to
  79:  * fail with a {@link ConcurrentModificationException}.
  80:  *
  81:  * @author Tom Tromey (tromey@redhat.com)
  82:  * @author Eric Blake (ebb9@email.byu.edu)
  83:  * @see System#identityHashCode(Object)
  84:  * @see Collection
  85:  * @see Map
  86:  * @see HashMap
  87:  * @see TreeMap
  88:  * @see LinkedHashMap
  89:  * @see WeakHashMap
  90:  * @since 1.4
  91:  * @status updated to 1.4
  92:  */
  93: public class IdentityHashMap extends AbstractMap
  94:   implements Map, Serializable, Cloneable
  95: {
  96:   /** The default capacity. */
  97:   private static final int DEFAULT_CAPACITY = 21;
  98: 
  99:   /**
 100:    * This object is used to mark deleted items. Package visible for use by
 101:    * nested classes.
 102:    */
 103:   static final Object tombstone = new Object();
 104: 
 105:   /**
 106:    * This object is used to mark empty slots.  We need this because
 107:    * using null is ambiguous. Package visible for use by nested classes.
 108:    */
 109:   static final Object emptyslot = new Object();
 110: 
 111:   /**
 112:    * Compatible with JDK 1.4.
 113:    */
 114:   private static final long serialVersionUID = 8188218128353913216L;
 115: 
 116:   /**
 117:    * The number of mappings in the table. Package visible for use by nested
 118:    * classes.
 119:    * @serial
 120:    */
 121:   int size;
 122: 
 123:   /**
 124:    * The table itself. Package visible for use by nested classes.
 125:    */
 126:   transient Object[] table;
 127: 
 128:   /**
 129:    * The number of structural modifications made so far. Package visible for
 130:    * use by nested classes.
 131:    */
 132:   transient int modCount;
 133: 
 134:   /**
 135:    * The cache for {@link #entrySet()}.
 136:    */
 137:   private transient Set entries;
 138: 
 139:   /**
 140:    * The threshold for rehashing, which is 75% of (table.length / 2).
 141:    */
 142:   private transient int threshold;
 143: 
 144:   /**
 145:    * Create a new IdentityHashMap with the default capacity (21 entries).
 146:    */
 147:   public IdentityHashMap()
 148:   {
 149:     this(DEFAULT_CAPACITY);
 150:   }
 151: 
 152:   /**
 153:    * Create a new IdentityHashMap with the indicated number of
 154:    * entries.  If the number of elements added to this hash map
 155:    * exceeds this maximum, the map will grow itself; however, that
 156:    * incurs a performance penalty.
 157:    *
 158:    * @param max initial size
 159:    * @throws IllegalArgumentException if max is negative
 160:    */
 161:   public IdentityHashMap(int max)
 162:   {
 163:     if (max < 0)
 164:       throw new IllegalArgumentException();
 165:     // Need at least two slots, or hash() will break.
 166:     if (max < 2)
 167:       max = 2;
 168:     table = new Object[max << 1];
 169:     Arrays.fill(table, emptyslot);
 170:     threshold = (max >> 2) * 3;
 171:   }
 172: 
 173:   /**
 174:    * Create a new IdentityHashMap whose contents are taken from the
 175:    * given Map.
 176:    *
 177:    * @param m The map whose elements are to be put in this map
 178:    * @throws NullPointerException if m is null
 179:    */
 180:   public IdentityHashMap(Map m)
 181:   {
 182:     this(Math.max(m.size() << 1, DEFAULT_CAPACITY));
 183:     putAll(m);
 184:   }
 185: 
 186:   /**
 187:    * Remove all mappings from this map.
 188:    */
 189:   public void clear()
 190:   {
 191:     if (size != 0)
 192:       {
 193:         modCount++;
 194:         Arrays.fill(table, emptyslot);
 195:         size = 0;
 196:       }
 197:   }
 198: 
 199:   /**
 200:    * Creates a shallow copy where keys and values are not cloned.
 201:    */
 202:   public Object clone()
 203:   {
 204:     try
 205:       {
 206:         IdentityHashMap copy = (IdentityHashMap) super.clone();
 207:         copy.table = (Object[]) table.clone();
 208:         copy.entries = null; // invalidate the cache
 209:         return copy;
 210:       }
 211:     catch (CloneNotSupportedException e)
 212:       {
 213:         // Can't happen.
 214:         return null;
 215:       }
 216:   }
 217: 
 218:   /**
 219:    * Tests whether the specified key is in this map.  Unlike normal Maps,
 220:    * this test uses <code>entry == key</code> instead of
 221:    * <code>entry == null ? key == null : entry.equals(key)</code>.
 222:    *
 223:    * @param key the key to look for
 224:    * @return true if the key is contained in the map
 225:    * @see #containsValue(Object)
 226:    * @see #get(Object)
 227:    */
 228:   public boolean containsKey(Object key)
 229:   {
 230:     return key == table[hash(key)];
 231:   }
 232: 
 233:   /**
 234:    * Returns true if this HashMap contains the value.  Unlike normal maps,
 235:    * this test uses <code>entry == value</code> instead of
 236:    * <code>entry == null ? value == null : entry.equals(value)</code>.
 237:    *
 238:    * @param value the value to search for in this HashMap
 239:    * @return true if at least one key maps to the value
 240:    * @see #containsKey(Object)
 241:    */
 242:   public boolean containsValue(Object value)
 243:   {
 244:     for (int i = table.length - 1; i > 0; i -= 2)
 245:       if (table[i] == value)
 246:         return true;
 247:     return false;
 248:   }
 249: 
 250:   /**
 251:    * Returns a "set view" of this Map's entries. The set is backed by
 252:    * the Map, so changes in one show up in the other.  The set supports
 253:    * element removal, but not element addition.
 254:    * <p>
 255:    *
 256:    * <em>The semantics of this set, and of its contained entries, are
 257:    * different from the contract of Set and Map.Entry in order to make
 258:    * IdentityHashMap work.  This means that while you can compare these
 259:    * objects between IdentityHashMaps, comparing them with regular sets
 260:    * or entries is likely to have undefined behavior.</em>  The entries
 261:    * in this set are reference-based, rather than the normal object
 262:    * equality.  Therefore, <code>e1.equals(e2)</code> returns
 263:    * <code>e1.getKey() == e2.getKey() && e1.getValue() == e2.getValue()</code>,
 264:    * and <code>e.hashCode()</code> returns
 265:    * <code>System.identityHashCode(e.getKey()) ^
 266:    *       System.identityHashCode(e.getValue())</code>.
 267:    * <p>
 268:    *
 269:    * Note that the iterators for all three views, from keySet(), entrySet(),
 270:    * and values(), traverse the Map in the same sequence.
 271:    *
 272:    * @return a set view of the entries
 273:    * @see #keySet()
 274:    * @see #values()
 275:    * @see Map.Entry
 276:    */
 277:   public Set entrySet()
 278:   {
 279:     if (entries == null)
 280:       entries = new AbstractSet()
 281:       {
 282:         public int size()
 283:         {
 284:           return size;
 285:         }
 286: 
 287:         public Iterator iterator()
 288:         {
 289:           return new IdentityIterator(ENTRIES);
 290:         }
 291: 
 292:         public void clear()
 293:         {
 294:           IdentityHashMap.this.clear();
 295:         }
 296: 
 297:         public boolean contains(Object o)
 298:         {
 299:           if (! (o instanceof Map.Entry))
 300:             return false;
 301:           Map.Entry m = (Map.Entry) o;
 302:           return m.getValue() == table[hash(m.getKey()) + 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 = ((Map.Entry) o).getKey();
 315:           int h = hash(key);
 316:           if (table[h] == key)
 317:             {
 318:               size--;
 319:               modCount++;
 320:               table[h] = tombstone;
 321:               table[h + 1] = tombstone;
 322:               return true;
 323:             }
 324:           return false;
 325:         }
 326:       };
 327:     return entries;
 328:   }
 329: 
 330:   /**
 331:    * Compares two maps for equality. This returns true only if both maps
 332:    * have the same reference-identity comparisons. While this returns
 333:    * <code>this.entrySet().equals(m.entrySet())</code> as specified by Map,
 334:    * this will not work with normal maps, since the entry set compares
 335:    * with == instead of .equals.
 336:    *
 337:    * @param o the object to compare to
 338:    * @return true if it is equal
 339:    */
 340:   public boolean equals(Object o)
 341:   {
 342:     // Why did Sun specify this one? The superclass does the right thing.
 343:     return super.equals(o);
 344:   }
 345: 
 346:   /**
 347:    * Return the value in this Map associated with the supplied key, or
 348:    * <code>null</code> if the key maps to nothing.
 349:    *
 350:    * <p>NOTE: Since the value could also be null, you must use
 351:    * containsKey to see if this key actually maps to something.
 352:    * Unlike normal maps, this tests for the key with <code>entry ==
 353:    * key</code> instead of <code>entry == null ? key == null :
 354:    * entry.equals(key)</code>.
 355:    *
 356:    * @param key the key for which to fetch an associated value
 357:    * @return what the key maps to, if present
 358:    * @see #put(Object, Object)
 359:    * @see #containsKey(Object)
 360:    */
 361:   public Object get(Object key)
 362:   {
 363:     int h = hash(key);
 364:     return table[h] == key ? 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 == emptyslot || key == tombstone)
 382:           continue;
 383:         hash += (System.identityHashCode(key)
 384:                  ^ System.identityHashCode(table[i + 1]));
 385:       }
 386:     return hash;
 387:   }
 388: 
 389:   /**
 390:    * Returns true if there are no key-value mappings currently in this Map
 391:    * @return <code>size() == 0</code>
 392:    */
 393:   public boolean isEmpty()
 394:   {
 395:     return size == 0;
 396:   }
 397: 
 398:   /**
 399:    * Returns a "set view" of this Map's keys. The set is backed by the
 400:    * Map, so changes in one show up in the other.  The set supports
 401:    * element removal, but not element addition.
 402:    * <p>
 403:    *
 404:    * <em>The semantics of this set are different from the contract of Set
 405:    * in order to make IdentityHashMap work.  This means that while you can
 406:    * compare these objects between IdentityHashMaps, comparing them with
 407:    * regular sets is likely to have undefined behavior.</em>  The hashCode
 408:    * of the set is the sum of the identity hash codes, instead of the
 409:    * regular hashCodes, and equality is determined by reference instead
 410:    * of by the equals method.
 411:    * <p>
 412:    *
 413:    * @return a set view of the keys
 414:    * @see #values()
 415:    * @see #entrySet()
 416:    */
 417:   public Set keySet()
 418:   {
 419:     if (keys == null)
 420:       keys = new AbstractSet()
 421:       {
 422:         public int size()
 423:         {
 424:           return size;
 425:         }
 426: 
 427:         public Iterator iterator()
 428:         {
 429:           return new IdentityIterator(KEYS);
 430:         }
 431: 
 432:         public void clear()
 433:         {
 434:           IdentityHashMap.this.clear();
 435:         }
 436: 
 437:         public boolean contains(Object o)
 438:         {
 439:           return containsKey(o);
 440:         }
 441: 
 442:         public int hashCode()
 443:         {
 444:           int hash = 0;
 445:           for (int i = table.length - 2; i >= 0; i -= 2)
 446:             {
 447:               Object key = table[i];
 448:               if (key == emptyslot || key == tombstone)
 449:                 continue;
 450:               hash += System.identityHashCode(key);
 451:             }
 452:           return hash;
 453: 
 454:         }
 455: 
 456:         public boolean remove(Object o)
 457:         {
 458:           int h = hash(o);
 459:           if (table[h] == o)
 460:             {
 461:               size--;
 462:               modCount++;
 463:               table[h] = tombstone;
 464:               table[h + 1] = tombstone;
 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 Object put(Object key, Object value)
 488:   {
 489:     // Rehash if the load factor is too high.
 490:     if (size > threshold)
 491:       {
 492:         Object[] old = table;
 493:         // This isn't necessarily prime, but it is an odd number of key/value
 494:         // slots, which has a higher probability of fewer collisions.
 495:         table = new Object[(old.length * 2) + 2];
 496:         Arrays.fill(table, emptyslot);
 497:         size = 0;
 498:         threshold = (table.length >>> 3) * 3;
 499: 
 500:         for (int i = old.length - 2; i >= 0; i -= 2)
 501:           {
 502:             Object oldkey = old[i];
 503:             if (oldkey != tombstone && oldkey != emptyslot)
 504:               // Just use put.  This isn't very efficient, but it is ok.
 505:               put(oldkey, old[i + 1]);
 506:           }
 507:       }
 508: 
 509:     int h = hash(key);
 510:     if (table[h] == key)
 511:       {
 512:         Object r = table[h + 1];
 513:         table[h + 1] = value;
 514:         return r;
 515:       }
 516: 
 517:     // At this point, we add a new mapping.
 518:     modCount++;
 519:     size++;
 520:     table[h] = key;
 521:     table[h + 1] = value;
 522:     return null;
 523:   }
 524: 
 525:   /**
 526:    * Copies all of the mappings from the specified map to this. If a key
 527:    * is already in this map, its value is replaced.
 528:    *
 529:    * @param m the map to copy
 530:    * @throws NullPointerException if m is null
 531:    */
 532:   public void putAll(Map m)
 533:   {
 534:     // Why did Sun specify this one? The superclass does the right thing.
 535:     super.putAll(m);
 536:   }
 537: 
 538:   /**
 539:    * Removes from the HashMap and returns the value which is mapped by
 540:    * the supplied key. If the key maps to nothing, then the HashMap
 541:    * remains unchanged, and <code>null</code> is returned.
 542:    *
 543:    * NOTE: Since the value could also be null, you must use
 544:    * containsKey to see if you are actually removing a mapping.
 545:    * Unlike normal maps, this tests for the key with <code>entry ==
 546:    * key</code> instead of <code>entry == null ? key == null :
 547:    * entry.equals(key)</code>.
 548:    *
 549:    * @param key the key used to locate the value to remove
 550:    * @return whatever the key mapped to, if present
 551:    */
 552:   public Object remove(Object key)
 553:   {
 554:     int h = hash(key);
 555:     if (table[h] == key)
 556:       {
 557:         modCount++;
 558:         size--;
 559:         Object r = table[h + 1];
 560:         table[h] = tombstone;
 561:         table[h + 1] = tombstone;
 562:         return r;
 563:       }
 564:     return null;
 565:   }
 566: 
 567:   /**
 568:    * Returns the number of kay-value mappings currently in this Map
 569:    * @return the size
 570:    */
 571:   public int size()
 572:   {
 573:     return size;
 574:   }
 575: 
 576:   /**
 577:    * Returns a "collection view" (or "bag view") of this Map's values.
 578:    * The collection is backed by the Map, so changes in one show up
 579:    * in the other.  The collection supports element removal, but not element
 580:    * addition.
 581:    * <p>
 582:    *
 583:    * <em>The semantics of this set are different from the contract of
 584:    * Collection in order to make IdentityHashMap work.  This means that
 585:    * while you can compare these objects between IdentityHashMaps, comparing
 586:    * them with regular sets is likely to have undefined behavior.</em>
 587:    * Likewise, contains and remove go by == instead of equals().
 588:    * <p>
 589:    *
 590:    * @return a bag view of the values
 591:    * @see #keySet()
 592:    * @see #entrySet()
 593:    */
 594:   public Collection values()
 595:   {
 596:     if (values == null)
 597:       values = new AbstractCollection()
 598:       {
 599:         public int size()
 600:         {
 601:           return size;
 602:         }
 603: 
 604:         public Iterator iterator()
 605:         {
 606:           return new IdentityIterator(VALUES);
 607:         }
 608: 
 609:         public void clear()
 610:         {
 611:           IdentityHashMap.this.clear();
 612:         }
 613: 
 614:         public boolean remove(Object o)
 615:         {
 616:           for (int i = table.length - 1; i > 0; i -= 2)
 617:             if (table[i] == o)
 618:               {
 619:                 modCount++;
 620:                 table[i - 1] = tombstone;
 621:                 table[i] = tombstone;
 622:                 size--;
 623:                 return true;
 624:               }
 625:           return false;
 626:         }
 627:       };
 628:     return values;
 629:   }
 630: 
 631:   /**
 632:    * Helper method which computes the hash code, then traverses the table
 633:    * until it finds the key, or the spot where the key would go.
 634:    *
 635:    * @param key the key to check
 636:    * @return the index where the key belongs
 637:    * @see #IdentityHashMap(int)
 638:    * @see #put(Object, Object)
 639:    */
 640:   // Package visible for use by nested classes.
 641:   int hash(Object key)
 642:   {
 643:     // Implementation note: it is feasible for the table to have no
 644:     // emptyslots, if it is full with entries and tombstones, so we must
 645:     // remember where we started. If we encounter the key or an emptyslot,
 646:     // we are done.  If we encounter a tombstone, the key may still be in
 647:     // the array.  If we don't encounter the key, we use the first emptyslot
 648:     // or tombstone we encountered as the location where the key would go.
 649:     // By requiring at least 2 key/value slots, and rehashing at 75%
 650:     // capacity, we guarantee that there will always be either an emptyslot
 651:     // or a tombstone somewhere in the table.
 652:     int h = Math.abs(System.identityHashCode(key) % (table.length >> 1)) << 1;
 653:     int del = -1;
 654:     int save = h;
 655: 
 656:     do
 657:       {
 658:         if (table[h] == key)
 659:           return h;
 660:         if (table[h] == emptyslot)
 661:           break;
 662:         if (table[h] == tombstone && del < 0)
 663:           del = h;
 664:         h -= 2;
 665:         if (h < 0)
 666:           h = table.length - 2;
 667:       }
 668:     while (h != save);
 669: 
 670:     return del < 0 ? h : del;
 671:   }
 672: 
 673:   /**
 674:    * This class allows parameterized iteration over IdentityHashMaps.  Based
 675:    * on its construction, it returns the key or value of a mapping, or
 676:    * creates the appropriate Map.Entry object with the correct fail-fast
 677:    * semantics and identity comparisons.
 678:    *
 679:    * @author Tom Tromey (tromey@redhat.com)
 680:    * @author Eric Blake (ebb9@email.byu.edu)
 681:    */
 682:   private class IdentityIterator implements Iterator
 683:   {
 684:     /**
 685:      * The type of this Iterator: {@link #KEYS}, {@link #VALUES},
 686:      * or {@link #ENTRIES}.
 687:      */
 688:     final int type;
 689:     /** The number of modifications to the backing Map that we know about. */
 690:     int knownMod = modCount;
 691:     /** The number of elements remaining to be returned by next(). */
 692:     int count = size;
 693:     /** Location in the table. */
 694:     int loc = table.length;
 695: 
 696:     /**
 697:      * Construct a new Iterator with the supplied type.
 698:      * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
 699:      */
 700:     IdentityIterator(int type)
 701:     {
 702:       this.type = type;
 703:     }
 704: 
 705:     /**
 706:      * Returns true if the Iterator has more elements.
 707:      * @return true if there are more elements
 708:      * @throws ConcurrentModificationException if the Map was modified
 709:      */
 710:     public boolean hasNext()
 711:     {
 712:       if (knownMod != modCount)
 713:         throw new ConcurrentModificationException();
 714:       return count > 0;
 715:     }
 716: 
 717:     /**
 718:      * Returns the next element in the Iterator's sequential view.
 719:      * @return the next element
 720:      * @throws ConcurrentModificationException if the Map was modified
 721:      * @throws NoSuchElementException if there is none
 722:      */
 723:     public Object next()
 724:     {
 725:       if (knownMod != modCount)
 726:         throw new ConcurrentModificationException();
 727:       if (count == 0)
 728:         throw new NoSuchElementException();
 729:       count--;
 730: 
 731:       Object key;
 732:       do
 733:         {
 734:           loc -= 2;
 735:           key = table[loc];
 736:         }
 737:       while (key == emptyslot || key == tombstone);
 738: 
 739:       return type == KEYS ? key : (type == VALUES ? table[loc + 1]
 740:                                    : new IdentityEntry(loc));
 741:     }
 742: 
 743:     /**
 744:      * Removes from the backing Map the last element which was fetched
 745:      * with the <code>next()</code> method.
 746:      *
 747:      * @throws ConcurrentModificationException if the Map was modified
 748:      * @throws IllegalStateException if called when there is no last element
 749:      */
 750:     public void remove()
 751:     {
 752:       if (knownMod != modCount)
 753:         throw new ConcurrentModificationException();
 754:       if (loc == table.length || table[loc] == tombstone)
 755:         throw new IllegalStateException();
 756:       modCount++;
 757:       size--;
 758:       table[loc] = tombstone;
 759:       table[loc + 1] = tombstone;
 760:       knownMod++;
 761:     }
 762:   } // class IdentityIterator
 763: 
 764:   /**
 765:    * This class provides Map.Entry objects for IdentityHashMaps.  The entry
 766:    * is fail-fast, and will throw a ConcurrentModificationException if
 767:    * the underlying map is modified, or if remove is called on the iterator
 768:    * that generated this object.  It is identity based, so it violates
 769:    * the general contract of Map.Entry, and is probably unsuitable for
 770:    * comparison to normal maps; but it works among other IdentityHashMaps.
 771:    *
 772:    * @author Eric Blake (ebb9@email.byu.edu)
 773:    */
 774:   private final class IdentityEntry implements Map.Entry
 775:   {
 776:     /** The location of this entry. */
 777:     final int loc;
 778:     /** The number of modifications to the backing Map that we know about. */
 779:     final int knownMod = modCount;
 780: 
 781:     /**
 782:      * Constructs the Entry.
 783:      *
 784:      * @param loc the location of this entry in table
 785:      */
 786:     IdentityEntry(int loc)
 787:     {
 788:       this.loc = loc;
 789:     }
 790: 
 791:     /**
 792:      * Compares the specified object with this entry, using identity
 793:      * semantics. Note that this can lead to undefined results with
 794:      * Entry objects created by normal maps.
 795:      *
 796:      * @param o the object to compare
 797:      * @return true if it is equal
 798:      * @throws ConcurrentModificationException if the entry was invalidated
 799:      *         by modifying the Map or calling Iterator.remove()
 800:      */
 801:     public boolean equals(Object o)
 802:     {
 803:       if (knownMod != modCount || table[loc] == tombstone)
 804:         throw new ConcurrentModificationException();
 805:       if (! (o instanceof Map.Entry))
 806:         return false;
 807:       Map.Entry e = (Map.Entry) o;
 808:       return table[loc] == e.getKey() && table[loc + 1] == e.getValue();
 809:     }
 810: 
 811:     /**
 812:      * Returns the key of this entry.
 813:      *
 814:      * @return the key
 815:      * @throws ConcurrentModificationException if the entry was invalidated
 816:      *         by modifying the Map or calling Iterator.remove()
 817:      */
 818:     public Object getKey()
 819:     {
 820:       if (knownMod != modCount || table[loc] == tombstone)
 821:         throw new ConcurrentModificationException();
 822:       return table[loc];
 823:     }
 824: 
 825:     /**
 826:      * Returns the value of this entry.
 827:      *
 828:      * @return the value
 829:      * @throws ConcurrentModificationException if the entry was invalidated
 830:      *         by modifying the Map or calling Iterator.remove()
 831:      */
 832:     public Object getValue()
 833:     {
 834:       if (knownMod != modCount || table[loc] == tombstone)
 835:         throw new ConcurrentModificationException();
 836:       return table[loc + 1];
 837:     }
 838: 
 839:     /**
 840:      * Returns the hashcode of the entry, using identity semantics.
 841:      * Note that this can lead to undefined results with Entry objects
 842:      * created by normal maps.
 843:      *
 844:      * @return the hash code
 845:      * @throws ConcurrentModificationException if the entry was invalidated
 846:      *         by modifying the Map or calling Iterator.remove()
 847:      */
 848:     public int hashCode()
 849:     {
 850:       if (knownMod != modCount || table[loc] == tombstone)
 851:         throw new ConcurrentModificationException();
 852:       return (System.identityHashCode(table[loc])
 853:               ^ System.identityHashCode(table[loc + 1]));
 854:     }
 855: 
 856:     /**
 857:      * Replaces the value of this mapping, and returns the old value.
 858:      *
 859:      * @param value the new value
 860:      * @return the old value
 861:      * @throws ConcurrentModificationException if the entry was invalidated
 862:      *         by modifying the Map or calling Iterator.remove()
 863:      */
 864:     public Object setValue(Object value)
 865:     {
 866:       if (knownMod != modCount || table[loc] == tombstone)
 867:         throw new ConcurrentModificationException();
 868:       Object r = table[loc + 1];
 869:       table[loc + 1] = value;
 870:       return r;
 871:     }
 872: 
 873:     /**
 874:      * This provides a string representation of the entry. It is of the form
 875:      * "key=value", where string concatenation is used on key and value.
 876:      *
 877:      * @return the string representation
 878:      * @throws ConcurrentModificationException if the entry was invalidated
 879:      *         by modifying the Map or calling Iterator.remove()
 880:      */
 881:     public String toString()
 882:     {
 883:       if (knownMod != modCount || table[loc] == tombstone)
 884:         throw new ConcurrentModificationException();
 885:       return table[loc] + "=" + table[loc + 1];
 886:     }
 887:   } // class IdentityEntry
 888: 
 889:   /**
 890:    * Reads the object from a serial stream.
 891:    *
 892:    * @param s the stream to read from
 893:    * @throws ClassNotFoundException if the underlying stream fails
 894:    * @throws IOException if the underlying stream fails
 895:    * @serialData expects the size (int), followed by that many key (Object)
 896:    *             and value (Object) pairs, with the pairs in no particular
 897:    *             order
 898:    */
 899:   private void readObject(ObjectInputStream s)
 900:     throws IOException, ClassNotFoundException
 901:   {
 902:     s.defaultReadObject();
 903: 
 904:     int num = s.readInt();
 905:     table = new Object[Math.max(num << 1, DEFAULT_CAPACITY) << 1];
 906:     // Read key/value pairs.
 907:     while (--num >= 0)
 908:       put(s.readObject(), s.readObject());
 909:   }
 910: 
 911:   /**
 912:    * Writes the object to a serial stream.
 913:    *
 914:    * @param s the stream to write to
 915:    * @throws IOException if the underlying stream fails
 916:    * @serialData outputs the size (int), followed by that many key (Object)
 917:    *             and value (Object) pairs, with the pairs in no particular
 918:    *             order
 919:    */
 920:   private void writeObject(ObjectOutputStream s)
 921:     throws IOException
 922:   {
 923:     s.defaultWriteObject();
 924:     s.writeInt(size);
 925:     for (int i = table.length - 2; i >= 0; i -= 2)
 926:       {
 927:         Object key = table[i];
 928:         if (key != tombstone && key != emptyslot)
 929:           {
 930:             s.writeObject(key);
 931:             s.writeObject(table[i + 1]);
 932:           }
 933:       }
 934:   }
 935: }