diff options
| -rw-r--r-- | src/library/scala/collection/mutable/FlatHashTable.scala | 15 | ||||
| -rw-r--r-- | test/files/run/bug978.scala | 38 |
2 files changed, 51 insertions, 2 deletions
diff --git a/src/library/scala/collection/mutable/FlatHashTable.scala b/src/library/scala/collection/mutable/FlatHashTable.scala index 0c9ec9c4d6..aeab7cd2ea 100644 --- a/src/library/scala/collection/mutable/FlatHashTable.scala +++ b/src/library/scala/collection/mutable/FlatHashTable.scala @@ -18,6 +18,8 @@ trait FlatHashTable[A] { */ protected def initialSize: Int = 16 + private final val tableDebug = false + /** The actual hash table. */ protected var table: Array[AnyRef] = @@ -69,8 +71,9 @@ trait FlatHashTable[A] { } def removeEntry(elem: A) { + checkConsistent() def precedes(i: int, j: int) = { - val d = table.length >> 2 + val d = table.length >> 1 if (i <= j) j - i < d else i - j > d } @@ -82,7 +85,7 @@ trait FlatHashTable[A] { var h1 = (h0 + 1) % table.length while (null != table(h1)) { val h2 = index(elemHashCode(table(h1).asInstanceOf[A])) - //Console.println("shift at "+h1+":"+table(h1)+" with h2 = "+h2+"?") + //Console.println("shift at "+h1+":"+table(h1)+" with h2 = "+h2+"? "+(h2 != h1)+precedes(h2, h0)+table.length) if (h2 != h1 && precedes(h2, h0)) { //Console.println("shift "+h1+" to "+h0+"!") table(h0) = table(h1) @@ -92,6 +95,7 @@ trait FlatHashTable[A] { } table(h0) = null tableSize = tableSize - 1 + if (tableDebug) checkConsistent() return } h = (h + 1) % table.length @@ -121,6 +125,13 @@ trait FlatHashTable[A] { if (null != entry) addEntry(entry.asInstanceOf[A]) i = i + 1 } + if (tableDebug) checkConsistent() + } + + private def checkConsistent() { + for (val i <- 0 until table.length) + if (table(i) != null && !containsEntry(table(i).asInstanceOf[A])) + assert(false, i+" "+table(i)+" "+table.toString) } protected def elemHashCode(elem: A) = elem.hashCode() diff --git a/test/files/run/bug978.scala b/test/files/run/bug978.scala new file mode 100644 index 0000000000..72dfdbae0a --- /dev/null +++ b/test/files/run/bug978.scala @@ -0,0 +1,38 @@ +class Foo(val n: Int) { + override def hashCode = n % 2 // pretty bad hash + override def equals(other: Any): Boolean = other match { + case f: Foo => f.n == n + case _ => false + } + + override def toString = "" + n +} + +object Test extends Application { + val set = new collection.mutable.HashSet[Foo] +// val set = new collection.jcl.HashSet[Foo] + + val max = 200 + for (val x <- 1 to max) + set += new Foo(x) + + testRemove(2) + testExists(2) + + def testRemove(m: Int) { + for (val x <- 1 to max; x % m == 0) { + val f = new Foo(x) + set -= f + assert(!(set contains f)) + testExists(m) + } + } + + def testExists(m: Int) { + for (val x <- 1 to max; x % m == 1) { + val f = new Foo(x) + assert(set contains f, "For element: " + f + " set: " + set) + } + } + +} |