--- jsr166/src/main/java/util/TimSort.java 2010/09/01 20:12:39 1.4 +++ jsr166/src/main/java/util/TimSort.java 2018/05/29 10:12:17 1.7 @@ -1,17 +1,27 @@ /* - * Copyright (C) 2008 The Android Open Source Project - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. + * Copyright (c) 2009, 2013, Oracle and/or its affiliates. All rights reserved. + * Copyright 2009 Google Inc. 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. Oracle designates this + * particular file as subject to the "Classpath" exception as provided + * by Oracle in the LICENSE file that accompanied this code. + * + * 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. */ package java.util; @@ -102,9 +112,13 @@ class TimSort { private static final int INITIAL_TMP_STORAGE_LENGTH = 256; /** - * Temp storage for merges. - */ - private T[] tmp; // Actual runtime type will be Object[], regardless of T + * Temp storage for merges. A workspace array may optionally be + * provided in constructor, and if so will be used as long as it + * is big enough. + */ + private T[] tmp; + private int tmpBase; // base of tmp array slice + private int tmpLen; // length of tmp array slice /** * A stack of pending runs yet to be merged. Run i starts at @@ -125,17 +139,31 @@ class TimSort { * * @param a the array to be sorted * @param c the comparator to determine the order of the sort + * @param work a workspace array (slice) + * @param workBase origin of usable space in work array + * @param workLen usable size of work array */ - private TimSort(T[] a, Comparator c) { + private TimSort(T[] a, Comparator c, T[] work, int workBase, int workLen) { this.a = a; this.c = c; // Allocate temp storage (which may be increased later if necessary) int len = a.length; - @SuppressWarnings({"unchecked", "UnnecessaryLocalVariable"}) - T[] newArray = (T[]) new Object[len < 2 * INITIAL_TMP_STORAGE_LENGTH ? - len >>> 1 : INITIAL_TMP_STORAGE_LENGTH]; - tmp = newArray; + int tlen = (len < 2 * INITIAL_TMP_STORAGE_LENGTH) ? + len >>> 1 : INITIAL_TMP_STORAGE_LENGTH; + if (work == null || workLen < tlen || workBase + tlen > work.length) { + @SuppressWarnings({"unchecked", "UnnecessaryLocalVariable"}) + T[] newArray = (T[])java.lang.reflect.Array.newInstance + (a.getClass().getComponentType(), tlen); + tmp = newArray; + tmpBase = 0; + tmpLen = tlen; + } + else { + tmp = work; + tmpBase = workBase; + tmpLen = workLen; + } /* * Allocate runs-to-be-merged stack (which cannot be expanded). The @@ -146,31 +174,43 @@ class TimSort { * large) stack lengths for smaller arrays. The "magic numbers" in the * computation below must be changed if MIN_MERGE is decreased. See * the MIN_MERGE declaration above for more information. + * The maximum value of 49 allows for an array up to length + * Integer.MAX_VALUE-4, if array is filled by the worst case stack size + * increasing scenario. More explanations are given in section 4 of: + * http://envisage-project.eu/wp-content/uploads/2015/02/sorting.pdf */ int stackLen = (len < 120 ? 5 : len < 1542 ? 10 : - len < 119151 ? 19 : 40); + len < 119151 ? 24 : 49); runBase = new int[stackLen]; runLen = new int[stackLen]; } /* - * The next two methods (which are package private and static) constitute - * the entire API of this class. Each of these methods obeys the contract - * of the public method with the same signature in java.util.Arrays. + * The next method (package private and static) constitutes the + * entire API of this class. */ - static void sort(T[] a, Comparator c) { - sort(a, 0, a.length, c); - } - - static void sort(T[] a, int lo, int hi, Comparator c) { - if (c == null) { - Arrays.sort(a, lo, hi); - return; - } + /** + * Sorts the given range, using the given workspace array slice + * for temp storage when possible. This method is designed to be + * invoked from public methods (in class Arrays) after performing + * any necessary array bounds checks and expanding parameters into + * the required forms. + * + * @param a the array to be sorted + * @param lo the index of the first element, inclusive, to be sorted + * @param hi the index of the last element, exclusive, to be sorted + * @param c the comparator to use + * @param work a workspace array (slice) + * @param workBase origin of usable space in work array + * @param workLen usable size of work array + * @since 1.8 + */ + static void sort(T[] a, int lo, int hi, Comparator c, + T[] work, int workBase, int workLen) { + assert c != null && a != null && lo >= 0 && lo <= hi && hi <= a.length; - rangeCheck(a.length, lo, hi); int nRemaining = hi - lo; if (nRemaining < 2) return; // Arrays of size 0 and 1 are always sorted @@ -187,7 +227,7 @@ class TimSort { * extending short natural runs to minRun elements, and merging runs * to maintain stack invariant. */ - TimSort ts = new TimSort(a, c); + TimSort ts = new TimSort<>(a, c, work, workBase, workLen); int minRun = minRunLength(nRemaining); do { // Identify next run @@ -230,7 +270,7 @@ class TimSort { * @param lo the index of the first element in the range to be sorted * @param hi the index after the last element in the range to be sorted * @param start the index of the first element in the range that is - * not already known to be sorted (@code lo <= start <= hi} + * not already known to be sorted ({@code lo <= start <= hi}) * @param c comparator to used for the sort */ @SuppressWarnings("fallthrough") @@ -265,7 +305,7 @@ class TimSort { * pivot < all in [left, start), so pivot belongs at left. Note * that if there are elements equal to pivot, left points to the * first slot after them -- that's why this sort is stable. - * Slide elements over to make room to make room for pivot. + * Slide elements over to make room for pivot. */ int n = start - left; // The number of elements to move // Switch is just an optimization for arraycopy in default case @@ -299,7 +339,7 @@ class TimSort { * @param a the array in which a run is to be counted and possibly reversed * @param lo index of the first element in the run * @param hi index after the last element that may be contained in the run. - It is required that @code{lo < hi}. + It is required that {@code lo < hi}. * @param c the comparator to used for the sort * @return the length of the run beginning at the specified position in * the specified array @@ -389,19 +429,23 @@ class TimSort { * This method is called each time a new run is pushed onto the stack, * so the invariants are guaranteed to hold for i < stackSize upon * entry to the method. + * + * Thanks to Stijn de Gouw, Jurriaan Rot, Frank S. de Boer, + * Richard Bubel and Reiner Hahnle, this is fixed with respect to + * the analysis in "On the Worst-Case Complexity of TimSort" by + * Nicolas Auger, Vincent Jug, Cyril Nicaud, and Carine Pivoteau. */ private void mergeCollapse() { while (stackSize > 1) { int n = stackSize - 2; - if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) { + if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1] || + n > 1 && runLen[n-2] <= runLen[n] + runLen[n-1]) { if (runLen[n - 1] < runLen[n + 1]) n--; - mergeAt(n); - } else if (runLen[n] <= runLen[n + 1]) { - mergeAt(n); - } else { + } else if (n < 0 || runLen[n] > runLen[n + 1]) { break; // Invariant is established } + mergeAt(n); } } @@ -644,11 +688,10 @@ class TimSort { // Copy first run into temp array T[] a = this.a; // For performance T[] tmp = ensureCapacity(len1); - System.arraycopy(a, base1, tmp, 0, len1); - - int cursor1 = 0; // Indexes into tmp array + int cursor1 = tmpBase; // Indexes into tmp array int cursor2 = base2; // Indexes int a int dest = base1; // Indexes int a + System.arraycopy(a, base1, tmp, cursor1, len1); // Move first element of second run and deal with degenerate cases a[dest++] = a[cursor2++]; @@ -761,16 +804,17 @@ class TimSort { // Copy second run into temp array T[] a = this.a; // For performance T[] tmp = ensureCapacity(len2); - System.arraycopy(a, base2, tmp, 0, len2); + int tmpBase = this.tmpBase; + System.arraycopy(a, base2, tmp, tmpBase, len2); int cursor1 = base1 + len1 - 1; // Indexes into a - int cursor2 = len2 - 1; // Indexes into tmp array + int cursor2 = tmpBase + len2 - 1; // Indexes into tmp array int dest = base2 + len2 - 1; // Indexes into a // Move last element of first run and deal with degenerate cases a[dest--] = a[cursor1--]; if (--len1 == 0) { - System.arraycopy(tmp, 0, a, dest - (len2 - 1), len2); + System.arraycopy(tmp, tmpBase, a, dest - (len2 - 1), len2); return; } if (len2 == 1) { @@ -829,7 +873,7 @@ class TimSort { if (--len2 == 1) break outer; - count2 = len2 - gallopLeft(a[cursor1], tmp, 0, len2, len2 - 1, c); + count2 = len2 - gallopLeft(a[cursor1], tmp, tmpBase, len2, len2 - 1, c); if (count2 != 0) { dest -= count2; cursor2 -= count2; @@ -861,7 +905,7 @@ class TimSort { } else { assert len1 == 0; assert len2 > 0; - System.arraycopy(tmp, 0, a, dest - (len2 - 1), len2); + System.arraycopy(tmp, tmpBase, a, dest - (len2 - 1), len2); } } @@ -874,14 +918,9 @@ class TimSort { * @return tmp, whether or not it grew */ private T[] ensureCapacity(int minCapacity) { - if (tmp.length < minCapacity) { + if (tmpLen < minCapacity) { // Compute smallest power of 2 > minCapacity - int newSize = minCapacity; - newSize |= newSize >> 1; - newSize |= newSize >> 2; - newSize |= newSize >> 4; - newSize |= newSize >> 8; - newSize |= newSize >> 16; + int newSize = -1 >>> Integer.numberOfLeadingZeros(minCapacity); newSize++; if (newSize < 0) // Not bloody likely! @@ -890,30 +929,12 @@ class TimSort { newSize = Math.min(newSize, a.length >>> 1); @SuppressWarnings({"unchecked", "UnnecessaryLocalVariable"}) - T[] newArray = (T[]) new Object[newSize]; + T[] newArray = (T[])java.lang.reflect.Array.newInstance + (a.getClass().getComponentType(), newSize); tmp = newArray; + tmpLen = newSize; + tmpBase = 0; } return tmp; } - - /** - * Checks that fromIndex and toIndex are in range, and throws an - * appropriate exception if they aren't. - * - * @param arrayLen the length of the array - * @param fromIndex the index of the first element of the range - * @param toIndex the index after the last element of the range - * @throws IllegalArgumentException if fromIndex > toIndex - * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 - * or toIndex > arrayLen - */ - private static void rangeCheck(int arrayLen, int fromIndex, int toIndex) { - if (fromIndex > toIndex) - throw new IllegalArgumentException("fromIndex(" + fromIndex + - ") > toIndex(" + toIndex+")"); - if (fromIndex < 0) - throw new ArrayIndexOutOfBoundsException(fromIndex); - if (toIndex > arrayLen) - throw new ArrayIndexOutOfBoundsException(toIndex); - } }