1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
|
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2011, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
\* */
package scala.collection
package parallel.mutable
import scala.collection.parallel.IterableSplitter
/** Parallel flat hash table.
*
* @tparam T type of the elements in the $coll.
* @define coll table
* @define Coll `ParFlatHashTable`
*
* @author Aleksandar Prokopec
*/
trait ParFlatHashTable[T] extends scala.collection.mutable.FlatHashTable[T] {
override def alwaysInitSizeMap = true
abstract class ParFlatHashTableIterator(var idx: Int, val until: Int, val totalsize: Int)
extends IterableSplitter[T] with SizeMapUtils {
import scala.collection.DebugUtils._
private var traversed = 0
private val itertable = table
if (hasNext) scan()
private def scan() {
while (itertable(idx) eq null) {
idx += 1
}
}
private def checkbounds() = if (idx >= itertable.length) {
throw new IndexOutOfBoundsException(idx.toString)
}
def newIterator(index: Int, until: Int, totalsize: Int): IterableSplitter[T]
def remaining = totalsize - traversed
def hasNext = traversed < totalsize
def next() = if (hasNext) {
val r = itertable(idx).asInstanceOf[T]
traversed += 1
idx += 1
if (hasNext) scan()
r
} else Iterator.empty.next
def dup = newIterator(idx, until, totalsize)
def split = if (remaining > 1) {
val divpt = (until + idx) / 2
val fstidx = idx
val fstuntil = divpt
val fsttotal = calcNumElems(idx, divpt, itertable.length, sizeMapBucketSize)
val fstit = newIterator(fstidx, fstuntil, fsttotal)
val sndidx = divpt
val snduntil = until
val sndtotal = remaining - fsttotal
val sndit = newIterator(sndidx, snduntil, sndtotal)
Seq(fstit, sndit)
} else Seq(this)
override def debugInformation = buildString {
append =>
append("Parallel flat hash table iterator")
append("---------------------------------")
append("Traversed/total: " + traversed + " / " + totalsize)
append("Table idx/until: " + idx + " / " + until)
append("Table length: " + itertable.length)
append("Table: ")
append(arrayString(itertable, 0, itertable.length))
append("Sizemap: ")
append(arrayString(sizemap, 0, sizemap.length))
}
protected def countElems(from: Int, until: Int) = {
var count = 0
var i = from
while (i < until) {
if (itertable(i) ne null) count += 1
i += 1
}
count
}
protected def countBucketSizes(frombucket: Int, untilbucket: Int) = {
var count = 0
var i = frombucket
while (i < untilbucket) {
count += sizemap(i)
i += 1
}
count
}
private def check() = if (table.slice(idx, until).count(_ != null) != remaining) {
println("Invariant broken: " + debugInformation)
assert(false)
}
}
}
|