ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/main/java/util/concurrent/LinkedBlockingQueue.java
(Generate patch)

Comparing jsr166/src/main/java/util/concurrent/LinkedBlockingQueue.java (file contents):
Revision 1.107 by jsr166, Thu Dec 29 17:42:05 2016 UTC vs.
Revision 1.108 by jsr166, Thu Dec 29 20:29:07 2016 UTC

# Line 730 | Line 730 | public class LinkedBlockingQueue<E> exte
730          return new Itr();
731      }
732  
733 +    /**
734 +     * Weakly-consistent iterator.
735 +     *
736 +     * Lazily updated ancestor field provides expected O(1) remove(),
737 +     * but still O(n) in the worst case, whenever the saved ancestor
738 +     * is concurrently deleted.
739 +     */
740      private class Itr implements Iterator<E> {
741 <        /*
742 <         * Basic weakly-consistent iterator.  At all times hold the next
736 <         * item to hand out so that if hasNext() reports true, we will
737 <         * still have it to return even if lost race with a take etc.
738 <         */
739 <
740 <        private Node<E> next;
741 <        private E nextItem;
741 >        private Node<E> next;           // Node holding nextItem
742 >        private E nextItem;             // next item to hand out
743          private Node<E> lastRet;
744 +        private Node<E> ancestor;       // Helps unlink lastRet on remove()
745  
746          Itr() {
747              fullyLock();
# Line 814 | Line 816 | public class LinkedBlockingQueue<E> exte
816          }
817  
818          public void remove() {
819 <            if (lastRet == null)
819 >            Node<E> p = lastRet;
820 >            if (p == null)
821                  throw new IllegalStateException();
822 +            lastRet = null;
823              fullyLock();
824              try {
825 <                Node<E> node = lastRet;
826 <                lastRet = null;
827 <                for (Node<E> pred = head, p = pred.next;
828 <                     p != null;
829 <                     pred = p, p = p.next) {
826 <                    if (p == node) {
827 <                        unlink(p, pred);
828 <                        break;
829 <                    }
825 >                if (p.item != null) {
826 >                    if (ancestor == null)
827 >                        ancestor = head;
828 >                    ancestor = findPred(p, ancestor);
829 >                    unlink(p, ancestor);
830                  }
831              } finally {
832                  fullyUnlock();
# Line 1013 | Line 1013 | public class LinkedBlockingQueue<E> exte
1013       * Returns the predecessor of live node p, given a node that was
1014       * once a live ancestor of p (or head); allows unlinking of p.
1015       */
1016 <    private Node<E> findPred(Node<E> p, Node<E> ancestor) {
1016 >    Node<E> findPred(Node<E> p, Node<E> ancestor) {
1017          // assert p.item != null;
1018          if (ancestor.item == null)
1019              ancestor = head;

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines