Robust/Transactions/dstm2/src/dstm2/util/HashMap.java

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