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<K,V> extends AbstractMap<K,V>
  94:   implements Map<K,V>, Serializable, Cloneable
  95: {
  96:   /** The default capacity. */
  97:   private static final int DEFAULT_CAPACITY = 21;
  98: 
  99:   /**
 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: }