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.) --- src/library/scala/collection/mutable/UnrolledBuffer.scala | 12 +++++++----- 1 file changed, 7 insertions(+), 5 deletions(-) (limited to 'src/library') 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 "") } } -- cgit v1.2.3