Optimized HashTable.nextPositivePowerOfTwo

l0rinc · l0rinc · commit 635b8afd7071 · 2016-12-20T00:03:54.000+02:00
diff --git 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
@@ -401,7 +401,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
@@ -429,16 +429,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
@@ -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
 
