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
|
/*
* Copyright 2016-2020 JetBrains s.r.o. Use of this source code is governed by the Apache 2.0 license.
*/
@file:Suppress("unused")
package kotlinx.coroutines.internal
private typealias Node = LinkedListNode
/** @suppress **This is unstable API and it is subject to change.** */
@Suppress("NO_ACTUAL_CLASS_MEMBER_FOR_EXPECTED_CLASS") // :TODO: Remove when fixed: https://youtrack.jetbrains.com/issue/KT-23703
public actual typealias LockFreeLinkedListNode = LinkedListNode
/** @suppress **This is unstable API and it is subject to change.** */
public actual typealias LockFreeLinkedListHead = LinkedListHead
/** @suppress **This is unstable API and it is subject to change.** */
public open class LinkedListNode {
@PublishedApi internal var _next = this
@PublishedApi internal var _prev = this
@PublishedApi internal var _removed: Boolean = false
public inline val nextNode get() = _next
public inline val prevNode get() = _prev
public inline val isRemoved get() = _removed
public fun addLast(node: Node) {
val prev = this._prev
node._next = this
node._prev = prev
prev._next = node
this._prev = node
}
public open fun remove(): Boolean {
if (_removed) return false
val prev = this._prev
val next = this._next
prev._next = next
next._prev = prev
_removed = true
return true
}
public fun addOneIfEmpty(node: Node): Boolean {
if (_next !== this) return false
addLast(node)
return true
}
public inline fun addLastIf(node: Node, crossinline condition: () -> Boolean): Boolean {
if (!condition()) return false
addLast(node)
return true
}
public inline fun addLastIfPrev(node: Node, predicate: (Node) -> Boolean): Boolean {
if (!predicate(_prev)) return false
addLast(node)
return true
}
public inline fun addLastIfPrevAndIf(
node: Node,
predicate: (Node) -> Boolean, // prev node predicate
crossinline condition: () -> Boolean // atomically checked condition
): Boolean {
if (!predicate(_prev)) return false
if (!condition()) return false
addLast(node)
return true
}
public fun helpRemove() {} // No concurrency on JS -> no removal
public fun removeFirstOrNull(): Node? {
val next = _next
if (next === this) return null
check(next.remove()) { "Should remove" }
return next
}
public inline fun <reified T> removeFirstIfIsInstanceOfOrPeekIf(predicate: (T) -> Boolean): T? {
val next = _next
if (next === this) return null
if (next !is T) return null
if (predicate(next)) return next
check(next.remove()) { "Should remove" }
return next
}
}
/** @suppress **This is unstable API and it is subject to change.** */
public actual open class AddLastDesc<T : Node> actual constructor(
actual val queue: Node,
actual val node: T
) : AbstractAtomicDesc() {
override val affectedNode: Node get() = queue._prev
actual override fun finishPrepare(prepareOp: PrepareOp) {}
override fun onComplete() = queue.addLast(node)
actual override fun finishOnSuccess(affected: LockFreeLinkedListNode, next: LockFreeLinkedListNode) = Unit
}
/** @suppress **This is unstable API and it is subject to change.** */
public actual open class RemoveFirstDesc<T> actual constructor(
actual val queue: LockFreeLinkedListNode
) : AbstractAtomicDesc() {
@Suppress("UNCHECKED_CAST")
actual val result: T get() = affectedNode as T
override val affectedNode: Node = queue.nextNode
actual override fun finishPrepare(prepareOp: PrepareOp) {}
override fun onComplete() { queue.removeFirstOrNull() }
actual override fun finishOnSuccess(affected: LockFreeLinkedListNode, next: LockFreeLinkedListNode) = Unit
}
/** @suppress **This is unstable API and it is subject to change.** */
public actual abstract class AbstractAtomicDesc : AtomicDesc() {
protected abstract val affectedNode: Node
actual abstract fun finishPrepare(prepareOp: PrepareOp)
protected abstract fun onComplete()
actual open fun onPrepare(prepareOp: PrepareOp): Any? {
finishPrepare(prepareOp)
return null
}
actual final override fun prepare(op: AtomicOp<*>): Any? {
val affected = affectedNode
val failure = failure(affected)
if (failure != null) return failure
@Suppress("UNCHECKED_CAST")
return onPrepare(PrepareOp(affected, this, op))
}
actual final override fun complete(op: AtomicOp<*>, failure: Any?) = onComplete()
protected actual open fun failure(affected: LockFreeLinkedListNode): Any? = null // Never fails by default
protected actual open fun retry(affected: LockFreeLinkedListNode, next: Any): Boolean = false // Always succeeds
protected actual abstract fun finishOnSuccess(affected: LockFreeLinkedListNode, next: LockFreeLinkedListNode)
}
/** @suppress **This is unstable API and it is subject to change.** */
public actual class PrepareOp(
actual val affected: LockFreeLinkedListNode,
actual val desc: AbstractAtomicDesc,
actual override val atomicOp: AtomicOp<*>
): OpDescriptor() {
override fun perform(affected: Any?): Any? = null
actual fun finishPrepare() {}
}
/** @suppress **This is unstable API and it is subject to change.** */
public open class LinkedListHead : LinkedListNode() {
public val isEmpty get() = _next === this
/**
* Iterates over all elements in this list of a specified type.
*/
public inline fun <reified T : Node> forEach(block: (T) -> Unit) {
var cur: Node = _next
while (cur != this) {
if (cur is T) block(cur)
cur = cur._next
}
}
// just a defensive programming -- makes sure that list head sentinel is never removed
public final override fun remove(): Boolean = throw UnsupportedOperationException()
}
|
