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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
|
import collection.concurrent.TrieMap
import Test.Spec
object ConcurrentMapSpec extends Spec {
val initsz = 500
val secondsz = 750
def test() {
"support put" in {
val ct = new TrieMap[Wrap, Int]
for (i <- 0 until initsz) assert(ct.put(new Wrap(i), i) == None)
for (i <- 0 until initsz) assert(ct.put(new Wrap(i), -i) == Some(i))
}
"support put if absent" in {
val ct = new TrieMap[Wrap, Int]
for (i <- 0 until initsz) ct.update(new Wrap(i), i)
for (i <- 0 until initsz) assert(ct.putIfAbsent(new Wrap(i), -i) == Some(i))
for (i <- 0 until initsz) assert(ct.putIfAbsent(new Wrap(i), -i) == Some(i))
for (i <- initsz until secondsz) assert(ct.putIfAbsent(new Wrap(i), -i) == None)
for (i <- initsz until secondsz) assert(ct.putIfAbsent(new Wrap(i), i) == Some(-i))
}
"support remove if mapped to a specific value" in {
val ct = new TrieMap[Wrap, Int]
for (i <- 0 until initsz) ct.update(new Wrap(i), i)
for (i <- 0 until initsz) assert(ct.remove(new Wrap(i), -i - 1) == false)
for (i <- 0 until initsz) assert(ct.remove(new Wrap(i), i) == true)
for (i <- 0 until initsz) assert(ct.remove(new Wrap(i), i) == false)
}
"support replace if mapped to a specific value" in {
val ct = new TrieMap[Wrap, Int]
for (i <- 0 until initsz) ct.update(new Wrap(i), i)
for (i <- 0 until initsz) assert(ct.replace(new Wrap(i), -i - 1, -i - 2) == false)
for (i <- 0 until initsz) assert(ct.replace(new Wrap(i), i, -i - 2) == true)
for (i <- 0 until initsz) assert(ct.replace(new Wrap(i), i, -i - 2) == false)
for (i <- initsz until secondsz) assert(ct.replace(new Wrap(i), i, 0) == false)
}
"support replace if present" in {
val ct = new TrieMap[Wrap, Int]
for (i <- 0 until initsz) ct.update(new Wrap(i), i)
for (i <- 0 until initsz) assert(ct.replace(new Wrap(i), -i) == Some(i))
for (i <- 0 until initsz) assert(ct.replace(new Wrap(i), i) == Some(-i))
for (i <- initsz until secondsz) assert(ct.replace(new Wrap(i), i) == None)
}
def assertEqual(a: Any, b: Any) = {
if (a != b) println(a, b)
assert(a == b)
}
"support replace if mapped to a specific value, using several threads" in {
val ct = new TrieMap[Wrap, Int]
val sz = 55000
for (i <- 0 until sz) ct.update(new Wrap(i), i)
class Updater(index: Int, offs: Int) extends Thread {
override def run() {
var repeats = 0
for (i <- 0 until sz) {
val j = (offs + i) % sz
var k = Int.MaxValue
do {
if (k != Int.MaxValue) repeats += 1
k = ct.lookup(new Wrap(j))
} while (!ct.replace(new Wrap(j), k, -k))
}
//println("Thread %d repeats: %d".format(index, repeats))
}
}
val threads = for (i <- 0 until 16) yield new Updater(i, sz / 32 * i)
threads.foreach(_.start())
threads.foreach(_.join())
for (i <- 0 until sz) assertEqual(ct(new Wrap(i)), i)
val threads2 = for (i <- 0 until 15) yield new Updater(i, sz / 32 * i)
threads2.foreach(_.start())
threads2.foreach(_.join())
for (i <- 0 until sz) assertEqual(ct(new Wrap(i)), -i)
}
"support put if absent, several threads" in {
val ct = new TrieMap[Wrap, Int]
val sz = 110000
class Updater(offs: Int) extends Thread {
override def run() {
for (i <- 0 until sz) {
val j = (offs + i) % sz
ct.putIfAbsent(new Wrap(j), j)
assert(ct.lookup(new Wrap(j)) == j)
}
}
}
val threads = for (i <- 0 until 16) yield new Updater(sz / 32 * i)
threads.foreach(_.start())
threads.foreach(_.join())
for (i <- 0 until sz) assert(ct(new Wrap(i)) == i)
}
"support remove if mapped to a specific value, several threads" in {
val ct = new TrieMap[Wrap, Int]
val sz = 55000
for (i <- 0 until sz) ct.update(new Wrap(i), i)
class Remover(offs: Int) extends Thread {
override def run() {
for (i <- 0 until sz) {
val j = (offs + i) % sz
ct.remove(new Wrap(j), j)
assert(ct.get(new Wrap(j)) == None)
}
}
}
val threads = for (i <- 0 until 16) yield new Remover(sz / 32 * i)
threads.foreach(_.start())
threads.foreach(_.join())
for (i <- 0 until sz) assert(ct.get(new Wrap(i)) == None)
}
"have all or none of the elements depending on the oddity" in {
val ct = new TrieMap[Wrap, Int]
val sz = 65000
for (i <- 0 until sz) ct(new Wrap(i)) = i
class Modifier(index: Int, offs: Int) extends Thread {
override def run() {
for (j <- 0 until sz) {
val i = (offs + j) % sz
var success = false
do {
if (ct.contains(new Wrap(i))) {
success = ct.remove(new Wrap(i)) != None
} else {
success = ct.putIfAbsent(new Wrap(i), i) == None
}
} while (!success)
}
}
}
def modify(n: Int) = {
val threads = for (i <- 0 until n) yield new Modifier(i, sz / n * i)
threads.foreach(_.start())
threads.foreach(_.join())
}
modify(16)
for (i <- 0 until sz) assertEqual(ct.get(new Wrap(i)), Some(i))
modify(15)
for (i <- 0 until sz) assertEqual(ct.get(new Wrap(i)), None)
}
"compute size correctly" in {
val ct = new TrieMap[Wrap, Int]
val sz = 36450
for (i <- 0 until sz) ct(new Wrap(i)) = i
assertEqual(ct.size, sz)
assertEqual(ct.size, sz)
}
"compute size correctly in parallel" in {
val ct = new TrieMap[Wrap, Int]
val sz = 36450
for (i <- 0 until sz) ct(new Wrap(i)) = i
val pct = ct.par
assertEqual(pct.size, sz)
assertEqual(pct.size, sz)
}
}
}
|
