diff options
author | Josh Suereth <Joshua.Suereth@gmail.com> | 2012-08-30 05:02:48 -0700 |
---|---|---|
committer | Josh Suereth <Joshua.Suereth@gmail.com> | 2012-08-30 05:02:48 -0700 |
commit | f1b5332150ad37a99b61ba0ba5858bc75eb13c9e (patch) | |
tree | 2703f00a9bc691a08200655b0104acf52a99fad4 | |
parent | 51c94a2a2ee78e23491a29a971c9f7469b221cf5 (diff) | |
parent | 94888cf69bfe6e7d2ce65427715e4d57e6da3f85 (diff) | |
download | scala-f1b5332150ad37a99b61ba0ba5858bc75eb13c9e.tar.gz scala-f1b5332150ad37a99b61ba0ba5858bc75eb13c9e.tar.bz2 scala-f1b5332150ad37a99b61ba0ba5858bc75eb13c9e.zip |
Merge pull request #1160 from rklaehn/SI-6220
Si 6220
-rw-r--r-- | src/library/scala/collection/immutable/HashSet.scala | 39 | ||||
-rw-r--r-- | test/files/run/t6220.scala | 92 |
2 files changed, 121 insertions, 10 deletions
diff --git a/src/library/scala/collection/immutable/HashSet.scala b/src/library/scala/collection/immutable/HashSet.scala index ef0173337c..d9ce7a68f7 100644 --- a/src/library/scala/collection/immutable/HashSet.scala +++ b/src/library/scala/collection/immutable/HashSet.scala @@ -102,6 +102,30 @@ object HashSet extends ImmutableSetFactory[HashSet] { private object EmptyHashSet extends HashSet[Any] { } + // utility method to create a HashTrieSet from two leaf HashSets (HashSet1 or HashSetCollision1) with non-colliding hash code) + private def makeHashTrieSet[A](hash0:Int, elem0:HashSet[A], hash1:Int, elem1:HashSet[A], level:Int) : HashTrieSet[A] = { + val index0 = (hash0 >>> level) & 0x1f + val index1 = (hash1 >>> level) & 0x1f + if(index0 != index1) { + val bitmap = (1 << index0) | (1 << index1) + val elems = new Array[HashSet[A]](2) + if(index0 < index1) { + elems(0) = elem0 + elems(1) = elem1 + } else { + elems(0) = elem1 + elems(1) = elem0 + } + new HashTrieSet[A](bitmap, elems, elem0.size + elem1.size) + } else { + val elems = new Array[HashSet[A]](1) + val bitmap = (1 << index0) + val child = makeHashTrieSet(hash0, elem0, hash1, elem1, level + 5) + elems(0) = child + new HashTrieSet[A](bitmap, elems, child.size) + } + } + // TODO: add HashSet2, HashSet3, ... class HashSet1[A](private[HashSet] val key: A, private[HashSet] val hash: Int) extends HashSet[A] { @@ -114,9 +138,7 @@ object HashSet extends ImmutableSetFactory[HashSet] { if (hash == this.hash && key == this.key) this else { if (hash != this.hash) { - //new HashTrieSet[A](level+5, this, new HashSet1(key, hash)) - val m = new HashTrieSet[A](0,new Array[HashSet[A]](0),0) // TODO: could save array alloc - m.updated0(this.key, this.hash, level).updated0(key, hash, level) + makeHashTrieSet(this.hash, this, hash, new HashSet1(key, hash), level) } else { // 32-bit hash collision (rare, but not impossible) new HashSetCollision1(hash, ListSet.empty + this.key + key) @@ -140,13 +162,7 @@ object HashSet extends ImmutableSetFactory[HashSet] { override def updated0(key: A, hash: Int, level: Int): HashSet[A] = if (hash == this.hash) new HashSetCollision1(hash, ks + key) - else { - var m: HashSet[A] = new HashTrieSet[A](0,new Array[HashSet[A]](0),0) - // might be able to save some ops here, but it doesn't seem to be worth it - for (k <- ks) - m = m.updated0(k, this.hash, level) - m.updated0(key, hash, level) - } + else makeHashTrieSet(this.hash, this, hash, new HashSet1(key, hash), level) override def removed0(key: A, hash: Int, level: Int): HashSet[A] = if (hash == this.hash) { @@ -181,6 +197,9 @@ object HashSet extends ImmutableSetFactory[HashSet] { class HashTrieSet[A](private val bitmap: Int, private[collection] val elems: Array[HashSet[A]], private val size0: Int) extends HashSet[A] { + assert(Integer.bitCount(bitmap) == elems.length) + // assertion has to remain disabled until SI-6197 is solved + // assert(elems.length > 1 || (elems.length == 1 && elems(0).isInstanceOf[HashTrieSet[_]])) override def size = size0 diff --git a/test/files/run/t6220.scala b/test/files/run/t6220.scala new file mode 100644 index 0000000000..834b692f43 --- /dev/null +++ b/test/files/run/t6220.scala @@ -0,0 +1,92 @@ +import scala.collection.immutable._ + +object Test extends App { + + // finds an int x such that improved(x) differs in the first bit to improved(0), + // which is the worst case for the HashTrieSet + def findWorstCaseInts() { + // copy of improve from HashSet + def improve(hcode: Int) = { + var h: Int = hcode + ~(hcode << 9) + h = h ^ (h >>> 14) + h = h + (h << 4) + h ^ (h >>> 10) + } + + // find two hashes which have a large separation + val x = 0 + var y = 1 + val ix = improve(x) + while(y!=0 && improve(y)!=ix+(1<<31)) + y+=1 + printf("%s %s %x %x\n",x,y,improve(x), improve(y)) + } + // this is not done every test run since it would slow down ant test.suite too much. + // findWorstCaseInts() + + // two numbers that are immediately adiacent when fed through HashSet.improve + val h0 = 0 + val h1 = 1270889724 + + // h is the hashcode, i is ignored for the hashcode but relevant for equality + case class Collision(h:Int, i:Int) { + override def hashCode = h + } + val a = Collision(h0,0) + val b = Collision(h0,1) + val c = Collision(h1,0) + + // create a HashSetCollision1 + val x = HashSet(a) + b + if(x.getClass.getSimpleName != "HashSetCollision1") + println("x should be a collision") + StructureTests.validate(x) + // StructureTests.printStructure(x) + require(x.size==2 && x.contains(a) && x.contains(b)) + + // go from a HashSetCollision1 to a HashTrieSet with maximum depth + val y = x + c + if(y.getClass.getSimpleName != "HashTrieSet") + println("y should be a HashTrieSet") + StructureTests.validate(y) + // StructureTests.printStructure(y) + require(y.size==3 && y.contains(a) && y.contains(b) && y.contains(c)) + + // go from a HashSet1 directly to a HashTrieSet with maximum depth + val z = HashSet(a) + c + if(y.getClass.getSimpleName != "HashTrieSet") + println("y should be a HashTrieSet") + StructureTests.validate(z) + // StructureTests.printStructure(z) + require(z.size == 2 && z.contains(a) && z.contains(c)) +} + +package scala.collection.immutable { + object StructureTests { + def printStructure(x:HashSet[_], prefix:String="") { + x match { + case m:HashSet.HashTrieSet[_] => + println(prefix+m.getClass.getSimpleName + " " + m.size) + m.elems.foreach(child => printStructure(child, prefix + " ")) + case m:HashSet.HashSetCollision1[_] => + println(prefix+m.getClass.getSimpleName + " " + m.ks.size) + case m:HashSet.HashSet1[_] => + println(prefix+m.getClass.getSimpleName + " " + m.head) + case _ => + println(prefix+"empty") + } + } + + def validate(x:HashSet[_]) { + x match { + case m:HashSet.HashTrieSet[_] => + require(m.elems.size>1 || (m.elems.size==1 && m.elems(0).isInstanceOf[HashSet.HashTrieSet[_]])) + m.elems.foreach(validate _) + case m:HashSet.HashSetCollision1[_] => + require(m.ks.size>1) + case m:HashSet.HashSet1[_] => + case _ => + } + } + } +} |