Robust/Transactions/jcarderbenchmarks/mysrc/dstm2/util/IntHashMap.java

   1 package dstm2.util;
   2
   3 import java.io.IOException;
   4 import java.util.AbstractSet;
   5 import java.util.ConcurrentModificationException;
   6 import java.util.Iterator;
   7 import java.util.NoSuchElementException;
   8 import java.util.Set;
   9 import java.util.concurrent.atomic.AtomicInteger;
  10
  11 import dstm2.Thread;
  12 import dstm2.atomic;
  13 import dstm2.factory.Factory;
  14
  15 public class IntHashMap implements Iterable<Integer>{
  16
  17     /**
  18      * The default initial capacity - MUST be a power of two.
  19      */
  20     static final int DEFAULT_INITIAL_CAPACITY = 16;
  21
  22     /**
  23      * The maximum capacity, used if a higher value is implicitly specified
  24      * by either of the constructors with arguments.
  25      * MUST be a power of two <= 1<<30.
  26      */
  27     static final int MAXIMUM_CAPACITY = 1 << 30;
  28
  29     /**
  30      * The load factor used when none specified in constructor.
  31      **/
  32     static final float DEFAULT_LOAD_FACTOR = 0.75f;
  33
  34     /**
  35      * The table, resized as necessary. Length MUST Always be a power of two.
  36      */
  37     //transient TEntry<V>[] table;
  38     dstm2.AtomicArray<TEntry> table;
  39     final private Factory<TEntry> factory;
  40
  41     //transient Entry<K, V>[] table;
  42
  43     /**
  44      * The number of key-value mappings contained in this identity hash map.
  45      */
  46     //transient int size;
  47
  48     java.util.concurrent.atomic.AtomicInteger size;
  49
  50     /*
  51      * The capacity of the table
  52      */
  53     transient int capacity;
  54
  55     /**
  56      * The next size value at which to resize (capacity * load factor).
  57      * @serial
  58      */
  59     int threshold;
  60
  61     /**
  62      * The load factor for the hash table.
  63      *
  64      * @serial
  65      */
  66     final float loadFactor;
  67
  68     /**
  69      * The number of times this HashMap has been structurally modified
  70      * Structural modifications are those that change the number of mappings in
  71      * the HashMap or otherwise modify its internal structure (e.g.,
  72      * rehash).  This field is used to make iterators on Collection-views of
  73      * the HashMap fail-fast.  (See ConcurrentModificationException).
  74      */
  75     transient volatile int modCount;
  76
  77     /**
  78      * Constructs an empty <tt>HashMap</tt> with the specified initial
  79      * capacity and load factor.
  80      *
  81      * @param  initialCapacity The initial capacity.
  82      * @param  loadFactor      The load factor.
  83      * @throws IllegalArgumentException if the initial capacity is negative
  84      *         or the load factor is nonpositive.
  85      */
  86     public IntHashMap(int initialCapacity, float loadFactor) {
  87         size = new AtomicInteger(0);
  88         factory = Thread.makeFactory(TEntry.class);
  89         if (initialCapacity < 0)
  90             throw new IllegalArgumentException("Illegal initial capacity: " +
  91                                                initialCapacity);
  92         if (initialCapacity > MAXIMUM_CAPACITY)
  93             initialCapacity = MAXIMUM_CAPACITY;
  94         if (loadFactor <= 0 || Float.isNaN(loadFactor))
  95             throw new IllegalArgumentException("Illegal load factor: " +
  96                                                loadFactor);
  97
  98         // Find a power of 2 >= initialCapacity
  99         int capacity = 1;
 100         while (capacity < initialCapacity)
 101             capacity <<= 1;
 102
 103         this.capacity = capacity;
 104         this.loadFactor = loadFactor;
 105         threshold = (int)(capacity * loadFactor);
 106         table = new dstm2.AtomicArray<TEntry>(TEntry.class, capacity);
 107 //        for(int i = 0; i < capacity; i++) {
 108 //              table[i] = factory.create();
 109 //        }
 110         //table = new Entry[capacity];
 111         init();
 112     }
 113
 114     /**
 115      * Constructs an empty <tt>HashMap</tt> with the specified initial
 116      * capacity and the default load factor (0.75).
 117      *
 118      * @param  initialCapacity the initial capacity.
 119      * @throws IllegalArgumentException if the initial capacity is negative.
 120      */
 121     public IntHashMap(int initialCapacity) {
 122         this(initialCapacity, DEFAULT_LOAD_FACTOR);
 123     }
 124
 125     /**
 126      * Constructs an empty <tt>HashMap</tt> with the default initial capacity
 127      * (16) and the default load factor (0.75).
 128      */
 129     public IntHashMap() {
 130         this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
 131     }
 132
 133     /**
 134      * Constructs a new <tt>HashMap</tt> with the same mappings as the
 135      * specified <tt>Map</tt>.  The <tt>HashMap</tt> is created with
 136      * default load factor (0.75) and an initial capacity sufficient to
 137      * hold the mappings in the specified <tt>Map</tt>.
 138      *
 139      * @param   m the map whose mappings are to be placed in this map.
 140      * @throws  NullPointerException if the specified map is null.
 141      */
 142     public IntHashMap(IntHashMap m) {
 143         this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
 144                       DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
 145         putAllForCreate(m);
 146     }
 147
 148     // internal utilities
 149
 150     /**
 151      * Initialization hook for subclasses. This method is called
 152      * in all constructors and pseudo-constructors (clone, readObject)
 153      * after HashMap has been initialized but before any entries have
 154      * been inserted.  (In the absence of this method, readObject would
 155      * require explicit knowledge of subclasses.)
 156      */
 157     void init() {
 158     }
 159     public dstm2.AtomicArray<TEntry> getBuckets() {
 160         return table;
 161     }
 162     /**
 163      * Value representing null keys inside tables.
 164      */
 165     static final Object NULL_KEY = new Object();
 166
 167     /**
 168      * Returns internal representation for key. Use NULL_KEY if key is null.
 169      */
 170     static <T> T maskNull(T key) {
 171         return key == null ? (T)NULL_KEY : key;
 172     }
 173
 174     /**
 175      * Returns key represented by specified internal representation.
 176      */
 177     static <T> T unmaskNull(T key) {
 178         return (key == NULL_KEY ? null : key);
 179     }
 180
 181     /**
 182      * Whether to prefer the old supplemental hash function, for
 183      * compatibility with broken applications that rely on the
 184      * internal hashing order.
 185      *
 186      * Set to true only by hotspot when invoked via
 187      * -XX:+UseNewHashFunction or -XX:+AggressiveOpts
 188      */
 189     private static final boolean useNewHash;
 190     static { useNewHash = false; }
 191
 192     private static int oldHash(int h) {
 193         h += ~(h << 9);
 194         h ^=  (h >>> 14);
 195         h +=  (h << 4);
 196         h ^=  (h >>> 10);
 197         return h;
 198     }
 199
 200     private static int newHash(int h) {
 201         // This function ensures that hashCodes that differ only by
 202         // constant multiples at each bit position have a bounded
 203         // number of collisions (approximately 8 at default load factor).
 204         h ^= (h >>> 20) ^ (h >>> 12);
 205         return h ^ (h >>> 7) ^ (h >>> 4);
 206     }
 207
 208     /**
 209      * Applies a supplemental hash function to a given hashCode, which
 210      * defends against poor quality hash functions.  This is critical
 211      * because HashMap uses power-of-two length hash tables, that
 212      * otherwise encounter collisions for hashCodes that do not differ
 213      * in lower bits.
 214      */
 215     public static int hash(int h) {
 216         return useNewHash ? newHash(h) : oldHash(h);
 217     }
 218
 219     public static int hash(Object key) {
 220         return hash(key.hashCode());
 221     }
 222
 223     /**
 224      * Check for equality of non-null reference x and possibly-null y.
 225      */
 226     static boolean eq(Object x, Object y) {
 227         return x == y || x.equals(y);
 228     }
 229
 230     /**
 231      * Returns index for hash code h.
 232      */
 233     public static int indexFor(int h, int length) {
 234         return h & (length-1);
 235     }
 236
 237     /**
 238      * Returns the number of key-value mappings in this map.
 239      *
 240      * @return the number of key-value mappings in this map.
 241      */
 242     public int size() {
 243         return size.get();
 244     }
 245
 246     /**
 247      * Returns <tt>true</tt> if this map contains no key-value mappings.
 248      *
 249      * @return <tt>true</tt> if this map contains no key-value mappings.
 250      */
 251     public boolean isEmpty() {
 252         return size.get() == 0;
 253     }
 254
 255     /**
 256      * Returns the value to which the specified key is mapped in this identity
 257      * hash map, or <tt>null</tt> if the map contains no mapping for this key.
 258      * A return value of <tt>null</tt> does not <i>necessarily</i> indicate
 259      * that the map contains no mapping for the key; it is also possible that
 260      * the map explicitly maps the key to <tt>null</tt>. The
 261      * <tt>containsKey</tt> method may be used to distinguish these two cases.
 262      *
 263      * @param   key the key whose associated value is to be returned.
 264      * @return  the value to which this map maps the specified key, or
 265      *          <tt>null</tt> if the map contains no mapping for this key.
 266      * @see #put(Object, Object)
 267      */
 268     public Integer get(int key) {
 269 //              if (key == null)
 270 //                  return getForNullKey();
 271         int hash = hash(key);
 272         for (TEntry e = table.get(indexFor(hash, capacity));
 273              e != null;
 274              e = e.getNext()) {
 275             Object k;
 276             if (e.getHash() == hash)
 277                 return e.getValue();
 278         }
 279         return null;
 280     }
 281
 282 //    private V getForNullKey() {
 283 //        int hash = hash(NULL_KEY.hashCode());
 284 //        int i = indexFor(hash, capacity);
 285 //        TEntry<K,V> e = table[i];
 286 //        //Entry<K,V> e = table[i];
 287 //        while (true) {
 288 //            if (e == null)
 289 //                return null;
 290 //            if (e.getKey() == NULL_KEY)
 291 //                return e.getValue();
 292 //            e = e.getNext();
 293 //        }
 294 //    }
 295
 296     /**
 297      * Returns <tt>true</tt> if this map contains a mapping for the
 298      * specified key.
 299      *
 300      * @param   key   The key whose presence in this map is to be tested
 301      * @return <tt>true</tt> if this map contains a mapping for the specified
 302      * key.
 303      */
 304     public boolean containsKey(int key) {
 305         Object k = maskNull(key);
 306         int hash = hash(k);
 307         int i = indexFor(hash, capacity);
 308         TEntry e = table.get(i);
 309         while (e != null) {
 310             if (e.getHash() == hash)
 311                 return true;
 312             e = e.getNext();
 313         }
 314         return false;
 315     }
 316
 317     /**
 318      * Returns the entry associated with the specified key in the
 319      * HashMap.  Returns null if the HashMap contains no mapping
 320      * for this key.
 321      */
 322     TEntry getEntry(int key) {
 323         int hash = hash(key);
 324         int i = indexFor(hash, capacity);
 325         TEntry e = table.get(i);
 326         while (e != null && !(e.getHash() == hash))
 327             e = e.getNext();
 328         return e;
 329     }
 330
 331     /**
 332      * Associates the specified value with the specified key in this map.
 333      * If the map previously contained a mapping for this key, the old
 334      * value is replaced.
 335      *
 336      * @param key key with which the specified value is to be associated.
 337      * @param value value to be associated with the specified key.
 338      * @return previous value associated with specified key, or <tt>null</tt>
 339      *         if there was no mapping for key.  A <tt>null</tt> return can
 340      *         also indicate that the HashMap previously associated
 341      *         <tt>null</tt> with the specified key.
 342      */
 343     public Integer put(int key, Integer value) {
 344         int hash = hash(key);
 345         int i = indexFor(hash, capacity);
 346         for (TEntry e = table.get(i); e != null; e = e.getNext()) {
 347             if (e.getHash() == hash) {
 348                 Integer oldValue = e.getValue();
 349                 e.setValue(value);
 350 //                e.recordAccess(this);
 351                 return oldValue;
 352             }
 353         }
 354         modCount++;
 355         addEntry(hash, value, i);
 356         return null;
 357     }
 358
 359
 360
 361     /**
 362      * This method is used instead of put by constructors and
 363      * pseudoconstructors (clone, readObject).  It does not resize the table,
 364      * check for comodification, etc.  It calls createEntry rather than
 365      * addEntry.
 366      */
 367     private void putForCreate(int key, Integer value) {
 368         int hash = hash(key);
 369         int i = indexFor(hash, capacity);
 370
 371         /**
 372          * Look for preexisting entry for key.  This will never happen for
 373          * clone or deserialize.  It will only happen for construction if the
 374          * input Map is a sorted map whose ordering is inconsistent w/ equals.
 375          */
 376         for (TEntry e = table.get(i); e != null; e = e.getNext()) {
 377             if (e.getHash() == hash) {
 378                 e.setValue(value);
 379                 return;
 380             }
 381         }
 382
 383         createEntry(hash, value, i);
 384     }
 385
 386     void putAllForCreate(IntHashMap m) {
 387         for (Iterator<? extends IntHashMap.TEntry> i = m.entrySet().iterator(); i.hasNext(); ) {
 388             IntHashMap.TEntry e = i.next();
 389             putForCreate(e.getHash(), e.getValue());
 390         }
 391     }
 392
 393     /**
 394      * Rehashes the contents of this map into a new array with a
 395      * larger capacity.  This method is called automatically when the
 396      * number of keys in this map reaches its threshold.
 397      *
 398      * If current capacity is MAXIMUM_CAPACITY, this method does not
 399      * resize the map, but sets threshold to Integer.MAX_VALUE.
 400      * This has the effect of preventing future calls.
 401      *
 402      * @param newCapacity the new capacity, MUST be a power of two;
 403      *        must be greater than current capacity unless current
 404      *        capacity is MAXIMUM_CAPACITY (in which case value
 405      *        is irrelevant).
 406      */
 407     void resize(int newCapacity) {
 408         dstm2.AtomicArray<TEntry> oldTable = table;
 409         int oldCapacity = capacity;
 410         if (oldCapacity == MAXIMUM_CAPACITY) {
 411             threshold = Integer.MAX_VALUE;
 412             return;
 413         }
 414
 415         dstm2.AtomicArray<TEntry> newTable = new dstm2.AtomicArray<TEntry>(TEntry.class, newCapacity);
 416         transfer(newTable, newCapacity);
 417         table = newTable;
 418         threshold = (int)(newCapacity * loadFactor);
 419         capacity = newCapacity;
 420     }
 421
 422     /**
 423      * Transfer all entries from current table to newTable.
 424      */
 425     void transfer(dstm2.AtomicArray<TEntry> newTable, int nc) {
 426         dstm2.AtomicArray<TEntry> src = table;
 427         int newCapacity = nc;
 428         for (int j = 0; j < capacity; j++) {
 429             TEntry e = src.get(j);
 430             if (e != null) {
 431                 src.set(j, null);
 432                 do {
 433                     TEntry next = e.getNext();
 434                     int i = indexFor(e.getHash(), newCapacity);
 435                     e.setNext(newTable.get(i));
 436                     newTable.set(i, e);
 437                     e = next;
 438                 } while (e != null);
 439             }
 440         }
 441     }
 442
 443     /**
 444      * Copies all of the mappings from the specified map to this map
 445      * These mappings will replace any mappings that
 446      * this map had for any of the keys currently in the specified map.
 447      *
 448      * @param m mappings to be stored in this map.
 449      * @throws NullPointerException if the specified map is null.
 450      */
 451     public void putAll(IntHashMap m) {
 452         int numKeysToBeAdded = m.size();
 453         if (numKeysToBeAdded == 0)
 454             return;
 455
 456         /*
 457          * Expand the map if the map if the number of mappings to be added
 458          * is greater than or equal to threshold.  This is conservative; the
 459          * obvious condition is (m.size() + size) >= threshold, but this
 460          * condition could result in a map with twice the appropriate capacity,
 461          * if the keys to be added overlap with the keys already in this map.
 462          * By using the conservative calculation, we subject ourself
 463          * to at most one extra resize.
 464          */
 465         if (numKeysToBeAdded > threshold) {
 466             int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
 467             if (targetCapacity > MAXIMUM_CAPACITY)
 468                 targetCapacity = MAXIMUM_CAPACITY;
 469             int newCapacity = capacity;
 470             while (newCapacity < targetCapacity)
 471                 newCapacity <<= 1;
 472             if (newCapacity > capacity)
 473                 resize(newCapacity);
 474         }
 475
 476         for (Iterator<? extends IntHashMap.TEntry> i = m.entrySet().iterator(); i.hasNext(); ) {
 477             IntHashMap.TEntry e = i.next();
 478             put(e.getHash(), e.getValue());
 479         }
 480     }
 481
 482     /**
 483      * Removes the mapping for this key from this map if present.
 484      *
 485      * @param  key key whose mapping is to be removed from the map.
 486      * @return previous value associated with specified key, or <tt>null</tt>
 487      *         if there was no mapping for key.  A <tt>null</tt> return can
 488      *         also indicate that the map previously associated <tt>null</tt>
 489      *         with the specified key.
 490      */
 491     public Integer remove(int key) {
 492         TEntry e = removeEntryForKey(key);
 493         return (e == null ? null : e.getValue());
 494     }
 495
 496     /**
 497      * Removes and returns the entry associated with the specified key
 498      * in the HashMap.  Returns null if the HashMap contains no mapping
 499      * for this key.
 500      */
 501     TEntry removeEntryForKey(int key) {
 502         int hash = hash(key);
 503         int i = indexFor(hash, capacity);
 504         TEntry prev = table.get(i);
 505         TEntry e = prev;
 506
 507         while (e != null) {
 508             TEntry next = e.getNext();
 509             if (e.getHash() == hash) {
 510                 modCount++;
 511                 size.decrementAndGet();
 512                 if (prev == e)
 513                     table.set(i, next);
 514                 else
 515                     prev.setNext(next);
 516 //                e.recordRemoval(this);
 517                 return e;
 518             }
 519             prev = e;
 520             e = next;
 521         }
 522
 523         return e;
 524     }
 525
 526     /**
 527      * Special version of remove for EntrySet.
 528      */
 529     TEntry removeMapping(TEntry o) {
 530
 531         TEntry entry = o;
 532         int hash = hash(o.getHash());
 533         int i = indexFor(hash, capacity);
 534         TEntry prev = table.get(i);
 535         TEntry e = prev;
 536
 537         while (e != null) {
 538             TEntry next = e.getNext();
 539             if (e.getHash() == hash) {
 540                 modCount++;
 541                 size.decrementAndGet();
 542                 if (prev == e)
 543                         table.set(i,  next);
 544                 else
 545                     prev.setNext(next);
 546 //                e.recordRemoval(this);
 547                 return e;
 548             }
 549             prev = e;
 550             e = next;
 551         }
 552
 553         return e;
 554     }
 555
 556     /**
 557      * Removes all mappings from this map.
 558      */
 559     public void clear() {
 560         modCount++;
 561         dstm2.AtomicArray<TEntry> tab = table;
 562         for (int i = 0; i < capacity; i++)
 563                 table.set(i, null);
 564         size.set(0);
 565     }
 566
 567     /**
 568      * Returns <tt>true</tt> if this map maps one or more keys to the
 569      * specified value.
 570      *
 571      * @param value value whose presence in this map is to be tested.
 572      * @return <tt>true</tt> if this map maps one or more keys to the
 573      *         specified value.
 574      */
 575     public boolean containsValue(Object value) {
 576         if (value == null)
 577             return containsNullValue();
 578
 579         dstm2.AtomicArray<TEntry> tab = table;
 580         for (int i = 0; i < capacity; i++)
 581             for (TEntry e = tab.get(i); e != null ; e = e.getNext())
 582                 if (value.equals(e.getValue()))
 583                     return true;
 584         return false;
 585     }
 586
 587     /**
 588      * Special-case code for containsValue with null argument
 589      **/
 590     private boolean containsNullValue() {
 591         dstm2.AtomicArray<TEntry> tab = table;
 592         for (int i = 0; i < capacity ; i++)
 593             for (TEntry e = tab.get(i) ; e != null ; e = e.getNext())
 594                 if (e.getValue() == null)
 595                     return true;
 596         return false;
 597     }
 598
 599     @atomic public interface TEntry {
 600         int getHash();
 601         Integer getValue();
 602         TEntry getNext();
 603         void setHash(int h);
 604         void setValue(Integer v);
 605         void setNext(TEntry n);
 606
 607     }
 608
 609
 610     /**
 611      * Add a new entry with the specified key, value and hash code to
 612      * the specified bucket.  It is the responsibility of this
 613      * method to resize the table if appropriate.
 614      *
 615      * Subclass overrides this to alter the behavior of put method.
 616      */
 617     void addEntry(int hash, Integer value, int bucketIndex) {
 618         TEntry e = table.get(bucketIndex);
 619         TEntry n = factory.create();
 620         n.setHash(hash);
 621         n.setValue(value);
 622         n.setNext(e);
 623         table.set(bucketIndex, n);
 624         if (size.incrementAndGet() >= threshold) {
 625                 synchronized(this) {
 626                         if(size.get() >= threshold)
 627                                 resize(2 * capacity);
 628                 }
 629         }
 630     }
 631
 632     /**
 633      * Like addEntry except that this version is used when creating entries
 634      * as part of Map construction or "pseudo-construction" (cloning,
 635      * deserialization).  This version needn't worry about resizing the table.
 636      *
 637      * Subclass overrides this to alter the behavior of HashMap(Map),
 638      * clone, and readObject.
 639      */
 640     void createEntry(int hash, Integer value, int bucketIndex) {
 641         TEntry e = table.get(bucketIndex);
 642         TEntry n = factory.create();
 643         n.setHash(hash);
 644         n.setValue(value);
 645         n.setNext(e);
 646         table.set(bucketIndex, n);
 647         size.incrementAndGet();
 648     }
 649
 650     private abstract class HashIterator<E> implements Iterator<E> {
 651         TEntry next;    // next entry to return
 652         int expectedModCount;   // For fast-fail
 653         int index;              // current slot
 654         TEntry current; // current entry
 655
 656         HashIterator() {
 657             expectedModCount = modCount;
 658             dstm2.AtomicArray<TEntry> t = table;
 659             int i = capacity;
 660             TEntry n = null;
 661             if (size.get() != 0) { // advance to first entry
 662                 while (i > 0 && (n = t.get(--i)) == null)
 663                     ;
 664             }
 665             next = n;
 666             index = i;
 667         }
 668
 669         public boolean hasNext() {
 670             return next != null;
 671         }
 672
 673         TEntry nextEntry() {
 674             if (modCount != expectedModCount)
 675                 throw new ConcurrentModificationException();
 676             TEntry e = next;
 677             if (e == null)
 678                 throw new NoSuchElementException();
 679
 680             TEntry n = e.getNext();
 681             dstm2.AtomicArray<TEntry> t = table;
 682             int i = index;
 683             while (n == null && i > 0)
 684                 n = t.get(--i);
 685             index = i;
 686             next = n;
 687             return current = e;
 688         }
 689
 690         public void remove() {
 691             if (current == null)
 692                 throw new IllegalStateException();
 693             if (modCount != expectedModCount)
 694                 throw new ConcurrentModificationException();
 695             int k = current.getHash();
 696             current = null;
 697             IntHashMap.this.removeEntryForKey(k);
 698             expectedModCount = modCount;
 699         }
 700
 701     }
 702
 703     private class ValueIterator extends HashIterator<Integer> {
 704         public Integer next() {
 705             return nextEntry().getValue();
 706         }
 707     }
 708
 709     private class KeyIterator extends HashIterator<Integer> {
 710         public Integer next() {
 711             return nextEntry().getHash();
 712         }
 713     }
 714
 715 //    private class EntryIterator extends HashIterator<Map.Entry<K,V>> {
 716 //        public Map.Entry<K,V> next() {
 717 //            return nextEntry();
 718 //        }
 719 //    }
 720
 721     // Subclass overrides these to alter behavior of views' iterator() method
 722     public Iterator<Integer> newKeyIterator()   {
 723         return new KeyIterator();
 724     }
 725     public Iterator<Integer> newValueIterator()   {
 726         return new ValueIterator();
 727     }
 728 //    Iterator<Map.Entry<K,V>> newEntryIterator()   {
 729 //        return new EntryIterator();
 730 //    }
 731
 732
 733     // Views
 734
 735     private transient Set<IntHashMap.TEntry> entrySet = null;
 736
 737
 738
 739     private class KeySet extends AbstractSet<Integer> {
 740         public Iterator<Integer> iterator() {
 741             return newKeyIterator();
 742         }
 743         public int size() {
 744             return size.get();
 745         }
 746         public boolean contains(Integer o) {
 747             return containsKey(o);
 748         }
 749         public boolean remove(Integer o) {
 750             return IntHashMap.this.removeEntryForKey(o) != null;
 751         }
 752         public void clear() {
 753             IntHashMap.this.clear();
 754         }
 755     }
 756
 757
 758
 759     /**
 760      * Returns a collection view of the mappings contained in this map.  Each
 761      * element in the returned collection is a <tt>Map.Entry</tt>.  The
 762      * collection is backed by the map, so changes to the map are reflected in
 763      * the collection, and vice-versa.  The collection supports element
 764      * removal, which removes the corresponding mapping from the map, via the
 765      * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
 766      * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
 767      * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
 768      *
 769      * @return a collection view of the mappings contained in this map.
 770      * @see Map.Entry
 771      */
 772     public Set<IntHashMap.TEntry> entrySet() {
 773         Set<IntHashMap.TEntry> es = entrySet;
 774         return (es != null ? es : (entrySet = (Set<IntHashMap.TEntry>) (Set) new EntrySet()));
 775     }
 776
 777     private class EntrySet {//extends AbstractSet/*<Map.Entry<K,V>>*/ {
 778 //        public Iterator/*<Map.Entry<K,V>>*/ iterator() {
 779 //            return newEntryIterator();
 780 //        }
 781         public boolean contains(IntHashMap.TEntry o) {
 782             IntHashMap.TEntry e = (IntHashMap.TEntry) o;
 783             TEntry candidate = getEntry(e.getHash());
 784             return candidate != null && candidate.equals(e);
 785         }
 786         public boolean remove(IntHashMap.TEntry o) {
 787             return removeMapping(o) != null;
 788         }
 789         public int size() {
 790             return size.get();
 791         }
 792         public void clear() {
 793             IntHashMap.this.clear();
 794         }
 795     }
 796
 797     /**
 798      * Save the state of the <tt>HashMap</tt> instance to a stream (i.e.,
 799      * serialize it).
 800      *
 801      * @serialData The <i>capacity</i> of the HashMap (the length of the
 802      *             bucket array) is emitted (int), followed  by the
 803      *             <i>size</i> of the HashMap (the number of key-value
 804      *             mappings), followed by the key (Object) and value (Object)
 805      *             for each key-value mapping represented by the HashMap
 806      *             The key-value mappings are emitted in the order that they
 807      *             are returned by <tt>entrySet().iterator()</tt>.
 808      *
 809      */
 810     private void writeObject(java.io.ObjectOutputStream s)
 811         throws IOException
 812     {
 813         Iterator<IntHashMap.TEntry> i = entrySet().iterator();
 814
 815         // Write out the threshold, loadfactor, and any hidden stuff
 816         s.defaultWriteObject();
 817
 818         // Write out number of buckets
 819         s.writeInt(capacity);
 820
 821         // Write out size (number of Mappings)
 822         s.writeInt(size.get());
 823
 824         // Write out keys and values (alternating)
 825         while (i.hasNext()) {
 826             IntHashMap.TEntry e = i.next();
 827             s.writeObject(e.getHash());
 828             s.writeObject(e.getValue());
 829         }
 830     }
 831
 832     private static final long serialVersionUID = 362498820763181265L;
 833
 834     /**
 835      * Reconstitute the <tt>HashMap</tt> instance from a stream (i.e.,
 836      * deserialize it).
 837      */
 838     private void readObject(java.io.ObjectInputStream s)
 839          throws IOException, ClassNotFoundException
 840     {
 841         // Read in the threshold, loadfactor, and any hidden stuff
 842         s.defaultReadObject();
 843
 844         // Read in number of buckets and allocate the bucket array;
 845         int numBuckets = s.readInt();
 846         table = new dstm2.AtomicArray(TEntry.class, numBuckets);
 847
 848         init();  // Give subclass a chance to do its thing.
 849
 850         // Read in size (number of Mappings)
 851         int size = s.readInt();
 852
 853         // Read the keys and values, and put the mappings in the HashMap
 854         for (int i=0; i<size; i++) {
 855             int key = (Integer) s.readObject();
 856             Integer value = (Integer) s.readObject();
 857             putForCreate(key, value);
 858         }
 859     }
 860
 861     // These methods are used when serializing HashSets
 862     int   capacity()     { return capacity; }
 863     float loadFactor()   { return loadFactor;   }
 864
 865         public int getCapacity() {
 866                 return capacity;
 867         }
 868
 869
 870           public Iterator<Integer> iterator() {
 871             return new Iterator<Integer>() {
 872               int tableIndex = 0;
 873               public TEntry cursor = table.get(tableIndex);
 874               public boolean hasNext() {
 875                 return cursor != null;
 876               }
 877               public Integer next() {
 878                 TEntry node = cursor;
 879                 cursor = cursor.getNext();
 880                 while(cursor==null) {
 881                         tableIndex++;
 882                         if(tableIndex < capacity) {
 883                                 cursor = table.get(tableIndex);
 884                         }
 885                 }
 886                 return node.getValue();
 887               }
 888               public void remove() {
 889                 throw new UnsupportedOperationException();
 890               }
 891
 892             };
 893           }
 894 }