1 /* 2 * Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. 8 * 9 * This code is distributed in the hope that it will be useful, but WITHOUT 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12 * version 2 for more details (a copy is included in the LICENSE file that 13 * accompanied this code). 14 * 15 * You should have received a copy of the GNU General Public License version 16 * 2 along with this work; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 */ 23 24 /* 25 * @test 26 * @bug 8011944 27 * @summary Test TimSort stack size 28 */ 29 30 package test.java.util.Arrays; 31 32 import java.util.Arrays; 33 import java.util.ArrayDeque; 34 35 public class TimSortStackSize { 36 main(String[] args)37 public static void main(String[] args) { 38 testComparableTimSort(); 39 testTimSort(); 40 } 41 testComparableTimSort()42 static void testComparableTimSort() { 43 System.out.printf("testComparableTimSort()%n"); 44 Arrays.sort(genData()); 45 } 46 testTimSort()47 static void testTimSort() { 48 System.out.printf("testTimSort()%n"); 49 Arrays.sort(genData(), Integer::compare); 50 } 51 52 private static final int MIN = 16; 53 54 private static final int BOUND1 = 2 * MIN + 1; 55 private static final int BOUND2 = BOUND1 + MIN + 2; 56 private static final int BOUND3 = BOUND1 + 1 + BOUND2; 57 private static final int BOUND4 = BOUND2 + 1 + BOUND3; 58 private static final int BOUND5 = BOUND3 + 1 + BOUND4; 59 build(int size, int B, ArrayDeque<Integer> chunks)60 static int build(int size, int B, ArrayDeque<Integer> chunks) { 61 chunks.addFirst(B); 62 if (size < BOUND1) { 63 chunks.addFirst(size); 64 return size; 65 } 66 67 int asize = (size + 2) / 2; 68 if (size >= BOUND2 && asize < BOUND1) { 69 asize = BOUND1; 70 } else if (size >= BOUND3 && asize < BOUND2) { 71 asize = BOUND2; 72 } else if (size >= BOUND4 && asize < BOUND3) { 73 asize = BOUND3; 74 } else if (size >= BOUND5 && asize < BOUND4) { 75 asize = BOUND4; 76 } 77 if (size - asize >= B) { 78 throw new AssertionError(" " + size + " , " + asize + " , " + B); 79 } 80 return build(asize, size - asize, chunks); 81 } 82 genData()83 static Integer[] genData() { 84 ArrayDeque<Integer> chunks = new ArrayDeque<Integer>(); 85 chunks.addFirst(MIN); 86 87 int B = MIN + 4; 88 int A = B + MIN + 1; 89 90 for (int i = 0; i < 8; i++) { 91 int eps = build(A, B, chunks); 92 B = B + A + 1; 93 A = B + eps + 1; 94 } 95 chunks.addFirst(B); 96 chunks.addFirst(A); 97 int total = 0; 98 for (Integer len : chunks) { 99 total += len; 100 } 101 int pow = MIN; 102 while (pow < total) { 103 pow += pow; 104 } 105 chunks.addLast(pow - total); 106 System.out.println(" Total: " + total); 107 Integer[] array = new Integer[pow]; 108 int off = 0; 109 int pos = 0; 110 for (Integer len : chunks) { 111 for (int i = 0; i < len; i++) { 112 array[pos++] = Integer.valueOf(i == 0 ? 0 : 1); 113 } 114 off++; 115 } 116 return array; 117 } 118 119 } 120