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 /src/library | |
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
Diffstat (limited to 'src/library')
-rw-r--r-- | src/library/scala/collection/immutable/HashSet.scala | 39 |
1 files changed, 29 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 |