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.61 by jsr166, Mon Nov 2 00:28:28 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 687 | Line 686 | public class LinkedTransferQueue<E> exte
686       * Returns the first unmatched node of the given mode, or null if
687       * none.  Used by methods isEmpty, hasWaitingConsumer.
688       */
689 <    private Node<E> firstOfMode(boolean data) {
690 <        for (Node<E> p = head; p != null; ) {
689 >    private Node firstOfMode(boolean data) {
690 >        for (Node p = head; p != null; ) {
691              if (!p.isMatched())
692                  return (p.isData == data) ? p : null;
693 <            Node<E> n = p.next;
693 >            Node n = p.next;
694              p = (n != p) ? n : head;
695          }
696          return null;
# Line 702 | Line 701 | public class LinkedTransferQueue<E> exte
701       * null if none.  Used by peek.
702       */
703      private E firstDataItem() {
704 <        for (Node<E> p = head; p != null; ) {
704 >        for (Node p = head; p != null; ) {
705              boolean isData = p.isData;
706              Object item = p.item;
707              if (item != p && (item != null) == isData)
708                  return isData ? this.<E>cast(item) : null;
709 <            Node<E> n = p.next;
709 >            Node n = p.next;
710              p = (n != p) ? n : head;
711          }
712          return null;
# Line 719 | Line 718 | public class LinkedTransferQueue<E> exte
718       */
719      private int countOfMode(boolean data) {
720          int count = 0;
721 <        for (Node<E> p = head; p != null; ) {
721 >        for (Node p = head; p != null; ) {
722              if (!p.isMatched()) {
723                  if (p.isData != data)
724                      return 0;
725                  if (++count == Integer.MAX_VALUE) // saturated
726                      break;
727              }
728 <            Node<E> n = p.next;
728 >            Node n = p.next;
729              if (n != p)
730                  p = n;
731              else {
# Line 738 | Line 737 | public class LinkedTransferQueue<E> exte
737      }
738  
739      final class Itr implements Iterator<E> {
740 <        private Node<E> nextNode;   // next node to return item for
741 <        private E nextItem;         // the corresponding item
742 <        private Node<E> lastRet;    // last returned node, to support remove
743 <        private Node<E> lastPred;   // predecessor to unlink lastRet
740 >        private Node nextNode;   // next node to return item for
741 >        private E nextItem;      // the corresponding item
742 >        private Node lastRet;    // last returned node, to support remove
743 >        private Node lastPred;   // predecessor to unlink lastRet
744  
745          /**
746           * Moves to next node after prev, or first node if prev null.
747           */
748 <        private void advance(Node<E> prev) {
748 >        private void advance(Node prev) {
749              lastPred = lastRet;
750              lastRet = prev;
751 <            Node<E> p;
751 >            Node p;
752              if (prev == null || (p = prev.next) == prev)
753                  p = head;
754              while (p != null) {
# Line 763 | Line 762 | public class LinkedTransferQueue<E> exte
762                  }
763                  else if (item == null)
764                      break;
765 <                Node<E> n = p.next;
765 >                Node n = p.next;
766                  p = (n != p) ? n : head;
767              }
768              nextNode = null;
# Line 778 | Line 777 | public class LinkedTransferQueue<E> exte
777          }
778  
779          public final E next() {
780 <            Node<E> p = nextNode;
780 >            Node p = nextNode;
781              if (p == null) throw new NoSuchElementException();
782              E e = nextItem;
783              advance(p);
# Line 786 | Line 785 | public class LinkedTransferQueue<E> exte
785          }
786  
787          public final void remove() {
788 <            Node<E> p = lastRet;
788 >            Node p = lastRet;
789              if (p == null) throw new IllegalStateException();
790              findAndRemoveDataNode(lastPred, p);
791          }
# Line 801 | Line 800 | public class LinkedTransferQueue<E> exte
800       * @param pred predecessor of node to be unspliced
801       * @param s the node to be unspliced
802       */
803 <    private void unsplice(Node<E> pred, Node<E> s) {
803 >    private void unsplice(Node pred, Node s) {
804          s.forgetContents(); // clear unneeded fields
805          /*
806           * At any given time, exactly one node on list cannot be
# Line 814 | Line 813 | public class LinkedTransferQueue<E> exte
813           */
814          if (pred != null && pred != s) {
815              while (pred.next == s) {
816 <                Node<E> oldpred = (cleanMe == null) ? null : reclean();
817 <                Node<E> n = s.next;
816 >                Node oldpred = (cleanMe == null) ? null : reclean();
817 >                Node n = s.next;
818                  if (n != null) {
819                      if (n != s)
820                          pred.casNext(s, n);
# Line 836 | Line 835 | public class LinkedTransferQueue<E> exte
835       *
836       * @return current cleanMe node (or null)
837       */
838 <    private Node<E> reclean() {
838 >    private Node reclean() {
839          /*
840           * cleanMe is, or at one time was, predecessor of a cancelled
841           * node s that was the tail so could not be unspliced.  If it
# Line 847 | Line 846 | public class LinkedTransferQueue<E> exte
846           * we can (must) clear cleanMe without unsplicing.  This can
847           * loop only due to contention.
848           */
849 <        Node<E> pred;
849 >        Node pred;
850          while ((pred = cleanMe) != null) {
851 <            Node<E> s = pred.next;
852 <            Node<E> n;
851 >            Node s = pred.next;
852 >            Node n;
853              if (s == null || s == pred || !s.isMatched())
854                  casCleanMe(pred, null); // already gone
855              else if ((n = s.next) != null) {
# Line 870 | Line 869 | public class LinkedTransferQueue<E> exte
869       * @param possiblePred possible predecessor of s
870       * @param s the node to remove
871       */
872 <    final void findAndRemoveDataNode(Node<E> possiblePred, Node<E> s) {
872 >    final void findAndRemoveDataNode(Node possiblePred, Node s) {
873          assert s.isData;
874          if (s.tryMatchData()) {
875              if (possiblePred != null && possiblePred.next == s)
876                  unsplice(possiblePred, s); // was actual predecessor
877              else {
878 <                for (Node<E> pred = null, p = head; p != null; ) {
878 >                for (Node pred = null, p = head; p != null; ) {
879                      if (p == s) {
880                          unsplice(pred, p);
881                          break;
# Line 898 | Line 897 | public class LinkedTransferQueue<E> exte
897       */
898      private boolean findAndRemove(Object e) {
899          if (e != null) {
900 <            for (Node<E> pred = null, p = head; p != null; ) {
900 >            for (Node pred = null, p = head; p != null; ) {
901                  Object item = p.item;
902                  if (p.isData) {
903                      if (item != null && item != p && e.equals(item) &&

Diff Legend

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