Merge pull request #1169 from rklaehn/SI-6261

Si 6261

2 files changed, 52 insertions, 40 deletions

diff --git a/src/library/scala/collection/immutable/HashMap.scala b/src/library/scala/collection/immutable/HashMap.scala
index 0b297aeb45..b41327ed95 100644
--- a/src/library/scala/collection/immutable/HashMap.scala
+++ b/src/library/scala/collection/immutable/HashMap.scala
@@ -146,6 +146,29 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int {
 
   private object EmptyHashMap extends HashMap[Any, Nothing] { }
 
+  // utility method to create a HashTrieMap from two leaf HashMaps (HashMap1 or HashMapCollision1) with non-colliding hash code)
+  private def makeHashTrieMap[A, B](hash0:Int, elem0:HashMap[A, B], hash1:Int, elem1:HashMap[A, B], level:Int, size:Int) : HashTrieMap[A, B] = {
+    val index0 = (hash0 >>> level) & 0x1f
+    val index1 = (hash1 >>> level) & 0x1f
+    if(index0 != index1) {
+      val bitmap = (1 << index0) | (1 << index1)
+      val elems = new Array[HashMap[A,B]](2)
+      if(index0 < index1) {
+        elems(0) = elem0
+        elems(1) = elem1
+      } else {
+        elems(0) = elem1
+        elems(1) = elem0
+      }
+      new HashTrieMap[A, B](bitmap, elems, size)
+    } else {
+      val elems = new Array[HashMap[A,B]](1)
+      val bitmap = (1 << index0)
+      elems(0) = makeHashTrieMap(hash0, elem0, hash1, elem1, level + 5, size)
+      new HashTrieMap[A, B](bitmap, elems, size)
+    }
+  }
+
   // TODO: add HashMap2, HashMap3, ...
 
   class HashMap1[A,+B](private[collection] val key: A, private[collection] val hash: Int, private[collection] val value: (B @uV), private[collection] var kv: (A,B @uV)) extends HashMap[A,B] {
@@ -183,30 +206,10 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int {
           new HashMap1(nkv._1, hash, nkv._2, nkv)
         }
       } else {
-        var thatindex = (hash >>> level) & 0x1f
-        var thisindex = (this.hash >>> level) & 0x1f
         if (hash != this.hash) {
           // they have different hashes, but may collide at this level - find a level at which they don't
-          var lvl = level
-          var top: HashTrieMap[A, B1] = null
-          var prev: HashTrieMap[A, B1] = null
-          while (thisindex == thatindex) {
-            val newlevel = new HashTrieMap[A, B1](1 << thisindex, new Array[HashMap[A, B1]](1), 2)
-            if (prev ne null) prev.elems(0) = newlevel else top = newlevel
-            prev = newlevel
-            lvl += 5
-            thatindex = (hash >>> lvl) & 0x1f
-            thisindex = (this.hash >>> lvl) & 0x1f
-          }
-          val bottelems = new Array[HashMap[A,B1]](2)
-          val ind = if (thisindex < thatindex) 1 else 0
-          bottelems(1 - ind) = this
-          bottelems(ind) = new HashMap1[A, B1](key, hash, value, kv)
-          val bottom = new HashTrieMap[A,B1]((1 << thisindex) | (1 << thatindex), bottelems, 2)
-          if (prev ne null) {
-            prev.elems(0) = bottom
-            top
-          } else bottom
+          val that = new HashMap1[A, B1](key, hash, value, kv)
+          makeHashTrieMap[A,B1](this.hash, this, hash, that, level, 2)
         } else {
           // 32-bit hash collision (rare, but not impossible)
           new HashMapCollision1(hash, ListMap.empty.updated(this.key,this.value).updated(key,value))
@@ -221,12 +224,13 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int {
     // this method may be called multiple times in a multithreaded environment, but that's ok
     private[HashMap] def ensurePair: (A,B) = if (kv ne null) kv else { kv = (key, value); kv }
     protected override def merge0[B1 >: B](that: HashMap[A, B1], level: Int, merger: Merger[A, B1]): HashMap[A, B1] = {
-      that.updated0(key, hash, level, value, kv, if (merger ne null) merger.invert else null)
+      that.updated0(key, hash, level, value, kv, merger.invert)
     }
   }
 
   private[collection] class HashMapCollision1[A, +B](private[collection] val hash: Int, val kvs: ListMap[A, B @uV])
           extends HashMap[A, B @uV] {
+    // assert(kvs.size > 1)
 
     override def size = kvs.size
 
@@ -238,20 +242,20 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int {
         if ((merger eq null) || !kvs.contains(key)) new HashMapCollision1(hash, kvs.updated(key, value))
         else new HashMapCollision1(hash, kvs + merger((key, kvs(key)), kv))
       } else {
-        var m: HashMap[A,B1] = new HashTrieMap[A,B1](0,new Array[HashMap[A,B1]](0),0)
-        // might be able to save some ops here, but it doesn't seem to be worth it
-        for ((k,v) <- kvs)
-          m = m.updated0(k, this.hash, level, v, null, merger)
-        m.updated0(key, hash, level, value, kv, merger)
+        val that = new HashMap1(key, hash, value, kv)
+        makeHashTrieMap(this.hash, this, hash, that, level, size + 1)
       }
 
     override def removed0(key: A, hash: Int, level: Int): HashMap[A, B] =
       if (hash == this.hash) {
         val kvs1 = kvs - key
-        if (!kvs1.isEmpty)
-          new HashMapCollision1(hash, kvs1)
-        else
+        if (kvs1.isEmpty)
           HashMap.empty[A,B]
+        else if(kvs1.tail.isEmpty) {
+          val kv = kvs1.head
+          new HashMap1[A,B](kv._1,hash,kv._2,kv)
+        } else
+          new HashMapCollision1(hash, kvs1)
       } else this
 
     override def iterator: Iterator[(A,B)] = kvs.iterator
@@ -275,6 +279,9 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int {
     private[collection] val size0: Int
   ) extends HashMap[A, B @uV] {
 
+    // assert(Integer.bitCount(bitmap) == elems.length)
+    // assert(elems.length > 1 || (elems.length == 1 && elems(0).isInstanceOf[HashTrieMap[_,_]]))
+
 /*
     def this (level: Int, m1: HashMap1[A,B], m2: HashMap1[A,B]) = {
       this(((m1.hash >>> level) & 0x1f) | ((m2.hash >>> level) & 0x1f), {
@@ -347,9 +354,14 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int {
             Array.copy(elems, 0, elemsNew, 0, offset)
             Array.copy(elems, offset + 1, elemsNew, offset, elems.length - offset - 1)
             val sizeNew = size - sub.size
-            new HashTrieMap(bitmapNew, elemsNew, sizeNew)
+            if (elemsNew.length == 1 && !elemsNew(0).isInstanceOf[HashTrieMap[_,_]])
+              elemsNew(0)
+            else
+              new HashTrieMap(bitmapNew, elemsNew, sizeNew)
           } else
             HashMap.empty[A,B]
+        } else if(elems.length == 1 && !subNew.isInstanceOf[HashTrieMap[_,_]]) {
+          subNew
         } else {
           val elemsNew = new Array[HashMap[A,B]](elems.length)
           Array.copy(elems, 0, elemsNew, 0, elems.length)
@@ -480,7 +492,7 @@ time { mNew.iterator.foreach( p => ()) }
         }
 
         new HashTrieMap[A, B1](this.bitmap | that.bitmap, merged, totalelems)
-      case hm: HashMapCollision1[_, _] => that.merge0(this, level, if (merger ne null) merger.invert else null)
+      case hm: HashMapCollision1[_, _] => that.merge0(this, level, merger.invert)
       case hm: HashMap[_, _] => this
       case _ => sys.error("section supposed to be unreachable.")
     }
diff --git a/src/library/scala/collection/immutable/ListMap.scala b/src/library/scala/collection/immutable/ListMap.scala
index 091443f909..c21032603f 100644
--- a/src/library/scala/collection/immutable/ListMap.scala
+++ b/src/library/scala/collection/immutable/ListMap.scala
@@ -121,12 +121,12 @@ extends AbstractMap[A, B]
       def hasNext = !self.isEmpty
       def next(): (A,B) =
         if (!hasNext) throw new NoSuchElementException("next on empty iterator")
-        else { val res = (self.key, self.value); self = self.next; res }
+        else { val res = (self.key, self.value); self = self.tail; res }
     }.toList.reverseIterator
 
   protected def key: A = throw new NoSuchElementException("empty map")
   protected def value: B = throw new NoSuchElementException("empty map")
-  protected def next: ListMap[A, B] = throw new NoSuchElementException("empty map")
+  override def tail: ListMap[A, B] = throw new NoSuchElementException("empty map")
 
   /** This class represents an entry in the `ListMap`.
    */
@@ -140,7 +140,7 @@ extends AbstractMap[A, B]
     override def size: Int = size0(this, 0)
 
     // to allow tail recursion and prevent stack overflows
-    @tailrec private def size0(cur: ListMap[A, B1], acc: Int): Int = if (cur.isEmpty) acc else size0(cur.next, acc + 1)
+    @tailrec private def size0(cur: ListMap[A, B1], acc: Int): Int = if (cur.isEmpty) acc else size0(cur.tail, acc + 1)
 
     /** Is this an empty map?
      *
@@ -157,7 +157,7 @@ extends AbstractMap[A, B]
      */
     override def apply(k: A): B1 = apply0(this, k)
 
-    @tailrec private def apply0(cur: ListMap[A, B1], k: A): B1 = if (k == cur.key) cur.value else apply0(cur.next, k)
+    @tailrec private def apply0(cur: ListMap[A, B1], k: A): B1 = if (k == cur.key) cur.value else apply0(cur.tail, k)
 
     /** Checks if this map maps `key` to a value and return the
      *  value if it exists.
@@ -169,7 +169,7 @@ extends AbstractMap[A, B]
 
     @tailrec private def get0(cur: ListMap[A, B1], k: A): Option[B1] =
       if (k == cur.key) Some(cur.value)
-      else if (cur.next.nonEmpty) get0(cur.next, k) else None
+      else if (cur.tail.nonEmpty) get0(cur.tail, k) else None
 
     /** This method allows one to create a new map with an additional mapping
      *  from `key` to `value`. If the map contains already a mapping for `key`,
@@ -198,7 +198,7 @@ extends AbstractMap[A, B]
       var lst: List[(A, B1)] = Nil
       while (cur.nonEmpty) {
         if (k != cur.key) lst ::= ((cur.key, cur.value))
-        cur = cur.next
+        cur = cur.tail
       }
       var acc = ListMap[A, B1]()
       while (lst != Nil) {
@@ -211,6 +211,6 @@ extends AbstractMap[A, B]
     }
 
 
-    override protected def next: ListMap[A, B1] = ListMap.this
+    override def tail: ListMap[A, B1] = ListMap.this
   }
 }