changeset 9887:c9e91d933770

8020860: cluster Hashtable/Vector field updates for better transactional memory behaviour Reviewed-by: mduigou, martin, psandoz Contributed-by: sandhya.viswanathan@intel.com, mike.duigou@oracle.com
author mduigou
date Mon, 05 May 2014 09:52:24 -0700
parents 0619a50c0e2b
children f3905a67a72c
files src/share/classes/java/util/Hashtable.java src/share/classes/java/util/Vector.java
diffstat 2 files changed, 72 insertions(+), 49 deletions(-) [+]
line wrap: on
line diff
--- a/src/share/classes/java/util/Hashtable.java	Sat May 03 17:23:51 2014 -0700
+++ b/src/share/classes/java/util/Hashtable.java	Mon May 05 09:52:24 2014 -0700
@@ -26,7 +26,6 @@
 package java.util;
 
 import java.io.*;
-import java.util.concurrent.ThreadLocalRandom;
 import java.util.function.BiConsumer;
 import java.util.function.Function;
 import java.util.function.BiFunction;
@@ -92,8 +91,10 @@
  * ConcurrentModificationException}.  Thus, in the face of concurrent
  * modification, the iterator fails quickly and cleanly, rather than risking
  * arbitrary, non-deterministic behavior at an undetermined time in the future.
