Merge IdentityHashMap from jdk-21.0.2-ga into the aosp/main branch

List of files:
  ojluni/src/main/java/java/util/IdentityHashMap.java
  ojluni/src/test/java/util/IdentityHashMap/Basic.java

Bug: 355185337
Test: CtsLibcoreOjTestCases
Change-Id: I48d5bb43b086e8b315a065f42f1a3ebb72acb0cf
diff --git a/EXPECTED_UPSTREAM b/EXPECTED_UPSTREAM
index ee06557..642ed6c 100644
--- a/EXPECTED_UPSTREAM
+++ b/EXPECTED_UPSTREAM
@@ -937,7 +937,7 @@
 ojluni/src/main/java/java/util/HashSet.java,jdk21u/jdk-21.0.1-ga,src/java.base/share/classes/java/util/HashSet.java
 ojluni/src/main/java/java/util/Hashtable.java,jdk17u/jdk-17.0.6-ga,src/java.base/share/classes/java/util/Hashtable.java
 ojluni/src/main/java/java/util/HexFormat.java,jdk17u/jdk-17.0.6-ga,src/java.base/share/classes/java/util/HexFormat.java
-ojluni/src/main/java/java/util/IdentityHashMap.java,jdk17u/jdk-17.0.6-ga,src/java.base/share/classes/java/util/IdentityHashMap.java
+ojluni/src/main/java/java/util/IdentityHashMap.java,jdk21u/jdk-21.0.2-ga,src/java.base/share/classes/java/util/IdentityHashMap.java
 ojluni/src/main/java/java/util/IllegalFormatArgumentIndexException.java,jdk17u/jdk-17.0.6-ga,src/java.base/share/classes/java/util/IllegalFormatArgumentIndexException.java
 ojluni/src/main/java/java/util/IllegalFormatCodePointException.java,jdk17u/jdk-17.0.6-ga,src/java.base/share/classes/java/util/IllegalFormatCodePointException.java
 ojluni/src/main/java/java/util/IllegalFormatConversionException.java,jdk17u/jdk-17.0.6-ga,src/java.base/share/classes/java/util/IllegalFormatConversionException.java
@@ -2441,6 +2441,7 @@
 ojluni/src/test/java/util/HashMap/WhiteBoxResizeTest.java,jdk17u/jdk-17.0.6-ga,test/jdk/java/util/HashMap/WhiteBoxResizeTest.java
 ojluni/src/test/java/util/HashSet/Serialization.java,jdk17u/jdk-17.0.6-ga,test/jdk/java/util/HashSet/Serialization.java
 ojluni/src/test/java/util/HexFormat/HexFormatTest.java,jdk17u/jdk-17.0.6-ga,test/jdk/java/util/HexFormat/HexFormatTest.java
+ojluni/src/test/java/util/IdentityHashMap/Basic.java,jdk21u/jdk-21.0.2-ga,test/jdk/java/util/IdentityHashMap/Basic.java
 ojluni/src/test/java/util/IdentityHashMap/Capacity.java,jdk17u/jdk-17.0.6-ga,test/jdk/java/util/IdentityHashMap/Capacity.java
 ojluni/src/test/java/util/IdentityHashMap/DistinctEntrySetElements.java,jdk17u/jdk-17.0.6-ga,test/jdk/java/util/IdentityHashMap/DistinctEntrySetElements.java
 ojluni/src/test/java/util/IdentityHashMap/EntrySetIteratorRemoveInvalidatesEntry.java,jdk17u/jdk-17.0.6-ga,test/jdk/java/util/IdentityHashMap/EntrySetIteratorRemoveInvalidatesEntry.java
diff --git a/api/current.txt b/api/current.txt
index 44f27db..116db29 100644
--- a/api/current.txt
+++ b/api/current.txt
@@ -14053,6 +14053,8 @@
     method public Object clone();
     method public java.util.Set<java.util.Map.Entry<K,V>> entrySet();
     method public void forEach(java.util.function.BiConsumer<? super K,? super V>);
+    method @FlaggedApi("com.android.libcore.openjdk_21_v1_apis") public boolean remove(Object, Object);
+    method @FlaggedApi("com.android.libcore.openjdk_21_v1_apis") public boolean replace(K, V, V);
     method public void replaceAll(java.util.function.BiFunction<? super K,? super V,? extends V>);
   }
 
