diff options
-rw-r--r-- | src/library/scala/collection/mutable/ListMap.scala | 17 | ||||
-rw-r--r-- | test/files/run/t6853.scala | 18 |
2 files changed, 29 insertions, 6 deletions
diff --git a/src/library/scala/collection/mutable/ListMap.scala b/src/library/scala/collection/mutable/ListMap.scala index 212ee917c5..7f05deffc8 100644 --- a/src/library/scala/collection/mutable/ListMap.scala +++ b/src/library/scala/collection/mutable/ListMap.scala @@ -12,6 +12,7 @@ package scala.collection package mutable import generic._ +import annotation.tailrec /** A simple mutable map backed by a list. * @@ -47,13 +48,17 @@ extends AbstractMap[A, B] def get(key: A): Option[B] = elems find (_._1 == key) map (_._2) def iterator: Iterator[(A, B)] = elems.iterator - def += (kv: (A, B)) = { elems = remove(kv._1, elems); elems = kv :: elems; siz += 1; this } - def -= (key: A) = { elems = remove(key, elems); this } - private def remove(key: A, elems: List[(A, B)]): List[(A, B)] = - if (elems.isEmpty) elems - else if (elems.head._1 == key) { siz -= 1; elems.tail } - else elems.head :: remove(key, elems.tail) + def += (kv: (A, B)) = { elems = remove(kv._1, elems, List()); elems = kv :: elems; siz += 1; this } + def -= (key: A) = { elems = remove(key, elems, List()); this } + + @tailrec + private def remove(key: A, elems: List[(A, B)], acc: List[(A, B)]): List[(A, B)] = { + if (elems.isEmpty) acc + else if (elems.head._1 == key) { siz -= 1; acc ::: elems.tail } + else remove(key, elems.tail, elems.head :: acc) + } + override def clear() = { elems = List(); siz = 0 } override def size: Int = siz diff --git a/test/files/run/t6853.scala b/test/files/run/t6853.scala new file mode 100644 index 0000000000..352375c99c --- /dev/null +++ b/test/files/run/t6853.scala @@ -0,0 +1,18 @@ +// Test cases: the only place we can cut and paste without crying +// ourself to sleep. +object Test { + + def main(args: Array[String]): Unit = { + // First testing the basic operations + val m = collection.mutable.ListMap[String, Int]() + var i = 0 + while(i < 2) { m += ("foo" + i) -> i; i = i+1} + assert(m == Map("foo1"->1,"foo0"->0)) + m-= "foo0" + assert(m == Map("foo1"->1)) + // Now checking if it scales as described in SI-6853 + i = 0 + while(i < 80000) { m += ("foo" + i) -> i; i = i+1} + assert(m.size == 80000) + } +} |