Merge pull request #5600 from paplorinc/HashTable_index

Further small HashTable optimizations

3 files changed, 5 insertions, 18 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/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