--- a/jdk/make/java/java/FILES_java.gmk Thu May 31 17:07:28 2012 -0400
+++ b/jdk/make/java/java/FILES_java.gmk Thu May 31 17:10:57 2012 -0400
@@ -482,6 +482,7 @@
sun/misc/JavaNioAccess.java \
sun/misc/Perf.java \
sun/misc/PerfCounter.java \
+ sun/misc/Hashing.java \
sun/net/www/protocol/jar/Handler.java \
sun/net/www/protocol/jar/JarURLConnection.java \
sun/net/www/protocol/file/Handler.java \
--- a/jdk/src/share/classes/java/lang/Integer.java Thu May 31 17:07:28 2012 -0400
+++ b/jdk/src/share/classes/java/lang/Integer.java Thu May 31 17:10:57 2012 -0400
@@ -381,7 +381,7 @@
int size = (i < 0) ? stringSize(-i) + 1 : stringSize(i);
char[] buf = new char[size];
getChars(i, size, buf);
- return new String(0, size, buf);
+ return new String(buf, true);
}
/**
--- a/jdk/src/share/classes/java/lang/Long.java Thu May 31 17:07:28 2012 -0400
+++ b/jdk/src/share/classes/java/lang/Long.java Thu May 31 17:10:57 2012 -0400
@@ -373,7 +373,7 @@
int size = (i < 0) ? stringSize(-i) + 1 : stringSize(i);
char[] buf = new char[size];
getChars(i, size, buf);
- return new String(0, size, buf);
+ return new String(buf, true);
}
/**
--- a/jdk/src/share/classes/java/lang/String.java Thu May 31 17:07:28 2012 -0400
+++ b/jdk/src/share/classes/java/lang/String.java Thu May 31 17:10:57 2012 -0400
@@ -25,7 +25,6 @@
package java.lang;
-import java.io.ObjectStreamClass;
import java.io.ObjectStreamField;
import java.io.UnsupportedEncodingException;
import java.nio.charset.Charset;
@@ -108,17 +107,10 @@
*/
public final class String
- implements java.io.Serializable, Comparable<String>, CharSequence
-{
+ implements java.io.Serializable, Comparable<String>, CharSequence {
/** The value is used for character storage. */
private final char value[];
- /** The offset is the first index of the storage that is used. */
- private final int offset;
-
- /** The count is the number of characters in the String. */
- private final int count;
-
/** Cache the hash code for the string */
private int hash; // Default to 0
@@ -138,7 +130,7 @@
* string instance within the stream.
*/
private static final ObjectStreamField[] serialPersistentFields =
- new ObjectStreamField[0];
+ new ObjectStreamField[0];
/**
* Initializes a newly created {@code String} object so that it represents
@@ -146,8 +138,6 @@
* unnecessary since Strings are immutable.
*/
public String() {
- this.offset = 0;
- this.count = 0;
this.value = new char[0];
}
@@ -162,23 +152,8 @@
* A {@code String}
*/
public String(String original) {
- int size = original.count;
- char[] originalValue = original.value;
- char[] v;
- if (originalValue.length > size) {
- // The array representing the String is bigger than the new
- // String itself. Perhaps this constructor is being called
- // in order to trim the baggage, so make a copy of the array.
- int off = original.offset;
- v = Arrays.copyOfRange(originalValue, off, off+size);
- } else {
- // The array representing the String is the same
- // size as the String, so no point in making a copy.
- v = originalValue;
- }
- this.offset = 0;
- this.count = size;
- this.value = v;
+ this.value = original.value;
+ this.hash = original.hash;
}
/**
@@ -191,10 +166,7 @@
* The initial value of the string
*/
public String(char value[]) {
- int size = value.length;
- this.offset = 0;
- this.count = size;
- this.value = Arrays.copyOf(value, size);
+ this.value = Arrays.copyOf(value, value.length);
}
/**
@@ -229,8 +201,6 @@
if (offset > value.length - count) {
throw new StringIndexOutOfBoundsException(offset + count);
}
- this.offset = 0;
- this.count = count;
this.value = Arrays.copyOfRange(value, offset, offset+count);
}
@@ -293,14 +263,12 @@
for (int i = offset, j = 0; i < end; i++, j++) {
int c = codePoints[i];
if (Character.isBmpCodePoint(c))
- v[j] = (char) c;
+ v[j] = (char)c;
else
Character.toSurrogates(c, v, j++);
}
- this.value = v;
- this.count = n;
- this.offset = 0;
+ this.value = v;
}
/**
@@ -348,17 +316,15 @@
char value[] = new char[count];
if (hibyte == 0) {
- for (int i = count ; i-- > 0 ;) {
- value[i] = (char) (ascii[i + offset] & 0xff);
+ for (int i = count; i-- > 0;) {
+ value[i] = (char)(ascii[i + offset] & 0xff);
}
} else {
hibyte <<= 8;
- for (int i = count ; i-- > 0 ;) {
- value[i] = (char) (hibyte | (ascii[i + offset] & 0xff));
+ for (int i = count; i-- > 0;) {
+ value[i] = (char)(hibyte | (ascii[i + offset] & 0xff));
}
}
- this.offset = 0;
- this.count = count;
this.value = value;
}
@@ -444,15 +410,11 @@
* @since JDK1.1
*/
public String(byte bytes[], int offset, int length, String charsetName)
- throws UnsupportedEncodingException
- {
+ throws UnsupportedEncodingException {
if (charsetName == null)
throw new NullPointerException("charsetName");
checkBounds(bytes, offset, length);
- char[] v = StringCoding.decode(charsetName, bytes, offset, length);
- this.offset = 0;
- this.count = v.length;
- this.value = v;
+ this.value = StringCoding.decode(charsetName, bytes, offset, length);
}
/**
@@ -489,10 +451,7 @@
if (charset == null)
throw new NullPointerException("charset");
checkBounds(bytes, offset, length);
- char[] v = StringCoding.decode(charset, bytes, offset, length);
- this.offset = 0;
- this.count = v.length;
- this.value = v;
+ this.value = StringCoding.decode(charset, bytes, offset, length);
}
/**
@@ -519,8 +478,7 @@
* @since JDK1.1
*/
public String(byte bytes[], String charsetName)
- throws UnsupportedEncodingException
- {
+ throws UnsupportedEncodingException {
this(bytes, 0, bytes.length, charsetName);
}
@@ -576,10 +534,7 @@
*/
public String(byte bytes[], int offset, int length) {
checkBounds(bytes, offset, length);
- char[] v = StringCoding.decode(bytes, offset, length);
- this.offset = 0;
- this.count = v.length;
- this.value = v;
+ this.value = StringCoding.decode(bytes, offset, length);
}
/**
@@ -612,10 +567,9 @@
* A {@code StringBuffer}
*/
public String(StringBuffer buffer) {
- String result = buffer.toString();
- this.value = result.value;
- this.count = result.count;
- this.offset = result.offset;
+ synchronized(buffer) {
+ this.value = Arrays.copyOf(buffer.getValue(), buffer.length());
+ }
}
/**
@@ -634,18 +588,18 @@
* @since 1.5
*/
public String(StringBuilder builder) {
- String result = builder.toString();
- this.value = result.value;
- this.count = result.count;
- this.offset = result.offset;
+ this.value = Arrays.copyOf(builder.getValue(), builder.length());
}
-
- // Package private constructor which shares value array for speed.
- String(int offset, int count, char value[]) {
+ /*
+ * Package private constructor which shares value array for speed.
+ * this constructor is always expected to be called with share==true.
+ * a separate constructor is needed because we already have a public
+ * String(char[]) constructor that makes a copy of the given char[].
+ */
+ String(char[] value, boolean share) {
+ // assert share : "unshared not supported";
this.value = value;
- this.offset = offset;
- this.count = count;
}
/**
@@ -657,7 +611,7 @@
* object.
*/
public int length() {
- return count;
+ return value.length;
}
/**
@@ -669,7 +623,7 @@
* @since 1.6
*/
public boolean isEmpty() {
- return count == 0;
+ return value.length == 0;
}
/**
@@ -691,10 +645,10 @@
* string.
*/
public char charAt(int index) {
- if ((index < 0) || (index >= count)) {
+ if ((index < 0) || (index >= value.length)) {
throw new StringIndexOutOfBoundsException(index);
}
- return value[index + offset];
+ return value[index];
}
/**
@@ -720,10 +674,10 @@
* @since 1.5
*/
public int codePointAt(int index) {
- if ((index < 0) || (index >= count)) {
+ if ((index < 0) || (index >= value.length)) {
throw new StringIndexOutOfBoundsException(index);
}
- return Character.codePointAtImpl(value, offset + index, offset + count);
+ return Character.codePointAtImpl(value, index, value.length);
}
/**
@@ -750,10 +704,10 @@
*/
public int codePointBefore(int index) {
int i = index - 1;
- if ((i < 0) || (i >= count)) {
+ if ((i < 0) || (i >= value.length)) {
throw new StringIndexOutOfBoundsException(index);
}
- return Character.codePointBeforeImpl(value, offset + index, offset);
+ return Character.codePointBeforeImpl(value, index, 0);
}
/**
@@ -778,10 +732,10 @@
* @since 1.5
*/
public int codePointCount(int beginIndex, int endIndex) {
- if (beginIndex < 0 || endIndex > count || beginIndex > endIndex) {
+ if (beginIndex < 0 || endIndex > value.length || beginIndex > endIndex) {
throw new IndexOutOfBoundsException();
}
- return Character.codePointCountImpl(value, offset+beginIndex, endIndex-beginIndex);
+ return Character.codePointCountImpl(value, beginIndex, endIndex - beginIndex);
}
/**
@@ -805,11 +759,11 @@
* @since 1.5
*/
public int offsetByCodePoints(int index, int codePointOffset) {
- if (index < 0 || index > count) {
+ if (index < 0 || index > value.length) {
throw new IndexOutOfBoundsException();
}
- return Character.offsetByCodePointsImpl(value, offset, count,
- offset+index, codePointOffset) - offset;
+ return Character.offsetByCodePointsImpl(value, 0, value.length,
+ index, codePointOffset);
}
/**
@@ -817,7 +771,7 @@
* This method doesn't perform any range checking.
*/
void getChars(char dst[], int dstBegin) {
- System.arraycopy(value, offset, dst, dstBegin, count);
+ System.arraycopy(value, 0, dst, dstBegin, value.length);
}
/**
@@ -854,14 +808,13 @@
if (srcBegin < 0) {
throw new StringIndexOutOfBoundsException(srcBegin);
}
- if (srcEnd > count) {
+ if (srcEnd > value.length) {
throw new StringIndexOutOfBoundsException(srcEnd);
}
if (srcBegin > srcEnd) {
throw new StringIndexOutOfBoundsException(srcEnd - srcBegin);
}
- System.arraycopy(value, offset + srcBegin, dst, dstBegin,
- srcEnd - srcBegin);
+ System.arraycopy(value, srcBegin, dst, dstBegin, srcEnd - srcBegin);
}
/**
@@ -912,15 +865,15 @@
if (srcBegin < 0) {
throw new StringIndexOutOfBoundsException(srcBegin);
}
- if (srcEnd > count) {
+ if (srcEnd > value.length) {
throw new StringIndexOutOfBoundsException(srcEnd);
}
if (srcBegin > srcEnd) {
throw new StringIndexOutOfBoundsException(srcEnd - srcBegin);
}
int j = dstBegin;
- int n = offset + srcEnd;
- int i = offset + srcBegin;
+ int n = srcEnd;
+ int i = srcBegin;
char[] val = value; /* avoid getfield opcode */
while (i < n) {
@@ -949,10 +902,9 @@
* @since JDK1.1
*/
public byte[] getBytes(String charsetName)
- throws UnsupportedEncodingException
- {
+ throws UnsupportedEncodingException {
if (charsetName == null) throw new NullPointerException();
- return StringCoding.encode(charsetName, value, offset, count);
+ return StringCoding.encode(charsetName, value, 0, value.length);
}
/**
@@ -975,7 +927,7 @@
*/
public byte[] getBytes(Charset charset) {
if (charset == null) throw new NullPointerException();
- return StringCoding.encode(charset, value, offset, count);
+ return StringCoding.encode(charset, value, 0, value.length);
}
/**
@@ -992,7 +944,7 @@
* @since JDK1.1
*/
public byte[] getBytes() {
- return StringCoding.encode(value, offset, count);
+ return StringCoding.encode(value, 0, value.length);
}
/**
@@ -1015,16 +967,16 @@
return true;
}
if (anObject instanceof String) {
- String anotherString = (String)anObject;
- int n = count;
- if (n == anotherString.count) {
+ String anotherString = (String) anObject;
+ int n = value.length;
+ if (n == anotherString.value.length) {
char v1[] = value;
char v2[] = anotherString.value;
- int i = offset;
- int j = anotherString.offset;
+ int i = 0;
while (n-- != 0) {
- if (v1[i++] != v2[j++])
- return false;
+ if (v1[i] != v2[i])
+ return false;
+ i++;
}
return true;
}
@@ -1047,8 +999,8 @@
* @since 1.4
*/
public boolean contentEquals(StringBuffer sb) {
- synchronized(sb) {
- return contentEquals((CharSequence)sb);
+ synchronized (sb) {
+ return contentEquals((CharSequence) sb);
}
}
@@ -1067,18 +1019,18 @@
* @since 1.5
*/
public boolean contentEquals(CharSequence cs) {
- if (count != cs.length())
+ if (value.length != cs.length())
return false;
// Argument is a StringBuffer, StringBuilder
if (cs instanceof AbstractStringBuilder) {
char v1[] = value;
- char v2[] = ((AbstractStringBuilder)cs).getValue();
- int i = offset;
- int j = 0;
- int n = count;
+ char v2[] = ((AbstractStringBuilder) cs).getValue();
+ int i = 0;
+ int n = value.length;
while (n-- != 0) {
- if (v1[i++] != v2[j++])
+ if (v1[i] != v2[i])
return false;
+ i++;
}
return true;
}
@@ -1087,12 +1039,12 @@
return true;
// Argument is a generic CharSequence
char v1[] = value;
- int i = offset;
- int j = 0;
- int n = count;
+ int i = 0;
+ int n = value.length;
while (n-- != 0) {
- if (v1[i++] != cs.charAt(j++))
+ if (v1[i] != cs.charAt(i))
return false;
+ i++;
}
return true;
}
@@ -1126,9 +1078,10 @@
* @see #equals(Object)
*/
public boolean equalsIgnoreCase(String anotherString) {
- return (this == anotherString) ? true :
- (anotherString != null) && (anotherString.count == count) &&
- regionMatches(true, 0, anotherString, 0, count);
+ return (this == anotherString) ? true
+ : (anotherString != null)
+ && (anotherString.value.length == value.length)
+ && regionMatches(true, 0, anotherString, 0, value.length);
}
/**
@@ -1173,33 +1126,20 @@
* lexicographically greater than the string argument.
*/
public int compareTo(String anotherString) {
- int len1 = count;
- int len2 = anotherString.count;
- int n = Math.min(len1, len2);
+ int len1 = value.length;
+ int len2 = anotherString.value.length;
+ int lim = Math.min(len1, len2);
char v1[] = value;
char v2[] = anotherString.value;
- int i = offset;
- int j = anotherString.offset;
- if (i == j) {
- int k = i;
- int lim = n + i;
- while (k < lim) {
- char c1 = v1[k];
- char c2 = v2[k];
- if (c1 != c2) {
- return c1 - c2;
- }
- k++;
+ int k = 0;
+ while (k < lim) {
+ char c1 = v1[k];
+ char c2 = v2[k];
+ if (c1 != c2) {
+ return c1 - c2;
}
- } else {
- while (n-- != 0) {
- char c1 = v1[i++];
- char c2 = v2[j++];
- if (c1 != c2) {
- return c1 - c2;
- }
- }
+ k++;
}
return len1 - len2;
}
@@ -1219,7 +1159,7 @@
public static final Comparator<String> CASE_INSENSITIVE_ORDER
= new CaseInsensitiveComparator();
private static class CaseInsensitiveComparator
- implements Comparator<String>, java.io.Serializable {
+ implements Comparator<String>, java.io.Serializable {
// use serialVersionUID from JDK 1.2.2 for interoperability
private static final long serialVersionUID = 8575799808933029326L;
@@ -1306,14 +1246,15 @@
* {@code false} otherwise.
*/
public boolean regionMatches(int toffset, String other, int ooffset,
- int len) {
+ int len) {
char ta[] = value;
- int to = offset + toffset;
+ int to = toffset;
char pa[] = other.value;
- int po = other.offset + ooffset;
+ int po = ooffset;
// Note: toffset, ooffset, or len might be near -1>>>1.
- if ((ooffset < 0) || (toffset < 0) || (toffset > (long)count - len)
- || (ooffset > (long)other.count - len)) {
+ if ((ooffset < 0) || (toffset < 0)
+ || (toffset > (long)value.length - len)
+ || (ooffset > (long)other.value.length - len)) {
return false;
}
while (len-- > 0) {
@@ -1351,7 +1292,7 @@
* integer <i>k</i> less than <tt>len</tt> such that:
* <blockquote><pre>
* Character.toLowerCase(this.charAt(toffset+k)) !=
- Character.toLowerCase(other.charAt(ooffset+k))
+ Character.toLowerCase(other.charAt(ooffset+k))
* </pre></blockquote>
* and:
* <blockquote><pre>
@@ -1375,14 +1316,15 @@
* argument.
*/
public boolean regionMatches(boolean ignoreCase, int toffset,
- String other, int ooffset, int len) {
+ String other, int ooffset, int len) {
char ta[] = value;
- int to = offset + toffset;
+ int to = toffset;
char pa[] = other.value;
- int po = other.offset + ooffset;
+ int po = ooffset;
// Note: toffset, ooffset, or len might be near -1>>>1.
- if ((ooffset < 0) || (toffset < 0) || (toffset > (long)count - len) ||
- (ooffset > (long)other.count - len)) {
+ if ((ooffset < 0) || (toffset < 0)
+ || (toffset > (long)value.length - len)
+ || (ooffset > (long)other.value.length - len)) {
return false;
}
while (len-- > 0) {
@@ -1433,12 +1375,12 @@
*/
public boolean startsWith(String prefix, int toffset) {
char ta[] = value;
- int to = offset + toffset;
+ int to = toffset;
char pa[] = prefix.value;
- int po = prefix.offset;
- int pc = prefix.count;
+ int po = 0;
+ int pc = prefix.value.length;
// Note: toffset might be near -1>>>1.
- if ((toffset < 0) || (toffset > count - pc)) {
+ if ((toffset < 0) || (toffset > value.length - pc)) {
return false;
}
while (--pc >= 0) {
@@ -1478,7 +1420,7 @@
* as determined by the {@link #equals(Object)} method.
*/
public boolean endsWith(String suffix) {
- return startsWith(suffix, count - suffix.count);
+ return startsWith(suffix, value.length - suffix.value.length);
}
/**
@@ -1496,13 +1438,11 @@
*/
public int hashCode() {
int h = hash;
- if (h == 0 && count > 0) {
- int off = offset;
+ if (h == 0 && value.length > 0) {
char val[] = value;
- int len = count;
- for (int i = 0; i < len; i++) {
- h = 31*h + val[off++];
+ for (int i = 0; i < value.length; i++) {
+ h = 31 * h + val[i];
}
hash = h;
}
@@ -1577,9 +1517,10 @@
* if the character does not occur.
*/
public int indexOf(int ch, int fromIndex) {
+ final int max = value.length;
if (fromIndex < 0) {
fromIndex = 0;
- } else if (fromIndex >= count) {
+ } else if (fromIndex >= max) {
// Note: fromIndex might be near -1>>>1.
return -1;
}
@@ -1588,11 +1529,9 @@
// handle most cases here (ch is a BMP code point or a
// negative value (invalid code point))
final char[] value = this.value;
- final int offset = this.offset;
- final int max = offset + count;
- for (int i = offset + fromIndex; i < max ; i++) {
+ for (int i = fromIndex; i < max; i++) {
if (value[i] == ch) {
- return i - offset;
+ return i;
}
}
return -1;
@@ -1607,13 +1546,12 @@
private int indexOfSupplementary(int ch, int fromIndex) {
if (Character.isValidCodePoint(ch)) {
final char[] value = this.value;
- final int offset = this.offset;
final char hi = Character.highSurrogate(ch);
final char lo = Character.lowSurrogate(ch);
- final int max = offset + count - 1;
- for (int i = offset + fromIndex; i < max; i++) {
- if (value[i] == hi && value[i+1] == lo) {
- return i - offset;
+ final int max = value.length - 1;
+ for (int i = fromIndex; i < max; i++) {
+ if (value[i] == hi && value[i + 1] == lo) {
+ return i;
}
}
}
@@ -1644,7 +1582,7 @@
* {@code -1} if the character does not occur.
*/
public int lastIndexOf(int ch) {
- return lastIndexOf(ch, count - 1);
+ return lastIndexOf(ch, value.length - 1);
}
/**
@@ -1686,11 +1624,10 @@
// handle most cases here (ch is a BMP code point or a
// negative value (invalid code point))
final char[] value = this.value;
- final int offset = this.offset;
- int i = offset + Math.min(fromIndex, count - 1);
- for (; i >= offset ; i--) {
+ int i = Math.min(fromIndex, value.length - 1);
+ for (; i >= 0; i--) {
if (value[i] == ch) {
- return i - offset;
+ return i;
}
}
return -1;
@@ -1705,13 +1642,12 @@
private int lastIndexOfSupplementary(int ch, int fromIndex) {
if (Character.isValidCodePoint(ch)) {
final char[] value = this.value;
- final int offset = this.offset;
char hi = Character.highSurrogate(ch);
char lo = Character.lowSurrogate(ch);
- int i = offset + Math.min(fromIndex, count - 2);
- for (; i >= offset; i--) {
- if (value[i] == hi && value[i+1] == lo) {
- return i - offset;
+ int i = Math.min(fromIndex, value.length - 2);
+ for (; i >= 0; i--) {
+ if (value[i] == hi && value[i + 1] == lo) {
+ return i;
}
}
}
@@ -1753,8 +1689,8 @@
* or {@code -1} if there is no such occurrence.
*/
public int indexOf(String str, int fromIndex) {
- return indexOf(value, offset, count,
- str.value, str.offset, str.count, fromIndex);
+ return indexOf(value, 0, value.length,
+ str.value, 0, str.value.length, fromIndex);
}
/**
@@ -1771,8 +1707,8 @@
* @param fromIndex the index to begin searching from.
*/
static int indexOf(char[] source, int sourceOffset, int sourceCount,
- char[] target, int targetOffset, int targetCount,
- int fromIndex) {
+ char[] target, int targetOffset, int targetCount,
+ int fromIndex) {
if (fromIndex >= sourceCount) {
return (targetCount == 0 ? sourceCount : -1);
}
@@ -1783,7 +1719,7 @@
return fromIndex;
}
- char first = target[targetOffset];
+ char first = target[targetOffset];
int max = sourceOffset + (sourceCount - targetCount);
for (int i = sourceOffset + fromIndex; i <= max; i++) {
@@ -1796,8 +1732,8 @@
if (i <= max) {
int j = i + 1;
int end = j + targetCount - 1;
- for (int k = targetOffset + 1; j < end && source[j] ==
- target[k]; j++, k++);
+ for (int k = targetOffset + 1; j < end && source[j]
+ == target[k]; j++, k++);
if (j == end) {
/* Found whole string. */
@@ -1824,7 +1760,7 @@
* or {@code -1} if there is no such occurrence.
*/
public int lastIndexOf(String str) {
- return lastIndexOf(str, count);
+ return lastIndexOf(str, value.length);
}
/**
@@ -1844,8 +1780,8 @@
* or {@code -1} if there is no such occurrence.
*/
public int lastIndexOf(String str, int fromIndex) {
- return lastIndexOf(value, offset, count,
- str.value, str.offset, str.count, fromIndex);
+ return lastIndexOf(value, 0, value.length,
+ str.value, 0, str.value.length, fromIndex);
}
/**
@@ -1862,8 +1798,8 @@
* @param fromIndex the index to begin searching from.
*/
static int lastIndexOf(char[] source, int sourceOffset, int sourceCount,
- char[] target, int targetOffset, int targetCount,
- int fromIndex) {
+ char[] target, int targetOffset, int targetCount,
+ int fromIndex) {
/*
* Check arguments; return immediately where possible. For
* consistency, don't check for null str.
@@ -1885,7 +1821,7 @@
int min = sourceOffset + targetCount - 1;
int i = min + fromIndex;
- startSearchForLastChar:
+ startSearchForLastChar:
while (true) {
while (i >= min && source[i] != strLastChar) {
i--;
@@ -1925,7 +1861,14 @@
* length of this {@code String} object.
*/
public String substring(int beginIndex) {
- return substring(beginIndex, count);
+ if (beginIndex < 0) {
+ throw new StringIndexOutOfBoundsException(beginIndex);
+ }
+ int subLen = value.length - beginIndex;
+ if (subLen < 0) {
+ throw new StringIndexOutOfBoundsException(subLen);
+ }
+ return (beginIndex == 0) ? this : new String(value, beginIndex, subLen);
}
/**
@@ -1954,14 +1897,15 @@
if (beginIndex < 0) {
throw new StringIndexOutOfBoundsException(beginIndex);
}
- if (endIndex > count) {
+ if (endIndex > value.length) {
throw new StringIndexOutOfBoundsException(endIndex);
}
- if (beginIndex > endIndex) {
- throw new StringIndexOutOfBoundsException(endIndex - beginIndex);
+ int subLen = endIndex - beginIndex;
+ if (subLen < 0) {
+ throw new StringIndexOutOfBoundsException(subLen);
}
- return ((beginIndex == 0) && (endIndex == count)) ? this :
- new String(offset + beginIndex, endIndex - beginIndex, value);
+ return ((beginIndex == 0) && (endIndex == value.length)) ? this
+ : new String(value, beginIndex, subLen);
}
/**
@@ -2021,10 +1965,10 @@
if (otherLen == 0) {
return this;
}
- char buf[] = new char[count + otherLen];
- getChars(0, count, buf, 0);
- str.getChars(0, otherLen, buf, count);
- return new String(0, count + otherLen, buf);
+ int len = value.length;
+ char buf[] = Arrays.copyOf(value, len + otherLen);
+ str.getChars(buf, len);
+ return new String(buf, true);
}
/**
@@ -2058,27 +2002,26 @@
*/
public String replace(char oldChar, char newChar) {
if (oldChar != newChar) {
- int len = count;
+ int len = value.length;
int i = -1;
char[] val = value; /* avoid getfield opcode */
- int off = offset; /* avoid getfield opcode */
while (++i < len) {
- if (val[off + i] == oldChar) {
+ if (val[i] == oldChar) {
break;
}
}
if (i < len) {
char buf[] = new char[len];
- for (int j = 0 ; j < i ; j++) {
- buf[j] = val[off+j];
+ for (int j = 0; j < i; j++) {
+ buf[j] = val[j];
}
while (i < len) {
- char c = val[off + i];
+ char c = val[i];
buf[i] = (c == oldChar) ? newChar : c;
i++;
}
- return new String(0, len, buf);
+ return new String(buf, true);
}
}
return this;
@@ -2229,7 +2172,7 @@
*/
public String replace(CharSequence target, CharSequence replacement) {
return Pattern.compile(target.toString(), Pattern.LITERAL).matcher(
- this).replaceAll(Matcher.quoteReplacement(replacement.toString()));
+ this).replaceAll(Matcher.quoteReplacement(replacement.toString()));
}
/**
@@ -2314,13 +2257,13 @@
*/
public String[] split(String regex, int limit) {
/* fastpath if the regex is a
- (1)one-char String and this character is not one of the
- RegEx's meta characters ".$|()[{^?*+\\", or
- (2)two-char String and the first char is the backslash and
- the second is not the ascii digit or ascii letter.
- */
+ (1)one-char String and this character is not one of the
+ RegEx's meta characters ".$|()[{^?*+\\", or
+ (2)two-char String and the first char is the backslash and
+ the second is not the ascii digit or ascii letter.
+ */
char ch = 0;
- if (((regex.count == 1 &&
+ if (((regex.value.length == 1 &&
".$|()[{^?*+\\".indexOf(ch = regex.charAt(0)) == -1) ||
(regex.length() == 2 &&
regex.charAt(0) == '\\' &&
@@ -2340,23 +2283,23 @@
off = next + 1;
} else { // last one
//assert (list.size() == limit - 1);
- list.add(substring(off, count));
- off = count;
+ list.add(substring(off, value.length));
+ off = value.length;
break;
}
}
// If no match was found, return this
if (off == 0)
- return new String[] { this };
+ return new String[]{this};
// Add remaining segment
if (!limited || list.size() < limit)
- list.add(substring(off, count));
+ list.add(substring(off, value.length));
// Construct result
int resultSize = list.size();
if (limit == 0)
- while (resultSize > 0 && list.get(resultSize-1).length() == 0)
+ while (resultSize > 0 && list.get(resultSize - 1).length() == 0)
resultSize--;
String[] result = new String[resultSize];
return list.subList(0, resultSize).toArray(result);
@@ -2463,14 +2406,15 @@
throw new NullPointerException();
}
- int firstUpper;
+ int firstUpper;
+ final int len = value.length;
/* Now check if there are any characters that need to be changed. */
scan: {
- for (firstUpper = 0 ; firstUpper < count; ) {
- char c = value[offset+firstUpper];
- if ((c >= Character.MIN_HIGH_SURROGATE) &&
- (c <= Character.MAX_HIGH_SURROGATE)) {
+ for (firstUpper = 0 ; firstUpper < len; ) {
+ char c = value[firstUpper];
+ if ((c >= Character.MIN_HIGH_SURROGATE)
+ && (c <= Character.MAX_HIGH_SURROGATE)) {
int supplChar = codePointAt(firstUpper);
if (supplChar != Character.toLowerCase(supplChar)) {
break scan;
@@ -2486,24 +2430,24 @@
return this;
}
- char[] result = new char[count];
- int resultOffset = 0; /* result may grow, so i+resultOffset
- * is the write location in result */
+ char[] result = new char[len];
+ int resultOffset = 0; /* result may grow, so i+resultOffset
+ * is the write location in result */
/* Just copy the first few lowerCase characters. */
- System.arraycopy(value, offset, result, 0, firstUpper);
+ System.arraycopy(value, 0, result, 0, firstUpper);
String lang = locale.getLanguage();
boolean localeDependent =
- (lang == "tr" || lang == "az" || lang == "lt");
+ (lang == "tr" || lang == "az" || lang == "lt");
char[] lowerCharArray;
int lowerChar;
int srcChar;
int srcCount;
- for (int i = firstUpper; i < count; i += srcCount) {
- srcChar = (int)value[offset+i];
- if ((char)srcChar >= Character.MIN_HIGH_SURROGATE &&
- (char)srcChar <= Character.MAX_HIGH_SURROGATE) {
+ for (int i = firstUpper; i < len; i += srcCount) {
+ srcChar = (int)value[i];
+ if ((char)srcChar >= Character.MIN_HIGH_SURROGATE
+ && (char)srcChar <= Character.MAX_HIGH_SURROGATE) {
srcChar = codePointAt(i);
srcCount = Character.charCount(srcChar);
} else {
@@ -2516,16 +2460,16 @@
} else {
lowerChar = Character.toLowerCase(srcChar);
}
- if ((lowerChar == Character.ERROR) ||
- (lowerChar >= Character.MIN_SUPPLEMENTARY_CODE_POINT)) {
+ if ((lowerChar == Character.ERROR)
+ || (lowerChar >= Character.MIN_SUPPLEMENTARY_CODE_POINT)) {
if (lowerChar == Character.ERROR) {
- if (!localeDependent && srcChar == '\u0130') {
- lowerCharArray =
- ConditionalSpecialCasing.toLowerCaseCharArray(this, i, Locale.ENGLISH);
- } else {
+ if (!localeDependent && srcChar == '\u0130') {
lowerCharArray =
- ConditionalSpecialCasing.toLowerCaseCharArray(this, i, locale);
- }
+ ConditionalSpecialCasing.toLowerCaseCharArray(this, i, Locale.ENGLISH);
+ } else {
+ lowerCharArray =
+ ConditionalSpecialCasing.toLowerCaseCharArray(this, i, locale);
+ }
} else if (srcCount == 2) {
resultOffset += Character.toChars(lowerChar, result, i + resultOffset) - srcCount;
continue;
@@ -2537,19 +2481,18 @@
int mapLen = lowerCharArray.length;
if (mapLen > srcCount) {
char[] result2 = new char[result.length + mapLen - srcCount];
- System.arraycopy(result, 0, result2, 0,
- i + resultOffset);
+ System.arraycopy(result, 0, result2, 0, i + resultOffset);
result = result2;
}
- for (int x=0; x<mapLen; ++x) {
- result[i+resultOffset+x] = lowerCharArray[x];
+ for (int x = 0; x < mapLen; ++x) {
+ result[i + resultOffset + x] = lowerCharArray[x];
}
resultOffset += (mapLen - srcCount);
} else {
- result[i+resultOffset] = (char)lowerChar;
+ result[i + resultOffset] = (char)lowerChar;
}
}
- return new String(0, count+resultOffset, result);
+ return new String(result, 0, len + resultOffset);
}
/**
@@ -2628,23 +2571,24 @@
throw new NullPointerException();
}
- int firstLower;
+ int firstLower;
+ final int len = value.length;
/* Now check if there are any characters that need to be changed. */
scan: {
- for (firstLower = 0 ; firstLower < count; ) {
- int c = (int)value[offset+firstLower];
+ for (firstLower = 0 ; firstLower < len; ) {
+ int c = (int)value[firstLower];
int srcCount;
- if ((c >= Character.MIN_HIGH_SURROGATE) &&
- (c <= Character.MAX_HIGH_SURROGATE)) {
+ if ((c >= Character.MIN_HIGH_SURROGATE)
+ && (c <= Character.MAX_HIGH_SURROGATE)) {
c = codePointAt(firstLower);
srcCount = Character.charCount(c);
} else {
srcCount = 1;
}
int upperCaseChar = Character.toUpperCaseEx(c);
- if ((upperCaseChar == Character.ERROR) ||
- (c != upperCaseChar)) {
+ if ((upperCaseChar == Character.ERROR)
+ || (c != upperCaseChar)) {
break scan;
}
firstLower += srcCount;
@@ -2652,22 +2596,22 @@
return this;
}
- char[] result = new char[count]; /* may grow */
- int resultOffset = 0; /* result may grow, so i+resultOffset
- * is the write location in result */
+ char[] result = new char[len]; /* may grow */
+ int resultOffset = 0; /* result may grow, so i+resultOffset
+ * is the write location in result */
/* Just copy the first few upperCase characters. */
- System.arraycopy(value, offset, result, 0, firstLower);
+ System.arraycopy(value, 0, result, 0, firstLower);
String lang = locale.getLanguage();
boolean localeDependent =
- (lang == "tr" || lang == "az" || lang == "lt");
+ (lang == "tr" || lang == "az" || lang == "lt");
char[] upperCharArray;
int upperChar;
int srcChar;
int srcCount;
- for (int i = firstLower; i < count; i += srcCount) {
- srcChar = (int)value[offset+i];
+ for (int i = firstLower; i < len; i += srcCount) {
+ srcChar = (int)value[i];
if ((char)srcChar >= Character.MIN_HIGH_SURROGATE &&
(char)srcChar <= Character.MAX_HIGH_SURROGATE) {
srcChar = codePointAt(i);
@@ -2680,12 +2624,12 @@
} else {
upperChar = Character.toUpperCaseEx(srcChar);
}
- if ((upperChar == Character.ERROR) ||
- (upperChar >= Character.MIN_SUPPLEMENTARY_CODE_POINT)) {
+ if ((upperChar == Character.ERROR)
+ || (upperChar >= Character.MIN_SUPPLEMENTARY_CODE_POINT)) {
if (upperChar == Character.ERROR) {
if (localeDependent) {
upperCharArray =
- ConditionalSpecialCasing.toUpperCaseCharArray(this, i, locale);
+ ConditionalSpecialCasing.toUpperCaseCharArray(this, i, locale);
} else {
upperCharArray = Character.toUpperCaseCharArray(srcChar);
}
@@ -2700,19 +2644,18 @@
int mapLen = upperCharArray.length;
if (mapLen > srcCount) {
char[] result2 = new char[result.length + mapLen - srcCount];
- System.arraycopy(result, 0, result2, 0,
- i + resultOffset);
+ System.arraycopy(result, 0, result2, 0, i + resultOffset);
result = result2;
}
- for (int x=0; x<mapLen; ++x) {
- result[i+resultOffset+x] = upperCharArray[x];
+ for (int x = 0; x < mapLen; ++x) {
+ result[i + resultOffset + x] = upperCharArray[x];
}
resultOffset += (mapLen - srcCount);
} else {
- result[i+resultOffset] = (char)upperChar;
+ result[i + resultOffset] = (char)upperChar;
}
}
- return new String(0, count+resultOffset, result);
+ return new String(result, 0, len + resultOffset);
}
/**
@@ -2770,18 +2713,17 @@
* trailing white space.
*/
public String trim() {
- int len = count;
+ int len = value.length;
int st = 0;
- int off = offset; /* avoid getfield opcode */
char[] val = value; /* avoid getfield opcode */
- while ((st < len) && (val[off + st] <= ' ')) {
+ while ((st < len) && (val[st] <= ' ')) {
st++;
}
- while ((st < len) && (val[off + len - 1] <= ' ')) {
+ while ((st < len) && (val[len - 1] <= ' ')) {
len--;
}
- return ((st > 0) || (len < count)) ? substring(st, len) : this;
+ return ((st > 0) || (len < value.length)) ? substring(st, len) : this;
}
/**
@@ -2801,8 +2743,9 @@
* the character sequence represented by this string.
*/
public char[] toCharArray() {
- char result[] = new char[count];
- getChars(0, count, result, 0);
+ // Cannot use Arrays.copyOf because of class initialization order issues
+ char result[] = new char[value.length];
+ System.arraycopy(value, 0, result, 0, value.length);
return result;
}
@@ -2844,7 +2787,7 @@
* @see java.util.Formatter
* @since 1.5
*/
- public static String format(String format, Object ... args) {
+ public static String format(String format, Object... args) {
return new Formatter().format(format, args).toString();
}
@@ -2888,7 +2831,7 @@
* @see java.util.Formatter
* @since 1.5
*/
- public static String format(Locale l, String format, Object ... args) {
+ public static String format(Locale l, String format, Object... args) {
return new Formatter(l).format(format, args).toString();
}
@@ -2968,7 +2911,7 @@
* character array.
*/
public static String copyValueOf(char data[]) {
- return copyValueOf(data, 0, data.length);
+ return new String(data);
}
/**
@@ -2993,7 +2936,7 @@
*/
public static String valueOf(char c) {
char data[] = {c};
- return new String(0, 1, data);
+ return new String(data, true);
}
/**
@@ -3077,4 +3020,100 @@
*/
public native String intern();
+ /**
+ * Seed value used for each alternative hash calculated.
+ */
+ private static final int HASHING_SEED;
+
+ static {
+ long nanos = System.nanoTime();
+ long now = System.currentTimeMillis();
+ int SEED_MATERIAL[] = {
+ System.identityHashCode(String.class),
+ System.identityHashCode(System.class),
+ (int) (nanos >>> 32),
+ (int) nanos,
+ (int) (now >>> 32),
+ (int) now,
+ (int) (System.nanoTime() >>> 2)
+ };
+
+ // Use murmur3 to scramble the seeding material.
+ // Inline implementation to avoid loading classes
+ int h1 = 0;
+
+ // body
+ for(int k1 : SEED_MATERIAL) {
+ k1 *= 0xcc9e2d51;
+ k1 = (k1 << 15) | (k1 >>> 17);
+ k1 *= 0x1b873593;
+
+ h1 ^= k1;
+ h1 = (h1 << 13) | (h1 >>> 19);
+ h1 = h1 * 5 + 0xe6546b64;
+ }
+
+ // tail (always empty, as body is always 32-bit chunks)
+
+ // finalization
+
+ h1 ^= SEED_MATERIAL.length * 4;
+
+ // finalization mix force all bits of a hash block to avalanche
+ h1 ^= h1 >>> 16;
+ h1 *= 0x85ebca6b;
+ h1 ^= h1 >>> 13;
+ h1 *= 0xc2b2ae35;
+ h1 ^= h1 >>> 16;
+
+ HASHING_SEED = h1;
+ }
+
+ /**
+ * Cached value of the hashing algorithm result
+ */
+ private transient int hash32 = 0;
+
+ /**
+ * Return a 32-bit hash code value for this object.
+ * <p>
+ * The general contract of {@code hash32} is:
+ * <ul>
+ * <li>Whenever it is invoked on the same object more than once during
+ * an execution of a Java application, the {@code hash32} method
+ * must consistently return the same integer, provided no information
+ * used in {@code equals} comparisons on the object is modified.
+ * This integer need not remain consistent from one execution of an
+ * application to another execution of the same application.
+ * <li>If two objects are equal according to the {@code equals(Object)}
+ * method, then calling the {@code hash32} method on each of
+ * the two objects must produce the same integer result.
+ * <li>It is <em>not</em> required that if two objects are unequal
+ * according to the {@link java.lang.Object#equals(java.lang.Object)}
+ * method, then calling the {@code hash32} method on each of the
+ * two objects must produce distinct integer results. However, the
+ * programmer should be aware that producing distinct integer results
+ * for unequal objects may improve the performance of hash tables.
+ * </ul>
+ * <p/>
+ * The hash value will never be zero.
+ *
+ * @return a hash code value for this object.
+ * @see java.lang.Object#equals(java.lang.Object)
+ */
+ public int hash32() {
+ int h = hash32;
+ if (0 == h) {
+ // harmless data race on hash32 here.
+ h = sun.misc.Hashing.murmur3_32(HASHING_SEED, value, 0, value.length);
+
+ // ensure result is not zero to avoid recalcing
+ h = (0 != h) ? h : 1;
+
+ hash32 = h;
+ }
+
+ return h;
+ }
+
}
--- a/jdk/src/share/classes/java/lang/StringCoding.java Thu May 31 17:07:28 2012 -0400
+++ b/jdk/src/share/classes/java/lang/StringCoding.java Thu May 31 17:10:57 2012 -0400
@@ -250,6 +250,7 @@
static char[] decode(byte[] ba, int off, int len) {
String csn = Charset.defaultCharset().name();
try {
+ // use charset name decode() variant which provides caching.
return decode(csn, ba, off, len);
} catch (UnsupportedEncodingException x) {
warnUnsupportedCharset(csn);
@@ -382,6 +383,7 @@
static byte[] encode(char[] ca, int off, int len) {
String csn = Charset.defaultCharset().name();
try {
+ // use charset name encode() variant which provides caching.
return encode(csn, ca, off, len);
} catch (UnsupportedEncodingException x) {
warnUnsupportedCharset(csn);
--- a/jdk/src/share/classes/java/util/HashMap.java Thu May 31 17:07:28 2012 -0400
+++ b/jdk/src/share/classes/java/util/HashMap.java Thu May 31 17:10:57 2012 -0400
@@ -175,6 +175,35 @@
*/
transient int modCount;
+ private static class Holder {
+ /**
+ *
+ */
+ static final sun.misc.Unsafe UNSAFE;
+
+ /**
+ * Offset of "final" hashSeed field we must set in
+ * readObject() method.
+ */
+ static final long HASHSEED_OFFSET;
+
+ static {
+ try {
+ UNSAFE = sun.misc.Unsafe.getUnsafe();
+ HASHSEED_OFFSET = UNSAFE.objectFieldOffset(
+ HashMap.class.getDeclaredField("hashSeed"));
+ } catch (NoSuchFieldException | SecurityException e) {
+ throw new InternalError("Failed to record hashSeed offset", e);
+ }
+ }
+ }
+
+ /**
+ * A randomizing value associated with this instance that is applied to
+ * hash code of keys to make hash collisions harder to find.
+ */
+ transient final int hashSeed = sun.misc.Hashing.randomHashSeed(this);
+
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and load factor.
@@ -200,7 +229,7 @@
capacity <<= 1;
this.loadFactor = loadFactor;
- threshold = (int)(capacity * loadFactor);
+ threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
init();
}
@@ -221,10 +250,7 @@
* (16) and the default load factor (0.75).
*/
public HashMap() {
- this.loadFactor = DEFAULT_LOAD_FACTOR;
- threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
- table = new Entry[DEFAULT_INITIAL_CAPACITY];
- init();
+ this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
/**
@@ -255,13 +281,20 @@
}
/**
- * Applies a supplemental hash function to a given hashCode, which
- * defends against poor quality hash functions. This is critical
- * because HashMap uses power-of-two length hash tables, that
+ * Retrieve object hash code and applies a supplemental hash function to the
+ * result hash, which defends against poor quality hash functions. This is
+ * critical because HashMap uses power-of-two length hash tables, that
* otherwise encounter collisions for hashCodes that do not differ
- * in lower bits. Note: Null keys always map to hash 0, thus index 0.
+ * in lower bits.
*/
- static int hash(int h) {
+ final int hash(Object k) {
+ int h = hashSeed;
+ if (k instanceof String) {
+ return ((String)k).hash32();
+ }
+
+ h ^= k.hashCode();
+
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
@@ -313,32 +346,9 @@
*/
@SuppressWarnings("unchecked")
public V get(Object key) {
- if (key == null)
- return (V)getForNullKey();
- int hash = hash(key.hashCode());
- for (Entry<?,?> e = table[indexFor(hash, table.length)];
- e != null;
- e = e.next) {
- Object k;
- if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
- return (V)e.value;
- }
- return null;
- }
+ Entry<K,V> entry = getEntry(key);
- /**
- * Offloaded version of get() to look up null keys. Null keys map
- * to index 0. This null case is split out into separate methods
- * for the sake of performance in the two most commonly used
- * operations (get and put), but incorporated with conditionals in
- * others.
- */
- private Object getForNullKey() {
- for (Entry<?,?> e = table[0]; e != null; e = e.next) {
- if (e.key == null)
- return e.value;
- }
- return null;
+ return null == entry ? null : entry.getValue();
}
/**
@@ -360,7 +370,7 @@
*/
@SuppressWarnings("unchecked")
final Entry<K,V> getEntry(Object key) {
- int hash = (key == null) ? 0 : hash(key.hashCode());
+ int hash = (key == null) ? 0 : hash(key);
for (Entry<?,?> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
@@ -388,7 +398,7 @@
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
- int hash = hash(key.hashCode());
+ int hash = hash(key);
int i = indexFor(hash, table.length);
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>)table[i];
@@ -433,7 +443,7 @@
* addEntry.
*/
private void putForCreate(K key, V value) {
- int hash = (key == null) ? 0 : hash(key.hashCode());
+ int hash = null == key ? 0 : hash(key);
int i = indexFor(hash, table.length);
/**
@@ -484,7 +494,7 @@
Entry<?,?>[] newTable = new Entry<?,?>[newCapacity];
transfer(newTable);
table = newTable;
- threshold = (int)(newCapacity * loadFactor);
+ threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
/**
@@ -494,19 +504,17 @@
void transfer(Entry<?,?>[] newTable) {
Entry<?,?>[] src = table;
int newCapacity = newTable.length;
- for (int j = 0; j < src.length; j++) {
- Entry<K,V> e = (Entry<K,V>)src[j];
- if (e != null) {
- src[j] = null;
- do {
- Entry<K,V> next = e.next;
- int i = indexFor(e.hash, newCapacity);
- e.next = (Entry<K,V>)newTable[i];
- newTable[i] = e;
- e = next;
- } while (e != null);
+ for (int j = 0; j < src.length; j++ ) {
+ Entry<K,V> e = (Entry<K,V>) src[j];
+ while(null != e) {
+ Entry<K,V> next = e.next;
+ int i = indexFor(e.hash, newCapacity);
+ e.next = (Entry<K,V>) newTable[i];
+ newTable[i] = e;
+ e = next;
}
}
+ Arrays.fill(table, null);
}
/**
@@ -566,7 +574,7 @@
* for this key.
*/
final Entry<K,V> removeEntryForKey(Object key) {
- int hash = (key == null) ? 0 : hash(key.hashCode());
+ int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
@SuppressWarnings("unchecked")
Entry<K,V> prev = (Entry<K,V>)table[i];
@@ -594,7 +602,8 @@
}
/**
- * Special version of remove for EntrySet.
+ * Special version of remove for EntrySet using {@code Map.Entry.equals()}
+ * for matching.
*/
final Entry<K,V> removeMapping(Object o) {
if (!(o instanceof Map.Entry))
@@ -773,11 +782,13 @@
* Subclass overrides this to alter the behavior of put method.
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
- @SuppressWarnings("unchecked")
- Entry<K,V> e = (Entry<K,V>)table[bucketIndex];
- table[bucketIndex] = new Entry<>(hash, key, value, e);
- if (size++ >= threshold)
+ if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
+ hash = hash(key);
+ bucketIndex = indexFor(hash, table.length);
+ }
+
+ createEntry(hash, key, value, bucketIndex);
}
/**
@@ -841,7 +852,6 @@
HashMap.this.removeEntryForKey(k);
expectedModCount = modCount;
}
-
}
private final class ValueIterator extends HashIterator<V> {
@@ -1021,9 +1031,8 @@
s.writeInt(size);
// Write out keys and values (alternating)
- if (i != null) {
- while (i.hasNext()) {
- Map.Entry<K,V> e = i.next();
+ if (size > 0) {
+ for(Map.Entry<K,V> e : entrySet0()) {
s.writeObject(e.getKey());
s.writeObject(e.getValue());
}
@@ -1033,26 +1042,50 @@
private static final long serialVersionUID = 362498820763181265L;
/**
- * Reconstitute the <tt>HashMap</tt> instance from a stream (i.e.,
+ * Reconstitute the {@code HashMap} instance from a stream (i.e.,
* deserialize it).
*/
private void readObject(java.io.ObjectInputStream s)
throws IOException, ClassNotFoundException
{
- // Read in the threshold, loadfactor, and any hidden stuff
+ // Read in the threshold (ignored), loadfactor, and any hidden stuff
s.defaultReadObject();
+ if (loadFactor <= 0 || Float.isNaN(loadFactor))
+ throw new InvalidObjectException("Illegal load factor: " +
+ loadFactor);
+
+ // set hashMask
+ Holder.UNSAFE.putIntVolatile(this, Holder.HASHSEED_OFFSET,
+ sun.misc.Hashing.randomHashSeed(this));
// Read in number of buckets and allocate the bucket array;
- int numBuckets = s.readInt();
- table = new Entry[numBuckets];
+ s.readInt(); // ignored
+
+ // Read number of mappings
+ int mappings = s.readInt();
+ if (mappings < 0)
+ throw new InvalidObjectException("Illegal mappings count: " +
+ mappings);
+ int initialCapacity = (int) Math.min(
+ // capacity chosen by number of mappings
+ // and desired load (if >= 0.25)
+ mappings * Math.min(1 / loadFactor, 4.0f),
+ // we have limits...
+ HashMap.MAXIMUM_CAPACITY);
+ int capacity = 1;
+ // find smallest power of two which holds all mappings
+ while (capacity < initialCapacity) {
+ capacity <<= 1;
+ }
+
+ table = new Entry[capacity];
+ threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
init(); // Give subclass a chance to do its thing.
- // Read in size (number of Mappings)
- int size = s.readInt();
// Read the keys and values, and put the mappings in the HashMap
- for (int i=0; i<size; i++) {
+ for (int i=0; i<mappings; i++) {
@SuppressWarnings("unchecked")
K key = (K) s.readObject();
@SuppressWarnings("unchecked")
--- a/jdk/src/share/classes/java/util/Hashtable.java Thu May 31 17:07:28 2012 -0400
+++ b/jdk/src/share/classes/java/util/Hashtable.java Thu May 31 17:10:57 2012 -0400
@@ -163,6 +163,52 @@
/** use serialVersionUID from JDK 1.0.2 for interoperability */
private static final long serialVersionUID = 1421746759512286392L;
+ private static class Holder {
+ // Unsafe mechanics
+ /**
+ *
+ */
+ static final sun.misc.Unsafe UNSAFE;
+
+ /**
+ * Offset of "final" hashSeed field we must set in
+ * readObject() method.
+ */
+ static final long HASHSEED_OFFSET;
+
+ static {
+ try {
+ UNSAFE = sun.misc.Unsafe.getUnsafe();
+ HASHSEED_OFFSET = UNSAFE.objectFieldOffset(
+ Hashtable.class.getDeclaredField("hashSeed"));
+ } catch (NoSuchFieldException | SecurityException e) {
+ throw new InternalError("Failed to record hashSeed offset", e);
+ }
+ }
+ }
+
+ /**
+ * A randomizing value associated with this instance that is applied to
+ * hash code of keys to make hash collisions harder to find.
+ */
+ transient final int hashSeed = sun.misc.Hashing.randomHashSeed(this);
+
+ private int hash(Object k) {
+ int h = hashSeed;
+
+ if (k instanceof String) {
+ return ((String)k).hash32();
+ } else {
+ h ^= k.hashCode();
+
+ // This function ensures that hashCodes that differ only by
+ // constant multiples at each bit position have a bounded
+ // number of collisions (approximately 8 at default load factor).
+ h ^= (h >>> 20) ^ (h >>> 12);
+ return h ^ (h >>> 7) ^ (h >>> 4);
+ }
+ }
+
/**
* Constructs a new, empty hashtable with the specified initial
* capacity and the specified load factor.
@@ -183,7 +229,7 @@
initialCapacity = 1;
this.loadFactor = loadFactor;
table = new Entry<?,?>[initialCapacity];
- threshold = (int)(initialCapacity * loadFactor);
+ threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}
/**
@@ -327,7 +373,7 @@
*/
public synchronized boolean containsKey(Object key) {
Entry<?,?> tab[] = table;
- int hash = key.hashCode();
+ int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
@@ -355,7 +401,7 @@
@SuppressWarnings("unchecked")
public synchronized V get(Object key) {
Entry<?,?> tab[] = table;
- int hash = key.hashCode();
+ int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
@@ -396,7 +442,7 @@
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
modCount++;
- threshold = (int)(newCapacity * loadFactor);
+ threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
table = newMap;
for (int i = oldCapacity ; i-- > 0 ;) {
@@ -436,7 +482,7 @@
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
- int hash = key.hashCode();
+ int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
@@ -454,6 +500,7 @@
rehash();
tab = table;
+ hash = hash(key);
index = (hash & 0x7FFFFFFF) % tab.length;
}
@@ -476,7 +523,7 @@
*/
public synchronized V remove(Object key) {
Entry<?,?> tab[] = table;
- int hash = key.hashCode();
+ int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>)tab[index];
@@ -685,7 +732,7 @@
Map.Entry<?,?> entry = (Map.Entry<?,?>)o;
Object key = entry.getKey();
Entry<?,?>[] tab = table;
- int hash = key.hashCode();
+ int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<?,?> e = tab[index]; e != null; e = e.next)
@@ -700,7 +747,7 @@
Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
Object key = entry.getKey();
Entry<?,?>[] tab = table;
- int hash = key.hashCode();
+ int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
@@ -835,9 +882,13 @@
loadFactor = -loadFactor; // Mark hashCode computation in progress
Entry<?,?>[] tab = table;
- for (int i = 0; i < tab.length; i++)
- for (Entry<?,?> e = tab[i]; e != null; e = e.next)
- h += e.key.hashCode() ^ e.value.hashCode();
+ for (Entry<?,?> entry : tab) {
+ while (entry != null) {
+ h += entry.hashCode();
+ entry = entry.next;
+ }
+ }
+
loadFactor = -loadFactor; // Mark hashCode computation complete
return h;
@@ -894,6 +945,10 @@
// Read in the length, threshold, and loadfactor
s.defaultReadObject();
+ // set hashMask
+ Holder.UNSAFE.putIntVolatile(this, Holder.HASHSEED_OFFSET,
+ sun.misc.Hashing.randomHashSeed(this));
+
// Read the original length of the array and number of elements
int origlength = s.readInt();
int elements = s.readInt();
@@ -907,7 +962,8 @@
length--;
if (origlength > 0 && length > origlength)
length = origlength;
- Entry<?,?>[] table = new Entry<?,?>[length];
+ table = new Entry<?,?>[length];
+ threshold = (int)Math.min(length * loadFactor, MAX_ARRAY_SIZE + 1);
count = 0;
// Read the number of elements and then all the key/value objects
@@ -919,7 +975,6 @@
// synch could be eliminated for performance
reconstitutionPut(table, key, value);
}
- this.table = table;
}
/**
@@ -941,7 +996,7 @@
}
// Makes sure the key is not already in the hashtable.
// This should not happen in deserialized version.
- int hash = key.hashCode();
+ int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
@@ -956,17 +1011,17 @@
}
/**
- * Hashtable collision list.
+ * Hashtable bucket collision list entry
*/
private static class Entry<K,V> implements Map.Entry<K,V> {
- int hash;
+ final int hash;
K key;
V value;
Entry<K,V> next;
protected Entry(int hash, K key, V value, Entry<K,V> next) {
this.hash = hash;
- this.key = key;
+ this.key = key;
this.value = value;
this.next = next;
}
--- a/jdk/src/share/classes/java/util/LinkedHashMap.java Thu May 31 17:07:28 2012 -0400
+++ b/jdk/src/share/classes/java/util/LinkedHashMap.java Thu May 31 17:10:57 2012 -0400
@@ -236,6 +236,7 @@
* readObject) before any entries are inserted into the map. Initializes
* the chain.
*/
+ @Override
void init() {
header = new Entry<>(-1, null, null, null);
header.before = header.after = header;
@@ -246,6 +247,7 @@
* by superclass resize. It is overridden for performance, as it is
* faster to iterate using our linked list.
*/
+ @Override
@SuppressWarnings("unchecked")
void transfer(HashMap.Entry[] newTable) {
int newCapacity = newTable.length;
@@ -421,15 +423,12 @@
* removes the eldest entry if appropriate.
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
- createEntry(hash, key, value, bucketIndex);
+ super.addEntry(hash, key, value, bucketIndex);
- // Remove eldest entry if instructed, else grow capacity if appropriate
+ // Remove eldest entry if instructed
Entry<K,V> eldest = header.after;
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
- } else {
- if (size >= threshold)
- resize(2 * table.length);
}
}
--- a/jdk/src/share/classes/java/util/WeakHashMap.java Thu May 31 17:07:28 2012 -0400
+++ b/jdk/src/share/classes/java/util/WeakHashMap.java Thu May 31 17:10:57 2012 -0400
@@ -184,6 +184,12 @@
*/
int modCount;
+ /**
+ * A randomizing value associated with this instance that is applied to
+ * hash code of keys to make hash collisions harder to find.
+ */
+ transient final int hashSeed = sun.misc.Hashing.randomHashSeed(this);
+
@SuppressWarnings("unchecked")
private Entry<K,V>[] newTable(int n) {
return (Entry<K,V>[]) new Entry<?,?>[n];
@@ -232,9 +238,7 @@
* capacity (16) and load factor (0.75).
*/
public WeakHashMap() {
- this.loadFactor = DEFAULT_LOAD_FACTOR;
- threshold = DEFAULT_INITIAL_CAPACITY;
- table = newTable(DEFAULT_INITIAL_CAPACITY);
+ this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
/**
@@ -248,7 +252,8 @@
* @since 1.3
*/
public WeakHashMap(Map<? extends K, ? extends V> m) {
- this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, 16),
+ this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
+ DEFAULT_INITIAL_CAPACITY),
DEFAULT_LOAD_FACTOR);
putAll(m);
}
@@ -283,6 +288,28 @@
}
/**
+ * Retrieve object hash code and applies a supplemental hash function to the
+ * result hash, which defends against poor quality hash functions. This is
+ * critical because HashMap uses power-of-two length hash tables, that
+ * otherwise encounter collisions for hashCodes that do not differ
+ * in lower bits.
+ */
+ int hash(Object k) {
+ int h = hashSeed;
+ if (k instanceof String) {
+ return ((String) k).hash32();
+ } else {
+ h ^= k.hashCode();
+ }
+
+ // This function ensures that hashCodes that differ only by
+ // constant multiples at each bit position have a bounded
+ // number of collisions (approximately 8 at default load factor).
+ h ^= (h >>> 20) ^ (h >>> 12);
+ return h ^ (h >>> 7) ^ (h >>> 4);
+ }
+
+ /**
* Returns index for hash code h.
*/
private static int indexFor(int h, int length) {
@@ -371,7 +398,7 @@
*/
public V get(Object key) {
Object k = maskNull(key);
- int h = HashMap.hash(k.hashCode());
+ int h = hash(k);
Entry<K,V>[] tab = getTable();
int index = indexFor(h, tab.length);
Entry<K,V> e = tab[index];
@@ -401,7 +428,7 @@
*/
Entry<K,V> getEntry(Object key) {
Object k = maskNull(key);
- int h = HashMap.hash(k.hashCode());
+ int h = hash(k);
Entry<K,V>[] tab = getTable();
int index = indexFor(h, tab.length);
Entry<K,V> e = tab[index];
@@ -424,7 +451,7 @@
*/
public V put(K key, V value) {
Object k = maskNull(key);
- int h = HashMap.hash(k.hashCode());
+ int h = hash(k);
Entry<K,V>[] tab = getTable();
int i = indexFor(h, tab.length);
@@ -566,7 +593,7 @@
*/
public V remove(Object key) {
Object k = maskNull(key);
- int h = HashMap.hash(k.hashCode());
+ int h = hash(k);
Entry<K,V>[] tab = getTable();
int i = indexFor(h, tab.length);
Entry<K,V> prev = tab[i];
@@ -597,7 +624,7 @@
Entry<K,V>[] tab = getTable();
Map.Entry<?,?> entry = (Map.Entry<?,?>)o;
Object k = maskNull(entry.getKey());
- int h = HashMap.hash(k.hashCode());
+ int h = hash(k);
int i = indexFor(h, tab.length);
Entry<K,V> prev = tab[i];
Entry<K,V> e = prev;
--- a/jdk/src/share/classes/java/util/concurrent/ConcurrentHashMap.java Thu May 31 17:07:28 2012 -0400
+++ b/jdk/src/share/classes/java/util/concurrent/ConcurrentHashMap.java Thu May 31 17:10:57 2012 -0400
@@ -175,6 +175,12 @@
/* ---------------- Fields -------------- */
/**
+ * A randomizing value associated with this instance that is applied to
+ * hash code of keys to make hash collisions harder to find.
+ */
+ private transient final int hashSeed = sun.misc.Hashing.randomHashSeed(this);
+
+ /**
* Mask value for indexing into segments. The upper bits of a
* key's hash code are used to choose the segment.
*/
@@ -262,7 +268,15 @@
* that otherwise encounter collisions for hashCodes that do not
* differ in lower or upper bits.
*/
- private static int hash(int h) {
+ private int hash(Object k) {
+ int h = hashSeed;
+
+ if (k instanceof String) {
+ return ((String) k).hash32();
+ }
+
+ h ^= k.hashCode();
+
// Spread bits to regularize both segment and index locations,
// using variant of single-word Wang/Jenkins hash.
h += (h << 15) ^ 0xffffcd7d;
@@ -917,7 +931,7 @@
public V get(Object key) {
Segment<K,V> s; // manually integrate access methods to reduce overhead
HashEntry<K,V>[] tab;
- int h = hash(key.hashCode());
+ int h = hash(key);
long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
(tab = s.table) != null) {
@@ -945,7 +959,7 @@
public boolean containsKey(Object key) {
Segment<K,V> s; // same as get() except no need for volatile value read
HashEntry<K,V>[] tab;
- int h = hash(key.hashCode());
+ int h = hash(key);
long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
(tab = s.table) != null) {
@@ -1054,7 +1068,7 @@
Segment<K,V> s;
if (value == null)
throw new NullPointerException();
- int hash = hash(key.hashCode());
+ int hash = hash(key);
int j = (hash >>> segmentShift) & segmentMask;
if ((s = (Segment<K,V>)UNSAFE.getObject // nonvolatile; recheck
(segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment
@@ -1074,7 +1088,7 @@
Segment<K,V> s;
if (value == null)
throw new NullPointerException();
- int hash = hash(key.hashCode());
+ int hash = hash(key);
int j = (hash >>> segmentShift) & segmentMask;
if ((s = (Segment<K,V>)UNSAFE.getObject
(segments, (j << SSHIFT) + SBASE)) == null)
@@ -1104,7 +1118,7 @@
* @throws NullPointerException if the specified key is null
*/
public V remove(Object key) {
- int hash = hash(key.hashCode());
+ int hash = hash(key);
Segment<K,V> s = segmentForHash(hash);
return s == null ? null : s.remove(key, hash, null);
}
@@ -1115,7 +1129,7 @@
* @throws NullPointerException if the specified key is null
*/
public boolean remove(Object key, Object value) {
- int hash = hash(key.hashCode());
+ int hash = hash(key);
Segment<K,V> s;
return value != null && (s = segmentForHash(hash)) != null &&
s.remove(key, hash, value) != null;
@@ -1127,7 +1141,7 @@
* @throws NullPointerException if any of the arguments are null
*/
public boolean replace(K key, V oldValue, V newValue) {
- int hash = hash(key.hashCode());
+ int hash = hash(key);
if (oldValue == null || newValue == null)
throw new NullPointerException();
Segment<K,V> s = segmentForHash(hash);
@@ -1142,7 +1156,7 @@
* @throws NullPointerException if the specified key or value is null
*/
public V replace(K key, V value) {
- int hash = hash(key.hashCode());
+ int hash = hash(key);
if (value == null)
throw new NullPointerException();
Segment<K,V> s = segmentForHash(hash);
@@ -1473,6 +1487,10 @@
throws java.io.IOException, ClassNotFoundException {
s.defaultReadObject();
+ // set hashMask
+ UNSAFE.putIntVolatile(this, HASHSEED_OFFSET,
+ sun.misc.Hashing.randomHashSeed(this));
+
// Re-initialize segments to be minimally sized, and let grow.
int cap = MIN_SEGMENT_TABLE_CAPACITY;
final Segment<K,V>[] segments = this.segments;
@@ -1500,6 +1518,7 @@
private static final int SSHIFT;
private static final long TBASE;
private static final int TSHIFT;
+ private static final long HASHSEED_OFFSET;
static {
int ss, ts;
@@ -1511,6 +1530,8 @@
SBASE = UNSAFE.arrayBaseOffset(sc);
ts = UNSAFE.arrayIndexScale(tc);
ss = UNSAFE.arrayIndexScale(sc);
+ HASHSEED_OFFSET = UNSAFE.objectFieldOffset(
+ ConcurrentHashMap.class.getDeclaredField("hashSeed"));
} catch (Exception e) {
throw new Error(e);
}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/src/share/classes/sun/misc/Hashing.java Thu May 31 17:10:57 2012 -0400
@@ -0,0 +1,251 @@
+/*
+ * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation. Oracle designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Oracle in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package sun.misc;
+
+import java.util.Random;
+
+/**
+ * Hashing utilities.
+ *
+ * Little endian implementations of Murmur3 hashing.
+ */
+public class Hashing {
+
+ /**
+ * Static utility methods only.
+ */
+ private Hashing() {
+ throw new Error("No instances");
+ }
+
+ public static int murmur3_32(byte[] data) {
+ return murmur3_32(0, data, 0, data.length);
+ }
+
+ public static int murmur3_32(int seed, byte[] data) {
+ return murmur3_32(seed, data, 0, data.length);
+ }
+
+ @SuppressWarnings("fallthrough")
+ public static int murmur3_32(int seed, byte[] data, int offset, int len) {
+ int h1 = seed;
+ int count = len;
+
+ // body
+ while (count >= 4) {
+ int k1 = (data[offset] & 0x0FF)
+ | (data[offset + 1] & 0x0FF) << 8
+ | (data[offset + 2] & 0x0FF) << 16
+ | data[offset + 3] << 24;
+
+ count -= 4;
+ offset += 4;
+
+ k1 *= 0xcc9e2d51;
+ k1 = Integer.rotateLeft(k1, 15);
+ k1 *= 0x1b873593;
+
+ h1 ^= k1;
+ h1 = Integer.rotateLeft(h1, 13);
+ h1 = h1 * 5 + 0xe6546b64;
+ }
+
+ // tail
+
+ if (count > 0) {
+ int k1 = 0;
+
+ switch (count) {
+ case 3:
+ k1 ^= (data[offset + 2] & 0xff) << 16;
+ // fall through
+ case 2:
+ k1 ^= (data[offset + 1] & 0xff) << 8;
+ // fall through
+ case 1:
+ k1 ^= (data[offset] & 0xff);
+ // fall through
+ default:
+ k1 *= 0xcc9e2d51;
+ k1 = Integer.rotateLeft(k1, 15);
+ k1 *= 0x1b873593;
+ h1 ^= k1;
+ }
+ }
+
+ // finalization
+
+ h1 ^= len;
+
+ // finalization mix force all bits of a hash block to avalanche
+ h1 ^= h1 >>> 16;
+ h1 *= 0x85ebca6b;
+ h1 ^= h1 >>> 13;
+ h1 *= 0xc2b2ae35;
+ h1 ^= h1 >>> 16;
+
+ return h1;
+ }
+
+ public static int murmur3_32(char[] data) {
+ return murmur3_32(0, data, 0, data.length);
+ }
+
+ public static int murmur3_32(int seed, char[] data) {
+ return murmur3_32(seed, data, 0, data.length);
+ }
+
+ public static int murmur3_32(int seed, char[] data, int offset, int len) {
+ int h1 = seed;
+
+ int off = offset;
+ int count = len;
+
+ // body
+ while (count >= 2) {
+ int k1 = (data[off++] & 0xFFFF) | (data[off++] << 16);
+
+ count -= 2;
+
+ k1 *= 0xcc9e2d51;
+ k1 = Integer.rotateLeft(k1, 15);
+ k1 *= 0x1b873593;
+
+ h1 ^= k1;
+ h1 = Integer.rotateLeft(h1, 13);
+ h1 = h1 * 5 + 0xe6546b64;
+ }
+
+ // tail
+
+ if (count > 0) {
+ int k1 = data[off];
+
+ k1 *= 0xcc9e2d51;
+ k1 = Integer.rotateLeft(k1, 15);
+ k1 *= 0x1b873593;
+ h1 ^= k1;
+ }
+
+ // finalization
+
+ h1 ^= len * (Character.SIZE / Byte.SIZE);
+
+ // finalization mix force all bits of a hash block to avalanche
+ h1 ^= h1 >>> 16;
+ h1 *= 0x85ebca6b;
+ h1 ^= h1 >>> 13;
+ h1 *= 0xc2b2ae35;
+ h1 ^= h1 >>> 16;
+
+ return h1;
+ }
+
+ public static int murmur3_32(int[] data) {
+ return murmur3_32(0, data, 0, data.length);
+ }
+
+ public static int murmur3_32(int seed, int[] data) {
+ return murmur3_32(seed, data, 0, data.length);
+ }
+
+ public static int murmur3_32(int seed, int[] data, int offset, int len) {
+ int h1 = seed;
+
+ int off = offset;
+ int end = offset + len;
+
+ // body
+ while (off < end) {
+ int k1 = data[off++];
+
+ k1 *= 0xcc9e2d51;
+ k1 = Integer.rotateLeft(k1, 15);
+ k1 *= 0x1b873593;
+
+ h1 ^= k1;
+ h1 = Integer.rotateLeft(h1, 13);
+ h1 = h1 * 5 + 0xe6546b64;
+ }
+
+ // tail (always empty, as body is always 32-bit chunks)
+
+ // finalization
+
+ h1 ^= len * (Integer.SIZE / Byte.SIZE);
+
+ // finalization mix force all bits of a hash block to avalanche
+ h1 ^= h1 >>> 16;
+ h1 *= 0x85ebca6b;
+ h1 ^= h1 >>> 13;
+ h1 *= 0xc2b2ae35;
+ h1 ^= h1 >>> 16;
+
+ return h1;
+ }
+
+ /**
+ * Holds references to things that can't be initialized until after VM
+ * is fully booted.
+ */
+ private static class Holder {
+
+ /**
+ * Used for generating per-instance hash seeds.
+ *
+ * We try to improve upon the default seeding.
+ */
+ static final Random SEED_MAKER = new Random(
+ Double.doubleToRawLongBits(Math.random())
+ ^ System.identityHashCode(Hashing.class)
+ ^ System.currentTimeMillis()
+ ^ System.nanoTime()
+ ^ Runtime.getRuntime().freeMemory());
+ }
+
+ public static int randomHashSeed(Object instance) {
+ int seed;
+ if (sun.misc.VM.isBooted()) {
+ seed = Holder.SEED_MAKER.nextInt();
+ } else {
+ // lower quality "random" seed value--still better than zero and not
+ // not practically reversible.
+ int hashing_seed[] = {
+ System.identityHashCode(Hashing.class),
+ System.identityHashCode(instance),
+ System.identityHashCode(Thread.currentThread()),
+ (int) Thread.currentThread().getId(),
+ (int) (System.currentTimeMillis() >>> 2), // resolution is poor
+ (int) (System.nanoTime() >>> 5), // resolution is poor
+ (int) (Runtime.getRuntime().freeMemory() >>> 4) // alloc min
+ };
+
+ seed = murmur3_32(hashing_seed);
+ }
+
+ // force to non-zero.
+ return (0 != seed) ? seed : 1;
+ }
+}
--- a/jdk/test/java/util/Collection/BiggernYours.java Thu May 31 17:07:28 2012 -0400
+++ b/jdk/test/java/util/Collection/BiggernYours.java Thu May 31 17:10:57 2012 -0400
@@ -34,15 +34,25 @@
@SuppressWarnings("unchecked")
public class BiggernYours {
- static final Random rnd = new Random();
+ static final Random rnd = new Random(18675309);
static void compareCollections(Collection c1, Collection c2) {
- arrayEqual(c1.toArray(),
- c2.toArray());
- arrayEqual(c1.toArray(new Object[0]),
- c2.toArray(new Object[0]));
- arrayEqual(c1.toArray(new Object[5]),
- c2.toArray(new Object[5]));
+ Object[] c1Array = c1.toArray();
+ Object[] c2Array = c2.toArray();
+
+ check(c1Array.length == c2Array.length);
+ for(Object aC1 : c1Array) {
+ boolean found = false;
+ for(Object aC2 : c2Array) {
+ if(Objects.equals(aC1, aC2)) {
+ found = true;
+ break;
+ }
+ }
+
+ if(!found)
+ fail(aC1 + " not found in " + Arrays.toString(c2Array));
+ }
}
static void compareMaps(Map m1, Map m2) {
--- a/jdk/test/java/util/Hashtable/HashCode.java Thu May 31 17:07:28 2012 -0400
+++ b/jdk/test/java/util/Hashtable/HashCode.java Thu May 31 17:10:57 2012 -0400
@@ -36,8 +36,5 @@
if (m.hashCode() != 0)
throw new Exception("Empty Hashtable has nonzero hashCode.");
- m.put("Joe", "Blow");
- if (m.hashCode() != ("Joe".hashCode() ^ "Blow".hashCode()))
- throw new Exception("Non-empty Hashtable has wrong hashCode.");
}
}
--- a/jdk/test/java/util/Hashtable/SimpleSerialization.java Thu May 31 17:07:28 2012 -0400
+++ b/jdk/test/java/util/Hashtable/SimpleSerialization.java Thu May 31 17:10:57 2012 -0400
@@ -34,48 +34,58 @@
import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
-import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.PrintWriter;
import java.io.StringWriter;
import java.util.Hashtable;
+import java.util.Map;
public class SimpleSerialization {
public static void main(final String[] args) throws Exception {
Hashtable<String, String> h1 = new Hashtable<>();
+ System.err.println("*** BEGIN TEST ***");
+
h1.put("key", "value");
final ByteArrayOutputStream baos = new ByteArrayOutputStream();
- final ObjectOutputStream oos = new ObjectOutputStream(baos);
-
- oos.writeObject(h1);
- oos.close();
+ try (ObjectOutputStream oos = new ObjectOutputStream(baos)) {
+ oos.writeObject(h1);
+ }
final byte[] data = baos.toByteArray();
final ByteArrayInputStream bais = new ByteArrayInputStream(data);
- final ObjectInputStream ois = new ObjectInputStream(bais);
+ final Object deserializedObject;
+ try (ObjectInputStream ois = new ObjectInputStream(bais)) {
+ deserializedObject = ois.readObject();
+ }
- final Object deserializedObject = ois.readObject();
- ois.close();
+ if(!h1.getClass().isInstance(deserializedObject)) {
+ throw new RuntimeException("Result not assignable to type of h1");
+ }
if (false == h1.equals(deserializedObject)) {
+ Hashtable<String, String> d1 = (Hashtable<String, String>) h1;
+ for(Map.Entry entry: h1.entrySet()) {
+ System.err.println("h1.key::" + entry.getKey() + " d1.containsKey()::" + d1.containsKey((String) entry.getKey()));
+ System.err.println("h1.value::" + entry.getValue() + " d1.contains()::" + d1.contains(entry.getValue()));
+ System.err.println("h1.value == d1.value " + entry.getValue().equals(d1.get((String) entry.getKey())));
+ }
+
throw new RuntimeException(getFailureText(h1, deserializedObject));
}
}
private static String getFailureText(final Object orig, final Object copy) {
final StringWriter sw = new StringWriter();
- final PrintWriter pw = new PrintWriter(sw);
-
- pw.println("Test FAILED: Deserialized object is not equal to the original object");
- pw.print("\tOriginal: ");
- printObject(pw, orig).println();
- pw.print("\tCopy: ");
- printObject(pw, copy).println();
-
- pw.close();
+ try (PrintWriter pw = new PrintWriter(sw)) {
+ pw.println("Test FAILED: Deserialized object is not equal to the original object");
+ pw.print("\tOriginal: ");
+ printObject(pw, orig).println();
+ pw.print("\tCopy: ");
+ printObject(pw, copy).println();
+ }
return sw.toString();
}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/test/java/util/Map/Collisions.java Thu May 31 17:10:57 2012 -0400
@@ -0,0 +1,345 @@
+/*
+ * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+/*
+ * @test
+ * @bug 7126277
+ * @summary Ensure Maps behave well with lots of hashCode() collisions.
+ * @author Mike Duigou
+ */
+import java.util.*;
+import java.util.concurrent.ConcurrentHashMap;
+import java.util.concurrent.ConcurrentSkipListMap;
+
+public class Collisions {
+
+ final static class HashableInteger implements Comparable<HashableInteger> {
+
+ final int value;
+ final int hashmask; //yes duplication
+
+ HashableInteger(int value, int hashmask) {
+ this.value = value;
+ this.hashmask = hashmask;
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (obj instanceof HashableInteger) {
+ HashableInteger other = (HashableInteger) obj;
+
+ return other.value == value;
+ }
+
+ return false;
+ }
+
+ @Override
+ public int hashCode() {
+ return value % hashmask;
+ }
+
+ @Override
+ public int compareTo(HashableInteger o) {
+ return value - o.value;
+ }
+
+ public String toString() {
+ return Integer.toString(value);
+ }
+ }
+ private static final int ITEMS = 10000;
+ private static final Object KEYS[][];
+
+ static {
+ HashableInteger UNIQUE_OBJECTS[] = new HashableInteger[ITEMS];
+ HashableInteger COLLIDING_OBJECTS[] = new HashableInteger[ITEMS];
+ String UNIQUE_STRINGS[] = new String[ITEMS];
+ String COLLIDING_STRINGS[] = new String[ITEMS];
+
+ for (int i = 0; i < ITEMS; i++) {
+ UNIQUE_OBJECTS[i] = new HashableInteger(i, Integer.MAX_VALUE);
+ COLLIDING_OBJECTS[i] = new HashableInteger(i, 10);
+ UNIQUE_STRINGS[i] = unhash(i);
+ COLLIDING_STRINGS[i] = (0 == i % 2)
+ ? UNIQUE_STRINGS[i / 2]
+ : "\u0000\u0000\u0000\u0000\u0000" + COLLIDING_STRINGS[i - 1];
+ }
+
+ KEYS = new Object[][] {
+ new Object[]{"Unique Objects", UNIQUE_OBJECTS},
+ new Object[]{"Colliding Objects", COLLIDING_OBJECTS},
+ new Object[]{"Unique Strings", UNIQUE_STRINGS},
+ new Object[]{"Colliding Strings", COLLIDING_STRINGS}
+ };
+ }
+
+ /**
+ * Returns a string with a hash equal to the argument.
+ *
+ * @return string with a hash equal to the argument.
+ */
+ public static String unhash(int target) {
+ StringBuilder answer = new StringBuilder();
+ if (target < 0) {
+ // String with hash of Integer.MIN_VALUE, 0x80000000
+ answer.append("\\u0915\\u0009\\u001e\\u000c\\u0002");
+
+ if (target == Integer.MIN_VALUE) {
+ return answer.toString();
+ }
+ // Find target without sign bit set
+ target = target & Integer.MAX_VALUE;
+ }
+
+ unhash0(answer, target);
+ return answer.toString();
+ }
+
+ private static void unhash0(StringBuilder partial, int target) {
+ int div = target / 31;
+ int rem = target % 31;
+
+ if (div <= Character.MAX_VALUE) {
+ if (div != 0) {
+ partial.append((char) div);
+ }
+ partial.append((char) rem);
+ } else {
+ unhash0(partial, div);
+ partial.append((char) rem);
+ }
+ }
+
+ private static void realMain(String[] args) throws Throwable {
+ for (Object[] keys_desc : KEYS) {
+ Map<Object, Boolean>[] MAPS = (Map<Object, Boolean>[]) new Map[]{
+// new Hashtable<>(),
+ new HashMap<>(),
+ new IdentityHashMap<>(),
+ new LinkedHashMap<>(),
+ new ConcurrentHashMap<>(),
+ new WeakHashMap<>(),
+ new TreeMap<>(),
+ new ConcurrentSkipListMap<>()
+ };
+
+ for (Map<Object, Boolean> map : MAPS) {
+ String desc = (String) keys_desc[0];
+ Object[] keys = (Object[]) keys_desc[1];
+ testMap(map, desc, keys);
+ }
+ }
+ }
+
+ private static <T> void testMap(Map<T, Boolean> map, String keys_desc, T[] keys) {
+ System.err.println(map.getClass() + " : " + keys_desc);
+ testInsertion(map, keys_desc, keys);
+
+ if (keys[0] instanceof HashableInteger) {
+ testIntegerIteration((Map<HashableInteger, Boolean>) map, (HashableInteger[]) keys);
+ } else {
+ testStringIteration((Map<String, Boolean>) map, (String[]) keys);
+ }
+
+ testContainsKey(map, keys_desc, keys);
+
+ testRemove(map, keys_desc, keys);
+
+ check(map.isEmpty());
+ }
+
+ private static <T> void testInsertion(Map<T, Boolean> map, String keys_desc, T[] keys) {
+ check("map empty", (map.size() == 0) && map.isEmpty());
+
+ for (int i = 0; i < keys.length; i++) {
+ check(String.format("insertion: map expected size m%d != i%d", map.size(), i),
+ map.size() == i);
+ check(String.format("insertion: put(%s[%d])", keys_desc, i), null == map.put(keys[i], true));
+ check(String.format("insertion: containsKey(%s[%d])", keys_desc, i), map.containsKey(keys[i]));
+ }
+
+ check(String.format("map expected size m%d != k%d", map.size(), keys.length),
+ map.size() == keys.length);
+ }
+
+ private static void testIntegerIteration(Map<HashableInteger, Boolean> map, HashableInteger[] keys) {
+ check(String.format("map expected size m%d != k%d", map.size(), keys.length),
+ map.size() == keys.length);
+
+ BitSet all = new BitSet(keys.length);
+ for (Map.Entry<HashableInteger, Boolean> each : map.entrySet()) {
+ check("Iteration: key already seen", !all.get(each.getKey().value));
+ all.set(each.getKey().value);
+ }
+
+ all.flip(0, keys.length);
+ check("Iteration: some keys not visited", all.isEmpty());
+
+ for (HashableInteger each : map.keySet()) {
+ check("Iteration: key already seen", !all.get(each.value));
+ all.set(each.value);
+ }
+
+ all.flip(0, keys.length);
+ check("Iteration: some keys not visited", all.isEmpty());
+
+ int count = 0;
+ for (Boolean each : map.values()) {
+ count++;
+ }
+
+ check(String.format("Iteration: value count matches size m%d != c%d", map.size(), count),
+ map.size() == count);
+ }
+
+ private static void testStringIteration(Map<String, Boolean> map, String[] keys) {
+ check(String.format("map expected size m%d != k%d", map.size(), keys.length),
+ map.size() == keys.length);
+
+ BitSet all = new BitSet(keys.length);
+ for (Map.Entry<String, Boolean> each : map.entrySet()) {
+ String key = each.getKey();
+ boolean longKey = key.length() > 5;
+ int index = key.hashCode() + (longKey ? keys.length / 2 : 0);
+ check("key already seen", !all.get(index));
+ all.set(index);
+ }
+
+ all.flip(0, keys.length);
+ check("some keys not visited", all.isEmpty());
+
+ for (String each : map.keySet()) {
+ boolean longKey = each.length() > 5;
+ int index = each.hashCode() + (longKey ? keys.length / 2 : 0);
+ check("key already seen", !all.get(index));
+ all.set(index);
+ }
+
+ all.flip(0, keys.length);
+ check("some keys not visited", all.isEmpty());
+
+ int count = 0;
+ for (Boolean each : map.values()) {
+ count++;
+ }
+
+ check(String.format("value count matches size m%d != k%d", map.size(), keys.length),
+ map.size() == keys.length);
+ }
+
+ private static <T> void testContainsKey(Map<T, Boolean> map, String keys_desc, T[] keys) {
+ for (int i = 0; i < keys.length; i++) {
+ T each = keys[i];
+ check("containsKey: " + keys_desc + "[" + i + "]" + each, map.containsKey(each));
+ }
+ }
+
+ private static <T> void testRemove(Map<T, Boolean> map, String keys_desc, T[] keys) {
+ check(String.format("remove: map expected size m%d != k%d", map.size(), keys.length),
+ map.size() == keys.length);
+
+ for (int i = 0; i < keys.length; i++) {
+ T each = keys[i];
+ check("remove: " + keys_desc + "[" + i + "]" + each, null != map.remove(each));
+ }
+
+ check(String.format("remove: map empty. size=%d", map.size()),
+ (map.size() == 0) && map.isEmpty());
+ }
+ //--------------------- Infrastructure ---------------------------
+ static volatile int passed = 0, failed = 0;
+
+ static void pass() {
+ passed++;
+ }
+
+ static void fail() {
+ failed++;
+ (new Error("Failure")).printStackTrace(System.err);
+ }
+
+ static void fail(String msg) {
+ failed++;
+ (new Error("Failure: " + msg)).printStackTrace(System.err);
+ }
+
+ static void abort() {
+ fail();
+ System.exit(1);
+ }
+
+ static void abort(String msg) {
+ fail(msg);
+ System.exit(1);
+ }
+
+ static void unexpected(String msg, Throwable t) {
+ System.err.println("Unexpected: " + msg);
+ unexpected(t);
+ }
+
+ static void unexpected(Throwable t) {
+ failed++;
+ t.printStackTrace(System.err);
+ }
+
+ static void check(boolean cond) {
+ if (cond) {
+ pass();
+ } else {
+ fail();
+ }
+ }
+
+ static void check(String desc, boolean cond) {
+ if (cond) {
+ pass();
+ } else {
+ fail(desc);
+ }
+ }
+
+ static void equal(Object x, Object y) {
+ if (Objects.equals(x, y)) {
+ pass();
+ } else {
+ fail(x + " not equal to " + y);
+ }
+ }
+
+ public static void main(String[] args) throws Throwable {
+ Thread.currentThread().setName("Collisions");
+// Thread.currentThread().setPriority(Thread.MAX_PRIORITY);
+ try {
+ realMain(args);
+ } catch (Throwable t) {
+ unexpected(t);
+ }
+
+ System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed);
+ if (failed > 0) {
+ throw new Error("Some tests failed");
+ }
+ }
+}
--- a/jdk/test/java/util/Map/Get.java Thu May 31 17:07:28 2012 -0400
+++ b/jdk/test/java/util/Map/Get.java Thu May 31 17:10:57 2012 -0400
@@ -50,16 +50,16 @@
Character key, Boolean value,
Boolean oldValue) {
if (oldValue != null) {
- check(m.containsValue(oldValue));
- check(m.values().contains(oldValue));
+ check("containsValue(oldValue)", m.containsValue(oldValue));
+ check("values.contains(oldValue)", m.values().contains(oldValue));
}
equal(m.put(key, value), oldValue);
equal(m.get(key), value);
- check(m.containsKey(key));
- check(m.keySet().contains(key));
- check(m.containsValue(value));
- check(m.values().contains(value));
- check(! m.isEmpty());
+ check("containsKey", m.containsKey(key));
+ check("keySet.contains", m.keySet().contains(key));
+ check("containsValue", m.containsValue(value));
+ check("values.contains", m.values().contains(value));
+ check("!isEmpty", ! m.isEmpty());
}
private static void testMap(Map<Character,Boolean> m) {
@@ -71,7 +71,7 @@
m instanceof Hashtable));
boolean usesIdentity = m instanceof IdentityHashMap;
- System.out.println(m.getClass());
+ System.err.println(m.getClass());
put(m, 'A', true, null);
put(m, 'A', false, true); // Guaranteed identical by JLS
put(m, 'B', true, null);
@@ -81,15 +81,15 @@
put(m, null, true, null);
put(m, null, false, true);
}
- catch (Throwable t) { unexpected(t); }
+ catch (Throwable t) { unexpected(m.getClass().getName(), t); }
} else {
- try { m.get(null); fail(); }
+ try { m.get(null); fail(m.getClass().getName() + " did not reject null key"); }
catch (NullPointerException e) {}
- catch (Throwable t) { unexpected(t); }
+ catch (Throwable t) { unexpected(m.getClass().getName(), t); }
- try { m.put(null, true); fail(); }
+ try { m.put(null, true); fail(m.getClass().getName() + " did not reject null key"); }
catch (NullPointerException e) {}
- catch (Throwable t) { unexpected(t); }
+ catch (Throwable t) { unexpected(m.getClass().getName(), t); }
}
if (permitsNullValues) {
try {
@@ -97,33 +97,35 @@
put(m, 'C', true, null);
put(m, 'C', null, true);
}
- catch (Throwable t) { unexpected(t); }
+ catch (Throwable t) { unexpected(m.getClass().getName(), t); }
} else {
- try { m.put('A', null); fail(); }
+ try { m.put('A', null); fail(m.getClass().getName() + " did not reject null key"); }
catch (NullPointerException e) {}
- catch (Throwable t) { unexpected(t); }
+ catch (Throwable t) { unexpected(m.getClass().getName(), t); }
- try { m.put('C', null); fail(); }
+ try { m.put('C', null); fail(m.getClass().getName() + " did not reject null key"); }
catch (NullPointerException e) {}
- catch (Throwable t) { unexpected(t); }
+ catch (Throwable t) { unexpected(m.getClass().getName(), t); }
}
}
//--------------------- Infrastructure ---------------------------
static volatile int passed = 0, failed = 0;
static void pass() { passed++; }
- static void fail() { failed++; Thread.dumpStack(); }
- static void fail(String msg) { System.out.println(msg); fail(); }
- static void unexpected(Throwable t) { failed++; t.printStackTrace(); }
+ static void fail() { failed++; (new Error("Failure")).printStackTrace(System.err); }
+ static void fail(String msg) { failed++; (new Error("Failure: " + msg)).printStackTrace(System.err); }
+ static void unexpected(String msg, Throwable t) { System.err.println("Unexpected: " + msg); unexpected(t); }
+ static void unexpected(Throwable t) { failed++; t.printStackTrace(System.err); }
static void check(boolean cond) { if (cond) pass(); else fail(); }
+ static void check(String desc, boolean cond) { if (cond) pass(); else fail(desc); }
static 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(); }}
+ if(Objects.equals(x,y)) pass(); else fail(x + " not equal to " + y);
+ }
public static void main(String[] args) throws Throwable {
try { realMain(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 Error("Some tests failed");
}
}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/test/sun/misc/Hashing.java Thu May 31 17:10:57 2012 -0400
@@ -0,0 +1,127 @@
+/*
+ * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+/*
+ * @test @summary Ensure that Murmur3 hash performs according to specification.
+ * @compile -XDignore.symbol.file Hashing.java
+ */
+public class Hashing {
+
+ static final byte ONE_BYTE[] = {
+ (byte) 0x80};
+ static final byte TWO_BYTE[] = {
+ (byte) 0x80, (byte) 0x81};
+ static final char ONE_CHAR[] = {
+ (char) 0x8180};
+ static final byte THREE_BYTE[] = {
+ (byte) 0x80, (byte) 0x81, (byte) 0x82};
+ static final byte FOUR_BYTE[] = {
+ (byte) 0x80, (byte) 0x81, (byte) 0x82, (byte) 0x83};
+ static final char TWO_CHAR[] = {
+ (char) 0x8180, (char) 0x8382};
+ static final int ONE_INT[] = {
+ 0x83828180};
+ static final byte SIX_BYTE[] = {
+ (byte) 0x80, (byte) 0x81, (byte) 0x82,
+ (byte) 0x83, (byte) 0x84, (byte) 0x85};
+ static final char THREE_CHAR[] = {
+ (char) 0x8180, (char) 0x8382, (char) 0x8584};
+ static final byte EIGHT_BYTE[] = {
+ (byte) 0x80, (byte) 0x81, (byte) 0x82,
+ (byte) 0x83, (byte) 0x84, (byte) 0x85,
+ (byte) 0x86, (byte) 0x87};
+ static final char FOUR_CHAR[] = {
+ (char) 0x8180, (char) 0x8382,
+ (char) 0x8584, (char) 0x8786};
+ static final int TWO_INT[] = {
+ 0x83828180, 0x87868584};
+ // per http://code.google.com/p/smhasher/source/browse/trunk/main.cpp, line:72
+ static final int MURMUR3_32_X86_CHECK_VALUE = 0xB0F57EE3;
+
+ public static void testMurmur3_32_ByteArray() {
+ System.out.println("testMurmur3_32_ByteArray");
+
+ byte[] vector = new byte[256];
+ byte[] hashes = new byte[4 * 256];
+
+ for (int i = 0; i < 256; i++) {
+ vector[i] = (byte) i;
+ }
+
+ // Hash subranges {}, {0}, {0,1}, {0,1,2}, ..., {0,...,255}
+ for (int i = 0; i < 256; i++) {
+ int hash = sun.misc.Hashing.murmur3_32(256 - i, vector, 0, i);
+
+ hashes[i * 4] = (byte) hash;
+ hashes[i * 4 + 1] = (byte) (hash >>> 8);
+ hashes[i * 4 + 2] = (byte) (hash >>> 16);
+ hashes[i * 4 + 3] = (byte) (hash >>> 24);
+ }
+
+ // hash to get final result.
+ int final_hash = sun.misc.Hashing.murmur3_32(0, hashes);
+
+ if (MURMUR3_32_X86_CHECK_VALUE != final_hash) {
+ throw new RuntimeException(
+ String.format("Calculated hash result not as expected. Expected %08X got %08X",
+ MURMUR3_32_X86_CHECK_VALUE,
+ final_hash));
+ }
+ }
+
+ public static void testEquivalentHashes() {
+ int bytes, chars, ints;
+
+ System.out.println("testEquivalentHashes");
+
+ bytes = sun.misc.Hashing.murmur3_32(TWO_BYTE);
+ chars = sun.misc.Hashing.murmur3_32(ONE_CHAR);
+ if (bytes != chars) {
+ throw new RuntimeException(String.format("Hashes did not match. b:%08x != c:%08x", bytes, chars));
+ }
+
+ bytes = sun.misc.Hashing.murmur3_32(FOUR_BYTE);
+ chars = sun.misc.Hashing.murmur3_32(TWO_CHAR);
+ ints = sun.misc.Hashing.murmur3_32(ONE_INT);
+ if ((bytes != chars) || (bytes != ints)) {
+ throw new RuntimeException(String.format("Hashes did not match. b:%08x != c:%08x != i:%08x", bytes, chars, ints));
+ }
+ bytes = sun.misc.Hashing.murmur3_32(SIX_BYTE);
+ chars = sun.misc.Hashing.murmur3_32(THREE_CHAR);
+ if (bytes != chars) {
+ throw new RuntimeException(String.format("Hashes did not match. b:%08x != c:%08x", bytes, chars));
+ }
+
+ bytes = sun.misc.Hashing.murmur3_32(EIGHT_BYTE);
+ chars = sun.misc.Hashing.murmur3_32(FOUR_CHAR);
+ ints = sun.misc.Hashing.murmur3_32(TWO_INT);
+ if ((bytes != chars) || (bytes != ints)) {
+ throw new RuntimeException(String.format("Hashes did not match. b:%08x != c:%08x != i:%08x", bytes, chars, ints));
+ }
+ }
+
+ public static void main(String[] args) {
+ testMurmur3_32_ByteArray();
+ testEquivalentHashes();
+ }
+}