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