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