diff options
author | Ruediger Klaehn <rklaehn@gmail.com> | 2012-08-09 21:09:39 +0200 |
---|---|---|
committer | Ruediger Klaehn <rklaehn@gmail.com> | 2012-08-09 21:09:39 +0200 |
commit | 1f3f1addfd21842da371a7d1755f9756a7fad3f0 (patch) | |
tree | eeb89823d30e9875201224943770d7992c68a4fa /src/library | |
parent | 6b3d36bc19cc82350c3754b0b91fb074a443d9bc (diff) | |
download | scala-1f3f1addfd21842da371a7d1755f9756a7fad3f0.tar.gz scala-1f3f1addfd21842da371a7d1755f9756a7fad3f0.tar.bz2 scala-1f3f1addfd21842da371a7d1755f9756a7fad3f0.zip |
Only create a HashTrieSet if necessary.
If allow HashTrieSets with one element, you can get a degenerate tree that is six levels deep yet contains only one element by first building a large tree and then removing elements
Diffstat (limited to 'src/library')
-rw-r--r-- | src/library/scala/collection/immutable/HashSet.scala | 7 |
1 files changed, 6 insertions, 1 deletions
diff --git a/src/library/scala/collection/immutable/HashSet.scala b/src/library/scala/collection/immutable/HashSet.scala index c60fdc3bf1..13e1269d46 100644 --- a/src/library/scala/collection/immutable/HashSet.scala +++ b/src/library/scala/collection/immutable/HashSet.scala @@ -236,7 +236,12 @@ object HashSet extends ImmutableSetFactory[HashSet] { Array.copy(elems, 0, elemsNew, 0, offset) Array.copy(elems, offset + 1, elemsNew, offset, elems.length - offset - 1) val sizeNew = size - sub.size - new HashTrieSet(bitmapNew, elemsNew, sizeNew) + // if we have only one child, which is not a HashTrieSet but a self-contained set like + // HashSet1 or HashSetCollision1, return the child instead + if (elemsNew.length == 1 && !elemsNew(0).isInstanceOf[HashTrieSet[_]]) + elemsNew(0) + else + new HashTrieSet(bitmapNew, elemsNew, sizeNew) } else HashSet.empty[A] } else { |