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.53 by jsr166, Tue Oct 27 19:59:43 2009 UTC vs.
Revision 1.61 by jsr166, Mon Nov 2 00:28:28 2009 UTC

# Line 373 | Line 373 | public class LinkedTransferQueue<E> exte
373          }
374  
375          final boolean casItem(Object cmp, Object val) {
376 +            assert cmp == null || cmp.getClass() != Node.class;
377              return UNSAFE.compareAndSwapObject(this, itemOffset, cmp, val);
378          }
379  
# Line 409 | Line 410 | public class LinkedTransferQueue<E> exte
410           */
411          final boolean isMatched() {
412              Object x = item;
413 <            return x == this || (x != null) != isData;
413 >            return (x == this) || ((x == null) == isData);
414 >        }
415 >
416 >        /**
417 >         * Returns true if this is an unmatched request node.
418 >         */
419 >        final boolean isUnmatchedRequest() {
420 >            return !isData && item == null;
421          }
422  
423          /**
# Line 427 | Line 435 | public class LinkedTransferQueue<E> exte
435           * Tries to artificially match a data node -- used by remove.
436           */
437          final boolean tryMatchData() {
438 +            assert isData;
439              Object x = item;
440              if (x != null && x != this && casItem(x, null)) {
441                  LockSupport.unpark(waiter);
# Line 448 | Line 457 | public class LinkedTransferQueue<E> exte
457      }
458  
459      /** head of the queue; null until first enqueue */
460 <    private transient volatile Node head;
460 >    transient volatile Node head;
461  
462      /** predecessor of dangling unspliceable node */
463 <    private transient volatile Node cleanMe; // decl here to reduce 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 tail;
# Line 478 | Line 487 | public class LinkedTransferQueue<E> exte
487      private static final int SYNC    = 2; // for transfer, take
488      private static final int TIMEOUT = 3; // for timed poll, tryTransfer
489  
490 +    @SuppressWarnings("unchecked")
491 +    static <E> E cast(Object item) {
492 +        assert item == null || item.getClass() != Node.class;
493 +        return (E) item;
494 +    }
495 +
496      /**
497       * Implements all queuing methods. See above for explanation.
498       *
# Line 488 | Line 503 | public class LinkedTransferQueue<E> exte
503       * @return an item if matched, else e
504       * @throws NullPointerException if haveData mode but e is null
505       */
506 <    private Object xfer(Object e, boolean haveData, int how, long nanos) {
506 >    private E xfer(E e, boolean haveData, int how, long nanos) {
507          if (haveData && (e == null))
508              throw new NullPointerException();
509          Node s = null;                        // the node to append, if needed
# Line 515 | Line 530 | public class LinkedTransferQueue<E> exte
530                                  break;        // unless slack < 2
531                          }
532                          LockSupport.unpark(p.waiter);
533 <                        return item;
533 >                        return this.<E>cast(item);
534                      }
535                  }
536                  Node n = p.next;
# Line 545 | Line 560 | public class LinkedTransferQueue<E> exte
560       * predecessor
561       */
562      private Node tryAppend(Node s, boolean haveData) {
563 <        for (Node t = tail, p = t;;) { // move p to last node and append
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))
# Line 582 | 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 Object awaitMatch(Node s, Node pred, Object e,
586 <                              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 592 | Line 606 | public class LinkedTransferQueue<E> exte
606          for (;;) {
607              Object item = s.item;
608              if (item != e) {                  // matched
609 +                assert item != s;
610                  s.forgetContents();           // avoid garbage
611 <                return item;
611 >                return this.<E>cast(item);
612              }
613              if ((w.isInterrupted() || (how == TIMEOUT && nanos <= 0)) &&
614 <                     s.casItem(e, s)) {       // cancel
614 >                    s.casItem(e, s)) {       // cancel
615                  unsplice(pred, s);
616                  return e;
617              }
# Line 683 | Line 698 | public class LinkedTransferQueue<E> exte
698  
699      /**
700       * Returns the item in the first unmatched node with isData; or
701 <     * null if none. Used by peek.
701 >     * null if none.  Used by peek.
702       */
703 <    private Object firstDataItem() {
703 >    private E firstDataItem() {
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 ? item : null;
708 >                return isData ? this.<E>cast(item) : null;
709              Node n = p.next;
710              p = (n != p) ? n : head;
711          }
# Line 723 | Line 738 | public class LinkedTransferQueue<E> exte
738  
739      final class Itr implements Iterator<E> {
740          private Node nextNode;   // next node to return item for
741 <        private Object nextItem; // the corresponding item
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 prev) {
749 +            lastPred = lastRet;
750              lastRet = prev;
751              Node p;
752              if (prev == null || (p = prev.next) == prev)
# Line 738 | Line 755 | public class LinkedTransferQueue<E> exte
755                  Object item = p.item;
756                  if (p.isData) {
757                      if (item != null && item != p) {
758 <                        nextItem = item;
758 >                        nextItem = LinkedTransferQueue.this.<E>cast(item);
759                          nextNode = p;
760                          return;
761                      }
# Line 762 | Line 779 | public class LinkedTransferQueue<E> exte
779          public final E next() {
780              Node p = nextNode;
781              if (p == null) throw new NoSuchElementException();
782 <            Object e = nextItem;
782 >            E e = nextItem;
783              advance(p);
784 <            return (E) e;
784 >            return e;
785          }
786  
787          public final void remove() {
788              Node p = lastRet;
789              if (p == null) throw new IllegalStateException();
790 <            lastRet = null;
774 <            findAndRemoveNode(p);
790 >            findAndRemoveDataNode(lastPred, p);
791          }
792      }
793  
# Line 805 | Line 821 | public class LinkedTransferQueue<E> exte
821                      break;
822                  }
823                  if (oldpred == pred ||      // Already saved
824 <                    (oldpred == null && casCleanMe(null, pred)))
825 <                    break;                  // Postpone cleaning
824 >                    ((oldpred == null || oldpred.next == s) &&
825 >                     casCleanMe(oldpred, pred))) {
826 >                    break;
827 >                }
828              }
829          }
830      }
# Line 847 | Line 865 | public class LinkedTransferQueue<E> exte
865  
866      /**
867       * Main implementation of Iterator.remove(). Find
868 <     * and unsplice the given node.
868 >     * and unsplice the given data node.
869 >     * @param possiblePred possible predecessor of s
870 >     * @param s the node to remove
871       */
872 <    final void findAndRemoveNode(Node s) {
872 >    final void findAndRemoveDataNode(Node possiblePred, Node s) {
873 >        assert s.isData;
874          if (s.tryMatchData()) {
875 <            Node pred = null;
876 <            Node p = head;
877 <            while (p != null) {
878 <                if (p == s) {
879 <                    unsplice(pred, p);
880 <                    break;
881 <                }
882 <                if (!p.isData && !p.isMatched())
883 <                    break;
884 <                pred = p;
885 <                if ((p = p.next) == pred) { // stale
886 <                    pred = null;
887 <                    p = head;
875 >            if (possiblePred != null && possiblePred.next == s)
876 >                unsplice(possiblePred, s); // was actual predecessor
877 >            else {
878 >                for (Node pred = null, p = head; p != null; ) {
879 >                    if (p == s) {
880 >                        unsplice(pred, p);
881 >                        break;
882 >                    }
883 >                    if (p.isUnmatchedRequest())
884 >                        break;
885 >                    pred = p;
886 >                    if ((p = p.next) == pred) { // stale
887 >                        pred = null;
888 >                        p = head;
889 >                    }
890                  }
891              }
892          }
# Line 874 | Line 897 | public class LinkedTransferQueue<E> exte
897       */
898      private boolean findAndRemove(Object e) {
899          if (e != null) {
900 <            Node pred = null;
878 <            Node p = head;
879 <            while (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) &&
# Line 888 | Line 909 | public class LinkedTransferQueue<E> exte
909                  else if (item == null)
910                      break;
911                  pred = p;
912 <                if ((p = p.next) == pred) {
912 >                if ((p = p.next) == pred) { // stale
913                      pred = null;
914                      p = head;
915                  }
# Line 1024 | Line 1045 | public class LinkedTransferQueue<E> exte
1045      }
1046  
1047      public E take() throws InterruptedException {
1048 <        Object e = xfer(null, false, SYNC, 0);
1048 >        E e = xfer(null, false, SYNC, 0);
1049          if (e != null)
1050 <            return (E)e;
1050 >            return e;
1051          Thread.interrupted();
1052          throw new InterruptedException();
1053      }
1054  
1055      public E poll(long timeout, TimeUnit unit) throws InterruptedException {
1056 <        Object e = xfer(null, false, TIMEOUT, unit.toNanos(timeout));
1056 >        E e = xfer(null, false, TIMEOUT, unit.toNanos(timeout));
1057          if (e != null || !Thread.interrupted())
1058 <            return (E)e;
1058 >            return e;
1059          throw new InterruptedException();
1060      }
1061  
1062      public E poll() {
1063 <        return (E)xfer(null, false, NOW, 0);
1063 >        return xfer(null, false, NOW, 0);
1064      }
1065  
1066      /**
# Line 1096 | Line 1117 | public class LinkedTransferQueue<E> exte
1117      }
1118  
1119      public E peek() {
1120 <        return (E) firstDataItem();
1120 >        return firstDataItem();
1121      }
1122  
1123      /**
# Line 1221 | Line 1242 | public class LinkedTransferQueue<E> exte
1242       *
1243       * @return a sun.misc.Unsafe
1244       */
1245 <    private static sun.misc.Unsafe getUnsafe() {
1245 >    static sun.misc.Unsafe getUnsafe() {
1246          try {
1247              return sun.misc.Unsafe.getUnsafe();
1248          } catch (SecurityException se) {

Diff Legend

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