From 5ae77a7ea9a3ccacc95e8ee9fca1761d8cc5a94d Mon Sep 17 00:00:00 2001 From: Pap Lőrinc Date: Fri, 18 Nov 2016 22:37:57 +0200 Subject: Applied suggestions to Vector cleanup --- .../scala/collection/immutable/Vector.scala | 340 ++++++++++----------- 1 file changed, 161 insertions(+), 179 deletions(-) diff --git a/src/library/scala/collection/immutable/Vector.scala b/src/library/scala/collection/immutable/Vector.scala index fa74e735ef..034691aea2 100644 --- a/src/library/scala/collection/immutable/Vector.scala +++ b/src/library/scala/collection/immutable/Vector.scala @@ -180,31 +180,36 @@ extends AbstractSeq[A] Vector.empty } - override /*IterableLike*/ def head: A = { + override /*IterableLike*/ + def head: A = { if (isEmpty) throw new UnsupportedOperationException("empty.head") apply(0) } - override /*TraversableLike*/ def tail: Vector[A] = { + override /*TraversableLike*/ + def tail: Vector[A] = { if (isEmpty) throw new UnsupportedOperationException("empty.tail") drop(1) } - override /*TraversableLike*/ def last: A = { + override /*TraversableLike*/ + def last: A = { if (isEmpty) throw new UnsupportedOperationException("empty.last") - apply(length-1) + apply(length - 1) } - override /*TraversableLike*/ def init: Vector[A] = { + override /*TraversableLike*/ + def init: Vector[A] = { if (isEmpty) throw new UnsupportedOperationException("empty.init") dropRight(1) } - override /*IterableLike*/ def slice(from: Int, until: Int): Vector[A] = + override /*IterableLike*/ + def slice(from: Int, until: Int): Vector[A] = take(until).drop(from) - override /*IterableLike*/ def splitAt(n: Int): (Vector[A], Vector[A]) = (take(n), drop(n)) - + override /*IterableLike*/ + def splitAt(n: Int): (Vector[A], Vector[A]) = (take(n), drop(n)) // concat (suboptimal but avoids worst performance gotchas) override def ++[B >: A, That](that: GenTraversableOnce[B])(implicit bf: CanBuildFrom[Vector[A], B, That]): That = { @@ -258,7 +263,7 @@ extends AbstractSeq[A] dirty = true } - private[immutable] def appendFront[B>:A](value: B): Vector[B] = { + private[immutable] def appendFront[B >: A](value: B): Vector[B] = { if (endIndex != startIndex) { val blockIndex = (startIndex - 1) & ~31 val lo = (startIndex - 1) & 31 @@ -272,9 +277,9 @@ extends AbstractSeq[A] s } else { - val freeSpace = ((1 << (5 * depth)) - endIndex) // free space at the right given the current tree-structure depth - val shift = (freeSpace & ~((1 << (5 * (depth - 1))) - 1)) // number of elements by which we'll shift right (only move at top level) - val shiftBlocks = (freeSpace >>> (5 * (depth - 1))) // number of top-level blocks + val freeSpace = (1 << (5 * depth)) - endIndex // free space at the right given the current tree-structure depth + val shift = freeSpace & ~((1 << (5 * (depth - 1))) - 1) // number of elements by which we'll shift right (only move at top level) + val shiftBlocks = freeSpace >>> (5 * (depth - 1)) // number of top-level blocks if (shift != 0) { // case A: we can shift right on the top level @@ -298,7 +303,7 @@ extends AbstractSeq[A] s.dirty = dirty s.shiftTopLevel(0, shiftBlocks) // shift right by n elements s.gotoPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex) // prepare for writing - s.display0(shift-1) = value.asInstanceOf[AnyRef] + s.display0(shift - 1) = value.asInstanceOf[AnyRef] s } } else if (blockIndex < 0) { @@ -329,14 +334,14 @@ extends AbstractSeq[A] // empty vector, just insert single element at the back val elems = new Array[AnyRef](32) elems(31) = value.asInstanceOf[AnyRef] - val s = new Vector(31,32,0) + val s = new Vector(31, 32, 0) s.depth = 1 s.display0 = elems s } } - private[immutable] def appendBack[B>:A](value: B): Vector[B] = { + private[immutable] def appendBack[B >: A](value: B): Vector[B] = { if (endIndex != startIndex) { val blockIndex = endIndex & ~31 val lo = endIndex & 31 @@ -349,8 +354,8 @@ extends AbstractSeq[A] s.display0(lo) = value.asInstanceOf[AnyRef] s } else { - val shift = startIndex & ~((1 << 5 * (depth - 1)) - 1) - val shiftBlocks = startIndex >>> 5 * (depth - 1) + val shift = startIndex & ~((1 << (5 * (depth - 1))) - 1) + val shiftBlocks = startIndex >>> (5 * (depth - 1)) if (shift != 0) { if (depth > 1) { @@ -389,7 +394,7 @@ extends AbstractSeq[A] } else { val elems = new Array[AnyRef](32) elems(0) = value.asInstanceOf[AnyRef] - val s = new Vector(0,1,0) + val s = new Vector(0, 1, 0) s.depth = 1 s.display0 = elems s @@ -415,22 +420,30 @@ extends AbstractSeq[A] } private def zeroLeft(array: Array[AnyRef], index: Int): Unit = { - var i = 0; while (i < index) { array(i) = null; i+=1 } + var i = 0 + while (i < index) { + array(i) = null + i += 1 + } } private def zeroRight(array: Array[AnyRef], index: Int): Unit = { - var i = index; while (i < array.length) { array(i) = null; i+=1 } + var i = index + while (i < array.length) { + array(i) = null + i += 1 + } } private def copyLeft(array: Array[AnyRef], right: Int): Array[AnyRef] = { - val a2 = new Array[AnyRef](array.length) - java.lang.System.arraycopy(array, 0, a2, 0, right) - a2 + val copy = new Array[AnyRef](array.length) + java.lang.System.arraycopy(array, 0, copy, 0, right) + copy } private def copyRight(array: Array[AnyRef], left: Int): Array[AnyRef] = { - val a2 = new Array[AnyRef](array.length) - java.lang.System.arraycopy(array, left, a2, left, a2.length - left) - a2 + val copy = new Array[AnyRef](array.length) + java.lang.System.arraycopy(array, left, copy, left, copy.length - left) + copy } private def preClean(depth: Int) = { @@ -462,38 +475,33 @@ extends AbstractSeq[A] // requires structure is at index cutIndex and writable at level 0 private def cleanLeftEdge(cutIndex: Int) = { - if (cutIndex < (1 << 5)) { + if (cutIndex < (1 << 5)) { zeroLeft(display0, cutIndex) - } else - if (cutIndex < (1 << 10)) { + } else if (cutIndex < (1 << 10)) { zeroLeft(display0, cutIndex & 31) - display1 = copyRight(display1, (cutIndex >>> 5)) - } else - if (cutIndex < (1 << 15)) { + display1 = copyRight(display1, cutIndex >>> 5) + } else if (cutIndex < (1 << 15)) { zeroLeft(display0, cutIndex & 31) display1 = copyRight(display1, (cutIndex >>> 5) & 31) - display2 = copyRight(display2, (cutIndex >>> 10)) - } else - if (cutIndex < (1 << 20)) { + display2 = copyRight(display2, cutIndex >>> 10) + } else if (cutIndex < (1 << 20)) { zeroLeft(display0, cutIndex & 31) display1 = copyRight(display1, (cutIndex >>> 5) & 31) display2 = copyRight(display2, (cutIndex >>> 10) & 31) - display3 = copyRight(display3, (cutIndex >>> 15)) - } else - if (cutIndex < (1 << 25)) { + display3 = copyRight(display3, cutIndex >>> 15) + } else if (cutIndex < (1 << 25)) { zeroLeft(display0, cutIndex & 31) display1 = copyRight(display1, (cutIndex >>> 5) & 31) display2 = copyRight(display2, (cutIndex >>> 10) & 31) display3 = copyRight(display3, (cutIndex >>> 15) & 31) - display4 = copyRight(display4, (cutIndex >>> 20)) - } else - if (cutIndex < (1 << 30)) { + display4 = copyRight(display4, cutIndex >>> 20) + } else if (cutIndex < (1 << 30)) { zeroLeft(display0, cutIndex & 31) display1 = copyRight(display1, (cutIndex >>> 5) & 31) display2 = copyRight(display2, (cutIndex >>> 10) & 31) display3 = copyRight(display3, (cutIndex >>> 15) & 31) display4 = copyRight(display4, (cutIndex >>> 20) & 31) - display5 = copyRight(display5, (cutIndex >>> 25)) + display5 = copyRight(display5, cutIndex >>> 25) } else { throw new IllegalArgumentException() } @@ -501,42 +509,36 @@ extends AbstractSeq[A] // requires structure is writable and at index cutIndex private def cleanRightEdge(cutIndex: Int) = { - // we're actually sitting one block left if cutIndex lies on a block boundary // this means that we'll end up erasing the whole block!! - if (cutIndex <= (1 << 5)) { + if (cutIndex <= (1 << 5)) { zeroRight(display0, cutIndex) - } else - if (cutIndex <= (1 << 10)) { - zeroRight(display0, ((cutIndex-1) & 31) + 1) - display1 = copyLeft(display1, (cutIndex >>> 5)) - } else - if (cutIndex <= (1 << 15)) { - zeroRight(display0, ((cutIndex-1) & 31) + 1) - display1 = copyLeft(display1, (((cutIndex-1) >>> 5) & 31) + 1) - display2 = copyLeft(display2, (cutIndex >>> 10)) - } else - if (cutIndex <= (1 << 20)) { - zeroRight(display0, ((cutIndex-1) & 31) + 1) - display1 = copyLeft(display1, (((cutIndex-1) >>> 5) & 31) + 1) - display2 = copyLeft(display2, (((cutIndex-1) >>> 10) & 31) + 1) - display3 = copyLeft(display3, (cutIndex >>> 15)) - } else - if (cutIndex <= (1 << 25)) { - zeroRight(display0, ((cutIndex-1) & 31) + 1) - display1 = copyLeft(display1, (((cutIndex-1) >>> 5) & 31) + 1) - display2 = copyLeft(display2, (((cutIndex-1) >>> 10) & 31) + 1) - display3 = copyLeft(display3, (((cutIndex-1) >>> 15) & 31) + 1) - display4 = copyLeft(display4, (cutIndex >>> 20)) - } else - if (cutIndex <= (1 << 30)) { - zeroRight(display0, ((cutIndex-1) & 31) + 1) - display1 = copyLeft(display1, (((cutIndex-1) >>> 5) & 31) + 1) - display2 = copyLeft(display2, (((cutIndex-1) >>> 10) & 31) + 1) - display3 = copyLeft(display3, (((cutIndex-1) >>> 15) & 31) + 1) - display4 = copyLeft(display4, (((cutIndex-1) >>> 20) & 31) + 1) - display5 = copyLeft(display5, (cutIndex >>> 25)) + } else if (cutIndex <= (1 << 10)) { + zeroRight(display0, ((cutIndex - 1) & 31) + 1) + display1 = copyLeft(display1, cutIndex >>> 5) + } else if (cutIndex <= (1 << 15)) { + zeroRight(display0, ((cutIndex - 1) & 31) + 1) + display1 = copyLeft(display1, (((cutIndex - 1) >>> 5) & 31) + 1) + display2 = copyLeft(display2, cutIndex >>> 10) + } else if (cutIndex <= (1 << 20)) { + zeroRight(display0, ((cutIndex - 1) & 31) + 1) + display1 = copyLeft(display1, (((cutIndex - 1) >>> 5) & 31) + 1) + display2 = copyLeft(display2, (((cutIndex - 1) >>> 10) & 31) + 1) + display3 = copyLeft(display3, cutIndex >>> 15) + } else if (cutIndex <= (1 << 25)) { + zeroRight(display0, ((cutIndex - 1) & 31) + 1) + display1 = copyLeft(display1, (((cutIndex - 1) >>> 5) & 31) + 1) + display2 = copyLeft(display2, (((cutIndex - 1) >>> 10) & 31) + 1) + display3 = copyLeft(display3, (((cutIndex - 1) >>> 15) & 31) + 1) + display4 = copyLeft(display4, cutIndex >>> 20) + } else if (cutIndex <= (1 << 30)) { + zeroRight(display0, ((cutIndex - 1) & 31) + 1) + display1 = copyLeft(display1, (((cutIndex - 1) >>> 5) & 31) + 1) + display2 = copyLeft(display2, (((cutIndex - 1) >>> 10) & 31) + 1) + display3 = copyLeft(display3, (((cutIndex - 1) >>> 15) & 31) + 1) + display4 = copyLeft(display4, (((cutIndex - 1) >>> 20) & 31) + 1) + display5 = copyLeft(display5, cutIndex >>> 25) } else { throw new IllegalArgumentException() } @@ -556,11 +558,11 @@ extends AbstractSeq[A] val blockIndex = cutIndex & ~31 val xor = cutIndex ^ (endIndex - 1) val d = requiredDepth(xor) - val shift = (cutIndex & ~((1 << (5 * d)) - 1)) + val shift = cutIndex & ~((1 << (5 * d)) - 1) // need to init with full display iff going to cutIndex requires swapping block at level >= d - val s = new Vector(cutIndex-shift, endIndex-shift, blockIndex-shift) + val s = new Vector(cutIndex - shift, endIndex - shift, blockIndex - shift) s.initFrom(this) s.dirty = dirty s.gotoPosWritable(focus, blockIndex, focus ^ blockIndex) @@ -573,14 +575,14 @@ extends AbstractSeq[A] val blockIndex = (cutIndex - 1) & ~31 val xor = startIndex ^ (cutIndex - 1) val d = requiredDepth(xor) - val shift = (startIndex & ~((1 << (5 * d)) - 1)) + val shift = startIndex & ~((1 << (5 * d)) - 1) - val s = new Vector(startIndex-shift, cutIndex-shift, blockIndex-shift) + val s = new Vector(startIndex - shift, cutIndex - shift, blockIndex - shift) s.initFrom(this) s.dirty = dirty s.gotoPosWritable(focus, blockIndex, focus ^ blockIndex) s.preClean(d) - s.cleanRightEdge(cutIndex-shift) + s.cleanRightEdge(cutIndex - shift) s } } @@ -607,7 +609,7 @@ class VectorIterator[+A](_startIndex: Int, endIndex: Int) if (lo == endLo) { if (blockIndex + lo < endIndex) { - val newBlockIndex = blockIndex+32 + val newBlockIndex = blockIndex + 32 gotoNextBlockStart(newBlockIndex, blockIndex ^ newBlockIndex) blockIndex = newBlockIndex @@ -634,7 +636,7 @@ class VectorIterator[+A](_startIndex: Int, endIndex: Int) } /** A class to build instances of `Vector`. This builder is reusable. */ -final class VectorBuilder[A]() extends ReusableBuilder[A,Vector[A]] with VectorPointer[A @uncheckedVariance] { +final class VectorBuilder[A]() extends ReusableBuilder[A, Vector[A]] with VectorPointer[A @uncheckedVariance] { // possible alternative: start with display0 = null, blockIndex = -32, lo = 32 // to avoid allocating initial array if the result will be empty anyways @@ -645,9 +647,9 @@ final class VectorBuilder[A]() extends ReusableBuilder[A,Vector[A]] with VectorP private var blockIndex = 0 private var lo = 0 - def += (elem: A): this.type = { + def +=(elem: A): this.type = { if (lo >= display0.length) { - val newBlockIndex = blockIndex+32 + val newBlockIndex = blockIndex + 32 gotoNextBlockStartWritable(newBlockIndex, blockIndex ^ newBlockIndex) blockIndex = newBlockIndex lo = 0 @@ -657,8 +659,7 @@ final class VectorBuilder[A]() extends ReusableBuilder[A,Vector[A]] with VectorP this } - override def ++=(xs: TraversableOnce[A]): this.type = - super.++=(xs) + override def ++=(xs: TraversableOnce[A]): this.type = super.++=(xs) def result: Vector[A] = { val size = blockIndex + lo @@ -678,9 +679,8 @@ final class VectorBuilder[A]() extends ReusableBuilder[A,Vector[A]] with VectorP } } - private[immutable] trait VectorPointer[T] { - private[immutable] var depth: Int = _ + private[immutable] var depth: Int = _ private[immutable] var display0: Array[AnyRef] = _ private[immutable] var display1: Array[AnyRef] = _ private[immutable] var display2: Array[AnyRef] = _ @@ -725,63 +725,52 @@ private[immutable] trait VectorPointer[T] { } } - // requires structure is at pos oldIndex = xor ^ index private[immutable] final def getElem(index: Int, xor: Int): T = { - if (xor < (1 << 5)) { // level = 0 + if (xor < (1 << 5)) { // level = 0 display0(index & 31).asInstanceOf[T] - } else - if (xor < (1 << 10)) { // level = 1 - display1((index >> 5) & 31).asInstanceOf[Array[AnyRef]](index & 31).asInstanceOf[T] - } else - if (xor < (1 << 15)) { // level = 2 - display2((index >> 10) & 31).asInstanceOf[Array[AnyRef]]((index >> 5) & 31).asInstanceOf[Array[AnyRef]](index & 31).asInstanceOf[T] - } else - if (xor < (1 << 20)) { // level = 3 - display3((index >> 15) & 31).asInstanceOf[Array[AnyRef]]((index >> 10) & 31).asInstanceOf[Array[AnyRef]]((index >> 5) & 31).asInstanceOf[Array[AnyRef]](index & 31).asInstanceOf[T] - } else - if (xor < (1 << 25)) { // level = 4 - display4((index >> 20) & 31).asInstanceOf[Array[AnyRef]]((index >> 15) & 31).asInstanceOf[Array[AnyRef]]((index >> 10) & 31).asInstanceOf[Array[AnyRef]]((index >> 5) & 31).asInstanceOf[Array[AnyRef]](index & 31).asInstanceOf[T] - } else - if (xor < (1 << 30)) { // level = 5 + } else if (xor < (1 << 10)) { // level = 1 + display1((index >> 5) & 31).asInstanceOf[Array[AnyRef]](index & 31).asInstanceOf[T] + } else if (xor < (1 << 15)) { // level = 2 + display2((index >> 10) & 31).asInstanceOf[Array[AnyRef]]((index >> 5) & 31).asInstanceOf[Array[AnyRef]](index & 31).asInstanceOf[T] + } else if (xor < (1 << 20)) { // level = 3 + display3((index >> 15) & 31).asInstanceOf[Array[AnyRef]]((index >> 10) & 31).asInstanceOf[Array[AnyRef]]((index >> 5) & 31).asInstanceOf[Array[AnyRef]](index & 31).asInstanceOf[T] + } else if (xor < (1 << 25)) { // level = 4 + display4((index >> 20) & 31).asInstanceOf[Array[AnyRef]]((index >> 15) & 31).asInstanceOf[Array[AnyRef]]((index >> 10) & 31).asInstanceOf[Array[AnyRef]]((index >> 5) & 31).asInstanceOf[Array[AnyRef]](index & 31).asInstanceOf[T] + } else if (xor < (1 << 30)) { // level = 5 display5((index >> 25) & 31).asInstanceOf[Array[AnyRef]]((index >> 20) & 31).asInstanceOf[Array[AnyRef]]((index >> 15) & 31).asInstanceOf[Array[AnyRef]]((index >> 10) & 31).asInstanceOf[Array[AnyRef]]((index >> 5) & 31).asInstanceOf[Array[AnyRef]](index & 31).asInstanceOf[T] - } else { // level = 6 + } else { // level = 6 throw new IllegalArgumentException() } } - // go to specific position // requires structure is at pos oldIndex = xor ^ index, // ensures structure is at pos index private[immutable] final def gotoPos(index: Int, xor: Int): Unit = { - if (xor < (1 << 5)) { // level = 0 (could maybe removed) - } else - if (xor < (1 << 10)) { // level = 1 + if (xor < (1 << 5)) { // level = 0 + // we're already at the block start pos + } else if (xor < (1 << 10)) { // level = 1 display0 = display1((index >> 5) & 31).asInstanceOf[Array[AnyRef]] - } else - if (xor < (1 << 15)) { // level = 2 + } else if (xor < (1 << 15)) { // level = 2 display1 = display2((index >> 10) & 31).asInstanceOf[Array[AnyRef]] display0 = display1((index >> 5) & 31).asInstanceOf[Array[AnyRef]] - } else - if (xor < (1 << 20)) { // level = 3 + } else if (xor < (1 << 20)) { // level = 3 display2 = display3((index >> 15) & 31).asInstanceOf[Array[AnyRef]] display1 = display2((index >> 10) & 31).asInstanceOf[Array[AnyRef]] display0 = display1((index >> 5) & 31).asInstanceOf[Array[AnyRef]] - } else - if (xor < (1 << 25)) { // level = 4 + } else if (xor < (1 << 25)) { // level = 4 display3 = display4((index >> 20) & 31).asInstanceOf[Array[AnyRef]] display2 = display3((index >> 15) & 31).asInstanceOf[Array[AnyRef]] display1 = display2((index >> 10) & 31).asInstanceOf[Array[AnyRef]] display0 = display1((index >> 5) & 31).asInstanceOf[Array[AnyRef]] - } else - if (xor < (1 << 30)) { // level = 5 + } else if (xor < (1 << 30)) { // level = 5 display4 = display5((index >> 25) & 31).asInstanceOf[Array[AnyRef]] display3 = display4((index >> 20) & 31).asInstanceOf[Array[AnyRef]] display2 = display3((index >> 15) & 31).asInstanceOf[Array[AnyRef]] display1 = display2((index >> 10) & 31).asInstanceOf[Array[AnyRef]] display0 = display1((index >> 5) & 31).asInstanceOf[Array[AnyRef]] - } else { // level = 6 + } else { // level = 6 throw new IllegalArgumentException() } } @@ -790,31 +779,27 @@ private[immutable] trait VectorPointer[T] { // xor: oldIndex ^ index private[immutable] final def gotoNextBlockStart(index: Int, xor: Int): Unit = { // goto block start pos - if (xor < (1 << 10)) { // level = 1 + if (xor < (1 << 10)) { // level = 1 display0 = display1((index >> 5) & 31).asInstanceOf[Array[AnyRef]] - } else - if (xor < (1 << 15)) { // level = 2 + } else if (xor < (1 << 15)) { // level = 2 display1 = display2((index >> 10) & 31).asInstanceOf[Array[AnyRef]] display0 = display1(0).asInstanceOf[Array[AnyRef]] - } else - if (xor < (1 << 20)) { // level = 3 + } else if (xor < (1 << 20)) { // level = 3 display2 = display3((index >> 15) & 31).asInstanceOf[Array[AnyRef]] display1 = display2(0).asInstanceOf[Array[AnyRef]] display0 = display1(0).asInstanceOf[Array[AnyRef]] - } else - if (xor < (1 << 25)) { // level = 4 + } else if (xor < (1 << 25)) { // level = 4 display3 = display4((index >> 20) & 31).asInstanceOf[Array[AnyRef]] display2 = display3(0).asInstanceOf[Array[AnyRef]] display1 = display2(0).asInstanceOf[Array[AnyRef]] display0 = display1(0).asInstanceOf[Array[AnyRef]] - } else - if (xor < (1 << 30)) { // level = 5 + } else if (xor < (1 << 30)) { // level = 5 display4 = display5((index >> 25) & 31).asInstanceOf[Array[AnyRef]] display3 = display4(0).asInstanceOf[Array[AnyRef]] display2 = display3(0).asInstanceOf[Array[AnyRef]] display1 = display2(0).asInstanceOf[Array[AnyRef]] display0 = display1(0).asInstanceOf[Array[AnyRef]] - } else { // level = 6 + } else { // level = 6 throw new IllegalArgumentException() } } @@ -823,29 +808,34 @@ private[immutable] trait VectorPointer[T] { // xor: oldIndex ^ index private[immutable] final def gotoNextBlockStartWritable(index: Int, xor: Int): Unit = { // goto block start pos - if (xor < (1 << 10)) { // level = 1 - if (depth == 1) { display1 = new Array(32); display1(0) = display0; depth+=1} + if (xor < (1 << 10)) { // level = 1 + if (depth == 1) { + display1 = new Array(32); display1(0) = display0; depth += 1 + } display0 = new Array(32) display1((index >> 5) & 31) = display0 - } else - if (xor < (1 << 15)) { // level = 2 - if (depth == 2) { display2 = new Array(32); display2(0) = display1; depth+=1} + } else if (xor < (1 << 15)) { // level = 2 + if (depth == 2) { + display2 = new Array(32); display2(0) = display1; depth += 1 + } display0 = new Array(32) display1 = new Array(32) display1((index >> 5) & 31) = display0 display2((index >> 10) & 31) = display1 - } else - if (xor < (1 << 20)) { // level = 3 - if (depth == 3) { display3 = new Array(32); display3(0) = display2; depth+=1} + } else if (xor < (1 << 20)) { // level = 3 + if (depth == 3) { + display3 = new Array(32); display3(0) = display2; depth += 1 + } display0 = new Array(32) display1 = new Array(32) display2 = new Array(32) display1((index >> 5) & 31) = display0 display2((index >> 10) & 31) = display1 display3((index >> 15) & 31) = display2 - } else - if (xor < (1 << 25)) { // level = 4 - if (depth == 4) { display4 = new Array(32); display4(0) = display3; depth+=1} + } else if (xor < (1 << 25)) { // level = 4 + if (depth == 4) { + display4 = new Array(32); display4(0) = display3; depth += 1 + } display0 = new Array(32) display1 = new Array(32) display2 = new Array(32) @@ -854,9 +844,10 @@ private[immutable] trait VectorPointer[T] { display2((index >> 10) & 31) = display1 display3((index >> 15) & 31) = display2 display4((index >> 20) & 31) = display3 - } else - if (xor < (1 << 30)) { // level = 5 - if (depth == 5) { display5 = new Array(32); display5(0) = display4; depth+=1} + } else if (xor < (1 << 30)) { // level = 5 + if (depth == 5) { + display5 = new Array(32); display5(0) = display4; depth += 1 + } display0 = new Array(32) display1 = new Array(32) display2 = new Array(32) @@ -867,20 +858,20 @@ private[immutable] trait VectorPointer[T] { display3((index >> 15) & 31) = display2 display4((index >> 20) & 31) = display3 display5((index >> 25) & 31) = display4 - } else { // level = 6 + } else { // level = 6 throw new IllegalArgumentException() } } // STUFF BELOW USED BY APPEND / UPDATE - private[immutable] final def copyOf(a: Array[AnyRef]) = { - val b = new Array[AnyRef](a.length) - java.lang.System.arraycopy(a, 0, b, 0, a.length) - b + private[immutable] final def copyOf(a: Array[AnyRef]): Array[AnyRef] = { + val copy = new Array[AnyRef](a.length) + java.lang.System.arraycopy(a, 0, copy, 0, a.length) + copy } - private[immutable] final def nullSlotAndCopy(array: Array[AnyRef], index: Int) = { + private[immutable] final def nullSlotAndCopy(array: Array[AnyRef], index: Int): Array[AnyRef] = { val x = array(index) array(index) = null copyOf(x.asInstanceOf[Array[AnyRef]]) @@ -970,23 +961,20 @@ private[immutable] trait VectorPointer[T] { // requires structure is dirty and at pos oldIndex, // ensures structure is dirty and at pos newIndex and writable at level 0 private[immutable] final def gotoPosWritable1(oldIndex: Int, newIndex: Int, xor: Int): Unit = { - if (xor < (1 << 5)) { // level = 0 + if (xor < (1 << 5)) { // level = 0 display0 = copyOf(display0) - } else - if (xor < (1 << 10)) { // level = 1 + } else if (xor < (1 << 10)) { // level = 1 display1 = copyOf(display1) - display1((oldIndex >> 5) & 31) = display0 + display1((oldIndex >> 5) & 31) = display0 display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31) - } else - if (xor < (1 << 15)) { // level = 2 + } else if (xor < (1 << 15)) { // level = 2 display1 = copyOf(display1) display2 = copyOf(display2) display1((oldIndex >> 5) & 31) = display0 display2((oldIndex >> 10) & 31) = display1 display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31) display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31) - } else - if (xor < (1 << 20)) { // level = 3 + } else if (xor < (1 << 20)) { // level = 3 display1 = copyOf(display1) display2 = copyOf(display2) display3 = copyOf(display3) @@ -996,8 +984,7 @@ private[immutable] trait VectorPointer[T] { display2 = nullSlotAndCopy(display3, (newIndex >> 15) & 31) display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31) display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31) - } else - if (xor < (1 << 25)) { // level = 4 + } else if (xor < (1 << 25)) { // level = 4 display1 = copyOf(display1) display2 = copyOf(display2) display3 = copyOf(display3) @@ -1010,8 +997,7 @@ private[immutable] trait VectorPointer[T] { display2 = nullSlotAndCopy(display3, (newIndex >> 15) & 31) display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31) display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31) - } else - if (xor < (1 << 30)) { // level = 5 + } else if (xor < (1 << 30)) { // level = 5 display1 = copyOf(display1) display2 = copyOf(display2) display3 = copyOf(display3) @@ -1027,7 +1013,7 @@ private[immutable] trait VectorPointer[T] { display2 = nullSlotAndCopy(display3, (newIndex >> 15) & 31) display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31) display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31) - } else { // level = 6 + } else { // level = 6 throw new IllegalArgumentException() } } @@ -1037,7 +1023,7 @@ private[immutable] trait VectorPointer[T] { private[immutable] final def copyRange(array: Array[AnyRef], oldLeft: Int, newLeft: Int) = { val elems = new Array[AnyRef](32) - java.lang.System.arraycopy(array, oldLeft, elems, newLeft, 32 - math.max(newLeft,oldLeft)) + java.lang.System.arraycopy(array, oldLeft, elems, newLeft, 32 - math.max(newLeft, oldLeft)) elems } @@ -1048,43 +1034,40 @@ private[immutable] trait VectorPointer[T] { // requires structure is clean and at pos oldIndex, // ensures structure is dirty and at pos newIndex and writable at level 0 private[immutable] final def gotoFreshPosWritable0(oldIndex: Int, newIndex: Int, xor: Int): Unit = { // goto block start pos - if (xor < (1 << 5)) { // level = 0 - } else - if (xor < (1 << 10)) { // level = 1 + if (xor < (1 << 5)) { // level = 0 + // we're already at the block start + } else if (xor < (1 << 10)) { // level = 1 if (depth == 1) { display1 = new Array(32) display1((oldIndex >> 5) & 31) = display0 - depth +=1 + depth += 1 } display0 = new Array(32) - } else - if (xor < (1 << 15)) { // level = 2 + } else if (xor < (1 << 15)) { // level = 2 if (depth == 2) { display2 = new Array(32) display2((oldIndex >> 10) & 31) = display1 - depth +=1 + depth += 1 } display1 = display2((newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] if (display1 == null) display1 = new Array(32) display0 = new Array(32) - } else - if (xor < (1 << 20)) { // level = 3 + } else if (xor < (1 << 20)) { // level = 3 if (depth == 3) { display3 = new Array(32) display3((oldIndex >> 15) & 31) = display2 - depth +=1 + depth += 1 } display2 = display3((newIndex >> 15) & 31).asInstanceOf[Array[AnyRef]] if (display2 == null) display2 = new Array(32) display1 = display2((newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] if (display1 == null) display1 = new Array(32) display0 = new Array(32) - } else - if (xor < (1 << 25)) { // level = 4 + } else if (xor < (1 << 25)) { // level = 4 if (depth == 4) { display4 = new Array(32) display4((oldIndex >> 20) & 31) = display3 - depth +=1 + depth += 1 } display3 = display4((newIndex >> 20) & 31).asInstanceOf[Array[AnyRef]] if (display3 == null) display3 = new Array(32) @@ -1093,12 +1076,11 @@ private[immutable] trait VectorPointer[T] { display1 = display2((newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] if (display1 == null) display1 = new Array(32) display0 = new Array(32) - } else - if (xor < (1 << 30)) { // level = 5 + } else if (xor < (1 << 30)) { // level = 5 if (depth == 5) { display5 = new Array(32) - display5((oldIndex >> 25) & 31) = display4 - depth +=1 + display5((oldIndex >> 25) & 31) = display4 + depth += 1 } display4 = display5((newIndex >> 25) & 31).asInstanceOf[Array[AnyRef]] if (display4 == null) display4 = new Array(32) @@ -1109,7 +1091,7 @@ private[immutable] trait VectorPointer[T] { display1 = display2((newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] if (display1 == null) display1 = new Array(32) display0 = new Array(32) - } else { // level = 6 + } else { // level = 6 throw new IllegalArgumentException() } } -- cgit v1.2.3