diff options
Diffstat (limited to 'luni/src/main/java')
19 files changed, 2077 insertions, 718 deletions
diff --git a/luni/src/main/java/java/lang/VMThread.java b/luni/src/main/java/java/lang/VMThread.java index 8e789cb..6d7bef0 100644 --- a/luni/src/main/java/java/lang/VMThread.java +++ b/luni/src/main/java/java/lang/VMThread.java @@ -16,6 +16,9 @@ package java.lang; +import java.util.logging.Logger; +import java.util.logging.Level; + class VMThread { Thread thread; @@ -47,20 +50,25 @@ class VMThread VMThread.create(thread, stacksize); } + private static final String UNSUPPORTED_THREAD_METHOD + = "Deprecated Thread methods are not supported."; + /** * Suspends the Thread. */ + @SuppressWarnings("ThrowableInstanceNeverThrown") void suspend() { - throw new UnsupportedOperationException( - "Deprecated Thread methods are not supported."); + Logger.global.log(Level.SEVERE, UNSUPPORTED_THREAD_METHOD, + new UnsupportedOperationException()); } /** * Resumes the Thread, assuming it is suspended. */ + @SuppressWarnings("ThrowableInstanceNeverThrown") void resume() { - throw new UnsupportedOperationException( - "Deprecated Thread methods are not supported."); + Logger.global.log(Level.SEVERE, UNSUPPORTED_THREAD_METHOD, + new UnsupportedOperationException()); } /** @@ -72,9 +80,10 @@ class VMThread /** * Stops the Thread, passing it a Throwable (which might be ThreadDeath). */ + @SuppressWarnings("ThrowableInstanceNeverThrown") void stop(Throwable throwable) { - throw new UnsupportedOperationException( - "Deprecated Thread methods are not supported."); + Logger.global.log(Level.SEVERE, UNSUPPORTED_THREAD_METHOD, + new UnsupportedOperationException()); } native void setPriority(int newPriority); diff --git a/luni/src/main/java/java/lang/reflect/AnnotatedElement.java b/luni/src/main/java/java/lang/reflect/AnnotatedElement.java index 23093c5..1f081b9 100644 --- a/luni/src/main/java/java/lang/reflect/AnnotatedElement.java +++ b/luni/src/main/java/java/lang/reflect/AnnotatedElement.java @@ -22,7 +22,6 @@ import java.lang.annotation.Annotation; /** * This interface provides reflective access to annotation information. * - * @since 1.5 * @since Android 1.0 */ public interface AnnotatedElement { diff --git a/luni/src/main/java/java/lang/reflect/GenericArrayType.java b/luni/src/main/java/java/lang/reflect/GenericArrayType.java index d47d7f2..81fb39f 100644 --- a/luni/src/main/java/java/lang/reflect/GenericArrayType.java +++ b/luni/src/main/java/java/lang/reflect/GenericArrayType.java @@ -21,7 +21,6 @@ package java.lang.reflect; * This interface represents an array type with a component type that is either * a parameterized type or a type variable. * - * @since 1.5 * @since Android 1.0 */ public interface GenericArrayType extends Type { diff --git a/luni/src/main/java/java/lang/reflect/GenericDeclaration.java b/luni/src/main/java/java/lang/reflect/GenericDeclaration.java index 6f2dcb3..c7cedcf 100644 --- a/luni/src/main/java/java/lang/reflect/GenericDeclaration.java +++ b/luni/src/main/java/java/lang/reflect/GenericDeclaration.java @@ -19,7 +19,6 @@ package java.lang.reflect; /** * Common interface for language constructs that declare type parameters. * - * @since 1.5 * @since Android 1.0 */ public interface GenericDeclaration { diff --git a/luni/src/main/java/java/lang/reflect/GenericSignatureFormatError.java b/luni/src/main/java/java/lang/reflect/GenericSignatureFormatError.java index 5691565..bb901fd 100644 --- a/luni/src/main/java/java/lang/reflect/GenericSignatureFormatError.java +++ b/luni/src/main/java/java/lang/reflect/GenericSignatureFormatError.java @@ -21,7 +21,6 @@ package java.lang.reflect; * Indicates that a malformed signature has been encountered via a reflective * method. * - * @since 1.5 * @since Android 1.0 */ public class GenericSignatureFormatError extends ClassFormatError { diff --git a/luni/src/main/java/java/lang/reflect/MalformedParameterizedTypeException.java b/luni/src/main/java/java/lang/reflect/MalformedParameterizedTypeException.java index d8f8096..7dfbc6f 100644 --- a/luni/src/main/java/java/lang/reflect/MalformedParameterizedTypeException.java +++ b/luni/src/main/java/java/lang/reflect/MalformedParameterizedTypeException.java @@ -21,7 +21,6 @@ package java.lang.reflect; * Indicates that a malformed parameterized type has been encountered by a * reflective method. * - * @since 1.5 * @since Android 1.0 */ public class MalformedParameterizedTypeException extends RuntimeException { diff --git a/luni/src/main/java/java/lang/reflect/ParameterizedType.java b/luni/src/main/java/java/lang/reflect/ParameterizedType.java index 349464a..3d03921 100644 --- a/luni/src/main/java/java/lang/reflect/ParameterizedType.java +++ b/luni/src/main/java/java/lang/reflect/ParameterizedType.java @@ -21,7 +21,6 @@ package java.lang.reflect; * This interface represents a parameterized type such as {@code * 'Set<String>'}. * - * @since 1.5 * @since Android 1.0 */ public interface ParameterizedType extends Type { diff --git a/luni/src/main/java/java/lang/reflect/Type.java b/luni/src/main/java/java/lang/reflect/Type.java index f0c6142..abd4978 100644 --- a/luni/src/main/java/java/lang/reflect/Type.java +++ b/luni/src/main/java/java/lang/reflect/Type.java @@ -19,7 +19,6 @@ package java.lang.reflect; /** * Common interface implemented by all Java types. * - * @since 1.5 * @since Android 1.0 */ public interface Type { diff --git a/luni/src/main/java/java/lang/reflect/TypeVariable.java b/luni/src/main/java/java/lang/reflect/TypeVariable.java index aef7ac9..99aca77 100644 --- a/luni/src/main/java/java/lang/reflect/TypeVariable.java +++ b/luni/src/main/java/java/lang/reflect/TypeVariable.java @@ -25,7 +25,6 @@ package java.lang.reflect; * @param <D> * the generic declaration that declares this type variable * - * @since 1.5 * @since Android 1.0 */ public interface TypeVariable<D extends GenericDeclaration> extends Type { diff --git a/luni/src/main/java/java/lang/reflect/WildcardType.java b/luni/src/main/java/java/lang/reflect/WildcardType.java index 2b913d0..72a022d 100644 --- a/luni/src/main/java/java/lang/reflect/WildcardType.java +++ b/luni/src/main/java/java/lang/reflect/WildcardType.java @@ -23,7 +23,6 @@ package java.lang.reflect; * multiple upper bounded wildcard {@code '? extends Closeable & Flushable'} or * the lower bounded wildcard {@code '? super OutputStream'}. * - * @since 1.5 * @since Android 1.0 */ public interface WildcardType extends Type { diff --git a/luni/src/main/java/java/net/InetAddress.java b/luni/src/main/java/java/net/InetAddress.java index d6b6978..89f827b 100644 --- a/luni/src/main/java/java/net/InetAddress.java +++ b/luni/src/main/java/java/net/InetAddress.java @@ -160,9 +160,6 @@ public class InetAddress extends Object implements Serializable { */ @Override public boolean equals(Object obj) { - if (obj == null) { - return false; - } // BEGIN android-changed if (!(obj instanceof InetAddress)) { return false; @@ -217,10 +214,11 @@ public class InetAddress extends Object implements Serializable { // Added change taken from newer harmony concerning zero length hostname. // Added special handling for localhost, since it doesn't work properly. // TODO Get rid of this later... - if (host == null || 0 == host.length() || + if (host == null || 0 == host.length() || "localhost".equalsIgnoreCase(host)) { - return new InetAddress[] { preferIPv6Addresses() ? Inet6Address.LOOPBACK - : LOOPBACK }; + return new InetAddress[] { preferIPv6Addresses() + ? Inet6Address.LOOPBACK + : LOOPBACK }; } // END android-changed @@ -229,13 +227,27 @@ public class InetAddress extends Object implements Serializable { if (security != null) { security.checkConnect(host, -1); } - if (Socket.preferIPv4Stack()) { - return getAliasesByNameImpl(host); + + byte[][] rawAddresses = getallbyname(host, + Socket.preferIPv4Stack()); + InetAddress[] returnedAddresses = new + InetAddress[rawAddresses.length]; + for (int i = 0; i < rawAddresses.length; i++) { + byte[] rawAddress = rawAddresses[i]; + if (rawAddress.length == 16) { + returnedAddresses[i] = new Inet6Address(rawAddress, host); + } else if (rawAddress.length == 4) { + returnedAddresses[i] = new Inet4Address(rawAddress, host); + } else { + // Cannot happen, because the underlying code only returns + // addresses that are 4 or 16 bytes long. + throw new AssertionError("Impossible address length " + + rawAddress.length); + } } // ok we may have to re-order to make sure the // preferIPv6Addresses is respected - InetAddress[] returnedAddresses = getAliasesByNameImpl(host); InetAddress[] orderedAddresses = null; if (returnedAddresses != null) { orderedAddresses = new InetAddress[returnedAddresses.length]; @@ -522,54 +534,16 @@ public class InetAddress extends Object implements Serializable { } // END android-changed - /** - * Query the IP stack for aliases for the host. The host is in string name - * form. If the host does not have aliases (only multihomed hosts do), - * return an array with a single {@code InetAddress} constructed from the - * host name & address. - * - * @param name - * the host name to lookup. - * @throws UnknownHostException - * if an error occurs during lookup. - */ - // BEGIN android-changed + // BEGIN android-deleted // static native InetAddress[] getAliasesByNameImpl(String name) // throws UnknownHostException; - static InetAddress[] getAliasesByNameImpl(String name) - throws UnknownHostException { - // TODO Probably a bit inefficient. Provide native later. - InetAddress addr = getHostByNameImpl(name, false); - - String[] aliases = getaliasesbyname(name); - - if (aliases.length == 0) { - // If no alias addresses where found (only multihosts do have them) - // return the address with the name - byte[] address = addr.getAddress(); - InetAddress[] result = new InetAddress[1]; - result[0] = (address.length == 4 ? - new Inet4Address(address, name) : - new Inet6Address(address, name)); - return result; - } - - InetAddress[] result = new InetAddress[aliases.length]; - for (int i = 0; i < result.length; i++) { - byte[] address = addr.getAddress(); - result[i] = (address.length == 4 ? - new Inet4Address(address, aliases[i]) : - new Inet6Address(address, aliases[i])); - } - - return result; - } + // END android-deleted /** - * Wrapper for libc call. It is assumed to be thread-safe, which is - * in fact the case on Android. + * Resolves a host name to its IP addresses. Thread safe. */ - private static native String[] getaliasesbyname(String name); + private static native byte[][] getallbyname(String name, + boolean preferIPv4Stack); // END android-changed /** @@ -585,23 +559,13 @@ public class InetAddress extends Object implements Serializable { // throws UnknownHostException; static InetAddress getHostByAddrImpl(byte[] addr) throws UnknownHostException { - // TODO Probably inefficient. Provide native later. - String ipaddr = (addr[0] & 0xff) + "." + (addr[1] & 0xff) + "." - + (addr[2] & 0xff) + "." + (addr[3] & 0xff); - String host = gethostbyaddr(ipaddr); - - if (host == null) { - throw new UnknownHostException(ipaddr); - } - - return new InetAddress(addr, host); + return new InetAddress(addr, gethostbyaddr(addr)); } /** - * Wrapper for libc call. It is assumed to be thread-safe, which is - * in fact the case on Android. + * Resolves an IP address to a hostname. Thread safe. */ - private static native String gethostbyaddr(String addr); + private static native String gethostbyaddr(byte[] addr); // END android-changed static int inetAddr(String host) throws UnknownHostException { @@ -664,35 +628,22 @@ public class InetAddress extends Object implements Serializable { static InetAddress getHostByNameImpl(String name, boolean preferIPv6Address) throws UnknownHostException { // TODO Mapped Harmony to Android native. Get rid of indirection later. - return new InetAddress(gethostbyname(name, preferIPv6Address), name); + return getAllByName(name)[0]; } - - /** - * Wrapper for libc call. It is assumed to be thread-safe, which is - * in fact the case on Android. Either returns a raw address or throws - * UnknownHostException. - */ - private native static byte[] gethostbyname(String host, boolean preferIPv6Addresses); // END android-changed /** - * Query the IP stack for the host machine name. + * Gets the host name of the system. * - * @return String the host machine name + * @return String the system hostname */ // BEGIN android-changed - // static native String getHostNameImpl(); static String getHostNameImpl() { // TODO Mapped Harmony to Android native. Get rid of indirection later. return gethostname(); } - - /** - * Wrapper for libc call. It is assumed to be thread-safe, which is - * in fact the case on Android. - */ - private native static String gethostname(); + static native String gethostname(); // END android-changed static String getHostNameInternal(String host) throws UnknownHostException { @@ -1037,7 +988,7 @@ public class InetAddress extends Object implements Serializable { // if (!reachable) { reachable = isReachableByTCP(this, null, timeout); // } - // END adnroid-changed + // END android-changed } else { // Not Bind to any address if (null == netif.addresses) { diff --git a/luni/src/main/java/java/net/SocketPermission.java b/luni/src/main/java/java/net/SocketPermission.java index 9112590..72d77e7 100644 --- a/luni/src/main/java/java/net/SocketPermission.java +++ b/luni/src/main/java/java/net/SocketPermission.java @@ -14,6 +14,9 @@ * See the License for the specific language governing permissions and * limitations under the License. */ +// BEGIN andorid-note +// This class was copied from a newer version of harmony +// END andorid-note package java.net; @@ -140,7 +143,7 @@ public final class SocketPermission extends Permission implements Serializable { setActions(action); actions = toCanonicalActionString(action); // Use host since we are only checking for port presence - parsePort(host); + parsePort(host, hostName); } /** @@ -238,6 +241,7 @@ public final class SocketPermission extends Permission implements Serializable { } else if (action.equals(actionNames[SP_ACCEPT])) { actionsMask |= SP_ACCEPT; } else if (action.equals(actionNames[SP_RESOLVE])) { + // do nothing } else { throw new IllegalArgumentException(Msg.getString("K0048", //$NON-NLS-1$ action)); @@ -297,70 +301,61 @@ public final class SocketPermission extends Permission implements Serializable { public PermissionCollection newPermissionCollection() { return new SocketPermissionCollection(); } - + /** - * Parses the port string into the lower and higher bound of the port range. - * + * Parse the port, including the minPort, maxPort + * @param hostPort the host[:port] one + * @param host the host name we just get + * @throws IllegalArgumentException If the port is not a positive number or minPort + * is not less than or equal maxPort */ - private void parsePort(String hostString) throws IllegalArgumentException { - int negidx = -1; - int len = -1; - int lastIdx = hostString.lastIndexOf(':'); - int idx = hostString.indexOf(':'); - int endOfIPv6Addr = hostString.lastIndexOf(']'); - if ((endOfIPv6Addr == -1) && (idx != lastIdx)) { - // there are no square braces, but there are more than one ':' which - // implies an IPv6 address with no port, or an illegal argument - // check for valid IPv6 address - if (Inet6Util.isValidIP6Address(hostString)) { - return; - } - // throw an invalid argument exception - throw new IllegalArgumentException(Msg.getString("K004a")); //$NON-NLS-1$ - } - // if there is a colon and it occurs after the ']' then there is a port - // to be parsed - if ((lastIdx > -1) && (lastIdx > endOfIPv6Addr)) { - try { - len = hostString.length(); - // if hostString ends with ":*", such as "localhost:*" - // the port range should be 0-65535 - if (hostString.endsWith(":*")) { //$NON-NLS-1$ - portMin = 0; - portMax = 65535; - return; - } - // look for a '-' after the colon - negidx = hostString.indexOf('-', lastIdx); - if (negidx == lastIdx + 1) { - portMax = Integer.parseInt(hostString.substring( - lastIdx + 2, len)); - } else { - // A port range was provided - if (negidx != -1 && (negidx != len - 1)) { - portMin = Integer.parseInt(hostString.substring( - lastIdx + 1, negidx)); - portMax = Integer.parseInt(hostString.substring( - negidx + 1, len)); - } else { - if (negidx == -1) { - portMin = Integer.parseInt(hostString.substring( - lastIdx + 1, len)); - portMax = portMin; - } else { - portMin = Integer.parseInt(hostString.substring( - lastIdx + 1, negidx)); - } - } - } - if (portMax < portMin) { - throw new IllegalArgumentException(Msg.getString("K0049")); //$NON-NLS-1$ - } - - } catch (NumberFormatException e) { - throw new IllegalArgumentException(Msg.getString("K004a")); //$NON-NLS-1$ - } - } + private void parsePort(String hostPort, String host) throws IllegalArgumentException { + String port = hostPort.substring(host.length()); + String emptyString = ""; //$NON-NLS-1$ + + if (emptyString.equals(port)) { + // Not specified + portMin = 80; + portMax = 80; + return; + } + + if (":*".equals(port)) { + // The port range should be 0-65535 + portMin = 0; + portMax = 65535; + return; + } + + // Omit ':' + port = port.substring(1); + int negIdx = port.indexOf('-'); + String strPortMin = emptyString; + String strPortMax = emptyString; + if (-1 == negIdx) { + // No neg mark, only one number + strPortMin = port; + strPortMax = port; + } else { + strPortMin = port.substring(0, negIdx); + strPortMax = port.substring(negIdx + 1); + if (emptyString.equals(strPortMin)) { + strPortMin = "0"; + } + if (emptyString.equals(strPortMax)) { + strPortMax = "65535"; + } + } + try { + portMin = Integer.valueOf(strPortMin).intValue(); + portMax = Integer.valueOf(strPortMax).intValue(); + + if (portMin > portMax) { + throw new IllegalArgumentException(Msg.getString("K0049") + " " + port); //$NON-NLS-1$ + } + } catch (NumberFormatException e) { + throw new IllegalArgumentException(Msg.getString("K004a") + " " + port); //$NON-NLS-1$ + } } /** @@ -400,13 +395,26 @@ public final class SocketPermission extends Permission implements Serializable { try { ipString = InetAddress.getHostNameInternal(hostName); } catch (UnknownHostException e) { + // ignore } resolved = true; } return ipString; } + /** + * Get the host part from the host[:port] one. + * The host should be + * host = (hostname | IPv4address | IPv6reference | IPv6 in full uncompressed form) + * The wildcard "*" may be included once in a DNS name host specification. If it is included, + * it must be in the leftmost position + * + * @param host + * @return + * @throws IllegalArgumentException if the host is invalid. + */ private String getHostString(String host) throws IllegalArgumentException { + host = host.trim(); int idx = -1; idx = host.indexOf(':'); isPartialWild = (host.length() > 0 && host.charAt(0) == '*'); @@ -423,22 +431,46 @@ public final class SocketPermission extends Permission implements Serializable { } int lastIdx = host.lastIndexOf(':'); - if ((idx > -1) && (idx == lastIdx)) { - host = host.substring(0, idx); - } else { - // likely host is or contains an IPv6 address - if (lastIdx != -1) { - if (Inet6Util.isValidIP6Address(host)) { - return host.toLowerCase(); - } else if (Inet6Util.isValidIP6Address(host.substring(0, - lastIdx))) { - host = host.substring(0, lastIdx); - } else { - throw new IllegalArgumentException(Msg.getString("K004a")); //$NON-NLS-1$ + + if (idx == lastIdx) { + if (-1 != idx) { + // only one colon, should be port + host = host.substring(0, idx); + } + return host.toLowerCase(); + } + // maybe ipv6 + boolean isFirstBracket = (host.charAt(0) == '['); + if (!isFirstBracket) { + // No bracket, should be in full form + int colonNum = 0; + for (int i = 0; i < host.length(); ++i) { + if (host.charAt(i) == ':') { + colonNum++; } } + // Get rid of the colon before port + if (8 == colonNum) { + host = host.substring(0, lastIdx); + } + if (Inet6Util.isIP6AddressInFullForm(host)) { + return host.toLowerCase(); + } + throw new IllegalArgumentException(Msg.getString("K004a") + " " + + host); + } + // forward bracket found + int bbracketIdx = host.indexOf(']'); + if (-1 == bbracketIdx) { + // no back bracket found, wrong + throw new IllegalArgumentException(Msg.getString("K004a") + " " + + host); + } + host = host.substring(0, bbracketIdx + 1); + if (Inet6Util.isValidIP6Address(host)) { + return host.toLowerCase(); } - return host.toLowerCase(); + throw new IllegalArgumentException(Msg.getString("K004a") + " " + host); } /** @@ -474,7 +506,7 @@ public final class SocketPermission extends Permission implements Serializable { portMax = HIGHEST_PORT; actionsMask = SP_RESOLVE; hostName = getHostString(getName()); - parsePort(getName()); + parsePort(getName(), hostName); setActions(actions); } } diff --git a/luni/src/main/java/java/net/URLConnection.java b/luni/src/main/java/java/net/URLConnection.java index ce92aad..6c1a192 100644 --- a/luni/src/main/java/java/net/URLConnection.java +++ b/luni/src/main/java/java/net/URLConnection.java @@ -840,9 +840,12 @@ public abstract class URLConnection { * @since Android 1.0 */ public void setDefaultUseCaches(boolean newValue) { - if (connected) { - throw new IllegalAccessError(Msg.getString("K0037")); //$NON-NLS-1$ - } + // BEGIN android-removed + // Setting the default doesn't concern the current connection. + // if (connected) { + // throw new IllegalAccessError(Msg.getString("K0037")); //$NON-NLS-1$ + // } + // END android-removed defaultUseCaches = newValue; } diff --git a/luni/src/main/java/java/util/Arrays.java b/luni/src/main/java/java/util/Arrays.java index d8aa6ee..6af24b0 100644 --- a/luni/src/main/java/java/util/Arrays.java +++ b/luni/src/main/java/java/util/Arrays.java @@ -27,9 +27,6 @@ import java.lang.reflect.Array; */ public class Arrays { - /* Specifies when to switch to insertion sort */ - private static final int SIMPLE_LENGTH = 7; - private static class ArrayList<E> extends AbstractList<E> implements List<E>, Serializable, RandomAccess { @@ -131,7 +128,7 @@ public class Arrays { } @Override - @SuppressWarnings("unchecked") + @SuppressWarnings({"unchecked", "SuspiciousSystemArraycopy"}) public <T> T[] toArray(T[] contents) { int size = size(); if (size > contents.length) { @@ -2373,6 +2370,41 @@ public class Arrays { } } +// BEGIN android-changed + + /* + * <p>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 comparbles if it + * offers sufficient performance. + */ + +// /** +// * A comparator that implements the natural order of a group of +// * mutually comparable elements. Using this comparator saves us +// * from duplicating most of the code in this file (one version for +// * commparables, 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 in ascending natural order. * @@ -2385,7 +2417,7 @@ public class Arrays { * @since Android 1.0 */ public static void sort(Object[] array) { - sort(0, array.length, array); + ComparableTimSort.sort(array); } /** @@ -2410,507 +2442,7 @@ public class Arrays { * @since Android 1.0 */ public static void sort(Object[] array, int start, int end) { - if (array == null) { - throw new NullPointerException(); - } - checkBounds(array.length, start, end); - sort(start, end, array); - } - - private static void sort(int fromIndex, int toIndex, Object[] array) { - int length = toIndex - fromIndex; - if (length <= 0) { - return; - } - if (array instanceof String[]) { - stableStringSort((String[]) array, fromIndex, toIndex); - } else { - Object[] out = new Object[toIndex]; - System.arraycopy(array, fromIndex, out, fromIndex, length); - mergeSort(out, array, fromIndex, toIndex); - } - } - - /** - * Swaps the elements at the specified positions in the specified array. - * - * @param a - - * the index of one element to be swapped. - * @param b - - * the index of the other element to be swapped. - * @param arr - - * the array in which to swap elements. - */ - private static void swap(int a, int b, Object[] arr) { - Object tmp = arr[a]; - arr[a] = arr[b]; - arr[b] = tmp; - } - - /** - * Sorts the specified range of the specified array of {@code Objects}. 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.) This - * sort is guaranteed to be stable: equal elements will not be reordered as - * a result of the sort. - * - * The sorting algorithm is a mergesort with exponential search (in which - * the merge is performed by exponential search). This algorithm offers - * guaranteed {@code n*log(n)} performance and in average case faster then any - * mergesort in which the merge is performed by linear search. - * - * @param in - - * the array for sorting. - * @param out - - * the result, sorted array. - * @param fromIndex - - * the index of the first element (inclusive) to be sorted. - * @param toIndex - - * the index of the last element (exclusive) to be sorted. - */ - @SuppressWarnings("unchecked") - private static void mergeSort(Object[] in, Object[] out, int fromIndex, - int toIndex) { - int len = toIndex - fromIndex; - // use insertion sort for small arrays - if (len <= SIMPLE_LENGTH) { - for (int i = fromIndex + 1; i < toIndex; i++) { - Comparable<Object> current = (Comparable<Object>) out[i]; - Object prev = out[i - 1]; - if (current.compareTo(prev) < 0) { - int j = i; - do { - out[j--] = prev; - } while (j > fromIndex - && current.compareTo(prev = out[j - 1]) < 0); - out[j] = current; - } - } - return; - } - int med = (toIndex + fromIndex) >> 1; - mergeSort(out, in, fromIndex, med); - mergeSort(out, in, med, toIndex); - - // merging - - // if arrays are already sorted - no merge - if (((Comparable<Object>) in[med]).compareTo(in[med - 1]) >= 0) { - System.arraycopy(in, fromIndex, out, fromIndex, len); - return; - } - int r = med, i = fromIndex; - - // use merging with exponential search - do { - Comparable<Object> fromVal = (Comparable<Object>) in[fromIndex]; - Comparable<Object> rVal = (Comparable<Object>) in[r]; - if (fromVal.compareTo(rVal) <= 0) { - int l_1 = find(in, rVal, -1, fromIndex + 1, med - 1); - int toCopy = l_1 - fromIndex + 1; - System.arraycopy(in, fromIndex, out, i, toCopy); - i += toCopy; - out[i++] = rVal; - r++; - fromIndex = l_1 + 1; - } else { - int r_1 = find(in, fromVal, 0, r + 1, toIndex - 1); - int toCopy = r_1 - r + 1; - System.arraycopy(in, r, out, i, toCopy); - i += toCopy; - out[i++] = fromVal; - fromIndex++; - r = r_1 + 1; - } - } while ((toIndex - r) > 0 && (med - fromIndex) > 0); - - // copy rest of array - if ((toIndex - r) <= 0) { - System.arraycopy(in, fromIndex, out, i, med - fromIndex); - } else { - System.arraycopy(in, r, out, i, toIndex - r); - } - } - - /** - * Sorts the specified range of the specified array of objects. The range to - * be sorted extends from index fromIndex, inclusive, to index toIndex, - * exclusive. (If fromIndex==toIndex, the range to be sorted is empty.) This - * sort is guaranteed to be stable: equal elements will not be reordered as - * a result of the sort. - * - * The sorting algorithm is a mergesort with exponential search (in which - * the merge is performed by exponential search). This algorithm offers - * guaranteed n*log(n) performance and in average case faster then any - * mergesort in which the merge is performed by linear search. - * - * @param in - - * the array for sorting. - * @param out - - * the result, sorted array. - * @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. - */ - @SuppressWarnings("unchecked") - private static void mergeSort(Object[] in, Object[] out, int fromIndex, - int toIndex, Comparator c) { - int len = toIndex - fromIndex; - // use insertion sort for small arrays - if (len <= SIMPLE_LENGTH) { - for (int i = fromIndex + 1; i < toIndex; i++) { - Object current = out[i]; - Object prev = out[i - 1]; - if (c.compare(prev, current) > 0) { - int j = i; - do { - out[j--] = prev; - } while (j > fromIndex - && (c.compare(prev = out[j - 1], current) > 0)); - out[j] = current; - } - } - return; - } - int med = (toIndex + fromIndex) >> 1; - mergeSort(out, in, fromIndex, med, c); - mergeSort(out, in, med, toIndex, c); - - // merging - - // if arrays are already sorted - no merge - if (c.compare(in[med], in[med - 1]) >= 0) { - System.arraycopy(in, fromIndex, out, fromIndex, len); - return; - } - int r = med, i = fromIndex; - - // use merging with exponential search - do { - Object fromVal = in[fromIndex]; - Object rVal = in[r]; - if (c.compare(fromVal, rVal) <= 0) { - int l_1 = find(in, rVal, -1, fromIndex + 1, med - 1, c); - int toCopy = l_1 - fromIndex + 1; - System.arraycopy(in, fromIndex, out, i, toCopy); - i += toCopy; - out[i++] = rVal; - r++; - fromIndex = l_1 + 1; - } else { - int r_1 = find(in, fromVal, 0, r + 1, toIndex - 1, c); - int toCopy = r_1 - r + 1; - System.arraycopy(in, r, out, i, toCopy); - i += toCopy; - out[i++] = fromVal; - fromIndex++; - r = r_1 + 1; - } - } while ((toIndex - r) > 0 && (med - fromIndex) > 0); - - // copy rest of array - if ((toIndex - r) <= 0) { - System.arraycopy(in, fromIndex, out, i, med - fromIndex); - } else { - System.arraycopy(in, r, out, i, toIndex - r); - } - } - - /** - * Finds the place where the element should be inserted into the specified - * range of the specified sorted array so that the resulting array would - * remain sorted. Uses an exponential search algorithm. - * - * @param arr - - * the array with a sorted range - * - * @param val - - * the object to be inserted - * - * @param l - - * the index of the first element (inclusive) - * - * @param r - - * the index of the last element (inclusive) - * - * @param bnd - - * A specifier to indicate how to treat the case where the - * array range contains an element or elements equal to - * {@code val}. "{@code -1}" indicates that val should be placed at - * the index greater than the indices of any elements equal to - * {@code val}. "{@code 0}" - indicates that val should be placed at - * the index less than the indices of any elements equal to - * {@code val}. - * - */ - @SuppressWarnings("unchecked") - private static int find(Object[] arr, Comparable val, int bnd, int l, int r) { - int m = l; - int d = 1; - while (m <= r) { - if (val.compareTo(arr[m]) > bnd) { - l = m + 1; - } else { - r = m - 1; - break; - } - m += d; - d <<= 1; - } - while (l <= r) { - m = (l + r) >> 1; - if (val.compareTo(arr[m]) > bnd) { - l = m + 1; - } else { - r = m - 1; - } - } - return l - 1; - } - - /** - * Finds the place where the element should be inserted into the specified - * range of the specified sorted array so that the resulting array would - * remain sorted. Uses an exponential search algorithm. - * - * @param arr - - * the array with a sorted range - * - * @param val - - * the object to be inserted - * - * @param l - - * the index of the first element (inclusive) - * - * @param r - - * the index of the last element (inclusive) - * - * @param bnd - - * A specifier to indicate how to treat the case where the - * array range contains an element or elements equal to - * {@code val}. "{@code -1}" indicates that val should be placed at - * the index greater than the indices of any elements equal to - * {@code val}. "{@code 0}" - indicates that val should be placed at - * the index less than the indices of any elements equal to - * {@code val}. - * - * @param c - - * the {@code Comparator} to determine the ordering of the array. - */ - @SuppressWarnings("unchecked") - private static int find(Object[] arr, Object val, int bnd, int l, int r, - Comparator c) { - int m = l; - int d = 1; - while (m <= r) { - if (c.compare(val, arr[m]) > bnd) { - l = m + 1; - } else { - r = m - 1; - break; - } - m += d; - d <<= 1; - } - while (l <= r) { - m = (l + r) >> 1; - if (c.compare(val, arr[m]) > bnd) { - l = m + 1; - } else { - r = m - 1; - } - } - return l - 1; - } - - /* - * returns the median index. - */ - private static int medChar(int a, int b, int c, String[] arr, int id) { - int ac = charAt(arr[a], id); - int bc = charAt(arr[b], id); - int cc = charAt(arr[c], id); - return ac < bc ? (bc < cc ? b : (ac < cc ? c : a)) - : (bc < cc ? (ac < cc ? a : c) : b); - - } - - /* - * Returns the char value at the specified index of string or -1 if the - * index more than the length of this string. - */ - private static int charAt(String str, int i) { - if (i >= str.length()) { - return -1; - } - return str.charAt(i); - } - - /** - * Copies object from one array to another array with reverse of objects - * order. Source and destination arrays may be the same. - * - * @param src - - * the source array. - * @param from - - * starting position in the source array. - * @param dst - - * the destination array. - * @param to - - * starting position in the destination array. - * @param len - - * the number of array elements to be copied. - */ - private static void copySwap(Object[] src, int from, Object[] dst, int to, - int len) { - if (src == dst && from + len > to) { - int new_to = to + len - 1; - for (; from < to; from++, new_to--, len--) { - dst[new_to] = src[from]; - } - for (; len > 1; from++, new_to--, len -= 2) { - swap(from, new_to, dst); - } - - } else { - to = to + len - 1; - for (; len > 0; from++, to--, len--) { - dst[to] = src[from]; - } - } - } - - /** - * Sorts the specified range of the specified {@code String} array. - * - * @param arr - - * 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. - */ - private static void stableStringSort(String[] arr, int fromIndex, - int toIndex) { - stableStringSort(arr, arr, new String[toIndex], fromIndex, toIndex, 0); - } - - /** - * Sorts the specified range of the specified {@code String} array. Use stable - * ternary quick sort algorithm. - * - * @param arr - - * the array to be sorted - * @param src - - * auxiliary array - * @param dst - - * auxiliary array - * @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 chId - - * index of {@code char} for current sorting - */ - private static void stableStringSort(String[] arr, String[] src, - String[] dst, int fromIndex, int toIndex, int chId) { - int length = toIndex - fromIndex; - // use insertion sort for small arrays - if (length < SIMPLE_LENGTH) { - if (src == arr) { - for (int i = fromIndex + 1; i < toIndex; i++) { - String current = arr[i]; - String prev = arr[i - 1]; - if (current.compareTo(prev) < 0) { - int j = i; - do { - arr[j--] = prev; - } while (j > fromIndex - && current.compareTo(prev = arr[j - 1]) < 0); - arr[j] = current; - } - } - } else { - int end = toIndex - 1; - dst[fromIndex] = src[end--]; - for (int i = fromIndex + 1; i < toIndex; i++, end--) { - String current = src[end]; - String prev; - int j = i; - while (j > fromIndex - && current.compareTo(prev = dst[j - 1]) < 0) { - dst[j--] = prev; - } - dst[j] = current; - } - } - return; - } - // Approximate median - int s; - int mid = fromIndex + length / 2; - int lo = fromIndex; - int hi = toIndex - 1; - if (length > 40) { - s = length / 8; - lo = medChar(lo, lo + s, lo + s * 2, src, chId); - mid = medChar(mid - s, mid, mid + s, src, chId); - hi = medChar(hi, hi - s, hi - s * 2, src, chId); - } - mid = medChar(lo, mid, hi, src, chId); - // median found - // create 4 pointers <a (in star of src) , - // =b(in start of dst), >c (in end of dst) - // i - current element; - int midVal = charAt(src[mid], chId); - int a, b, c; - a = b = fromIndex; - c = toIndex - 1; - int cmp; - - for (int i = fromIndex; i < toIndex; i++) { - String el = src[i]; - cmp = charAt(el, chId) - midVal; - if (cmp < 0) { - src[a] = el; - a++; - } else if (cmp > 0) { - dst[c] = el; - c--; - } else { - dst[b] = el; - b++; - } - } - - s = b - fromIndex; - if (s > 0) { - if (arr == src) { - System.arraycopy(dst, fromIndex, arr, a, s); - } else { - copySwap(dst, fromIndex, arr, a, s); - } - - if (b >= toIndex && midVal == -1) { - return; - } - stableStringSort(arr, arr, arr == dst ? src : dst, a, a + s, - chId + 1); - } - - s = a - fromIndex; - if (s > 0) { - stableStringSort(arr, src, dst, fromIndex, a, chId); - } - - c++; - s = toIndex - c; - if (s > 0) { - stableStringSort(arr, dst, src, c, toIndex, chId); - } + ComparableTimSort.sort(array, start, end); } /** @@ -2937,23 +2469,7 @@ public class Arrays { */ public static <T> void sort(T[] array, int start, int end, Comparator<? super T> comparator) { - if (array == null) { - throw new NullPointerException(); - } - checkBounds(array.length, start, end); - sort(start, end, array, comparator); - } - - private static <T> void sort(int start, int end, T[] array, - Comparator<? super T> comparator) { - if (comparator == null) { - sort(start, end, array); - } else { - int length = end - start; - Object[] out = new Object[end]; - System.arraycopy(array, start, out, start, length); - mergeSort(out, array, start, end, comparator); - } + TimSort.sort(array, start, end, comparator); } /** @@ -2970,9 +2486,11 @@ public class Arrays { * @since Android 1.0 */ public static <T> void sort(T[] array, Comparator<? super T> comparator) { - sort(0, array.length, array, comparator); + TimSort.sort(array, comparator); } +// END android-changed + /** * Sorts the specified array in ascending numerical order. * diff --git a/luni/src/main/java/java/util/ComparableTimSort.java b/luni/src/main/java/java/util/ComparableTimSort.java new file mode 100644 index 0000000..b9f7145 --- /dev/null +++ b/luni/src/main/java/java/util/ComparableTimSort.java @@ -0,0 +1,885 @@ +/* + * Copyright (C) 2008 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package java.util; + +/** + * This is a near duplicate of {@link TimSort}, modified for use with + * arrays of objects that implement {@link Comparable}, instead of using + * explicit comparators. + * + * <p>If you are using an optimizing VM, you may find that ComparableTimSort + * offers no performance benefit over TimSort in conjunction with a + * comparator that simply returns {@code ((Comparable)first).compareTo(Second)}. + * If this is the case, you are better off deleting ComparableTimSort to + * eliminate the code duplication. (See Arrays.java for details.) + */ +class ComparableTimSort { + /** + * This is the minimum sized sequence that will be merged. Shorter + * sequences will be lengthened by calling binarySort. If the entire + * array is less than this length, no merges will be performed. + * + * This constant should be a power of two. It was 64 in Tim Peter's C + * implementation, but 32 was empirically determined to work better in + * this implementation. In the unlikely event that you set this constant + * to be a number that's not a power of two, you'll need to change the + * {@link #minRunLength} computation. + * + * If you decrease this constant, you must change the stackLen + * computation in the TimSort constructor, or you risk an + * ArrayOutOfBounds exception. See listsort.txt for a discussion + * of the minimum stack length required as a function of the length + * of the array being sorted and the minimum merge sequence length. + */ + private static final int MIN_MERGE = 32; + + /** + * The array being sorted. + */ + private final Object[] a; + + /** + * When we get into galloping mode, we stay there until both runs win less + * often than MIN_GALLOP consecutive times. + */ + private static final int MIN_GALLOP = 7; + + /** + * This controls when we get *into* galloping mode. It is initialized + * to MIN_GALLOP. The mergeLo and mergeHi methods nudge it higher for + * random data, and lower for highly structured data. + */ + private int minGallop = MIN_GALLOP; + + /** + * Maximum initial size of tmp array, which is used for merging. The array + * can grow to accommodate demand. + * + * Unlike Tim's original C version, we do not allocate this much storage + * when sorting smaller arrays. This change was required for performance. + */ + private static final int INITIAL_TMP_STORAGE_LENGTH = 256; + + /** + * Temp storage for merges. + */ + private Object[] tmp; + + /** + * A stack of pending runs yet to be merged. Run i starts at + * address base[i] and extends for len[i] elements. It's always + * true (so long as the indices are in bounds) that: + * + * runBase[i] + runLen[i] == runBase[i + 1] + * + * so we could cut the storage for this, but it's a minor amount, + * and keeping all the info explicit simplifies the code. + */ + private int stackSize = 0; // Number of pending runs on stack + private final int[] runBase; + private final int[] runLen; + + /** + * Asserts have been placed in if-statements for performace. To enable them, + * set this field to true and enable them in VM with a command line flag. + * If you modify this class, please do test the asserts! + */ + private static final boolean DEBUG = false; + + /** + * Creates a TimSort instance to maintain the state of an ongoing sort. + * + * @param a the array to be sorted + */ + private ComparableTimSort(Object[] a) { + this.a = a; + + // Allocate temp storage (which may be increased later if necessary) + int len = a.length; + @SuppressWarnings({"unchecked", "UnnecessaryLocalVariable"}) + Object[] newArray = new Object[len < 2 * INITIAL_TMP_STORAGE_LENGTH ? + len >>> 1 : INITIAL_TMP_STORAGE_LENGTH]; + tmp = newArray; + + /* + * Allocate runs-to-be-merged stack (which cannot be expanded). The + * stack length requirements are described in listsort.txt. The C + * version always uses the same stack length (85), but this was + * measured to be too expensive when sorting "mid-sized" arrays (e.g., + * 100 elements) in Java. Therefore, we use smaller (but sufficiently + * large) stack lengths for smaller arrays. The "magic numbers" in the + * computation below must be changed if MIN_MERGE is decreased. See + * the MIN_MERGE declaration above for more information. + */ + int stackLen = (len < 120 ? 5 : + len < 1542 ? 10 : + len < 119151 ? 19 : 40); + runBase = new int[stackLen]; + runLen = new int[stackLen]; + } + + /* + * The next two methods (which are package private and static) constitute + * the entire API of this class. Each of these methods obeys the contract + * of the public method with the same signature in java.util.Arrays. + */ + + static void sort(Object[] a) { + sort(a, 0, 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 + + // If array is small, do a "mini-TimSort" with no merges + if (nRemaining < MIN_MERGE) { + int initRunLen = countRunAndMakeAscending(a, lo, nRemaining); + binarySort(a, lo, hi, lo + initRunLen); + return; + } + + /** + * March over the array once, left to right, finding natural runs, + * extending short natural runs to minRun elements, and merging runs + * to maintain stack invariant. + */ + ComparableTimSort ts = new ComparableTimSort(a); + int minRun = minRunLength(nRemaining); + do { + // Identify next run + int runLen = countRunAndMakeAscending(a, lo, hi); + + // If run is short, extend to min(minRun, nRemaining) + if (runLen < minRun) { + int force = nRemaining <= minRun ? nRemaining : minRun; + binarySort(a, lo, lo + force, lo + runLen); + runLen = force; + } + + // Push run onto pending-run stack, and maybe merge + ts.pushRun(lo, runLen); + ts.mergeCollapse(); + + // Advance to find next run + lo += runLen; + nRemaining -= runLen; + } while (nRemaining != 0); + + // Merge all remaining runs to complete sort + if (DEBUG) assert lo == hi; + ts.mergeForceCollapse(); + if (DEBUG) assert ts.stackSize == 1; + } + + /** + * Sorts the specified portion of the specified array using a binary + * insertion sort. This is the best method for sorting small numbers + * of elements. It requires O(n log n) compares, but O(n^2) data + * movement (worst case). + * + * If the initial part of the specified range is already sorted, + * this method can take advantage of it: the method assumes that the + * elements from index {@code lo}, inclusive, to {@code start}, + * exclusive are already sorted. + * + * @param a the array in which a range is to be sorted + * @param lo the index of the first element in the range to be sorted + * @param hi the index after the last element in the range to be sorted + * @param start the index of the first element in the range that is + * not already known to be sorted (@code lo <= start <= hi} + */ + @SuppressWarnings("fallthrough") + private static void binarySort(Object[] a, int lo, int hi, int start) { + if (DEBUG) assert lo <= start && start <= hi; + if (start == lo) + start++; + for ( ; start < hi; start++) { + @SuppressWarnings("unchecked") + Comparable<Object> pivot = (Comparable) a[start]; + + // Set left (and right) to the index where a[start] (pivot) belongs + int left = lo; + int right = start; + if (DEBUG) assert left <= right; + /* + * Invariants: + * pivot >= all in [lo, left). + * pivot < all in [right, start). + */ + while (left < right) { + int mid = (left + right) >>> 1; + if (pivot.compareTo(a[mid]) < 0) + right = mid; + else + left = mid + 1; + } + if (DEBUG) assert left == right; + + /* + * The invariants still hold: pivot >= all in [lo, left) and + * pivot < all in [left, start), so pivot belongs at left. Note + * that if there are elements equal to pivot, left points to the + * first slot after them -- that's why this sort is stable. + * Slide elements over to make room to make room for pivot. + */ + int n = start - left; // The number of elements to move + // Switch is just an optimization for arraycopy in default case + switch(n) { + case 2: a[left + 2] = a[left + 1]; + case 1: a[left + 1] = a[left]; + break; + default: System.arraycopy(a, left, a, left + 1, n); + } + a[left] = pivot; + } + } + + /** + * Returns the length of the run beginning at the specified position in + * the specified array and reverses the run if it is descending (ensuring + * that the run will always be ascending when the method returns). + * + * A run is the longest ascending sequence with: + * + * a[lo] <= a[lo + 1] <= a[lo + 2] <= ... + * + * or the longest descending sequence with: + * + * a[lo] > a[lo + 1] > a[lo + 2] > ... + * + * For its intended use in a stable mergesort, the strictness of the + * definition of "descending" is needed so that the call can safely + * reverse a descending sequence without violating stability. + * + * @param a the array in which a run is to be counted and possibly reversed + * @param lo index of the first element in the run + * @param hi index after the last element that may be contained in the run. + It is required that @code{lo < hi}. + * @return the length of the run beginning at the specified position in + * the specified array + */ + @SuppressWarnings("unchecked") + private static int countRunAndMakeAscending(Object[] a, int lo, int hi) { + if (DEBUG) assert lo < hi; + int runHi = lo + 1; + if (runHi == hi) + return 1; + + // Find end of run, and reverse range if descending + if (((Comparable) a[runHi++]).compareTo(a[lo]) < 0) { // Descending + while(runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) < 0) + runHi++; + reverseRange(a, lo, runHi); + } else { // Ascending + while (runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) >= 0) + runHi++; + } + + return runHi - lo; + } + + /** + * Reverse the specified range of the specified array. + * + * @param a the array in which a range is to be reversed + * @param lo the index of the first element in the range to be reversed + * @param hi the index after the last element in the range to be reversed + */ + private static void reverseRange(Object[] a, int lo, int hi) { + hi--; + while (lo < hi) { + Object t = a[lo]; + a[lo++] = a[hi]; + a[hi--] = t; + } + } + + /** + * Returns the minimum acceptable run length for an array of the specified + * length. Natural runs shorter than this will be extended with + * {@link #binarySort}. + * + * Roughly speaking, the computation is: + * + * If n < MIN_MERGE, return n (it's too small to bother with fancy stuff). + * Else if n is an exact power of 2, return MIN_MERGE/2. + * Else return an int k, MIN_MERGE/2 <= k <= MIN_MERGE, such that n/k + * is close to, but strictly less than, an exact power of 2. + * + * For the rationale, see listsort.txt. + * + * @param n the length of the array to be sorted + * @return the length of the minimum run to be merged + */ + private static int minRunLength(int n) { + if (DEBUG) assert n >= 0; + int r = 0; // Becomes 1 if any 1 bits are shifted off + while (n >= MIN_MERGE) { + r |= (n & 1); + n >>= 1; + } + return n + r; + } + + /** + * Pushes the specified run onto the pending-run stack. + * + * @param runBase index of the first element in the run + * @param runLen the number of elements in the run + */ + private void pushRun(int runBase, int runLen) { + this.runBase[stackSize] = runBase; + this.runLen[stackSize] = runLen; + stackSize++; + } + + /** + * Examines the stack of runs waiting to be merged and merges adjacent runs + * until the stack invariants are reestablished: + * + * 1. runLen[i - 3] > runLen[i - 2] + runLen[i - 1] + * 2. runLen[i - 2] > runLen[i - 1] + * + * This method is called each time a new run is pushed onto the stack, + * so the invariants are guaranteed to hold for i < stackSize upon + * entry to the method. + */ + private void mergeCollapse() { + while (stackSize > 1) { + int n = stackSize - 2; + if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) { + if (runLen[n - 1] < runLen[n + 1]) + n--; + mergeAt(n); + } else if (runLen[n] <= runLen[n + 1]) { + mergeAt(n); + } else { + break; // Invariant is established + } + } + } + + /** + * Merges all runs on the stack until only one remains. This method is + * called once, to complete the sort. + */ + private void mergeForceCollapse() { + while (stackSize > 1) { + int n = stackSize - 2; + if (n > 0 && runLen[n - 1] < runLen[n + 1]) + n--; + mergeAt(n); + } + } + + /** + * Merges the two runs at stack indices i and i+1. Run i must be + * the penultimate or antepenultimate run on the stack. In other words, + * i must be equal to stackSize-2 or stackSize-3. + * + * @param i stack index of the first of the two runs to merge + */ + @SuppressWarnings("unchecked") + private void mergeAt(int i) { + if (DEBUG) assert stackSize >= 2; + if (DEBUG) assert i >= 0; + if (DEBUG) assert i == stackSize - 2 || i == stackSize - 3; + + int base1 = runBase[i]; + int len1 = runLen[i]; + int base2 = runBase[i + 1]; + int len2 = runLen[i + 1]; + if (DEBUG) assert len1 > 0 && len2 > 0; + if (DEBUG) assert base1 + len1 == base2; + + /* + * Record the length of the combined runs; if i is the 3rd-last + * run now, also slide over the last run (which isn't involved + * in this merge). The current run (i+1) goes away in any case. + */ + runLen[i] = len1 + len2; + if (i == stackSize - 3) { + runBase[i + 1] = runBase[i + 2]; + runLen[i + 1] = runLen[i + 2]; + } + stackSize--; + + /* + * Find where the first element of run2 goes in run1. Prior elements + * in run1 can be ignored (because they're already in place). + */ + int k = gallopRight((Comparable<Object>) a[base2], a, base1, len1, 0); + if (DEBUG) assert k >= 0; + base1 += k; + len1 -= k; + if (len1 == 0) + return; + + /* + * Find where the last element of run1 goes in run2. Subsequent elements + * in run2 can be ignored (because they're already in place). + */ + len2 = gallopLeft((Comparable<Object>) a[base1 + len1 - 1], a, + base2, len2, len2 - 1); + if (DEBUG) assert len2 >= 0; + if (len2 == 0) + return; + + // Merge remaining runs, using tmp array with min(len1, len2) elements + if (len1 <= len2) + mergeLo(base1, len1, base2, len2); + else + mergeHi(base1, len1, base2, len2); + } + + /** + * Locates the position at which to insert the specified key into the + * specified sorted range; if the range contains an element equal to key, + * returns the index of the leftmost equal element. + * + * @param key the key whose insertion point to search for + * @param a the array in which to search + * @param base the index of the first element in the range + * @param len the length of the range; must be > 0 + * @param hint the index at which to begin the search, 0 <= hint < n. + * The closer hint is to the result, the faster this method will run. + * @return the int k, 0 <= k <= n such that a[b + k - 1] < key <= a[b + k], + * pretending that a[b - 1] is minus infinity and a[b + n] is infinity. + * In other words, key belongs at index b + k; or in other words, + * the first k elements of a should precede key, and the last n - k + * should follow it. + */ + private static int gallopLeft(Comparable<Object> key, Object[] a, + int base, int len, int hint) { + if (DEBUG) assert len > 0 && hint >= 0 && hint < len; + + int lastOfs = 0; + int ofs = 1; + if (key.compareTo(a[base + hint]) > 0) { + // Gallop right until a[base+hint+lastOfs] < key <= a[base+hint+ofs] + int maxOfs = len - hint; + while (ofs < maxOfs && key.compareTo(a[base + hint + ofs]) > 0) { + lastOfs = ofs; + ofs = (ofs << 1) + 1; + if (ofs <= 0) // int overflow + ofs = maxOfs; + } + if (ofs > maxOfs) + ofs = maxOfs; + + // Make offsets relative to base + lastOfs += hint; + ofs += hint; + } else { // key <= a[base + hint] + // Gallop left until a[base+hint-ofs] < key <= a[base+hint-lastOfs] + final int maxOfs = hint + 1; + while (ofs < maxOfs && key.compareTo(a[base + hint - ofs]) <= 0) { + lastOfs = ofs; + ofs = (ofs << 1) + 1; + if (ofs <= 0) // int overflow + ofs = maxOfs; + } + if (ofs > maxOfs) + ofs = maxOfs; + + // Make offsets relative to base + int tmp = lastOfs; + lastOfs = hint - ofs; + ofs = hint - tmp; + } + if (DEBUG) assert -1 <= lastOfs && lastOfs < ofs && ofs <= len; + + /* + * Now a[base+lastOfs] < key <= a[base+ofs], so key belongs somewhere + * to the right of lastOfs but no farther right than ofs. Do a binary + * search, with invariant a[base + lastOfs - 1] < key <= a[base + ofs]. + */ + lastOfs++; + while (lastOfs < ofs) { + int m = lastOfs + ((ofs - lastOfs) >>> 1); + + if (key.compareTo(a[base + m]) > 0) + lastOfs = m + 1; // a[base + m] < key + else + ofs = m; // key <= a[base + m] + } + if (DEBUG) assert lastOfs == ofs; // so a[base + ofs - 1] < key <= a[base + ofs] + return ofs; + } + + /** + * Like gallopLeft, except that if the range contains an element equal to + * key, gallopRight returns the index after the rightmost equal element. + * + * @param key the key whose insertion point to search for + * @param a the array in which to search + * @param base the index of the first element in the range + * @param len the length of the range; must be > 0 + * @param hint the index at which to begin the search, 0 <= hint < n. + * The closer hint is to the result, the faster this method will run. + * @return the int k, 0 <= k <= n such that a[b + k - 1] <= key < a[b + k] + */ + private static int gallopRight(Comparable<Object> key, Object[] a, + int base, int len, int hint) { + if (DEBUG) assert len > 0 && hint >= 0 && hint < len; + + int ofs = 1; + int lastOfs = 0; + if (key.compareTo(a[base + hint]) < 0) { + // Gallop left until a[b+hint - ofs] <= key < a[b+hint - lastOfs] + int maxOfs = hint + 1; + while (ofs < maxOfs && key.compareTo(a[base + hint - ofs]) < 0) { + lastOfs = ofs; + ofs = (ofs << 1) + 1; + if (ofs <= 0) // int overflow + ofs = maxOfs; + } + if (ofs > maxOfs) + ofs = maxOfs; + + // Make offsets relative to b + int tmp = lastOfs; + lastOfs = hint - ofs; + ofs = hint - tmp; + } else { // a[b + hint] <= key + // Gallop right until a[b+hint + lastOfs] <= key < a[b+hint + ofs] + int maxOfs = len - hint; + while (ofs < maxOfs && key.compareTo(a[base + hint + ofs]) >= 0) { + lastOfs = ofs; + ofs = (ofs << 1) + 1; + if (ofs <= 0) // int overflow + ofs = maxOfs; + } + if (ofs > maxOfs) + ofs = maxOfs; + + // Make offsets relative to b + lastOfs += hint; + ofs += hint; + } + if (DEBUG) assert -1 <= lastOfs && lastOfs < ofs && ofs <= len; + + /* + * Now a[b + lastOfs] <= key < a[b + ofs], so key belongs somewhere to + * the right of lastOfs but no farther right than ofs. Do a binary + * search, with invariant a[b + lastOfs - 1] <= key < a[b + ofs]. + */ + lastOfs++; + while (lastOfs < ofs) { + int m = lastOfs + ((ofs - lastOfs) >>> 1); + + if (key.compareTo(a[base + m]) < 0) + ofs = m; // key < a[b + m] + else + lastOfs = m + 1; // a[b + m] <= key + } + if (DEBUG) assert lastOfs == ofs; // so a[b + ofs - 1] <= key < a[b + ofs] + return ofs; + } + + /** + * Merges two adjacent runs in place, in a stable fashion. The first + * element of the first run must be greater than the first element of the + * second run (a[base1] > a[base2]), and the last element of the first run + * (a[base1 + len1-1]) must be greater than all elements of the second run. + * + * For performance, this method should be called only when len1 <= len2; + * its twin, mergeHi should be called if len1 >= len2. (Either method + * may be called if len1 == len2.) + * + * @param base1 index of first element in first run to be merged + * @param len1 length of first run to be merged (must be > 0) + * @param base2 index of first element in second run to be merged + * (must be aBase + aLen) + * @param len2 length of second run to be merged (must be > 0) + */ + @SuppressWarnings("unchecked") + private void mergeLo(int base1, int len1, int base2, int len2) { + if (DEBUG) assert len1 > 0 && len2 > 0 && base1 + len1 == base2; + + // 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 cursor2 = base2; // Indexes int a + int dest = base1; // Indexes int a + + // Move first element of second run and deal with degenerate cases + a[dest++] = a[cursor2++]; + if (--len2 == 0) { + System.arraycopy(tmp, cursor1, a, dest, len1); + return; + } + if (len1 == 1) { + System.arraycopy(a, cursor2, a, dest, len2); + a[dest + len2] = tmp[cursor1]; // Last elt of run 1 to end of merge + return; + } + + int minGallop = this.minGallop; // Use local variable for performance + outer: + while (true) { + int count1 = 0; // Number of times in a row that first run won + int count2 = 0; // Number of times in a row that second run won + + /* + * Do the straightforward thing until (if ever) one run starts + * winning consistently. + */ + do { + if (DEBUG) assert len1 > 1 && len2 > 0; + if (((Comparable) a[cursor2]).compareTo(tmp[cursor1]) < 0) { + a[dest++] = a[cursor2++]; + count2++; + count1 = 0; + if (--len2 == 0) + break outer; + } else { + a[dest++] = tmp[cursor1++]; + count1++; + count2 = 0; + if (--len1 == 1) + break outer; + } + } while ((count1 | count2) < minGallop); + + /* + * One run is winning so consistently that galloping may be a + * huge win. So try that, and continue galloping until (if ever) + * neither run appears to be winning consistently anymore. + */ + do { + if (DEBUG) assert len1 > 1 && len2 > 0; + count1 = gallopRight((Comparable) a[cursor2], tmp, cursor1, len1, 0); + if (count1 != 0) { + System.arraycopy(tmp, cursor1, a, dest, count1); + dest += count1; + cursor1 += count1; + len1 -= count1; + if (len1 == 1) + break outer; + } + a[dest++] = a[cursor2++]; + if (--len2 == 0) + break outer; + + count2 = gallopLeft((Comparable) tmp[cursor1], a, cursor2, len2, 0); + if (count2 != 0) { + System.arraycopy(a, cursor2, a, dest, count2); + dest += count2; + cursor2 += count2; + len2 -= count2; + if (len2 == 0) + break outer; + } + a[dest++] = tmp[cursor1++]; + if (--len1 == 1) + break outer; + minGallop--; + } while (count1 >= MIN_GALLOP | count2 >= MIN_GALLOP); + if (minGallop < 0) + minGallop = 0; + minGallop += 2; // Penalize for leaving gallop mode + } // End of "outer" loop + this.minGallop = minGallop < 1 ? 1 : minGallop; // Write back to field + + if (len1 == 1) { + if (DEBUG) assert len2 > 0; + System.arraycopy(a, cursor2, a, dest, len2); + a[dest + len2] = tmp[cursor1]; // Last elt of run 1 to end of merge + } else { + if (DEBUG) assert len2 == 0; + if (DEBUG) assert len1 > 1; + System.arraycopy(tmp, cursor1, a, dest, len1); + } + } + + /** + * Like mergeLo, except that this method should be called only if + * len1 >= len2; mergeLo should be called if len1 <= len2. (Either method + * may be called if len1 == len2.) + * + * @param base1 index of first element in first run to be merged + * @param len1 length of first run to be merged (must be > 0) + * @param base2 index of first element in second run to be merged + * (must be aBase + aLen) + * @param len2 length of second run to be merged (must be > 0) + */ + @SuppressWarnings("unchecked") + private void mergeHi(int base1, int len1, int base2, int len2) { + if (DEBUG) assert len1 > 0 && len2 > 0 && base1 + len1 == base2; + + // Copy second run into temp array + Object[] a = this.a; // For performance + Object[] tmp = ensureCapacity(len2); + System.arraycopy(a, base2, tmp, 0, len2); + + int cursor1 = base1 + len1 - 1; // Indexes into a + int cursor2 = 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); + return; + } + if (len2 == 1) { + dest -= len1; + cursor1 -= len1; + System.arraycopy(a, cursor1 + 1, a, dest + 1, len1); + a[dest] = tmp[cursor2]; + return; + } + + int minGallop = this.minGallop; // Use local variable for performance + outer: + while (true) { + int count1 = 0; // Number of times in a row that first run won + int count2 = 0; // Number of times in a row that second run won + + /* + * Do the straightforward thing until (if ever) one run + * appears to win consistently. + */ + do { + if (DEBUG) assert len1 > 0 && len2 > 1; + if (((Comparable) tmp[cursor2]).compareTo(a[cursor1]) < 0) { + a[dest--] = a[cursor1--]; + count1++; + count2 = 0; + if (--len1 == 0) + break outer; + } else { + a[dest--] = tmp[cursor2--]; + count2++; + count1 = 0; + if (--len2 == 1) + break outer; + } + } while ((count1 | count2) < minGallop); + + /* + * One run is winning so consistently that galloping may be a + * huge win. So try that, and continue galloping until (if ever) + * neither run appears to be winning consistently anymore. + */ + do { + if (DEBUG) assert len1 > 0 && len2 > 1; + count1 = len1 - gallopRight((Comparable) tmp[cursor2], a, base1, len1, len1 - 1); + if (count1 != 0) { + dest -= count1; + cursor1 -= count1; + len1 -= count1; + System.arraycopy(a, cursor1 + 1, a, dest + 1, count1); + if (len1 == 0) + break outer; + } + a[dest--] = tmp[cursor2--]; + if (--len2 == 1) + break outer; + + count2 = len2 - gallopLeft((Comparable) a[cursor1], tmp, 0, len2, len2 - 1); + if (count2 != 0) { + dest -= count2; + cursor2 -= count2; + len2 -= count2; + System.arraycopy(tmp, cursor2 + 1, a, dest + 1, count2); + if (len2 == 1) + break outer; + } + a[dest--] = a[cursor1--]; + if (--len1 == 0) + break outer; + minGallop--; + } while (count1 >= MIN_GALLOP | count2 >= MIN_GALLOP); + if (minGallop < 0) + minGallop = 0; + minGallop += 2; // Penalize for leaving gallop mode + } // End of "outer" loop + this.minGallop = minGallop < 1 ? 1 : minGallop; // Write back to field + + if (len2 == 1) { + if (DEBUG) assert len1 > 0; + dest -= len1; + cursor1 -= len1; + System.arraycopy(a, cursor1 + 1, a, dest + 1, len1); + a[dest] = tmp[cursor2]; // Move first elt of run2 to front of merge + } else { + if (DEBUG) assert len1 == 0; + if (DEBUG) assert len2 > 0; + System.arraycopy(tmp, 0, a, dest - (len2 - 1), len2); + } + } + + /** + * Ensures that the external array tmp has at least the specified + * number of elements, increasing its size if necessary. The size + * increases exponentially to ensure amortized linear time complexity. + * + * @param minCapacity the minimum required capacity of the tmp array + * @return tmp, whether or not it grew + */ + private Object[] ensureCapacity(int minCapacity) { + if (tmp.length < minCapacity) { + // Compute smallest power of 2 > minCapacity + int newSize = minCapacity; + newSize |= newSize >> 1; + newSize |= newSize >> 2; + newSize |= newSize >> 4; + newSize |= newSize >> 8; + newSize |= newSize >> 16; + newSize++; + + if (newSize < 0) // Not bloody likely! + newSize = minCapacity; + else + newSize = Math.min(newSize, a.length >>> 1); + + @SuppressWarnings({"unchecked", "UnnecessaryLocalVariable"}) + Object[] newArray = new Object[newSize]; + tmp = newArray; + } + 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); + } +} diff --git a/luni/src/main/java/java/util/TimSort.java b/luni/src/main/java/java/util/TimSort.java new file mode 100644 index 0000000..3c73a2c --- /dev/null +++ b/luni/src/main/java/java/util/TimSort.java @@ -0,0 +1,918 @@ +/* + * Copyright (C) 2008 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package java.util; + +/** + * A stable, adaptive, iterative mergesort that requires far fewer than + * n lg(n) comparisons when running on partially sorted arrays, while + * offering performance comparable to a traditional mergesort when run + * on random arrays. Like all proper mergesorts, this sort is stable and + * runs O(n log n) time (worst case). In the worst case, this sort requires + * temporary storage space for n/2 object references; in the best case, + * it requires only a small constant amount of space. + * + * This implementation was adapted from Tim Peters's list sort for + * Python, which is described in detail here: + * + * http://svn.python.org/projects/python/trunk/Objects/listsort.txt + * + * Tim's C code may be found here: + * + * http://svn.python.org/projects/python/trunk/Objects/listobject.c + * + * The underlying techniques are described in this paper (and may have + * even earlier origins): + * + * "Optimistic Sorting and Information Theoretic Complexity" + * Peter McIlroy + * SODA (Fourth Annual ACM-SIAM Symposium on Discrete Algorithms), + * pp 467-474, Austin, Texas, 25-27 January 1993. + * + * While the API to this class consists solely of static methods, it is + * (privately) instantiable; a TimSort instance holds the state of an ongoing + * sort, assuming the input array is large enough to warrant the full-blown + * TimSort. Small arrays are sorted in place, using a binary insertion sort. + */ +class TimSort<T> { + /** + * This is the minimum sized sequence that will be merged. Shorter + * sequences will be lengthened by calling binarySort. If the entire + * array is less than this length, no merges will be performed. + * + * This constant should be a power of two. It was 64 in Tim Peter's C + * implementation, but 32 was empirically determined to work better in + * this implementation. In the unlikely event that you set this constant + * to be a number that's not a power of two, you'll need to change the + * {@link #minRunLength} computation. + * + * If you decrease this constant, you must change the stackLen + * computation in the TimSort constructor, or you risk an + * ArrayOutOfBounds exception. See listsort.txt for a discussion + * of the minimum stack length required as a function of the length + * of the array being sorted and the minimum merge sequence length. + */ + private static final int MIN_MERGE = 32; + + /** + * The array being sorted. + */ + private final T[] a; + + /** + * The comparator for this sort. + */ + private final Comparator<? super T> c; + + /** + * When we get into galloping mode, we stay there until both runs win less + * often than MIN_GALLOP consecutive times. + */ + private static final int MIN_GALLOP = 7; + + /** + * This controls when we get *into* galloping mode. It is initialized + * to MIN_GALLOP. The mergeLo and mergeHi methods nudge it higher for + * random data, and lower for highly structured data. + */ + private int minGallop = MIN_GALLOP; + + /** + * Maximum initial size of tmp array, which is used for merging. The array + * can grow to accommodate demand. + * + * Unlike Tim's original C version, we do not allocate this much storage + * when sorting smaller arrays. This change was required for performance. + */ + private static final int INITIAL_TMP_STORAGE_LENGTH = 256; + + /** + * Temp storage for merges. + */ + private T[] tmp; // Actual runtime type will be Object[], regardless of T + + /** + * A stack of pending runs yet to be merged. Run i starts at + * address base[i] and extends for len[i] elements. It's always + * true (so long as the indices are in bounds) that: + * + * runBase[i] + runLen[i] == runBase[i + 1] + * + * so we could cut the storage for this, but it's a minor amount, + * and keeping all the info explicit simplifies the code. + */ + private int stackSize = 0; // Number of pending runs on stack + private final int[] runBase; + private final int[] runLen; + + /** + * Asserts have been placed in if-statements for performace. To enable them, + * set this field to true and enable them in VM with a command line flag. + * If you modify this class, please do test the asserts! + */ + private static final boolean DEBUG = false; + + /** + * Creates a TimSort instance to maintain the state of an ongoing sort. + * + * @param a the array to be sorted + * @param c the comparator to determine the order of the sort + */ + private TimSort(T[] a, Comparator<? super T> c) { + 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; + + /* + * Allocate runs-to-be-merged stack (which cannot be expanded). The + * stack length requirements are described in listsort.txt. The C + * version always uses the same stack length (85), but this was + * measured to be too expensive when sorting "mid-sized" arrays (e.g., + * 100 elements) in Java. Therefore, we use smaller (but sufficiently + * large) stack lengths for smaller arrays. The "magic numbers" in the + * computation below must be changed if MIN_MERGE is decreased. See + * the MIN_MERGE declaration above for more information. + */ + int stackLen = (len < 120 ? 5 : + len < 1542 ? 10 : + len < 119151 ? 19 : 40); + runBase = new int[stackLen]; + runLen = new int[stackLen]; + } + + /* + * The next two methods (which are package private and static) constitute + * the entire API of this class. Each of these methods obeys the contract + * of the public method with the same signature in java.util.Arrays. + */ + + static <T> void sort(T[] a, Comparator<? super T> c) { + sort(a, 0, a.length, c); + } + + 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 + + // If array is small, do a "mini-TimSort" with no merges + if (nRemaining < MIN_MERGE) { + int initRunLen = countRunAndMakeAscending(a, lo, nRemaining, c); + binarySort(a, lo, hi, lo + initRunLen, c); + return; + } + + /** + * March over the array once, left to right, finding natural runs, + * extending short natural runs to minRun elements, and merging runs + * to maintain stack invariant. + */ + TimSort<T> ts = new TimSort<T>(a, c); + int minRun = minRunLength(nRemaining); + do { + // Identify next run + int runLen = countRunAndMakeAscending(a, lo, hi, c); + + // If run is short, extend to min(minRun, nRemaining) + if (runLen < minRun) { + int force = nRemaining <= minRun ? nRemaining : minRun; + binarySort(a, lo, lo + force, lo + runLen, c); + runLen = force; + } + + // Push run onto pending-run stack, and maybe merge + ts.pushRun(lo, runLen); + ts.mergeCollapse(); + + // Advance to find next run + lo += runLen; + nRemaining -= runLen; + } while (nRemaining != 0); + + // Merge all remaining runs to complete sort + if (DEBUG) assert lo == hi; + ts.mergeForceCollapse(); + if (DEBUG) assert ts.stackSize == 1; + } + + /** + * Sorts the specified portion of the specified array using a binary + * insertion sort. This is the best method for sorting small numbers + * of elements. It requires O(n log n) compares, but O(n^2) data + * movement (worst case). + * + * If the initial part of the specified range is already sorted, + * this method can take advantage of it: the method assumes that the + * elements from index {@code lo}, inclusive, to {@code start}, + * exclusive are already sorted. + * + * @param a the array in which a range is to be sorted + * @param lo the index of the first element in the range to be sorted + * @param hi the index after the last element in the range to be sorted + * @param start the index of the first element in the range that is + * not already known to be sorted (@code lo <= start <= hi} + * @param c comparator to used for the sort + */ + @SuppressWarnings("fallthrough") + private static <T> void binarySort(T[] a, int lo, int hi, int start, + Comparator<? super T> c) { + if (DEBUG) assert lo <= start && start <= hi; + if (start == lo) + start++; + for ( ; start < hi; start++) { + T pivot = a[start]; + + // Set left (and right) to the index where a[start] (pivot) belongs + int left = lo; + int right = start; + if (DEBUG) assert left <= right; + /* + * Invariants: + * pivot >= all in [lo, left). + * pivot < all in [right, start). + */ + while (left < right) { + int mid = (left + right) >>> 1; + if (c.compare(pivot, a[mid]) < 0) + right = mid; + else + left = mid + 1; + } + if (DEBUG) assert left == right; + + /* + * The invariants still hold: pivot >= all in [lo, left) and + * pivot < all in [left, start), so pivot belongs at left. Note + * that if there are elements equal to pivot, left points to the + * first slot after them -- that's why this sort is stable. + * Slide elements over to make room to make room for pivot. + */ + int n = start - left; // The number of elements to move + // Switch is just an optimization for arraycopy in default case + switch(n) { + case 2: a[left + 2] = a[left + 1]; + case 1: a[left + 1] = a[left]; + break; + default: System.arraycopy(a, left, a, left + 1, n); + } + a[left] = pivot; + } + } + + /** + * Returns the length of the run beginning at the specified position in + * the specified array and reverses the run if it is descending (ensuring + * that the run will always be ascending when the method returns). + * + * A run is the longest ascending sequence with: + * + * a[lo] <= a[lo + 1] <= a[lo + 2] <= ... + * + * or the longest descending sequence with: + * + * a[lo] > a[lo + 1] > a[lo + 2] > ... + * + * For its intended use in a stable mergesort, the strictness of the + * definition of "descending" is needed so that the call can safely + * reverse a descending sequence without violating stability. + * + * @param a the array in which a run is to be counted and possibly reversed + * @param lo index of the first element in the run + * @param hi index after the last element that may be contained in the run. + It is required that @code{lo < hi}. + * @param c the comparator to used for the sort + * @return the length of the run beginning at the specified position in + * the specified array + */ + private static <T> int countRunAndMakeAscending(T[] a, int lo, int hi, + Comparator<? super T> c) { + if (DEBUG) assert lo < hi; + int runHi = lo + 1; + if (runHi == hi) + return 1; + + // Find end of run, and reverse range if descending + if (c.compare(a[runHi++], a[lo]) < 0) { // Descending + while(runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0) + runHi++; + reverseRange(a, lo, runHi); + } else { // Ascending + while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0) + runHi++; + } + + return runHi - lo; + } + + /** + * Reverse the specified range of the specified array. + * + * @param a the array in which a range is to be reversed + * @param lo the index of the first element in the range to be reversed + * @param hi the index after the last element in the range to be reversed + */ + private static void reverseRange(Object[] a, int lo, int hi) { + hi--; + while (lo < hi) { + Object t = a[lo]; + a[lo++] = a[hi]; + a[hi--] = t; + } + } + + /** + * Returns the minimum acceptable run length for an array of the specified + * length. Natural runs shorter than this will be extended with + * {@link #binarySort}. + * + * Roughly speaking, the computation is: + * + * If n < MIN_MERGE, return n (it's too small to bother with fancy stuff). + * Else if n is an exact power of 2, return MIN_MERGE/2. + * Else return an int k, MIN_MERGE/2 <= k <= MIN_MERGE, such that n/k + * is close to, but strictly less than, an exact power of 2. + * + * For the rationale, see listsort.txt. + * + * @param n the length of the array to be sorted + * @return the length of the minimum run to be merged + */ + private static int minRunLength(int n) { + if (DEBUG) assert n >= 0; + int r = 0; // Becomes 1 if any 1 bits are shifted off + while (n >= MIN_MERGE) { + r |= (n & 1); + n >>= 1; + } + return n + r; + } + + /** + * Pushes the specified run onto the pending-run stack. + * + * @param runBase index of the first element in the run + * @param runLen the number of elements in the run + */ + private void pushRun(int runBase, int runLen) { + this.runBase[stackSize] = runBase; + this.runLen[stackSize] = runLen; + stackSize++; + } + + /** + * Examines the stack of runs waiting to be merged and merges adjacent runs + * until the stack invariants are reestablished: + * + * 1. runLen[i - 3] > runLen[i - 2] + runLen[i - 1] + * 2. runLen[i - 2] > runLen[i - 1] + * + * This method is called each time a new run is pushed onto the stack, + * so the invariants are guaranteed to hold for i < stackSize upon + * entry to the method. + */ + private void mergeCollapse() { + while (stackSize > 1) { + int n = stackSize - 2; + if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) { + if (runLen[n - 1] < runLen[n + 1]) + n--; + mergeAt(n); + } else if (runLen[n] <= runLen[n + 1]) { + mergeAt(n); + } else { + break; // Invariant is established + } + } + } + + /** + * Merges all runs on the stack until only one remains. This method is + * called once, to complete the sort. + */ + private void mergeForceCollapse() { + while (stackSize > 1) { + int n = stackSize - 2; + if (n > 0 && runLen[n - 1] < runLen[n + 1]) + n--; + mergeAt(n); + } + } + + /** + * Merges the two runs at stack indices i and i+1. Run i must be + * the penultimate or antepenultimate run on the stack. In other words, + * i must be equal to stackSize-2 or stackSize-3. + * + * @param i stack index of the first of the two runs to merge + */ + private void mergeAt(int i) { + if (DEBUG) assert stackSize >= 2; + if (DEBUG) assert i >= 0; + if (DEBUG) assert i == stackSize - 2 || i == stackSize - 3; + + int base1 = runBase[i]; + int len1 = runLen[i]; + int base2 = runBase[i + 1]; + int len2 = runLen[i + 1]; + if (DEBUG) assert len1 > 0 && len2 > 0; + if (DEBUG) assert base1 + len1 == base2; + + /* + * Record the length of the combined runs; if i is the 3rd-last + * run now, also slide over the last run (which isn't involved + * in this merge). The current run (i+1) goes away in any case. + */ + runLen[i] = len1 + len2; + if (i == stackSize - 3) { + runBase[i + 1] = runBase[i + 2]; + runLen[i + 1] = runLen[i + 2]; + } + stackSize--; + + /* + * Find where the first element of run2 goes in run1. Prior elements + * in run1 can be ignored (because they're already in place). + */ + int k = gallopRight(a[base2], a, base1, len1, 0, c); + if (DEBUG) assert k >= 0; + base1 += k; + len1 -= k; + if (len1 == 0) + return; + + /* + * Find where the last element of run1 goes in run2. Subsequent elements + * in run2 can be ignored (because they're already in place). + */ + len2 = gallopLeft(a[base1 + len1 - 1], a, base2, len2, len2 - 1, c); + if (DEBUG) assert len2 >= 0; + if (len2 == 0) + return; + + // Merge remaining runs, using tmp array with min(len1, len2) elements + if (len1 <= len2) + mergeLo(base1, len1, base2, len2); + else + mergeHi(base1, len1, base2, len2); + } + + /** + * Locates the position at which to insert the specified key into the + * specified sorted range; if the range contains an element equal to key, + * returns the index of the leftmost equal element. + * + * @param key the key whose insertion point to search for + * @param a the array in which to search + * @param base the index of the first element in the range + * @param len the length of the range; must be > 0 + * @param hint the index at which to begin the search, 0 <= hint < n. + * The closer hint is to the result, the faster this method will run. + * @param c the comparator used to order the range, and to search + * @return the int k, 0 <= k <= n such that a[b + k - 1] < key <= a[b + k], + * pretending that a[b - 1] is minus infinity and a[b + n] is infinity. + * In other words, key belongs at index b + k; or in other words, + * the first k elements of a should precede key, and the last n - k + * should follow it. + */ + private static <T> int gallopLeft(T key, T[] a, int base, int len, int hint, + Comparator<? super T> c) { + if (DEBUG) assert len > 0 && hint >= 0 && hint < len; + int lastOfs = 0; + int ofs = 1; + if (c.compare(key, a[base + hint]) > 0) { + // Gallop right until a[base+hint+lastOfs] < key <= a[base+hint+ofs] + int maxOfs = len - hint; + while (ofs < maxOfs && c.compare(key, a[base + hint + ofs]) > 0) { + lastOfs = ofs; + ofs = (ofs << 1) + 1; + if (ofs <= 0) // int overflow + ofs = maxOfs; + } + if (ofs > maxOfs) + ofs = maxOfs; + + // Make offsets relative to base + lastOfs += hint; + ofs += hint; + } else { // key <= a[base + hint] + // Gallop left until a[base+hint-ofs] < key <= a[base+hint-lastOfs] + final int maxOfs = hint + 1; + while (ofs < maxOfs && c.compare(key, a[base + hint - ofs]) <= 0) { + lastOfs = ofs; + ofs = (ofs << 1) + 1; + if (ofs <= 0) // int overflow + ofs = maxOfs; + } + if (ofs > maxOfs) + ofs = maxOfs; + + // Make offsets relative to base + int tmp = lastOfs; + lastOfs = hint - ofs; + ofs = hint - tmp; + } + if (DEBUG) assert -1 <= lastOfs && lastOfs < ofs && ofs <= len; + + /* + * Now a[base+lastOfs] < key <= a[base+ofs], so key belongs somewhere + * to the right of lastOfs but no farther right than ofs. Do a binary + * search, with invariant a[base + lastOfs - 1] < key <= a[base + ofs]. + */ + lastOfs++; + while (lastOfs < ofs) { + int m = lastOfs + ((ofs - lastOfs) >>> 1); + + if (c.compare(key, a[base + m]) > 0) + lastOfs = m + 1; // a[base + m] < key + else + ofs = m; // key <= a[base + m] + } + if (DEBUG) assert lastOfs == ofs; // so a[base + ofs - 1] < key <= a[base + ofs] + return ofs; + } + + /** + * Like gallopLeft, except that if the range contains an element equal to + * key, gallopRight returns the index after the rightmost equal element. + * + * @param key the key whose insertion point to search for + * @param a the array in which to search + * @param base the index of the first element in the range + * @param len the length of the range; must be > 0 + * @param hint the index at which to begin the search, 0 <= hint < n. + * The closer hint is to the result, the faster this method will run. + * @param c the comparator used to order the range, and to search + * @return the int k, 0 <= k <= n such that a[b + k - 1] <= key < a[b + k] + */ + private static <T> int gallopRight(T key, T[] a, int base, int len, + int hint, Comparator<? super T> c) { + if (DEBUG) assert len > 0 && hint >= 0 && hint < len; + + int ofs = 1; + int lastOfs = 0; + if (c.compare(key, a[base + hint]) < 0) { + // Gallop left until a[b+hint - ofs] <= key < a[b+hint - lastOfs] + int maxOfs = hint + 1; + while (ofs < maxOfs && c.compare(key, a[base + hint - ofs]) < 0) { + lastOfs = ofs; + ofs = (ofs << 1) + 1; + if (ofs <= 0) // int overflow + ofs = maxOfs; + } + if (ofs > maxOfs) + ofs = maxOfs; + + // Make offsets relative to b + int tmp = lastOfs; + lastOfs = hint - ofs; + ofs = hint - tmp; + } else { // a[b + hint] <= key + // Gallop right until a[b+hint + lastOfs] <= key < a[b+hint + ofs] + int maxOfs = len - hint; + while (ofs < maxOfs && c.compare(key, a[base + hint + ofs]) >= 0) { + lastOfs = ofs; + ofs = (ofs << 1) + 1; + if (ofs <= 0) // int overflow + ofs = maxOfs; + } + if (ofs > maxOfs) + ofs = maxOfs; + + // Make offsets relative to b + lastOfs += hint; + ofs += hint; + } + if (DEBUG) assert -1 <= lastOfs && lastOfs < ofs && ofs <= len; + + /* + * Now a[b + lastOfs] <= key < a[b + ofs], so key belongs somewhere to + * the right of lastOfs but no farther right than ofs. Do a binary + * search, with invariant a[b + lastOfs - 1] <= key < a[b + ofs]. + */ + lastOfs++; + while (lastOfs < ofs) { + int m = lastOfs + ((ofs - lastOfs) >>> 1); + + if (c.compare(key, a[base + m]) < 0) + ofs = m; // key < a[b + m] + else + lastOfs = m + 1; // a[b + m] <= key + } + if (DEBUG) assert lastOfs == ofs; // so a[b + ofs - 1] <= key < a[b + ofs] + return ofs; + } + + /** + * Merges two adjacent runs in place, in a stable fashion. The first + * element of the first run must be greater than the first element of the + * second run (a[base1] > a[base2]), and the last element of the first run + * (a[base1 + len1-1]) must be greater than all elements of the second run. + * + * For performance, this method should be called only when len1 <= len2; + * its twin, mergeHi should be called if len1 >= len2. (Either method + * may be called if len1 == len2.) + * + * @param base1 index of first element in first run to be merged + * @param len1 length of first run to be merged (must be > 0) + * @param base2 index of first element in second run to be merged + * (must be aBase + aLen) + * @param len2 length of second run to be merged (must be > 0) + */ + private void mergeLo(int base1, int len1, int base2, int len2) { + if (DEBUG) assert len1 > 0 && len2 > 0 && base1 + len1 == base2; + + // 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 cursor2 = base2; // Indexes int a + int dest = base1; // Indexes int a + + // Move first element of second run and deal with degenerate cases + a[dest++] = a[cursor2++]; + if (--len2 == 0) { + System.arraycopy(tmp, cursor1, a, dest, len1); + return; + } + if (len1 == 1) { + System.arraycopy(a, cursor2, a, dest, len2); + a[dest + len2] = tmp[cursor1]; // Last elt of run 1 to end of merge + return; + } + + Comparator<? super T> c = this.c; // Use local variable for performance + int minGallop = this.minGallop; // " " " " " + outer: + while (true) { + int count1 = 0; // Number of times in a row that first run won + int count2 = 0; // Number of times in a row that second run won + + /* + * Do the straightforward thing until (if ever) one run starts + * winning consistently. + */ + do { + if (DEBUG) assert len1 > 1 && len2 > 0; + if (c.compare(a[cursor2], tmp[cursor1]) < 0) { + a[dest++] = a[cursor2++]; + count2++; + count1 = 0; + if (--len2 == 0) + break outer; + } else { + a[dest++] = tmp[cursor1++]; + count1++; + count2 = 0; + if (--len1 == 1) + break outer; + } + } while ((count1 | count2) < minGallop); + + /* + * One run is winning so consistently that galloping may be a + * huge win. So try that, and continue galloping until (if ever) + * neither run appears to be winning consistently anymore. + */ + do { + if (DEBUG) assert len1 > 1 && len2 > 0; + count1 = gallopRight(a[cursor2], tmp, cursor1, len1, 0, c); + if (count1 != 0) { + System.arraycopy(tmp, cursor1, a, dest, count1); + dest += count1; + cursor1 += count1; + len1 -= count1; + if (len1 == 1) + break outer; + } + a[dest++] = a[cursor2++]; + if (--len2 == 0) + break outer; + + count2 = gallopLeft(tmp[cursor1], a, cursor2, len2, 0, c); + if (count2 != 0) { + System.arraycopy(a, cursor2, a, dest, count2); + dest += count2; + cursor2 += count2; + len2 -= count2; + if (len2 == 0) + break outer; + } + a[dest++] = tmp[cursor1++]; + if (--len1 == 1) + break outer; + minGallop--; + } while (count1 >= MIN_GALLOP | count2 >= MIN_GALLOP); + if (minGallop < 0) + minGallop = 0; + minGallop += 2; // Penalize for leaving gallop mode + } // End of "outer" loop + this.minGallop = minGallop < 1 ? 1 : minGallop; // Write back to field + + if (len1 == 1) { + if (DEBUG) assert len2 > 0; + System.arraycopy(a, cursor2, a, dest, len2); + a[dest + len2] = tmp[cursor1]; // Last elt of run 1 to end of merge + } else { + if (DEBUG) assert len2 == 0; + if (DEBUG) assert len1 > 1; + System.arraycopy(tmp, cursor1, a, dest, len1); + } + } + + /** + * Like mergeLo, except that this method should be called only if + * len1 >= len2; mergeLo should be called if len1 <= len2. (Either method + * may be called if len1 == len2.) + * + * @param base1 index of first element in first run to be merged + * @param len1 length of first run to be merged (must be > 0) + * @param base2 index of first element in second run to be merged + * (must be aBase + aLen) + * @param len2 length of second run to be merged (must be > 0) + */ + private void mergeHi(int base1, int len1, int base2, int len2) { + if (DEBUG) assert len1 > 0 && len2 > 0 && base1 + len1 == base2; + + // Copy second run into temp array + T[] a = this.a; // For performance + T[] tmp = ensureCapacity(len2); + System.arraycopy(a, base2, tmp, 0, len2); + + int cursor1 = base1 + len1 - 1; // Indexes into a + int cursor2 = 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); + return; + } + if (len2 == 1) { + dest -= len1; + cursor1 -= len1; + System.arraycopy(a, cursor1 + 1, a, dest + 1, len1); + a[dest] = tmp[cursor2]; + return; + } + + Comparator<? super T> c = this.c; // Use local variable for performance + int minGallop = this.minGallop; // " " " " " + outer: + while (true) { + int count1 = 0; // Number of times in a row that first run won + int count2 = 0; // Number of times in a row that second run won + + /* + * Do the straightforward thing until (if ever) one run + * appears to win consistently. + */ + do { + if (DEBUG) assert len1 > 0 && len2 > 1; + if (c.compare(tmp[cursor2], a[cursor1]) < 0) { + a[dest--] = a[cursor1--]; + count1++; + count2 = 0; + if (--len1 == 0) + break outer; + } else { + a[dest--] = tmp[cursor2--]; + count2++; + count1 = 0; + if (--len2 == 1) + break outer; + } + } while ((count1 | count2) < minGallop); + + /* + * One run is winning so consistently that galloping may be a + * huge win. So try that, and continue galloping until (if ever) + * neither run appears to be winning consistently anymore. + */ + do { + if (DEBUG) assert len1 > 0 && len2 > 1; + count1 = len1 - gallopRight(tmp[cursor2], a, base1, len1, len1 - 1, c); + if (count1 != 0) { + dest -= count1; + cursor1 -= count1; + len1 -= count1; + System.arraycopy(a, cursor1 + 1, a, dest + 1, count1); + if (len1 == 0) + break outer; + } + a[dest--] = tmp[cursor2--]; + if (--len2 == 1) + break outer; + + count2 = len2 - gallopLeft(a[cursor1], tmp, 0, len2, len2 - 1, c); + if (count2 != 0) { + dest -= count2; + cursor2 -= count2; + len2 -= count2; + System.arraycopy(tmp, cursor2 + 1, a, dest + 1, count2); + if (len2 == 1) + break outer; + } + a[dest--] = a[cursor1--]; + if (--len1 == 0) + break outer; + minGallop--; + } while (count1 >= MIN_GALLOP | count2 >= MIN_GALLOP); + if (minGallop < 0) + minGallop = 0; + minGallop += 2; // Penalize for leaving gallop mode + } // End of "outer" loop + this.minGallop = minGallop < 1 ? 1 : minGallop; // Write back to field + + if (len2 == 1) { + if (DEBUG) assert len1 > 0; + dest -= len1; + cursor1 -= len1; + System.arraycopy(a, cursor1 + 1, a, dest + 1, len1); + a[dest] = tmp[cursor2]; // Move first elt of run2 to front of merge + } else { + if (DEBUG) assert len1 == 0; + if (DEBUG) assert len2 > 0; + System.arraycopy(tmp, 0, a, dest - (len2 - 1), len2); + } + } + + /** + * Ensures that the external array tmp has at least the specified + * number of elements, increasing its size if necessary. The size + * increases exponentially to ensure amortized linear time complexity. + * + * @param minCapacity the minimum required capacity of the tmp array + * @return tmp, whether or not it grew + */ + private T[] ensureCapacity(int minCapacity) { + if (tmp.length < minCapacity) { + // Compute smallest power of 2 > minCapacity + int newSize = minCapacity; + newSize |= newSize >> 1; + newSize |= newSize >> 2; + newSize |= newSize >> 4; + newSize |= newSize >> 8; + newSize |= newSize >> 16; + newSize++; + + if (newSize < 0) // Not bloody likely! + newSize = minCapacity; + else + newSize = Math.min(newSize, a.length >>> 1); + + @SuppressWarnings({"unchecked", "UnnecessaryLocalVariable"}) + T[] newArray = (T[]) new Object[newSize]; + tmp = newArray; + } + 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); + } +} diff --git a/luni/src/main/java/org/apache/harmony/luni/internal/net/www/protocol/http/Header.java b/luni/src/main/java/org/apache/harmony/luni/internal/net/www/protocol/http/Header.java index 2718199..1f7589d 100644 --- a/luni/src/main/java/org/apache/harmony/luni/internal/net/www/protocol/http/Header.java +++ b/luni/src/main/java/org/apache/harmony/luni/internal/net/www/protocol/http/Header.java @@ -150,8 +150,6 @@ public class Header implements Cloneable { * Lists of Strings. * * @return an unmodifiable map of the headers - * - * @since 1.4 */ public Map<String, List<String>> getFieldMap() { Map<String, List<String>> result = new HashMap<String, List<String>>( diff --git a/luni/src/main/java/org/apache/harmony/luni/internal/net/www/protocol/http/HttpURLConnection.java b/luni/src/main/java/org/apache/harmony/luni/internal/net/www/protocol/http/HttpURLConnection.java index 76432e6..6f5a2be 100644 --- a/luni/src/main/java/org/apache/harmony/luni/internal/net/www/protocol/http/HttpURLConnection.java +++ b/luni/src/main/java/org/apache/harmony/luni/internal/net/www/protocol/http/HttpURLConnection.java @@ -141,23 +141,41 @@ public class HttpURLConnection extends java.net.HttpURLConnection { throwClosed(); } - return is.read(); + int result = is.read(); + if (useCaches && cacheOut != null) { + cacheOut.write(result); + } + return result; } public int read(byte[] b, int off, int len) throws IOException { if (closed) { throwClosed(); } - - return is.read(b, off, len); + int result = is.read(b, off, len); + if (result > 0) { + // if user has set useCache to true and cache exists, writes to + // it + if (useCaches && cacheOut != null) { + cacheOut.write(b, off, result); + } + } + return result; } public int read(byte[] b) throws IOException { if (closed) { throwClosed(); } - - return is.read(b); + int result = is.read(b); + if (result > 0) { + // if user has set useCache to true and cache exists, writes to + // it + if (useCaches && cacheOut != null) { + cacheOut.write(b, 0, result); + } + } + return result; } public long skip(long n) throws IOException { @@ -178,6 +196,9 @@ public class HttpURLConnection extends java.net.HttpURLConnection { public void close() { closed = true; + if (useCaches && cacheRequest != null) { + cacheRequest.abort(); + } } public void mark(int readLimit) { @@ -1000,8 +1021,6 @@ public class HttpURLConnection extends java.net.HttpURLConnection { * header field values associated with that key name. * * @return the mapping of header field names to values - * - * @since 1.4 */ @Override public Map<String, List<String>> getHeaderFields() { diff --git a/luni/src/main/java/org/apache/harmony/luni/util/Inet6Util.java b/luni/src/main/java/org/apache/harmony/luni/util/Inet6Util.java index b062aee..8c8257b 100644 --- a/luni/src/main/java/org/apache/harmony/luni/util/Inet6Util.java +++ b/luni/src/main/java/org/apache/harmony/luni/util/Inet6Util.java @@ -144,7 +144,10 @@ public class Inet6Util { } - static String hexCharacters = "0123456789ABCDEF"; + // BEGIN android-changed + static char[] hexCharacters = {'0', '1', '2', '3', '4', '5', '6', '7', '8', + '9', 'a', 'b', 'c', 'd', 'e', 'f'}; + // END android-changed public static String createIPAddrStringFromByteArray(byte ipByteArray[]) { if (ipByteArray.length == 4) { @@ -160,15 +163,31 @@ public class Inet6Util { return addressToString(bytesToInt(ipv4ByteArray, 0)); } StringBuilder buffer = new StringBuilder(); - for (int i = 0; i < ipByteArray.length; i++) { - int j = (ipByteArray[i] & 0xf0) >>> 4; - buffer.append(hexCharacters.charAt(j)); - j = ipByteArray[i] & 0x0f; - buffer.append(hexCharacters.charAt(j)); - if (i % 2 != 0 && (i + 1) < ipByteArray.length) { + // BEGIN android-changed + for (int i = 0; i < 8; i++) { // ipByteArray.length / 2 + + int num = (ipByteArray[2 * i] & 0xff) << 8; + num ^= ipByteArray[2 * i + 1] & 0xff; + + // count the digits to display without leading 0 + int count = 1, j = num; + while ((j >>>= 4) != 0) { + count++; + } + + char[] buf = new char[count]; + do { + int t = num & 0x0f; + buf[--count] = hexCharacters[t]; + num >>>= 4; + } while (count > 0); + + buffer.append(buf); + if ((i + 1) < 8) { // ipByteArray.length / 2 buffer.append(":"); } } + // END android-changed return buffer.toString(); } return null; @@ -293,6 +312,21 @@ public class Inet6Util { + ((value >> 8) & 0xff) + "." + (value & 0xff); } + // BEGIN android-added + // copied from a newer version of harmony + public static boolean isIP6AddressInFullForm(String ipAddress) { + if (isValidIP6Address(ipAddress)) { + int doubleColonIndex = ipAddress.indexOf("::"); + if (doubleColonIndex >= 0) { + // Simplified form which contains :: + return false; + } + return true; + } + return false; + } + // END android-added + public static boolean isValidIP6Address(String ipAddress) { int length = ipAddress.length(); boolean doubleColon = false; @@ -501,4 +535,5 @@ public class Inet6Util { } // END android-changed } + } |