diff options
-rw-r--r-- | src/compiler/scala/tools/nsc/ast/parser/Parsers.scala | 32 | ||||
-rwxr-xr-x | src/library/scala/collection/mutable/FlatHashTable.scala | 27 | ||||
-rw-r--r-- | test/files/run/colltest.check | 1 | ||||
-rw-r--r-- | test/files/run/colltest.scala | 50 |
4 files changed, 87 insertions, 23 deletions
diff --git a/src/compiler/scala/tools/nsc/ast/parser/Parsers.scala b/src/compiler/scala/tools/nsc/ast/parser/Parsers.scala index 53314b4581..6f26578833 100644 --- a/src/compiler/scala/tools/nsc/ast/parser/Parsers.scala +++ b/src/compiler/scala/tools/nsc/ast/parser/Parsers.scala @@ -287,18 +287,20 @@ trait Parsers requires SyntaxAnalyzer { /** make closure from tree */ def makeClosure(tree: Tree): Tree = { val pname: Name = unit.fresh.newName("x$") - def insertParam(tree: Tree): Tree = tree match { - case Ident(name) => - Select(Ident(pname), name) - case Select(qual, name) => - Select(insertParam(qual), name) - case Apply(fn, args) => - Apply(insertParam(fn), args) - case TypeApply(fn, args) => - TypeApply(insertParam(fn), args) - case _ => - syntaxError(tree.pos, "cannot convert to closure", false) - errorTermTree + def insertParam(tree: Tree): Tree = atPos(tree.pos) { + tree match { + case Ident(name) => + Select(Ident(pname), name) + case Select(qual, name) => + Select(insertParam(qual), name) + case Apply(fn, args) => + Apply(insertParam(fn), args) + case TypeApply(fn, args) => + TypeApply(insertParam(fn), args) + case _ => + syntaxError(tree.pos, "cannot convert to closure", false) + errorTermTree + } } Function( @@ -507,7 +509,8 @@ trait Parsers requires SyntaxAnalyzer { atPos(pos) { var symid = scalaDot(nme.Symbol) if (isPattern) { symid = convertToTypeId(symid) } - Apply(symid, List(t)) + val symobj = Apply(symid, List(t)) + if (isPattern) symobj else Select(symobj, nme.intern) } } else { t @@ -1266,7 +1269,8 @@ trait Parsers requires SyntaxAnalyzer { if (name == nme.WILDCARD) { in.nextToken(); pattern3(seqOK) } else if (treeInfo.isVarPattern(p)) { - atPos(in.skipToken()) { Bind(name, pattern3(seqOK)) } + in.nextToken() + atPos(p.pos) { Bind(name, pattern3(seqOK)) } } else { p } diff --git a/src/library/scala/collection/mutable/FlatHashTable.scala b/src/library/scala/collection/mutable/FlatHashTable.scala index aee4cb7fc8..6bb6af59f3 100755 --- a/src/library/scala/collection/mutable/FlatHashTable.scala +++ b/src/library/scala/collection/mutable/FlatHashTable.scala @@ -6,11 +6,13 @@ package scala.collection.mutable +import Predef._ + trait FlatHashTable[A] { - /** The load factor for the hash table. + /** The load factor for the hash table; must be < 0.5f */ - protected def loadFactor: Float = 0.5f + protected def loadFactor: Float = 0.45f /** The initial size of the hash table. */ @@ -67,9 +69,11 @@ trait FlatHashTable[A] { } def removeEntry(elem: A) { - def precedes(i: int, j: int, base: int) = - if (base <= i) i <= j || j < base - else i <= j && j < base + def precedes(i: int, j: int) = { + val d = table.length >> 2 + if (i <= j) j - i < d + else i - j > d + } var h = index(elemHashCode(elem)) var entry = table(h) while (null != entry) { @@ -78,13 +82,15 @@ trait FlatHashTable[A] { var h1 = (h0 + 1) % table.length while (null != table(h1)) { val h2 = index(elemHashCode(table(h1).asInstanceOf[A])) - if (h2 != h1 && precedes(h2, h0, h)) { + //Console.println("shift at "+h1+":"+table(h1)+" with h2 = "+h2+"?") + if (h2 != h1 && precedes(h2, h0)) { + //Console.println("shift "+h1+" to "+h0+"!") table(h0) = table(h1) h0 = h1 } h1 = (h1 + 1) % table.length } - table(h1) = null + table(h0) = null tableSize = tableSize - 1 return } @@ -128,8 +134,11 @@ trait FlatHashTable[A] { protected final def index(hcode: Int) = improve(hcode) & (table.length - 1) - private def newThreshold(size: Int) = - (size * loadFactor).asInstanceOf[Int] + private def newThreshold(size: Int) = { + val lf = loadFactor + assert(lf < 0.5f, "loadFactor too large; must be < 0.5") + (size * lf).asInstanceOf[Int] + } protected def clear() { var i = table.length - 1 diff --git a/test/files/run/colltest.check b/test/files/run/colltest.check new file mode 100644 index 0000000000..868cc81ece --- /dev/null +++ b/test/files/run/colltest.check @@ -0,0 +1 @@ +succeeded for 1000000 iterations. diff --git a/test/files/run/colltest.scala b/test/files/run/colltest.scala new file mode 100644 index 0000000000..024f2fb1f4 --- /dev/null +++ b/test/files/run/colltest.scala @@ -0,0 +1,50 @@ +import collection.mutable._ +class TestSet(s0: Set[int], s1: Set[int]) { + val Iterations = 1000000 + val Range = 100000 + val testEachStep = false + val Threshold = 20000 + val r = new java.util.Random(12345) + def test(s: Set[int], n: int): Any = { + val v = n >> 3 + n & 7 match { + case 0 | 1 | 2 => s contains v + case 3 => s += v + case 4 => s -= v + case 5 => if (s.size > Threshold) s -= v else s += v + case 6 => s += v + case 7 => s.size + } + } + def explain(n: int, s: Set[int]): String = n & 7 match { + case 0 | 1 | 2 => "contains" + case 3 => "add" + case 4 => "remove" + case 5 => if (s.size > Threshold) "remove" else "add" + case 6 => "add" + case 7 => "size" + } + def checkSubSet(pre: String, s0: Set[int], s1: Set[int]) { + for (val e <- s0.elements) + if (!(s1 contains e)) { + assert(false, pre+" element: "+e+"\n S0 = "+s0+"\n S1 = "+s1) + } + } + for (val i <- 0 until Iterations) { + val n = r.nextInt(Range) + val res0 = test(s0, n) + val res1 = test(s1, n) + //Console.println("operation = "+explain(n, s0)+", value ="+(n >> 3)+", result0 = "+res0) + if (testEachStep) { + checkSubSet("superfluous", s0, s1) + checkSubSet("missing", s1, s0) + } + if (res0 != res1) + assert(false, "DIFFERENCE , operation = "+explain(n, s0)+", value ="+(n >> 3)+ + ", result0 = "+res0+", result1 = "+res1) + } + Console.println("succeeded for "+Iterations+" iterations.") +} +object Test extends Application { + new TestSet(HashSet.empty, new LinkedHashSet) +} |