8029795: LinkedHashMap.getOrDefault() doesn't update access order.
authormduigou
Tue, 17 Dec 2013 09:36:59 -0800
changeset 22058 db159b144c98
parent 22057 890596c090a9
child 22059 3ad91a1b7495
8029795: LinkedHashMap.getOrDefault() doesn't update access order. Reviewed-by: psandoz
jdk/src/share/classes/java/util/LinkedHashMap.java
jdk/test/java/util/LinkedHashMap/Basic.java
--- a/jdk/src/share/classes/java/util/LinkedHashMap.java	Tue Dec 17 13:27:30 2013 +0000
+++ b/jdk/src/share/classes/java/util/LinkedHashMap.java	Tue Dec 17 09:36:59 2013 -0800
@@ -28,7 +28,6 @@
 import java.util.function.Consumer;
 import java.util.function.BiConsumer;
 import java.util.function.BiFunction;
-import java.io.Serializable;
 import java.io.IOException;
 
 /**
@@ -63,14 +62,17 @@
  * provided to create a linked hash map whose order of iteration is the order
  * in which its entries were last accessed, from least-recently accessed to
  * most-recently (<i>access-order</i>).  This kind of map is well-suited to
- * building LRU caches.  Invoking the <tt>put</tt> or <tt>get</tt> method
- * results in an access to the corresponding entry (assuming it exists after
- * the invocation completes).  The <tt>putAll</tt> method generates one entry
- * access for each mapping in the specified map, in the order that key-value
- * mappings are provided by the specified map's entry set iterator.  <i>No
- * other methods generate entry accesses.</i> In particular, operations on
- * collection-views do <i>not</i> affect the order of iteration of the backing
- * map.
+ * building LRU caches.  Invoking the {@code put}, {@code putIfAbsent},
+ * {@code get}, {@code getOrDefault}, {@code compute}, {@code computeIfAbsent},
+ * {@code computeIfPresent}, or {@code merge} methods results
+ * in an access to the corresponding entry (assuming it exists after the
+ * invocation completes). The {@code replace} methods only result in an access
+ * of the entry if the value is replaced.  The {@code putAll} method generates one
+ * entry access for each mapping in the specified map, in the order that
+ * key-value mappings are provided by the specified map's entry set iterator.
+ * <i>No other methods generate entry accesses.</i>  In particular, operations
+ * on collection-views do <i>not</i> affect the order of iteration of the
+ * backing map.
  *
  * <p>The {@link #removeEldestEntry(Map.Entry)} method may be overridden to
  * impose a policy for removing stale mappings automatically when new mappings
@@ -112,8 +114,8 @@
  * iteration order.  In insertion-ordered linked hash maps, merely changing
  * the value associated with a key that is already contained in the map is not
  * a structural modification.  <strong>In access-ordered linked hash maps,
- * merely querying the map with <tt>get</tt> is a structural
- * modification.</strong>)
+ * merely querying the map with <tt>get</tt> is a structural modification.
+ * </strong>)
  *
  * <p>The iterators returned by the <tt>iterator</tt> method of the collections
  * returned by all of this class's collection view methods are
@@ -443,8 +445,19 @@
     }
 
     /**
-     * Removes all of the mappings from this map.
-     * The map will be empty after this call returns.
+     * {@inheritDoc}
+     */
+    public V getOrDefault(Object key, V defaultValue) {
+       Node<K,V> e;
+       if ((e = getNode(hash(key), key)) == null)
+           return defaultValue;
+       if (accessOrder)
+           afterNodeAccess(e);
+       return e.value;
+   }
+
+    /**
+     * {@inheritDoc}
      */
     public void clear() {
         super.clear();
--- a/jdk/test/java/util/LinkedHashMap/Basic.java	Tue Dec 17 13:27:30 2013 +0000
+++ b/jdk/test/java/util/LinkedHashMap/Basic.java	Tue Dec 17 09:36:59 2013 -0800
@@ -23,28 +23,29 @@
 
 /**
  * @test
- * @bug 4245809
+ * @bug 4245809 8029795
  * @summary Basic test for LinkedHashMap.  (Based on MapBash)
  */
 
 import java.util.*;
+import java.util.function.*;
 import java.io.*;
 
 public class Basic {
-    static Random rnd = new Random(666);
-    static Object nil = new Integer(0);
+    final static Random rnd = new Random(666);
+    final static Integer nil = new Integer(0);
 
     public static void main(String[] args)  throws Exception {
         int numItr =  500;
         int mapSize = 500;
 
-        // Linked List test
+        // Linked List testk
         for (int i=0; i<numItr; i++) {
-            Map m = new LinkedHashMap();
-            Object head = nil;
+            Map<Integer,Integer> m = new LinkedHashMap();
+            Integer head = nil;
 
             for (int j=0; j<mapSize; j++) {
-                Object newHead;
+                Integer newHead;
                 do {
                     newHead = new Integer(rnd.nextInt());
                 } while (m.containsKey(newHead));
@@ -57,7 +58,7 @@
             if (new HashMap(m).hashCode() != m.hashCode())
                 throw new Exception("Incorrect hashCode computation.");
 
-            Map m2 = new LinkedHashMap(); m2.putAll(m);
+            Map<Integer,Integer> m2 = new LinkedHashMap(); m2.putAll(m);
             m2.values().removeAll(m.keySet());
             if (m2.size()!= 1 || !m2.containsValue(nil))
                 throw new Exception("Collection views test failed.");
@@ -66,7 +67,7 @@
             while (head != nil) {
                 if (!m.containsKey(head))
                     throw new Exception("Linked list doesn't contain a link.");
-                Object newHead = m.get(head);
+                Integer newHead = m.get(head);
                 if (newHead == null)
                     throw new Exception("Could not retrieve a link.");
                 m.remove(head);
@@ -79,7 +80,7 @@
                 throw new Exception("Linked list size not as expected.");
         }
 
-        Map m = new LinkedHashMap();
+        Map<Integer,Integer> m = new LinkedHashMap();
         for (int i=0; i<mapSize; i++)
             if (m.put(new Integer(i), new Integer(2*i)) != null)
                 throw new Exception("put returns non-null value erroenously.");
@@ -88,12 +89,12 @@
                 throw new Exception("contains value "+i);
         if (m.put(nil, nil) == null)
             throw new Exception("put returns a null value erroenously.");
-        Map m2 = new LinkedHashMap(); m2.putAll(m);
+        Map<Integer,Integer> m2 = new LinkedHashMap(); m2.putAll(m);
         if (!m.equals(m2))
             throw new Exception("Clone not equal to original. (1)");
         if (!m2.equals(m))
             throw new Exception("Clone not equal to original. (2)");
-        Set s = m.entrySet(), s2 = m2.entrySet();
+        Set<Map.Entry<Integer,Integer>> s = m.entrySet(), s2 = m2.entrySet();
         if (!s.equals(s2))
             throw new Exception("Clone not equal to original. (3)");
         if (!s2.equals(s))
@@ -137,7 +138,7 @@
 
         // Test ordering properties with insert order
         m = new LinkedHashMap();
-        List l = new ArrayList(mapSize);
+        List<Integer> l = new ArrayList(mapSize);
         for (int i=0; i<mapSize; i++) {
             Integer x = new Integer(i);
             m.put(x, x);
@@ -164,7 +165,7 @@
         if (!m.equals(m2))
             throw new Exception("Insert-order Map != clone.");
 
-        List l2 = new ArrayList(l);
+        List<Integer> l2 = new ArrayList(l);
         Collections.shuffle(l2);
         for (int i=0; i<mapSize; i++) {
             Integer x = (Integer) l2.get(i);
@@ -175,7 +176,7 @@
             throw new Exception("Clone: altered by read.");
 
         // Test ordering properties with access order
-        m = new LinkedHashMap(1000, .75f, true);
+        m = new LinkedHashMap(2*mapSize, .75f, true);
         for (int i=0; i<mapSize; i++) {
             Integer x = new Integer(i);
             m.put(x, x);
@@ -192,6 +193,70 @@
             throw new Exception("Insert order not properly altered by read.");
 
         for (int i=0; i<mapSize; i++) {
+            Integer x = (Integer) l2.get(i);
+            if (!m.getOrDefault(x, new Integer(i + 1000)).equals(x))
+                throw new Exception("Wrong value: "+i+", "+m.get(x)+", "+x);
+        }
+        if (!new ArrayList(m.keySet()).equals(l2))
+            throw new Exception("Insert order not properly altered by read.");
+
+        for (int i=0; i<mapSize; i++) {
+            Integer x = (Integer) l2.get(i);
+            if (!m.replace(x, x).equals(x))
+                throw new Exception("Wrong value: "+i+", "+m.get(x)+", "+x);
+        }
+        if (!new ArrayList(m.keySet()).equals(l2))
+            throw new Exception("Insert order not properly altered by replace.");
+
+        for (int i=0; i<mapSize; i++) {
+            Integer x = (Integer) l2.get(i);
+            if (!m.replace(x, x, x))
+                throw new Exception("Wrong value: "+i+", "+m.get(x)+", "+x);
+        }
+        if (!new ArrayList(m.keySet()).equals(l2))
+            throw new Exception("Insert order not properly altered by replace.");
+
+        BiFunction<Integer,Integer,Integer> f = (Integer y, Integer z) -> {
+            if (!Objects.equals(y,z))
+                throw new RuntimeException("unequal " + y + "," + z);
+            return new Integer(z);
+        };
+
+        for (int i=0; i<mapSize; i++) {
+            Integer x = (Integer) l2.get(i);
+            if (!x.equals(m.merge(x, x, f)))
+                throw new Exception("Wrong value: "+i+", "+m.get(x)+", "+x);
+        }
+        if (!new ArrayList(m.keySet()).equals(l2))
+            throw new Exception("Insert order not properly altered by replace.");
+
+        for (int i=0; i<mapSize; i++) {
+            Integer x = (Integer) l2.get(i);
+            if (!x.equals(m.compute(x, f)))
+                throw new Exception("Wrong value: "+i+", "+m.get(x)+", "+x);
+        }
+        if (!new ArrayList(m.keySet()).equals(l2))
+            throw new Exception("Insert order not properly altered by replace.");
+
+        for (int i=0; i<mapSize; i++) {
+            Integer x = (Integer) l2.get(i);
+            if(!x.equals(m.remove(x)))
+              throw new Exception("Missing key: "+i+", "+x);
+            if (!x.equals(m.computeIfAbsent(x, Integer::valueOf)))
+                throw new Exception("Wrong value: "+i+", "+m.get(x)+", "+x);
+        }
+        if (!new ArrayList(m.keySet()).equals(l2))
+            throw new Exception("Insert order not properly altered by replace.");
+
+        for (int i=0; i<mapSize; i++) {
+            Integer x = (Integer) l2.get(i);
+            if (!x.equals(m.computeIfPresent(x, f)))
+                throw new Exception("Wrong value: "+i+", "+m.get(x)+", "+x);
+        }
+        if (!new ArrayList(m.keySet()).equals(l2))
+            throw new Exception("Insert order not properly altered by replace.");
+
+        for (int i=0; i<mapSize; i++) {
             Integer x = new Integer(i);
             m.put(x, x);
         }