From 302562f86e418630b476852b9ba235e85f98bacb Mon Sep 17 00:00:00 2001 From: Rex Kerr Date: Mon, 30 Mar 2015 23:34:02 -0700 Subject: SI-9254 UnrolledBuffer appends in wrong position Fixed two bugs in insertion (insertAll of Unrolled): 1. Incorrect recursion leading to an inability to insert past the first chunk 2. Incorect repositioning of `lastptr` leading to strange `append` behavior after early insertion Added tests checking that both of these things now work. Also added a comment that "waterlineDelim" is misnamed. But we can't fix it now--it's part of the public API. (Shouldn't be, but it is.) --- .../scala/collection/mutable/UnrolledBuffer.scala | 12 ++++++----- .../collection/mutable/UnrolledBufferTest.scala | 25 ++++++++++++++++++++++ 2 files changed, 32 insertions(+), 5 deletions(-) create mode 100644 test/junit/scala/collection/mutable/UnrolledBufferTest.scala diff --git a/src/library/scala/collection/mutable/UnrolledBuffer.scala b/src/library/scala/collection/mutable/UnrolledBuffer.scala index 693c47d86e..1fda318e51 100644 --- a/src/library/scala/collection/mutable/UnrolledBuffer.scala +++ b/src/library/scala/collection/mutable/UnrolledBuffer.scala @@ -208,7 +208,7 @@ object UnrolledBuffer extends ClassTagTraversableFactory[UnrolledBuffer] { def newBuilder[T](implicit t: ClassTag[T]): Builder[T, UnrolledBuffer[T]] = new UnrolledBuffer[T] val waterline = 50 - val waterlineDelim = 100 + val waterlineDelim = 100 // TODO -- fix this name! It's a denominator, not a delimiter. (But it's part of the API so we can't just change it.) private[collection] val unrolledlength = 32 /** Unrolled buffer node. @@ -319,13 +319,15 @@ object UnrolledBuffer extends ClassTagTraversableFactory[UnrolledBuffer] { for (elem <- t) curr = curr append elem curr.next = newnextnode - // try to merge the last node of this with the newnextnode + // try to merge the last node of this with the newnextnode and fix tail pointer if needed if (curr.tryMergeWithNext()) buffer.lastPtr = curr + else if (newnextnode.next eq null) buffer.lastPtr = newnextnode } - else if (idx == size) { + else if (idx == size || (next eq null)) { var curr = this for (elem <- t) curr = curr append elem - } else insertAll(idx - size, t, buffer) + } + else next.insertAll(idx - size, t, buffer) } private def nullout(from: Int, until: Int) { var idx = from @@ -344,7 +346,7 @@ object UnrolledBuffer extends ClassTagTraversableFactory[UnrolledBuffer] { tryMergeWithNext() } - override def toString = array.take(size).mkString("Unrolled[" + array.length + "](", ", ", ")") + " -> " + (if (next ne null) next.toString else "") + override def toString = array.take(size).mkString("Unrolled@%08x".format(System.identityHashCode(this)) + "[" + size + "/" + array.length + "](", ", ", ")") + " -> " + (if (next ne null) next.toString else "") } } diff --git a/test/junit/scala/collection/mutable/UnrolledBufferTest.scala b/test/junit/scala/collection/mutable/UnrolledBufferTest.scala new file mode 100644 index 0000000000..8660b6cbc1 --- /dev/null +++ b/test/junit/scala/collection/mutable/UnrolledBufferTest.scala @@ -0,0 +1,25 @@ +package scala.collection.mutable + +import org.junit.runner.RunWith +import org.junit.runners.JUnit4 +import org.junit.Test + +@RunWith(classOf[JUnit4]) +class UnrolledBufferTestTest { + @Test + def test_SI9254_original() { + val b = new UnrolledBuffer[Int]() + (1 to 16).foreach(i => b append i) + b.insert(0,-1) + b append 17 + assert(b sameElements (Seq(-1) ++ (1 to 16) ++ Seq(17))) + } + + @Test + def test_SI9254_additional() { + val b = new UnrolledBuffer[Int]() + (1 to 100).foreach(i => b append i) + b.insert(40, -1) + assert(b sameElements((1 to 40) ++ Seq(-1) ++ (41 to 100))) + } +} -- cgit v1.2.3