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