ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/jsr166y/LinkedTransferQueue.java
(Generate patch)

Comparing jsr166/src/jsr166y/LinkedTransferQueue.java (file contents):
Revision 1.60 by dl, Fri Oct 30 12:06:31 2009 UTC vs.
Revision 1.62 by jsr166, Mon Nov 2 03:01:10 2009 UTC

# Line 361 | Line 361 | public class LinkedTransferQueue<E> exte
361       * precede or follow CASes use simple relaxed forms.  Other
362       * cleanups use releasing/lazy writes.
363       */
364 <    static final class Node<E> {
364 >    static final class Node {
365          final boolean isData;   // false if this is a request node
366          volatile Object item;   // initially non-null if isData; CASed to match
367 <        volatile Node<E> next;
367 >        volatile Node next;
368          volatile Thread waiter; // null until waiting
369  
370          // CAS methods for fields
371 <        final boolean casNext(Node<E> cmp, Node<E> val) {
371 >        final boolean casNext(Node cmp, Node val) {
372              return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val);
373          }
374  
# Line 381 | Line 381 | public class LinkedTransferQueue<E> exte
381           * Creates a new node. Uses relaxed write because item can only
382           * be seen if followed by CAS.
383           */
384 <        Node(E item, boolean isData) {
384 >        Node(Object item, boolean isData) {
385              UNSAFE.putObject(this, itemOffset, item); // relaxed write
386              this.isData = isData;
387          }
# Line 457 | Line 457 | public class LinkedTransferQueue<E> exte
457      }
458  
459      /** head of the queue; null until first enqueue */
460 <    transient volatile Node<E> head;
460 >    transient volatile Node head;
461  
462      /** predecessor of dangling unspliceable node */
463 <    private transient volatile Node<E> cleanMe; // decl here reduces contention
463 >    private transient volatile Node cleanMe; // decl here reduces contention
464  
465      /** tail of the queue; null until first append */
466 <    private transient volatile Node<E> tail;
466 >    private transient volatile Node tail;
467  
468      // CAS methods for fields
469 <    private boolean casTail(Node<E> cmp, Node<E> val) {
469 >    private boolean casTail(Node cmp, Node val) {
470          return UNSAFE.compareAndSwapObject(this, tailOffset, cmp, val);
471      }
472  
473 <    private boolean casHead(Node<E> cmp, Node<E> val) {
473 >    private boolean casHead(Node cmp, Node val) {
474          return UNSAFE.compareAndSwapObject(this, headOffset, cmp, val);
475      }
476  
477 <    private boolean casCleanMe(Node<E> cmp, Node<E> val) {
477 >    private boolean casCleanMe(Node cmp, Node val) {
478          return UNSAFE.compareAndSwapObject(this, cleanMeOffset, cmp, val);
479      }
480  
# Line 506 | Line 506 | public class LinkedTransferQueue<E> exte
506      private E xfer(E e, boolean haveData, int how, long nanos) {
507          if (haveData && (e == null))
508              throw new NullPointerException();
509 <        Node<E> s = null;                     // the node to append, if needed
509 >        Node s = null;                        // the node to append, if needed
510  
511          retry: for (;;) {                     // restart on append race
512  
513 <            for (Node<E> h = head, p = h; p != null;) {
514 <                // find & match first node
513 >            for (Node h = head, p = h; p != null;) { // find & match first node
514                  boolean isData = p.isData;
515                  Object item = p.item;
516                  if (item != p && (item != null) == isData) { // unmatched
517                      if (isData == haveData)   // can't match
518                          break;
519                      if (p.casItem(item, e)) { // match
520 <                        for (Node<E> q = p; q != h;) {
521 <                            Node<E> n = q.next; // update head by 2
520 >                        for (Node q = p; q != h;) {
521 >                            Node n = q.next;  // update head by 2
522                              if (n != null)    // unless singleton
523                                  q = n;
524                              if (head == h && casHead(h, q)) {
# Line 534 | Line 533 | public class LinkedTransferQueue<E> exte
533                          return this.<E>cast(item);
534                      }
535                  }
536 <                Node<E> n = p.next;
536 >                Node n = p.next;
537                  p = (p != n) ? n : (h = head); // Use head if p offlist
538              }
539  
540              if (how >= ASYNC) {               // No matches available
541                  if (s == null)
542 <                    s = new Node<E>(e, haveData);
543 <                Node<E> pred = tryAppend(s, haveData);
542 >                    s = new Node(e, haveData);
543 >                Node pred = tryAppend(s, haveData);
544                  if (pred == null)
545                      continue retry;           // lost race vs opposite mode
546                  if (how >= SYNC)
# Line 560 | Line 559 | public class LinkedTransferQueue<E> exte
559       * different mode, else s's predecessor, or s itself if no
560       * predecessor
561       */
562 <    private Node<E> tryAppend(Node<E> s, boolean haveData) {
563 <        for (Node<E> t = tail, p = t;;) { // move p to last node and append
564 <            Node<E> n, u;                     // temps for reads of next & tail
562 >    private Node tryAppend(Node s, boolean haveData) {
563 >        for (Node t = tail, p = t;;) {        // move p to last node and append
564 >            Node n, u;                        // temps for reads of next & tail
565              if (p == null && (p = head) == null) {
566                  if (casHead(null, s))
567                      return s;                 // initialize
# Line 598 | Line 597 | public class LinkedTransferQueue<E> exte
597       * @param nanos timeout value
598       * @return matched item, or e if unmatched on interrupt or timeout
599       */
600 <    private E awaitMatch(Node<E> s, Node<E> pred, E e, int how, long nanos) {
600 >    private E awaitMatch(Node s, Node pred, E e, int how, long nanos) {
601          long lastTime = (how == TIMEOUT) ? System.nanoTime() : 0L;
602          Thread w = Thread.currentThread();
603          int spins = -1; // initialized after first item and cancel checks
# Line 648 | Line 647 | public class LinkedTransferQueue<E> exte
647       * Returns spin/yield value for a node with given predecessor and
648       * data mode. See above for explanation.
649       */
650 <    private static int spinsFor(Node<?> pred, boolean haveData) {
650 >    private static int spinsFor(Node pred, boolean haveData) {
651          if (MP && pred != null) {
652              if (pred.isData != haveData)      // phase change
653                  return FRONT_SPINS + CHAINED_SPINS;
# Line 665 | Line 664 | public class LinkedTransferQueue<E> exte
664       * or trailing node; failing on contention.
665       */
666      private void shortenHeadPath() {
667 <        Node<E> h, hn, p, q;
667 >        Node h, hn, p, q;
668          if ((p = h = head) != null && h.isMatched() &&
669              (q = hn = h.next) != null) {
670 <            Node<E> n;
670 >            Node n;
671              while ((n = q.next) != q) {
672                  if (n == null || !q.isMatched()) {
673                      if (hn != q && h.next == hn)
# Line 684 | Line 683 | public class LinkedTransferQueue<E> exte
683      /* -------------- Traversal methods -------------- */
684  
685      /**
686 +     * Returns the successor of p, or the head node if p.next has been
687 +     * linked to self, which will only be true if traversing with a
688 +     * stale pointer that is now off the list.
689 +     */
690 +    final Node succ(Node p) {
691 +        Node next = p.next;
692 +        return (p == next) ? head : next;
693 +    }
694 +
695 +    /**
696       * Returns the first unmatched node of the given mode, or null if
697       * none.  Used by methods isEmpty, hasWaitingConsumer.
698       */
699 <    private Node<E> firstOfMode(boolean data) {
700 <        for (Node<E> p = head; p != null; ) {
699 >    private Node firstOfMode(boolean isData) {
700 >        for (Node p = head; p != null; p = succ(p)) {
701              if (!p.isMatched())
702 <                return (p.isData == data) ? p : null;
694 <            Node<E> n = p.next;
695 <            p = (n != p) ? n : head;
702 >                return (p.isData == isData) ? p : null;
703          }
704          return null;
705      }
# Line 702 | Line 709 | public class LinkedTransferQueue<E> exte
709       * null if none.  Used by peek.
710       */
711      private E firstDataItem() {
712 <        for (Node<E> p = head; p != null; ) {
706 <            boolean isData = p.isData;
712 >        for (Node p = head; p != null; p = succ(p)) {
713              Object item = p.item;
714 <            if (item != p && (item != null) == isData)
715 <                return isData ? this.<E>cast(item) : null;
716 <            Node<E> n = p.next;
717 <            p = (n != p) ? n : head;
714 >            if (p.isData) {
715 >                if (item != null && item != p)
716 >                    return this.<E>cast(item);
717 >            }
718 >            else if (item == null)
719 >                return null;
720          }
721          return null;
722      }
# Line 719 | Line 727 | public class LinkedTransferQueue<E> exte
727       */
728      private int countOfMode(boolean data) {
729          int count = 0;
730 <        for (Node<E> p = head; p != null; ) {
730 >        for (Node p = head; p != null; ) {
731              if (!p.isMatched()) {
732                  if (p.isData != data)
733                      return 0;
734                  if (++count == Integer.MAX_VALUE) // saturated
735                      break;
736              }
737 <            Node<E> n = p.next;
737 >            Node n = p.next;
738              if (n != p)
739                  p = n;
740              else {
# Line 738 | Line 746 | public class LinkedTransferQueue<E> exte
746      }
747  
748      final class Itr implements Iterator<E> {
749 <        private Node<E> nextNode;   // next node to return item for
750 <        private E nextItem;         // the corresponding item
751 <        private Node<E> lastRet;    // last returned node, to support remove
752 <        private Node<E> lastPred;   // predecessor to unlink lastRet
749 >        private Node nextNode;   // next node to return item for
750 >        private E nextItem;      // the corresponding item
751 >        private Node lastRet;    // last returned node, to support remove
752 >        private Node lastPred;   // predecessor to unlink lastRet
753  
754          /**
755           * Moves to next node after prev, or first node if prev null.
756           */
757 <        private void advance(Node<E> prev) {
757 >        private void advance(Node prev) {
758              lastPred = lastRet;
759              lastRet = prev;
760 <            Node<E> p;
761 <            if (prev == null || (p = prev.next) == prev)
754 <                p = head;
755 <            while (p != null) {
760 >            for (Node p = (prev == null) ? head : succ(prev);
761 >                 p != null; p = succ(p)) {
762                  Object item = p.item;
763                  if (p.isData) {
764                      if (item != null && item != p) {
# Line 763 | Line 769 | public class LinkedTransferQueue<E> exte
769                  }
770                  else if (item == null)
771                      break;
766 –                Node<E> n = p.next;
767 –                p = (n != p) ? n : head;
772              }
773              nextNode = null;
774          }
# Line 778 | Line 782 | public class LinkedTransferQueue<E> exte
782          }
783  
784          public final E next() {
785 <            Node<E> p = nextNode;
785 >            Node p = nextNode;
786              if (p == null) throw new NoSuchElementException();
787              E e = nextItem;
788              advance(p);
# Line 786 | Line 790 | public class LinkedTransferQueue<E> exte
790          }
791  
792          public final void remove() {
793 <            Node<E> p = lastRet;
793 >            Node p = lastRet;
794              if (p == null) throw new IllegalStateException();
795              findAndRemoveDataNode(lastPred, p);
796          }
# Line 801 | Line 805 | public class LinkedTransferQueue<E> exte
805       * @param pred predecessor of node to be unspliced
806       * @param s the node to be unspliced
807       */
808 <    private void unsplice(Node<E> pred, Node<E> s) {
808 >    private void unsplice(Node pred, Node s) {
809          s.forgetContents(); // clear unneeded fields
810          /*
811           * At any given time, exactly one node on list cannot be
# Line 814 | Line 818 | public class LinkedTransferQueue<E> exte
818           */
819          if (pred != null && pred != s) {
820              while (pred.next == s) {
821 <                Node<E> oldpred = (cleanMe == null) ? null : reclean();
822 <                Node<E> n = s.next;
821 >                Node oldpred = (cleanMe == null) ? null : reclean();
822 >                Node n = s.next;
823                  if (n != null) {
824                      if (n != s)
825                          pred.casNext(s, n);
# Line 836 | Line 840 | public class LinkedTransferQueue<E> exte
840       *
841       * @return current cleanMe node (or null)
842       */
843 <    private Node<E> reclean() {
843 >    private Node reclean() {
844          /*
845           * cleanMe is, or at one time was, predecessor of a cancelled
846           * node s that was the tail so could not be unspliced.  If it
# Line 847 | Line 851 | public class LinkedTransferQueue<E> exte
851           * we can (must) clear cleanMe without unsplicing.  This can
852           * loop only due to contention.
853           */
854 <        Node<E> pred;
854 >        Node pred;
855          while ((pred = cleanMe) != null) {
856 <            Node<E> s = pred.next;
857 <            Node<E> n;
856 >            Node s = pred.next;
857 >            Node n;
858              if (s == null || s == pred || !s.isMatched())
859                  casCleanMe(pred, null); // already gone
860              else if ((n = s.next) != null) {
# Line 870 | Line 874 | public class LinkedTransferQueue<E> exte
874       * @param possiblePred possible predecessor of s
875       * @param s the node to remove
876       */
877 <    final void findAndRemoveDataNode(Node<E> possiblePred, Node<E> s) {
877 >    final void findAndRemoveDataNode(Node possiblePred, Node s) {
878          assert s.isData;
879          if (s.tryMatchData()) {
880              if (possiblePred != null && possiblePred.next == s)
881                  unsplice(possiblePred, s); // was actual predecessor
882              else {
883 <                for (Node<E> pred = null, p = head; p != null; ) {
883 >                for (Node pred = null, p = head; p != null; ) {
884                      if (p == s) {
885                          unsplice(pred, p);
886                          break;
# Line 898 | Line 902 | public class LinkedTransferQueue<E> exte
902       */
903      private boolean findAndRemove(Object e) {
904          if (e != null) {
905 <            for (Node<E> pred = null, p = head; p != null; ) {
905 >            for (Node pred = null, p = head; p != null; ) {
906                  Object item = p.item;
907                  if (p.isData) {
908                      if (item != null && item != p && e.equals(item) &&

Diff Legend

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