author | lpriima |
Mon, 16 Feb 2015 19:16:50 -0500 | |
changeset 28971 | 53e56ca0e39d |
parent 28871 | d04fa3bde1d0 |
child 29124 | b8f3a6579ab2 |
permissions | -rw-r--r-- |
28871
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
1 |
/* |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
2 |
* Copyright (c) 2015, Oracle and/or its affiliates. All rights reserved. |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
3 |
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
4 |
* |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
5 |
* This code is free software; you can redistribute it and/or modify it |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
6 |
* under the terms of the GNU General Public License version 2 only, as |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
7 |
* published by the Free Software Foundation. |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
8 |
* |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
9 |
* This code is distributed in the hope that it will be useful, but WITHOUT |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
10 |
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
11 |
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
12 |
* version 2 for more details (a copy is included in the LICENSE file that |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
13 |
* accompanied this code). |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
14 |
* |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
15 |
* You should have received a copy of the GNU General Public License version |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
16 |
* 2 along with this work; if not, write to the Free Software Foundation, |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
17 |
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
18 |
* |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
19 |
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
20 |
* or visit www.oracle.com if you need additional information or have any |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
21 |
* questions. |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
22 |
*/ |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
23 |
|
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
24 |
/* |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
25 |
* @test |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
26 |
* @bug 8072909 |
28971
53e56ca0e39d
8073124: Tune test and document TimSort runs length stack size increase
lpriima
parents:
28871
diff
changeset
|
27 |
* @run main/othervm -Xmx385m TimSortStackSize2 67108864 |
28871
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
28 |
* not for regular execution on all platforms: |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
29 |
* run main/othervm -Xmx8g TimSortStackSize2 1073741824 |
28971
53e56ca0e39d
8073124: Tune test and document TimSort runs length stack size increase
lpriima
parents:
28871
diff
changeset
|
30 |
* run main/othervm -Xmx16g TimSortStackSize2 2147483644 |
28871
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
31 |
* @summary Test TimSort stack size on big arrays |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
32 |
*/ |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
33 |
import java.util.ArrayList; |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
34 |
import java.util.Arrays; |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
35 |
import java.util.Comparator; |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
36 |
import java.util.List; |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
37 |
|
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
38 |
public class TimSortStackSize2 { |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
39 |
|
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
40 |
public static void main(String[] args) { |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
41 |
int lengthOfTest = Integer.parseInt(args[0]); |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
42 |
boolean passed = true; |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
43 |
try { |
28971
53e56ca0e39d
8073124: Tune test and document TimSort runs length stack size increase
lpriima
parents:
28871
diff
changeset
|
44 |
Integer [] a = new TimSortStackSize2(lengthOfTest).createArray(); |
53e56ca0e39d
8073124: Tune test and document TimSort runs length stack size increase
lpriima
parents:
28871
diff
changeset
|
45 |
long begin = System.nanoTime(); |
53e56ca0e39d
8073124: Tune test and document TimSort runs length stack size increase
lpriima
parents:
28871
diff
changeset
|
46 |
Arrays.sort(a, new Comparator<Object>() { |
28871
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
47 |
@SuppressWarnings("unchecked") |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
48 |
public int compare(Object first, Object second) { |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
49 |
return ((Comparable<Object>)first).compareTo(second); |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
50 |
} |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
51 |
}); |
28971
53e56ca0e39d
8073124: Tune test and document TimSort runs length stack size increase
lpriima
parents:
28871
diff
changeset
|
52 |
long end = System.nanoTime(); |
53e56ca0e39d
8073124: Tune test and document TimSort runs length stack size increase
lpriima
parents:
28871
diff
changeset
|
53 |
System.out.println("TimSort: " + (end - begin)); |
53e56ca0e39d
8073124: Tune test and document TimSort runs length stack size increase
lpriima
parents:
28871
diff
changeset
|
54 |
a = null; |
28871
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
55 |
} catch (ArrayIndexOutOfBoundsException e){ |
28971
53e56ca0e39d
8073124: Tune test and document TimSort runs length stack size increase
lpriima
parents:
28871
diff
changeset
|
56 |
System.out.println("TimSort broken:"); |
28871
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
57 |
e.printStackTrace(); |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
58 |
passed = false; |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
59 |
} |
28971
53e56ca0e39d
8073124: Tune test and document TimSort runs length stack size increase
lpriima
parents:
28871
diff
changeset
|
60 |
|
28871
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
61 |
try { |
28971
53e56ca0e39d
8073124: Tune test and document TimSort runs length stack size increase
lpriima
parents:
28871
diff
changeset
|
62 |
Integer [] a = new TimSortStackSize2(lengthOfTest).createArray(); |
53e56ca0e39d
8073124: Tune test and document TimSort runs length stack size increase
lpriima
parents:
28871
diff
changeset
|
63 |
long begin = System.nanoTime(); |
53e56ca0e39d
8073124: Tune test and document TimSort runs length stack size increase
lpriima
parents:
28871
diff
changeset
|
64 |
Arrays.sort(a); |
53e56ca0e39d
8073124: Tune test and document TimSort runs length stack size increase
lpriima
parents:
28871
diff
changeset
|
65 |
long end = System.nanoTime(); |
53e56ca0e39d
8073124: Tune test and document TimSort runs length stack size increase
lpriima
parents:
28871
diff
changeset
|
66 |
System.out.println("ComparableTimSort: " + (end - begin)); |
53e56ca0e39d
8073124: Tune test and document TimSort runs length stack size increase
lpriima
parents:
28871
diff
changeset
|
67 |
a = null; |
28871
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
68 |
} catch (ArrayIndexOutOfBoundsException e){ |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
69 |
System.out.println("ComparableTimSort broken:"); |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
70 |
e.printStackTrace(); |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
71 |
passed = false; |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
72 |
} |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
73 |
if ( !passed ){ |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
74 |
throw new RuntimeException(); |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
75 |
} |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
76 |
} |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
77 |
|
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
78 |
private static final int MIN_MERGE = 32; |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
79 |
private final int minRun; |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
80 |
private final int length; |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
81 |
private final List<Long> runs = new ArrayList<Long>(); |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
82 |
|
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
83 |
public TimSortStackSize2(int len) { |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
84 |
this.length = len; |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
85 |
minRun = minRunLength(len); |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
86 |
fillRunsJDKWorstCase(); |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
87 |
} |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
88 |
|
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
89 |
private static int minRunLength(int n) { |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
90 |
assert n >= 0; |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
91 |
int r = 0; // Becomes 1 if any 1 bits are shifted off |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
92 |
while (n >= MIN_MERGE) { |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
93 |
r |= (n & 1); |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
94 |
n >>= 1; |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
95 |
} |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
96 |
return n + r; |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
97 |
} |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
98 |
|
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
99 |
/** |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
100 |
* Adds a sequence x_1, ..., x_n of run lengths to <code>runs</code> such that:<br> |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
101 |
* 1. X = x_1 + ... + x_n <br> |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
102 |
* 2. x_j >= minRun for all j <br> |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
103 |
* 3. x_1 + ... + x_{j-2} < x_j < x_1 + ... + x_{j-1} for all j <br> |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
104 |
* These conditions guarantee that TimSort merges all x_j's one by one |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
105 |
* (resulting in X) using only merges on the second-to-last element. |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
106 |
* @param X The sum of the sequence that should be added to runs. |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
107 |
*/ |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
108 |
private void generateJDKWrongElem(long X) { |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
109 |
for(long newTotal; X >= 2*minRun+1; X = newTotal) { |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
110 |
//Default strategy |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
111 |
newTotal = X/2 + 1; |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
112 |
//Specialized strategies |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
113 |
if(3*minRun+3 <= X && X <= 4*minRun+1) { |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
114 |
// add x_1=MIN+1, x_2=MIN, x_3=X-newTotal to runs |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
115 |
newTotal = 2*minRun+1; |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
116 |
} else if(5*minRun+5 <= X && X <= 6*minRun+5) { |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
117 |
// add x_1=MIN+1, x_2=MIN, x_3=MIN+2, x_4=X-newTotal to runs |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
118 |
newTotal = 3*minRun+3; |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
119 |
} else if(8*minRun+9 <= X && X <= 10*minRun+9) { |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
120 |
// add x_1=MIN+1, x_2=MIN, x_3=MIN+2, x_4=2MIN+2, x_5=X-newTotal to runs |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
121 |
newTotal = 5*minRun+5; |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
122 |
} else if(13*minRun+15 <= X && X <= 16*minRun+17) { |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
123 |
// add x_1=MIN+1, x_2=MIN, x_3=MIN+2, x_4=2MIN+2, x_5=3MIN+4, x_6=X-newTotal to runs |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
124 |
newTotal = 8*minRun+9; |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
125 |
} |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
126 |
runs.add(0, X-newTotal); |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
127 |
} |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
128 |
runs.add(0, X); |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
129 |
} |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
130 |
|
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
131 |
/** |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
132 |
* Fills <code>runs</code> with a sequence of run lengths of the form<br> |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
133 |
* Y_n x_{n,1} x_{n,2} ... x_{n,l_n} <br> |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
134 |
* Y_{n-1} x_{n-1,1} x_{n-1,2} ... x_{n-1,l_{n-1}} <br> |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
135 |
* ... <br> |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
136 |
* Y_1 x_{1,1} x_{1,2} ... x_{1,l_1}<br> |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
137 |
* The Y_i's are chosen to satisfy the invariant throughout execution, |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
138 |
* but the x_{i,j}'s are merged (by <code>TimSort.mergeCollapse</code>) |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
139 |
* into an X_i that violates the invariant. |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
140 |
* X is the sum of all run lengths that will be added to <code>runs</code>. |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
141 |
*/ |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
142 |
private void fillRunsJDKWorstCase() { |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
143 |
long runningTotal = 0; |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
144 |
long Y = minRun + 4; |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
145 |
long X = minRun; |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
146 |
|
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
147 |
while(runningTotal+Y+X <= length) { |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
148 |
runningTotal += X + Y; |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
149 |
generateJDKWrongElem(X); |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
150 |
runs.add(0,Y); |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
151 |
|
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
152 |
// X_{i+1} = Y_i + x_{i,1} + 1, since runs.get(1) = x_{i,1} |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
153 |
X = Y + runs.get(1) + 1; |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
154 |
|
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
155 |
// Y_{i+1} = X_{i+1} + Y_i + 1 |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
156 |
Y += X + 1; |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
157 |
} |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
158 |
|
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
159 |
if(runningTotal + X <= length) { |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
160 |
runningTotal += X; |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
161 |
generateJDKWrongElem(X); |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
162 |
} |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
163 |
|
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
164 |
runs.add(length-runningTotal); |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
165 |
} |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
166 |
|
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
167 |
private Integer[] createArray() { |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
168 |
Integer[] a = new Integer[length]; |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
169 |
Arrays.fill(a, 0); |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
170 |
int endRun = -1; |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
171 |
for(long len : runs) |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
172 |
a[endRun+=len] = 1; |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
173 |
a[length-1]=0; |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
174 |
return a; |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
175 |
} |
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
176 |
|
d04fa3bde1d0
8072909: TimSort fails with ArrayIndexOutOfBoundsException on worst case long arrays
lpriima
parents:
diff
changeset
|
177 |
} |