Fixed LinkedHashMap bug 2121546
Also made minor improvements in LinkedHashMap and NegativeCache.
(The "opportunities for improvement" were discovered while investigating the bug.)
diff --git a/libcore/luni/src/main/java/java/net/NegCacheElement.java b/libcore/luni/src/main/java/java/net/NegCacheElement.java
index e166db4..e195f31 100644
--- a/libcore/luni/src/main/java/java/net/NegCacheElement.java
+++ b/libcore/luni/src/main/java/java/net/NegCacheElement.java
@@ -4,9 +4,9 @@
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
- *
+ *
* http://www.apache.org/licenses/LICENSE-2.0
- *
+ *
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
@@ -28,17 +28,17 @@
final long nanoTimeAdded = System.nanoTime();
// END android-changed
- // holds the name of the host for which the lookup failed
- final String hostName;
+ // holds the name of the lookup failure message for this host
+ final String failedMessage;
/**
* Constructor used to set the hostname for the entry for which the lookup
* failed.
*
- * @param hostName
+ * @param failedMessage
* name of the host for which the lookup failed.
*/
- NegCacheElement(String hostName) {
- this.hostName = hostName;
+ NegCacheElement(String failedMessage) {
+ this.failedMessage = failedMessage;
}
}
diff --git a/libcore/luni/src/main/java/java/net/NegativeCache.java b/libcore/luni/src/main/java/java/net/NegativeCache.java
index e66d3f3..d6b1515 100644
--- a/libcore/luni/src/main/java/java/net/NegativeCache.java
+++ b/libcore/luni/src/main/java/java/net/NegativeCache.java
@@ -4,9 +4,9 @@
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
- *
+ *
* http://www.apache.org/licenses/LICENSE-2.0
- *
+ *
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
@@ -28,45 +28,32 @@
*
* @see NegCacheElement
*/
-class NegativeCache<K, V> extends LinkedHashMap<K, V> {
-
- private static final long serialVersionUID = 1L;
-
- private static NegativeCache<String, NegCacheElement> negCache;
-
- // maximum number of entries in the cache
+class NegativeCache {
+ // maximum number of entries in the cache
private static final int MAX_NEGATIVE_ENTRIES = 5;
// the loading for the cache
- private static final float LOADING = 0.75F;
+ private static final float LOAD_FACTOR = 0.75F;
- /**
- * Constructs a negative cache for name lookups.
- *
- * @param initialCapacity
- * the initial size of the cache.
- * @param loadFactor
- * the load factor of the backing map.
- * @param accessOrder
- * if {@code true} indicates that traversal order should begin
- * with most recently accessed element.
- */
- NegativeCache(int initialCapacity, float loadFactor, boolean accessOrder) {
- super(initialCapacity, loadFactor, accessOrder);
- }
+ private static final Map<String, NegCacheElement> negCache
+ = new LinkedHashMap<String, NegCacheElement>(
+ 2 * MAX_NEGATIVE_ENTRIES, LOAD_FACTOR, true) {
- /**
- * Returns whether the eldest entry should be removed. It is removed if the
- * size has grown beyond the maximum size allowed for the cache. A {@code
- * LinkedHashMap} is created such that the least recently used entry is
- * deleted.
- *
- * @param eldest
- * the map entry which will be deleted if we return {@code true}.
- */
- @Override
- protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
- return size() > MAX_NEGATIVE_ENTRIES;
+ /**
+ * Returns whether the eldest entry should be removed. It is removed if
+ * the size has grown beyond the maximum size allowed for the cache.
+ *
+ * @param eldest
+ * the LRU entry, which will be deleted if we return true.
+ */
+ @Override protected boolean removeEldestEntry(
+ Entry<String, NegCacheElement> eldest) {
+ return size() > MAX_NEGATIVE_ENTRIES;
+ }
+ };
+
+ /** Ensures non-instantiability */
+ private NegativeCache() {
}
/**
@@ -79,7 +66,6 @@
* the message returned when the lookup fails.
*/
static synchronized void put(String hostName, String failedMessage) {
- checkCacheExists();
negCache.put(hostName, new NegCacheElement(failedMessage));
}
@@ -93,7 +79,6 @@
* entry has not yet expired.
*/
static synchronized String getFailedMessage(String hostName) {
- checkCacheExists();
NegCacheElement element = negCache.get(hostName);
if (element != null) {
// check if element is still valid
@@ -103,9 +88,10 @@
int ttl = 10;
try {
if (ttlValue != null) {
- ttl = Integer.decode(ttlValue).intValue();
+ ttl = Integer.decode(ttlValue);
}
} catch (NumberFormatException e) {
+ // If exception, go with ttl == 10
}
if (ttl == 0) {
negCache.clear();
@@ -122,7 +108,7 @@
}
}
if (element != null) {
- return element.hostName;
+ return element.failedMessage;
}
return null;
}
@@ -135,20 +121,4 @@
return ttl * 1000000000;
}
// END android-added
-
- /**
- * This method checks if we have created the cache and if not creates it
- */
- static synchronized void checkCacheExists() {
- if (negCache == null) {
- /*
- * Create with the access order set so ordering is based on when the
- * entries were last accessed. We make the default cache size one
- * greater than the maximum number of entries as we will grow to one
- * larger and then delete the LRU entry
- */
- negCache = new NegativeCache<String, NegCacheElement>(
- MAX_NEGATIVE_ENTRIES + 1, LOADING, true);
- }
- }
}
diff --git a/libcore/luni/src/main/java/java/util/HashMap.java b/libcore/luni/src/main/java/java/util/HashMap.java
index af24d86..28978d4 100644
--- a/libcore/luni/src/main/java/java/util/HashMap.java
+++ b/libcore/luni/src/main/java/java/util/HashMap.java
@@ -376,8 +376,7 @@
int hash = secondaryHash(key.hashCode());
HashMapEntry<K, V>[] tab = table;
int index = hash & (tab.length - 1);
- HashMapEntry<K, V> first = tab[index];
- for (HashMapEntry<K, V> e = first; e != null; e = e.next) {
+ for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) {
if (e.hash == hash && key.equals(e.key)) {
preModify(e);
V oldValue = e.value;
@@ -391,16 +390,15 @@
if (size++ > threshold) {
tab = doubleCapacity();
index = hash & (tab.length - 1);
- first = tab[index];
}
- tab[index] = newEntry(key, value, hash, first);
+ addNewEntry(key, value, hash, index);
return null;
}
private V putValueForNullKey(V value) {
HashMapEntry<K, V> entry = entryForNullKey;
if (entry == null) {
- entryForNullKey = newEntry(null, value, 0, null);
+ addNewEntryForNullKey(value);
size++;
modCount++;
return null;
@@ -455,13 +453,22 @@
}
/**
- * Creates a new entry for the given key, value, hash, and successor entry.
- * This method is called by put (and indirectly, putAll), and overridden by
- * LinkedHashMap. The hash must incorporate the secondary hash function.
+ * Creates a new entry for the given key, value, hash, and index and
+ * inserts it into the hash table. This method is called by put
+ * (and indirectly, putAll), and overridden by LinkedHashMap. The hash
+ * must incorporate the secondary hash function.
*/
- HashMapEntry<K, V> newEntry(
- K key, V value, int hash, HashMapEntry<K, V> next) {
- return new HashMapEntry<K, V>(key, value, hash, next);
+ void addNewEntry(K key, V value, int hash, int index) {
+ table[index] = new HashMapEntry<K, V>(key, value, hash, table[index]);
+ }
+
+ /**
+ * Creates a new entry for the null key, and the given value and
+ * inserts it into the hash table. This method is called by put
+ * (and indirectly, putAll), and overridden by LinkedHashMap.
+ */
+ void addNewEntryForNullKey(V value) {
+ entryForNullKey = new HashMapEntry<K, V>(null, value, 0, null);
}
/**
diff --git a/libcore/luni/src/main/java/java/util/LinkedHashMap.java b/libcore/luni/src/main/java/java/util/LinkedHashMap.java
index 4e2fb3c..cd6825b 100644
--- a/libcore/luni/src/main/java/java/util/LinkedHashMap.java
+++ b/libcore/luni/src/main/java/java/util/LinkedHashMap.java
@@ -57,7 +57,7 @@
* The first real entry is header.nxt, and the last is header.prv.
* If the map is empty, header.nxt == header && header.prv == header.
*/
- private transient LinkedEntry<K, V> header;
+ transient LinkedEntry<K, V> header;
/**
* True if access ordered, false if insertion ordered.
@@ -138,9 +138,8 @@
constructorPutAll(map);
}
- @Override void init(){
- header = new LinkedEntry<K, V>(null, null, 0, null, null, null);
- header.nxt = header.prv = header;
+ @Override void init() {
+ header = new LinkedEntry<K, V>();
}
/**
@@ -150,6 +149,13 @@
LinkedEntry<K, V> nxt;
LinkedEntry<K, V> prv;
+ /** Create the header entry */
+ LinkedEntry() {
+ super(null, null, 0, null);
+ nxt = prv = this;
+ }
+
+ /** Create a normal entry */
LinkedEntry(K key, V value, int hash, HashMapEntry<K, V> next,
LinkedEntry<K, V> nxt, LinkedEntry<K, V> prv) {
super(key, value, hash, next);
@@ -162,20 +168,45 @@
* Evicts eldest entry if instructed, creates a new entry and links it in
* as head of linked list. This method should call constructorNewEntry
* (instead of duplicating code) if the performance of your VM permits.
+ *
+ * <p>It may seem strange that this method is tasked with adding the entry
+ * to the hash table (which is properly the province of our superclass).
+ * The alternative of passing the "next" link in to this method and
+ * returning the newly created element does not work! If we remove an
+ * (eldest) entry that happens to be the first entry in the same bucket
+ * as the newly created entry, the "next" link would become invalid, and
+ * the resulting hash table corrupt.
*/
- @Override LinkedEntry<K, V> newEntry(
- K key, V value, int hash, HashMapEntry<K, V> next) {
+ @Override void addNewEntry(K key, V value, int hash, int index) {
+ LinkedEntry<K, V> header = this.header;
+
// Remove eldest entry if instructed to do so.
LinkedEntry<K, V> eldest = header.nxt;
- if (eldest != header && removeEldestEntry(eldest))
+ if (eldest != header && removeEldestEntry(eldest)) {
remove(eldest.key);
+ }
- // Create new entry and link it on to list
- LinkedEntry<K, V> header = this.header;
+ // Create new entry, link it on to list, and put it into table
LinkedEntry<K, V> oldTail = header.prv;
- LinkedEntry<K, V> newTail
- = new LinkedEntry<K,V>(key, value, hash, next, header, oldTail);
- return oldTail.nxt = header.prv = newTail;
+ LinkedEntry<K, V> newTail = new LinkedEntry<K,V>(
+ key, value, hash, table[index], header, oldTail);
+ table[index] = oldTail.nxt = header.prv = newTail;
+ }
+
+ @Override void addNewEntryForNullKey(V value) {
+ LinkedEntry<K, V> header = this.header;
+
+ // Remove eldest entry if instructed to do so.
+ LinkedEntry<K, V> eldest = header.nxt;
+ if (eldest != header && removeEldestEntry(eldest)) {
+ remove(eldest.key);
+ }
+
+ // Create new entry, link it on to list, and put it into table
+ LinkedEntry<K, V> oldTail = header.prv;
+ LinkedEntry<K, V> newTail = new LinkedEntry<K,V>(
+ null, value, 0, null, header, oldTail);
+ entryForNullKey = oldTail.nxt = header.prv = newTail;
}
/**
@@ -274,7 +305,7 @@
return true;
}
}
- return entryForNullKey != null && entryForNullKey.value == null;
+ return false;
}
// value is non-null
@@ -284,20 +315,19 @@
return true;
}
}
- return entryForNullKey != null && value.equals(entryForNullKey.value);
+ return false;
}
-
+
public void clear() {
super.clear();
// Clear all links to help GC
LinkedEntry<K, V> header = this.header;
- LinkedEntry<K, V> e = header;
- do {
+ for (LinkedEntry<K, V> e = header.nxt; e != header; ) {
LinkedEntry<K, V> nxt = e.nxt;
e.nxt = e.prv = null;
e = nxt;
- } while(e != header);
+ }
header.nxt = header.prv = header;
}
diff --git a/libcore/luni/src/test/java/tests/api/java/util/LinkedHashMapTest.java b/libcore/luni/src/test/java/tests/api/java/util/LinkedHashMapTest.java
index f3d0a7b..d5223fe 100644
--- a/libcore/luni/src/test/java/tests/api/java/util/LinkedHashMapTest.java
+++ b/libcore/luni/src/test/java/tests/api/java/util/LinkedHashMapTest.java
@@ -20,7 +20,7 @@
import dalvik.annotation.TestTargetNew;
import dalvik.annotation.TestTargets;
import dalvik.annotation.TestLevel;
-import dalvik.annotation.TestTargetClass;
+import dalvik.annotation.TestTargetClass;
import java.util.AbstractMap;
import java.util.ArrayList;
@@ -38,7 +38,7 @@
/**
* @tests java.util.LinkedHashMap
*/
-@TestTargetClass(LinkedHashMap.class)
+@TestTargetClass(LinkedHashMap.class)
public class LinkedHashMapTest extends junit.framework.TestCase {
LinkedHashMap hm;
@@ -48,13 +48,13 @@
Object[] objArray;
Object[] objArray2;
-
+
static final class CacheMap extends LinkedHashMap {
protected boolean removeEldestEntry(Map.Entry e) {
return size() > 5;
}
}
-
+
private static class MockMapNull extends AbstractMap {
@Override
public Set entrySet() {
@@ -131,7 +131,7 @@
} catch (IllegalArgumentException e) {
//expected
}
-
+
LinkedHashMap empty = new LinkedHashMap(0, 0.75f);
assertNull("Empty hashtable access", empty.get("nothing"));
empty.put("something", "here");
@@ -196,7 +196,7 @@
// Test for method java.lang.Object
// java.util.LinkedHashMap.put(java.lang.Object, java.lang.Object)
hm.put("KEY", "VALUE");
- assertEquals("Failed to install key/value pair",
+ assertEquals("Failed to install key/value pair",
"VALUE", hm.get("KEY"));
LinkedHashMap m = new LinkedHashMap();
@@ -237,7 +237,7 @@
notes = "",
method = "putAll",
args = {java.util.Map.class}
- )
+ )
public void test_putAllLjava_util_Map() {
// Test for method void java.util.LinkedHashMap.putAll(java.util.Map)
LinkedHashMap hm2 = new LinkedHashMap();
@@ -271,7 +271,7 @@
} catch (NullPointerException e) {
// expected.
}
- }
+ }
/**
* @tests java.util.LinkedHashMap#entrySet()
@@ -303,7 +303,7 @@
)
public void test_entrySetRemove() {
entrySetRemoveHelper("military", "intelligence");
- entrySetRemoveHelper(null, "hypothesis");
+ entrySetRemoveHelper(null, "hypothesis");
}
private void entrySetRemoveHelper(String key, String value) {
Map<String, String> m1 = new LinkedHashMap<String, String>();
@@ -475,23 +475,23 @@
// get the keySet() and values() on the original Map
Set keys = map.keySet();
Collection values = map.values();
- assertEquals("values() does not work",
+ assertEquals("values() does not work",
"value", values.iterator().next());
- assertEquals("keySet() does not work",
+ assertEquals("keySet() does not work",
"key", keys.iterator().next());
AbstractMap map2 = (AbstractMap) map.clone();
map2.put("key", "value2");
Collection values2 = map2.values();
assertTrue("values() is identical", values2 != values);
-
+
// values() and keySet() on the cloned() map should be different
- assertEquals("values() was not cloned",
+ assertEquals("values() was not cloned",
"value2", values2.iterator().next());
map2.clear();
map2.put("key2", "value3");
Set key2 = map2.keySet();
assertTrue("keySet() is identical", key2 != keys);
- assertEquals("keySet() was not cloned",
+ assertEquals("keySet() was not cloned",
"key2", key2.iterator().next());
}
@@ -512,10 +512,10 @@
hm1.put("c", "c");
LinkedHashMap<String, String> hm2 = (LinkedHashMap<String, String>) hm1.clone();
hm1.get("a");
-
+
Map.Entry<String, String>[] set = new Map.Entry[3];
Iterator<Map.Entry<String,String>> iterator = hm1.entrySet().iterator();
-
+
assertEquals("b", iterator.next().getKey());
assertEquals("c", iterator.next().getKey());
assertEquals("a", iterator.next().getKey());
@@ -531,7 +531,7 @@
notes = "Regression test.",
method = "clone",
args = {}
- )
+ )
// regresion test for HARMONY-4603
public void test_clone_Mock() {
LinkedHashMap hashMap = new MockMap();
@@ -557,7 +557,30 @@
protected boolean removeEldestEntry(Map.Entry e) {
return num > 1;
}
- }
+ }
+
+ /**
+ * @tests put/get interaction in access-order map where removeEldest
+ * returns true.
+ */
+ @TestTargetNew(
+ level = TestLevel.PARTIAL_COMPLETE,
+ notes = "Regression for bug Google Bug 2121546",
+ method = "get",
+ args = {java.lang.Object.class}
+ )
+ public void test_removeEldestFromSameBucketAsNewEntry() {
+ LinkedHashMap<String, String> map
+ = new LinkedHashMap<String, String>(6, 0.75F, true) {
+ @Override
+ protected boolean removeEldestEntry(Entry<String, String> e) {
+ return true;
+ }
+ };
+ map.put("N", "E");
+ map.put("F", "I");
+ assertEquals(null, map.get("N"));
+ }
/**
* @tests java.util.LinkedHashMap#containsKey(java.lang.Object)
