diff options
author | Ruediger Klaehn <rklaehn@gmail.com> | 2012-08-12 22:55:07 +0200 |
---|---|---|
committer | Ruediger Klaehn <rklaehn@gmail.com> | 2012-08-12 22:55:07 +0200 |
commit | 5be6e644dccde9298413ede3c8d20528fba12643 (patch) | |
tree | ef8de392bb46e19cc87e97222911e9b92a8d39fe | |
parent | 6b3d36bc19cc82350c3754b0b91fb074a443d9bc (diff) | |
download | scala-5be6e644dccde9298413ede3c8d20528fba12643.tar.gz scala-5be6e644dccde9298413ede3c8d20528fba12643.tar.bz2 scala-5be6e644dccde9298413ede3c8d20528fba12643.zip |
Improve efficiency of updated
Added utility method to create a HashTrieSet with two leaf HashSets with different hash
Used said utility method instead of creating a temorary HashTrieSet with an empty elems array
Added assertions to HashTrieSet to validate tree
-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 c60fdc3bf1..43e776d5ae 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) { @@ -179,6 +195,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 |