diff options
Diffstat (limited to 'src/library')
4 files changed, 15 insertions, 20 deletions
diff --git a/src/library/scala/collection/mutable/FlatHashTable.scala b/src/library/scala/collection/mutable/FlatHashTable.scala index 8c4115b1dd..0d8799282f 100644 --- a/src/library/scala/collection/mutable/FlatHashTable.scala +++ b/src/library/scala/collection/mutable/FlatHashTable.scala @@ -47,9 +47,7 @@ trait FlatHashTable[A] extends FlatHashTable.HashUtils[A] { @transient protected var seedvalue: Int = tableSizeSeed - import HashTable.powerOfTwo - - protected def capacity(expectedSize: Int) = if (expectedSize == 0) 1 else powerOfTwo(expectedSize) + protected def capacity(expectedSize: Int) = HashTable.nextPositivePowerOfTwo(expectedSize) /** The initial size of the hash table. */ diff --git a/src/library/scala/collection/mutable/HashMap.scala b/src/library/scala/collection/mutable/HashMap.scala index 11ff1f0893..de61ebb796 100644 --- a/src/library/scala/collection/mutable/HashMap.scala +++ b/src/library/scala/collection/mutable/HashMap.scala @@ -73,10 +73,18 @@ extends AbstractMap[A, B] } override def getOrElseUpdate(key: A, defaultValue: => B): B = { - val i = index(elemHashCode(key)) + val hash = elemHashCode(key) + val i = index(hash) val entry = findEntry(key, i) if (entry != null) entry.value - else addEntry(createNewEntry(key, defaultValue), i) + else { + val table0 = table + val default = defaultValue + // Avoid recomputing index if the `defaultValue()` hasn't triggered + // a table resize. + val newEntryIndex = if (table0 eq table) i else index(hash) + addEntry(createNewEntry(key, default), newEntryIndex) + } } /* inlined HashTable.findEntry0 to preserve its visibility */ diff --git a/src/library/scala/collection/mutable/HashTable.scala b/src/library/scala/collection/mutable/HashTable.scala index 445217ebef..01ec1defad 100644 --- a/src/library/scala/collection/mutable/HashTable.scala +++ b/src/library/scala/collection/mutable/HashTable.scala @@ -12,7 +12,7 @@ package scala package collection package mutable -import java.lang.Integer.rotateRight +import java.lang.Integer.{numberOfLeadingZeros, rotateRight} import scala.util.hashing.byteswap32 /** This class can be used to construct data structures that are based @@ -405,7 +405,7 @@ private[collection] object HashTable { private[collection] final def sizeForThreshold(_loadFactor: Int, thr: Int) = ((thr.toLong * loadFactorDenum) / _loadFactor).toInt - private[collection] final def capacity(expectedSize: Int) = if (expectedSize == 0) 1 else powerOfTwo(expectedSize) + private[collection] final def capacity(expectedSize: Int) = nextPositivePowerOfTwo(expectedSize) trait HashUtils[KeyType] { protected final def sizeMapBucketBitSize = 5 @@ -433,16 +433,7 @@ private[collection] object HashTable { /** * Returns a power of two >= `target`. */ - private[collection] def powerOfTwo(target: Int): Int = { - /* See http://bits.stephan-brumme.com/roundUpToNextPowerOfTwo.html */ - var c = target - 1 - c |= c >>> 1 - c |= c >>> 2 - c |= c >>> 4 - c |= c >>> 8 - c |= c >>> 16 - c + 1 - } + private[collection] def nextPositivePowerOfTwo(target: Int): Int = 1 << -numberOfLeadingZeros(target - 1) class Contents[A, Entry >: Null <: HashEntry[A, Entry]]( val loadFactor: Int, diff --git a/src/library/scala/collection/mutable/OpenHashMap.scala b/src/library/scala/collection/mutable/OpenHashMap.scala index ca08f475ce..b2e9ee27b9 100644 --- a/src/library/scala/collection/mutable/OpenHashMap.scala +++ b/src/library/scala/collection/mutable/OpenHashMap.scala @@ -31,8 +31,6 @@ object OpenHashMap { final private class OpenEntry[Key, Value](var key: Key, var hash: Int, var value: Option[Value]) - - private[mutable] def nextPositivePowerOfTwo(i : Int) = 1 << (32 - Integer.numberOfLeadingZeros(i - 1)) } /** A mutable hash map based on an open hashing scheme. The precise scheme is @@ -67,7 +65,7 @@ extends AbstractMap[Key, Value] override def empty: OpenHashMap[Key, Value] = OpenHashMap.empty[Key, Value] - private[this] val actualInitialSize = OpenHashMap.nextPositivePowerOfTwo(initialSize) + private[this] val actualInitialSize = HashTable.nextPositivePowerOfTwo(initialSize) private var mask = actualInitialSize - 1 |