diff options
author | Paul Phillips <paulp@improving.org> | 2009-12-02 04:59:33 +0000 |
---|---|---|
committer | Paul Phillips <paulp@improving.org> | 2009-12-02 04:59:33 +0000 |
commit | 87fa83d3f91bd151eaacdb98862af66021fd5b38 (patch) | |
tree | 5482a05f704933c9802bca9b196b17056914ff9d | |
parent | 75d02a1a5278b49487cef7669c998d4b052bbb2d (diff) | |
download | scala-87fa83d3f91bd151eaacdb98862af66021fd5b38.tar.gz scala-87fa83d3f91bd151eaacdb98862af66021fd5b38.tar.bz2 scala-87fa83d3f91bd151eaacdb98862af66021fd5b38.zip |
A minor optimization to HashSet.
-rw-r--r-- | src/compiler/scala/tools/nsc/symtab/Types.scala | 8 | ||||
-rw-r--r-- | src/compiler/scala/tools/nsc/util/HashSet.scala | 32 |
2 files changed, 29 insertions, 11 deletions
diff --git a/src/compiler/scala/tools/nsc/symtab/Types.scala b/src/compiler/scala/tools/nsc/symtab/Types.scala index 668f7149a9..66f3212922 100644 --- a/src/compiler/scala/tools/nsc/symtab/Types.scala +++ b/src/compiler/scala/tools/nsc/symtab/Types.scala @@ -2633,13 +2633,7 @@ A type's typeSymbol should never be inspected directly. uniques = new HashSet("uniques", initialUniquesCapacity) uniqueRunId = currentRunId } - uniques.findEntry(tp) match { - case null => - //println("new unique type: "+tp) - uniques.addEntry(tp); - tp - case tp1 => tp1.asInstanceOf[T] - } + (uniques findEntryOrUpdate tp).asInstanceOf[T] } // Helper Classes --------------------------------------------------------- diff --git a/src/compiler/scala/tools/nsc/util/HashSet.scala b/src/compiler/scala/tools/nsc/util/HashSet.scala index 32aef80d25..81853785d6 100644 --- a/src/compiler/scala/tools/nsc/util/HashSet.scala +++ b/src/compiler/scala/tools/nsc/util/HashSet.scala @@ -26,6 +26,22 @@ class HashSet[T >: Null <: AnyRef](val label: String, initialCapacity: Int) exte private def index(x: Int): Int = math.abs(x % capacity) + def findEntryOrUpdate(x: T): T = { + var h = index(x.hashCode()) + var entry = table(h) + while (entry ne null) { + if (x == entry) + return entry.asInstanceOf[T] + + h = index(h + 1) + entry = table(h) + } + table(h) = x + used += 1 + if (used > (capacity >> 2)) growTable() + x + } + def findEntry(x: T): T = { var h = index(x.hashCode()) var entry = table(h) @@ -41,7 +57,7 @@ class HashSet[T >: Null <: AnyRef](val label: String, initialCapacity: Int) exte var entry = table(h) while (entry ne null) { if (entry == x) return - h = index((h + 1)) + h = index(h + 1) entry = table(h) } table(h) = x @@ -60,6 +76,16 @@ class HashSet[T >: Null <: AnyRef](val label: String, initialCapacity: Int) exte else null } + private def addOldEntry(x: T) { + var h = index(x.hashCode()) + var entry = table(h) + while (entry ne null) { + h = index(h + 1) + entry = table(h) + } + table(h) = x + } + private def growTable() { val oldtable = table val growthFactor = @@ -70,13 +96,11 @@ class HashSet[T >: Null <: AnyRef](val label: String, initialCapacity: Int) exte capacity *= growthFactor table = new Array[AnyRef](capacity) var i = 0 - used = 0 while (i < oldtable.length) { val entry = oldtable(i) - if (entry ne null) addEntry(entry.asInstanceOf[T]) + if (entry ne null) addOldEntry(entry.asInstanceOf[T]) i += 1 } - // System.err.println("Grown: " + this) } override def toString() = "HashSet %s(%d / %d)".format(label, used, capacity) } |