Mercurial > hg > openjdk > lambda > jdk
changeset 10514:193652dff077
Merge
author | jlaskey |
---|---|
date | Wed, 29 May 2013 13:22:58 -0300 |
parents | 00ad19610e75 (diff) efd620f8963f (current diff) |
children | 733713d7517c |
files | |
diffstat | 47 files changed, 2858 insertions(+), 2442 deletions(-) [+] |
line wrap: on
line diff
--- a/src/share/classes/com/sun/jndi/toolkit/ctx/Continuation.java Thu May 23 09:48:44 2013 -0300 +++ b/src/share/classes/com/sun/jndi/toolkit/ctx/Continuation.java Wed May 29 13:22:58 2013 -0300 @@ -1,5 +1,5 @@ /* - * Copyright (c) 1999, 2011, Oracle and/or its affiliates. All rights reserved. + * Copyright (c) 1999, 2013, 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 @@ -90,14 +90,16 @@ * Constructs a new instance of Continuation. * @param top The name of the object that is to be resolved/operated upon. * This becomes the Continuation's 'starter' and is used to - * calculate the "resolved name" when filling in a NamingException. + * calculate the "resolved name" when filling in a NamingException. * @param environment The environment used by the caller. It is used - * when setting the "environment" of a CannotProceedException. + * when setting the "environment" of a CannotProceedException. */ + @SuppressWarnings("unchecked") // For Hashtable clone: environment.clone() public Continuation(Name top, Hashtable<?,?> environment) { super(); starter = top; - this.environment = environment; + this.environment = (Hashtable<?,?>) + ((environment == null) ? null : environment.clone()); } /**
--- a/src/share/classes/com/sun/jndi/toolkit/dir/LazySearchEnumerationImpl.java Thu May 23 09:48:44 2013 -0300 +++ b/src/share/classes/com/sun/jndi/toolkit/dir/LazySearchEnumerationImpl.java Wed May 29 13:22:58 2013 -0300 @@ -1,5 +1,5 @@ /* - * Copyright (c) 1999, 2011, Oracle and/or its affiliates. All rights reserved. + * Copyright (c) 1999, 2013, 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 @@ -69,6 +69,7 @@ } } + @SuppressWarnings("unchecked") // For Hashtable clone: env.clone() public LazySearchEnumerationImpl(NamingEnumeration<Binding> candidates, AttrFilter filter, SearchControls cons, Context ctx, Hashtable<String, Object> env, boolean useFactory) @@ -76,7 +77,8 @@ this.candidates = candidates; this.filter = filter; - this.env = env; + this.env = (Hashtable<String, Object>) + ((env == null) ? null : env.clone()); this.context = ctx; this.useFactory = useFactory;
--- a/src/share/classes/com/sun/jndi/toolkit/url/GenericURLContext.java Thu May 23 09:48:44 2013 -0300 +++ b/src/share/classes/com/sun/jndi/toolkit/url/GenericURLContext.java Wed May 29 13:22:58 2013 -0300 @@ -1,5 +1,5 @@ /* - * Copyright (c) 1999, 2011, Oracle and/or its affiliates. All rights reserved. + * Copyright (c) 1999, 2013, 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 @@ -53,7 +53,8 @@ @SuppressWarnings("unchecked") // Expect Hashtable<String, Object> public GenericURLContext(Hashtable<?,?> env) { // context that is not tied to any specific URL - myEnv = (Hashtable<String, Object>)env; // copied on write + myEnv = + (Hashtable<String, Object>)(env == null ? null : env.clone()); } public void close() throws NamingException { @@ -488,22 +489,19 @@ return result; } - @SuppressWarnings("unchecked") // clone() public Object removeFromEnvironment(String propName) throws NamingException { if (myEnv == null) { return null; } - myEnv = (Hashtable<String, Object>)myEnv.clone(); return myEnv.remove(propName); } - @SuppressWarnings("unchecked") // clone() public Object addToEnvironment(String propName, Object propVal) throws NamingException { - myEnv = (myEnv == null) - ? new Hashtable<String, Object>(11, 0.75f) - : (Hashtable<String, Object>)myEnv.clone(); + if (myEnv == null) { + myEnv = new Hashtable<String, Object>(11, 0.75f); + } return myEnv.put(propName, propVal); }
--- a/src/share/classes/java/lang/ref/Reference.java Thu May 23 09:48:44 2013 -0300 +++ b/src/share/classes/java/lang/ref/Reference.java Wed May 29 13:22:58 2013 -0300 @@ -1,5 +1,5 @@ /* - * Copyright (c) 1997, 2011, Oracle and/or its affiliates. All rights reserved. + * Copyright (c) 1997, 2013, 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 @@ -138,8 +138,23 @@ pending = r.discovered; r.discovered = null; } else { + // The waiting on the lock may cause an OOME because it may try to allocate + // exception objects, so also catch OOME here to avoid silent exit of the + // reference handler thread. + // + // Explicitly define the order of the two exceptions we catch here + // when waiting for the lock. + // + // We do not want to try to potentially load the InterruptedException class + // (which would be done if this was its first use, and InterruptedException + // were checked first) in this situation. + // + // This may lead to the VM not ever trying to load the InterruptedException + // class again. try { - lock.wait(); + try { + lock.wait(); + } catch (OutOfMemoryError x) { } } catch (InterruptedException x) { } continue; }
--- a/src/share/classes/java/nio/charset/Charset-X-Coder.java.template Thu May 23 09:48:44 2013 -0300 +++ b/src/share/classes/java/nio/charset/Charset-X-Coder.java.template Wed May 29 13:22:58 2013 -0300 @@ -34,6 +34,7 @@ import java.nio.BufferUnderflowException; import java.lang.ref.WeakReference; import java.nio.charset.CoderMalfunctionError; // javadoc +import java.util.Arrays; /** @@ -244,7 +245,12 @@ * which is never <tt>null</tt> and is never empty */ public final $replType$ replacement() { +#if[decoder] return replacement; +#end[decoder] +#if[encoder] + return Arrays.copyOf(replacement, replacement.$replLength$); +#end[encoder] } /** @@ -280,12 +286,15 @@ throw new IllegalArgumentException("Empty replacement"); if (len > max$ItypesPerOtype$) throw new IllegalArgumentException("Replacement too long"); +#if[decoder] + this.replacement = newReplacement; +#end[decoder] #if[encoder] if (!isLegalReplacement(newReplacement)) throw new IllegalArgumentException("Illegal replacement"); + this.replacement = Arrays.copyOf(newReplacement, newReplacement.$replLength$); #end[encoder] - this.replacement = newReplacement; - implReplaceWith(newReplacement); + implReplaceWith(this.replacement); return this; }
--- a/src/share/classes/java/nio/file/Files.java Thu May 23 09:48:44 2013 -0300 +++ b/src/share/classes/java/nio/file/Files.java Wed May 29 13:22:58 2013 -0300 @@ -25,9 +25,11 @@ package java.nio.file; +import java.nio.ByteBuffer; import java.nio.file.attribute.*; import java.nio.file.spi.FileSystemProvider; import java.nio.file.spi.FileTypeDetector; +import java.nio.channels.FileChannel; import java.nio.channels.SeekableByteChannel; import java.io.Closeable; import java.io.InputStream; @@ -2945,40 +2947,6 @@ } /** - * Read all the bytes from an input stream. The {@code initialSize} - * parameter indicates the initial size of the byte[] to allocate. - */ - private static byte[] read(InputStream source, int initialSize) - throws IOException - { - int capacity = initialSize; - byte[] buf = new byte[capacity]; - int nread = 0; - int rem = buf.length; - int n; - // read to EOF which may read more or less than initialSize (eg: file - // is truncated while we are reading) - while ((n = source.read(buf, nread, rem)) > 0) { - nread += n; - rem -= n; - assert rem >= 0; - if (rem == 0) { - // need larger buffer - int newCapacity = capacity << 1; - if (newCapacity < 0) { - if (capacity == Integer.MAX_VALUE) - throw new OutOfMemoryError("Required array size too large"); - newCapacity = Integer.MAX_VALUE; - } - rem = newCapacity - capacity; - buf = Arrays.copyOf(buf, newCapacity); - capacity = newCapacity; - } - } - return (capacity == nread) ? buf : Arrays.copyOf(buf, nread); - } - - /** * Read all the bytes from a file. The method ensures that the file is * closed when all bytes have been read or an I/O error, or other runtime * exception, is thrown. @@ -3003,12 +2971,22 @@ * method is invoked to check read access to the file. */ public static byte[] readAllBytes(Path path) throws IOException { - long size = size(path); - if (size > (long)Integer.MAX_VALUE) - throw new OutOfMemoryError("Required array size too large"); + try (FileChannel fc = FileChannel.open(path)) { + long size = fc.size(); + if (size > (long)Integer.MAX_VALUE) + throw new OutOfMemoryError("Required array size too large"); - try (InputStream in = newInputStream(path)) { - return read(in, (int)size); + byte[] arr = new byte[(int)size]; + ByteBuffer bb = ByteBuffer.wrap(arr); + while (bb.hasRemaining()) { + if (fc.read(bb) < 0) { + // truncated + break; + } + } + + int nread = bb.position(); + return (nread == size) ? arr : Arrays.copyOf(arr, nread); } }
--- a/src/share/classes/java/util/Arrays.java Thu May 23 09:48:44 2013 -0300 +++ b/src/share/classes/java/util/Arrays.java Wed May 29 13:22:58 2013 -0300 @@ -40,7 +40,6 @@ import java.util.stream.LongStream; import java.util.stream.Stream; import java.util.stream.StreamSupport; -import static java.util.ArraysParallelSortHelpers.*; /** * This class contains various methods for manipulating arrays (such as @@ -70,17 +69,62 @@ public class Arrays { /** - * The minimum array length below which the sorting algorithm will not - * further partition the sorting task. + * The minimum array length below which a parallel sorting + * algorithm will not further partition the sorting task. Using + * smaller sizes typically results in memory contention across + * tasks that makes parallel speedups unlikely. */ - // reasonable default so that we don't overcreate tasks - private static final int MIN_ARRAY_SORT_GRAN = 256; + private static final int MIN_ARRAY_SORT_GRAN = 1 << 13; // Suppresses default constructor, ensuring non-instantiability. private Arrays() {} + /** + * A comparator that implements the natural ordering of a group of + * mutually comparable elements. May be used when a supplied + * comparator is null. To simplify code-sharing within underlying + * implementations, the compare method only declares type Object + * for its second argument. + * + * Arrays class implementor's note: It is an empirical matter + * whether ComparableTimSort offers any performance benefit over + * TimSort used with this comparator. If not, you are better off + * deleting or bypassing ComparableTimSort. There is currently no + * empirical case for separating them for parallel sorting, so all + * public Object parallelSort methods use the same comparator + * based implementation. + */ + static final class NaturalOrder implements Comparator<Object> { + @SuppressWarnings("unchecked") + public int compare(Object first, Object second) { + return ((Comparable<Object>)first).compareTo(second); + } + static final NaturalOrder INSTANCE = new NaturalOrder(); + } + + /** + * Checks that {@code fromIndex} and {@code toIndex} are in + * the range and throws an exception if they aren't. + */ + private static void rangeCheck(int arrayLength, int fromIndex, int toIndex) { + if (fromIndex > toIndex) { + throw new IllegalArgumentException( + "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")"); + } + if (fromIndex < 0) { + throw new ArrayIndexOutOfBoundsException(fromIndex); + } + if (toIndex > arrayLength) { + throw new ArrayIndexOutOfBoundsException(toIndex); + } + } + /* - * Sorting of primitive type arrays. + * Sorting methods. Note that all public "sort" methods take the + * same form: Performing argument checks if necessary, and then + * expanding arguments into those required for the internal + * implementation methods residing in other package-private + * classes (except for legacyMergeSort, included in this class). */ /** @@ -95,7 +139,7 @@ * @param a the array to be sorted */ public static void sort(int[] a) { - DualPivotQuicksort.sort(a); + DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0); } /** @@ -120,7 +164,7 @@ */ public static void sort(int[] a, int fromIndex, int toIndex) { rangeCheck(a.length, fromIndex, toIndex); - DualPivotQuicksort.sort(a, fromIndex, toIndex - 1); + DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0); } /** @@ -135,7 +179,7 @@ * @param a the array to be sorted */ public static void sort(long[] a) { - DualPivotQuicksort.sort(a); + DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0); } /** @@ -160,7 +204,7 @@ */ public static void sort(long[] a, int fromIndex, int toIndex) { rangeCheck(a.length, fromIndex, toIndex); - DualPivotQuicksort.sort(a, fromIndex, toIndex - 1); + DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0); } /** @@ -175,7 +219,7 @@ * @param a the array to be sorted */ public static void sort(short[] a) { - DualPivotQuicksort.sort(a); + DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0); } /** @@ -200,7 +244,7 @@ */ public static void sort(short[] a, int fromIndex, int toIndex) { rangeCheck(a.length, fromIndex, toIndex); - DualPivotQuicksort.sort(a, fromIndex, toIndex - 1); + DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0); } /** @@ -215,7 +259,7 @@ * @param a the array to be sorted */ public static void sort(char[] a) { - DualPivotQuicksort.sort(a); + DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0); } /** @@ -240,7 +284,7 @@ */ public static void sort(char[] a, int fromIndex, int toIndex) { rangeCheck(a.length, fromIndex, toIndex); - DualPivotQuicksort.sort(a, fromIndex, toIndex - 1); + DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0); } /** @@ -255,7 +299,7 @@ * @param a the array to be sorted */ public static void sort(byte[] a) { - DualPivotQuicksort.sort(a); + DualPivotQuicksort.sort(a, 0, a.length - 1); } /** @@ -303,7 +347,7 @@ * @param a the array to be sorted */ public static void sort(float[] a) { - DualPivotQuicksort.sort(a); + DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0); } /** @@ -336,7 +380,7 @@ */ public static void sort(float[] a, int fromIndex, int toIndex) { rangeCheck(a.length, fromIndex, toIndex); - DualPivotQuicksort.sort(a, fromIndex, toIndex - 1); + DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0); } /** @@ -359,7 +403,7 @@ * @param a the array to be sorted */ public static void sort(double[] a) { - DualPivotQuicksort.sort(a); + DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0); } /** @@ -392,7 +436,742 @@ */ public static void sort(double[] a, int fromIndex, int toIndex) { rangeCheck(a.length, fromIndex, toIndex); - DualPivotQuicksort.sort(a, fromIndex, toIndex - 1); + DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0); + } + + /** + * Sorts the specified array into ascending numerical order. + * + * @implNote The sorting algorithm is a parallel sort-merge that breaks the + * array into sub-arrays that are themselves sorted and then merged. When + * the sub-array length reaches a minimum granularity, the sub-array is + * sorted using the appropriate {@link Arrays#sort(byte[]) Arrays.sort} + * method. If the length of the specified array is less than the minimum + * granularity, then it is sorted using the appropriate {@link + * Arrays#sort(byte[]) Arrays.sort} method. The algorithm requires a + * working space no greater than the size of the original array. The + * {@link ForkJoinPool#commonPool() ForkJoin common pool} is used to + * execute any parallel tasks. + * + * @param a the array to be sorted + * + * @since 1.8 + */ + public static void parallelSort(byte[] a) { + int n = a.length, p, g; + if (n <= MIN_ARRAY_SORT_GRAN || + (p = ForkJoinPool.getCommonPoolParallelism()) == 1) + DualPivotQuicksort.sort(a, 0, n - 1); + else + new ArraysParallelSortHelpers.FJByte.Sorter + (null, a, new byte[n], 0, n, 0, + ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? + MIN_ARRAY_SORT_GRAN : g).invoke(); + } + + /** + * Sorts the specified range of the array into ascending numerical order. + * The range to be sorted extends from the index {@code fromIndex}, + * inclusive, to the index {@code toIndex}, exclusive. If + * {@code fromIndex == toIndex}, the range to be sorted is empty. + * + * @implNote The sorting algorithm is a parallel sort-merge that breaks the + * array into sub-arrays that are themselves sorted and then merged. When + * the sub-array length reaches a minimum granularity, the sub-array is + * sorted using the appropriate {@link Arrays#sort(byte[]) Arrays.sort} + * method. If the length of the specified array is less than the minimum + * granularity, then it is sorted using the appropriate {@link + * Arrays#sort(byte[]) Arrays.sort} method. The algorithm requires a working + * space no greater than the size of the specified range of the original + * array. The {@link ForkJoinPool#commonPool() ForkJoin common pool} is + * used to execute any parallel tasks. + * + * @param a the array to be sorted + * @param fromIndex the index of the first element, inclusive, to be sorted + * @param toIndex the index of the last element, exclusive, to be sorted + * + * @throws IllegalArgumentException if {@code fromIndex > toIndex} + * @throws ArrayIndexOutOfBoundsException + * if {@code fromIndex < 0} or {@code toIndex > a.length} + * + * @since 1.8 + */ + public static void parallelSort(byte[] a, int fromIndex, int toIndex) { + rangeCheck(a.length, fromIndex, toIndex); + int n = toIndex - fromIndex, p, g; + if (n <= MIN_ARRAY_SORT_GRAN || + (p = ForkJoinPool.getCommonPoolParallelism()) == 1) + DualPivotQuicksort.sort(a, fromIndex, toIndex - 1); + else + new ArraysParallelSortHelpers.FJByte.Sorter + (null, a, new byte[n], fromIndex, n, 0, + ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? + MIN_ARRAY_SORT_GRAN : g).invoke(); + } + + /** + * Sorts the specified array into ascending numerical order. + * + * @implNote The sorting algorithm is a parallel sort-merge that breaks the + * array into sub-arrays that are themselves sorted and then merged. When + * the sub-array length reaches a minimum granularity, the sub-array is + * sorted using the appropriate {@link Arrays#sort(char[]) Arrays.sort} + * method. If the length of the specified array is less than the minimum + * granularity, then it is sorted using the appropriate {@link + * Arrays#sort(char[]) Arrays.sort} method. The algorithm requires a + * working space no greater than the size of the original array. The + * {@link ForkJoinPool#commonPool() ForkJoin common pool} is used to + * execute any parallel tasks. + * + * @param a the array to be sorted + * + * @since 1.8 + */ + public static void parallelSort(char[] a) { + int n = a.length, p, g; + if (n <= MIN_ARRAY_SORT_GRAN || + (p = ForkJoinPool.getCommonPoolParallelism()) == 1) + DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0); + else + new ArraysParallelSortHelpers.FJChar.Sorter + (null, a, new char[n], 0, n, 0, + ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? + MIN_ARRAY_SORT_GRAN : g).invoke(); + } + + /** + * Sorts the specified range of the array into ascending numerical order. + * The range to be sorted extends from the index {@code fromIndex}, + * inclusive, to the index {@code toIndex}, exclusive. If + * {@code fromIndex == toIndex}, the range to be sorted is empty. + * + @implNote The sorting algorithm is a parallel sort-merge that breaks the + * array into sub-arrays that are themselves sorted and then merged. When + * the sub-array length reaches a minimum granularity, the sub-array is + * sorted using the appropriate {@link Arrays#sort(char[]) Arrays.sort} + * method. If the length of the specified array is less than the minimum + * granularity, then it is sorted using the appropriate {@link + * Arrays#sort(char[]) Arrays.sort} method. The algorithm requires a working + * space no greater than the size of the specified range of the original + * array. The {@link ForkJoinPool#commonPool() ForkJoin common pool} is + * used to execute any parallel tasks. + * + * @param a the array to be sorted + * @param fromIndex the index of the first element, inclusive, to be sorted + * @param toIndex the index of the last element, exclusive, to be sorted + * + * @throws IllegalArgumentException if {@code fromIndex > toIndex} + * @throws ArrayIndexOutOfBoundsException + * if {@code fromIndex < 0} or {@code toIndex > a.length} + * + * @since 1.8 + */ + public static void parallelSort(char[] a, int fromIndex, int toIndex) { + rangeCheck(a.length, fromIndex, toIndex); + int n = toIndex - fromIndex, p, g; + if (n <= MIN_ARRAY_SORT_GRAN || + (p = ForkJoinPool.getCommonPoolParallelism()) == 1) + DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0); + else + new ArraysParallelSortHelpers.FJChar.Sorter + (null, a, new char[n], fromIndex, n, 0, + ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? + MIN_ARRAY_SORT_GRAN : g).invoke(); + } + + /** + * Sorts the specified array into ascending numerical order. + * + * @implNote The sorting algorithm is a parallel sort-merge that breaks the + * array into sub-arrays that are themselves sorted and then merged. When + * the sub-array length reaches a minimum granularity, the sub-array is + * sorted using the appropriate {@link Arrays#sort(short[]) Arrays.sort} + * method. If the length of the specified array is less than the minimum + * granularity, then it is sorted using the appropriate {@link + * Arrays#sort(short[]) Arrays.sort} method. The algorithm requires a + * working space no greater than the size of the original array. The + * {@link ForkJoinPool#commonPool() ForkJoin common pool} is used to + * execute any parallel tasks. + * + * @param a the array to be sorted + * + * @since 1.8 + */ + public static void parallelSort(short[] a) { + int n = a.length, p, g; + if (n <= MIN_ARRAY_SORT_GRAN || + (p = ForkJoinPool.getCommonPoolParallelism()) == 1) + DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0); + else + new ArraysParallelSortHelpers.FJShort.Sorter + (null, a, new short[n], 0, n, 0, + ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? + MIN_ARRAY_SORT_GRAN : g).invoke(); + } + + /** + * Sorts the specified range of the array into ascending numerical order. + * The range to be sorted extends from the index {@code fromIndex}, + * inclusive, to the index {@code toIndex}, exclusive. If + * {@code fromIndex == toIndex}, the range to be sorted is empty. + * + * @implNote The sorting algorithm is a parallel sort-merge that breaks the + * array into sub-arrays that are themselves sorted and then merged. When + * the sub-array length reaches a minimum granularity, the sub-array is + * sorted using the appropriate {@link Arrays#sort(short[]) Arrays.sort} + * method. If the length of the specified array is less than the minimum + * granularity, then it is sorted using the appropriate {@link + * Arrays#sort(short[]) Arrays.sort} method. The algorithm requires a working + * space no greater than the size of the specified range of the original + * array. The {@link ForkJoinPool#commonPool() ForkJoin common pool} is + * used to execute any parallel tasks. + * + * @param a the array to be sorted + * @param fromIndex the index of the first element, inclusive, to be sorted + * @param toIndex the index of the last element, exclusive, to be sorted + * + * @throws IllegalArgumentException if {@code fromIndex > toIndex} + * @throws ArrayIndexOutOfBoundsException + * if {@code fromIndex < 0} or {@code toIndex > a.length} + * + * @since 1.8 + */ + public static void parallelSort(short[] a, int fromIndex, int toIndex) { + rangeCheck(a.length, fromIndex, toIndex); + int n = toIndex - fromIndex, p, g; + if (n <= MIN_ARRAY_SORT_GRAN || + (p = ForkJoinPool.getCommonPoolParallelism()) == 1) + DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0); + else + new ArraysParallelSortHelpers.FJShort.Sorter + (null, a, new short[n], fromIndex, n, 0, + ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? + MIN_ARRAY_SORT_GRAN : g).invoke(); + } + + /** + * Sorts the specified array into ascending numerical order. + * + * @implNote The sorting algorithm is a parallel sort-merge that breaks the + * array into sub-arrays that are themselves sorted and then merged. When + * the sub-array length reaches a minimum granularity, the sub-array is + * sorted using the appropriate {@link Arrays#sort(int[]) Arrays.sort} + * method. If the length of the specified array is less than the minimum + * granularity, then it is sorted using the appropriate {@link + * Arrays#sort(int[]) Arrays.sort} method. The algorithm requires a + * working space no greater than the size of the original array. The + * {@link ForkJoinPool#commonPool() ForkJoin common pool} is used to + * execute any parallel tasks. + * + * @param a the array to be sorted + * + * @since 1.8 + */ + public static void parallelSort(int[] a) { + int n = a.length, p, g; + if (n <= MIN_ARRAY_SORT_GRAN || + (p = ForkJoinPool.getCommonPoolParallelism()) == 1) + DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0); + else + new ArraysParallelSortHelpers.FJInt.Sorter + (null, a, new int[n], 0, n, 0, + ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? + MIN_ARRAY_SORT_GRAN : g).invoke(); + } + + /** + * Sorts the specified range of the array into ascending numerical order. + * The range to be sorted extends from the index {@code fromIndex}, + * inclusive, to the index {@code toIndex}, exclusive. If + * {@code fromIndex == toIndex}, the range to be sorted is empty. + * + * @implNote The sorting algorithm is a parallel sort-merge that breaks the + * array into sub-arrays that are themselves sorted and then merged. When + * the sub-array length reaches a minimum granularity, the sub-array is + * sorted using the appropriate {@link Arrays#sort(int[]) Arrays.sort} + * method. If the length of the specified array is less than the minimum + * granularity, then it is sorted using the appropriate {@link + * Arrays#sort(int[]) Arrays.sort} method. The algorithm requires a working + * space no greater than the size of the specified range of the original + * array. The {@link ForkJoinPool#commonPool() ForkJoin common pool} is + * used to execute any parallel tasks. + * + * @param a the array to be sorted + * @param fromIndex the index of the first element, inclusive, to be sorted + * @param toIndex the index of the last element, exclusive, to be sorted + * + * @throws IllegalArgumentException if {@code fromIndex > toIndex} + * @throws ArrayIndexOutOfBoundsException + * if {@code fromIndex < 0} or {@code toIndex > a.length} + * + * @since 1.8 + */ + public static void parallelSort(int[] a, int fromIndex, int toIndex) { + rangeCheck(a.length, fromIndex, toIndex); + int n = toIndex - fromIndex, p, g; + if (n <= MIN_ARRAY_SORT_GRAN || + (p = ForkJoinPool.getCommonPoolParallelism()) == 1) + DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0); + else + new ArraysParallelSortHelpers.FJInt.Sorter + (null, a, new int[n], fromIndex, n, 0, + ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? + MIN_ARRAY_SORT_GRAN : g).invoke(); + } + + /** + * Sorts the specified array into ascending numerical order. + * + * @implNote The sorting algorithm is a parallel sort-merge that breaks the + * array into sub-arrays that are themselves sorted and then merged. When + * the sub-array length reaches a minimum granularity, the sub-array is + * sorted using the appropriate {@link Arrays#sort(long[]) Arrays.sort} + * method. If the length of the specified array is less than the minimum + * granularity, then it is sorted using the appropriate {@link + * Arrays#sort(long[]) Arrays.sort} method. The algorithm requires a + * working space no greater than the size of the original array. The + * {@link ForkJoinPool#commonPool() ForkJoin common pool} is used to + * execute any parallel tasks. + * + * @param a the array to be sorted + * + * @since 1.8 + */ + public static void parallelSort(long[] a) { + int n = a.length, p, g; + if (n <= MIN_ARRAY_SORT_GRAN || + (p = ForkJoinPool.getCommonPoolParallelism()) == 1) + DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0); + else + new ArraysParallelSortHelpers.FJLong.Sorter + (null, a, new long[n], 0, n, 0, + ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? + MIN_ARRAY_SORT_GRAN : g).invoke(); + } + + /** + * Sorts the specified range of the array into ascending numerical order. + * The range to be sorted extends from the index {@code fromIndex}, + * inclusive, to the index {@code toIndex}, exclusive. If + * {@code fromIndex == toIndex}, the range to be sorted is empty. + * + * @implNote The sorting algorithm is a parallel sort-merge that breaks the + * array into sub-arrays that are themselves sorted and then merged. When + * the sub-array length reaches a minimum granularity, the sub-array is + * sorted using the appropriate {@link Arrays#sort(long[]) Arrays.sort} + * method. If the length of the specified array is less than the minimum + * granularity, then it is sorted using the appropriate {@link + * Arrays#sort(long[]) Arrays.sort} method. The algorithm requires a working + * space no greater than the size of the specified range of the original + * array. The {@link ForkJoinPool#commonPool() ForkJoin common pool} is + * used to execute any parallel tasks. + * + * @param a the array to be sorted + * @param fromIndex the index of the first element, inclusive, to be sorted + * @param toIndex the index of the last element, exclusive, to be sorted + * + * @throws IllegalArgumentException if {@code fromIndex > toIndex} + * @throws ArrayIndexOutOfBoundsException + * if {@code fromIndex < 0} or {@code toIndex > a.length} + * + * @since 1.8 + */ + public static void parallelSort(long[] a, int fromIndex, int toIndex) { + rangeCheck(a.length, fromIndex, toIndex); + int n = toIndex - fromIndex, p, g; + if (n <= MIN_ARRAY_SORT_GRAN || + (p = ForkJoinPool.getCommonPoolParallelism()) == 1) + DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0); + else + new ArraysParallelSortHelpers.FJLong.Sorter + (null, a, new long[n], fromIndex, n, 0, + ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? + MIN_ARRAY_SORT_GRAN : g).invoke(); + } + + /** + * Sorts the specified array into ascending numerical order. + * + * <p>The {@code <} relation does not provide a total order on all float + * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN} + * value compares neither less than, greater than, nor equal to any value, + * even itself. This method uses the total order imposed by the method + * {@link Float#compareTo}: {@code -0.0f} is treated as less than value + * {@code 0.0f} and {@code Float.NaN} is considered greater than any + * other value and all {@code Float.NaN} values are considered equal. + * + * @implNote The sorting algorithm is a parallel sort-merge that breaks the + * array into sub-arrays that are themselves sorted and then merged. When + * the sub-array length reaches a minimum granularity, the sub-array is + * sorted using the appropriate {@link Arrays#sort(float[]) Arrays.sort} + * method. If the length of the specified array is less than the minimum + * granularity, then it is sorted using the appropriate {@link + * Arrays#sort(float[]) Arrays.sort} method. The algorithm requires a + * working space no greater than the size of the original array. The + * {@link ForkJoinPool#commonPool() ForkJoin common pool} is used to + * execute any parallel tasks. + * + * @param a the array to be sorted + * + * @since 1.8 + */ + public static void parallelSort(float[] a) { + int n = a.length, p, g; + if (n <= MIN_ARRAY_SORT_GRAN || + (p = ForkJoinPool.getCommonPoolParallelism()) == 1) + DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0); + else + new ArraysParallelSortHelpers.FJFloat.Sorter + (null, a, new float[n], 0, n, 0, + ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? + MIN_ARRAY_SORT_GRAN : g).invoke(); + } + + /** + * Sorts the specified range of the array into ascending numerical order. + * The range to be sorted extends from the index {@code fromIndex}, + * inclusive, to the index {@code toIndex}, exclusive. If + * {@code fromIndex == toIndex}, the range to be sorted is empty. + * + * <p>The {@code <} relation does not provide a total order on all float + * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN} + * value compares neither less than, greater than, nor equal to any value, + * even itself. This method uses the total order imposed by the method + * {@link Float#compareTo}: {@code -0.0f} is treated as less than value + * {@code 0.0f} and {@code Float.NaN} is considered greater than any + * other value and all {@code Float.NaN} values are considered equal. + * + * @implNote The sorting algorithm is a parallel sort-merge that breaks the + * array into sub-arrays that are themselves sorted and then merged. When + * the sub-array length reaches a minimum granularity, the sub-array is + * sorted using the appropriate {@link Arrays#sort(float[]) Arrays.sort} + * method. If the length of the specified array is less than the minimum + * granularity, then it is sorted using the appropriate {@link + * Arrays#sort(float[]) Arrays.sort} method. The algorithm requires a working + * space no greater than the size of the specified range of the original + * array. The {@link ForkJoinPool#commonPool() ForkJoin common pool} is + * used to execute any parallel tasks. + * + * @param a the array to be sorted + * @param fromIndex the index of the first element, inclusive, to be sorted + * @param toIndex the index of the last element, exclusive, to be sorted + * + * @throws IllegalArgumentException if {@code fromIndex > toIndex} + * @throws ArrayIndexOutOfBoundsException + * if {@code fromIndex < 0} or {@code toIndex > a.length} + * + * @since 1.8 + */ + public static void parallelSort(float[] a, int fromIndex, int toIndex) { + rangeCheck(a.length, fromIndex, toIndex); + int n = toIndex - fromIndex, p, g; + if (n <= MIN_ARRAY_SORT_GRAN || + (p = ForkJoinPool.getCommonPoolParallelism()) == 1) + DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0); + else + new ArraysParallelSortHelpers.FJFloat.Sorter + (null, a, new float[n], fromIndex, n, 0, + ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? + MIN_ARRAY_SORT_GRAN : g).invoke(); + } + + /** + * Sorts the specified array into ascending numerical order. + * + * <p>The {@code <} relation does not provide a total order on all double + * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN} + * value compares neither less than, greater than, nor equal to any value, + * even itself. This method uses the total order imposed by the method + * {@link Double#compareTo}: {@code -0.0d} is treated as less than value + * {@code 0.0d} and {@code Double.NaN} is considered greater than any + * other value and all {@code Double.NaN} values are considered equal. + * + * @implNote The sorting algorithm is a parallel sort-merge that breaks the + * array into sub-arrays that are themselves sorted and then merged. When + * the sub-array length reaches a minimum granularity, the sub-array is + * sorted using the appropriate {@link Arrays#sort(double[]) Arrays.sort} + * method. If the length of the specified array is less than the minimum + * granularity, then it is sorted using the appropriate {@link + * Arrays#sort(double[]) Arrays.sort} method. The algorithm requires a + * working space no greater than the size of the original array. The + * {@link ForkJoinPool#commonPool() ForkJoin common pool} is used to + * execute any parallel tasks. + * + * @param a the array to be sorted + * + * @since 1.8 + */ + public static void parallelSort(double[] a) { + int n = a.length, p, g; + if (n <= MIN_ARRAY_SORT_GRAN || + (p = ForkJoinPool.getCommonPoolParallelism()) == 1) + DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0); + else + new ArraysParallelSortHelpers.FJDouble.Sorter + (null, a, new double[n], 0, n, 0, + ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? + MIN_ARRAY_SORT_GRAN : g).invoke(); + } + + /** + * Sorts the specified range of the array into ascending numerical order. + * The range to be sorted extends from the index {@code fromIndex}, + * inclusive, to the index {@code toIndex}, exclusive. If + * {@code fromIndex == toIndex}, the range to be sorted is empty. + * + * <p>The {@code <} relation does not provide a total order on all double + * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN} + * value compares neither less than, greater than, nor equal to any value, + * even itself. This method uses the total order imposed by the method + * {@link Double#compareTo}: {@code -0.0d} is treated as less than value + * {@code 0.0d} and {@code Double.NaN} is considered greater than any + * other value and all {@code Double.NaN} values are considered equal. + * + * @implNote The sorting algorithm is a parallel sort-merge that breaks the + * array into sub-arrays that are themselves sorted and then merged. When + * the sub-array length reaches a minimum granularity, the sub-array is + * sorted using the appropriate {@link Arrays#sort(double[]) Arrays.sort} + * method. If the length of the specified array is less than the minimum + * granularity, then it is sorted using the appropriate {@link + * Arrays#sort(double[]) Arrays.sort} method. The algorithm requires a working + * space no greater than the size of the specified range of the original + * array. The {@link ForkJoinPool#commonPool() ForkJoin common pool} is + * used to execute any parallel tasks. + * + * @param a the array to be sorted + * @param fromIndex the index of the first element, inclusive, to be sorted + * @param toIndex the index of the last element, exclusive, to be sorted + * + * @throws IllegalArgumentException if {@code fromIndex > toIndex} + * @throws ArrayIndexOutOfBoundsException + * if {@code fromIndex < 0} or {@code toIndex > a.length} + * + * @since 1.8 + */ + public static void parallelSort(double[] a, int fromIndex, int toIndex) { + rangeCheck(a.length, fromIndex, toIndex); + int n = toIndex - fromIndex, p, g; + if (n <= MIN_ARRAY_SORT_GRAN || + (p = ForkJoinPool.getCommonPoolParallelism()) == 1) + DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0); + else + new ArraysParallelSortHelpers.FJDouble.Sorter + (null, a, new double[n], fromIndex, n, 0, + ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? + MIN_ARRAY_SORT_GRAN : g).invoke(); + } + + /** + * Sorts the specified array of objects into ascending order, according + * to the {@linkplain Comparable natural ordering} of its elements. + * All elements in the array must implement the {@link Comparable} + * interface. Furthermore, all elements in the array must be + * <i>mutually comparable</i> (that is, {@code e1.compareTo(e2)} must + * not throw a {@code ClassCastException} for any elements {@code e1} + * and {@code e2} in the array). + * + * <p>This sort is guaranteed to be <i>stable</i>: equal elements will + * not be reordered as a result of the sort. + * + * @implNote The sorting algorithm is a parallel sort-merge that breaks the + * array into sub-arrays that are themselves sorted and then merged. When + * the sub-array length reaches a minimum granularity, the sub-array is + * sorted using the appropriate {@link Arrays#sort(Object[]) Arrays.sort} + * method. If the length of the specified array is less than the minimum + * granularity, then it is sorted using the appropriate {@link + * Arrays#sort(Object[]) Arrays.sort} method. The algorithm requires a + * working space no greater than the size of the original array. The + * {@link ForkJoinPool#commonPool() ForkJoin common pool} is used to + * execute any parallel tasks. + * + * @param a the array to be sorted + * + * @throws ClassCastException if the array contains elements that are not + * <i>mutually comparable</i> (for example, strings and integers) + * @throws IllegalArgumentException (optional) if the natural + * ordering of the array elements is found to violate the + * {@link Comparable} contract + * + * @since 1.8 + */ + @SuppressWarnings("unchecked") + public static <T extends Comparable<? super T>> void parallelSort(T[] a) { + int n = a.length, p, g; + if (n <= MIN_ARRAY_SORT_GRAN || + (p = ForkJoinPool.getCommonPoolParallelism()) == 1) + TimSort.sort(a, 0, n, NaturalOrder.INSTANCE, null, 0, 0); + else + new ArraysParallelSortHelpers.FJObject.Sorter<T> + (null, a, + (T[])Array.newInstance(a.getClass().getComponentType(), n), + 0, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? + MIN_ARRAY_SORT_GRAN : g, NaturalOrder.INSTANCE).invoke(); + } + + /** + * Sorts the specified range of the specified array of objects into + * ascending order, according to the + * {@linkplain Comparable natural ordering} of its + * elements. The range to be sorted extends from index + * {@code fromIndex}, inclusive, to index {@code toIndex}, exclusive. + * (If {@code fromIndex==toIndex}, the range to be sorted is empty.) All + * elements in this range must implement the {@link Comparable} + * interface. Furthermore, all elements in this range must be <i>mutually + * comparable</i> (that is, {@code e1.compareTo(e2)} must not throw a + * {@code ClassCastException} for any elements {@code e1} and + * {@code e2} in the array). + * + * <p>This sort is guaranteed to be <i>stable</i>: equal elements will + * not be reordered as a result of the sort. + * + * @implNote The sorting algorithm is a parallel sort-merge that breaks the + * array into sub-arrays that are themselves sorted and then merged. When + * the sub-array length reaches a minimum granularity, the sub-array is + * sorted using the appropriate {@link Arrays#sort(Object[]) Arrays.sort} + * method. If the length of the specified array is less than the minimum + * granularity, then it is sorted using the appropriate {@link + * Arrays#sort(Object[]) Arrays.sort} method. The algorithm requires a working + * space no greater than the size of the specified range of the original + * array. The {@link ForkJoinPool#commonPool() ForkJoin common pool} is + * used to execute any parallel tasks. + * + * @param a the array to be sorted + * @param fromIndex the index of the first element (inclusive) to be + * sorted + * @param toIndex the index of the last element (exclusive) to be sorted + * @throws IllegalArgumentException if {@code fromIndex > toIndex} or + * (optional) if the natural ordering of the array elements is + * found to violate the {@link Comparable} contract + * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or + * {@code toIndex > a.length} + * @throws ClassCastException if the array contains elements that are + * not <i>mutually comparable</i> (for example, strings and + * integers). + * + * @since 1.8 + */ + @SuppressWarnings("unchecked") + public static <T extends Comparable<? super T>> + void parallelSort(T[] a, int fromIndex, int toIndex) { + rangeCheck(a.length, fromIndex, toIndex); + int n = toIndex - fromIndex, p, g; + if (n <= MIN_ARRAY_SORT_GRAN || + (p = ForkJoinPool.getCommonPoolParallelism()) == 1) + TimSort.sort(a, fromIndex, toIndex, NaturalOrder.INSTANCE, null, 0, 0); + else + new ArraysParallelSortHelpers.FJObject.Sorter<T> + (null, a, + (T[])Array.newInstance(a.getClass().getComponentType(), n), + fromIndex, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? + MIN_ARRAY_SORT_GRAN : g, NaturalOrder.INSTANCE).invoke(); + } + + /** + * Sorts the specified array of objects according to the order induced by + * the specified comparator. All elements in the array must be + * <i>mutually comparable</i> by the specified comparator (that is, + * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException} + * for any elements {@code e1} and {@code e2} in the array). + * + * <p>This sort is guaranteed to be <i>stable</i>: equal elements will + * not be reordered as a result of the sort. + * + * @implNote The sorting algorithm is a parallel sort-merge that breaks the + * array into sub-arrays that are themselves sorted and then merged. When + * the sub-array length reaches a minimum granularity, the sub-array is + * sorted using the appropriate {@link Arrays#sort(Object[]) Arrays.sort} + * method. If the length of the specified array is less than the minimum + * granularity, then it is sorted using the appropriate {@link + * Arrays#sort(Object[]) Arrays.sort} method. The algorithm requires a + * working space no greater than the size of the original array. The + * {@link ForkJoinPool#commonPool() ForkJoin common pool} is used to + * execute any parallel tasks. + * + * @param a the array to be sorted + * @param cmp the comparator to determine the order of the array. A + * {@code null} value indicates that the elements' + * {@linkplain Comparable natural ordering} should be used. + * @throws ClassCastException if the array contains elements that are + * not <i>mutually comparable</i> using the specified comparator + * @throws IllegalArgumentException (optional) if the comparator is + * found to violate the {@link java.util.Comparator} contract + * + * @since 1.8 + */ + @SuppressWarnings("unchecked") + public static <T> void parallelSort(T[] a, Comparator<? super T> cmp) { + if (cmp == null) + cmp = NaturalOrder.INSTANCE; + int n = a.length, p, g; + if (n <= MIN_ARRAY_SORT_GRAN || + (p = ForkJoinPool.getCommonPoolParallelism()) == 1) + TimSort.sort(a, 0, n, cmp, null, 0, 0); + else + new ArraysParallelSortHelpers.FJObject.Sorter<T> + (null, a, + (T[])Array.newInstance(a.getClass().getComponentType(), n), + 0, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? + MIN_ARRAY_SORT_GRAN : g, cmp).invoke(); + } + + /** + * Sorts the specified range of the specified array of objects according + * to the order induced by the specified comparator. The range to be + * sorted extends from index {@code fromIndex}, inclusive, to index + * {@code toIndex}, exclusive. (If {@code fromIndex==toIndex}, the + * range to be sorted is empty.) All elements in the range must be + * <i>mutually comparable</i> by the specified comparator (that is, + * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException} + * for any elements {@code e1} and {@code e2} in the range). + * + * <p>This sort is guaranteed to be <i>stable</i>: equal elements will + * not be reordered as a result of the sort. + * + * @implNote The sorting algorithm is a parallel sort-merge that breaks the + * array into sub-arrays that are themselves sorted and then merged. When + * the sub-array length reaches a minimum granularity, the sub-array is + * sorted using the appropriate {@link Arrays#sort(Object[]) Arrays.sort} + * method. If the length of the specified array is less than the minimum + * granularity, then it is sorted using the appropriate {@link + * Arrays#sort(Object[]) Arrays.sort} method. The algorithm requires a working + * space no greater than the size of the specified range of the original + * array. The {@link ForkJoinPool#commonPool() ForkJoin common pool} is + * used to execute any parallel tasks. + * + * @param a the array to be sorted + * @param fromIndex the index of the first element (inclusive) to be + * sorted + * @param toIndex the index of the last element (exclusive) to be sorted + * @param cmp the comparator to determine the order of the array. A + * {@code null} value indicates that the elements' + * {@linkplain Comparable natural ordering} should be used. + * @throws IllegalArgumentException if {@code fromIndex > toIndex} or + * (optional) if the natural ordering of the array elements is + * found to violate the {@link Comparable} contract + * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or + * {@code toIndex > a.length} + * @throws ClassCastException if the array contains elements that are + * not <i>mutually comparable</i> (for example, strings and + * integers). + * + * @since 1.8 + */ + @SuppressWarnings("unchecked") + public static <T> void parallelSort(T[] a, int fromIndex, int toIndex, + Comparator<? super T> cmp) { + rangeCheck(a.length, fromIndex, toIndex); + if (cmp == null) + cmp = NaturalOrder.INSTANCE; + int n = toIndex - fromIndex, p, g; + if (n <= MIN_ARRAY_SORT_GRAN || + (p = ForkJoinPool.getCommonPoolParallelism()) == 1) + TimSort.sort(a, fromIndex, toIndex, cmp, null, 0, 0); + else + new ArraysParallelSortHelpers.FJObject.Sorter<T> + (null, a, + (T[])Array.newInstance(a.getClass().getComponentType(), n), + fromIndex, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? + MIN_ARRAY_SORT_GRAN : g, cmp).invoke(); } /* @@ -412,39 +1191,6 @@ "java.util.Arrays.useLegacyMergeSort")).booleanValue(); } - /* - * If this platform has an optimizing VM, check whether ComparableTimSort - * offers any performance benefit over TimSort in conjunction with a - * comparator that returns: - * {@code ((Comparable)first).compareTo(Second)}. - * If not, you are better off deleting ComparableTimSort to - * eliminate the code duplication. In other words, the commented - * out code below is the preferable implementation for sorting - * arrays of Comparables if it offers sufficient performance. - */ - -// /** -// * A comparator that implements the natural ordering of a group of -// * mutually comparable elements. Using this comparator saves us -// * from duplicating most of the code in this file (one version for -// * Comparables, one for explicit Comparators). -// */ -// private static final Comparator<Object> NATURAL_ORDER = -// new Comparator<Object>() { -// @SuppressWarnings("unchecked") -// public int compare(Object first, Object second) { -// return ((Comparable<Object>)first).compareTo(second); -// } -// }; -// -// public static void sort(Object[] a) { -// sort(a, 0, a.length, NATURAL_ORDER); -// } -// -// public static void sort(Object[] a, int fromIndex, int toIndex) { -// sort(a, fromIndex, toIndex, NATURAL_ORDER); -// } - /** * Sorts the specified array of objects into ascending order, according * to the {@linkplain Comparable natural ordering} of its elements. @@ -491,7 +1237,7 @@ if (LegacyMergeSort.userRequested) legacyMergeSort(a); else - ComparableTimSort.sort(a); + ComparableTimSort.sort(a, 0, a.length, null, 0, 0); } /** To be removed in a future release. */ @@ -553,16 +1299,16 @@ * integers). */ public static void sort(Object[] a, int fromIndex, int toIndex) { + rangeCheck(a.length, fromIndex, toIndex); if (LegacyMergeSort.userRequested) legacyMergeSort(a, fromIndex, toIndex); else - ComparableTimSort.sort(a, fromIndex, toIndex); + ComparableTimSort.sort(a, fromIndex, toIndex, null, 0, 0); } /** To be removed in a future release. */ private static void legacyMergeSort(Object[] a, int fromIndex, int toIndex) { - rangeCheck(a.length, fromIndex, toIndex); Object[] aux = copyOfRange(a, fromIndex, toIndex); mergeSort(aux, a, fromIndex, toIndex, -fromIndex); } @@ -676,10 +1422,12 @@ * found to violate the {@link Comparator} contract */ public static <T> void sort(T[] a, Comparator<? super T> c) { + if (c == null) + c = NaturalOrder.INSTANCE; if (LegacyMergeSort.userRequested) legacyMergeSort(a, c); else - TimSort.sort(a, c); + TimSort.sort(a, 0, a.length, c, null, 0, 0); } /** To be removed in a future release. */ @@ -744,16 +1492,18 @@ */ public static <T> void sort(T[] a, int fromIndex, int toIndex, Comparator<? super T> c) { + if (c == null) + c = NaturalOrder.INSTANCE; + rangeCheck(a.length, fromIndex, toIndex); if (LegacyMergeSort.userRequested) legacyMergeSort(a, fromIndex, toIndex, c); else - TimSort.sort(a, fromIndex, toIndex, c); + TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0); } /** To be removed in a future release. */ private static <T> void legacyMergeSort(T[] a, int fromIndex, int toIndex, Comparator<? super T> c) { - rangeCheck(a.length, fromIndex, toIndex); T[] aux = copyOfRange(a, fromIndex, toIndex); if (c==null) mergeSort(aux, a, fromIndex, toIndex, -fromIndex); @@ -809,630 +1559,6 @@ } } - /* - * Parallel sorting of primitive type arrays. - */ - - /** - * Sorts the specified array into ascending numerical order. - * - * <p>Implementation note: The sorting algorithm is a parallel sort-merge - * that breaks the array into sub-arrays that are themselves sorted and then - * merged. When the sub-array length reaches a minimum granularity, the - * sub-array is sorted using the appropriate {@link Arrays#sort(byte[]) - * Arrays.sort} method. The algorithm requires a working space equal to the - * size of the original array. The {@link - * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is - * used to execute any parallel tasks. - * - * @param a the array to be sorted - * - * @since 1.8 - */ - public static void parallelSort(byte[] a) { - parallelSort(a, 0, a.length); - } - - /** - * Sorts the specified range of the array into ascending order. The range - * to be sorted extends from the index {@code fromIndex}, inclusive, to - * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex}, - * the range to be sorted is empty. - * - * <p>Implementation note: The sorting algorithm is a parallel sort-merge - * that breaks the array into sub-arrays that are themselves sorted and then - * merged. When the sub-array length reaches a minimum granularity, the - * sub-array is sorted using the appropriate {@link Arrays#sort(byte[]) - * Arrays.sort} method. The algorithm requires a working space equal to the - * size of the original array. The {@link - * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is - * used to execute any parallel tasks. - * - * @param a the array to be sorted - * @param fromIndex the index of the first element, inclusive, to be sorted - * @param toIndex the index of the last element, exclusive, to be sorted - * - * @throws IllegalArgumentException if {@code fromIndex > toIndex} - * @throws ArrayIndexOutOfBoundsException - * if {@code fromIndex < 0} or {@code toIndex > a.length} - * - * @since 1.8 - */ - public static void parallelSort(byte[] a, int fromIndex, int toIndex) { - rangeCheck(a.length, fromIndex, toIndex); - int nelements = toIndex - fromIndex; - int gran = getSplitThreshold(nelements); - FJByte.Sorter task = new FJByte.Sorter(a, new byte[a.length], fromIndex, - nelements, gran); - task.invoke(); - } - - /** - * Sorts the specified array into ascending numerical order. - * - * <p>Implementation note: The sorting algorithm is a parallel sort-merge - * that breaks the array into sub-arrays that are themselves sorted and then - * merged. When the sub-array length reaches a minimum granularity, the - * sub-array is sorted using the appropriate {@link Arrays#sort(char[]) - * Arrays.sort} method. The algorithm requires a working space equal to the - * size of the original array. The {@link - * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is - * used to execute any parallel tasks. - * - * @param a the array to be sorted - * - * @since 1.8 - */ - public static void parallelSort(char[] a) { - parallelSort(a, 0, a.length); - } - - /** - * Sorts the specified range of the array into ascending order. The range - * to be sorted extends from the index {@code fromIndex}, inclusive, to - * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex}, - * the range to be sorted is empty. - * - * <p>Implementation note: The sorting algorithm is a parallel sort-merge - * that breaks the array into sub-arrays that are themselves sorted and then - * merged. When the sub-array length reaches a minimum granularity, the - * sub-array is sorted using the appropriate {@link Arrays#sort(char[]) - * Arrays.sort} method. The algorithm requires a working space equal to the - * size of the original array. The {@link - * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is - * used to execute any parallel tasks. - * - * @param a the array to be sorted - * @param fromIndex the index of the first element, inclusive, to be sorted - * @param toIndex the index of the last element, exclusive, to be sorted - * - * @throws IllegalArgumentException if {@code fromIndex > toIndex} - * @throws ArrayIndexOutOfBoundsException - * if {@code fromIndex < 0} or {@code toIndex > a.length} - * - * @since 1.8 - */ - public static void parallelSort(char[] a, int fromIndex, int toIndex) { - rangeCheck(a.length, fromIndex, toIndex); - int nelements = toIndex - fromIndex; - int gran = getSplitThreshold(nelements); - FJChar.Sorter task = new FJChar.Sorter(a, new char[a.length], fromIndex, - nelements, gran); - task.invoke(); - } - - /** - * Sorts the specified array into ascending numerical order. - * - * <p>Implementation note: The sorting algorithm is a parallel sort-merge - * that breaks the array into sub-arrays that are themselves sorted and then - * merged. When the sub-array length reaches a minimum granularity, the - * sub-array is sorted using the appropriate {@link Arrays#sort(short[]) - * Arrays.sort} method. The algorithm requires a working space equal to the - * size of the original array. The {@link - * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is - * used to execute any parallel tasks. - * - * @param a the array to be sorted - * - * @since 1.8 - */ - public static void parallelSort(short[] a) { - parallelSort(a, 0, a.length); - } - - /** - * Sorts the specified range of the array into ascending order. The range - * to be sorted extends from the index {@code fromIndex}, inclusive, to - * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex}, - * the range to be sorted is empty. - * - * <p>Implementation note: The sorting algorithm is a parallel sort-merge - * that breaks the array into sub-arrays that are themselves sorted and then - * merged. When the sub-array length reaches a minimum granularity, the - * sub-array is sorted using the appropriate {@link Arrays#sort(short[]) - * Arrays.sort} method. The algorithm requires a working space equal to the - * size of the original array. The {@link - * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is - * used to execute any parallel tasks. - * - * @param a the array to be sorted - * @param fromIndex the index of the first element, inclusive, to be sorted - * @param toIndex the index of the last element, exclusive, to be sorted - * - * @throws IllegalArgumentException if {@code fromIndex > toIndex} - * @throws ArrayIndexOutOfBoundsException - * if {@code fromIndex < 0} or {@code toIndex > a.length} - * - * @since 1.8 - */ - public static void parallelSort(short[] a, int fromIndex, int toIndex) { - rangeCheck(a.length, fromIndex, toIndex); - int nelements = toIndex - fromIndex; - int gran = getSplitThreshold(nelements); - FJShort.Sorter task = new FJShort.Sorter(a, new short[a.length], fromIndex, - nelements, gran); - task.invoke(); - } - - /** - * Sorts the specified array into ascending numerical order. - * - * <p>Implementation note: The sorting algorithm is a parallel sort-merge - * that breaks the array into sub-arrays that are themselves sorted and then - * merged. When the sub-array length reaches a minimum granularity, the - * sub-array is sorted using the appropriate {@link Arrays#sort(int[]) - * Arrays.sort} method. The algorithm requires a working space equal to the - * size of the original array. The {@link - * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is - * used to execute any parallel tasks. - * - * @param a the array to be sorted - * - * @since 1.8 - */ - public static void parallelSort(int[] a) { - parallelSort(a, 0, a.length); - } - - /** - * Sorts the specified range of the array into ascending order. The range - * to be sorted extends from the index {@code fromIndex}, inclusive, to - * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex}, - * the range to be sorted is empty. - * - * <p>Implementation note: The sorting algorithm is a parallel sort-merge - * that breaks the array into sub-arrays that are themselves sorted and then - * merged. When the sub-array length reaches a minimum granularity, the - * sub-array is sorted using the appropriate {@link Arrays#sort(int[]) - * Arrays.sort} method. The algorithm requires a working space equal to the - * size of the original array. The {@link - * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is - * used to execute any parallel tasks. - * - * @param a the array to be sorted - * @param fromIndex the index of the first element, inclusive, to be sorted - * @param toIndex the index of the last element, exclusive, to be sorted - * - * @throws IllegalArgumentException if {@code fromIndex > toIndex} - * @throws ArrayIndexOutOfBoundsException - * if {@code fromIndex < 0} or {@code toIndex > a.length} - * - * @since 1.8 - */ - public static void parallelSort(int[] a, int fromIndex, int toIndex) { - rangeCheck(a.length, fromIndex, toIndex); - int nelements = toIndex - fromIndex; - int gran = getSplitThreshold(nelements); - FJInt.Sorter task = new FJInt.Sorter(a, new int[a.length], fromIndex, - nelements, gran); - task.invoke(); - } - - /** - * Sorts the specified array into ascending numerical order. - * - * <p>Implementation note: The sorting algorithm is a parallel sort-merge - * that breaks the array into sub-arrays that are themselves sorted and then - * merged. When the sub-array length reaches a minimum granularity, the - * sub-array is sorted using the appropriate {@link Arrays#sort(long[]) - * Arrays.sort} method. The algorithm requires a working space equal to the - * size of the original array. The {@link - * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is - * used to execute any parallel tasks. - * - * @param a the array to be sorted - * - * @since 1.8 - */ - public static void parallelSort(long[] a) { - parallelSort(a, 0, a.length); - } - - /** - * Sorts the specified range of the array into ascending order. The range - * to be sorted extends from the index {@code fromIndex}, inclusive, to - * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex}, - * the range to be sorted is empty. - * - * <p>Implementation note: The sorting algorithm is a parallel sort-merge - * that breaks the array into sub-arrays that are themselves sorted and then - * merged. When the sub-array length reaches a minimum granularity, the - * sub-array is sorted using the appropriate {@link Arrays#sort(long[]) - * Arrays.sort} method. The algorithm requires a working space equal to the - * size of the original array. The {@link - * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is - * used to execute any parallel tasks. - * - * @param a the array to be sorted - * @param fromIndex the index of the first element, inclusive, to be sorted - * @param toIndex the index of the last element, exclusive, to be sorted - * - * @throws IllegalArgumentException if {@code fromIndex > toIndex} - * @throws ArrayIndexOutOfBoundsException - * if {@code fromIndex < 0} or {@code toIndex > a.length} - * - * @since 1.8 - */ - public static void parallelSort(long[] a, int fromIndex, int toIndex) { - rangeCheck(a.length, fromIndex, toIndex); - int nelements = toIndex - fromIndex; - int gran = getSplitThreshold(nelements); - FJLong.Sorter task = new FJLong.Sorter(a, new long[a.length], fromIndex, - nelements, gran); - task.invoke(); - } - - /** - * Sorts the specified array into ascending numerical order. - * - * <p>The {@code <} relation does not provide a total order on all float - * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN} - * value compares neither less than, greater than, nor equal to any value, - * even itself. This method uses the total order imposed by the method - * {@link Float#compareTo}: {@code -0.0f} is treated as less than value - * {@code 0.0f} and {@code Float.NaN} is considered greater than any - * other value and all {@code Float.NaN} values are considered equal. - * - * <p>Implementation note: The sorting algorithm is a parallel sort-merge - * that breaks the array into sub-arrays that are themselves sorted and then - * merged. When the sub-array length reaches a minimum granularity, the - * sub-array is sorted using the appropriate {@link Arrays#sort(float[]) - * Arrays.sort} method. The algorithm requires a working space equal to the - * size of the original array. The {@link - * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is - * used to execute any parallel tasks. - * - * @param a the array to be sorted - * - * @since 1.8 - */ - public static void parallelSort(float[] a) { - parallelSort(a, 0, a.length); - } - - /** - * Sorts the specified range of the array into ascending order. The range - * to be sorted extends from the index {@code fromIndex}, inclusive, to - * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex}, - * the range to be sorted is empty. - * - * <p>The {@code <} relation does not provide a total order on all float - * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN} - * value compares neither less than, greater than, nor equal to any value, - * even itself. This method uses the total order imposed by the method - * {@link Float#compareTo}: {@code -0.0f} is treated as less than value - * {@code 0.0f} and {@code Float.NaN} is considered greater than any - * other value and all {@code Float.NaN} values are considered equal. - * - * <p>Implementation note: The sorting algorithm is a parallel sort-merge - * that breaks the array into sub-arrays that are themselves sorted and then - * merged. When the sub-array length reaches a minimum granularity, the - * sub-array is sorted using the appropriate {@link Arrays#sort(float[]) - * Arrays.sort} method. The algorithm requires a working space equal to the - * size of the original array. The {@link - * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is - * used to execute any parallel tasks. - * - * @param a the array to be sorted - * @param fromIndex the index of the first element, inclusive, to be sorted - * @param toIndex the index of the last element, exclusive, to be sorted - * - * @throws IllegalArgumentException if {@code fromIndex > toIndex} - * @throws ArrayIndexOutOfBoundsException - * if {@code fromIndex < 0} or {@code toIndex > a.length} - * - * @since 1.8 - */ - public static void parallelSort(float[] a, int fromIndex, int toIndex) { - rangeCheck(a.length, fromIndex, toIndex); - int nelements = toIndex - fromIndex; - int gran = getSplitThreshold(nelements); - FJFloat.Sorter task = new FJFloat.Sorter(a, new float[a.length], fromIndex, - nelements, gran); - task.invoke(); - } - - /** - * Sorts the specified array into ascending numerical order. - * - * <p>The {@code <} relation does not provide a total order on all double - * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN} - * value compares neither less than, greater than, nor equal to any value, - * even itself. This method uses the total order imposed by the method - * {@link Double#compareTo}: {@code -0.0d} is treated as less than value - * {@code 0.0d} and {@code Double.NaN} is considered greater than any - * other value and all {@code Double.NaN} values are considered equal. - * - * <p>Implementation note: The sorting algorithm is a parallel sort-merge - * that breaks the array into sub-arrays that are themselves sorted and then - * merged. When the sub-array length reaches a minimum granularity, the - * sub-array is sorted using the appropriate {@link Arrays#sort(double[]) - * Arrays.sort} method. The algorithm requires a working space equal to the - * size of the original array. The {@link - * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is - * used to execute any parallel tasks. - * - * @param a the array to be sorted - * - * @since 1.8 - */ - public static void parallelSort(double[] a) { - parallelSort(a, 0, a.length); - } - - /** - * Sorts the specified range of the array into ascending order. The range - * to be sorted extends from the index {@code fromIndex}, inclusive, to - * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex}, - * the range to be sorted is empty. - * - * <p>The {@code <} relation does not provide a total order on all double - * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN} - * value compares neither less than, greater than, nor equal to any value, - * even itself. This method uses the total order imposed by the method - * {@link Double#compareTo}: {@code -0.0d} is treated as less than value - * {@code 0.0d} and {@code Double.NaN} is considered greater than any - * other value and all {@code Double.NaN} values are considered equal. - * - * <p>Implementation note: The sorting algorithm is a parallel sort-merge - * that breaks the array into sub-arrays that are themselves sorted and then - * merged. When the sub-array length reaches a minimum granularity, the - * sub-array is sorted using the appropriate {@link Arrays#sort(double[]) - * Arrays.sort} method. The algorithm requires a working space equal to the - * size of the original array. The {@link - * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is - * used to execute any parallel tasks. - * - * @param a the array to be sorted - * @param fromIndex the index of the first element, inclusive, to be sorted - * @param toIndex the index of the last element, exclusive, to be sorted - * - * @throws IllegalArgumentException if {@code fromIndex > toIndex} - * @throws ArrayIndexOutOfBoundsException - * if {@code fromIndex < 0} or {@code toIndex > a.length} - * - * @since 1.8 - */ - public static void parallelSort(double[] a, int fromIndex, int toIndex) { - rangeCheck(a.length, fromIndex, toIndex); - int nelements = toIndex - fromIndex; - int gran = getSplitThreshold(nelements); - FJDouble.Sorter task = new FJDouble.Sorter(a, new double[a.length], - fromIndex, nelements, gran); - task.invoke(); - } - - /* - * Parallel sorting of complex type arrays. - */ - - /** - * Sorts the specified array of objects into ascending order, according - * to the {@linkplain Comparable natural ordering} of its elements. - * All elements in the array must implement the {@link Comparable} - * interface. Furthermore, all elements in the array must be - * <i>mutually comparable</i> (that is, {@code e1.compareTo(e2)} must - * not throw a {@code ClassCastException} for any elements {@code e1} - * and {@code e2} in the array). - * - * <p>This sort is not guaranteed to be <i>stable</i>: equal elements - * may be reordered as a result of the sort. - * - * <p>Implementation note: The sorting algorithm is a parallel sort-merge - * that breaks the array into sub-arrays that are themselves sorted and then - * merged. When the sub-array length reaches a minimum granularity, the - * sub-array is sorted using the appropriate {@link Arrays#sort(Object[]) - * Arrays.sort} method. The algorithm requires a working space equal to the - * size of the original array. The {@link - * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is - * used to execute any parallel tasks. - * - * @param a the array to be sorted - * - * @throws ClassCastException if the array contains elements that are not - * <i>mutually comparable</i> (for example, strings and integers) - * @throws IllegalArgumentException (optional) if the natural - * ordering of the array elements is found to violate the - * {@link Comparable} contract - * - * @since 1.8 - */ - public static <T extends Comparable<? super T>> void parallelSort(T[] a) { - parallelSort(a, 0, a.length); - } - - /** - * Sorts the specified range of the specified array of objects into - * ascending order, according to the - * {@linkplain Comparable natural ordering} of its - * elements. The range to be sorted extends from index - * {@code fromIndex}, inclusive, to index {@code toIndex}, exclusive. - * (If {@code fromIndex==toIndex}, the range to be sorted is empty.) All - * elements in this range must implement the {@link Comparable} - * interface. Furthermore, all elements in this range must be <i>mutually - * comparable</i> (that is, {@code e1.compareTo(e2)} must not throw a - * {@code ClassCastException} for any elements {@code e1} and - * {@code e2} in the array). - * - * <p>This sort is not guaranteed to be <i>stable</i>: equal elements - * may be reordered as a result of the sort. - * - * <p>Implementation note: The sorting algorithm is a parallel sort-merge - * that breaks the array into sub-arrays that are themselves sorted and then - * merged. When the sub-array length reaches a minimum granularity, the - * sub-array is sorted using the appropriate {@link Arrays#sort(Object[]) - * Arrays.sort} method. The algorithm requires a working space equal to the - * size of the original array. The {@link - * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is - * used to execute any parallel tasks. - * - * @param a the array to be sorted - * @param fromIndex the index of the first element (inclusive) to be - * sorted - * @param toIndex the index of the last element (exclusive) to be sorted - * @throws IllegalArgumentException if {@code fromIndex > toIndex} or - * (optional) if the natural ordering of the array elements is - * found to violate the {@link Comparable} contract - * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or - * {@code toIndex > a.length} - * @throws ClassCastException if the array contains elements that are - * not <i>mutually comparable</i> (for example, strings and - * integers). - * - * @since 1.8 - */ - public static <T extends Comparable<? super T>> - void parallelSort(T[] a, int fromIndex, int toIndex) { - rangeCheck(a.length, fromIndex, toIndex); - int nelements = toIndex - fromIndex; - Class<?> tc = a.getClass().getComponentType(); - @SuppressWarnings("unchecked") - T[] workspace = (T[])Array.newInstance(tc, a.length); - int gran = getSplitThreshold(nelements); - FJComparable.Sorter<T> task = new FJComparable.Sorter<>(a, workspace, - fromIndex, - nelements, gran); - task.invoke(); - } - - /** - * Sorts the specified array of objects according to the order induced by - * the specified comparator. All elements in the array must be - * <i>mutually comparable</i> by the specified comparator (that is, - * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException} - * for any elements {@code e1} and {@code e2} in the array). - * - * <p>This sort is not guaranteed to be <i>stable</i>: equal elements - * may be reordered as a result of the sort. - * - * <p>Implementation note: The sorting algorithm is a parallel sort-merge - * that breaks the array into sub-arrays that are themselves sorted and then - * merged. When the sub-array length reaches a minimum granularity, the - * sub-array is sorted using the appropriate {@link Arrays#sort(Object[]) - * Arrays.sort} method. The algorithm requires a working space equal to the - * size of the original array. The {@link - * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is - * used to execute any parallel tasks. - * - * @param a the array to be sorted - * @param c the comparator to determine the order of the array. A - * {@code null} value indicates that the elements' - * {@linkplain Comparable natural ordering} should be used. - * @throws ClassCastException if the array contains elements that are - * not <i>mutually comparable</i> using the specified comparator - * @throws IllegalArgumentException (optional) if the comparator is - * found to violate the {@link java.util.Comparator} contract - * - * @since 1.8 - */ - public static <T> void parallelSort(T[] a, Comparator<? super T> c) { - parallelSort(a, 0, a.length, c); - } - - /** - * Sorts the specified range of the specified array of objects according - * to the order induced by the specified comparator. The range to be - * sorted extends from index {@code fromIndex}, inclusive, to index - * {@code toIndex}, exclusive. (If {@code fromIndex==toIndex}, the - * range to be sorted is empty.) All elements in the range must be - * <i>mutually comparable</i> by the specified comparator (that is, - * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException} - * for any elements {@code e1} and {@code e2} in the range). - * - * <p>This sort is not guaranteed to be <i>stable</i>: equal elements - * may be reordered as a result of the sort. - * - * <p>Implementation note: The sorting algorithm is a parallel sort-merge - * that breaks the array into sub-arrays that are themselves sorted and then - * merged. When the sub-array length reaches a minimum granularity, the - * sub-array is sorted using the appropriate {@link Arrays#sort(Object[]) - * Arrays.sort} method. The algorithm requires a working space equal to the - * size of the original array. The {@link - * java.util.concurrent.ForkJoinPool#commonPool() ForkJoin common pool} is - * used to execute any parallel tasks. - * - * @param a the array to be sorted - * @param fromIndex the index of the first element (inclusive) to be - * sorted - * @param toIndex the index of the last element (exclusive) to be sorted - * @param c the comparator to determine the order of the array. A - * {@code null} value indicates that the elements' - * {@linkplain Comparable natural ordering} should be used. - * @throws IllegalArgumentException if {@code fromIndex > toIndex} or - * (optional) if the natural ordering of the array elements is - * found to violate the {@link Comparable} contract - * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or - * {@code toIndex > a.length} - * @throws ClassCastException if the array contains elements that are - * not <i>mutually comparable</i> (for example, strings and - * integers). - * - * @since 1.8 - */ - public static <T> void parallelSort(T[] a, int fromIndex, int toIndex, - Comparator<? super T> c) { - rangeCheck(a.length, fromIndex, toIndex); - int nelements = toIndex - fromIndex; - Class<?> tc = a.getClass().getComponentType(); - @SuppressWarnings("unchecked") - T[] workspace = (T[])Array.newInstance(tc, a.length); - int gran = getSplitThreshold(nelements); - FJComparator.Sorter<T> task = new FJComparator.Sorter<>(a, workspace, - fromIndex, - nelements, gran, c); - task.invoke(); - } - - /** - * Returns the size threshold for splitting into subtasks. - * By default, uses about 8 times as many tasks as threads - * - * @param n number of elements in the array to be processed - */ - private static int getSplitThreshold(int n) { - int p = java.util.concurrent.ForkJoinPool.getCommonPoolParallelism(); - int t = (p > 1) ? (1 + n / (p << 3)) : n; - return t < MIN_ARRAY_SORT_GRAN ? MIN_ARRAY_SORT_GRAN : t; - } - - /** - * Checks that {@code fromIndex} and {@code toIndex} are in - * the range and throws an appropriate exception, if they aren't. - */ - private static void rangeCheck(int length, int fromIndex, int toIndex) { - if (fromIndex > toIndex) { - throw new IllegalArgumentException( - "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")"); - } - if (fromIndex < 0) { - throw new ArrayIndexOutOfBoundsException(fromIndex); - } - if (toIndex > length) { - throw new ArrayIndexOutOfBoundsException(toIndex); - } - } - // Searching /**
--- a/src/share/classes/java/util/ArraysParallelSortHelpers.java Thu May 23 09:48:44 2013 -0300 +++ b/src/share/classes/java/util/ArraysParallelSortHelpers.java Wed May 29 13:22:58 2013 -0300 @@ -25,6 +25,7 @@ package java.util; import java.util.concurrent.RecursiveAction; +import java.util.concurrent.CountedCompleter; /** * Helper utilities for the parallel sort methods in Arrays.parallelSort. @@ -44,1180 +45,966 @@ * c. merge them together * 3. merge together the two halves. * - * One reason for splitting in quarters is that this guarantees - * that the final sort is in the main array, not the workspace - * array. (workspace and main swap roles on each subsort step.) - * Leaf-level sorts use a Sequential quicksort, that in turn uses - * insertion sort if under threshold. Otherwise it uses median of - * three to pick pivot, and loops rather than recurses along left - * path. - * + * One reason for splitting in quarters is that this guarantees that + * the final sort is in the main array, not the workspace array. + * (workspace and main swap roles on each subsort step.) Leaf-level + * sorts use the associated sequential sort. * - * Merger classes perform merging for Sorter. If big enough, splits Left - * partition in half; finds the greatest point in Right partition - * less than the beginning of the second half of Left via binary - * search; and then, in parallel, merges left half of Left with - * elements of Right up to split point, and merges right half of - * Left with elements of R past split point. At leaf, it just - * sequentially merges. This is all messy to code; sadly we need - * distinct versions for each type. + * Merger classes perform merging for Sorter. They are structured + * such that if the underlying sort is stable (as is true for + * TimSort), then so is the full sort. If big enough, they split the + * largest of the two partitions in half, find the greatest point in + * smaller partition less than the beginning of the second half of + * larger via binary search; and then merge in parallel the two + * partitions. In part to ensure tasks are triggered in + * stability-preserving order, the current CountedCompleter design + * requires some little tasks to serve as place holders for triggering + * completion tasks. These classes (EmptyCompleter and Relay) don't + * need to keep track of the arrays, and are never themselves forked, + * so don't hold any task state. * + * The primitive class versions (FJByte... FJDouble) are + * identical to each other except for type declarations. + * + * The base sequential sorts rely on non-public versions of TimSort, + * ComparableTimSort, and DualPivotQuicksort sort methods that accept + * temp workspace array slices that we will have already allocated, so + * avoids redundant allocation. (Except for DualPivotQuicksort byte[] + * sort, that does not ever use a workspace array.) */ /*package*/ class ArraysParallelSortHelpers { - // RFE: we should only need a working array as large as the subarray - // to be sorted, but the logic assumes that indices in the two - // arrays always line-up + /* + * Style note: The task classes have a lot of parameters, that are + * stored as task fields and copied to local variables and used in + * compute() methods, We pack these into as few lines as possible, + * and hoist consistency checks among them before main loops, to + * reduce distraction. + */ - /** byte support class */ - static final class FJByte { - static final class Sorter extends RecursiveAction { - static final long serialVersionUID = 749471161188027634L; - final byte[] a; // array to be sorted. - final byte[] w; // workspace for merge - final int origin; // origin of the part of array we deal with - final int n; // Number of elements in (sub)arrays. - final int gran; // split control + /** + * A placeholder task for Sorters, used for the lowest + * quartile task, that does not need to maintain array state. + */ + static final class EmptyCompleter extends CountedCompleter<Void> { + static final long serialVersionUID = 2446542900576103244L; + EmptyCompleter(CountedCompleter<?> p) { super(p); } + public final void compute() { } + } - Sorter(byte[] a, byte[] w, int origin, int n, int gran) { - this.a = a; - this.w = w; - this.origin = origin; - this.n = n; - this.gran = gran; - } + /** + * A trigger for secondary merge of two merges + */ + static final class Relay extends CountedCompleter<Void> { + static final long serialVersionUID = 2446542900576103244L; + final CountedCompleter<?> task; + Relay(CountedCompleter<?> task) { + super(null, 1); + this.task = task; + } + public final void compute() { } + public final void onCompletion(CountedCompleter<?> t) { + task.compute(); + } + } - public void compute() { - final int l = origin; - final int g = gran; - final int n = this.n; - final byte[] a = this.a; - final byte[] w = this.w; - if (n > g) { - int h = n >>> 1; // half - int q = n >>> 2; // lower quarter index - int u = h + q; // upper quarter - FJSubSorter ls = new FJSubSorter(new Sorter(a, w, l, q, g), - new Sorter(a, w, l+q, h-q, g), - new Merger(a, w, l, q, - l+q, h-q, l, g, null)); - FJSubSorter rs = new FJSubSorter(new Sorter(a, w, l+h, q, g), - new Sorter(a, w, l+u, n-u, g), - new Merger(a, w, l+h, q, - l+u, n-u, l+h, g, null)); - rs.fork(); - ls.compute(); - if (rs.tryUnfork()) rs.compute(); else rs.join(); - new Merger(w, a, l, h, - l+h, n-h, l, g, null).compute(); - } else { - DualPivotQuicksort.sort(a, l, l+n-1); //skip rangeCheck + /** Object + Comparator support class */ + static final class FJObject { + static final class Sorter<T> extends CountedCompleter<Void> { + static final long serialVersionUID = 2446542900576103244L; + final T[] a, w; + final int base, size, wbase, gran; + Comparator<? super T> comparator; + Sorter(CountedCompleter<?> par, T[] a, T[] w, int base, int size, + int wbase, int gran, + Comparator<? super T> comparator) { + super(par); + this.a = a; this.w = w; this.base = base; this.size = size; + this.wbase = wbase; this.gran = gran; + this.comparator = comparator; + } + public final void compute() { + CountedCompleter<?> s = this; + Comparator<? super T> c = this.comparator; + T[] a = this.a, w = this.w; // localize all params + int b = this.base, n = this.size, wb = this.wbase, g = this.gran; + while (n > g) { + int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles + Relay fc = new Relay(new Merger<T>(s, w, a, wb, h, + wb+h, n-h, b, g, c)); + Relay rc = new Relay(new Merger<T>(fc, a, w, b+h, q, + b+u, n-u, wb+h, g, c)); + new Sorter<T>(rc, a, w, b+u, n-u, wb+u, g, c).fork(); + new Sorter<T>(rc, a, w, b+h, q, wb+h, g, c).fork();; + Relay bc = new Relay(new Merger<T>(fc, a, w, b, q, + b+q, h-q, wb, g, c)); + new Sorter<T>(bc, a, w, b+q, h-q, wb+q, g, c).fork(); + s = new EmptyCompleter(bc); + n = q; } + TimSort.sort(a, b, b + n, c, w, wb, n); + s.tryComplete(); } } - static final class Merger extends RecursiveAction { - static final long serialVersionUID = -9090258248781844470L; - final byte[] a; - final byte[] w; - final int lo; - final int ln; - final int ro; - final int rn; - final int wo; - final int gran; - final Merger next; + static final class Merger<T> extends CountedCompleter<Void> { + static final long serialVersionUID = 2446542900576103244L; + final T[] a, w; // main and workspace arrays + final int lbase, lsize, rbase, rsize, wbase, gran; + Comparator<? super T> comparator; + Merger(CountedCompleter<?> par, T[] a, T[] w, + int lbase, int lsize, int rbase, + int rsize, int wbase, int gran, + Comparator<? super T> comparator) { + super(par); + this.a = a; this.w = w; + this.lbase = lbase; this.lsize = lsize; + this.rbase = rbase; this.rsize = rsize; + this.wbase = wbase; this.gran = gran; + this.comparator = comparator; + } - Merger(byte[] a, byte[] w, int lo, int ln, int ro, int rn, int wo, - int gran, Merger next) { - this.a = a; - this.w = w; - this.lo = lo; - this.ln = ln; - this.ro = ro; - this.rn = rn; - this.wo = wo; - this.gran = gran; - this.next = next; + public final void compute() { + Comparator<? super T> c = this.comparator; + T[] a = this.a, w = this.w; // localize all params + int lb = this.lbase, ln = this.lsize, rb = this.rbase, + rn = this.rsize, k = this.wbase, g = this.gran; + if (a == null || w == null || lb < 0 || rb < 0 || k < 0 || + c == null) + throw new IllegalStateException(); // hoist checks + for (int lh, rh;;) { // split larger, find point in smaller + if (ln >= rn) { + if (ln <= g) + break; + rh = rn; + T split = a[(lh = ln >>> 1) + lb]; + for (int lo = 0; lo < rh; ) { + int rm = (lo + rh) >>> 1; + if (c.compare(split, a[rm + rb]) <= 0) + rh = rm; + else + lo = rm + 1; + } + } + else { + if (rn <= g) + break; + lh = ln; + T split = a[(rh = rn >>> 1) + rb]; + for (int lo = 0; lo < lh; ) { + int lm = (lo + lh) >>> 1; + if (c.compare(split, a[lm + lb]) <= 0) + lh = lm; + else + lo = lm + 1; + } + } + Merger<T> m = new Merger<T>(this, a, w, lb + lh, ln - lh, + rb + rh, rn - rh, + k + lh + rh, g, c); + rn = rh; + ln = lh; + addToPendingCount(1); + m.fork(); + } + + int lf = lb + ln, rf = rb + rn; // index bounds + while (lb < lf && rb < rf) { + T t, al, ar; + if (c.compare((al = a[lb]), (ar = a[rb])) <= 0) { + lb++; t = al; + } + else { + rb++; t = ar; + } + w[k++] = t; + } + if (rb < rf) + System.arraycopy(a, rb, w, k, rf - rb); + else if (lb < lf) + System.arraycopy(a, lb, w, k, lf - lb); + + tryComplete(); } - public void compute() { - final byte[] a = this.a; - final byte[] w = this.w; - Merger rights = null; - int nleft = ln; - int nright = rn; - while (nleft > gran) { - int lh = nleft >>> 1; - int splitIndex = lo + lh; - byte split = a[splitIndex]; - int rl = 0; - int rh = nright; - while (rl < rh) { - int mid = (rl + rh) >>> 1; - if (split <= a[ro + mid]) - rh = mid; - else - rl = mid + 1; + } + } // FJObject + + /** byte support class */ + static final class FJByte { + static final class Sorter extends CountedCompleter<Void> { + static final long serialVersionUID = 2446542900576103244L; + final byte[] a, w; + final int base, size, wbase, gran; + Sorter(CountedCompleter<?> par, byte[] a, byte[] w, int base, + int size, int wbase, int gran) { + super(par); + this.a = a; this.w = w; this.base = base; this.size = size; + this.wbase = wbase; this.gran = gran; + } + public final void compute() { + CountedCompleter<?> s = this; + byte[] a = this.a, w = this.w; // localize all params + int b = this.base, n = this.size, wb = this.wbase, g = this.gran; + while (n > g) { + int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles + Relay fc = new Relay(new Merger(s, w, a, wb, h, + wb+h, n-h, b, g)); + Relay rc = new Relay(new Merger(fc, a, w, b+h, q, + b+u, n-u, wb+h, g)); + new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork(); + new Sorter(rc, a, w, b+h, q, wb+h, g).fork();; + Relay bc = new Relay(new Merger(fc, a, w, b, q, + b+q, h-q, wb, g)); + new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork(); + s = new EmptyCompleter(bc); + n = q; + } + DualPivotQuicksort.sort(a, b, b + n - 1); + s.tryComplete(); + } + } + + static final class Merger extends CountedCompleter<Void> { + static final long serialVersionUID = 2446542900576103244L; + final byte[] a, w; // main and workspace arrays + final int lbase, lsize, rbase, rsize, wbase, gran; + Merger(CountedCompleter<?> par, byte[] a, byte[] w, + int lbase, int lsize, int rbase, + int rsize, int wbase, int gran) { + super(par); + this.a = a; this.w = w; + this.lbase = lbase; this.lsize = lsize; + this.rbase = rbase; this.rsize = rsize; + this.wbase = wbase; this.gran = gran; + } + + public final void compute() { + byte[] a = this.a, w = this.w; // localize all params + int lb = this.lbase, ln = this.lsize, rb = this.rbase, + rn = this.rsize, k = this.wbase, g = this.gran; + if (a == null || w == null || lb < 0 || rb < 0 || k < 0) + throw new IllegalStateException(); // hoist checks + for (int lh, rh;;) { // split larger, find point in smaller + if (ln >= rn) { + if (ln <= g) + break; + rh = rn; + byte split = a[(lh = ln >>> 1) + lb]; + for (int lo = 0; lo < rh; ) { + int rm = (lo + rh) >>> 1; + if (split <= a[rm + rb]) + rh = rm; + else + lo = rm + 1; + } } - (rights = new Merger(a, w, splitIndex, nleft-lh, ro+rh, - nright-rh, wo+lh+rh, gran, rights)).fork(); - nleft = lh; - nright = rh; + else { + if (rn <= g) + break; + lh = ln; + byte split = a[(rh = rn >>> 1) + rb]; + for (int lo = 0; lo < lh; ) { + int lm = (lo + lh) >>> 1; + if (split <= a[lm + lb]) + lh = lm; + else + lo = lm + 1; + } + } + Merger m = new Merger(this, a, w, lb + lh, ln - lh, + rb + rh, rn - rh, + k + lh + rh, g); + rn = rh; + ln = lh; + addToPendingCount(1); + m.fork(); } - int l = lo; - int lFence = l + nleft; - int r = ro; - int rFence = r + nright; - int k = wo; - while (l < lFence && r < rFence) { - byte al = a[l]; - byte ar = a[r]; - byte t; - if (al <= ar) {++l; t=al;} else {++r; t = ar;} + int lf = lb + ln, rf = rb + rn; // index bounds + while (lb < lf && rb < rf) { + byte t, al, ar; + if ((al = a[lb]) <= (ar = a[rb])) { + lb++; t = al; + } + else { + rb++; t = ar; + } w[k++] = t; } - while (l < lFence) - w[k++] = a[l++]; - while (r < rFence) - w[k++] = a[r++]; - while (rights != null) { - if (rights.tryUnfork()) - rights.compute(); - else - rights.join(); - rights = rights.next; - } + if (rb < rf) + System.arraycopy(a, rb, w, k, rf - rb); + else if (lb < lf) + System.arraycopy(a, lb, w, k, lf - lb); + tryComplete(); } } } // FJByte /** char support class */ static final class FJChar { - static final class Sorter extends RecursiveAction { - static final long serialVersionUID = 8723376019074596641L; - final char[] a; // array to be sorted. - final char[] w; // workspace for merge - final int origin; // origin of the part of array we deal with - final int n; // Number of elements in (sub)arrays. - final int gran; // split control - - Sorter(char[] a, char[] w, int origin, int n, int gran) { - this.a = a; - this.w = w; - this.origin = origin; - this.n = n; - this.gran = gran; + static final class Sorter extends CountedCompleter<Void> { + static final long serialVersionUID = 2446542900576103244L; + final char[] a, w; + final int base, size, wbase, gran; + Sorter(CountedCompleter<?> par, char[] a, char[] w, int base, + int size, int wbase, int gran) { + super(par); + this.a = a; this.w = w; this.base = base; this.size = size; + this.wbase = wbase; this.gran = gran; } - - public void compute() { - final int l = origin; - final int g = gran; - final int n = this.n; - final char[] a = this.a; - final char[] w = this.w; - if (n > g) { - int h = n >>> 1; // half - int q = n >>> 2; // lower quarter index - int u = h + q; // upper quarter - FJSubSorter ls = new FJSubSorter(new Sorter(a, w, l, q, g), - new Sorter(a, w, l+q, h-q, g), - new Merger(a, w, l, q, - l+q, h-q, l, g, null)); - FJSubSorter rs = new FJSubSorter(new Sorter(a, w, l + h, q, g), - new Sorter(a, w, l+u, n-u, g), - new Merger(a, w, l+h, q, - l+u, n-u, l+h, g, null)); - rs.fork(); - ls.compute(); - if (rs.tryUnfork()) rs.compute(); else rs.join(); - new Merger(w, a, l, h, l + h, n - h, l, g, null).compute(); - } else { - DualPivotQuicksort.sort(a, l, l+n-1); // skip rangeCheck + public final void compute() { + CountedCompleter<?> s = this; + char[] a = this.a, w = this.w; // localize all params + int b = this.base, n = this.size, wb = this.wbase, g = this.gran; + while (n > g) { + int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles + Relay fc = new Relay(new Merger(s, w, a, wb, h, + wb+h, n-h, b, g)); + Relay rc = new Relay(new Merger(fc, a, w, b+h, q, + b+u, n-u, wb+h, g)); + new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork(); + new Sorter(rc, a, w, b+h, q, wb+h, g).fork();; + Relay bc = new Relay(new Merger(fc, a, w, b, q, + b+q, h-q, wb, g)); + new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork(); + s = new EmptyCompleter(bc); + n = q; } + DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n); + s.tryComplete(); } } - static final class Merger extends RecursiveAction { - static final long serialVersionUID = -1383975444621698926L; - final char[] a; - final char[] w; - final int lo; - final int ln; - final int ro; - final int rn; - final int wo; - final int gran; - final Merger next; - - Merger(char[] a, char[] w, int lo, int ln, int ro, int rn, int wo, - int gran, Merger next) { - this.a = a; - this.w = w; - this.lo = lo; - this.ln = ln; - this.ro = ro; - this.rn = rn; - this.wo = wo; - this.gran = gran; - this.next = next; + static final class Merger extends CountedCompleter<Void> { + static final long serialVersionUID = 2446542900576103244L; + final char[] a, w; // main and workspace arrays + final int lbase, lsize, rbase, rsize, wbase, gran; + Merger(CountedCompleter<?> par, char[] a, char[] w, + int lbase, int lsize, int rbase, + int rsize, int wbase, int gran) { + super(par); + this.a = a; this.w = w; + this.lbase = lbase; this.lsize = lsize; + this.rbase = rbase; this.rsize = rsize; + this.wbase = wbase; this.gran = gran; } - public void compute() { - final char[] a = this.a; - final char[] w = this.w; - Merger rights = null; - int nleft = ln; - int nright = rn; - while (nleft > gran) { - int lh = nleft >>> 1; - int splitIndex = lo + lh; - char split = a[splitIndex]; - int rl = 0; - int rh = nright; - while (rl < rh) { - int mid = (rl + rh) >>> 1; - if (split <= a[ro + mid]) - rh = mid; - else - rl = mid + 1; + public final void compute() { + char[] a = this.a, w = this.w; // localize all params + int lb = this.lbase, ln = this.lsize, rb = this.rbase, + rn = this.rsize, k = this.wbase, g = this.gran; + if (a == null || w == null || lb < 0 || rb < 0 || k < 0) + throw new IllegalStateException(); // hoist checks + for (int lh, rh;;) { // split larger, find point in smaller + if (ln >= rn) { + if (ln <= g) + break; + rh = rn; + char split = a[(lh = ln >>> 1) + lb]; + for (int lo = 0; lo < rh; ) { + int rm = (lo + rh) >>> 1; + if (split <= a[rm + rb]) + rh = rm; + else + lo = rm + 1; + } } - (rights = new Merger(a, w, splitIndex, nleft-lh, ro+rh, - nright-rh, wo+lh+rh, gran, rights)).fork(); - nleft = lh; - nright = rh; + else { + if (rn <= g) + break; + lh = ln; + char split = a[(rh = rn >>> 1) + rb]; + for (int lo = 0; lo < lh; ) { + int lm = (lo + lh) >>> 1; + if (split <= a[lm + lb]) + lh = lm; + else + lo = lm + 1; + } + } + Merger m = new Merger(this, a, w, lb + lh, ln - lh, + rb + rh, rn - rh, + k + lh + rh, g); + rn = rh; + ln = lh; + addToPendingCount(1); + m.fork(); } - int l = lo; - int lFence = l + nleft; - int r = ro; - int rFence = r + nright; - int k = wo; - while (l < lFence && r < rFence) { - char al = a[l]; - char ar = a[r]; - char t; - if (al <= ar) {++l; t=al;} else {++r; t = ar;} + int lf = lb + ln, rf = rb + rn; // index bounds + while (lb < lf && rb < rf) { + char t, al, ar; + if ((al = a[lb]) <= (ar = a[rb])) { + lb++; t = al; + } + else { + rb++; t = ar; + } w[k++] = t; } - while (l < lFence) - w[k++] = a[l++]; - while (r < rFence) - w[k++] = a[r++]; - while (rights != null) { - if (rights.tryUnfork()) - rights.compute(); - else - rights.join(); - rights = rights.next; - } + if (rb < rf) + System.arraycopy(a, rb, w, k, rf - rb); + else if (lb < lf) + System.arraycopy(a, lb, w, k, lf - lb); + tryComplete(); } } } // FJChar /** short support class */ static final class FJShort { - static final class Sorter extends RecursiveAction { - static final long serialVersionUID = -7886754793730583084L; - final short[] a; // array to be sorted. - final short[] w; // workspace for merge - final int origin; // origin of the part of array we deal with - final int n; // Number of elements in (sub)arrays. - final int gran; // split control - - Sorter(short[] a, short[] w, int origin, int n, int gran) { - this.a = a; - this.w = w; - this.origin = origin; - this.n = n; - this.gran = gran; + static final class Sorter extends CountedCompleter<Void> { + static final long serialVersionUID = 2446542900576103244L; + final short[] a, w; + final int base, size, wbase, gran; + Sorter(CountedCompleter<?> par, short[] a, short[] w, int base, + int size, int wbase, int gran) { + super(par); + this.a = a; this.w = w; this.base = base; this.size = size; + this.wbase = wbase; this.gran = gran; } - - public void compute() { - final int l = origin; - final int g = gran; - final int n = this.n; - final short[] a = this.a; - final short[] w = this.w; - if (n > g) { - int h = n >>> 1; // half - int q = n >>> 2; // lower quarter index - int u = h + q; // upper quarter - FJSubSorter ls = new FJSubSorter(new Sorter(a, w, l, q, g), - new Sorter(a, w, l+q, h-q, g), - new Merger(a, w, l, q, - l+q, h-q, l, g, null)); - FJSubSorter rs = new FJSubSorter(new Sorter(a, w, l + h, q, g), - new Sorter(a, w, l+u, n-u, g), - new Merger(a, w, l+h, q, - l+u, n-u, l+h, g, null)); - rs.fork(); - ls.compute(); - if (rs.tryUnfork()) rs.compute(); else rs.join(); - new Merger(w, a, l, h, l + h, n - h, l, g, null).compute(); - } else { - DualPivotQuicksort.sort(a, l, l+n-1); // skip rangeCheck + public final void compute() { + CountedCompleter<?> s = this; + short[] a = this.a, w = this.w; // localize all params + int b = this.base, n = this.size, wb = this.wbase, g = this.gran; + while (n > g) { + int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles + Relay fc = new Relay(new Merger(s, w, a, wb, h, + wb+h, n-h, b, g)); + Relay rc = new Relay(new Merger(fc, a, w, b+h, q, + b+u, n-u, wb+h, g)); + new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork(); + new Sorter(rc, a, w, b+h, q, wb+h, g).fork();; + Relay bc = new Relay(new Merger(fc, a, w, b, q, + b+q, h-q, wb, g)); + new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork(); + s = new EmptyCompleter(bc); + n = q; } + DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n); + s.tryComplete(); } } - static final class Merger extends RecursiveAction { - static final long serialVersionUID = 3895749408536700048L; - final short[] a; - final short[] w; - final int lo; - final int ln; - final int ro; - final int rn; - final int wo; - final int gran; - final Merger next; - - Merger(short[] a, short[] w, int lo, int ln, int ro, int rn, int wo, - int gran, Merger next) { - this.a = a; - this.w = w; - this.lo = lo; - this.ln = ln; - this.ro = ro; - this.rn = rn; - this.wo = wo; - this.gran = gran; - this.next = next; + static final class Merger extends CountedCompleter<Void> { + static final long serialVersionUID = 2446542900576103244L; + final short[] a, w; // main and workspace arrays + final int lbase, lsize, rbase, rsize, wbase, gran; + Merger(CountedCompleter<?> par, short[] a, short[] w, + int lbase, int lsize, int rbase, + int rsize, int wbase, int gran) { + super(par); + this.a = a; this.w = w; + this.lbase = lbase; this.lsize = lsize; + this.rbase = rbase; this.rsize = rsize; + this.wbase = wbase; this.gran = gran; } - public void compute() { - final short[] a = this.a; - final short[] w = this.w; - Merger rights = null; - int nleft = ln; - int nright = rn; - while (nleft > gran) { - int lh = nleft >>> 1; - int splitIndex = lo + lh; - short split = a[splitIndex]; - int rl = 0; - int rh = nright; - while (rl < rh) { - int mid = (rl + rh) >>> 1; - if (split <= a[ro + mid]) - rh = mid; - else - rl = mid + 1; + public final void compute() { + short[] a = this.a, w = this.w; // localize all params + int lb = this.lbase, ln = this.lsize, rb = this.rbase, + rn = this.rsize, k = this.wbase, g = this.gran; + if (a == null || w == null || lb < 0 || rb < 0 || k < 0) + throw new IllegalStateException(); // hoist checks + for (int lh, rh;;) { // split larger, find point in smaller + if (ln >= rn) { + if (ln <= g) + break; + rh = rn; + short split = a[(lh = ln >>> 1) + lb]; + for (int lo = 0; lo < rh; ) { + int rm = (lo + rh) >>> 1; + if (split <= a[rm + rb]) + rh = rm; + else + lo = rm + 1; + } } - (rights = new Merger(a, w, splitIndex, nleft-lh, ro+rh, - nright-rh, wo+lh+rh, gran, rights)).fork(); - nleft = lh; - nright = rh; + else { + if (rn <= g) + break; + lh = ln; + short split = a[(rh = rn >>> 1) + rb]; + for (int lo = 0; lo < lh; ) { + int lm = (lo + lh) >>> 1; + if (split <= a[lm + lb]) + lh = lm; + else + lo = lm + 1; + } + } + Merger m = new Merger(this, a, w, lb + lh, ln - lh, + rb + rh, rn - rh, + k + lh + rh, g); + rn = rh; + ln = lh; + addToPendingCount(1); + m.fork(); } - int l = lo; - int lFence = l + nleft; - int r = ro; - int rFence = r + nright; - int k = wo; - while (l < lFence && r < rFence) { - short al = a[l]; - short ar = a[r]; - short t; - if (al <= ar) {++l; t=al;} else {++r; t = ar;} + int lf = lb + ln, rf = rb + rn; // index bounds + while (lb < lf && rb < rf) { + short t, al, ar; + if ((al = a[lb]) <= (ar = a[rb])) { + lb++; t = al; + } + else { + rb++; t = ar; + } w[k++] = t; } - while (l < lFence) - w[k++] = a[l++]; - while (r < rFence) - w[k++] = a[r++]; - while (rights != null) { - if (rights.tryUnfork()) - rights.compute(); - else - rights.join(); - rights = rights.next; - } + if (rb < rf) + System.arraycopy(a, rb, w, k, rf - rb); + else if (lb < lf) + System.arraycopy(a, lb, w, k, lf - lb); + tryComplete(); } } } // FJShort /** int support class */ static final class FJInt { - static final class Sorter extends RecursiveAction { - static final long serialVersionUID = 4263311808957292729L; - final int[] a; // array to be sorted. - final int[] w; // workspace for merge - final int origin; // origin of the part of array we deal with - final int n; // Number of elements in (sub)arrays. - final int gran; // split control - - Sorter(int[] a, int[] w, int origin, int n, int gran) { - this.a = a; - this.w = w; - this.origin = origin; - this.n = n; - this.gran = gran; + static final class Sorter extends CountedCompleter<Void> { + static final long serialVersionUID = 2446542900576103244L; + final int[] a, w; + final int base, size, wbase, gran; + Sorter(CountedCompleter<?> par, int[] a, int[] w, int base, + int size, int wbase, int gran) { + super(par); + this.a = a; this.w = w; this.base = base; this.size = size; + this.wbase = wbase; this.gran = gran; } - - public void compute() { - final int l = origin; - final int g = gran; - final int n = this.n; - final int[] a = this.a; - final int[] w = this.w; - if (n > g) { - int h = n >>> 1; // half - int q = n >>> 2; // lower quarter index - int u = h + q; // upper quarter - FJSubSorter ls = new FJSubSorter(new Sorter(a, w, l, q, g), - new Sorter(a, w, l+q, h-q, g), - new Merger(a, w, l, q, - l+q, h-q, l, g, null)); - FJSubSorter rs = new FJSubSorter(new Sorter(a, w, l + h, q, g), - new Sorter(a, w, l+u, n-u, g), - new Merger(a, w, l+h, q, - l+u, n-u, l+h, g, null)); - rs.fork(); - ls.compute(); - if (rs.tryUnfork()) rs.compute(); else rs.join(); - new Merger(w, a, l, h, l + h, n - h, l, g, null).compute(); - } else { - DualPivotQuicksort.sort(a, l, l+n-1); // skip rangeCheck + public final void compute() { + CountedCompleter<?> s = this; + int[] a = this.a, w = this.w; // localize all params + int b = this.base, n = this.size, wb = this.wbase, g = this.gran; + while (n > g) { + int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles + Relay fc = new Relay(new Merger(s, w, a, wb, h, + wb+h, n-h, b, g)); + Relay rc = new Relay(new Merger(fc, a, w, b+h, q, + b+u, n-u, wb+h, g)); + new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork(); + new Sorter(rc, a, w, b+h, q, wb+h, g).fork();; + Relay bc = new Relay(new Merger(fc, a, w, b, q, + b+q, h-q, wb, g)); + new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork(); + s = new EmptyCompleter(bc); + n = q; } + DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n); + s.tryComplete(); } } - static final class Merger extends RecursiveAction { - static final long serialVersionUID = -8727507284219982792L; - final int[] a; - final int[] w; - final int lo; - final int ln; - final int ro; - final int rn; - final int wo; - final int gran; - final Merger next; - - Merger(int[] a, int[] w, int lo, int ln, int ro, int rn, int wo, - int gran, Merger next) { - this.a = a; - this.w = w; - this.lo = lo; - this.ln = ln; - this.ro = ro; - this.rn = rn; - this.wo = wo; - this.gran = gran; - this.next = next; + static final class Merger extends CountedCompleter<Void> { + static final long serialVersionUID = 2446542900576103244L; + final int[] a, w; // main and workspace arrays + final int lbase, lsize, rbase, rsize, wbase, gran; + Merger(CountedCompleter<?> par, int[] a, int[] w, + int lbase, int lsize, int rbase, + int rsize, int wbase, int gran) { + super(par); + this.a = a; this.w = w; + this.lbase = lbase; this.lsize = lsize; + this.rbase = rbase; this.rsize = rsize; + this.wbase = wbase; this.gran = gran; } - public void compute() { - final int[] a = this.a; - final int[] w = this.w; - Merger rights = null; - int nleft = ln; - int nright = rn; - while (nleft > gran) { - int lh = nleft >>> 1; - int splitIndex = lo + lh; - int split = a[splitIndex]; - int rl = 0; - int rh = nright; - while (rl < rh) { - int mid = (rl + rh) >>> 1; - if (split <= a[ro + mid]) - rh = mid; - else - rl = mid + 1; + public final void compute() { + int[] a = this.a, w = this.w; // localize all params + int lb = this.lbase, ln = this.lsize, rb = this.rbase, + rn = this.rsize, k = this.wbase, g = this.gran; + if (a == null || w == null || lb < 0 || rb < 0 || k < 0) + throw new IllegalStateException(); // hoist checks + for (int lh, rh;;) { // split larger, find point in smaller + if (ln >= rn) { + if (ln <= g) + break; + rh = rn; + int split = a[(lh = ln >>> 1) + lb]; + for (int lo = 0; lo < rh; ) { + int rm = (lo + rh) >>> 1; + if (split <= a[rm + rb]) + rh = rm; + else + lo = rm + 1; + } } - (rights = new Merger(a, w, splitIndex, nleft-lh, ro+rh, - nright-rh, wo+lh+rh, gran, rights)).fork(); - nleft = lh; - nright = rh; + else { + if (rn <= g) + break; + lh = ln; + int split = a[(rh = rn >>> 1) + rb]; + for (int lo = 0; lo < lh; ) { + int lm = (lo + lh) >>> 1; + if (split <= a[lm + lb]) + lh = lm; + else + lo = lm + 1; + } + } + Merger m = new Merger(this, a, w, lb + lh, ln - lh, + rb + rh, rn - rh, + k + lh + rh, g); + rn = rh; + ln = lh; + addToPendingCount(1); + m.fork(); } - int l = lo; - int lFence = l + nleft; - int r = ro; - int rFence = r + nright; - int k = wo; - while (l < lFence && r < rFence) { - int al = a[l]; - int ar = a[r]; - int t; - if (al <= ar) {++l; t=al;} else {++r; t = ar;} + int lf = lb + ln, rf = rb + rn; // index bounds + while (lb < lf && rb < rf) { + int t, al, ar; + if ((al = a[lb]) <= (ar = a[rb])) { + lb++; t = al; + } + else { + rb++; t = ar; + } w[k++] = t; } - while (l < lFence) - w[k++] = a[l++]; - while (r < rFence) - w[k++] = a[r++]; - while (rights != null) { - if (rights.tryUnfork()) - rights.compute(); - else - rights.join(); - rights = rights.next; - } + if (rb < rf) + System.arraycopy(a, rb, w, k, rf - rb); + else if (lb < lf) + System.arraycopy(a, lb, w, k, lf - lb); + tryComplete(); } } } // FJInt /** long support class */ static final class FJLong { - static final class Sorter extends RecursiveAction { - static final long serialVersionUID = 6553695007444392455L; - final long[] a; // array to be sorted. - final long[] w; // workspace for merge - final int origin; // origin of the part of array we deal with - final int n; // Number of elements in (sub)arrays. - final int gran; // split control - - Sorter(long[] a, long[] w, int origin, int n, int gran) { - this.a = a; - this.w = w; - this.origin = origin; - this.n = n; - this.gran = gran; + static final class Sorter extends CountedCompleter<Void> { + static final long serialVersionUID = 2446542900576103244L; + final long[] a, w; + final int base, size, wbase, gran; + Sorter(CountedCompleter<?> par, long[] a, long[] w, int base, + int size, int wbase, int gran) { + super(par); + this.a = a; this.w = w; this.base = base; this.size = size; + this.wbase = wbase; this.gran = gran; } - - public void compute() { - final int l = origin; - final int g = gran; - final int n = this.n; - final long[] a = this.a; - final long[] w = this.w; - if (n > g) { - int h = n >>> 1; // half - int q = n >>> 2; // lower quarter index - int u = h + q; // upper quarter - FJSubSorter ls = new FJSubSorter(new Sorter(a, w, l, q, g), - new Sorter(a, w, l+q, h-q, g), - new Merger(a, w, l, q, - l+q, h-q, l, g, null)); - FJSubSorter rs = new FJSubSorter(new Sorter(a, w, l + h, q, g), - new Sorter(a, w, l+u, n-u, g), - new Merger(a, w, l+h, q, - l+u, n-u, l+h, g, null)); - rs.fork(); - ls.compute(); - if (rs.tryUnfork()) rs.compute(); else rs.join(); - new Merger(w, a, l, h, l + h, n - h, l, g, null).compute(); - } else { - DualPivotQuicksort.sort(a, l, l+n-1); // skip rangeCheck + public final void compute() { + CountedCompleter<?> s = this; + long[] a = this.a, w = this.w; // localize all params + int b = this.base, n = this.size, wb = this.wbase, g = this.gran; + while (n > g) { + int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles + Relay fc = new Relay(new Merger(s, w, a, wb, h, + wb+h, n-h, b, g)); + Relay rc = new Relay(new Merger(fc, a, w, b+h, q, + b+u, n-u, wb+h, g)); + new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork(); + new Sorter(rc, a, w, b+h, q, wb+h, g).fork();; + Relay bc = new Relay(new Merger(fc, a, w, b, q, + b+q, h-q, wb, g)); + new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork(); + s = new EmptyCompleter(bc); + n = q; } + DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n); + s.tryComplete(); } } - static final class Merger extends RecursiveAction { - static final long serialVersionUID = 8843567516333283861L; - final long[] a; - final long[] w; - final int lo; - final int ln; - final int ro; - final int rn; - final int wo; - final int gran; - final Merger next; - - Merger(long[] a, long[] w, int lo, int ln, int ro, int rn, int wo, - int gran, Merger next) { - this.a = a; - this.w = w; - this.lo = lo; - this.ln = ln; - this.ro = ro; - this.rn = rn; - this.wo = wo; - this.gran = gran; - this.next = next; + static final class Merger extends CountedCompleter<Void> { + static final long serialVersionUID = 2446542900576103244L; + final long[] a, w; // main and workspace arrays + final int lbase, lsize, rbase, rsize, wbase, gran; + Merger(CountedCompleter<?> par, long[] a, long[] w, + int lbase, int lsize, int rbase, + int rsize, int wbase, int gran) { + super(par); + this.a = a; this.w = w; + this.lbase = lbase; this.lsize = lsize; + this.rbase = rbase; this.rsize = rsize; + this.wbase = wbase; this.gran = gran; } - public void compute() { - final long[] a = this.a; - final long[] w = this.w; - Merger rights = null; - int nleft = ln; - int nright = rn; - while (nleft > gran) { - int lh = nleft >>> 1; - int splitIndex = lo + lh; - long split = a[splitIndex]; - int rl = 0; - int rh = nright; - while (rl < rh) { - int mid = (rl + rh) >>> 1; - if (split <= a[ro + mid]) - rh = mid; - else - rl = mid + 1; + public final void compute() { + long[] a = this.a, w = this.w; // localize all params + int lb = this.lbase, ln = this.lsize, rb = this.rbase, + rn = this.rsize, k = this.wbase, g = this.gran; + if (a == null || w == null || lb < 0 || rb < 0 || k < 0) + throw new IllegalStateException(); // hoist checks + for (int lh, rh;;) { // split larger, find point in smaller + if (ln >= rn) { + if (ln <= g) + break; + rh = rn; + long split = a[(lh = ln >>> 1) + lb]; + for (int lo = 0; lo < rh; ) { + int rm = (lo + rh) >>> 1; + if (split <= a[rm + rb]) + rh = rm; + else + lo = rm + 1; + } } - (rights = new Merger(a, w, splitIndex, nleft-lh, ro+rh, - nright-rh, wo+lh+rh, gran, rights)).fork(); - nleft = lh; - nright = rh; + else { + if (rn <= g) + break; + lh = ln; + long split = a[(rh = rn >>> 1) + rb]; + for (int lo = 0; lo < lh; ) { + int lm = (lo + lh) >>> 1; + if (split <= a[lm + lb]) + lh = lm; + else + lo = lm + 1; + } + } + Merger m = new Merger(this, a, w, lb + lh, ln - lh, + rb + rh, rn - rh, + k + lh + rh, g); + rn = rh; + ln = lh; + addToPendingCount(1); + m.fork(); } - int l = lo; - int lFence = l + nleft; - int r = ro; - int rFence = r + nright; - int k = wo; - while (l < lFence && r < rFence) { - long al = a[l]; - long ar = a[r]; - long t; - if (al <= ar) {++l; t=al;} else {++r; t = ar;} + int lf = lb + ln, rf = rb + rn; // index bounds + while (lb < lf && rb < rf) { + long t, al, ar; + if ((al = a[lb]) <= (ar = a[rb])) { + lb++; t = al; + } + else { + rb++; t = ar; + } w[k++] = t; } - while (l < lFence) - w[k++] = a[l++]; - while (r < rFence) - w[k++] = a[r++]; - while (rights != null) { - if (rights.tryUnfork()) - rights.compute(); - else - rights.join(); - rights = rights.next; - } + if (rb < rf) + System.arraycopy(a, rb, w, k, rf - rb); + else if (lb < lf) + System.arraycopy(a, lb, w, k, lf - lb); + tryComplete(); } } } // FJLong /** float support class */ static final class FJFloat { - static final class Sorter extends RecursiveAction { - static final long serialVersionUID = 1602600178202763377L; - final float[] a; // array to be sorted. - final float[] w; // workspace for merge - final int origin; // origin of the part of array we deal with - final int n; // Number of elements in (sub)arrays. - final int gran; // split control - - Sorter(float[] a, float[] w, int origin, int n, int gran) { - this.a = a; - this.w = w; - this.origin = origin; - this.n = n; - this.gran = gran; + static final class Sorter extends CountedCompleter<Void> { + static final long serialVersionUID = 2446542900576103244L; + final float[] a, w; + final int base, size, wbase, gran; + Sorter(CountedCompleter<?> par, float[] a, float[] w, int base, + int size, int wbase, int gran) { + super(par); + this.a = a; this.w = w; this.base = base; this.size = size; + this.wbase = wbase; this.gran = gran; } - - public void compute() { - final int l = origin; - final int g = gran; - final int n = this.n; - final float[] a = this.a; - final float[] w = this.w; - if (n > g) { - int h = n >>> 1; // half - int q = n >>> 2; // lower quarter index - int u = h + q; // upper quarter - FJSubSorter ls = new FJSubSorter(new Sorter(a, w, l, q, g), - new Sorter(a, w, l+q, h-q, g), - new Merger(a, w, l, q, - l+q, h-q, l, g, null)); - FJSubSorter rs = new FJSubSorter(new Sorter(a, w, l + h, q, g), - new Sorter(a, w, l+u, n-u, g), - new Merger(a, w, l+h, q, - l+u, n-u, l+h, g, null)); - rs.fork(); - ls.compute(); - if (rs.tryUnfork()) rs.compute(); else rs.join(); - new Merger(w, a, l, h, l + h, n - h, l, g, null).compute(); - } else { - DualPivotQuicksort.sort(a, l, l+n-1); // skip rangeCheck + public final void compute() { + CountedCompleter<?> s = this; + float[] a = this.a, w = this.w; // localize all params + int b = this.base, n = this.size, wb = this.wbase, g = this.gran; + while (n > g) { + int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles + Relay fc = new Relay(new Merger(s, w, a, wb, h, + wb+h, n-h, b, g)); + Relay rc = new Relay(new Merger(fc, a, w, b+h, q, + b+u, n-u, wb+h, g)); + new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork(); + new Sorter(rc, a, w, b+h, q, wb+h, g).fork();; + Relay bc = new Relay(new Merger(fc, a, w, b, q, + b+q, h-q, wb, g)); + new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork(); + s = new EmptyCompleter(bc); + n = q; } + DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n); + s.tryComplete(); } } - static final class Merger extends RecursiveAction { - static final long serialVersionUID = 1518176433845397426L; - final float[] a; - final float[] w; - final int lo; - final int ln; - final int ro; - final int rn; - final int wo; - final int gran; - final Merger next; - - Merger(float[] a, float[] w, int lo, int ln, int ro, int rn, int wo, - int gran, Merger next) { - this.a = a; - this.w = w; - this.lo = lo; - this.ln = ln; - this.ro = ro; - this.rn = rn; - this.wo = wo; - this.gran = gran; - this.next = next; + static final class Merger extends CountedCompleter<Void> { + static final long serialVersionUID = 2446542900576103244L; + final float[] a, w; // main and workspace arrays + final int lbase, lsize, rbase, rsize, wbase, gran; + Merger(CountedCompleter<?> par, float[] a, float[] w, + int lbase, int lsize, int rbase, + int rsize, int wbase, int gran) { + super(par); + this.a = a; this.w = w; + this.lbase = lbase; this.lsize = lsize; + this.rbase = rbase; this.rsize = rsize; + this.wbase = wbase; this.gran = gran; } - public void compute() { - final float[] a = this.a; - final float[] w = this.w; - Merger rights = null; - int nleft = ln; - int nright = rn; - while (nleft > gran) { - int lh = nleft >>> 1; - int splitIndex = lo + lh; - float split = a[splitIndex]; - int rl = 0; - int rh = nright; - while (rl < rh) { - int mid = (rl + rh) >>> 1; - if (Float.compare(split, a[ro+mid]) <= 0) - rh = mid; - else - rl = mid + 1; + public final void compute() { + float[] a = this.a, w = this.w; // localize all params + int lb = this.lbase, ln = this.lsize, rb = this.rbase, + rn = this.rsize, k = this.wbase, g = this.gran; + if (a == null || w == null || lb < 0 || rb < 0 || k < 0) + throw new IllegalStateException(); // hoist checks + for (int lh, rh;;) { // split larger, find point in smaller + if (ln >= rn) { + if (ln <= g) + break; + rh = rn; + float split = a[(lh = ln >>> 1) + lb]; + for (int lo = 0; lo < rh; ) { + int rm = (lo + rh) >>> 1; + if (split <= a[rm + rb]) + rh = rm; + else + lo = rm + 1; + } } - (rights = new Merger(a, w, splitIndex, nleft-lh, ro+rh, - nright-rh, wo+lh+rh, gran, rights)).fork(); - nleft = lh; - nright = rh; + else { + if (rn <= g) + break; + lh = ln; + float split = a[(rh = rn >>> 1) + rb]; + for (int lo = 0; lo < lh; ) { + int lm = (lo + lh) >>> 1; + if (split <= a[lm + lb]) + lh = lm; + else + lo = lm + 1; + } + } + Merger m = new Merger(this, a, w, lb + lh, ln - lh, + rb + rh, rn - rh, + k + lh + rh, g); + rn = rh; + ln = lh; + addToPendingCount(1); + m.fork(); } - int l = lo; - int lFence = l + nleft; - int r = ro; - int rFence = r + nright; - int k = wo; - while (l < lFence && r < rFence) { - float al = a[l]; - float ar = a[r]; - float t; - if (Float.compare(al, ar) <= 0) { - ++l; - t = al; - } else { - ++r; - t = ar; + int lf = lb + ln, rf = rb + rn; // index bounds + while (lb < lf && rb < rf) { + float t, al, ar; + if ((al = a[lb]) <= (ar = a[rb])) { + lb++; t = al; + } + else { + rb++; t = ar; } w[k++] = t; } - while (l < lFence) - w[k++] = a[l++]; - while (r < rFence) - w[k++] = a[r++]; - while (rights != null) { - if (rights.tryUnfork()) - rights.compute(); - else - rights.join(); - rights = rights.next; - } + if (rb < rf) + System.arraycopy(a, rb, w, k, rf - rb); + else if (lb < lf) + System.arraycopy(a, lb, w, k, lf - lb); + tryComplete(); } } } // FJFloat /** double support class */ static final class FJDouble { - static final class Sorter extends RecursiveAction { + static final class Sorter extends CountedCompleter<Void> { static final long serialVersionUID = 2446542900576103244L; - final double[] a; // array to be sorted. - final double[] w; // workspace for merge - final int origin; // origin of the part of array we deal with - final int n; // Number of elements in (sub)arrays. - final int gran; // split control - - Sorter(double[] a, double[] w, int origin, int n, int gran) { - this.a = a; - this.w = w; - this.origin = origin; - this.n = n; - this.gran = gran; + final double[] a, w; + final int base, size, wbase, gran; + Sorter(CountedCompleter<?> par, double[] a, double[] w, int base, + int size, int wbase, int gran) { + super(par); + this.a = a; this.w = w; this.base = base; this.size = size; + this.wbase = wbase; this.gran = gran; } - - public void compute() { - final int l = origin; - final int g = gran; - final int n = this.n; - final double[] a = this.a; - final double[] w = this.w; - if (n > g) { - int h = n >>> 1; // half - int q = n >>> 2; // lower quarter index - int u = h + q; // upper quarter - FJSubSorter ls = new FJSubSorter(new Sorter(a, w, l, q, g), - new Sorter(a, w, l+q, h-q, g), - new Merger(a, w, l, q, - l+q, h-q, l, g, null)); - FJSubSorter rs = new FJSubSorter(new Sorter(a, w, l + h, q, g), - new Sorter(a, w, l+u, n-u, g), - new Merger(a, w, l+h, q, - l+u, n-u, l+h, g, null)); - rs.fork(); - ls.compute(); - if (rs.tryUnfork()) rs.compute(); else rs.join(); - new Merger(w, a, l, h, l + h, n - h, l, g, null).compute(); - } else { - DualPivotQuicksort.sort(a, l, l+n-1); // skip rangeCheck + public final void compute() { + CountedCompleter<?> s = this; + double[] a = this.a, w = this.w; // localize all params + int b = this.base, n = this.size, wb = this.wbase, g = this.gran; + while (n > g) { + int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles + Relay fc = new Relay(new Merger(s, w, a, wb, h, + wb+h, n-h, b, g)); + Relay rc = new Relay(new Merger(fc, a, w, b+h, q, + b+u, n-u, wb+h, g)); + new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork(); + new Sorter(rc, a, w, b+h, q, wb+h, g).fork();; + Relay bc = new Relay(new Merger(fc, a, w, b, q, + b+q, h-q, wb, g)); + new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork(); + s = new EmptyCompleter(bc); + n = q; } + DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n); + s.tryComplete(); } } - static final class Merger extends RecursiveAction { - static final long serialVersionUID = 8076242187166127592L; - final double[] a; - final double[] w; - final int lo; - final int ln; - final int ro; - final int rn; - final int wo; - final int gran; - final Merger next; - - Merger(double[] a, double[] w, int lo, int ln, int ro, int rn, int wo, - int gran, Merger next) { - this.a = a; - this.w = w; - this.lo = lo; - this.ln = ln; - this.ro = ro; - this.rn = rn; - this.wo = wo; - this.gran = gran; - this.next = next; + static final class Merger extends CountedCompleter<Void> { + static final long serialVersionUID = 2446542900576103244L; + final double[] a, w; // main and workspace arrays + final int lbase, lsize, rbase, rsize, wbase, gran; + Merger(CountedCompleter<?> par, double[] a, double[] w, + int lbase, int lsize, int rbase, + int rsize, int wbase, int gran) { + super(par); + this.a = a; this.w = w; + this.lbase = lbase; this.lsize = lsize; + this.rbase = rbase; this.rsize = rsize; + this.wbase = wbase; this.gran = gran; } - public void compute() { - final double[] a = this.a; - final double[] w = this.w; - Merger rights = null; - int nleft = ln; - int nright = rn; - while (nleft > gran) { - int lh = nleft >>> 1; - int splitIndex = lo + lh; - double split = a[splitIndex]; - int rl = 0; - int rh = nright; - while (rl < rh) { - int mid = (rl + rh) >>> 1; - if (Double.compare(split, a[ro+mid]) <= 0) - rh = mid; - else - rl = mid + 1; + public final void compute() { + double[] a = this.a, w = this.w; // localize all params + int lb = this.lbase, ln = this.lsize, rb = this.rbase, + rn = this.rsize, k = this.wbase, g = this.gran; + if (a == null || w == null || lb < 0 || rb < 0 || k < 0) + throw new IllegalStateException(); // hoist checks + for (int lh, rh;;) { // split larger, find point in smaller + if (ln >= rn) { + if (ln <= g) + break; + rh = rn; + double split = a[(lh = ln >>> 1) + lb]; + for (int lo = 0; lo < rh; ) { + int rm = (lo + rh) >>> 1; + if (split <= a[rm + rb]) + rh = rm; + else + lo = rm + 1; + } } - (rights = new Merger(a, w, splitIndex, nleft-lh, ro+rh, - nright-rh, wo+lh+rh, gran, rights)).fork(); - nleft = lh; - nright = rh; + else { + if (rn <= g) + break; + lh = ln; + double split = a[(rh = rn >>> 1) + rb]; + for (int lo = 0; lo < lh; ) { + int lm = (lo + lh) >>> 1; + if (split <= a[lm + lb]) + lh = lm; + else + lo = lm + 1; + } + } + Merger m = new Merger(this, a, w, lb + lh, ln - lh, + rb + rh, rn - rh, + k + lh + rh, g); + rn = rh; + ln = lh; + addToPendingCount(1); + m.fork(); } - int l = lo; - int lFence = l + nleft; - int r = ro; - int rFence = r + nright; - int k = wo; - while (l < lFence && r < rFence) { - double al = a[l]; - double ar = a[r]; - double t; - if (Double.compare(al, ar) <= 0) { - ++l; - t = al; - } else { - ++r; - t = ar; + int lf = lb + ln, rf = rb + rn; // index bounds + while (lb < lf && rb < rf) { + double t, al, ar; + if ((al = a[lb]) <= (ar = a[rb])) { + lb++; t = al; + } + else { + rb++; t = ar; } w[k++] = t; } - while (l < lFence) - w[k++] = a[l++]; - while (r < rFence) - w[k++] = a[r++]; - while (rights != null) { - if (rights.tryUnfork()) - rights.compute(); - else - rights.join(); - rights = rights.next; - } + if (rb < rf) + System.arraycopy(a, rb, w, k, rf - rb); + else if (lb < lf) + System.arraycopy(a, lb, w, k, lf - lb); + tryComplete(); } } } // FJDouble - /** Comparable support class */ - static final class FJComparable { - static final class Sorter<T extends Comparable<? super T>> extends RecursiveAction { - static final long serialVersionUID = -1024003289463302522L; - final T[] a; - final T[] w; - final int origin; - final int n; - final int gran; - - Sorter(T[] a, T[] w, int origin, int n, int gran) { - this.a = a; - this.w = w; - this.origin = origin; - this.n = n; - this.gran = gran; - } - - public void compute() { - final int l = origin; - final int g = gran; - final int n = this.n; - final T[] a = this.a; - final T[] w = this.w; - if (n > g) { - int h = n >>> 1; - int q = n >>> 2; - int u = h + q; - FJSubSorter ls = new FJSubSorter(new Sorter<>(a, w, l, q, g), - new Sorter<>(a, w, l+q, h-q, g), - new Merger<>(a, w, l, q, - l+q, h-q, l, g, null)); - FJSubSorter rs = new FJSubSorter(new Sorter<>(a, w, l+h, q, g), - new Sorter<>(a, w, l+u, n-u, g), - new Merger<>(a, w, l+h, q, - l+u, n-u, l+h, g, null)); - rs.fork(); - ls.compute(); - if (rs.tryUnfork()) rs.compute(); else rs.join(); - new Merger<>(w, a, l, h, l + h, n - h, l, g, null).compute(); - } else { - Arrays.sort(a, l, l+n); - } - } - } - - static final class Merger<T extends Comparable<? super T>> extends RecursiveAction { - static final long serialVersionUID = -3989771675258379302L; - final T[] a; - final T[] w; - final int lo; - final int ln; - final int ro; - final int rn; - final int wo; - final int gran; - final Merger<T> next; - - Merger(T[] a, T[] w, int lo, int ln, int ro, int rn, int wo, - int gran, Merger<T> next) { - this.a = a; - this.w = w; - this.lo = lo; - this.ln = ln; - this.ro = ro; - this.rn = rn; - this.wo = wo; - this.gran = gran; - this.next = next; - } - - public void compute() { - final T[] a = this.a; - final T[] w = this.w; - Merger<T> rights = null; - int nleft = ln; - int nright = rn; - while (nleft > gran) { - int lh = nleft >>> 1; - int splitIndex = lo + lh; - T split = a[splitIndex]; - int rl = 0; - int rh = nright; - while (rl < rh) { - int mid = (rl + rh) >>> 1; - if (split.compareTo(a[ro + mid]) <= 0) - rh = mid; - else - rl = mid + 1; - } - (rights = new Merger<>(a, w, splitIndex, nleft-lh, ro+rh, - nright-rh, wo+lh+rh, gran, rights)).fork(); - nleft = lh; - nright = rh; - } - - int l = lo; - int lFence = l + nleft; - int r = ro; - int rFence = r + nright; - int k = wo; - while (l < lFence && r < rFence) { - T al = a[l]; - T ar = a[r]; - T t; - if (al.compareTo(ar) <= 0) {++l; t=al;} else {++r; t=ar; } - w[k++] = t; - } - while (l < lFence) - w[k++] = a[l++]; - while (r < rFence) - w[k++] = a[r++]; - while (rights != null) { - if (rights.tryUnfork()) - rights.compute(); - else - rights.join(); - rights = rights.next; - } - } - } - } // FJComparable - - /** Object + Comparator support class */ - static final class FJComparator { - static final class Sorter<T> extends RecursiveAction { - static final long serialVersionUID = 9191600840025808581L; - final T[] a; // array to be sorted. - final T[] w; // workspace for merge - final int origin; // origin of the part of array we deal with - final int n; // Number of elements in (sub)arrays. - final int gran; // split control - final Comparator<? super T> cmp; // Comparator to use - - Sorter(T[] a, T[] w, int origin, int n, int gran, Comparator<? super T> cmp) { - this.a = a; - this.w = w; - this.origin = origin; - this.n = n; - this.cmp = cmp; - this.gran = gran; - } - - public void compute() { - final int l = origin; - final int g = gran; - final int n = this.n; - final T[] a = this.a; - final T[] w = this.w; - if (n > g) { - int h = n >>> 1; // half - int q = n >>> 2; // lower quarter index - int u = h + q; // upper quarter - FJSubSorter ls = new FJSubSorter(new Sorter<>(a, w, l, q, g, cmp), - new Sorter<>(a, w, l+q, h-q, g, cmp), - new Merger<>(a, w, l, q, - l+q, h-q, l, g, null, cmp)); - FJSubSorter rs = new FJSubSorter(new Sorter<>(a, w, l + h, q, g, cmp), - new Sorter<>(a, w, l+u, n-u, g, cmp), - new Merger<>(a, w, l+h, q, - l+u, n-u, l+h, g, null, cmp)); - rs.fork(); - ls.compute(); - if (rs.tryUnfork()) rs.compute(); else rs.join(); - new Merger<>(w, a, l, h, l + h, n - h, l, g, null, cmp).compute(); - } else { - Arrays.sort(a, l, l+n, cmp); - } - } - } - - static final class Merger<T> extends RecursiveAction { - static final long serialVersionUID = -2679539040379156203L; - final T[] a; - final T[] w; - final int lo; - final int ln; - final int ro; - final int rn; - final int wo; - final int gran; - final Merger<T> next; - final Comparator<? super T> cmp; - - Merger(T[] a, T[] w, int lo, int ln, int ro, int rn, int wo, - int gran, Merger<T> next, Comparator<? super T> cmp) { - this.a = a; - this.w = w; - this.lo = lo; - this.ln = ln; - this.ro = ro; - this.rn = rn; - this.wo = wo; - this.gran = gran; - this.next = next; - this.cmp = cmp; - } - - public void compute() { - final T[] a = this.a; - final T[] w = this.w; - Merger<T> rights = null; - int nleft = ln; - int nright = rn; - while (nleft > gran) { - int lh = nleft >>> 1; - int splitIndex = lo + lh; - T split = a[splitIndex]; - int rl = 0; - int rh = nright; - while (rl < rh) { - int mid = (rl + rh) >>> 1; - if (cmp.compare(split, a[ro+mid]) <= 0) - rh = mid; - else - rl = mid + 1; - } - (rights = new Merger<>(a, w, splitIndex, nleft-lh, ro+rh, - nright-rh, wo+lh+rh, gran, rights, cmp)).fork(); - nleft = lh; - nright = rh; - } - - int l = lo; - int lFence = l + nleft; - int r = ro; - int rFence = r + nright; - int k = wo; - while (l < lFence && r < rFence) { - T al = a[l]; - T ar = a[r]; - T t; - if (cmp.compare(al, ar) <= 0) { - ++l; - t = al; - } else { - ++r; - t = ar; - } - w[k++] = t; - } - while (l < lFence) - w[k++] = a[l++]; - while (r < rFence) - w[k++] = a[r++]; - while (rights != null) { - if (rights.tryUnfork()) - rights.compute(); - else - rights.join(); - rights = rights.next; - } - } - } - } // FJComparator - - /** Utility class to sort half a partitioned array */ - private static final class FJSubSorter extends RecursiveAction { - static final long serialVersionUID = 9159249695527935512L; - final RecursiveAction left; - final RecursiveAction right; - final RecursiveAction merger; - - FJSubSorter(RecursiveAction left, RecursiveAction right, - RecursiveAction merger) { - this.left = left; - this.right = right; - this.merger = merger; - } - - public void compute() { - right.fork(); - left.invoke(); - right.join(); - merger.invoke(); - } - } }
--- a/src/share/classes/java/util/ComparableTimSort.java Thu May 23 09:48:44 2013 -0300 +++ b/src/share/classes/java/util/ComparableTimSort.java Wed May 29 13:22:58 2013 -0300 @@ -86,9 +86,13 @@ private static final int INITIAL_TMP_STORAGE_LENGTH = 256; /** - * Temp storage for merges. + * 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 Object[] 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 @@ -108,15 +112,27 @@ * Creates a TimSort instance to maintain the state of an ongoing sort. * * @param a the array to be sorted + * @param work a workspace array (slice) + * @param workBase origin of usable space in work array + * @param workLen usable size of work array */ - private ComparableTimSort(Object[] a) { + private ComparableTimSort(Object[] a, Object[] work, int workBase, int workLen) { this.a = a; // Allocate temp storage (which may be increased later if necessary) int len = a.length; - Object[] newArray = 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) { + tmp = new Object[tlen]; + tmpBase = 0; + tmpLen = tlen; + } + else { + tmp = work; + tmpBase = workBase; + tmpLen = workLen; + } /* * Allocate runs-to-be-merged stack (which cannot be expanded). The @@ -136,17 +152,28 @@ } /* - * 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(Object[] a) { - sort(a, 0, a.length); - } + /** + * 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 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(Object[] a, int lo, int hi, Object[] work, int workBase, int workLen) { + assert a != null && lo >= 0 && lo <= hi && hi <= a.length; - static void sort(Object[] a, int lo, int hi) { - rangeCheck(a.length, lo, hi); int nRemaining = hi - lo; if (nRemaining < 2) return; // Arrays of size 0 and 1 are always sorted @@ -163,7 +190,7 @@ * extending short natural runs to minRun elements, and merging runs * to maintain stack invariant. */ - ComparableTimSort ts = new ComparableTimSort(a); + ComparableTimSort ts = new ComparableTimSort(a, work, workBase, workLen); int minRun = minRunLength(nRemaining); do { // Identify next run @@ -619,11 +646,11 @@ // Copy first run into temp array Object[] a = this.a; // For performance Object[] 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++]; @@ -736,16 +763,17 @@ // Copy second run into temp array Object[] a = this.a; // For performance Object[] 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) { @@ -803,7 +831,7 @@ if (--len2 == 1) break outer; - count2 = len2 - gallopLeft((Comparable) a[cursor1], tmp, 0, len2, len2 - 1); + count2 = len2 - gallopLeft((Comparable) a[cursor1], tmp, tmpBase, len2, len2 - 1); if (count2 != 0) { dest -= count2; cursor2 -= count2; @@ -835,7 +863,7 @@ } 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); } } @@ -848,7 +876,7 @@ * @return tmp, whether or not it grew */ private Object[] ensureCapacity(int minCapacity) { - if (tmp.length < minCapacity) { + if (tmpLen < minCapacity) { // Compute smallest power of 2 > minCapacity int newSize = minCapacity; newSize |= newSize >> 1; @@ -863,30 +891,13 @@ else newSize = Math.min(newSize, a.length >>> 1); + @SuppressWarnings({"unchecked", "UnnecessaryLocalVariable"}) Object[] newArray = new Object[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); - } }
--- a/src/share/classes/java/util/DualPivotQuicksort.java Thu May 23 09:48:44 2013 -0300 +++ b/src/share/classes/java/util/DualPivotQuicksort.java Wed May 29 13:22:58 2013 -0300 @@ -32,6 +32,11 @@ * quicksorts to degrade to quadratic performance, and is typically * faster than traditional (one-pivot) Quicksort implementations. * + * All exposed methods are package-private, designed to be invoked + * from public methods (in class Arrays) after performing any + * necessary array bounds checks and expanding parameters into the + * required forms. + * * @author Vladimir Yaroslavskiy * @author Jon Bentley * @author Josh Bloch @@ -89,22 +94,18 @@ */ /** - * Sorts the specified array. - * - * @param a the array to be sorted - */ - public static void sort(int[] a) { - sort(a, 0, a.length - 1); - } - - /** - * Sorts the specified range of the array. + * Sorts the specified range of the array using the given + * workspace array slice if possible for merging * * @param a the array to be sorted * @param left the index of the first element, inclusive, to be sorted * @param right the index of the last element, inclusive, to be sorted + * @param work a workspace array (slice) + * @param workBase origin of usable space in work array + * @param workLen usable size of work array */ - public static void sort(int[] a, int left, int right) { + static void sort(int[] a, int left, int right, + int[] work, int workBase, int workLen) { // Use Quicksort on small arrays if (right - left < QUICKSORT_THRESHOLD) { sort(a, left, right, true); @@ -147,24 +148,35 @@ } // Check special cases + // Implementation note: variable "right" is increased by 1. if (run[count] == right++) { // The last run contains one element run[++count] = right; } else if (count == 1) { // The array is already sorted return; } - /* - * Create temporary array, which is used for merging. - * Implementation note: variable "right" is increased by 1. - */ - int[] b; byte odd = 0; + // Determine alternation base for merge + byte odd = 0; for (int n = 1; (n <<= 1) < count; odd ^= 1); + // Use or create temporary array b for merging + int[] b; // temp array; alternates with a + int ao, bo; // array offsets from 'left' + int blen = right - left; // space needed for b + if (work == null || workLen < blen || workBase + blen > work.length) { + work = new int[blen]; + workBase = 0; + } if (odd == 0) { - b = a; a = new int[b.length]; - for (int i = left - 1; ++i < right; a[i] = b[i]); + System.arraycopy(a, left, work, workBase, blen); + b = a; + bo = 0; + a = work; + ao = workBase - left; } else { - b = new int[a.length]; + b = work; + ao = 0; + bo = workBase - left; } // Merging @@ -172,21 +184,22 @@ for (int k = (last = 0) + 2; k <= count; k += 2) { int hi = run[k], mi = run[k - 1]; for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) { - if (q >= hi || p < mi && a[p] <= a[q]) { - b[i] = a[p++]; + if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) { + b[i + bo] = a[p++ + ao]; } else { - b[i] = a[q++]; + b[i + bo] = a[q++ + ao]; } } run[++last] = hi; } if ((count & 1) != 0) { for (int i = right, lo = run[count - 1]; --i >= lo; - b[i] = a[i] + b[i + bo] = a[i + ao] ); run[++last] = right; } int[] t = a; a = b; b = t; + int o = ao; ao = bo; bo = o; } } @@ -529,22 +542,18 @@ } /** - * Sorts the specified array. - * - * @param a the array to be sorted - */ - public static void sort(long[] a) { - sort(a, 0, a.length - 1); - } - - /** - * Sorts the specified range of the array. + * Sorts the specified range of the array using the given + * workspace array slice if possible for merging * * @param a the array to be sorted * @param left the index of the first element, inclusive, to be sorted * @param right the index of the last element, inclusive, to be sorted + * @param work a workspace array (slice) + * @param workBase origin of usable space in work array + * @param workLen usable size of work array */ - public static void sort(long[] a, int left, int right) { + static void sort(long[] a, int left, int right, + long[] work, int workBase, int workLen) { // Use Quicksort on small arrays if (right - left < QUICKSORT_THRESHOLD) { sort(a, left, right, true); @@ -587,24 +596,35 @@ } // Check special cases + // Implementation note: variable "right" is increased by 1. if (run[count] == right++) { // The last run contains one element run[++count] = right; } else if (count == 1) { // The array is already sorted return; } - /* - * Create temporary array, which is used for merging. - * Implementation note: variable "right" is increased by 1. - */ - long[] b; byte odd = 0; + // Determine alternation base for merge + byte odd = 0; for (int n = 1; (n <<= 1) < count; odd ^= 1); + // Use or create temporary array b for merging + long[] b; // temp array; alternates with a + int ao, bo; // array offsets from 'left' + int blen = right - left; // space needed for b + if (work == null || workLen < blen || workBase + blen > work.length) { + work = new long[blen]; + workBase = 0; + } if (odd == 0) { - b = a; a = new long[b.length]; - for (int i = left - 1; ++i < right; a[i] = b[i]); + System.arraycopy(a, left, work, workBase, blen); + b = a; + bo = 0; + a = work; + ao = workBase - left; } else { - b = new long[a.length]; + b = work; + ao = 0; + bo = workBase - left; } // Merging @@ -612,21 +632,22 @@ for (int k = (last = 0) + 2; k <= count; k += 2) { int hi = run[k], mi = run[k - 1]; for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) { - if (q >= hi || p < mi && a[p] <= a[q]) { - b[i] = a[p++]; + if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) { + b[i + bo] = a[p++ + ao]; } else { - b[i] = a[q++]; + b[i + bo] = a[q++ + ao]; } } run[++last] = hi; } if ((count & 1) != 0) { for (int i = right, lo = run[count - 1]; --i >= lo; - b[i] = a[i] + b[i + bo] = a[i + ao] ); run[++last] = right; } long[] t = a; a = b; b = t; + int o = ao; ao = bo; bo = o; } } @@ -969,22 +990,18 @@ } /** - * Sorts the specified array. - * - * @param a the array to be sorted - */ - public static void sort(short[] a) { - sort(a, 0, a.length - 1); - } - - /** - * Sorts the specified range of the array. + * Sorts the specified range of the array using the given + * workspace array slice if possible for merging * * @param a the array to be sorted * @param left the index of the first element, inclusive, to be sorted * @param right the index of the last element, inclusive, to be sorted + * @param work a workspace array (slice) + * @param workBase origin of usable space in work array + * @param workLen usable size of work array */ - public static void sort(short[] a, int left, int right) { + static void sort(short[] a, int left, int right, + short[] work, int workBase, int workLen) { // Use counting sort on large arrays if (right - left > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) { int[] count = new int[NUM_SHORT_VALUES]; @@ -1002,7 +1019,7 @@ } while (--s > 0); } } else { // Use Dual-Pivot Quicksort on small arrays - doSort(a, left, right); + doSort(a, left, right, work, workBase, workLen); } } @@ -1015,8 +1032,12 @@ * @param a the array to be sorted * @param left the index of the first element, inclusive, to be sorted * @param right the index of the last element, inclusive, to be sorted + * @param work a workspace array (slice) + * @param workBase origin of usable space in work array + * @param workLen usable size of work array */ - private static void doSort(short[] a, int left, int right) { + private static void doSort(short[] a, int left, int right, + short[] work, int workBase, int workLen) { // Use Quicksort on small arrays if (right - left < QUICKSORT_THRESHOLD) { sort(a, left, right, true); @@ -1059,24 +1080,35 @@ } // Check special cases + // Implementation note: variable "right" is increased by 1. if (run[count] == right++) { // The last run contains one element run[++count] = right; } else if (count == 1) { // The array is already sorted return; } - /* - * Create temporary array, which is used for merging. - * Implementation note: variable "right" is increased by 1. - */ - short[] b; byte odd = 0; + // Determine alternation base for merge + byte odd = 0; for (int n = 1; (n <<= 1) < count; odd ^= 1); + // Use or create temporary array b for merging + short[] b; // temp array; alternates with a + int ao, bo; // array offsets from 'left' + int blen = right - left; // space needed for b + if (work == null || workLen < blen || workBase + blen > work.length) { + work = new short[blen]; + workBase = 0; + } if (odd == 0) { - b = a; a = new short[b.length]; - for (int i = left - 1; ++i < right; a[i] = b[i]); + System.arraycopy(a, left, work, workBase, blen); + b = a; + bo = 0; + a = work; + ao = workBase - left; } else { - b = new short[a.length]; + b = work; + ao = 0; + bo = workBase - left; } // Merging @@ -1084,21 +1116,22 @@ for (int k = (last = 0) + 2; k <= count; k += 2) { int hi = run[k], mi = run[k - 1]; for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) { - if (q >= hi || p < mi && a[p] <= a[q]) { - b[i] = a[p++]; + if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) { + b[i + bo] = a[p++ + ao]; } else { - b[i] = a[q++]; + b[i + bo] = a[q++ + ao]; } } run[++last] = hi; } if ((count & 1) != 0) { for (int i = right, lo = run[count - 1]; --i >= lo; - b[i] = a[i] + b[i + bo] = a[i + ao] ); run[++last] = right; } short[] t = a; a = b; b = t; + int o = ao; ao = bo; bo = o; } } @@ -1441,22 +1474,18 @@ } /** - * Sorts the specified array. - * - * @param a the array to be sorted - */ - public static void sort(char[] a) { - sort(a, 0, a.length - 1); - } - - /** - * Sorts the specified range of the array. + * Sorts the specified range of the array using the given + * workspace array slice if possible for merging * * @param a the array to be sorted * @param left the index of the first element, inclusive, to be sorted * @param right the index of the last element, inclusive, to be sorted + * @param work a workspace array (slice) + * @param workBase origin of usable space in work array + * @param workLen usable size of work array */ - public static void sort(char[] a, int left, int right) { + static void sort(char[] a, int left, int right, + char[] work, int workBase, int workLen) { // Use counting sort on large arrays if (right - left > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) { int[] count = new int[NUM_CHAR_VALUES]; @@ -1474,7 +1503,7 @@ } while (--s > 0); } } else { // Use Dual-Pivot Quicksort on small arrays - doSort(a, left, right); + doSort(a, left, right, work, workBase, workLen); } } @@ -1487,8 +1516,12 @@ * @param a the array to be sorted * @param left the index of the first element, inclusive, to be sorted * @param right the index of the last element, inclusive, to be sorted + * @param work a workspace array (slice) + * @param workBase origin of usable space in work array + * @param workLen usable size of work array */ - private static void doSort(char[] a, int left, int right) { + private static void doSort(char[] a, int left, int right, + char[] work, int workBase, int workLen) { // Use Quicksort on small arrays if (right - left < QUICKSORT_THRESHOLD) { sort(a, left, right, true); @@ -1531,24 +1564,35 @@ } // Check special cases + // Implementation note: variable "right" is increased by 1. if (run[count] == right++) { // The last run contains one element run[++count] = right; } else if (count == 1) { // The array is already sorted return; } - /* - * Create temporary array, which is used for merging. - * Implementation note: variable "right" is increased by 1. - */ - char[] b; byte odd = 0; + // Determine alternation base for merge + byte odd = 0; for (int n = 1; (n <<= 1) < count; odd ^= 1); + // Use or create temporary array b for merging + char[] b; // temp array; alternates with a + int ao, bo; // array offsets from 'left' + int blen = right - left; // space needed for b + if (work == null || workLen < blen || workBase + blen > work.length) { + work = new char[blen]; + workBase = 0; + } if (odd == 0) { - b = a; a = new char[b.length]; - for (int i = left - 1; ++i < right; a[i] = b[i]); + System.arraycopy(a, left, work, workBase, blen); + b = a; + bo = 0; + a = work; + ao = workBase - left; } else { - b = new char[a.length]; + b = work; + ao = 0; + bo = workBase - left; } // Merging @@ -1556,21 +1600,22 @@ for (int k = (last = 0) + 2; k <= count; k += 2) { int hi = run[k], mi = run[k - 1]; for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) { - if (q >= hi || p < mi && a[p] <= a[q]) { - b[i] = a[p++]; + if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) { + b[i + bo] = a[p++ + ao]; } else { - b[i] = a[q++]; + b[i + bo] = a[q++ + ao]; } } run[++last] = hi; } if ((count & 1) != 0) { for (int i = right, lo = run[count - 1]; --i >= lo; - b[i] = a[i] + b[i + bo] = a[i + ao] ); run[++last] = right; } char[] t = a; a = b; b = t; + int o = ao; ao = bo; bo = o; } } @@ -1916,22 +1961,13 @@ private static final int NUM_BYTE_VALUES = 1 << 8; /** - * Sorts the specified array. - * - * @param a the array to be sorted - */ - public static void sort(byte[] a) { - sort(a, 0, a.length - 1); - } - - /** * Sorts the specified range of the array. * * @param a the array to be sorted * @param left the index of the first element, inclusive, to be sorted * @param right the index of the last element, inclusive, to be sorted */ - public static void sort(byte[] a, int left, int right) { + static void sort(byte[] a, int left, int right) { // Use counting sort on large arrays if (right - left > COUNTING_SORT_THRESHOLD_FOR_BYTE) { int[] count = new int[NUM_BYTE_VALUES]; @@ -1963,22 +1999,18 @@ } /** - * Sorts the specified array. - * - * @param a the array to be sorted - */ - public static void sort(float[] a) { - sort(a, 0, a.length - 1); - } - - /** - * Sorts the specified range of the array. + * Sorts the specified range of the array using the given + * workspace array slice if possible for merging * * @param a the array to be sorted * @param left the index of the first element, inclusive, to be sorted * @param right the index of the last element, inclusive, to be sorted + * @param work a workspace array (slice) + * @param workBase origin of usable space in work array + * @param workLen usable size of work array */ - public static void sort(float[] a, int left, int right) { + static void sort(float[] a, int left, int right, + float[] work, int workBase, int workLen) { /* * Phase 1: Move NaNs to the end of the array. */ @@ -1997,7 +2029,7 @@ /* * Phase 2: Sort everything except NaNs (which are already in place). */ - doSort(a, left, right); + doSort(a, left, right, work, workBase, workLen); /* * Phase 3: Place negative zeros before positive zeros. @@ -2064,8 +2096,12 @@ * @param a the array to be sorted * @param left the index of the first element, inclusive, to be sorted * @param right the index of the last element, inclusive, to be sorted + * @param work a workspace array (slice) + * @param workBase origin of usable space in work array + * @param workLen usable size of work array */ - private static void doSort(float[] a, int left, int right) { + private static void doSort(float[] a, int left, int right, + float[] work, int workBase, int workLen) { // Use Quicksort on small arrays if (right - left < QUICKSORT_THRESHOLD) { sort(a, left, right, true); @@ -2108,24 +2144,35 @@ } // Check special cases + // Implementation note: variable "right" is increased by 1. if (run[count] == right++) { // The last run contains one element run[++count] = right; } else if (count == 1) { // The array is already sorted return; } - /* - * Create temporary array, which is used for merging. - * Implementation note: variable "right" is increased by 1. - */ - float[] b; byte odd = 0; + // Determine alternation base for merge + byte odd = 0; for (int n = 1; (n <<= 1) < count; odd ^= 1); + // Use or create temporary array b for merging + float[] b; // temp array; alternates with a + int ao, bo; // array offsets from 'left' + int blen = right - left; // space needed for b + if (work == null || workLen < blen || workBase + blen > work.length) { + work = new float[blen]; + workBase = 0; + } if (odd == 0) { - b = a; a = new float[b.length]; - for (int i = left - 1; ++i < right; a[i] = b[i]); + System.arraycopy(a, left, work, workBase, blen); + b = a; + bo = 0; + a = work; + ao = workBase - left; } else { - b = new float[a.length]; + b = work; + ao = 0; + bo = workBase - left; } // Merging @@ -2133,21 +2180,22 @@ for (int k = (last = 0) + 2; k <= count; k += 2) { int hi = run[k], mi = run[k - 1]; for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) { - if (q >= hi || p < mi && a[p] <= a[q]) { - b[i] = a[p++]; + if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) { + b[i + bo] = a[p++ + ao]; } else { - b[i] = a[q++]; + b[i + bo] = a[q++ + ao]; } } run[++last] = hi; } if ((count & 1) != 0) { for (int i = right, lo = run[count - 1]; --i >= lo; - b[i] = a[i] + b[i + bo] = a[i + ao] ); run[++last] = right; } float[] t = a; a = b; b = t; + int o = ao; ao = bo; bo = o; } } @@ -2490,22 +2538,18 @@ } /** - * Sorts the specified array. - * - * @param a the array to be sorted - */ - public static void sort(double[] a) { - sort(a, 0, a.length - 1); - } - - /** - * Sorts the specified range of the array. + * Sorts the specified range of the array using the given + * workspace array slice if possible for merging * * @param a the array to be sorted * @param left the index of the first element, inclusive, to be sorted * @param right the index of the last element, inclusive, to be sorted + * @param work a workspace array (slice) + * @param workBase origin of usable space in work array + * @param workLen usable size of work array */ - public static void sort(double[] a, int left, int right) { + static void sort(double[] a, int left, int right, + double[] work, int workBase, int workLen) { /* * Phase 1: Move NaNs to the end of the array. */ @@ -2524,7 +2568,7 @@ /* * Phase 2: Sort everything except NaNs (which are already in place). */ - doSort(a, left, right); + doSort(a, left, right, work, workBase, workLen); /* * Phase 3: Place negative zeros before positive zeros. @@ -2591,8 +2635,12 @@ * @param a the array to be sorted * @param left the index of the first element, inclusive, to be sorted * @param right the index of the last element, inclusive, to be sorted + * @param work a workspace array (slice) + * @param workBase origin of usable space in work array + * @param workLen usable size of work array */ - private static void doSort(double[] a, int left, int right) { + private static void doSort(double[] a, int left, int right, + double[] work, int workBase, int workLen) { // Use Quicksort on small arrays if (right - left < QUICKSORT_THRESHOLD) { sort(a, left, right, true); @@ -2635,24 +2683,35 @@ } // Check special cases + // Implementation note: variable "right" is increased by 1. if (run[count] == right++) { // The last run contains one element run[++count] = right; } else if (count == 1) { // The array is already sorted return; } - /* - * Create temporary array, which is used for merging. - * Implementation note: variable "right" is increased by 1. - */ - double[] b; byte odd = 0; + // Determine alternation base for merge + byte odd = 0; for (int n = 1; (n <<= 1) < count; odd ^= 1); + // Use or create temporary array b for merging + double[] b; // temp array; alternates with a + int ao, bo; // array offsets from 'left' + int blen = right - left; // space needed for b + if (work == null || workLen < blen || workBase + blen > work.length) { + work = new double[blen]; + workBase = 0; + } if (odd == 0) { - b = a; a = new double[b.length]; - for (int i = left - 1; ++i < right; a[i] = b[i]); + System.arraycopy(a, left, work, workBase, blen); + b = a; + bo = 0; + a = work; + ao = workBase - left; } else { - b = new double[a.length]; + b = work; + ao = 0; + bo = workBase - left; } // Merging @@ -2660,21 +2719,22 @@ for (int k = (last = 0) + 2; k <= count; k += 2) { int hi = run[k], mi = run[k - 1]; for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) { - if (q >= hi || p < mi && a[p] <= a[q]) { - b[i] = a[p++]; + if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) { + b[i + bo] = a[p++ + ao]; } else { - b[i] = a[q++]; + b[i + bo] = a[q++ + ao]; } } run[++last] = hi; } if ((count & 1) != 0) { for (int i = right, lo = run[count - 1]; --i >= lo; - b[i] = a[i] + b[i + bo] = a[i + ao] ); run[++last] = right; } double[] t = a; a = b; b = t; + int o = ao; ao = bo; bo = o; } }
--- a/src/share/classes/java/util/PropertyResourceBundle.java Thu May 23 09:48:44 2013 -0300 +++ b/src/share/classes/java/util/PropertyResourceBundle.java Wed May 29 13:22:58 2013 -0300 @@ -124,6 +124,8 @@ * to read from. * @throws IOException if an I/O error occurs * @throws NullPointerException if <code>stream</code> is null + * @throws IllegalArgumentException if {@code stream} contains a + * malformed Unicode escape sequence. */ @SuppressWarnings({"unchecked", "rawtypes"}) public PropertyResourceBundle (InputStream stream) throws IOException { @@ -142,6 +144,8 @@ * read from. * @throws IOException if an I/O error occurs * @throws NullPointerException if <code>reader</code> is null + * @throws IllegalArgumentException if a malformed Unicode escape sequence appears + * from {@code reader}. * @since 1.6 */ @SuppressWarnings({"unchecked", "rawtypes"})
--- a/src/share/classes/java/util/TimSort.java Thu May 23 09:48:44 2013 -0300 +++ b/src/share/classes/java/util/TimSort.java Wed May 29 13:22:58 2013 -0300 @@ -111,9 +111,13 @@ private static final int INITIAL_TMP_STORAGE_LENGTH = 256; /** - * Temp storage for merges. + * 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; // Actual runtime type will be Object[], regardless of T + 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 @@ -134,17 +138,31 @@ * * @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<? super T> c) { + private TimSort(T[] a, Comparator<? super T> 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 @@ -164,22 +182,30 @@ } /* - * 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 <T> void sort(T[] a, Comparator<? super T> c) { - sort(a, 0, a.length, c); - } + /** + * 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 <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c, + T[] work, int workBase, int workLen) { + assert c != null && a != null && lo >= 0 && lo <= hi && hi <= a.length; - static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c) { - if (c == null) { - Arrays.sort(a, lo, hi); - return; - } - - rangeCheck(a.length, lo, hi); int nRemaining = hi - lo; if (nRemaining < 2) return; // Arrays of size 0 and 1 are always sorted @@ -196,7 +222,7 @@ * extending short natural runs to minRun elements, and merging runs * to maintain stack invariant. */ - TimSort<T> ts = new TimSort<>(a, c); + TimSort<T> ts = new TimSort<>(a, c, work, workBase, workLen); int minRun = minRunLength(nRemaining); do { // Identify next run @@ -653,11 +679,10 @@ // 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++]; @@ -770,16 +795,17 @@ // 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) { @@ -838,7 +864,7 @@ 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; @@ -870,7 +896,7 @@ } 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); } } @@ -883,7 +909,7 @@ * @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; @@ -899,30 +925,12 @@ 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); - } }
--- a/src/share/classes/java/util/concurrent/ConcurrentHashMap.java Thu May 23 09:48:44 2013 -0300 +++ b/src/share/classes/java/util/concurrent/ConcurrentHashMap.java Wed May 29 13:22:58 2013 -0300 @@ -44,19 +44,19 @@ * adjustable expected concurrency for updates. This class obeys the * same functional specification as {@link java.util.Hashtable}, and * includes versions of methods corresponding to each method of - * <tt>Hashtable</tt>. However, even though all operations are + * {@code Hashtable}. However, even though all operations are * thread-safe, retrieval operations do <em>not</em> entail locking, * and there is <em>not</em> any support for locking the entire table * in a way that prevents all access. This class is fully - * interoperable with <tt>Hashtable</tt> in programs that rely on its + * interoperable with {@code Hashtable} in programs that rely on its * thread safety but not on its synchronization details. * - * <p> Retrieval operations (including <tt>get</tt>) generally do not + * <p> Retrieval operations (including {@code get}) generally do not * block, so may overlap with update operations (including - * <tt>put</tt> and <tt>remove</tt>). Retrievals reflect the results + * {@code put} and {@code remove}). Retrievals reflect the results * of the most recently <em>completed</em> update operations holding - * upon their onset. For aggregate operations such as <tt>putAll</tt> - * and <tt>clear</tt>, concurrent retrievals may reflect insertion or + * upon their onset. For aggregate operations such as {@code putAll} + * and {@code clear}, concurrent retrievals may reflect insertion or * removal of only some entries. Similarly, Iterators and * Enumerations return elements reflecting the state of the hash table * at some point at or since the creation of the iterator/enumeration. @@ -64,8 +64,8 @@ * However, iterators are designed to be used by only one thread at a time. * * <p> The allowed concurrency among update operations is guided by - * the optional <tt>concurrencyLevel</tt> constructor argument - * (default <tt>16</tt>), which is used as a hint for internal sizing. The + * the optional {@code concurrencyLevel} constructor argument + * (default {@code 16}), which is used as a hint for internal sizing. The * table is internally partitioned to try to permit the indicated * number of concurrent updates without contention. Because placement * in hash tables is essentially random, the actual concurrency will @@ -85,8 +85,8 @@ * <em>optional</em> methods of the {@link Map} and {@link Iterator} * interfaces. * - * <p> Like {@link Hashtable} but unlike {@link HashMap}, this class - * does <em>not</em> allow <tt>null</tt> to be used as a key or value. + * <p>Like {@link Hashtable} but unlike {@link HashMap}, this class + * does <em>not</em> allow {@code null} to be used as a key or value. * * <p>This class is a member of the * <a href="{@docRoot}/../technotes/guides/collections/index.html"> @@ -353,8 +353,8 @@ /** * The table is rehashed when its size exceeds this threshold. - * (The value of this field is always <tt>(int)(capacity * - * loadFactor)</tt>.) + * (The value of this field is always {@code (int)(capacity * + * loadFactor)}.) */ transient int threshold; @@ -829,9 +829,9 @@ } /** - * Returns <tt>true</tt> if this map contains no key-value mappings. + * Returns {@code true} if this map contains no key-value mappings. * - * @return <tt>true</tt> if this map contains no key-value mappings + * @return {@code true} if this map contains no key-value mappings */ public boolean isEmpty() { /* @@ -870,8 +870,8 @@ /** * Returns the number of key-value mappings in this map. If the - * map contains more than <tt>Integer.MAX_VALUE</tt> elements, returns - * <tt>Integer.MAX_VALUE</tt>. + * map contains more than {@code Integer.MAX_VALUE} elements, returns + * {@code Integer.MAX_VALUE}. * * @return the number of key-value mappings in this map */ @@ -948,10 +948,10 @@ /** * Tests if the specified object is a key in this table. * - * @param key possible key - * @return <tt>true</tt> if and only if the specified object + * @param key possible key + * @return {@code true} if and only if the specified object * is a key in this table, as determined by the - * <tt>equals</tt> method; <tt>false</tt> otherwise. + * {@code equals} method; {@code false} otherwise * @throws NullPointerException if the specified key is null */ @SuppressWarnings("unchecked") @@ -974,13 +974,12 @@ } /** - * Returns <tt>true</tt> if this map maps one or more keys to the - * specified value. Note: This method requires a full internal - * traversal of the hash table, and so is much slower than - * method <tt>containsKey</tt>. + * Returns {@code true} if this map maps one or more keys to the + * specified value. Note: This method requires a full traversal + * of the map, and so is much slower than method {@code containsKey}. * * @param value value whose presence in this map is to be tested - * @return <tt>true</tt> if this map maps one or more keys to the + * @return {@code true} if this map maps one or more keys to the * specified value * @throws NullPointerException if the specified value is null */ @@ -1033,16 +1032,16 @@ /** * Legacy method testing if some key maps into the specified value * in this table. This method is identical in functionality to - * {@link #containsValue}, and exists solely to ensure + * {@link #containsValue(Object)}, and exists solely to ensure * full compatibility with class {@link java.util.Hashtable}, * which supported this method prior to introduction of the * Java Collections framework. * * @param value a value to search for - * @return <tt>true</tt> if and only if some key maps to the - * <tt>value</tt> argument in this table as - * determined by the <tt>equals</tt> method; - * <tt>false</tt> otherwise + * @return {@code true} if and only if some key maps to the + * {@code value} argument in this table as + * determined by the {@code equals} method; + * {@code false} otherwise * @throws NullPointerException if the specified value is null */ public boolean contains(Object value) { @@ -1053,13 +1052,13 @@ * Maps the specified key to the specified value in this table. * Neither the key nor the value can be null. * - * <p> The value can be retrieved by calling the <tt>get</tt> method + * <p>The value can be retrieved by calling the {@code get} method * with a key that is equal to the original key. * * @param key key with which the specified value is to be associated * @param value value to be associated with the specified key - * @return the previous value associated with <tt>key</tt>, or - * <tt>null</tt> if there was no mapping for <tt>key</tt> + * @return the previous value associated with {@code key}, or + * {@code null} if there was no mapping for {@code key} * @throws NullPointerException if the specified key or value is null */ @SuppressWarnings("unchecked") @@ -1079,7 +1078,7 @@ * {@inheritDoc} * * @return the previous value associated with the specified key, - * or <tt>null</tt> if there was no mapping for the key + * or {@code null} if there was no mapping for the key * @throws NullPointerException if the specified key or value is null */ @SuppressWarnings("unchecked") @@ -1112,8 +1111,8 @@ * This method does nothing if the key is not in the map. * * @param key the key that needs to be removed - * @return the previous value associated with <tt>key</tt>, or - * <tt>null</tt> if there was no mapping for <tt>key</tt> + * @return the previous value associated with {@code key}, or + * {@code null} if there was no mapping for {@code key} * @throws NullPointerException if the specified key is null */ public V remove(Object key) { @@ -1151,7 +1150,7 @@ * {@inheritDoc} * * @return the previous value associated with the specified key, - * or <tt>null</tt> if there was no mapping for the key + * or {@code null} if there was no mapping for the key * @throws NullPointerException if the specified key or value is null */ public V replace(K key, V value) { @@ -1177,14 +1176,14 @@ /** * Returns a {@link Set} view of the keys contained in this map. * The set is backed by the map, so changes to the map are - * reflected in the set, and vice-versa. The set supports element + * reflected in the set, and vice-versa. The set supports element * removal, which removes the corresponding mapping from this map, - * via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, - * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> - * operations. It does not support the <tt>add</tt> or - * <tt>addAll</tt> operations. + * via the {@code Iterator.remove}, {@code Set.remove}, + * {@code removeAll}, {@code retainAll}, and {@code clear} + * operations. It does not support the {@code add} or + * {@code addAll} operations. * - * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator + * <p>The view's {@code iterator} is a "weakly consistent" iterator * that will never throw {@link ConcurrentModificationException}, * and guarantees to traverse elements as they existed upon * construction of the iterator, and may (but is not guaranteed to) @@ -1200,12 +1199,12 @@ * The collection is backed by the map, so changes to the map are * reflected in the collection, and vice-versa. The collection * supports element removal, which removes the corresponding - * mapping from this map, via the <tt>Iterator.remove</tt>, - * <tt>Collection.remove</tt>, <tt>removeAll</tt>, - * <tt>retainAll</tt>, and <tt>clear</tt> operations. It does not - * support the <tt>add</tt> or <tt>addAll</tt> operations. + * mapping from this map, via the {@code Iterator.remove}, + * {@code Collection.remove}, {@code removeAll}, + * {@code retainAll}, and {@code clear} operations. It does not + * support the {@code add} or {@code addAll} operations. * - * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator + * <p>The view's {@code iterator} is a "weakly consistent" iterator * that will never throw {@link ConcurrentModificationException}, * and guarantees to traverse elements as they existed upon * construction of the iterator, and may (but is not guaranteed to) @@ -1221,12 +1220,12 @@ * The set is backed by the map, so changes to the map are * reflected in the set, and vice-versa. The set supports element * removal, which removes the corresponding mapping from the map, - * via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, - * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> - * operations. It does not support the <tt>add</tt> or - * <tt>addAll</tt> operations. + * via the {@code Iterator.remove}, {@code Set.remove}, + * {@code removeAll}, {@code retainAll}, and {@code clear} + * operations. It does not support the {@code add} or + * {@code addAll} operations. * - * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator + * <p>The view's {@code iterator} is a "weakly consistent" iterator * that will never throw {@link ConcurrentModificationException}, * and guarantees to traverse elements as they existed upon * construction of the iterator, and may (but is not guaranteed to) @@ -1440,7 +1439,7 @@ /* ---------------- Serialization Support -------------- */ /** - * Saves the state of the <tt>ConcurrentHashMap</tt> instance to a + * Saves the state of the {@code ConcurrentHashMap} instance to a * stream (i.e., serializes it). * @param s the stream * @serialData @@ -1477,8 +1476,7 @@ } /** - * Reconstitutes the <tt>ConcurrentHashMap</tt> instance from a - * stream (i.e., deserializes it). + * Reconstitutes the instance from a stream (that is, deserializes it). * @param s the stream */ @SuppressWarnings("unchecked")
--- a/src/share/classes/sun/management/Agent.java Thu May 23 09:48:44 2013 -0300 +++ b/src/share/classes/sun/management/Agent.java Wed May 29 13:22:58 2013 -0300 @@ -77,7 +77,7 @@ private static final String SNMP_ADAPTOR_BOOTSTRAP_CLASS_NAME = "sun.management.snmp.AdaptorBootstrap"; - private static final String JDP_DEFAULT_ADDRESS = "239.255.255.225"; + private static final String JDP_DEFAULT_ADDRESS = "224.0.23.178"; private static final int JDP_DEFAULT_PORT = 7095; // The only active agent allowed
--- a/src/share/classes/sun/management/jdp/package-info.java Thu May 23 09:48:44 2013 -0300 +++ b/src/share/classes/sun/management/jdp/package-info.java Wed May 29 13:22:58 2013 -0300 @@ -60,7 +60,7 @@ * * - `INSTANCE_NAME` -- The user-provided name of the running instance * - * The protocol sends packets to 239.255.255.225:7095 by default. + * The protocol sends packets to 224.0.23.178:7095 by default. * * The protocol uses system properties to control it's behaviour: * - `com.sun.management.jdp.port` -- override default port
--- a/src/share/classes/sun/nio/cs/UTF_8.java Thu May 23 09:48:44 2013 -0300 +++ b/src/share/classes/sun/nio/cs/UTF_8.java Wed May 29 13:22:58 2013 -0300 @@ -682,6 +682,11 @@ return encodeBufferLoop(src, dst); } + private byte repl = (byte)'?'; + protected void implReplaceWith(byte[] newReplacement) { + repl = newReplacement[0]; + } + // returns -1 if there is malformed char(s) and the // "action" for malformed input is not REPLACE. public int encode(char[] sa, int sp, int len, byte[] da) { @@ -709,7 +714,7 @@ if (uc < 0) { if (malformedInputAction() != CodingErrorAction.REPLACE) return -1; - da[dp++] = replacement()[0]; + da[dp++] = repl; } else { da[dp++] = (byte)(0xf0 | ((uc >> 18))); da[dp++] = (byte)(0x80 | ((uc >> 12) & 0x3f));
--- a/src/share/classes/sun/nio/cs/ext/DoubleByte.java Thu May 23 09:48:44 2013 -0300 +++ b/src/share/classes/sun/nio/cs/ext/DoubleByte.java Wed May 29 13:22:58 2013 -0300 @@ -610,6 +610,11 @@ return encodeBufferLoop(src, dst); } + protected byte[] repl = replacement(); + protected void implReplaceWith(byte[] newReplacement) { + repl = newReplacement; + } + public int encode(char[] src, int sp, int len, byte[] dst) { int dp = 0; int sl = sp + len; @@ -622,7 +627,6 @@ Character.isLowSurrogate(src[sp])) { sp++; } - byte[] repl = replacement(); dst[dp++] = repl[0]; if (repl.length > 1) dst[dp++] = repl[1]; @@ -877,7 +881,6 @@ Character.isLowSurrogate(src[sp])) { sp++; } - byte[] repl = replacement(); dst[dp++] = repl[0]; if (repl.length > 1) dst[dp++] = repl[1];
--- a/src/share/classes/sun/nio/cs/ext/HKSCS.java Thu May 23 09:48:44 2013 -0300 +++ b/src/share/classes/sun/nio/cs/ext/HKSCS.java Wed May 29 13:22:58 2013 -0300 @@ -356,6 +356,11 @@ return encodeBufferLoop(src, dst); } + private byte[] repl = replacement(); + protected void implReplaceWith(byte[] newReplacement) { + repl = newReplacement; + } + public int encode(char[] src, int sp, int len, byte[] dst) { int dp = 0; int sl = sp + len; @@ -367,7 +372,6 @@ !Character.isLowSurrogate(src[sp]) || (bb = encodeSupp(Character.toCodePoint(c, src[sp++]))) == UNMAPPABLE_ENCODING) { - byte[] repl = replacement(); dst[dp++] = repl[0]; if (repl.length > 1) dst[dp++] = repl[1];
--- a/src/share/classes/sun/security/krb5/internal/ktab/KeyTab.java Thu May 23 09:48:44 2013 -0300 +++ b/src/share/classes/sun/security/krb5/internal/ktab/KeyTab.java Wed May 29 13:22:58 2013 -0300 @@ -78,7 +78,7 @@ private final String tabName; private long lastModified; - private int kt_vno; + private int kt_vno = KRB5_KT_VNO; private Vector<KeyTabEntry> entries = new Vector<>();
--- a/src/share/classes/sun/security/provider/certpath/OCSPResponse.java Thu May 23 09:48:44 2013 -0300 +++ b/src/share/classes/sun/security/provider/certpath/OCSPResponse.java Wed May 29 13:22:58 2013 -0300 @@ -552,7 +552,7 @@ try { Signature respSignature = Signature.getInstance(sigAlgId.getName()); - respSignature.initVerify(cert); + respSignature.initVerify(cert.getPublicKey()); respSignature.update(tbsResponseData); if (respSignature.verify(signature)) {
--- a/src/share/classes/sun/tools/jconsole/AboutDialog.java Thu May 23 09:48:44 2013 -0300 +++ b/src/share/classes/sun/tools/jconsole/AboutDialog.java Wed May 29 13:22:58 2013 -0300 @@ -34,6 +34,7 @@ import javax.swing.border.*; import javax.swing.event.*; +import static sun.misc.Version.jdkMinorVersion; import static java.awt.BorderLayout.*; import static sun.tools.jconsole.Utilities.*; @@ -73,7 +74,7 @@ String jConsoleVersion = Version.getVersion(); String vmName = System.getProperty("java.vm.name"); String vmVersion = System.getProperty("java.vm.version"); - String urlStr = Messages.HELP_ABOUT_DIALOG_USER_GUIDE_LINK_URL; + String urlStr = getOnlineDocUrl(); if (isBrowseSupported()) { urlStr = "<a style='color:#35556b' href=\"" + urlStr + "\">" + urlStr + "</a>"; } @@ -86,8 +87,7 @@ "<html><font color=#"+ colorStr + ">" + Resources.format(Messages.HELP_ABOUT_DIALOG_JCONSOLE_VERSION, jConsoleVersion) + "<p>" + Resources.format(Messages.HELP_ABOUT_DIALOG_JAVA_VERSION, (vmName +", "+ vmVersion)) + - "<p>" + Resources.format(Messages.HELP_ABOUT_DIALOG_USER_GUIDE_LINK, urlStr) + - "</html>"); + "<p>" + urlStr + "</html>"); helpLink.setOpaque(false); helpLink.setEditable(false); helpLink.setForeground(textColor); @@ -153,7 +153,7 @@ } static void browseUserGuide(JConsole jConsole) { - getAboutDialog(jConsole).browse(Messages.HELP_ABOUT_DIALOG_USER_GUIDE_LINK_URL); + getAboutDialog(jConsole).browse(getOnlineDocUrl()); } static boolean isBrowseSupported() { @@ -182,6 +182,12 @@ }; } + private static String getOnlineDocUrl() { + String version = Integer.toString(jdkMinorVersion()); + return Resources.format(Messages.HELP_ABOUT_DIALOG_USER_GUIDE_LINK_URL, + version); + } + private static class TPanel extends JPanel { TPanel(int hgap, int vgap) { super(new BorderLayout(hgap, vgap));
--- a/src/share/classes/sun/tools/jconsole/VMPanel.java Thu May 23 09:48:44 2013 -0300 +++ b/src/share/classes/sun/tools/jconsole/VMPanel.java Wed May 29 13:22:58 2013 -0300 @@ -55,6 +55,7 @@ private VMInternalFrame vmIF = null; private static ArrayList<TabInfo> tabInfos = new ArrayList<TabInfo>(); private boolean wasConnected = false; + private boolean userDisconnected = false; // The everConnected flag keeps track of whether the window can be // closed if the user clicks Cancel after a failed connection attempt. @@ -125,6 +126,7 @@ if (connectedIconBounds != null && (e.getModifiers() & MouseEvent.BUTTON1_MASK) != 0 && connectedIconBounds.contains(e.getPoint())) { if (isConnected()) { + userDisconnected = true; disconnect(); wasConnected = false; } else { @@ -452,6 +454,11 @@ private void vmPanelDied() { disconnect(); + if (userDisconnected) { + userDisconnected = false; + return; + } + JOptionPane optionPane; String msgTitle, msgExplanation, buttonStr;
--- a/src/share/classes/sun/tools/jconsole/resources/messages.properties Thu May 23 09:48:44 2013 -0300 +++ b/src/share/classes/sun/tools/jconsole/resources/messages.properties Wed May 29 13:22:58 2013 -0300 @@ -105,7 +105,7 @@ HELP_ABOUT_DIALOG_MASTHEAD_TITLE=About JConsole HELP_ABOUT_DIALOG_TITLE=JConsole: About HELP_ABOUT_DIALOG_USER_GUIDE_LINK=JConsole &User Guide:<br>{0} -HELP_ABOUT_DIALOG_USER_GUIDE_LINK_URL=http://java.sun.com/javase/6/docs/technotes/guides/management/jconsole.html +HELP_ABOUT_DIALOG_USER_GUIDE_LINK_URL=http://docs.oracle.com/javase/{0}/docs/technotes/guides/management/jconsole.html HELP_MENU_ABOUT_TITLE=&About JConsole HELP_MENU_USER_GUIDE_TITLE=Online &User Guide HELP_MENU_TITLE=&Help
--- a/src/share/classes/sun/tools/jconsole/resources/messages_ja.properties Thu May 23 09:48:44 2013 -0300 +++ b/src/share/classes/sun/tools/jconsole/resources/messages_ja.properties Wed May 29 13:22:58 2013 -0300 @@ -105,7 +105,7 @@ HELP_ABOUT_DIALOG_MASTHEAD_TITLE=JConsole\u306B\u3064\u3044\u3066 HELP_ABOUT_DIALOG_TITLE=JConsole: \u8A73\u7D30 HELP_ABOUT_DIALOG_USER_GUIDE_LINK=JConsole\u30E6\u30FC\u30B6\u30FC\u30FB\u30AC\u30A4\u30C9(&U):<br>{0} -HELP_ABOUT_DIALOG_USER_GUIDE_LINK_URL=http://java.sun.com/javase/6/docs/technotes/guides/management/jconsole.html +HELP_ABOUT_DIALOG_USER_GUIDE_LINK_URL=http://docs.oracle.com/javase/{0}/docs/technotes/guides/management/jconsole.html HELP_MENU_ABOUT_TITLE=JConsole\u306B\u3064\u3044\u3066(&A) HELP_MENU_USER_GUIDE_TITLE=\u30AA\u30F3\u30E9\u30A4\u30F3\u30FB\u30E6\u30FC\u30B6\u30FC\u30FB\u30AC\u30A4\u30C9(&U) HELP_MENU_TITLE=\u30D8\u30EB\u30D7(&H)
--- a/src/share/classes/sun/tools/jconsole/resources/messages_zh_CN.properties Thu May 23 09:48:44 2013 -0300 +++ b/src/share/classes/sun/tools/jconsole/resources/messages_zh_CN.properties Wed May 29 13:22:58 2013 -0300 @@ -105,7 +105,7 @@ HELP_ABOUT_DIALOG_MASTHEAD_TITLE=\u5173\u4E8E JConsole HELP_ABOUT_DIALOG_TITLE=JConsole: \u5173\u4E8E HELP_ABOUT_DIALOG_USER_GUIDE_LINK=JConsole \u7528\u6237\u6307\u5357(&U):<br>{0} -HELP_ABOUT_DIALOG_USER_GUIDE_LINK_URL=http://java.sun.com/javase/6/docs/technotes/guides/management/jconsole.html +HELP_ABOUT_DIALOG_USER_GUIDE_LINK_URL=http://docs.oracle.com/javase/{0}/docs/technotes/guides/management/jconsole.html HELP_MENU_ABOUT_TITLE=\u5173\u4E8E JConsole(&A) HELP_MENU_USER_GUIDE_TITLE=\u8054\u673A\u7528\u6237\u6307\u5357(&U) HELP_MENU_TITLE=\u5E2E\u52A9(&H)
--- a/src/windows/bin/cmdtoargs.c Thu May 23 09:48:44 2013 -0300 +++ b/src/windows/bin/cmdtoargs.c Wed May 29 13:22:58 2013 -0300 @@ -128,7 +128,9 @@ *wildcard = JNI_TRUE; } if (prev == '\\') { - *dest++ = prev; + for (i = 0 ; i < slashes ; i++) { + *dest++ = prev; + } } *dest++ = ch; break; @@ -184,7 +186,7 @@ argv = (StdArg*) JLI_MemRealloc(argv, (nargs+1) * sizeof(StdArg)); argv[nargs].arg = JLI_StringDup(arg); argv[nargs].has_wildcard = wildcard; - + *arg = NULL; nargs++; } while (src != NULL); @@ -602,6 +604,14 @@ v->add("d", FALSE); vectors[i++] = v; + v= new Vector(argv[0], "\\\\?"); + v->add("\\\\?", TRUE); + vectors[i++] = v; + + v= new Vector(argv[0], "\\\\*"); + v->add("\\\\*", TRUE); + vectors[i++] = v; + dotest(vectors); printf("All tests pass [%d]\n", i); doexit(0);
--- a/src/windows/classes/sun/nio/fs/WindowsConstants.java Thu May 23 09:48:44 2013 -0300 +++ b/src/windows/classes/sun/nio/fs/WindowsConstants.java Wed May 29 13:22:58 2013 -0300 @@ -100,6 +100,7 @@ public static final int ERROR_INVALID_LEVEL = 124; public static final int ERROR_DIR_NOT_EMPTY = 145; public static final int ERROR_ALREADY_EXISTS = 183; + public static final int ERROR_MORE_DATA = 234; public static final int ERROR_DIRECTORY = 267; public static final int ERROR_NOTIFY_ENUM_DIR = 1022; public static final int ERROR_NONE_MAPPED = 1332;
--- a/src/windows/classes/sun/nio/fs/WindowsNativeDispatcher.java Thu May 23 09:48:44 2013 -0300 +++ b/src/windows/classes/sun/nio/fs/WindowsNativeDispatcher.java Wed May 29 13:22:58 2013 -0300 @@ -973,19 +973,19 @@ * HANDLE CreateIoCompletionPort ( * HANDLE FileHandle, * HANDLE ExistingCompletionPort, - * DWORD CompletionKey, + * ULONG_PTR CompletionKey, * DWORD NumberOfConcurrentThreads * ) */ static native long CreateIoCompletionPort(long fileHandle, long existingPort, - int completionKey) throws WindowsException; + long completionKey) throws WindowsException; /** * GetQueuedCompletionStatus( * HANDLE CompletionPort, * LPDWORD lpNumberOfBytesTransferred, - * LPDWORD lpCompletionKey, + * PULONG_PTR lpCompletionKey, * LPOVERLAPPED *lpOverlapped, * DWORD dwMilliseconds */ @@ -999,12 +999,12 @@ static class CompletionStatus { private int error; private int bytesTransferred; - private int completionKey; + private long completionKey; private CompletionStatus() { } int error() { return error; } int bytesTransferred() { return bytesTransferred; } - int completionKey() { return completionKey; } + long completionKey() { return completionKey; } } private static native void GetQueuedCompletionStatus0(long completionPort, CompletionStatus status) throws WindowsException; @@ -1013,12 +1013,12 @@ * PostQueuedCompletionStatus( * HANDLE CompletionPort, * DWORD dwNumberOfBytesTransferred, - * DWORD dwCompletionKey, + * ULONG_PTR dwCompletionKey, * LPOVERLAPPED lpOverlapped * ) */ static native void PostQueuedCompletionStatus(long completionPort, - int completionKey) throws WindowsException; + long completionKey) throws WindowsException; /** * ReadDirectoryChangesW(
--- a/src/windows/classes/sun/nio/fs/WindowsWatchService.java Thu May 23 09:48:44 2013 -0300 +++ b/src/windows/classes/sun/nio/fs/WindowsWatchService.java Wed May 29 13:22:58 2013 -0300 @@ -41,6 +41,7 @@ class WindowsWatchService extends AbstractWatchService { + private final static int WAKEUP_COMPLETION_KEY = 0; private final Unsafe unsafe = Unsafe.getUnsafe(); // background thread to service I/O completion port @@ -83,7 +84,7 @@ */ private class WindowsWatchKey extends AbstractWatchKey { // file key (used to detect existing registrations) - private FileKey fileKey; + private final FileKey fileKey; // handle to directory private volatile long handle = INVALID_HANDLE_VALUE; @@ -223,8 +224,7 @@ FileKey other = (FileKey)obj; if (this.volSerialNumber != other.volSerialNumber) return false; if (this.fileIndexHigh != other.fileIndexHigh) return false; - if (this.fileIndexLow != other.fileIndexLow) return false; - return true; + return this.fileIndexLow == other.fileIndexLow; } } @@ -268,6 +268,7 @@ private static final short OFFSETOF_FILENAME = 12; // size of per-directory buffer for events (FIXME - make this configurable) + // Need to be less than 4*16384 = 65536. DWORD align. private static final int CHANGES_BUFFER_SIZE = 16 * 1024; private final WindowsFileSystem fs; @@ -275,27 +276,28 @@ private final long port; // maps completion key to WatchKey - private final Map<Integer,WindowsWatchKey> int2key; + private final Map<Integer,WindowsWatchKey> ck2key; // maps file key to WatchKey private final Map<FileKey,WindowsWatchKey> fk2key; // unique completion key for each directory + // native completion key capacity is 64 bits on Win64. private int lastCompletionKey; Poller(WindowsFileSystem fs, WindowsWatchService watcher, long port) { this.fs = fs; this.watcher = watcher; this.port = port; - this.int2key = new HashMap<Integer,WindowsWatchKey>(); - this.fk2key = new HashMap<FileKey,WindowsWatchKey>(); + this.ck2key = new HashMap<>(); + this.fk2key = new HashMap<>(); this.lastCompletionKey = 0; } @Override void wakeup() throws IOException { try { - PostQueuedCompletionStatus(port, 0); + PostQueuedCompletionStatus(port, WAKEUP_COMPLETION_KEY); } catch (WindowsException x) { throw new IOException(x.getMessage()); } @@ -322,7 +324,6 @@ for (WatchEvent.Modifier modifier: modifiers) { if (modifier == ExtendedWatchEventModifier.FILE_TREE) { watchSubtree = true; - continue; } else { if (modifier == null) return new NullPointerException(); @@ -333,7 +334,7 @@ } // open directory - long handle = -1L; + long handle; try { handle = CreateFile(dir.getPathForWin32Calls(), FILE_LIST_DIRECTORY, @@ -347,7 +348,7 @@ boolean registered = false; try { // read attributes and check file is a directory - WindowsFileAttributes attrs = null; + WindowsFileAttributes attrs; try { attrs = WindowsFileAttributes.readAttributes(handle); } catch (WindowsException x) { @@ -370,9 +371,10 @@ return existing; } - // unique completion key (skip 0) + // Can overflow the int type capacity. + // Skip WAKEUP_COMPLETION_KEY value. int completionKey = ++lastCompletionKey; - if (completionKey == 0) + if (completionKey == WAKEUP_COMPLETION_KEY) completionKey = ++lastCompletionKey; // associate handle with completion port @@ -418,13 +420,13 @@ // 1. remove mapping from old completion key to existing watch key // 2. release existing key's resources (handle/buffer) // 3. re-initialize key with new handle/buffer - int2key.remove(existing.completionKey()); + ck2key.remove(existing.completionKey()); existing.releaseResources(); watchKey = existing.init(handle, events, watchSubtree, buffer, countAddress, overlappedAddress, completionKey); } // map completion map to watch key - int2key.put(completionKey, watchKey); + ck2key.put(completionKey, watchKey); registered = true; return watchKey; @@ -440,7 +442,7 @@ WindowsWatchKey key = (WindowsWatchKey)obj; if (key.isValid()) { fk2key.remove(key.fileKey()); - int2key.remove(key.completionKey()); + ck2key.remove(key.completionKey()); key.invalidate(); } } @@ -449,11 +451,11 @@ @Override void implCloseAll() { // cancel all keys - for (Map.Entry<Integer,WindowsWatchKey> entry: int2key.entrySet()) { + for (Map.Entry<Integer, WindowsWatchKey> entry: ck2key.entrySet()) { entry.getValue().invalidate(); } fk2key.clear(); - int2key.clear(); + ck2key.clear(); // close I/O completion port CloseHandle(port); @@ -517,7 +519,7 @@ @Override public void run() { for (;;) { - CompletionStatus info = null; + CompletionStatus info; try { info = GetQueuedCompletionStatus(port); } catch (WindowsException x) { @@ -527,7 +529,7 @@ } // wakeup - if (info.completionKey() == 0) { + if (info.completionKey() == WAKEUP_COMPLETION_KEY) { boolean shutdown = processRequests(); if (shutdown) { return; @@ -536,7 +538,7 @@ } // map completionKey to get WatchKey - WindowsWatchKey key = int2key.get(info.completionKey()); + WindowsWatchKey key = ck2key.get((int)info.completionKey()); if (key == null) { // We get here when a registration is changed. In that case // the directory is closed which causes an event with the @@ -544,38 +546,44 @@ continue; } - // ReadDirectoryChangesW failed - if (info.error() != 0) { + boolean criticalError = false; + int errorCode = info.error(); + int messageSize = info.bytesTransferred(); + if (errorCode == ERROR_NOTIFY_ENUM_DIR) { // buffer overflow - if (info.error() == ERROR_NOTIFY_ENUM_DIR) { - key.signalEvent(StandardWatchEventKinds.OVERFLOW, null); - } else { - // other error so cancel key - implCancelKey(key); - key.signal(); - } - continue; - } + key.signalEvent(StandardWatchEventKinds.OVERFLOW, null); + } else if (errorCode != 0 && errorCode != ERROR_MORE_DATA) { + // ReadDirectoryChangesW failed + criticalError = true; + } else { + // ERROR_MORE_DATA is a warning about incomplite + // data transfer over TCP/UDP stack. For the case + // [messageSize] is zero in the most of cases. - // process the events - if (info.bytesTransferred() > 0) { - processEvents(key, info.bytesTransferred()); - } else { - // insufficient buffer size - key.signalEvent(StandardWatchEventKinds.OVERFLOW, null); - } + if (messageSize > 0) { + // process non-empty events. + processEvents(key, messageSize); + } else if (errorCode == 0) { + // insufficient buffer size + // not described, but can happen. + key.signalEvent(StandardWatchEventKinds.OVERFLOW, null); + } - // start read for next batch of changes - try { - ReadDirectoryChangesW(key.handle(), - key.buffer().address(), - CHANGES_BUFFER_SIZE, - key.watchSubtree(), - ALL_FILE_NOTIFY_EVENTS, - key.countAddress(), - key.overlappedAddress()); - } catch (WindowsException x) { - // no choice but to cancel key + // start read for next batch of changes + try { + ReadDirectoryChangesW(key.handle(), + key.buffer().address(), + CHANGES_BUFFER_SIZE, + key.watchSubtree(), + ALL_FILE_NOTIFY_EVENTS, + key.countAddress(), + key.overlappedAddress()); + } catch (WindowsException x) { + // no choice but to cancel key + criticalError = true; + } + } + if (criticalError) { implCancelKey(key); key.signal(); }
--- a/src/windows/classes/sun/security/krb5/internal/tools/Ktab.java Thu May 23 09:48:44 2013 -0300 +++ b/src/windows/classes/sun/security/krb5/internal/tools/Ktab.java Wed May 29 13:22:58 2013 -0300 @@ -80,42 +80,24 @@ } else { ktab.processArgs(args); } - try { + ktab.table = KeyTab.getInstance(ktab.name); + if (ktab.table.isMissing() && ktab.action != 'a') { if (ktab.name == null) { - // ktab.admin = new KeyTabAdmin(); // use the default keytab. - ktab.table = KeyTab.getInstance(); - if (ktab.table == null) { - if (ktab.action == 'a') { - ktab.table = KeyTab.create(); - } else { - System.out.println("No default key table exists."); - System.exit(-1); - } - } + System.out.println("No default key table exists."); } else { - if ((ktab.action != 'a') && - !(new File(ktab.name)).exists()) { - System.out.println("Key table " + - ktab.name + " does not exist."); - System.exit(-1); - } else { - ktab.table = KeyTab.getInstance(ktab.name); - } - if (ktab.table == null) { - if (ktab.action == 'a') { - ktab.table = KeyTab.create(ktab.name); - } else { - System.out.println("The format of key table " + - ktab.name + " is incorrect."); - System.exit(-1); - } - } + System.out.println("Key table " + + ktab.name + " does not exist."); } - } catch (RealmException e) { - System.err.println("Error loading key table."); System.exit(-1); - } catch (IOException e) { - System.err.println("Error loading key table."); + } + if (!ktab.table.isValid()) { + if (ktab.name == null) { + System.out.println("The format of the default key table " + + " is incorrect."); + } else { + System.out.println("The format of key table " + + ktab.name + " is incorrect."); + } System.exit(-1); } switch (ktab.action) {
--- a/src/windows/native/java/io/WinNTFileSystem_md.c Thu May 23 09:48:44 2013 -0300 +++ b/src/windows/native/java/io/WinNTFileSystem_md.c Wed May 29 13:22:58 2013 -0300 @@ -1,5 +1,5 @@ /* - * Copyright (c) 2001, 2012, Oracle and/or its affiliates. All rights reserved. + * Copyright (c) 2001, 2013, 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 @@ -199,7 +199,7 @@ /** * If the given attributes are the attributes of a reparse point, then - * read and return the attributes of the final target. + * read and return the attributes of the special cases. */ DWORD getFinalAttributesIfReparsePoint(WCHAR *path, DWORD a) { @@ -213,6 +213,28 @@ return a; } +/** + * Take special cases into account when retrieving the attributes + * of path + */ +DWORD getFinalAttributes(WCHAR *path) +{ + DWORD attr = INVALID_FILE_ATTRIBUTES; + + WIN32_FILE_ATTRIBUTE_DATA wfad; + WIN32_FIND_DATAW wfd; + HANDLE h; + + if (GetFileAttributesExW(path, GetFileExInfoStandard, &wfad)) { + attr = getFinalAttributesIfReparsePoint(path, wfad.dwFileAttributes); + } else if (GetLastError() == ERROR_SHARING_VIOLATION && + (h = FindFirstFileW(path, &wfd)) != INVALID_HANDLE_VALUE) { + attr = getFinalAttributesIfReparsePoint(path, wfd.dwFileAttributes); + CloseHandle(h); + } + return attr; +} + JNIEXPORT jstring JNICALL Java_java_io_WinNTFileSystem_canonicalize0(JNIEnv *env, jobject this, jstring pathname) @@ -337,38 +359,21 @@ Java_java_io_WinNTFileSystem_getBooleanAttributes(JNIEnv *env, jobject this, jobject file) { - jint rv = 0; jint pathlen; - /* both pagefile.sys and hiberfil.sys have length 12 */ -#define SPECIALFILE_NAMELEN 12 - WCHAR *pathbuf = fileToNTPath(env, file, ids.path); - WIN32_FILE_ATTRIBUTE_DATA wfad; if (pathbuf == NULL) return rv; if (!isReservedDeviceNameW(pathbuf)) { - if (GetFileAttributesExW(pathbuf, GetFileExInfoStandard, &wfad)) { - DWORD a = getFinalAttributesIfReparsePoint(pathbuf, wfad.dwFileAttributes); - if (a != INVALID_FILE_ATTRIBUTES) { - rv = (java_io_FileSystem_BA_EXISTS - | ((a & FILE_ATTRIBUTE_DIRECTORY) - ? java_io_FileSystem_BA_DIRECTORY - : java_io_FileSystem_BA_REGULAR) - | ((a & FILE_ATTRIBUTE_HIDDEN) - ? java_io_FileSystem_BA_HIDDEN : 0)); - } - } else { /* pagefile.sys is a special case */ - if (GetLastError() == ERROR_SHARING_VIOLATION) { - rv = java_io_FileSystem_BA_EXISTS; - if ((pathlen = (jint)wcslen(pathbuf)) >= SPECIALFILE_NAMELEN && - (_wcsicmp(pathbuf + pathlen - SPECIALFILE_NAMELEN, - L"pagefile.sys") == 0) || - (_wcsicmp(pathbuf + pathlen - SPECIALFILE_NAMELEN, - L"hiberfil.sys") == 0)) - rv |= java_io_FileSystem_BA_REGULAR; - } + DWORD a = getFinalAttributes(pathbuf); + if (a != INVALID_FILE_ATTRIBUTES) { + rv = (java_io_FileSystem_BA_EXISTS + | ((a & FILE_ATTRIBUTE_DIRECTORY) + ? java_io_FileSystem_BA_DIRECTORY + : java_io_FileSystem_BA_REGULAR) + | ((a & FILE_ATTRIBUTE_HIDDEN) + ? java_io_FileSystem_BA_HIDDEN : 0)); } } free(pathbuf);
--- a/src/windows/native/sun/nio/fs/WindowsNativeDispatcher.c Thu May 23 09:48:44 2013 -0300 +++ b/src/windows/native/sun/nio/fs/WindowsNativeDispatcher.c Wed May 29 13:22:58 2013 -0300 @@ -162,7 +162,7 @@ } completionStatus_error = (*env)->GetFieldID(env, clazz, "error", "I"); completionStatus_bytesTransferred = (*env)->GetFieldID(env, clazz, "bytesTransferred", "I"); - completionStatus_completionKey = (*env)->GetFieldID(env, clazz, "completionKey", "I"); + completionStatus_completionKey = (*env)->GetFieldID(env, clazz, "completionKey", "J"); clazz = (*env)->FindClass(env, "sun/nio/fs/WindowsNativeDispatcher$BackupResult"); if (clazz == NULL) { @@ -1169,12 +1169,11 @@ JNIEXPORT jlong JNICALL Java_sun_nio_fs_WindowsNativeDispatcher_CreateIoCompletionPort(JNIEnv* env, jclass this, - jlong fileHandle, jlong existingPort, jint completionKey) + jlong fileHandle, jlong existingPort, jlong completionKey) { - ULONG_PTR ck = completionKey; HANDLE port = CreateIoCompletionPort((HANDLE)jlong_to_ptr(fileHandle), (HANDLE)jlong_to_ptr(existingPort), - ck, + (ULONG_PTR)completionKey, 0); if (port == NULL) { throwWindowsException(env, GetLastError()); @@ -1203,21 +1202,20 @@ (*env)->SetIntField(env, obj, completionStatus_error, ioResult); (*env)->SetIntField(env, obj, completionStatus_bytesTransferred, (jint)bytesTransferred); - (*env)->SetIntField(env, obj, completionStatus_completionKey, - (jint)completionKey); - + (*env)->SetLongField(env, obj, completionStatus_completionKey, + (jlong)completionKey); } } JNIEXPORT void JNICALL Java_sun_nio_fs_WindowsNativeDispatcher_PostQueuedCompletionStatus(JNIEnv* env, jclass this, - jlong completionPort, jint completionKey) + jlong completionPort, jlong completionKey) { BOOL res; res = PostQueuedCompletionStatus((HANDLE)jlong_to_ptr(completionPort), (DWORD)0, /* dwNumberOfBytesTransferred */ - (DWORD)completionKey, + (ULONG_PTR)completionKey, NULL); /* lpOverlapped */ if (res == 0) { throwWindowsException(env, GetLastError()); @@ -1232,7 +1230,17 @@ BOOL res; BOOL subtree = (watchSubTree == JNI_TRUE) ? TRUE : FALSE; - ((LPOVERLAPPED)jlong_to_ptr(pOverlapped))->hEvent = NULL; + /* Any unused members of [OVERLAPPED] structure should always be initialized to zero + before the structure is used in a function call. + Otherwise, the function may fail and return ERROR_INVALID_PARAMETER. + http://msdn.microsoft.com/en-us/library/windows/desktop/ms684342%28v=vs.85%29.aspx + + The [Offset] and [OffsetHigh] members of this structure are not used. + http://msdn.microsoft.com/en-us/library/windows/desktop/aa365465%28v=vs.85%29.aspx + + [hEvent] should be zero, other fields are the return values. */ + ZeroMemory((LPOVERLAPPED)jlong_to_ptr(pOverlapped), sizeof(OVERLAPPED)); + res = ReadDirectoryChangesW((HANDLE)jlong_to_ptr(hDirectory), (LPVOID)jlong_to_ptr(bufferAddress), (DWORD)bufferLength,
--- a/test/ProblemList.txt Thu May 23 09:48:44 2013 -0300 +++ b/test/ProblemList.txt Wed May 29 13:22:58 2013 -0300 @@ -151,9 +151,6 @@ # 6959636 javax/management/loading/LibraryLoader/LibraryLoaderTest.java windows-all -# 8005472 -com/sun/jmx/remote/NotificationMarshalVersions/TestSerializationMismatch.sh windows-all - ############################################################################ # jdk_math
--- a/test/com/sun/jmx/remote/NotificationMarshalVersions/Client/Client.java Thu May 23 09:48:44 2013 -0300 +++ b/test/com/sun/jmx/remote/NotificationMarshalVersions/Client/Client.java Wed May 29 13:22:58 2013 -0300 @@ -1,47 +1,78 @@ -import java.nio.charset.Charset; -import java.nio.file.FileSystems; -import java.nio.file.Files; -import java.nio.file.Path; -import java.nio.file.StandardWatchEventKinds; -import java.nio.file.WatchEvent; -import java.nio.file.WatchService; +import java.util.Collections; +import java.util.HashSet; +import java.util.Set; +import java.util.concurrent.CountDownLatch; +import java.util.concurrent.TimeUnit; +import java.util.concurrent.atomic.AtomicBoolean; import javax.management.MBeanServerConnection; import javax.management.Notification; import javax.management.NotificationListener; import javax.management.ObjectName; +import javax.management.remote.JMXConnectionNotification; import javax.management.remote.JMXConnector; import javax.management.remote.JMXConnectorFactory; import javax.management.remote.JMXServiceURL; public class Client { - public static void main(String[] argv) throws Exception { - if (argv.length != 1) throw new IllegalArgumentException("Expecting exactly one jmx url argument"); + public static void run(String url) throws Exception { + final int notifEmittedCnt = 10; + final CountDownLatch counter = new CountDownLatch(notifEmittedCnt); + final Set<Long> seqSet = Collections.synchronizedSet(new HashSet<Long>()); + final AtomicBoolean duplNotification = new AtomicBoolean(); - JMXServiceURL serverUrl = new JMXServiceURL(argv[0]); + JMXServiceURL serverUrl = new JMXServiceURL(url); ObjectName name = new ObjectName("test", "foo", "bar"); JMXConnector jmxConnector = JMXConnectorFactory.connect(serverUrl); System.out.println("client connected"); jmxConnector.addConnectionNotificationListener(new NotificationListener() { + @Override public void handleNotification(Notification notification, Object handback) { - System.err.println("no!" + notification); + System.out.println("connection notification: " + notification); + if (!seqSet.add(notification.getSequenceNumber())) { + duplNotification.set(true); + } + if (notification.getType().equals(JMXConnectionNotification.NOTIFS_LOST)) { + long lostNotifs = ((Long)((JMXConnectionNotification)notification).getUserData()).longValue(); + for(int i=0;i<lostNotifs;i++) { + counter.countDown(); + } + } } }, null, null); MBeanServerConnection jmxServer = jmxConnector.getMBeanServerConnection(); jmxServer.addNotificationListener(name, new NotificationListener() { + @Override public void handleNotification(Notification notification, Object handback) { - System.out.println("client got:" + notification); + System.out.println("client got: " + notification); + if (!seqSet.add(notification.getSequenceNumber())) { + duplNotification.set(true); + } + counter.countDown(); } }, null, null); - for(int i=0;i<10;i++) { - System.out.println("client invoking foo"); + System.out.println("client invoking foo (" + notifEmittedCnt + " times)"); + for(int i=0;i<notifEmittedCnt;i++) { + System.out.print("."); jmxServer.invoke(name, "foo", new Object[]{}, new String[]{}); - Thread.sleep(50); } - - System.err.println("happy!"); + System.out.println(); + try { + System.out.println("waiting for " + notifEmittedCnt + " notifications to arrive"); + if (!counter.await(30, TimeUnit.SECONDS)) { + throw new InterruptedException(); + } + if (duplNotification.get()) { + System.out.println("ERROR: received duplicated notifications"); + throw new Error("received duplicated notifications"); + } + System.out.println("\nshutting down client"); + } catch (InterruptedException e) { + System.out.println("ERROR: notification processing thread interrupted"); + throw new Error("notification thread interrupted unexpectedly"); + } } }
--- a/test/com/sun/jmx/remote/NotificationMarshalVersions/Server/Server.java Thu May 23 09:48:44 2013 -0300 +++ b/test/com/sun/jmx/remote/NotificationMarshalVersions/Server/Server.java Wed May 29 13:22:58 2013 -0300 @@ -1,11 +1,6 @@ +import java.io.File; import java.lang.management.ManagementFactory; import java.net.BindException; -import java.nio.charset.Charset; -import java.nio.file.FileSystem; -import java.nio.file.FileSystems; -import java.nio.file.Files; -import java.nio.file.Path; -import java.nio.file.StandardOpenOption; import java.rmi.registry.LocateRegistry; import java.rmi.server.ExportException; import java.util.Random; @@ -16,7 +11,7 @@ import javax.management.remote.JMXServiceURL; public class Server { - public static void main(String[] argv) throws Exception { + public static String start() throws Exception { int serverPort = 12345; ObjectName name = new ObjectName("test", "foo", "bar"); MBeanServer jmxServer = ManagementFactory.getPlatformMBeanServer(); @@ -40,7 +35,7 @@ JMXServiceURL serverUrl = new JMXServiceURL("service:jmx:rmi:///jndi/rmi://localhost:" + serverPort + "/test"); JMXConnectorServer jmxConnector = JMXConnectorServerFactory.newJMXConnectorServer(serverUrl, null, jmxServer); jmxConnector.start(); - System.out.println(serverUrl); - System.err.println("server listening on " + serverUrl); + + return serverUrl.toString(); } }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/com/sun/jmx/remote/NotificationMarshalVersions/TestSerializationMismatch.java Wed May 29 13:22:58 2013 -0300 @@ -0,0 +1,123 @@ + +import java.io.File; +import java.lang.reflect.Method; +import java.net.URL; +import java.net.URLClassLoader; +import java.util.Arrays; + +/** + * @test + * @summary Tests for the RMI unmarshalling errors not to cause silent failure. + * @author Jaroslav Bachorik + * @bug 6937053 8005472 + * + * @run clean TestSerializationMismatch + * @run main TestSerializationMismatch + * + */ +public class TestSerializationMismatch { + static final String clientDir = "Client"; + static final String serverDir = "Server"; + static final String testSrc = System.getProperty("test.src"); + static final String testSrcDir = testSrc != null ? testSrc : "."; + static final String testSrcClientDir = testSrcDir + File.separator + clientDir + File.separator; + static final String testSrcServerDir = testSrcDir + File.separator + serverDir + File.separator; + static final String testClasses = System.getProperty("test.classes"); + static final String testClassesDir = testClasses != null ? testClasses : "."; + static final String testClassesClientDir = testClassesDir + File.separator + clientDir + File.separator; + static final String testClassesServerDir = testClassesDir + File.separator + serverDir + File.separator; + + static final boolean debug = true; + + public static void main(String[] args) throws Exception { + setup(); + + compileClient(); + compileServer(); + + debug("starting server"); + String url = startServer(); + debug("server started and listening on " + url); + debug("starting client"); + startClient(url); + } + + static void setup() { + debug("setting up the output dirs"); + cleanupDir(testClassesClientDir); + cleanupDir(testClassesServerDir); + } + + static void cleanupDir(String path) { + debug("cleaning " + path); + File dir = new File(path); + if (dir.exists()) { + for(File src : dir.listFiles()) { + boolean rslt = src.delete(); + debug((rslt == false ? "not " : "") + "deleted " + src); + } + } else { + dir.mkdirs(); + } + } + + static void compileClient() { + debug("compiling client"); + compile("-d" , testClassesClientDir, + "-sourcepath", testSrcClientDir, + testSrcClientDir + "Client.java", + testSrcClientDir + "ConfigKey.java", + testSrcClientDir + "TestNotification.java"); + } + + static void compileServer() { + debug("compiling server"); + compile("-d" , testClassesServerDir, + "-sourcepath", testSrcServerDir, + testSrcServerDir + "Server.java", + testSrcServerDir + "ConfigKey.java", + testSrcServerDir + "TestNotification.java", + testSrcServerDir + "Ste.java", + testSrcServerDir + "SteMBean.java"); + } + + static String startServer() throws Exception { + ClassLoader serverCL = customCL(testClassesServerDir); + + Class serverClz = serverCL.loadClass("Server"); + Method startMethod = serverClz.getMethod("start"); + return (String)startMethod.invoke(null); + } + + static void startClient(String url) throws Exception { + ClassLoader clientCL = customCL(testClassesClientDir); + + Thread.currentThread().setContextClassLoader(clientCL); + Class clientClz = clientCL.loadClass("Client"); + Method runMethod = clientClz.getMethod("run", String.class); + runMethod.invoke(null, url); + } + + static ClassLoader customCL(String classDir) throws Exception { + return new URLClassLoader( + new URL[]{ + new File(classDir).toURI().toURL() + }, + TestSerializationMismatch.class.getClassLoader() + ); + } + + static void debug(Object message) { + if (debug) { + System.out.println(message); + } + } + + /* run javac <args> */ + static void compile(String... args) { + debug("Running: javac " + Arrays.toString(args)); + if (com.sun.tools.javac.Main.compile(args) != 0) { + throw new RuntimeException("javac failed: args=" + Arrays.toString(args)); + } + } +}
--- a/test/com/sun/jmx/remote/NotificationMarshalVersions/TestSerializationMismatch.sh Thu May 23 09:48:44 2013 -0300 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,93 +0,0 @@ -# -# Copyright (c) 2005, 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 -# @summary Tests for the RMI unmarshalling errors not to cause silent failure. -# @author Jaroslav Bachorik -# @bug 6937053 -# -# @run shell TestSerializationMismatch.sh -# - -#set -x - -#Set appropriate jdk -# - -if [ ! -z "${TESTJAVA}" ] ; then - jdk="$TESTJAVA" -else - echo "--Error: TESTJAVA must be defined as the pathname of a jdk to test." - exit 1 -fi - -SERVER_TESTCLASSES=$TESTCLASSES/Server -CLIENT_TESTCLASSES=$TESTCLASSES/Client - -URL_PATH=$SERVER_TESTCLASSES/jmxurl - -rm $URL_PATH - -mkdir -p $SERVER_TESTCLASSES -mkdir -p $CLIENT_TESTCLASSES - -$TESTJAVA/bin/javac -d $CLIENT_TESTCLASSES $TESTSRC/Client/ConfigKey.java $TESTSRC/Client/TestNotification.java $TESTSRC/Client/Client.java -$TESTJAVA/bin/javac -d $SERVER_TESTCLASSES $TESTSRC/Server/ConfigKey.java $TESTSRC/Server/TestNotification.java $TESTSRC/Server/SteMBean.java $TESTSRC/Server/Ste.java $TESTSRC/Server/Server.java - -startServer() -{ - ($TESTJAVA/bin/java -classpath $SERVER_TESTCLASSES Server) 1>$URL_PATH & - SERVER_PID=$! -} - -runClient() -{ - while true - do - [ -f $URL_PATH ] && break - sleep 2 - done - read JMXURL < $URL_PATH - - HAS_ERRORS=`($TESTJAVA/bin/java -classpath $CLIENT_TESTCLASSES Client $JMXURL) 2>&1 | grep -i "SEVERE: Failed to fetch notification, stopping thread. Error is: java.rmi.UnmarshalException"` -} - -startServer - -runClient - -sleep 1 # wait for notifications to arrive - -kill "$SERVER_PID" - -if [ -z "$HAS_ERRORS" ] -then - echo "Test PASSED" - exit 0 -fi - -echo "Test FAILED" -echo $HAS_ERRORS 1>&2 -exit 1 -
--- a/test/java/io/File/IsHidden.java Thu May 23 09:48:44 2013 -0300 +++ b/test/java/io/File/IsHidden.java Wed May 29 13:22:58 2013 -0300 @@ -1,5 +1,5 @@ /* - * Copyright (c) 1998, 2011, Oracle and/or its affiliates. All rights reserved. + * Copyright (c) 1998, 2013, 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 @@ -46,6 +46,11 @@ Files.getFileAttributeView(f.toPath(), DosFileAttributeView.class).setHidden(value); } + private static void checkHidden(File f) { + if (!f.isHidden()) + throw new RuntimeException(f + " should be hidden"); + } + private static void testWin32() throws Exception { File f = new File(dir, "test"); f.deleteOnExit(); @@ -58,6 +63,11 @@ } ck(".foo", false); ck("foo", false); + + File pagefile = new File("C:\\pagefile.sys"); + File hiberfil = new File("C:\\hiberfil.sys"); + if (pagefile.exists()) checkHidden(pagefile); + if (hiberfil.exists()) checkHidden(hiberfil); } private static void testUnix() throws Exception {
--- a/test/java/io/pathNames/General.java Thu May 23 09:48:44 2013 -0300 +++ b/test/java/io/pathNames/General.java Wed May 29 13:22:58 2013 -0300 @@ -1,5 +1,5 @@ /* - * Copyright (c) 1998, 2000, Oracle and/or its affiliates. All rights reserved. + * Copyright (c) 1998, 2013, 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 @@ -40,7 +40,7 @@ /* Generate a filename unique to this run */ - private static String gensym() { + protected static String gensym() { return "x." + ++gensymCounter; } @@ -127,9 +127,9 @@ } for (int i = 0; i < dl.length; i++) { File f = new File(d, dl[i]); - if (f.isDirectory() && f.canRead()) { + if (f.isDirectory()) { String[] dl2 = f.list(); - if (dl2.length >= 250) { + if (dl2 == null || dl2.length >= 250) { /* Heuristic to avoid scanning huge directories */ continue; } @@ -277,8 +277,8 @@ { check(ans, ask + slash); checkNames(depth, create, - ans.endsWith(File.separator) ? ans : ans + File.separator, - ask + slash); + ans, + ask); } @@ -308,13 +308,16 @@ String ans, String ask) throws Exception { + ans = ans.endsWith(File.separator) ? ans : ans + File.separator; + ask = ask.endsWith(File.separator) ? ask : ask + File.separator; + int d = depth - 1; File f = new File(ans); String n; /* Normal name */ if (f.exists()) { - if (f.isDirectory() && f.canRead()) { + if (f.isDirectory() && f.list() != null) { if ((n = findSomeFile(ans, create)) != null) checkSlashes(d, create, ans + n, ask + n); if ((n = findSomeDir(ans, create)) != null)
--- a/test/java/io/pathNames/GeneralWin32.java Thu May 23 09:48:44 2013 -0300 +++ b/test/java/io/pathNames/GeneralWin32.java Wed May 29 13:22:58 2013 -0300 @@ -1,5 +1,5 @@ /* - * Copyright (c) 1998, 2010, Oracle and/or its affiliates. All rights reserved. + * Copyright (c) 1998, 2013, 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 @@ -22,7 +22,7 @@ */ /* @test - @bug 4032066 4039597 4046914 4054511 4065189 4109131 4875229 6983520 + @bug 4032066 4039597 4046914 4054511 4065189 4109131 4875229 6983520 8009258 @summary General exhaustive test of win32 pathname handling @author Mark Reinhold @@ -31,8 +31,6 @@ */ import java.io.*; -import java.util.*; - public class GeneralWin32 extends General { @@ -49,25 +47,29 @@ private static final String EXISTENT_UNC_SHARE = "pcdist"; private static final String NONEXISTENT_UNC_HOST = "non-existent-unc-host"; private static final String NONEXISTENT_UNC_SHARE = "bogus-share"; - + private static final int DEPTH = 2; + private static String baseDir = null; + private static String userDir = null; /* Pathnames relative to working directory */ - private static void checkCaseLookup(String ud) throws IOException { + private static void checkCaseLookup() throws IOException { /* Use long names here to avoid 8.3 format, which Samba servers often force to lowercase */ - File d = new File("XyZzY0123", "FOO_bar_BAZ"); - File f = new File(d, "GLORPified"); + String relative = baseDir.substring(userDir.length() + 1); + File d1 = new File(relative, "XyZzY0123"); + File d2 = new File(d1, "FOO_bar_BAZ"); + File f = new File(d2, "GLORPified"); if (!f.exists()) { - if (!d.exists()) { - if (!d.mkdirs()) { - throw new RuntimeException("Can't create directory " + d); + if (!d2.exists()) { + if (!d2.mkdirs()) { + throw new RuntimeException("Can't create directory " + d2); } } OutputStream o = new FileOutputStream(f); o.close(); } - File f2 = new File(d.getParent(), "mumble"); /* For later ud tests */ + File f2 = new File(d2.getParent(), "mumble"); /* For later ud tests */ if (!f2.exists()) { OutputStream o = new FileOutputStream(f2); o.close(); @@ -75,11 +77,11 @@ /* Computing the canonical path of a Win32 file should expose the true case of filenames, rather than just using the input case */ - File y = new File(ud, f.getPath()); + File y = new File(userDir, f.getPath()); String ans = y.getPath(); - check(ans, "XyZzY0123\\FOO_bar_BAZ\\GLORPified"); - check(ans, "xyzzy0123\\foo_bar_baz\\glorpified"); - check(ans, "XYZZY0123\\FOO_BAR_BAZ\\GLORPIFIED"); + check(ans, relative + "\\" + "XyZzY0123\\FOO_bar_BAZ\\GLORPified"); + check(ans, relative + "\\" + "xyzzy0123\\foo_bar_baz\\glorpified"); + check(ans, relative + "\\" + "XYZZY0123\\FOO_BAR_BAZ\\GLORPIFIED"); } private static void checkWild(File f) throws Exception { @@ -91,18 +93,18 @@ throw new Exception("Wildcard path not rejected: " + f); } - private static void checkWildCards(String ud) throws Exception { - File d = new File(ud).getCanonicalFile(); + private static void checkWildCards() throws Exception { + File d = new File(baseDir).getCanonicalFile(); checkWild(new File(d, "*.*")); checkWild(new File(d, "*.???")); checkWild(new File(new File(d, "*.*"), "foo")); } private static void checkRelativePaths() throws Exception { - String ud = System.getProperty("user.dir").replace('/', '\\'); - checkCaseLookup(ud); - checkWildCards(ud); - checkNames(3, true, ud + "\\", ""); + checkCaseLookup(); + checkWildCards(); + String relative = baseDir.substring(userDir.length() + 1); + checkNames(3, true, baseDir.toString(), relative); } @@ -134,7 +136,8 @@ String ans = exists ? df.getAbsolutePath() : d; if (!ans.endsWith("\\")) ans = ans + "\\"; - checkNames(depth, false, ans, d); + String relative = baseDir.substring(userDir.length() + 1); + checkNames(depth, false, ans + relative, d + relative); } private static void checkDrivePaths() throws Exception { @@ -149,7 +152,7 @@ String s = ("\\\\" + NONEXISTENT_UNC_HOST + "\\" + NONEXISTENT_UNC_SHARE); ensureNon(s); - checkSlashes(2, false, s, s); + checkSlashes(DEPTH, false, s, s); s = "\\\\" + EXISTENT_UNC_HOST + "\\" + EXISTENT_UNC_SHARE; if (!(new File(s)).exists()) { @@ -158,7 +161,7 @@ return; } - checkSlashes(2, false, s, s); + checkSlashes(DEPTH, false, s, s); } @@ -168,9 +171,33 @@ return; } if (args.length > 0) debug = true; + userDir = System.getProperty("user.dir"); + baseDir = initTestData(6); checkRelativePaths(); checkDrivePaths(); checkUncPaths(); } + private static String initTestData(int maxDepth) throws IOException { + File parent = new File(System.getProperty("user.dir")); + String baseDir = null; + maxDepth = maxDepth < DEPTH + 2 ? DEPTH + 2 : maxDepth; + for (int i = 0; i < maxDepth; i ++) { + File dir1 = new File(parent, gensym()); + dir1.mkdir(); + if (i != 0) { + File dir2 = new File(parent, gensym()); + dir2.mkdir(); + File f1 = new File(parent, gensym()); + f1.createNewFile(); + File f2 = new File(parent, gensym()); + f2.createNewFile(); + } + if (i == DEPTH + 1) { + baseDir = dir1.getAbsolutePath(); + } + parent = dir1; + } + return baseDir; + } }
--- a/test/java/lang/management/MemoryMXBean/ResetPeakMemoryUsage.java Thu May 23 09:48:44 2013 -0300 +++ b/test/java/lang/management/MemoryMXBean/ResetPeakMemoryUsage.java Wed May 29 13:22:58 2013 -0300 @@ -22,13 +22,18 @@ */ /* + * The -XX:MarkSweepAlwaysCompactCount=1 argument below makes sure serial gc + * compacts the heap at every full gc so that the usage is correctly updated. + */ + +/* * @test * @bug 4892507 * @summary Basic Test for MemoryPool.resetPeakUsage() * @author Mandy Chung * * @build ResetPeakMemoryUsage MemoryUtil - * @run main/othervm -XX:+UseSerialGC -Xmn8m ResetPeakMemoryUsage + * @run main/othervm -XX:+UseSerialGC -XX:MarkSweepAlwaysCompactCount=1 -Xmn8m ResetPeakMemoryUsage * @run main/othervm -XX:+UseConcMarkSweepGC -Xmn8m ResetPeakMemoryUsage * @run main/othervm -XX:+UseParallelGC -Xmn8m ResetPeakMemoryUsage * @run main/othervm -XX:+UseG1GC -Xmn8m -XX:G1HeapRegionSize=1m ResetPeakMemoryUsage
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/java/lang/ref/OOMEInReferenceHandler.java Wed May 29 13:22:58 2013 -0300 @@ -0,0 +1,112 @@ +/* + * Copyright (c) 2013, 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 7038914 + * @summary Verify that the reference handler does not die after an OOME allocating the InterruptedException object + * @run main/othervm -Xmx16M -XX:-UseTLAB OOMEInReferenceHandler + * @author peter.levart@gmail.com + */ + +import java.lang.ref.*; + +public class OOMEInReferenceHandler { + static Object[] fillHeap() { + Object[] first = null, last = null; + int size = 1 << 20; + while (size > 0) { + try { + Object[] array = new Object[size]; + if (first == null) { + first = array; + } else { + last[0] = array; + } + last = array; + } catch (OutOfMemoryError oome) { + size = size >>> 1; + } + } + return first; + } + + public static void main(String[] args) throws Exception { + // preinitialize the InterruptedException class so that the reference handler + // does not die due to OOME when loading the class if it is the first use + InterruptedException ie = new InterruptedException("dummy"); + + ThreadGroup tg = Thread.currentThread().getThreadGroup(); + for ( + ThreadGroup tgn = tg; + tgn != null; + tg = tgn, tgn = tg.getParent() + ) + ; + + Thread[] threads = new Thread[tg.activeCount()]; + Thread referenceHandlerThread = null; + int n = tg.enumerate(threads); + for (int i = 0; i < n; i++) { + if ("Reference Handler".equals(threads[i].getName())) { + referenceHandlerThread = threads[i]; + } + } + + if (referenceHandlerThread == null) { + throw new IllegalStateException("Couldn't find Reference Handler thread."); + } + + ReferenceQueue<Object> refQueue = new ReferenceQueue<>(); + Object referent = new Object(); + WeakReference<Object> weakRef = new WeakReference<>(referent, refQueue); + + Object waste = fillHeap(); + + referenceHandlerThread.interrupt(); + + // allow referenceHandlerThread some time to throw OOME + Thread.sleep(500L); + + // release waste & referent + waste = null; + referent = null; + + // wait at most 10 seconds for success or failure + for (int i = 0; i < 20; i++) { + if (refQueue.poll() != null) { + // Reference Handler thread still working -> success + return; + } + System.gc(); + Thread.sleep(500L); // wait a little to allow GC to do it's work before allocating objects + if (!referenceHandlerThread.isAlive()) { + // Reference Handler thread died -> failure + throw new Exception("Reference Handler thread died."); + } + } + + // no sure answer after 10 seconds + throw new IllegalStateException("Reference Handler thread stuck."); + } +}
--- a/test/java/util/Arrays/ParallelSorting.java Thu May 23 09:48:44 2013 -0300 +++ b/test/java/util/Arrays/ParallelSorting.java Wed May 29 13:22:58 2013 -0300 @@ -50,11 +50,11 @@ // Array lengths used in a long run (default) private static final int[] LONG_RUN_LENGTHS = { - 1, 2, 3, 5, 8, 13, 21, 34, 55, 100, 1000, 10000, 100000, 1000000 }; + 1000, 10000, 100000, 1000000 }; // Array lengths used in a short run private static final int[] SHORT_RUN_LENGTHS = { - 1, 2, 3, 21, 55, 1000, 10000 }; + 5000, 9000, 10000, 12000 }; // Random initial values used in a long run (default) private static final long[] LONG_RUN_RANDOMS = { 666, 0xC0FFEE, 999 };
--- a/test/sun/management/jdp/JdpTest.sh Thu May 23 09:48:44 2013 -0300 +++ b/test/sun/management/jdp/JdpTest.sh Wed May 29 13:22:58 2013 -0300 @@ -2,17 +2,17 @@ # Copyright (c) 2011, 2012, 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. @@ -22,8 +22,8 @@ # questions. # @test -# @bug 7169888 -# @compile -XDignore.symbol.file JdpUnitTest.java JdpClient.java JdpDoSomething.java +# @bug 7169888 +# @compile -XDignore.symbol.file JdpUnitTest.java JdpClient.java JdpDoSomething.java # @run shell JdpTest.sh --jtreg --no-compile # @summary No word Failed expected in the test output @@ -44,17 +44,20 @@ _logname=".classes/output.txt" _last_pid="" +_ip="224.0.23.178" +_port="7095" +_jmxport="4545" _do_compile(){ # If the test run without JTReg, we have to compile it by our self # Under JTReg see @compile statement above - # sun.* packages is not included to symbol file lib/ct.sym so we have + # sun.* packages is not included to symbol file lib/ct.sym so we have # to ignore it if [ ! -d ${_testclasses} ] then mkdir -p ${_testclasses} - fi + fi rm -f ${_testclasses}/*.class @@ -64,11 +67,11 @@ JdpDoSomething.java \ JdpClient.java - + if [ ! -f ${_testclasses}/JdpDoSomething.class -o ! -f ${_testclasses}/JdpClient.class -o ! -f ${_testclasses}/JdpUnitTest.class ] then echo "ERROR: Can't compile" - exit -1 + exit 255 fi } @@ -84,10 +87,10 @@ npid=`_get_pid` if [ "${npid}" = "" ] then - echo "ERROR: Test app not started" + echo "ERROR: Test app not started. Please check machine resources before filing a bug." if [ "${_jtreg}" = "yes" ] then - exit -1 + exit 255 fi fi } @@ -100,53 +103,53 @@ rm ${_lockFileName} # wait until VM is actually shuts down - while true + while true do npid=`_get_pid` - if [ "${npid}" = "" ] + if [ "${npid}" = "" ] then break fi sleep 1 - done + done } - + _testme(){ ${TESTJAVA}/bin/java \ -cp ${_testclasses} \ $* \ - -Dcom.sun.management.jdp.port=7095 \ - -Dcom.sun.management.jdp.address=239.255.255.225 \ - JdpClient + -Dcom.sun.management.jdp.port=${_port} \ + -Dcom.sun.management.jdp.address=${_ip} \ + JdpClient -} +} _jcmd(){ ${TESTJAVA}/bin/jcmd JdpDoSomething $* > /dev/null 2>/dev/null -} +} _echo(){ echo "$*" echo "$*" >> ${_logname} } - + # ============= TESTS ====================================== - + test_01(){ - - _echo "**** Test one ****" + + _echo "**** Test one ****" _app_start JdpUnitTest \ - -Dcom.sun.management.jdp.port=7095 \ - -Dcom.sun.management.jdp.address=239.255.255.225 \ + -Dcom.sun.management.jdp.port=${_port} \ + -Dcom.sun.management.jdp.address=${_ip} \ -Dcom.sun.management.jdp.pause=5 res=`_testme` - case "${res}" in - OK*) + case "${res}" in + OK*) _echo "Passed" ;; *) @@ -155,24 +158,24 @@ esac _app_stop -} +} test_02(){ - - _echo "**** Test two ****" + + _echo "**** Test two ****" _app_start JdpDoSomething \ - -Dcom.sun.management.jdp.port=7095 \ - -Dcom.sun.management.jdp.address=239.255.255.225 \ + -Dcom.sun.management.jdp.port=${_port} \ + -Dcom.sun.management.jdp.address=${_ip} \ -Dcom.sun.management.jdp.pause=5 \ - -Dcom.sun.management.jmxremote.port=4545 \ + -Dcom.sun.management.jmxremote.port=${_jmxport} \ -Dcom.sun.management.jmxremote.authenticate=false \ -Dcom.sun.management.jmxremote.ssl=false res=`_testme` - case "${res}" in - OK*) + case "${res}" in + OK*) _echo "Passed" ;; *) @@ -181,26 +184,26 @@ esac _app_stop -} +} test_03(){ - + _echo "**** Test three ****" _app_start JdpDoSomething - + _jcmd ManagementAgent.start\ - jdp.port=7095 \ - jdp.address=239.255.255.225 \ + jdp.port=${_port} \ + jdp.address=${_ip} \ jdp.pause=5 \ - jmxremote.port=4545 \ + jmxremote.port=${_jmxport} \ jmxremote.authenticate=false \ jmxremote.ssl=false res=`_testme` - case "${res}" in - OK*) + case "${res}" in + OK*) _echo "Passed" ;; *) @@ -209,7 +212,7 @@ esac _app_stop -} +} test_04(){ @@ -217,7 +220,7 @@ _app_start JdpDoSomething \ -Dcom.sun.management.jmxremote.autodiscovery=true \ - -Dcom.sun.management.jmxremote.port=4545 \ + -Dcom.sun.management.jmxremote.port=${_jmxport} \ -Dcom.sun.management.jmxremote.authenticate=false \ -Dcom.sun.management.jmxremote.ssl=false @@ -243,7 +246,7 @@ _jcmd ManagementAgent.start\ jmxremote.autodiscovery=true \ - jmxremote.port=4545 \ + jmxremote.port=${_jmxport} \ jmxremote.authenticate=false \ jmxremote.ssl=false @@ -279,20 +282,20 @@ #------------------------------------------------------------------------------ -# reading parameters +# reading parameters -for parm in "$@" +for parm in "$@" do case $parm in --verbose) _verbose=yes ;; --jtreg) _jtreg=yes ;; --no-compile) _compile=no ;; --testsuite=*) _testsuite=`_echo $parm | sed "s,^--.*=\(.*\),\1,"` ;; - *) - echo "Undefined parameter $parm. Try --help for help" - exit + *) + echo "Undefined parameter $parm. Try --help for help" + exit ;; - esac + esac done if [ "${_compile}" = "yes" ] @@ -325,11 +328,11 @@ cat ${_testsrc}/policy.tpl | \ sed -e "s,@_TESTCLASSES@,${_testclasses},g" -e "s,@TESTJAVA@,${TESTJAVA},g" \ > ${_policyname} - + fi - + # Local mode tests for i in `echo ${_testsuite} | sed -e "s/,/ /g"` do - test_${i} + test_${i} done
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/sun/security/krb5/tools/KtabZero.java Wed May 29 13:22:58 2013 -0300 @@ -0,0 +1,78 @@ +/* + * Copyright (c) 2013, 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. + */ + +import sun.security.krb5.internal.ktab.KeyTab; +import sun.security.krb5.internal.ktab.KeyTabConstants; + +import java.io.File; +import java.lang.reflect.Field; +import java.nio.file.Files; +import java.nio.file.Paths; + +/* + * @test + * @bug 8014196 + * @summary ktab creates a file with zero kt_vno + */ +public class KtabZero { + + static final String NAME = "k.tab"; + + public static void main(String[] args) throws Exception { + + // 0. Non-existing keytab + Files.deleteIfExists(Paths.get(NAME)); + check(true); + + // 1. Create with KeyTab + Files.deleteIfExists(Paths.get(NAME)); + KeyTab.getInstance(NAME).save(); + check(false); + + // 2. Create with the tool + Files.deleteIfExists(Paths.get(NAME)); + try { + Class ktab = Class.forName("sun.security.krb5.internal.tools.Ktab"); + ktab.getDeclaredMethod("main", String[].class).invoke(null, + (Object)(("-k " + NAME + " -a me@HERE pass").split(" "))); + } catch (ClassNotFoundException cnfe) { + // Only Windows has ktab tool + System.out.println("No ktab tool here. Ignored."); + return; + } + check(false); + } + + // Checks existence as well as kt-vno + static void check(boolean showBeMissing) throws Exception { + KeyTab kt = KeyTab.getInstance(NAME); + if (kt.isMissing() != showBeMissing) { + throw new Exception("isMissing is not " + showBeMissing); + } + Field f = KeyTab.class.getDeclaredField("kt_vno"); + f.setAccessible(true); + if (f.getInt(kt) != KeyTabConstants.KRB5_KT_VNO) { + throw new Exception("kt_vno is " + f.getInt(kt)); + } + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/sun/security/krb5/tools/ktzero.sh Wed May 29 13:22:58 2013 -0300 @@ -0,0 +1,74 @@ +# +# Copyright (c) 2013, 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 8014196 +# @summary ktab creates a file with zero kt_vno +# @run shell ktzero.sh +# + +if [ "${TESTJAVA}" = "" ] ; then + JAVAC_CMD=`which javac` + TESTJAVA=`dirname $JAVAC_CMD`/.. +fi + +if [ "${TESTSRC}" = "" ] ; then + TESTSRC="." +fi + +OS=`uname -s` +case "$OS" in + CYGWIN* ) + FS="/" + ;; + Windows_* ) + FS="\\" + ;; + * ) + FS="/" + echo "Unsupported system!" + exit 0; + ;; +esac + +KEYTAB=ktzero.tmp + +rm $KEYTAB 2> /dev/null +KTAB="${TESTJAVA}${FS}bin${FS}ktab -k $KEYTAB" + +# Listing non-existing ktab should fail +$KTAB -l && exit 1 + +# Can add to non-existing ktab +$KTAB -a me@LOCAL mine || exit 2 + +# Now can be listed +$KTAB -l || exit 3 + +echo ABCDEFG > $KEYTAB + +# Invalid keytab should fail for all commands +$KTAB -l && exit 4 +$KTAB -a me@LOCAL mine && exit 2 + +exit 0
--- a/test/tools/launcher/Arrrghs.java Thu May 23 09:48:44 2013 -0300 +++ b/test/tools/launcher/Arrrghs.java Wed May 29 13:22:58 2013 -0300 @@ -24,7 +24,7 @@ /** * @test * @bug 5030233 6214916 6356475 6571029 6684582 6742159 4459600 6758881 6753938 - * 6894719 6968053 7151434 7146424 + * 6894719 6968053 7151434 7146424 8007333 * @summary Argument parsing validation. * @compile -XDignore.symbol.file Arrrghs.java * @run main/othervm Arrrghs @@ -310,6 +310,20 @@ checkArgumentParsing("..\\..\\", "..\\..\\"); checkArgumentParsing("../../", "../../"); checkArgumentParsing("a b\\ c", "a", "b\\", "c"); + // 2 back-slashes + checkArgumentParsing("\\\\?", "\\\\?"); + // 3 back-slashes + checkArgumentParsing("\\\\\\?", "\\\\\\?"); + // 4 back-slashes + checkArgumentParsing("\\\\\\\\?", "\\\\\\\\?"); + // 5 back-slashes + checkArgumentParsing("\\\\\\\\\\?", "\\\\\\\\\\?"); + // 6 back-slashes + checkArgumentParsing("\\\\\\\\\\\\?", "\\\\\\\\\\\\?"); + + // more treatment of mixed slashes + checkArgumentParsing("f1/ f3\\ f4/", "f1/", "f3\\", "f4/"); + checkArgumentParsing("f1/ f2\' ' f3/ f4/", "f1/", "f2\'", "'", "f3/", "f4/"); } private void initEmptyDir(File emptyDir) throws IOException {