diff options
author | Performant Data LLC <performantdata@users.noreply.github.com> | 2016-04-25 16:33:04 -0700 |
---|---|---|
committer | Performant Data LLC <performantdata@users.noreply.github.com> | 2016-05-24 10:42:04 -0700 |
commit | 60f28f9e6a330e91a0f1204917301d401a6fce72 (patch) | |
tree | 8b47f18cc2703c61cd483fa6c84d6241452c03ed /src/library | |
parent | 207e32df30fd733e4dd1cb28fb8cb5c3153c21a6 (diff) | |
download | scala-60f28f9e6a330e91a0f1204917301d401a6fce72.tar.gz scala-60f28f9e6a330e91a0f1204917301d401a6fce72.tar.bz2 scala-60f28f9e6a330e91a0f1204917301d401a6fce72.zip |
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.
Diffstat (limited to 'src/library')
-rw-r--r-- | src/library/scala/collection/mutable/OpenHashMap.scala | 83 |
1 files changed, 54 insertions, 29 deletions
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 } |