Roman Elizarov | f16fd27 | 2017-02-07 11:26:00 +0300 | [diff] [blame] | 1 | /* |
| 2 | * Copyright 2016-2017 JetBrains s.r.o. |
| 3 | * |
| 4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
| 5 | * you may not use this file except in compliance with the License. |
| 6 | * You may obtain a copy of the License at |
| 7 | * |
| 8 | * http://www.apache.org/licenses/LICENSE-2.0 |
| 9 | * |
| 10 | * Unless required by applicable law or agreed to in writing, software |
| 11 | * distributed under the License is distributed on an "AS IS" BASIS, |
| 12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 13 | * See the License for the specific language governing permissions and |
| 14 | * limitations under the License. |
| 15 | */ |
| 16 | |
Roman Elizarov | a567659 | 2017-01-19 10:31:13 +0300 | [diff] [blame] | 17 | package kotlinx.coroutines.experimental.internal |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 18 | |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 19 | import kotlinx.atomicfu.atomic |
| 20 | import kotlinx.atomicfu.loop |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 21 | |
| 22 | private typealias Node = LockFreeLinkedListNode |
| 23 | |
Roman Elizarov | f024608 | 2017-02-10 18:02:38 +0300 | [diff] [blame] | 24 | @PublishedApi |
Roman Elizarov | 6c63aea | 2017-02-02 12:20:48 +0300 | [diff] [blame] | 25 | internal const val UNDECIDED = 0 |
Roman Elizarov | f024608 | 2017-02-10 18:02:38 +0300 | [diff] [blame] | 26 | |
| 27 | @PublishedApi |
Roman Elizarov | 6c63aea | 2017-02-02 12:20:48 +0300 | [diff] [blame] | 28 | internal const val SUCCESS = 1 |
Roman Elizarov | f024608 | 2017-02-10 18:02:38 +0300 | [diff] [blame] | 29 | |
| 30 | @PublishedApi |
Roman Elizarov | 6c63aea | 2017-02-02 12:20:48 +0300 | [diff] [blame] | 31 | internal const val FAILURE = 2 |
| 32 | |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 33 | @PublishedApi |
| 34 | internal val CONDITION_FALSE: Any = Symbol("CONDITION_FALSE") |
| 35 | |
| 36 | @PublishedApi |
| 37 | internal val ALREADY_REMOVED: Any = Symbol("ALREADY_REMOVED") |
| 38 | |
| 39 | @PublishedApi |
| 40 | internal val LIST_EMPTY: Any = Symbol("LIST_EMPTY") |
| 41 | |
| 42 | private val REMOVE_PREPARED: Any = Symbol("REMOVE_PREPARED") |
| 43 | |
Roman Elizarov | aa461cf | 2018-04-11 13:20:29 +0300 | [diff] [blame] | 44 | /** @suppress **This is unstable API and it is subject to change.** */ |
Vsevolod Tolstopyatov | 9619134 | 2018-04-20 18:13:33 +0300 | [diff] [blame] | 45 | public actual typealias RemoveFirstDesc<T> = LockFreeLinkedListNode.RemoveFirstDesc<T> |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 46 | |
Roman Elizarov | aa461cf | 2018-04-11 13:20:29 +0300 | [diff] [blame] | 47 | /** @suppress **This is unstable API and it is subject to change.** */ |
| 48 | public actual typealias AddLastDesc<T> = LockFreeLinkedListNode.AddLastDesc<T> |
| 49 | |
| 50 | /** @suppress **This is unstable API and it is subject to change.** */ |
| 51 | public actual typealias AbstractAtomicDesc = LockFreeLinkedListNode.AbstractAtomicDesc |
Roman Elizarov | 1216e91 | 2017-02-22 09:57:06 +0300 | [diff] [blame] | 52 | |
| 53 | /** |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 54 | * Doubly-linked concurrent list node with remove support. |
| 55 | * Based on paper |
| 56 | * ["Lock-Free and Practical Doubly Linked List-Based Deques Using Single-Word Compare-and-Swap"](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.140.4693&rep=rep1&type=pdf) |
| 57 | * by Sundell and Tsigas. |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 58 | * |
| 59 | * Important notes: |
| 60 | * * The instance of this class serves both as list head/tail sentinel and as the list item. |
| 61 | * Sentinel node should be never removed. |
| 62 | * * There are no operations to add items to left side of the list, only to the end (right side), because we cannot |
| 63 | * efficiently linearize them with atomic multi-step head-removal operations. In short, |
| 64 | * support for [describeRemoveFirst] operation precludes ability to add items at the beginning. |
Roman Elizarov | f024608 | 2017-02-10 18:02:38 +0300 | [diff] [blame] | 65 | * |
| 66 | * @suppress **This is unstable API and it is subject to change.** |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 67 | */ |
| 68 | @Suppress("LeakingThis") |
Roman Elizarov | aa461cf | 2018-04-11 13:20:29 +0300 | [diff] [blame] | 69 | public actual open class LockFreeLinkedListNode { |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 70 | private val _next = atomic<Any>(this) // Node | Removed | OpDescriptor |
| 71 | private val _prev = atomic<Any>(this) // Node | Removed |
| 72 | private val _removedRef = atomic<Removed?>(null) // lazily cached removed ref to this |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 73 | |
Roman Elizarov | 6f82783 | 2017-01-25 16:42:23 +0300 | [diff] [blame] | 74 | private fun removed(): Removed = |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 75 | _removedRef.value ?: Removed(this).also { _removedRef.lazySet(it) } |
Roman Elizarov | 6f82783 | 2017-01-25 16:42:23 +0300 | [diff] [blame] | 76 | |
Roman Elizarov | f024608 | 2017-02-10 18:02:38 +0300 | [diff] [blame] | 77 | @PublishedApi |
Roman Elizarov | 1216e91 | 2017-02-22 09:57:06 +0300 | [diff] [blame] | 78 | internal abstract class CondAddOp( |
| 79 | @JvmField val newNode: Node |
Roman Elizarov | d82b3a9 | 2017-06-23 21:52:08 +0300 | [diff] [blame] | 80 | ) : AtomicOp<Node>() { |
Roman Elizarov | 1216e91 | 2017-02-22 09:57:06 +0300 | [diff] [blame] | 81 | @JvmField var oldNext: Node? = null |
Roman Elizarov | 6c63aea | 2017-02-02 12:20:48 +0300 | [diff] [blame] | 82 | |
Roman Elizarov | d82b3a9 | 2017-06-23 21:52:08 +0300 | [diff] [blame] | 83 | override fun complete(affected: Node, failure: Any?) { |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 84 | val success = failure == null |
| 85 | val update = if (success) newNode else oldNext |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 86 | if (update != null && affected._next.compareAndSet( this, update)) { |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 87 | // only the thread the makes this update actually finishes add operation |
Roman Elizarov | 1216e91 | 2017-02-22 09:57:06 +0300 | [diff] [blame] | 88 | if (success) newNode.finishAdd(oldNext!!) |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 89 | } |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 90 | } |
| 91 | } |
| 92 | |
Roman Elizarov | f024608 | 2017-02-10 18:02:38 +0300 | [diff] [blame] | 93 | @PublishedApi |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 94 | internal inline fun makeCondAddOp(node: Node, crossinline condition: () -> Boolean): CondAddOp = |
| 95 | object : CondAddOp(node) { |
Roman Elizarov | d82b3a9 | 2017-06-23 21:52:08 +0300 | [diff] [blame] | 96 | override fun prepare(affected: Node): Any? = if (condition()) null else CONDITION_FALSE |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 97 | } |
Roman Elizarov | 6c63aea | 2017-02-02 12:20:48 +0300 | [diff] [blame] | 98 | |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 99 | public val isFresh: Boolean get() = _next.value === this |
Roman Elizarov | 35d2c34 | 2017-07-20 14:54:39 +0300 | [diff] [blame] | 100 | |
Roman Elizarov | aa461cf | 2018-04-11 13:20:29 +0300 | [diff] [blame] | 101 | public actual val isRemoved: Boolean get() = next is Removed |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 102 | |
Roman Elizarov | 3aed4ee | 2017-03-06 12:21:05 +0300 | [diff] [blame] | 103 | // LINEARIZABLE. Returns Node | Removed |
Roman Elizarov | 0406a9b | 2018-04-26 12:35:43 +0300 | [diff] [blame^] | 104 | public val next: Any get() { |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 105 | _next.loop { next -> |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 106 | if (next !is OpDescriptor) return next |
| 107 | next.perform(this) |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 108 | } |
| 109 | } |
| 110 | |
Roman Elizarov | 0406a9b | 2018-04-26 12:35:43 +0300 | [diff] [blame^] | 111 | // LINEARIZABLE. Returns next non-removed Node |
Roman Elizarov | aa461cf | 2018-04-11 13:20:29 +0300 | [diff] [blame] | 112 | public actual val nextNode: Node get() = next.unwrap() |
| 113 | |
Roman Elizarov | 3aed4ee | 2017-03-06 12:21:05 +0300 | [diff] [blame] | 114 | // LINEARIZABLE. Returns Node | Removed |
Roman Elizarov | 0406a9b | 2018-04-26 12:35:43 +0300 | [diff] [blame^] | 115 | public val prev: Any get() { |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 116 | _prev.loop { prev -> |
Roman Elizarov | 3aed4ee | 2017-03-06 12:21:05 +0300 | [diff] [blame] | 117 | if (prev is Removed) return prev |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 118 | prev as Node // otherwise, it can be only node |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 119 | if (prev.next === this) return prev |
Roman Elizarov | b78fa42 | 2017-07-05 09:54:03 +0300 | [diff] [blame] | 120 | correctPrev(prev, null) |
Roman Elizarov | 01934df | 2017-01-31 09:18:34 +0300 | [diff] [blame] | 121 | } |
| 122 | } |
| 123 | |
Roman Elizarov | 0406a9b | 2018-04-26 12:35:43 +0300 | [diff] [blame^] | 124 | // LINEARIZABLE. Returns prev non-removed Node |
Roman Elizarov | aa461cf | 2018-04-11 13:20:29 +0300 | [diff] [blame] | 125 | public actual val prevNode: Node get() = prev.unwrap() |
| 126 | |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 127 | // ------ addOneIfEmpty ------ |
Roman Elizarov | 01934df | 2017-01-31 09:18:34 +0300 | [diff] [blame] | 128 | |
Roman Elizarov | aa461cf | 2018-04-11 13:20:29 +0300 | [diff] [blame] | 129 | public actual fun addOneIfEmpty(node: Node): Boolean { |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 130 | node._prev.lazySet(this) |
| 131 | node._next.lazySet(this) |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 132 | while (true) { |
| 133 | val next = next |
| 134 | if (next !== this) return false // this is not an empty list! |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 135 | if (_next.compareAndSet(this, node)) { |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 136 | // added successfully (linearized add) -- fixup the list |
| 137 | node.finishAdd(this) |
| 138 | return true |
| 139 | } |
| 140 | } |
Roman Elizarov | daa7922 | 2017-01-26 11:31:31 +0300 | [diff] [blame] | 141 | } |
| 142 | |
Roman Elizarov | 01934df | 2017-01-31 09:18:34 +0300 | [diff] [blame] | 143 | // ------ addLastXXX ------ |
| 144 | |
Roman Elizarov | 6c63aea | 2017-02-02 12:20:48 +0300 | [diff] [blame] | 145 | /** |
| 146 | * Adds last item to this list. |
| 147 | */ |
Roman Elizarov | aa461cf | 2018-04-11 13:20:29 +0300 | [diff] [blame] | 148 | public actual fun addLast(node: Node) { |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 149 | while (true) { // lock-free loop on prev.next |
Roman Elizarov | 3aed4ee | 2017-03-06 12:21:05 +0300 | [diff] [blame] | 150 | val prev = prev as Node // sentinel node is never removed, so prev is always defined |
Roman Elizarov | 6c63aea | 2017-02-02 12:20:48 +0300 | [diff] [blame] | 151 | if (prev.addNext(node, this)) return |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 152 | } |
| 153 | } |
| 154 | |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 155 | public fun <T : Node> describeAddLast(node: T): AddLastDesc<T> = AddLastDesc(this, node) |
Roman Elizarov | 1216e91 | 2017-02-22 09:57:06 +0300 | [diff] [blame] | 156 | |
Roman Elizarov | 01934df | 2017-01-31 09:18:34 +0300 | [diff] [blame] | 157 | /** |
Roman Elizarov | 01934df | 2017-01-31 09:18:34 +0300 | [diff] [blame] | 158 | * Adds last item to this list atomically if the [condition] is true. |
| 159 | */ |
Roman Elizarov | aa461cf | 2018-04-11 13:20:29 +0300 | [diff] [blame] | 160 | public actual inline fun addLastIf(node: Node, crossinline condition: () -> Boolean): Boolean { |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 161 | val condAdd = makeCondAddOp(node, condition) |
Roman Elizarov | 6c63aea | 2017-02-02 12:20:48 +0300 | [diff] [blame] | 162 | while (true) { // lock-free loop on prev.next |
Roman Elizarov | 3aed4ee | 2017-03-06 12:21:05 +0300 | [diff] [blame] | 163 | val prev = prev as Node // sentinel node is never removed, so prev is always defined |
Roman Elizarov | 6c63aea | 2017-02-02 12:20:48 +0300 | [diff] [blame] | 164 | when (prev.tryCondAddNext(node, this, condAdd)) { |
| 165 | SUCCESS -> return true |
| 166 | FAILURE -> return false |
| 167 | } |
| 168 | } |
| 169 | } |
Roman Elizarov | 01934df | 2017-01-31 09:18:34 +0300 | [diff] [blame] | 170 | |
Roman Elizarov | aa461cf | 2018-04-11 13:20:29 +0300 | [diff] [blame] | 171 | public actual inline fun addLastIfPrev(node: Node, predicate: (Node) -> Boolean): Boolean { |
Roman Elizarov | 01934df | 2017-01-31 09:18:34 +0300 | [diff] [blame] | 172 | while (true) { // lock-free loop on prev.next |
Roman Elizarov | 3aed4ee | 2017-03-06 12:21:05 +0300 | [diff] [blame] | 173 | val prev = prev as Node // sentinel node is never removed, so prev is always defined |
Roman Elizarov | 01934df | 2017-01-31 09:18:34 +0300 | [diff] [blame] | 174 | if (!predicate(prev)) return false |
Roman Elizarov | 6c63aea | 2017-02-02 12:20:48 +0300 | [diff] [blame] | 175 | if (prev.addNext(node, this)) return true |
| 176 | } |
| 177 | } |
| 178 | |
Roman Elizarov | aa461cf | 2018-04-11 13:20:29 +0300 | [diff] [blame] | 179 | public actual inline fun addLastIfPrevAndIf( |
Roman Elizarov | 6c63aea | 2017-02-02 12:20:48 +0300 | [diff] [blame] | 180 | node: Node, |
| 181 | predicate: (Node) -> Boolean, // prev node predicate |
| 182 | crossinline condition: () -> Boolean // atomically checked condition |
| 183 | ): Boolean { |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 184 | val condAdd = makeCondAddOp(node, condition) |
Roman Elizarov | 6c63aea | 2017-02-02 12:20:48 +0300 | [diff] [blame] | 185 | while (true) { // lock-free loop on prev.next |
Roman Elizarov | 3aed4ee | 2017-03-06 12:21:05 +0300 | [diff] [blame] | 186 | val prev = prev as Node // sentinel node is never removed, so prev is always defined |
Roman Elizarov | 6c63aea | 2017-02-02 12:20:48 +0300 | [diff] [blame] | 187 | if (!predicate(prev)) return false |
| 188 | when (prev.tryCondAddNext(node, this, condAdd)) { |
| 189 | SUCCESS -> return true |
| 190 | FAILURE -> return false |
| 191 | } |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 192 | } |
| 193 | } |
| 194 | |
Roman Elizarov | 6c63aea | 2017-02-02 12:20:48 +0300 | [diff] [blame] | 195 | // ------ addXXX util ------ |
| 196 | |
Roman Elizarov | db0d4fc | 2018-01-29 10:50:20 +0300 | [diff] [blame] | 197 | /** |
| 198 | * Given: |
| 199 | * ``` |
| 200 | * +-----------------------+ |
| 201 | * this | node V next |
| 202 | * +---+---+ +---+---+ +---+---+ |
| 203 | * ... <-- | P | N | | P | N | | P | N | --> .... |
| 204 | * +---+---+ +---+---+ +---+---+ |
| 205 | * ^ | |
| 206 | * +-----------------------+ |
| 207 | * ``` |
| 208 | * Produces: |
| 209 | * ``` |
| 210 | * this node next |
| 211 | * +---+---+ +---+---+ +---+---+ |
| 212 | * ... <-- | P | N | ==> | P | N | --> | P | N | --> .... |
| 213 | * +---+---+ +---+---+ +---+---+ |
| 214 | * ^ | ^ | |
| 215 | * +---------+ +---------+ |
| 216 | * ``` |
| 217 | * Where `==>` denotes linearization point. |
| 218 | * Returns `false` if `next` was not following `this` node. |
| 219 | */ |
Roman Elizarov | f024608 | 2017-02-10 18:02:38 +0300 | [diff] [blame] | 220 | @PublishedApi |
| 221 | internal fun addNext(node: Node, next: Node): Boolean { |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 222 | node._prev.lazySet(this) |
| 223 | node._next.lazySet(next) |
| 224 | if (!_next.compareAndSet(next, node)) return false |
Roman Elizarov | 6c63aea | 2017-02-02 12:20:48 +0300 | [diff] [blame] | 225 | // added successfully (linearized add) -- fixup the list |
| 226 | node.finishAdd(next) |
| 227 | return true |
| 228 | } |
| 229 | |
| 230 | // returns UNDECIDED, SUCCESS or FAILURE |
Roman Elizarov | f024608 | 2017-02-10 18:02:38 +0300 | [diff] [blame] | 231 | @PublishedApi |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 232 | internal fun tryCondAddNext(node: Node, next: Node, condAdd: CondAddOp): Int { |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 233 | node._prev.lazySet(this) |
| 234 | node._next.lazySet(next) |
Roman Elizarov | 6c63aea | 2017-02-02 12:20:48 +0300 | [diff] [blame] | 235 | condAdd.oldNext = next |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 236 | if (!_next.compareAndSet(next, condAdd)) return UNDECIDED |
Roman Elizarov | 6c63aea | 2017-02-02 12:20:48 +0300 | [diff] [blame] | 237 | // added operation successfully (linearized) -- complete it & fixup the list |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 238 | return if (condAdd.perform(this) == null) SUCCESS else FAILURE |
Roman Elizarov | 01934df | 2017-01-31 09:18:34 +0300 | [diff] [blame] | 239 | } |
| 240 | |
| 241 | // ------ removeXXX ------ |
| 242 | |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 243 | /** |
Roman Elizarov | e9f6449 | 2017-07-11 12:50:00 +0300 | [diff] [blame] | 244 | * Removes this node from the list. Returns `true` when removed successfully, or `false` if the node was already |
| 245 | * removed or if it was not added to any list in the first place. |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 246 | */ |
Roman Elizarov | aa461cf | 2018-04-11 13:20:29 +0300 | [diff] [blame] | 247 | public actual open fun remove(): Boolean { |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 248 | while (true) { // lock-free loop on next |
| 249 | val next = this.next |
Roman Elizarov | 53a0a40 | 2017-01-19 20:21:57 +0300 | [diff] [blame] | 250 | if (next is Removed) return false // was already removed -- don't try to help (original thread will take care) |
Roman Elizarov | e9f6449 | 2017-07-11 12:50:00 +0300 | [diff] [blame] | 251 | if (next === this) return false // was not even added |
Roman Elizarov | 1216e91 | 2017-02-22 09:57:06 +0300 | [diff] [blame] | 252 | val removed = (next as Node).removed() |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 253 | if (_next.compareAndSet(next, removed)) { |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 254 | // was removed successfully (linearized remove) -- fixup the list |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 255 | finishRemove(next) |
Roman Elizarov | 53a0a40 | 2017-01-19 20:21:57 +0300 | [diff] [blame] | 256 | return true |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 257 | } |
| 258 | } |
| 259 | } |
| 260 | |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 261 | public open fun describeRemove() : AtomicDesc? { |
| 262 | if (isRemoved) return null // fast path if was already removed |
| 263 | return object : AbstractAtomicDesc() { |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 264 | private val _originalNext = atomic<Node?>(null) |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 265 | override val affectedNode: Node? get() = this@LockFreeLinkedListNode |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 266 | override val originalNext get() = _originalNext.value |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 267 | override fun failure(affected: Node, next: Any): Any? = |
| 268 | if (next is Removed) ALREADY_REMOVED else null |
Roman Elizarov | 1216e91 | 2017-02-22 09:57:06 +0300 | [diff] [blame] | 269 | override fun onPrepare(affected: Node, next: Node): Any? { |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 270 | // Note: onPrepare must use CAS to make sure the stale invocation is not |
| 271 | // going to overwrite the previous decision on successful preparation. |
| 272 | // Result of CAS is irrelevant, but we must ensure that it is set when invoker completes |
| 273 | _originalNext.compareAndSet(null, next) |
Roman Elizarov | 1216e91 | 2017-02-22 09:57:06 +0300 | [diff] [blame] | 274 | return null // always success |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 275 | } |
Roman Elizarov | 1216e91 | 2017-02-22 09:57:06 +0300 | [diff] [blame] | 276 | override fun updatedNext(affected: Node, next: Node) = next.removed() |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 277 | override fun finishOnSuccess(affected: Node, next: Node) = finishRemove(next) |
Roman Elizarov | 53a0a40 | 2017-01-19 20:21:57 +0300 | [diff] [blame] | 278 | } |
| 279 | } |
| 280 | |
Roman Elizarov | aa461cf | 2018-04-11 13:20:29 +0300 | [diff] [blame] | 281 | public actual fun removeFirstOrNull(): Node? { |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 282 | while (true) { // try to linearize |
| 283 | val first = next as Node |
| 284 | if (first === this) return null |
| 285 | if (first.remove()) return first |
| 286 | first.helpDelete() // must help delete, or loose lock-freedom |
| 287 | } |
| 288 | } |
| 289 | |
| 290 | public fun describeRemoveFirst(): RemoveFirstDesc<Node> = RemoveFirstDesc(this) |
| 291 | |
Roman Elizarov | f024608 | 2017-02-10 18:02:38 +0300 | [diff] [blame] | 292 | public inline fun <reified T> removeFirstIfIsInstanceOf(): T? { |
Roman Elizarov | 01934df | 2017-01-31 09:18:34 +0300 | [diff] [blame] | 293 | while (true) { // try to linearize |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 294 | val first = next as Node |
| 295 | if (first === this) return null |
Roman Elizarov | 01934df | 2017-01-31 09:18:34 +0300 | [diff] [blame] | 296 | if (first !is T) return null |
| 297 | if (first.remove()) return first |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 298 | first.helpDelete() // must help delete, or loose lock-freedom |
Roman Elizarov | 01934df | 2017-01-31 09:18:34 +0300 | [diff] [blame] | 299 | } |
| 300 | } |
| 301 | |
| 302 | // just peek at item when predicate is true |
Roman Elizarov | aa461cf | 2018-04-11 13:20:29 +0300 | [diff] [blame] | 303 | public actual inline fun <reified T> removeFirstIfIsInstanceOfOrPeekIf(predicate: (T) -> Boolean): T? { |
Roman Elizarov | 01934df | 2017-01-31 09:18:34 +0300 | [diff] [blame] | 304 | while (true) { // try to linearize |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 305 | val first = next as Node |
| 306 | if (first === this) return null |
Roman Elizarov | 01934df | 2017-01-31 09:18:34 +0300 | [diff] [blame] | 307 | if (first !is T) return null |
| 308 | if (predicate(first)) return first // just peek when predicate is true |
| 309 | if (first.remove()) return first |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 310 | first.helpDelete() // must help delete, or loose lock-freedom |
| 311 | } |
| 312 | } |
| 313 | |
| 314 | // ------ multi-word atomic operations helpers ------ |
| 315 | |
Vsevolod Tolstopyatov | 9619134 | 2018-04-20 18:13:33 +0300 | [diff] [blame] | 316 | public open class AddLastDesc<T : Node> constructor( |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 317 | @JvmField val queue: Node, |
| 318 | @JvmField val node: T |
| 319 | ) : AbstractAtomicDesc() { |
Roman Elizarov | 1216e91 | 2017-02-22 09:57:06 +0300 | [diff] [blame] | 320 | init { |
| 321 | // require freshly allocated node here |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 322 | check(node._next.value === node && node._prev.value === node) |
Roman Elizarov | 1216e91 | 2017-02-22 09:57:06 +0300 | [diff] [blame] | 323 | } |
| 324 | |
| 325 | final override fun takeAffectedNode(op: OpDescriptor): Node { |
| 326 | while (true) { |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 327 | val prev = queue._prev.value as Node // this sentinel node is never removed |
| 328 | val next = prev._next.value |
Roman Elizarov | 1216e91 | 2017-02-22 09:57:06 +0300 | [diff] [blame] | 329 | if (next === queue) return prev // all is good -> linked properly |
| 330 | if (next === op) return prev // all is good -> our operation descriptor is already there |
| 331 | if (next is OpDescriptor) { // some other operation descriptor -> help & retry |
| 332 | next.perform(prev) |
| 333 | continue |
| 334 | } |
| 335 | // linked improperly -- help insert |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 336 | val affected = queue.correctPrev(prev, op) |
| 337 | // we can find node which this operation is already affecting while trying to correct prev |
| 338 | if (affected != null) return affected |
Roman Elizarov | 1216e91 | 2017-02-22 09:57:06 +0300 | [diff] [blame] | 339 | } |
| 340 | } |
| 341 | |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 342 | private val _affectedNode = atomic<Node?>(null) |
| 343 | final override val affectedNode: Node? get() = _affectedNode.value |
Roman Elizarov | 1216e91 | 2017-02-22 09:57:06 +0300 | [diff] [blame] | 344 | final override val originalNext: Node? get() = queue |
| 345 | |
| 346 | override fun retry(affected: Node, next: Any): Boolean = next !== queue |
| 347 | |
Roman Elizarov | aa461cf | 2018-04-11 13:20:29 +0300 | [diff] [blame] | 348 | protected override fun onPrepare(affected: Node, next: Node): Any? { |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 349 | // Note: onPrepare must use CAS to make sure the stale invocation is not |
| 350 | // going to overwrite the previous decision on successful preparation. |
| 351 | // Result of CAS is irrelevant, but we must ensure that it is set when invoker completes |
| 352 | _affectedNode.compareAndSet(null, affected) |
Roman Elizarov | 1216e91 | 2017-02-22 09:57:06 +0300 | [diff] [blame] | 353 | return null // always success |
| 354 | } |
| 355 | |
| 356 | override fun updatedNext(affected: Node, next: Node): Any { |
| 357 | // it is invoked only on successfully completion of operation, but this invocation can be stale, |
| 358 | // so we must use CAS to set both prev & next pointers |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 359 | node._prev.compareAndSet(node, affected) |
| 360 | node._next.compareAndSet(node, queue) |
Roman Elizarov | 1216e91 | 2017-02-22 09:57:06 +0300 | [diff] [blame] | 361 | return node |
| 362 | } |
| 363 | |
| 364 | override fun finishOnSuccess(affected: Node, next: Node) { |
| 365 | node.finishAdd(queue) |
| 366 | } |
| 367 | } |
| 368 | |
Roman Elizarov | 174c696 | 2017-02-28 17:36:51 +0300 | [diff] [blame] | 369 | public open class RemoveFirstDesc<T>( |
| 370 | @JvmField val queue: Node |
| 371 | ) : AbstractAtomicDesc() { |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 372 | private val _affectedNode = atomic<Node?>(null) |
| 373 | private val _originalNext = atomic<Node?>(null) |
| 374 | |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 375 | @Suppress("UNCHECKED_CAST") |
| 376 | public val result: T get() = affectedNode!! as T |
| 377 | |
Roman Elizarov | 1216e91 | 2017-02-22 09:57:06 +0300 | [diff] [blame] | 378 | final override fun takeAffectedNode(op: OpDescriptor): Node = queue.next as Node |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 379 | final override val affectedNode: Node? get() = _affectedNode.value |
| 380 | final override val originalNext: Node? get() = _originalNext.value |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 381 | |
| 382 | // check node predicates here, must signal failure if affect is not of type T |
| 383 | protected override fun failure(affected: Node, next: Any): Any? = |
| 384 | if (affected === queue) LIST_EMPTY else null |
Roman Elizarov | 1216e91 | 2017-02-22 09:57:06 +0300 | [diff] [blame] | 385 | |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 386 | // validate the resulting node (return false if it should be deleted) |
| 387 | protected open fun validatePrepared(node: T): Boolean = true // false means remove node & retry |
| 388 | |
| 389 | final override fun retry(affected: Node, next: Any): Boolean { |
| 390 | if (next !is Removed) return false |
| 391 | affected.helpDelete() // must help delete, or loose lock-freedom |
| 392 | return true |
| 393 | } |
Roman Elizarov | 1216e91 | 2017-02-22 09:57:06 +0300 | [diff] [blame] | 394 | |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 395 | @Suppress("UNCHECKED_CAST") |
Roman Elizarov | 1216e91 | 2017-02-22 09:57:06 +0300 | [diff] [blame] | 396 | final override fun onPrepare(affected: Node, next: Node): Any? { |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 397 | check(affected !is LockFreeLinkedListHead) |
Roman Elizarov | 1216e91 | 2017-02-22 09:57:06 +0300 | [diff] [blame] | 398 | if (!validatePrepared(affected as T)) return REMOVE_PREPARED |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 399 | // Note: onPrepare must use CAS to make sure the stale invocation is not |
| 400 | // going to overwrite the previous decision on successful preparation. |
| 401 | // Result of CAS is irrelevant, but we must ensure that it is set when invoker completes |
| 402 | _affectedNode.compareAndSet(null, affected) |
| 403 | _originalNext.compareAndSet(null, next) |
Roman Elizarov | 1216e91 | 2017-02-22 09:57:06 +0300 | [diff] [blame] | 404 | return null // ok |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 405 | } |
Roman Elizarov | 1216e91 | 2017-02-22 09:57:06 +0300 | [diff] [blame] | 406 | |
| 407 | final override fun updatedNext(affected: Node, next: Node): Any = next.removed() |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 408 | final override fun finishOnSuccess(affected: Node, next: Node) = affected.finishRemove(next) |
| 409 | } |
| 410 | |
| 411 | public abstract class AbstractAtomicDesc : AtomicDesc() { |
| 412 | protected abstract val affectedNode: Node? |
| 413 | protected abstract val originalNext: Node? |
Roman Elizarov | 1216e91 | 2017-02-22 09:57:06 +0300 | [diff] [blame] | 414 | protected open fun takeAffectedNode(op: OpDescriptor): Node = affectedNode!! |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 415 | protected open fun failure(affected: Node, next: Any): Any? = null // next: Node | Removed |
| 416 | protected open fun retry(affected: Node, next: Any): Boolean = false // next: Node | Removed |
Roman Elizarov | 1216e91 | 2017-02-22 09:57:06 +0300 | [diff] [blame] | 417 | protected abstract fun onPrepare(affected: Node, next: Node): Any? // non-null on failure |
| 418 | protected abstract fun updatedNext(affected: Node, next: Node): Any |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 419 | protected abstract fun finishOnSuccess(affected: Node, next: Node) |
| 420 | |
| 421 | // This is Harris's RDCSS (Restricted Double-Compare Single Swap) operation |
| 422 | // It inserts "op" descriptor of when "op" status is still undecided (rolls back otherwise) |
| 423 | private class PrepareOp( |
Roman Elizarov | 1216e91 | 2017-02-22 09:57:06 +0300 | [diff] [blame] | 424 | @JvmField val next: Node, |
Roman Elizarov | d82b3a9 | 2017-06-23 21:52:08 +0300 | [diff] [blame] | 425 | @JvmField val op: AtomicOp<Node>, |
Roman Elizarov | 1216e91 | 2017-02-22 09:57:06 +0300 | [diff] [blame] | 426 | @JvmField val desc: AbstractAtomicDesc |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 427 | ) : OpDescriptor() { |
| 428 | override fun perform(affected: Any?): Any? { |
| 429 | affected as Node // type assertion |
Roman Elizarov | 1216e91 | 2017-02-22 09:57:06 +0300 | [diff] [blame] | 430 | val decision = desc.onPrepare(affected, next) |
| 431 | if (decision != null) { |
| 432 | if (decision === REMOVE_PREPARED) { |
| 433 | // remove element on failure |
| 434 | val removed = next.removed() |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 435 | if (affected._next.compareAndSet(this, removed)) { |
Roman Elizarov | 1216e91 | 2017-02-22 09:57:06 +0300 | [diff] [blame] | 436 | affected.helpDelete() |
| 437 | } |
| 438 | } else { |
| 439 | // some other failure -- mark as decided |
| 440 | op.tryDecide(decision) |
| 441 | // undo preparations |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 442 | affected._next.compareAndSet(this, next) |
Roman Elizarov | 1216e91 | 2017-02-22 09:57:06 +0300 | [diff] [blame] | 443 | } |
| 444 | return decision |
| 445 | } |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 446 | val update: Any = if (op.isDecided) next else op // restore if decision was already reached |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 447 | affected._next.compareAndSet(this, update) |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 448 | return null // ok |
| 449 | } |
| 450 | } |
| 451 | |
Roman Elizarov | d82b3a9 | 2017-06-23 21:52:08 +0300 | [diff] [blame] | 452 | @Suppress("UNCHECKED_CAST") |
| 453 | final override fun prepare(op: AtomicOp<*>): Any? { |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 454 | while (true) { // lock free loop on next |
Roman Elizarov | 1216e91 | 2017-02-22 09:57:06 +0300 | [diff] [blame] | 455 | val affected = takeAffectedNode(op) |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 456 | // read its original next pointer first |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 457 | val next = affected._next.value |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 458 | // then see if already reached consensus on overall operation |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 459 | if (next === op) return null // already in process of operation -- all is good |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 460 | if (op.isDecided) return null // already decided this operation -- go to next desc |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 461 | if (next is OpDescriptor) { |
| 462 | // some other operation is in process -- help it |
| 463 | next.perform(affected) |
| 464 | continue // and retry |
| 465 | } |
| 466 | // next: Node | Removed |
| 467 | val failure = failure(affected, next) |
| 468 | if (failure != null) return failure // signal failure |
| 469 | if (retry(affected, next)) continue // retry operation |
Roman Elizarov | d82b3a9 | 2017-06-23 21:52:08 +0300 | [diff] [blame] | 470 | val prepareOp = PrepareOp(next as Node, op as AtomicOp<Node>, this) |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 471 | if (affected._next.compareAndSet(next, prepareOp)) { |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 472 | // prepared -- complete preparations |
Roman Elizarov | 1216e91 | 2017-02-22 09:57:06 +0300 | [diff] [blame] | 473 | val prepFail = prepareOp.perform(affected) |
| 474 | if (prepFail === REMOVE_PREPARED) continue // retry |
| 475 | return prepFail |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 476 | } |
| 477 | } |
| 478 | } |
| 479 | |
Roman Elizarov | d82b3a9 | 2017-06-23 21:52:08 +0300 | [diff] [blame] | 480 | final override fun complete(op: AtomicOp<*>, failure: Any?) { |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 481 | val success = failure == null |
Roman Elizarov | 1216e91 | 2017-02-22 09:57:06 +0300 | [diff] [blame] | 482 | val affectedNode = affectedNode ?: run { check(!success); return } |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 483 | val originalNext = originalNext ?: run { check(!success); return } |
Roman Elizarov | 1216e91 | 2017-02-22 09:57:06 +0300 | [diff] [blame] | 484 | val update = if (success) updatedNext(affectedNode, originalNext) else originalNext |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 485 | if (affectedNode._next.compareAndSet(op, update)) { |
Roman Elizarov | 1216e91 | 2017-02-22 09:57:06 +0300 | [diff] [blame] | 486 | if (success) finishOnSuccess(affectedNode, originalNext) |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 487 | } |
Roman Elizarov | 01934df | 2017-01-31 09:18:34 +0300 | [diff] [blame] | 488 | } |
| 489 | } |
| 490 | |
| 491 | // ------ other helpers ------ |
| 492 | |
Roman Elizarov | db0d4fc | 2018-01-29 10:50:20 +0300 | [diff] [blame] | 493 | /** |
| 494 | * Given: |
| 495 | * ``` |
| 496 | * |
| 497 | * prev this next |
| 498 | * +---+---+ +---+---+ +---+---+ |
| 499 | * ... <-- | P | N | --> | P | N | --> | P | N | --> .... |
| 500 | * +---+---+ +---+---+ +---+---+ |
| 501 | * ^ ^ | | |
| 502 | * | +---------+ | |
| 503 | * +-------------------------+ |
| 504 | * ``` |
| 505 | * Produces: |
| 506 | * ``` |
| 507 | * prev this next |
| 508 | * +---+---+ +---+---+ +---+---+ |
| 509 | * ... <-- | P | N | --> | P | N | --> | P | N | --> .... |
| 510 | * +---+---+ +---+---+ +---+---+ |
| 511 | * ^ | ^ | |
| 512 | * +---------+ +---------+ |
| 513 | * ``` |
| 514 | */ |
Roman Elizarov | 01934df | 2017-01-31 09:18:34 +0300 | [diff] [blame] | 515 | private fun finishAdd(next: Node) { |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 516 | next._prev.loop { nextPrev -> |
Roman Elizarov | 01934df | 2017-01-31 09:18:34 +0300 | [diff] [blame] | 517 | if (nextPrev is Removed || this.next !== next) return // next was removed, remover fixes up links |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 518 | if (next._prev.compareAndSet(nextPrev, this)) { |
Roman Elizarov | 01934df | 2017-01-31 09:18:34 +0300 | [diff] [blame] | 519 | if (this.next is Removed) { |
| 520 | // already removed |
Roman Elizarov | b78fa42 | 2017-07-05 09:54:03 +0300 | [diff] [blame] | 521 | next.correctPrev(nextPrev as Node, null) |
Roman Elizarov | 01934df | 2017-01-31 09:18:34 +0300 | [diff] [blame] | 522 | } |
| 523 | return |
| 524 | } |
| 525 | } |
| 526 | } |
| 527 | |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 528 | private fun finishRemove(next: Node) { |
| 529 | helpDelete() |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 530 | next.correctPrev(_prev.value.unwrap(), null) |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 531 | } |
| 532 | |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 533 | private fun markPrev(): Node { |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 534 | _prev.loop { prev -> |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 535 | if (prev is Removed) return prev.ref |
Roman Elizarov | 0aa6db0 | 2018-01-29 13:18:38 +0300 | [diff] [blame] | 536 | // See detailed comment in findHead on why `prev === this` is a special case for which we know that |
| 537 | // the prev should have being pointing to the head of list but finishAdd that was supposed |
| 538 | // to do that is not complete yet. |
| 539 | val removedPrev = (if (prev === this) findHead() else (prev as Node)).removed() |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 540 | if (_prev.compareAndSet(prev, removedPrev)) return prev |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 541 | } |
| 542 | } |
| 543 | |
Roman Elizarov | 0aa6db0 | 2018-01-29 13:18:38 +0300 | [diff] [blame] | 544 | /** |
| 545 | * Finds the head of the list (implementing [LockFreeLinkedListHead]) by following [next] pointers. |
| 546 | * |
| 547 | * The code in [kotlinx.coroutines.experimental.JobSupport] performs upgrade of a single node to a list. |
| 548 | * It uses [addOneIfEmpty] to add the list head to "empty list of a single node" once. |
| 549 | * During upgrade a transient state of the list looks like this: |
| 550 | * |
| 551 | * ``` |
| 552 | * +-----------------+ |
| 553 | * | | |
| 554 | * node V head | |
| 555 | * +---+---+ +---+---+ | |
| 556 | * +-> | P | N | --> | P | N |-+ |
| 557 | * | +---+---+ +---+---+ |
| 558 | * | | ^ | |
| 559 | * +---- + +---------+ |
| 560 | * ``` |
| 561 | * |
| 562 | * The [prev] pointer in `node` still points to itself when [finishAdd] (invoked inside [addOneIfEmpty]) |
| 563 | * has not completed yet. If this state is observed, then we know that [prev] should have been pointing |
| 564 | * to the list head. This function is looking up the head by following consistent chain of [next] pointers. |
| 565 | */ |
| 566 | private fun findHead(): Node { |
| 567 | var cur = this |
| 568 | while (true) { |
| 569 | if (cur is LockFreeLinkedListHead) return cur |
Roman Elizarov | 0406a9b | 2018-04-26 12:35:43 +0300 | [diff] [blame^] | 570 | cur = cur.nextNode |
Roman Elizarov | 0aa6db0 | 2018-01-29 13:18:38 +0300 | [diff] [blame] | 571 | check(cur !== this) { "Cannot loop to this while looking for list head" } |
| 572 | } |
| 573 | } |
| 574 | |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 575 | // fixes next links to the left of this node |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 576 | @PublishedApi |
| 577 | internal fun helpDelete() { |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 578 | var last: Node? = null // will set to the node left of prev when found |
| 579 | var prev: Node = markPrev() |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 580 | var next: Node = (this._next.value as Removed).ref |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 581 | while (true) { |
| 582 | // move to the right until first non-removed node |
| 583 | val nextNext = next.next |
| 584 | if (nextNext is Removed) { |
| 585 | next.markPrev() |
| 586 | next = nextNext.ref |
| 587 | continue |
| 588 | } |
| 589 | // move the the left until first non-removed node |
| 590 | val prevNext = prev.next |
| 591 | if (prevNext is Removed) { |
| 592 | if (last != null) { |
| 593 | prev.markPrev() |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 594 | last._next.compareAndSet(prev, prevNext.ref) |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 595 | prev = last |
| 596 | last = null |
| 597 | } else { |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 598 | prev = prev._prev.value.unwrap() |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 599 | } |
| 600 | continue |
| 601 | } |
| 602 | if (prevNext !== this) { |
| 603 | // skipped over some removed nodes to the left -- setup to fixup the next links |
| 604 | last = prev |
| 605 | prev = prevNext as Node |
| 606 | if (prev === next) return // already done!!! |
| 607 | continue |
| 608 | } |
| 609 | // Now prev & next are Ok |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 610 | if (prev._next.compareAndSet(this, next)) return // success! |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 611 | } |
| 612 | } |
| 613 | |
| 614 | // fixes prev links from this node |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 615 | // returns affected node by this operation when this op is in progress (and nothing can be corrected) |
| 616 | // returns null otherwise (prev was corrected) |
| 617 | private fun correctPrev(_prev: Node, op: OpDescriptor?): Node? { |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 618 | var prev: Node = _prev |
| 619 | var last: Node? = null // will be set so that last.next === prev |
| 620 | while (true) { |
| 621 | // move the the left until first non-removed node |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 622 | val prevNext = prev._next.value |
| 623 | if (prevNext === op) return prev // part of the same op -- don't recurse, didn't correct prev |
Roman Elizarov | 1216e91 | 2017-02-22 09:57:06 +0300 | [diff] [blame] | 624 | if (prevNext is OpDescriptor) { // help & retry |
| 625 | prevNext.perform(prev) |
| 626 | continue |
| 627 | } |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 628 | if (prevNext is Removed) { |
| 629 | if (last !== null) { |
| 630 | prev.markPrev() |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 631 | last._next.compareAndSet(prev, prevNext.ref) |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 632 | prev = last |
| 633 | last = null |
| 634 | } else { |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 635 | prev = prev._prev.value.unwrap() |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 636 | } |
| 637 | continue |
| 638 | } |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 639 | val oldPrev = this._prev.value |
| 640 | if (oldPrev is Removed) return null // this node was removed, too -- its remover will take care |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 641 | if (prevNext !== this) { |
| 642 | // need to fixup next |
| 643 | last = prev |
| 644 | prev = prevNext as Node |
| 645 | continue |
| 646 | } |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 647 | if (oldPrev === prev) return null // it is already linked as needed |
| 648 | if (this._prev.compareAndSet(oldPrev, prev)) { |
| 649 | if (prev._prev.value !is Removed) return null // finish only if prev was not concurrently removed |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 650 | } |
| 651 | } |
| 652 | } |
| 653 | |
Roman Elizarov | f024608 | 2017-02-10 18:02:38 +0300 | [diff] [blame] | 654 | internal fun validateNode(prev: Node, next: Node) { |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 655 | check(prev === this._prev.value) |
| 656 | check(next === this._next.value) |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 657 | } |
Roman Elizarov | 1216e91 | 2017-02-22 09:57:06 +0300 | [diff] [blame] | 658 | |
| 659 | override fun toString(): String = "${this::class.java.simpleName}@${Integer.toHexString(System.identityHashCode(this))}" |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 660 | } |
| 661 | |
Roman Elizarov | 1216e91 | 2017-02-22 09:57:06 +0300 | [diff] [blame] | 662 | private class Removed(@JvmField val ref: Node) { |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 663 | override fun toString(): String = "Removed[$ref]" |
| 664 | } |
| 665 | |
| 666 | @PublishedApi |
Roman Elizarov | aa461cf | 2018-04-11 13:20:29 +0300 | [diff] [blame] | 667 | internal fun Any.unwrap(): Node = (this as? Removed)?.ref ?: this as Node |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 668 | |
Roman Elizarov | f024608 | 2017-02-10 18:02:38 +0300 | [diff] [blame] | 669 | /** |
| 670 | * Head (sentinel) item of the linked list that is never removed. |
| 671 | * |
| 672 | * @suppress **This is unstable API and it is subject to change.** |
| 673 | */ |
Roman Elizarov | aa461cf | 2018-04-11 13:20:29 +0300 | [diff] [blame] | 674 | public actual open class LockFreeLinkedListHead : LockFreeLinkedListNode() { |
| 675 | public actual val isEmpty: Boolean get() = next === this |
Roman Elizarov | 53a0a40 | 2017-01-19 20:21:57 +0300 | [diff] [blame] | 676 | |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 677 | /** |
| 678 | * Iterates over all elements in this list of a specified type. |
| 679 | */ |
Roman Elizarov | aa461cf | 2018-04-11 13:20:29 +0300 | [diff] [blame] | 680 | public actual inline fun <reified T : Node> forEach(block: (T) -> Unit) { |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 681 | var cur: Node = next as Node |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 682 | while (cur != this) { |
| 683 | if (cur is T) block(cur) |
Roman Elizarov | 0406a9b | 2018-04-26 12:35:43 +0300 | [diff] [blame^] | 684 | cur = cur.nextNode |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 685 | } |
| 686 | } |
| 687 | |
Roman Elizarov | 01934df | 2017-01-31 09:18:34 +0300 | [diff] [blame] | 688 | // just a defensive programming -- makes sure that list head sentinel is never removed |
Roman Elizarov | aa461cf | 2018-04-11 13:20:29 +0300 | [diff] [blame] | 689 | public actual final override fun remove(): Nothing = throw UnsupportedOperationException() |
| 690 | |
| 691 | public final override fun describeRemove(): Nothing = throw UnsupportedOperationException() |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 692 | |
Roman Elizarov | f024608 | 2017-02-10 18:02:38 +0300 | [diff] [blame] | 693 | internal fun validate() { |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 694 | var prev: Node = this |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 695 | var cur: Node = next as Node |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 696 | while (cur != this) { |
Roman Elizarov | 0406a9b | 2018-04-26 12:35:43 +0300 | [diff] [blame^] | 697 | val next = cur.nextNode |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 698 | cur.validateNode(prev, next) |
| 699 | prev = cur |
| 700 | cur = next |
| 701 | } |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 702 | validateNode(prev, next as Node) |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 703 | } |
| 704 | } |