- * The Enumerations returned by Hashtable's keys and elements methods are
- * <em>not</em> fail-fast.
+ * The Enumerations returned by Hashtable's {@link #keys keys} and
+ * {@link #elements elements} methods are <em>not</em> fail-fast; if the
+ * Hashtable is structurally modified at any time after the enumeration is
+ * created then the results of enumerating are undefined.
  *
  * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
  * as it is, generally speaking, impossible to make any hard guarantees in the
@@ -115,6 +116,9 @@
  * to use {@link java.util.concurrent.ConcurrentHashMap} in place of
  * {@code Hashtable}.
  *
+ * @param <K> the type of keys maintained by this map
+ * @param <V> the type of mapped values
+ *
  * @author  Arthur van Hoff
  * @author  Josh Bloch
  * @author  Neal Gafter
@@ -246,6 +250,9 @@
 
     /**
      * Returns an enumeration of the keys in this hashtable.
+     * Use the Enumeration methods on the returned object to fetch the keys
+     * sequentially. If the hashtable is structurally modified while enumerating
+     * over the keys then the results of enumerating are undefined.
      *
      * @return  an enumeration of the keys in this hashtable.
      * @see     Enumeration
@@ -260,7 +267,8 @@
     /**
      * Returns an enumeration of the values in this hashtable.
      * Use the Enumeration methods on the returned object to fetch the elements
-     * sequentially.
+     * sequentially. If the hashtable is structurally modified while enumerating
+     * over the values then the results of enumerating are undefined.
      *
      * @return  an enumeration of the values in this hashtable.
      * @see     java.util.Enumeration
@@ -417,8 +425,6 @@
     }
 
     private void addEntry(int hash, K key, V value, int index) {
-        modCount++;
-
         Entry<?,?> tab[] = table;
         if (count >= threshold) {
             // Rehash the table if the threshold is exceeded
@@ -434,6 +440,7 @@
         Entry<K,V> e = (Entry<K,V>) tab[index];
         tab[index] = new Entry<>(hash, key, value, e);
         count++;
+        modCount++;
     }
 
     /**
@@ -494,12 +501,12 @@
         Entry<K,V> e = (Entry<K,V>)tab[index];
         for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
             if ((e.hash == hash) && e.key.equals(key)) {
-                modCount++;
                 if (prev != null) {
                     prev.next = e.next;
                 } else {
                     tab[index] = e.next;
                 }
+                modCount++;
                 count--;
                 V oldValue = e.value;
                 e.value = null;
@@ -528,9 +535,9 @@
      */
     public synchronized void clear() {
         Entry<?,?> tab[] = table;
-        modCount++;
         for (int index = tab.length; --index >= 0; )
             tab[index] = null;
+        modCount++;
         count = 0;
     }
 
@@ -719,14 +726,14 @@
             Entry<K,V> e = (Entry<K,V>)tab[index];
             for(Entry<K,V> prev = null; e != null; prev = e, e = e.next) {
                 if (e.hash==hash && e.equals(entry)) {
-                    modCount++;
                     if (prev != null)
                         prev.next = e.next;
                     else
                         tab[index] = e.next;
 
+                    e.value = null; // clear for gc.
+                    modCount++;
                     count--;
-                    e.value = null;
                     return true;
                 }
             }
@@ -939,14 +946,14 @@
         Entry<K,V> e = (Entry<K,V>)tab[index];
         for (Entry<K,V> prev = null; e != null; prev = e, e = e.next) {
             if ((e.hash == hash) && e.key.equals(key) && e.value.equals(value)) {
-                modCount++;
                 if (prev != null) {
                     prev.next = e.next;
                 } else {
                     tab[index] = e.next;
                 }
+                e.value = null; // clear for gc
+                modCount++;
                 count--;
-                e.value = null;
                 return true;
             }
         }
@@ -1030,12 +1037,12 @@
             if (e.hash == hash && e.key.equals(key)) {
                 V newValue = remappingFunction.apply(key, e.value);
                 if (newValue == null) {
-                    modCount++;
                     if (prev != null) {
                         prev.next = e.next;
                     } else {
                         tab[index] = e.next;
                     }
+                    modCount++;
                     count--;
                 } else {
                     e.value = newValue;
@@ -1059,12 +1066,12 @@
             if (e.hash == hash && Objects.equals(e.key, key)) {
                 V newValue = remappingFunction.apply(key, e.value);
                 if (newValue == null) {
-                    modCount++;
                     if (prev != null) {
                         prev.next = e.next;
                     } else {
                         tab[index] = e.next;
                     }
+                    modCount++;
                     count--;
                 } else {
                     e.value = newValue;
@@ -1094,12 +1101,12 @@
             if (e.hash == hash && e.key.equals(key)) {
                 V newValue = remappingFunction.apply(e.value, value);
                 if (newValue == null) {
-                    modCount++;
                     if (prev != null) {
                         prev.next = e.next;
                     } else {
                         tab[index] = e.next;
                     }
+                    modCount++;
                     count--;
                 } else {
                     e.value = newValue;
@@ -1298,24 +1305,24 @@
      * by passing an Enumeration.
      */
     private class Enumerator<T> implements Enumeration<T>, Iterator<T> {
-        Entry<?,?>[] table = Hashtable.this.table;
+        final Entry<?,?>[] table = Hashtable.this.table;
         int index = table.length;
         Entry<?,?> entry;
         Entry<?,?> lastReturned;
-        int type;
+        final int type;
 
         /**
          * Indicates whether this Enumerator is serving as an Iterator
          * or an Enumeration.  (true -> Iterator).
          */
-        boolean iterator;
+        final boolean iterator;
 
         /**
          * The modCount value that the iterator believes that the backing
          * Hashtable should have.  If this expectation is violated, the iterator
          * has detected concurrent modification.
          */
-        protected int expectedModCount = modCount;
+        protected int expectedModCount = Hashtable.this.modCount;
 
         Enumerator(int type, boolean iterator) {
             this.type = type;
@@ -1360,7 +1367,7 @@
         }
 
         public T next() {
-            if (modCount != expectedModCount)
+            if (Hashtable.this.modCount != expectedModCount)
                 throw new ConcurrentModificationException();
             return nextElement();
         }
@@ -1381,14 +1388,14 @@
                 Entry<K,V> e = (Entry<K,V>)tab[index];
                 for(Entry<K,V> prev = null; e != null; prev = e, e = e.next) {
                     if (e == lastReturned) {
-                        modCount++;
-                        expectedModCount++;
                         if (prev == null)
                             tab[index] = e.next;
                         else
                             prev.next = e.next;
-                        count--;
+                        expectedModCount++;
                         lastReturned = null;
+                        Hashtable.this.modCount++;
+                        Hashtable.this.count--;
                         return;
                     }
                 }
--- a/src/share/classes/java/util/Vector.java	Sat May 03 17:23:51 2014 -0700
+++ b/src/share/classes/java/util/Vector.java	Mon May 05 09:52:24 2014 -0700
@@ -56,7 +56,9 @@
  * concurrent modification, the iterator fails quickly and cleanly, rather
  * than risking arbitrary, non-deterministic behavior at an undetermined
  * time in the future.  The {@link Enumeration Enumerations} returned by
- * the {@link #elements() elements} method are <em>not</em> fail-fast.
+ * the {@link #elements() elements} method are <em>not</em> fail-fast; if the
+ * Vector is structurally modified at any time after the enumeration is
+ * created then the results of enumerating are undefined.
  *
  * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
  * as it is, generally speaking, impossible to make any hard guarantees in the
@@ -74,6 +76,8 @@
  * implementation is not needed, it is recommended to use {@link
  * ArrayList} in place of {@code Vector}.
  *
+ * @param <E> Type of component elements
+ *
  * @author  Lee Boynton
  * @author  Jonathan Payne
  * @see Collection
@@ -330,7 +334,9 @@
      * Returns an enumeration of the components of this vector. The
      * returned {@code Enumeration} object will generate all items in
      * this vector. The first item generated is the item at index {@code 0},
-     * then the item at index {@code 1}, and so on.
+     * then the item at index {@code 1}, and so on. If the vector is
+     * structurally modified while enumerating over the elements then the
+     * results of enumerating are undefined.
      *
      * @return  an enumeration of the components of this vector
      * @see     Iterator
@@ -553,7 +559,6 @@
      *         ({@code index < 0 || index >= size()})
      */
     public synchronized void removeElementAt(int index) {
-        modCount++;
         if (index >= elementCount) {
             throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                      elementCount);
@@ -565,6 +570,7 @@
         if (j > 0) {
             System.arraycopy(elementData, index + 1, elementData, index, j);
         }
+        modCount++;
         elementCount--;
         elementData[elementCount] = null; /* to let gc do its work */
     }
@@ -593,7 +599,6 @@
      *         ({@code index < 0 || index > size()})
      */
     public synchronized void insertElementAt(E obj, int index) {
-        modCount++;
         if (index > elementCount) {
             throw new ArrayIndexOutOfBoundsException(index
                                                      + " > " + elementCount);
@@ -601,6 +606,7 @@
         ensureCapacityHelper(elementCount + 1);
         System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
         elementData[index] = obj;
+        modCount++;
         elementCount++;
     }
 
@@ -616,8 +622,8 @@
      * @param   obj   the component to be added
      */
     public synchronized void addElement(E obj) {
+        ensureCapacityHelper(elementCount + 1);
         modCount++;
-        ensureCapacityHelper(elementCount + 1);
         elementData[elementCount++] = obj;
     }
 
@@ -653,11 +659,11 @@
      * method (which is part of the {@link List} interface).
      */
     public synchronized void removeAllElements() {
-        modCount++;
         // Let gc do its work
         for (int i = 0; i < elementCount; i++)
             elementData[i] = null;
 
+        modCount++;
         elementCount = 0;
     }
 
@@ -705,12 +711,15 @@
      * of the Vector <em>only</em> if the caller knows that the Vector
      * does not contain any null elements.)
      *
+     * @param <T> type of array elements. The same type as {@code <E>} or a
+     * supertype of {@code <E>}.
      * @param a the array into which the elements of the Vector are to
      *          be stored, if it is big enough; otherwise, a new array of the
      *          same runtime type is allocated for this purpose.
      * @return an array containing the elements of the Vector
-     * @throws ArrayStoreException if the runtime type of a is not a supertype
-     * of the runtime type of every element in this Vector
+     * @throws ArrayStoreException if the runtime type of a, {@code <T>}, is not
+     * a supertype of the runtime type, {@code <E>}, of every element in this
+     * Vector
      * @throws NullPointerException if the given array is null
      * @since 1.2
      */
@@ -778,8 +787,8 @@
      * @since 1.2
      */
     public synchronized boolean add(E e) {
+        ensureCapacityHelper(elementCount + 1);
         modCount++;
-        ensureCapacityHelper(elementCount + 1);
         elementData[elementCount++] = e;
         return true;
     }
@@ -879,14 +888,18 @@
      * @throws NullPointerException if the specified collection is null
      * @since 1.2
      */
-    public synchronized boolean addAll(Collection<? extends E> c) {
-        modCount++;
+    public boolean addAll(Collection<? extends E> c) {
         Object[] a = c.toArray();
         int numNew = a.length;
-        ensureCapacityHelper(elementCount + numNew);
-        System.arraycopy(a, 0, elementData, elementCount, numNew);
-        elementCount += numNew;
-        return numNew != 0;
+        if (numNew > 0) {
+            synchronized (this) {
+                ensureCapacityHelper(elementCount + numNew);
+                System.arraycopy(a, 0, elementData, elementCount, numNew);
+                modCount++;
+                elementCount += numNew;
+            }
+        }
+        return numNew > 0;
     }
 
     /**
@@ -951,22 +964,25 @@
      * @since 1.2
      */
     public synchronized boolean addAll(int index, Collection<? extends E> c) {
-        modCount++;
         if (index < 0 || index > elementCount)
             throw new ArrayIndexOutOfBoundsException(index);
 
         Object[] a = c.toArray();
         int numNew = a.length;
-        ensureCapacityHelper(elementCount + numNew);
 
-        int numMoved = elementCount - index;
-        if (numMoved > 0)
-            System.arraycopy(elementData, index, elementData, index + numNew,
-                             numMoved);
+        if (numNew > 0) {
+            ensureCapacityHelper(elementCount + numNew);
 
-        System.arraycopy(a, 0, elementData, index, numNew);
-        elementCount += numNew;
-        return numNew != 0;
+            int numMoved = elementCount - index;
+            if (numMoved > 0)
+                System.arraycopy(elementData, index, elementData,
+                        index + numNew, numMoved);
+
+             System.arraycopy(a, 0, elementData, index, numNew);
+             elementCount += numNew;
+             modCount++;
+        }
+        return numNew > 0;
     }
 
     /**
@@ -1047,12 +1063,12 @@
      * (If {@code toIndex==fromIndex}, this operation has no effect.)
      */
     protected synchronized void removeRange(int fromIndex, int toIndex) {
-        modCount++;
         int numMoved = elementCount - toIndex;
         System.arraycopy(elementData, toIndex, elementData, fromIndex,
                          numMoved);
 
         // Let gc do its work
+        modCount++;
         int newElementCount = elementCount - (toIndex-fromIndex);
         while (elementCount != newElementCount)
             elementData[--elementCount] = null;
@@ -1420,7 +1436,7 @@
         }
 
         public long estimateSize() {
-            return (long) (getFence() - index);
+            return getFence() - index;
         }
 
         public int characteristics() {