diff options
| -rw-r--r-- | build.sbt | 3 | ||||
| -rw-r--r-- | build.xml | 1 | ||||
| -rw-r--r-- | src/eclipse/repl/.classpath | 2 | ||||
| -rw-r--r-- | src/eclipse/test-junit/.classpath | 1 | ||||
| -rw-r--r-- | src/library/scala/collection/mutable/OpenHashMap.scala | 83 | ||||
| -rw-r--r-- | test/junit/scala/collection/mutable/OpenHashMapTest.scala | 58 |
6 files changed, 116 insertions, 32 deletions
@@ -66,6 +66,7 @@ val scalaXmlDep = withoutScalaLang("org.scala-lang.modules" %% "scala-xml" % ver val partestDep = withoutScalaLang("org.scala-lang.modules" %% "scala-partest" % versionNumber("partest")) val junitDep = "junit" % "junit" % "4.11" val junitIntefaceDep = "com.novocode" % "junit-interface" % "0.11" % "test" +val jolDep = "org.openjdk.jol" % "jol-core" % "0.5" val asmDep = "org.scala-lang.modules" % "scala-asm" % versionProps("scala-asm.version") val jlineDep = "jline" % "jline" % versionProps("jline.version") val antDep = "org.apache.ant" % "ant" % "1.9.4" @@ -544,7 +545,7 @@ lazy val junit = project.in(file("test") / "junit") .settings(disablePublishing: _*) .settings( fork in Test := true, - libraryDependencies ++= Seq(junitDep, junitIntefaceDep), + libraryDependencies ++= Seq(junitDep, junitIntefaceDep, jolDep), testOptions += Tests.Argument(TestFrameworks.JUnit, "-a", "-v"), unmanagedSourceDirectories in Test := List(baseDirectory.value) ) @@ -277,6 +277,7 @@ TODO: <property name="junit.version" value="4.12"/> <artifact:dependencies pathId="junit.classpath" filesetId="junit.fileset"> <dependency groupId="junit" artifactId="junit" version="${junit.version}"/> + <dependency groupId="org.openjdk.jol" artifactId="jol-core" version="0.5"/> </artifact:dependencies> <copy-deps project="junit"/> diff --git a/src/eclipse/repl/.classpath b/src/eclipse/repl/.classpath index 682377adc9..141f84e6bb 100644 --- a/src/eclipse/repl/.classpath +++ b/src/eclipse/repl/.classpath @@ -2,7 +2,7 @@ <classpath> <classpathentry kind="src" path="repl"/> <classpathentry kind="var" path="SCALA_BASEDIR/build/deps/asm/scala-asm-5.0.4-scala-3.jar"/> - <classpathentry kind="var" path="SCALA_BASEDIR/build/deps/repl/jline-2.12.1.jar"/> + <classpathentry kind="var" path="SCALA_BASEDIR/build/deps/repl/jline-2.14.1.jar"/> <classpathentry combineaccessrules="false" kind="src" path="/scala-compiler"/> <classpathentry combineaccessrules="false" kind="src" path="/scala-library"/> <classpathentry kind="con" path="org.eclipse.jdt.launching.JRE_CONTAINER"/> diff --git a/src/eclipse/test-junit/.classpath b/src/eclipse/test-junit/.classpath index 3635c85112..1e1b510663 100644 --- a/src/eclipse/test-junit/.classpath +++ b/src/eclipse/test-junit/.classpath @@ -11,6 +11,7 @@ <classpathentry combineaccessrules="false" kind="src" path="/partest-extras"/> <classpathentry combineaccessrules="false" kind="src" path="/scaladoc"/> <classpathentry kind="var" path="SCALA_BASEDIR/build/deps/scaladoc/scala-xml_2.12.0-M4-1.0.5.jar"/> + <classpathentry kind="var" path="SCALA_BASEDIR/build/deps/junit/jol-core-0.5.jar"/> <classpathentry kind="con" path="org.eclipse.jdt.junit.JUNIT_CONTAINER/4"/> <classpathentry kind="output" path="build-test-junit"/> </classpath> diff --git a/src/library/scala/collection/mutable/OpenHashMap.scala b/src/library/scala/collection/mutable/OpenHashMap.scala index 5f8f5b9a0a..5bea1634c4 100644 --- a/src/library/scala/collection/mutable/OpenHashMap.scala +++ b/src/library/scala/collection/mutable/OpenHashMap.scala @@ -21,10 +21,16 @@ object OpenHashMap { def apply[K, V](elems : (K, V)*) = new OpenHashMap[K, V] ++= elems def empty[K, V] = new OpenHashMap[K, V] - final private class OpenEntry[Key, Value](val key: Key, - val hash: Int, + /** A hash table entry. + * + * The entry is occupied if and only if its `value` is a `Some`; + * deleted if and only if its `value` is `None`. + * If its `key` is not the default value of type `Key`, the entry is occupied. + * If the entry is occupied, `hash` contains the hash value of `key`. + */ + final private class OpenEntry[Key, Value](var key: Key, + var hash: Int, var value: Option[Value]) - extends HashEntry[Key, OpenEntry[Key, Value]] private[mutable] def nextPositivePowerOfTwo(i : Int) = 1 << (32 - Integer.numberOfLeadingZeros(i - 1)) } @@ -64,7 +70,14 @@ extends AbstractMap[Key, Value] private[this] val actualInitialSize = OpenHashMap.nextPositivePowerOfTwo(initialSize) private var mask = actualInitialSize - 1 - private var table : Array[Entry] = new Array[Entry](actualInitialSize) + + /** The hash table. + * + * The table's entries are initialized to `null`, indication of an empty slot. + * A slot is either deleted or occupied if and only if the entry is non-`null`. + */ + private[this] var table = new Array[Entry](actualInitialSize) + private var _size = 0 private var deleted = 0 @@ -91,42 +104,43 @@ extends AbstractMap[Key, Value] table = new Array[Entry](newSize) mask = newSize - 1 oldTable.foreach( entry => - if (entry != null && entry.value != None) addEntry(entry)) + if (entry != null && entry.value != None) + table(findIndex(entry.key, entry.hash)) = entry ) deleted = 0 } /** Return the index of the first slot in the hash table (in probe order) - * that either is empty, or is or was last occupied by the given key. - */ - private[this] def findIndex(key: Key) : Int = findIndex(key, hashOf(key)) - - /** Return the index of the first slot in the hash table (in probe order) - * that either is empty, or is or was last occupied by the given key. - * - * This method is an optimization for when the hash value is in hand. + * that is, in order of preference, either occupied by the given key, deleted, or empty. * * @param hash hash value for `key` */ private[this] def findIndex(key: Key, hash: Int): Int = { var j = hash - var index = hash & mask var perturb = index - while(table(index) != null && - !(table(index).hash == hash && - table(index).key == key)){ + + /** Index of the first slot containing a deleted entry, or -1 if none found yet. */ + var firstDeletedIndex = -1 + + var entry = table(index) + while (entry != null) { + if (entry.hash == hash && entry.key == key && entry.value != None) + return index + + if (firstDeletedIndex == -1 && entry.value == None) + firstDeletedIndex = index + j = 5 * j + 1 + perturb perturb >>= 5 index = j & mask + entry = table(index) } - index - } - private[this] def addEntry(entry: Entry) = - if (entry != null) table(findIndex(entry.key, entry.hash)) = entry + if (firstDeletedIndex == -1) index else firstDeletedIndex + } override def update(key: Key, value: Value) { - put(key, hashOf(key), value) + put(key, value) } @deprecatedOverriding("+= should not be overridden in order to maintain consistency with put.", "2.11.0") @@ -150,6 +164,8 @@ extends AbstractMap[Key, Value] } else { val res = entry.value if (entry.value == None) { + entry.key = key + entry.hash = hash size += 1 deleted -= 1 modCount += 1 @@ -159,13 +175,22 @@ extends AbstractMap[Key, Value] } } + /** Delete the hash table slot contained in the given entry. */ + @inline + private[this] def deleteSlot(entry: Entry) = { + entry.key = null.asInstanceOf[Key] + entry.hash = 0 + entry.value = None + + size -= 1 + deleted += 1 + } + override def remove(key : Key): Option[Value] = { - val index = findIndex(key) - if (table(index) != null && table(index).value != None){ - val res = table(index).value - table(index).value = None - size -= 1 - deleted += 1 + val entry = table(findIndex(key, hashOf(key))) + if (entry != null && entry.value != None) { + val res = entry.value + deleteSlot(entry) res } else None } @@ -249,7 +274,7 @@ extends AbstractMap[Key, Value] } override def retain(f : (Key, Value) => Boolean) = { - foreachUndeletedEntry(entry => if (!f(entry.key, entry.value.get)) {entry.value = None; size -= 1; deleted += 1} ) + foreachUndeletedEntry(entry => if (!f(entry.key, entry.value.get)) deleteSlot(entry)) this } 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)) + } } |