Roman Elizarov | a7db8ec | 2017-12-21 22:45:12 +0300 | [diff] [blame] | 1 | /* |
Roman Elizarov | 1f74a2d | 2018-06-29 19:19:45 +0300 | [diff] [blame^] | 2 | * Copyright 2016-2018 JetBrains s.r.o. Use of this source code is governed by the Apache 2.0 license. |
Roman Elizarov | a7db8ec | 2017-12-21 22:45:12 +0300 | [diff] [blame] | 3 | */ |
| 4 | |
Roman Elizarov | e1c0b65 | 2017-12-01 14:02:57 +0300 | [diff] [blame] | 5 | package kotlinx.coroutines.experimental.internal |
| 6 | |
| 7 | private typealias Node = LinkedListNode |
| 8 | |
Roman Elizarov | aa461cf | 2018-04-11 13:20:29 +0300 | [diff] [blame] | 9 | /** @suppress **This is unstable API and it is subject to change.** */ |
| 10 | @Suppress("NO_ACTUAL_CLASS_MEMBER_FOR_EXPECTED_CLASS") // :TODO: Remove when fixed: https://youtrack.jetbrains.com/issue/KT-23703 |
| 11 | public actual typealias LockFreeLinkedListNode = LinkedListNode |
| 12 | |
| 13 | /** @suppress **This is unstable API and it is subject to change.** */ |
| 14 | public actual typealias LockFreeLinkedListHead = LinkedListHead |
| 15 | |
| 16 | /** @suppress **This is unstable API and it is subject to change.** */ |
Roman Elizarov | e1c0b65 | 2017-12-01 14:02:57 +0300 | [diff] [blame] | 17 | public open class LinkedListNode { |
Roman Elizarov | aa461cf | 2018-04-11 13:20:29 +0300 | [diff] [blame] | 18 | @PublishedApi internal var _next = this |
| 19 | @PublishedApi internal var _prev = this |
| 20 | @PublishedApi internal var _removed: Boolean = false |
| 21 | |
| 22 | public inline val nextNode get() = _next |
| 23 | public inline val prevNode get() = _prev |
| 24 | public inline val isRemoved get() = _removed |
Roman Elizarov | e1c0b65 | 2017-12-01 14:02:57 +0300 | [diff] [blame] | 25 | |
| 26 | public fun addLast(node: Node) { |
Roman Elizarov | aa461cf | 2018-04-11 13:20:29 +0300 | [diff] [blame] | 27 | val prev = this._prev |
| 28 | node._next = this |
| 29 | node._prev = prev |
| 30 | prev._next = node |
| 31 | this._prev = node |
Roman Elizarov | e1c0b65 | 2017-12-01 14:02:57 +0300 | [diff] [blame] | 32 | } |
| 33 | |
Roman Elizarov | a12ee15 | 2017-12-20 10:50:17 +0300 | [diff] [blame] | 34 | public open fun remove(): Boolean { |
Roman Elizarov | aa461cf | 2018-04-11 13:20:29 +0300 | [diff] [blame] | 35 | if (_removed) return false |
| 36 | val prev = this._prev |
| 37 | val next = this._next |
| 38 | prev._next = next |
| 39 | next._prev = prev |
| 40 | _removed = true |
Roman Elizarov | a12ee15 | 2017-12-20 10:50:17 +0300 | [diff] [blame] | 41 | return true |
Roman Elizarov | e1c0b65 | 2017-12-01 14:02:57 +0300 | [diff] [blame] | 42 | } |
Roman Elizarov | aa461cf | 2018-04-11 13:20:29 +0300 | [diff] [blame] | 43 | |
| 44 | public fun addOneIfEmpty(node: Node): Boolean { |
| 45 | if (_next !== this) return false |
| 46 | addLast(node) |
| 47 | return true |
| 48 | } |
| 49 | |
| 50 | public inline fun addLastIf(node: Node, crossinline condition: () -> Boolean): Boolean { |
| 51 | if (!condition()) return false |
| 52 | addLast(node) |
| 53 | return true |
| 54 | } |
| 55 | |
| 56 | public inline fun addLastIfPrev(node: Node, predicate: (Node) -> Boolean): Boolean { |
| 57 | if (!predicate(_prev)) return false |
| 58 | addLast(node) |
| 59 | return true |
| 60 | } |
| 61 | |
| 62 | public inline fun addLastIfPrevAndIf( |
| 63 | node: Node, |
| 64 | predicate: (Node) -> Boolean, // prev node predicate |
| 65 | crossinline condition: () -> Boolean // atomically checked condition |
| 66 | ): Boolean { |
| 67 | if (!predicate(_prev)) return false |
| 68 | if (!condition()) return false |
| 69 | addLast(node) |
| 70 | return true |
| 71 | } |
| 72 | |
| 73 | public fun removeFirstOrNull(): Node? { |
| 74 | val next = _next |
| 75 | if (next === this) return null |
| 76 | check(next.remove()) { "Should remove" } |
| 77 | return next |
| 78 | } |
| 79 | |
| 80 | public inline fun <reified T> removeFirstIfIsInstanceOfOrPeekIf(predicate: (T) -> Boolean): T? { |
| 81 | val next = _next |
| 82 | if (next === this) return null |
| 83 | if (next !is T) return null |
| 84 | if (predicate(next)) return next |
| 85 | check(next.remove()) { "Should remove" } |
| 86 | return next |
| 87 | } |
Roman Elizarov | e1c0b65 | 2017-12-01 14:02:57 +0300 | [diff] [blame] | 88 | } |
| 89 | |
Roman Elizarov | aa461cf | 2018-04-11 13:20:29 +0300 | [diff] [blame] | 90 | /** @suppress **This is unstable API and it is subject to change.** */ |
| 91 | public actual open class AddLastDesc<T : Node> actual constructor( |
| 92 | actual val queue: Node, |
| 93 | actual val node: T |
| 94 | ) : AbstractAtomicDesc() { |
| 95 | protected override val affectedNode: Node get() = queue._prev |
| 96 | protected actual override fun onPrepare(affected: Node, next: Node): Any? = null |
| 97 | protected override fun onComplete() = queue.addLast(node) |
Vsevolod Tolstopyatov | 9619134 | 2018-04-20 18:13:33 +0300 | [diff] [blame] | 98 | protected actual override fun finishOnSuccess(affected: LockFreeLinkedListNode, next: LockFreeLinkedListNode) = Unit |
| 99 | } |
| 100 | |
Roman Elizarov | 11d6b5b | 2018-04-26 10:11:50 +0300 | [diff] [blame] | 101 | /** @suppress **This is unstable API and it is subject to change.** */ |
Vsevolod Tolstopyatov | 9619134 | 2018-04-20 18:13:33 +0300 | [diff] [blame] | 102 | public actual open class RemoveFirstDesc<T> actual constructor( |
| 103 | actual val queue: LockFreeLinkedListNode |
| 104 | ) : AbstractAtomicDesc() { |
| 105 | |
| 106 | @Suppress("UNCHECKED_CAST") |
| 107 | public actual val result: T get() = affectedNode as T |
Roman Elizarov | 0406a9b | 2018-04-26 12:35:43 +0300 | [diff] [blame] | 108 | protected override val affectedNode: Node = queue.nextNode |
Vsevolod Tolstopyatov | 9619134 | 2018-04-20 18:13:33 +0300 | [diff] [blame] | 109 | protected actual open fun validatePrepared(node: T): Boolean = true |
Vsevolod Tolstopyatov | 2cdbfd7 | 2018-04-22 18:26:14 +0300 | [diff] [blame] | 110 | protected actual final override fun onPrepare(affected: LockFreeLinkedListNode, next: LockFreeLinkedListNode): Any? { |
| 111 | @Suppress("UNCHECKED_CAST") |
| 112 | validatePrepared(affectedNode as T) |
| 113 | return null |
| 114 | } |
| 115 | protected override fun onComplete() { queue.removeFirstOrNull() } |
Vsevolod Tolstopyatov | 9619134 | 2018-04-20 18:13:33 +0300 | [diff] [blame] | 116 | protected actual override fun finishOnSuccess(affected: LockFreeLinkedListNode, next: LockFreeLinkedListNode) = Unit |
Roman Elizarov | aa461cf | 2018-04-11 13:20:29 +0300 | [diff] [blame] | 117 | } |
| 118 | |
| 119 | /** @suppress **This is unstable API and it is subject to change.** */ |
| 120 | public actual abstract class AbstractAtomicDesc : AtomicDesc() { |
| 121 | protected abstract val affectedNode: Node |
| 122 | protected actual abstract fun onPrepare(affected: Node, next: Node): Any? |
| 123 | protected abstract fun onComplete() |
Vsevolod Tolstopyatov | 9619134 | 2018-04-20 18:13:33 +0300 | [diff] [blame] | 124 | |
Vsevolod Tolstopyatov | 2cdbfd7 | 2018-04-22 18:26:14 +0300 | [diff] [blame] | 125 | actual final override fun prepare(op: AtomicOp<*>): Any? { |
| 126 | val affected = affectedNode |
| 127 | val next = affected._next |
| 128 | val failure = failure(affected, next) |
| 129 | if (failure != null) return failure |
| 130 | return onPrepare(affected, next) |
| 131 | } |
| 132 | |
| 133 | actual final override fun complete(op: AtomicOp<*>, failure: Any?) = onComplete() |
| 134 | protected actual open fun failure(affected: LockFreeLinkedListNode, next: Any): Any? = null // Never fails by default |
Vsevolod Tolstopyatov | 9619134 | 2018-04-20 18:13:33 +0300 | [diff] [blame] | 135 | protected actual open fun retry(affected: LockFreeLinkedListNode, next: Any): Boolean = false // Always succeeds |
| 136 | protected actual abstract fun finishOnSuccess(affected: LockFreeLinkedListNode, next: LockFreeLinkedListNode) |
Roman Elizarov | aa461cf | 2018-04-11 13:20:29 +0300 | [diff] [blame] | 137 | } |
| 138 | |
| 139 | /** @suppress **This is unstable API and it is subject to change.** */ |
Roman Elizarov | e1c0b65 | 2017-12-01 14:02:57 +0300 | [diff] [blame] | 140 | public open class LinkedListHead : LinkedListNode() { |
Roman Elizarov | aa461cf | 2018-04-11 13:20:29 +0300 | [diff] [blame] | 141 | public val isEmpty get() = _next === this |
Roman Elizarov | a12ee15 | 2017-12-20 10:50:17 +0300 | [diff] [blame] | 142 | |
Roman Elizarov | e1c0b65 | 2017-12-01 14:02:57 +0300 | [diff] [blame] | 143 | /** |
| 144 | * Iterates over all elements in this list of a specified type. |
| 145 | */ |
| 146 | public inline fun <reified T : Node> forEach(block: (T) -> Unit) { |
Roman Elizarov | aa461cf | 2018-04-11 13:20:29 +0300 | [diff] [blame] | 147 | var cur: Node = _next |
Roman Elizarov | e1c0b65 | 2017-12-01 14:02:57 +0300 | [diff] [blame] | 148 | while (cur != this) { |
| 149 | if (cur is T) block(cur) |
Roman Elizarov | aa461cf | 2018-04-11 13:20:29 +0300 | [diff] [blame] | 150 | cur = cur._next |
Roman Elizarov | e1c0b65 | 2017-12-01 14:02:57 +0300 | [diff] [blame] | 151 | } |
| 152 | } |
| 153 | |
| 154 | // just a defensive programming -- makes sure that list head sentinel is never removed |
| 155 | public final override fun remove() = throw UnsupportedOperationException() |
Roman Elizarov | e1c0b65 | 2017-12-01 14:02:57 +0300 | [diff] [blame] | 156 | } |