Fixed LinkedHashMap bug 2121546

Also made minor improvements in LinkedHashMap and NegativeCache.
(The "opportunities for improvement" were discovered while investigating the bug.)

5 files changed, 139 insertions, 109 deletions

diff --git a/luni/src/main/java/java/net/NegCacheElement.java b/luni/src/main/java/java/net/NegCacheElement.java
index e166db4..e195f31 100644
--- a/luni/src/main/java/java/net/NegCacheElement.java
+++ b/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 @@ class NegCacheElement {
     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/luni/src/main/java/java/net/NegativeCache.java b/luni/src/main/java/java/net/NegativeCache.java
index e66d3f3..d6b1515 100644
--- a/luni/src/main/java/java/net/NegativeCache.java
+++ b/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 @@ import org.apache.harmony.luni.util.PriviAction;
  *
  * @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 @@ class NegativeCache<K, V> extends LinkedHashMap<K, V> {
      *            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 @@ class NegativeCache<K, V> extends LinkedHashMap<K, V> {
      *         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 @@ class NegativeCache<K, V> extends LinkedHashMap<K, V> {
             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 @@ class NegativeCache<K, V> extends LinkedHashMap<K, V> {
             }
         }
         if (element != null) {
-            return element.hostName;
+            return element.failedMessage;
         }
         return null;
     }
@@ -135,20 +121,4 @@ class NegativeCache<K, V> extends LinkedHashMap<K, V> {
         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/luni/src/main/java/java/util/HashMap.java b/luni/src/main/java/java/util/HashMap.java
index af24d86..28978d4 100644
--- a/luni/src/main/java/java/util/HashMap.java
+++ b/luni/src/main/java/java/util/HashMap.java
@@ -376,8 +376,7 @@ public class HashMap<K, V> extends AbstractMap<K, V>
         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 @@ public class HashMap<K, V> extends AbstractMap<K, V>
         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 @@ public class HashMap<K, V> extends AbstractMap<K, V>
     }
 
     /**
-     * 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.
+     */
+    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.
      */
-    HashMapEntry<K, V> newEntry(
-            K key, V value, int hash, HashMapEntry<K, V> next) {
-        return new HashMapEntry<K, V>(key, value, hash, next);
+    void addNewEntryForNullKey(V value) {
+        entryForNullKey = new HashMapEntry<K, V>(null, value, 0, null);
     }
 
     /**
diff --git a/luni/src/main/java/java/util/LinkedHashMap.java b/luni/src/main/java/java/util/LinkedHashMap.java
index 4e2fb3c..cd6825b 100644
--- a/luni/src/main/java/java/util/LinkedHashMap.java
+++ b/luni/src/main/java/java/util/LinkedHashMap.java
@@ -57,7 +57,7 @@ public class LinkedHashMap<K, V> extends HashMap<K, V> {
      * 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 @@ public class LinkedHashMap<K, V> extends HashMap<K, V> {
         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 @@ public class LinkedHashMap<K, V> extends HashMap<K, V> {
         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 @@ public class LinkedHashMap<K, V> extends HashMap<K, V> {
      * 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, 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, table[index], header, oldTail);
+        table[index] = oldTail.nxt = header.prv = newTail;
+    }
 
-        // Create new entry and link it on to list
+    @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>(key, value, hash, next, header, oldTail);
-        return oldTail.nxt = header.prv = newTail;
+        LinkedEntry<K, V> newTail = new LinkedEntry<K,V>(
+                null, value, 0, null, header, oldTail);
+        entryForNullKey = oldTail.nxt = header.prv = newTail;
     }
 
     /**
@@ -274,7 +305,7 @@ public class LinkedHashMap<K, V> extends HashMap<K, V> {
                     return true;
                 }
             }
-            return entryForNullKey != null && entryForNullKey.value == null;
+            return false;
         }
 
         // value is non-null
@@ -284,20 +315,19 @@ public class LinkedHashMap<K, V> extends HashMap<K, V> {
                 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/luni/src/test/java/tests/api/java/util/LinkedHashMapTest.java b/luni/src/test/java/tests/api/java/util/LinkedHashMapTest.java
index f3d0a7b..d5223fe 100644
--- a/luni/src/test/java/tests/api/java/util/LinkedHashMapTest.java
+++ b/luni/src/test/java/tests/api/java/util/LinkedHashMapTest.java
@@ -20,7 +20,7 @@ package tests.api.java.util;
 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 @@ import tests.support.Support_UnmodifiableCollectionTest;
 /**
  * @tests java.util.LinkedHashMap
  */
-@TestTargetClass(LinkedHashMap.class) 
+@TestTargetClass(LinkedHashMap.class)
 public class LinkedHashMapTest extends junit.framework.TestCase {
 
     LinkedHashMap hm;
@@ -48,13 +48,13 @@ public class LinkedHashMapTest extends junit.framework.TestCase {
     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 @@ public class LinkedHashMapTest extends junit.framework.TestCase {
         } 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 @@ public class LinkedHashMapTest extends junit.framework.TestCase {
         // 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 @@ public class LinkedHashMapTest extends junit.framework.TestCase {
         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 @@ public class LinkedHashMapTest extends junit.framework.TestCase {
         } catch (NullPointerException e) {
             // expected.
         }
-    } 
+    }
 
     /**
      * @tests java.util.LinkedHashMap#entrySet()
@@ -303,7 +303,7 @@ public class LinkedHashMapTest extends junit.framework.TestCase {
     )
     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 @@ public class LinkedHashMapTest extends junit.framework.TestCase {
         // 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 @@ public class LinkedHashMapTest extends junit.framework.TestCase {
         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 @@ public class LinkedHashMapTest extends junit.framework.TestCase {
         notes = "Regression test.",
         method = "clone",
         args = {}
-    )   
+    )
     // regresion test for HARMONY-4603
     public void test_clone_Mock() {
         LinkedHashMap hashMap = new MockMap();
@@ -557,7 +557,30 @@ public class LinkedHashMapTest extends junit.framework.TestCase {
         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)