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 | |
| 19 | import java.util.concurrent.atomic.AtomicIntegerFieldUpdater |
| 20 | import java.util.concurrent.atomic.AtomicReferenceFieldUpdater |
| 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 | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 33 | /** |
| 34 | * Doubly-linked concurrent list node with remove support. |
| 35 | * Based on paper |
| 36 | * ["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) |
| 37 | * by Sundell and Tsigas. |
| 38 | * The instance of this class serves both as list head/tail sentinel and as the list item. |
| 39 | * Sentinel node should be never removed. |
Roman Elizarov | f024608 | 2017-02-10 18:02:38 +0300 | [diff] [blame] | 40 | * |
| 41 | * @suppress **This is unstable API and it is subject to change.** |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 42 | */ |
| 43 | @Suppress("LeakingThis") |
Roman Elizarov | f024608 | 2017-02-10 18:02:38 +0300 | [diff] [blame] | 44 | public open class LockFreeLinkedListNode { |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 45 | @Volatile |
| 46 | private var _next: Any = this // DoubleLinkedNode | Removed | CondAdd |
| 47 | @Volatile |
| 48 | private var prev: Any = this // DoubleLinkedNode | Removed |
Roman Elizarov | 6f82783 | 2017-01-25 16:42:23 +0300 | [diff] [blame] | 49 | @Volatile |
| 50 | private var removedRef: Removed? = null // lazily cached removed ref to this |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 51 | |
| 52 | private companion object { |
| 53 | @JvmStatic |
| 54 | val NEXT: AtomicReferenceFieldUpdater<Node, Any> = |
| 55 | AtomicReferenceFieldUpdater.newUpdater(Node::class.java, Any::class.java, "_next") |
| 56 | @JvmStatic |
| 57 | val PREV: AtomicReferenceFieldUpdater<Node, Any> = |
| 58 | AtomicReferenceFieldUpdater.newUpdater(Node::class.java, Any::class.java, "prev") |
Roman Elizarov | 6f82783 | 2017-01-25 16:42:23 +0300 | [diff] [blame] | 59 | @JvmStatic |
| 60 | val REMOVED_REF: AtomicReferenceFieldUpdater<Node, Removed?> = |
| 61 | AtomicReferenceFieldUpdater.newUpdater(Node::class.java, Removed::class.java, "removedRef") |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 62 | } |
| 63 | |
| 64 | private class Removed(val ref: Node) { |
| 65 | override fun toString(): String = "Removed[$ref]" |
| 66 | } |
| 67 | |
Roman Elizarov | 6f82783 | 2017-01-25 16:42:23 +0300 | [diff] [blame] | 68 | private fun removed(): Removed = |
| 69 | removedRef ?: Removed(this).also { REMOVED_REF.lazySet(this, it) } |
| 70 | |
Roman Elizarov | f024608 | 2017-02-10 18:02:38 +0300 | [diff] [blame] | 71 | @PublishedApi |
| 72 | internal abstract class CondAdd(val newNode: Node) { |
Roman Elizarov | 6c63aea | 2017-02-02 12:20:48 +0300 | [diff] [blame] | 73 | lateinit var oldNext: Node |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 74 | @Volatile |
| 75 | private var consensus: Int = UNDECIDED // status of operation |
Roman Elizarov | 6c63aea | 2017-02-02 12:20:48 +0300 | [diff] [blame] | 76 | |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 77 | abstract fun isCondition(): Boolean |
| 78 | |
| 79 | private companion object { |
| 80 | @JvmStatic |
| 81 | val CONSENSUS: AtomicIntegerFieldUpdater<CondAdd> = |
Roman Elizarov | 6c63aea | 2017-02-02 12:20:48 +0300 | [diff] [blame] | 82 | AtomicIntegerFieldUpdater.newUpdater(CondAdd::class.java, "consensus") |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 83 | } |
| 84 | |
Roman Elizarov | 6c63aea | 2017-02-02 12:20:48 +0300 | [diff] [blame] | 85 | // returns either SUCCESS or FAILURE |
| 86 | fun completeAdd(node: Node): Int { |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 87 | // make decision on status |
| 88 | var consensus: Int |
| 89 | while (true) { |
| 90 | consensus = this.consensus |
| 91 | if (consensus != UNDECIDED) break |
| 92 | val proposal = if (isCondition()) SUCCESS else FAILURE |
| 93 | if (CONSENSUS.compareAndSet(this, UNDECIDED, proposal)) { |
| 94 | consensus = proposal |
| 95 | break |
| 96 | } |
| 97 | } |
| 98 | val success = consensus == SUCCESS |
| 99 | if (NEXT.compareAndSet(node, this, if (success) newNode else oldNext)) { |
| 100 | // only the thread the makes this update actually finishes add operation |
| 101 | if (success) newNode.finishAdd(oldNext) |
| 102 | } |
Roman Elizarov | 6c63aea | 2017-02-02 12:20:48 +0300 | [diff] [blame] | 103 | return consensus |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 104 | } |
| 105 | } |
| 106 | |
Roman Elizarov | f024608 | 2017-02-10 18:02:38 +0300 | [diff] [blame] | 107 | @PublishedApi |
| 108 | internal inline fun makeCondAdd(node: Node, crossinline condition: () -> Boolean): CondAdd = object : CondAdd(node) { |
Roman Elizarov | 6c63aea | 2017-02-02 12:20:48 +0300 | [diff] [blame] | 109 | override fun isCondition(): Boolean = condition() |
| 110 | } |
| 111 | |
Roman Elizarov | f024608 | 2017-02-10 18:02:38 +0300 | [diff] [blame] | 112 | public val isRemoved: Boolean get() = _next is Removed |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 113 | |
| 114 | private val isFresh: Boolean get() = _next === this && prev === this |
| 115 | |
Roman Elizarov | f024608 | 2017-02-10 18:02:38 +0300 | [diff] [blame] | 116 | @PublishedApi |
| 117 | internal val next: Any get() { |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 118 | while (true) { // helper loop on _next |
| 119 | val next = this._next |
| 120 | if (next !is CondAdd) return next |
| 121 | next.completeAdd(this) |
| 122 | } |
| 123 | } |
| 124 | |
Roman Elizarov | f024608 | 2017-02-10 18:02:38 +0300 | [diff] [blame] | 125 | public fun next(): Node = next.unwrap() |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 126 | |
Roman Elizarov | f024608 | 2017-02-10 18:02:38 +0300 | [diff] [blame] | 127 | public fun prev(): Node { |
Roman Elizarov | 01934df | 2017-01-31 09:18:34 +0300 | [diff] [blame] | 128 | while (true) { |
| 129 | prevHelper()?.let { return it.unwrap() } |
| 130 | } |
| 131 | } |
| 132 | |
| 133 | // ------ addFirstXXX ------ |
| 134 | |
Roman Elizarov | 6c63aea | 2017-02-02 12:20:48 +0300 | [diff] [blame] | 135 | /** |
| 136 | * Adds first item to this list. |
| 137 | */ |
Roman Elizarov | f024608 | 2017-02-10 18:02:38 +0300 | [diff] [blame] | 138 | public fun addFirst(node: Node) { |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 139 | while (true) { // lock-free loop on next |
| 140 | val next = this.next as Node // this sentinel node is never removed |
Roman Elizarov | 6c63aea | 2017-02-02 12:20:48 +0300 | [diff] [blame] | 141 | if (addNext(node, next)) return |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 142 | } |
| 143 | } |
| 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 first item to this list atomically if the [condition] is true. |
| 147 | */ |
Roman Elizarov | f024608 | 2017-02-10 18:02:38 +0300 | [diff] [blame] | 148 | public inline fun addFirstIf(node: Node, crossinline condition: () -> Boolean): Boolean { |
Roman Elizarov | 6c63aea | 2017-02-02 12:20:48 +0300 | [diff] [blame] | 149 | val condAdd = makeCondAdd(node, condition) |
| 150 | while (true) { // lock-free loop on next |
| 151 | val next = this.next as Node // this sentinel node is never removed |
| 152 | when (tryCondAddNext(node, next, 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 | f024608 | 2017-02-10 18:02:38 +0300 | [diff] [blame] | 159 | public fun addFirstIfEmpty(node: Node): Boolean { |
Roman Elizarov | daa7922 | 2017-01-26 11:31:31 +0300 | [diff] [blame] | 160 | PREV.lazySet(node, this) |
| 161 | NEXT.lazySet(node, this) |
| 162 | if (!NEXT.compareAndSet(this, this, node)) return false // this is not an empty list! |
| 163 | // added successfully (linearized add) -- fixup the list |
| 164 | node.finishAdd(this) |
| 165 | return true |
| 166 | } |
| 167 | |
Roman Elizarov | 01934df | 2017-01-31 09:18:34 +0300 | [diff] [blame] | 168 | // ------ addLastXXX ------ |
| 169 | |
Roman Elizarov | 6c63aea | 2017-02-02 12:20:48 +0300 | [diff] [blame] | 170 | /** |
| 171 | * Adds last item to this list. |
| 172 | */ |
Roman Elizarov | f024608 | 2017-02-10 18:02:38 +0300 | [diff] [blame] | 173 | public fun addLast(node: Node) { |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 174 | while (true) { // lock-free loop on prev.next |
Roman Elizarov | 01934df | 2017-01-31 09:18:34 +0300 | [diff] [blame] | 175 | val prev = prevHelper() ?: continue |
Roman Elizarov | 6c63aea | 2017-02-02 12:20:48 +0300 | [diff] [blame] | 176 | if (prev.addNext(node, this)) return |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 177 | } |
| 178 | } |
| 179 | |
Roman Elizarov | 01934df | 2017-01-31 09:18:34 +0300 | [diff] [blame] | 180 | /** |
Roman Elizarov | 01934df | 2017-01-31 09:18:34 +0300 | [diff] [blame] | 181 | * Adds last item to this list atomically if the [condition] is true. |
| 182 | */ |
Roman Elizarov | f024608 | 2017-02-10 18:02:38 +0300 | [diff] [blame] | 183 | public inline fun addLastIf(node: Node, crossinline condition: () -> Boolean): Boolean { |
Roman Elizarov | 6c63aea | 2017-02-02 12:20:48 +0300 | [diff] [blame] | 184 | val condAdd = makeCondAdd(node, condition) |
| 185 | while (true) { // lock-free loop on prev.next |
| 186 | val prev = prevHelper() ?: continue |
| 187 | when (prev.tryCondAddNext(node, this, condAdd)) { |
| 188 | SUCCESS -> return true |
| 189 | FAILURE -> return false |
| 190 | } |
| 191 | } |
| 192 | } |
Roman Elizarov | 01934df | 2017-01-31 09:18:34 +0300 | [diff] [blame] | 193 | |
Roman Elizarov | f024608 | 2017-02-10 18:02:38 +0300 | [diff] [blame] | 194 | public inline fun addLastIfPrev(node: Node, predicate: (Node) -> Boolean): Boolean { |
Roman Elizarov | 01934df | 2017-01-31 09:18:34 +0300 | [diff] [blame] | 195 | while (true) { // lock-free loop on prev.next |
| 196 | val prev = prevHelper() ?: continue |
| 197 | if (!predicate(prev)) return false |
Roman Elizarov | 6c63aea | 2017-02-02 12:20:48 +0300 | [diff] [blame] | 198 | if (prev.addNext(node, this)) return true |
| 199 | } |
| 200 | } |
| 201 | |
Roman Elizarov | f024608 | 2017-02-10 18:02:38 +0300 | [diff] [blame] | 202 | public inline fun addLastIfPrevAndIf( |
Roman Elizarov | 6c63aea | 2017-02-02 12:20:48 +0300 | [diff] [blame] | 203 | node: Node, |
| 204 | predicate: (Node) -> Boolean, // prev node predicate |
| 205 | crossinline condition: () -> Boolean // atomically checked condition |
| 206 | ): Boolean { |
| 207 | val condAdd = makeCondAdd(node, condition) |
| 208 | while (true) { // lock-free loop on prev.next |
| 209 | val prev = prevHelper() ?: continue |
| 210 | if (!predicate(prev)) return false |
| 211 | when (prev.tryCondAddNext(node, this, condAdd)) { |
| 212 | SUCCESS -> return true |
| 213 | FAILURE -> return false |
| 214 | } |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 215 | } |
| 216 | } |
| 217 | |
Roman Elizarov | f024608 | 2017-02-10 18:02:38 +0300 | [diff] [blame] | 218 | @PublishedApi |
| 219 | internal fun prevHelper(): Node? { |
Roman Elizarov | 01934df | 2017-01-31 09:18:34 +0300 | [diff] [blame] | 220 | val prev = this.prev as Node // this sentinel node is never removed |
| 221 | if (prev.next === this) return prev |
| 222 | helpInsert(prev) |
| 223 | return null |
| 224 | } |
| 225 | |
Roman Elizarov | 6c63aea | 2017-02-02 12:20:48 +0300 | [diff] [blame] | 226 | // ------ addXXX util ------ |
| 227 | |
Roman Elizarov | f024608 | 2017-02-10 18:02:38 +0300 | [diff] [blame] | 228 | @PublishedApi |
| 229 | internal fun addNext(node: Node, next: Node): Boolean { |
Roman Elizarov | 6c63aea | 2017-02-02 12:20:48 +0300 | [diff] [blame] | 230 | PREV.lazySet(node, this) |
| 231 | NEXT.lazySet(node, next) |
| 232 | if (!NEXT.compareAndSet(this, next, node)) return false |
| 233 | // added successfully (linearized add) -- fixup the list |
| 234 | node.finishAdd(next) |
| 235 | return true |
| 236 | } |
| 237 | |
| 238 | // returns UNDECIDED, SUCCESS or FAILURE |
Roman Elizarov | f024608 | 2017-02-10 18:02:38 +0300 | [diff] [blame] | 239 | @PublishedApi |
| 240 | internal fun tryCondAddNext(node: Node, next: Node, condAdd: CondAdd): Int { |
Roman Elizarov | 6c63aea | 2017-02-02 12:20:48 +0300 | [diff] [blame] | 241 | PREV.lazySet(node, this) |
| 242 | NEXT.lazySet(node, next) |
| 243 | condAdd.oldNext = next |
| 244 | if (!NEXT.compareAndSet(this, next, condAdd)) return UNDECIDED |
| 245 | // added operation successfully (linearized) -- complete it & fixup the list |
| 246 | return condAdd.completeAdd(this) |
Roman Elizarov | 01934df | 2017-01-31 09:18:34 +0300 | [diff] [blame] | 247 | } |
| 248 | |
| 249 | // ------ removeXXX ------ |
| 250 | |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 251 | /** |
Roman Elizarov | 53a0a40 | 2017-01-19 20:21:57 +0300 | [diff] [blame] | 252 | * Removes this node from the list. Returns `true` when removed successfully. |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 253 | */ |
Roman Elizarov | f024608 | 2017-02-10 18:02:38 +0300 | [diff] [blame] | 254 | public open fun remove(): Boolean { |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 255 | while (true) { // lock-free loop on next |
| 256 | val next = this.next |
Roman Elizarov | 53a0a40 | 2017-01-19 20:21:57 +0300 | [diff] [blame] | 257 | if (next is Removed) return false // was already removed -- don't try to help (original thread will take care) |
Roman Elizarov | 6f82783 | 2017-01-25 16:42:23 +0300 | [diff] [blame] | 258 | if (NEXT.compareAndSet(this, next, (next as Node).removed())) { |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 259 | // was removed successfully (linearized remove) -- fixup the list |
| 260 | helpDelete() |
| 261 | next.helpInsert(prev.unwrap()) |
Roman Elizarov | 53a0a40 | 2017-01-19 20:21:57 +0300 | [diff] [blame] | 262 | return true |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 263 | } |
| 264 | } |
| 265 | } |
| 266 | |
Roman Elizarov | f024608 | 2017-02-10 18:02:38 +0300 | [diff] [blame] | 267 | public fun removeFirstOrNull(): Node? { |
Roman Elizarov | 53a0a40 | 2017-01-19 20:21:57 +0300 | [diff] [blame] | 268 | while (true) { // try to linearize |
| 269 | val first = next() |
| 270 | if (first == this) return null |
| 271 | if (first.remove()) return first |
| 272 | } |
| 273 | } |
| 274 | |
Roman Elizarov | f024608 | 2017-02-10 18:02:38 +0300 | [diff] [blame] | 275 | public inline fun <reified T> removeFirstIfIsInstanceOf(): T? { |
Roman Elizarov | 01934df | 2017-01-31 09:18:34 +0300 | [diff] [blame] | 276 | while (true) { // try to linearize |
| 277 | val first = next() |
| 278 | if (first == this) return null |
| 279 | if (first !is T) return null |
| 280 | if (first.remove()) return first |
| 281 | } |
| 282 | } |
| 283 | |
| 284 | // just peek at item when predicate is true |
Roman Elizarov | f024608 | 2017-02-10 18:02:38 +0300 | [diff] [blame] | 285 | public inline fun <reified T> removeFirstIfIsInstanceOfOrPeekIf(predicate: (T) -> Boolean): T? { |
Roman Elizarov | 01934df | 2017-01-31 09:18:34 +0300 | [diff] [blame] | 286 | while (true) { // try to linearize |
| 287 | val first = next() |
| 288 | if (first == this) return null |
| 289 | if (first !is T) return null |
| 290 | if (predicate(first)) return first // just peek when predicate is true |
| 291 | if (first.remove()) return first |
| 292 | } |
| 293 | } |
| 294 | |
| 295 | // ------ other helpers ------ |
| 296 | |
| 297 | private fun finishAdd(next: Node) { |
| 298 | while (true) { |
| 299 | val nextPrev = next.prev |
| 300 | if (nextPrev is Removed || this.next !== next) return // next was removed, remover fixes up links |
| 301 | if (PREV.compareAndSet(next, nextPrev, this)) { |
| 302 | if (this.next is Removed) { |
| 303 | // already removed |
| 304 | next.helpInsert(nextPrev as Node) |
| 305 | } |
| 306 | return |
| 307 | } |
| 308 | } |
| 309 | } |
| 310 | |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 311 | private fun markPrev(): Node { |
| 312 | while (true) { // lock-free loop on prev |
| 313 | val prev = this.prev |
| 314 | if (prev is Removed) return prev.ref |
Roman Elizarov | 6f82783 | 2017-01-25 16:42:23 +0300 | [diff] [blame] | 315 | if (PREV.compareAndSet(this, prev, (prev as Node).removed())) return prev |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 316 | } |
| 317 | } |
| 318 | |
| 319 | // fixes next links to the left of this node |
| 320 | private fun helpDelete() { |
| 321 | var last: Node? = null // will set to the node left of prev when found |
| 322 | var prev: Node = markPrev() |
| 323 | var next: Node = (this._next as Removed).ref |
| 324 | while (true) { |
| 325 | // move to the right until first non-removed node |
| 326 | val nextNext = next.next |
| 327 | if (nextNext is Removed) { |
| 328 | next.markPrev() |
| 329 | next = nextNext.ref |
| 330 | continue |
| 331 | } |
| 332 | // move the the left until first non-removed node |
| 333 | val prevNext = prev.next |
| 334 | if (prevNext is Removed) { |
| 335 | if (last != null) { |
| 336 | prev.markPrev() |
| 337 | NEXT.compareAndSet(last, prev, prevNext.ref) |
| 338 | prev = last |
| 339 | last = null |
| 340 | } else { |
| 341 | prev = prev.prev.unwrap() |
| 342 | } |
| 343 | continue |
| 344 | } |
| 345 | if (prevNext !== this) { |
| 346 | // skipped over some removed nodes to the left -- setup to fixup the next links |
| 347 | last = prev |
| 348 | prev = prevNext as Node |
| 349 | if (prev === next) return // already done!!! |
| 350 | continue |
| 351 | } |
| 352 | // Now prev & next are Ok |
| 353 | if (NEXT.compareAndSet(prev, this, next)) return // success! |
| 354 | } |
| 355 | } |
| 356 | |
| 357 | // fixes prev links from this node |
| 358 | private fun helpInsert(_prev: Node) { |
| 359 | var prev: Node = _prev |
| 360 | var last: Node? = null // will be set so that last.next === prev |
| 361 | while (true) { |
| 362 | // move the the left until first non-removed node |
| 363 | val prevNext = prev.next |
| 364 | if (prevNext is Removed) { |
| 365 | if (last !== null) { |
| 366 | prev.markPrev() |
| 367 | NEXT.compareAndSet(last, prev, prevNext.ref) |
| 368 | prev = last |
| 369 | last = null |
| 370 | } else { |
| 371 | prev = prev.prev.unwrap() |
| 372 | } |
| 373 | continue |
| 374 | } |
| 375 | val oldPrev = this.prev |
| 376 | if (oldPrev is Removed) return // this node was removed, too -- its remover will take care |
| 377 | if (prevNext !== this) { |
| 378 | // need to fixup next |
| 379 | last = prev |
| 380 | prev = prevNext as Node |
| 381 | continue |
| 382 | } |
| 383 | if (oldPrev === prev) return // it is already linked as needed |
| 384 | if (PREV.compareAndSet(this, oldPrev, prev)) { |
| 385 | if (prev.prev !is Removed) return // finish only if prev was not concurrently removed |
| 386 | } |
| 387 | } |
| 388 | } |
| 389 | |
| 390 | private fun Any.unwrap(): Node = if (this is Removed) ref else this as Node |
| 391 | |
Roman Elizarov | f024608 | 2017-02-10 18:02:38 +0300 | [diff] [blame] | 392 | internal fun validateNode(prev: Node, next: Node) { |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 393 | check(prev === this.prev) |
| 394 | check(next === this.next) |
| 395 | } |
| 396 | } |
| 397 | |
Roman Elizarov | f024608 | 2017-02-10 18:02:38 +0300 | [diff] [blame] | 398 | /** |
| 399 | * Head (sentinel) item of the linked list that is never removed. |
| 400 | * |
| 401 | * @suppress **This is unstable API and it is subject to change.** |
| 402 | */ |
| 403 | public open class LockFreeLinkedListHead : LockFreeLinkedListNode() { |
| 404 | public val isEmpty: Boolean get() = next() == this |
Roman Elizarov | 53a0a40 | 2017-01-19 20:21:57 +0300 | [diff] [blame] | 405 | |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 406 | /** |
| 407 | * Iterates over all elements in this list of a specified type. |
| 408 | */ |
Roman Elizarov | f024608 | 2017-02-10 18:02:38 +0300 | [diff] [blame] | 409 | public inline fun <reified T : Node> forEach(block: (T) -> Unit) { |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 410 | var cur: Node = next() |
| 411 | while (cur != this) { |
| 412 | if (cur is T) block(cur) |
| 413 | cur = cur.next() |
| 414 | } |
| 415 | } |
| 416 | |
Roman Elizarov | 01934df | 2017-01-31 09:18:34 +0300 | [diff] [blame] | 417 | // just a defensive programming -- makes sure that list head sentinel is never removed |
Roman Elizarov | f024608 | 2017-02-10 18:02:38 +0300 | [diff] [blame] | 418 | public final override fun remove() = throw UnsupportedOperationException() |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 419 | |
Roman Elizarov | f024608 | 2017-02-10 18:02:38 +0300 | [diff] [blame] | 420 | internal fun validate() { |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 421 | var prev: Node = this |
| 422 | var cur: Node = next() |
| 423 | while (cur != this) { |
| 424 | val next = cur.next() |
| 425 | cur.validateNode(prev, next) |
| 426 | prev = cur |
| 427 | cur = next |
| 428 | } |
| 429 | validateNode(prev, next()) |
| 430 | } |
| 431 | } |