Applied performance patch and test case from ij...

Applied performance patch and test case from ijuma; closes #2526.

3 files changed, 41 insertions, 2 deletions

diff --git a/src/library/scala/collection/MapLike.scala b/src/library/scala/collection/MapLike.scala
index 3b188acab6..3287a4524c 100644
--- a/src/library/scala/collection/MapLike.scala
+++ b/src/library/scala/collection/MapLike.scala
@@ -129,7 +129,7 @@ self =>
 
   protected class DefaultKeySet extends Set[A] {
     def contains(key : A) = self.contains(key)
-    def iterator = self.iterator.map(_._1)
+    def iterator = keysIterator
     def + (elem: A): Set[A] = (Set[A]() ++ this + elem).asInstanceOf[Set[A]] // !!! concrete overrides abstract problem
     def - (elem: A): Set[A] = (Set[A]() ++ this - elem).asInstanceOf[Set[A]] // !!! concrete overrides abstract problem
     override def size = self.size
@@ -158,7 +158,7 @@ self =>
   def valuesIterable: Iterable[B] = new DefaultValuesIterable
 
   protected class DefaultValuesIterable extends Iterable[B] {
-    def iterator = self.iterator.map(_._2)
+    def iterator = valuesIterator
     override def size = self.size
     override def foreach[C](f: B => C) = for ((k, v) <- self) f(v)
   }
diff --git a/src/library/scala/collection/mutable/HashMap.scala b/src/library/scala/collection/mutable/HashMap.scala
index b2f259e4e9..e4969a3af0 100644
--- a/src/library/scala/collection/mutable/HashMap.scala
+++ b/src/library/scala/collection/mutable/HashMap.scala
@@ -58,6 +58,32 @@ class HashMap[A, B] extends Map[A, B]
   def -=(key: A): this.type = { removeEntry(key); this }
 
   def iterator = entriesIterator map {e => (e.key, e.value)}
+
+  override def foreach[C](f: ((A, B)) => C): Unit = foreachEntry(e => f(e.key, e.value))
+
+  /* Override to avoid tuple allocation in foreach */
+  override def keySet: collection.Set[A] = new DefaultKeySet {
+    override def foreach[C](f: A => C) = foreachEntry(e => f(e.key))
+  }
+
+  /* Override to avoid tuple allocation in foreach */
+  override def valuesIterable: collection.Iterable[B] = new DefaultValuesIterable {
+    override def foreach[C](f: B => C) = foreachEntry(e => f(e.value))
+  }
+
+  /* Override to avoid tuple allocation */
+  override def keysIterator: Iterator[A] = new Iterator[A] {
+    val iter = entriesIterator
+    def hasNext = iter.hasNext
+    def next = iter.next.key
+  }
+
+  /* Override to avoid tuple allocation */
+  override def valuesIterator: Iterator[B] = new Iterator[B] {
+    val iter = entriesIterator
+    def hasNext = iter.hasNext
+    def next = iter.next.value
+  }
 }
 
 /** This class implements mutable maps using a hashtable.
diff --git a/src/library/scala/collection/mutable/HashTable.scala b/src/library/scala/collection/mutable/HashTable.scala
index 9dd8a7aeb0..db4e100634 100644
--- a/src/library/scala/collection/mutable/HashTable.scala
+++ b/src/library/scala/collection/mutable/HashTable.scala
@@ -144,6 +144,19 @@ trait HashTable[A] {
     }
   }
 
+  protected final def foreachEntry[C](f: Entry => C) {
+    val t = table
+    var index = t.length - 1
+    while (index >= 0) {
+      var entry = t(index)
+      while (entry ne null) {
+        f(entry.asInstanceOf[Entry])
+        entry = entry.next
+      }
+      index -= 1
+    }
+  }
+
   /** An iterator returning all entries */
   @deprecated("use entriesIterator instead")
   protected def entries: Iterator[Entry] = entriesIterator