7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException
authoralanb
Wed, 09 Feb 2011 15:59:27 +0000
changeset 8193 626b859aabb2
parent 8190 c8cdf811a171
child 8194 09cff98c5bb8
7018258: Dual-pivot updates in 7013585 can fail with ArrayIndexOutOfBoundsException Reviewed-by: alanb Contributed-by: vladimir.yaroslavskiy@oracle.com
jdk/src/share/classes/java/util/DualPivotQuicksort.java
jdk/test/java/util/Arrays/Sorting.java
--- a/jdk/src/share/classes/java/util/DualPivotQuicksort.java	Tue Feb 08 13:30:30 2011 -0800
+++ b/jdk/src/share/classes/java/util/DualPivotQuicksort.java	Wed Feb 09 15:59:27 2011 +0000
@@ -36,7 +36,7 @@
  * @author Jon Bentley
  * @author Josh Bloch
  *
- * @version 2011.01.21 m765.827.12i:5\7pm
+ * @version 2011.02.11 m765.827.12i:5\7pm
  * @since 1.7
  */
 final class DualPivotQuicksort {
@@ -115,7 +115,7 @@
          * Index run[i] is the start of i-th run
          * (ascending or descending sequence).
          */
-        int[] run = new int[MAX_RUN_COUNT];
+        int[] run = new int[MAX_RUN_COUNT + 1];
         int count = 0; run[0] = left;
 
         // Check if the array is nearly sorted
@@ -555,7 +555,7 @@
          * Index run[i] is the start of i-th run
          * (ascending or descending sequence).
          */
-        int[] run = new int[MAX_RUN_COUNT];
+        int[] run = new int[MAX_RUN_COUNT + 1];
         int count = 0; run[0] = left;
 
         // Check if the array is nearly sorted
@@ -1027,7 +1027,7 @@
          * Index run[i] is the start of i-th run
          * (ascending or descending sequence).
          */
-        int[] run = new int[MAX_RUN_COUNT];
+        int[] run = new int[MAX_RUN_COUNT + 1];
         int count = 0; run[0] = left;
 
         // Check if the array is nearly sorted
@@ -1499,7 +1499,7 @@
          * Index run[i] is the start of i-th run
          * (ascending or descending sequence).
          */
-        int[] run = new int[MAX_RUN_COUNT];
+        int[] run = new int[MAX_RUN_COUNT + 1];
         int count = 0; run[0] = left;
 
         // Check if the array is nearly sorted
@@ -2076,7 +2076,7 @@
          * Index run[i] is the start of i-th run
          * (ascending or descending sequence).
          */
-        int[] run = new int[MAX_RUN_COUNT];
+        int[] run = new int[MAX_RUN_COUNT + 1];
         int count = 0; run[0] = left;
 
         // Check if the array is nearly sorted
@@ -2603,7 +2603,7 @@
          * Index run[i] is the start of i-th run
          * (ascending or descending sequence).
          */
-        int[] run = new int[MAX_RUN_COUNT];
+        int[] run = new int[MAX_RUN_COUNT + 1];
         int count = 0; run[0] = left;
 
         // Check if the array is nearly sorted
--- a/jdk/test/java/util/Arrays/Sorting.java	Tue Feb 08 13:30:30 2011 -0800
+++ b/jdk/test/java/util/Arrays/Sorting.java	Wed Feb 09 15:59:27 2011 +0000
@@ -23,7 +23,7 @@
 
 /*
  * @test
- * @bug 6880672 6896573 6899694 6976036 7013585
+ * @bug 6880672 6896573 6899694 6976036 7013585 7018258
  * @summary Exercise Arrays.sort
  * @build Sorting
  * @run main Sorting -shortrun
@@ -66,7 +66,7 @@
         }
         long end = System.currentTimeMillis();
 
-        out.format("\nPASSED in %d sec.\n", Math.round((end - start) / 1E3));
+        out.format("PASSED in %d sec.\n", Math.round((end - start) / 1E3));
     }
 
     private static void testAndCheck(int[] lengths, long[] randoms) {
@@ -78,46 +78,19 @@
         testEmptyAndNullFloatArray();
         testEmptyAndNullDoubleArray();
 
-        for (long random : randoms) {
-            reset(random);
-
-            for (int length : lengths) {
-                testAndCheckWithInsertionSort(length, random);
-            }
-            reset(random);
-
-            for (int length : lengths) {
-                testAndCheckWithCheckSum(length, random);
-            }
-            reset(random);
-
-            for (int length : lengths) {
-                testAndCheckWithScrambling(length, random);
-            }
-            reset(random);
-
+        for (int length : lengths) {
+            testMergeSort(length);
+            testAndCheckRange(length);
+            testAndCheckSubArray(length);
+        }
+        for (long seed : randoms) {
             for (int length : lengths) {
-                testAndCheckFloat(length, random);
-            }
-            reset(random);
-
-            for (int length : lengths) {
-                testAndCheckDouble(length, random);
-            }
-            reset(random);
-
-            for (int length : lengths) {
-                testAndCheckRange(length, random);
-            }
-            reset(random);
-
-            for (int length : lengths) {
-                testAndCheckSubArray(length, random);
-            }
-            reset(random);
-
-            for (int length : lengths) {
-                testStable(length, random);
+                testAndCheckWithInsertionSort(length, new MyRandom(seed));
+                testAndCheckWithCheckSum(length, new MyRandom(seed));
+                testAndCheckWithScrambling(length, new MyRandom(seed));
+                testAndCheckFloat(length, new MyRandom(seed));
+                testAndCheckDouble(length, new MyRandom(seed));
+                testStable(length, new MyRandom(seed));
             }
         }
     }
@@ -255,7 +228,7 @@
         failed("Arrays.sort(double[]) shouldn't catch null array");
     }
 
-    private static void testAndCheckSubArray(int length, long random) {
+    private static void testAndCheckSubArray(int length) {
         ourDescription = "Check sorting of subarray";
         int[] golden = new int[length];
         boolean newLine = false;
@@ -282,7 +255,7 @@
         }
     }
 
-    private static void testAndCheckRange(int length, long random) {
+    private static void testAndCheckRange(int length) {
         ourDescription = "Check range check";
         int[] golden = new int[length];
 
@@ -300,15 +273,16 @@
         out.println();
     }
 
-    private static void testStable(int length, long random) {
+    private static void testStable(int length, MyRandom random) {
         ourDescription = "Check if sorting is stable";
-        Pair[] a = build(length);
+        Pair[] a = build(length, random);
 
-        out.println("Test 'stable': " + "random = " +  random +
+        out.println("Test 'stable': " + "random = " + random.getSeed() +
             ", length = " + length);
         Arrays.sort(a);
         checkSorted(a);
         checkStable(a);
+        out.println();
     }
 
     private static void checkSorted(Pair[] a) {
@@ -342,11 +316,11 @@
         }
     }
 
-    private static Pair[] build(int length) {
+    private static Pair[] build(int length, Random random) {
         Pair[] a = new Pair[length * 4];
 
         for (int i = 0; i < a.length; ) {
-            int key = ourRandom.nextInt();
+            int key = random.nextInt();
             a[i++] = new Pair(key, 1);
             a[i++] = new Pair(key, 2);
             a[i++] = new Pair(key, 3);
@@ -389,7 +363,7 @@
     }
 
 
-    private static void testAndCheckWithInsertionSort(int length, long random) {
+    private static void testAndCheckWithInsertionSort(int length, MyRandom random) {
         if (length > 1000) {
             return;
         }
@@ -398,13 +372,13 @@
 
         for (int m = 1; m < 2 * length; m *= 2) {
             for (UnsortedBuilder builder : UnsortedBuilder.values()) {
-                builder.build(golden, m);
+                builder.build(golden, m, random);
                 int[] test = golden.clone();
 
                 for (TypeConverter converter : TypeConverter.values()) {
-                    out.println("Test 'insertion sort': " + converter + " " +
-                        builder + "random = " +  random + ", length = " +
-                        length + ", m = " + m);
+                    out.println("Test 'insertion sort': " + converter +
+                        " " + builder + "random = " + random.getSeed() +
+                        ", length = " + length + ", m = " + m);
                     Object convertedGolden = converter.convert(golden);
                     Object convertedTest1 = converter.convert(test);
                     Object convertedTest2 = converter.convert(test);
@@ -417,19 +391,44 @@
         out.println();
     }
 
-    private static void testAndCheckWithCheckSum(int length, long random) {
+    private static void testMergeSort(int length) {
+        if (length < 1000) {
+            return;
+        }
+        ourDescription = "Check merge sorting";
+        int[] golden = new int[length];
+        int period = 67; // java.util.DualPivotQuicksort.MAX_RUN_COUNT
+
+        for (int m = period - 2; m <= period + 2; m++) {
+            for (MergeBuilder builder : MergeBuilder.values()) {
+                builder.build(golden, m);
+                int[] test = golden.clone();
+
+                for (TypeConverter converter : TypeConverter.values()) {
+                    out.println("Test 'merge sort': " + converter + " " +
+                        builder + "length = " + length + ", m = " + m);
+                    Object convertedGolden = converter.convert(golden);
+                    sort(convertedGolden);
+                    checkSorted(convertedGolden);
+                }
+            }
+        }
+        out.println();
+    }
+
+    private static void testAndCheckWithCheckSum(int length, MyRandom random) {
         ourDescription = "Check sorting with check sum";
         int[] golden = new int[length];
 
         for (int m = 1; m < 2 * length; m *= 2) {
             for (UnsortedBuilder builder : UnsortedBuilder.values()) {
-                builder.build(golden, m);
+                builder.build(golden, m, random);
                 int[] test = golden.clone();
 
                 for (TypeConverter converter : TypeConverter.values()) {
-                    out.println("Test 'check sum': " + converter + " " +
-                        builder + "random = " +  random + ", length = " +
-                        length + ", m = " + m);
+                    out.println("Test 'check sum': " + converter +
+                        " " + builder + "random = " + random.getSeed() +
+                        ", length = " + length + ", m = " + m);
                     Object convertedGolden = converter.convert(golden);
                     Object convertedTest = converter.convert(test);
                     sort(convertedTest);
@@ -440,7 +439,7 @@
         out.println();
     }
 
-    private static void testAndCheckWithScrambling(int length, long random) {
+    private static void testAndCheckWithScrambling(int length, MyRandom random) {
         ourDescription = "Check sorting with scrambling";
         int[] golden = new int[length];
 
@@ -451,12 +450,12 @@
             for (SortedBuilder builder : SortedBuilder.values()) {
                 builder.build(golden, m);
                 int[] test = golden.clone();
-                scramble(test);
+                scramble(test, random);
 
                 for (TypeConverter converter : TypeConverter.values()) {
-                    out.println("Test 'scrambling': " + converter + " " +
-                       builder + "random = " +  random + ", length = " +
-                       length + ", m = " + m);
+                    out.println("Test 'scrambling': " + converter +
+                       " " + builder + "random = " + random.getSeed() +
+                       ", length = " + length + ", m = " + m);
                     Object convertedGolden = converter.convert(golden);
                     Object convertedTest = converter.convert(test);
                     sort(convertedTest);
@@ -467,7 +466,7 @@
         out.println();
     }
 
-    private static void testAndCheckFloat(int length, long random) {
+    private static void testAndCheckFloat(int length, MyRandom random) {
         ourDescription = "Check float sorting";
         float[] golden = new float[length];
         final int MAX = 10;
@@ -485,13 +484,12 @@
                                 continue;
                             }
                             for (FloatBuilder builder : FloatBuilder.values()) {
-                                out.println("Test 'float': random = " + random +
-                                   ", length = " + length + ", a = " + a +
-                                   ", g = " + g + ", z = " + z + ", n = " + n +
-                                   ", p = " + p);
-                                builder.build(golden, a, g, z, n, p);
+                                out.println("Test 'float': random = " + random.getSeed() +
+                                   ", length = " + length + ", a = " + a + ", g = " +
+                                   g + ", z = " + z + ", n = " + n + ", p = " + p);
+                                builder.build(golden, a, g, z, n, p, random);
                                 float[] test = golden.clone();
-                                scramble(test);
+                                scramble(test, random);
                                 sort(test);
                                 compare(test, golden, a, n, g);
                             }
@@ -506,7 +504,7 @@
         }
     }
 
-    private static void testAndCheckDouble(int length, long random) {
+    private static void testAndCheckDouble(int length, MyRandom random) {
         ourDescription = "Check double sorting";
         double[] golden = new double[length];
         final int MAX = 10;
@@ -524,12 +522,12 @@
                                 continue;
                             }
                             for (DoubleBuilder builder : DoubleBuilder.values()) {
-                                out.println("Test 'double': random = " + random +
+                                out.println("Test 'double': random = " + random.getSeed() +
                                    ", length = " + length + ", a = " + a + ", g = " +
                                    g + ", z = " + z + ", n = " + n + ", p = " + p);
-                                builder.build(golden, a, g, z, n, p);
+                                builder.build(golden, a, g, z, n, p, random);
                                 double[] test = golden.clone();
-                                scramble(test);
+                                scramble(test, random);
                                 sort(test);
                                 compare(test, golden, a, n, g);
                             }
@@ -562,21 +560,21 @@
         }
     }
 
-    private static void scramble(int[] a) {
+    private static void scramble(int[] a, Random random) {
         for (int i = 0; i < a.length * 7; i++) {
-            swap(a, ourRandom.nextInt(a.length), ourRandom.nextInt(a.length));
+            swap(a, random.nextInt(a.length), random.nextInt(a.length));
         }
     }
 
-    private static void scramble(float[] a) {
+    private static void scramble(float[] a, Random random) {
         for (int i = 0; i < a.length * 7; i++) {
-            swap(a, ourRandom.nextInt(a.length), ourRandom.nextInt(a.length));
+            swap(a, random.nextInt(a.length), random.nextInt(a.length));
         }
     }
 
-    private static void scramble(double[] a) {
+    private static void scramble(double[] a, Random random) {
         for (int i = 0; i < a.length * 7; i++) {
-            swap(a, ourRandom.nextInt(a.length), ourRandom.nextInt(a.length));
+            swap(a, random.nextInt(a.length), random.nextInt(a.length));
         }
     }
 
@@ -689,10 +687,10 @@
 
     private static enum FloatBuilder {
         SIMPLE {
-            void build(float[] x, int a, int g, int z, int n, int p) {
+            void build(float[] x, int a, int g, int z, int n, int p, Random random) {
                 int fromIndex = 0;
-                float negativeValue = -ourRandom.nextFloat();
-                float positiveValue =  ourRandom.nextFloat();
+                float negativeValue = -random.nextFloat();
+                float positiveValue =  random.nextFloat();
 
                 writeValue(x, negativeValue, fromIndex, n);
                 fromIndex += n;
@@ -710,15 +708,15 @@
             }
         };
 
-        abstract void build(float[] x, int a, int g, int z, int n, int p);
+        abstract void build(float[] x, int a, int g, int z, int n, int p, Random random);
     }
 
     private static enum DoubleBuilder {
         SIMPLE {
-            void build(double[] x, int a, int g, int z, int n, int p) {
+            void build(double[] x, int a, int g, int z, int n, int p, Random random) {
                 int fromIndex = 0;
-                double negativeValue = -ourRandom.nextFloat();
-                double positiveValue =  ourRandom.nextFloat();
+                double negativeValue = -random.nextFloat();
+                double positiveValue =  random.nextFloat();
 
                 writeValue(x, negativeValue, fromIndex, n);
                 fromIndex += n;
@@ -736,7 +734,7 @@
             }
         };
 
-        abstract void build(double[] x, int a, int g, int z, int n, int p);
+        abstract void build(double[] x, int a, int g, int z, int n, int p, Random random);
     }
 
     private static void writeValue(float[] a, float value, int fromIndex, int count) {
@@ -812,7 +810,6 @@
                 }
             }
         },
-
         ORGAN_PIPES {
             void build(int[] a, int m) {
                 int i = 0;
@@ -841,37 +838,85 @@
         }
     }
 
+    private static enum MergeBuilder {
+        ASCENDING {
+            void build(int[] a, int m) {
+                int period = a.length / m;
+                int v = 1, i = 0;
+
+                for (int k = 0; k < m; k++) {
+                    v = 1;
+                    for (int p = 0; p < period; p++) {
+                        a[i++] = v++;
+                    }
+                }
+                for (int j = i; j < a.length - 1; j++) {
+                    a[j] = v++;
+                }
+                a[a.length - 1] = 0;
+            }
+        },
+        DESCENDING {
+            void build(int[] a, int m) {
+                int period = a.length / m;
+                int v = -1, i = 0;
+
+                for (int k = 0; k < m; k++) {
+                    v = -1;
+                    for (int p = 0; p < period; p++) {
+                        a[i++] = v--;
+                    }
+                }
+                for (int j = i; j < a.length - 1; j++) {
+                    a[j] = v--;
+                }
+                a[a.length - 1] = 0;
+            }
+        };
+
+        abstract void build(int[] a, int m);
+
+        @Override public String toString() {
+            String name = name();
+
+            for (int i = name.length(); i < 12; i++) {
+                name += " ";
+            }
+            return name;
+        }
+    }
+
     private static enum UnsortedBuilder {
         RANDOM {
-            void build(int[] a, int m) {
+            void build(int[] a, int m, Random random) {
                 for (int i = 0; i < a.length; i++) {
-                    a[i] = ourRandom.nextInt();
+                    a[i] = random.nextInt();
                 }
             }
         },
         ASCENDING {
-            void build(int[] a, int m) {
+            void build(int[] a, int m, Random random) {
                 for (int i = 0; i < a.length; i++) {
                     a[i] = m + i;
                 }
             }
         },
         DESCENDING {
-            void build(int[] a, int m) {
+            void build(int[] a, int m, Random random) {
                 for (int i = 0; i < a.length; i++) {
                     a[i] = a.length - m - i;
                 }
             }
         },
         ALL_EQUAL {
-            void build(int[] a, int m) {
+            void build(int[] a, int m, Random random) {
                 for (int i = 0; i < a.length; i++) {
                     a[i] = m;
                 }
             }
         },
         SAW {
-            void build(int[] a, int m) {
+            void build(int[] a, int m, Random random) {
                 int incCount = 1;
                 int decCount = a.length;
                 int i = 0;
@@ -897,21 +942,21 @@
             }
         },
         REPEATED {
-            void build(int[] a, int m) {
+            void build(int[] a, int m, Random random) {
                 for (int i = 0; i < a.length; i++) {
                     a[i] = i % m;
                 }
             }
         },
         DUPLICATED {
-            void build(int[] a, int m) {
+            void build(int[] a, int m, Random random) {
                 for (int i = 0; i < a.length; i++) {
-                    a[i] = ourRandom.nextInt(m);
+                    a[i] = random.nextInt(m);
                 }
             }
         },
         ORGAN_PIPES {
-            void build(int[] a, int m) {
+            void build(int[] a, int m, Random random) {
                 int middle = a.length / (m + 1);
 
                 for (int i = 0; i < middle; i++) {
@@ -923,28 +968,29 @@
             }
         },
         STAGGER {
-            void build(int[] a, int m) {
+            void build(int[] a, int m, Random random) {
                 for (int i = 0; i < a.length; i++) {
                     a[i] = (i * m + i) % a.length;
                 }
             }
         },
         PLATEAU {
-            void build(int[] a, int m) {
+            void build(int[] a, int m, Random random) {
                 for (int i = 0; i < a.length; i++) {
                     a[i] = Math.min(i, m);
                 }
             }
         },
         SHUFFLE {
-            void build(int[] a, int m) {
+            void build(int[] a, int m, Random random) {
+                int x = 0, y = 0;
                 for (int i = 0; i < a.length; i++) {
-                    a[i] = ourRandom.nextBoolean() ? (ourFirst += 2) : (ourSecond += 2);
+                    a[i] = random.nextBoolean() ? (x += 2) : (y += 2);
                 }
             }
         };
 
-        abstract void build(int[] a, int m);
+        abstract void build(int[] a, int m, Random random);
 
         @Override public String toString() {
             String name = name();
@@ -1953,18 +1999,6 @@
         }
     }
 
-    private static void prepareRandom(int[] a) {
-        for (int i = 0; i < a.length; i++) {
-            a[i] = ourRandom.nextInt();
-        }
-    }
-
-    private static void reset(long seed) {
-        ourRandom = new Random(seed);
-        ourFirst = 0;
-        ourSecond = 0;
-    }
-
     private static void outArray(Object[] a) {
         for (int i = 0; i < a.length; i++) {
             out.print(a[i] + " ");
@@ -1993,8 +2027,18 @@
         out.println();
     }
 
-    private static int ourFirst;
-    private static int ourSecond;
-    private static Random ourRandom;
+    private static class MyRandom extends Random {
+        MyRandom(long seed) {
+            super(seed);
+            mySeed = seed;
+        }
+
+        long getSeed() {
+            return mySeed;
+        }
+
+        private long mySeed;
+    }
+
     private static String ourDescription;
 }