48 * The <em>head</em> of the queue is that element that has been on the 49 * queue the longest time. 50 * The <em>tail</em> of the queue is that element that has been on the 51 * queue the shortest time. New elements 52 * are inserted at the tail of the queue, and the queue retrieval 53 * operations obtain elements at the head of the queue. 54 * A {@code ConcurrentLinkedQueue} is an appropriate choice when 55 * many threads will share access to a common collection. 56 * Like most other concurrent collection implementations, this class 57 * does not permit the use of {@code null} elements. 58 * 59 * <p>This implementation employs an efficient "wait-free" 60 * algorithm based on one described in <a 61 * href="http://www.cs.rochester.edu/u/michael/PODC96.html"> Simple, 62 * Fast, and Practical Non-Blocking and Blocking Concurrent Queue 63 * Algorithms</a> by Maged M. Michael and Michael L. Scott. 64 * 65 * <p>Iterators are <i>weakly consistent</i>, returning elements 66 * reflecting the state of the queue at some point at or since the 67 * creation of the iterator. They do <em>not</em> throw {@link 68 * ConcurrentModificationException}, and may proceed concurrently with 69 * other operations. Elements contained in the queue since the creation 70 * of the iterator will be returned exactly once. 71 * 72 * <p>Beware that, unlike in most collections, the {@code size} method 73 * is <em>NOT</em> a constant-time operation. Because of the 74 * asynchronous nature of these queues, determining the current number 75 * of elements requires a traversal of the elements. 76 * 77 * <p>This class and its iterator implement all of the <em>optional</em> 78 * methods of the {@link Queue} and {@link Iterator} interfaces. 79 * 80 * <p>Memory consistency effects: As with other concurrent 81 * collections, actions in a thread prior to placing an object into a 82 * {@code ConcurrentLinkedQueue} 83 * <a href="package-summary.html#MemoryVisibility"><i>happen-before</i></a> 84 * actions subsequent to the access or removal of that element from 85 * the {@code ConcurrentLinkedQueue} in another thread. 86 * 87 * <p>This class is a member of the 88 * <a href="{@docRoot}/../technotes/guides/collections/index.html"> 89 * Java Collections Framework</a>. 252 for (E e : c) { 253 checkNotNull(e); 254 Node<E> newNode = new Node<E>(e); 255 if (h == null) 256 h = t = newNode; 257 else { 258 t.lazySetNext(newNode); 259 t = newNode; 260 } 261 } 262 if (h == null) 263 h = t = new Node<E>(null); 264 head = h; 265 tail = t; 266 } 267 268 // Have to override just to update the javadoc 269 270 /** 271 * Inserts the specified element at the tail of this queue. 272 * 273 * @return {@code true} (as specified by {@link Collection#add}) 274 * @throws NullPointerException if the specified element is null 275 */ 276 public boolean add(E e) { 277 return offer(e); 278 } 279 280 /** 281 * Try to CAS head to p. If successful, repoint old head to itself 282 * as sentinel for succ(), below. 283 */ 284 final void updateHead(Node<E> h, Node<E> p) { 285 if (h != p && casHead(h, p)) 286 h.lazySetNext(h); 287 } 288 289 /** 290 * Returns the successor of p, or the head node if p.next has been 291 * linked to self, which will only be true if traversing with a 292 * stale pointer that is now off the list. 293 */ 294 final Node<E> succ(Node<E> p) { 295 Node<E> next = p.next; 296 return (p == next) ? head : next; 297 } 298 299 /** 300 * Inserts the specified element at the tail of this queue. 301 * 302 * @return {@code true} (as specified by {@link Queue#offer}) 303 * @throws NullPointerException if the specified element is null 304 */ 305 public boolean offer(E e) { 306 checkNotNull(e); 307 final Node<E> newNode = new Node<E>(e); 308 309 for (Node<E> t = tail, p = t;;) { 310 Node<E> q = p.next; 311 if (q == null) { 312 // p is last node 313 if (p.casNext(null, newNode)) { 314 // Successful CAS is the linearization point 315 // for e to become an element of this queue, 316 // and for newNode to become "live". 317 if (p != t) // hop two nodes at a time 318 casTail(t, newNode); // Failure is OK. 319 return true; 320 } 617 if (p == null) { 618 if (k < a.length) 619 a[k] = null; 620 return a; 621 } 622 623 // If won't fit, use ArrayList version 624 ArrayList<E> al = new ArrayList<E>(); 625 for (Node<E> q = first(); q != null; q = succ(q)) { 626 E item = q.item; 627 if (item != null) 628 al.add(item); 629 } 630 return al.toArray(a); 631 } 632 633 /** 634 * Returns an iterator over the elements in this queue in proper sequence. 635 * The elements will be returned in order from first (head) to last (tail). 636 * 637 * <p>The returned {@code Iterator} is a "weakly consistent" iterator that 638 * will never throw {@link java.util.ConcurrentModificationException 639 * ConcurrentModificationException}, 640 * and guarantees to traverse elements as they existed upon 641 * construction of the iterator, and may (but is not guaranteed to) 642 * reflect any modifications subsequent to construction. 643 * 644 * @return an iterator over the elements in this queue in proper sequence 645 */ 646 public Iterator<E> iterator() { 647 return new Itr(); 648 } 649 650 private class Itr implements Iterator<E> { 651 /** 652 * Next node to return item for. 653 */ 654 private Node<E> nextNode; 655 656 /** 657 * nextItem holds on to item fields because once we claim 658 * that an element exists in hasNext(), we must return it in 659 * the following next() call even if it was in the process of 660 * being removed when hasNext() was called. 661 */ 662 private E nextItem; | 48 * The <em>head</em> of the queue is that element that has been on the 49 * queue the longest time. 50 * The <em>tail</em> of the queue is that element that has been on the 51 * queue the shortest time. New elements 52 * are inserted at the tail of the queue, and the queue retrieval 53 * operations obtain elements at the head of the queue. 54 * A {@code ConcurrentLinkedQueue} is an appropriate choice when 55 * many threads will share access to a common collection. 56 * Like most other concurrent collection implementations, this class 57 * does not permit the use of {@code null} elements. 58 * 59 * <p>This implementation employs an efficient "wait-free" 60 * algorithm based on one described in <a 61 * href="http://www.cs.rochester.edu/u/michael/PODC96.html"> Simple, 62 * Fast, and Practical Non-Blocking and Blocking Concurrent Queue 63 * Algorithms</a> by Maged M. Michael and Michael L. Scott. 64 * 65 * <p>Iterators are <i>weakly consistent</i>, returning elements 66 * reflecting the state of the queue at some point at or since the 67 * creation of the iterator. They do <em>not</em> throw {@link 68 * java.util.ConcurrentModificationException}, and may proceed concurrently 69 * with other operations. Elements contained in the queue since the creation 70 * of the iterator will be returned exactly once. 71 * 72 * <p>Beware that, unlike in most collections, the {@code size} method 73 * is <em>NOT</em> a constant-time operation. Because of the 74 * asynchronous nature of these queues, determining the current number 75 * of elements requires a traversal of the elements. 76 * 77 * <p>This class and its iterator implement all of the <em>optional</em> 78 * methods of the {@link Queue} and {@link Iterator} interfaces. 79 * 80 * <p>Memory consistency effects: As with other concurrent 81 * collections, actions in a thread prior to placing an object into a 82 * {@code ConcurrentLinkedQueue} 83 * <a href="package-summary.html#MemoryVisibility"><i>happen-before</i></a> 84 * actions subsequent to the access or removal of that element from 85 * the {@code ConcurrentLinkedQueue} in another thread. 86 * 87 * <p>This class is a member of the 88 * <a href="{@docRoot}/../technotes/guides/collections/index.html"> 89 * Java Collections Framework</a>. 252 for (E e : c) { 253 checkNotNull(e); 254 Node<E> newNode = new Node<E>(e); 255 if (h == null) 256 h = t = newNode; 257 else { 258 t.lazySetNext(newNode); 259 t = newNode; 260 } 261 } 262 if (h == null) 263 h = t = new Node<E>(null); 264 head = h; 265 tail = t; 266 } 267 268 // Have to override just to update the javadoc 269 270 /** 271 * Inserts the specified element at the tail of this queue. 272 * As the queue is unbounded, this method will never throw 273 * {@link IllegalStateException} or return {@code false}. 274 * 275 * @return {@code true} (as specified by {@link Collection#add}) 276 * @throws NullPointerException if the specified element is null 277 */ 278 public boolean add(E e) { 279 return offer(e); 280 } 281 282 /** 283 * Try to CAS head to p. If successful, repoint old head to itself 284 * as sentinel for succ(), below. 285 */ 286 final void updateHead(Node<E> h, Node<E> p) { 287 if (h != p && casHead(h, p)) 288 h.lazySetNext(h); 289 } 290 291 /** 292 * Returns the successor of p, or the head node if p.next has been 293 * linked to self, which will only be true if traversing with a 294 * stale pointer that is now off the list. 295 */ 296 final Node<E> succ(Node<E> p) { 297 Node<E> next = p.next; 298 return (p == next) ? head : next; 299 } 300 301 /** 302 * Inserts the specified element at the tail of this queue. 303 * As the queue is unbounded, this method will never return {@code false}. 304 * 305 * @return {@code true} (as specified by {@link Queue#offer}) 306 * @throws NullPointerException if the specified element is null 307 */ 308 public boolean offer(E e) { 309 checkNotNull(e); 310 final Node<E> newNode = new Node<E>(e); 311 312 for (Node<E> t = tail, p = t;;) { 313 Node<E> q = p.next; 314 if (q == null) { 315 // p is last node 316 if (p.casNext(null, newNode)) { 317 // Successful CAS is the linearization point 318 // for e to become an element of this queue, 319 // and for newNode to become "live". 320 if (p != t) // hop two nodes at a time 321 casTail(t, newNode); // Failure is OK. 322 return true; 323 } 620 if (p == null) { 621 if (k < a.length) 622 a[k] = null; 623 return a; 624 } 625 626 // If won't fit, use ArrayList version 627 ArrayList<E> al = new ArrayList<E>(); 628 for (Node<E> q = first(); q != null; q = succ(q)) { 629 E item = q.item; 630 if (item != null) 631 al.add(item); 632 } 633 return al.toArray(a); 634 } 635 636 /** 637 * Returns an iterator over the elements in this queue in proper sequence. 638 * The elements will be returned in order from first (head) to last (tail). 639 * 640 * <p>The returned iterator is a "weakly consistent" iterator that 641 * will never throw {@link java.util.ConcurrentModificationException 642 * ConcurrentModificationException}, and guarantees to traverse 643 * elements as they existed upon construction of the iterator, and 644 * may (but is not guaranteed to) reflect any modifications 645 * subsequent to construction. 646 * 647 * @return an iterator over the elements in this queue in proper sequence 648 */ 649 public Iterator<E> iterator() { 650 return new Itr(); 651 } 652 653 private class Itr implements Iterator<E> { 654 /** 655 * Next node to return item for. 656 */ 657 private Node<E> nextNode; 658 659 /** 660 * nextItem holds on to item fields because once we claim 661 * that an element exists in hasNext(), we must return it in 662 * the following next() call even if it was in the process of 663 * being removed when hasNext() was called. 664 */ 665 private E nextItem; |