diff --git a/ojluni/annotations/flagged_api/java/util/IdentityHashMap.annotated.java b/ojluni/annotations/flagged_api/java/util/IdentityHashMap.annotated.java
new file mode 100644
index 0000000..e1bf621
--- /dev/null
+++ b/ojluni/annotations/flagged_api/java/util/IdentityHashMap.annotated.java
@@ -0,0 +1,78 @@
+/*
+ * Copyright (c) 2000, 2022, 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 java.util;
+
+@SuppressWarnings({"unchecked", "deprecation", "all"})
+public class IdentityHashMap<K, V> extends java.util.AbstractMap<K,V> implements java.lang.Cloneable, java.util.Map<K,V>, java.io.Serializable {
+
+public IdentityHashMap() { throw new RuntimeException("Stub!"); }
+
+public IdentityHashMap(int expectedMaxSize) { throw new RuntimeException("Stub!"); }
+
+public IdentityHashMap(java.util.Map<? extends K,? extends V> m) { throw new RuntimeException("Stub!"); }
+
+public int size() { throw new RuntimeException("Stub!"); }
+
+public boolean isEmpty() { throw new RuntimeException("Stub!"); }
+
+public V get(java.lang.Object key) { throw new RuntimeException("Stub!"); }
+
+public boolean containsKey(java.lang.Object key) { throw new RuntimeException("Stub!"); }
+
+public boolean containsValue(java.lang.Object value) { throw new RuntimeException("Stub!"); }
+
+public V put(K key, V value) { throw new RuntimeException("Stub!"); }
+
+public void putAll(java.util.Map<? extends K,? extends V> m) { throw new RuntimeException("Stub!"); }
+
+public V remove(java.lang.Object key) { throw new RuntimeException("Stub!"); }
+
+public void clear() { throw new RuntimeException("Stub!"); }
+
+public boolean equals(java.lang.Object o) { throw new RuntimeException("Stub!"); }
+
+public int hashCode() { throw new RuntimeException("Stub!"); }
+
+public java.lang.Object clone() { throw new RuntimeException("Stub!"); }
+
+public java.util.Set<K> keySet() { throw new RuntimeException("Stub!"); }
+
+public java.util.Collection<V> values() { throw new RuntimeException("Stub!"); }
+
+public java.util.Set<java.util.Map.Entry<K,V>> entrySet() { throw new RuntimeException("Stub!"); }
+
+public void forEach(java.util.function.BiConsumer<? super K,? super V> action) { throw new RuntimeException("Stub!"); }
+
+public void replaceAll(java.util.function.BiFunction<? super K,? super V,? extends V> function) { throw new RuntimeException("Stub!"); }
+
+@android.annotation.FlaggedApi(com.android.libcore.Flags.FLAG_OPENJDK_21_V1_APIS)
+public boolean remove(java.lang.Object key, java.lang.Object value) { throw new RuntimeException("Stub!"); }
+
+@android.annotation.FlaggedApi(com.android.libcore.Flags.FLAG_OPENJDK_21_V1_APIS)
+public boolean replace(K key, V oldValue, V newValue) { throw new RuntimeException("Stub!"); }
+}
+
diff --git a/ojluni/src/main/java/java/util/IdentityHashMap.java b/ojluni/src/main/java/java/util/IdentityHashMap.java
index 4795c30..77f06fb 100644
--- a/ojluni/src/main/java/java/util/IdentityHashMap.java
+++ b/ojluni/src/main/java/java/util/IdentityHashMap.java
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2000, 2021, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2000, 2022, 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
@@ -49,6 +49,10 @@
  * designed for use only in the rare cases wherein reference-equality
  * semantics are required.</b>
  *
+ * <p>The view collections of this map also have reference-equality semantics
+ * for their elements. See the {@link keySet() keySet}, {@link values() values},
+ * and {@link entrySet() entrySet} methods for further information.
+ *
  * <p>A typical use of this class is <i>topology-preserving object graph
  * transformations</i>, such as serialization or deep-copying.  To perform such
  * a transformation, a program must maintain a "node table" that keeps track
@@ -130,6 +134,9 @@
  * and operation mixes, this class will yield better performance than
  * {@link HashMap}, which uses <i>chaining</i> rather than linear-probing.
  *
+ * @param <K> the type of keys maintained by this map
+ * @param <V> the type of mapped values
+ *
  * @see     System#identityHashCode(Object)
  * @see     Object#hashCode()
  * @see     Collection
@@ -343,7 +350,8 @@
 
     /**
      * Tests whether the specified object reference is a key in this identity
-     * hash map.
+     * hash map. Returns {@code true} if and only if this map contains a mapping
+     * with key {@code k} such that {@code (key == k)}.
      *
      * @param   key   possible key
      * @return  {@code true} if the specified object reference is a key
@@ -367,7 +375,8 @@
 
     /**
      * Tests whether the specified object reference is a value in this identity
-     * hash map.
+     * hash map. Returns {@code true} if and only if this map contains a mapping
+     * with value {@code v} such that {@code (value == v)}.
      *
      * @param value value whose presence in this map is to be tested
      * @return {@code true} if this map maps one or more keys to the
@@ -408,8 +417,9 @@
 
     /**
      * Associates the specified value with the specified key in this identity
-     * hash map.  If the map previously contained a mapping for the key, the
-     * old value is replaced.
+     * hash map. If this map already {@link containsKey(Object) contains}
+     * a mapping for the key, the old value is replaced, otherwise, a new mapping
+     * is inserted into this map.
      *
      * @param key the key with which the specified value is to be associated
      * @param value the value to be associated with the specified key
@@ -494,8 +504,10 @@
 
     /**
      * Copies all of the mappings from the specified map to this map.
-     * These mappings will replace any mappings that this map had for
-     * any of the keys currently in the specified map.
+     * For each mapping in the specified map, if this map already
+     * {@link containsKey(Object) contains} a mapping for the key,
+     * its value is replaced with the value from the specified map;
+     * otherwise, a new mapping is inserted into this map.
      *
      * @param m mappings to be stored in this map
      * @throws NullPointerException if the specified map is null
@@ -513,6 +525,8 @@
 
     /**
      * Removes the mapping for this key from this map if present.
+     * The mapping is removed if and only if the mapping has a key
+     * {@code k} such that (key == k).
      *
      * @param key key whose mapping is to be removed from the map
      * @return the previous value associated with {@code key}, or
@@ -629,7 +643,9 @@
      * {@code true} if the given object is also a map and the two maps
      * represent identical object-reference mappings.  More formally, this
      * map is equal to another map {@code m} if and only if
-     * {@code this.entrySet().equals(m.entrySet())}.
+     * {@code this.entrySet().equals(m.entrySet())}. See the
+     * {@link entrySet() entrySet} method for the specification of equality
+     * of this map's entries.
      *
      * <p><b>Owing to the reference-equality-based semantics of this map it is
      * possible that the symmetry and transitivity requirements of the
@@ -664,8 +680,11 @@
 
     /**
      * Returns the hash code value for this map.  The hash code of a map is
-     * defined to be the sum of the hash codes of each entry in the map's
-     * {@code entrySet()} view.  This ensures that {@code m1.equals(m2)}
+     * defined to be the sum of the hash codes of each entry of this map.
+     * See the {@link entrySet() entrySet} method for a specification of the
+     * hash code of this map's entries.
+     *
+     * <p>This specification ensures that {@code m1.equals(m2)}
      * implies that {@code m1.hashCode()==m2.hashCode()} for any two
      * {@code IdentityHashMap} instances {@code m1} and {@code m2}, as
      * required by the general contract of {@link Object#hashCode}.
@@ -1159,7 +1178,9 @@
      * e.getValue()==o.getValue()}.  To accommodate these equals
      * semantics, the {@code hashCode} method returns
      * {@code System.identityHashCode(e.getKey()) ^
-     * System.identityHashCode(e.getValue())}.
+     * System.identityHashCode(e.getValue())}. (While the keys and values
+     * are compared using reference equality, the {@code Map.Entry}
+     * objects themselves are not.)
      *
      * <p><b>Owing to the reference-equality-based semantics of the
      * {@code Map.Entry} instances in the set returned by this method,
@@ -1380,6 +1401,50 @@
     }
 
     /**
+     * {@inheritDoc}
+     *
+     * <p>More formally, if this map contains a mapping from a key
+     * {@code k} to a value {@code v} such that {@code (key == k)}
+     * and {@code (value == v)}, then this method removes the mapping
+     * for this key and returns {@code true}; otherwise it returns
+     * {@code false}.
+     */
+    @Override
+    public boolean remove(Object key, Object value) {
+        return removeMapping(key, value);
+    }
+
+    /**
+     * {@inheritDoc}
+     *
+     * <p>More formally, if this map contains a mapping from a key
+     * {@code k} to a value {@code v} such that {@code (key == k)}
+     * and {@code (oldValue == v)}, then this method associates
+     * {@code k} with {@code newValue} and returns {@code true};
+     * otherwise it returns {@code false}.
+     */
+    @Override
+    public boolean replace(K key, V oldValue, V newValue) {
+        Object k = maskNull(key);
+        Object[] tab = table;
+        int len = tab.length;
+        int i = hash(k, len);
+
+        while (true) {
+            Object item = tab[i];
+            if (item == k) {
+                if (tab[i + 1] != oldValue)
+                    return false;
+                tab[i + 1] = newValue;
+                return true;
+            }
+            if (item == null)
+                return false;
+            i = nextKeyIndex(i, len);
+        }
+    }
+
+    /**
      * Similar form as array-based Spliterators, but skips blank elements,
      * and guestimates size as decreasing by half per split.
      */
