Mercurial > hg > openjdk > bsd-port > jdk
changeset 7793:9f5d6c8c6f4c
8011944: Sort fails with ArrayIndexOutOfBoundsException
Reviewed-by: alanb
author | miroslawzn |
---|---|
date | Thu, 30 Jan 2014 13:28:59 -0800 |
parents | 5d4ddcee9b06 |
children | cbbd96e17b06 |
files | src/share/classes/java/util/ComparableTimSort.java src/share/classes/java/util/TimSort.java test/java/util/Arrays/TimSortStackSize.java |
diffstat | 3 files changed, 125 insertions(+), 2 deletions(-) [+] |
line wrap: on
line diff
--- a/src/share/classes/java/util/ComparableTimSort.java Tue Jan 21 12:08:02 2014 +0800 +++ b/src/share/classes/java/util/ComparableTimSort.java Thu Jan 30 13:28:59 2014 -0800 @@ -131,7 +131,7 @@ */ int stackLen = (len < 120 ? 5 : len < 1542 ? 10 : - len < 119151 ? 19 : 40); + len < 119151 ? 24 : 40); runBase = new int[stackLen]; runLen = new int[stackLen]; }
--- a/src/share/classes/java/util/TimSort.java Tue Jan 21 12:08:02 2014 +0800 +++ b/src/share/classes/java/util/TimSort.java Thu Jan 30 13:28:59 2014 -0800 @@ -158,7 +158,7 @@ */ int stackLen = (len < 120 ? 5 : len < 1542 ? 10 : - len < 119151 ? 19 : 40); + len < 119151 ? 24 : 40); runBase = new int[stackLen]; runLen = new int[stackLen]; }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/java/util/Arrays/TimSortStackSize.java Thu Jan 30 13:28:59 2014 -0800 @@ -0,0 +1,123 @@ +/* + * Copyright (c) 2014, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ + +/* + * @test + * @bug 8011944 + * @summary Test TimSort stack size + */ +import java.util.Arrays; +import java.util.ArrayDeque; +import java.util.Comparator; + +public class TimSortStackSize { + + public static void main(String[] args) { + testComparableTimSort(); + testTimSort(); + } + + static void testComparableTimSort() { + System.out.printf("testComparableTimSort()%n"); + Arrays.sort(genData()); + } + + static void testTimSort() { + System.out.printf("testTimSort()%n"); + //Arrays.sort(genData(), Integer::compare); + Arrays.sort(genData(), + new java.util.Comparator<Integer>() { + public int compare(Integer a1, Integer a2){ + return Integer.compare(a1.intValue(), a2.intValue()); + } + }); + } + + private static final int MIN = 16; + + private static final int BOUND1 = 2 * MIN + 1; + private static final int BOUND2 = BOUND1 + MIN + 2; + private static final int BOUND3 = BOUND1 + 1 + BOUND2; + private static final int BOUND4 = BOUND2 + 1 + BOUND3; + private static final int BOUND5 = BOUND3 + 1 + BOUND4; + + static int build(int size, int B, ArrayDeque<Integer> chunks) { + chunks.addFirst(B); + if (size < BOUND1) { + chunks.addFirst(size); + return size; + } + + int asize = (size + 2) / 2; + if (size >= BOUND2 && asize < BOUND1) { + asize = BOUND1; + } else if (size >= BOUND3 && asize < BOUND2) { + asize = BOUND2; + } else if (size >= BOUND4 && asize < BOUND3) { + asize = BOUND3; + } else if (size >= BOUND5 && asize < BOUND4) { + asize = BOUND4; + } + if (size - asize >= B) { + throw new AssertionError(" " + size + " , " + asize + " , " + B); + } + return build(asize, size - asize, chunks); + } + + static Integer[] genData() { + ArrayDeque<Integer> chunks = new ArrayDeque<Integer>(); + chunks.addFirst(MIN); + + int B = MIN + 4; + int A = B + MIN + 1; + + for (int i = 0; i < 8; i++) { + int eps = build(A, B, chunks); + B = B + A + 1; + A = B + eps + 1; + } + chunks.addFirst(B); + chunks.addFirst(A); + int total = 0; + for (Integer len : chunks) { + total += len; + } + int pow = MIN; + while (pow < total) { + pow += pow; + } + chunks.addLast(pow - total); + System.out.println(" Total: " + total); + Integer[] array = new Integer[pow]; + int off = 0; + int pos = 0; + for (Integer len : chunks) { + for (int i = 0; i < len; i++) { + array[pos++] = Integer.valueOf(i == 0 ? 0 : 1); + } + off++; + } + return array; + } + +}