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