OpenJDK / amber / amber
changeset 3534:bb2fd58dae03
Merge
| author | duke |
|---|---|
| date | Wed, 05 Jul 2017 16:59:08 +0200 |
| parents | c311084b506d b7436f6e6495 |
| children | b00e0c1a3f23 |
| files | jdk/test/java/util/concurrent/ConcurrentLinkedQueue/ConcurrentQueueLoops.java jdk/test/java/util/concurrent/ConcurrentLinkedQueue/LoopHelpers.java |
| diffstat | 296 files changed, 30951 insertions(+), 2223 deletions(-) [+] |
line wrap: on
line diff
--- a/.hgtags-top-repo Tue Aug 18 16:15:37 2009 -0700 +++ b/.hgtags-top-repo Wed Jul 05 16:59:08 2017 +0200 @@ -43,3 +43,4 @@ 6bad5e3fe50337d95b1416d744780d65bc570da6 jdk7-b66 c4523c6f82048f420bf0d57c4cd47976753b7d2c jdk7-b67 e1b972ff53cd58f825791f8ed9b2deffd16e768c jdk7-b68 +82e6c820c51ac27882b77755d42efefdbf1dcda0 jdk7-b69
--- a/THIRD_PARTY_README Tue Aug 18 16:15:37 2009 -0700 +++ b/THIRD_PARTY_README Wed Jul 05 16:59:08 2017 +0200 @@ -32,7 +32,7 @@ --- end of LICENSE file --- %% This notice is provided with respect to ASM, which may be included with this software: -Copyright (c) 2000-2005 INRIA, France Telecom +Copyright (c) 2000-2007 INRIA, France Telecom All rights reserved. Redistribution and use in source and binary forms, with or without
--- a/corba/.hgtags Tue Aug 18 16:15:37 2009 -0700 +++ b/corba/.hgtags Wed Jul 05 16:59:08 2017 +0200 @@ -43,3 +43,4 @@ a821e059a961bcb02830280d51f6dd030425c066 jdk7-b66 a12ea7c7b497b4ba7830550095ef633bd6f43971 jdk7-b67 5182bcc9c60cac429d1f7988676cec7320752be3 jdk7-b68 +8120d308ec4e805c5588b8d9372844d781c4112d jdk7-b69
--- a/corba/THIRD_PARTY_README Tue Aug 18 16:15:37 2009 -0700 +++ b/corba/THIRD_PARTY_README Wed Jul 05 16:59:08 2017 +0200 @@ -32,7 +32,7 @@ --- end of LICENSE file --- %% This notice is provided with respect to ASM, which may be included with this software: -Copyright (c) 2000-2005 INRIA, France Telecom +Copyright (c) 2000-2007 INRIA, France Telecom All rights reserved. Redistribution and use in source and binary forms, with or without
--- a/hotspot/.hgtags Tue Aug 18 16:15:37 2009 -0700 +++ b/hotspot/.hgtags Wed Jul 05 16:59:08 2017 +0200 @@ -43,3 +43,4 @@ 57c71ad0341b8b64ed20f81151eb7f06324f8894 jdk7-b66 18f526145aea355a9320b724373386fc2170f183 jdk7-b67 d07e68298d4e17ebf93d8299e43fcc3ded26472a jdk7-b68 +54fd4d9232969ea6cd3d236e5ad276183bb0d423 jdk7-b69
--- a/hotspot/THIRD_PARTY_README Tue Aug 18 16:15:37 2009 -0700 +++ b/hotspot/THIRD_PARTY_README Wed Jul 05 16:59:08 2017 +0200 @@ -32,7 +32,7 @@ --- end of LICENSE file --- %% This notice is provided with respect to ASM, which may be included with this software: -Copyright (c) 2000-2005 INRIA, France Telecom +Copyright (c) 2000-2007 INRIA, France Telecom All rights reserved. Redistribution and use in source and binary forms, with or without
--- a/jaxp/.hgtags Tue Aug 18 16:15:37 2009 -0700 +++ b/jaxp/.hgtags Wed Jul 05 16:59:08 2017 +0200 @@ -43,3 +43,4 @@ 22f9d5d5b5fe0f47048f41e6c6e54fee5edad0ec jdk7-b66 a033af8d824a408d3ac602205ecdefc128749e1e jdk7-b67 83b2a9331383f9db7a49350d4cb13b7635f6b861 jdk7-b68 +a4ab0d6ded63bed0fd1e5be55d38090e0ee5efb7 jdk7-b69
--- a/jaxp/THIRD_PARTY_README Tue Aug 18 16:15:37 2009 -0700 +++ b/jaxp/THIRD_PARTY_README Wed Jul 05 16:59:08 2017 +0200 @@ -32,7 +32,7 @@ --- end of LICENSE file --- %% This notice is provided with respect to ASM, which may be included with this software: -Copyright (c) 2000-2005 INRIA, France Telecom +Copyright (c) 2000-2007 INRIA, France Telecom All rights reserved. Redistribution and use in source and binary forms, with or without
--- a/jaxp/src/share/classes/com/sun/org/apache/xerces/internal/impl/XMLScanner.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jaxp/src/share/classes/com/sun/org/apache/xerces/internal/impl/XMLScanner.java Wed Jul 05 16:59:08 2017 +0200 @@ -1027,6 +1027,9 @@ int c = fEntityScanner.peekChar(); if (XMLChar.isMarkup(c) || c == ']') { fStringBuffer.append((char)fEntityScanner.scanChar()); + } else if (c != -1 && isInvalidLiteral(c)) { + reportFatalError("InvalidCharInSystemID", + new Object[] {Integer.toString(c, 16)}); } } while (fEntityScanner.scanLiteral(quote, ident) != quote); fStringBuffer.append(ident);
--- a/jdk/.hgtags Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/.hgtags Wed Jul 05 16:59:08 2017 +0200 @@ -43,3 +43,4 @@ bd31b30a5b21f20e42965b1633f18a5c7946d398 jdk7-b66 a952aafd5181af953b0ef3010dbd2fcc28460e8a jdk7-b67 b23d905cb5d3b382295240d28ab0bfb266b4503c jdk7-b68 +226b20019b1f020c09ea97d137d98e011ce65d76 jdk7-b69
--- a/jdk/THIRD_PARTY_README Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/THIRD_PARTY_README Wed Jul 05 16:59:08 2017 +0200 @@ -32,7 +32,7 @@ --- end of LICENSE file --- %% This notice is provided with respect to ASM, which may be included with this software: -Copyright (c) 2000-2005 INRIA, France Telecom +Copyright (c) 2000-2007 INRIA, France Telecom All rights reserved. Redistribution and use in source and binary forms, with or without
--- a/jdk/make/java/java/FILES_java.gmk Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/make/java/java/FILES_java.gmk Wed Jul 05 16:59:08 2017 +0200 @@ -77,6 +77,7 @@ java/lang/Compiler.java \ java/lang/Throwable.java \ java/lang/Exception.java \ + java/lang/ReflectiveOperationException.java \ java/lang/IllegalAccessException.java \ java/lang/InstantiationException.java \ java/lang/ClassNotFoundException.java \ @@ -250,6 +251,8 @@ java/util/IdentityHashMap.java \ java/util/EnumMap.java \ java/util/Arrays.java \ + java/util/TimSort.java \ + java/util/ComparableTimSort.java \ java/util/ConcurrentModificationException.java \ java/util/ServiceLoader.java \ java/util/ServiceConfigurationError.java \
--- a/jdk/make/sun/net/FILES_java.gmk Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/make/sun/net/FILES_java.gmk Wed Jul 05 16:59:08 2017 +0200 @@ -41,6 +41,7 @@ sun/net/NetProperties.java \ sun/net/NetHooks.java \ sun/net/util/IPAddressUtil.java \ + sun/net/util/URLUtil.java \ sun/net/dns/ResolverConfiguration.java \ sun/net/dns/ResolverConfigurationImpl.java \ sun/net/ftp/FtpClient.java \
--- a/jdk/make/sun/security/Makefile Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/make/sun/security/Makefile Wed Jul 05 16:59:08 2017 +0200 @@ -1,5 +1,5 @@ # -# Copyright 1996-2007 Sun Microsystems, Inc. All Rights Reserved. +# Copyright 1996-2009 Sun Microsystems, Inc. All Rights Reserved. # DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. # # This code is free software; you can redistribute it and/or modify it @@ -60,7 +60,7 @@ endif endif -SUBDIRS = other action util tools jgss krb5 smartcardio $(PKCS11) \ +SUBDIRS = ec other action util tools jgss krb5 smartcardio $(PKCS11) \ $(JGSS_WRAPPER) $(MSCAPI) all build clean clobber::
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/jdk/make/sun/security/ec/FILES_c.gmk Wed Jul 05 16:59:08 2017 +0200 @@ -0,0 +1,54 @@ +# +# Copyright 2009 Sun Microsystems, Inc. All Rights Reserved. +# DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. +# +# This code is free software; you can redistribute it and/or modify it +# under the terms of the GNU General Public License version 2 only, as +# published by the Free Software Foundation. Sun designates this +# particular file as subject to the "Classpath" exception as provided +# by Sun in the LICENSE file that accompanied this code. +# +# This code is distributed in the hope that it will be useful, but WITHOUT +# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or +# FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +# version 2 for more details (a copy is included in the LICENSE file that +# accompanied this code). +# +# You should have received a copy of the GNU General Public License version +# 2 along with this work; if not, write to the Free Software Foundation, +# Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. +# +# Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, +# CA 95054 USA or visit www.sun.com if you need additional information or +# have any questions. +# + +FILES_c = \ + ec.c \ + ec2_163.c \ + ec2_193.c \ + ec2_233.c \ + ec2_aff.c \ + ec2_mont.c \ + ecdecode.c \ + ecl.c \ + ecl_curve.c \ + ecl_gf.c \ + ecl_mult.c \ + ec_naf.c \ + ecp_192.c \ + ecp_224.c \ + ecp_256.c \ + ecp_384.c \ + ecp_521.c \ + ecp_aff.c \ + ecp_jac.c \ + ecp_jm.c \ + ecp_mont.c \ + mp_gf2m.c \ + mpi.c \ + mplogic.c \ + mpmontg.c \ + oid.c \ + secitem.c +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/jdk/make/sun/security/ec/Makefile Wed Jul 05 16:59:08 2017 +0200 @@ -0,0 +1,319 @@ +# +# Copyright 2009 Sun Microsystems, Inc. All Rights Reserved. +# DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. +# +# This code is free software; you can redistribute it and/or modify it +# under the terms of the GNU General Public License version 2 only, as +# published by the Free Software Foundation. Sun designates this +# particular file as subject to the "Classpath" exception as provided +# by Sun in the LICENSE file that accompanied this code. +# +# This code is distributed in the hope that it will be useful, but WITHOUT +# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or +# FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +# version 2 for more details (a copy is included in the LICENSE file that +# accompanied this code). +# +# You should have received a copy of the GNU General Public License version +# 2 along with this work; if not, write to the Free Software Foundation, +# Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. +# +# Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, +# CA 95054 USA or visit www.sun.com if you need additional information or +# have any questions. +# + +# +# Makefile for building sunec.jar and sunecc native library. +# +# This file was derived from make/com/sun/crypto/provider/Makefile. +# + +# +# (The terms "OpenJDK" and "JDK" below refer to OpenJDK and Sun JDK builds +# respectively.) +# +# JCE builds are very different between OpenJDK and JDK. The OpenJDK JCE +# jar files do not require signing, but those for JDK do. If an unsigned +# jar file is installed into JDK, things will break when the crypto +# routines are called. +# +# This Makefile does the "real" build of the JCE files. For OpenJDK, +# the jar files built here are installed directly into the OpenJDK. +# +# For JDK, the binaries use pre-built/pre-signed binary files stored in +# the closed workspace that are not shipped in the OpenJDK workspaces. +# We still build the JDK files here to verify the files compile, and in +# preparation for possible signing. Developers working on JCE in JDK +# must sign the JCE files before testing. The JCE signing key is kept +# separate from the JDK workspace to prevent its disclosure. +# +# SPECIAL NOTE TO JCE/JDK developers: The source files must eventually +# be built, signed, and then the resulting jar files MUST BE CHECKED +# INTO THE CLOSED PART OF THE WORKSPACE*. This separate step *MUST NOT +# BE FORGOTTEN*, otherwise a bug fixed in the source code will not be +# reflected in the shipped binaries. The "release" target should be +# used to generate the required files. +# +# There are a number of targets to help both JDK/OpenJDK developers. +# +# Main Targets (JDK/OPENJDK): +# +# all/clobber/clean The usual, plus the native libraries. +# If OpenJDK, installs sunec.jar. +# If JDK, installs prebuilt +# sunec.jar. +# +# jar Builds/installs sunec.jar +# If OpenJDK, does not sign. +# If JDK, tries to sign. +# +# Other lesser-used Targets (JDK/OPENJDK): +# +# build-jar Builds sunec.jar +# (does not sign/install) +# +# install-jar Alias for "jar" above. +# +# Other targets (JDK only): +# +# sign Alias for sign-jar +# sign-jar Builds/signs sunec.jar (no install) +# +# release Builds all targets in preparation +# for workspace integration. +# +# install-prebuilt Installs the pre-built jar files +# +# This makefile was written to support parallel target execution. +# + +BUILDDIR = ../../.. +PACKAGE = sun.security.ec +PRODUCT = sun + +# +# The following is for when we need to do postprocessing +# (signing) against a read-only build. If the OUTPUTDIR +# isn't writable, the build currently crashes out. +# +ifndef OPENJDK + ifdef ALT_JCE_BUILD_DIR + # ===================================================== + # Where to place the output, in case we're building from a read-only + # build area. (e.g. a release engineering build.) + JCE_BUILD_DIR=${ALT_JCE_BUILD_DIR} + IGNORE_WRITABLE_OUTPUTDIR_TEST=true + else + JCE_BUILD_DIR=${TEMPDIR} + endif +endif + +include $(BUILDDIR)/common/Defs.gmk + +# +# Location for the newly built classfiles. +# +CLASSDESTDIR = $(TEMPDIR)/classes + +# +# Java files +# +AUTO_FILES_JAVA_DIRS = $(PKGDIR) + +include $(BUILDDIR)/common/Classes.gmk + +# +# Some licensees do not get the native ECC sources, but we still need to +# be able to build "all" for them. Check here to see if the sources are +# available. If not, then skip them. +# + +NATIVE_ECC_AVAILABLE := $(shell \ + if [ -d $(SHARE_SRC)/native/$(PKGDIR) ] ; then \ + $(ECHO) true; \ + else \ + $(ECHO) false; \ + fi) + +ifeq ($(NATIVE_ECC_AVAILABLE), true) + + LIBRARY = sunecc + + # + # Java files that define native methods + # + FILES_export = \ + $(PKGDIR)/ECDHKeyAgreement.java \ + $(PKGDIR)/ECDSASignature.java \ + $(PKGDIR)/ECKeyPairGenerator.java + + JAVAHFLAGS += -classpath $(CLASSDESTDIR) + + # + # C and C++ files + # + include FILES_c.gmk + + FILES_cpp = ECC_JNI.cpp + + CPLUSPLUSLIBRARY=true + + FILES_m = mapfile-vers + + # + # Find native code + # + vpath %.cpp $(SHARE_SRC)/native/$(PKGDIR) + + vpath %.c $(SHARE_SRC)/native/$(PKGDIR) + + # + # Find include files + # + OTHER_INCLUDES += -I$(SHARE_SRC)/native/$(PKGDIR) + + # + # Compiler flags + # + OTHER_CFLAGS += -DMP_API_COMPATIBLE -DNSS_ECC_MORE_THAN_SUITE_B + + # + # Libraries to link + # + ifeq ($(PLATFORM), windows) + OTHER_LDLIBS += $(JVMLIB) + else + OTHER_LDLIBS = -ldl $(JVMLIB) $(LIBCXX) + endif + + include $(BUILDDIR)/common/Mapfile-vers.gmk + + include $(BUILDDIR)/common/Library.gmk + +endif # NATIVE_ECC_AVAILABLE + +# +# We use a variety of subdirectories in the $(TEMPDIR) depending on what +# part of the build we're doing. Both OPENJDK/JDK builds are initially +# done in the unsigned area. When files are signed in JDK, +# they will be placed in the appropriate area. +# +UNSIGNED_DIR = $(TEMPDIR)/unsigned + +include $(BUILDDIR)/javax/crypto/Defs-jce.gmk + +# +# Rules +# + +ifdef OPENJDK +all: build-jar install-jar +else +all: build-jar install-prebuilt + $(build-warning) +endif + + +# ===================================================== +# Build the unsigned sunec.jar file. +# + +JAR_DESTFILE = $(EXTDIR)/sunec.jar + +# +# Since the -C option to jar is used below, each directory entry must be +# preceded with the appropriate directory to "cd" into. +# +JAR_DIRS = $(patsubst %, -C $(CLASSDESTDIR) %, $(AUTO_FILES_JAVA_DIRS)) + +build-jar: $(UNSIGNED_DIR)/sunec.jar + +# +# Build sunec.jar. +# +$(UNSIGNED_DIR)/sunec.jar: build + $(prep-target) + $(BOOT_JAR_CMD) cf $@ $(JAR_DIRS) \ + $(BOOT_JAR_JFLAGS) + @$(java-vm-cleanup) + + +ifndef OPENJDK +# ===================================================== +# Sign the provider jar file. Not needed for OpenJDK. +# + +SIGNED_DIR = $(JCE_BUILD_DIR)/signed + +sign: sign-jar + +sign-jar: $(SIGNED_DIR)/sunec.jar + +ifndef ALT_JCE_BUILD_DIR +$(SIGNED_DIR)/sunec.jar: $(UNSIGNED_DIR)/sunec.jar +else +# +# We have to remove the build dependency, otherwise, we'll try to rebuild it +# which we can't do on a read-only filesystem. +# +$(SIGNED_DIR)/sunec.jar: + @if [ ! -r $(UNSIGNED_DIR)/sunec.jar ] ; then \ + $(ECHO) "Couldn't find $(UNSIGNED_DIR)/sunec.jar"; \ + exit 1; \ + fi +endif + $(call sign-file, $(UNSIGNED_DIR)/sunec.jar) + + +# ===================================================== +# Create the Release Engineering files. Signed builds, etc. +# + +release: $(SIGNED_DIR)/sunec.jar + $(RM) $(JCE_BUILD_DIR)/release/sunec.jar + $(MKDIR) -p $(JCE_BUILD_DIR)/release + $(CP) $(SIGNED_DIR)/sunec.jar $(JCE_BUILD_DIR)/release + $(release-warning) + +endif # OPENJDK + + +# ===================================================== +# Install routines. +# + +# +# Install sunec.jar, depending on which type is requested. +# +install-jar jar: $(JAR_DESTFILE) +ifndef OPENJDK + $(release-warning) +endif + +ifdef OPENJDK +$(JAR_DESTFILE): $(UNSIGNED_DIR)/sunec.jar +else +$(JAR_DESTFILE): $(SIGNED_DIR)/sunec.jar +endif + $(install-file) + +ifndef OPENJDK +install-prebuilt: + @$(ECHO) "\n>>>Installing prebuilt SunEC provider..." + $(RM) $(JAR_DESTFILE) + $(CP) $(PREBUILT_DIR)/ec/sunec.jar $(JAR_DESTFILE) +endif + + +# ===================================================== +# Support routines. +# + +clobber clean:: + $(RM) -r $(JAR_DESTFILE) $(TEMPDIR) $(JCE_BUILD_DIR) + +.PHONY: build-jar jar install-jar +ifndef OPENJDK +.PHONY: sign sign-jar release install-prebuilt +endif
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/jdk/make/sun/security/ec/mapfile-vers Wed Jul 05 16:59:08 2017 +0200 @@ -0,0 +1,37 @@ +# +# Copyright 2009 Sun Microsystems, Inc. All Rights Reserved. +# DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. +# +# This code is free software; you can redistribute it and/or modify it +# under the terms of the GNU General Public License version 2 only, as +# published by the Free Software Foundation. Sun designates this +# particular file as subject to the "Classpath" exception as provided +# by Sun in the LICENSE file that accompanied this code. +# +# This code is distributed in the hope that it will be useful, but WITHOUT +# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or +# FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +# version 2 for more details (a copy is included in the LICENSE file that +# accompanied this code). +# +# You should have received a copy of the GNU General Public License version +# 2 along with this work; if not, write to the Free Software Foundation, +# Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. +# +# Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, +# CA 95054 USA or visit www.sun.com if you need additional information or +# have any questions. +# + +# Define public interface. + +SUNWprivate_1.1 { + global: + Java_sun_security_ec_ECKeyPairGenerator_generateECKeyPair; + Java_sun_security_ec_ECKeyPairGenerator_getEncodedBytes; + Java_sun_security_ec_ECDSASignature_signDigest; + Java_sun_security_ec_ECDSASignature_verifySignedDigest; + Java_sun_security_ec_ECDHKeyAgreement_deriveKey; + local: + *; +};
--- a/jdk/make/sun/security/other/Makefile Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/make/sun/security/other/Makefile Wed Jul 05 16:59:08 2017 +0200 @@ -1,5 +1,5 @@ # -# Copyright 1996-2007 Sun Microsystems, Inc. All Rights Reserved. +# Copyright 1996-2009 Sun Microsystems, Inc. All Rights Reserved. # DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. # # This code is free software; you can redistribute it and/or modify it @@ -33,7 +33,6 @@ # AUTO_FILES_JAVA_DIRS = \ sun/security/acl \ - sun/security/ec \ sun/security/jca \ sun/security/pkcs \ sun/security/pkcs12 \
--- a/jdk/make/tools/CharsetMapping/IBM420.c2b Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/make/tools/CharsetMapping/IBM420.c2b Wed Jul 05 16:59:08 2017 +0200 @@ -1,1 +1,187 @@ -0x15 U+0085 +# +# The diff of 01A434B0.TXMAP110 and 34B001A4.RXMAP110 +# +# Added: 0x15 U+0085 +# +0x15 U+0085 +0x42 U+FE7C +0x46 U+FE80 +0x47 U+FE81 +0x49 U+FE83 +0x4B U+066C +0x4B U+FF0E +0x4C U+FF1C +0x4D U+FF08 +0x4E U+FF0B +0x4F U+FF5C +0x50 U+FF06 +0x52 U+FE85 +0x52 U+FE86 +0x55 U+FE89 +0x55 U+FE8A +0x55 U+FE8B +0x55 U+FE8C +0x56 U+0625 +0x56 U+FE87 +0x56 U+FE8D +0x57 U+FE88 +0x58 U+FE8F +0x58 U+FE90 +0x59 U+FE92 +0x5A U+FF01 +0x5B U+FF04 +0x5C U+066D +0x5C U+FF0A +0x5D U+FF09 +0x5E U+FF1B +0x60 U+FF0D +0x61 U+FF0F +0x62 U+FE93 +0x62 U+FE94 +0x63 U+FE95 +0x63 U+FE96 +0x64 U+FE98 +0x65 U+FE99 +0x65 U+FE9A +0x66 U+FE9C +0x67 U+FE9D +0x67 U+FE9E +0x68 U+FEA0 +0x69 U+FEA1 +0x69 U+FEA2 +0x6B U+066B +0x6B U+FF0C +0x6C U+066A +0x6C U+FF05 +0x6D U+FF3F +0x6E U+FF1E +0x6F U+FF1F +0x70 U+FEA4 +0x71 U+FEA5 +0x71 U+FEA6 +0x72 U+FEA8 +0x73 U+FEA9 +0x73 U+FEAA +0x74 U+FEAB +0x74 U+FEAC +0x75 U+FEAD +0x75 U+FEAE +0x76 U+FEAF +0x76 U+FEB0 +0x77 U+FEB1 +0x77 U+FEB2 +0x78 U+FEB4 +0x7A U+FF1A +0x7B U+FF03 +0x7C U+FF20 +0x7D U+FF07 +0x7E U+FF1D +0x7F U+FF02 +0x80 U+FEB5 +0x80 U+FEB6 +0x81 U+FF41 +0x82 U+FF42 +0x83 U+FF43 +0x84 U+FF44 +0x85 U+FF45 +0x86 U+FF46 +0x87 U+FF47 +0x88 U+FF48 +0x89 U+FF49 +0x8A U+FEB8 +0x8B U+FEB9 +0x8B U+FEBA +0x8C U+FEBC +0x8D U+FEBD +0x8D U+FEBE +0x8E U+FEC0 +0x8F U+FEC1 +0x8F U+FEC2 +0x8F U+FEC3 +0x8F U+FEC4 +0x90 U+FEC5 +0x90 U+FEC6 +0x90 U+FEC7 +0x90 U+FEC8 +0x91 U+FF4A +0x92 U+FF4B +0x93 U+FF4C +0x94 U+FF4D +0x95 U+FF4E +0x96 U+FF4F +0x97 U+FF50 +0x98 U+FF51 +0x99 U+FF52 +0x9A U+FEC9 +0x9E U+FECD +0xA2 U+FF53 +0xA3 U+FF54 +0xA4 U+FF55 +0xA5 U+FF56 +0xA6 U+FF57 +0xA7 U+FF58 +0xA8 U+FF59 +0xA9 U+FF5A +0xAB U+FED1 +0xAB U+FED2 +0xAC U+FED4 +0xAD U+FED5 +0xAD U+FED6 +0xAE U+FED8 +0xAF U+FED9 +0xAF U+FEDA +0xB0 U+FEDC +0xB1 U+FEDD +0xB1 U+FEDE +0xB8 U+FEF9 +0xB9 U+FEFA +0xBA U+FEE0 +0xBB U+FEE1 +0xBB U+FEE2 +0xBC U+FEE4 +0xBD U+FEE5 +0xBD U+FEE6 +0xBE U+FEE8 +0xBF U+FEE9 +0xBF U+FEEA +0xC1 U+FF21 +0xC2 U+FF22 +0xC3 U+FF23 +0xC4 U+FF24 +0xC5 U+FF25 +0xC6 U+FF26 +0xC7 U+FF27 +0xC8 U+FF28 +0xC9 U+FF29 +0xCF U+FEED +0xCF U+FEEE +0xD1 U+FF2A +0xD2 U+FF2B +0xD3 U+FF2C +0xD4 U+FF2D +0xD5 U+FF2E +0xD6 U+FF2F +0xD7 U+FF30 +0xD8 U+FF31 +0xD9 U+FF32 +0xDA U+FEEF +0xDC U+FEF1 +0xDE U+FEF4 +0xE2 U+FF33 +0xE3 U+FF34 +0xE4 U+FF35 +0xE5 U+FF36 +0xE6 U+FF37 +0xE7 U+FF38 +0xE8 U+FF39 +0xE9 U+FF3A +0xF0 U+FF10 +0xF1 U+FF11 +0xF2 U+FF12 +0xF3 U+FF13 +0xF4 U+FF14 +0xF5 U+FF15 +0xF6 U+FF16 +0xF7 U+FF17 +0xF8 U+FF18 +0xF9 U+FF19
--- a/jdk/make/tools/CharsetMapping/IBM420.map Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/make/tools/CharsetMapping/IBM420.map Wed Jul 05 16:59:08 2017 +0200 @@ -1,257 +1,253 @@ -#Generated from IBM420.java -0x00 U+0000 -0x01 U+0001 -0x02 U+0002 -0x03 U+0003 -0x04 U+009c -0x05 U+0009 -0x06 U+0086 -0x07 U+007f -0x08 U+0097 -0x09 U+008d -0x0a U+008e -0x0b U+000b -0x0c U+000c -0x0d U+000d -0x0e U+000e -0x0f U+000f -0x10 U+0010 -0x11 U+0011 -0x12 U+0012 -0x13 U+0013 -0x14 U+009d -0x15 U+000a -0x16 U+0008 -0x17 U+0087 -0x18 U+0018 -0x19 U+0019 -0x1a U+0092 -0x1b U+008f -0x1c U+001c -0x1d U+001d -0x1e U+001e -0x1f U+001f -0x20 U+0080 -0x21 U+0081 -0x22 U+0082 -0x23 U+0083 -0x24 U+0084 -0x25 U+000a -0x26 U+0017 -0x27 U+001b -0x28 U+0088 -0x29 U+0089 -0x2a U+008a -0x2b U+008b -0x2c U+008c -0x2d U+0005 -0x2e U+0006 -0x2f U+0007 -0x30 U+0090 -0x31 U+0091 -0x32 U+0016 -0x33 U+0093 -0x34 U+0094 -0x35 U+0095 -0x36 U+0096 -0x37 U+0004 -0x38 U+0098 -0x39 U+0099 -0x3a U+009a -0x3b U+009b -0x3c U+0014 -0x3d U+0015 -0x3e U+009e -0x3f U+001a -0x40 U+0020 -0x41 U+00a0 -0x42 U+fe7c -0x43 U+fe7d -0x44 U+0640 -0x45 U+f8fc -0x46 U+fe80 -0x47 U+fe81 -0x48 U+fe82 -0x49 U+fe83 -0x4a U+00a2 -0x4b U+002e -0x4c U+003c -0x4d U+0028 -0x4e U+002b -0x4f U+007c -0x50 U+0026 -0x51 U+fe84 -0x52 U+fe85 -0x53 U+fffd -0x54 U+fffd -0x55 U+fe8b -0x56 U+fe8d -0x57 U+fe8e -0x58 U+fe8f -0x59 U+fe91 -0x5a U+0021 -0x5b U+0024 -0x5c U+002a -0x5d U+0029 -0x5e U+003b -0x5f U+00ac -0x60 U+002d -0x61 U+002f -0x62 U+fe93 -0x63 U+fe95 -0x64 U+fe97 -0x65 U+fe99 -0x66 U+fe9b -0x67 U+fe9d -0x68 U+fe9f -0x69 U+fea1 -0x6a U+00a6 -0x6b U+002c -0x6c U+0025 -0x6d U+005f -0x6e U+003e -0x6f U+003f -0x70 U+fea3 -0x71 U+fea5 -0x72 U+fea7 -0x73 U+fea9 -0x74 U+feab -0x75 U+fead -0x76 U+feaf -0x77 U+f8f6 -0x78 U+feb3 -0x79 U+060c -0x7a U+003a -0x7b U+0023 -0x7c U+0040 -0x7d U+0027 -0x7e U+003d -0x7f U+0022 -0x80 U+f8f5 -0x81 U+0061 -0x82 U+0062 -0x83 U+0063 -0x84 U+0064 -0x85 U+0065 -0x86 U+0066 -0x87 U+0067 -0x88 U+0068 -0x89 U+0069 -0x8a U+feb7 -0x8b U+f8f4 -0x8c U+febb -0x8d U+f8f7 -0x8e U+febf -0x8f U+fec3 -0x90 U+fec7 -0x91 U+006a -0x92 U+006b -0x93 U+006c -0x94 U+006d -0x95 U+006e -0x96 U+006f -0x97 U+0070 -0x98 U+0071 -0x99 U+0072 -0x9a U+fec9 -0x9b U+feca -0x9c U+fecb -0x9d U+fecc -0x9e U+fecd -0x9f U+fece -0xa0 U+fecf -0xa1 U+00f7 -0xa2 U+0073 -0xa3 U+0074 -0xa4 U+0075 -0xa5 U+0076 -0xa6 U+0077 -0xa7 U+0078 -0xa8 U+0079 -0xa9 U+007a -0xaa U+fed0 -0xab U+fed1 -0xac U+fed3 -0xad U+fed5 -0xae U+fed7 -0xaf U+fed9 -0xb0 U+fedb -0xb1 U+fedd -0xb2 U+fef5 -0xb3 U+fef6 -0xb4 U+fef7 -0xb5 U+fef8 -0xb6 U+fffd -0xb7 U+fffd -0xb8 U+fefb -0xb9 U+fefc -0xba U+fedf -0xbb U+fee1 -0xbc U+fee3 -0xbd U+fee5 -0xbe U+fee7 -0xbf U+fee9 -0xc0 U+061b -0xc1 U+0041 -0xc2 U+0042 -0xc3 U+0043 -0xc4 U+0044 -0xc5 U+0045 -0xc6 U+0046 -0xc7 U+0047 -0xc8 U+0048 -0xc9 U+0049 -0xca U+00ad -0xcb U+feeb -0xcc U+fffd -0xcd U+feec -0xce U+fffd -0xcf U+feed -0xd0 U+061f -0xd1 U+004a -0xd2 U+004b -0xd3 U+004c -0xd4 U+004d -0xd5 U+004e -0xd6 U+004f -0xd7 U+0050 -0xd8 U+0051 -0xd9 U+0052 -0xda U+feef -0xdb U+fef0 -0xdc U+fef1 -0xdd U+fef2 -0xde U+fef3 -0xdf U+0660 -0xe0 U+00d7 -0xe1 U+2007 -0xe2 U+0053 -0xe3 U+0054 -0xe4 U+0055 -0xe5 U+0056 -0xe6 U+0057 -0xe7 U+0058 -0xe8 U+0059 -0xe9 U+005a -0xea U+0661 -0xeb U+0662 -0xec U+fffd -0xed U+0663 -0xee U+0664 -0xef U+0665 -0xf0 U+0030 -0xf1 U+0031 -0xf2 U+0032 -0xf3 U+0033 -0xf4 U+0034 -0xf5 U+0035 -0xf6 U+0036 -0xf7 U+0037 -0xf8 U+0038 -0xf9 U+0039 -0xfa U+fffd -0xfb U+0666 -0xfc U+0667 -0xfd U+0668 -0xfe U+0669 -0xff U+009f +# +# Frm IBMCDC datatable 01A434B0.TXMAP110 +# +# Changed +# 0x15 U+0085 -> 0x15 U+000a +# +0x00 U+0000 +0x01 U+0001 +0x02 U+0002 +0x03 U+0003 +0x04 U+009C +0x05 U+0009 +0x06 U+0086 +0x07 U+007F +0x08 U+0097 +0x09 U+008D +0x0A U+008E +0x0B U+000B +0x0C U+000C +0x0D U+000D +0x0E U+000E +0x0F U+000F +0x10 U+0010 +0x11 U+0011 +0x12 U+0012 +0x13 U+0013 +0x14 U+009D +0x15 U+000A +0x16 U+0008 +0x17 U+0087 +0x18 U+0018 +0x19 U+0019 +0x1A U+0092 +0x1B U+008F +0x1C U+001C +0x1D U+001D +0x1E U+001E +0x1F U+001F +0x20 U+0080 +0x21 U+0081 +0x22 U+0082 +0x23 U+0083 +0x24 U+0084 +0x25 U+000A +0x26 U+0017 +0x27 U+001B +0x28 U+0088 +0x29 U+0089 +0x2A U+008A +0x2B U+008B +0x2C U+008C +0x2D U+0005 +0x2E U+0006 +0x2F U+0007 +0x30 U+0090 +0x31 U+0091 +0x32 U+0016 +0x33 U+0093 +0x34 U+0094 +0x35 U+0095 +0x36 U+0096 +0x37 U+0004 +0x38 U+0098 +0x39 U+0099 +0x3A U+009A +0x3B U+009B +0x3C U+0014 +0x3D U+0015 +0x3E U+009E +0x3F U+001A +0x40 U+0020 +0x41 U+00A0 +0x42 U+0651 +0x43 U+FE7D +0x44 U+0640 +0x45 U+200B +0x46 U+0621 +0x47 U+0622 +0x48 U+FE82 +0x49 U+0623 +0x4A U+00A2 +0x4B U+002E +0x4C U+003C +0x4D U+0028 +0x4E U+002B +0x4F U+007C +0x50 U+0026 +0x51 U+FE84 +0x52 U+0624 +0x55 U+0626 +0x56 U+0627 +0x57 U+FE8E +0x58 U+0628 +0x59 U+FE91 +0x5A U+0021 +0x5B U+0024 +0x5C U+002A +0x5D U+0029 +0x5E U+003B +0x5F U+00AC +0x60 U+002D +0x61 U+002F +0x62 U+0629 +0x63 U+062A +0x64 U+FE97 +0x65 U+062B +0x66 U+FE9B +0x67 U+062C +0x68 U+FE9F +0x69 U+062D +0x6A U+00A6 +0x6B U+002C +0x6C U+0025 +0x6D U+005F +0x6E U+003E +0x6F U+003F +0x70 U+FEA3 +0x71 U+062E +0x72 U+FEA7 +0x73 U+062F +0x74 U+0630 +0x75 U+0631 +0x76 U+0632 +0x77 U+0633 +0x78 U+FEB3 +0x79 U+060C +0x7A U+003A +0x7B U+0023 +0x7C U+0040 +0x7D U+0027 +0x7E U+003D +0x7F U+0022 +0x80 U+0634 +0x81 U+0061 +0x82 U+0062 +0x83 U+0063 +0x84 U+0064 +0x85 U+0065 +0x86 U+0066 +0x87 U+0067 +0x88 U+0068 +0x89 U+0069 +0x8A U+FEB7 +0x8B U+0635 +0x8C U+FEBB +0x8D U+0636 +0x8E U+FEBF +0x8F U+0637 +0x90 U+0638 +0x91 U+006A +0x92 U+006B +0x93 U+006C +0x94 U+006D +0x95 U+006E +0x96 U+006F +0x97 U+0070 +0x98 U+0071 +0x99 U+0072 +0x9A U+0639 +0x9B U+FECA +0x9C U+FECB +0x9D U+FECC +0x9E U+063A +0x9F U+FECE +0xA0 U+FECF +0xA1 U+00F7 +0xA2 U+0073 +0xA3 U+0074 +0xA4 U+0075 +0xA5 U+0076 +0xA6 U+0077 +0xA7 U+0078 +0xA8 U+0079 +0xA9 U+007A +0xAA U+FED0 +0xAB U+0641 +0xAC U+FED3 +0xAD U+0642 +0xAE U+FED7 +0xAF U+0643 +0xB0 U+FEDB +0xB1 U+0644 +0xB2 U+FEF5 +0xB3 U+FEF6 +0xB4 U+FEF7 +0xB5 U+FEF8 +0xB8 U+FEFB +0xB9 U+FEFC +0xBA U+FEDF +0xBB U+0645 +0xBC U+FEE3 +0xBD U+0646 +0xBE U+FEE7 +0xBF U+0647 +0xC0 U+061B +0xC1 U+0041 +0xC2 U+0042 +0xC3 U+0043 +0xC4 U+0044 +0xC5 U+0045 +0xC6 U+0046 +0xC7 U+0047 +0xC8 U+0048 +0xC9 U+0049 +0xCA U+00AD +0xCB U+FEEB +0xCD U+FEEC +0xCF U+0648 +0xD0 U+061F +0xD1 U+004A +0xD2 U+004B +0xD3 U+004C +0xD4 U+004D +0xD5 U+004E +0xD6 U+004F +0xD7 U+0050 +0xD8 U+0051 +0xD9 U+0052 +0xDA U+0649 +0xDB U+FEF0 +0xDC U+064A +0xDD U+FEF2 +0xDE U+FEF3 +0xDF U+0660 +0xE0 U+00D7 +0xE2 U+0053 +0xE3 U+0054 +0xE4 U+0055 +0xE5 U+0056 +0xE6 U+0057 +0xE7 U+0058 +0xE8 U+0059 +0xE9 U+005A +0xEA U+0661 +0xEB U+0662 +0xED U+0663 +0xEE U+0664 +0xEF U+0665 +0xF0 U+0030 +0xF1 U+0031 +0xF2 U+0032 +0xF3 U+0033 +0xF4 U+0034 +0xF5 U+0035 +0xF6 U+0036 +0xF7 U+0037 +0xF8 U+0038 +0xF9 U+0039 +0xFB U+0666 +0xFC U+0667 +0xFD U+0668 +0xFE U+0669 +0xFF U+009F
--- a/jdk/make/tools/CharsetMapping/IBM420.nr Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/make/tools/CharsetMapping/IBM420.nr Wed Jul 05 16:59:08 2017 +0200 @@ -1,1 +1,1 @@ -0x25 U+000a +0x25 U+000a
--- a/jdk/make/tools/src/build/tools/charsetmapping/GenerateSBCS.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/make/tools/src/build/tools/charsetmapping/GenerateSBCS.java Wed Jul 05 16:59:08 2017 +0200 @@ -26,6 +26,7 @@ package build.tools.charsetmapping; import java.io.*; +import java.util.Arrays; import java.util.ArrayList; import java.util.Scanner; import java.util.Formatter; @@ -54,33 +55,19 @@ String pkgName = fields[4]; System.out.printf("%s,%s,%s,%b,%s%n", clzName, csName, hisName, isASCII, pkgName); - StringBuilder b2c = new StringBuilder(); - int c2bLen = genB2C( - new FileInputStream(new File(args[0], clzName+".map")), b2c); - - String b2cNR = null; - File nrF = new File(args[0], clzName+".nr"); - if (nrF.exists()) { - b2cNR = genNR(new FileInputStream(nrF)); - } - - String c2bNR = null; - File c2bF = new File(args[0], clzName+".c2b"); - if (c2bF.exists()) { - c2bNR = genC2BNR(new FileInputStream(c2bF)); - } - - genSBCSClass(args[0], args[1], "SingleByte-X.java", - clzName, csName, hisName, pkgName, isASCII, - b2c.toString(), b2cNR, c2bNR, c2bLen); + genClass(args[0], args[1], "SingleByte-X.java", + clzName, csName, hisName, pkgName, isASCII); } } private static void toString(char[] sb, int off, int end, - Formatter out, String closure) { + Formatter out, String closure, + boolean comment) { while (off < end) { out.format(" \""); for (int j = 0; j < 8; j++) { + if (off == end) + break; char c = sb[off++]; switch (c) { case '\b': @@ -103,101 +90,124 @@ out.format("\\u%04X", c & 0xffff); } } - if (off == end) - out.format("\" %s // 0x%02x - 0x%02x%n", closure, off-8, off-1); - else - out.format("\" + // 0x%02x - 0x%02x%n", off-8, off-1); + if (comment) { + if (off == end) + out.format("\" %s // 0x%02x - 0x%02x%n", + closure, off-8, off-1); + else + out.format("\" + // 0x%02x - 0x%02x%n", + off-8, off-1); + } else { + if (off == end) + out.format("\"%s%n", closure); + else + out.format("\" +%n"); + } } } static Pattern sbmap = Pattern.compile("0x(\\p{XDigit}++)\\s++U\\+(\\p{XDigit}++)(\\s++#.*)?"); - private static int genB2C(InputStream in, StringBuilder out) + + private static void genClass(String srcDir, String dstDir, + String template, + String clzName, + String csName, + String hisName, + String pkgName, + boolean isASCII) throws Exception { + StringBuilder b2cSB = new StringBuilder(); + StringBuilder b2cNRSB = new StringBuilder(); + StringBuilder c2bNRSB = new StringBuilder(); + char[] sb = new char[0x100]; - int[] indexC2B = new int[0x100]; + char[] c2bIndex = new char[0x100]; + int c2bOff = 0; + Arrays.fill(sb, UNMAPPABLE_DECODING); + Arrays.fill(c2bIndex, UNMAPPABLE_DECODING); - for (int i = 0; i < sb.length; i++) - sb[i] = UNMAPPABLE_DECODING; - - // parse the b2c mapping table + // (1)read in .map to parse all b->c entries + FileInputStream in = new FileInputStream( + new File(srcDir, clzName + ".map")); Parser p = new Parser(in, sbmap); Entry e = null; - int off = 0; + while ((e = p.next()) != null) { sb[e.bs] = (char)e.cp; - if (indexC2B[e.cp>>8] == 0) { - off += 0x100; - indexC2B[e.cp>>8] = 1; + if (c2bIndex[e.cp>>8] == UNMAPPABLE_DECODING) { + c2bOff += 0x100; + c2bIndex[e.cp>>8] = 1; } } - Formatter fm = new Formatter(out); + Formatter fm = new Formatter(b2cSB); fm.format("%n"); // vm -server shows cc[byte + 128] access is much faster than // cc[byte&0xff] so we output the upper segment first - toString(sb, 0x80, 0x100, fm, "+"); - toString(sb, 0x00, 0x80, fm, ";"); + toString(sb, 0x80, 0x100, fm, "+", true); + toString(sb, 0x00, 0x80, fm, ";", true); + fm.close(); - fm.close(); - return off; - } + // (2)now the .nr file which includes "b->c" non-roundtrip entries + File f = new File(srcDir, clzName + ".nr"); + if (f.exists()) { + in = new FileInputStream(f); + fm = new Formatter(b2cNRSB); + p = new Parser(in, sbmap); + e = null; - // generate non-roundtrip entries from xxx.nr file - private static String genNR(InputStream in) throws Exception - { - StringBuilder sb = new StringBuilder(); - Formatter fm = new Formatter(sb); - Parser p = new Parser(in, sbmap); - Entry e = null; - fm.format("// remove non-roundtrip entries%n"); - fm.format(" b2cMap = b2cTable.toCharArray();%n"); - while ((e = p.next()) != null) { - fm.format(" b2cMap[%d] = UNMAPPABLE_DECODING;%n", - (e.bs>=0x80)?(e.bs-0x80):(e.bs+0x80)); - } - fm.close(); - return sb.toString(); - } - - // generate c2b only entries from xxx.c2b file - private static String genC2BNR(InputStream in) throws Exception - { - StringBuilder sb = new StringBuilder(); - Formatter fm = new Formatter(sb); - Parser p = new Parser(in, sbmap); - ArrayList<Entry> es = new ArrayList<Entry>(); - Entry e = null; - while ((e = p.next()) != null) { - es.add(e); + fm.format("// remove non-roundtrip entries%n"); + fm.format(" b2cMap = b2cTable.toCharArray();%n"); + while ((e = p.next()) != null) { + fm.format(" b2cMap[%d] = UNMAPPABLE_DECODING;%n", + (e.bs>=0x80)?(e.bs-0x80):(e.bs+0x80)); + } + fm.close(); } - fm.format("// non-roundtrip c2b only entries%n"); - fm.format(" c2bNR = new char[%d];%n", es.size() * 2); - int i = 0; - for (Entry entry: es) { - fm.format(" c2bNR[%d] = 0x%x; c2bNR[%d] = 0x%x;%n", - i++, entry.bs, i++, entry.cp); + // (3)finally the .c2b file which includes c->b non-roundtrip entries + f = new File(srcDir, clzName + ".c2b"); + if (f.exists()) { + in = new FileInputStream(f); + fm = new Formatter(c2bNRSB); + p = new Parser(in, sbmap); + e = null; + ArrayList<Entry> es = new ArrayList<Entry>(); + while ((e = p.next()) != null) { + if (c2bIndex[e.cp>>8] == UNMAPPABLE_DECODING) { + c2bOff += 0x100; + c2bIndex[e.cp>>8] = 1; + } + es.add(e); + } + fm.format("// non-roundtrip c2b only entries%n"); + if (es.size() < 100) { + fm.format(" c2bNR = new char[%d];%n", es.size() * 2); + int i = 0; + for (Entry entry: es) { + fm.format(" c2bNR[%d] = 0x%x; c2bNR[%d] = 0x%x;%n", + i++, entry.bs, i++, entry.cp); + } + } else { + char[] cc = new char[es.size() * 2]; + int i = 0; + for (Entry entry: es) { + cc[i++] = (char)entry.bs; + cc[i++] = (char)entry.cp; + } + fm.format(" c2bNR = (%n"); + toString(cc, 0, i, fm, ").toCharArray();", false); + } + fm.close(); } - fm.close(); - return sb.toString(); - } - private static void genSBCSClass(String srcDir, - String dstDir, - String template, - String clzName, - String csName, - String hisName, - String pkgName, - boolean isASCII, - String b2c, - String b2cNR, - String c2bNR, - int c2blen) - throws Exception - { + // (4)it's time to generate the source file + String b2c = b2cSB.toString(); + String b2cNR = b2cNRSB.toString(); + String c2bNR = c2bNRSB.toString(); + Scanner s = new Scanner(new File(srcDir, template)); PrintStream out = new PrintStream(new FileOutputStream( new File(dstDir, clzName + ".java"))); @@ -239,16 +249,16 @@ line = line.replace("$B2CTABLE$", b2c); } if (line.indexOf("$C2BLENGTH$") != -1) { - line = line.replace("$C2BLENGTH$", "0x" + Integer.toString(c2blen, 16)); + line = line.replace("$C2BLENGTH$", "0x" + Integer.toString(c2bOff, 16)); } if (line.indexOf("$NONROUNDTRIP_B2C$") != -1) { - if (b2cNR == null) + if (b2cNR.length() == 0) continue; line = line.replace("$NONROUNDTRIP_B2C$", b2cNR); } if (line.indexOf("$NONROUNDTRIP_C2B$") != -1) { - if (c2bNR == null) + if (c2bNR.length() == 0) continue; line = line.replace("$NONROUNDTRIP_C2B$", c2bNR); }
--- a/jdk/src/share/classes/com/sun/beans/finder/BeanInfoFinder.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/com/sun/beans/finder/BeanInfoFinder.java Wed Jul 05 16:59:08 2017 +0200 @@ -48,7 +48,7 @@ } private static boolean isValid(Class<?> type, Method method) { - return (method != null) && type.equals(method.getDeclaringClass()); + return (method != null) && method.getDeclaringClass().isAssignableFrom(type); } @Override
--- a/jdk/src/share/classes/com/sun/imageio/plugins/bmp/BMPImageReaderSpi.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/com/sun/imageio/plugins/bmp/BMPImageReaderSpi.java Wed Jul 05 16:59:08 2017 +0200 @@ -51,7 +51,7 @@ entensions, mimeType, "com.sun.imageio.plugins.bmp.BMPImageReader", - STANDARD_INPUT_TYPE, + new Class[] { ImageInputStream.class }, writerSpiNames, false, null, null, null, null,
--- a/jdk/src/share/classes/com/sun/imageio/plugins/bmp/BMPImageWriterSpi.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/com/sun/imageio/plugins/bmp/BMPImageWriterSpi.java Wed Jul 05 16:59:08 2017 +0200 @@ -32,6 +32,7 @@ import javax.imageio.spi.ImageWriterSpi; import javax.imageio.spi.ServiceRegistry; import javax.imageio.spi.IIORegistry; +import javax.imageio.stream.ImageOutputStream; import javax.imageio.ImageWriter; import javax.imageio.ImageTypeSpecifier; import javax.imageio.IIOException; @@ -55,7 +56,7 @@ entensions, mimeType, "com.sun.imageio.plugins.bmp.BMPImageWriter", - STANDARD_OUTPUT_TYPE, + new Class[] { ImageOutputStream.class }, readerSpiNames, false, null, null, null, null,
--- a/jdk/src/share/classes/com/sun/imageio/plugins/gif/GIFImageReaderSpi.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/com/sun/imageio/plugins/gif/GIFImageReaderSpi.java Wed Jul 05 16:59:08 2017 +0200 @@ -60,7 +60,7 @@ suffixes, MIMETypes, readerClassName, - STANDARD_INPUT_TYPE, + new Class[] { ImageInputStream.class }, writerSpiNames, true, GIFStreamMetadata.nativeMetadataFormatName,
--- a/jdk/src/share/classes/com/sun/imageio/plugins/gif/GIFImageWriterSpi.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/com/sun/imageio/plugins/gif/GIFImageWriterSpi.java Wed Jul 05 16:59:08 2017 +0200 @@ -31,6 +31,7 @@ import javax.imageio.ImageTypeSpecifier; import javax.imageio.ImageWriter; import javax.imageio.spi.ImageWriterSpi; +import javax.imageio.stream.ImageOutputStream; import com.sun.imageio.plugins.common.PaletteBuilder; public class GIFImageWriterSpi extends ImageWriterSpi { @@ -59,7 +60,7 @@ suffixes, MIMETypes, writerClassName, - STANDARD_OUTPUT_TYPE, + new Class[] { ImageOutputStream.class }, readerSpiNames, true, GIFWritableStreamMetadata.NATIVE_FORMAT_NAME,
--- a/jdk/src/share/classes/com/sun/imageio/plugins/jpeg/JPEGImageReaderSpi.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/com/sun/imageio/plugins/jpeg/JPEGImageReaderSpi.java Wed Jul 05 16:59:08 2017 +0200 @@ -46,7 +46,7 @@ JPEG.suffixes, JPEG.MIMETypes, "com.sun.imageio.plugins.jpeg.JPEGImageReader", - STANDARD_INPUT_TYPE, + new Class[] { ImageInputStream.class }, writerSpiNames, true, JPEG.nativeStreamMetadataFormatName,
--- a/jdk/src/share/classes/com/sun/imageio/plugins/jpeg/JPEGImageWriterSpi.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/com/sun/imageio/plugins/jpeg/JPEGImageWriterSpi.java Wed Jul 05 16:59:08 2017 +0200 @@ -28,6 +28,7 @@ import javax.imageio.spi.ImageWriterSpi; import javax.imageio.spi.ServiceRegistry; import javax.imageio.spi.IIORegistry; +import javax.imageio.stream.ImageOutputStream; import javax.imageio.ImageWriter; import javax.imageio.ImageTypeSpecifier; import javax.imageio.IIOException; @@ -49,7 +50,7 @@ JPEG.suffixes, JPEG.MIMETypes, "com.sun.imageio.plugins.jpeg.JPEGImageWriter", - STANDARD_OUTPUT_TYPE, + new Class[] { ImageOutputStream.class }, readerSpiNames, true, JPEG.nativeStreamMetadataFormatName,
--- a/jdk/src/share/classes/com/sun/imageio/plugins/png/PNGImageReaderSpi.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/com/sun/imageio/plugins/png/PNGImageReaderSpi.java Wed Jul 05 16:59:08 2017 +0200 @@ -60,7 +60,7 @@ suffixes, MIMETypes, readerClassName, - STANDARD_INPUT_TYPE, + new Class[] { ImageInputStream.class }, writerSpiNames, false, null, null,
--- a/jdk/src/share/classes/com/sun/imageio/plugins/png/PNGImageWriterSpi.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/com/sun/imageio/plugins/png/PNGImageWriterSpi.java Wed Jul 05 16:59:08 2017 +0200 @@ -34,6 +34,7 @@ import javax.imageio.metadata.IIOMetadataFormat; import javax.imageio.metadata.IIOMetadataFormatImpl; import javax.imageio.spi.ImageWriterSpi; +import javax.imageio.stream.ImageOutputStream; public class PNGImageWriterSpi extends ImageWriterSpi { @@ -61,7 +62,7 @@ suffixes, MIMETypes, writerClassName, - STANDARD_OUTPUT_TYPE, + new Class[] { ImageOutputStream.class }, readerSpiNames, false, null, null,
--- a/jdk/src/share/classes/com/sun/imageio/plugins/wbmp/WBMPImageReaderSpi.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/com/sun/imageio/plugins/wbmp/WBMPImageReaderSpi.java Wed Jul 05 16:59:08 2017 +0200 @@ -55,7 +55,7 @@ entensions, mimeType, "com.sun.imageio.plugins.wbmp.WBMPImageReader", - STANDARD_INPUT_TYPE, + new Class[] { ImageInputStream.class }, writerSpiNames, true, null, null, null, null,
--- a/jdk/src/share/classes/com/sun/imageio/plugins/wbmp/WBMPImageWriterSpi.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/com/sun/imageio/plugins/wbmp/WBMPImageWriterSpi.java Wed Jul 05 16:59:08 2017 +0200 @@ -28,6 +28,7 @@ import javax.imageio.spi.ImageWriterSpi; import javax.imageio.spi.ServiceRegistry; import javax.imageio.spi.IIORegistry; +import javax.imageio.stream.ImageOutputStream; import javax.imageio.ImageWriter; import javax.imageio.ImageTypeSpecifier; import javax.imageio.IIOException; @@ -54,7 +55,7 @@ entensions, mimeType, "com.sun.imageio.plugins.wbmp.WBMPImageWriter", - STANDARD_OUTPUT_TYPE, + new Class[] { ImageOutputStream.class }, readerSpiNames, true, null, null, null, null,
--- a/jdk/src/share/classes/com/sun/imageio/stream/StreamCloser.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/com/sun/imageio/stream/StreamCloser.java Wed Jul 05 16:59:08 2017 +0200 @@ -43,35 +43,35 @@ */ public class StreamCloser { - private static WeakHashMap<ImageInputStream, Object> toCloseQueue; + private static WeakHashMap<CloseAction, Object> toCloseQueue; private static Thread streamCloser; - public static void addToQueue(ImageInputStream iis) { + public static void addToQueue(CloseAction ca) { synchronized (StreamCloser.class) { if (toCloseQueue == null) { toCloseQueue = - new WeakHashMap<ImageInputStream, Object>(); + new WeakHashMap<CloseAction, Object>(); } - toCloseQueue.put(iis, null); + toCloseQueue.put(ca, null); if (streamCloser == null) { final Runnable streamCloserRunnable = new Runnable() { public void run() { if (toCloseQueue != null) { synchronized (StreamCloser.class) { - Set<ImageInputStream> set = + Set<CloseAction> set = toCloseQueue.keySet(); // Make a copy of the set in order to avoid // concurrent modification (the is.close() // will in turn call removeFromQueue()) - ImageInputStream[] streams = - new ImageInputStream[set.size()]; - streams = set.toArray(streams); - for (ImageInputStream is : streams) { - if (is != null) { + CloseAction[] actions = + new CloseAction[set.size()]; + actions = set.toArray(actions); + for (CloseAction ca : actions) { + if (ca != null) { try { - is.close(); + ca.performAction(); } catch (IOException e) { } } @@ -106,10 +106,28 @@ } } - public static void removeFromQueue(ImageInputStream iis) { + public static void removeFromQueue(CloseAction ca) { synchronized (StreamCloser.class) { if (toCloseQueue != null) { - toCloseQueue.remove(iis); + toCloseQueue.remove(ca); + } + } + } + + public static CloseAction createCloseAction(ImageInputStream iis) { + return new CloseAction(iis); + } + + public static final class CloseAction { + private ImageInputStream iis; + + private CloseAction(ImageInputStream iis) { + this.iis = iis; + } + + public void performAction() throws IOException { + if (iis != null) { + iis.close(); } } }
--- a/jdk/src/share/classes/com/sun/jndi/dns/DnsContext.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/com/sun/jndi/dns/DnsContext.java Wed Jul 05 16:59:08 2017 +0200 @@ -1,5 +1,5 @@ /* - * Copyright 2000-2007 Sun Microsystems, Inc. All Rights Reserved. + * Copyright 2000-2009 Sun Microsystems, Inc. All Rights Reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it @@ -922,7 +922,7 @@ //---------- Debugging - public static boolean debug = false; + private static final boolean debug = false; private static final void dprint(String msg) { if (debug) { @@ -972,14 +972,11 @@ } /* - * ctx will be closed when no longer needed by the enumeration. + * ctx will be set to null when no longer needed by the enumeration. */ - public void close () { + public void close() { nodes = null; - if (ctx != null) { - ctx.close(); - ctx = null; - } + ctx = null; } public boolean hasMore() {
--- a/jdk/src/share/classes/com/sun/media/sound/JDK13Services.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/com/sun/media/sound/JDK13Services.java Wed Jul 05 16:59:08 2017 +0200 @@ -1,5 +1,5 @@ /* - * Copyright 1999-2007 Sun Microsystems, Inc. All Rights Reserved. + * Copyright 1999-2009 Sun Microsystems, Inc. All Rights Reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it @@ -41,6 +41,15 @@ import javax.sound.midi.spi.SoundbankReader; import javax.sound.midi.spi.MidiDeviceProvider; +import javax.sound.midi.Receiver; +import javax.sound.midi.Sequencer; +import javax.sound.midi.Synthesizer; +import javax.sound.midi.Transmitter; +import javax.sound.sampled.Clip; +import javax.sound.sampled.Port; +import javax.sound.sampled.SourceDataLine; +import javax.sound.sampled.TargetDataLine; + /** * JDK13Services uses the Service class in JDK 1.3 @@ -186,6 +195,16 @@ If the property is not set, null is returned. */ private static synchronized String getDefaultProvider(Class typeClass) { + if (!SourceDataLine.class.equals(typeClass) + && !TargetDataLine.class.equals(typeClass) + && !Clip.class.equals(typeClass) + && !Port.class.equals(typeClass) + && !Receiver.class.equals(typeClass) + && !Transmitter.class.equals(typeClass) + && !Synthesizer.class.equals(typeClass) + && !Sequencer.class.equals(typeClass)) { + return null; + } String value; String propertyName = typeClass.getName(); value = JSSecurityManager.getProperty(propertyName);
--- a/jdk/src/share/classes/com/sun/media/sound/JSSecurityManager.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/com/sun/media/sound/JSSecurityManager.java Wed Jul 05 16:59:08 2017 +0200 @@ -1,5 +1,5 @@ /* - * Copyright 1999-2007 Sun Microsystems, Inc. All Rights Reserved. + * Copyright 1999-2009 Sun Microsystems, Inc. All Rights Reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it @@ -283,28 +283,37 @@ static List getProviders(final Class providerClass) { - PrivilegedAction action = new PrivilegedAction() { - public Object run() { - List p = new ArrayList(); - Iterator ps = Service.providers(providerClass); - while (ps.hasNext()) { - try { - Object provider = ps.next(); - if (providerClass.isInstance(provider)) { - // $$mp 2003-08-22 - // Always adding at the beginning reverses the - // order of the providers. So we no longer have - // to do this in AudioSystem and MidiSystem. - p.add(0, provider); - } - } catch (Throwable t) { - //$$fb 2002-11-07: do not fail on SPI not found - if (Printer.err) t.printStackTrace(); - } } - return p; + List p = new ArrayList(); + // Service.providers(Class) just creates "lazy" iterator instance, + // so it doesn't require do be called from privileged section + final Iterator ps = Service.providers(providerClass); + + // the iterator's hasNext() method looks through classpath for + // the provider class names, so it requires read permissions + PrivilegedAction<Boolean> hasNextAction = new PrivilegedAction<Boolean>() { + public Boolean run() { + return ps.hasNext(); + } + }; + + while (AccessController.doPrivileged(hasNextAction)) { + try { + // the iterator's next() method creates instances of the + // providers and it should be called in the current security + // context + Object provider = ps.next(); + if (providerClass.isInstance(provider)) { + // $$mp 2003-08-22 + // Always adding at the beginning reverses the + // order of the providers. So we no longer have + // to do this in AudioSystem and MidiSystem. + p.add(0, provider); } - }; - List providers = (List) AccessController.doPrivileged(action); - return providers; + } catch (Throwable t) { + //$$fb 2002-11-07: do not fail on SPI not found + if (Printer.err) t.printStackTrace(); + } + } + return p; } }
--- a/jdk/src/share/classes/com/sun/media/sound/StandardMidiFileWriter.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/com/sun/media/sound/StandardMidiFileWriter.java Wed Jul 05 16:59:08 2017 +0200 @@ -1,5 +1,5 @@ /* - * Copyright 1999-2007 Sun Microsystems, Inc. All Rights Reserved. + * Copyright 1999-2009 Sun Microsystems, Inc. All Rights Reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it @@ -82,7 +82,7 @@ /** * MIDI parser types */ - public static final int types[] = { + private static final int types[] = { MIDI_TYPE_0, MIDI_TYPE_1 };
--- a/jdk/src/share/classes/com/sun/org/apache/xml/internal/security/algorithms/implementations/IntegrityHmac.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/com/sun/org/apache/xml/internal/security/algorithms/implementations/IntegrityHmac.java Wed Jul 05 16:59:08 2017 +0200 @@ -60,8 +60,14 @@ */ public abstract String engineGetURI(); + /** + * Returns the output length of the hash/digest. + */ + abstract int getDigestLength(); + /** Field _macAlgorithm */ private Mac _macAlgorithm = null; + private boolean _HMACOutputLengthSet = false; /** Field _HMACOutputLength */ int _HMACOutputLength = 0; @@ -100,7 +106,9 @@ } public void reset() { - _HMACOutputLength=0; + _HMACOutputLength=0; + _HMACOutputLengthSet = false; + _macAlgorithm.reset(); } /** @@ -115,14 +123,16 @@ throws XMLSignatureException { try { - byte[] completeResult = this._macAlgorithm.doFinal(); - - if ((this._HMACOutputLength == 0) || (this._HMACOutputLength >= 160)) { + if (this._HMACOutputLengthSet && this._HMACOutputLength < getDigestLength()) { + if (log.isLoggable(java.util.logging.Level.FINE)) { + log.log(java.util.logging.Level.FINE, + "HMACOutputLength must not be less than " + getDigestLength()); + } + throw new XMLSignatureException("errorMessages.XMLSignatureException"); + } else { + byte[] completeResult = this._macAlgorithm.doFinal(); return MessageDigestAlgorithm.isEqual(completeResult, signature); } - byte[] stripped = IntegrityHmac.reduceBitLength(completeResult, - this._HMACOutputLength); - return MessageDigestAlgorithm.isEqual(stripped, signature); } catch (IllegalStateException ex) { throw new XMLSignatureException("empty", ex); } @@ -176,14 +186,15 @@ protected byte[] engineSign() throws XMLSignatureException { try { - byte[] completeResult = this._macAlgorithm.doFinal(); - - if ((this._HMACOutputLength == 0) || (this._HMACOutputLength >= 160)) { - return completeResult; + if (this._HMACOutputLengthSet && this._HMACOutputLength < getDigestLength()) { + if (log.isLoggable(java.util.logging.Level.FINE)) { + log.log(java.util.logging.Level.FINE, + "HMACOutputLength must not be less than " + getDigestLength()); + } + throw new XMLSignatureException("errorMessages.XMLSignatureException"); + } else { + return this._macAlgorithm.doFinal(); } - return IntegrityHmac.reduceBitLength(completeResult, - this._HMACOutputLength); - } catch (IllegalStateException ex) { throw new XMLSignatureException("empty", ex); } @@ -361,6 +372,7 @@ */ protected void engineSetHMACOutputLength(int HMACOutputLength) { this._HMACOutputLength = HMACOutputLength; + this._HMACOutputLengthSet = true; } /** @@ -376,12 +388,13 @@ throw new IllegalArgumentException("element null"); } - Text hmaclength =XMLUtils.selectDsNodeText(element.getFirstChild(), - Constants._TAG_HMACOUTPUTLENGTH,0); + Text hmaclength =XMLUtils.selectDsNodeText(element.getFirstChild(), + Constants._TAG_HMACOUTPUTLENGTH,0); - if (hmaclength != null) { - this._HMACOutputLength = Integer.parseInt(hmaclength.getData()); - } + if (hmaclength != null) { + this._HMACOutputLength = Integer.parseInt(hmaclength.getData()); + this._HMACOutputLengthSet = true; + } } @@ -390,14 +403,13 @@ * * @param element */ - public void engineAddContextToElement(Element element) - { + public void engineAddContextToElement(Element element) { if (element == null) { throw new IllegalArgumentException("null element"); } - if (this._HMACOutputLength != 0) { + if (this._HMACOutputLengthSet) { Document doc = element.getOwnerDocument(); Element HMElem = XMLUtils.createElementInSignatureSpace(doc, Constants._TAG_HMACOUTPUTLENGTH); @@ -436,6 +448,10 @@ public String engineGetURI() { return XMLSignature.ALGO_ID_MAC_HMAC_SHA1; } + + int getDigestLength() { + return 160; + } } /** @@ -463,6 +479,10 @@ public String engineGetURI() { return XMLSignature.ALGO_ID_MAC_HMAC_SHA256; } + + int getDigestLength() { + return 256; + } } /** @@ -490,6 +510,10 @@ public String engineGetURI() { return XMLSignature.ALGO_ID_MAC_HMAC_SHA384; } + + int getDigestLength() { + return 384; + } } /** @@ -517,6 +541,10 @@ public String engineGetURI() { return XMLSignature.ALGO_ID_MAC_HMAC_SHA512; } + + int getDigestLength() { + return 512; + } } /** @@ -544,6 +572,10 @@ public String engineGetURI() { return XMLSignature.ALGO_ID_MAC_HMAC_RIPEMD160; } + + int getDigestLength() { + return 160; + } } /** @@ -571,5 +603,9 @@ public String engineGetURI() { return XMLSignature.ALGO_ID_MAC_HMAC_NOT_RECOMMENDED_MD5; } + + int getDigestLength() { + return 128; + } } }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/jdk/src/share/classes/com/sun/security/jgss/AuthorizationDataEntry.java Wed Jul 05 16:59:08 2017 +0200 @@ -0,0 +1,68 @@ +/* + * Copyright 2009 Sun Microsystems, Inc. All Rights Reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. Sun designates this + * particular file as subject to the "Classpath" exception as provided + * by Sun in the LICENSE file that accompanied this code. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, + * CA 95054 USA or visit www.sun.com if you need additional information or + * have any questions. + */ + +package com.sun.security.jgss; + +/** + * Kerberos 5 AuthorizationData entry. + */ +final public class AuthorizationDataEntry { + + private final int type; + private final byte[] data; + + /** + * Create an AuthorizationDataEntry object. + * @param type the ad-type + * @param data the ad-data, a copy of the data will be saved + * inside the object. + */ + public AuthorizationDataEntry(int type, byte[] data) { + this.type = type; + this.data = data.clone(); + } + + /** + * Get the ad-type field. + * @return ad-type + */ + public int getType() { + return type; + } + + /** + * Get a copy of the ad-data field. + * @return ad-data + */ + public byte[] getData() { + return data.clone(); + } + + public String toString() { + return "AuthorizationDataEntry: type="+type+", data=" + + data.length + " bytes:\n" + + new sun.misc.HexDumpEncoder().encode(data); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/jdk/src/share/classes/com/sun/security/jgss/ExtendedGSSContext.java Wed Jul 05 16:59:08 2017 +0200 @@ -0,0 +1,102 @@ +/* + * Copyright 2009 Sun Microsystems, Inc. All Rights Reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. Sun designates this + * particular file as subject to the "Classpath" exception as provided + * by Sun in the LICENSE file that accompanied this code. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, + * CA 95054 USA or visit www.sun.com if you need additional information or + * have any questions. + */ + +package com.sun.security.jgss; + +import org.ietf.jgss.*; + +/** + * The extended GSSContext interface for supporting additional + * functionalities not defined by {@code org.ietf.jgss.GSSContext}, + * such as querying context-specific attributes. + */ +public interface ExtendedGSSContext extends GSSContext { + /** + * Return the mechanism-specific attribute associated with {@code type}. + * <br><br> + * For each supported attribute type, the type for the output are + * defined below. + * <ol> + * <li>{@code KRB5_GET_TKT_FLAGS}: + * the returned object is a boolean array for the service ticket flags, + * which is long enough to contain all true bits. This means if + * the user wants to get the <em>n</em>'th bit but the length of the + * returned array is less than <em>n</em>, it is regarded as false. + * <li>{@code KRB5_GET_SESSION_KEY}: + * the returned object is an instance of {@link java.security.Key}, + * which has the following properties: + * <ul> + * <li>Algorithm: enctype as a string, where + * enctype is defined in RFC 3961, section 8. + * <li>Format: "RAW" + * <li>Encoded form: the raw key bytes, not in any ASN.1 encoding + * </ul> + * <li>{@code KRB5_GET_AUTHZ_DATA}: + * the returned object is an array of + * {@link com.sun.security.jgss.AuthorizationDataEntry}, or null if the + * optional field is missing in the service ticket. + * <li>{@code KRB5_GET_AUTHTIME}: + * the returned object is a String object in the standard KerberosTime + * format defined in RFC 4120 5.2.3 + * </ol> + * + * If there is a security manager, an {@link InquireSecContextPermission} + * with the name {@code type.mech} must be granted. Otherwise, this could + * result in a {@link SecurityException}.<p> + * + * Example: + * <pre> + * GSSContext ctxt = m.createContext(...) + * // Establishing the context + * if (ctxt instanceof ExtendedGSSContext) { + * ExtendedGSSContext ex = (ExtendedGSSContext)ctxt; + * try { + * Key key = (key)ex.inquireSecContext( + * InquireType.KRB5_GET_SESSION_KEY); + * // read key info + * } catch (GSSException gsse) { + * // deal with exception + * } + * } + * </pre> + * @param type the type of the attribute requested + * @return the attribute, see the method documentation for details. + * @throws GSSException containing the following + * major error codes: + * {@link GSSException#BAD_MECH GSSException.BAD_MECH} if the mechanism + * does not support this method, + * {@link GSSException#UNAVAILABLE GSSException.UNAVAILABLE} if the + * type specified is not supported, + * {@link GSSException#NO_CONTEXT GSSException.NO_CONTEXT} if the + * security context is invalid, + * {@link GSSException#FAILURE GSSException.FAILURE} for other + * unspecified failures. + * @throws SecurityException if a security manager exists and a proper + * {@link InquireSecContextPermission} is not granted. + * @see InquireSecContextPermission + */ + public Object inquireSecContext(InquireType type) + throws GSSException; +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/jdk/src/share/classes/com/sun/security/jgss/InquireSecContextPermission.java Wed Jul 05 16:59:08 2017 +0200 @@ -0,0 +1,54 @@ +/* + * Copyright 2009 Sun Microsystems, Inc. All Rights Reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. Sun designates this + * particular file as subject to the "Classpath" exception as provided + * by Sun in the LICENSE file that accompanied this code. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, + * CA 95054 USA or visit www.sun.com if you need additional information or + * have any questions. + */ + +package com.sun.security.jgss; + +import java.security.BasicPermission; + +/** + * This class is used to protect various attributes of an established + * GSS security context that can be accessed using the + * {@link com.sun.security.jgss.ExtendedGSSContext#inquireSecContext} + * method. + * + * <p>The target name is the {@link InquireType} allowed. + */ +public final class InquireSecContextPermission extends BasicPermission { + + /** + * Constructs a new {@code InquireSecContextPermission} object with + * the specified name. The name is the symbolic name of the + * {@link InquireType} allowed. + * + * @param name the {@link InquireType} allowed by this + * permission. "*" means all {@link InquireType}s are allowed. + * + * @throws NullPointerException if <code>name</code> is <code>null</code>. + * @throws IllegalArgumentException if <code>name</code> is empty. + */ + public InquireSecContextPermission(String name) { + super(name); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/jdk/src/share/classes/com/sun/security/jgss/InquireType.java Wed Jul 05 16:59:08 2017 +0200 @@ -0,0 +1,54 @@ +/* + * Copyright 2009 Sun Microsystems, Inc. All Rights Reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. Sun designates this + * particular file as subject to the "Classpath" exception as provided + * by Sun in the LICENSE file that accompanied this code. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, + * CA 95054 USA or visit www.sun.com if you need additional information or + * have any questions. + */ + +package com.sun.security.jgss; + +/** + * Attribute types that can be specified as an argument of + * {@link com.sun.security.jgss.ExtendedGSSContext#inquireSecContext} + */ +public enum InquireType { + /** + * Attribute type for retrieving the session key of an + * established Kerberos 5 security context. + */ + KRB5_GET_SESSION_KEY, + /** + * Attribute type for retrieving the service ticket flags of an + * established Kerberos 5 security context. + */ + KRB5_GET_TKT_FLAGS, + /** + * Attribute type for retrieving the authorization data in the + * service ticket of an established Kerberos 5 security context. + * Only supported on the acceptor side. + */ + KRB5_GET_AUTHZ_DATA, + /** + * Attribute type for retrieving the authtime in the service ticket + * of an established Kerberos 5 security context. + */ + KRB5_GET_AUTHTIME +}
--- a/jdk/src/share/classes/com/sun/security/sasl/util/AbstractSaslImpl.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/com/sun/security/sasl/util/AbstractSaslImpl.java Wed Jul 05 16:59:08 2017 +0200 @@ -1,5 +1,5 @@ /* - * Copyright 2000-2003 Sun Microsystems, Inc. All Rights Reserved. + * Copyright 2000-2009 Sun Microsystems, Inc. All Rights Reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it @@ -48,10 +48,6 @@ * @author Rosanna Lee */ public abstract class AbstractSaslImpl { - /** - * Logger for debug messages - */ - protected static Logger logger; // set in initLogger(); lazily loads logger protected boolean completed = false; protected boolean privacy = false; @@ -68,7 +64,6 @@ protected String myClassName; protected AbstractSaslImpl(Map props, String className) throws SaslException { - initLogger(); myClassName = className; // Parse properties to set desired context options @@ -325,19 +320,15 @@ } } - /** - * Sets logger field. - */ - private static synchronized void initLogger() { - if (logger == null) { - logger = Logger.getLogger(SASL_LOGGER_NAME); - } - } - // ---------------- Constants ----------------- private static final String SASL_LOGGER_NAME = "javax.security.sasl"; protected static final String MAX_SEND_BUF = "javax.security.sasl.sendmaxbuffer"; + /** + * Logger for debug messages + */ + protected static final Logger logger = Logger.getLogger(SASL_LOGGER_NAME); + // default 0 (no protection); 1 (integrity only) protected static final byte NO_PROTECTION = (byte)1; protected static final byte INTEGRITY_ONLY_PROTECTION = (byte)2;
--- a/jdk/src/share/classes/java/awt/Cursor.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/java/awt/Cursor.java Wed Jul 05 16:59:08 2017 +0200 @@ -118,8 +118,18 @@ */ public static final int MOVE_CURSOR = 13; + /** + * @deprecated As of JDK version 1.7, the {@link #getPredefinedCursor()} + * method should be used instead. + */ + @Deprecated protected static Cursor predefined[] = new Cursor[14]; + /** + * This field is a private replacement for 'predefined' array. + */ + private final static Cursor[] predefinedPrivate = new Cursor[14]; + /* Localization names and default values */ static final String[][] cursorProperties = { { "AWT.DefaultCursor", "Default Cursor" }, @@ -253,10 +263,15 @@ if (type < Cursor.DEFAULT_CURSOR || type > Cursor.MOVE_CURSOR) { throw new IllegalArgumentException("illegal cursor type"); } + Cursor c = predefinedPrivate[type]; + if (c == null) { + predefinedPrivate[type] = c = new Cursor(type); + } + // fill 'predefined' array for backwards compatibility. if (predefined[type] == null) { - predefined[type] = new Cursor(type); + predefined[type] = c; } - return predefined[type]; + return c; } /**
--- a/jdk/src/share/classes/java/awt/Window.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/java/awt/Window.java Wed Jul 05 16:59:08 2017 +0200 @@ -3743,16 +3743,58 @@ // ****************** END OF MIXING CODE ******************************** - // This method gets the window location/size as reported by the native - // system since the locally cached values may represent outdated data. - // NOTE: this method is invoked on the toolkit thread, and therefore - // is not supposed to become public/user-overridable. + /** + * Limit the given double value with the given range. + */ + private static double limit(double value, double min, double max) { + value = Math.max(value, min); + value = Math.min(value, max); + return value; + } + + /** + * Calculate the position of the security warning. + * + * This method gets the window location/size as reported by the native + * system since the locally cached values may represent outdated data. + * + * The method is used from the native code, or via AWTAccessor. + * + * NOTE: this method is invoked on the toolkit thread, and therefore is not + * supposed to become public/user-overridable. + */ private Point2D calculateSecurityWarningPosition(double x, double y, double w, double h) { - return new Point2D.Double( - x + w * securityWarningAlignmentX + securityWarningPointX, - y + h * securityWarningAlignmentY + securityWarningPointY); + // The position according to the spec of SecurityWarning.setPosition() + double wx = x + w * securityWarningAlignmentX + securityWarningPointX; + double wy = y + h * securityWarningAlignmentY + securityWarningPointY; + + // First, make sure the warning is not too far from the window bounds + wx = Window.limit(wx, + x - securityWarningWidth - 2, + x + w + 2); + wy = Window.limit(wy, + y - securityWarningHeight - 2, + y + h + 2); + + // Now make sure the warning window is visible on the screen + GraphicsConfiguration graphicsConfig = + getGraphicsConfiguration_NoClientCode(); + Rectangle screenBounds = graphicsConfig.getBounds(); + Insets screenInsets = + Toolkit.getDefaultToolkit().getScreenInsets(graphicsConfig); + + wx = Window.limit(wx, + screenBounds.x + screenInsets.left, + screenBounds.x + screenBounds.width - screenInsets.right + - securityWarningWidth); + wy = Window.limit(wy, + screenBounds.y + screenInsets.top, + screenBounds.y + screenBounds.height - screenInsets.bottom + - securityWarningHeight); + + return new Point2D.Double(wx, wy); } static {
--- a/jdk/src/share/classes/java/beans/Introspector.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/java/beans/Introspector.java Wed Jul 05 16:59:08 2017 +0200 @@ -114,8 +114,8 @@ // Static Caches to speed up introspection. private static Map declaredMethodCache = Collections.synchronizedMap(new WeakHashMap()); - private static Map beanInfoCache = - Collections.synchronizedMap(new WeakHashMap()); + + private static final Object BEANINFO_CACHE = new Object(); private Class beanClass; private BeanInfo explicitBeanInfo; @@ -174,10 +174,18 @@ if (!ReflectUtil.isPackageAccessible(beanClass)) { return (new Introspector(beanClass, null, USE_ALL_BEANINFO)).getBeanInfo(); } - BeanInfo bi = (BeanInfo)beanInfoCache.get(beanClass); + Map<Class<?>, BeanInfo> map; + synchronized (BEANINFO_CACHE) { + map = (Map<Class<?>, BeanInfo>) AppContext.getAppContext().get(BEANINFO_CACHE); + if (map == null) { + map = Collections.synchronizedMap(new WeakHashMap<Class<?>, BeanInfo>()); + AppContext.getAppContext().put(BEANINFO_CACHE, map); + } + } + BeanInfo bi = map.get(beanClass); if (bi == null) { bi = (new Introspector(beanClass, null, USE_ALL_BEANINFO)).getBeanInfo(); - beanInfoCache.put(beanClass, bi); + map.put(beanClass, bi); } return bi; } @@ -351,7 +359,10 @@ */ public static void flushCaches() { - beanInfoCache.clear(); + Map map = (Map) AppContext.getAppContext().get(BEANINFO_CACHE); + if (map != null) { + map.clear(); + } declaredMethodCache.clear(); } @@ -374,7 +385,10 @@ if (clz == null) { throw new NullPointerException(); } - beanInfoCache.remove(clz); + Map map = (Map) AppContext.getAppContext().get(BEANINFO_CACHE); + if (map != null) { + map.remove(clz); + } declaredMethodCache.remove(clz); }
--- a/jdk/src/share/classes/java/beans/MetaData.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/java/beans/MetaData.java Wed Jul 05 16:59:08 2017 +0200 @@ -335,31 +335,6 @@ return (oldC.size() == newC.size()) && oldC.containsAll(newC); } - static Object getPrivateField(final Object instance, final String name) { - return AccessController.doPrivileged( - new PrivilegedAction() { - public Object run() { - Class type = instance.getClass(); - while ( true ) { - try { - Field field = type.getDeclaredField(name); - field.setAccessible(true); - return field.get( instance ); - } - catch (NoSuchFieldException exception) { - type = type.getSuperclass(); - if (type == null) { - throw new IllegalStateException("Could not find field " + name, exception); - } - } - catch (Exception exception) { - throw new IllegalStateException("Could not get value " + type.getName() + '.' + name, exception); - } - } - } - } ); - } - static final class EmptyList_PersistenceDelegate extends java_util_Collections { protected Expression instantiate(Object oldInstance, Encoder out) { return new Expression(oldInstance, Collections.class, "emptyList", null); @@ -500,7 +475,7 @@ static final class CheckedCollection_PersistenceDelegate extends java_util_Collections { protected Expression instantiate(Object oldInstance, Encoder out) { - Object type = getPrivateField(oldInstance, "type"); + Object type = MetaData.getPrivateFieldValue(oldInstance, "java.util.Collections$CheckedCollection.type"); List list = new ArrayList((Collection) oldInstance); return new Expression(oldInstance, Collections.class, "checkedCollection", new Object[]{list, type}); } @@ -508,7 +483,7 @@ static final class CheckedList_PersistenceDelegate extends java_util_Collections { protected Expression instantiate(Object oldInstance, Encoder out) { - Object type = getPrivateField(oldInstance, "type"); + Object type = MetaData.getPrivateFieldValue(oldInstance, "java.util.Collections$CheckedCollection.type"); List list = new LinkedList((Collection) oldInstance); return new Expression(oldInstance, Collections.class, "checkedList", new Object[]{list, type}); } @@ -516,7 +491,7 @@ static final class CheckedRandomAccessList_PersistenceDelegate extends java_util_Collections { protected Expression instantiate(Object oldInstance, Encoder out) { - Object type = getPrivateField(oldInstance, "type"); + Object type = MetaData.getPrivateFieldValue(oldInstance, "java.util.Collections$CheckedCollection.type"); List list = new ArrayList((Collection) oldInstance); return new Expression(oldInstance, Collections.class, "checkedList", new Object[]{list, type}); } @@ -524,7 +499,7 @@ static final class CheckedSet_PersistenceDelegate extends java_util_Collections { protected Expression instantiate(Object oldInstance, Encoder out) { - Object type = getPrivateField(oldInstance, "type"); + Object type = MetaData.getPrivateFieldValue(oldInstance, "java.util.Collections$CheckedCollection.type"); Set set = new HashSet((Set) oldInstance); return new Expression(oldInstance, Collections.class, "checkedSet", new Object[]{set, type}); } @@ -532,7 +507,7 @@ static final class CheckedSortedSet_PersistenceDelegate extends java_util_Collections { protected Expression instantiate(Object oldInstance, Encoder out) { - Object type = getPrivateField(oldInstance, "type"); + Object type = MetaData.getPrivateFieldValue(oldInstance, "java.util.Collections$CheckedCollection.type"); SortedSet set = new TreeSet((SortedSet) oldInstance); return new Expression(oldInstance, Collections.class, "checkedSortedSet", new Object[]{set, type}); } @@ -540,8 +515,8 @@ static final class CheckedMap_PersistenceDelegate extends java_util_Collections { protected Expression instantiate(Object oldInstance, Encoder out) { - Object keyType = getPrivateField(oldInstance, "keyType"); - Object valueType = getPrivateField(oldInstance, "valueType"); + Object keyType = MetaData.getPrivateFieldValue(oldInstance, "java.util.Collections$CheckedMap.keyType"); + Object valueType = MetaData.getPrivateFieldValue(oldInstance, "java.util.Collections$CheckedMap.valueType"); Map map = new HashMap((Map) oldInstance); return new Expression(oldInstance, Collections.class, "checkedMap", new Object[]{map, keyType, valueType}); } @@ -549,8 +524,8 @@ static final class CheckedSortedMap_PersistenceDelegate extends java_util_Collections { protected Expression instantiate(Object oldInstance, Encoder out) { - Object keyType = getPrivateField(oldInstance, "keyType"); - Object valueType = getPrivateField(oldInstance, "valueType"); + Object keyType = MetaData.getPrivateFieldValue(oldInstance, "java.util.Collections$CheckedMap.keyType"); + Object valueType = MetaData.getPrivateFieldValue(oldInstance, "java.util.Collections$CheckedMap.valueType"); SortedMap map = new TreeMap((SortedMap) oldInstance); return new Expression(oldInstance, Collections.class, "checkedSortedMap", new Object[]{map, keyType, valueType}); } @@ -572,7 +547,7 @@ } private static Object getType(Object instance) { - return java_util_Collections.getPrivateField(instance, "keyType"); + return MetaData.getPrivateFieldValue(instance, "java.util.EnumMap.keyType"); } } @@ -591,7 +566,7 @@ } private static Object getType(Object instance) { - return java_util_Collections.getPrivateField(instance, "elementType"); + return MetaData.getPrivateFieldValue(instance, "java.util.EnumSet.elementType"); } } @@ -1282,7 +1257,7 @@ private Integer getAxis(Object object) { Box box = (Box) object; - return (Integer) java_util_Collections.getPrivateField(box.getLayout(), "axis"); + return (Integer) MetaData.getPrivateFieldValue(box.getLayout(), "javax.swing.BoxLayout.axis"); } } @@ -1365,6 +1340,7 @@ } class MetaData { + private static final Map<String,Field> fields = Collections.synchronizedMap(new WeakHashMap<String, Field>()); private static Hashtable internalPersistenceDelegates = new Hashtable(); private static PersistenceDelegate nullPersistenceDelegate = new NullPersistenceDelegate(); @@ -1503,4 +1479,35 @@ return null; } } + + static Object getPrivateFieldValue(Object instance, String name) { + Field field = fields.get(name); + if (field == null) { + int index = name.lastIndexOf('.'); + final String className = name.substring(0, index); + final String fieldName = name.substring(1 + index); + field = AccessController.doPrivileged(new PrivilegedAction<Field>() { + public Field run() { + try { + Field field = Class.forName(className).getDeclaredField(fieldName); + field.setAccessible(true); + return field; + } + catch (ClassNotFoundException exception) { + throw new IllegalStateException("Could not find class", exception); + } + catch (NoSuchFieldException exception) { + throw new IllegalStateException("Could not find field", exception); + } + } + }); + fields.put(name, field); + } + try { + return field.get(instance); + } + catch (IllegalAccessException exception) { + throw new IllegalStateException("Could not get value of the field", exception); + } + } }
--- a/jdk/src/share/classes/java/lang/Character.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/java/lang/Character.java Wed Jul 05 16:59:08 2017 +0200 @@ -38,7 +38,7 @@ * a character's category (lowercase letter, digit, etc.) and for converting * characters from uppercase to lowercase and vice versa. * <p> - * Character information is based on the Unicode Standard, version 4.0. + * Character information is based on the Unicode Standard, version 5.1.0. * <p> * The methods and data of class <code>Character</code> are defined by * the information in the <i>UnicodeData</i> file that is part of the
--- a/jdk/src/share/classes/java/lang/instrument/Instrumentation.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/java/lang/instrument/Instrumentation.java Wed Jul 05 16:59:08 2017 +0200 @@ -81,7 +81,7 @@ * an exception during execution, the JVM will still call the other registered * transformers in order. The same transformer may be added more than once, * but it is strongly discouraged -- avoid this by creating a new instance of - * tranformer class. + * transformer class. * <P> * This method is intended for use in instrumentation, as described in the * {@linkplain Instrumentation class specification}. @@ -183,7 +183,7 @@ * <P> * * The order of transformation is described in the - * ({@link java.lang.instrument.ClassFileTransformer#transform transform} method. + * {@link java.lang.instrument.ClassFileTransformer#transform transform} method. * This same order is used in the automatic reapplication of retransformation * incapable transforms. * <P> @@ -424,7 +424,7 @@ * classes or resources other than those to be defined by the bootstrap * class loader for the purpose of instrumentation. * Failure to observe this warning could result in unexpected - * behaviour that is difficult to diagnose. For example, suppose there is a + * behavior that is difficult to diagnose. For example, suppose there is a * loader L, and L's parent for delegation is the bootstrap class loader. * Furthermore, a method in class C, a class defined by L, makes reference to * a non-public accessor class C$1. If the JAR file contains a class C$1 then @@ -475,9 +475,9 @@ * classes or resources other than those to be defined by the system class * loader for the purpose of instrumentation. * Failure to observe this warning could result in unexpected - * behaviour that is difficult to diagnose (see + * behavior that is difficult to diagnose (see * {@link #appendToBootstrapClassLoaderSearch - * appendToBootstrapClassLoaderSearch}. + * appendToBootstrapClassLoaderSearch}). * * <p> The system class loader supports adding a JAR file to be searched if * it implements a method named <code>appendToClassPathForInstrumentation</code> @@ -485,7 +485,7 @@ * method is not required to have <code>public</code> access. The name of * the JAR file is obtained by invoking the {@link java.util.zip.ZipFile#getName * getName()} method on the <code>jarfile</code> and this is provided as the - * parameter to the <code>appendtoClassPathForInstrumentation</code> method. + * parameter to the <code>appendToClassPathForInstrumentation</code> method. * * <p> The <a href="http://java.sun.com/docs/books/vmspec/">Java Virtual Machine * Specification</a> specifies that a subsequent attempt to resolve a symbolic
--- a/jdk/src/share/classes/java/net/Socket.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/java/net/Socket.java Wed Jul 05 16:59:08 2017 +0200 @@ -114,9 +114,14 @@ * @since 1.5 */ public Socket(Proxy proxy) { - if (proxy != null && proxy.type() == Proxy.Type.SOCKS) { + // Create a copy of Proxy as a security measure + if (proxy == null) { + throw new IllegalArgumentException("Invalid Proxy"); + } + Proxy p = proxy == Proxy.NO_PROXY ? Proxy.NO_PROXY : sun.net.ApplicationProxy.create(proxy); + if (p.type() == Proxy.Type.SOCKS) { SecurityManager security = System.getSecurityManager(); - InetSocketAddress epoint = (InetSocketAddress) proxy.address(); + InetSocketAddress epoint = (InetSocketAddress) p.address(); if (security != null) { if (epoint.isUnresolved()) security.checkConnect(epoint.getHostName(), @@ -125,10 +130,10 @@ security.checkConnect(epoint.getAddress().getHostAddress(), epoint.getPort()); } - impl = new SocksSocketImpl(proxy); + impl = new SocksSocketImpl(p); impl.setSocket(this); } else { - if (proxy == Proxy.NO_PROXY) { + if (p == Proxy.NO_PROXY) { if (factory == null) { impl = new PlainSocketImpl(); impl.setSocket(this);
--- a/jdk/src/share/classes/java/net/SocksSocketImpl.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/java/net/SocksSocketImpl.java Wed Jul 05 16:59:08 2017 +0200 @@ -46,6 +46,9 @@ private Socket cmdsock = null; private InputStream cmdIn = null; private OutputStream cmdOut = null; + /* true if the Proxy has been set programatically */ + private boolean applicationSetProxy; /* false */ + SocksSocketImpl() { // Nothing needed @@ -237,8 +240,7 @@ out.write((endpoint.getPort() >> 8) & 0xff); out.write((endpoint.getPort() >> 0) & 0xff); out.write(endpoint.getAddress().getAddress()); - String userName = java.security.AccessController.doPrivileged( - new sun.security.action.GetPropertyAction("user.name")); + String userName = getUserName(); try { out.write(userName.getBytes("ISO-8859-1")); } catch (java.io.UnsupportedEncodingException uee) { @@ -554,8 +556,7 @@ out.write((super.getLocalPort() >> 8) & 0xff); out.write((super.getLocalPort() >> 0) & 0xff); out.write(addr1); - String userName = java.security.AccessController.doPrivileged( - new sun.security.action.GetPropertyAction("user.name")); + String userName = getUserName(); try { out.write(userName.getBytes("ISO-8859-1")); } catch (java.io.UnsupportedEncodingException uee) { @@ -1022,4 +1023,16 @@ super.close(); } + private String getUserName() { + String userName = ""; + if (applicationSetProxy) { + try { + userName = System.getProperty("user.name"); + } catch (SecurityException se) { /* swallow Exception */ } + } else { + userName = java.security.AccessController.doPrivileged( + new sun.security.action.GetPropertyAction("user.name")); + } + return userName; + } }
--- a/jdk/src/share/classes/java/net/URL.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/java/net/URL.java Wed Jul 05 16:59:08 2017 +0200 @@ -1004,16 +1004,18 @@ throw new IllegalArgumentException("proxy can not be null"); } + // Create a copy of Proxy as a security measure + Proxy p = proxy == Proxy.NO_PROXY ? Proxy.NO_PROXY : sun.net.ApplicationProxy.create(proxy); SecurityManager sm = System.getSecurityManager(); - if (proxy.type() != Proxy.Type.DIRECT && sm != null) { - InetSocketAddress epoint = (InetSocketAddress) proxy.address(); + if (p.type() != Proxy.Type.DIRECT && sm != null) { + InetSocketAddress epoint = (InetSocketAddress) p.address(); if (epoint.isUnresolved()) sm.checkConnect(epoint.getHostName(), epoint.getPort()); else sm.checkConnect(epoint.getAddress().getHostAddress(), epoint.getPort()); } - return handler.openConnection(this, proxy); + return handler.openConnection(this, p); } /**
--- a/jdk/src/share/classes/java/nio/channels/DatagramChannel.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/java/nio/channels/DatagramChannel.java Wed Jul 05 16:59:08 2017 +0200 @@ -421,7 +421,7 @@ * invocation of this method will block until the first operation is * complete. If this channel's socket is not bound then this method will * first cause the socket to be bound to an address that is assigned - * automatically, as if by invoking the {@link #bind bind) method with a + * automatically, as if by invoking the {@link #bind bind} method with a * parameter of {@code null}. </p> * * @param src
--- a/jdk/src/share/classes/java/nio/channels/package-info.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/java/nio/channels/package-info.java Wed Jul 05 16:59:08 2017 +0200 @@ -115,8 +115,8 @@ * <td>Reads, writes, maps, and manipulates files</td></tr> * <tr><td valign=top><tt>{@link java.nio.channels.FileLock}</tt></td> * <td>A lock on a (region of a) file</td></tr> - * <tr><td valign=top><tt>{@link java.nio.MappedByteBuffer}/{@link java.nio.MappedBigByteBuffer} </tt></td> - * <td>A direct byte buffer or big byte buffer mapped to a region of a file</td></tr> + * <tr><td valign=top><tt>{@link java.nio.MappedByteBuffer} </tt></td> + * <td>A direct byte buffer mapped to a region of a file</td></tr> * </table></blockquote> * * <p> The {@link java.nio.channels.FileChannel} class supports the usual
--- a/jdk/src/share/classes/java/nio/file/DirectoryStream.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/java/nio/file/DirectoryStream.java Wed Jul 05 16:59:08 2017 +0200 @@ -53,7 +53,7 @@ * invoking the {@link #close close} method. Closing the directory stream * releases any resources associated with the stream. Once a directory stream * is closed, all further method invocations on the iterator throw {@link - * java.util.concurrent.ConcurrentModificationException} with cause {@link + * java.util.ConcurrentModificationException} with cause {@link * ClosedDirectoryStreamException}. * * <p> A directory stream is not required to be <i>asynchronously closeable</i>.
--- a/jdk/src/share/classes/java/nio/file/Path.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/java/nio/file/Path.java Wed Jul 05 16:59:08 2017 +0200 @@ -987,7 +987,7 @@ * exception then it is propogated to the iterator's {@link Iterator#hasNext() * hasNext} or {@link Iterator#next() next} method. Where an {@code * IOException} is thrown, it is propogated as a {@link - * java.util.concurrent.ConcurrentModificationException} with the {@code + * java.util.ConcurrentModificationException} with the {@code * IOException} as the cause. * * <p> When an implementation supports operations on entries in the
--- a/jdk/src/share/classes/java/nio/file/SimpleFileVisitor.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/java/nio/file/SimpleFileVisitor.java Wed Jul 05 16:59:08 2017 +0200 @@ -48,6 +48,14 @@ } /** + * Throws NullPointerException if obj is null. + */ + private static void checkNotNull(Object obj) { + if (obj == null) + throw new NullPointerException(); + } + + /** * Invoked for a directory before entries in the directory are visited. * * <p> Unless overridden, this method returns {@link FileVisitResult#CONTINUE @@ -55,6 +63,7 @@ */ @Override public FileVisitResult preVisitDirectory(T dir) { + checkNotNull(dir); return FileVisitResult.CONTINUE; } @@ -70,6 +79,8 @@ */ @Override public FileVisitResult preVisitDirectoryFailed(T dir, IOException exc) { + checkNotNull(dir); + checkNotNull(exc); throw new IOError(exc); } @@ -81,6 +92,8 @@ */ @Override public FileVisitResult visitFile(T file, BasicFileAttributes attrs) { + checkNotNull(file); + checkNotNull(attrs); return FileVisitResult.CONTINUE; } @@ -96,6 +109,8 @@ */ @Override public FileVisitResult visitFileFailed(T file, IOException exc) { + checkNotNull(file); + checkNotNull(exc); throw new IOError(exc); } @@ -114,6 +129,7 @@ */ @Override public FileVisitResult postVisitDirectory(T dir, IOException exc) { + checkNotNull(dir); if (exc != null) throw new IOError(exc); return FileVisitResult.CONTINUE;
--- a/jdk/src/share/classes/java/nio/file/attribute/AclFileAttributeView.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/java/nio/file/attribute/AclFileAttributeView.java Wed Jul 05 16:59:08 2017 +0200 @@ -75,7 +75,7 @@ * .lookupPrincipalByName("joe"); * * // get view - * AclFileAttributeView view = file.newFileAttributeView(AclFileAttributeView.class); + * AclFileAttributeView view = file.getFileAttributeView(AclFileAttributeView.class); * * // create ACE to give "joe" read access * AclEntry entry = AclEntry.newBuilder()
--- a/jdk/src/share/classes/java/nio/file/attribute/PosixFileAttributeView.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/java/nio/file/attribute/PosixFileAttributeView.java Wed Jul 05 16:59:08 2017 +0200 @@ -61,7 +61,7 @@ * Suppose we need to print out the owner and access permissions of a file: * <pre> * FileRef file = ... - * PosixFileAttributes attrs = file.newFileAttributeView(PosixFileAttributeView.class) + * PosixFileAttributes attrs = file.getFileAttributeView(PosixFileAttributeView.class) * .readAttributes(); * System.out.format("%s %s%n", * attrs.owner().getName(),
--- a/jdk/src/share/classes/java/nio/file/attribute/package-info.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/java/nio/file/attribute/package-info.java Wed Jul 05 16:59:08 2017 +0200 @@ -102,9 +102,9 @@ * <p><li> The {@link java.nio.file.attribute.UserPrincipalLookupService} * interface defines methods to lookup user or group principals. </li> * - * <p><li> The {@link java.nio.file.attribute.Attribute} interface + * <p><li> The {@link java.nio.file.attribute.FileAttribute} interface * represents the value of an attribute for cases where the attribute value is - * require to be set atomically when creating an object in the file system. </li> + * required to be set atomically when creating an object in the file system. </li> * * </ul> *
--- a/jdk/src/share/classes/java/util/Arrays.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/java/util/Arrays.java Wed Jul 05 16:59:08 2017 +0200 @@ -1065,29 +1065,103 @@ (x[b] > x[c] ? b : x[a] > x[c] ? c : a)); } - /** - * Sorts the specified array of objects into ascending order, according to - * the {@linkplain Comparable natural ordering} - * of its elements. All elements in the array - * must implement the {@link Comparable} interface. Furthermore, all - * elements in the array must be <i>mutually comparable</i> (that is, - * <tt>e1.compareTo(e2)</tt> must not throw a <tt>ClassCastException</tt> - * for any elements <tt>e1</tt> and <tt>e2</tt> in the array).<p> + * Old merge sort implementation can be selected (for + * compatibility with broken comparators) using a system property. + * Cannot be a static boolean in the enclosing class due to + * circular dependencies. To be removed in a future release. + */ + static final class LegacyMergeSort { + private static final boolean userRequested = + java.security.AccessController.doPrivileged( + new sun.security.action.GetBooleanAction( + "java.util.Arrays.useLegacyMergeSort")).booleanValue(); + } + + /* + * If this platform has an optimizing VM, check whether ComparableTimSort + * offers any performance benefit over TimSort in conjunction with a + * comparator that returns: + * {@code ((Comparable)first).compareTo(Second)}. + * If not, you are better off deleting ComparableTimSort to + * eliminate the code duplication. In other words, the commented + * out code below is the preferable implementation for sorting + * arrays of Comparables if it offers sufficient performance. + */ + +// /** +// * A comparator that implements the natural ordering of a group of +// * mutually comparable elements. Using this comparator saves us +// * from duplicating most of the code in this file (one version for +// * Comparables, one for explicit Comparators). +// */ +// private static final Comparator<Object> NATURAL_ORDER = +// new Comparator<Object>() { +// @SuppressWarnings("unchecked") +// public int compare(Object first, Object second) { +// return ((Comparable<Object>)first).compareTo(second); +// } +// }; +// +// public static void sort(Object[] a) { +// sort(a, 0, a.length, NATURAL_ORDER); +// } +// +// public static void sort(Object[] a, int fromIndex, int toIndex) { +// sort(a, fromIndex, toIndex, NATURAL_ORDER); +// } + + /** + * Sorts the specified array of objects into ascending order, according + * to the {@linkplain Comparable natural ordering} of its elements. + * All elements in the array must implement the {@link Comparable} + * interface. Furthermore, all elements in the array must be + * <i>mutually comparable</i> (that is, {@code e1.compareTo(e2)} must + * not throw a {@code ClassCastException} for any elements {@code e1} + * and {@code e2} in the array). * - * This sort is guaranteed to be <i>stable</i>: equal elements will - * not be reordered as a result of the sort.<p> + * <p>This sort is guaranteed to be <i>stable</i>: equal elements will + * not be reordered as a result of the sort. * - * The sorting algorithm is a modified mergesort (in which the merge is - * omitted if the highest element in the low sublist is less than the - * lowest element in the high sublist). This algorithm offers guaranteed - * n*log(n) performance. + * <p>Implementation note: This implementation is a stable, adaptive, + * iterative mergesort that requires far fewer than n lg(n) comparisons + * when the input array is partially sorted, while offering the + * performance of a traditional mergesort when the input array is + * randomly ordered. If the input array is nearly sorted, the + * implementation requires approximately n comparisons. Temporary + * storage requirements vary from a small constant for nearly sorted + * input arrays to n/2 object references for randomly ordered input + * arrays. + * + * <p>The implementation takes equal advantage of ascending and + * descending order in its input array, and can take advantage of + * ascending and descending order in different parts of the the same + * input array. It is well-suited to merging two or more sorted arrays: + * simply concatenate the arrays and sort the resulting array. + * + * <p>The implementation was adapted from Tim Peters's list sort for Python + * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt"> + * TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic + * Sorting and Information Theoretic Complexity", in Proceedings of the + * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, + * January 1993. * * @param a the array to be sorted - * @throws ClassCastException if the array contains elements that are not - * <i>mutually comparable</i> (for example, strings and integers). + * @throws ClassCastException if the array contains elements that are not + * <i>mutually comparable</i> (for example, strings and integers) + * @throws IllegalArgumentException (optional) if the natural + * ordering of the array elements is found to violate the + * {@link Comparable} contract */ public static void sort(Object[] a) { + if (LegacyMergeSort.userRequested) + legacyMergeSort(a); + else + ComparableTimSort.sort(a); + } + + /** To be removed in a future release. */ + private static void legacyMergeSort(Object[] a) { Object[] aux = a.clone(); mergeSort(aux, a, 0, a.length, 0); } @@ -1097,34 +1171,63 @@ * ascending order, according to the * {@linkplain Comparable natural ordering} of its * elements. The range to be sorted extends from index - * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive. - * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.) All + * {@code fromIndex}, inclusive, to index {@code toIndex}, exclusive. + * (If {@code fromIndex==toIndex}, the range to be sorted is empty.) All * elements in this range must implement the {@link Comparable} * interface. Furthermore, all elements in this range must be <i>mutually - * comparable</i> (that is, <tt>e1.compareTo(e2)</tt> must not throw a - * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and - * <tt>e2</tt> in the array).<p> + * comparable</i> (that is, {@code e1.compareTo(e2)} must not throw a + * {@code ClassCastException} for any elements {@code e1} and + * {@code e2} in the array). * - * This sort is guaranteed to be <i>stable</i>: equal elements will - * not be reordered as a result of the sort.<p> + * <p>This sort is guaranteed to be <i>stable</i>: equal elements will + * not be reordered as a result of the sort. * - * The sorting algorithm is a modified mergesort (in which the merge is - * omitted if the highest element in the low sublist is less than the - * lowest element in the high sublist). This algorithm offers guaranteed - * n*log(n) performance. + * <p>Implementation note: This implementation is a stable, adaptive, + * iterative mergesort that requires far fewer than n lg(n) comparisons + * when the input array is partially sorted, while offering the + * performance of a traditional mergesort when the input array is + * randomly ordered. If the input array is nearly sorted, the + * implementation requires approximately n comparisons. Temporary + * storage requirements vary from a small constant for nearly sorted + * input arrays to n/2 object references for randomly ordered input + * arrays. + * + * <p>The implementation takes equal advantage of ascending and + * descending order in its input array, and can take advantage of + * ascending and descending order in different parts of the the same + * input array. It is well-suited to merging two or more sorted arrays: + * simply concatenate the arrays and sort the resulting array. + * + * <p>The implementation was adapted from Tim Peters's list sort for Python + * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt"> + * TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic + * Sorting and Information Theoretic Complexity", in Proceedings of the + * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, + * January 1993. * * @param a the array to be sorted * @param fromIndex the index of the first element (inclusive) to be * sorted * @param toIndex the index of the last element (exclusive) to be sorted - * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt> - * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or - * <tt>toIndex > a.length</tt> - * @throws ClassCastException if the array contains elements that are - * not <i>mutually comparable</i> (for example, strings and - * integers). + * @throws IllegalArgumentException if {@code fromIndex > toIndex} or + * (optional) if the natural ordering of the array elements is + * found to violate the {@link Comparable} contract + * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or + * {@code toIndex > a.length} + * @throws ClassCastException if the array contains elements that are + * not <i>mutually comparable</i> (for example, strings and + * integers). */ public static void sort(Object[] a, int fromIndex, int toIndex) { + if (LegacyMergeSort.userRequested) + legacyMergeSort(a, fromIndex, toIndex); + else + ComparableTimSort.sort(a, fromIndex, toIndex); + } + + /** To be removed in a future release. */ + private static void legacyMergeSort(Object[] a, + int fromIndex, int toIndex) { rangeCheck(a.length, fromIndex, toIndex); Object[] aux = copyOfRange(a, fromIndex, toIndex); mergeSort(aux, a, fromIndex, toIndex, -fromIndex); @@ -1133,6 +1236,7 @@ /** * Tuning parameter: list size at or below which insertion sort will be * used in preference to mergesort or quicksort. + * To be removed in a future release. */ private static final int INSERTIONSORT_THRESHOLD = 7; @@ -1142,6 +1246,7 @@ * low is the index in dest to start sorting * high is the end index in dest to end sorting * off is the offset to generate corresponding low, high in src + * To be removed in a future release. */ private static void mergeSort(Object[] src, Object[] dest, @@ -1197,25 +1302,53 @@ * Sorts the specified array of objects according to the order induced by * the specified comparator. All elements in the array must be * <i>mutually comparable</i> by the specified comparator (that is, - * <tt>c.compare(e1, e2)</tt> must not throw a <tt>ClassCastException</tt> - * for any elements <tt>e1</tt> and <tt>e2</tt> in the array).<p> + * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException} + * for any elements {@code e1} and {@code e2} in the array). * - * This sort is guaranteed to be <i>stable</i>: equal elements will - * not be reordered as a result of the sort.<p> + * <p>This sort is guaranteed to be <i>stable</i>: equal elements will + * not be reordered as a result of the sort. * - * The sorting algorithm is a modified mergesort (in which the merge is - * omitted if the highest element in the low sublist is less than the - * lowest element in the high sublist). This algorithm offers guaranteed - * n*log(n) performance. + * <p>Implementation note: This implementation is a stable, adaptive, + * iterative mergesort that requires far fewer than n lg(n) comparisons + * when the input array is partially sorted, while offering the + * performance of a traditional mergesort when the input array is + * randomly ordered. If the input array is nearly sorted, the + * implementation requires approximately n comparisons. Temporary + * storage requirements vary from a small constant for nearly sorted + * input arrays to n/2 object references for randomly ordered input + * arrays. + * + * <p>The implementation takes equal advantage of ascending and + * descending order in its input array, and can take advantage of + * ascending and descending order in different parts of the the same + * input array. It is well-suited to merging two or more sorted arrays: + * simply concatenate the arrays and sort the resulting array. + * + * <p>The implementation was adapted from Tim Peters's list sort for Python + * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt"> + * TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic + * Sorting and Information Theoretic Complexity", in Proceedings of the + * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, + * January 1993. * * @param a the array to be sorted * @param c the comparator to determine the order of the array. A - * <tt>null</tt> value indicates that the elements' + * {@code null} value indicates that the elements' * {@linkplain Comparable natural ordering} should be used. - * @throws ClassCastException if the array contains elements that are - * not <i>mutually comparable</i> using the specified comparator. + * @throws ClassCastException if the array contains elements that are + * not <i>mutually comparable</i> using the specified comparator + * @throws IllegalArgumentException (optional) if the comparator is + * found to violate the {@link Comparator} contract */ public static <T> void sort(T[] a, Comparator<? super T> c) { + if (LegacyMergeSort.userRequested) + legacyMergeSort(a, c); + else + TimSort.sort(a, c); + } + + /** To be removed in a future release. */ + private static <T> void legacyMergeSort(T[] a, Comparator<? super T> c) { T[] aux = a.clone(); if (c==null) mergeSort(aux, a, 0, a.length, 0); @@ -1226,36 +1359,65 @@ /** * Sorts the specified range of the specified array of objects according * to the order induced by the specified comparator. The range to be - * sorted extends from index <tt>fromIndex</tt>, inclusive, to index - * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the + * sorted extends from index {@code fromIndex}, inclusive, to index + * {@code toIndex}, exclusive. (If {@code fromIndex==toIndex}, the * range to be sorted is empty.) All elements in the range must be * <i>mutually comparable</i> by the specified comparator (that is, - * <tt>c.compare(e1, e2)</tt> must not throw a <tt>ClassCastException</tt> - * for any elements <tt>e1</tt> and <tt>e2</tt> in the range).<p> + * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException} + * for any elements {@code e1} and {@code e2} in the range). * - * This sort is guaranteed to be <i>stable</i>: equal elements will - * not be reordered as a result of the sort.<p> + * <p>This sort is guaranteed to be <i>stable</i>: equal elements will + * not be reordered as a result of the sort. * - * The sorting algorithm is a modified mergesort (in which the merge is - * omitted if the highest element in the low sublist is less than the - * lowest element in the high sublist). This algorithm offers guaranteed - * n*log(n) performance. + * <p>Implementation note: This implementation is a stable, adaptive, + * iterative mergesort that requires far fewer than n lg(n) comparisons + * when the input array is partially sorted, while offering the + * performance of a traditional mergesort when the input array is + * randomly ordered. If the input array is nearly sorted, the + * implementation requires approximately n comparisons. Temporary + * storage requirements vary from a small constant for nearly sorted + * input arrays to n/2 object references for randomly ordered input + * arrays. + * + * <p>The implementation takes equal advantage of ascending and + * descending order in its input array, and can take advantage of + * ascending and descending order in different parts of the the same + * input array. It is well-suited to merging two or more sorted arrays: + * simply concatenate the arrays and sort the resulting array. + * + * <p>The implementation was adapted from Tim Peters's list sort for Python + * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt"> + * TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic + * Sorting and Information Theoretic Complexity", in Proceedings of the + * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, + * January 1993. * * @param a the array to be sorted * @param fromIndex the index of the first element (inclusive) to be * sorted * @param toIndex the index of the last element (exclusive) to be sorted * @param c the comparator to determine the order of the array. A - * <tt>null</tt> value indicates that the elements' + * {@code null} value indicates that the elements' * {@linkplain Comparable natural ordering} should be used. * @throws ClassCastException if the array contains elements that are not * <i>mutually comparable</i> using the specified comparator. - * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt> - * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or - * <tt>toIndex > a.length</tt> + * @throws IllegalArgumentException if {@code fromIndex > toIndex} or + * (optional) if the comparator is found to violate the + * {@link Comparator} contract + * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or + * {@code toIndex > a.length} */ public static <T> void sort(T[] a, int fromIndex, int toIndex, Comparator<? super T> c) { + if (LegacyMergeSort.userRequested) + legacyMergeSort(a, fromIndex, toIndex, c); + else + TimSort.sort(a, fromIndex, toIndex, c); + } + + /** To be removed in a future release. */ + private static <T> void legacyMergeSort(T[] a, int fromIndex, int toIndex, + Comparator<? super T> c) { rangeCheck(a.length, fromIndex, toIndex); T[] aux = copyOfRange(a, fromIndex, toIndex); if (c==null) @@ -1270,6 +1432,7 @@ * low is the index in dest to start sorting * high is the end index in dest to end sorting * off is the offset into src corresponding to low in dest + * To be removed in a future release. */ private static void mergeSort(Object[] src, Object[] dest,
--- a/jdk/src/share/classes/java/util/Collections.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/java/util/Collections.java Wed Jul 05 16:59:08 2017 +0200 @@ -100,23 +100,42 @@ /** * Sorts the specified list into ascending order, according to the - * <i>natural ordering</i> of its elements. All elements in the list must - * implement the <tt>Comparable</tt> interface. Furthermore, all elements - * in the list must be <i>mutually comparable</i> (that is, - * <tt>e1.compareTo(e2)</tt> must not throw a <tt>ClassCastException</tt> - * for any elements <tt>e1</tt> and <tt>e2</tt> in the list).<p> + * {@linkplain Comparable natural ordering} of its elements. + * All elements in the list must implement the {@link Comparable} + * interface. Furthermore, all elements in the list must be + * <i>mutually comparable</i> (that is, {@code e1.compareTo(e2)} + * must not throw a {@code ClassCastException} for any elements + * {@code e1} and {@code e2} in the list). * - * This sort is guaranteed to be <i>stable</i>: equal elements will - * not be reordered as a result of the sort.<p> + * <p>This sort is guaranteed to be <i>stable</i>: equal elements will + * not be reordered as a result of the sort. * - * The specified list must be modifiable, but need not be resizable.<p> + * <p>The specified list must be modifiable, but need not be resizable. * - * The sorting algorithm is a modified mergesort (in which the merge is - * omitted if the highest element in the low sublist is less than the - * lowest element in the high sublist). This algorithm offers guaranteed - * n log(n) performance. + * <p>Implementation note: This implementation is a stable, adaptive, + * iterative mergesort that requires far fewer than n lg(n) comparisons + * when the input array is partially sorted, while offering the + * performance of a traditional mergesort when the input array is + * randomly ordered. If the input array is nearly sorted, the + * implementation requires approximately n comparisons. Temporary + * storage requirements vary from a small constant for nearly sorted + * input arrays to n/2 object references for randomly ordered input + * arrays. * - * This implementation dumps the specified list into an array, sorts + * <p>The implementation takes equal advantage of ascending and + * descending order in its input array, and can take advantage of + * ascending and descending order in different parts of the the same + * input array. It is well-suited to merging two or more sorted arrays: + * simply concatenate the arrays and sort the resulting array. + * + * <p>The implementation was adapted from Tim Peters's list sort for Python + * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt"> + * TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic + * Sorting and Information Theoretic Complexity", in Proceedings of the + * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, + * January 1993. + * + * <p>This implementation dumps the specified list into an array, sorts * the array, and iterates over the list resetting each element * from the corresponding position in the array. This avoids the * n<sup>2</sup> log(n) performance that would result from attempting @@ -126,8 +145,10 @@ * @throws ClassCastException if the list contains elements that are not * <i>mutually comparable</i> (for example, strings and integers). * @throws UnsupportedOperationException if the specified list's - * list-iterator does not support the <tt>set</tt> operation. - * @see Comparable + * list-iterator does not support the {@code set} operation. + * @throws IllegalArgumentException (optional) if the implementation + * detects that the natural ordering of the list elements is + * found to violate the {@link Comparable} contract */ public static <T extends Comparable<? super T>> void sort(List<T> list) { Object[] a = list.toArray(); @@ -143,19 +164,38 @@ * Sorts the specified list according to the order induced by the * specified comparator. All elements in the list must be <i>mutually * comparable</i> using the specified comparator (that is, - * <tt>c.compare(e1, e2)</tt> must not throw a <tt>ClassCastException</tt> - * for any elements <tt>e1</tt> and <tt>e2</tt> in the list).<p> + * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException} + * for any elements {@code e1} and {@code e2} in the list). * - * This sort is guaranteed to be <i>stable</i>: equal elements will - * not be reordered as a result of the sort.<p> + * <p>This sort is guaranteed to be <i>stable</i>: equal elements will + * not be reordered as a result of the sort. * - * The sorting algorithm is a modified mergesort (in which the merge is - * omitted if the highest element in the low sublist is less than the - * lowest element in the high sublist). This algorithm offers guaranteed - * n log(n) performance. + * <p>The specified list must be modifiable, but need not be resizable. * - * The specified list must be modifiable, but need not be resizable. - * This implementation dumps the specified list into an array, sorts + * <p>Implementation note: This implementation is a stable, adaptive, + * iterative mergesort that requires far fewer than n lg(n) comparisons + * when the input array is partially sorted, while offering the + * performance of a traditional mergesort when the input array is + * randomly ordered. If the input array is nearly sorted, the + * implementation requires approximately n comparisons. Temporary + * storage requirements vary from a small constant for nearly sorted + * input arrays to n/2 object references for randomly ordered input + * arrays. + * + * <p>The implementation takes equal advantage of ascending and + * descending order in its input array, and can take advantage of + * ascending and descending order in different parts of the the same + * input array. It is well-suited to merging two or more sorted arrays: + * simply concatenate the arrays and sort the resulting array. + * + * <p>The implementation was adapted from Tim Peters's list sort for Python + * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt"> + * TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic + * Sorting and Information Theoretic Complexity", in Proceedings of the + * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, + * January 1993. + * + * <p>This implementation dumps the specified list into an array, sorts * the array, and iterates over the list resetting each element * from the corresponding position in the array. This avoids the * n<sup>2</sup> log(n) performance that would result from attempting @@ -163,13 +203,14 @@ * * @param list the list to be sorted. * @param c the comparator to determine the order of the list. A - * <tt>null</tt> value indicates that the elements' <i>natural + * {@code null} value indicates that the elements' <i>natural * ordering</i> should be used. * @throws ClassCastException if the list contains elements that are not * <i>mutually comparable</i> using the specified comparator. * @throws UnsupportedOperationException if the specified list's - * list-iterator does not support the <tt>set</tt> operation. - * @see Comparator + * list-iterator does not support the {@code set} operation. + * @throws IllegalArgumentException (optional) if the comparator is + * found to violate the {@link Comparator} contract */ public static <T> void sort(List<T> list, Comparator<? super T> c) { Object[] a = list.toArray();
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/jdk/src/share/classes/java/util/ComparableTimSort.java Wed Jul 05 16:59:08 2017 +0200 @@ -0,0 +1,895 @@ +/* + * Copyright 2009 Google Inc. All Rights Reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. Sun designates this + * particular file as subject to the "Classpath" exception as provided + * by Sun in the LICENSE file that accompanied this code. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, + * CA 95054 USA or visit www.sun.com if you need additional information or + * have any questions. + */ + +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.) + * + * @author Josh Bloch + */ +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; + + /** + * 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, hi); + 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 + assert lo == hi; + ts.mergeForceCollapse(); + 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) { + 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; + 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; + } + 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) { + 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) { + 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) { + assert stackSize >= 2; + assert i >= 0; + 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]; + assert len1 > 0 && len2 > 0; + 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); + 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); + 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) { + 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; + } + 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] + } + 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) { + 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; + } + 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 + } + 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) { + 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 { + 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 { + 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) // len1 == 1 || len1 == 0 + 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) { + 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 (len1 == 0) { + throw new IllegalArgumentException( + "Comparison method violates its general contract!"); + } else { + assert len2 == 0; + 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) { + 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 { + 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 { + 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; // len2 == 1 || len2 == 0 + } + 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) { + 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 (len2 == 0) { + throw new IllegalArgumentException( + "Comparison method violates its general contract!"); + } else { + assert len1 == 0; + 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); + } +}
--- a/jdk/src/share/classes/java/util/Formatter.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/java/util/Formatter.java Wed Jul 05 16:59:08 2017 +0200 @@ -2818,15 +2818,18 @@ } private void printString(Object arg, Locale l) throws IOException { - if (arg == null) { - print("null"); - } else if (arg instanceof Formattable) { + if (arg instanceof Formattable) { Formatter fmt = formatter; if (formatter.locale() != l) fmt = new Formatter(formatter.out(), l); ((Formattable)arg).formatTo(fmt, f.valueOf(), width, precision); } else { - print(arg.toString()); + if (f.contains(Flags.ALTERNATE)) + failMismatch(Flags.ALTERNATE, 's'); + if (arg == null) + print("null"); + else + print(arg.toString()); } }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/jdk/src/share/classes/java/util/TimSort.java Wed Jul 05 16:59:08 2017 +0200 @@ -0,0 +1,928 @@ +/* + * Copyright 2009 Google Inc. All Rights Reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. Sun designates this + * particular file as subject to the "Classpath" exception as provided + * by Sun in the LICENSE file that accompanied this code. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, + * CA 95054 USA or visit www.sun.com if you need additional information or + * have any questions. + */ + +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. + * + * @author Josh Bloch + */ +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; + + /** + * 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, hi, 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 + assert lo == hi; + ts.mergeForceCollapse(); + 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) { + 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; + 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; + } + 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) { + 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) { + 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) { + assert stackSize >= 2; + assert i >= 0; + 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]; + assert len1 > 0 && len2 > 0; + 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); + 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); + 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) { + 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; + } + 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] + } + 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) { + 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; + } + 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 + } + 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) { + 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 { + 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 { + 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) // len1 == 1 || len1 == 0 + 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) { + 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 (len1 == 0) { + throw new IllegalArgumentException( + "Comparison method violates its general contract!"); + } else { + assert len2 == 0; + 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) { + 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 { + 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 { + 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) // len2 == 1 || len2 == 0 + 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) { + 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 (len2 == 0) { + throw new IllegalArgumentException( + "Comparison method violates its general contract!"); + } else { + assert len1 == 0; + 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); + } +}
--- a/jdk/src/share/classes/java/util/concurrent/ConcurrentLinkedQueue.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/java/util/concurrent/ConcurrentLinkedQueue.java Wed Jul 05 16:59:08 2017 +0200 @@ -34,9 +34,13 @@ */ package java.util.concurrent; -import java.util.*; -import java.util.concurrent.atomic.*; +import java.util.AbstractQueue; +import java.util.ArrayList; +import java.util.Collection; +import java.util.Iterator; +import java.util.NoSuchElementException; +import java.util.Queue; /** * An unbounded thread-safe {@linkplain Queue queue} based on linked nodes. @@ -47,9 +51,9 @@ * queue the shortest time. New elements * are inserted at the tail of the queue, and the queue retrieval * operations obtain elements at the head of the queue. - * A <tt>ConcurrentLinkedQueue</tt> is an appropriate choice when + * A {@code ConcurrentLinkedQueue} is an appropriate choice when * many threads will share access to a common collection. - * This queue does not permit <tt>null</tt> elements. + * This queue does not permit {@code null} elements. * * <p>This implementation employs an efficient "wait-free" * algorithm based on one described in <a @@ -57,7 +61,7 @@ * Fast, and Practical Non-Blocking and Blocking Concurrent Queue * Algorithms</a> by Maged M. Michael and Michael L. Scott. * - * <p>Beware that, unlike in most collections, the <tt>size</tt> method + * <p>Beware that, unlike in most collections, the {@code size} method * is <em>NOT</em> a constant-time operation. Because of the * asynchronous nature of these queues, determining the current number * of elements requires a traversal of the elements. @@ -87,51 +91,102 @@ private static final long serialVersionUID = 196745693267521676L; /* - * This is a straight adaptation of Michael & Scott algorithm. - * For explanation, read the paper. The only (minor) algorithmic - * difference is that this version supports lazy deletion of - * internal nodes (method remove(Object)) -- remove CAS'es item - * fields to null. The normal queue operations unlink but then - * pass over nodes with null item fields. Similarly, iteration - * methods ignore those with nulls. + * This is a modification of the Michael & Scott algorithm, + * adapted for a garbage-collected environment, with support for + * interior node deletion (to support remove(Object)). For + * explanation, read the paper. * - * Also note that like most non-blocking algorithms in this - * package, this implementation relies on the fact that in garbage + * Note that like most non-blocking algorithms in this package, + * this implementation relies on the fact that in garbage * collected systems, there is no possibility of ABA problems due * to recycled nodes, so there is no need to use "counted * pointers" or related techniques seen in versions used in * non-GC'ed settings. + * + * The fundamental invariants are: + * - There is exactly one (last) Node with a null next reference, + * which is CASed when enqueueing. This last Node can be + * reached in O(1) time from tail, but tail is merely an + * optimization - it can always be reached in O(N) time from + * head as well. + * - The elements contained in the queue are the non-null items in + * Nodes that are reachable from head. CASing the item + * reference of a Node to null atomically removes it from the + * queue. Reachability of all elements from head must remain + * true even in the case of concurrent modifications that cause + * head to advance. A dequeued Node may remain in use + * indefinitely due to creation of an Iterator or simply a + * poll() that has lost its time slice. + * + * The above might appear to imply that all Nodes are GC-reachable + * from a predecessor dequeued Node. That would cause two problems: + * - allow a rogue Iterator to cause unbounded memory retention + * - cause cross-generational linking of old Nodes to new Nodes if + * a Node was tenured while live, which generational GCs have a + * hard time dealing with, causing repeated major collections. + * However, only non-deleted Nodes need to be reachable from + * dequeued Nodes, and reachability does not necessarily have to + * be of the kind understood by the GC. We use the trick of + * linking a Node that has just been dequeued to itself. Such a + * self-link implicitly means to advance to head. + * + * Both head and tail are permitted to lag. In fact, failing to + * update them every time one could is a significant optimization + * (fewer CASes). This is controlled by local "hops" variables + * that only trigger helping-CASes after experiencing multiple + * lags. + * + * Since head and tail are updated concurrently and independently, + * it is possible for tail to lag behind head (why not)? + * + * CASing a Node's item reference to null atomically removes the + * element from the queue. Iterators skip over Nodes with null + * items. Prior implementations of this class had a race between + * poll() and remove(Object) where the same element would appear + * to be successfully removed by two concurrent operations. The + * method remove(Object) also lazily unlinks deleted Nodes, but + * this is merely an optimization. + * + * When constructing a Node (before enqueuing it) we avoid paying + * for a volatile write to item by using lazySet instead of a + * normal write. This allows the cost of enqueue to be + * "one-and-a-half" CASes. + * + * Both head and tail may or may not point to a Node with a + * non-null item. If the queue is empty, all items must of course + * be null. Upon creation, both head and tail refer to a dummy + * Node with null item. Both head and tail are only updated using + * CAS, so they never regress, although again this is merely an + * optimization. */ private static class Node<E> { private volatile E item; private volatile Node<E> next; - private static final - AtomicReferenceFieldUpdater<Node, Node> - nextUpdater = - AtomicReferenceFieldUpdater.newUpdater - (Node.class, Node.class, "next"); - private static final - AtomicReferenceFieldUpdater<Node, Object> - itemUpdater = - AtomicReferenceFieldUpdater.newUpdater - (Node.class, Object.class, "item"); - - Node(E x) { item = x; } - - Node(E x, Node<E> n) { item = x; next = n; } + Node(E item) { + // Piggyback on imminent casNext() + lazySetItem(item); + } E getItem() { return item; } boolean casItem(E cmp, E val) { - return itemUpdater.compareAndSet(this, cmp, val); + return UNSAFE.compareAndSwapObject(this, itemOffset, cmp, val); } void setItem(E val) { - itemUpdater.set(this, val); + item = val; + } + + void lazySetItem(E val) { + UNSAFE.putOrderedObject(this, itemOffset, val); + } + + void lazySetNext(Node<E> val) { + UNSAFE.putOrderedObject(this, nextOffset, val); } Node<E> getNext() { @@ -139,52 +194,55 @@ } boolean casNext(Node<E> cmp, Node<E> val) { - return nextUpdater.compareAndSet(this, cmp, val); + return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val); } - void setNext(Node<E> val) { - nextUpdater.set(this, val); - } + // Unsafe mechanics + private static final sun.misc.Unsafe UNSAFE = + sun.misc.Unsafe.getUnsafe(); + private static final long nextOffset = + objectFieldOffset(UNSAFE, "next", Node.class); + private static final long itemOffset = + objectFieldOffset(UNSAFE, "item", Node.class); } - private static final - AtomicReferenceFieldUpdater<ConcurrentLinkedQueue, Node> - tailUpdater = - AtomicReferenceFieldUpdater.newUpdater - (ConcurrentLinkedQueue.class, Node.class, "tail"); - private static final - AtomicReferenceFieldUpdater<ConcurrentLinkedQueue, Node> - headUpdater = - AtomicReferenceFieldUpdater.newUpdater - (ConcurrentLinkedQueue.class, Node.class, "head"); - - private boolean casTail(Node<E> cmp, Node<E> val) { - return tailUpdater.compareAndSet(this, cmp, val); - } - - private boolean casHead(Node<E> cmp, Node<E> val) { - return headUpdater.compareAndSet(this, cmp, val); - } - + /** + * A node from which the first live (non-deleted) node (if any) + * can be reached in O(1) time. + * Invariants: + * - all live nodes are reachable from head via succ() + * - head != null + * - (tmp = head).next != tmp || tmp != head + * Non-invariants: + * - head.item may or may not be null. + * - it is permitted for tail to lag behind head, that is, for tail + * to not be reachable from head! + */ + private transient volatile Node<E> head = new Node<E>(null); /** - * Pointer to header node, initialized to a dummy node. The first - * actual node is at head.getNext(). + * A node from which the last node on list (that is, the unique + * node with node.next == null) can be reached in O(1) time. + * Invariants: + * - the last node is always reachable from tail via succ() + * - tail != null + * Non-invariants: + * - tail.item may or may not be null. + * - it is permitted for tail to lag behind head, that is, for tail + * to not be reachable from head! + * - tail.next may or may not be self-pointing to tail. */ - private transient volatile Node<E> head = new Node<E>(null, null); - - /** Pointer to last node on list **/ private transient volatile Node<E> tail = head; /** - * Creates a <tt>ConcurrentLinkedQueue</tt> that is initially empty. + * Creates a {@code ConcurrentLinkedQueue} that is initially empty. */ public ConcurrentLinkedQueue() {} /** - * Creates a <tt>ConcurrentLinkedQueue</tt> + * Creates a {@code ConcurrentLinkedQueue} * initially containing the elements of the given collection, * added in traversal order of the collection's iterator. * @param c the collection of elements to initially contain @@ -201,7 +259,7 @@ /** * Inserts the specified element at the tail of this queue. * - * @return <tt>true</tt> (as specified by {@link Collection#add}) + * @return {@code true} (as specified by {@link Collection#add}) * @throws NullPointerException if the specified element is null */ public boolean add(E e) { @@ -209,107 +267,135 @@ } /** + * We don't bother to update head or tail pointers if fewer than + * HOPS links from "true" location. We assume that volatile + * writes are significantly more expensive than volatile reads. + */ + private static final int HOPS = 1; + + /** + * Try to CAS head to p. If successful, repoint old head to itself + * as sentinel for succ(), below. + */ + final void updateHead(Node<E> h, Node<E> p) { + if (h != p && casHead(h, p)) + h.lazySetNext(h); + } + + /** + * Returns the successor of p, or the head node if p.next has been + * linked to self, which will only be true if traversing with a + * stale pointer that is now off the list. + */ + final Node<E> succ(Node<E> p) { + Node<E> next = p.getNext(); + return (p == next) ? head : next; + } + + /** * Inserts the specified element at the tail of this queue. * - * @return <tt>true</tt> (as specified by {@link Queue#offer}) + * @return {@code true} (as specified by {@link Queue#offer}) * @throws NullPointerException if the specified element is null */ public boolean offer(E e) { if (e == null) throw new NullPointerException(); - Node<E> n = new Node<E>(e, null); + Node<E> n = new Node<E>(e); + retry: for (;;) { Node<E> t = tail; - Node<E> s = t.getNext(); - if (t == tail) { - if (s == null) { - if (t.casNext(s, n)) { - casTail(t, n); - return true; - } + Node<E> p = t; + for (int hops = 0; ; hops++) { + Node<E> next = succ(p); + if (next != null) { + if (hops > HOPS && t != tail) + continue retry; + p = next; + } else if (p.casNext(null, n)) { + if (hops >= HOPS) + casTail(t, n); // Failure is OK. + return true; } else { - casTail(t, s); + p = succ(p); } } } } public E poll() { - for (;;) { - Node<E> h = head; - Node<E> t = tail; - Node<E> first = h.getNext(); - if (h == head) { - if (h == t) { - if (first == null) - return null; - else - casTail(t, first); - } else if (casHead(h, first)) { - E item = first.getItem(); - if (item != null) { - first.setItem(null); - return item; - } - // else skip over deleted item, continue loop, + Node<E> h = head; + Node<E> p = h; + for (int hops = 0; ; hops++) { + E item = p.getItem(); + + if (item != null && p.casItem(item, null)) { + if (hops >= HOPS) { + Node<E> q = p.getNext(); + updateHead(h, (q != null) ? q : p); } + return item; } + Node<E> next = succ(p); + if (next == null) { + updateHead(h, p); + break; + } + p = next; } + return null; } - public E peek() { // same as poll except don't remove item + public E peek() { + Node<E> h = head; + Node<E> p = h; + E item; for (;;) { - Node<E> h = head; - Node<E> t = tail; - Node<E> first = h.getNext(); - if (h == head) { - if (h == t) { - if (first == null) - return null; - else - casTail(t, first); - } else { - E item = first.getItem(); - if (item != null) - return item; - else // remove deleted node and continue - casHead(h, first); - } + item = p.getItem(); + if (item != null) + break; + Node<E> next = succ(p); + if (next == null) { + break; } + p = next; } + updateHead(h, p); + return item; } /** - * Returns the first actual (non-header) node on list. This is yet - * another variant of poll/peek; here returning out the first - * node, not element (so we cannot collapse with peek() without - * introducing race.) + * Returns the first live (non-deleted) node on list, or null if none. + * This is yet another variant of poll/peek; here returning the + * first node, not element. We could make peek() a wrapper around + * first(), but that would cost an extra volatile read of item, + * and the need to add a retry loop to deal with the possibility + * of losing a race to a concurrent poll(). */ Node<E> first() { + Node<E> h = head; + Node<E> p = h; + Node<E> result; for (;;) { - Node<E> h = head; - Node<E> t = tail; - Node<E> first = h.getNext(); - if (h == head) { - if (h == t) { - if (first == null) - return null; - else - casTail(t, first); - } else { - if (first.getItem() != null) - return first; - else // remove deleted node and continue - casHead(h, first); - } + E item = p.getItem(); + if (item != null) { + result = p; + break; } + Node<E> next = succ(p); + if (next == null) { + result = null; + break; + } + p = next; } + updateHead(h, p); + return result; } - /** - * Returns <tt>true</tt> if this queue contains no elements. + * Returns {@code true} if this queue contains no elements. * - * @return <tt>true</tt> if this queue contains no elements + * @return {@code true} if this queue contains no elements */ public boolean isEmpty() { return first() == null; @@ -317,8 +403,8 @@ /** * Returns the number of elements in this queue. If this queue - * contains more than <tt>Integer.MAX_VALUE</tt> elements, returns - * <tt>Integer.MAX_VALUE</tt>. + * contains more than {@code Integer.MAX_VALUE} elements, returns + * {@code Integer.MAX_VALUE}. * * <p>Beware that, unlike in most collections, this method is * <em>NOT</em> a constant-time operation. Because of the @@ -329,7 +415,7 @@ */ public int size() { int count = 0; - for (Node<E> p = first(); p != null; p = p.getNext()) { + for (Node<E> p = first(); p != null; p = succ(p)) { if (p.getItem() != null) { // Collections.size() spec says to max out if (++count == Integer.MAX_VALUE) @@ -340,16 +426,16 @@ } /** - * Returns <tt>true</tt> if this queue contains the specified element. - * More formally, returns <tt>true</tt> if and only if this queue contains - * at least one element <tt>e</tt> such that <tt>o.equals(e)</tt>. + * Returns {@code true} if this queue contains the specified element. + * More formally, returns {@code true} if and only if this queue contains + * at least one element {@code e} such that {@code o.equals(e)}. * * @param o object to be checked for containment in this queue - * @return <tt>true</tt> if this queue contains the specified element + * @return {@code true} if this queue contains the specified element */ public boolean contains(Object o) { if (o == null) return false; - for (Node<E> p = first(); p != null; p = p.getNext()) { + for (Node<E> p = first(); p != null; p = succ(p)) { E item = p.getItem(); if (item != null && o.equals(item)) @@ -360,23 +446,29 @@ /** * Removes a single instance of the specified element from this queue, - * if it is present. More formally, removes an element <tt>e</tt> such - * that <tt>o.equals(e)</tt>, if this queue contains one or more such + * if it is present. More formally, removes an element {@code e} such + * that {@code o.equals(e)}, if this queue contains one or more such * elements. - * Returns <tt>true</tt> if this queue contained the specified element + * Returns {@code true} if this queue contained the specified element * (or equivalently, if this queue changed as a result of the call). * * @param o element to be removed from this queue, if present - * @return <tt>true</tt> if this queue changed as a result of the call + * @return {@code true} if this queue changed as a result of the call */ public boolean remove(Object o) { if (o == null) return false; - for (Node<E> p = first(); p != null; p = p.getNext()) { + Node<E> pred = null; + for (Node<E> p = first(); p != null; p = succ(p)) { E item = p.getItem(); if (item != null && o.equals(item) && - p.casItem(item, null)) + p.casItem(item, null)) { + Node<E> next = succ(p); + if (pred != null && next != null) + pred.casNext(p, next); return true; + } + pred = p; } return false; } @@ -397,7 +489,7 @@ public Object[] toArray() { // Use ArrayList to deal with resizing. ArrayList<E> al = new ArrayList<E>(); - for (Node<E> p = first(); p != null; p = p.getNext()) { + for (Node<E> p = first(); p != null; p = succ(p)) { E item = p.getItem(); if (item != null) al.add(item); @@ -415,22 +507,22 @@ * <p>If this queue fits in the specified array with room to spare * (i.e., the array has more elements than this queue), the element in * the array immediately following the end of the queue is set to - * <tt>null</tt>. + * {@code null}. * * <p>Like the {@link #toArray()} method, this method acts as bridge between * array-based and collection-based APIs. Further, this method allows * precise control over the runtime type of the output array, and may, * under certain circumstances, be used to save allocation costs. * - * <p>Suppose <tt>x</tt> is a queue known to contain only strings. + * <p>Suppose {@code x} is a queue known to contain only strings. * The following code can be used to dump the queue into a newly - * allocated array of <tt>String</tt>: + * allocated array of {@code String}: * * <pre> * String[] y = x.toArray(new String[0]);</pre> * - * Note that <tt>toArray(new Object[0])</tt> is identical in function to - * <tt>toArray()</tt>. + * Note that {@code toArray(new Object[0])} is identical in function to + * {@code toArray()}. * * @param a the array into which the elements of the queue are to * be stored, if it is big enough; otherwise, a new array of the @@ -441,11 +533,12 @@ * this queue * @throws NullPointerException if the specified array is null */ + @SuppressWarnings("unchecked") public <T> T[] toArray(T[] a) { // try to use sent-in array int k = 0; Node<E> p; - for (p = first(); p != null && k < a.length; p = p.getNext()) { + for (p = first(); p != null && k < a.length; p = succ(p)) { E item = p.getItem(); if (item != null) a[k++] = (T)item; @@ -458,7 +551,7 @@ // If won't fit, use ArrayList version ArrayList<E> al = new ArrayList<E>(); - for (Node<E> q = first(); q != null; q = q.getNext()) { + for (Node<E> q = first(); q != null; q = succ(q)) { E item = q.getItem(); if (item != null) al.add(item); @@ -469,7 +562,8 @@ /** * Returns an iterator over the elements in this queue in proper sequence. * The returned iterator is a "weakly consistent" iterator that - * will never throw {@link ConcurrentModificationException}, + * will never throw {@link java.util.ConcurrentModificationException + * ConcurrentModificationException}, * and guarantees to traverse elements as they existed upon * construction of the iterator, and may (but is not guaranteed to) * reflect any modifications subsequent to construction. @@ -511,7 +605,15 @@ lastRet = nextNode; E x = nextItem; - Node<E> p = (nextNode == null)? first() : nextNode.getNext(); + Node<E> pred, p; + if (nextNode == null) { + p = first(); + pred = null; + } else { + pred = nextNode; + p = succ(nextNode); + } + for (;;) { if (p == null) { nextNode = null; @@ -523,8 +625,13 @@ nextNode = p; nextItem = item; return x; - } else // skip over nulls - p = p.getNext(); + } else { + // skip over nulls + Node<E> next = succ(p); + if (pred != null && next != null) + pred.casNext(p, next); + p = next; + } } } @@ -549,7 +656,7 @@ /** * Save the state to a stream (that is, serialize it). * - * @serialData All of the elements (each an <tt>E</tt>) in + * @serialData All of the elements (each an {@code E}) in * the proper order, followed by a null * @param s the stream */ @@ -560,7 +667,7 @@ s.defaultWriteObject(); // Write out all elements in the proper order. - for (Node<E> p = first(); p != null; p = p.getNext()) { + for (Node<E> p = first(); p != null; p = succ(p)) { Object item = p.getItem(); if (item != null) s.writeObject(item); @@ -579,10 +686,11 @@ throws java.io.IOException, ClassNotFoundException { // Read in capacity, and any hidden stuff s.defaultReadObject(); - head = new Node<E>(null, null); + head = new Node<E>(null); tail = head; // Read in all elements and place in queue for (;;) { + @SuppressWarnings("unchecked") E item = (E)s.readObject(); if (item == null) break; @@ -591,4 +699,35 @@ } } + // Unsafe mechanics + + private static final sun.misc.Unsafe UNSAFE = sun.misc.Unsafe.getUnsafe(); + private static final long headOffset = + objectFieldOffset(UNSAFE, "head", ConcurrentLinkedQueue.class); + private static final long tailOffset = + objectFieldOffset(UNSAFE, "tail", ConcurrentLinkedQueue.class); + + private boolean casTail(Node<E> cmp, Node<E> val) { + return UNSAFE.compareAndSwapObject(this, tailOffset, cmp, val); + } + + private boolean casHead(Node<E> cmp, Node<E> val) { + return UNSAFE.compareAndSwapObject(this, headOffset, cmp, val); + } + + private void lazySetHead(Node<E> val) { + UNSAFE.putOrderedObject(this, headOffset, val); + } + + static long objectFieldOffset(sun.misc.Unsafe UNSAFE, + String field, Class<?> klazz) { + try { + return UNSAFE.objectFieldOffset(klazz.getDeclaredField(field)); + } catch (NoSuchFieldException e) { + // Convert Exception to corresponding Error + NoSuchFieldError error = new NoSuchFieldError(field); + error.initCause(e); + throw error; + } + } }
--- a/jdk/src/share/classes/java/util/concurrent/LinkedBlockingDeque.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/java/util/concurrent/LinkedBlockingDeque.java Wed Jul 05 16:59:08 2017 +0200 @@ -34,8 +34,13 @@ */ package java.util.concurrent; -import java.util.*; -import java.util.concurrent.locks.*; + +import java.util.AbstractQueue; +import java.util.Collection; +import java.util.Iterator; +import java.util.NoSuchElementException; +import java.util.concurrent.locks.Condition; +import java.util.concurrent.locks.ReentrantLock; /** * An optionally-bounded {@linkplain BlockingDeque blocking deque} based on @@ -73,6 +78,20 @@ /* * Implemented as a simple doubly-linked list protected by a * single lock and using conditions to manage blocking. + * + * To implement weakly consistent iterators, it appears we need to + * keep all Nodes GC-reachable from a predecessor dequeued Node. + * That would cause two problems: + * - allow a rogue Iterator to cause unbounded memory retention + * - cause cross-generational linking of old Nodes to new Nodes if + * a Node was tenured while live, which generational GCs have a + * hard time dealing with, causing repeated major collections. + * However, only non-deleted Nodes need to be reachable from + * dequeued Nodes, and reachability does not necessarily have to + * be of the kind understood by the GC. We use the trick of + * linking a Node that has just been dequeued to itself. Such a + * self-link implicitly means to jump to "first" (for next links) + * or "last" (for prev links). */ /* @@ -86,9 +105,27 @@ /** Doubly-linked list node class */ static final class Node<E> { + /** + * The item, or null if this node has been removed. + */ E item; + + /** + * One of: + * - the real predecessor Node + * - this Node, meaning the predecessor is tail + * - null, meaning there is no predecessor + */ Node<E> prev; + + /** + * One of: + * - the real successor Node + * - this Node, meaning the successor is head + * - null, meaning there is no successor + */ Node<E> next; + Node(E x, Node<E> p, Node<E> n) { item = x; prev = p; @@ -96,23 +133,37 @@ } } - /** Pointer to first node */ - private transient Node<E> first; - /** Pointer to last node */ - private transient Node<E> last; + /** + * Pointer to first node. + * Invariant: (first == null && last == null) || + * (first.prev == null && first.item != null) + */ + transient Node<E> first; + + /** + * Pointer to last node. + * Invariant: (first == null && last == null) || + * (last.next == null && last.item != null) + */ + transient Node<E> last; + /** Number of items in the deque */ private transient int count; + /** Maximum number of items in the deque */ private final int capacity; + /** Main lock guarding all access */ - private final ReentrantLock lock = new ReentrantLock(); + final ReentrantLock lock = new ReentrantLock(); + /** Condition for waiting takes */ private final Condition notEmpty = lock.newCondition(); + /** Condition for waiting puts */ private final Condition notFull = lock.newCondition(); /** - * Creates a <tt>LinkedBlockingDeque</tt> with a capacity of + * Creates a {@code LinkedBlockingDeque} with a capacity of * {@link Integer#MAX_VALUE}. */ public LinkedBlockingDeque() { @@ -120,10 +171,10 @@ } /** - * Creates a <tt>LinkedBlockingDeque</tt> with the given (fixed) capacity. + * Creates a {@code LinkedBlockingDeque} with the given (fixed) capacity. * * @param capacity the capacity of this deque - * @throws IllegalArgumentException if <tt>capacity</tt> is less than 1 + * @throws IllegalArgumentException if {@code capacity} is less than 1 */ public LinkedBlockingDeque(int capacity) { if (capacity <= 0) throw new IllegalArgumentException(); @@ -131,7 +182,7 @@ } /** - * Creates a <tt>LinkedBlockingDeque</tt> with a capacity of + * Creates a {@code LinkedBlockingDeque} with a capacity of * {@link Integer#MAX_VALUE}, initially containing the elements of * the given collection, added in traversal order of the * collection's iterator. @@ -142,8 +193,18 @@ */ public LinkedBlockingDeque(Collection<? extends E> c) { this(Integer.MAX_VALUE); - for (E e : c) - add(e); + final ReentrantLock lock = this.lock; + lock.lock(); // Never contended, but necessary for visibility + try { + for (E e : c) { + if (e == null) + throw new NullPointerException(); + if (!linkLast(e)) + throw new IllegalStateException("Deque full"); + } + } finally { + lock.unlock(); + } } @@ -153,9 +214,9 @@ * Links e as first element, or returns false if full. */ private boolean linkFirst(E e) { + // assert lock.isHeldByCurrentThread(); if (count >= capacity) return false; - ++count; Node<E> f = first; Node<E> x = new Node<E>(e, null, f); first = x; @@ -163,6 +224,7 @@ last = x; else f.prev = x; + ++count; notEmpty.signal(); return true; } @@ -171,9 +233,9 @@ * Links e as last element, or returns false if full. */ private boolean linkLast(E e) { + // assert lock.isHeldByCurrentThread(); if (count >= capacity) return false; - ++count; Node<E> l = last; Node<E> x = new Node<E>(e, l, null); last = x; @@ -181,6 +243,7 @@ first = x; else l.next = x; + ++count; notEmpty.signal(); return true; } @@ -189,10 +252,14 @@ * Removes and returns first element, or null if empty. */ private E unlinkFirst() { + // assert lock.isHeldByCurrentThread(); Node<E> f = first; if (f == null) return null; Node<E> n = f.next; + E item = f.item; + f.item = null; + f.next = f; // help GC first = n; if (n == null) last = null; @@ -200,17 +267,21 @@ n.prev = null; --count; notFull.signal(); - return f.item; + return item; } /** * Removes and returns last element, or null if empty. */ private E unlinkLast() { + // assert lock.isHeldByCurrentThread(); Node<E> l = last; if (l == null) return null; Node<E> p = l.prev; + E item = l.item; + l.item = null; + l.prev = l; // help GC last = p; if (p == null) first = null; @@ -218,31 +289,29 @@ p.next = null; --count; notFull.signal(); - return l.item; + return item; } /** - * Unlink e + * Unlinks x. */ - private void unlink(Node<E> x) { + void unlink(Node<E> x) { + // assert lock.isHeldByCurrentThread(); Node<E> p = x.prev; Node<E> n = x.next; if (p == null) { - if (n == null) - first = last = null; - else { - n.prev = null; - first = n; - } + unlinkFirst(); } else if (n == null) { - p.next = null; - last = p; + unlinkLast(); } else { p.next = n; n.prev = p; + x.item = null; + // Don't mess with x's links. They may still be in use by + // an iterator. + --count; + notFull.signal(); } - --count; - notFull.signalAll(); } // BlockingDeque methods @@ -270,6 +339,7 @@ */ public boolean offerFirst(E e) { if (e == null) throw new NullPointerException(); + final ReentrantLock lock = this.lock; lock.lock(); try { return linkFirst(e); @@ -283,6 +353,7 @@ */ public boolean offerLast(E e) { if (e == null) throw new NullPointerException(); + final ReentrantLock lock = this.lock; lock.lock(); try { return linkLast(e); @@ -297,6 +368,7 @@ */ public void putFirst(E e) throws InterruptedException { if (e == null) throw new NullPointerException(); + final ReentrantLock lock = this.lock; lock.lock(); try { while (!linkFirst(e)) @@ -312,6 +384,7 @@ */ public void putLast(E e) throws InterruptedException { if (e == null) throw new NullPointerException(); + final ReentrantLock lock = this.lock; lock.lock(); try { while (!linkLast(e)) @@ -329,15 +402,15 @@ throws InterruptedException { if (e == null) throw new NullPointerException(); long nanos = unit.toNanos(timeout); + final ReentrantLock lock = this.lock; lock.lockInterruptibly(); try { - for (;;) { - if (linkFirst(e)) - return true; + while (!linkFirst(e)) { if (nanos <= 0) return false; nanos = notFull.awaitNanos(nanos); } + return true; } finally { lock.unlock(); } @@ -351,15 +424,15 @@ throws InterruptedException { if (e == null) throw new NullPointerException(); long nanos = unit.toNanos(timeout); + final ReentrantLock lock = this.lock; lock.lockInterruptibly(); try { - for (;;) { - if (linkLast(e)) - return true; + while (!linkLast(e)) { if (nanos <= 0) return false; nanos = notFull.awaitNanos(nanos); } + return true; } finally { lock.unlock(); } @@ -384,6 +457,7 @@ } public E pollFirst() { + final ReentrantLock lock = this.lock; lock.lock(); try { return unlinkFirst(); @@ -393,6 +467,7 @@ } public E pollLast() { + final ReentrantLock lock = this.lock; lock.lock(); try { return unlinkLast(); @@ -402,6 +477,7 @@ } public E takeFirst() throws InterruptedException { + final ReentrantLock lock = this.lock; lock.lock(); try { E x; @@ -414,6 +490,7 @@ } public E takeLast() throws InterruptedException { + final ReentrantLock lock = this.lock; lock.lock(); try { E x; @@ -428,16 +505,16 @@ public E pollFirst(long timeout, TimeUnit unit) throws InterruptedException { long nanos = unit.toNanos(timeout); + final ReentrantLock lock = this.lock; lock.lockInterruptibly(); try { - for (;;) { - E x = unlinkFirst(); - if (x != null) - return x; + E x; + while ( (x = unlinkFirst()) == null) { if (nanos <= 0) return null; nanos = notEmpty.awaitNanos(nanos); } + return x; } finally { lock.unlock(); } @@ -446,16 +523,16 @@ public E pollLast(long timeout, TimeUnit unit) throws InterruptedException { long nanos = unit.toNanos(timeout); + final ReentrantLock lock = this.lock; lock.lockInterruptibly(); try { - for (;;) { - E x = unlinkLast(); - if (x != null) - return x; + E x; + while ( (x = unlinkLast()) == null) { if (nanos <= 0) return null; nanos = notEmpty.awaitNanos(nanos); } + return x; } finally { lock.unlock(); } @@ -480,6 +557,7 @@ } public E peekFirst() { + final ReentrantLock lock = this.lock; lock.lock(); try { return (first == null) ? null : first.item; @@ -489,6 +567,7 @@ } public E peekLast() { + final ReentrantLock lock = this.lock; lock.lock(); try { return (last == null) ? null : last.item; @@ -499,6 +578,7 @@ public boolean removeFirstOccurrence(Object o) { if (o == null) return false; + final ReentrantLock lock = this.lock; lock.lock(); try { for (Node<E> p = first; p != null; p = p.next) { @@ -515,6 +595,7 @@ public boolean removeLastOccurrence(Object o) { if (o == null) return false; + final ReentrantLock lock = this.lock; lock.lock(); try { for (Node<E> p = last; p != null; p = p.prev) { @@ -619,14 +700,15 @@ * Returns the number of additional elements that this deque can ideally * (in the absence of memory or resource constraints) accept without * blocking. This is always equal to the initial capacity of this deque - * less the current <tt>size</tt> of this deque. + * less the current {@code size} of this deque. * * <p>Note that you <em>cannot</em> always tell if an attempt to insert - * an element will succeed by inspecting <tt>remainingCapacity</tt> + * an element will succeed by inspecting {@code remainingCapacity} * because it may be the case that another thread is about to * insert or remove an element. */ public int remainingCapacity() { + final ReentrantLock lock = this.lock; lock.lock(); try { return capacity - count; @@ -642,22 +724,7 @@ * @throws IllegalArgumentException {@inheritDoc} */ public int drainTo(Collection<? super E> c) { - if (c == null) - throw new NullPointerException(); - if (c == this) - throw new IllegalArgumentException(); - lock.lock(); - try { - for (Node<E> p = first; p != null; p = p.next) - c.add(p.item); - int n = count; - count = 0; - first = last = null; - notFull.signalAll(); - return n; - } finally { - lock.unlock(); - } + return drainTo(c, Integer.MAX_VALUE); } /** @@ -671,19 +738,14 @@ throw new NullPointerException(); if (c == this) throw new IllegalArgumentException(); + final ReentrantLock lock = this.lock; lock.lock(); try { - int n = 0; - while (n < maxElements && first != null) { - c.add(first.item); - first.prev = null; - first = first.next; - --count; - ++n; + int n = Math.min(maxElements, count); + for (int i = 0; i < n; i++) { + c.add(first.item); // In this order, in case add() throws. + unlinkFirst(); } - if (first == null) - last = null; - notFull.signalAll(); return n; } finally { lock.unlock(); @@ -712,16 +774,16 @@ /** * Removes the first occurrence of the specified element from this deque. * If the deque does not contain the element, it is unchanged. - * More formally, removes the first element <tt>e</tt> such that - * <tt>o.equals(e)</tt> (if such an element exists). - * Returns <tt>true</tt> if this deque contained the specified element + * More formally, removes the first element {@code e} such that + * {@code o.equals(e)} (if such an element exists). + * Returns {@code true} if this deque contained the specified element * (or equivalently, if this deque changed as a result of the call). * * <p>This method is equivalent to * {@link #removeFirstOccurrence(Object) removeFirstOccurrence}. * * @param o element to be removed from this deque, if present - * @return <tt>true</tt> if this deque changed as a result of the call + * @return {@code true} if this deque changed as a result of the call */ public boolean remove(Object o) { return removeFirstOccurrence(o); @@ -733,6 +795,7 @@ * @return the number of elements in this deque */ public int size() { + final ReentrantLock lock = this.lock; lock.lock(); try { return count; @@ -742,15 +805,16 @@ } /** - * Returns <tt>true</tt> if this deque contains the specified element. - * More formally, returns <tt>true</tt> if and only if this deque contains - * at least one element <tt>e</tt> such that <tt>o.equals(e)</tt>. + * Returns {@code true} if this deque contains the specified element. + * More formally, returns {@code true} if and only if this deque contains + * at least one element {@code e} such that {@code o.equals(e)}. * * @param o object to be checked for containment in this deque - * @return <tt>true</tt> if this deque contains the specified element + * @return {@code true} if this deque contains the specified element */ public boolean contains(Object o) { if (o == null) return false; + final ReentrantLock lock = this.lock; lock.lock(); try { for (Node<E> p = first; p != null; p = p.next) @@ -762,24 +826,46 @@ } } - /** - * Variant of removeFirstOccurrence needed by iterator.remove. - * Searches for the node, not its contents. + /* + * TODO: Add support for more efficient bulk operations. + * + * We don't want to acquire the lock for every iteration, but we + * also want other threads a chance to interact with the + * collection, especially when count is close to capacity. */ - boolean removeNode(Node<E> e) { - lock.lock(); - try { - for (Node<E> p = first; p != null; p = p.next) { - if (p == e) { - unlink(p); - return true; - } - } - return false; - } finally { - lock.unlock(); - } - } + +// /** +// * Adds all of the elements in the specified collection to this +// * queue. Attempts to addAll of a queue to itself result in +// * {@code IllegalArgumentException}. Further, the behavior of +// * this operation is undefined if the specified collection is +// * modified while the operation is in progress. +// * +// * @param c collection containing elements to be added to this queue +// * @return {@code true} if this queue changed as a result of the call +// * @throws ClassCastException {@inheritDoc} +// * @throws NullPointerException {@inheritDoc} +// * @throws IllegalArgumentException {@inheritDoc} +// * @throws IllegalStateException {@inheritDoc} +// * @see #add(Object) +// */ +// public boolean addAll(Collection<? extends E> c) { +// if (c == null) +// throw new NullPointerException(); +// if (c == this) +// throw new IllegalArgumentException(); +// final ReentrantLock lock = this.lock; +// lock.lock(); +// try { +// boolean modified = false; +// for (E e : c) +// if (linkLast(e)) +// modified = true; +// return modified; +// } finally { +// lock.unlock(); +// } +// } /** * Returns an array containing all of the elements in this deque, in @@ -794,7 +880,9 @@ * * @return an array containing all of the elements in this deque */ + @SuppressWarnings("unchecked") public Object[] toArray() { + final ReentrantLock lock = this.lock; lock.lock(); try { Object[] a = new Object[count]; @@ -817,22 +905,22 @@ * <p>If this deque fits in the specified array with room to spare * (i.e., the array has more elements than this deque), the element in * the array immediately following the end of the deque is set to - * <tt>null</tt>. + * {@code null}. * * <p>Like the {@link #toArray()} method, this method acts as bridge between * array-based and collection-based APIs. Further, this method allows * precise control over the runtime type of the output array, and may, * under certain circumstances, be used to save allocation costs. * - * <p>Suppose <tt>x</tt> is a deque known to contain only strings. + * <p>Suppose {@code x} is a deque known to contain only strings. * The following code can be used to dump the deque into a newly - * allocated array of <tt>String</tt>: + * allocated array of {@code String}: * * <pre> * String[] y = x.toArray(new String[0]);</pre> * - * Note that <tt>toArray(new Object[0])</tt> is identical in function to - * <tt>toArray()</tt>. + * Note that {@code toArray(new Object[0])} is identical in function to + * {@code toArray()}. * * @param a the array into which the elements of the deque are to * be stored, if it is big enough; otherwise, a new array of the @@ -843,14 +931,14 @@ * this deque * @throws NullPointerException if the specified array is null */ + @SuppressWarnings("unchecked") public <T> T[] toArray(T[] a) { + final ReentrantLock lock = this.lock; lock.lock(); try { if (a.length < count) - a = (T[])java.lang.reflect.Array.newInstance( - a.getClass().getComponentType(), - count - ); + a = (T[])java.lang.reflect.Array.newInstance + (a.getClass().getComponentType(), count); int k = 0; for (Node<E> p = first; p != null; p = p.next) @@ -864,6 +952,7 @@ } public String toString() { + final ReentrantLock lock = this.lock; lock.lock(); try { return super.toString(); @@ -877,8 +966,16 @@ * The deque will be empty after this call returns. */ public void clear() { + final ReentrantLock lock = this.lock; lock.lock(); try { + for (Node<E> f = first; f != null; ) { + f.item = null; + Node<E> n = f.next; + f.prev = null; + f.next = null; + f = n; + } first = last = null; count = 0; notFull.signalAll(); @@ -890,8 +987,9 @@ /** * Returns an iterator over the elements in this deque in proper sequence. * The elements will be returned in order from first (head) to last (tail). - * The returned <tt>Iterator</tt> is a "weakly consistent" iterator that - * will never throw {@link ConcurrentModificationException}, + * The returned {@code Iterator} is a "weakly consistent" iterator that + * will never throw {@link java.util.ConcurrentModificationException + * ConcurrentModificationException}, * and guarantees to traverse elements as they existed upon * construction of the iterator, and may (but is not guaranteed to) * reflect any modifications subsequent to construction. @@ -906,8 +1004,9 @@ * Returns an iterator over the elements in this deque in reverse * sequential order. The elements will be returned in order from * last (tail) to first (head). - * The returned <tt>Iterator</tt> is a "weakly consistent" iterator that - * will never throw {@link ConcurrentModificationException}, + * The returned {@code Iterator} is a "weakly consistent" iterator that + * will never throw {@link java.util.ConcurrentModificationException + * ConcurrentModificationException}, * and guarantees to traverse elements as they existed upon * construction of the iterator, and may (but is not guaranteed to) * reflect any modifications subsequent to construction. @@ -921,7 +1020,7 @@ */ private abstract class AbstractItr implements Iterator<E> { /** - * The next node to return in next + * The next node to return in next() */ Node<E> next; @@ -939,15 +1038,44 @@ */ private Node<E> lastRet; + abstract Node<E> firstNode(); + abstract Node<E> nextNode(Node<E> n); + AbstractItr() { - advance(); // set to initial position + // set to initial position + final ReentrantLock lock = LinkedBlockingDeque.this.lock; + lock.lock(); + try { + next = firstNode(); + nextItem = (next == null) ? null : next.item; + } finally { + lock.unlock(); + } } /** - * Advances next, or if not yet initialized, sets to first node. - * Implemented to move forward vs backward in the two subclasses. + * Advances next. */ - abstract void advance(); + void advance() { + final ReentrantLock lock = LinkedBlockingDeque.this.lock; + lock.lock(); + try { + // assert next != null; + Node<E> s = nextNode(next); + if (s == next) { + next = firstNode(); + } else { + // Skip over removed nodes. + // May be necessary if multiple interior Nodes are removed. + while (s != null && s.item == null) + s = nextNode(s); + next = s; + } + nextItem = (next == null) ? null : next.item; + } finally { + lock.unlock(); + } + } public boolean hasNext() { return next != null; @@ -967,52 +1095,39 @@ if (n == null) throw new IllegalStateException(); lastRet = null; - // Note: removeNode rescans looking for this node to make - // sure it was not already removed. Otherwise, trying to - // re-remove could corrupt list. - removeNode(n); - } - } - - /** Forward iterator */ - private class Itr extends AbstractItr { - void advance() { final ReentrantLock lock = LinkedBlockingDeque.this.lock; lock.lock(); try { - next = (next == null)? first : next.next; - nextItem = (next == null)? null : next.item; + if (n.item != null) + unlink(n); } finally { lock.unlock(); } } } - /** - * Descending iterator for LinkedBlockingDeque - */ + /** Forward iterator */ + private class Itr extends AbstractItr { + Node<E> firstNode() { return first; } + Node<E> nextNode(Node<E> n) { return n.next; } + } + + /** Descending iterator */ private class DescendingItr extends AbstractItr { - void advance() { - final ReentrantLock lock = LinkedBlockingDeque.this.lock; - lock.lock(); - try { - next = (next == null)? last : next.prev; - nextItem = (next == null)? null : next.item; - } finally { - lock.unlock(); - } - } + Node<E> firstNode() { return last; } + Node<E> nextNode(Node<E> n) { return n.prev; } } /** * Save the state of this deque to a stream (that is, serialize it). * * @serialData The capacity (int), followed by elements (each an - * <tt>Object</tt>) in the proper order, followed by a null + * {@code Object}) in the proper order, followed by a null * @param s the stream */ private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException { + final ReentrantLock lock = this.lock; lock.lock(); try { // Write out capacity and any hidden stuff @@ -1040,6 +1155,7 @@ last = null; // Read in all elements and place in queue for (;;) { + @SuppressWarnings("unchecked") E item = (E)s.readObject(); if (item == null) break;
--- a/jdk/src/share/classes/java/util/concurrent/LinkedBlockingQueue.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/java/util/concurrent/LinkedBlockingQueue.java Wed Jul 05 16:59:08 2017 +0200 @@ -34,9 +34,14 @@ */ package java.util.concurrent; -import java.util.concurrent.atomic.*; -import java.util.concurrent.locks.*; -import java.util.*; + +import java.util.concurrent.atomic.AtomicInteger; +import java.util.concurrent.locks.Condition; +import java.util.concurrent.locks.ReentrantLock; +import java.util.AbstractQueue; +import java.util.Collection; +import java.util.Iterator; +import java.util.NoSuchElementException; /** * An optionally-bounded {@linkplain BlockingQueue blocking queue} based on @@ -86,15 +91,43 @@ * items have been entered since the signal. And symmetrically for * takes signalling puts. Operations such as remove(Object) and * iterators acquire both locks. + * + * Visibility between writers and readers is provided as follows: + * + * Whenever an element is enqueued, the putLock is acquired and + * count updated. A subsequent reader guarantees visibility to the + * enqueued Node by either acquiring the putLock (via fullyLock) + * or by acquiring the takeLock, and then reading n = count.get(); + * this gives visibility to the first n items. + * + * To implement weakly consistent iterators, it appears we need to + * keep all Nodes GC-reachable from a predecessor dequeued Node. + * That would cause two problems: + * - allow a rogue Iterator to cause unbounded memory retention + * - cause cross-generational linking of old Nodes to new Nodes if + * a Node was tenured while live, which generational GCs have a + * hard time dealing with, causing repeated major collections. + * However, only non-deleted Nodes need to be reachable from + * dequeued Nodes, and reachability does not necessarily have to + * be of the kind understood by the GC. We use the trick of + * linking a Node that has just been dequeued to itself. Such a + * self-link implicitly means to advance to head.next. */ /** * Linked list node class */ static class Node<E> { - /** The item, volatile to ensure barrier separating write and read */ - volatile E item; + E item; + + /** + * One of: + * - the real successor Node + * - this Node, meaning the successor is head.next + * - null, meaning there is no successor (this is the last node) + */ Node<E> next; + Node(E x) { item = x; } } @@ -104,10 +137,16 @@ /** Current number of elements */ private final AtomicInteger count = new AtomicInteger(0); - /** Head of linked list */ + /** + * Head of linked list. + * Invariant: head.item == null + */ private transient Node<E> head; - /** Tail of linked list */ + /** + * Tail of linked list. + * Invariant: last.next == null + */ private transient Node<E> last; /** Lock held by take, poll, etc */ @@ -151,18 +190,26 @@ /** * Creates a node and links it at end of queue. + * * @param x the item */ - private void insert(E x) { + private void enqueue(E x) { + // assert putLock.isHeldByCurrentThread(); + // assert last.next == null; last = last.next = new Node<E>(x); } /** - * Removes a node from head of queue, + * Removes a node from head of queue. + * * @return the node */ - private E extract() { - Node<E> first = head.next; + private E dequeue() { + // assert takeLock.isHeldByCurrentThread(); + // assert head.item == null; + Node<E> h = head; + Node<E> first = h.next; + h.next = h; // help GC head = first; E x = first.item; first.item = null; @@ -172,7 +219,7 @@ /** * Lock to prevent both puts and takes. */ - private void fullyLock() { + void fullyLock() { putLock.lock(); takeLock.lock(); } @@ -180,14 +227,21 @@ /** * Unlock to allow both puts and takes. */ - private void fullyUnlock() { + void fullyUnlock() { takeLock.unlock(); putLock.unlock(); } +// /** +// * Tells whether both locks are held by current thread. +// */ +// boolean isFullyLocked() { +// return (putLock.isHeldByCurrentThread() && +// takeLock.isHeldByCurrentThread()); +// } /** - * Creates a <tt>LinkedBlockingQueue</tt> with a capacity of + * Creates a {@code LinkedBlockingQueue} with a capacity of * {@link Integer#MAX_VALUE}. */ public LinkedBlockingQueue() { @@ -195,10 +249,10 @@ } /** - * Creates a <tt>LinkedBlockingQueue</tt> with the given (fixed) capacity. + * Creates a {@code LinkedBlockingQueue} with the given (fixed) capacity. * * @param capacity the capacity of this queue - * @throws IllegalArgumentException if <tt>capacity</tt> is not greater + * @throws IllegalArgumentException if {@code capacity} is not greater * than zero */ public LinkedBlockingQueue(int capacity) { @@ -208,7 +262,7 @@ } /** - * Creates a <tt>LinkedBlockingQueue</tt> with a capacity of + * Creates a {@code LinkedBlockingQueue} with a capacity of * {@link Integer#MAX_VALUE}, initially containing the elements of the * given collection, * added in traversal order of the collection's iterator. @@ -219,8 +273,22 @@ */ public LinkedBlockingQueue(Collection<? extends E> c) { this(Integer.MAX_VALUE); - for (E e : c) - add(e); + final ReentrantLock putLock = this.putLock; + putLock.lock(); // Never contended, but necessary for visibility + try { + int n = 0; + for (E e : c) { + if (e == null) + throw new NullPointerException(); + if (n == capacity) + throw new IllegalStateException("Queue full"); + enqueue(e); + ++n; + } + count.set(n); + } finally { + putLock.unlock(); + } } @@ -241,10 +309,10 @@ * Returns the number of additional elements that this queue can ideally * (in the absence of memory or resource constraints) accept without * blocking. This is always equal to the initial capacity of this queue - * less the current <tt>size</tt> of this queue. + * less the current {@code size} of this queue. * * <p>Note that you <em>cannot</em> always tell if an attempt to insert - * an element will succeed by inspecting <tt>remainingCapacity</tt> + * an element will succeed by inspecting {@code remainingCapacity} * because it may be the case that another thread is about to * insert or remove an element. */ @@ -261,8 +329,8 @@ */ public void put(E e) throws InterruptedException { if (e == null) throw new NullPointerException(); - // Note: convention in all put/take/etc is to preset - // local var holding count negative to indicate failure unless set. + // Note: convention in all put/take/etc is to preset local var + // holding count negative to indicate failure unless set. int c = -1; final ReentrantLock putLock = this.putLock; final AtomicInteger count = this.count; @@ -273,18 +341,13 @@ * not protected by lock. This works because count can * only decrease at this point (all other puts are shut * out by lock), and we (or some other waiting put) are - * signalled if it ever changes from - * capacity. Similarly for all other uses of count in - * other wait guards. + * signalled if it ever changes from capacity. Similarly + * for all other uses of count in other wait guards. */ - try { - while (count.get() == capacity) - notFull.await(); - } catch (InterruptedException ie) { - notFull.signal(); // propagate to a non-interrupted thread - throw ie; + while (count.get() == capacity) { + notFull.await(); } - insert(e); + enqueue(e); c = count.getAndIncrement(); if (c + 1 < capacity) notFull.signal(); @@ -299,7 +362,7 @@ * Inserts the specified element at the tail of this queue, waiting if * necessary up to the specified wait time for space to become available. * - * @return <tt>true</tt> if successful, or <tt>false</tt> if + * @return {@code true} if successful, or {@code false} if * the specified waiting time elapses before space is available. * @throws InterruptedException {@inheritDoc} * @throws NullPointerException {@inheritDoc} @@ -314,23 +377,15 @@ final AtomicInteger count = this.count; putLock.lockInterruptibly(); try { - for (;;) { - if (count.get() < capacity) { - insert(e); - c = count.getAndIncrement(); - if (c + 1 < capacity) - notFull.signal(); - break; - } + while (count.get() == capacity) { if (nanos <= 0) return false; - try { - nanos = notFull.awaitNanos(nanos); - } catch (InterruptedException ie) { - notFull.signal(); // propagate to a non-interrupted thread - throw ie; - } + nanos = notFull.awaitNanos(nanos); } + enqueue(e); + c = count.getAndIncrement(); + if (c + 1 < capacity) + notFull.signal(); } finally { putLock.unlock(); } @@ -342,7 +397,7 @@ /** * Inserts the specified element at the tail of this queue if it is * possible to do so immediately without exceeding the queue's capacity, - * returning <tt>true</tt> upon success and <tt>false</tt> if this queue + * returning {@code true} upon success and {@code false} if this queue * is full. * When using a capacity-restricted queue, this method is generally * preferable to method {@link BlockingQueue#add add}, which can fail to @@ -360,7 +415,7 @@ putLock.lock(); try { if (count.get() < capacity) { - insert(e); + enqueue(e); c = count.getAndIncrement(); if (c + 1 < capacity) notFull.signal(); @@ -381,15 +436,10 @@ final ReentrantLock takeLock = this.takeLock; takeLock.lockInterruptibly(); try { - try { - while (count.get() == 0) - notEmpty.await(); - } catch (InterruptedException ie) { - notEmpty.signal(); // propagate to a non-interrupted thread - throw ie; + while (count.get() == 0) { + notEmpty.await(); } - - x = extract(); + x = dequeue(); c = count.getAndDecrement(); if (c > 1) notEmpty.signal(); @@ -409,23 +459,15 @@ final ReentrantLock takeLock = this.takeLock; takeLock.lockInterruptibly(); try { - for (;;) { - if (count.get() > 0) { - x = extract(); - c = count.getAndDecrement(); - if (c > 1) - notEmpty.signal(); - break; - } + while (count.get() == 0) { if (nanos <= 0) return null; - try { - nanos = notEmpty.awaitNanos(nanos); - } catch (InterruptedException ie) { - notEmpty.signal(); // propagate to a non-interrupted thread - throw ie; - } + nanos = notEmpty.awaitNanos(nanos); } + x = dequeue(); + c = count.getAndDecrement(); + if (c > 1) + notEmpty.signal(); } finally { takeLock.unlock(); } @@ -444,7 +486,7 @@ takeLock.lock(); try { if (count.get() > 0) { - x = extract(); + x = dequeue(); c = count.getAndDecrement(); if (c > 1) notEmpty.signal(); @@ -457,7 +499,6 @@ return x; } - public E peek() { if (count.get() == 0) return null; @@ -475,43 +516,47 @@ } /** + * Unlinks interior Node p with predecessor trail. + */ + void unlink(Node<E> p, Node<E> trail) { + // assert isFullyLocked(); + // p.next is not changed, to allow iterators that are + // traversing p to maintain their weak-consistency guarantee. + p.item = null; + trail.next = p.next; + if (last == p) + last = trail; + if (count.getAndDecrement() == capacity) + notFull.signal(); + } + + /** * Removes a single instance of the specified element from this queue, - * if it is present. More formally, removes an element <tt>e</tt> such - * that <tt>o.equals(e)</tt>, if this queue contains one or more such + * if it is present. More formally, removes an element {@code e} such + * that {@code o.equals(e)}, if this queue contains one or more such * elements. - * Returns <tt>true</tt> if this queue contained the specified element + * Returns {@code true} if this queue contained the specified element * (or equivalently, if this queue changed as a result of the call). * * @param o element to be removed from this queue, if present - * @return <tt>true</tt> if this queue changed as a result of the call + * @return {@code true} if this queue changed as a result of the call */ public boolean remove(Object o) { if (o == null) return false; - boolean removed = false; fullyLock(); try { - Node<E> trail = head; - Node<E> p = head.next; - while (p != null) { + for (Node<E> trail = head, p = trail.next; + p != null; + trail = p, p = p.next) { if (o.equals(p.item)) { - removed = true; - break; + unlink(p, trail); + return true; } - trail = p; - p = p.next; } - if (removed) { - p.item = null; - trail.next = p.next; - if (last == p) - last = trail; - if (count.getAndDecrement() == capacity) - notFull.signalAll(); - } + return false; } finally { fullyUnlock(); } - return removed; } /** @@ -551,22 +596,22 @@ * <p>If this queue fits in the specified array with room to spare * (i.e., the array has more elements than this queue), the element in * the array immediately following the end of the queue is set to - * <tt>null</tt>. + * {@code null}. * * <p>Like the {@link #toArray()} method, this method acts as bridge between * array-based and collection-based APIs. Further, this method allows * precise control over the runtime type of the output array, and may, * under certain circumstances, be used to save allocation costs. * - * <p>Suppose <tt>x</tt> is a queue known to contain only strings. + * <p>Suppose {@code x} is a queue known to contain only strings. * The following code can be used to dump the queue into a newly - * allocated array of <tt>String</tt>: + * allocated array of {@code String}: * * <pre> * String[] y = x.toArray(new String[0]);</pre> * - * Note that <tt>toArray(new Object[0])</tt> is identical in function to - * <tt>toArray()</tt>. + * Note that {@code toArray(new Object[0])} is identical in function to + * {@code toArray()}. * * @param a the array into which the elements of the queue are to * be stored, if it is big enough; otherwise, a new array of the @@ -577,6 +622,7 @@ * this queue * @throws NullPointerException if the specified array is null */ + @SuppressWarnings("unchecked") public <T> T[] toArray(T[] a) { fullyLock(); try { @@ -586,7 +632,7 @@ (a.getClass().getComponentType(), size); int k = 0; - for (Node p = head.next; p != null; p = p.next) + for (Node<E> p = head.next; p != null; p = p.next) a[k++] = (T)p.item; if (a.length > k) a[k] = null; @@ -612,11 +658,14 @@ public void clear() { fullyLock(); try { - head.next = null; - assert head.item == null; - last = head; + for (Node<E> p, h = head; (p = h.next) != null; h = p) { + h.next = h; + p.item = null; + } + head = last; + // assert head.item == null && head.next == null; if (count.getAndSet(0) == capacity) - notFull.signalAll(); + notFull.signal(); } finally { fullyUnlock(); } @@ -629,30 +678,7 @@ * @throws IllegalArgumentException {@inheritDoc} */ public int drainTo(Collection<? super E> c) { - if (c == null) - throw new NullPointerException(); - if (c == this) - throw new IllegalArgumentException(); - Node<E> first; - fullyLock(); - try { - first = head.next; - head.next = null; - assert head.item == null; - last = head; - if (count.getAndSet(0) == capacity) - notFull.signalAll(); - } finally { - fullyUnlock(); - } - // Transfer the elements outside of locks - int n = 0; - for (Node<E> p = first; p != null; p = p.next) { - c.add(p.item); - p.item = null; - ++n; - } - return n; + return drainTo(c, Integer.MAX_VALUE); } /** @@ -666,34 +692,44 @@ throw new NullPointerException(); if (c == this) throw new IllegalArgumentException(); - fullyLock(); + boolean signalNotFull = false; + final ReentrantLock takeLock = this.takeLock; + takeLock.lock(); try { - int n = 0; - Node<E> p = head.next; - while (p != null && n < maxElements) { - c.add(p.item); - p.item = null; - p = p.next; - ++n; + int n = Math.min(maxElements, count.get()); + // count.get provides visibility to first n Nodes + Node<E> h = head; + int i = 0; + try { + while (i < n) { + Node<E> p = h.next; + c.add(p.item); + p.item = null; + h.next = h; + h = p; + ++i; + } + return n; + } finally { + // Restore invariants even if c.add() threw + if (i > 0) { + // assert h.item == null; + head = h; + signalNotFull = (count.getAndAdd(-i) == capacity); + } } - if (n != 0) { - head.next = p; - assert head.item == null; - if (p == null) - last = head; - if (count.getAndAdd(-n) == capacity) - notFull.signalAll(); - } - return n; } finally { - fullyUnlock(); + takeLock.unlock(); + if (signalNotFull) + signalNotFull(); } } /** * Returns an iterator over the elements in this queue in proper sequence. - * The returned <tt>Iterator</tt> is a "weakly consistent" iterator that - * will never throw {@link ConcurrentModificationException}, + * The returned {@code Iterator} is a "weakly consistent" iterator that + * will never throw {@link java.util.ConcurrentModificationException + * ConcurrentModificationException}, * and guarantees to traverse elements as they existed upon * construction of the iterator, and may (but is not guaranteed to) * reflect any modifications subsequent to construction. @@ -706,7 +742,7 @@ private class Itr implements Iterator<E> { /* - * Basic weak-consistent iterator. At all times hold the next + * Basic weakly-consistent iterator. At all times hold the next * item to hand out so that if hasNext() reports true, we will * still have it to return even if lost race with a take etc. */ @@ -715,17 +751,13 @@ private E currentElement; Itr() { - final ReentrantLock putLock = LinkedBlockingQueue.this.putLock; - final ReentrantLock takeLock = LinkedBlockingQueue.this.takeLock; - putLock.lock(); - takeLock.lock(); + fullyLock(); try { current = head.next; if (current != null) currentElement = current.item; } finally { - takeLock.unlock(); - putLock.unlock(); + fullyUnlock(); } } @@ -733,54 +765,54 @@ return current != null; } + /** + * Unlike other traversal methods, iterators need to handle: + * - dequeued nodes (p.next == p) + * - interior removed nodes (p.item == null) + */ + private Node<E> nextNode(Node<E> p) { + Node<E> s = p.next; + if (p == s) + return head.next; + // Skip over removed nodes. + // May be necessary if multiple interior Nodes are removed. + while (s != null && s.item == null) + s = s.next; + return s; + } + public E next() { - final ReentrantLock putLock = LinkedBlockingQueue.this.putLock; - final ReentrantLock takeLock = LinkedBlockingQueue.this.takeLock; - putLock.lock(); - takeLock.lock(); + fullyLock(); try { if (current == null) throw new NoSuchElementException(); E x = currentElement; lastRet = current; - current = current.next; - if (current != null) - currentElement = current.item; + current = nextNode(current); + currentElement = (current == null) ? null : current.item; return x; } finally { - takeLock.unlock(); - putLock.unlock(); + fullyUnlock(); } } public void remove() { if (lastRet == null) throw new IllegalStateException(); - final ReentrantLock putLock = LinkedBlockingQueue.this.putLock; - final ReentrantLock takeLock = LinkedBlockingQueue.this.takeLock; - putLock.lock(); - takeLock.lock(); + fullyLock(); try { Node<E> node = lastRet; lastRet = null; - Node<E> trail = head; - Node<E> p = head.next; - while (p != null && p != node) { - trail = p; - p = p.next; - } - if (p == node) { - p.item = null; - trail.next = p.next; - if (last == p) - last = trail; - int c = count.getAndDecrement(); - if (c == capacity) - notFull.signalAll(); + for (Node<E> trail = head, p = trail.next; + p != null; + trail = p, p = p.next) { + if (p == node) { + unlink(p, trail); + break; + } } } finally { - takeLock.unlock(); - putLock.unlock(); + fullyUnlock(); } } } @@ -789,7 +821,7 @@ * Save the state to a stream (that is, serialize it). * * @serialData The capacity is emitted (int), followed by all of - * its elements (each an <tt>Object</tt>) in the proper order, + * its elements (each an {@code Object}) in the proper order, * followed by a null * @param s the stream */ @@ -815,6 +847,7 @@ /** * Reconstitute this queue instance from a stream (that is, * deserialize it). + * * @param s the stream */ private void readObject(java.io.ObjectInputStream s) @@ -827,6 +860,7 @@ // Read in all elements and place in queue for (;;) { + @SuppressWarnings("unchecked") E item = (E)s.readObject(); if (item == null) break;
--- a/jdk/src/share/classes/javax/accessibility/AccessibleResourceBundle.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/javax/accessibility/AccessibleResourceBundle.java Wed Jul 05 16:59:08 2017 +0200 @@ -44,15 +44,11 @@ * localized display strings. */ public Object[][] getContents() { - return contents; - } + // The table holding the mapping between the programmatic keys + // and the display strings for the en_US locale. + return new Object[][] { - /** - * The table holding the mapping between the programmatic keys - * and the display strings for the en_US locale. - */ - static final Object[][] contents = { - // LOCALIZE THIS + // LOCALIZE THIS // Role names // { "application","application" }, // { "border","border" }, @@ -151,5 +147,6 @@ { "vertical","vertical" }, { "horizontal","horizontal" } // END OF MATERIAL TO LOCALIZE - }; + }; + } }
--- a/jdk/src/share/classes/javax/imageio/plugins/bmp/BMPImageWriteParam.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/javax/imageio/plugins/bmp/BMPImageWriteParam.java Wed Jul 05 16:59:08 2017 +0200 @@ -78,7 +78,7 @@ super(locale); // Set compression types ("BI_RGB" denotes uncompressed). - compressionTypes = BMPConstants.compressionTypeNames; + compressionTypes = BMPConstants.compressionTypeNames.clone(); // Set compression flag. canWriteCompressed = true;
--- a/jdk/src/share/classes/javax/imageio/spi/ImageReaderSpi.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/javax/imageio/spi/ImageReaderSpi.java Wed Jul 05 16:59:08 2017 +0200 @@ -77,7 +77,10 @@ * A single-element array, initially containing * <code>ImageInputStream.class</code>, to be returned from * <code>getInputTypes</code>. + * @deprecated Instead of using this field, directly create + * the equivalent array <code>{ ImageInputStream.class }<code>. */ + @Deprecated public static final Class[] STANDARD_INPUT_TYPE = { ImageInputStream.class }; @@ -227,7 +230,11 @@ throw new IllegalArgumentException ("inputTypes.length == 0!"); } - this.inputTypes = (Class[])inputTypes.clone(); + + this.inputTypes = (inputTypes == STANDARD_INPUT_TYPE) ? + new Class<?>[] { ImageInputStream.class } : + inputTypes.clone(); + // If length == 0, leave it null if (writerSpiNames != null && writerSpiNames.length > 0) { this.writerSpiNames = (String[])writerSpiNames.clone();
--- a/jdk/src/share/classes/javax/imageio/spi/ImageWriterSpi.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/javax/imageio/spi/ImageWriterSpi.java Wed Jul 05 16:59:08 2017 +0200 @@ -77,9 +77,12 @@ /** * A single-element array, initially containing - * <code>ImageInputStream.class</code>, to be returned from - * <code>getInputTypes</code>. + * <code>ImageOutputStream.class</code>, to be returned from + * <code>getOutputTypes</code>. + * @deprecated Instead of using this field, directly create + * the equivalent array <code>{ ImageOutputStream.class }<code>. */ + @Deprecated public static final Class[] STANDARD_OUTPUT_TYPE = { ImageOutputStream.class }; @@ -228,7 +231,11 @@ throw new IllegalArgumentException ("outputTypes.length == 0!"); } - this.outputTypes = (Class[])outputTypes.clone(); + + this.outputTypes = (outputTypes == STANDARD_OUTPUT_TYPE) ? + new Class<?>[] { ImageOutputStream.class } : + outputTypes.clone(); + // If length == 0, leave it null if (readerSpiNames != null && readerSpiNames.length > 0) { this.readerSpiNames = (String[])readerSpiNames.clone();
--- a/jdk/src/share/classes/javax/imageio/stream/FileCacheImageInputStream.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/javax/imageio/stream/FileCacheImageInputStream.java Wed Jul 05 16:59:08 2017 +0200 @@ -62,6 +62,10 @@ /** The DisposerRecord that closes the underlying cache. */ private final DisposerRecord disposerRecord; + /** The CloseAction that closes the stream in + * the StreamCloser's shutdown hook */ + private final StreamCloser.CloseAction closeAction; + /** * Constructs a <code>FileCacheImageInputStream</code> that will read * from a given <code>InputStream</code>. @@ -96,7 +100,9 @@ this.cacheFile = File.createTempFile("imageio", ".tmp", cacheDir); this.cache = new RandomAccessFile(cacheFile, "rw"); - StreamCloser.addToQueue(this); + + this.closeAction = StreamCloser.createCloseAction(this); + StreamCloser.addToQueue(closeAction); disposerRecord = new StreamDisposerRecord(cacheFile, cache); if (getClass() == FileCacheImageInputStream.class) { @@ -242,7 +248,7 @@ stream = null; cache = null; cacheFile = null; - StreamCloser.removeFromQueue(this); + StreamCloser.removeFromQueue(closeAction); } /**
--- a/jdk/src/share/classes/javax/imageio/stream/FileCacheImageOutputStream.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/javax/imageio/stream/FileCacheImageOutputStream.java Wed Jul 05 16:59:08 2017 +0200 @@ -48,6 +48,10 @@ // Pos after last (rightmost) byte written private long maxStreamPos = 0L; + /** The CloseAction that closes the stream in + * the StreamCloser's shutdown hook */ + private final StreamCloser.CloseAction closeAction; + /** * Constructs a <code>FileCacheImageOutputStream</code> that will write * to a given <code>outputStream</code>. @@ -82,7 +86,9 @@ this.cacheFile = File.createTempFile("imageio", ".tmp", cacheDir); this.cache = new RandomAccessFile(cacheFile, "rw"); - StreamCloser.addToQueue(this); + + this.closeAction = StreamCloser.createCloseAction(this); + StreamCloser.addToQueue(closeAction); } public int read() throws IOException { @@ -227,7 +233,7 @@ cacheFile = null; stream.flush(); stream = null; - StreamCloser.removeFromQueue(this); + StreamCloser.removeFromQueue(closeAction); } public void flushBefore(long pos) throws IOException {
--- a/jdk/src/share/classes/javax/management/openmbean/OpenMBeanAttributeInfoSupport.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/javax/management/openmbean/OpenMBeanAttributeInfoSupport.java Wed Jul 05 16:59:08 2017 +0200 @@ -690,7 +690,7 @@ private static <T> T convertFromString(String s, OpenType<T> openType) { Class<T> c; try { - c = cast(Class.forName(openType.getClassName())); + c = cast(Class.forName(openType.safeGetClassName())); } catch (ClassNotFoundException e) { throw new NoClassDefFoundError(e.toString()); // can't happen } @@ -711,7 +711,7 @@ } catch (Exception e) { final String msg = "Could not convert \"" + s + "\" using method: " + valueOf; - throw new IllegalArgumentException(msg); + throw new IllegalArgumentException(msg, e); } } @@ -728,7 +728,7 @@ } catch (Exception e) { final String msg = "Could not convert \"" + s + "\" using constructor: " + con; - throw new IllegalArgumentException(msg); + throw new IllegalArgumentException(msg, e); } } @@ -757,7 +757,7 @@ stringArrayClass = Class.forName(squareBrackets + "Ljava.lang.String;"); targetArrayClass = - Class.forName(squareBrackets + "L" + baseType.getClassName() + + Class.forName(squareBrackets + "L" + baseType.safeGetClassName() + ";"); } catch (ClassNotFoundException e) { throw new NoClassDefFoundError(e.toString()); // can't happen
--- a/jdk/src/share/classes/javax/management/openmbean/OpenType.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/javax/management/openmbean/OpenType.java Wed Jul 05 16:59:08 2017 +0200 @@ -304,7 +304,12 @@ * @return the class name. */ public String getClassName() { + return className; + } + // A version of getClassName() that can only be called from within this + // package and that cannot be overridden. + String safeGetClassName() { return className; }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/jdk/src/share/classes/javax/swing/JLayer.java Wed Jul 05 16:59:08 2017 +0200 @@ -0,0 +1,788 @@ +/* + * Copyright 2009 Sun Microsystems, Inc. All rights reserved. + * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. + */ + +package javax.swing; + +import javax.swing.plaf.LayerUI; +import java.awt.*; +import java.awt.event.*; +import java.beans.PropertyChangeEvent; +import java.beans.PropertyChangeListener; +import java.io.IOException; +import java.io.ObjectInputStream; +import java.io.Serializable; +import java.lang.ref.WeakReference; +import java.util.ArrayList; +import java.util.Iterator; +import java.security.AccessController; +import java.security.PrivilegedAction; + +/** + * {@code JLayer} is a universal decorator for Swing components + * which enables you to implement various advanced painting effects as well as + * receive notifications of all {@code AWTEvent}s generated within its borders. + * <p/> + * {@code JLayer} delegates the handling of painting and input events to a + * {@link javax.swing.plaf.LayerUI} object, which performs the actual decoration. + * <p/> + * The custom painting implemented in the {@code LayerUI} and events notification + * work for the JLayer itself and all its subcomponents. + * This combination enables you to enrich existing components + * by adding new advanced functionality such as temporary locking of a hierarchy, + * data tips for compound components, enhanced mouse scrolling etc and so on. + * <p/> + * {@code JLayer} is a good solution if you only need to do custom painting + * over compound component or catch input events from its subcomponents. + * <pre> + * // create a component to be decorated with the layer + * JPanel panel = new JPanel(); + * panel.add(new JButton("JButton")); + * // This custom layerUI will fill the layer with translucent green + * // and print out all mouseMotion events generated within its borders + * LayerUI<JPanel> layerUI = new LayerUI<JPanel>() { + * public void paint(Graphics g, JCompo nent c) { + * // paint the layer as is + * super.paint(g, c); + * // fill it with the translucent green + * g.setColor(new Color(0, 128, 0, 128)); + * g.fillRect(0, 0, c.getWidth(), c.getHeight()); + * } + * // overridden method which catches MouseMotion events + * public void eventDispatched(AWTEvent e, JLayer<JPanel> l) { + * System.out.println("AWTEvent detected: " + e); + * } + * }; + * // create the layer for the panel using our custom layerUI + * JLayer<JPanel> layer = new JLayer<JPanel>(panel, layerUI); + * // work with the layer as with any other Swing component + * frame.add(layer); + * </pre> + * + * <b>Note:</b> {@code JLayer} doesn't support the following methods: + * <ul> + * <li>{@link Container#add(java.awt.Component)}</li> + * <li>{@link Container#add(String, java.awt.Component)}</li> + * <li>{@link Container#add(java.awt.Component, int)}</li> + * <li>{@link Container#add(java.awt.Component, Object)}</li> + * <li>{@link Container#add(java.awt.Component, Object, int)}</li> + * </ul> + * using any of of them will cause {@code UnsupportedOperationException} to be thrown, + * to add a component to {@code JLayer} + * use {@link #setView(Component)} or {@link #setGlassPane(JPanel)}. + * + * @param <V> the type of {@code JLayer}'s view component + * + * @see #JLayer(Component) + * @see #setView(Component) + * @see #getView() + * @see javax.swing.plaf.LayerUI + * @see #JLayer(Component, LayerUI) + * @see #setUI(javax.swing.plaf.LayerUI) + * @see #getUI() + * @since 1.7 + * + * @author Alexander Potochkin + */ +public final class JLayer<V extends Component> + extends JComponent + implements Scrollable, PropertyChangeListener { + private V view; + // this field is necessary because JComponent.ui is transient + // when layerUI is serializable + private LayerUI<? super V> layerUI; + private JPanel glassPane; + private boolean isPainting; + private static final DefaultLayerLayout sharedLayoutInstance = + new DefaultLayerLayout(); + private long eventMask; + + private static final LayerEventController eventController = + new LayerEventController(); + + private static final long ACCEPTED_EVENTS = + AWTEvent.COMPONENT_EVENT_MASK | + AWTEvent.CONTAINER_EVENT_MASK | + AWTEvent.FOCUS_EVENT_MASK | + AWTEvent.KEY_EVENT_MASK | + AWTEvent.MOUSE_WHEEL_EVENT_MASK | + AWTEvent.MOUSE_MOTION_EVENT_MASK | + AWTEvent.MOUSE_EVENT_MASK | + AWTEvent.INPUT_METHOD_EVENT_MASK | + AWTEvent.HIERARCHY_EVENT_MASK | + AWTEvent.HIERARCHY_BOUNDS_EVENT_MASK; + + /** + * Creates a new {@code JLayer} object with a {@code null} view component + * and {@code null} {@link javax.swing.plaf.LayerUI}. + * + * @see #setView + * @see #setUI + */ + public JLayer() { + this(null); + } + + /** + * Creates a new {@code JLayer} object + * with {@code null} {@link javax.swing.plaf.LayerUI}. + * + * @param view the component to be decorated by this {@code JLayer} + * + * @see #setUI + */ + public JLayer(V view) { + this(view, null); + } + + /** + * Creates a new {@code JLayer} object with the specified view component + * and {@link javax.swing.plaf.LayerUI} object. + * + * @param view the component to be decorated + * @param ui the {@link javax.swing.plaf.LayerUI} delegate + * to be used by this {@code JLayer} + */ + public JLayer(V view, LayerUI<V> ui) { + setLayout(sharedLayoutInstance); + setGlassPane(createGlassPane()); + setView(view); + setUI(ui); + } + + /** + * Returns the {@code JLayer}'s view component or {@code null}. + * <br/>This is a bound property. + * + * @return the {@code JLayer}'s view component + * or {@code null} if none exists + * + * @see #setView(V) + */ + public V getView() { + return view; + } + + /** + * Sets the {@code JLayer}'s view component, which can be {@code null}. + * <br/>This is a bound property. + * + * @param view the view component for this {@code JLayer} + * + * @see #getView() + */ + public void setView(V view) { + Component oldView = getView(); + if (oldView != null) { + super.remove(oldView); + } + if (view != null) { + super.addImpl(view, null, getComponentCount()); + } + this.view = view; + firePropertyChange("view", oldView, view); + revalidate(); + repaint(); + } + + /** + * Sets the {@link javax.swing.plaf.LayerUI} which will perform painting + * and receive input events for this {@code JLayer}. + * + * @param ui the {@link javax.swing.plaf.LayerUI} for this {@code JLayer} + */ + public void setUI(LayerUI<? super V> ui) { + this.layerUI = ui; + super.setUI(ui); + } + + /** + * Returns the {@link javax.swing.plaf.LayerUI} for this {@code JLayer}. + * + * @return the {@code LayerUI} for this {@code JLayer} + */ + public LayerUI<? super V> getUI() { + return layerUI; + } + + /** + * Returns the {@code JLayer}'s glassPane component or {@code null}. + * <br/>This is a bound property. + * + * @return the {@code JLayer}'s glassPane component + * or {@code null} if none exists + * + * @see #setGlassPane(JPanel) + */ + public JPanel getGlassPane() { + return glassPane; + } + + /** + * Sets the {@code JLayer}'s glassPane component, which can be {@code null}. + * <br/>This is a bound property. + * + * @param glassPane the glassPane component of this {@code JLayer} + * + * @see #getGlassPane() + */ + public void setGlassPane(JPanel glassPane) { + Component oldGlassPane = getGlassPane(); + if (oldGlassPane != null) { + super.remove(oldGlassPane); + } + if (glassPane != null) { + super.addImpl(glassPane, null, 0); + } + this.glassPane = glassPane; + firePropertyChange("glassPane", oldGlassPane, glassPane); + revalidate(); + repaint(); + } + + /** + * Called by the constructor methods to create a default {@code glassPane}. + * By default this method creates a new JPanel with visibility set to true + * and opacity set to false. + * + * @return the default {@code glassPane} + */ + public JPanel createGlassPane() { + return new DefaultLayerGlassPane(); + } + + /** + * This method is not supported by {@code JLayer} + * and always throws {@code UnsupportedOperationException} + * + * @throws UnsupportedOperationException this method is not supported + * + * @see #setView(Component) + * @see #setGlassPane(Component) + */ + protected void addImpl(Component comp, Object constraints, int index) { + throw new UnsupportedOperationException( + "Adding components to JLayer is not supported, " + + "use setView() or setGlassPane() instead"); + } + + /** + * {@inheritDoc} + */ + public void remove(Component comp) { + if (comp == getView()) { + setView(null); + } else if (comp == getGlassPane()) { + setGlassPane(null); + } else { + super.remove(comp); + } + } + + /** + * {@inheritDoc} + */ + public void removeAll() { + setView(null); + setGlassPane(null); + } + + /** + * Delegates all painting to the {@link javax.swing.plaf.LayerUI} object. + * + * @param g the {@code Graphics} to render to + */ + public void paint(Graphics g) { + if (!isPainting) { + isPainting = true; + super.paintComponent(g); + isPainting = false; + } else { + super.paint(g); + } + } + + /** + * This method is empty, because all painting is done by + * {@link #paint(Graphics)} and + * {@link javax.swing.plaf.LayerUI#update(Graphics, JComponent)} methods + */ + protected void paintComponent(Graphics g) { + } + + /** + * To enable the correct painting of the {@code glassPane} and view component, + * the {@code JLayer} overrides the default implementation of + * this method to return {@code false} when the {@code glassPane} is visible. + * + * @return false if {@code JLayer}'s {@code glassPane} is visible + */ + public boolean isOptimizedDrawingEnabled() { + return !glassPane.isVisible(); + } + + /** + * {@inheritDoc} + */ + public void propertyChange(PropertyChangeEvent evt) { + if (getUI() != null) { + getUI().applyPropertyChange(evt, this); + } + } + + /** + * Sets the bitmask of event types to receive by this {@code JLayer}. + * Here is the list of the supported event types: + * <ul> + * <li>AWTEvent.COMPONENT_EVENT_MASK</li> + * <li>AWTEvent.CONTAINER_EVENT_MASK</li> + * <li>AWTEvent.FOCUS_EVENT_MASK</li> + * <li>AWTEvent.KEY_EVENT_MASK</li> + * <li>AWTEvent.MOUSE_WHEEL_EVENT_MASK</li> + * <li>AWTEvent.MOUSE_MOTION_EVENT_MASK</li> + * <li>AWTEvent.MOUSE_EVENT_MASK</li> + * <li>AWTEvent.INPUT_METHOD_EVENT_MASK</li> + * <li>AWTEvent.HIERARCHY_EVENT_MASK</li> + * <li>AWTEvent.HIERARCHY_BOUNDS_EVENT_MASK</li> + * </ul> + * <p/> + * If {@code LayerUI} is installed, + * {@link javax.swing.plaf.LayerUI#eventDispatched(AWTEvent, JLayer)} method + * will only receive events that match the event mask. + * <p/> + * The following example shows how to correclty use this method + * in the {@code LayerUI} implementations: + * <pre> + * public void installUI(JComponent c) { + * super.installUI(c); + * JLayer l = (JLayer) c; + * // this LayerUI will receive only key and focus events + * l.setLayerEventMask(AWTEvent.KEY_EVENT_MASK | AWTEvent.FOCUS_EVENT_MASK); + * } + * + * public void uninstallUI(JComponent c) { + * super.uninstallUI(c); + * JLayer l = (JLayer) c; + * // JLayer must be returned to its initial state + * l.setLayerEventMask(0); + * } + * </pre> + * + * By default {@code JLayer} receives no events. + * + * @param layerEventMask the bitmask of event types to receive + * + * @throws IllegalArgumentException if the {@code layerEventMask} parameter + * contains unsupported event types + * @see #getLayerEventMask() + */ + public void setLayerEventMask(long layerEventMask) { + if (layerEventMask != (layerEventMask & ACCEPTED_EVENTS)) { + throw new IllegalArgumentException( + "The event bitmask contains unsupported event types"); + } + long oldEventMask = getLayerEventMask(); + this.eventMask = layerEventMask; + firePropertyChange("layerEventMask", oldEventMask, layerEventMask); + if (layerEventMask != oldEventMask) { + disableEvents(oldEventMask); + enableEvents(eventMask); + eventController.updateAWTEventListener(this); + } + } + + /** + * Returns the bitmap of event mask to receive by this {@code JLayer} + * and its {@code LayerUI}. + * <p/> + * It means that {@link javax.swing.plaf.LayerUI#eventDispatched(AWTEvent, JLayer)} method + * will only receive events that match the event mask. + * <p/> + * By default {@code JLayer} receives no events. + * + * @return the bitmask of event types to receive for this {@code JLayer} + */ + public long getLayerEventMask() { + return eventMask; + } + + /** + * Delegates its functionality to the {@link javax.swing.plaf.LayerUI#updateUI(JLayer)} method, + * if {@code LayerUI} is set. + */ + public void updateUI() { + if (getUI() != null) { + getUI().updateUI(this); + } + } + + /** + * Returns the preferred size of the viewport for a view component. + * <p/> + * If the ui delegate of this layer is not {@code null}, this method delegates its + * implementation to the {@code LayerUI.getPreferredScrollableViewportSize(JLayer)} + * + * @return the preferred size of the viewport for a view component + * + * @see Scrollable + * @see LayerUI#getPreferredScrollableViewportSize(JLayer) + */ + public Dimension getPreferredScrollableViewportSize() { + if (getUI() != null) { + return getUI().getPreferredScrollableViewportSize(this); + } + return getPreferredSize(); + } + + /** + * Returns a scroll increment, which is required for components + * that display logical rows or columns in order to completely expose + * one block of rows or columns, depending on the value of orientation. + * <p/> + * If the ui delegate of this layer is not {@code null}, this method delegates its + * implementation to the {@code LayerUI.getScrollableBlockIncrement(JLayer,Rectangle,int,int)} + * + * @return the "block" increment for scrolling in the specified direction + * + * @see Scrollable + * @see LayerUI#getScrollableBlockIncrement(JLayer, Rectangle, int, int) + */ + public int getScrollableBlockIncrement(Rectangle visibleRect, + int orientation, int direction) { + if (getUI() != null) { + return getUI().getScrollableBlockIncrement(this, visibleRect, + orientation, direction); + } + return (orientation == SwingConstants.VERTICAL) ? visibleRect.height : + visibleRect.width; + } + + /** + * Returns {@code false} to indicate that the height of the viewport does not + * determine the height of the layer, unless the preferred height + * of the layer is smaller than the height of the viewport. + * <p/> + * If the ui delegate of this layer is not null, this method delegates its + * implementation to the {@code LayerUI.getScrollableTracksViewportHeight(JLayer)} + * + * @return whether the layer should track the height of the viewport + * + * @see Scrollable + * @see LayerUI#getScrollableTracksViewportHeight(JLayer) + */ + public boolean getScrollableTracksViewportHeight() { + if (getUI() != null) { + return getUI().getScrollableTracksViewportHeight(this); + } + if (getParent() instanceof JViewport) { + return ((getParent()).getHeight() > getPreferredSize().height); + } + return false; + } + + /** + * Returns {@code false} to indicate that the width of the viewport does not + * determine the width of the layer, unless the preferred width + * of the layer is smaller than the width of the viewport. + * <p/> + * If the ui delegate of this layer is not null, this method delegates its + * implementation to the {@code LayerUI.getScrollableTracksViewportWidth(JLayer)} + * + * @return whether the layer should track the width of the viewport + * + * @see Scrollable + * @see LayerUI#getScrollableTracksViewportWidth(JLayer) + */ + public boolean getScrollableTracksViewportWidth() { + if (getUI() != null) { + return getUI().getScrollableTracksViewportWidth(this); + } + if (getParent() instanceof JViewport) { + return ((getParent()).getWidth() > getPreferredSize().width); + } + return false; + } + + /** + * Returns a scroll increment, which is required for components + * that display logical rows or columns in order to completely expose + * one new row or column, depending on the value of orientation. + * Ideally, components should handle a partially exposed row or column + * by returning the distance required to completely expose the item. + * <p/> + * Scrolling containers, like {@code JScrollPane}, will use this method + * each time the user requests a unit scroll. + * <p/> + * If the ui delegate of this layer is not {@code null}, this method delegates its + * implementation to the {@code LayerUI.getScrollableUnitIncrement(JLayer,Rectangle,int,int)} + * + * @return The "unit" increment for scrolling in the specified direction. + * This value should always be positive. + * + * @see Scrollable + * @see LayerUI#getScrollableUnitIncrement(JLayer, Rectangle, int, int) + */ + public int getScrollableUnitIncrement(Rectangle visibleRect, int orientation, + int direction) { + if (getUI() != null) { + return getUI().getScrollableUnitIncrement( + this, visibleRect, orientation, direction); + } + return 1; + } + + private void readObject(ObjectInputStream s) + throws IOException, ClassNotFoundException { + s.defaultReadObject(); + if (getUI() != null) { + setUI(getUI()); + } + if (getLayerEventMask() != 0) { + eventController.updateAWTEventListener(this); + } + } + + /** + * static AWTEventListener to be shared with all AbstractLayerUIs + */ + private static class LayerEventController implements AWTEventListener { + private ArrayList<WeakReference<JLayer>> layerList = + new ArrayList<WeakReference<JLayer>>(); + + private long currentEventMask; + + @SuppressWarnings("unchecked") + public void eventDispatched(AWTEvent event) { + Object source = event.getSource(); + if (source instanceof Component) { + Component component = (Component) source; + while (component != null) { + if (component instanceof JLayer) { + JLayer l = (JLayer) component; + LayerUI ui = l.getUI(); + if (ui != null && + isEventEnabled(l.getLayerEventMask(), + event.getID())) { + ui.eventDispatched(event, l); + } + } + component = component.getParent(); + } + } + } + + private boolean layerListContains(JLayer l) { + for (WeakReference<JLayer> layerWeakReference : layerList) { + if (layerWeakReference.get() == l) { + return true; + } + } + return false; + } + + private void updateAWTEventListener(JLayer layer) { + if (!layerListContains(layer) && layer.getLayerEventMask() != 0) { + layerList.add(new WeakReference<JLayer>(layer)); + } + long combinedMask = 0; + Iterator<WeakReference<JLayer>> it = layerList.iterator(); + while (it.hasNext()) { + WeakReference<JLayer> weakRef = it.next(); + JLayer currLayer = weakRef.get(); + if (currLayer == null) { + it.remove(); + } else { + combinedMask |= currLayer.getLayerEventMask(); + } + } + if (combinedMask == 0) { + removeAWTEventListener(); + layerList.clear(); + } else if (getCurrentEventMask() != combinedMask) { + removeAWTEventListener(); + addAWTEventListener(combinedMask); + } + } + + private long getCurrentEventMask() { + return currentEventMask; + } + + private void addAWTEventListener(final long eventMask) { + AccessController.doPrivileged(new PrivilegedAction<Void>() { + public Void run() { + Toolkit.getDefaultToolkit(). + addAWTEventListener(LayerEventController.this, eventMask); + return null; + } + }); + currentEventMask = eventMask; + } + + private void removeAWTEventListener() { + AccessController.doPrivileged(new PrivilegedAction<Void>() { + public Void run() { + Toolkit.getDefaultToolkit(). + removeAWTEventListener(LayerEventController.this); + return null; + } + }); + currentEventMask = 0; + } + + private boolean isEventEnabled(long eventMask, int id) { + return (((eventMask & AWTEvent.COMPONENT_EVENT_MASK) != 0 && + id >= ComponentEvent.COMPONENT_FIRST && + id <= ComponentEvent.COMPONENT_LAST) + || ((eventMask & AWTEvent.CONTAINER_EVENT_MASK) != 0 && + id >= ContainerEvent.CONTAINER_FIRST && + id <= ContainerEvent.CONTAINER_LAST) + || ((eventMask & AWTEvent.FOCUS_EVENT_MASK) != 0 && + id >= FocusEvent.FOCUS_FIRST && + id <= FocusEvent.FOCUS_LAST) + || ((eventMask & AWTEvent.KEY_EVENT_MASK) != 0 && + id >= KeyEvent.KEY_FIRST && + id <= KeyEvent.KEY_LAST) + || ((eventMask & AWTEvent.MOUSE_WHEEL_EVENT_MASK) != 0 && + id == MouseEvent.MOUSE_WHEEL) + || ((eventMask & AWTEvent.MOUSE_MOTION_EVENT_MASK) != 0 && + (id == MouseEvent.MOUSE_MOVED || + id == MouseEvent.MOUSE_DRAGGED)) + || ((eventMask & AWTEvent.MOUSE_EVENT_MASK) != 0 && + id != MouseEvent.MOUSE_MOVED && + id != MouseEvent.MOUSE_DRAGGED && + id != MouseEvent.MOUSE_WHEEL && + id >= MouseEvent.MOUSE_FIRST && + id <= MouseEvent.MOUSE_LAST) + || ((eventMask & AWTEvent.INPUT_METHOD_EVENT_MASK) != 0 && + id >= InputMethodEvent.INPUT_METHOD_FIRST && + id <= InputMethodEvent.INPUT_METHOD_LAST) + || ((eventMask & AWTEvent.HIERARCHY_EVENT_MASK) != 0 && + id == HierarchyEvent.HIERARCHY_CHANGED) + || ((eventMask & AWTEvent.HIERARCHY_BOUNDS_EVENT_MASK) != 0 && + (id == HierarchyEvent.ANCESTOR_MOVED || + id == HierarchyEvent.ANCESTOR_RESIZED))); + } + } + + /** + * The default glassPane for the {@link javax.swing.JLayer}. + * It is a subclass of {@code JPanel} which is non opaque by default. + */ + private static class DefaultLayerGlassPane extends JPanel { + /** + * Creates a new {@link DefaultLayerGlassPane} + */ + public DefaultLayerGlassPane() { + setOpaque(false); + } + + /** + * First, implementatation of this method iterates through + * glassPane's child components and returns {@code true} + * if any of them is visible and contains passed x,y point. + * After that it checks if no mouseListeners is attached to this component + * and no mouse cursor is set, then it returns {@code false}, + * otherwise calls the super implementation of this method. + * + * @param x the <i>x</i> coordinate of the point + * @param y the <i>y</i> coordinate of the point + * @return true if this component logically contains x,y + */ + public boolean contains(int x, int y) { + for (int i = 0; i < getComponentCount(); i++) { + Component c = getComponent(i); + Point point = SwingUtilities.convertPoint(this, new Point(x, y), c); + if(c.isVisible() && c.contains(point)){ + return true; + } + } + if (getMouseListeners().length == 0 + && getMouseMotionListeners().length == 0 + && getMouseWheelListeners().length == 0 + && !isCursorSet()) { + return false; + } + return super.contains(x, y); + } + } + + /** + * The default layout manager for the {@link javax.swing.JLayer}.<br/> + * It places the glassPane on top of the view component + * and makes it the same size as {@code JLayer}, + * it also makes the view component the same size but minus layer's insets<br/> + */ + private static class DefaultLayerLayout implements LayoutManager, Serializable { + /** + * {@inheritDoc} + */ + public void layoutContainer(Container parent) { + JLayer layer = (JLayer) parent; + Component view = layer.getView(); + Component glassPane = layer.getGlassPane(); + if (view != null) { + Insets insets = layer.getInsets(); + view.setLocation(insets.left, insets.top); + view.setSize(layer.getWidth() - insets.left - insets.right, + layer.getHeight() - insets.top - insets.bottom); + } + if (glassPane != null) { + glassPane.setLocation(0, 0); + glassPane.setSize(layer.getWidth(), layer.getHeight()); + } + } + + /** + * {@inheritDoc} + */ + public Dimension minimumLayoutSize(Container parent) { + JLayer layer = (JLayer) parent; + Insets insets = layer.getInsets(); + Dimension ret = new Dimension(insets.left + insets.right, + insets.top + insets.bottom); + Component view = layer.getView(); + if (view != null) { + Dimension size = view.getMinimumSize(); + ret.width += size.width; + ret.height += size.height; + } + if (ret.width == 0 || ret.height == 0) { + ret.width = ret.height = 4; + } + return ret; + } + + /** + * {@inheritDoc} + */ + public Dimension preferredLayoutSize(Container parent) { + JLayer layer = (JLayer) parent; + Insets insets = layer.getInsets(); + Dimension ret = new Dimension(insets.left + insets.right, + insets.top + insets.bottom); + Component view = layer.getView(); + if (view != null) { + Dimension size = view.getPreferredSize(); + if (size.width > 0 && size.height > 0) { + ret.width += size.width; + ret.height += size.height; + } + } + return ret; + } + + /** + * {@inheritDoc} + */ + public void addLayoutComponent(String name, Component comp) { + } + + /** + * {@inheritDoc} + */ + public void removeLayoutComponent(Component comp) { + } + } +} \ No newline at end of file
--- a/jdk/src/share/classes/javax/swing/filechooser/FileSystemView.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/javax/swing/filechooser/FileSystemView.java Wed Jul 05 16:59:08 2017 +0200 @@ -37,6 +37,8 @@ import java.lang.ref.WeakReference; import java.beans.PropertyChangeListener; import java.beans.PropertyChangeEvent; +import java.security.AccessController; +import java.security.PrivilegedAction; import sun.awt.shell.*; @@ -718,8 +720,13 @@ return isFileSystemRoot(dir); } - public boolean isFloppyDrive(File dir) { - String path = dir.getAbsolutePath(); + public boolean isFloppyDrive(final File dir) { + String path = AccessController.doPrivileged(new PrivilegedAction<String>() { + public String run() { + return dir.getAbsolutePath(); + } + }); + return (path != null && (path.equals("A:\\") || path.equals("B:\\"))); }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/jdk/src/share/classes/javax/swing/plaf/LayerUI.java Wed Jul 05 16:59:08 2017 +0200 @@ -0,0 +1,370 @@ +/* + * Copyright 2009 Sun Microsystems, Inc. All rights reserved. + * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. + */ + +package javax.swing.plaf; + +import javax.accessibility.Accessible; +import javax.swing.*; +import javax.swing.plaf.ComponentUI; +import java.awt.*; +import java.awt.event.*; +import java.beans.PropertyChangeEvent; +import java.beans.PropertyChangeSupport; +import java.beans.PropertyChangeListener; +import java.io.Serializable; + +/** + * The base class for all {@link javax.swing.JLayer}'s UI delegates. + * <p/> + * {@link #paint(java.awt.Graphics, javax.swing.JComponent)} method performes the + * painting of the {@code JLayer} + * and {@link #eventDispatched(AWTEvent, JLayer)} method is notified + * about any {@code AWTEvent}s which have been generated by a {@code JLayer} + * or any of its subcomponents. + * <p/> + * The {@code LayerUI} differs from the UI delegates of the other components, + * because it is LookAndFeel independent and is not updated by default when + * the system LookAndFeel is changed. + * <p/> + * The subclasses of {@code LayerUI} can either be stateless and shareable + * by multiple {@code JLayer}s or not shareable. + * + * @param <V> one of the super types of {@code JLayer}'s view component + * + * @see JLayer#setUI(LayerUI) + * @see JLayer#setView(Component) + * @see JLayer#getView() + * @since 1.7 + * + * @author Alexander Potochkin + */ +public class LayerUI<V extends Component> + extends ComponentUI implements Serializable { + + private final PropertyChangeSupport propertyChangeSupport = + new PropertyChangeSupport(this); + + /** + * Paints the specified component. + * Subclasses should override this method and use + * the specified {@code Graphics} object to + * render the content of the component. + * + * @param g the {@code Graphics} context in which to paint; + * @param c the component being painted; + * it can be safely cast to the {@code JLayer<V>} + */ + @Override + public void paint(Graphics g, JComponent c) { + c.paint(g); + } + + /** + * Dispatches {@code AWTEvent}s for {@code JLayer} + * and <b>all it subcomponents</b> to this {@code LayerUI} instance. + * <p> + * To enable the {@code AWTEvent} of the particular type, + * you call {@link javax.swing.JLayer#setLayerEventMask} + * in {@link #installUI(javax.swing.JComponent)} + * and set the layer event mask to {@code 0} + * in {@link #uninstallUI(javax.swing.JComponent)} after that + * + * @param e the event to be dispatched + * @param l the layer this LayerUI is set to + * + * @see JLayer#setLayerEventMask(long) + * @see javax.swing.JLayer#getLayerEventMask() + */ + public void eventDispatched(AWTEvent e, JLayer<? extends V> l){ + } + + /** + * Invoked when {@link javax.swing.JLayer#updateUI()} is called + * by the {@code JLayer} this {@code LayerUI} is set to. + * + * @param l the {@code JLayer} which UI is updated + */ + public void updateUI(JLayer<? extends V> l){ + } + + /** + * Configures the {@code JLayer} this {@code LayerUI} is set to. + * The default implementation registers the {@code LayerUI} + * as a property change listener for the passed {@code JLayer} component. + * + * @param c the {@code JLayer} component where this UI delegate is being installed + */ + public void installUI(JComponent c) { + addPropertyChangeListener((JLayer) c); + } + + /** + * Reverses the configuration which was previously set + * in the {@link #installUI(JComponent)} method. + * The default implementation unregisters the property change listener + * for the passed JLayer component. + * + * @param c the component from which this UI delegate is being removed. + */ + public void uninstallUI(JComponent c) { + removePropertyChangeListener((JLayer) c); + } + + /** + * Adds a PropertyChangeListener to the listener list. The listener is + * registered for all bound properties of this class. + * <p/> + * If {@code listener} is {@code null}, + * no exception is thrown and no action is performed. + * + * @param listener the property change listener to be added + * @see #removePropertyChangeListener + * @see #getPropertyChangeListeners + * @see #addPropertyChangeListener(String, java.beans.PropertyChangeListener) + */ + public void addPropertyChangeListener(PropertyChangeListener listener) { + propertyChangeSupport.addPropertyChangeListener(listener); + } + + /** + * Removes a PropertyChangeListener from the listener list. This method + * should be used to remove PropertyChangeListeners that were registered + * for all bound properties of this class. + * <p/> + * If {@code listener} is {@code null}, + * no exception is thrown and no action is performed. + * + * @param listener the PropertyChangeListener to be removed + * @see #addPropertyChangeListener + * @see #getPropertyChangeListeners + * @see #removePropertyChangeListener(String, PropertyChangeListener) + */ + public void removePropertyChangeListener(PropertyChangeListener listener) { + propertyChangeSupport.removePropertyChangeListener(listener); + } + + /** + * Returns an array of all the property change listeners + * registered on this component. + * + * @return all of this ui's {@code PropertyChangeListener}s + * or an empty array if no property change + * listeners are currently registered + * @see #addPropertyChangeListener + * @see #removePropertyChangeListener + * @see #getPropertyChangeListeners(String) + */ + public PropertyChangeListener[] getPropertyChangeListeners() { + return propertyChangeSupport.getPropertyChangeListeners(); + } + + /** + * Adds a PropertyChangeListener to the listener list for a specific + * property. + * <p/> + * If {@code propertyName} or {@code listener} is {@code null}, + * no exception is thrown and no action is taken. + * + * @param propertyName one of the property names listed above + * @param listener the property change listener to be added + * @see #removePropertyChangeListener(String, PropertyChangeListener) + * @see #getPropertyChangeListeners(String) + * @see #addPropertyChangeListener(String, PropertyChangeListener) + */ + public void addPropertyChangeListener(String propertyName, + PropertyChangeListener listener) { + propertyChangeSupport.addPropertyChangeListener(propertyName, listener); + } + + /** + * Removes a {@code PropertyChangeListener} from the listener + * list for a specific property. This method should be used to remove + * {@code PropertyChangeListener}s + * that were registered for a specific bound property. + * <p/> + * If {@code propertyName} or {@code listener} is {@code null}, + * no exception is thrown and no action is taken. + * + * @param propertyName a valid property name + * @param listener the PropertyChangeListener to be removed + * @see #addPropertyChangeListener(String, PropertyChangeListener) + * @see #getPropertyChangeListeners(String) + * @see #removePropertyChangeListener(PropertyChangeListener) + */ + public void removePropertyChangeListener(String propertyName, + PropertyChangeListener listener) { + propertyChangeSupport.removePropertyChangeListener(propertyName, listener); + } + + /** + * Returns an array of all the listeners which have been associated + * with the named property. + * + * @return all of the {@code PropertyChangeListener}s associated with + * the named property; if no such listeners have been added or + * if {@code propertyName} is {@code null}, an empty + * array is returned + * @see #addPropertyChangeListener(String, PropertyChangeListener) + * @see #removePropertyChangeListener(String, PropertyChangeListener) + * @see #getPropertyChangeListeners + */ + public PropertyChangeListener[] getPropertyChangeListeners(String propertyName) { + return propertyChangeSupport.getPropertyChangeListeners(propertyName); + } + + /** + * Support for reporting bound property changes for Object properties. + * This method can be called when a bound property has changed and it will + * send the appropriate PropertyChangeEvent to any registered + * PropertyChangeListeners. + * + * @param propertyName the property whose value has changed + * @param oldValue the property's previous value + * @param newValue the property's new value + */ + protected void firePropertyChange(String propertyName, + Object oldValue, Object newValue) { + propertyChangeSupport.firePropertyChange(propertyName, oldValue, newValue); + } + + /** + * Notifies the {@code LayerUI} when any of its property are changed + * and enables updating every {@code JLayer} this {@code LayerUI} instance is set to. + * + * @param evt the PropertyChangeEvent generated by this {@code LayerUI} + * @param l the {@code JLayer} this LayerUI is set to + */ + public void applyPropertyChange(PropertyChangeEvent evt, JLayer<? extends V> l) { + } + + /** + * Returns the preferred size of the viewport for a view component. + * + * @return the preferred size of the viewport for a view component + * @see Scrollable#getPreferredScrollableViewportSize() + */ + public Dimension getPreferredScrollableViewportSize(JLayer<? extends V> l) { + if (l.getView() instanceof Scrollable) { + return ((Scrollable)l.getView()).getPreferredScrollableViewportSize(); + } + return l.getPreferredSize(); + } + + /** + * Returns a scroll increment, which is required for components + * that display logical rows or columns in order to completely expose + * one block of rows or columns, depending on the value of orientation. + * + * @return the "block" increment for scrolling in the specified direction + * @see Scrollable#getScrollableBlockIncrement(Rectangle, int, int) + */ + public int getScrollableBlockIncrement(JLayer<? extends V> l, + Rectangle visibleRect, + int orientation, int direction) { + if (l.getView() instanceof Scrollable) { + return ((Scrollable)l.getView()).getScrollableBlockIncrement( + visibleRect,orientation, direction); + } + return (orientation == SwingConstants.VERTICAL) ? visibleRect.height : + visibleRect.width; + } + + /** + * Returns {@code false} to indicate that the height of the viewport does not + * determine the height of the layer, unless the preferred height + * of the layer is smaller than the height of the viewport. + * + * @return whether the layer should track the height of the viewport + * @see Scrollable#getScrollableTracksViewportHeight() + */ + public boolean getScrollableTracksViewportHeight(JLayer<? extends V> l) { + if (l.getView() instanceof Scrollable) { + return ((Scrollable)l.getView()).getScrollableTracksViewportHeight(); + } + if (l.getParent() instanceof JViewport) { + return (((JViewport)l.getParent()).getHeight() > l.getPreferredSize().height); + } + return false; + } + + /** + * Returns {@code false} to indicate that the width of the viewport does not + * determine the width of the layer, unless the preferred width + * of the layer is smaller than the width of the viewport. + * + * @return whether the layer should track the width of the viewport + * @see Scrollable + * @see LayerUI#getScrollableTracksViewportWidth(JLayer) + */ + public boolean getScrollableTracksViewportWidth(JLayer<? extends V> l) { + if (l.getView() instanceof Scrollable) { + return ((Scrollable)l.getView()).getScrollableTracksViewportWidth(); + } + if (l.getParent() instanceof JViewport) { + return (((JViewport)l.getParent()).getWidth() > l.getPreferredSize().width); + } + return false; + } + + /** + * Returns a scroll increment, which is required for components + * that display logical rows or columns in order to completely expose + * one new row or column, depending on the value of orientation. + * Ideally, components should handle a partially exposed row or column + * by returning the distance required to completely expose the item. + * <p> + * Scrolling containers, like JScrollPane, will use this method + * each time the user requests a unit scroll. + * + * @return The "unit" increment for scrolling in the specified direction. + * This value should always be positive. + * @see Scrollable#getScrollableUnitIncrement(Rectangle, int, int) + */ + public int getScrollableUnitIncrement(JLayer<? extends V> l, + Rectangle visibleRect, + int orientation, int direction) { + if (l.getView() instanceof Scrollable) { + return ((Scrollable)l.getView()).getScrollableUnitIncrement( + visibleRect, orientation, direction); + } + return 1; + } + + /** + * If the {@code JLayer}'s view component is not {@code null}, + * this calls the view's {@code getBaseline()} method. + * Otherwise, the default implementation is called. + * + * @param c {@code JLayer} to return baseline resize behavior for + * @param width the width to get the baseline for + * @param height the height to get the baseline for + * @return baseline or a value < 0 indicating there is no reasonable + * baseline + */ + public int getBaseline(JComponent c, int width, int height) { + JLayer l = (JLayer) c; + if (l.getView() != null) { + return l.getView().getBaseline(width, height); + } + return super.getBaseline(c, width, height); + } + + /** + * If the {@code JLayer}'s view component is not {@code null}, + * this calls the view's {@code getBaselineResizeBehavior()} method. + * Otherwise, the default implementation is called. + * + * @param c {@code JLayer} to return baseline resize behavior for + * @return an enum indicating how the baseline changes as the component + * size changes + */ + public Component.BaselineResizeBehavior getBaselineResizeBehavior(JComponent c) { + JLayer l = (JLayer) c; + if (l.getView() != null) { + return l.getView().getBaselineResizeBehavior(); + } + return super.getBaselineResizeBehavior(c); + } +} \ No newline at end of file
--- a/jdk/src/share/classes/javax/swing/plaf/synth/Region.java Tue Aug 18 16:15:37 2009 -0700 +++ b/jdk/src/share/classes/javax/swing/plaf/synth/Region.java Wed Jul 05 16:59:08 2017 +0200 @@ -1,5 +1,5 @@ /* - * Copyright 2002-2008 Sun Microsystems, Inc. All Rights Reserved. + * Copyright 2002-2009 Sun Microsystems, Inc. All Rights Reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it @@ -24,8 +24,13 @@ */ package javax.swing.plaf.synth; -import javax.swing.*; -import java.util.*; +import sun.awt.AppContext; + +import java.util.HashMap; +import java.util.Locale; +im