-
Notifications
You must be signed in to change notification settings - Fork 3
/
FAABasedQueueSimplified.kt
36 lines (31 loc) · 1.21 KB
/
FAABasedQueueSimplified.kt
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
package day2
import day1.*
import kotlinx.atomicfu.*
class FAABasedQueueSimplified<E> : Queue<E> {
private val infiniteArray = atomicArrayOfNulls<Any?>(1024) // conceptually infinite array
private val enqIdx = atomic(0)
private val deqIdx = atomic(0)
override fun enqueue(element: E) {
// TODO: Increment the counter atomically via Fetch-and-Add.
// TODO: Use `getAndIncrement()` function for that.
val i = enqIdx.value
enqIdx.value = i + 1
// TODO: Atomically install the element into the cell
// TODO: if the cell is not poisoned.
infiniteArray[i].value = element
}
@Suppress("UNCHECKED_CAST")
override fun dequeue(): E? {
// Is this queue empty?
if (enqIdx.value <= deqIdx.value) return null
// TODO: Increment the counter atomically via Fetch-and-Add.
// TODO: Use `getAndIncrement()` function for that.
val i = deqIdx.value
deqIdx.value = i + 1
// TODO: Try to retrieve an element if the cell contains an
// TODO: element, poisoning the cell if it is empty.
return infiniteArray[i].value as E
}
}
// TODO: poison cells with this value.
private val POISONED = Any()