From f4ae496f920d49d120f7453d2599740bf249287a Mon Sep 17 00:00:00 2001 From: Pap Lőrinc Date: Fri, 18 Nov 2016 15:37:39 +0200 Subject: Removed redundant casts from Vector --- .../scala/collection/immutable/Vector.scala | 58 +++++++++++----------- 1 file changed, 29 insertions(+), 29 deletions(-) diff --git a/src/library/scala/collection/immutable/Vector.scala b/src/library/scala/collection/immutable/Vector.scala index d9d925705f..1d713e3e59 100644 --- a/src/library/scala/collection/immutable/Vector.scala +++ b/src/library/scala/collection/immutable/Vector.scala @@ -1020,29 +1020,29 @@ private[immutable] trait VectorPointer[T] { private[immutable] final def gotoPosWritable0(newIndex: Int, xor: Int): Unit = (depth - 1) match { case 5 => display5 = copyOf(display5) - display4 = nullSlotAndCopy(display5, (newIndex >> 25) & 31).asInstanceOf[Array[AnyRef]] - display3 = nullSlotAndCopy(display4, (newIndex >> 20) & 31).asInstanceOf[Array[AnyRef]] - display2 = nullSlotAndCopy(display3, (newIndex >> 15) & 31).asInstanceOf[Array[AnyRef]] - display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31).asInstanceOf[Array[AnyRef]] + display4 = nullSlotAndCopy(display5, (newIndex >> 25) & 31) + display3 = nullSlotAndCopy(display4, (newIndex >> 20) & 31) + display2 = nullSlotAndCopy(display3, (newIndex >> 15) & 31) + display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31) + display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31) case 4 => display4 = copyOf(display4) - display3 = nullSlotAndCopy(display4, (newIndex >> 20) & 31).asInstanceOf[Array[AnyRef]] - display2 = nullSlotAndCopy(display3, (newIndex >> 15) & 31).asInstanceOf[Array[AnyRef]] - display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31).asInstanceOf[Array[AnyRef]] + display3 = nullSlotAndCopy(display4, (newIndex >> 20) & 31) + display2 = nullSlotAndCopy(display3, (newIndex >> 15) & 31) + display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31) + display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31) case 3 => display3 = copyOf(display3) - display2 = nullSlotAndCopy(display3, (newIndex >> 15) & 31).asInstanceOf[Array[AnyRef]] - display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31).asInstanceOf[Array[AnyRef]] + display2 = nullSlotAndCopy(display3, (newIndex >> 15) & 31) + display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31) + display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31) case 2 => display2 = copyOf(display2) - display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31).asInstanceOf[Array[AnyRef]] + display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31) + display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31) case 1 => display1 = copyOf(display1) - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31).asInstanceOf[Array[AnyRef]] + display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31) case 0 => display0 = copyOf(display0) } @@ -1064,8 +1064,8 @@ private[immutable] trait VectorPointer[T] { display2 = copyOf(display2) display1((oldIndex >> 5) & 31) = display0 display2((oldIndex >> 10) & 31) = display1 - display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31).asInstanceOf[Array[AnyRef]] + display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31) + display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31) } else if (xor < (1 << 20)) { // level = 3 display1 = copyOf(display1) @@ -1074,9 +1074,9 @@ private[immutable] trait VectorPointer[T] { display1((oldIndex >> 5) & 31) = display0 display2((oldIndex >> 10) & 31) = display1 display3((oldIndex >> 15) & 31) = display2 - display2 = nullSlotAndCopy(display3, (newIndex >> 15) & 31).asInstanceOf[Array[AnyRef]] - display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31).asInstanceOf[Array[AnyRef]] + 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 display1 = copyOf(display1) @@ -1087,10 +1087,10 @@ private[immutable] trait VectorPointer[T] { display2((oldIndex >> 10) & 31) = display1 display3((oldIndex >> 15) & 31) = display2 display4((oldIndex >> 20) & 31) = display3 - display3 = nullSlotAndCopy(display4, (newIndex >> 20) & 31).asInstanceOf[Array[AnyRef]] - display2 = nullSlotAndCopy(display3, (newIndex >> 15) & 31).asInstanceOf[Array[AnyRef]] - display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31).asInstanceOf[Array[AnyRef]] + display3 = nullSlotAndCopy(display4, (newIndex >> 20) & 31) + 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 display1 = copyOf(display1) @@ -1103,11 +1103,11 @@ private[immutable] trait VectorPointer[T] { display3((oldIndex >> 15) & 31) = display2 display4((oldIndex >> 20) & 31) = display3 display5((oldIndex >> 25) & 31) = display4 - display4 = nullSlotAndCopy(display5, (newIndex >> 25) & 31).asInstanceOf[Array[AnyRef]] - display3 = nullSlotAndCopy(display4, (newIndex >> 20) & 31).asInstanceOf[Array[AnyRef]] - display2 = nullSlotAndCopy(display3, (newIndex >> 15) & 31).asInstanceOf[Array[AnyRef]] - display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31).asInstanceOf[Array[AnyRef]] + display4 = nullSlotAndCopy(display5, (newIndex >> 25) & 31) + display3 = nullSlotAndCopy(display4, (newIndex >> 20) & 31) + display2 = nullSlotAndCopy(display3, (newIndex >> 15) & 31) + display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31) + display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31) } else { // level = 6 throw new IllegalArgumentException() } -- cgit v1.2.3 From 6af55b027122f7c2d7d9f9a2c7bfcfd913cce5ae Mon Sep 17 00:00:00 2001 From: Pap Lőrinc Date: Fri, 18 Nov 2016 15:41:39 +0200 Subject: Unified masks in Vector --- .../scala/collection/immutable/Vector.scala | 62 +++++++++++----------- 1 file changed, 31 insertions(+), 31 deletions(-) diff --git a/src/library/scala/collection/immutable/Vector.scala b/src/library/scala/collection/immutable/Vector.scala index 1d713e3e59..4c853cccd9 100644 --- a/src/library/scala/collection/immutable/Vector.scala +++ b/src/library/scala/collection/immutable/Vector.scala @@ -253,7 +253,7 @@ override def companion: GenericCompanion[Vector] = Vector s.initFrom(this) s.dirty = dirty s.gotoPosWritable(focus, idx, focus ^ idx) // if dirty commit changes; go to new pos and prepare for writing - s.display0(idx & 0x1f) = elem.asInstanceOf[AnyRef] + s.display0(idx & 31) = elem.asInstanceOf[AnyRef] s } @@ -519,33 +519,33 @@ override def companion: GenericCompanion[Vector] = Vector zeroLeft(display0, cutIndex) } else if (cutIndex < (1 << 10)) { - zeroLeft(display0, cutIndex & 0x1f) + zeroLeft(display0, cutIndex & 31) display1 = copyRight(display1, (cutIndex >>> 5)) } else if (cutIndex < (1 << 15)) { - zeroLeft(display0, cutIndex & 0x1f) - display1 = copyRight(display1, (cutIndex >>> 5) & 0x1f) + zeroLeft(display0, cutIndex & 31) + display1 = copyRight(display1, (cutIndex >>> 5) & 31) display2 = copyRight(display2, (cutIndex >>> 10)) } else if (cutIndex < (1 << 20)) { - zeroLeft(display0, cutIndex & 0x1f) - display1 = copyRight(display1, (cutIndex >>> 5) & 0x1f) - display2 = copyRight(display2, (cutIndex >>> 10) & 0x1f) + 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)) { - zeroLeft(display0, cutIndex & 0x1f) - display1 = copyRight(display1, (cutIndex >>> 5) & 0x1f) - display2 = copyRight(display2, (cutIndex >>> 10) & 0x1f) - display3 = copyRight(display3, (cutIndex >>> 15) & 0x1f) + 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)) { - zeroLeft(display0, cutIndex & 0x1f) - display1 = copyRight(display1, (cutIndex >>> 5) & 0x1f) - display2 = copyRight(display2, (cutIndex >>> 10) & 0x1f) - display3 = copyRight(display3, (cutIndex >>> 15) & 0x1f) - display4 = copyRight(display4, (cutIndex >>> 20) & 0x1f) + 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)) } else { throw new IllegalArgumentException() @@ -562,33 +562,33 @@ override def companion: GenericCompanion[Vector] = Vector zeroRight(display0, cutIndex) } else if (cutIndex <= (1 << 10)) { - zeroRight(display0, ((cutIndex-1) & 0x1f) + 1) + zeroRight(display0, ((cutIndex-1) & 31) + 1) display1 = copyLeft(display1, (cutIndex >>> 5)) } else if (cutIndex <= (1 << 15)) { - zeroRight(display0, ((cutIndex-1) & 0x1f) + 1) - display1 = copyLeft(display1, (((cutIndex-1) >>> 5) & 0x1f) + 1) + 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) & 0x1f) + 1) - display1 = copyLeft(display1, (((cutIndex-1) >>> 5) & 0x1f) + 1) - display2 = copyLeft(display2, (((cutIndex-1) >>> 10) & 0x1f) + 1) + 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) & 0x1f) + 1) - display1 = copyLeft(display1, (((cutIndex-1) >>> 5) & 0x1f) + 1) - display2 = copyLeft(display2, (((cutIndex-1) >>> 10) & 0x1f) + 1) - display3 = copyLeft(display3, (((cutIndex-1) >>> 15) & 0x1f) + 1) + 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) & 0x1f) + 1) - display1 = copyLeft(display1, (((cutIndex-1) >>> 5) & 0x1f) + 1) - display2 = copyLeft(display2, (((cutIndex-1) >>> 10) & 0x1f) + 1) - display3 = copyLeft(display3, (((cutIndex-1) >>> 15) & 0x1f) + 1) - display4 = copyLeft(display4, (((cutIndex-1) >>> 20) & 0x1f) + 1) + 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() -- cgit v1.2.3 From fd338a7526d940611b04667f404ec59a0adc30ed Mon Sep 17 00:00:00 2001 From: Pap Lőrinc Date: Tue, 22 Nov 2016 23:50:23 +0200 Subject: Deleted leftover debug method from Vector --- bincompat-backward.whitelist.conf | 16 +++++++++ .../scala/collection/immutable/Vector.scala | 38 ---------------------- 2 files changed, 16 insertions(+), 38 deletions(-) diff --git a/bincompat-backward.whitelist.conf b/bincompat-backward.whitelist.conf index 6e260872c9..01777bc4ed 100644 --- a/bincompat-backward.whitelist.conf +++ b/bincompat-backward.whitelist.conf @@ -5,6 +5,22 @@ filter { # "scala.reflect.runtime" ] problems=[ + { + matchName="scala.collection.immutable.Vector.debug" + problemName=DirectMissingMethodProblem + }, + { + matchName="scala.collection.immutable.VectorBuilder.debug" + problemName=DirectMissingMethodProblem + }, + { + matchName="scala.collection.immutable.VectorPointer.debug" + problemName=DirectMissingMethodProblem + }, + { + matchName="scala.collection.immutable.VectorIterator.debug" + problemName=DirectMissingMethodProblem + }, { matchName="scala.reflect.runtime.JavaMirrors#JavaMirror.unpickleClass" problemName=IncompatibleMethTypeProblem diff --git a/src/library/scala/collection/immutable/Vector.scala b/src/library/scala/collection/immutable/Vector.scala index 4c853cccd9..295ef490db 100644 --- a/src/library/scala/collection/immutable/Vector.scala +++ b/src/library/scala/collection/immutable/Vector.scala @@ -293,7 +293,6 @@ override def companion: GenericCompanion[Vector] = Vector //println("----- appendFront " + value + " at " + (startIndex - 1) + " reached block start") if (shift != 0) { // case A: we can shift right on the top level - debug() //println("shifting right by " + shiftBlocks + " at level " + (depth-1) + " (had "+freeSpace+" free space)") if (depth > 1) { @@ -303,7 +302,6 @@ override def companion: GenericCompanion[Vector] = Vector s.initFrom(this) s.dirty = dirty s.shiftTopLevel(0, shiftBlocks) // shift right by n blocks - s.debug() s.gotoFreshPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex) // maybe create pos; prepare for writing s.display0(lo) = value.asInstanceOf[AnyRef] //assert(depth == s.depth) @@ -321,7 +319,6 @@ override def companion: GenericCompanion[Vector] = Vector 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.debug() s } } else if (blockIndex < 0) { @@ -336,10 +333,8 @@ override def companion: GenericCompanion[Vector] = Vector val s = new Vector(startIndex - 1 + move, endIndex + move, newBlockIndex) s.initFrom(this) s.dirty = dirty - s.debug() s.gotoFreshPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex) // could optimize: we know it will create a whole branch s.display0(lo) = value.asInstanceOf[AnyRef] - s.debug() //assert(s.depth == depth+1) s } else { @@ -389,7 +384,6 @@ override def companion: GenericCompanion[Vector] = Vector //println("----- appendBack " + value + " at " + endIndex + " reached block end") if (shift != 0) { - debug() //println("shifting left by " + shiftBlocks + " at level " + (depth-1) + " (had "+startIndex+" free space)") if (depth > 1) { val newBlockIndex = blockIndex - shift @@ -398,10 +392,8 @@ override def companion: GenericCompanion[Vector] = Vector s.initFrom(this) s.dirty = dirty s.shiftTopLevel(shiftBlocks, 0) // shift left by n blocks - s.debug() s.gotoFreshPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex) s.display0(lo) = value.asInstanceOf[AnyRef] - s.debug() //assert(depth == s.depth) s } else { @@ -417,7 +409,6 @@ override def companion: GenericCompanion[Vector] = Vector s.shiftTopLevel(shiftBlocks, 0) // shift right by n elements s.gotoPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex) s.display0(32 - shift) = value.asInstanceOf[AnyRef] - s.debug() s } } else { @@ -430,10 +421,6 @@ override def companion: GenericCompanion[Vector] = Vector s.gotoFreshPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex) s.display0(lo) = value.asInstanceOf[AnyRef] //assert(s.depth == depth+1) might or might not create new level! - if (s.depth == depth+1) { - //println("creating new level " + s.depth + " (had "+0+" free space)") - s.debug() - } s } } @@ -1205,30 +1192,5 @@ private[immutable] trait VectorPointer[T] { stabilize(oldIndex) gotoFreshPosWritable0(oldIndex, newIndex, xor) } - - - - - // DEBUG STUFF - - private[immutable] def debug(): Unit = { - return -/* - //println("DISPLAY 5: " + display5 + " ---> " + (if (display5 ne null) display5.map(x=> if (x eq null) "." else x + "->" +x.asInstanceOf[Array[AnyRef]].mkString("")).mkString(" ") else "null")) - //println("DISPLAY 4: " + display4 + " ---> " + (if (display4 ne null) display4.map(x=> if (x eq null) "." else x + "->" +x.asInstanceOf[Array[AnyRef]].mkString("")).mkString(" ") else "null")) - //println("DISPLAY 3: " + display3 + " ---> " + (if (display3 ne null) display3.map(x=> if (x eq null) "." else x + "->" +x.asInstanceOf[Array[AnyRef]].mkString("")).mkString(" ") else "null")) - //println("DISPLAY 2: " + display2 + " ---> " + (if (display2 ne null) display2.map(x=> if (x eq null) "." else x + "->" +x.asInstanceOf[Array[AnyRef]].mkString("")).mkString(" ") else "null")) - //println("DISPLAY 1: " + display1 + " ---> " + (if (display1 ne null) display1.map(x=> if (x eq null) "." else x + "->" +x.asInstanceOf[Array[AnyRef]].mkString("")).mkString(" ") else "null")) - //println("DISPLAY 0: " + display0 + " ---> " + (if (display0 ne null) display0.map(x=> if (x eq null) "." else x.toString).mkString(" ") else "null")) -*/ - //println("DISPLAY 5: " + (if (display5 ne null) display5.map(x=> if (x eq null) "." else x.asInstanceOf[Array[AnyRef]].deepMkString("[","","]")).mkString(" ") else "null")) - //println("DISPLAY 4: " + (if (display4 ne null) display4.map(x=> if (x eq null) "." else x.asInstanceOf[Array[AnyRef]].deepMkString("[","","]")).mkString(" ") else "null")) - //println("DISPLAY 3: " + (if (display3 ne null) display3.map(x=> if (x eq null) "." else x.asInstanceOf[Array[AnyRef]].deepMkString("[","","]")).mkString(" ") else "null")) - //println("DISPLAY 2: " + (if (display2 ne null) display2.map(x=> if (x eq null) "." else x.asInstanceOf[Array[AnyRef]].deepMkString("[","","]")).mkString(" ") else "null")) - //println("DISPLAY 1: " + (if (display1 ne null) display1.map(x=> if (x eq null) "." else x.asInstanceOf[Array[AnyRef]].deepMkString("[","","]")).mkString(" ") else "null")) - //println("DISPLAY 0: " + (if (display0 ne null) display0.map(x=> if (x eq null) "." else x.toString).mkString(" ") else "null")) - } - - } -- cgit v1.2.3 From 95a29f2ab3c2d5e52624720c375ef8977516a9fc Mon Sep 17 00:00:00 2001 From: Pap Lőrinc Date: Fri, 18 Nov 2016 18:02:48 +0200 Subject: Deleted leftover code-comments from Vector --- .../scala/collection/immutable/Vector.scala | 113 ++++----------------- 1 file changed, 20 insertions(+), 93 deletions(-) diff --git a/src/library/scala/collection/immutable/Vector.scala b/src/library/scala/collection/immutable/Vector.scala index 295ef490db..fa74e735ef 100644 --- a/src/library/scala/collection/immutable/Vector.scala +++ b/src/library/scala/collection/immutable/Vector.scala @@ -23,7 +23,7 @@ object Vector extends IndexedSeqFactory[Vector] { ReusableCBF.asInstanceOf[GenericCanBuildFrom[A]] private[immutable] val NIL = new Vector[Nothing](0, 0, 0) override def empty[A]: Vector[A] = NIL - + // Constants governing concat strategy for performance private final val Log2ConcatFaster = 5 private final val TinyAppendFaster = 2 @@ -71,12 +71,7 @@ extends AbstractSeq[A] with CustomParallelizable[A, ParVector[A]] { self => -override def companion: GenericCompanion[Vector] = Vector - - //assert(startIndex >= 0, startIndex+"<0") - //assert(startIndex <= endIndex, startIndex+">"+endIndex) - //assert(focus >= 0, focus+"<0") - //assert(focus <= endIndex, focus+">"+endIndex) + override def companion: GenericCompanion[Vector] = Vector private[immutable] var dirty = false @@ -100,8 +95,6 @@ override def companion: GenericCompanion[Vector] = Vector s } - - // can still be improved override /*SeqLike*/ def reverseIterator: Iterator[A] = new AbstractIterator[A] { private var i = self.length @@ -113,16 +106,12 @@ override def companion: GenericCompanion[Vector] = Vector } else Iterator.empty.next() } - // TODO: reverse - - // TODO: check performance of foreach/map etc. should override or not? // Ideally, clients will inline calls to map all the way down, including the iterator/builder methods. // In principle, escape analysis could even remove the iterator/builder allocations and do it // with local variables exclusively. But we're not quite there yet ... def apply(index: Int): A = { val idx = checkRangeConvert(index) - //println("get elem: "+index + "/"+idx + "(focus:" +focus+" xor:"+(idx^focus)+" depth:"+depth+")") getElem(idx, idx ^ focus) } @@ -137,7 +126,7 @@ override def companion: GenericCompanion[Vector] = Vector // If we have a default builder, there are faster ways to perform some operations @inline private[this] def isDefaultCBF[A, B, That](bf: CanBuildFrom[Vector[A], B, That]): Boolean = (bf eq IndexedSeq.ReusableCBF) || (bf eq collection.immutable.Seq.ReusableCBF) || (bf eq collection.Seq.ReusableCBF) - + // SeqLike api override def updated[B >: A, That](index: Int, elem: B)(implicit bf: CanBuildFrom[Vector[A], B, That]): That = @@ -227,7 +216,7 @@ override def companion: GenericCompanion[Vector] = Vector val again = if (!that.isTraversableAgain) that.toVector else that.seq again.size match { // Often it's better to append small numbers of elements (or prepend if RHS is a vector) - case n if n <= TinyAppendFaster || n < (this.size >> Log2ConcatFaster) => + case n if n <= TinyAppendFaster || n < (this.size >> Log2ConcatFaster) => var v: Vector[B] = this for (x <- again) v = v :+ x v.asInstanceOf[That] @@ -243,8 +232,6 @@ override def companion: GenericCompanion[Vector] = Vector else super.++(that.seq) } - - // semi-private api private[immutable] def updateAt[B >: A](index: Int, elem: B): Vector[B] = { @@ -257,7 +244,6 @@ override def companion: GenericCompanion[Vector] = Vector s } - private def gotoPosWritable(oldIndex: Int, newIndex: Int, xor: Int) = if (dirty) { gotoPosWritable1(oldIndex, newIndex, xor) } else { @@ -286,33 +272,27 @@ override def companion: GenericCompanion[Vector] = Vector 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 - //println("----- appendFront " + value + " at " + (startIndex - 1) + " reached block start") if (shift != 0) { // case A: we can shift right on the top level - //println("shifting right by " + shiftBlocks + " at level " + (depth-1) + " (had "+freeSpace+" free space)") - if (depth > 1) { val newBlockIndex = blockIndex + shift val newFocus = focus + shift + val s = new Vector(startIndex - 1 + shift, endIndex + shift, newBlockIndex) s.initFrom(this) s.dirty = dirty s.shiftTopLevel(0, shiftBlocks) // shift right by n blocks s.gotoFreshPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex) // maybe create pos; prepare for writing s.display0(lo) = value.asInstanceOf[AnyRef] - //assert(depth == s.depth) s } else { val newBlockIndex = blockIndex + 32 val newFocus = focus - //assert(newBlockIndex == 0) - //assert(newFocus == 0) - val s = new Vector(startIndex - 1 + shift, endIndex + shift, newBlockIndex) s.initFrom(this) s.dirty = dirty @@ -323,19 +303,15 @@ override def companion: GenericCompanion[Vector] = Vector } } else if (blockIndex < 0) { // case B: we need to move the whole structure - val move = (1 << 5*(depth+1)) - (1 << 5*(depth)) - //println("moving right by " + move + " at level " + (depth-1) + " (had "+freeSpace+" free space)") - + val move = (1 << (5 * (depth + 1))) - (1 << (5 * depth)) val newBlockIndex = blockIndex + move val newFocus = focus + move - val s = new Vector(startIndex - 1 + move, endIndex + move, newBlockIndex) s.initFrom(this) s.dirty = dirty s.gotoFreshPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex) // could optimize: we know it will create a whole branch s.display0(lo) = value.asInstanceOf[AnyRef] - //assert(s.depth == depth+1) s } else { val newBlockIndex = blockIndex @@ -346,10 +322,8 @@ override def companion: GenericCompanion[Vector] = Vector s.dirty = dirty s.gotoFreshPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex) s.display0(lo) = value.asInstanceOf[AnyRef] - //assert(s.depth == depth) s } - } } else { // empty vector, just insert single element at the back @@ -363,14 +337,11 @@ override def companion: GenericCompanion[Vector] = Vector } private[immutable] def appendBack[B>:A](value: B): Vector[B] = { -// //println("------- append " + value) -// debug() if (endIndex != startIndex) { val blockIndex = endIndex & ~31 val lo = endIndex & 31 if (endIndex != blockIndex) { - //println("will make writable block (from "+focus+") at: " + blockIndex) val s = new Vector(startIndex, endIndex + 1, blockIndex) s.initFrom(this) s.dirty = dirty @@ -378,13 +349,10 @@ override def companion: GenericCompanion[Vector] = Vector s.display0(lo) = value.asInstanceOf[AnyRef] s } else { - val shift = startIndex & ~((1<<5*(depth-1))-1) - val shiftBlocks = startIndex >>> 5*(depth-1) - - //println("----- appendBack " + value + " at " + endIndex + " reached block end") + val shift = startIndex & ~((1 << 5 * (depth - 1)) - 1) + val shiftBlocks = startIndex >>> 5 * (depth - 1) if (shift != 0) { - //println("shifting left by " + shiftBlocks + " at level " + (depth-1) + " (had "+startIndex+" free space)") if (depth > 1) { val newBlockIndex = blockIndex - shift val newFocus = focus - shift @@ -394,15 +362,10 @@ override def companion: GenericCompanion[Vector] = Vector s.shiftTopLevel(shiftBlocks, 0) // shift left by n blocks s.gotoFreshPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex) s.display0(lo) = value.asInstanceOf[AnyRef] - //assert(depth == s.depth) s } else { val newBlockIndex = blockIndex - 32 val newFocus = focus - - //assert(newBlockIndex == 0) - //assert(newFocus == 0) - val s = new Vector(startIndex - shift, endIndex + 1 - shift, newBlockIndex) s.initFrom(this) s.dirty = dirty @@ -420,7 +383,6 @@ override def companion: GenericCompanion[Vector] = Vector s.dirty = dirty s.gotoFreshPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex) s.display0(lo) = value.asInstanceOf[AnyRef] - //assert(s.depth == depth+1) might or might not create new level! s } } @@ -461,8 +423,6 @@ override def companion: GenericCompanion[Vector] = Vector } private def copyLeft(array: Array[AnyRef], right: Int): Array[AnyRef] = { -// if (array eq null) -// println("OUCH!!! " + right + "/" + depth + "/"+startIndex + "/" + endIndex + "/" + focus) val a2 = new Array[AnyRef](array.length) java.lang.System.arraycopy(array, 0, a2, 0, right) a2 @@ -583,7 +543,7 @@ override def companion: GenericCompanion[Vector] = Vector } private def requiredDepth(xor: Int) = { - if (xor < (1 << 5)) 1 + if (xor < (1 << 5)) 1 else if (xor < (1 << 10)) 2 else if (xor < (1 << 15)) 3 else if (xor < (1 << 20)) 4 @@ -596,20 +556,7 @@ override def companion: GenericCompanion[Vector] = Vector val blockIndex = cutIndex & ~31 val xor = cutIndex ^ (endIndex - 1) val d = requiredDepth(xor) - val shift = (cutIndex & ~((1 << (5*d))-1)) - - //println("cut front at " + cutIndex + ".." + endIndex + " (xor: "+xor+" shift: " + shift + " d: " + d +")") - -/* - val s = new Vector(cutIndex-shift, endIndex-shift, blockIndex-shift) - s.initFrom(this) - if (s.depth > 1) - s.gotoPos(blockIndex, focus ^ blockIndex) - s.depth = d - s.stabilize(blockIndex-shift) - s.cleanLeftEdge(cutIndex-shift) - s -*/ + val shift = (cutIndex & ~((1 << (5 * d)) - 1)) // need to init with full display iff going to cutIndex requires swapping block at level >= d @@ -626,13 +573,8 @@ override def companion: GenericCompanion[Vector] = Vector 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)) -/* - println("cut back at " + startIndex + ".." + cutIndex + " (xor: "+xor+" d: " + d +")") - if (cutIndex == blockIndex + 32) - println("OUCH!!!") -*/ val s = new Vector(startIndex-shift, cutIndex-shift, blockIndex-shift) s.initFrom(this) s.dirty = dirty @@ -641,14 +583,12 @@ override def companion: GenericCompanion[Vector] = Vector s.cleanRightEdge(cutIndex-shift) s } - } - class VectorIterator[+A](_startIndex: Int, endIndex: Int) -extends AbstractIterator[A] - with Iterator[A] - with VectorPointer[A @uncheckedVariance] { + extends AbstractIterator[A] + with Iterator[A] + with VectorPointer[A @uncheckedVariance] { private var blockIndex: Int = _startIndex & ~31 private var lo: Int = _startIndex & 31 @@ -739,7 +679,6 @@ final class VectorBuilder[A]() extends ReusableBuilder[A,Vector[A]] with VectorP } - private[immutable] trait VectorPointer[T] { private[immutable] var depth: Int = _ private[immutable] var display0: Array[AnyRef] = _ @@ -819,7 +758,7 @@ private[immutable] trait VectorPointer[T] { if (xor < (1 << 5)) { // level = 0 (could maybe removed) } else if (xor < (1 << 10)) { // level = 1 - display0 = display1((index >> 5) & 31).asInstanceOf[Array[AnyRef]] + display0 = display1((index >> 5) & 31).asInstanceOf[Array[AnyRef]] } else if (xor < (1 << 15)) { // level = 2 display1 = display2((index >> 10) & 31).asInstanceOf[Array[AnyRef]] @@ -847,14 +786,12 @@ private[immutable] trait VectorPointer[T] { } } - - // USED BY ITERATOR // xor: oldIndex ^ index private[immutable] final def gotoNextBlockStart(index: Int, xor: Int): Unit = { // goto block start pos if (xor < (1 << 10)) { // level = 1 - display0 = display1((index >> 5) & 31).asInstanceOf[Array[AnyRef]] + display0 = display1((index >> 5) & 31).asInstanceOf[Array[AnyRef]] } else if (xor < (1 << 15)) { // level = 2 display1 = display2((index >> 10) & 31).asInstanceOf[Array[AnyRef]] @@ -935,8 +872,6 @@ private[immutable] trait VectorPointer[T] { } } - - // STUFF BELOW USED BY APPEND / UPDATE private[immutable] final def copyOf(a: Array[AnyRef]) = { @@ -946,13 +881,11 @@ private[immutable] trait VectorPointer[T] { } private[immutable] final def nullSlotAndCopy(array: Array[AnyRef], index: Int) = { - //println("copy and null") val x = array(index) array(index) = null copyOf(x.asInstanceOf[Array[AnyRef]]) } - // make sure there is no aliasing // requires structure is at pos index // ensures structure is clean and at pos index and writable at all levels except 0 @@ -997,7 +930,6 @@ private[immutable] trait VectorPointer[T] { } - /// USED IN UPDATE AND APPEND BACK // prepare for writing at an existing position @@ -1110,8 +1042,6 @@ private[immutable] trait VectorPointer[T] { } - - // USED IN APPEND // create a new block at the bottom level (and possibly nodes on its path) and prepares for writing @@ -1119,7 +1049,6 @@ private[immutable] trait VectorPointer[T] { // 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 - //println("XXX clean with low xor") } else if (xor < (1 << 10)) { // level = 1 if (depth == 1) { @@ -1185,12 +1114,10 @@ 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 gotoFreshPosWritable1(oldIndex: Int, newIndex: Int, xor: Int): Unit = { stabilize(oldIndex) gotoFreshPosWritable0(oldIndex, newIndex, xor) } -} - +} \ No newline at end of file -- cgit v1.2.3 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 From e06d383727161702a551a6a0fc248fc1aef93e61 Mon Sep 17 00:00:00 2001 From: Pap Lőrinc Date: Wed, 23 Nov 2016 00:56:26 +0200 Subject: Changed >> to >>> in Vector to unify style Unified, since indices are always positive and unsigned shift was already used in other places --- .../scala/collection/immutable/Vector.scala | 236 ++++++++++----------- 1 file changed, 118 insertions(+), 118 deletions(-) diff --git a/src/library/scala/collection/immutable/Vector.scala b/src/library/scala/collection/immutable/Vector.scala index 034691aea2..843fc9af55 100644 --- a/src/library/scala/collection/immutable/Vector.scala +++ b/src/library/scala/collection/immutable/Vector.scala @@ -117,7 +117,7 @@ extends AbstractSeq[A] private def checkRangeConvert(index: Int) = { val idx = index + startIndex - if (0 <= index && idx < endIndex) + if (index >= 0 && idx < endIndex) idx else throw new IndexOutOfBoundsException(index.toString) @@ -221,11 +221,11 @@ extends AbstractSeq[A] val again = if (!that.isTraversableAgain) that.toVector else that.seq again.size match { // Often it's better to append small numbers of elements (or prepend if RHS is a vector) - case n if n <= TinyAppendFaster || n < (this.size >> Log2ConcatFaster) => + case n if n <= TinyAppendFaster || n < (this.size >>> Log2ConcatFaster) => var v: Vector[B] = this for (x <- again) v = v :+ x v.asInstanceOf[That] - case n if this.size < (n >> Log2ConcatFaster) && again.isInstanceOf[Vector[_]] => + case n if this.size < (n >>> Log2ConcatFaster) && again.isInstanceOf[Vector[_]] => var v = again.asInstanceOf[Vector[B]] val ri = this.reverseIterator while (ri.hasNext) v = ri.next +: v @@ -730,15 +730,15 @@ private[immutable] trait VectorPointer[T] { 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] + 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] + 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] + 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] + 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] + 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 throw new IllegalArgumentException() } @@ -751,25 +751,25 @@ private[immutable] trait VectorPointer[T] { 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]] + display0 = display1((index >>> 5) & 31).asInstanceOf[Array[AnyRef]] } else if (xor < (1 << 15)) { // level = 2 - display1 = display2((index >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = display1((index >> 5) & 31).asInstanceOf[Array[AnyRef]] + display1 = display2((index >>> 10) & 31).asInstanceOf[Array[AnyRef]] + display0 = display1((index >>> 5) & 31).asInstanceOf[Array[AnyRef]] } 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]] + 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 - 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]] + 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 - 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]] + 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 throw new IllegalArgumentException() } @@ -780,21 +780,21 @@ 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 - display0 = display1((index >> 5) & 31).asInstanceOf[Array[AnyRef]] + display0 = display1((index >>> 5) & 31).asInstanceOf[Array[AnyRef]] } else if (xor < (1 << 15)) { // level = 2 - display1 = display2((index >> 10) & 31).asInstanceOf[Array[AnyRef]] + display1 = display2((index >>> 10) & 31).asInstanceOf[Array[AnyRef]] display0 = display1(0).asInstanceOf[Array[AnyRef]] } else if (xor < (1 << 20)) { // level = 3 - display2 = display3((index >> 15) & 31).asInstanceOf[Array[AnyRef]] + 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 - display3 = display4((index >> 20) & 31).asInstanceOf[Array[AnyRef]] + 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 - display4 = display5((index >> 25) & 31).asInstanceOf[Array[AnyRef]] + 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]] @@ -813,15 +813,15 @@ private[immutable] trait VectorPointer[T] { display1 = new Array(32); display1(0) = display0; depth += 1 } display0 = new Array(32) - display1((index >> 5) & 31) = display0 + display1((index >>> 5) & 31) = display0 } 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 + 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 @@ -829,9 +829,9 @@ private[immutable] trait VectorPointer[T] { 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 + 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 @@ -840,10 +840,10 @@ private[immutable] trait VectorPointer[T] { display1 = new Array(32) display2 = new Array(32) display3 = new Array(32) - display1((index >> 5) & 31) = display0 - display2((index >> 10) & 31) = display1 - display3((index >> 15) & 31) = display2 - display4((index >> 20) & 31) = display3 + display1((index >>> 5) & 31) = display0 + 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 @@ -853,11 +853,11 @@ private[immutable] trait VectorPointer[T] { display2 = new Array(32) display3 = new Array(32) display4 = new Array(32) - display1((index >> 5) & 31) = display0 - display2((index >> 10) & 31) = display1 - display3((index >> 15) & 31) = display2 - display4((index >> 20) & 31) = display3 - display5((index >> 25) & 31) = display4 + display1((index >>> 5) & 31) = display0 + display2((index >>> 10) & 31) = display1 + display3((index >>> 15) & 31) = display2 + display4((index >>> 20) & 31) = display3 + display5((index >>> 25) & 31) = display4 } else { // level = 6 throw new IllegalArgumentException() } @@ -888,35 +888,35 @@ private[immutable] trait VectorPointer[T] { display3 = copyOf(display3) display2 = copyOf(display2) display1 = copyOf(display1) - display5((index >> 25) & 31) = display4 - display4((index >> 20) & 31) = display3 - display3((index >> 15) & 31) = display2 - display2((index >> 10) & 31) = display1 - display1((index >> 5) & 31) = display0 + display5((index >>> 25) & 31) = display4 + display4((index >>> 20) & 31) = display3 + display3((index >>> 15) & 31) = display2 + display2((index >>> 10) & 31) = display1 + display1((index >>> 5) & 31) = display0 case 4 => display4 = copyOf(display4) display3 = copyOf(display3) display2 = copyOf(display2) display1 = copyOf(display1) - display4((index >> 20) & 31) = display3 - display3((index >> 15) & 31) = display2 - display2((index >> 10) & 31) = display1 - display1((index >> 5) & 31) = display0 + display4((index >>> 20) & 31) = display3 + display3((index >>> 15) & 31) = display2 + display2((index >>> 10) & 31) = display1 + display1((index >>> 5) & 31) = display0 case 3 => display3 = copyOf(display3) display2 = copyOf(display2) display1 = copyOf(display1) - display3((index >> 15) & 31) = display2 - display2((index >> 10) & 31) = display1 - display1((index >> 5) & 31) = display0 + display3((index >>> 15) & 31) = display2 + display2((index >>> 10) & 31) = display1 + display1((index >>> 5) & 31) = display0 case 2 => display2 = copyOf(display2) display1 = copyOf(display1) - display2((index >> 10) & 31) = display1 - display1((index >> 5) & 31) = display0 + display2((index >>> 10) & 31) = display1 + display1((index >>> 5) & 31) = display0 case 1 => display1 = copyOf(display1) - display1((index >> 5) & 31) = display0 + display1((index >>> 5) & 31) = display0 case 0 => } @@ -930,29 +930,29 @@ private[immutable] trait VectorPointer[T] { private[immutable] final def gotoPosWritable0(newIndex: Int, xor: Int): Unit = (depth - 1) match { case 5 => display5 = copyOf(display5) - display4 = nullSlotAndCopy(display5, (newIndex >> 25) & 31) - display3 = nullSlotAndCopy(display4, (newIndex >> 20) & 31) - display2 = nullSlotAndCopy(display3, (newIndex >> 15) & 31) - display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31) - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31) + display4 = nullSlotAndCopy(display5, (newIndex >>> 25) & 31) + display3 = nullSlotAndCopy(display4, (newIndex >>> 20) & 31) + display2 = nullSlotAndCopy(display3, (newIndex >>> 15) & 31) + display1 = nullSlotAndCopy(display2, (newIndex >>> 10) & 31) + display0 = nullSlotAndCopy(display1, (newIndex >>> 5) & 31) case 4 => display4 = copyOf(display4) - display3 = nullSlotAndCopy(display4, (newIndex >> 20) & 31) - display2 = nullSlotAndCopy(display3, (newIndex >> 15) & 31) - display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31) - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31) + display3 = nullSlotAndCopy(display4, (newIndex >>> 20) & 31) + display2 = nullSlotAndCopy(display3, (newIndex >>> 15) & 31) + display1 = nullSlotAndCopy(display2, (newIndex >>> 10) & 31) + display0 = nullSlotAndCopy(display1, (newIndex >>> 5) & 31) case 3 => display3 = copyOf(display3) - display2 = nullSlotAndCopy(display3, (newIndex >> 15) & 31) - display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31) - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31) + display2 = nullSlotAndCopy(display3, (newIndex >>> 15) & 31) + display1 = nullSlotAndCopy(display2, (newIndex >>> 10) & 31) + display0 = nullSlotAndCopy(display1, (newIndex >>> 5) & 31) case 2 => display2 = copyOf(display2) - display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31) - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31) + display1 = nullSlotAndCopy(display2, (newIndex >>> 10) & 31) + display0 = nullSlotAndCopy(display1, (newIndex >>> 5) & 31) case 1 => display1 = copyOf(display1) - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31) + display0 = nullSlotAndCopy(display1, (newIndex >>> 5) & 31) case 0 => display0 = copyOf(display0) } @@ -965,54 +965,54 @@ private[immutable] trait VectorPointer[T] { display0 = copyOf(display0) } else if (xor < (1 << 10)) { // level = 1 display1 = copyOf(display1) - display1((oldIndex >> 5) & 31) = display0 - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31) + display1((oldIndex >>> 5) & 31) = display0 + display0 = nullSlotAndCopy(display1, (newIndex >>> 5) & 31) } 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) + 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 display1 = copyOf(display1) display2 = copyOf(display2) display3 = copyOf(display3) - display1((oldIndex >> 5) & 31) = display0 - display2((oldIndex >> 10) & 31) = display1 - display3((oldIndex >> 15) & 31) = display2 - display2 = nullSlotAndCopy(display3, (newIndex >> 15) & 31) - display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31) - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31) + display1((oldIndex >>> 5) & 31) = display0 + display2((oldIndex >>> 10) & 31) = display1 + display3((oldIndex >>> 15) & 31) = display2 + 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 display1 = copyOf(display1) display2 = copyOf(display2) display3 = copyOf(display3) display4 = copyOf(display4) - display1((oldIndex >> 5) & 31) = display0 - display2((oldIndex >> 10) & 31) = display1 - display3((oldIndex >> 15) & 31) = display2 - display4((oldIndex >> 20) & 31) = display3 - display3 = nullSlotAndCopy(display4, (newIndex >> 20) & 31) - display2 = nullSlotAndCopy(display3, (newIndex >> 15) & 31) - display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31) - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31) + display1((oldIndex >>> 5) & 31) = display0 + display2((oldIndex >>> 10) & 31) = display1 + display3((oldIndex >>> 15) & 31) = display2 + display4((oldIndex >>> 20) & 31) = display3 + display3 = nullSlotAndCopy(display4, (newIndex >>> 20) & 31) + 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 display1 = copyOf(display1) display2 = copyOf(display2) display3 = copyOf(display3) display4 = copyOf(display4) display5 = copyOf(display5) - display1((oldIndex >> 5) & 31) = display0 - display2((oldIndex >> 10) & 31) = display1 - display3((oldIndex >> 15) & 31) = display2 - display4((oldIndex >> 20) & 31) = display3 - display5((oldIndex >> 25) & 31) = display4 - display4 = nullSlotAndCopy(display5, (newIndex >> 25) & 31) - display3 = nullSlotAndCopy(display4, (newIndex >> 20) & 31) - display2 = nullSlotAndCopy(display3, (newIndex >> 15) & 31) - display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31) - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31) + display1((oldIndex >>> 5) & 31) = display0 + display2((oldIndex >>> 10) & 31) = display1 + display3((oldIndex >>> 15) & 31) = display2 + display4((oldIndex >>> 20) & 31) = display3 + display5((oldIndex >>> 25) & 31) = display4 + display4 = nullSlotAndCopy(display5, (newIndex >>> 25) & 31) + display3 = nullSlotAndCopy(display4, (newIndex >>> 20) & 31) + display2 = nullSlotAndCopy(display3, (newIndex >>> 15) & 31) + display1 = nullSlotAndCopy(display2, (newIndex >>> 10) & 31) + display0 = nullSlotAndCopy(display1, (newIndex >>> 5) & 31) } else { // level = 6 throw new IllegalArgumentException() } @@ -1039,56 +1039,56 @@ private[immutable] trait VectorPointer[T] { } else if (xor < (1 << 10)) { // level = 1 if (depth == 1) { display1 = new Array(32) - display1((oldIndex >> 5) & 31) = display0 + display1((oldIndex >>> 5) & 31) = display0 depth += 1 } display0 = new Array(32) } else if (xor < (1 << 15)) { // level = 2 if (depth == 2) { display2 = new Array(32) - display2((oldIndex >> 10) & 31) = display1 + display2((oldIndex >>> 10) & 31) = display1 depth += 1 } - display1 = display2((newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] + 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 if (depth == 3) { display3 = new Array(32) - display3((oldIndex >> 15) & 31) = display2 + display3((oldIndex >>> 15) & 31) = display2 depth += 1 } - display2 = display3((newIndex >> 15) & 31).asInstanceOf[Array[AnyRef]] + display2 = display3((newIndex >>> 15) & 31).asInstanceOf[Array[AnyRef]] if (display2 == null) display2 = new Array(32) - display1 = display2((newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] + 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 if (depth == 4) { display4 = new Array(32) - display4((oldIndex >> 20) & 31) = display3 + display4((oldIndex >>> 20) & 31) = display3 depth += 1 } - display3 = display4((newIndex >> 20) & 31).asInstanceOf[Array[AnyRef]] + display3 = display4((newIndex >>> 20) & 31).asInstanceOf[Array[AnyRef]] if (display3 == null) display3 = new Array(32) - display2 = display3((newIndex >> 15) & 31).asInstanceOf[Array[AnyRef]] + display2 = display3((newIndex >>> 15) & 31).asInstanceOf[Array[AnyRef]] if (display2 == null) display2 = new Array(32) - display1 = display2((newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] + 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 if (depth == 5) { display5 = new Array(32) - display5((oldIndex >> 25) & 31) = display4 + display5((oldIndex >>> 25) & 31) = display4 depth += 1 } - display4 = display5((newIndex >> 25) & 31).asInstanceOf[Array[AnyRef]] + display4 = display5((newIndex >>> 25) & 31).asInstanceOf[Array[AnyRef]] if (display4 == null) display4 = new Array(32) - display3 = display4((newIndex >> 20) & 31).asInstanceOf[Array[AnyRef]] + display3 = display4((newIndex >>> 20) & 31).asInstanceOf[Array[AnyRef]] if (display3 == null) display3 = new Array(32) - display2 = display3((newIndex >> 15) & 31).asInstanceOf[Array[AnyRef]] + display2 = display3((newIndex >>> 15) & 31).asInstanceOf[Array[AnyRef]] if (display2 == null) display2 = new Array(32) - display1 = display2((newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] + display1 = display2((newIndex >>> 10) & 31).asInstanceOf[Array[AnyRef]] if (display1 == null) display1 = new Array(32) display0 = new Array(32) } else { // level = 6 -- cgit v1.2.3 From 74db1d358ad320bbc6f138feb3f6f152ac4e83aa Mon Sep 17 00:00:00 2001 From: Pap Lőrinc Date: Wed, 23 Nov 2016 23:37:01 +0200 Subject: Applied further cleanup to Vector --- .../scala/collection/immutable/Vector.scala | 119 +++++++++++---------- 1 file changed, 63 insertions(+), 56 deletions(-) diff --git a/src/library/scala/collection/immutable/Vector.scala b/src/library/scala/collection/immutable/Vector.scala index 843fc9af55..1093084b9d 100644 --- a/src/library/scala/collection/immutable/Vector.scala +++ b/src/library/scala/collection/immutable/Vector.scala @@ -277,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 @@ -354,13 +354,14 @@ extends AbstractSeq[A] s.display0(lo) = value.asInstanceOf[AnyRef] s } else { - val shift = startIndex & ~((1 << (5 * (depth - 1))) - 1) + val shift = startIndex & ~((1 << (5 * (depth - 1))) - 1) val shiftBlocks = startIndex >>> (5 * (depth - 1)) if (shift != 0) { if (depth > 1) { val newBlockIndex = blockIndex - shift val newFocus = focus - shift + val s = new Vector(startIndex - shift, endIndex + 1 - shift, newBlockIndex) s.initFrom(this) s.dirty = dirty @@ -371,6 +372,7 @@ extends AbstractSeq[A] } else { val newBlockIndex = blockIndex - 32 val newFocus = focus + val s = new Vector(startIndex - shift, endIndex + 1 - shift, newBlockIndex) s.initFrom(this) s.dirty = dirty @@ -405,18 +407,12 @@ extends AbstractSeq[A] // low-level implementation (needs cleanup, maybe move to util class) private def shiftTopLevel(oldLeft: Int, newLeft: Int) = (depth - 1) match { - case 0 => - display0 = copyRange(display0, oldLeft, newLeft) - case 1 => - display1 = copyRange(display1, oldLeft, newLeft) - case 2 => - display2 = copyRange(display2, oldLeft, newLeft) - case 3 => - display3 = copyRange(display3, oldLeft, newLeft) - case 4 => - display4 = copyRange(display4, oldLeft, newLeft) - case 5 => - display5 = copyRange(display5, oldLeft, newLeft) + case 0 => display0 = copyRange(display0, oldLeft, newLeft) + case 1 => display1 = copyRange(display1, oldLeft, newLeft) + case 2 => display2 = copyRange(display2, oldLeft, newLeft) + case 3 => display3 = copyRange(display3, oldLeft, newLeft) + case 4 => display4 = copyRange(display4, oldLeft, newLeft) + case 5 => display5 = copyRange(display5, oldLeft, newLeft) } private def zeroLeft(array: Array[AnyRef], index: Int): Unit = { @@ -588,9 +584,9 @@ extends AbstractSeq[A] } class VectorIterator[+A](_startIndex: Int, endIndex: Int) - extends AbstractIterator[A] - with Iterator[A] - with VectorPointer[A @uncheckedVariance] { +extends AbstractIterator[A] + with Iterator[A] + with VectorPointer[A @uncheckedVariance] { private var blockIndex: Int = _startIndex & ~31 private var lo: Int = _startIndex & 31 @@ -728,17 +724,38 @@ 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 - display0(index & 31).asInstanceOf[T] + (display0 + (index & 31).asInstanceOf[T]) } else if (xor < (1 << 10)) { // level = 1 - display1((index >>> 5) & 31).asInstanceOf[Array[AnyRef]](index & 31).asInstanceOf[T] + (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] + (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] + (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] + (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] + (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 throw new IllegalArgumentException() } @@ -809,55 +826,45 @@ 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 (depth == 1) { display1 = new Array(32); display1(0) = display0; depth += 1 } display0 = new Array(32) - display1((index >>> 5) & 31) = display0 + display1((index >>> 5) & 31) = display0 } else if (xor < (1 << 15)) { // level = 2 - if (depth == 2) { - display2 = new Array(32); display2(0) = display1; depth += 1 - } + 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 + 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 - } + 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 + 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 - } + if (depth == 4) { display4 = new Array(32); display4(0) = display3; depth += 1 } display0 = new Array(32) display1 = new Array(32) display2 = new Array(32) display3 = new Array(32) - display1((index >>> 5) & 31) = display0 - display2((index >>> 10) & 31) = display1 - display3((index >>> 15) & 31) = display2 - display4((index >>> 20) & 31) = display3 + display1((index >>> 5) & 31) = display0 + 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 - } + if (depth == 5) { display5 = new Array(32); display5(0) = display4; depth += 1 } display0 = new Array(32) display1 = new Array(32) display2 = new Array(32) display3 = new Array(32) display4 = new Array(32) - display1((index >>> 5) & 31) = display0 - display2((index >>> 10) & 31) = display1 - display3((index >>> 15) & 31) = display2 - display4((index >>> 20) & 31) = display3 - display5((index >>> 25) & 31) = display4 + display1((index >>> 5) & 31) = display0 + display2((index >>> 10) & 31) = display1 + display3((index >>> 15) & 31) = display2 + display4((index >>> 20) & 31) = display3 + display5((index >>> 25) & 31) = display4 } else { // level = 6 throw new IllegalArgumentException() } @@ -1102,4 +1109,4 @@ private[immutable] trait VectorPointer[T] { stabilize(oldIndex) gotoFreshPosWritable0(oldIndex, newIndex, xor) } -} \ No newline at end of file +} -- cgit v1.2.3