From 3ad5af7316fba587c43a2ddc070d556f261667a0 Mon Sep 17 00:00:00 2001
From: Pap Lőrinc <paplorinc@gmail.com>
Date: Tue, 13 Dec 2016 00:42:10 +0200
Subject: Optimized HashTable.nextPositivePowerOfTwo

---
 bincompat-backward.whitelist.conf                        | 12 ++++++++++++
 bincompat-forward.whitelist.conf                         |  4 ++++
 src/library/scala/collection/mutable/FlatHashTable.scala |  4 +---
 src/library/scala/collection/mutable/HashTable.scala     | 15 +++------------
 src/library/scala/collection/mutable/OpenHashMap.scala   |  4 +---
 5 files changed, 21 insertions(+), 18 deletions(-)

diff --git a/bincompat-backward.whitelist.conf b/bincompat-backward.whitelist.conf
index 57dc564e8a..eb7886e8ce 100644
--- a/bincompat-backward.whitelist.conf
+++ b/bincompat-backward.whitelist.conf
@@ -21,6 +21,18 @@ filter {
       matchName="scala.collection.immutable.VectorIterator.debug"
       problemName=DirectMissingMethodProblem
     },
+    {
+      matchName="scala.collection.mutable.OpenHashMap.nextPositivePowerOfTwo"
+      problemName=DirectMissingMethodProblem
+    },
+    {
+      matchName="scala.collection.mutable.HashTable.nextPositivePowerOfTwo"
+      problemName=DirectMissingMethodProblem
+    },
+    {
+      matchName="scala.collection.mutable.HashTable.powerOfTwo"
+      problemName=DirectMissingMethodProblem
+    },
     {
       matchName="scala.reflect.runtime.JavaMirrors#JavaMirror.unpickleClass"
       problemName=IncompatibleMethTypeProblem
diff --git a/bincompat-forward.whitelist.conf b/bincompat-forward.whitelist.conf
index ad778f447a..0a9193ea4d 100644
--- a/bincompat-forward.whitelist.conf
+++ b/bincompat-forward.whitelist.conf
@@ -21,6 +21,10 @@ filter {
       matchName="scala.sys.process.ProcessImpl#CompoundProcess.futureThread"
       problemName=DirectMissingMethodProblem
     },
+    {
+      matchName="scala.collection.mutable.HashTable.nextPositivePowerOfTwo"
+      problemName=DirectMissingMethodProblem
+    }
     {
       matchName="scala.reflect.runtime.Settings.Yvirtpatmat"
       problemName=DirectMissingMethodProblem
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
 
-- 
cgit v1.2.3