1 /*

     2  * Copyright (c) 2015, 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 8072909

    27  * @run main/othervm TimSortStackSize2 67108864

    28  * not for regular execution on all platforms:

    29  * run main/othervm -Xmx8g TimSortStackSize2 1073741824

    30  * run main/othervm -Xmx32g TimSortStackSize2 2147483644

    31  * @summary Test TimSort stack size on big arrays

    32  */

    33 import java.util.ArrayList;

    34 import java.util.Arrays;

    35 import java.util.Comparator;

    36 import java.util.List;

    37 

    38 public class TimSortStackSize2 {

    39 

    40     public static void main(String[] args) {

    41         int lengthOfTest = Integer.parseInt(args[0]);

    42         boolean passed = true;

    43         try {

    44             Arrays.sort(new TimSortStackSize2(lengthOfTest).createArray(),

    45                 new Comparator<Object>() {

    46                     @SuppressWarnings("unchecked")

    47                     public int compare(Object first, Object second) {

    48                         return ((Comparable<Object>)first).compareTo(second);

    49                     }

    50                 });

    51             System.out.println("TimSort OK");

    52         } catch (ArrayIndexOutOfBoundsException e){

    53             System.out.println("TimSort broken");

    54             e.printStackTrace();

    55             passed = false;

    56         }

    57         try {

    58             Arrays.sort(new TimSortStackSize2(lengthOfTest).createArray());

    59             System.out.println("ComparableTimSort OK");

    60         } catch (ArrayIndexOutOfBoundsException e){

    61             System.out.println("ComparableTimSort broken:");

    62             e.printStackTrace();

    63             passed = false;

    64         }

    65         if ( !passed ){

    66             throw new RuntimeException();

    67         }

    68     }

    69 

    70     private static final int MIN_MERGE = 32;

    71     private final int minRun;

    72     private final int length;

    73     private final List<Long> runs = new ArrayList<Long>();

    74 

    75     public TimSortStackSize2(int len) {

    76         this.length = len;

    77         minRun = minRunLength(len);

    78         fillRunsJDKWorstCase();

    79     }

    80 

    81     private static int minRunLength(int n) {

    82         assert n >= 0;

    83         int r = 0;      // Becomes 1 if any 1 bits are shifted off

    84         while (n >= MIN_MERGE) {

    85             r |= (n & 1);

    86             n >>= 1;

    87         }

    88         return n + r;

    89     }

    90 

    91     /**

    92      * Adds a sequence x_1, ..., x_n of run lengths to <code>runs</code> such that:<br>

    93      * 1. X = x_1 + ... + x_n <br>

    94      * 2. x_j >= minRun for all j <br>

    95      * 3. x_1 + ... + x_{j-2}  <  x_j  <  x_1 + ... + x_{j-1} for all j <br>

    96      * These conditions guarantee that TimSort merges all x_j's one by one

    97      * (resulting in X) using only merges on the second-to-last element.

    98      * @param X  The sum of the sequence that should be added to runs.

    99      */

   100     private void generateJDKWrongElem(long X) {

   101         for(long newTotal; X >= 2*minRun+1; X = newTotal) {

   102             //Default strategy

   103             newTotal = X/2 + 1;

   104             //Specialized strategies

   105             if(3*minRun+3 <= X && X <= 4*minRun+1) {

   106                 // add x_1=MIN+1, x_2=MIN, x_3=X-newTotal  to runs

   107                 newTotal = 2*minRun+1;

   108             } else if(5*minRun+5 <= X && X <= 6*minRun+5) {

   109                 // add x_1=MIN+1, x_2=MIN, x_3=MIN+2, x_4=X-newTotal  to runs

   110                 newTotal = 3*minRun+3;

   111             } else if(8*minRun+9 <= X && X <= 10*minRun+9) {

   112                 // add x_1=MIN+1, x_2=MIN, x_3=MIN+2, x_4=2MIN+2, x_5=X-newTotal  to runs

   113                 newTotal = 5*minRun+5;

   114             } else if(13*minRun+15 <= X && X <= 16*minRun+17) {

   115                 // 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

   116                 newTotal = 8*minRun+9;

   117             }

   118             runs.add(0, X-newTotal);

   119         }

   120         runs.add(0, X);

   121     }

   122 

   123     /**

   124      * Fills <code>runs</code> with a sequence of run lengths of the form<br>

   125      * Y_n     x_{n,1}   x_{n,2}   ... x_{n,l_n} <br>

   126      * Y_{n-1} x_{n-1,1} x_{n-1,2} ... x_{n-1,l_{n-1}} <br>

   127      * ... <br>

   128      * Y_1     x_{1,1}   x_{1,2}   ... x_{1,l_1}<br>

   129      * The Y_i's are chosen to satisfy the invariant throughout execution,

   130      * but the x_{i,j}'s are merged (by <code>TimSort.mergeCollapse</code>)

   131      * into an X_i that violates the invariant.

   132      * X is the sum of all run lengths that will be added to <code>runs</code>.

   133      */

   134     private void fillRunsJDKWorstCase() {

   135         long runningTotal = 0;

   136         long Y = minRun + 4;

   137         long X = minRun;

   138 

   139         while(runningTotal+Y+X <= length) {

   140             runningTotal += X + Y;

   141             generateJDKWrongElem(X);

   142             runs.add(0,Y);

   143 

   144             // X_{i+1} = Y_i + x_{i,1} + 1, since runs.get(1) = x_{i,1}

   145             X = Y + runs.get(1) + 1;

   146 

   147             // Y_{i+1} = X_{i+1} + Y_i + 1

   148             Y += X + 1;

   149         }

   150 

   151         if(runningTotal + X <= length) {

   152             runningTotal += X;

   153             generateJDKWrongElem(X);

   154         }

   155 

   156         runs.add(length-runningTotal);

   157     }

   158 

   159     private Integer[] createArray() {

   160         Integer[] a = new Integer[length];

   161         Arrays.fill(a, 0);

   162         int endRun = -1;

   163         for(long len : runs)

   164             a[endRun+=len] = 1;

   165         a[length-1]=0;

   166         return a;

   167     }

   168 

   169 }