Merge "FileInputStreamTest : Add test for skips of files larger than 2G."
diff --git a/luni/src/test/java/libcore/java/util/jar/OldManifestTest.java b/luni/src/test/java/libcore/java/util/jar/OldManifestTest.java
index e5c3bdb..29cdffa 100644
--- a/luni/src/test/java/libcore/java/util/jar/OldManifestTest.java
+++ b/luni/src/test/java/libcore/java/util/jar/OldManifestTest.java
@@ -23,6 +23,8 @@
import java.io.IOException;
import java.net.MalformedURLException;
import java.net.URL;
+import java.util.Arrays;
+import java.util.List;
import java.util.jar.Attributes;
import java.util.jar.Manifest;
import junit.framework.TestCase;
@@ -176,9 +178,12 @@
// The Manifest-Version takes precedence,
// and the Signature-Version gets no special treatment.
- String[] lines = new String(os.toByteArray(), "UTF-8").split("\r\n");
- assertEquals("Manifest-Version: 1.0", lines[0]);
- assertEquals("Aardvark-Version: 3.0", lines[1]);
- assertEquals("Signature-Version: 2.0", lines[2]);
+ List<String> lines = Arrays.asList(new String(os.toByteArray(), "UTF-8").split("\r\n"));
+ // The first line must always contain the Manifest-Version (or the Signature-Version if
+ // the ManifestVersion is missing.
+ assertEquals("Manifest-Version: 1.0", lines.get(0));
+
+ assertTrue(lines.contains("Aardvark-Version: 3.0"));
+ assertTrue(lines.contains("Signature-Version: 2.0"));
}
}
diff --git a/luni/src/test/java/libcore/javax/net/ssl/KeyManagerFactoryTest.java b/luni/src/test/java/libcore/javax/net/ssl/KeyManagerFactoryTest.java
index 0657f18..b99a3f1 100644
--- a/luni/src/test/java/libcore/javax/net/ssl/KeyManagerFactoryTest.java
+++ b/luni/src/test/java/libcore/javax/net/ssl/KeyManagerFactoryTest.java
@@ -26,6 +26,7 @@
import java.security.cert.Certificate;
import java.security.cert.X509Certificate;
import java.util.Arrays;
+import java.util.Locale;
import java.util.Set;
import javax.net.ssl.KeyManager;
import javax.net.ssl.KeyManagerFactory;
@@ -39,17 +40,18 @@
public class KeyManagerFactoryTest extends TestCase {
- private static TestKeyStore TEST_KEY_STORE;
+ private TestKeyStore testKeyStore;
- // note the rare usage of DSA keys here in addition to RSA
- private static TestKeyStore getTestKeyStore() throws Exception {
- if (TEST_KEY_STORE == null) {
- TEST_KEY_STORE = new TestKeyStore.Builder()
- .keyAlgorithms("RSA", "DH_RSA", "DSA", "DH_DSA", "EC", "EC_RSA")
- .aliasPrefix("rsa-dsa-ec-dh")
- .build();
- }
- return TEST_KEY_STORE;
+ protected void setUp() throws Exception {
+ // note the rare usage of DSA keys here in addition to RSA
+ testKeyStore = new TestKeyStore.Builder()
+ .keyAlgorithms("RSA", "DH_RSA", "DSA", "DH_DSA", "EC", "EC_RSA")
+ .aliasPrefix("rsa-dsa-ec-dh")
+ .build();
+ }
+
+ private TestKeyStore getTestKeyStore() throws Exception {
+ return testKeyStore;
}
public void test_KeyManagerFactory_getDefaultAlgorithm() throws Exception {
@@ -230,34 +232,30 @@
X509Certificate[] certificateChain = km.getCertificateChain(alias);
PrivateKey privateKey = km.getPrivateKey(alias);
- String keyAlgName;
- String sigAlgName;
- if (keyType == null) {
- keyAlgName = privateKey.getAlgorithm();
- sigAlgName = keyAlgName;
- } else {
- // potentially handle EC_EC or EC_RSA
- keyAlgName = TestKeyStore.keyAlgorithm(keyType);
- sigAlgName = TestKeyStore.signatureAlgorithm(keyType);
- X509Certificate certificate = certificateChain[0];
- assertEquals(keyType, keyAlgName, certificate.getPublicKey().getAlgorithm());
- assertEquals(keyType, keyAlgName, privateKey.getAlgorithm());
- // skip this for EC which could return EC_RSA case instead of EC_EC
- if (!keyType.equals("EC")) {
- String expectedSigAlgName = sigAlgName.toUpperCase();
- String actualSigAlgName = certificate.getSigAlgName().toUpperCase();
- String expected = actualSigAlgName + " contains " + expectedSigAlgName;
- assertTrue(expected, actualSigAlgName.contains(expectedSigAlgName));
- }
- }
+ String keyAlgName = privateKey.getAlgorithm();
+
+ X509Certificate certificate = certificateChain[0];
+ assertEquals(keyType, keyAlgName, certificate.getPublicKey().getAlgorithm());
+
+ String sigAlgName = certificate.getSigAlgName();
PrivateKeyEntry privateKeyEntry = getTestKeyStore().getPrivateKey(keyAlgName, sigAlgName);
- if (!"EC".equals(keyAlgName)) {
- assertEquals(keyType,
- Arrays.<Certificate>asList(privateKeyEntry.getCertificateChain()),
- Arrays.<Certificate>asList(certificateChain));
- assertEquals(keyType,
- privateKeyEntry.getPrivateKey(), privateKey);
+
+ assertEquals(keyType,
+ Arrays.<Certificate>asList(privateKeyEntry.getCertificateChain()),
+ Arrays.<Certificate>asList(certificateChain));
+ assertEquals(keyType,
+ privateKeyEntry.getPrivateKey(), privateKey);
+
+ if (keyType != null) {
+ assertEquals(TestKeyStore.keyAlgorithm(keyType), keyAlgName);
+
+ // Skip this when we're given only "DH" or "EC" instead of "DH_DSA",
+ // "EC_RSA", etc. since we don't know what the expected
+ // algorithm was.
+ if (!keyType.equals("DH") && !keyType.equals("EC")) {
+ assertTrue(sigAlgName.contains(TestKeyStore.signatureAlgorithm(keyType)));
+ }
}
}
diff --git a/ojluni/src/main/java/java/lang/JavaLangAccess.java b/ojluni/src/main/java/java/lang/JavaLangAccess.java
index 20d673e..2779c60 100644
--- a/ojluni/src/main/java/java/lang/JavaLangAccess.java
+++ b/ojluni/src/main/java/java/lang/JavaLangAccess.java
@@ -35,13 +35,6 @@
/**
* @hide
*/
- public static int getStringHash32(String string) {
- return string.hash32();
- }
-
- /**
- * @hide
- */
public static <E extends Enum<E>>
E[] getEnumConstantsShared(Class<E> klass) {
return klass.getEnumConstantsShared();
diff --git a/ojluni/src/main/java/java/lang/String.java b/ojluni/src/main/java/java/lang/String.java
index 7213e2d..0e66ad7 100755
--- a/ojluni/src/main/java/java/lang/String.java
+++ b/ojluni/src/main/java/java/lang/String.java
@@ -2879,74 +2879,4 @@
* guaranteed to be from a pool of unique strings.
*/
public native String intern();
-
- /**
- * Seed value used for each alternative hash calculated.
- */
- private static int HASHING_SEED;
-
- private static int getHashingSeed() {
- 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;
- return HASHING_SEED;
- }
-
- /**
- * Cached value of the alternative hashing algorithm result
- */
- // TODO(narayan): This adds a 4 byte overhead to all string objects. Is it
- // worth the trouble ? hash32() below has been changed not to cache the calculated
- // hash. This is likely to be expensive and needs further analysis.
- //
- // private transient int hash32 = 0;
-
- /**
- * Calculates a 32-bit hash value for this string.
- *
- * @return a 32-bit hash value for this string.
- */
- int hash32() {
- char[] value = new char[count];
- getChars(0, count, value, 0);
- return sun.misc.Hashing.murmur3_32(getHashingSeed(), value, 0, count);
- }
}
diff --git a/ojluni/src/main/java/java/util/HashMap.java b/ojluni/src/main/java/java/util/HashMap.java
index 6d76a33..9403225 100755
--- a/ojluni/src/main/java/java/util/HashMap.java
+++ b/ojluni/src/main/java/java/util/HashMap.java
@@ -134,7 +134,7 @@
/**
* The default initial capacity - MUST be a power of two.
*/
- static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
+ static final int DEFAULT_INITIAL_CAPACITY = 4;
/**
* The maximum capacity, used if a higher value is implicitly specified
@@ -176,7 +176,9 @@
*
* @serial
*/
- final float loadFactor;
+ // Android-Note: We always use a load factor of 0.75 and ignore any explicitly
+ // selected values.
+ final float loadFactor = DEFAULT_LOAD_FACTOR;
/**
* The number of times this HashMap has been structurally modified
@@ -188,62 +190,6 @@
transient int modCount;
/**
- * The default threshold of map capacity above which alternative hashing is
- * used for String keys. Alternative hashing reduces the incidence of
- * collisions due to weak hash code calculation for String keys.
- * <p/>
- * This value may be overridden by defining the system property
- * {@code jdk.map.althashing.threshold}. A property value of {@code 1}
- * forces alternative hashing to be used at all times whereas
- * {@code -1} value ensures that alternative hashing is never used.
- */
- static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
-
- /**
- * holds values which can't be initialized until after VM is booted.
- */
- private static class Holder {
-
- /**
- * Table capacity above which to switch to use alternative hashing.
- */
- static final int ALTERNATIVE_HASHING_THRESHOLD;
-
- static {
- String altThreshold = java.security.AccessController.doPrivileged(
- new sun.security.action.GetPropertyAction(
- "jdk.map.althashing.threshold"));
-
- int threshold;
- try {
- threshold = (null != altThreshold)
- ? Integer.parseInt(altThreshold)
- : ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;
-
- // disable alternative hashing if -1
- if (threshold == -1) {
- threshold = Integer.MAX_VALUE;
- }
-
- if (threshold < 0) {
- throw new IllegalArgumentException("value must be positive integer.");
- }
- } catch(IllegalArgumentException failed) {
- throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
- }
-
- ALTERNATIVE_HASHING_THRESHOLD = threshold;
- }
- }
-
- /**
- * A randomizing value associated with this instance that is applied to
- * hash code of keys to make hash collisions harder to find. If 0 then
- * alternative hashing is disabled.
- */
- transient int hashSeed = 0;
-
- /**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and load factor.
*
@@ -256,13 +202,21 @@
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
- if (initialCapacity > MAXIMUM_CAPACITY)
+ if (initialCapacity > MAXIMUM_CAPACITY) {
initialCapacity = MAXIMUM_CAPACITY;
+ } else if (initialCapacity < DEFAULT_INITIAL_CAPACITY) {
+ initialCapacity = DEFAULT_INITIAL_CAPACITY;
+ }
+
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
+ // Android-Note: We always use the default load factor of 0.75f.
- this.loadFactor = loadFactor;
+ // This might appear wrong but it's just awkward design. We always call
+ // inflateTable() when table == EMPTY_TABLE. That method will take "threshold"
+ // to mean "capacity" and then replace it with the real threshold (i.e, multiplied with
+ // the load factor).
threshold = initialCapacity;
init();
}
@@ -331,7 +285,6 @@
threshold = (int) thresholdFloat;
table = new HashMapEntry[capacity];
- initHashSeedAsNeeded(capacity);
}
// internal utilities
@@ -347,45 +300,6 @@
}
/**
- * Initialize the hashing mask value. We defer initialization until we
- * really need it.
- */
- final boolean initHashSeedAsNeeded(int capacity) {
- boolean currentAltHashing = hashSeed != 0;
- boolean useAltHashing = sun.misc.VM.isBooted() &&
- (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
- boolean switching = currentAltHashing ^ useAltHashing;
- if (switching) {
- hashSeed = useAltHashing
- ? sun.misc.Hashing.randomHashSeed(this)
- : 0;
- }
- return switching;
- }
-
- /**
- * 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.
- */
- final int hash(Object k) {
- int h = hashSeed;
- if (0 != h && k instanceof String) {
- return sun.misc.Hashing.stringHash32((String) k);
- }
-
- 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.
*/
static int indexFor(int h, int length) {
@@ -476,7 +390,7 @@
return null;
}
- int hash = (key == null) ? 0 : hash(key);
+ int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
for (HashMapEntry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
@@ -506,7 +420,7 @@
}
if (key == null)
return putForNullKey(value);
- int hash = hash(key);
+ int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
int i = indexFor(hash, table.length);
for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
@@ -547,7 +461,7 @@
* addEntry.
*/
private void putForCreate(K key, V value) {
- int hash = null == key ? 0 : hash(key);
+ int hash = null == key ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
int i = indexFor(hash, table.length);
/**
@@ -595,7 +509,7 @@
}
HashMapEntry[] newTable = new HashMapEntry[newCapacity];
- transfer(newTable, initHashSeedAsNeeded(newCapacity));
+ transfer(newTable);
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
@@ -603,14 +517,11 @@
/**
* Transfers all entries from current table to newTable.
*/
- void transfer(HashMapEntry[] newTable, boolean rehash) {
+ void transfer(HashMapEntry[] newTable) {
int newCapacity = newTable.length;
for (HashMapEntry<K,V> e : table) {
while(null != e) {
HashMapEntry<K,V> next = e.next;
- if (rehash) {
- e.hash = null == e.key ? 0 : hash(e.key);
- }
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
@@ -683,7 +594,7 @@
if (size == 0) {
return null;
}
- int hash = (key == null) ? 0 : hash(key);
+ int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
int i = indexFor(hash, table.length);
HashMapEntry<K,V> prev = table[i];
HashMapEntry<K,V> e = prev;
@@ -719,7 +630,7 @@
Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
Object key = entry.getKey();
- int hash = (key == null) ? 0 : hash(key);
+ int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
int i = indexFor(hash, table.length);
HashMapEntry<K,V> prev = table[i];
HashMapEntry<K,V> e = prev;
@@ -895,7 +806,7 @@
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
- hash = (null != key) ? hash(key) : 0;
+ hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
diff --git a/ojluni/src/main/java/java/util/Hashtable.java b/ojluni/src/main/java/java/util/Hashtable.java
index 791d2b4..783d17b 100755
--- a/ojluni/src/main/java/java/util/Hashtable.java
+++ b/ojluni/src/main/java/java/util/Hashtable.java
@@ -168,80 +168,8 @@
/** use serialVersionUID from JDK 1.0.2 for interoperability */
private static final long serialVersionUID = 1421746759512286392L;
- /**
- * The default threshold of map capacity above which alternative hashing is
- * used for String keys. Alternative hashing reduces the incidence of
- * collisions due to weak hash code calculation for String keys.
- * <p>
- * This value may be overridden by defining the system property
- * {@code jdk.map.althashing.threshold}. A property value of {@code 1}
- * forces alternative hashing to be used at all times whereas
- * {@code -1} value ensures that alternative hashing is never used.
- */
- static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
-
- /**
- * holds values which can't be initialized until after VM is booted.
- */
- private static class Holder {
-
- /**
- * Table capacity above which to switch to use alternative hashing.
- */
- static final int ALTERNATIVE_HASHING_THRESHOLD;
-
- static {
- String altThreshold = java.security.AccessController.doPrivileged(
- new sun.security.action.GetPropertyAction(
- "jdk.map.althashing.threshold"));
-
- int threshold;
- try {
- threshold = (null != altThreshold)
- ? Integer.parseInt(altThreshold)
- : ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;
-
- // disable alternative hashing if -1
- if (threshold == -1) {
- threshold = Integer.MAX_VALUE;
- }
-
- if (threshold < 0) {
- throw new IllegalArgumentException("value must be positive integer.");
- }
- } catch(IllegalArgumentException failed) {
- throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
- }
-
- ALTERNATIVE_HASHING_THRESHOLD = threshold;
- }
- }
-
- /**
- * A randomizing value associated with this instance that is applied to
- * hash code of keys to make hash collisions harder to find.
- */
- transient int hashSeed;
-
- /**
- * Initialize the hashing mask value.
- */
- final boolean initHashSeedAsNeeded(int capacity) {
- boolean currentAltHashing = hashSeed != 0;
- boolean useAltHashing = sun.misc.VM.isBooted() &&
- (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
- boolean switching = currentAltHashing ^ useAltHashing;
- if (switching) {
- hashSeed = useAltHashing
- ? sun.misc.Hashing.randomHashSeed(this)
- : 0;
- }
- return switching;
- }
-
- private int hash(Object k) {
- // hashSeed will be zero if alternative hashing is disabled.
- return hashSeed ^ k.hashCode();
+ private static int hash(Object k) {
+ return k.hashCode();
}
/**
@@ -265,7 +193,6 @@
this.loadFactor = loadFactor;
table = new HashtableEntry[initialCapacity];
threshold = (initialCapacity <= MAX_ARRAY_SIZE + 1) ? initialCapacity : MAX_ARRAY_SIZE + 1;
- initHashSeedAsNeeded(initialCapacity);
}
/**
@@ -477,7 +404,6 @@
modCount++;
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
- boolean rehash = initHashSeedAsNeeded(newCapacity);
table = newMap;
@@ -486,9 +412,6 @@
HashtableEntry<K,V> e = old;
old = old.next;
- if (rehash) {
- e.hash = hash(e.key);
- }
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
e.next = newMap[index];
newMap[index] = e;
@@ -1086,7 +1009,6 @@
HashtableEntry<K,V>[] newTable = new HashtableEntry[length];
threshold = (int) Math.min(length * loadFactor, MAX_ARRAY_SIZE + 1);
count = 0;
- initHashSeedAsNeeded(length);
// Read the number of elements and then all the key/value objects
for (; elements > 0; elements--) {
diff --git a/ojluni/src/main/java/java/util/LinkedHashMap.java b/ojluni/src/main/java/java/util/LinkedHashMap.java
index 037c133..5a35728 100755
--- a/ojluni/src/main/java/java/util/LinkedHashMap.java
+++ b/ojluni/src/main/java/java/util/LinkedHashMap.java
@@ -26,6 +26,8 @@
package java.util;
+import sun.misc.Hashing;
+
import java.io.*;
import java.util.function.BiFunction;
import java.util.function.Consumer;
@@ -265,11 +267,9 @@
* faster to iterate using our linked list.
*/
@Override
- void transfer(HashMapEntry[] newTable, boolean rehash) {
+ void transfer(HashMapEntry[] newTable) {
int newCapacity = newTable.length;
for (LinkedHashMapEntry<K,V> e = header.after; e != header; e = e.after) {
- if (rehash)
- e.hash = (e.key == null) ? 0 : hash(e.key);
int index = indexFor(e.hash, newCapacity);
e.next = newTable[index];
newTable[index] = e;
diff --git a/ojluni/src/main/java/java/util/WeakHashMap.java b/ojluni/src/main/java/java/util/WeakHashMap.java
index 1e67600..7785e05 100755
--- a/ojluni/src/main/java/java/util/WeakHashMap.java
+++ b/ojluni/src/main/java/java/util/WeakHashMap.java
@@ -189,68 +189,6 @@
*/
int modCount;
- /**
- * The default threshold of map capacity above which alternative hashing is
- * used for String keys. Alternative hashing reduces the incidence of
- * collisions due to weak hash code calculation for String keys.
- * <p/>
- * This value may be overridden by defining the system property
- * {@code jdk.map.althashing.threshold}. A property value of {@code 1}
- * forces alternative hashing to be used at all times whereas
- * {@code -1} value ensures that alternative hashing is never used.
- */
- static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
-
- /**
- * holds values which can't be initialized until after VM is booted.
- */
- private static class Holder {
-
- /**
- * Table capacity above which to switch to use alternative hashing.
- */
- static final int ALTERNATIVE_HASHING_THRESHOLD;
-
- static {
- String altThreshold = java.security.AccessController.doPrivileged(
- new sun.security.action.GetPropertyAction(
- "jdk.map.althashing.threshold"));
-
- int threshold;
- try {
- threshold = (null != altThreshold)
- ? Integer.parseInt(altThreshold)
- : ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;
-
- // disable alternative hashing if -1
- if (threshold == -1) {
- threshold = Integer.MAX_VALUE;
- }
-
- if (threshold < 0) {
- throw new IllegalArgumentException("value must be positive integer.");
- }
- } catch(IllegalArgumentException failed) {
- throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
- }
- ALTERNATIVE_HASHING_THRESHOLD = threshold;
- }
- }
-
- /**
- * If {@code true} then perform alternate hashing to reduce the incidence of
- * collisions due to weak hash code calculation.
- */
- transient boolean useAltHashing;
-
- /**
- * A randomizing value associated with this instance that is applied to
- * hash code of keys to make hash collisions harder to find.
- *
- * This hash seed is only used if {@code useAltHashing} is true.
- */
- transient int hashSeed;
-
@SuppressWarnings("unchecked")
private Entry<K,V>[] newTable(int n) {
return (Entry<K,V>[]) new Entry[n];
@@ -281,13 +219,6 @@
table = newTable(capacity);
this.loadFactor = loadFactor;
threshold = (int)(capacity * loadFactor);
- useAltHashing = sun.misc.VM.isBooted() &&
- (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
- if (useAltHashing) {
- hashSeed = sun.misc.Hashing.randomHashSeed(this);
- } else {
- hashSeed = 0;
- }
}
/**
@@ -356,34 +287,6 @@
}
/**
- * 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;
- if (useAltHashing) {
- h = hashSeed;
- if (k instanceof String) {
- return sun.misc.Hashing.stringHash32((String) k);
- } else {
- h ^= k.hashCode();
- }
- } 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) {
@@ -472,7 +375,7 @@
*/
public V get(Object key) {
Object k = maskNull(key);
- int h = hash(k);
+ int h = sun.misc.Hashing.singleWordWangJenkinsHash(k);
Entry<K,V>[] tab = getTable();
int index = indexFor(h, tab.length);
Entry<K,V> e = tab[index];
@@ -502,7 +405,7 @@
*/
Entry<K,V> getEntry(Object key) {
Object k = maskNull(key);
- int h = hash(k);
+ int h = sun.misc.Hashing.singleWordWangJenkinsHash(k);
Entry<K,V>[] tab = getTable();
int index = indexFor(h, tab.length);
Entry<K,V> e = tab[index];
@@ -525,7 +428,7 @@
*/
public V put(K key, V value) {
Object k = maskNull(key);
- int h = hash(k);
+ int h = sun.misc.Hashing.singleWordWangJenkinsHash(k);
Entry<K,V>[] tab = getTable();
int i = indexFor(h, tab.length);
@@ -569,14 +472,7 @@
}
Entry<K,V>[] newTable = newTable(newCapacity);
- boolean oldAltHashing = useAltHashing;
- useAltHashing |= sun.misc.VM.isBooted() &&
- (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
- boolean rehash = oldAltHashing ^ useAltHashing;
- if (rehash) {
- hashSeed = sun.misc.Hashing.randomHashSeed(this);
- }
- transfer(oldTable, newTable, rehash);
+ transfer(oldTable, newTable);
table = newTable;
/*
@@ -588,13 +484,13 @@
threshold = (int)(newCapacity * loadFactor);
} else {
expungeStaleEntries();
- transfer(newTable, oldTable, false);
+ transfer(newTable, oldTable);
table = oldTable;
}
}
/** Transfers all entries from src to dest tables */
- private void transfer(Entry<K,V>[] src, Entry<K,V>[] dest, boolean rehash) {
+ private void transfer(Entry<K,V>[] src, Entry<K,V>[] dest) {
for (int j = 0; j < src.length; ++j) {
Entry<K,V> e = src[j];
src[j] = null;
@@ -606,9 +502,6 @@
e.value = null; // " "
size--;
} else {
- if (rehash) {
- e.hash = hash(key);
- }
int i = indexFor(e.hash, dest.length);
e.next = dest[i];
dest[i] = e;
@@ -677,7 +570,7 @@
*/
public V remove(Object key) {
Object k = maskNull(key);
- int h = hash(k);
+ int h = sun.misc.Hashing.singleWordWangJenkinsHash(k);
Entry<K,V>[] tab = getTable();
int i = indexFor(h, tab.length);
Entry<K,V> prev = tab[i];
@@ -708,7 +601,7 @@
Entry<K,V>[] tab = getTable();
Map.Entry<?,?> entry = (Map.Entry<?,?>)o;
Object k = maskNull(entry.getKey());
- int h = hash(k);
+ int h = sun.misc.Hashing.singleWordWangJenkinsHash(k);
int i = indexFor(h, tab.length);
Entry<K,V> prev = tab[i];
Entry<K,V> e = prev;
diff --git a/ojluni/src/main/java/sun/misc/Hashing.java b/ojluni/src/main/java/sun/misc/Hashing.java
index 50e55ab..2b3b144 100755
--- a/ojluni/src/main/java/sun/misc/Hashing.java
+++ b/ojluni/src/main/java/sun/misc/Hashing.java
@@ -25,9 +25,6 @@
package sun.misc;
import java.util.concurrent.ThreadLocalRandom;
-// ----- BEGIN android -----
-import java.lang.JavaLangAccess;
-// ----- END android -----
/**
* Hashing utilities.
@@ -43,212 +40,18 @@
throw new Error("No instances");
}
- public static int murmur3_32(byte[] data) {
- return murmur3_32(0, data, 0, data.length);
- }
+ // Spread bits to regularize both segment and index locations,
+ // using variant of single-word Wang/Jenkins hash.
+ //
+ // Based on commit 1424a2a1a9fc53dc8b859a77c02c924.
+ public static int singleWordWangJenkinsHash(Object k) {
+ int h = k.hashCode();
- 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;
- }
-
- /**
- * Return a 32 bit hash value for the specified string. The algorithm is
- * unspecified but will be consistent within a VM instance.
- *
- * @param string String to be hashed.
- * @return hash value of the string.
- */
- public static int stringHash32(String string) {
- // Android-changed: Access JavaLangAccess directly.
- return JavaLangAccess.getStringHash32(string);
- }
-
- /**
- * Return a non-zero 32-bit pseudo random value. The {@code instance} object
- * may be used as part of the value.
- *
- * @param instance an object to use if desired in choosing value.
- * @return a non-zero 32-bit pseudo random value.
- */
- public static int randomHashSeed(Object instance) {
- int seed;
- if (sun.misc.VM.isBooted()) {
- seed = ThreadLocalRandom.current().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;
+ h += (h << 15) ^ 0xffffcd7d;
+ h ^= (h >>> 10);
+ h += (h << 3);
+ h ^= (h >>> 6);
+ h += (h << 2) + (h << 14);
+ return h ^ (h >>> 16);
}
}
