src/share/classes/java/util/concurrent/ConcurrentLinkedQueue.java

Print this page




  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 &quot;wait-free&quot;
  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 &quot;wait-free&quot;
  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;