1 /* <lambda>null2 * Copyright 2016-2020 JetBrains s.r.o. Use of this source code is governed by the Apache 2.0 license. 3 */ 4 @file:Suppress("NO_EXPLICIT_VISIBILITY_IN_API_MODE") 5 6 package kotlinx.coroutines.internal 7 8 import kotlinx.atomicfu.* 9 import kotlinx.coroutines.* 10 11 private typealias Node = LockFreeLinkedListNode 12 13 @PublishedApi 14 internal const val UNDECIDED = 0 15 16 @PublishedApi 17 internal const val SUCCESS = 1 18 19 @PublishedApi 20 internal const val FAILURE = 2 21 22 @PublishedApi 23 internal val CONDITION_FALSE: Any = Symbol("CONDITION_FALSE") 24 25 @PublishedApi 26 internal val LIST_EMPTY: Any = Symbol("LIST_EMPTY") 27 28 /** @suppress **This is unstable API and it is subject to change.** */ 29 public actual typealias RemoveFirstDesc<T> = LockFreeLinkedListNode.RemoveFirstDesc<T> 30 31 /** @suppress **This is unstable API and it is subject to change.** */ 32 public actual typealias AddLastDesc<T> = LockFreeLinkedListNode.AddLastDesc<T> 33 34 /** @suppress **This is unstable API and it is subject to change.** */ 35 public actual typealias AbstractAtomicDesc = LockFreeLinkedListNode.AbstractAtomicDesc 36 37 /** @suppress **This is unstable API and it is subject to change.** */ 38 public actual typealias PrepareOp = LockFreeLinkedListNode.PrepareOp 39 40 /** 41 * Doubly-linked concurrent list node with remove support. 42 * Based on paper 43 * ["Lock-Free and Practical Doubly Linked List-Based Deques Using Single-Word Compare-and-Swap"](https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.140.4693&rep=rep1&type=pdf) 44 * by Sundell and Tsigas with considerable changes. 45 * 46 * The core idea of the algorithm is to maintain a doubly-linked list with an ever-present sentinel node (it is 47 * never removed) that serves both as a list head and tail and to linearize all operations (both insert and remove) on 48 * the update of the next pointer. Removed nodes have their next pointer marked with [Removed] class. 49 * 50 * Important notes: 51 * * There are no operations to add items to left side of the list, only to the end (right side), because we cannot 52 * efficiently linearize them with atomic multi-step head-removal operations. In short, 53 * support for [describeRemoveFirst] operation precludes ability to add items at the beginning. 54 * * Previous pointers are not marked for removal. We don't support linearizable backwards traversal. 55 * * Remove-helping logic is simplified and consolidated in [correctPrev] method. 56 * 57 * @suppress **This is unstable API and it is subject to change.** 58 */ 59 @Suppress("LeakingThis") 60 @InternalCoroutinesApi 61 public actual open class LockFreeLinkedListNode { 62 private val _next = atomic<Any>(this) // Node | Removed | OpDescriptor 63 private val _prev = atomic(this) // Node to the left (cannot be marked as removed) 64 private val _removedRef = atomic<Removed?>(null) // lazily cached removed ref to this 65 66 private fun removed(): Removed = 67 _removedRef.value ?: Removed(this).also { _removedRef.lazySet(it) } 68 69 @PublishedApi 70 internal abstract class CondAddOp( 71 @JvmField val newNode: Node 72 ) : AtomicOp<Node>() { 73 @JvmField var oldNext: Node? = null 74 75 override fun complete(affected: Node, failure: Any?) { 76 val success = failure == null 77 val update = if (success) newNode else oldNext 78 if (update != null && affected._next.compareAndSet( this, update)) { 79 // only the thread the makes this update actually finishes add operation 80 if (success) newNode.finishAdd(oldNext!!) 81 } 82 } 83 } 84 85 @PublishedApi 86 internal inline fun makeCondAddOp(node: Node, crossinline condition: () -> Boolean): CondAddOp = 87 object : CondAddOp(node) { 88 override fun prepare(affected: Node): Any? = if (condition()) null else CONDITION_FALSE 89 } 90 91 public actual open val isRemoved: Boolean get() = next is Removed 92 93 // LINEARIZABLE. Returns Node | Removed 94 public val next: Any get() { 95 _next.loop { next -> 96 if (next !is OpDescriptor) return next 97 next.perform(this) 98 } 99 } 100 101 // LINEARIZABLE. Returns next non-removed Node 102 public actual val nextNode: Node get() = next.unwrap() 103 104 // LINEARIZABLE WHEN THIS NODE IS NOT REMOVED: 105 // Returns prev non-removed Node, makes sure prev is correct (prev.next === this) 106 // NOTE: if this node is removed, then returns non-removed previous node without applying 107 // prev.next correction, which does not provide linearizable backwards iteration, but can be used to 108 // resume forward iteration when current node was removed. 109 public actual val prevNode: Node 110 get() = correctPrev(null) ?: findPrevNonRemoved(_prev.value) 111 112 private tailrec fun findPrevNonRemoved(current: Node): Node { 113 if (!current.isRemoved) return current 114 return findPrevNonRemoved(current._prev.value) 115 } 116 117 // ------ addOneIfEmpty ------ 118 119 public actual fun addOneIfEmpty(node: Node): Boolean { 120 node._prev.lazySet(this) 121 node._next.lazySet(this) 122 while (true) { 123 val next = next 124 if (next !== this) return false // this is not an empty list! 125 if (_next.compareAndSet(this, node)) { 126 // added successfully (linearized add) -- fixup the list 127 node.finishAdd(this) 128 return true 129 } 130 } 131 } 132 133 // ------ addLastXXX ------ 134 135 /** 136 * Adds last item to this list. 137 */ 138 public actual fun addLast(node: Node) { 139 while (true) { // lock-free loop on prev.next 140 if (prevNode.addNext(node, this)) return 141 } 142 } 143 144 public fun <T : Node> describeAddLast(node: T): AddLastDesc<T> = AddLastDesc(this, node) 145 146 /** 147 * Adds last item to this list atomically if the [condition] is true. 148 */ 149 public actual inline fun addLastIf(node: Node, crossinline condition: () -> Boolean): Boolean { 150 val condAdd = makeCondAddOp(node, condition) 151 while (true) { // lock-free loop on prev.next 152 val prev = prevNode // sentinel node is never removed, so prev is always defined 153 when (prev.tryCondAddNext(node, this, condAdd)) { 154 SUCCESS -> return true 155 FAILURE -> return false 156 } 157 } 158 } 159 160 public actual inline fun addLastIfPrev(node: Node, predicate: (Node) -> Boolean): Boolean { 161 while (true) { // lock-free loop on prev.next 162 val prev = prevNode // sentinel node is never removed, so prev is always defined 163 if (!predicate(prev)) return false 164 if (prev.addNext(node, this)) return true 165 } 166 } 167 168 public actual inline fun addLastIfPrevAndIf( 169 node: Node, 170 predicate: (Node) -> Boolean, // prev node predicate 171 crossinline condition: () -> Boolean // atomically checked condition 172 ): Boolean { 173 val condAdd = makeCondAddOp(node, condition) 174 while (true) { // lock-free loop on prev.next 175 val prev = prevNode // sentinel node is never removed, so prev is always defined 176 if (!predicate(prev)) return false 177 when (prev.tryCondAddNext(node, this, condAdd)) { 178 SUCCESS -> return true 179 FAILURE -> return false 180 } 181 } 182 } 183 184 // ------ addXXX util ------ 185 186 /** 187 * Given: 188 * ``` 189 * +-----------------------+ 190 * this | node V next 191 * +---+---+ +---+---+ +---+---+ 192 * ... <-- | P | N | | P | N | | P | N | --> .... 193 * +---+---+ +---+---+ +---+---+ 194 * ^ | 195 * +-----------------------+ 196 * ``` 197 * Produces: 198 * ``` 199 * this node next 200 * +---+---+ +---+---+ +---+---+ 201 * ... <-- | P | N | ==> | P | N | --> | P | N | --> .... 202 * +---+---+ +---+---+ +---+---+ 203 * ^ | ^ | 204 * +---------+ +---------+ 205 * ``` 206 * Where `==>` denotes linearization point. 207 * Returns `false` if `next` was not following `this` node. 208 */ 209 @PublishedApi 210 internal fun addNext(node: Node, next: Node): Boolean { 211 node._prev.lazySet(this) 212 node._next.lazySet(next) 213 if (!_next.compareAndSet(next, node)) return false 214 // added successfully (linearized add) -- fixup the list 215 node.finishAdd(next) 216 return true 217 } 218 219 // returns UNDECIDED, SUCCESS or FAILURE 220 @PublishedApi 221 internal fun tryCondAddNext(node: Node, next: Node, condAdd: CondAddOp): Int { 222 node._prev.lazySet(this) 223 node._next.lazySet(next) 224 condAdd.oldNext = next 225 if (!_next.compareAndSet(next, condAdd)) return UNDECIDED 226 // added operation successfully (linearized) -- complete it & fixup the list 227 return if (condAdd.perform(this) == null) SUCCESS else FAILURE 228 } 229 230 // ------ removeXXX ------ 231 232 /** 233 * Removes this node from the list. Returns `true` when removed successfully, or `false` if the node was already 234 * removed or if it was not added to any list in the first place. 235 * 236 * **Note**: Invocation of this operation does not guarantee that remove was actually complete if result was `false`. 237 * In particular, invoking [nextNode].[prevNode] might still return this node even though it is "already removed". 238 * Invoke [helpRemove] to make sure that remove was completed. 239 */ 240 public actual open fun remove(): Boolean = 241 removeOrNext() == null 242 243 // returns null if removed successfully or next node if this node is already removed 244 @PublishedApi 245 internal fun removeOrNext(): Node? { 246 while (true) { // lock-free loop on next 247 val next = this.next 248 if (next is Removed) return next.ref // was already removed -- don't try to help (original thread will take care) 249 if (next === this) return next // was not even added 250 val removed = (next as Node).removed() 251 if (_next.compareAndSet(next, removed)) { 252 // was removed successfully (linearized remove) -- fixup the list 253 next.correctPrev(null) 254 return null 255 } 256 } 257 } 258 259 // Helps with removal of this node 260 public actual fun helpRemove() { 261 // Note: this node must be already removed 262 (next as Removed).ref.correctPrev(null) 263 } 264 265 // Helps with removal of nodes that are previous to this 266 @PublishedApi 267 internal fun helpRemovePrev() { 268 // We need to call correctPrev on a non-removed node to ensure progress, since correctPrev bails out when 269 // called on a removed node. There's always at least one non-removed node (list head). 270 var node = this 271 while (true) { 272 val next = node.next 273 if (next !is Removed) break 274 node = next.ref 275 } 276 // Found a non-removed node 277 node.correctPrev(null) 278 } 279 280 public actual fun removeFirstOrNull(): Node? { 281 while (true) { // try to linearize 282 val first = next as Node 283 if (first === this) return null 284 if (first.remove()) return first 285 first.helpRemove() // must help remove to ensure lock-freedom 286 } 287 } 288 289 public fun describeRemoveFirst(): RemoveFirstDesc<Node> = RemoveFirstDesc(this) 290 291 // just peek at item when predicate is true 292 public actual inline fun <reified T> removeFirstIfIsInstanceOfOrPeekIf(predicate: (T) -> Boolean): T? { 293 while (true) { 294 val first = this.next as Node 295 if (first === this) return null // got list head -- nothing to remove 296 if (first !is T) return null 297 if (predicate(first)) { 298 // check for removal of the current node to make sure "peek" operation is linearizable 299 if (!first.isRemoved) return first 300 } 301 val next = first.removeOrNext() 302 if (next === null) return first // removed successfully -- return it 303 // help and start from the beginning 304 next.helpRemovePrev() 305 } 306 } 307 308 // ------ multi-word atomic operations helpers ------ 309 310 public open class AddLastDesc<T : Node> constructor( 311 @JvmField val queue: Node, 312 @JvmField val node: T 313 ) : AbstractAtomicDesc() { 314 init { 315 // require freshly allocated node here 316 assert { node._next.value === node && node._prev.value === node } 317 } 318 319 // Returns null when atomic op got into deadlock trying to help operation that started later (RETRY_ATOMIC) 320 final override fun takeAffectedNode(op: OpDescriptor): Node? = 321 queue.correctPrev(op) // queue head is never removed, so null result can only mean RETRY_ATOMIC 322 323 private val _affectedNode = atomic<Node?>(null) 324 final override val affectedNode: Node? get() = _affectedNode.value 325 final override val originalNext: Node? get() = queue 326 327 override fun retry(affected: Node, next: Any): Boolean = next !== queue 328 329 override fun finishPrepare(prepareOp: PrepareOp) { 330 // Note: onPrepare must use CAS to make sure the stale invocation is not 331 // going to overwrite the previous decision on successful preparation. 332 // Result of CAS is irrelevant, but we must ensure that it is set when invoker completes 333 _affectedNode.compareAndSet(null, prepareOp.affected) 334 } 335 336 override fun updatedNext(affected: Node, next: Node): Any { 337 // it is invoked only on successfully completion of operation, but this invocation can be stale, 338 // so we must use CAS to set both prev & next pointers 339 node._prev.compareAndSet(node, affected) 340 node._next.compareAndSet(node, queue) 341 return node 342 } 343 344 override fun finishOnSuccess(affected: Node, next: Node) { 345 node.finishAdd(queue) 346 } 347 } 348 349 public open class RemoveFirstDesc<T>( 350 @JvmField val queue: Node 351 ) : AbstractAtomicDesc() { 352 private val _affectedNode = atomic<Node?>(null) 353 private val _originalNext = atomic<Node?>(null) 354 355 @Suppress("UNCHECKED_CAST") 356 public val result: T get() = affectedNode!! as T 357 358 final override fun takeAffectedNode(op: OpDescriptor): Node? { 359 queue._next.loop { next -> 360 if (next is OpDescriptor) { 361 if (op.isEarlierThan(next)) 362 return null // RETRY_ATOMIC 363 next.perform(queue) 364 } else { 365 return next as Node 366 } 367 } 368 } 369 370 final override val affectedNode: Node? get() = _affectedNode.value 371 final override val originalNext: Node? get() = _originalNext.value 372 373 // check node predicates here, must signal failure if affect is not of type T 374 protected override fun failure(affected: Node): Any? = 375 if (affected === queue) LIST_EMPTY else null 376 377 final override fun retry(affected: Node, next: Any): Boolean { 378 if (next !is Removed) return false 379 next.ref.helpRemovePrev() // must help delete to ensure lock-freedom 380 return true 381 } 382 383 override fun finishPrepare(prepareOp: PrepareOp) { 384 // Note: finishPrepare must use CAS to make sure the stale invocation is not 385 // going to overwrite the previous decision on successful preparation. 386 // Result of CAS is irrelevant, but we must ensure that it is set when invoker completes 387 _affectedNode.compareAndSet(null, prepareOp.affected) 388 _originalNext.compareAndSet(null, prepareOp.next) 389 } 390 391 final override fun updatedNext(affected: Node, next: Node): Any = next.removed() 392 393 final override fun finishOnSuccess(affected: Node, next: Node) { 394 // Complete removal operation here. It bails out if next node is also removed. It becomes 395 // responsibility of the next's removes to call correctPrev which would help fix all the links. 396 next.correctPrev(null) 397 } 398 } 399 400 // This is Harris's RDCSS (Restricted Double-Compare Single Swap) operation 401 // It inserts "op" descriptor of when "op" status is still undecided (rolls back otherwise) 402 public class PrepareOp( 403 @JvmField val affected: Node, 404 @JvmField val next: Node, 405 @JvmField val desc: AbstractAtomicDesc 406 ) : OpDescriptor() { 407 override val atomicOp: AtomicOp<*> get() = desc.atomicOp 408 409 // Returns REMOVE_PREPARED or null (it makes decision on any failure) 410 override fun perform(affected: Any?): Any? { 411 assert { affected === this.affected } 412 affected as Node // type assertion 413 val decision = desc.onPrepare(this) 414 if (decision === REMOVE_PREPARED) { 415 // remove element on failure -- do not mark as decided, will try another one 416 val next = this.next 417 val removed = next.removed() 418 if (affected._next.compareAndSet(this, removed)) { 419 // The element was actually removed 420 desc.onRemoved(affected) 421 // Complete removal operation here. It bails out if next node is also removed and it becomes 422 // responsibility of the next's removes to call correctPrev which would help fix all the links. 423 next.correctPrev(null) 424 } 425 return REMOVE_PREPARED 426 } 427 // We need to ensure progress even if it operation result consensus was already decided 428 val consensus = if (decision != null) { 429 // some other logic failure, including RETRY_ATOMIC -- reach consensus on decision fail reason ASAP 430 atomicOp.decide(decision) 431 } else { 432 atomicOp.consensus // consult with current decision status like in Harris DCSS 433 } 434 val update: Any = when { 435 consensus === NO_DECISION -> atomicOp // desc.onPrepare returned null -> start doing atomic op 436 consensus == null -> desc.updatedNext(affected, next) // move forward if consensus on success 437 else -> next // roll back if consensus if failure 438 } 439 affected._next.compareAndSet(this, update) 440 return null 441 } 442 443 public fun finishPrepare(): Unit = desc.finishPrepare(this) 444 445 override fun toString(): String = "PrepareOp(op=$atomicOp)" 446 } 447 448 public abstract class AbstractAtomicDesc : AtomicDesc() { 449 protected abstract val affectedNode: Node? 450 protected abstract val originalNext: Node? 451 protected open fun takeAffectedNode(op: OpDescriptor): Node? = affectedNode!! // null for RETRY_ATOMIC 452 protected open fun failure(affected: Node): Any? = null // next: Node | Removed 453 protected open fun retry(affected: Node, next: Any): Boolean = false // next: Node | Removed 454 protected abstract fun finishOnSuccess(affected: Node, next: Node) 455 456 public abstract fun updatedNext(affected: Node, next: Node): Any 457 458 public abstract fun finishPrepare(prepareOp: PrepareOp) 459 460 // non-null on failure 461 public open fun onPrepare(prepareOp: PrepareOp): Any? { 462 finishPrepare(prepareOp) 463 return null 464 } 465 466 public open fun onRemoved(affected: Node) {} // called once when node was prepared & later removed 467 468 @Suppress("UNCHECKED_CAST") 469 final override fun prepare(op: AtomicOp<*>): Any? { 470 while (true) { // lock free loop on next 471 val affected = takeAffectedNode(op) ?: return RETRY_ATOMIC 472 // read its original next pointer first 473 val next = affected._next.value 474 // then see if already reached consensus on overall operation 475 if (next === op) return null // already in process of operation -- all is good 476 if (op.isDecided) return null // already decided this operation -- go to next desc 477 if (next is OpDescriptor) { 478 // some other operation is in process 479 // if operation in progress (preparing or prepared) has higher sequence number -- abort our preparations 480 if (op.isEarlierThan(next)) 481 return RETRY_ATOMIC 482 next.perform(affected) 483 continue // and retry 484 } 485 // next: Node | Removed 486 val failure = failure(affected) 487 if (failure != null) return failure // signal failure 488 if (retry(affected, next)) continue // retry operation 489 val prepareOp = PrepareOp(affected, next as Node, this) 490 if (affected._next.compareAndSet(next, prepareOp)) { 491 // prepared -- complete preparations 492 try { 493 val prepFail = prepareOp.perform(affected) 494 if (prepFail === REMOVE_PREPARED) continue // retry 495 assert { prepFail == null } 496 return null 497 } catch (e: Throwable) { 498 // Crashed during preparation (for example IllegalStateExpception) -- undo & rethrow 499 affected._next.compareAndSet(prepareOp, next) 500 throw e 501 } 502 } 503 } 504 } 505 506 final override fun complete(op: AtomicOp<*>, failure: Any?) { 507 val success = failure == null 508 val affectedNode = affectedNode ?: run { assert { !success }; return } 509 val originalNext = originalNext ?: run { assert { !success }; return } 510 val update = if (success) updatedNext(affectedNode, originalNext) else originalNext 511 if (affectedNode._next.compareAndSet(op, update)) { 512 if (success) finishOnSuccess(affectedNode, originalNext) 513 } 514 } 515 } 516 517 // ------ other helpers ------ 518 519 /** 520 * Given: 521 * ``` 522 * 523 * prev this next 524 * +---+---+ +---+---+ +---+---+ 525 * ... <-- | P | N | --> | P | N | --> | P | N | --> .... 526 * +---+---+ +---+---+ +---+---+ 527 * ^ ^ | | 528 * | +---------+ | 529 * +-------------------------+ 530 * ``` 531 * Produces: 532 * ``` 533 * prev this next 534 * +---+---+ +---+---+ +---+---+ 535 * ... <-- | P | N | --> | P | N | --> | P | N | --> .... 536 * +---+---+ +---+---+ +---+---+ 537 * ^ | ^ | 538 * +---------+ +---------+ 539 * ``` 540 */ 541 private fun finishAdd(next: Node) { 542 next._prev.loop { nextPrev -> 543 if (this.next !== next) return // this or next was removed or another node added, remover/adder fixes up links 544 if (next._prev.compareAndSet(nextPrev, this)) { 545 // This newly added node could have been removed, and the above CAS would have added it physically again. 546 // Let us double-check for this situation and correct if needed 547 if (isRemoved) next.correctPrev(null) 548 return 549 } 550 } 551 } 552 553 protected open fun nextIfRemoved(): Node? = (next as? Removed)?.ref 554 555 /** 556 * Returns the corrected value of the previous node while also correcting the `prev` pointer 557 * (so that `this.prev.next === this`) and helps complete node removals to the left ot this node. 558 * 559 * It returns `null` in two special cases: 560 * 561 * * When this node is removed. In this case there is no need to waste time on corrections, because 562 * remover of this node will ultimately call [correctPrev] on the next node and that will fix all 563 * the links from this node, too. 564 * * When [op] descriptor is not `null` and operation descriptor that is [OpDescriptor.isEarlierThan] 565 * that current [op] is found while traversing the list. This `null` result will be translated 566 * by callers to [RETRY_ATOMIC]. 567 */ 568 private tailrec fun correctPrev(op: OpDescriptor?): Node? { 569 val oldPrev = _prev.value 570 var prev: Node = oldPrev 571 var last: Node? = null // will be set so that last.next === prev 572 while (true) { // move the left until first non-removed node 573 val prevNext: Any = prev._next.value 574 when { 575 // fast path to find quickly find prev node when everything is properly linked 576 prevNext === this -> { 577 if (oldPrev === prev) return prev // nothing to update -- all is fine, prev found 578 // otherwise need to update prev 579 if (!this._prev.compareAndSet(oldPrev, prev)) { 580 // Note: retry from scratch on failure to update prev 581 return correctPrev(op) 582 } 583 return prev // return the correct prev 584 } 585 // slow path when we need to help remove operations 586 this.isRemoved -> return null // nothing to do, this node was removed, bail out asap to save time 587 prevNext === op -> return prev // part of the same op -- don't recurse, didn't correct prev 588 prevNext is OpDescriptor -> { // help & retry 589 if (op != null && op.isEarlierThan(prevNext)) 590 return null // RETRY_ATOMIC 591 prevNext.perform(prev) 592 return correctPrev(op) // retry from scratch 593 } 594 prevNext is Removed -> { 595 if (last !== null) { 596 // newly added (prev) node is already removed, correct last.next around it 597 if (!last._next.compareAndSet(prev, prevNext.ref)) { 598 return correctPrev(op) // retry from scratch on failure to update next 599 } 600 prev = last 601 last = null 602 } else { 603 prev = prev._prev.value 604 } 605 } 606 else -> { // prevNext is a regular node, but not this -- help delete 607 last = prev 608 prev = prevNext as Node 609 } 610 } 611 } 612 } 613 614 internal fun validateNode(prev: Node, next: Node) { 615 assert { prev === this._prev.value } 616 assert { next === this._next.value } 617 } 618 619 override fun toString(): String = "${this::class.java.simpleName}@${Integer.toHexString(System.identityHashCode(this))}" 620 } 621 622 private class Removed(@JvmField val ref: Node) { toStringnull623 override fun toString(): String = "Removed[$ref]" 624 } 625 626 @PublishedApi 627 internal fun Any.unwrap(): Node = (this as? Removed)?.ref ?: this as Node 628 629 /** 630 * Head (sentinel) item of the linked list that is never removed. 631 * 632 * @suppress **This is unstable API and it is subject to change.** 633 */ 634 public actual open class LockFreeLinkedListHead : LockFreeLinkedListNode() { 635 public actual val isEmpty: Boolean get() = next === this 636 637 /** 638 * Iterates over all elements in this list of a specified type. 639 */ 640 public actual inline fun <reified T : Node> forEach(block: (T) -> Unit) { 641 var cur: Node = next as Node 642 while (cur != this) { 643 if (cur is T) block(cur) 644 cur = cur.nextNode 645 } 646 } 647 648 // just a defensive programming -- makes sure that list head sentinel is never removed 649 public actual final override fun remove(): Boolean = error("head cannot be removed") 650 651 // optimization: because head is never removed, we don't have to read _next.value to check these: 652 override val isRemoved: Boolean get() = false 653 override fun nextIfRemoved(): Node? = null 654 655 internal fun validate() { 656 var prev: Node = this 657 var cur: Node = next as Node 658 while (cur != this) { 659 val next = cur.nextNode 660 cur.validateNode(prev, next) 661 prev = cur 662 cur = next 663 } 664 validateNode(prev, next as Node) 665 } 666 } 667