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 */ 29import java.util.Arrays; 30import java.util.ArrayDeque; 31 32public class TimSortStackSize { 33 34 public static void main(String[] args) { 35 testComparableTimSort(); 36 testTimSort(); 37 } 38 39 static void testComparableTimSort() { 40 System.out.printf("testComparableTimSort()%n"); 41 Arrays.sort(genData()); 42 } 43 44 static void testTimSort() { 45 System.out.printf("testTimSort()%n"); 46 Arrays.sort(genData(), Integer::compare); 47 } 48 49 private static final int MIN = 16; 50 51 private static final int BOUND1 = 2 * MIN + 1; 52 private static final int BOUND2 = BOUND1 + MIN + 2; 53 private static final int BOUND3 = BOUND1 + 1 + BOUND2; 54 private static final int BOUND4 = BOUND2 + 1 + BOUND3; 55 private static final int BOUND5 = BOUND3 + 1 + BOUND4; 56 57 static int build(int size, int B, ArrayDeque<Integer> chunks) { 58 chunks.addFirst(B); 59 if (size < BOUND1) { 60 chunks.addFirst(size); 61 return size; 62 } 63 64 int asize = (size + 2) / 2; 65 if (size >= BOUND2 && asize < BOUND1) { 66 asize = BOUND1; 67 } else if (size >= BOUND3 && asize < BOUND2) { 68 asize = BOUND2; 69 } else if (size >= BOUND4 && asize < BOUND3) { 70 asize = BOUND3; 71 } else if (size >= BOUND5 && asize < BOUND4) { 72 asize = BOUND4; 73 } 74 if (size - asize >= B) { 75 throw new AssertionError(" " + size + " , " + asize + " , " + B); 76 } 77 return build(asize, size - asize, chunks); 78 } 79 80 static Integer[] genData() { 81 ArrayDeque<Integer> chunks = new ArrayDeque<Integer>(); 82 chunks.addFirst(MIN); 83 84 int B = MIN + 4; 85 int A = B + MIN + 1; 86 87 for (int i = 0; i < 8; i++) { 88 int eps = build(A, B, chunks); 89 B = B + A + 1; 90 A = B + eps + 1; 91 } 92 chunks.addFirst(B); 93 chunks.addFirst(A); 94 int total = 0; 95 for (Integer len : chunks) { 96 total += len; 97 } 98 int pow = MIN; 99 while (pow < total) { 100 pow += pow; 101 } 102 chunks.addLast(pow - total); 103 System.out.println(" Total: " + total); 104 Integer[] array = new Integer[pow]; 105 int off = 0; 106 int pos = 0; 107 for (Integer len : chunks) { 108 for (int i = 0; i < len; i++) { 109 array[pos++] = Integer.valueOf(i == 0 ? 0 : 1); 110 } 111 off++; 112 } 113 return array; 114 } 115 116} 117