diff --git a/ojluni/src/test/java/util/IdentityHashMap/Basic.java b/ojluni/src/test/java/util/IdentityHashMap/Basic.java
new file mode 100644
index 0000000..659ca7d
--- /dev/null
+++ b/ojluni/src/test/java/util/IdentityHashMap/Basic.java
@@ -0,0 +1,769 @@
+/*
+ * Copyright (c) 2022, 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.
+ */
+
+package test.java.util.IdentityHashMap;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.List;
+import java.util.Map;
+import java.util.IdentityHashMap;
+import java.util.Set;
+import java.util.function.BiPredicate;
+import java.util.stream.IntStream;
+import org.testng.annotations.BeforeMethod;
+import org.testng.annotations.Test;
+
+import static java.util.Map.entry;
+import static org.testng.Assert.*;
+
+/*
+ * @test
+ * @bug 8285295 8178355
+ * @summary Basic tests for IdentityHashMap
+ * @run testng Basic
+ */
+
+// NOTE: avoid using TestNG's assertEquals/assertNotEquals directly on two IDHM instances,
+// as its logic for testing collections equality is suspect. Use checkEntries() to assert
+// that a map's entrySet contains exactly the expected mappings. There are no guarantees about
+// the identities of Map.Entry instances obtained from the entrySet; however, the keys and
+// values they contain are guaranteed to have the right identity.
+
+// TODO add tests using null keys and values
+// TODO deeper testing of view collections including iterators, equals, contains, etc.
+// TODO Map.Entry::setValue
+
+public class Basic {
+    /*
+     * Helpers
+     */
+
+    record Box(int i) {
+        Box(Box other) {
+            this(other.i());
+        }
+    }
+
+    // Checks that a collection contains exactly the given elements and no others, using the
+    // provided predicate for equivalence. Checking is performed both using contains() on the
+    // collection and by simple array searching. The latter is O(N^2) so is suitable only for
+    // small arrays. No two of the given elements can be equivalent according to the predicate.
+
+    // TODO: read out the elements using iterator and stream and check them too
+
+    @SafeVarargs
+    private <E> void checkContents(Collection<E> c, BiPredicate<E,E> p, E... given) {
+        @SuppressWarnings("unchecked")
+        E[] contents = (E[]) c.toArray();
+
+        assertEquals(c.size(), given.length);
+        assertEquals(contents.length, given.length);
+        final int LEN = given.length;
+
+        for (E e : given) {
+            assertTrue(c.contains(e));
+        }
+
+        // Fill indexes array with position of a given element in the contents array,
+        // or -1 if the given element cannot be found.
+
+        int[] indexes = new int[LEN];
+
+        outer:
+        for (int i = 0; i < LEN; i++) {
+            for (int j = 0; j < LEN; j++) {
+                if (p.test(given[i], contents[j])) {
+                    indexes[i] = j;
+                    continue outer;
+                }
+            }
+            indexes[i] = -1;
+        }
+
+        // If every given element matches a distinct element in the contents array,
+        // the sorted indexes array will be the sequence [0..LEN-1].
+
+        Arrays.sort(indexes);
+        assertEquals(indexes, IntStream.range(0, LEN).toArray());
+    }
+
+    // Checks that the collection contains the given boxes, by identity.
+    private void checkElements(Collection<Box> c, Box... given) {
+        checkContents(c, (b1, b2) -> b1 == b2, given);
+    }
+
+    // Checks that the collection contains entries that have identical keys and values.
+    // The entries themselves are not checked for identity.
+    @SafeVarargs
+    private void checkEntries(Collection<Map.Entry<Box, Box>> c, Map.Entry<Box, Box>... given) {
+        checkContents(c, (e1, e2) -> e1.getKey() == e2.getKey() && e1.getValue() == e2.getValue(), given);
+    }
+
+    /*
+     * Setup
+     */
+
+    final Box k1a = new Box(17);
+    final Box k1b = new Box(17); // equals but != k1a
+    final Box k2  = new Box(42);
+
+    final Box v1a = new Box(30);
+    final Box v1b = new Box(30); // equals but != v1a
+    final Box v2  = new Box(99);
+
+    IdentityHashMap<Box, Box> map;
+    IdentityHashMap<Box, Box> map2;
+
+    @BeforeMethod
+    public void setup() {
+        map = new IdentityHashMap<>();
+        map.put(k1a, v1a);
+        map.put(k1b, v1b);
+        map.put(k2,  v2);
+
+        map2 = new IdentityHashMap<>();
+        map2.put(k1a, v1a);
+        map2.put(k1b, v1b);
+        map2.put(k2,  v2);
+    }
+
+    /*
+     * Tests
+     */
+
+    // containsKey
+    // containsValue
+    // size
+    @Test
+    public void testSizeContainsKeyValue() {
+        assertEquals(map.size(), 3);
+
+        assertTrue(map.containsKey(k1a));
+        assertTrue(map.containsKey(k1b));
+        assertTrue(map.containsKey(k2));
+        assertFalse(map.containsKey(new Box(k1a)));
+
+        assertTrue(map.containsValue(v1a));
+        assertTrue(map.containsValue(v1b));
+        assertFalse(map.containsValue(new Box(v1a)));
+        assertTrue(map.containsValue(v2));
+    }
+
+    // get
+    @Test
+    public void testGet() {
+        assertSame(map.get(k1a), v1a);
+        assertSame(map.get(k1b), v1b);
+        assertSame(map.get(k2), v2);
+        assertNull(map.get(new Box(k1a)));
+    }
+
+    // getOrDefault
+    @Test
+    public void testGetOrDefault() {
+        Box other = new Box(22);
+
+        assertSame(map.getOrDefault(k1a, other), v1a);
+        assertSame(map.getOrDefault(k1b, other), v1b);
+        assertSame(map.getOrDefault(new Box(k1a), other), other);
+        assertSame(map.getOrDefault(k2, other), v2);
+    }
+
+    // clear
+    // isEmpty
+    @Test
+    public void testClearEmpty() {
+        assertFalse(map.isEmpty());
+        map.clear();
+        assertTrue(map.isEmpty());
+    }
+
+    // hashCode
+    @Test
+    public void testHashCode() {
+        int expected = (System.identityHashCode(k1a) ^ System.identityHashCode(v1a)) +
+                       (System.identityHashCode(k1b) ^ System.identityHashCode(v1b)) +
+                       (System.identityHashCode(k2)  ^ System.identityHashCode(v2));
+        assertEquals(map.hashCode(), expected);
+        assertEquals(map.entrySet().hashCode(), expected);
+    }
+
+    // equals
+    @Test
+    public void testEquals() {
+        assertTrue(map.equals(map));
+        assertTrue(map.equals(map2));
+        assertTrue(map2.equals(map));
+
+        assertTrue(map.keySet().equals(map.keySet()));
+        assertTrue(map.keySet().equals(map2.keySet()));
+        assertTrue(map2.keySet().equals(map.keySet()));
+
+        assertTrue(map.entrySet().equals(map.entrySet()));
+        assertTrue(map.entrySet().equals(map2.entrySet()));
+        assertTrue(map2.entrySet().equals(map.entrySet()));
+    }
+
+    // equals
+    @Test
+    public void testEqualsDifferentKey() {
+        map2.remove(k1a);
+        map2.put(new Box(k1a), v1a);
+
+        assertFalse(map.equals(map2));
+        assertFalse(map2.equals(map));
+
+        assertFalse(map.keySet().equals(map2.keySet()));
+        assertFalse(map2.keySet().equals(map.keySet()));
+
+        assertFalse(map.entrySet().equals(map2.entrySet()));
+        assertFalse(map2.entrySet().equals(map.entrySet()));
+    }
+
+    // equals
+    @Test
+    public void testEqualsDifferentValue() {
+        map2.put(k1a, new Box(v1a));
+
+        assertFalse(map.equals(map2));
+        assertFalse(map2.equals(map));
+
+        assertTrue(map.keySet().equals(map2.keySet()));
+        assertTrue(map2.keySet().equals(map.keySet()));
+
+        assertFalse(map.entrySet().equals(map2.entrySet()));
+        assertFalse(map2.entrySet().equals(map.entrySet()));
+    }
+
+    // equals
+    @Test
+    public void testEqualsNewMapping() {
+        map.put(new Box(k1a), new Box(v1a));
+
+        assertFalse(map.equals(map2));
+        assertFalse(map2.equals(map));
+
+        assertFalse(map.keySet().equals(map2.keySet()));
+        assertFalse(map2.keySet().equals(map.keySet()));
+
+        assertFalse(map.entrySet().equals(map2.entrySet()));
+        assertFalse(map2.entrySet().equals(map.entrySet()));
+    }
+
+    // equals
+    @Test
+    public void testEqualsMissingMapping() {
+        var tmp = new IdentityHashMap<Box, Box>();
+        tmp.put(k1a, v1a);
+        tmp.put(k1b, v1b);
+
+        assertFalse(map.equals(tmp));
+        assertFalse(tmp.equals(map));
+
+        assertFalse(map.keySet().equals(tmp.keySet()));
+        assertFalse(tmp.keySet().equals(map.keySet()));
+
+        assertFalse(map.entrySet().equals(tmp.entrySet()));
+        assertFalse(tmp.entrySet().equals(map.entrySet()));
+    }
+
+    // keySet equals, contains
+    @Test
+    public void testKeySet() {
+        Set<Box> keySet = map.keySet();
+
+        checkElements(keySet, k1a, k1b, k2);
+        assertFalse(keySet.contains(new Box(k1a)));
+        assertTrue(map.keySet().equals(map2.keySet()));
+        assertTrue(map2.keySet().equals(map.keySet()));
+    }
+
+    // keySet remove
+    @Test
+    public void testKeySetNoRemove() {
+        Set<Box> keySet = map.keySet();
+        boolean r = keySet.remove(new Box(k1a));
+
+        assertFalse(r);
+        checkElements(keySet, k1a, k1b, k2);
+        checkEntries(map.entrySet(), entry(k1a, v1a),
+                                     entry(k1b, v1b),
+                                     entry(k2, v2));
+        assertTrue(map.keySet().equals(map2.keySet()));
+        assertTrue(map2.keySet().equals(map.keySet()));
+    }
+
+    // keySet remove
+    @Test
+    public void testKeySetRemove() {
+        Set<Box> keySet = map.keySet();
+        boolean r = keySet.remove(k1a);
+
+        assertTrue(r);
+        checkElements(keySet, k1b, k2);
+        checkEntries(map.entrySet(), entry(k1b, v1b),
+                                     entry(k2, v2));
+        assertFalse(map.keySet().equals(map2.keySet()));
+        assertFalse(map2.keySet().equals(map.keySet()));
+    }
+
+    // values
+    @Test
+    public void testValues() {
+        Collection<Box> values = map.values();
+        checkElements(values, v1a, v1b, v2);
+        assertFalse(values.contains(new Box(v1a)));
+    }
+
+    // values remove
+    @Test
+    public void testValuesNoRemove() {
+        Collection<Box> values = map.values();
+        boolean r = values.remove(new Box(v1a));
+
+        assertFalse(r);
+        checkElements(values, v1a, v1b, v2);
+        checkEntries(map.entrySet(), entry(k1a, v1a),
+                                     entry(k1b, v1b),
+                                     entry(k2, v2));
+    }
+
+    // values remove
+    @Test
+    public void testValuesRemove() {
+        Collection<Box> values = map.values();
+        boolean r = values.remove(v1a);
+
+        assertTrue(r);
+        checkElements(values, v1b, v2);
+        checkEntries(map.entrySet(), entry(k1b, v1b),
+                                     entry(k2, v2));
+    }
+
+    // entrySet equals, contains
+    @Test
+    public void testEntrySet() {
+        Set<Map.Entry<Box,Box>> entrySet = map.entrySet();
+
+        assertFalse(entrySet.contains(entry(new Box(k1a), v1a)));
+        assertFalse(entrySet.contains(entry(k1b, new Box(v1b))));
+        assertFalse(entrySet.contains(entry(new Box(k2), new Box(v2))));
+        assertTrue(map.entrySet().equals(map2.entrySet()));
+        checkEntries(entrySet, entry(k1a, v1a),
+                               entry(k1b, v1b),
+                               entry(k2, v2));
+    }
+
+    // entrySet remove
+    @Test
+    public void testEntrySetNoRemove() {
+        Set<Map.Entry<Box, Box>> entrySet = map.entrySet();
+        boolean r1 = entrySet.remove(entry(new Box(k1a), v1a));
+        boolean r2 = entrySet.remove(entry(k1a, new Box(v1a)));
+
+        assertFalse(r1);
+        assertFalse(r2);
+        assertTrue(entrySet.equals(map2.entrySet()));
+        checkEntries(entrySet, entry(k1a, v1a),
+                               entry(k1b, v1b),
+                               entry(k2, v2));
+    }
+
+    // entrySet remove
+    @Test
+    public void testEntrySetRemove() {
+        Set<Map.Entry<Box, Box>> entrySet = map.entrySet();
+        boolean r = entrySet.remove(Map.entry(k1a, v1a));
+
+        assertTrue(r);
+        assertFalse(entrySet.equals(map2.entrySet()));
+        assertFalse(map.entrySet().equals(map2.entrySet()));
+        checkEntries(entrySet, entry(k1b, v1b),
+                               entry(k2, v2));
+        checkEntries(map.entrySet(), entry(k1b, v1b),
+                                     entry(k2, v2));
+    }
+
+    // put
+    @Test
+    public void testPutNew() {
+        Box newKey = new Box(k1a);
+        Box newVal = new Box(v1a);
+        Box r = map.put(newKey, newVal);
+
+        assertNull(r);
+        checkEntries(map.entrySet(), entry(k1a, v1a),
+                                     entry(k1b, v1b),
+                                     entry(k2, v2),
+                                     entry(newKey, newVal));
+    }
+
+    // put
+    @Test
+    public void testPutOverwrite() {
+        Box newVal = new Box(v1a);
+        Box r = map.put(k1a, newVal);
+
+        assertSame(r, v1a);
+        checkEntries(map.entrySet(), entry(k1a, newVal),
+                                     entry(k1b, v1b),
+                                     entry(k2, v2));
+    }
+
+    // putAll
+    @Test
+    public void testPutAll() {
+        Box newKey  = new Box(k1a);
+        Box newVal  = new Box(v1a);
+        Box newValB = new Box(v1b);
+        var argMap = new IdentityHashMap<Box, Box>();
+        argMap.put(newKey, newVal); // new entry
+        argMap.put(k1b, newValB);   // will overwrite value
+        map.putAll(argMap);
+
+        checkEntries(map.entrySet(), entry(k1a, v1a),
+                                     entry(k1b, newValB),
+                                     entry(k2, v2),
+                                     entry(newKey, newVal));
+    }
+
+    // putIfAbsent
+    @Test
+    public void testPutIfAbsentNoop() {
+        Box r = map.putIfAbsent(k1a, new Box(v1a)); // no-op
+
+        assertSame(r, v1a);
+        checkEntries(map.entrySet(), entry(k1a, v1a),
+                                     entry(k1b, v1b),
+                                     entry(k2, v2));
+    }
+
+    // putIfAbsent
+    @Test
+    public void testPutIfAbsentAddsNew() {
+        Box newKey = new Box(k1a);
+        Box newVal = new Box(v1a);
+        Box r = map.putIfAbsent(newKey, newVal); // adds new entry
+
+        assertNull(r);
+        checkEntries(map.entrySet(), entry(k1a, v1a),
+                                     entry(k1b, v1b),
+                                     entry(k2, v2),
+                                     entry(newKey, newVal));
+    }
+
+    // remove(Object)
+    @Test
+    public void testRemoveKey() {
+        Box r = map.remove(k1b);
+
+        assertSame(r, v1b);
+        checkEntries(map.entrySet(), entry(k1a, v1a),
+                                     entry(k2, v2));
+    }
+
+    // remove(Object, Object) absent key, absent value
+    @Test
+    public void testRemoveAA() {
+        Box k1c = new Box(k1a);
+        Box v1c = new Box(v1a);
+        assertFalse(map.remove(k1c, v1c));
+        checkEntries(map.entrySet(),
+                entry(k1a, v1a),
+                entry(k1b, v1b),
+                entry(k2, v2));
+    }
+
+    // remove(Object, Object) absent key, present value
+    @Test
+    public void testRemoveAV() {
+        Box k1c = new Box(k1a);
+        assertFalse(map.remove(k1c, v1a));
+        checkEntries(map.entrySet(),
+                     entry(k1a, v1a),
+                     entry(k1b, v1b),
+                     entry(k2, v2));
+    }
+
+    // remove(Object, Object) present key, absent value
+    @Test
+    public void testRemoveKA() {
+        Box v1c = new Box(v1a);
+        assertFalse(map.remove(k1a, v1c));
+        checkEntries(map.entrySet(),
+                entry(k1a, v1a),
+                entry(k1b, v1b),
+                entry(k2, v2));
+    }
+
+    // remove(Object, Object) present key, present value
+    @Test
+    public void testRemoveKV() {
+        assertTrue(map.remove(k1a, v1a));
+        checkEntries(map.entrySet(),
+                entry(k1b, v1b),
+                entry(k2, v2));
+    }
+
+    // replace(K, V, V) absent key, absent oldValue
+    @Test
+    public void testReplaceAA() {
+        Box k1c = new Box(k1a);
+        Box v1c = new Box(v1a);
+        Box newVal = new Box(v2);
+        assertFalse(map.replace(k1c, v1c, newVal));
+        checkEntries(map.entrySet(),
+                entry(k1a, v1a),
+                entry(k1b, v1b),
+                entry(k2, v2));
+    }
+
+    // replace(K, V, V) absent key, present oldValue
+    @Test
+    public void testReplaceAV() {
+        Box k1c = new Box(k1a);
+        Box newVal = new Box(v2);
+        assertFalse(map.replace(k1c, v1a, newVal));
+        checkEntries(map.entrySet(),
+                entry(k1a, v1a),
+                entry(k1b, v1b),
+                entry(k2, v2));
+    }
+
+    // replace(K, V, V) present key, absent oldValue
+    @Test
+    public void testReplaceKA() {
+        Box v1c = new Box(v1a);
+        Box newVal = new Box(v2);
+        assertFalse(map.replace(k1a, v1c, newVal));
+        checkEntries(map.entrySet(),
+                entry(k1a, v1a),
+                entry(k1b, v1b),
+                entry(k2, v2));
+    }
+
+    // replace(K, V, V) present key, present oldValue
+    @Test
+    public void testReplaceKV() {
+        Box newVal = new Box(v2);
+        assertTrue(map.replace(k1a, v1a, newVal));
+        checkEntries(map.entrySet(),
+                entry(k1a, newVal),
+                entry(k1b, v1b),
+                entry(k2, v2));
+    }
+
+    // AN: key absent, remappingFunction returns null
+    @Test
+    public void testComputeAN() {
+        Box newKey = new Box(k1a);
+        Box r = map.compute(newKey, (k, v) -> null);
+
+        assertNull(r);
+        checkEntries(map.entrySet(), entry(k1a, v1a),
+                                     entry(k1b, v1b),
+                                     entry(k2, v2));
+    }
+
+    // AV: key absent, remappingFunction returns non-null value
+    @Test
+    public void testComputeAV() {
+        Box newKey = new Box(k1a);
+        Box newVal = new Box(v1a);
+        Box r = map.compute(newKey, (k, v) -> newVal);
+
+        assertSame(r, newVal);
+        checkEntries(map.entrySet(), entry(k1a, v1a),
+                                     entry(k1b, v1b),
+                                     entry(k2, v2),
+                                     entry(newKey, newVal));
+    }
+
+    // PN: key present, remappingFunction returns null
+    @Test
+    public void testComputePN() {
+        Box r = map.compute(k1a, (k, v) -> null);
+
+        assertNull(r);
+        checkEntries(map.entrySet(), entry(k1b, v1b),
+                                     entry(k2, v2));
+    }
+
+    // PV: key present, remappingFunction returns non-null value
+    @Test
+    public void testComputePV() {
+        Box newVal = new Box(v1a);
+        Box r = map.compute(k1a, (k, v) -> newVal);
+
+        assertSame(r, newVal);
+        checkEntries(map.entrySet(), entry(k1a, newVal),
+                                     entry(k1b, v1b),
+                                     entry(k2, v2));
+    }
+
+    // computeIfAbsent
+    @Test
+    public void testComputeIfAbsentIsCalled() {
+        boolean[] called = new boolean[1];
+        Box newKey = new Box(k1a);
+        Box newVal = new Box(v1a);
+        Box r = map.computeIfAbsent(newKey, k -> { called[0] = true; return newVal; });
+
+        assertSame(r, newVal);
+        assertTrue(called[0]);
+        checkEntries(map.entrySet(), entry(k1a, v1a),
+                                     entry(k1b, v1b),
+                                     entry(k2, v2),
+                                     entry(newKey, newVal));
+    }
+
+    // computeIfAbsent
+    @Test
+    public void testComputeIfAbsentNotCalled() {
+        boolean[] called = new boolean[1];
+        Box r = map.computeIfAbsent(k1a, k -> { called[0] = true; return null; });
+
+        assertSame(r, v1a);
+        assertFalse(called[0]);
+        checkEntries(map.entrySet(), entry(k1a, v1a),
+                                     entry(k1b, v1b),
+                                     entry(k2, v2));
+    }
+
+    // computeIfAbsent
+    @Test
+    public void testComputeIfAbsentNullReturn() {
+        boolean[] called = new boolean[1];
+        Box newKey = new Box(k1a);
+        Box r = map.computeIfAbsent(newKey, k -> { called[0] = true; return null; });
+
+        assertNull(r);
+        assertTrue(called[0]);
+        checkEntries(map.entrySet(), entry(k1a, v1a),
+                                     entry(k1b, v1b),
+                                     entry(k2, v2));
+    }
+
+    // computeIfPresent
+    @Test
+    public void testComputeIfPresentIsCalled() {
+        boolean[] called = new boolean[1];
+        Box newVal = new Box(v1a);
+        Box r = map.computeIfPresent(k1a, (k, v) -> { called[0] = true; return newVal; });
+
+        assertSame(r, newVal);
+        assertTrue(called[0]);
+        checkEntries(map.entrySet(), entry(k1a, newVal),
+                                     entry(k1b, v1b),
+                                     entry(k2, v2));
+    }
+
+    // computeIfPresent
+    @Test
+    public void testComputeIfPresentNotCalled() {
+        boolean[] called = new boolean[1];
+        Box r = map.computeIfPresent(new Box(k1a), (k, v) -> { called[0] = true; return null; });
+
+        assertNull(r);
+        assertFalse(called[0]);
+        checkEntries(map.entrySet(), entry(k1a, v1a),
+                                     entry(k1b, v1b),
+                                     entry(k2, v2));
+    }
+
+    // computeIfPresent
+    @Test
+    public void testComputeIfPresentNullReturn() {
+        boolean[] called = new boolean[1];
+        Box r = map.computeIfPresent(k1a, (k, v) -> { called[0] = true; return null; });
+
+        assertNull(r);
+        assertTrue(called[0]);
+        checkEntries(map.entrySet(), entry(k1b, v1b),
+                                     entry(k2, v2));
+    }
+
+    // merge
+    @Test
+    public void testMergeAbsent() {
+        boolean[] called = new boolean[1];
+        Box newKey = new Box(k1a);
+        Box newVal = new Box(v1a);
+        Box r = map.merge(newKey, newVal, (v1, v2) -> { called[0] = true; return newVal; });
+
+        assertSame(r, newVal);
+        assertFalse(called[0]);
+        checkEntries(map.entrySet(), entry(k1a, v1a),
+                                     entry(k1b, v1b),
+                                     entry(k2, v2),
+                                     entry(newKey, newVal));
+    }
+
+    // merge
+    @Test
+    public void testMergePresent() {
+        boolean[] called = new boolean[1];
+        Box val2 = new Box(47);
+        Box[] mergedVal = new Box[1];
+        Box r = map.merge(k1a, val2, (v1, v2) -> {
+            called[0] = true;
+            mergedVal[0] = new Box(v1.i + v2.i);
+            return mergedVal[0];
+        });
+
+        assertSame(r, mergedVal[0]);
+        assertTrue(called[0]);
+        checkEntries(map.entrySet(), entry(k1a, mergedVal[0]),
+                                     entry(k1b, v1b),
+                                     entry(k2, v2));
+    }
+
+    // forEach
+    @Test
+    public void testForEach() {
+        @SuppressWarnings("unchecked")
+        List<Map.Entry<Box, Box>> entries = new ArrayList<>();
+        map.forEach((k, v) -> entries.add(entry(k, v)));
+        checkEntries(entries, entry(k1a, v1a),
+                              entry(k1b, v1b),
+                              entry(k2, v2));
+    }
+
+    // replaceAll
+    @Test
+    public void testReplaceAll() {
+        List<Map.Entry<Box, Box>> replacements = new ArrayList<>();
+
+        map.replaceAll((k, v) -> {
+            Box v1 = new Box(v);
+            replacements.add(entry(k, v1));
+            return v1;
+        });
+
+        @SuppressWarnings("unchecked")
+        var replacementArray = (Map.Entry<Box, Box>[]) replacements.toArray(Map.Entry[]::new);
+        checkEntries(map.entrySet(), replacementArray);
+    }
+}