diff options
author | Matthias Zenger <mzenger@gmail.com> | 2003-08-10 23:06:23 +0000 |
---|---|---|
committer | Matthias Zenger <mzenger@gmail.com> | 2003-08-10 23:06:23 +0000 |
commit | 6150a5b04ecbb2fa46aab49a226cf00dfae24e74 (patch) | |
tree | 162d68121b977e01f719f25aba5be8fd17cd813b | |
parent | 7a1154824c6aa7feb18f5c0925f358d737ba6a3a (diff) | |
download | scala-6150a5b04ecbb2fa46aab49a226cf00dfae24e74.tar.gz scala-6150a5b04ecbb2fa46aab49a226cf00dfae24e74.tar.bz2 scala-6150a5b04ecbb2fa46aab49a226cf00dfae24e74.zip |
Fixed bug in hash table resizing method.
-rw-r--r-- | sources/scala/collection/mutable/HashMap.scala | 2 | ||||
-rw-r--r-- | sources/scala/collection/mutable/HashSet.scala | 2 | ||||
-rw-r--r-- | sources/scala/collection/mutable/HashTable.scala | 33 |
3 files changed, 17 insertions, 20 deletions
diff --git a/sources/scala/collection/mutable/HashMap.scala b/sources/scala/collection/mutable/HashMap.scala index 1394c21f48..9e545a7281 100644 --- a/sources/scala/collection/mutable/HashMap.scala +++ b/sources/scala/collection/mutable/HashMap.scala @@ -23,7 +23,7 @@ class HashMap[A, B] extends scala.collection.mutable.Map[A, B] protected def entryKey(e: Entry) = e.key; override def clear = { - initTable(table.length - 1); + initTable(table); tableSize = 0; } } diff --git a/sources/scala/collection/mutable/HashSet.scala b/sources/scala/collection/mutable/HashSet.scala index 1c27ea6c18..9134ca9524 100644 --- a/sources/scala/collection/mutable/HashSet.scala +++ b/sources/scala/collection/mutable/HashSet.scala @@ -32,7 +32,7 @@ class HashSet[A] extends scala.collection.mutable.Set[A] with HashTable[A] { def elements = entries; override def clear = { - initTable(table.length - 1); + initTable(table); tableSize = 0; } diff --git a/sources/scala/collection/mutable/HashTable.scala b/sources/scala/collection/mutable/HashTable.scala index b79b9a2b29..4795fc5339 100644 --- a/sources/scala/collection/mutable/HashTable.scala +++ b/sources/scala/collection/mutable/HashTable.scala @@ -4,10 +4,9 @@ ** __\ \/ /__/ __ |/ /__/ __ | ** ** /____/\___/_/ |_/____/_/ | | ** ** |/ ** +** $Id$ \* */ -// $Id$ - package scala.collection.mutable; @@ -45,7 +44,7 @@ abstract class HashTable[A] { /** The actual hash table. */ protected var table: Array[List[Entry]] = new Array(initialSize); - initTable(initialSize - 1); + initTable(table); /** The number of mappings contained in this hash table. */ @@ -107,9 +106,12 @@ abstract class HashTable[A] { private def entryFor(key: A) = (e: Entry => elemEquals(entryKey(e), key)); - protected def initTable(n: Int): Unit = { - table(n) = Nil; - if (n > 0) initTable(n - 1); + protected def initTable(tb: Array[List[Entry]]): Unit = { + var i = tb.length - 1; + while (i >= 0) { + tb(i) = Nil; + i = i - 1; + } } private def newThreshold(size: Int) = @@ -117,20 +119,15 @@ abstract class HashTable[A] { private def resize(newSize: Int) = { val newTable: Array[List[Entry]] = new Array(newSize); - initTable(newSize - 1); - def rehash(i: Int) = { - if (i >= 0) - rehashList(table(i)); - } - def rehashList(xs: List[Entry]): Unit = xs.match { - case Nil => () - case e :: es => { - val idx = improve(elemHashCode(entryKey(e))) & (newSize - 1); + initTable(newTable); + var i = table.length - 1; + while (i >= 0) { + table(i).foreach { e => { + val idx = improve(elemHashCode(entryKey(e))) & (newSize - 1); newTable(idx) = e :: newTable(idx); - rehashList(es); - } + }}; + i = i - 1; } - rehash(table.length - 1); table = newTable; threshold = newThreshold(newSize); } |