SI-9522 release key reference when deleting from OpenHashMap

This sets the key field in the hash table entry to its default value
when an entry is deleted, so as not to unexpectedly retain an object
reference, leading to a memory leak.

Also includes incidental changes to the slot location algorithm that
reduce the number of deleted entries.

1 files changed, 57 insertions, 1 deletions

diff --git a/test/junit/scala/collection/mutable/OpenHashMapTest.scala b/test/junit/scala/collection/mutable/OpenHashMapTest.scala
index 9b5c20e01a..b6cddf2101 100644
--- a/test/junit/scala/collection/mutable/OpenHashMapTest.scala
+++ b/test/junit/scala/collection/mutable/OpenHashMapTest.scala
@@ -4,6 +4,10 @@ import org.junit.Test
 import org.junit.Assert._
 import org.junit.runner.RunWith
 import org.junit.runners.JUnit4
+import org.openjdk.jol.info.GraphLayout
+import org.openjdk.jol.info.GraphWalker
+import org.openjdk.jol.info.GraphVisitor
+import org.openjdk.jol.info.GraphPathRecord
 
 /** Tests for [[OpenHashMap]]. */
 @RunWith(classOf[JUnit4])
@@ -28,7 +32,13 @@ class OpenHashMapTest {
     val fieldMirror = mirror.reflect(m).reflectField(termSym)
 		*/
     // Use Java reflection instead for now.
-    val field = m.getClass.getDeclaredField("deleted")
+    val field =
+      try {  // Name may or not be mangled, depending on what the compiler authors are doing.
+        m.getClass.getDeclaredField("scala$collection$mutable$OpenHashMap$$deleted")
+      } catch {
+        case _: NoSuchFieldException =>
+          m.getClass.getDeclaredField("deleted")
+      }
     field.setAccessible(true)
 
     m.put(0, 0)
@@ -39,4 +49,50 @@ class OpenHashMapTest {
     // TODO assertEquals(0, fieldMirror.get.asInstanceOf[Int])
     assertEquals(0, field.getInt(m))
   }
+
+  /** Test that an [[OpenHashMap]] frees references to a deleted key (SI-9522). */
+  @Test
+  def freesDeletedKey {
+    import scala.language.reflectiveCalls
+
+    class MyClass {
+      override def hashCode() = 42
+    }
+
+    val counter = new GraphVisitor() {
+      private[this] var instanceCount: Int = _
+
+      def countInstances(obj: AnyRef) = {
+        instanceCount = 0
+        val walker = new GraphWalker(obj)
+        walker.addVisitor(this)
+        walker.walk
+        instanceCount
+      }
+
+      override def visit(record: GraphPathRecord) {
+        if (record.klass() == classOf[MyClass])  instanceCount += 1
+      }
+    }
+
+    val m = OpenHashMap.empty[MyClass, Int]
+    val obj = new MyClass
+    assertEquals("Found a key instance in the map before adding one!?", 0, counter.countInstances(m))
+    m.put(obj, 0)
+    assertEquals("There should be only one key instance in the map.", 1, counter.countInstances(m))
+    m.put(obj, 1)
+    assertEquals("There should still be only one key instance in the map.", 1, counter.countInstances(m))
+    m.remove(obj)
+    assertEquals("There should be no key instance in the map.", 0, counter.countInstances(m))
+
+    val obj2 = new MyClass
+    assertEquals("The hash codes of the test objects need to match.", obj.##, obj2.##)
+    m.put(obj, 0)
+    m.put(obj2, 0)
+    assertEquals("There should be two key instances in the map.", 2, counter.countInstances(m))
+    m.remove(obj)
+    assertEquals("There should be one key instance in the map.", 1, counter.countInstances(m))
+    m.remove(obj2)
+    assertEquals("There should be no key instance in the map.", 0, counter.countInstances(m))
+  }
 }