diff options
author | Aleksandar Pokopec <aleksandar.prokopec@epfl.ch> | 2010-06-16 10:07:42 +0000 |
---|---|---|
committer | Aleksandar Pokopec <aleksandar.prokopec@epfl.ch> | 2010-06-16 10:07:42 +0000 |
commit | 85d5a0cfcd549224d28774b4b13ced5e8367298f (patch) | |
tree | c2546160126066fb7616e8747512ddff4fb51ca4 /src | |
parent | 0c6cbdac433a001f76b1f9afd00f4280d17d1832 (diff) | |
download | scala-85d5a0cfcd549224d28774b4b13ced5e8367298f.tar.gz scala-85d5a0cfcd549224d28774b4b13ced5e8367298f.tar.bz2 scala-85d5a0cfcd549224d28774b4b13ced5e8367298f.zip |
Fixed hash trie splitting. No review.
Diffstat (limited to 'src')
-rw-r--r-- | src/library/scala/collection/immutable/HashMap.scala | 38 | ||||
-rw-r--r-- | src/parallel-collections/scala/collection/parallel/immutable/ParallelHashTrie.scala | 19 |
2 files changed, 32 insertions, 25 deletions
diff --git a/src/library/scala/collection/immutable/HashMap.scala b/src/library/scala/collection/immutable/HashMap.scala index 57fc72d8c7..22760b88c2 100644 --- a/src/library/scala/collection/immutable/HashMap.scala +++ b/src/library/scala/collection/immutable/HashMap.scala @@ -430,23 +430,27 @@ time { mNew.iterator.foreach( p => ()) } } override def split: Seq[HashMap[A, B]] = if (size == 1) Seq(this) else { - // printBitmap(bitmap) - // println(elems.toList) - - // println("subtrees: " + Integer.bitCount(bitmap)) - // println("will split at: " + posOf(Integer.bitCount(bitmap) / 2, bitmap)) - val splitpoint = posOf(Integer.bitCount(bitmap) / 2, bitmap) - val bm1 = bitmap & (-1 << splitpoint) - val bm2 = bitmap & (-1 >>> (32 - splitpoint)) - // printBitmap(bm1) - // printBitmap(bm2) - val (e1, e2) = elems.splitAt(splitpoint) - // println(e1.toList) - // println(e2.toList) - val hm1 = new HashTrieMap(bm1, e1, e1.foldLeft(0)(_ + _.size)) - val hm2 = new HashTrieMap(bm2, e2, e2.foldLeft(0)(_ + _.size)) - - List(hm1, hm2) + val nodesize = Integer.bitCount(bitmap) + if (nodesize > 1) { + // printBitmap(bitmap) + // println(elems.toList) + + // println("subtrees: " + nodesize) + // println("will split at: " + (nodesize / 2)) + val splitpoint = nodesize / 2 + val bitsplitpoint = posOf(nodesize / 2, bitmap) + val bm1 = bitmap & (-1 << bitsplitpoint) + val bm2 = bitmap & (-1 >>> (32 - bitsplitpoint)) + // printBitmap(bm1) + // printBitmap(bm2) + val (e1, e2) = elems.splitAt(splitpoint) + // println(e1.toList) + // println(e2.toList) + val hm1 = new HashTrieMap(bm1, e1, e1.foldLeft(0)(_ + _.size)) + val hm2 = new HashTrieMap(bm2, e2, e2.foldLeft(0)(_ + _.size)) + + List(hm1, hm2) + } else elems(0).split } protected override def combine0[B1 >: B](that: HashMap[A, B1], level: Int): HashMap[A, B1] = that match { diff --git a/src/parallel-collections/scala/collection/parallel/immutable/ParallelHashTrie.scala b/src/parallel-collections/scala/collection/parallel/immutable/ParallelHashTrie.scala index 577fb2642b..362e36135e 100644 --- a/src/parallel-collections/scala/collection/parallel/immutable/ParallelHashTrie.scala +++ b/src/parallel-collections/scala/collection/parallel/immutable/ParallelHashTrie.scala @@ -42,23 +42,26 @@ extends ParallelMap[K, V] type SCPI = SignalContextPassingIterator[ParallelHashTrieIterator] - class ParallelHashTrieIterator(trie: HashMap[K, V]) + class ParallelHashTrieIterator(val ht: HashMap[K, V]) extends super.ParallelIterator { self: SignalContextPassingIterator[ParallelHashTrieIterator] => - println("created iterator") + // println("created iterator " + ht) var i = 0 - lazy val triter = trie.iterator + lazy val triter = ht.iterator def split: Seq[ParallelIterator] = { - println("splitting " + trie + " into " + (trie.split.map(_.size))) - trie.split.map(new ParallelHashTrieIterator(_) with SCPI) + // println("splitting " + ht + " into " + ht.split.map(new ParallelHashTrieIterator(_) with SCPI).map(_.toList)) + ht.split.map(new ParallelHashTrieIterator(_) with SCPI) } def next: (K, V) = { - println("taking next after " + i) + // println("taking next after " + i + ", in " + ht) i += 1 triter.next } - def hasNext: Boolean = i < trie.size - def remaining = trie.size - i + def hasNext: Boolean = { + // println("hasNext: " + i + ", " + ht.size + ", " + ht) + i < ht.size + } + def remaining = ht.size - i } } |