diff options
-rw-r--r-- | src/library/scala/collection/mutable/OpenHashMap.scala | 19 | ||||
-rw-r--r-- | test/junit/scala/collection/mutable/OpenHashMapTest.scala | 42 |
2 files changed, 60 insertions, 1 deletions
diff --git a/src/library/scala/collection/mutable/OpenHashMap.scala b/src/library/scala/collection/mutable/OpenHashMap.scala index 24f5761cf5..5f8f5b9a0a 100644 --- a/src/library/scala/collection/mutable/OpenHashMap.scala +++ b/src/library/scala/collection/mutable/OpenHashMap.scala @@ -81,6 +81,9 @@ extends AbstractMap[Key, Value] h ^ (h >>> 7) ^ (h >>> 4) } + /** Increase the size of the table. + * Copy only the occupied slots, effectively eliminating the deleted slots. + */ private[this] def growTable() = { val oldSize = mask + 1 val newSize = 4 * oldSize @@ -92,8 +95,18 @@ extends AbstractMap[Key, Value] 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. + * + * @param hash hash value for `key` + */ private[this] def findIndex(key: Key, hash: Int): Int = { var j = hash @@ -136,7 +149,11 @@ extends AbstractMap[Key, Value] None } else { val res = entry.value - if (entry.value == None) { size += 1; modCount += 1 } + if (entry.value == None) { + size += 1 + deleted -= 1 + modCount += 1 + } entry.value = Some(value) res } diff --git a/test/junit/scala/collection/mutable/OpenHashMapTest.scala b/test/junit/scala/collection/mutable/OpenHashMapTest.scala new file mode 100644 index 0000000000..1459c14d78 --- /dev/null +++ b/test/junit/scala/collection/mutable/OpenHashMapTest.scala @@ -0,0 +1,42 @@ +package scala.collection.mutable + +import org.junit.Test +import org.junit.Assert._ +import org.junit.runner.RunWith +import org.junit.runners.JUnit4 + +/** Tests for [[OpenHashMap]]. */ +@RunWith(classOf[JUnit4]) +class OpenHashMapTest { + /** Test that an [[OpenHashMap]] correctly maintains its internal `deleted` count. */ + @Test + def maintainsDeletedCount { + val m = OpenHashMap.empty[Int, Int] + + // Reflect to get the private `deleted` field's value, which should be zero. + + /* TODO Doesn't work, due to SI-9306. + import scala.reflect.runtime.{universe => ru} + + val mirror = ru.runtimeMirror(m.getClass.getClassLoader) + val mapType = ru.typeOf[OpenHashMap[Int, Int]] + val termSym = mapType.decls + .filterNot { s => s.isMethod } + .filter { s => s.fullName.endsWith("deleted") } + .head.asTerm + + val fieldMirror = mirror.reflect(m).reflectField(termSym) + */ + // Use Java reflection instead for now. + val field = m.getClass.getDeclaredField("scala$collection$mutable$OpenHashMap$$deleted") + field.setAccessible(true) + + m.put(0, 0) + m.remove(0) + assertEquals(1, field.getInt(m)) + + m.put(0, 0) // Add an entry with the same key + // TODO assertEquals(0, fieldMirror.get.asInstanceOf[Int]) + assertEquals(0, field.getInt(m)) + } +} |