16 * You should have received a copy of the GNU General Public License version 17 * 2 along with this work; if not, write to the Free Software Foundation, 18 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 19 * 20 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 21 * or visit www.oracle.com if you need additional information or have any 22 * questions. 23 */ 24 25 /* 26 * This file is available under and governed by the GNU General Public 27 * License version 2 only, as published by the Free Software Foundation. 28 * However, the following notice accompanied the original version of this 29 * file: 30 * 31 * Written by Doug Lea and Martin Buchholz with assistance from members of 32 * JCP JSR-166 Expert Group and released to the public domain, as explained 33 * at http://creativecommons.org/publicdomain/zero/1.0/ 34 */ 35 36 package java.util.concurrent; 37 38 import java.util.AbstractCollection; 39 import java.util.ArrayList; 40 import java.util.Collection; 41 import java.util.Deque; 42 import java.util.Iterator; 43 import java.util.NoSuchElementException; 44 import java.util.Queue; 45 import java.util.Spliterator; 46 import java.util.Spliterators; 47 import java.util.function.Consumer; 48 49 /** 50 * An unbounded concurrent {@linkplain Deque deque} based on linked nodes. 51 * Concurrent insertion, removal, and access operations execute safely 52 * across multiple threads. 53 * A {@code ConcurrentLinkedDeque} is an appropriate choice when 54 * many threads will share access to a common collection. 55 * Like most other concurrent collection implementations, this class 56 * does not permit the use of {@code null} elements. 57 * 58 * <p>Iterators and spliterators are 59 * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>. 60 * 61 * <p>Beware that, unlike in most collections, the {@code size} method 62 * is <em>NOT</em> a constant-time operation. Because of the 63 * asynchronous nature of these deques, determining the current number 64 * of elements requires a traversal of the elements, and so may report 65 * inaccurate results if this collection is modified during traversal. 66 * Additionally, the bulk operations {@code addAll}, 67 * {@code removeAll}, {@code retainAll}, {@code containsAll}, 68 * {@code equals}, and {@code toArray} are <em>not</em> guaranteed 69 * to be performed atomically. For example, an iterator operating 70 * concurrently with an {@code addAll} operation might view only some 71 * of the added elements. 72 * 73 * <p>This class and its iterator implement all of the <em>optional</em> 74 * methods of the {@link Deque} and {@link Iterator} interfaces. 75 * 76 * <p>Memory consistency effects: As with other concurrent collections, 77 * actions in a thread prior to placing an object into a 78 * {@code ConcurrentLinkedDeque} 79 * <a href="package-summary.html#MemoryVisibility"><i>happen-before</i></a> 80 * actions subsequent to the access or removal of that element from 81 * the {@code ConcurrentLinkedDeque} in another thread. 82 * 83 * <p>This class is a member of the 84 * <a href="{@docRoot}/../technotes/guides/collections/index.html"> 85 * Java Collections Framework</a>. 86 * 87 * @since 1.7 88 * @author Doug Lea 89 * @author Martin Buchholz 90 * @param <E> the type of elements held in this collection 91 */ 92 public class ConcurrentLinkedDeque<E> 93 extends AbstractCollection<E> 94 implements Deque<E>, java.io.Serializable { 95 96 /* 97 * This is an implementation of a concurrent lock-free deque 98 * supporting interior removes but not interior insertions, as 99 * required to support the entire Deque interface. 100 * 101 * We extend the techniques developed for ConcurrentLinkedQueue and 102 * LinkedTransferQueue (see the internal docs for those classes). 103 * Understanding the ConcurrentLinkedQueue implementation is a 104 * prerequisite for understanding the implementation of this class. 105 * 106 * The data structure is a symmetrical doubly-linked "GC-robust" 107 * linked list of nodes. We minimize the number of volatile writes 108 * using two techniques: advancing multiple hops with a single CAS 109 * and mixing volatile and non-volatile writes of the same memory 110 * locations. 111 * 112 * A node contains the expected E ("item") and links to predecessor 113 * ("prev") and successor ("next") nodes: 114 * 115 * class Node<E> { volatile Node<E> prev, next; volatile E item; } 116 * 117 * A node p is considered "live" if it contains a non-null item 118 * (p.item != null). When an item is CASed to null, the item is 119 * atomically logically deleted from the collection. 120 * 121 * At any time, there is precisely one "first" node with a null 122 * prev reference that terminates any chain of prev references 123 * starting at a live node. Similarly there is precisely one 124 * "last" node terminating any chain of next references starting at 125 * a live node. The "first" and "last" nodes may or may not be live. 126 * The "first" and "last" nodes are always mutually reachable. 127 * 128 * A new element is added atomically by CASing the null prev or 129 * next reference in the first or last node to a fresh node 130 * containing the element. The element's node atomically becomes 131 * "live" at that point. 132 * 133 * A node is considered "active" if it is a live node, or the 134 * first or last node. Active nodes cannot be unlinked. 135 * 136 * A "self-link" is a next or prev reference that is the same node: 137 * p.prev == p or p.next == p 138 * Self-links are used in the node unlinking process. Active nodes 139 * never have self-links. 140 * 141 * A node p is active if and only if: 142 * 143 * p.item != null || 144 * (p.prev == null && p.next != p) || 145 * (p.next == null && p.prev != p) 146 * 147 * The deque object has two node references, "head" and "tail". 148 * The head and tail are only approximations to the first and last 149 * nodes of the deque. The first node can always be found by 150 * following prev pointers from head; likewise for tail. However, 151 * it is permissible for head and tail to be referring to deleted 152 * nodes that have been unlinked and so may not be reachable from 153 * any live node. 154 * 155 * There are 3 stages of node deletion; 156 * "logical deletion", "unlinking", and "gc-unlinking". 157 * 158 * 1. "logical deletion" by CASing item to null atomically removes 159 * the element from the collection, and makes the containing node 160 * eligible for unlinking. 161 * 162 * 2. "unlinking" makes a deleted node unreachable from active 163 * nodes, and thus eventually reclaimable by GC. Unlinked nodes 164 * may remain reachable indefinitely from an iterator. 165 * 166 * Physical node unlinking is merely an optimization (albeit a 167 * critical one), and so can be performed at our convenience. At 168 * any time, the set of live nodes maintained by prev and next 169 * links are identical, that is, the live nodes found via next 170 * links from the first node is equal to the elements found via 171 * prev links from the last node. However, this is not true for 172 * nodes that have already been logically deleted - such nodes may 173 * be reachable in one direction only. 174 * 175 * 3. "gc-unlinking" takes unlinking further by making active 176 * nodes unreachable from deleted nodes, making it easier for the 177 * GC to reclaim future deleted nodes. This step makes the data 178 * structure "gc-robust", as first described in detail by Boehm 179 * (http://portal.acm.org/citation.cfm?doid=503272.503282). 180 * 181 * GC-unlinked nodes may remain reachable indefinitely from an 182 * iterator, but unlike unlinked nodes, are never reachable from 183 * head or tail. 184 * 185 * Making the data structure GC-robust will eliminate the risk of 186 * unbounded memory retention with conservative GCs and is likely 187 * to improve performance with generational GCs. 188 * 189 * When a node is dequeued at either end, e.g. via poll(), we would 190 * like to break any references from the node to active nodes. We 191 * develop further the use of self-links that was very effective in 192 * other concurrent collection classes. The idea is to replace 193 * prev and next pointers with special values that are interpreted 194 * to mean off-the-list-at-one-end. These are approximations, but 195 * good enough to preserve the properties we want in our 196 * traversals, e.g. we guarantee that a traversal will never visit 197 * the same element twice, but we don't guarantee whether a 198 * traversal that runs out of elements will be able to see more 199 * elements later after enqueues at that end. Doing gc-unlinking 200 * safely is particularly tricky, since any node can be in use 201 * indefinitely (for example by an iterator). We must ensure that 202 * the nodes pointed at by head/tail never get gc-unlinked, since 203 * head/tail are needed to get "back on track" by other nodes that 204 * are gc-unlinked. gc-unlinking accounts for much of the 205 * implementation complexity. 206 * 207 * Since neither unlinking nor gc-unlinking are necessary for 208 * correctness, there are many implementation choices regarding 209 * frequency (eagerness) of these operations. Since volatile 210 * reads are likely to be much cheaper than CASes, saving CASes by 211 * unlinking multiple adjacent nodes at a time may be a win. 212 * gc-unlinking can be performed rarely and still be effective, 213 * since it is most important that long chains of deleted nodes 214 * are occasionally broken. 215 * 216 * The actual representation we use is that p.next == p means to 217 * goto the first node (which in turn is reached by following prev 218 * pointers from head), and p.next == null && p.prev == p means 219 * that the iteration is at an end and that p is a (static final) 220 * dummy node, NEXT_TERMINATOR, and not the last active node. 221 * Finishing the iteration when encountering such a TERMINATOR is 222 * good enough for read-only traversals, so such traversals can use 223 * p.next == null as the termination condition. When we need to 224 * find the last (active) node, for enqueueing a new node, we need 225 * to check whether we have reached a TERMINATOR node; if so, 226 * restart traversal from tail. 227 * 228 * The implementation is completely directionally symmetrical, 229 * except that most public methods that iterate through the list 230 * follow next pointers ("forward" direction). 231 * 232 * We believe (without full proof) that all single-element deque 233 * operations (e.g., addFirst, peekLast, pollLast) are linearizable 234 * (see Herlihy and Shavit's book). However, some combinations of 235 * operations are known not to be linearizable. In particular, 236 * when an addFirst(A) is racing with pollFirst() removing B, it is 237 * possible for an observer iterating over the elements to observe 238 * A B C and subsequently observe A C, even though no interior 239 * removes are ever performed. Nevertheless, iterators behave 240 * reasonably, providing the "weakly consistent" guarantees. 241 * 242 * Empirically, microbenchmarks suggest that this class adds about 243 * 40% overhead relative to ConcurrentLinkedQueue, which feels as 244 * good as we can hope for. 245 */ 246 247 private static final long serialVersionUID = 876323262645176354L; 248 249 /** 250 * A node from which the first node on list (that is, the unique node p 251 * with p.prev == null && p.next != p) can be reached in O(1) time. 252 * Invariants: 253 * - the first node is always O(1) reachable from head via prev links 254 * - all live nodes are reachable from the first node via succ() 255 * - head != null 256 * - (tmp = head).next != tmp || tmp != head 257 * - head is never gc-unlinked (but may be unlinked) 258 * Non-invariants: 259 * - head.item may or may not be null 260 * - head may not be reachable from the first or last node, or from tail 261 */ 262 private transient volatile Node<E> head; 263 264 /** 265 * A node from which the last node on list (that is, the unique node p 266 * with p.next == null && p.prev != p) can be reached in O(1) time. 267 * Invariants: 268 * - the last node is always O(1) reachable from tail via next links 269 * - all live nodes are reachable from the last node via pred() 270 * - tail != null 271 * - tail is never gc-unlinked (but may be unlinked) 272 * Non-invariants: 273 * - tail.item may or may not be null 274 * - tail may not be reachable from the first or last node, or from head 275 */ 276 private transient volatile Node<E> tail; 277 278 private static final Node<Object> PREV_TERMINATOR, NEXT_TERMINATOR; 279 280 @SuppressWarnings("unchecked") 281 Node<E> prevTerminator() { 282 return (Node<E>) PREV_TERMINATOR; 283 } 284 285 @SuppressWarnings("unchecked") 286 Node<E> nextTerminator() { 287 return (Node<E>) NEXT_TERMINATOR; 288 } 289 290 static final class Node<E> { 291 volatile Node<E> prev; 292 volatile E item; 293 volatile Node<E> next; 294 295 Node() { // default constructor for NEXT_TERMINATOR, PREV_TERMINATOR 296 } 297 298 /** 299 * Constructs a new node. Uses relaxed write because item can 300 * only be seen after publication via casNext or casPrev. 301 */ 302 Node(E item) { 303 UNSAFE.putObject(this, itemOffset, item); 304 } 305 306 boolean casItem(E cmp, E val) { 307 return UNSAFE.compareAndSwapObject(this, itemOffset, cmp, val); 308 } 309 310 void lazySetNext(Node<E> val) { 311 UNSAFE.putOrderedObject(this, nextOffset, val); 312 } 313 314 boolean casNext(Node<E> cmp, Node<E> val) { 315 return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val); 316 } 317 318 void lazySetPrev(Node<E> val) { 319 UNSAFE.putOrderedObject(this, prevOffset, val); 320 } 321 322 boolean casPrev(Node<E> cmp, Node<E> val) { 323 return UNSAFE.compareAndSwapObject(this, prevOffset, cmp, val); 324 } 325 326 // Unsafe mechanics 327 328 private static final sun.misc.Unsafe UNSAFE; 329 private static final long prevOffset; 330 private static final long itemOffset; 331 private static final long nextOffset; 332 333 static { 334 try { 335 UNSAFE = sun.misc.Unsafe.getUnsafe(); 336 Class<?> k = Node.class; 337 prevOffset = UNSAFE.objectFieldOffset 338 (k.getDeclaredField("prev")); 339 itemOffset = UNSAFE.objectFieldOffset 340 (k.getDeclaredField("item")); 341 nextOffset = UNSAFE.objectFieldOffset 342 (k.getDeclaredField("next")); 343 } catch (Exception e) { 344 throw new Error(e); 345 } 346 } 347 } 348 349 /** 350 * Links e as first element. 351 */ 352 private void linkFirst(E e) { 353 checkNotNull(e); 354 final Node<E> newNode = new Node<E>(e); 355 356 restartFromHead: 357 for (;;) 358 for (Node<E> h = head, p = h, q;;) { 359 if ((q = p.prev) != null && 360 (q = (p = q).prev) != null) 361 // Check for head updates every other hop. 362 // If p == q, we are sure to follow head instead. 363 p = (h != (h = head)) ? h : q; 364 else if (p.next == p) // PREV_TERMINATOR 365 continue restartFromHead; 366 else { 367 // p is first node 368 newNode.lazySetNext(p); // CAS piggyback 369 if (p.casPrev(null, newNode)) { 370 // Successful CAS is the linearization point 371 // for e to become an element of this deque, 372 // and for newNode to become "live". 373 if (p != h) // hop two nodes at a time 374 casHead(h, newNode); // Failure is OK. 375 return; 376 } 377 // Lost CAS race to another thread; re-read prev 378 } 379 } 380 } 381 382 /** 383 * Links e as last element. 384 */ 385 private void linkLast(E e) { 386 checkNotNull(e); 387 final Node<E> newNode = new Node<E>(e); 388 389 restartFromTail: 390 for (;;) 391 for (Node<E> t = tail, p = t, q;;) { 392 if ((q = p.next) != null && 393 (q = (p = q).next) != null) 394 // Check for tail updates every other hop. 395 // If p == q, we are sure to follow tail instead. 396 p = (t != (t = tail)) ? t : q; 397 else if (p.prev == p) // NEXT_TERMINATOR 398 continue restartFromTail; 399 else { 400 // p is last node 401 newNode.lazySetPrev(p); // CAS piggyback 402 if (p.casNext(null, newNode)) { 403 // Successful CAS is the linearization point 404 // for e to become an element of this deque, 405 // and for newNode to become "live". 406 if (p != t) // hop two nodes at a time 407 casTail(t, newNode); // Failure is OK. 408 return; 409 } 410 // Lost CAS race to another thread; re-read next 411 } 412 } 413 } 414 415 private static final int HOPS = 2; 416 417 /** 418 * Unlinks non-null node x. 419 */ 420 void unlink(Node<E> x) { 421 // assert x != null; 422 // assert x.item == null; 423 // assert x != PREV_TERMINATOR; 424 // assert x != NEXT_TERMINATOR; 425 426 final Node<E> prev = x.prev; 427 final Node<E> next = x.next; 428 if (prev == null) { 429 unlinkFirst(x, next); 430 } else if (next == null) { 431 unlinkLast(x, prev); 432 } else { 433 // Unlink interior node. 434 // 435 // This is the common case, since a series of polls at the 436 // same end will be "interior" removes, except perhaps for 437 // the first one, since end nodes cannot be unlinked. 438 // 439 // At any time, all active nodes are mutually reachable by 440 // following a sequence of either next or prev pointers. 441 // 442 // Our strategy is to find the unique active predecessor 443 // and successor of x. Try to fix up their links so that 444 // they point to each other, leaving x unreachable from 445 // active nodes. If successful, and if x has no live 446 // predecessor/successor, we additionally try to gc-unlink, 447 // leaving active nodes unreachable from x, by rechecking 448 // that the status of predecessor and successor are 449 // unchanged and ensuring that x is not reachable from 450 // tail/head, before setting x's prev/next links to their 451 // logical approximate replacements, self/TERMINATOR. 452 Node<E> activePred, activeSucc; 453 boolean isFirst, isLast; 454 int hops = 1; 455 456 // Find active predecessor 457 for (Node<E> p = prev; ; ++hops) { 458 if (p.item != null) { 459 activePred = p; 460 isFirst = false; 461 break; 462 } 463 Node<E> q = p.prev; 464 if (q == null) { 465 if (p.next == p) 466 return; 467 activePred = p; 468 isFirst = true; 469 break; 470 } 471 else if (p == q) 472 return; 473 else 474 p = q; 475 } 476 477 // Find active successor 478 for (Node<E> p = next; ; ++hops) { 479 if (p.item != null) { 480 activeSucc = p; 481 isLast = false; 482 break; 483 } 484 Node<E> q = p.next; 485 if (q == null) { 486 if (p.prev == p) 487 return; 488 activeSucc = p; 489 isLast = true; 490 break; 491 } 492 else if (p == q) 493 return; 494 else 495 p = q; 496 } 497 498 // TODO: better HOP heuristics 499 if (hops < HOPS 500 // always squeeze out interior deleted nodes 501 && (isFirst | isLast)) 502 return; 503 504 // Squeeze out deleted nodes between activePred and 505 // activeSucc, including x. 506 skipDeletedSuccessors(activePred); 507 skipDeletedPredecessors(activeSucc); 508 509 // Try to gc-unlink, if possible 510 if ((isFirst | isLast) && 511 512 // Recheck expected state of predecessor and successor 513 (activePred.next == activeSucc) && 514 (activeSucc.prev == activePred) && 515 (isFirst ? activePred.prev == null : activePred.item != null) && 516 (isLast ? activeSucc.next == null : activeSucc.item != null)) { 517 518 updateHead(); // Ensure x is not reachable from head 519 updateTail(); // Ensure x is not reachable from tail 520 521 // Finally, actually gc-unlink 522 x.lazySetPrev(isFirst ? prevTerminator() : x); 523 x.lazySetNext(isLast ? nextTerminator() : x); 524 } 525 } 526 } 527 528 /** 529 * Unlinks non-null first node. 530 */ 531 private void unlinkFirst(Node<E> first, Node<E> next) { 532 // assert first != null; 533 // assert next != null; 534 // assert first.item == null; 535 for (Node<E> o = null, p = next, q;;) { 536 if (p.item != null || (q = p.next) == null) { 537 if (o != null && p.prev != p && first.casNext(next, p)) { 538 skipDeletedPredecessors(p); 539 if (first.prev == null && 540 (p.next == null || p.item != null) && 541 p.prev == first) { 542 543 updateHead(); // Ensure o is not reachable from head 544 updateTail(); // Ensure o is not reachable from tail 545 546 // Finally, actually gc-unlink 547 o.lazySetNext(o); 548 o.lazySetPrev(prevTerminator()); 549 } 550 } 551 return; 552 } 553 else if (p == q) 554 return; 555 else { 556 o = p; 557 p = q; 558 } 559 } 560 } 561 562 /** 563 * Unlinks non-null last node. 564 */ 565 private void unlinkLast(Node<E> last, Node<E> prev) { 566 // assert last != null; 567 // assert prev != null; 568 // assert last.item == null; 569 for (Node<E> o = null, p = prev, q;;) { 570 if (p.item != null || (q = p.prev) == null) { 571 if (o != null && p.next != p && last.casPrev(prev, p)) { 572 skipDeletedSuccessors(p); 573 if (last.next == null && 574 (p.prev == null || p.item != null) && 575 p.next == last) { 576 577 updateHead(); // Ensure o is not reachable from head 578 updateTail(); // Ensure o is not reachable from tail 579 580 // Finally, actually gc-unlink 581 o.lazySetPrev(o); 582 o.lazySetNext(nextTerminator()); 583 } 584 } 585 return; 586 } 587 else if (p == q) 588 return; 589 else { 590 o = p; 591 p = q; 592 } 593 } 594 } 595 596 /** 597 * Guarantees that any node which was unlinked before a call to 598 * this method will be unreachable from head after it returns. 599 * Does not guarantee to eliminate slack, only that head will 600 * point to a node that was active while this method was running. 601 */ 602 private final void updateHead() { 603 // Either head already points to an active node, or we keep 604 // trying to cas it to the first node until it does. 605 Node<E> h, p, q; 606 restartFromHead: 607 while ((h = head).item == null && (p = h.prev) != null) { 608 for (;;) { 609 if ((q = p.prev) == null || 610 (q = (p = q).prev) == null) { 611 // It is possible that p is PREV_TERMINATOR, 612 // but if so, the CAS is guaranteed to fail. 613 if (casHead(h, p)) 614 return; 615 else 616 continue restartFromHead; 617 } 618 else if (h != head) 619 continue restartFromHead; 620 else 621 p = q; 622 } 623 } 624 } 625 626 /** 627 * Guarantees that any node which was unlinked before a call to 628 * this method will be unreachable from tail after it returns. 629 * Does not guarantee to eliminate slack, only that tail will 630 * point to a node that was active while this method was running. 631 */ 632 private final void updateTail() { 633 // Either tail already points to an active node, or we keep 634 // trying to cas it to the last node until it does. 635 Node<E> t, p, q; 636 restartFromTail: 637 while ((t = tail).item == null && (p = t.next) != null) { 638 for (;;) { 639 if ((q = p.next) == null || 640 (q = (p = q).next) == null) { 641 // It is possible that p is NEXT_TERMINATOR, 642 // but if so, the CAS is guaranteed to fail. 643 if (casTail(t, p)) 644 return; 645 else 646 continue restartFromTail; 647 } 648 else if (t != tail) 649 continue restartFromTail; 650 else 651 p = q; 652 } 653 } 654 } 655 656 private void skipDeletedPredecessors(Node<E> x) { 657 whileActive: 658 do { 659 Node<E> prev = x.prev; 660 // assert prev != null; 661 // assert x != NEXT_TERMINATOR; 662 // assert x != PREV_TERMINATOR; 663 Node<E> p = prev; 664 findActive: 665 for (;;) { 666 if (p.item != null) 667 break findActive; 668 Node<E> q = p.prev; 669 if (q == null) { 670 if (p.next == p) 671 continue whileActive; 672 break findActive; 673 } 674 else if (p == q) 675 continue whileActive; 676 else 677 p = q; 678 } 679 680 // found active CAS target 681 if (prev == p || x.casPrev(prev, p)) 682 return; 683 684 } while (x.item != null || x.next == null); 685 } 686 687 private void skipDeletedSuccessors(Node<E> x) { 688 whileActive: 689 do { 690 Node<E> next = x.next; 691 // assert next != null; 692 // assert x != NEXT_TERMINATOR; 693 // assert x != PREV_TERMINATOR; 694 Node<E> p = next; 695 findActive: 696 for (;;) { 697 if (p.item != null) 698 break findActive; 699 Node<E> q = p.next; 700 if (q == null) { 701 if (p.prev == p) 702 continue whileActive; 703 break findActive; 704 } 705 else if (p == q) 706 continue whileActive; 707 else 708 p = q; 709 } 710 711 // found active CAS target 712 if (next == p || x.casNext(next, p)) 713 return; 714 715 } while (x.item != null || x.prev == null); 716 } 717 718 /** 719 * Returns the successor of p, or the first node if p.next has been 720 * linked to self, which will only be true if traversing with a 721 * stale pointer that is now off the list. 722 */ 723 final Node<E> succ(Node<E> p) { 724 // TODO: should we skip deleted nodes here? 725 Node<E> q = p.next; 726 return (p == q) ? first() : q; 727 } 728 729 /** 730 * Returns the predecessor of p, or the last node if p.prev has been 731 * linked to self, which will only be true if traversing with a 732 * stale pointer that is now off the list. 733 */ 734 final Node<E> pred(Node<E> p) { 735 Node<E> q = p.prev; 736 return (p == q) ? last() : q; 737 } 738 739 /** 740 * Returns the first node, the unique node p for which: 741 * p.prev == null && p.next != p 742 * The returned node may or may not be logically deleted. 743 * Guarantees that head is set to the returned node. 744 */ 745 Node<E> first() { 746 restartFromHead: 747 for (;;) 748 for (Node<E> h = head, p = h, q;;) { 749 if ((q = p.prev) != null && 750 (q = (p = q).prev) != null) 751 // Check for head updates every other hop. 752 // If p == q, we are sure to follow head instead. 753 p = (h != (h = head)) ? h : q; 754 else if (p == h 755 // It is possible that p is PREV_TERMINATOR, 756 // but if so, the CAS is guaranteed to fail. 757 || casHead(h, p)) 758 return p; 759 else 760 continue restartFromHead; 761 } 762 } 763 764 /** 765 * Returns the last node, the unique node p for which: 766 * p.next == null && p.prev != p 767 * The returned node may or may not be logically deleted. 768 * Guarantees that tail is set to the returned node. 769 */ 770 Node<E> last() { 771 restartFromTail: 772 for (;;) 773 for (Node<E> t = tail, p = t, q;;) { 774 if ((q = p.next) != null && 775 (q = (p = q).next) != null) 776 // Check for tail updates every other hop. 777 // If p == q, we are sure to follow tail instead. 778 p = (t != (t = tail)) ? t : q; 779 else if (p == t 780 // It is possible that p is NEXT_TERMINATOR, 781 // but if so, the CAS is guaranteed to fail. 782 || casTail(t, p)) 783 return p; 784 else 785 continue restartFromTail; 786 } 787 } 788 789 // Minor convenience utilities 790 791 /** 792 * Throws NullPointerException if argument is null. 793 * 794 * @param v the element 795 */ 796 private static void checkNotNull(Object v) { 797 if (v == null) 798 throw new NullPointerException(); 799 } 800 801 /** 802 * Returns element unless it is null, in which case throws 803 * NoSuchElementException. 804 * 805 * @param v the element 806 * @return the element 807 */ 808 private E screenNullResult(E v) { 809 if (v == null) 810 throw new NoSuchElementException(); 811 return v; 812 } 813 814 /** 815 * Creates an array list and fills it with elements of this list. 816 * Used by toArray. 817 * 818 * @return the array list 819 */ 820 private ArrayList<E> toArrayList() { 821 ArrayList<E> list = new ArrayList<E>(); 822 for (Node<E> p = first(); p != null; p = succ(p)) { 823 E item = p.item; 824 if (item != null) 825 list.add(item); 826 } 827 return list; 828 } 829 830 /** 831 * Constructs an empty deque. 832 */ 833 public ConcurrentLinkedDeque() { 834 head = tail = new Node<E>(null); 835 } 836 837 /** 838 * Constructs a deque initially containing the elements of 839 * the given collection, added in traversal order of the 840 * collection's iterator. 841 * 842 * @param c the collection of elements to initially contain 843 * @throws NullPointerException if the specified collection or any 844 * of its elements are null 845 */ 846 public ConcurrentLinkedDeque(Collection<? extends E> c) { 847 // Copy c into a private chain of Nodes 848 Node<E> h = null, t = null; 849 for (E e : c) { 850 checkNotNull(e); 851 Node<E> newNode = new Node<E>(e); 852 if (h == null) 853 h = t = newNode; 854 else { 855 t.lazySetNext(newNode); 856 newNode.lazySetPrev(t); 857 t = newNode; 858 } 859 } 860 initHeadTail(h, t); 861 } 862 863 /** 864 * Initializes head and tail, ensuring invariants hold. 865 */ 866 private void initHeadTail(Node<E> h, Node<E> t) { 867 if (h == t) { 868 if (h == null) 869 h = t = new Node<E>(null); 870 else { 871 // Avoid edge case of a single Node with non-null item. 872 Node<E> newNode = new Node<E>(null); 873 t.lazySetNext(newNode); 874 newNode.lazySetPrev(t); 875 t = newNode; 876 } 877 } 878 head = h; 879 tail = t; 880 } 881 882 /** 883 * Inserts the specified element at the front of this deque. 884 * As the deque is unbounded, this method will never throw 885 * {@link IllegalStateException}. 886 * 887 * @throws NullPointerException if the specified element is null 888 */ 889 public void addFirst(E e) { 890 linkFirst(e); 891 } 892 893 /** 894 * Inserts the specified element at the end of this deque. 895 * As the deque is unbounded, this method will never throw 896 * {@link IllegalStateException}. 897 * 898 * <p>This method is equivalent to {@link #add}. 899 * 900 * @throws NullPointerException if the specified element is null 901 */ 902 public void addLast(E e) { 903 linkLast(e); 904 } 905 906 /** 907 * Inserts the specified element at the front of this deque. 908 * As the deque is unbounded, this method will never return {@code false}. 909 * 910 * @return {@code true} (as specified by {@link Deque#offerFirst}) 911 * @throws NullPointerException if the specified element is null 912 */ 913 public boolean offerFirst(E e) { 914 linkFirst(e); 915 return true; 916 } 917 918 /** 919 * Inserts the specified element at the end of this deque. 920 * As the deque is unbounded, this method will never return {@code false}. 921 * 922 * <p>This method is equivalent to {@link #add}. 923 * 924 * @return {@code true} (as specified by {@link Deque#offerLast}) 925 * @throws NullPointerException if the specified element is null 926 */ 927 public boolean offerLast(E e) { 928 linkLast(e); 929 return true; 930 } 931 932 public E peekFirst() { 933 for (Node<E> p = first(); p != null; p = succ(p)) { 934 E item = p.item; 935 if (item != null) 936 return item; 937 } 938 return null; 939 } 940 941 public E peekLast() { 942 for (Node<E> p = last(); p != null; p = pred(p)) { 943 E item = p.item; 944 if (item != null) 945 return item; 946 } 947 return null; 948 } 949 950 /** 951 * @throws NoSuchElementException {@inheritDoc} 952 */ 953 public E getFirst() { 954 return screenNullResult(peekFirst()); 955 } 956 957 /** 958 * @throws NoSuchElementException {@inheritDoc} 959 */ 960 public E getLast() { 961 return screenNullResult(peekLast()); 962 } 963 964 public E pollFirst() { 965 for (Node<E> p = first(); p != null; p = succ(p)) { 966 E item = p.item; 967 if (item != null && p.casItem(item, null)) { 968 unlink(p); 969 return item; 970 } 971 } 972 return null; 973 } 974 975 public E pollLast() { 976 for (Node<E> p = last(); p != null; p = pred(p)) { 977 E item = p.item; 978 if (item != null && p.casItem(item, null)) { 979 unlink(p); 980 return item; 981 } 982 } 983 return null; 984 } 985 986 /** 987 * @throws NoSuchElementException {@inheritDoc} 988 */ 989 public E removeFirst() { 990 return screenNullResult(pollFirst()); 991 } 992 993 /** 994 * @throws NoSuchElementException {@inheritDoc} 995 */ 996 public E removeLast() { 997 return screenNullResult(pollLast()); 998 } 999 1000 // *** Queue and stack methods *** 1001 1002 /** 1003 * Inserts the specified element at the tail of this deque. 1004 * As the deque is unbounded, this method will never return {@code false}. 1005 * 1006 * @return {@code true} (as specified by {@link Queue#offer}) 1007 * @throws NullPointerException if the specified element is null 1008 */ 1009 public boolean offer(E e) { 1010 return offerLast(e); 1011 } 1012 1013 /** 1014 * Inserts the specified element at the tail of this deque. 1015 * As the deque is unbounded, this method will never throw 1016 * {@link IllegalStateException} or return {@code false}. 1017 * 1018 * @return {@code true} (as specified by {@link Collection#add}) 1019 * @throws NullPointerException if the specified element is null 1020 */ 1021 public boolean add(E e) { 1022 return offerLast(e); 1023 } 1024 1025 public E poll() { return pollFirst(); } 1026 public E peek() { return peekFirst(); } 1027 1028 /** 1029 * @throws NoSuchElementException {@inheritDoc} 1030 */ 1031 public E remove() { return removeFirst(); } 1032 1033 /** 1034 * @throws NoSuchElementException {@inheritDoc} 1035 */ 1036 public E pop() { return removeFirst(); } 1037 1038 /** 1039 * @throws NoSuchElementException {@inheritDoc} 1040 */ 1041 public E element() { return getFirst(); } 1042 1043 /** 1044 * @throws NullPointerException {@inheritDoc} 1045 */ 1046 public void push(E e) { addFirst(e); } 1047 1048 /** 1049 * Removes the first element {@code e} such that 1050 * {@code o.equals(e)}, if such an element exists in this deque. 1051 * If the deque does not contain the element, it is unchanged. 1052 * 1053 * @param o element to be removed from this deque, if present 1054 * @return {@code true} if the deque contained the specified element 1055 * @throws NullPointerException if the specified element is null 1056 */ 1057 public boolean removeFirstOccurrence(Object o) { 1058 checkNotNull(o); 1059 for (Node<E> p = first(); p != null; p = succ(p)) { 1060 E item = p.item; 1061 if (item != null && o.equals(item) && p.casItem(item, null)) { 1062 unlink(p); 1063 return true; 1064 } 1065 } 1066 return false; 1067 } 1068 1069 /** 1070 * Removes the last element {@code e} such that 1071 * {@code o.equals(e)}, if such an element exists in this deque. 1072 * If the deque does not contain the element, it is unchanged. 1073 * 1074 * @param o element to be removed from this deque, if present 1075 * @return {@code true} if the deque contained the specified element 1076 * @throws NullPointerException if the specified element is null 1077 */ 1078 public boolean removeLastOccurrence(Object o) { 1079 checkNotNull(o); 1080 for (Node<E> p = last(); p != null; p = pred(p)) { 1081 E item = p.item; 1082 if (item != null && o.equals(item) && p.casItem(item, null)) { 1083 unlink(p); 1084 return true; 1085 } 1086 } 1087 return false; 1088 } 1089 1090 /** 1091 * Returns {@code true} if this deque contains at least one 1092 * element {@code e} such that {@code o.equals(e)}. 1093 * 1094 * @param o element whose presence in this deque is to be tested 1095 * @return {@code true} if this deque contains the specified element 1096 */ 1097 public boolean contains(Object o) { 1098 if (o == null) return false; 1099 for (Node<E> p = first(); p != null; p = succ(p)) { 1100 E item = p.item; 1101 if (item != null && o.equals(item)) 1102 return true; 1103 } 1104 return false; 1105 } 1106 1107 /** 1108 * Returns {@code true} if this collection contains no elements. 1109 * 1110 * @return {@code true} if this collection contains no elements 1111 */ 1112 public boolean isEmpty() { 1113 return peekFirst() == null; 1114 } 1115 1116 /** 1117 * Returns the number of elements in this deque. If this deque 1118 * contains more than {@code Integer.MAX_VALUE} elements, it 1119 * returns {@code Integer.MAX_VALUE}. 1120 * 1121 * <p>Beware that, unlike in most collections, this method is 1122 * <em>NOT</em> a constant-time operation. Because of the 1123 * asynchronous nature of these deques, determining the current 1124 * number of elements requires traversing them all to count them. 1125 * Additionally, it is possible for the size to change during 1126 * execution of this method, in which case the returned result 1127 * will be inaccurate. Thus, this method is typically not very 1128 * useful in concurrent applications. 1129 * 1130 * @return the number of elements in this deque 1131 */ 1132 public int size() { 1133 int count = 0; 1134 for (Node<E> p = first(); p != null; p = succ(p)) 1135 if (p.item != null) 1136 // Collection.size() spec says to max out 1137 if (++count == Integer.MAX_VALUE) 1138 break; 1139 return count; 1140 } 1141 1142 /** 1143 * Removes the first element {@code e} such that 1144 * {@code o.equals(e)}, if such an element exists in this deque. 1145 * If the deque does not contain the element, it is unchanged. 1146 * 1147 * @param o element to be removed from this deque, if present 1148 * @return {@code true} if the deque contained the specified element 1149 * @throws NullPointerException if the specified element is null 1150 */ 1151 public boolean remove(Object o) { 1152 return removeFirstOccurrence(o); 1153 } 1154 1155 /** 1156 * Appends all of the elements in the specified collection to the end of 1157 * this deque, in the order that they are returned by the specified 1158 * collection's iterator. Attempts to {@code addAll} of a deque to 1159 * itself result in {@code IllegalArgumentException}. 1160 * 1161 * @param c the elements to be inserted into this deque 1162 * @return {@code true} if this deque changed as a result of the call 1163 * @throws NullPointerException if the specified collection or any 1164 * of its elements are null 1165 * @throws IllegalArgumentException if the collection is this deque 1166 */ 1167 public boolean addAll(Collection<? extends E> c) { 1168 if (c == this) 1169 // As historically specified in AbstractQueue#addAll 1170 throw new IllegalArgumentException(); 1171 1172 // Copy c into a private chain of Nodes 1173 Node<E> beginningOfTheEnd = null, last = null; 1174 for (E e : c) { 1175 checkNotNull(e); 1176 Node<E> newNode = new Node<E>(e); 1177 if (beginningOfTheEnd == null) 1178 beginningOfTheEnd = last = newNode; 1179 else { 1180 last.lazySetNext(newNode); 1181 newNode.lazySetPrev(last); 1182 last = newNode; 1183 } 1184 } 1185 if (beginningOfTheEnd == null) 1186 return false; 1187 1188 // Atomically append the chain at the tail of this collection 1189 restartFromTail: 1190 for (;;) 1191 for (Node<E> t = tail, p = t, q;;) { 1192 if ((q = p.next) != null && 1193 (q = (p = q).next) != null) 1194 // Check for tail updates every other hop. 1195 // If p == q, we are sure to follow tail instead. 1196 p = (t != (t = tail)) ? t : q; 1197 else if (p.prev == p) // NEXT_TERMINATOR 1198 continue restartFromTail; 1199 else { 1200 // p is last node 1201 beginningOfTheEnd.lazySetPrev(p); // CAS piggyback 1202 if (p.casNext(null, beginningOfTheEnd)) { 1203 // Successful CAS is the linearization point 1204 // for all elements to be added to this deque. 1205 if (!casTail(t, last)) { 1206 // Try a little harder to update tail, 1207 // since we may be adding many elements. 1208 t = tail; 1209 if (last.next == null) 1210 casTail(t, last); 1211 } 1212 return true; 1213 } 1214 // Lost CAS race to another thread; re-read next 1215 } 1216 } 1217 } 1218 1219 /** 1220 * Removes all of the elements from this deque. 1221 */ 1222 public void clear() { 1223 while (pollFirst() != null) 1224 ; 1225 } 1226 1227 /** 1228 * Returns an array containing all of the elements in this deque, in 1229 * proper sequence (from first to last element). 1230 * 1231 * <p>The returned array will be "safe" in that no references to it are 1232 * maintained by this deque. (In other words, this method must allocate 1233 * a new array). The caller is thus free to modify the returned array. 1234 * 1235 * <p>This method acts as bridge between array-based and collection-based 1236 * APIs. 1237 * 1238 * @return an array containing all of the elements in this deque 1239 */ 1240 public Object[] toArray() { 1241 return toArrayList().toArray(); 1242 } 1243 1244 /** 1245 * Returns an array containing all of the elements in this deque, 1246 * in proper sequence (from first to last element); the runtime 1247 * type of the returned array is that of the specified array. If 1248 * the deque fits in the specified array, it is returned therein. 1249 * Otherwise, a new array is allocated with the runtime type of 1250 * the specified array and the size of this deque. 1251 * 1252 * <p>If this deque fits in the specified array with room to spare 1253 * (i.e., the array has more elements than this deque), the element in 1254 * the array immediately following the end of the deque is set to 1255 * {@code null}. 1256 * 1257 * <p>Like the {@link #toArray()} method, this method acts as 1258 * bridge between array-based and collection-based APIs. Further, 1259 * this method allows precise control over the runtime type of the 1260 * output array, and may, under certain circumstances, be used to 1261 * save allocation costs. 1262 * 1263 * <p>Suppose {@code x} is a deque known to contain only strings. 1264 * The following code can be used to dump the deque into a newly 1265 * allocated array of {@code String}: 1266 * 1267 * <pre> {@code String[] y = x.toArray(new String[0]);}</pre> 1268 * 1269 * Note that {@code toArray(new Object[0])} is identical in function to 1270 * {@code toArray()}. 1271 * 1272 * @param a the array into which the elements of the deque are to 1273 * be stored, if it is big enough; otherwise, a new array of the 1274 * same runtime type is allocated for this purpose 1275 * @return an array containing all of the elements in this deque 1276 * @throws ArrayStoreException if the runtime type of the specified array 1277 * is not a supertype of the runtime type of every element in 1278 * this deque 1279 * @throws NullPointerException if the specified array is null 1280 */ 1281 public <T> T[] toArray(T[] a) { 1282 return toArrayList().toArray(a); 1283 } 1284 1285 /** 1286 * Returns an iterator over the elements in this deque in proper sequence. 1287 * The elements will be returned in order from first (head) to last (tail). 1288 * 1289 * <p>The returned iterator is 1290 * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>. 1291 * 1292 * @return an iterator over the elements in this deque in proper sequence 1293 */ 1294 public Iterator<E> iterator() { 1295 return new Itr(); 1296 } 1297 1298 /** 1299 * Returns an iterator over the elements in this deque in reverse 1300 * sequential order. The elements will be returned in order from 1301 * last (tail) to first (head). 1302 * 1303 * <p>The returned iterator is 1304 * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>. 1305 * 1306 * @return an iterator over the elements in this deque in reverse order 1307 */ 1308 public Iterator<E> descendingIterator() { 1309 return new DescendingItr(); 1310 } 1311 1312 private abstract class AbstractItr implements Iterator<E> { 1313 /** 1314 * Next node to return item for. 1315 */ 1316 private Node<E> nextNode; 1317 1318 /** 1319 * nextItem holds on to item fields because once we claim 1320 * that an element exists in hasNext(), we must return it in 1321 * the following next() call even if it was in the process of 1322 * being removed when hasNext() was called. 1323 */ 1324 private E nextItem; 1325 1326 /** 1327 * Node returned by most recent call to next. Needed by remove. 1328 * Reset to null if this element is deleted by a call to remove. 1329 */ 1330 private Node<E> lastRet; 1331 1332 abstract Node<E> startNode(); 1333 abstract Node<E> nextNode(Node<E> p); 1334 1335 AbstractItr() { 1336 advance(); 1337 } 1338 1339 /** 1340 * Sets nextNode and nextItem to next valid node, or to null 1341 * if no such. 1342 */ 1343 private void advance() { 1344 lastRet = nextNode; 1345 1346 Node<E> p = (nextNode == null) ? startNode() : nextNode(nextNode); 1347 for (;; p = nextNode(p)) { 1348 if (p == null) { 1349 // p might be active end or TERMINATOR node; both are OK 1350 nextNode = null; 1351 nextItem = null; 1352 break; 1353 } 1354 E item = p.item; 1355 if (item != null) { 1356 nextNode = p; 1357 nextItem = item; 1358 break; 1359 } 1360 } 1361 } 1362 1363 public boolean hasNext() { 1364 return nextItem != null; 1365 } 1366 1367 public E next() { 1368 E item = nextItem; 1369 if (item == null) throw new NoSuchElementException(); 1370 advance(); 1371 return item; 1372 } 1373 1374 public void remove() { 1375 Node<E> l = lastRet; 1376 if (l == null) throw new IllegalStateException(); 1377 l.item = null; 1378 unlink(l); 1379 lastRet = null; 1380 } 1381 } 1382 1383 /** Forward iterator */ 1384 private class Itr extends AbstractItr { 1385 Node<E> startNode() { return first(); } 1386 Node<E> nextNode(Node<E> p) { return succ(p); } 1387 } 1388 1389 /** Descending iterator */ 1390 private class DescendingItr extends AbstractItr { 1391 Node<E> startNode() { return last(); } 1392 Node<E> nextNode(Node<E> p) { return pred(p); } 1393 } 1394 1395 /** A customized variant of Spliterators.IteratorSpliterator */ 1396 static final class CLDSpliterator<E> implements Spliterator<E> { 1397 static final int MAX_BATCH = 1 << 25; // max batch array size; 1398 final ConcurrentLinkedDeque<E> queue; 1399 Node<E> current; // current node; null until initialized 1400 int batch; // batch size for splits 1401 boolean exhausted; // true when no more nodes 1402 CLDSpliterator(ConcurrentLinkedDeque<E> queue) { 1403 this.queue = queue; 1404 } 1405 1406 public Spliterator<E> trySplit() { 1407 Node<E> p; 1408 final ConcurrentLinkedDeque<E> q = this.queue; 1409 int b = batch; 1410 int n = (b <= 0) ? 1 : (b >= MAX_BATCH) ? MAX_BATCH : b + 1; 1411 if (!exhausted && 1412 ((p = current) != null || (p = q.first()) != null)) { 1413 if (p.item == null && p == (p = p.next)) 1414 current = p = q.first(); 1415 if (p != null && p.next != null) { 1416 Object[] a = new Object[n]; 1417 int i = 0; 1418 do { 1419 if ((a[i] = p.item) != null) 1420 ++i; 1421 if (p == (p = p.next)) 1422 p = q.first(); 1423 } while (p != null && i < n); 1424 if ((current = p) == null) 1425 exhausted = true; 1426 if (i > 0) { 1427 batch = i; 1428 return Spliterators.spliterator 1429 (a, 0, i, Spliterator.ORDERED | Spliterator.NONNULL | 1430 Spliterator.CONCURRENT); 1431 } 1432 } 1433 } 1434 return null; 1435 } 1436 1437 public void forEachRemaining(Consumer<? super E> action) { 1438 Node<E> p; 1439 if (action == null) throw new NullPointerException(); 1440 final ConcurrentLinkedDeque<E> q = this.queue; 1441 if (!exhausted && 1442 ((p = current) != null || (p = q.first()) != null)) { 1443 exhausted = true; 1444 do { 1445 E e = p.item; 1446 if (p == (p = p.next)) 1447 p = q.first(); 1448 if (e != null) 1449 action.accept(e); 1450 } while (p != null); 1451 } 1452 } 1453 1454 public boolean tryAdvance(Consumer<? super E> action) { 1455 Node<E> p; 1456 if (action == null) throw new NullPointerException(); 1457 final ConcurrentLinkedDeque<E> q = this.queue; 1458 if (!exhausted && 1459 ((p = current) != null || (p = q.first()) != null)) { 1460 E e; 1461 do { 1462 e = p.item; 1463 if (p == (p = p.next)) 1464 p = q.first(); 1465 } while (e == null && p != null); 1466 if ((current = p) == null) 1467 exhausted = true; 1468 if (e != null) { 1469 action.accept(e); 1470 return true; 1471 } 1472 } 1473 return false; 1474 } 1475 1476 public long estimateSize() { return Long.MAX_VALUE; } 1477 1478 public int characteristics() { 1479 return Spliterator.ORDERED | Spliterator.NONNULL | 1480 Spliterator.CONCURRENT; 1481 } 1482 } 1483 1484 /** 1485 * Returns a {@link Spliterator} over the elements in this deque. 1486 * 1487 * <p>The returned spliterator is 1488 * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>. 1489 * 1490 * <p>The {@code Spliterator} reports {@link Spliterator#CONCURRENT}, 1491 * {@link Spliterator#ORDERED}, and {@link Spliterator#NONNULL}. 1492 * 1493 * @implNote 1494 * The {@code Spliterator} implements {@code trySplit} to permit limited 1495 * parallelism. 1496 * 1497 * @return a {@code Spliterator} over the elements in this deque 1498 * @since 1.8 1499 */ 1500 public Spliterator<E> spliterator() { 1501 return new CLDSpliterator<E>(this); 1502 } 1503 1504 /** 1505 * Saves this deque to a stream (that is, serializes it). 1506 * 1507 * @param s the stream 1508 * @throws java.io.IOException if an I/O error occurs 1509 * @serialData All of the elements (each an {@code E}) in 1510 * the proper order, followed by a null 1511 */ 1512 private void writeObject(java.io.ObjectOutputStream s) 1513 throws java.io.IOException { 1514 1515 // Write out any hidden stuff 1516 s.defaultWriteObject(); 1517 1518 // Write out all elements in the proper order. 1519 for (Node<E> p = first(); p != null; p = succ(p)) { 1520 E item = p.item; 1521 if (item != null) 1522 s.writeObject(item); 1523 } 1524 1525 // Use trailing null as sentinel 1526 s.writeObject(null); 1527 } 1528 1529 /** 1530 * Reconstitutes this deque from a stream (that is, deserializes it). 1531 * @param s the stream 1532 * @throws ClassNotFoundException if the class of a serialized object 1533 * could not be found 1534 * @throws java.io.IOException if an I/O error occurs 1535 */ 1536 private void readObject(java.io.ObjectInputStream s) 1537 throws java.io.IOException, ClassNotFoundException { 1538 s.defaultReadObject(); 1539 1540 // Read in elements until trailing null sentinel found 1541 Node<E> h = null, t = null; 1542 Object item; 1543 while ((item = s.readObject()) != null) { 1544 @SuppressWarnings("unchecked") 1545 Node<E> newNode = new Node<E>((E) item); 1546 if (h == null) 1547 h = t = newNode; 1548 else { 1549 t.lazySetNext(newNode); 1550 newNode.lazySetPrev(t); 1551 t = newNode; 1552 } 1553 } 1554 initHeadTail(h, t); 1555 } 1556 1557 private boolean casHead(Node<E> cmp, Node<E> val) { 1558 return UNSAFE.compareAndSwapObject(this, headOffset, cmp, val); 1559 } 1560 1561 private boolean casTail(Node<E> cmp, Node<E> val) { 1562 return UNSAFE.compareAndSwapObject(this, tailOffset, cmp, val); 1563 } 1564 1565 // Unsafe mechanics 1566 1567 private static final sun.misc.Unsafe UNSAFE; 1568 private static final long headOffset; 1569 private static final long tailOffset; 1570 static { 1571 PREV_TERMINATOR = new Node<Object>(); 1572 PREV_TERMINATOR.next = PREV_TERMINATOR; 1573 NEXT_TERMINATOR = new Node<Object>(); 1574 NEXT_TERMINATOR.prev = NEXT_TERMINATOR; 1575 try { 1576 UNSAFE = sun.misc.Unsafe.getUnsafe(); 1577 Class<?> k = ConcurrentLinkedDeque.class; 1578 headOffset = UNSAFE.objectFieldOffset 1579 (k.getDeclaredField("head")); 1580 tailOffset = UNSAFE.objectFieldOffset 1581 (k.getDeclaredField("tail")); 1582 } catch (Exception e) { 1583 throw new Error(e); 1584 } 1585 } 1586 } | 16 * You should have received a copy of the GNU General Public License version 17 * 2 along with this work; if not, write to the Free Software Foundation, 18 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 19 * 20 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 21 * or visit www.oracle.com if you need additional information or have any 22 * questions. 23 */ 24 25 /* 26 * This file is available under and governed by the GNU General Public 27 * License version 2 only, as published by the Free Software Foundation. 28 * However, the following notice accompanied the original version of this 29 * file: 30 * 31 * Written by Doug Lea and Martin Buchholz with assistance from members of 32 * JCP JSR-166 Expert Group and released to the public domain, as explained 33 * at http://creativecommons.org/publicdomain/zero/1.0/ 34 */ 35 36 package java.lang.ref; 37 38 /** 39 * A concurrent doubly-linked list of {@link java.lang.ref.Finalizer} nodes 40 * modeled by {@link java.util.concurrent.ConcurrentLinkedDeque}. 41 */ 42 final class FinalizerList { 43 44 /** 45 * A node from which the first node on list (that is, the unique node p 46 * with p.prev == null && p.next != p) can be reached in O(1) time. 47 * Invariants: 48 * - the first node is always O(1) reachable from head via prev links 49 * - all live nodes are reachable from the first node via succ() 50 * - head != null 51 * - (tmp = head).next != tmp || tmp != head 52 * - head is never gc-unlinked (but may be unlinked) 53 * Non-invariants: 54 * - head.item may or may not be null 55 * - head may not be reachable from the first or last node, or from tail 56 */ 57 private volatile Finalizer head; 58 59 /** 60 * A node from which the last node on list (that is, the unique node p 61 * with p.next == null && p.prev != p) can be reached in O(1) time. 62 * Invariants: 63 * - the last node is always O(1) reachable from tail via next links 64 * - all live nodes are reachable from the last node via pred() 65 * - tail != null 66 * - tail is never gc-unlinked (but may be unlinked) 67 * Non-invariants: 68 * - tail.item may or may not be null 69 * - tail may not be reachable from the first or last node, or from head 70 */ 71 private volatile Finalizer tail; 72 73 private static final Finalizer PREV_TERMINATOR, NEXT_TERMINATOR; 74 75 /** 76 * Links newFinalizer as first or last element, depending on 77 * specified boolean flag. 78 */ 79 void link(Finalizer newFinalizer, boolean first) { 80 if (first) { 81 linkFirst(newFinalizer); 82 } else { 83 linkLast(newFinalizer); 84 } 85 } 86 87 /** 88 * Links newFinalizer as first element. 89 */ 90 private void linkFirst(Finalizer newFinalizer) { 91 92 restartFromHead: 93 for (;;) 94 for (Finalizer h = head, p = h, q;;) { 95 if ((q = p.prev) != null && 96 (q = (p = q).prev) != null) 97 // Check for head updates every other hop. 98 // If p == q, we are sure to follow head instead. 99 p = (h != (h = head)) ? h : q; 100 else if (p.next == p) // PREV_TERMINATOR 101 continue restartFromHead; 102 else { 103 // p is first node 104 newFinalizer.lazySetNext(p); // CAS piggyback 105 if (p.casPrev(null, newFinalizer)) { 106 // Successful CAS is the linearization point 107 // for e to become an element of this deque, 108 // and for newNode to become "live". 109 if (p != h) // hop two nodes at a time 110 casHead(h, newFinalizer); // Failure is OK. 111 return; 112 } 113 // Lost CAS race to another thread; re-read prev 114 } 115 } 116 } 117 118 /** 119 * Links newNode as last element. 120 */ 121 private void linkLast(Finalizer newFinalizer) { 122 123 restartFromTail: 124 for (;;) 125 for (Finalizer t = tail, p = t, q;;) { 126 if ((q = p.next) != null && 127 (q = (p = q).next) != null) 128 // Check for tail updates every other hop. 129 // If p == q, we are sure to follow tail instead. 130 p = (t != (t = tail)) ? t : q; 131 else if (p.prev == p) // NEXT_TERMINATOR 132 continue restartFromTail; 133 else { 134 // p is last node 135 newFinalizer.lazySetPrev(p); // CAS piggyback 136 if (p.casNext(null, newFinalizer)) { 137 // Successful CAS is the linearization point 138 // for e to become an element of this deque, 139 // and for newNode to become "live". 140 if (p != t) // hop two nodes at a time 141 casTail(t, newFinalizer); // Failure is OK. 142 return; 143 } 144 // Lost CAS race to another thread; re-read next 145 } 146 } 147 } 148 149 private static final int HOPS = 2; 150 151 /** 152 * Unlinks non-null node x. 153 */ 154 void unlink(Finalizer x) { 155 // assert x != null; 156 // assert x.item == null; 157 // assert x != PREV_TERMINATOR; 158 // assert x != NEXT_TERMINATOR; 159 160 final Finalizer prev = x.prev; 161 final Finalizer next = x.next; 162 if (prev == null) { 163 unlinkFirst(x, next); 164 } else if (next == null) { 165 unlinkLast(x, prev); 166 } else { 167 // Unlink interior node. 168 // 169 // This is the common case, since a series of polls at the 170 // same end will be "interior" removes, except perhaps for 171 // the first one, since end nodes cannot be unlinked. 172 // 173 // At any time, all active nodes are mutually reachable by 174 // following a sequence of either next or prev pointers. 175 // 176 // Our strategy is to find the unique active predecessor 177 // and successor of x. Try to fix up their links so that 178 // they point to each other, leaving x unreachable from 179 // active nodes. If successful, and if x has no live 180 // predecessor/successor, we additionally try to gc-unlink, 181 // leaving active nodes unreachable from x, by rechecking 182 // that the status of predecessor and successor are 183 // unchanged and ensuring that x is not reachable from 184 // tail/head, before setting x's prev/next links to their 185 // logical approximate replacements, self/TERMINATOR. 186 Finalizer activePred, activeSucc; 187 boolean isFirst, isLast; 188 int hops = 1; 189 190 // Find active predecessor 191 for (Finalizer p = prev; ; ++hops) { 192 if (p.isAlive()) { 193 activePred = p; 194 isFirst = false; 195 break; 196 } 197 Finalizer q = p.prev; 198 if (q == null) { 199 if (p.next == p) 200 return; 201 activePred = p; 202 isFirst = true; 203 break; 204 } 205 else if (p == q) 206 return; 207 else 208 p = q; 209 } 210 211 // Find active successor 212 for (Finalizer p = next; ; ++hops) { 213 if (p.isAlive()) { 214 activeSucc = p; 215 isLast = false; 216 break; 217 } 218 Finalizer q = p.next; 219 if (q == null) { 220 if (p.prev == p) 221 return; 222 activeSucc = p; 223 isLast = true; 224 break; 225 } 226 else if (p == q) 227 return; 228 else 229 p = q; 230 } 231 232 // TODO: better HOP heuristics 233 if (hops < HOPS 234 // always squeeze out interior deleted nodes 235 && (isFirst | isLast)) 236 return; 237 238 // Squeeze out deleted nodes between activePred and 239 // activeSucc, including x. 240 skipDeletedSuccessors(activePred); 241 skipDeletedPredecessors(activeSucc); 242 243 // Try to gc-unlink, if possible 244 if ((isFirst | isLast) && 245 246 // Recheck expected state of predecessor and successor 247 (activePred.next == activeSucc) && 248 (activeSucc.prev == activePred) && 249 (isFirst ? activePred.prev == null : activePred.isAlive()) && 250 (isLast ? activeSucc.next == null : activeSucc.isAlive())) { 251 252 updateHead(); // Ensure x is not reachable from head 253 updateTail(); // Ensure x is not reachable from tail 254 255 // Finally, actually gc-unlink 256 x.lazySetPrev(isFirst ? PREV_TERMINATOR : x); 257 x.lazySetNext(isLast ? NEXT_TERMINATOR : x); 258 } 259 } 260 } 261 262 /** 263 * Unlinks non-null first node. 264 */ 265 private void unlinkFirst(Finalizer first, Finalizer next) { 266 // assert first != null; 267 // assert next != null; 268 // assert first.item == null; 269 for (Finalizer o = null, p = next, q;;) { 270 if (p.isAlive() || (q = p.next) == null) { 271 if (o != null && p.prev != p && first.casNext(next, p)) { 272 skipDeletedPredecessors(p); 273 if (first.prev == null && 274 (p.next == null || p.isAlive()) && 275 p.prev == first) { 276 277 updateHead(); // Ensure o is not reachable from head 278 updateTail(); // Ensure o is not reachable from tail 279 280 // Finally, actually gc-unlink 281 o.lazySetNext(o); 282 o.lazySetPrev(PREV_TERMINATOR); 283 } 284 } 285 return; 286 } 287 else if (p == q) 288 return; 289 else { 290 o = p; 291 p = q; 292 } 293 } 294 } 295 296 /** 297 * Unlinks non-null last node. 298 */ 299 private void unlinkLast(Finalizer last, Finalizer prev) { 300 // assert last != null; 301 // assert prev != null; 302 // assert last.item == null; 303 for (Finalizer o = null, p = prev, q;;) { 304 if (p.isAlive() || (q = p.prev) == null) { 305 if (o != null && p.next != p && last.casPrev(prev, p)) { 306 skipDeletedSuccessors(p); 307 if (last.next == null && 308 (p.prev == null || p.isAlive()) && 309 p.next == last) { 310 311 updateHead(); // Ensure o is not reachable from head 312 updateTail(); // Ensure o is not reachable from tail 313 314 // Finally, actually gc-unlink 315 o.lazySetPrev(o); 316 o.lazySetNext(NEXT_TERMINATOR); 317 } 318 } 319 return; 320 } 321 else if (p == q) 322 return; 323 else { 324 o = p; 325 p = q; 326 } 327 } 328 } 329 330 /** 331 * Guarantees that any node which was unlinked before a call to 332 * this method will be unreachable from head after it returns. 333 * Does not guarantee to eliminate slack, only that head will 334 * point to a node that was active while this method was running. 335 */ 336 private void updateHead() { 337 // Either head already points to an active node, or we keep 338 // trying to cas it to the first node until it does. 339 Finalizer h, p, q; 340 restartFromHead: 341 while ((h = head).isDeleted() && (p = h.prev) != null) { 342 for (;;) { 343 if ((q = p.prev) == null || 344 (q = (p = q).prev) == null) { 345 // It is possible that p is PREV_TERMINATOR, 346 // but if so, the CAS is guaranteed to fail. 347 if (casHead(h, p)) 348 return; 349 else 350 continue restartFromHead; 351 } 352 else if (h != head) 353 continue restartFromHead; 354 else 355 p = q; 356 } 357 } 358 } 359 360 /** 361 * Guarantees that any node which was unlinked before a call to 362 * this method will be unreachable from tail after it returns. 363 * Does not guarantee to eliminate slack, only that tail will 364 * point to a node that was active while this method was running. 365 */ 366 private void updateTail() { 367 // Either tail already points to an active node, or we keep 368 // trying to cas it to the last node until it does. 369 Finalizer t, p, q; 370 restartFromTail: 371 while ((t = tail).isDeleted() && (p = t.next) != null) { 372 for (;;) { 373 if ((q = p.next) == null || 374 (q = (p = q).next) == null) { 375 // It is possible that p is NEXT_TERMINATOR, 376 // but if so, the CAS is guaranteed to fail. 377 if (casTail(t, p)) 378 return; 379 else 380 continue restartFromTail; 381 } 382 else if (t != tail) 383 continue restartFromTail; 384 else 385 p = q; 386 } 387 } 388 } 389 390 private void skipDeletedPredecessors(Finalizer x) { 391 whileActive: 392 do { 393 Finalizer prev = x.prev; 394 // assert prev != null; 395 // assert x != NEXT_TERMINATOR; 396 // assert x != PREV_TERMINATOR; 397 Finalizer p = prev; 398 findActive: 399 for (;;) { 400 if (p.isAlive()) 401 break findActive; 402 Finalizer q = p.prev; 403 if (q == null) { 404 if (p.next == p) 405 continue whileActive; 406 break findActive; 407 } 408 else if (p == q) 409 continue whileActive; 410 else 411 p = q; 412 } 413 414 // found active CAS target 415 if (prev == p || x.casPrev(prev, p)) 416 return; 417 418 } while (x.isAlive() || x.next == null); 419 } 420 421 private void skipDeletedSuccessors(Finalizer x) { 422 whileActive: 423 do { 424 Finalizer next = x.next; 425 // assert next != null; 426 // assert x != NEXT_TERMINATOR; 427 // assert x != PREV_TERMINATOR; 428 Finalizer p = next; 429 findActive: 430 for (;;) { 431 if (p.isAlive()) 432 break findActive; 433 Finalizer q = p.next; 434 if (q == null) { 435 if (p.prev == p) 436 continue whileActive; 437 break findActive; 438 } 439 else if (p == q) 440 continue whileActive; 441 else 442 p = q; 443 } 444 445 // found active CAS target 446 if (next == p || x.casNext(next, p)) 447 return; 448 449 } while (x.isAlive() || x.prev == null); 450 } 451 452 /** 453 * Returns the successor of p, or the first node if p.next has been 454 * linked to self, which will only be true if traversing with a 455 * stale pointer that is now off the list. 456 */ 457 Finalizer succ(Finalizer p) { 458 // TODO: should we skip deleted nodes here? 459 Finalizer q = p.next; 460 return (p == q) ? first() : q; 461 } 462 463 /** 464 * Returns the predecessor of p, or the last node if p.prev has been 465 * linked to self, which will only be true if traversing with a 466 * stale pointer that is now off the list. 467 */ 468 Finalizer pred(Finalizer p) { 469 Finalizer q = p.prev; 470 return (p == q) ? last() : q; 471 } 472 473 /** 474 * Returns the first node, the unique node p for which: 475 * p.prev == null && p.next != p 476 * The returned node may or may not be logically deleted. 477 * Guarantees that head is set to the returned node. 478 */ 479 Finalizer first() { 480 restartFromHead: 481 for (;;) 482 for (Finalizer h = head, p = h, q;;) { 483 if ((q = p.prev) != null && 484 (q = (p = q).prev) != null) 485 // Check for head updates every other hop. 486 // If p == q, we are sure to follow head instead. 487 p = (h != (h = head)) ? h : q; 488 else if (p == h 489 // It is possible that p is PREV_TERMINATOR, 490 // but if so, the CAS is guaranteed to fail. 491 || casHead(h, p)) 492 return p; 493 else 494 continue restartFromHead; 495 } 496 } 497 498 /** 499 * Returns the last node, the unique node p for which: 500 * p.next == null && p.prev != p 501 * The returned node may or may not be logically deleted. 502 * Guarantees that tail is set to the returned node. 503 */ 504 Finalizer last() { 505 restartFromTail: 506 for (;;) 507 for (Finalizer t = tail, p = t, q;;) { 508 if ((q = p.next) != null && 509 (q = (p = q).next) != null) 510 // Check for tail updates every other hop. 511 // If p == q, we are sure to follow tail instead. 512 p = (t != (t = tail)) ? t : q; 513 else if (p == t 514 // It is possible that p is NEXT_TERMINATOR, 515 // but if so, the CAS is guaranteed to fail. 516 || casTail(t, p)) 517 return p; 518 else 519 continue restartFromTail; 520 } 521 } 522 523 /** 524 * Constructs an empty list. 525 */ 526 FinalizerList() { 527 head = tail = new Finalizer(); 528 } 529 530 // Unsafe mechanics 531 532 private boolean casHead(Finalizer cmp, Finalizer val) { 533 return UNSAFE.compareAndSwapObject(this, HEAD, cmp, val); 534 } 535 536 private boolean casTail(Finalizer cmp, Finalizer val) { 537 return UNSAFE.compareAndSwapObject(this, TAIL, cmp, val); 538 } 539 540 private static final sun.misc.Unsafe UNSAFE; 541 private static final long HEAD; 542 private static final long TAIL; 543 static { 544 PREV_TERMINATOR = new Finalizer(); 545 PREV_TERMINATOR.next = PREV_TERMINATOR; 546 NEXT_TERMINATOR = new Finalizer(); 547 NEXT_TERMINATOR.prev = NEXT_TERMINATOR; 548 try { 549 UNSAFE = sun.misc.Unsafe.getUnsafe(); 550 Class<?> flc = FinalizerList.class; 551 HEAD = UNSAFE.objectFieldOffset 552 (flc.getDeclaredField("head")); 553 TAIL = UNSAFE.objectFieldOffset 554 (flc.getDeclaredField("tail")); 555 } catch (Exception e) { 556 throw new Error(e); 557 } 558 } 559 } |