diff options
author | Jason Zaugg <jzaugg@gmail.com> | 2013-04-21 22:32:57 -0700 |
---|---|---|
committer | Jason Zaugg <jzaugg@gmail.com> | 2013-04-21 22:32:57 -0700 |
commit | 66ba223de5f237d543d60c3fe6c812e7a6344ae9 (patch) | |
tree | dc4ae33eed50620dd231dfe01ca8f7ef1aa7392c /src/library | |
parent | cde1c93197e85806a743ddbae190f2a78a43014e (diff) | |
parent | e8c85a37186b65561a3826b9889c9d06a69650da (diff) | |
download | scala-66ba223de5f237d543d60c3fe6c812e7a6344ae9.tar.gz scala-66ba223de5f237d543d60c3fe6c812e7a6344ae9.tar.bz2 scala-66ba223de5f237d543d60c3fe6c812e7a6344ae9.zip |
Merge pull request #2360 from ihji/bugfix/SI-7080
SI-7080 improve boundary value checking for BitSet
Diffstat (limited to 'src/library')
-rw-r--r-- | src/library/scala/collection/BitSetLike.scala | 16 | ||||
-rw-r--r-- | src/library/scala/collection/mutable/BitSet.scala | 5 |
2 files changed, 15 insertions, 6 deletions
diff --git a/src/library/scala/collection/BitSetLike.scala b/src/library/scala/collection/BitSetLike.scala index 034ed2b24a..9c4e710558 100644 --- a/src/library/scala/collection/BitSetLike.scala +++ b/src/library/scala/collection/BitSetLike.scala @@ -106,8 +106,8 @@ trait BitSetLike[+This <: BitSetLike[This] with SortedSet[Int]] extends SortedSe private var current = start private val end = nwords * WordLength def hasNext: Boolean = { - while (current < end && !self.contains(current)) current += 1 - current < end + while (current != end && !self.contains(current)) current += 1 + current != end } def next(): Int = if (hasNext) { val r = current; current += 1; r } @@ -117,7 +117,10 @@ trait BitSetLike[+This <: BitSetLike[This] with SortedSet[Int]] extends SortedSe override def foreach[B](f: Int => B) { for (i <- 0 until nwords) { val w = word(i) - for (j <- i * WordLength until (i + 1) * WordLength) { + /* NOTE: `until` instead of `to` will not work here because + the maximum value of `(i + 1) * WordLength` could be + `Int.MaxValue + 1` (i.e. `Int.MinValue`). */ + for (j <- i * WordLength to (i + 1) * WordLength - 1) { if ((w & (1L << j)) != 0L) f(j) } } @@ -197,11 +200,15 @@ trait BitSetLike[+This <: BitSetLike[This] with SortedSet[Int]] extends SortedSe override def addString(sb: StringBuilder, start: String, sep: String, end: String) = { sb append start var pre = "" - for (i <- 0 until nwords * WordLength) + val max = nwords * WordLength + var i = 0 + while(i != max) { if (contains(i)) { sb append pre append i pre = sep } + i += 1 + } sb append end } @@ -212,6 +219,7 @@ trait BitSetLike[+This <: BitSetLike[This] with SortedSet[Int]] extends SortedSe object BitSetLike { private[collection] val LogWL = 6 private val WordLength = 64 + private[collection] val MaxSize = (Int.MaxValue >> LogWL) + 1 private[collection] def updateArray(elems: Array[Long], idx: Int, w: Long): Array[Long] = { var len = elems.length diff --git a/src/library/scala/collection/mutable/BitSet.scala b/src/library/scala/collection/mutable/BitSet.scala index 397f8099eb..29c341590d 100644 --- a/src/library/scala/collection/mutable/BitSet.scala +++ b/src/library/scala/collection/mutable/BitSet.scala @@ -12,7 +12,7 @@ package scala.collection package mutable import generic._ -import BitSetLike.{LogWL, updateArray} +import BitSetLike.{LogWL, MaxSize, updateArray} /** A class for mutable bitsets. * @@ -63,9 +63,10 @@ class BitSet(protected var elems: Array[Long]) extends AbstractSet[Int] } private def ensureCapacity(idx: Int) { + require(idx < MaxSize) if (idx >= nwords) { var newlen = nwords - while (idx >= newlen) newlen = newlen * 2 + while (idx >= newlen) newlen = (newlen * 2) min MaxSize val elems1 = new Array[Long](newlen) Array.copy(elems, 0, elems1, 0, nwords) elems = elems1 |