diff options
Diffstat (limited to 'src/library/scala/collection/mutable/HashTable.scala')
| -rw-r--r-- | src/library/scala/collection/mutable/HashTable.scala | 21 |
1 files changed, 8 insertions, 13 deletions
diff --git a/src/library/scala/collection/mutable/HashTable.scala b/src/library/scala/collection/mutable/HashTable.scala index 4873aa3c3e..01ec1defad 100644 --- a/src/library/scala/collection/mutable/HashTable.scala +++ b/src/library/scala/collection/mutable/HashTable.scala @@ -367,7 +367,11 @@ trait HashTable[A, Entry >: Null <: HashEntry[A, Entry]] extends HashTable.HashU * Note: we take the most significant bits of the hashcode, not the lower ones * this is of crucial importance when populating the table in parallel */ - protected final def index(hcode: Int): Int = if (table.length == 1) 0 else improve(hcode, seedvalue) >>> numberOfLeadingZeros(table.length - 1) + protected final def index(hcode: Int): Int = { + val ones = table.length - 1 + val exponent = Integer.numberOfLeadingZeros(ones) + (improve(hcode, seedvalue) >>> exponent) & ones + } protected def initWithContents(c: HashTable.Contents[A, Entry]) = { if (c != null) { @@ -395,13 +399,13 @@ private[collection] object HashTable { /** The load factor for the hash table (in 0.001 step). */ private[collection] final def defaultLoadFactor: Int = 750 // corresponds to 75% - private[collection] final def loadFactorDenum = 1000 + private[collection] final def loadFactorDenum = 1000 // should be loadFactorDenom, but changing that isn't binary compatible private[collection] final def newThreshold(_loadFactor: Int, size: Int) = ((size.toLong * _loadFactor) / loadFactorDenum).toInt 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 @@ -429,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, |