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