OpenJDK / bsd-port / jdk9 / jdk
changeset 1488:bf41e885717f
Merge
author | tbell |
---|---|
date | Thu, 06 Aug 2009 19:01:59 -0700 |
parents | 9ae4027c5fe1 bc1deb18bfb1 |
children | 0d99696fec64 c223ce2294c1 |
files | test/java/util/concurrent/ConcurrentLinkedQueue/ConcurrentQueueLoops.java test/java/util/concurrent/ConcurrentLinkedQueue/LoopHelpers.java |
diffstat | 106 files changed, 5379 insertions(+), 1382 deletions(-) [+] |
line wrap: on
line diff
--- a/make/java/java/FILES_java.gmk Thu Aug 06 10:25:18 2009 -0700 +++ b/make/java/java/FILES_java.gmk Thu Aug 06 19:01:59 2009 -0700 @@ -250,6 +250,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/make/tools/CharsetMapping/IBM420.c2b Thu Aug 06 10:25:18 2009 -0700 +++ b/make/tools/CharsetMapping/IBM420.c2b Thu Aug 06 19:01:59 2009 -0700 @@ -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/make/tools/CharsetMapping/IBM420.map Thu Aug 06 10:25:18 2009 -0700 +++ b/make/tools/CharsetMapping/IBM420.map Thu Aug 06 19:01:59 2009 -0700 @@ -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/make/tools/CharsetMapping/IBM420.nr Thu Aug 06 10:25:18 2009 -0700 +++ b/make/tools/CharsetMapping/IBM420.nr Thu Aug 06 19:01:59 2009 -0700 @@ -1,1 +1,1 @@ -0x25 U+000a +0x25 U+000a
--- a/make/tools/src/build/tools/charsetmapping/GenerateSBCS.java Thu Aug 06 10:25:18 2009 -0700 +++ b/make/tools/src/build/tools/charsetmapping/GenerateSBCS.java Thu Aug 06 19:01:59 2009 -0700 @@ -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/src/share/classes/java/nio/channels/DatagramChannel.java Thu Aug 06 10:25:18 2009 -0700 +++ b/src/share/classes/java/nio/channels/DatagramChannel.java Thu Aug 06 19:01:59 2009 -0700 @@ -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/src/share/classes/java/nio/channels/package-info.java Thu Aug 06 10:25:18 2009 -0700 +++ b/src/share/classes/java/nio/channels/package-info.java Thu Aug 06 19:01:59 2009 -0700 @@ -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/src/share/classes/java/nio/file/DirectoryStream.java Thu Aug 06 10:25:18 2009 -0700 +++ b/src/share/classes/java/nio/file/DirectoryStream.java Thu Aug 06 19:01:59 2009 -0700 @@ -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/src/share/classes/java/nio/file/Path.java Thu Aug 06 10:25:18 2009 -0700 +++ b/src/share/classes/java/nio/file/Path.java Thu Aug 06 19:01:59 2009 -0700 @@ -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/src/share/classes/java/nio/file/attribute/package-info.java Thu Aug 06 10:25:18 2009 -0700 +++ b/src/share/classes/java/nio/file/attribute/package-info.java Thu Aug 06 19:01:59 2009 -0700 @@ -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/src/share/classes/java/util/Arrays.java Thu Aug 06 10:25:18 2009 -0700 +++ b/src/share/classes/java/util/Arrays.java Thu Aug 06 19:01:59 2009 -0700 @@ -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/src/share/classes/java/util/Collections.java Thu Aug 06 10:25:18 2009 -0700 +++ b/src/share/classes/java/util/Collections.java Thu Aug 06 19:01:59 2009 -0700 @@ -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/src/share/classes/java/util/ComparableTimSort.java Thu Aug 06 19:01:59 2009 -0700 @@ -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/src/share/classes/java/util/Formatter.java Thu Aug 06 10:25:18 2009 -0700 +++ b/src/share/classes/java/util/Formatter.java Thu Aug 06 19:01:59 2009 -0700 @@ -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/src/share/classes/java/util/TimSort.java Thu Aug 06 19:01:59 2009 -0700 @@ -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/src/share/classes/java/util/concurrent/ConcurrentLinkedQueue.java Thu Aug 06 10:25:18 2009 -0700 +++ b/src/share/classes/java/util/concurrent/ConcurrentLinkedQueue.java Thu Aug 06 19:01:59 2009 -0700 @@ -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/src/share/classes/java/util/concurrent/LinkedBlockingDeque.java Thu Aug 06 10:25:18 2009 -0700 +++ b/src/share/classes/java/util/concurrent/LinkedBlockingDeque.java Thu Aug 06 19:01:59 2009 -0700 @@ -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/src/share/classes/java/util/concurrent/LinkedBlockingQueue.java Thu Aug 06 10:25:18 2009 -0700 +++ b/src/share/classes/java/util/concurrent/LinkedBlockingQueue.java Thu Aug 06 19:01:59 2009 -0700 @@ -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/src/share/classes/sun/dyn/FilterGeneric.java Thu Aug 06 10:25:18 2009 -0700 +++ b/src/share/classes/sun/dyn/FilterGeneric.java Thu Aug 06 19:01:59 2009 -0700 @@ -16,7 +16,7 @@ * * 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 Sf, tifth Floor, Boston, MA 02110-1301 USA. + * 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
--- a/src/solaris/native/java/lang/UNIXProcess_md.c Thu Aug 06 10:25:18 2009 -0700 +++ b/src/solaris/native/java/lang/UNIXProcess_md.c Thu Aug 06 19:01:59 2009 -0700 @@ -50,27 +50,72 @@ #include <limits.h> /* - * (Hopefully temporarily) disable the clone-exec feature pending - * further investigation and bug-fixing. - * 32-bit (but not 64-bit) Linux fails on the program - * Runtime.getRuntime().exec("/bin/true").waitFor(); - * with: - * # Internal Error (os_linux_x86.cpp:683), pid=19940, tid=2934639536 - * # Error: pthread_getattr_np failed with errno = 3 (ESRCH) - * Linux kernel/pthread gurus are invited to figure this out. + * There are 3 possible strategies we might use to "fork": + * + * - fork(2). Very portable and reliable but subject to + * failure due to overcommit (see the documentation on + * /proc/sys/vm/overcommit_memory in Linux proc(5)). + * This is the ancient problem of spurious failure whenever a large + * process starts a small subprocess. + * + * - vfork(). Using this is scary because all relevant man pages + * contain dire warnings, e.g. Linux vfork(2). But at least it's + * documented in the glibc docs and is standardized by XPG4. + * http://www.opengroup.org/onlinepubs/000095399/functions/vfork.html + * On Linux, one might think that vfork() would be implemented using + * the clone system call with flag CLONE_VFORK, but in fact vfork is + * a separate system call (which is a good sign, suggesting that + * vfork will continue to be supported at least on Linux). + * Another good sign is that glibc implements posix_spawn using + * vfork whenever possible. Note that we cannot use posix_spawn + * ourselves because there's no reliable way to close all inherited + * file descriptors. + * + * - clone() with flags CLONE_VM but not CLONE_THREAD. clone() is + * Linux-specific, but this ought to work - at least the glibc + * sources contain code to handle different combinations of CLONE_VM + * and CLONE_THREAD. However, when this was implemented, it + * appeared to fail on 32-bit i386 (but not 64-bit x86_64) Linux with + * the simple program + * Runtime.getRuntime().exec("/bin/true").waitFor(); + * with: + * # Internal Error (os_linux_x86.cpp:683), pid=19940, tid=2934639536 + * # Error: pthread_getattr_np failed with errno = 3 (ESRCH) + * We believe this is a glibc bug, reported here: + * http://sources.redhat.com/bugzilla/show_bug.cgi?id=10311 + * but the glibc maintainers closed it as WONTFIX. + * + * Based on the above analysis, we are currently using vfork() on + * Linux and fork() on other Unix systems, but the code to use clone() + * remains. */ -#define USE_CLONE 0 -#ifndef USE_CLONE -#ifdef __linux__ -#define USE_CLONE 1 -#else -#define USE_CLONE 0 -#endif +#define START_CHILD_USE_CLONE 0 /* clone() currently disabled; see above. */ + +#ifndef START_CHILD_USE_CLONE + #ifdef __linux__ + #define START_CHILD_USE_CLONE 1 + #else + #define START_CHILD_USE_CLONE 0 + #endif #endif -#if USE_CLONE +/* By default, use vfork() on Linux. */ +#ifndef START_CHILD_USE_VFORK + #ifdef __linux__ + #define START_CHILD_USE_VFORK 1 + #else + #define START_CHILD_USE_VFORK 0 + #endif +#endif + +#if START_CHILD_USE_CLONE #include <sched.h> +#define START_CHILD_SYSTEM_CALL "clone" +#elif START_CHILD_USE_VFORK +#define START_CHILD_SYSTEM_CALL "vfork" +#else +#define START_CHILD_SYSTEM_CALL "fork" #endif #ifndef STDIN_FILENO @@ -95,6 +140,27 @@ #define FAIL_FILENO (STDERR_FILENO + 1) +/* TODO: Refactor. */ +#define RESTARTABLE(_cmd, _result) do { \ + do { \ + _result = _cmd; \ + } while((_result == -1) && (errno == EINTR)); \ +} while(0) + +/* This is one of the rare times it's more portable to declare an + * external symbol explicitly, rather than via a system header. + * The declaration is standardized as part of UNIX98, but there is + * no standard (not even de-facto) header file where the + * declaration is to be found. See: + * http://www.opengroup.org/onlinepubs/009695399/functions/environ.html + * http://www.opengroup.org/onlinepubs/009695399/functions/xsh_chap02_02.html + * + * "All identifiers in this volume of IEEE Std 1003.1-2001, except + * environ, are defined in at least one of the headers" (!) + */ +extern char **environ; + + static void setSIGCHLDHandler(JNIEnv *env) { @@ -283,6 +349,36 @@ } } +static ssize_t +restartableWrite(int fd, const void *buf, size_t count) +{ + ssize_t result; + RESTARTABLE(write(fd, buf, count), result); + return result; +} + +static int +restartableDup2(int fd_from, int fd_to) +{ + int err; + RESTARTABLE(dup2(fd_from, fd_to), err); + return err; +} + +static int +restartableClose(int fd) +{ + int err; + RESTARTABLE(close(fd), err); + return err; +} + +static int +closeSafely(int fd) +{ + return (fd == -1) ? 0 : restartableClose(fd); +} + static int isAsciiDigit(char c) { @@ -303,8 +399,8 @@ * the lowest numbered file descriptor, just like open(). So we * close a couple explicitly. */ - close(from_fd); /* for possible use by opendir() */ - close(from_fd + 1); /* another one for good luck */ + restartableClose(from_fd); /* for possible use by opendir() */ + restartableClose(from_fd + 1); /* another one for good luck */ if ((dp = opendir("/proc/self/fd")) == NULL) return 0; @@ -316,7 +412,7 @@ int fd; if (isAsciiDigit(dirp->d_name[0]) && (fd = strtol(dirp->d_name, NULL, 10)) >= from_fd + 2) - close(fd); + restartableClose(fd); } closedir(dp); @@ -324,13 +420,15 @@ return 1; } -static void +static int moveDescriptor(int fd_from, int fd_to) { if (fd_from != fd_to) { - dup2(fd_from, fd_to); - close(fd_from); + if ((restartableDup2(fd_from, fd_to) == -1) || + (restartableClose(fd_from) == -1)) + return -1; } + return 0; } static const char * @@ -434,41 +532,30 @@ const char *argv[], const char *const envp[]) { -#if USE_CLONE +#if START_CHILD_USE_CLONE || START_CHILD_USE_VFORK + /* shared address space; be very careful. */ execve(file, (char **) argv, (char **) envp); if (errno == ENOEXEC) execve_as_traditional_shell_script(file, argv, envp); #else - /* Our address space is unshared, so can mutate environ. */ - extern char **environ; + /* unshared address space; we can mutate environ. */ environ = (char **) envp; execvp(file, (char **) argv); #endif } /** - * execvpe should have been included in the Unix standards. - * execvpe is identical to execvp, except that the child environment is + * 'execvpe' should have been included in the Unix standards, + * and is a GNU extension in glibc 2.10. + * + * JDK_execvpe is identical to execvp, except that the child environment is * specified via the 3rd argument instead of being inherited from environ. */ static void -execvpe(const char *file, - const char *argv[], - const char *const envp[]) +JDK_execvpe(const char *file, + const char *argv[], + const char *const envp[]) { - /* This is one of the rare times it's more portable to declare an - * external symbol explicitly, rather than via a system header. - * The declaration is standardized as part of UNIX98, but there is - * no standard (not even de-facto) header file where the - * declaration is to be found. See: - * http://www.opengroup.org/onlinepubs/009695399/functions/environ.html - * http://www.opengroup.org/onlinepubs/009695399/functions/xsh_chap02_02.html - * - * "All identifiers in this volume of IEEE Std 1003.1-2001, except - * environ, are defined in at least one of the headers" (!) - */ - extern char **environ; - if (envp == NULL || (char **) envp == environ) { execvp(file, (char **) argv); return; @@ -538,13 +625,6 @@ } } -static void -closeSafely(int fd) -{ - if (fd != -1) - close(fd); -} - /* * Reads nbyte bytes from file descriptor fd into buf, * The read operation is retried in case of EINTR or partial reads. @@ -587,6 +667,9 @@ const char **envv; const char *pdir; jboolean redirectErrorStream; +#if START_CHILD_USE_CLONE + void *clone_stack; +#endif } ChildStuff; static void @@ -610,31 +693,40 @@ /* Close the parent sides of the pipes. Closing pipe fds here is redundant, since closeDescriptors() would do it anyways, but a little paranoia is a good thing. */ - closeSafely(p->in[1]); - closeSafely(p->out[0]); - closeSafely(p->err[0]); - closeSafely(p->fail[0]); + if ((closeSafely(p->in[1]) == -1) || + (closeSafely(p->out[0]) == -1) || + (closeSafely(p->err[0]) == -1) || + (closeSafely(p->fail[0]) == -1)) + goto WhyCantJohnnyExec; /* Give the child sides of the pipes the right fileno's. */ /* Note: it is possible for in[0] == 0 */ - moveDescriptor(p->in[0] != -1 ? p->in[0] : p->fds[0], STDIN_FILENO); - moveDescriptor(p->out[1]!= -1 ? p->out[1] : p->fds[1], STDOUT_FILENO); + if ((moveDescriptor(p->in[0] != -1 ? p->in[0] : p->fds[0], + STDIN_FILENO) == -1) || + (moveDescriptor(p->out[1]!= -1 ? p->out[1] : p->fds[1], + STDOUT_FILENO) == -1)) + goto WhyCantJohnnyExec; if (p->redirectErrorStream) { - closeSafely(p->err[1]); - dup2(STDOUT_FILENO, STDERR_FILENO); + if ((closeSafely(p->err[1]) == -1) || + (restartableDup2(STDOUT_FILENO, STDERR_FILENO) == -1)) + goto WhyCantJohnnyExec; } else { - moveDescriptor(p->err[1] != -1 ? p->err[1] : p->fds[2], STDERR_FILENO); + if (moveDescriptor(p->err[1] != -1 ? p->err[1] : p->fds[2], + STDERR_FILENO) == -1) + goto WhyCantJohnnyExec; } - moveDescriptor(p->fail[1], FAIL_FILENO); + if (moveDescriptor(p->fail[1], FAIL_FILENO) == -1) + goto WhyCantJohnnyExec; /* close everything */ if (closeDescriptors() == 0) { /* failed, close the old way */ int max_fd = (int)sysconf(_SC_OPEN_MAX); - int i; - for (i = FAIL_FILENO + 1; i < max_fd; i++) - close(i); + int fd; + for (fd = FAIL_FILENO + 1; fd < max_fd; fd++) + if (restartableClose(fd) == -1 && errno != EBADF) + goto WhyCantJohnnyExec; } /* change to the new working directory */ @@ -644,7 +736,7 @@ if (fcntl(FAIL_FILENO, F_SETFD, FD_CLOEXEC) == -1) goto WhyCantJohnnyExec; - execvpe(p->argv[0], p->argv, p->envv); + JDK_execvpe(p->argv[0], p->argv, p->envv); WhyCantJohnnyExec: /* We used to go to an awful lot of trouble to predict whether the @@ -659,13 +751,62 @@ */ { int errnum = errno; - write(FAIL_FILENO, &errnum, sizeof(errnum)); + restartableWrite(FAIL_FILENO, &errnum, sizeof(errnum)); } - close(FAIL_FILENO); + restartableClose(FAIL_FILENO); _exit(-1); return 0; /* Suppress warning "no return value from function" */ } +/** + * Start a child process running function childProcess. + * This function only returns in the parent. + * We are unusually paranoid; use of clone/vfork is + * especially likely to tickle gcc/glibc bugs. + */ +#ifdef __attribute_noinline__ /* See: sys/cdefs.h */ +__attribute_noinline__ +#endif +static pid_t +startChild(ChildStuff *c) { +#if START_CHILD_USE_CLONE +#define START_CHILD_CLONE_STACK_SIZE (64 * 1024) + /* + * See clone(2). + * Instead of worrying about which direction the stack grows, just + * allocate twice as much and start the stack in the middle. + */ + if ((c->clone_stack = malloc(2 * START_CHILD_CLONE_STACK_SIZE)) == NULL) + /* errno will be set to ENOMEM */ + return -1; + return clone(childProcess, + c->clone_stack + START_CHILD_CLONE_STACK_SIZE, + CLONE_VFORK | CLONE_VM | SIGCHLD, c); +#else + #if START_CHILD_USE_VFORK + /* + * We separate the call to vfork into a separate function to make + * very sure to keep stack of child from corrupting stack of parent, + * as suggested by the scary gcc warning: + * warning: variable 'foo' might be clobbered by 'longjmp' or 'vfork' + */ + volatile pid_t resultPid = vfork(); + #else + /* + * From Solaris fork(2): In Solaris 10, a call to fork() is + * identical to a call to fork1(); only the calling thread is + * replicated in the child process. This is the POSIX-specified + * behavior for fork(). + */ + pid_t resultPid = fork(); + #endif + if (resultPid == 0) + childProcess(c); + assert(resultPid != 0); /* childProcess never returns */ + return resultPid; +#endif /* ! START_CHILD_USE_CLONE */ +} + JNIEXPORT jint JNICALL Java_java_lang_UNIXProcess_forkAndExec(JNIEnv *env, jobject process, @@ -678,9 +819,6 @@ { int errnum; int resultPid = -1; -#if USE_CLONE - void *clone_stack = NULL; -#endif int in[2], out[2], err[2], fail[2]; jint *fds = NULL; const char *pprog = NULL; @@ -694,6 +832,9 @@ c->argv = NULL; c->envv = NULL; c->pdir = NULL; +#if START_CHILD_USE_CLONE + c->clone_stack = NULL; +#endif /* Convert prog + argBlock into a char ** argv. * Add one word room for expansion of argv for use by @@ -739,37 +880,15 @@ c->redirectErrorStream = redirectErrorStream; - { -#if USE_CLONE - /* See clone(2). - * Instead of worrying about which direction the stack grows, just - * allocate twice as much and start the stack in the middle. */ - const int stack_size = 64 * 1024; - if ((clone_stack = NEW(char, 2 * stack_size)) == NULL) goto Catch; - resultPid = clone(childProcess, clone_stack + stack_size, - /* CLONE_VFORK | // works, but unnecessary */ - CLONE_VM | SIGCHLD, c); -#else - /* From fork(2): In Solaris 10, a call to fork() is identical - * to a call to fork1(); only the calling thread is replicated - * in the child process. This is the POSIX-specified behavior - * for fork(). */ - resultPid = fork(); - if (resultPid == 0) { - childProcess(c); - assert(0); /* childProcess must not return */ - } -#endif - } + resultPid = startChild(c); + assert(resultPid != 0); if (resultPid < 0) { - throwIOException(env, errno, "Fork failed"); + throwIOException(env, errno, START_CHILD_SYSTEM_CALL " failed"); goto Catch; } - /* parent process */ - - close(fail[1]); fail[1] = -1; /* See: WhyCantJohnnyExec */ + restartableClose(fail[1]); fail[1] = -1; /* See: WhyCantJohnnyExec */ switch (readFully(fail[0], &errnum, sizeof(errnum))) { case 0: break; /* Exec succeeded */ @@ -787,8 +906,8 @@ fds[2] = (err[0] != -1) ? err[0] : -1; Finally: -#if USE_CLONE - free(clone_stack); +#if START_CHILD_USE_CLONE + free(c->clone_stack); #endif /* Always clean up the child's side of the pipes */
--- a/src/windows/classes/sun/nio/fs/WindowsConstants.java Thu Aug 06 10:25:18 2009 -0700 +++ b/src/windows/classes/sun/nio/fs/WindowsConstants.java Thu Aug 06 19:01:59 2009 -0700 @@ -92,6 +92,7 @@ public static final int ERROR_INVALID_DATA = 13; public static final int ERROR_NOT_SAME_DEVICE = 17; public static final int ERROR_NOT_READY = 21; + public static final int ERROR_SHARING_VIOLATION = 32; public static final int ERROR_FILE_EXISTS = 80; public static final int ERROR_INVALID_PARAMATER = 87; public static final int ERROR_DISK_FULL = 112;
--- a/src/windows/classes/sun/nio/fs/WindowsFileAttributes.java Thu Aug 06 10:25:18 2009 -0700 +++ b/src/windows/classes/sun/nio/fs/WindowsFileAttributes.java Thu Aug 06 19:01:59 2009 -0700 @@ -299,6 +299,9 @@ throws WindowsException { if (!ensureAccurateMetadata) { + WindowsException firstException = null; + + // GetFileAttributesEx is the fastest way to read the attributes NativeBuffer buffer = NativeBuffers.getNativeBuffer(SIZEOF_FILE_ATTRIBUTE_DATA); try { @@ -310,9 +313,39 @@ .getInt(address + OFFSETOF_FILE_ATTRIBUTE_DATA_ATTRIBUTES); if ((fileAttrs & FILE_ATTRIBUTE_REPARSE_POINT) == 0) return fromFileAttributeData(address, 0); + } catch (WindowsException x) { + if (x.lastError() != ERROR_SHARING_VIOLATION) + throw x; + firstException = x; } finally { buffer.release(); } + + // For sharing violations, fallback to FindFirstFile if the file + // is not a root directory. + if (firstException != null) { + String search = path.getPathForWin32Calls(); + char last = search.charAt(search.length() -1); + if (last == ':' || last == '\\') + throw firstException; + buffer = getBufferForFindData(); + try { + long handle = FindFirstFile(search, buffer.address()); + FindClose(handle); + WindowsFileAttributes attrs = fromFindData(buffer.address()); + // FindFirstFile does not follow sym links. Even if + // followLinks is false, there isn't sufficient information + // in the WIN32_FIND_DATA structure to know if the reparse + // point is a sym link. + if (attrs.isReparsePoint()) + throw firstException; + return attrs; + } catch (WindowsException ignore) { + throw firstException; + } finally { + buffer.release(); + } + } } // file is reparse point so need to open file to get attributes
--- a/test/com/sun/jdi/EnumTest.java Thu Aug 06 10:25:18 2009 -0700 +++ b/test/com/sun/jdi/EnumTest.java Thu Aug 06 19:01:59 2009 -0700 @@ -29,7 +29,7 @@ * @author jjh * * @run build TestScaffold VMConnection TargetListener TargetAdapter - * @run compile -source 1.5 -target 1.5 -g EnumTest.java + * @run compile -g EnumTest.java * @run main EnumTest */ import com.sun.jdi.*;
--- a/test/com/sun/jdi/GenericsTest.java Thu Aug 06 10:25:18 2009 -0700 +++ b/test/com/sun/jdi/GenericsTest.java Thu Aug 06 19:01:59 2009 -0700 @@ -29,7 +29,7 @@ * @author jjh * * @run build TestScaffold VMConnection TargetListener TargetAdapter - * @run compile -source 1.5 -target 1.5 -g GenericsTest.java + * @run compile -g GenericsTest.java * @run main GenericsTest */ import com.sun.jdi.*;
--- a/test/com/sun/jdi/JdbVarargsTest.sh Thu Aug 06 10:25:18 2009 -0700 +++ b/test/com/sun/jdi/JdbVarargsTest.sh Thu Aug 06 19:01:59 2009 -0700 @@ -32,7 +32,6 @@ # @run shell JdbVarargsTest.sh classname=JdbVarargsTest -compileOptions="-source 1.5 -target 1.5" createJavaFile() { cat <<EOF > $classname.java.1
--- a/test/com/sun/jdi/StepTest.java Thu Aug 06 10:25:18 2009 -0700 +++ b/test/com/sun/jdi/StepTest.java Thu Aug 06 19:01:59 2009 -0700 @@ -27,7 +27,7 @@ * @author Gordon Hirsch * * @run build TestScaffold VMConnection TargetAdapter TargetListener - * @run compile -g -target 1.5 MethodCalls.java + * @run compile -g MethodCalls.java * @run compile -g MethodCallsReflection.java * @run compile -g ControlFlow.java * @run build StepTest
--- a/test/com/sun/jdi/UTF8Test.java Thu Aug 06 10:25:18 2009 -0700 +++ b/test/com/sun/jdi/UTF8Test.java Thu Aug 06 19:01:59 2009 -0700 @@ -29,7 +29,7 @@ * @author jjh * * @run build TestScaffold VMConnection TargetListener TargetAdapter - * @run compile -g -source 1.5 UTF8Test.java + * @run compile -g UTF8Test.java * @run main UTF8Test */
--- a/test/com/sun/jdi/VarargsTest.java Thu Aug 06 10:25:18 2009 -0700 +++ b/test/com/sun/jdi/VarargsTest.java Thu Aug 06 19:01:59 2009 -0700 @@ -29,7 +29,7 @@ * @author jjh * * @run build TestScaffold VMConnection TargetListener TargetAdapter - * @run compile -g -source 1.5 -target 1.5 VarargsTest.java + * @run compile -g VarargsTest.java * @run main VarargsTest */ import com.sun.jdi.*;
--- a/test/java/net/Authenticator/B4933582.sh Thu Aug 06 10:25:18 2009 -0700 +++ b/test/java/net/Authenticator/B4933582.sh Thu Aug 06 19:01:59 2009 -0700 @@ -30,6 +30,10 @@ PS=":" FS="/" ;; + CYGWIN* ) + PS=";" + FS="/" + ;; Windows* ) PS=";" FS="\\" @@ -39,7 +43,7 @@ exit 1; ;; esac -${TESTJAVA}${FS}bin${FS}javac -d . -classpath ${TESTSRC}${FS}..${FS}..${FS}..${FS}sun${FS}net${FS}www${FS}httptest ${TESTSRC}${FS}B4933582.java +${TESTJAVA}${FS}bin${FS}javac -d . -classpath "${TESTSRC}${FS}..${FS}..${FS}..${FS}sun${FS}net${FS}www${FS}httptest" ${TESTSRC}${FS}B4933582.java rm -f cache.ser auth.save -${TESTJAVA}${FS}bin${FS}java -classpath ${TESTSRC}${FS}..${FS}..${FS}..${FS}sun${FS}net${FS}www${FS}httptest${PS}. B4933582 first -${TESTJAVA}${FS}bin${FS}java -classpath ${TESTSRC}${FS}..${FS}..${FS}..${FS}sun${FS}net${FS}www${FS}httptest${PS}. B4933582 second +${TESTJAVA}${FS}bin${FS}java -classpath "${TESTSRC}${FS}..${FS}..${FS}..${FS}sun${FS}net${FS}www${FS}httptest${PS}." B4933582 first +${TESTJAVA}${FS}bin${FS}java -classpath "${TESTSRC}${FS}..${FS}..${FS}..${FS}sun${FS}net${FS}www${FS}httptest${PS}." B4933582 second
--- a/test/java/net/DatagramSocket/SetDatagramSocketImplFactory/ADatagramSocket.sh Thu Aug 06 10:25:18 2009 -0700 +++ b/test/java/net/DatagramSocket/SetDatagramSocketImplFactory/ADatagramSocket.sh Thu Aug 06 19:01:59 2009 -0700 @@ -35,6 +35,10 @@ PATHSEP=":" FILESEP="/" ;; + CYGWIN* ) + PATHSEP=";" + FILESEP="/" + ;; Windows* ) PATHSEP=";" FILESEP="\\"
--- a/test/java/net/Socket/OldSocketImpl.sh Thu Aug 06 10:25:18 2009 -0700 +++ b/test/java/net/Socket/OldSocketImpl.sh Thu Aug 06 19:01:59 2009 -0700 @@ -32,6 +32,10 @@ PS=":" FS="/" ;; + CYGWIN* ) + PS=";" + FS="/" + ;; Windows* ) PS=";" FS="\\"
--- a/test/java/net/URL/B5086147.sh Thu Aug 06 10:25:18 2009 -0700 +++ b/test/java/net/URL/B5086147.sh Thu Aug 06 19:01:59 2009 -0700 @@ -29,6 +29,10 @@ SunOS | Linux ) exit 0 ;; + CYGWIN* ) + PS=";" + FS="/" + ;; Windows* ) PS=";" FS="\\"
--- a/test/java/net/URL/runconstructor.sh Thu Aug 06 10:25:18 2009 -0700 +++ b/test/java/net/URL/runconstructor.sh Thu Aug 06 19:01:59 2009 -0700 @@ -31,6 +31,10 @@ PS=":" FS="/" ;; + CYGWIN* ) + PS=";" + FS="/" + ;; Windows* ) PS=";" FS="\\"
--- a/test/java/net/URLClassLoader/B5077773.sh Thu Aug 06 10:25:18 2009 -0700 +++ b/test/java/net/URLClassLoader/B5077773.sh Thu Aug 06 19:01:59 2009 -0700 @@ -42,6 +42,10 @@ PS=":" FS="/" ;; + CYGWIN* ) + PS=";" + FS="/" + ;; Windows* ) PS=";" FS="\\"
--- a/test/java/net/URLClassLoader/sealing/checksealed.sh Thu Aug 06 10:25:18 2009 -0700 +++ b/test/java/net/URLClassLoader/sealing/checksealed.sh Thu Aug 06 19:01:59 2009 -0700 @@ -35,6 +35,10 @@ PS=":" FS="/" ;; + CYGWIN* ) + PS=";" + FS="/" + ;; Windows* ) PS=";" FS="\\" @@ -49,10 +53,10 @@ if [ x"$TESTJAVA" = x ]; then TESTJAVA=$1; fi if [ x"$TESTSRC" = x ]; then TESTSRC=.; fi -CLASSPATH=.${PS}${TESTSRC}${FS}a${PS}${TESTSRC}${FS}b.jar +CLASSPATH=".${PS}${TESTSRC}${FS}a${PS}${TESTSRC}${FS}b.jar" -${TESTJAVA}${FS}bin${FS}javac -classpath ${CLASSPATH} -d . ${TESTSRC}${FS}CheckSealed.java -${TESTJAVA}${FS}bin${FS}java -cp ${CLASSPATH} CheckSealed 1 +${TESTJAVA}${FS}bin${FS}javac -classpath "${CLASSPATH}" -d . ${TESTSRC}${FS}CheckSealed.java +${TESTJAVA}${FS}bin${FS}java -cp "${CLASSPATH}" CheckSealed 1 if [ $? != 0 ]; then exit 1; fi -${TESTJAVA}${FS}bin${FS}java -cp ${CLASSPATH} CheckSealed 2 +${TESTJAVA}${FS}bin${FS}java -cp "${CLASSPATH}" CheckSealed 2 if [ $? != 0 ]; then exit 1; fi
--- a/test/java/net/URLConnection/6212146/test.sh Thu Aug 06 10:25:18 2009 -0700 +++ b/test/java/net/URLConnection/6212146/test.sh Thu Aug 06 19:01:59 2009 -0700 @@ -41,6 +41,10 @@ PS=":" FS="/" ;; + CYGWIN* ) + PS=";" + FS="/" + ;; Windows* ) PS=";" FS="\\"
--- a/test/java/nio/channels/DatagramChannel/BasicMulticastTests.java Thu Aug 06 10:25:18 2009 -0700 +++ b/test/java/nio/channels/DatagramChannel/BasicMulticastTests.java Thu Aug 06 19:01:59 2009 -0700 @@ -25,6 +25,7 @@ * @bug 4527345 * @summary Unit test for DatagramChannel's multicast support * @build BasicMulticastTests NetworkConfiguration + * @run main BasicMulticastTests */ import java.nio.ByteBuffer;
--- a/test/java/nio/channels/DatagramChannel/MulticastSendReceiveTests.java Thu Aug 06 10:25:18 2009 -0700 +++ b/test/java/nio/channels/DatagramChannel/MulticastSendReceiveTests.java Thu Aug 06 19:01:59 2009 -0700 @@ -25,6 +25,7 @@ * @bug 4527345 * @summary Unit test for DatagramChannel's multicast support * @build MulticastSendReceiveTests NetworkConfiguration + * @run main MulticastSendReceiveTests */ import java.nio.ByteBuffer;
--- a/test/java/nio/file/Files/ContentType.java Thu Aug 06 10:25:18 2009 -0700 +++ b/test/java/nio/file/Files/ContentType.java Thu Aug 06 19:01:59 2009 -0700 @@ -26,6 +26,7 @@ * @summary Unit test for probeContentType method * @library .. * @build ContentType SimpleFileTypeDetector + * @run main ContentType */ import java.nio.file.*;
--- a/test/java/nio/file/Path/Misc.java Thu Aug 06 10:25:18 2009 -0700 +++ b/test/java/nio/file/Path/Misc.java Thu Aug 06 19:01:59 2009 -0700 @@ -22,7 +22,7 @@ */ /* @test - * @bug 4313887 6838333 + * @bug 4313887 6838333 6866804 * @summary Unit test for java.nio.file.Path for miscellenous methods not * covered by other tests * @library .. @@ -107,6 +107,28 @@ dir.checkAccess(AccessMode.READ, AccessMode.WRITE); /** + * Test: Check access to all files in all root directories. + * (A useful test on Windows for special files such as pagefile.sys) + */ + for (Path root: FileSystems.getDefault().getRootDirectories()) { + DirectoryStream<Path> stream; + try { + stream = root.newDirectoryStream(); + } catch (IOException x) { + continue; // skip root directories that aren't accessible + } + try { + for (Path entry: stream) { + try { + entry.checkAccess(); + } catch (AccessDeniedException ignore) { } + } + } finally { + stream.close(); + } + } + + /** * Test: File does not exist */ Path doesNotExist = dir.resolve("thisDoesNotExists");
--- a/test/java/security/Security/ClassLoaderDeadlock/ClassLoaderDeadlock.sh Thu Aug 06 10:25:18 2009 -0700 +++ b/test/java/security/Security/ClassLoaderDeadlock/ClassLoaderDeadlock.sh Thu Aug 06 19:01:59 2009 -0700 @@ -54,6 +54,10 @@ PATHSEP=":" FILESEP="/" ;; + CYGWIN* ) + PATHSEP=";" + FILESEP="/" + ;; Windows* ) PATHSEP=";" FILESEP="\\" @@ -81,7 +85,7 @@ # run the test ${TESTJAVA}${FILESEP}bin${FILESEP}java \ - -classpath ${TESTCLASSES}${PATHSEP}${TESTSRC}${FILESEP}Deadlock.jar \ + -classpath "${TESTCLASSES}${PATHSEP}${TESTSRC}${FILESEP}Deadlock.jar" \ ClassLoaderDeadlock exit $?
--- a/test/java/security/Security/ClassLoaderDeadlock/Deadlock.sh Thu Aug 06 10:25:18 2009 -0700 +++ b/test/java/security/Security/ClassLoaderDeadlock/Deadlock.sh Thu Aug 06 19:01:59 2009 -0700 @@ -42,6 +42,10 @@ PATHSEP=":" FILESEP="/" ;; + CYGWIN* ) + PATHSEP=";" + FILESEP="/" + ;; Windows* ) PATHSEP=";" FILESEP="\\" @@ -54,5 +58,5 @@ JAVA="${TESTJAVA}${FILESEP}bin${FILESEP}java" -${JAVA} -cp ${TESTCLASSES}${PATHSEP}${TESTSRC}${FILESEP}Deadlock.jar Deadlock +${JAVA} -cp "${TESTCLASSES}${PATHSEP}${TESTSRC}${FILESEP}Deadlock.jar" Deadlock
--- a/test/java/security/Security/signedfirst/Dyn.sh Thu Aug 06 10:25:18 2009 -0700 +++ b/test/java/security/Security/signedfirst/Dyn.sh Thu Aug 06 19:01:59 2009 -0700 @@ -54,6 +54,10 @@ PATHSEP=":" FILESEP="/" ;; + CYGWIN* ) + PATHSEP=";" + FILESEP="/" + ;; Windows* ) PATHSEP=";" FILESEP="\\" @@ -76,7 +80,7 @@ # run the test ${TESTJAVA}${FILESEP}bin${FILESEP}java \ - -classpath ${TESTCLASSES}${PATHSEP}${TESTSRC}${FILESEP}exp.jar \ + -classpath "${TESTCLASSES}${PATHSEP}${TESTSRC}${FILESEP}exp.jar" \ DynSignedProvFirst exit $?
--- a/test/java/security/Security/signedfirst/Static.sh Thu Aug 06 10:25:18 2009 -0700 +++ b/test/java/security/Security/signedfirst/Static.sh Thu Aug 06 19:01:59 2009 -0700 @@ -54,6 +54,10 @@ PATHSEP=":" FILESEP="/" ;; + CYGWIN* ) + PATHSEP=";" + FILESEP="/" + ;; Windows* ) PATHSEP=";" FILESEP="\\" @@ -70,14 +74,14 @@ # compile the test program ${TESTJAVA}${FILESEP}bin${FILESEP}javac \ - -classpath ${TESTCLASSES}${PATHSEP}${TESTSRC}${FILESEP}exp.jar \ + -classpath "${TESTCLASSES}${PATHSEP}${TESTSRC}${FILESEP}exp.jar" \ -d ${TESTCLASSES}${FILESEP} \ ${TESTSRC}${FILESEP}StaticSignedProvFirst.java # run the test cd ${TESTSRC}${FILESEP} ${TESTJAVA}${FILESEP}bin${FILESEP}java \ - -classpath ${TESTCLASSES}${PATHSEP}${TESTSRC}${FILESEP}exp.jar \ + -classpath "${TESTCLASSES}${PATHSEP}${TESTSRC}${FILESEP}exp.jar" \ -Djava.security.properties=file:${TESTSRC}${FILESEP}Static.props \ StaticSignedProvFirst
--- a/test/java/util/Collection/MOAT.java Thu Aug 06 10:25:18 2009 -0700 +++ b/test/java/util/Collection/MOAT.java Thu Aug 06 19:01:59 2009 -0700 @@ -426,6 +426,36 @@ q.poll(); equal(q.size(), 4); checkFunctionalInvariants(q); + if ((q instanceof LinkedBlockingQueue) || + (q instanceof LinkedBlockingDeque) || + (q instanceof ConcurrentLinkedQueue)) { + testQueueIteratorRemove(q); + } + } + + private static void testQueueIteratorRemove(Queue<Integer> q) { + System.err.printf("testQueueIteratorRemove %s%n", + q.getClass().getSimpleName()); + q.clear(); + for (int i = 0; i < 5; i++) + q.add(i); + Iterator<Integer> it = q.iterator(); + check(it.hasNext()); + for (int i = 3; i >= 0; i--) + q.remove(i); + equal(it.next(), 0); + equal(it.next(), 4); + + q.clear(); + for (int i = 0; i < 5; i++) + q.add(i); + it = q.iterator(); + equal(it.next(), 0); + check(it.hasNext()); + for (int i = 1; i < 4; i++) + q.remove(i); + equal(it.next(), 1); + equal(it.next(), 4); } private static void testList(final List<Integer> l) { @@ -451,6 +481,11 @@ } private static void testCollection(Collection<Integer> c) { + try { testCollection1(c); } + catch (Throwable t) { unexpected(t); } + } + + private static void testCollection1(Collection<Integer> c) { System.out.println("\n==> " + c.getClass().getName());
--- a/test/java/util/Formatter/Basic-X.java Thu Aug 06 10:25:18 2009 -0700 +++ b/test/java/util/Formatter/Basic-X.java Thu Aug 06 19:01:59 2009 -0700 @@ -486,6 +486,10 @@ //--------------------------------------------------------------------- tryCatch("%-s", MissingFormatWidthException.class); tryCatch("%--s", DuplicateFormatFlagsException.class); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, 0); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, 0.5f); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, "hello"); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, null); //--------------------------------------------------------------------- // %h
--- a/test/java/util/Formatter/Basic.java Thu Aug 06 10:25:18 2009 -0700 +++ b/test/java/util/Formatter/Basic.java Thu Aug 06 19:01:59 2009 -0700 @@ -25,7 +25,7 @@ * @summary Unit test for formatter * @bug 4906370 4962433 4973103 4989961 5005818 5031150 4970931 4989491 5002937 * 5005104 5007745 5061412 5055180 5066788 5088703 6317248 6318369 6320122 - * 6344623 6369500 6534606 6282094 6286592 6476425 + * 6344623 6369500 6534606 6282094 6286592 6476425 5063507 * * @run shell/timeout=240 Basic.sh */
--- a/test/java/util/Formatter/BasicBigDecimal.java Thu Aug 06 10:25:18 2009 -0700 +++ b/test/java/util/Formatter/BasicBigDecimal.java Thu Aug 06 19:01:59 2009 -0700 @@ -486,6 +486,10 @@ //--------------------------------------------------------------------- tryCatch("%-s", MissingFormatWidthException.class); tryCatch("%--s", DuplicateFormatFlagsException.class); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, 0); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, 0.5f); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, "hello"); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, null); //--------------------------------------------------------------------- // %h
--- a/test/java/util/Formatter/BasicBigInteger.java Thu Aug 06 10:25:18 2009 -0700 +++ b/test/java/util/Formatter/BasicBigInteger.java Thu Aug 06 19:01:59 2009 -0700 @@ -486,6 +486,10 @@ //--------------------------------------------------------------------- tryCatch("%-s", MissingFormatWidthException.class); tryCatch("%--s", DuplicateFormatFlagsException.class); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, 0); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, 0.5f); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, "hello"); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, null); //--------------------------------------------------------------------- // %h
--- a/test/java/util/Formatter/BasicBoolean.java Thu Aug 06 10:25:18 2009 -0700 +++ b/test/java/util/Formatter/BasicBoolean.java Thu Aug 06 19:01:59 2009 -0700 @@ -486,6 +486,10 @@ //--------------------------------------------------------------------- tryCatch("%-s", MissingFormatWidthException.class); tryCatch("%--s", DuplicateFormatFlagsException.class); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, 0); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, 0.5f); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, "hello"); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, null); //--------------------------------------------------------------------- // %h
--- a/test/java/util/Formatter/BasicBooleanObject.java Thu Aug 06 10:25:18 2009 -0700 +++ b/test/java/util/Formatter/BasicBooleanObject.java Thu Aug 06 19:01:59 2009 -0700 @@ -486,6 +486,10 @@ //--------------------------------------------------------------------- tryCatch("%-s", MissingFormatWidthException.class); tryCatch("%--s", DuplicateFormatFlagsException.class); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, 0); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, 0.5f); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, "hello"); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, null); //--------------------------------------------------------------------- // %h
--- a/test/java/util/Formatter/BasicByte.java Thu Aug 06 10:25:18 2009 -0700 +++ b/test/java/util/Formatter/BasicByte.java Thu Aug 06 19:01:59 2009 -0700 @@ -486,6 +486,10 @@ //--------------------------------------------------------------------- tryCatch("%-s", MissingFormatWidthException.class); tryCatch("%--s", DuplicateFormatFlagsException.class); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, 0); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, 0.5f); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, "hello"); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, null); //--------------------------------------------------------------------- // %h
--- a/test/java/util/Formatter/BasicByteObject.java Thu Aug 06 10:25:18 2009 -0700 +++ b/test/java/util/Formatter/BasicByteObject.java Thu Aug 06 19:01:59 2009 -0700 @@ -486,6 +486,10 @@ //--------------------------------------------------------------------- tryCatch("%-s", MissingFormatWidthException.class); tryCatch("%--s", DuplicateFormatFlagsException.class); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, 0); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, 0.5f); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, "hello"); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, null); //--------------------------------------------------------------------- // %h
--- a/test/java/util/Formatter/BasicChar.java Thu Aug 06 10:25:18 2009 -0700 +++ b/test/java/util/Formatter/BasicChar.java Thu Aug 06 19:01:59 2009 -0700 @@ -486,6 +486,10 @@ //--------------------------------------------------------------------- tryCatch("%-s", MissingFormatWidthException.class); tryCatch("%--s", DuplicateFormatFlagsException.class); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, 0); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, 0.5f); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, "hello"); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, null); //--------------------------------------------------------------------- // %h
--- a/test/java/util/Formatter/BasicCharObject.java Thu Aug 06 10:25:18 2009 -0700 +++ b/test/java/util/Formatter/BasicCharObject.java Thu Aug 06 19:01:59 2009 -0700 @@ -486,6 +486,10 @@ //--------------------------------------------------------------------- tryCatch("%-s", MissingFormatWidthException.class); tryCatch("%--s", DuplicateFormatFlagsException.class); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, 0); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, 0.5f); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, "hello"); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, null); //--------------------------------------------------------------------- // %h
--- a/test/java/util/Formatter/BasicDateTime.java Thu Aug 06 10:25:18 2009 -0700 +++ b/test/java/util/Formatter/BasicDateTime.java Thu Aug 06 19:01:59 2009 -0700 @@ -486,6 +486,10 @@ //--------------------------------------------------------------------- tryCatch("%-s", MissingFormatWidthException.class); tryCatch("%--s", DuplicateFormatFlagsException.class); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, 0); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, 0.5f); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, "hello"); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, null); //--------------------------------------------------------------------- // %h
--- a/test/java/util/Formatter/BasicDouble.java Thu Aug 06 10:25:18 2009 -0700 +++ b/test/java/util/Formatter/BasicDouble.java Thu Aug 06 19:01:59 2009 -0700 @@ -486,6 +486,10 @@ //--------------------------------------------------------------------- tryCatch("%-s", MissingFormatWidthException.class); tryCatch("%--s", DuplicateFormatFlagsException.class); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, 0); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, 0.5f); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, "hello"); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, null); //--------------------------------------------------------------------- // %h
--- a/test/java/util/Formatter/BasicDoubleObject.java Thu Aug 06 10:25:18 2009 -0700 +++ b/test/java/util/Formatter/BasicDoubleObject.java Thu Aug 06 19:01:59 2009 -0700 @@ -486,6 +486,10 @@ //--------------------------------------------------------------------- tryCatch("%-s", MissingFormatWidthException.class); tryCatch("%--s", DuplicateFormatFlagsException.class); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, 0); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, 0.5f); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, "hello"); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, null); //--------------------------------------------------------------------- // %h
--- a/test/java/util/Formatter/BasicFloat.java Thu Aug 06 10:25:18 2009 -0700 +++ b/test/java/util/Formatter/BasicFloat.java Thu Aug 06 19:01:59 2009 -0700 @@ -486,6 +486,10 @@ //--------------------------------------------------------------------- tryCatch("%-s", MissingFormatWidthException.class); tryCatch("%--s", DuplicateFormatFlagsException.class); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, 0); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, 0.5f); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, "hello"); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, null); //--------------------------------------------------------------------- // %h
--- a/test/java/util/Formatter/BasicFloatObject.java Thu Aug 06 10:25:18 2009 -0700 +++ b/test/java/util/Formatter/BasicFloatObject.java Thu Aug 06 19:01:59 2009 -0700 @@ -486,6 +486,10 @@ //--------------------------------------------------------------------- tryCatch("%-s", MissingFormatWidthException.class); tryCatch("%--s", DuplicateFormatFlagsException.class); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, 0); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, 0.5f); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, "hello"); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, null); //--------------------------------------------------------------------- // %h
--- a/test/java/util/Formatter/BasicInt.java Thu Aug 06 10:25:18 2009 -0700 +++ b/test/java/util/Formatter/BasicInt.java Thu Aug 06 19:01:59 2009 -0700 @@ -486,6 +486,10 @@ //--------------------------------------------------------------------- tryCatch("%-s", MissingFormatWidthException.class); tryCatch("%--s", DuplicateFormatFlagsException.class); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, 0); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, 0.5f); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, "hello"); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, null); //--------------------------------------------------------------------- // %h
--- a/test/java/util/Formatter/BasicIntObject.java Thu Aug 06 10:25:18 2009 -0700 +++ b/test/java/util/Formatter/BasicIntObject.java Thu Aug 06 19:01:59 2009 -0700 @@ -486,6 +486,10 @@ //--------------------------------------------------------------------- tryCatch("%-s", MissingFormatWidthException.class); tryCatch("%--s", DuplicateFormatFlagsException.class); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, 0); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, 0.5f); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, "hello"); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, null); //--------------------------------------------------------------------- // %h
--- a/test/java/util/Formatter/BasicLong.java Thu Aug 06 10:25:18 2009 -0700 +++ b/test/java/util/Formatter/BasicLong.java Thu Aug 06 19:01:59 2009 -0700 @@ -486,6 +486,10 @@ //--------------------------------------------------------------------- tryCatch("%-s", MissingFormatWidthException.class); tryCatch("%--s", DuplicateFormatFlagsException.class); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, 0); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, 0.5f); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, "hello"); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, null); //--------------------------------------------------------------------- // %h
--- a/test/java/util/Formatter/BasicLongObject.java Thu Aug 06 10:25:18 2009 -0700 +++ b/test/java/util/Formatter/BasicLongObject.java Thu Aug 06 19:01:59 2009 -0700 @@ -486,6 +486,10 @@ //--------------------------------------------------------------------- tryCatch("%-s", MissingFormatWidthException.class); tryCatch("%--s", DuplicateFormatFlagsException.class); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, 0); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, 0.5f); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, "hello"); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, null); //--------------------------------------------------------------------- // %h
--- a/test/java/util/Formatter/BasicShort.java Thu Aug 06 10:25:18 2009 -0700 +++ b/test/java/util/Formatter/BasicShort.java Thu Aug 06 19:01:59 2009 -0700 @@ -486,6 +486,10 @@ //--------------------------------------------------------------------- tryCatch("%-s", MissingFormatWidthException.class); tryCatch("%--s", DuplicateFormatFlagsException.class); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, 0); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, 0.5f); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, "hello"); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, null); //--------------------------------------------------------------------- // %h
--- a/test/java/util/Formatter/BasicShortObject.java Thu Aug 06 10:25:18 2009 -0700 +++ b/test/java/util/Formatter/BasicShortObject.java Thu Aug 06 19:01:59 2009 -0700 @@ -486,6 +486,10 @@ //--------------------------------------------------------------------- tryCatch("%-s", MissingFormatWidthException.class); tryCatch("%--s", DuplicateFormatFlagsException.class); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, 0); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, 0.5f); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, "hello"); + tryCatch("%#s", FormatFlagsConversionMismatchException.class, null); //--------------------------------------------------------------------- // %h
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/java/util/TimSort/ArrayBuilder.java Thu Aug 06 19:01:59 2009 -0700 @@ -0,0 +1,142 @@ +/* + * 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. + * + * 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. + */ + +import java.util.Random; +import java.math.BigInteger; + +public enum ArrayBuilder { + + // These seven are from Tim's paper (listsort.txt) + + RANDOM_INT { + public Object[] build(int len) { + Integer[] result = new Integer[len]; + for (int i = 0; i < len; i++) + result[i] = rnd.nextInt(); + return result; + } + }, + + DESCENDING_INT { + public Object[] build(int len) { + Integer[] result = new Integer[len]; + for (int i = 0; i < len; i++) + result[i] = len - i; + return result; + } + }, + + ASCENDING_INT { + public Object[] build(int len) { + Integer[] result = new Integer[len]; + for (int i = 0; i < len; i++) + result[i] = i; + return result; + } + }, + + ASCENDING_3_RND_EXCH_INT { + public Object[] build(int len) { + Integer[] result = new Integer[len]; + for (int i = 0; i < len; i++) + result[i] = i; + for (int i = 0; i < 3; i++) + swap(result, rnd.nextInt(result.length), + rnd.nextInt(result.length)); + return result; + } + }, + + ASCENDING_10_RND_AT_END_INT { + public Object[] build(int len) { + Integer[] result = new Integer[len]; + int endStart = len - 10; + for (int i = 0; i < endStart; i++) + result[i] = i; + for (int i = endStart; i < len; i++) + result[i] = rnd.nextInt(endStart + 10); + return result; + } + }, + + ALL_EQUAL_INT { + public Object[] build(int len) { + Integer[] result = new Integer[len]; + for (int i = 0; i < len; i++) + result[i] = 666; + return result; + } + }, + + DUPS_GALORE_INT { + public Object[] build(int len) { + Integer[] result = new Integer[len]; + for (int i = 0; i < len; i++) + result[i] = rnd.nextInt(4); + return result; + } + }, + + RANDOM_WITH_DUPS_INT { + public Object[] build(int len) { + Integer[] result = new Integer[len]; + for (int i = 0; i < len; i++) + result[i] = rnd.nextInt(len); + return result; + } + }, + + PSEUDO_ASCENDING_STRING { + public String[] build(int len) { + String[] result = new String[len]; + for (int i = 0; i < len; i++) + result[i] = Integer.toString(i); + return result; + } + }, + + RANDOM_BIGINT { + public BigInteger[] build(int len) { + BigInteger[] result = new BigInteger[len]; + for (int i = 0; i < len; i++) + result[i] = HUGE.add(BigInteger.valueOf(rnd.nextInt(len))); + return result; + } + }; + + public abstract Object[] build(int len); + + public void resetRandom() { + rnd = new Random(666); + } + + private static Random rnd = new Random(666); + + private static void swap(Object[] a, int i, int j) { + Object t = a[i]; + a[i] = a[j]; + a[j] = t; + } + + private static BigInteger HUGE = BigInteger.ONE.shiftLeft(100); +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/java/util/TimSort/README Thu Aug 06 19:01:59 2009 -0700 @@ -0,0 +1,4 @@ +This directory contains benchmark programs used to compare the +performance of the TimSort algorithm against the historic 1997 +implementation of Arrays.sort. Any future benchmarking will require +minor modifications.
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/java/util/TimSort/SortPerf.java Thu Aug 06 19:01:59 2009 -0700 @@ -0,0 +1,66 @@ +/* + * 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. + * + * 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. + */ + +import java.util.Arrays; + +public class SortPerf { + private static final int NUM_SETS = 5; + private static final int[] lengths = { 10, 100, 1000, 10000, 1000000 }; + + // Returns the number of repetitions as a function of the list length + private static int reps(int n) { + return (int) (12000000 / (n * Math.log10(n))); + } + + public static void main(String[] args) { + Sorter.warmup(); + + System.out.print("Strategy,Length"); + for (Sorter sorter : Sorter.values()) + System.out.print("," + sorter); + System.out.println(); + + for (ArrayBuilder ab : ArrayBuilder.values()) { + for (int n : lengths) { + System.out.printf("%s,%d", ab, n); + int reps = reps(n); + Object[] proto = ab.build(n); + for (Sorter sorter : Sorter.values()) { + double minTime = Double.POSITIVE_INFINITY; + for (int set = 0; set < NUM_SETS; set++) { + long startTime = System.nanoTime(); + for (int k = 0; k < reps; k++) { + Object[] a = proto.clone(); + sorter.sort(a); + } + long endTime = System.nanoTime(); + double time = (endTime - startTime) / (1000000. * reps); + minTime = Math.min(minTime, time); + } + System.out.printf(",%5f", minTime); + } + System.out.println(); + } + } + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/java/util/TimSort/Sorter.java Thu Aug 06 19:01:59 2009 -0700 @@ -0,0 +1,55 @@ +/* + * 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. + * + * 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. + */ + +import java.util.*; + +public enum Sorter { + TIMSORT { + public void sort(Object[] array) { + ComparableTimSort.sort(array); + } + }, + MERGESORT { + public void sort(Object[] array) { + Arrays.sort(array); + } + }; + + public abstract void sort(Object[] array); + + public static void warmup() { + System.out.println("start warm up"); + Integer[] gold = new Integer[10000]; + Random random = new java.util.Random(); + for (int i=0; i < gold.length; i++) + gold[i] = random.nextInt(); + + for (int i=0; i < 10000; i++) { + for (Sorter s : values()) { + Integer[] test= gold.clone(); + s.sort(test); + } + } + System.out.println(" end warm up"); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/java/util/concurrent/BlockingQueue/OfferDrainToLoops.java Thu Aug 06 19:01:59 2009 -0700 @@ -0,0 +1,130 @@ +/* + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact 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. + */ + +/* + * This file is available under and governed by the GNU General Public + * License version 2 only, as published by the Free Software Foundation. + * However, the following notice accompanied the original version of this + * file: + * + * Written by Doug Lea with assistance from members of JCP JSR-166 + * Expert Group and released to the public domain, as explained at + * http://creativecommons.org/licenses/publicdomain + */ + +/* + * @test + * @bug 6805775 6815766 + * @summary Test concurrent offer vs. drainTo + */ + +import java.util.*; +import java.util.concurrent.*; + +@SuppressWarnings({"unchecked", "rawtypes"}) +public class OfferDrainToLoops { + void checkNotContainsNull(Iterable it) { + for (Object x : it) + check(x != null); + } + + abstract class CheckedThread extends Thread { + abstract protected void realRun(); + public void run() { + try { realRun(); } catch (Throwable t) { unexpected(t); } + } + { + setDaemon(true); + start(); + } + } + + void test(String[] args) throws Throwable { + test(new LinkedBlockingQueue()); + test(new LinkedBlockingQueue(2000)); + test(new LinkedBlockingDeque()); + test(new LinkedBlockingDeque(2000)); + test(new ArrayBlockingQueue(2000)); + } + + void test(final BlockingQueue q) throws Throwable { + System.out.println(q.getClass().getSimpleName()); + final long testDurationSeconds = 1L; + final long testDurationMillis = testDurationSeconds * 1000L; + final long quittingTimeNanos + = System.nanoTime() + testDurationSeconds * 1000L * 1000L * 1000L; + + Thread offerer = new CheckedThread() { + protected void realRun() { + for (long i = 0; ; i++) { + if ((i % 1024) == 0 && + System.nanoTime() - quittingTimeNanos > 0) + break; + while (! q.offer(i)) + Thread.yield(); + }}}; + + Thread drainer = new CheckedThread() { + protected void realRun() { + for (long i = 0; ; i++) { + if (System.nanoTime() - quittingTimeNanos > 0) + break; + List list = new ArrayList(); + int n = q.drainTo(list); + equal(list.size(), n); + for (int j = 0; j < n - 1; j++) + equal((Long) list.get(j) + 1L, list.get(j + 1)); + Thread.yield(); + }}}; + + Thread scanner = new CheckedThread() { + protected void realRun() { + for (long i = 0; ; i++) { + if (System.nanoTime() - quittingTimeNanos > 0) + break; + checkNotContainsNull(q); + Thread.yield(); + }}}; + + offerer.join(10 * testDurationMillis); + drainer.join(10 * testDurationMillis); + check(! offerer.isAlive()); + check(! drainer.isAlive()); + } + + //--------------------- Infrastructure --------------------------- + volatile int passed = 0, failed = 0; + void pass() {passed++;} + void fail() {failed++; Thread.dumpStack();} + void fail(String msg) {System.err.println(msg); fail();} + void unexpected(Throwable t) {failed++; t.printStackTrace();} + void check(boolean cond) {if (cond) pass(); else fail();} + void equal(Object x, Object y) { + if (x == null ? y == null : x.equals(y)) pass(); + else fail(x + " not equal to " + y);} + public static void main(String[] args) throws Throwable { + new OfferDrainToLoops().instanceMain(args);} + public void instanceMain(String[] args) throws Throwable { + try {test(args);} catch (Throwable t) {unexpected(t);} + System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed); + if (failed > 0) throw new AssertionError("Some tests failed");} +}
--- a/test/java/util/concurrent/ConcurrentLinkedQueue/ConcurrentQueueLoops.java Thu Aug 06 10:25:18 2009 -0700 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,146 +0,0 @@ -/* - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact 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. - */ - -/* - * This file is available under and governed by the GNU General Public - * License version 2 only, as published by the Free Software Foundation. - * However, the following notice accompanied the original version of this - * file: - * - * Written by Doug Lea with assistance from members of JCP JSR-166 - * Expert Group and released to the public domain, as explained at - * http://creativecommons.org/licenses/publicdomain - */ - -/* - * @test - * @bug 4486658 - * @compile -source 1.5 ConcurrentQueueLoops.java - * @run main/timeout=230 ConcurrentQueueLoops - * @summary Checks that a set of threads can repeatedly get and modify items - */ - -import java.util.*; -import java.util.concurrent.*; -import java.util.concurrent.atomic.*; - -public class ConcurrentQueueLoops { - static final ExecutorService pool = Executors.newCachedThreadPool(); - static AtomicInteger totalItems; - static boolean print = false; - - public static void main(String[] args) throws Exception { - int maxStages = 8; - int items = 100000; - - if (args.length > 0) - maxStages = Integer.parseInt(args[0]); - - print = false; - System.out.println("Warmup..."); - oneRun(1, items); - Thread.sleep(100); - oneRun(1, items); - Thread.sleep(100); - print = true; - - for (int i = 1; i <= maxStages; i += (i+1) >>> 1) { - oneRun(i, items); - } - pool.shutdown(); - if (! pool.awaitTermination(Long.MAX_VALUE, TimeUnit.NANOSECONDS)) - throw new Error(); - } - - static class Stage implements Callable<Integer> { - final Queue<Integer> queue; - final CyclicBarrier barrier; - int items; - Stage (Queue<Integer> q, CyclicBarrier b, int items) { - queue = q; - barrier = b; - this.items = items; - } - - public Integer call() { - // Repeatedly take something from queue if possible, - // transform it, and put back in. - try { - barrier.await(); - int l = 4321; - int takes = 0; - for (;;) { - Integer item = queue.poll(); - if (item != null) { - ++takes; - l = LoopHelpers.compute2(item.intValue()); - } - else if (takes != 0) { - totalItems.getAndAdd(-takes); - takes = 0; - } - else if (totalItems.get() <= 0) - break; - l = LoopHelpers.compute1(l); - if (items > 0) { - --items; - queue.offer(new Integer(l)); - } - else if ( (l & (3 << 5)) == 0) // spinwait - Thread.sleep(1); - } - return new Integer(l); - } - catch (Exception ie) { - ie.printStackTrace(); - throw new Error("Call loop failed"); - } - } - } - - static void oneRun(int n, int items) throws Exception { - Queue<Integer> q = new ConcurrentLinkedQueue<Integer>(); - LoopHelpers.BarrierTimer timer = new LoopHelpers.BarrierTimer(); - CyclicBarrier barrier = new CyclicBarrier(n + 1, timer); - totalItems = new AtomicInteger(n * items); - ArrayList<Future<Integer>> results = new ArrayList<Future<Integer>>(n); - for (int i = 0; i < n; ++i) - results.add(pool.submit(new Stage(q, barrier, items))); - - if (print) - System.out.print("Threads: " + n + "\t:"); - barrier.await(); - int total = 0; - for (int i = 0; i < n; ++i) { - Future<Integer> f = results.get(i); - Integer r = f.get(); - total += r.intValue(); - } - long endTime = System.nanoTime(); - long time = endTime - timer.startTime; - if (print) - System.out.println(LoopHelpers.rightJustify(time / (items * n)) + " ns per item"); - if (total == 0) // avoid overoptimization - System.out.println("useless result: " + total); - - } -}
--- a/test/java/util/concurrent/ConcurrentLinkedQueue/LoopHelpers.java Thu Aug 06 10:25:18 2009 -0700 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,129 +0,0 @@ -/* - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact 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. - */ - -/* - * This file is available under and governed by the GNU General Public - * License version 2 only, as published by the Free Software Foundation. - * However, the following notice accompanied the original version of this - * file: - * - * Written by Doug Lea with assistance from members of JCP JSR-166 - * Expert Group and released to the public domain, as explained at - * http://creativecommons.org/licenses/publicdomain - */ - -/** - * Misc utilities in JSR166 performance tests - */ - -import java.util.concurrent.*; -import java.util.concurrent.atomic.*; - -class LoopHelpers { - - // Some mindless computation to do between synchronizations... - - /** - * generates 32 bit pseudo-random numbers. - * Adapted from http://www.snippets.org - */ - public static int compute1(int x) { - int lo = 16807 * (x & 0xFFFF); - int hi = 16807 * (x >>> 16); - lo += (hi & 0x7FFF) << 16; - if ((lo & 0x80000000) != 0) { - lo &= 0x7fffffff; - ++lo; - } - lo += hi >>> 15; - if (lo == 0 || (lo & 0x80000000) != 0) { - lo &= 0x7fffffff; - ++lo; - } - return lo; - } - - /** - * Computes a linear congruential random number a random number - * of times. - */ - public static int compute2(int x) { - int loops = (x >>> 4) & 7; - while (loops-- > 0) { - x = (x * 2147483647) % 16807; - } - return x; - } - - /** - * An actually useful random number generator, but unsynchronized. - * Basically same as java.util.Random. - */ - public static class SimpleRandom { - private final static long multiplier = 0x5DEECE66DL; - private final static long addend = 0xBL; - private final static long mask = (1L << 48) - 1; - static final AtomicLong seq = new AtomicLong(1); - private long seed = System.nanoTime() + seq.getAndIncrement(); - - public void setSeed(long s) { - seed = s; - } - - public int next() { - long nextseed = (seed * multiplier + addend) & mask; - seed = nextseed; - return ((int)(nextseed >>> 17)) & 0x7FFFFFFF; - } - } - - public static class BarrierTimer implements Runnable { - public volatile long startTime; - public volatile long endTime; - public void run() { - long t = System.nanoTime(); - if (startTime == 0) - startTime = t; - else - endTime = t; - } - public void clear() { - startTime = 0; - endTime = 0; - } - public long getTime() { - return endTime - startTime; - } - } - - public static String rightJustify(long n) { - // There's probably a better way to do this... - String field = " "; - String num = Long.toString(n); - if (num.length() >= field.length()) - return num; - StringBuffer b = new StringBuffer(field); - b.replace(b.length()-num.length(), b.length(), num); - return b.toString(); - } - -}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/java/util/concurrent/ConcurrentQueues/ConcurrentQueueLoops.java Thu Aug 06 19:01:59 2009 -0700 @@ -0,0 +1,198 @@ +/* + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact 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. + */ + +/* + * This file is available under and governed by the GNU General Public + * License version 2 only, as published by the Free Software Foundation. + * However, the following notice accompanied the original version of this + * file: + * + * Written by Doug Lea with assistance from members of JCP JSR-166 + * Expert Group and released to the public domain, as explained at + * http://creativecommons.org/licenses/publicdomain + */ + +/* + * @test + * @bug 4486658 6785442 + * @run main ConcurrentQueueLoops 8 123456 + * @summary Checks that a set of threads can repeatedly get and modify items + */ + +import java.util.*; +import java.util.concurrent.*; +import java.util.concurrent.atomic.*; + +public class ConcurrentQueueLoops { + ExecutorService pool; + AtomicInteger totalItems; + boolean print; + + // Suitable for benchmarking. Overriden by args[0] for testing. + int maxStages = 20; + + // Suitable for benchmarking. Overriden by args[1] for testing. + int items = 1024 * 1024; + + Collection<Queue<Integer>> concurrentQueues() { + List<Queue<Integer>> queues = new ArrayList<Queue<Integer>>(); + queues.add(new ConcurrentLinkedQueue<Integer>()); + queues.add(new ArrayBlockingQueue<Integer>(items, false)); + //queues.add(new ArrayBlockingQueue<Integer>(count, true)); + queues.add(new LinkedBlockingQueue<Integer>()); + queues.add(new LinkedBlockingDeque<Integer>()); + + try { + queues.add((Queue<Integer>) + Class.forName("java.util.concurrent.LinkedTransferQueue") + .newInstance()); + } catch (IllegalAccessException e) { + } catch (InstantiationException e) { + } catch (ClassNotFoundException e) { + // OK; not yet added to JDK + } + + // Following additional implementations are available from: + // http://gee.cs.oswego.edu/dl/concurrency-interest/index.html + // queues.add(new LinkedTransferQueue<Integer>()); + // queues.add(new SynchronizedLinkedListQueue<Integer>()); + + // Avoid "first fast, second slow" benchmark effect. + Collections.shuffle(queues); + return queues; + } + + void test(String[] args) throws Throwable { + if (args.length > 0) + maxStages = Integer.parseInt(args[0]); + if (args.length > 1) + items = Integer.parseInt(args[1]); + + for (Queue<Integer> queue : concurrentQueues()) + test(queue); + } + + void test(final Queue<Integer> q) throws Throwable { + System.out.println(q.getClass().getSimpleName()); + pool = Executors.newCachedThreadPool(); + print = false; + + print = false; + System.out.println("Warmup..."); + oneRun(1, items, q); + //Thread.sleep(100); + oneRun(3, items, q); + Thread.sleep(100); + print = true; + + for (int i = 1; i <= maxStages; i += (i+1) >>> 1) { + oneRun(i, items, q); + } + pool.shutdown(); + check(pool.awaitTermination(Long.MAX_VALUE, TimeUnit.NANOSECONDS)); + } + + class Stage implements Callable<Integer> { + final Queue<Integer> queue; + final CyclicBarrier barrier; + int items; + Stage (Queue<Integer> q, CyclicBarrier b, int items) { + queue = q; + barrier = b; + this.items = items; + } + + public Integer call() { + // Repeatedly take something from queue if possible, + // transform it, and put back in. + try { + barrier.await(); + int l = 4321; + int takes = 0; + for (;;) { + Integer item = queue.poll(); + if (item != null) { + ++takes; + l = LoopHelpers.compute2(item.intValue()); + } + else if (takes != 0) { + totalItems.getAndAdd(-takes); + takes = 0; + } + else if (totalItems.get() <= 0) + break; + l = LoopHelpers.compute1(l); + if (items > 0) { + --items; + queue.offer(new Integer(l)); + } + else if ( (l & (3 << 5)) == 0) // spinwait + Thread.sleep(1); + } + return new Integer(l); + } + catch (Throwable t) { unexpected(t); return null; } + } + } + + void oneRun(int n, int items, final Queue<Integer> q) throws Exception { + LoopHelpers.BarrierTimer timer = new LoopHelpers.BarrierTimer(); + CyclicBarrier barrier = new CyclicBarrier(n + 1, timer); + totalItems = new AtomicInteger(n * items); + ArrayList<Future<Integer>> results = new ArrayList<Future<Integer>>(n); + for (int i = 0; i < n; ++i) + results.add(pool.submit(new Stage(q, barrier, items))); + + if (print) + System.out.print("Threads: " + n + "\t:"); + barrier.await(); + int total = 0; + for (int i = 0; i < n; ++i) { + Future<Integer> f = results.get(i); + Integer r = f.get(); + total += r.intValue(); + } + long endTime = System.nanoTime(); + long time = endTime - timer.startTime; + if (print) + System.out.println(LoopHelpers.rightJustify(time / (items * n)) + " ns per item"); + if (total == 0) // avoid overoptimization + System.out.println("useless result: " + total); + } + + //--------------------- Infrastructure --------------------------- + volatile int passed = 0, failed = 0; + void pass() {passed++;} + void fail() {failed++; Thread.dumpStack();} + void fail(String msg) {System.err.println(msg); fail();} + void unexpected(Throwable t) {failed++; t.printStackTrace();} + void check(boolean cond) {if (cond) pass(); else fail();} + void equal(Object x, Object y) { + if (x == null ? y == null : x.equals(y)) pass(); + else fail(x + " not equal to " + y);} + public static void main(String[] args) throws Throwable { + new ConcurrentQueueLoops().instanceMain(args);} + public void instanceMain(String[] args) throws Throwable { + try {test(args);} catch (Throwable t) {unexpected(t);} + System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed); + if (failed > 0) throw new AssertionError("Some tests failed");} +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/java/util/concurrent/ConcurrentQueues/GCRetention.java Thu Aug 06 19:01:59 2009 -0700 @@ -0,0 +1,165 @@ +/* + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact 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. + */ + +/* + * This file is available under and governed by the GNU General Public + * License version 2 only, as published by the Free Software Foundation. + * However, the following notice accompanied the original version of this + * file: + * + * Written by Doug Lea with assistance from members of JCP JSR-166 + * Expert Group and released to the public domain, as explained at + * http://creativecommons.org/licenses/publicdomain + */ +/* + * @test + * @bug 6785442 + * @summary Benchmark that tries to GC-tenure head, followed by + * many add/remove operations. + * @run main GCRetention 12345 + */ + +import java.util.concurrent.ArrayBlockingQueue; +import java.util.concurrent.ConcurrentHashMap; +import java.util.concurrent.ConcurrentLinkedQueue; +import java.util.concurrent.LinkedBlockingQueue; +import java.util.concurrent.LinkedBlockingDeque; +import java.util.concurrent.PriorityBlockingQueue; +import java.util.LinkedList; +import java.util.PriorityQueue; +import java.util.ArrayList; +import java.util.Collection; +import java.util.Collections; +import java.util.List; +import java.util.Queue; +import java.util.Map; + +public class GCRetention { + // Suitable for benchmarking. Overriden by args[0] for testing. + int count = 1024 * 1024; + + final Map<String,String> results = new ConcurrentHashMap<String,String>(); + + Collection<Queue<Boolean>> queues() { + List<Queue<Boolean>> queues = new ArrayList<Queue<Boolean>>(); + queues.add(new ConcurrentLinkedQueue<Boolean>()); + queues.add(new ArrayBlockingQueue<Boolean>(count, false)); + queues.add(new ArrayBlockingQueue<Boolean>(count, true)); + queues.add(new LinkedBlockingQueue<Boolean>()); + queues.add(new LinkedBlockingDeque<Boolean>()); + queues.add(new PriorityBlockingQueue<Boolean>()); + queues.add(new PriorityQueue<Boolean>()); + queues.add(new LinkedList<Boolean>()); + + try { + queues.add((Queue<Boolean>) + Class.forName("java.util.concurrent.LinkedTransferQueue") + .newInstance()); + } catch (IllegalAccessException e) { + } catch (InstantiationException e) { + } catch (ClassNotFoundException e) { + // OK; not yet added to JDK + } + + // Following additional implementations are available from: + // http://gee.cs.oswego.edu/dl/concurrency-interest/index.html + // queues.add(new LinkedTransferQueue<Boolean>()); + // queues.add(new SynchronizedLinkedListQueue<Boolean>()); + + // Avoid "first fast, second slow" benchmark effect. + Collections.shuffle(queues); + return queues; + } + + void prettyPrintResults() { + List<String> classNames = new ArrayList<String>(results.keySet()); + Collections.sort(classNames); + int maxClassNameLength = 0; + int maxNanosLength = 0; + for (String name : classNames) { + if (maxClassNameLength < name.length()) + maxClassNameLength = name.length(); + if (maxNanosLength < results.get(name).length()) + maxNanosLength = results.get(name).length(); + } + String format = String.format("%%%ds %%%ds nanos/item%%n", + maxClassNameLength, maxNanosLength); + for (String name : classNames) + System.out.printf(format, name, results.get(name)); + } + + void test(String[] args) { + if (args.length > 0) + count = Integer.valueOf(args[0]); + // Warmup + for (Queue<Boolean> queue : queues()) + test(queue); + results.clear(); + for (Queue<Boolean> queue : queues()) + test(queue); + + prettyPrintResults(); + } + + void test(Queue<Boolean> q) { + long t0 = System.nanoTime(); + for (int i = 0; i < count; i++) + check(q.add(Boolean.TRUE)); + System.gc(); + System.gc(); + Boolean x; + while ((x = q.poll()) != null) + equal(x, Boolean.TRUE); + check(q.isEmpty()); + + for (int i = 0; i < 10 * count; i++) { + for (int k = 0; k < 3; k++) + check(q.add(Boolean.TRUE)); + for (int k = 0; k < 3; k++) + if (q.poll() != Boolean.TRUE) + fail(); + } + check(q.isEmpty()); + + String className = q.getClass().getSimpleName(); + long elapsed = System.nanoTime() - t0; + int nanos = (int) ((double) elapsed / (10 * 3 * count)); + results.put(className, String.valueOf(nanos)); + } + + //--------------------- Infrastructure --------------------------- + volatile int passed = 0, failed = 0; + void pass() {passed++;} + void fail() {failed++; Thread.dumpStack();} + void fail(String msg) {System.err.println(msg); fail();} + void unexpected(Throwable t) {failed++; t.printStackTrace();} + void check(boolean cond) {if (cond) pass(); else fail();} + void equal(Object x, Object y) { + if (x == null ? y == null : x.equals(y)) pass(); + else fail(x + " not equal to " + y);} + public static void main(String[] args) throws Throwable { + new GCRetention().instanceMain(args);} + public void instanceMain(String[] args) throws Throwable { + try {test(args);} catch (Throwable t) {unexpected(t);} + System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed); + if (failed > 0) throw new AssertionError("Some tests failed");} +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/java/util/concurrent/ConcurrentQueues/IteratorWeakConsistency.java Thu Aug 06 19:01:59 2009 -0700 @@ -0,0 +1,93 @@ +/* + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact 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. + */ + +/* + * This file is available under and governed by the GNU General Public + * License version 2 only, as published by the Free Software Foundation. + * However, the following notice accompanied the original version of this + * file: + * + * Written by Doug Lea with assistance from members of JCP JSR-166 + * Expert Group and released to the public domain, as explained at + * http://creativecommons.org/licenses/publicdomain + */ + +import java.util.*; +import java.util.concurrent.*; + +/* + * @test + * @bug 6805775 6815766 + * @summary Check weak consistency of concurrent queue iterators + */ + +@SuppressWarnings({"unchecked", "rawtypes"}) +public class IteratorWeakConsistency { + + void test(String[] args) throws Throwable { + test(new LinkedBlockingQueue()); + test(new LinkedBlockingQueue(20)); + test(new LinkedBlockingDeque()); + test(new LinkedBlockingDeque(20)); + test(new ConcurrentLinkedQueue()); + // Other concurrent queues (e.g. ArrayBlockingQueue) do not + // currently have weakly consistent iterators. + // test(new ArrayBlockingQueue(20)); + } + + void test(Queue q) throws Throwable { + // TODO: make this more general + for (int i = 0; i < 10; i++) + q.add(i); + Iterator it = q.iterator(); + q.poll(); + q.poll(); + q.poll(); + q.remove(7); + List list = new ArrayList(); + while (it.hasNext()) + list.add(it.next()); + equal(list, Arrays.asList(0, 3, 4, 5, 6, 8, 9)); + check(! list.contains(null)); + System.out.printf("%s: %s%n", + q.getClass().getSimpleName(), + list); + } + + //--------------------- Infrastructure --------------------------- + volatile int passed = 0, failed = 0; + void pass() {passed++;} + void fail() {failed++; Thread.dumpStack();} + void fail(String msg) {System.err.println(msg); fail();} + void unexpected(Throwable t) {failed++; t.printStackTrace();} + void check(boolean cond) {if (cond) pass(); else fail();} + void equal(Object x, Object y) { + if (x == null ? y == null : x.equals(y)) pass(); + else fail(x + " not equal to " + y);} + static Class<?> thisClass = new Object(){}.getClass().getEnclosingClass(); + public static void main(String[] args) throws Throwable { + new IteratorWeakConsistency().instanceMain(args);} + public void instanceMain(String[] args) throws Throwable { + try {test(args);} catch (Throwable t) {unexpected(t);} + System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed); + if (failed > 0) throw new AssertionError("Some tests failed");} +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/java/util/concurrent/ConcurrentQueues/LoopHelpers.java Thu Aug 06 19:01:59 2009 -0700 @@ -0,0 +1,129 @@ +/* + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact 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. + */ + +/* + * This file is available under and governed by the GNU General Public + * License version 2 only, as published by the Free Software Foundation. + * However, the following notice accompanied the original version of this + * file: + * + * Written by Doug Lea with assistance from members of JCP JSR-166 + * Expert Group and released to the public domain, as explained at + * http://creativecommons.org/licenses/publicdomain + */ + +/** + * Misc utilities in JSR166 performance tests + */ + +import java.util.concurrent.*; +import java.util.concurrent.atomic.*; + +class LoopHelpers { + + // Some mindless computation to do between synchronizations... + + /** + * generates 32 bit pseudo-random numbers. + * Adapted from http://www.snippets.org + */ + public static int compute1(int x) { + int lo = 16807 * (x & 0xFFFF); + int hi = 16807 * (x >>> 16); + lo += (hi & 0x7FFF) << 16; + if ((lo & 0x80000000) != 0) { + lo &= 0x7fffffff; + ++lo; + } + lo += hi >>> 15; + if (lo == 0 || (lo & 0x80000000) != 0) { + lo &= 0x7fffffff; + ++lo; + } + return lo; + } + + /** + * Computes a linear congruential random number a random number + * of times. + */ + public static int compute2(int x) { + int loops = (x >>> 4) & 7; + while (loops-- > 0) { + x = (x * 2147483647) % 16807; + } + return x; + } + + /** + * An actually useful random number generator, but unsynchronized. + * Basically same as java.util.Random. + */ + public static class SimpleRandom { + private final static long multiplier = 0x5DEECE66DL; + private final static long addend = 0xBL; + private final static long mask = (1L << 48) - 1; + static final AtomicLong seq = new AtomicLong(1); + private long seed = System.nanoTime() + seq.getAndIncrement(); + + public void setSeed(long s) { + seed = s; + } + + public int next() { + long nextseed = (seed * multiplier + addend) & mask; + seed = nextseed; + return ((int)(nextseed >>> 17)) & 0x7FFFFFFF; + } + } + + public static class BarrierTimer implements Runnable { + public volatile long startTime; + public volatile long endTime; + public void run() { + long t = System.nanoTime(); + if (startTime == 0) + startTime = t; + else + endTime = t; + } + public void clear() { + startTime = 0; + endTime = 0; + } + public long getTime() { + return endTime - startTime; + } + } + + public static String rightJustify(long n) { + // There's probably a better way to do this... + String field = " "; + String num = Long.toString(n); + if (num.length() >= field.length()) + return num; + StringBuffer b = new StringBuffer(field); + b.replace(b.length()-num.length(), b.length(), num); + return b.toString(); + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/java/util/concurrent/ConcurrentQueues/RemovePollRace.java Thu Aug 06 19:01:59 2009 -0700 @@ -0,0 +1,230 @@ +/* + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact 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. + */ + +/* + * This file is available under and governed by the GNU General Public + * License version 2 only, as published by the Free Software Foundation. + * However, the following notice accompanied the original version of this + * file: + * + * Written by Doug Lea with assistance from members of JCP JSR-166 + * Expert Group and released to the public domain, as explained at + * http://creativecommons.org/licenses/publicdomain + */ + +/* + * @test + * @bug 6785442 + * @summary Checks race between poll and remove(Object), while + * occasionally moonlighting as a microbenchmark. + * @run main RemovePollRace 12345 + */ + +import java.util.concurrent.ArrayBlockingQueue; +import java.util.concurrent.ConcurrentHashMap; +import java.util.concurrent.ConcurrentLinkedQueue; +import java.util.concurrent.CountDownLatch; +import java.util.concurrent.LinkedBlockingDeque; +import java.util.concurrent.LinkedBlockingQueue; +import java.util.concurrent.atomic.AtomicLong; +import java.util.ArrayList; +import java.util.Collection; +import java.util.Collections; +import java.util.List; +import java.util.Queue; +import java.util.Map; + +public class RemovePollRace { + // Suitable for benchmarking. Overriden by args[0] for testing. + int count = 1024 * 1024; + + final Map<String,String> results = new ConcurrentHashMap<String,String>(); + + Collection<Queue<Boolean>> concurrentQueues() { + List<Queue<Boolean>> queues = new ArrayList<Queue<Boolean>>(); + queues.add(new ConcurrentLinkedQueue<Boolean>()); + queues.add(new ArrayBlockingQueue<Boolean>(count, false)); + queues.add(new ArrayBlockingQueue<Boolean>(count, true)); + queues.add(new LinkedBlockingQueue<Boolean>()); + queues.add(new LinkedBlockingDeque<Boolean>()); + + try { + queues.add((Queue<Boolean>) + Class.forName("java.util.concurrent.LinkedTransferQueue") + .newInstance()); + } catch (IllegalAccessException e) { + } catch (InstantiationException e) { + } catch (ClassNotFoundException e) { + // OK; not yet added to JDK + } + + // Following additional implementations are available from: + // http://gee.cs.oswego.edu/dl/concurrency-interest/index.html + // queues.add(new LinkedTransferQueue<Boolean>()); + // queues.add(new SynchronizedLinkedListQueue<Boolean>()); + + // Avoid "first fast, second slow" benchmark effect. + Collections.shuffle(queues); + return queues; + } + + void prettyPrintResults() { + List<String> classNames = new ArrayList<String>(results.keySet()); + Collections.sort(classNames); + int maxClassNameLength = 0; + int maxNanosLength = 0; + for (String name : classNames) { + if (maxClassNameLength < name.length()) + maxClassNameLength = name.length(); + if (maxNanosLength < results.get(name).length()) + maxNanosLength = results.get(name).length(); + } + String format = String.format("%%%ds %%%ds nanos/item%%n", + maxClassNameLength, maxNanosLength); + for (String name : classNames) + System.out.printf(format, name, results.get(name)); + } + + void test(String[] args) throws Throwable { + if (args.length > 0) + count = Integer.valueOf(args[0]); + // Warmup + for (Queue<Boolean> queue : concurrentQueues()) + test(queue); + results.clear(); + for (Queue<Boolean> queue : concurrentQueues()) + test(queue); + + prettyPrintResults(); + } + + void await(CountDownLatch latch) { + try { latch.await(); } + catch (InterruptedException e) { unexpected(e); } + } + + void test(final Queue<Boolean> q) throws Throwable { + long t0 = System.nanoTime(); + final int SPINS = 5; + final AtomicLong removes = new AtomicLong(0); + final AtomicLong polls = new AtomicLong(0); + final int adderCount = + Math.max(1, Runtime.getRuntime().availableProcessors() / 4); + final int removerCount = + Math.max(1, Runtime.getRuntime().availableProcessors() / 4); + final int pollerCount = removerCount; + final int threadCount = adderCount + removerCount + pollerCount; + final CountDownLatch startingGate = new CountDownLatch(1); + final CountDownLatch addersDone = new CountDownLatch(adderCount); + final Runnable remover = new Runnable() { + public void run() { + await(startingGate); + int spins = 0; + for (;;) { + boolean quittingTime = (addersDone.getCount() == 0); + if (q.remove(Boolean.TRUE)) + removes.getAndIncrement(); + else if (quittingTime) + break; + else if (++spins > SPINS) { + Thread.yield(); + spins = 0; + }}}}; + final Runnable poller = new Runnable() { + public void run() { + await(startingGate); + int spins = 0; + for (;;) { + boolean quittingTime = (addersDone.getCount() == 0); + if (q.poll() == Boolean.TRUE) + polls.getAndIncrement(); + else if (quittingTime) + break; + else if (++spins > SPINS) { + Thread.yield(); + spins = 0; + }}}}; + final Runnable adder = new Runnable() { + public void run() { + await(startingGate); + for (int i = 0; i < count; i++) { + for (;;) { + try { q.add(Boolean.TRUE); break; } + catch (IllegalStateException e) { Thread.yield(); } + } + } + addersDone.countDown(); + }}; + + final List<Thread> adders = new ArrayList<Thread>(); + final List<Thread> removers = new ArrayList<Thread>(); + final List<Thread> pollers = new ArrayList<Thread>(); + for (int i = 0; i < adderCount; i++) + adders.add(checkedThread(adder)); + for (int i = 0; i < removerCount; i++) + removers.add(checkedThread(remover)); + for (int i = 0; i < pollerCount; i++) + pollers.add(checkedThread(poller)); + + final List<Thread> allThreads = new ArrayList<Thread>(); + allThreads.addAll(removers); + allThreads.addAll(pollers); + allThreads.addAll(adders); + + for (Thread t : allThreads) + t.start(); + startingGate.countDown(); + for (Thread t : allThreads) + t.join(); + + String className = q.getClass().getSimpleName(); + long elapsed = System.nanoTime() - t0; + int nanos = (int) ((double) elapsed / (adderCount * count)); + results.put(className, String.valueOf(nanos)); + if (removes.get() + polls.get() != adderCount * count) { + String msg = String.format + ("class=%s removes=%s polls=%d count=%d", + className, removes.get(), polls.get(), count); + fail(msg); + } + } + + //--------------------- Infrastructure --------------------------- + volatile int passed = 0, failed = 0; + void pass() {passed++;} + void fail() {failed++; Thread.dumpStack();} + void fail(String msg) {System.err.println(msg); fail();} + void unexpected(Throwable t) {failed++; t.printStackTrace();} + void check(boolean cond) {if (cond) pass(); else fail();} + void equal(Object x, Object y) { + if (x == null ? y == null : x.equals(y)) pass(); + else fail(x + " not equal to " + y);} + public static void main(String[] args) throws Throwable { + new RemovePollRace().instanceMain(args);} + public void instanceMain(String[] args) throws Throwable { + try {test(args);} catch (Throwable t) {unexpected(t);} + System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed); + if (failed > 0) throw new AssertionError("Some tests failed");} + Thread checkedThread(final Runnable r) { + return new Thread() {public void run() { + try {r.run();} catch (Throwable t) {unexpected(t);}}};} +}
--- a/test/java/util/concurrent/LinkedBlockingQueue/OfferRemoveLoops.java Thu Aug 06 10:25:18 2009 -0700 +++ b/test/java/util/concurrent/LinkedBlockingQueue/OfferRemoveLoops.java Thu Aug 06 19:01:59 2009 -0700 @@ -28,62 +28,74 @@ * @author Martin Buchholz */ +import java.util.*; import java.util.concurrent.*; public class OfferRemoveLoops { - private static void realMain(String[] args) throws Throwable { + void test(String[] args) throws Throwable { testQueue(new LinkedBlockingQueue<String>(10)); testQueue(new LinkedBlockingQueue<String>()); testQueue(new LinkedBlockingDeque<String>(10)); testQueue(new LinkedBlockingDeque<String>()); testQueue(new ArrayBlockingQueue<String>(10)); testQueue(new PriorityBlockingQueue<String>(10)); + testQueue(new ConcurrentLinkedQueue<String>()); } - private abstract static class ControlledThread extends Thread { + abstract class CheckedThread extends Thread { abstract protected void realRun(); public void run() { try { realRun(); } catch (Throwable t) { unexpected(t); } } } - private static void testQueue(final BlockingQueue<String> q) throws Throwable { - System.out.println(q.getClass()); - final int count = 10000; - final long quittingTime = System.nanoTime() + 1L * 1000L * 1000L * 1000L; - Thread t1 = new ControlledThread() { - protected void realRun() { - for (int i = 0, j = 0; i < count; i++) - while (! q.remove(String.valueOf(i)) - && System.nanoTime() - quittingTime < 0) - Thread.yield();}}; - Thread t2 = new ControlledThread() { - protected void realRun() { - for (int i = 0, j = 0; i < count; i++) - while (! q.offer(String.valueOf(i)) - && System.nanoTime() - quittingTime < 0) - Thread.yield();}}; + void testQueue(final Queue<String> q) throws Throwable { + System.out.println(q.getClass().getSimpleName()); + final int count = 1000 * 1000; + final long testDurationSeconds = 1L; + final long testDurationMillis = testDurationSeconds * 1000L; + final long quittingTimeNanos + = System.nanoTime() + testDurationSeconds * 1000L * 1000L * 1000L; + Thread t1 = new CheckedThread() { + protected void realRun() { + for (int i = 0; i < count; i++) { + if ((i % 1024) == 0 && + System.nanoTime() - quittingTimeNanos > 0) + return; + while (! q.remove(String.valueOf(i))) + Thread.yield(); + }}}; + Thread t2 = new CheckedThread() { + protected void realRun() { + for (int i = 0; i < count; i++) { + if ((i % 1024) == 0 && + System.nanoTime() - quittingTimeNanos > 0) + return; + while (! q.offer(String.valueOf(i))) + Thread.yield(); + }}}; t1.setDaemon(true); t2.setDaemon(true); t1.start(); t2.start(); - t1.join(10000); t2.join(10000); + t1.join(10 * testDurationMillis); + t2.join(10 * testDurationMillis); check(! t1.isAlive()); check(! t2.isAlive()); } //--------------------- Infrastructure --------------------------- - static volatile int passed = 0, failed = 0; - static void pass() { passed++; } - static void fail() { failed++; Thread.dumpStack(); } - static void unexpected(Throwable t) { failed++; t.printStackTrace(); } - static void check(boolean cond) { if (cond) pass(); else fail(); } - static void equal(Object x, Object y) { + volatile int passed = 0, failed = 0; + void pass() {passed++;} + void fail() {failed++; Thread.dumpStack();} + void fail(String msg) {System.err.println(msg); fail();} + void unexpected(Throwable t) {failed++; t.printStackTrace();} + void check(boolean cond) {if (cond) pass(); else fail();} + void equal(Object x, Object y) { if (x == null ? y == null : x.equals(y)) pass(); - else {System.out.println(x + " not equal to " + y); fail(); }} - + else fail(x + " not equal to " + y);} public static void main(String[] args) throws Throwable { - try { realMain(args); } catch (Throwable t) { unexpected(t); } - + new OfferRemoveLoops().instanceMain(args);} + public void instanceMain(String[] args) throws Throwable { + try {test(args);} catch (Throwable t) {unexpected(t);} System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed); - if (failed > 0) throw new Exception("Some tests failed"); - } + if (failed > 0) throw new AssertionError("Some tests failed");} }
--- a/test/javax/crypto/SecretKeyFactory/FailOverTest.sh Thu Aug 06 10:25:18 2009 -0700 +++ b/test/javax/crypto/SecretKeyFactory/FailOverTest.sh Thu Aug 06 19:01:59 2009 -0700 @@ -56,6 +56,11 @@ PS=":" FS="/" ;; + CYGWIN* ) + NULL=/dev/null + PS=";" + FS="/" + ;; Windows* ) NULL=NUL PS=";" @@ -69,7 +74,7 @@ ${TESTJAVA}${FS}bin${FS}javac \ -d . \ - -classpath ${TESTSRC}${FS}P1.jar${PS}${TESTSRC}${FS}P2.jar \ + -classpath "${TESTSRC}${FS}P1.jar${PS}${TESTSRC}${FS}P2.jar" \ ${TESTSRC}${FS}FailOverTest.java if [ $? -ne 0 ]; then @@ -77,7 +82,7 @@ fi ${TESTJAVA}${FS}bin${FS}java \ - -classpath ${TESTSRC}${FS}P1.jar${PS}${TESTSRC}${FS}P2.jar${PS}. \ + -classpath "${TESTSRC}${FS}P1.jar${PS}${TESTSRC}${FS}P2.jar${PS}." \ FailOverTest result=$?
--- a/test/javax/security/auth/Subject/doAs/Test.sh Thu Aug 06 10:25:18 2009 -0700 +++ b/test/javax/security/auth/Subject/doAs/Test.sh Thu Aug 06 19:01:59 2009 -0700 @@ -43,6 +43,11 @@ FS="/" RM="/bin/rm -f" ;; + CYGWIN* ) + PS=";" + FS="/" + RM="rm" + ;; Windows* ) PS=";" FS="\\"
--- a/test/lib/security/java.policy/Ext_AllPolicy.sh Thu Aug 06 10:25:18 2009 -0700 +++ b/test/lib/security/java.policy/Ext_AllPolicy.sh Thu Aug 06 19:01:59 2009 -0700 @@ -56,6 +56,12 @@ FS="/" TMP=/tmp ;; + CYGWIN* ) + NULL=/dev/null + PS=";" + FS="/" + TMP=/tmp + ;; Windows_95 | Windows_98 | Windows_NT ) NULL=NUL PS=";"
--- a/test/sun/net/www/MarkResetTest.sh Thu Aug 06 10:25:18 2009 -0700 +++ b/test/sun/net/www/MarkResetTest.sh Thu Aug 06 19:01:59 2009 -0700 @@ -32,6 +32,10 @@ PS=":" FS="/" ;; + CYGWIN* ) + PS=";" + FS="/" + ;; Windows* ) PS=";" FS="\\"
--- a/test/sun/net/www/http/ChunkedInputStream/ChunkedCharEncoding.sh Thu Aug 06 10:25:18 2009 -0700 +++ b/test/sun/net/www/http/ChunkedInputStream/ChunkedCharEncoding.sh Thu Aug 06 19:01:59 2009 -0700 @@ -32,6 +32,10 @@ PS=":" FS="/" ;; + CYGWIN* ) + PS=";" + FS="/" + ;; Windows* ) PS=";" FS="\\"
--- a/test/sun/net/www/http/HttpClient/RetryPost.sh Thu Aug 06 10:25:18 2009 -0700 +++ b/test/sun/net/www/http/HttpClient/RetryPost.sh Thu Aug 06 19:01:59 2009 -0700 @@ -32,6 +32,10 @@ PS=":" FS="/" ;; + CYGWIN* ) + PS=";" + FS="/" + ;; Windows* ) PS=";" FS="\\"
--- a/test/sun/net/www/protocol/jar/B5105410.sh Thu Aug 06 10:25:18 2009 -0700 +++ b/test/sun/net/www/protocol/jar/B5105410.sh Thu Aug 06 19:01:59 2009 -0700 @@ -39,6 +39,10 @@ PS=":" FS="/" ;; + CYGWIN* ) + PS=";" + FS="/" + ;; Windows* ) PS=";" FS="\\"
--- a/test/sun/net/www/protocol/jar/jarbug/run.sh Thu Aug 06 10:25:18 2009 -0700 +++ b/test/sun/net/www/protocol/jar/jarbug/run.sh Thu Aug 06 19:01:59 2009 -0700 @@ -28,23 +28,54 @@ # @summary various resource and classloading bugs related to jar files #set -x DEST=`pwd` + +OS=`uname -s` +case "$OS" in + SunOS ) + PS=":" + FS="/" + ;; + Linux ) + PS=":" + FS="/" + ;; + Windows* ) + PS=";" + FS="\\" + ;; + CYGWIN* ) + PS=";" + FS="/" + # + # javac does not like /cygdrive produced by `pwd`. + # + DEST=`cygpath -d ${DEST}` + ;; + * ) + echo "Unrecognized system!" + exit 1; + ;; +esac + # # build jar1 # -mkdir ${DEST}/jar1 -cd ${TESTSRC}/etc/jar1 -cp -r . ${DEST}/jar1 -${TESTJAVA}/bin/javac -d ${DEST}/jar1 ${TESTSRC}/src/jar1/LoadResourceBundle.java -${TESTJAVA}/bin/javac -d ${DEST}/jar1 ${TESTSRC}/src/jar1/GetResource.java -cd ${DEST}/jar1 -${TESTJAVA}/bin/jar cfM jar1.jar jar1 res1.txt +mkdir -p ${DEST}${FS}jar1 +cd ${TESTSRC}${FS}etc${FS}jar1 +cp -r . ${DEST}${FS}jar1 +${TESTJAVA}${FS}bin${FS}javac -d ${DEST}${FS}jar1 \ + ${TESTSRC}${FS}src${FS}jar1${FS}LoadResourceBundle.java +${TESTJAVA}${FS}bin${FS}javac -d ${DEST}${FS}jar1 \ + ${TESTSRC}${FS}src${FS}jar1${FS}GetResource.java +cd ${DEST}${FS}jar1 +${TESTJAVA}${FS}bin${FS}jar cfM jar1.jar jar1 res1.txt mv jar1.jar .. # # build the test sources and run them # -${TESTJAVA}/bin/javac -d ${DEST} ${TESTSRC}/src/test/*.java +${TESTJAVA}${FS}bin${FS}javac -d ${DEST} ${TESTSRC}${FS}src${FS}test${FS}*.java cd ${DEST} -${TESTJAVA}/bin/java RunAllTests +${TESTJAVA}${FS}bin${FS}java RunAllTests result=$? if [ "$result" -ne "0" ]; then exit 1
--- a/test/sun/security/krb5/ConfPlusProp.java Thu Aug 06 10:25:18 2009 -0700 +++ b/test/sun/security/krb5/ConfPlusProp.java Thu Aug 06 19:01:59 2009 -0700 @@ -23,7 +23,7 @@ /* * @test * @bug 6857795 - * @buf 6858589 + * @bug 6858589 * @summary krb5.conf ignored if system properties on realm and kdc are provided */
--- a/test/sun/security/pkcs11/Provider/ConfigQuotedString.sh Thu Aug 06 10:25:18 2009 -0700 +++ b/test/sun/security/pkcs11/Provider/ConfigQuotedString.sh Thu Aug 06 19:01:59 2009 -0700 @@ -68,6 +68,20 @@ CP="cp" CHMOD="chmod" ;; + CYGWIN* ) + FS="/" + PS=";" + CP="cp" + CHMOD="chmod" + # + # javac does not like /cygdrive produced by `pwd` + # + TESTSRC=`cygpath -d ${TESTSRC}` + ;; + * ) + echo "Unrecognized system!" + exit 1; + ;; esac # compile test
--- a/test/sun/security/pkcs11/Provider/Login.sh Thu Aug 06 10:25:18 2009 -0700 +++ b/test/sun/security/pkcs11/Provider/Login.sh Thu Aug 06 19:01:59 2009 -0700 @@ -69,6 +69,20 @@ CP="cp" CHMOD="chmod" ;; + CYGWIN* ) + FS="/" + PS=";" + CP="cp" + CHMOD="chmod" + # + # javac does not like /cygdrive produced by `pwd` + # + TESTSRC=`cygpath -d ${TESTSRC}` + ;; + * ) + echo "Unrecognized system!" + exit 1; + ;; esac # first make cert/key DBs writable
--- a/test/sun/security/provider/PolicyFile/getinstance/getinstance.sh Thu Aug 06 10:25:18 2009 -0700 +++ b/test/sun/security/provider/PolicyFile/getinstance/getinstance.sh Thu Aug 06 19:01:59 2009 -0700 @@ -55,6 +55,10 @@ PS=":" FS="/" ;; + CYGWIN* ) + PS=";" + FS="/" + ;; Windows* ) PS=";" FS="\\"
--- a/test/sun/security/ssl/com/sun/net/ssl/internal/ssl/SSLSocketImpl/NotifyHandshakeTest.sh Thu Aug 06 10:25:18 2009 -0700 +++ b/test/sun/security/ssl/com/sun/net/ssl/internal/ssl/SSLSocketImpl/NotifyHandshakeTest.sh Thu Aug 06 19:01:59 2009 -0700 @@ -43,10 +43,17 @@ OS=`uname -s` case "$OS" in SunOS | Linux ) + FILESEP="/" PATHSEP=":" ;; + CYGWIN* ) + FILESEP="/" + PATHSEP=";" + ;; + Windows* ) + FILESEP="\\" PATHSEP=";" ;; esac @@ -56,11 +63,13 @@ # # Compile the tests, package into their respective jars # -${TESTJAVA}/bin/javac -d . \ - ${TESTSRC}/NotifyHandshakeTest.java \ - ${TESTSRC}/NotifyHandshakeTestHeyYou.java -${TESTJAVA}/bin/jar -cvf com.jar com/NotifyHandshakeTest*.class -${TESTJAVA}/bin/jar -cvf edu.jar edu/NotifyHandshakeTestHeyYou.class +${TESTJAVA}${FILESEP}bin${FILESEP}javac -d . \ + ${TESTSRC}${FILESEP}NotifyHandshakeTest.java \ + ${TESTSRC}${FILESEP}NotifyHandshakeTestHeyYou.java +${TESTJAVA}${FILESEP}bin${FILESEP}jar -cvf com.jar \ + com${FILESEP}NotifyHandshakeTest*.class +${TESTJAVA}${FILESEP}bin${FILESEP}jar -cvf edu.jar \ + edu${FILESEP}NotifyHandshakeTestHeyYou.class # # Don't want the original class files to be used, because @@ -73,11 +82,11 @@ # This is the only thing we really care about as far as # test status goes. # -${TESTJAVA}/bin/java \ +${TESTJAVA}${FILESEP}bin${FILESEP}java \ -Dtest.src=${TESTSRC} \ -classpath "com.jar${PATHSEP}edu.jar" \ -Djava.security.manager \ - -Djava.security.policy=${TESTSRC}/NotifyHandshakeTest.policy \ + -Djava.security.policy=${TESTSRC}${FILESEP}NotifyHandshakeTest.policy \ com.NotifyHandshakeTest retval=$?
--- a/test/sun/security/ssl/sun/net/www/protocol/https/HttpsURLConnection/PostThruProxy.sh Thu Aug 06 10:25:18 2009 -0700 +++ b/test/sun/security/ssl/sun/net/www/protocol/https/HttpsURLConnection/PostThruProxy.sh Thu Aug 06 19:01:59 2009 -0700 @@ -36,6 +36,10 @@ PS=":" FS="/" ;; + CYGWIN* ) + PS=";" + FS="/" + ;; Windows* ) PS=";" FS="\\" @@ -46,6 +50,7 @@ ;; esac -${TESTJAVA}${FS}bin${FS}javac -d . ${TESTSRC}${FS}OriginServer.java ${TESTSRC}${FS}ProxyTunnelServer.java ${TESTSRC}${FS}PostThruProxy.java +${TESTJAVA}${FS}bin${FS}javac -d . ${TESTSRC}${FS}OriginServer.java \ + ${TESTSRC}${FS}ProxyTunnelServer.java ${TESTSRC}${FS}PostThruProxy.java ${TESTJAVA}${FS}bin${FS}java PostThruProxy ${HOSTNAME} ${TESTSRC} exit
--- a/test/sun/security/ssl/sun/net/www/protocol/https/HttpsURLConnection/PostThruProxyWithAuth.sh Thu Aug 06 10:25:18 2009 -0700 +++ b/test/sun/security/ssl/sun/net/www/protocol/https/HttpsURLConnection/PostThruProxyWithAuth.sh Thu Aug 06 19:01:59 2009 -0700 @@ -36,6 +36,10 @@ PS=":" FS="/" ;; + CYGWIN* ) + PS=";" + FS="/" + ;; Windows* ) PS=";" FS="\\" @@ -46,6 +50,8 @@ ;; esac -${TESTJAVA}${FS}bin${FS}javac -d . ${TESTSRC}${FS}OriginServer.java ${TESTSRC}${FS}ProxyTunnelServer.java ${TESTSRC}${FS}PostThruProxyWithAuth.java +${TESTJAVA}${FS}bin${FS}javac -d . ${TESTSRC}${FS}OriginServer.java \ + ${TESTSRC}${FS}ProxyTunnelServer.java \ + ${TESTSRC}${FS}PostThruProxyWithAuth.java ${TESTJAVA}${FS}bin${FS}java PostThruProxyWithAuth ${HOSTNAME} ${TESTSRC} exit
--- a/test/sun/security/tools/jarsigner/AlgOptions.sh Thu Aug 06 10:25:18 2009 -0700 +++ b/test/sun/security/tools/jarsigner/AlgOptions.sh Thu Aug 06 19:01:59 2009 -0700 @@ -53,6 +53,13 @@ CP="${FS}bin${FS}cp -f" TMP=/tmp ;; + CYGWIN* ) + NULL=/dev/null + PS=";" + FS="/" + CP="cp -f" + TMP=/tmp + ;; Windows_* ) NULL=NUL PS=";"
--- a/test/sun/security/tools/jarsigner/PercentSign.sh Thu Aug 06 10:25:18 2009 -0700 +++ b/test/sun/security/tools/jarsigner/PercentSign.sh Thu Aug 06 19:01:59 2009 -0700 @@ -53,6 +53,13 @@ CP="${FS}bin${FS}cp -f" TMP=/tmp ;; + CYGWIN* ) + NULL=/dev/null + PS=";" + FS="/" + CP="cp -f" + TMP=/tmp + ;; Windows_* ) NULL=NUL PS=";"
--- a/test/sun/security/tools/jarsigner/oldsig.sh Thu Aug 06 10:25:18 2009 -0700 +++ b/test/sun/security/tools/jarsigner/oldsig.sh Thu Aug 06 19:01:59 2009 -0700 @@ -49,6 +49,13 @@ CP="${FS}bin${FS}cp -f" TMP=/tmp ;; + CYGWIN* ) + NULL=/dev/null + PS=";" + FS="/" + CP="cp -f" + TMP=/tmp + ;; Windows_* ) NULL=NUL PS=";"
--- a/test/sun/security/tools/keytool/AltProviderPath.sh Thu Aug 06 10:25:18 2009 -0700 +++ b/test/sun/security/tools/keytool/AltProviderPath.sh Thu Aug 06 19:01:59 2009 -0700 @@ -52,6 +52,12 @@ FS="/" TMP=/tmp ;; + CYGWIN* ) + NULL=/dev/null + PS=";" + FS="/" + TMP=/tmp + ;; Windows_* ) NULL=NUL PS=";" @@ -66,14 +72,21 @@ # the test code #genkey -${TESTJAVA}${FS}bin${FS}keytool -genkey -v -alias dummyTestCA -keyalg "RSA" -keysize 1024 -sigalg "ShA1WithRSA" -dname "cn=Dummy Test CA, ou=JSN, o=JavaSoft, c=US" -validity 3650 -keypass storepass -keystore keystoreCA.dks -storepass storepass -storetype "dks" -provider "org.test.dummy.DummyProvider" -providerPath ${TESTCLASSES} +${TESTJAVA}${FS}bin${FS}keytool -genkey -v -alias dummyTestCA \ + -keyalg "RSA" -keysize 1024 -sigalg "ShA1WithRSA" \ + -dname "cn=Dummy Test CA, ou=JSN, o=JavaSoft, c=US" -validity 3650 \ + -keypass storepass -keystore keystoreCA.dks -storepass storepass \ + -storetype "dks" -provider "org.test.dummy.DummyProvider" \ + -providerPath ${TESTCLASSES} if [ $? -ne 0 ]; then exit 1 fi #Change keystore password -${TESTJAVA}${FS}bin${FS}keytool -storepasswd -new storepass2 -keystore keystoreCA.dks -storetype "dks" -storepass storepass -provider "org.test.dummy.DummyProvider" -providerPath ${TESTCLASSES} +${TESTJAVA}${FS}bin${FS}keytool -storepasswd -new storepass2 \ + -keystore keystoreCA.dks -storetype "dks" -storepass storepass \ + -provider "org.test.dummy.DummyProvider" -providerPath ${TESTCLASSES} if [ $? -ne 0 ]; then exit 1 @@ -81,21 +94,29 @@ #Change keystore key password -${TESTJAVA}${FS}bin${FS}keytool -keypasswd -alias "dummyTestCA" -keypass storepass -new keypass -keystore keystoreCA.dks -storetype "dks" -storepass storepass2 -provider "org.test.dummy.DummyProvider" -providerPath ${TESTCLASSES} +${TESTJAVA}${FS}bin${FS}keytool -keypasswd -alias "dummyTestCA" \ + -keypass storepass -new keypass -keystore keystoreCA.dks \ + -storetype "dks" -storepass storepass2 \ + -provider "org.test.dummy.DummyProvider" -providerPath ${TESTCLASSES} if [ $? -ne 0 ]; then exit 1 fi #Export certificate -${TESTJAVA}${FS}bin${FS}keytool -v -export -rfc -alias "dummyTestCA" -file "dummyTestCA.der" -keystore keystoreCA.dks -storetype "dks" -storepass storepass2 -provider "org.test.dummy.DummyProvider" -providerPath ${TESTCLASSES} +${TESTJAVA}${FS}bin${FS}keytool -v -export -rfc -alias "dummyTestCA" \ + -file "dummyTestCA.der" -keystore keystoreCA.dks -storetype "dks" \ + -storepass storepass2 -provider "org.test.dummy.DummyProvider" \ + -providerPath ${TESTCLASSES} if [ $? -ne 0 ]; then exit 1 fi #list keystore -${TESTJAVA}${FS}bin${FS}keytool -v -list -keystore keystoreCA.dks -storetype "dks" -storepass storepass2 -provider "org.test.dummy.DummyProvider" -providerPath ${TESTCLASSES} +${TESTJAVA}${FS}bin${FS}keytool -v -list -keystore keystoreCA.dks \ + -storetype "dks" -storepass storepass2 \ + -provider "org.test.dummy.DummyProvider" -providerPath ${TESTCLASSES} if [ $? -ne 0 ]; then exit 1
--- a/test/sun/security/tools/keytool/CloneKeyAskPassword.sh Thu Aug 06 10:25:18 2009 -0700 +++ b/test/sun/security/tools/keytool/CloneKeyAskPassword.sh Thu Aug 06 19:01:59 2009 -0700 @@ -55,6 +55,10 @@ PATHSEP=":" FILESEP="/" ;; + CYGWIN* ) + PATHSEP=";" + FILESEP="/" + ;; Windows* ) PATHSEP=";" FILESEP="\\"
--- a/test/sun/security/tools/keytool/NoExtNPE.sh Thu Aug 06 10:25:18 2009 -0700 +++ b/test/sun/security/tools/keytool/NoExtNPE.sh Thu Aug 06 19:01:59 2009 -0700 @@ -48,6 +48,9 @@ Linux ) FILESEP="/" ;; + CYGWIN* ) + FILESEP="/" + ;; Windows* ) FILESEP="\\" ;;
--- a/test/sun/security/tools/keytool/SecretKeyKS.sh Thu Aug 06 10:25:18 2009 -0700 +++ b/test/sun/security/tools/keytool/SecretKeyKS.sh Thu Aug 06 19:01:59 2009 -0700 @@ -51,6 +51,12 @@ FS="/" TMP=/tmp ;; + CYGWIN* ) + NULL=/dev/null + PS=";" + FS="/" + TMP=/tmp + ;; Windows_* ) NULL=NUL PS=";"
--- a/test/sun/security/tools/keytool/StandardAlgName.sh Thu Aug 06 10:25:18 2009 -0700 +++ b/test/sun/security/tools/keytool/StandardAlgName.sh Thu Aug 06 19:01:59 2009 -0700 @@ -52,6 +52,12 @@ FS="/" TMP=/tmp ;; + CYGWIN* ) + NULL=/dev/null + PS=";" + FS="/" + TMP=/tmp + ;; Windows_* ) NULL=NUL PS=";"
--- a/test/sun/security/tools/keytool/i18n.sh Thu Aug 06 10:25:18 2009 -0700 +++ b/test/sun/security/tools/keytool/i18n.sh Thu Aug 06 19:01:59 2009 -0700 @@ -52,6 +52,12 @@ FS="/" TMP=/tmp ;; + CYGWIN* ) + NULL=/dev/null + PS=";" + FS="/" + TMP=/tmp + ;; Windows* ) NULL=NUL PS=";"
--- a/test/sun/security/tools/keytool/printssl.sh Thu Aug 06 10:25:18 2009 -0700 +++ b/test/sun/security/tools/keytool/printssl.sh Thu Aug 06 19:01:59 2009 -0700 @@ -40,6 +40,9 @@ SunOS | Linux ) FS="/" ;; + CYGWIN* ) + FS="/" + ;; Windows_* ) FS="\\" ;;
--- a/test/sun/security/tools/keytool/resource.sh Thu Aug 06 10:25:18 2009 -0700 +++ b/test/sun/security/tools/keytool/resource.sh Thu Aug 06 19:01:59 2009 -0700 @@ -48,6 +48,11 @@ FS="/" TMP=/tmp ;; + CYGWIN* ) + NULL=/dev/null + FS="/" + TMP=/tmp + ;; Windows_* ) NULL=NUL FS="\\"
--- a/test/sun/security/tools/keytool/standard.sh Thu Aug 06 10:25:18 2009 -0700 +++ b/test/sun/security/tools/keytool/standard.sh Thu Aug 06 19:01:59 2009 -0700 @@ -24,6 +24,7 @@ # @test # @summary (almost) all keytool behaviors # @author Weijun Wang +# @run shell/timeout=600 standard.sh # # This test is always excecuted. # @@ -43,11 +44,15 @@ # set platform-dependent variables OS=`uname -s` case "$OS" in + SunOS | Linux | CYGWIN* ) + FS="/" + ;; Windows_* ) FS="\\" ;; * ) - FS="/" + echo "Unrecognized system!" + exit 1; ;; esac