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.11 by jsr166, Mon Jan 5 03:53:26 2009 UTC vs.
Revision 1.16 by jsr166, Mon Mar 30 04:32:23 2009 UTC

# Line 116 | Line 116 | public class LinkedTransferQueue<E> exte
116              nextUpdater = AtomicReferenceFieldUpdater.newUpdater
117              (QNode.class, QNode.class, "next");
118  
119 <        boolean casNext(QNode cmp, QNode val) {
119 >        final boolean casNext(QNode cmp, QNode val) {
120              return nextUpdater.compareAndSet(this, cmp, val);
121          }
122 +
123 +        final void clearNext() {
124 +            nextUpdater.lazySet(this, this);
125 +        }
126 +
127      }
128  
129      /**
# Line 151 | Line 156 | public class LinkedTransferQueue<E> exte
156       */
157      private boolean advanceHead(QNode h, QNode nh) {
158          if (h == head.get() && head.compareAndSet(h, nh)) {
159 <            h.next = h; // forget old next
159 >            h.clearNext(); // forget old next
160              return true;
161          }
162          return false;
# Line 298 | Line 303 | public class LinkedTransferQueue<E> exte
303              else if (s.waiter == null)
304                  s.waiter = w;
305              else if (mode != TIMEOUT) {
306 <                //                LockSupport.park(this);
302 <                LockSupport.park(); // allows run on java5
306 >                LockSupport.park(this);
307                  s.waiter = null;
308                  spins = -1;
309              }
310              else if (nanos > spinForTimeoutThreshold) {
311 <                //                LockSupport.parkNanos(this, nanos);
308 <                LockSupport.parkNanos(nanos);
311 >                LockSupport.parkNanos(this, nanos);
312                  s.waiter = null;
313                  spins = -1;
314              }
# Line 346 | Line 349 | public class LinkedTransferQueue<E> exte
349              if (w != Thread.currentThread())
350                  LockSupport.unpark(w);
351          }
352 +
353 +        if (pred == null)
354 +            return;
355 +
356          /*
357           * At any given time, exactly one node on list cannot be
358           * deleted -- the last inserted node. To accommodate this, if
# Line 444 | Line 451 | public class LinkedTransferQueue<E> exte
451          return true;
452      }
453  
454 +    public boolean add(E e) {
455 +        if (e == null) throw new NullPointerException();
456 +        xfer(e, NOWAIT, 0);
457 +        return true;
458 +    }
459 +
460      public void transfer(E e) throws InterruptedException {
461          if (e == null) throw new NullPointerException();
462          if (xfer(e, WAIT, 0) == null) {
# Line 540 | Line 553 | public class LinkedTransferQueue<E> exte
553                          return h;
554                  }
555              }
556 +            reclean();
557          }
558      }
559  
# Line 556 | Line 570 | public class LinkedTransferQueue<E> exte
570       * if subsequently removed.
571       */
572      class Itr implements Iterator<E> {
573 <        QNode nextNode;    // Next node to return next
574 <        QNode currentNode; // last returned node, for remove()
575 <        QNode prevNode;    // predecessor of last returned node
573 >        QNode next;        // node to return next
574 >        QNode pnext;       // predecessor of next
575 >        QNode snext;       // successor of next
576 >        QNode curr;        // last returned node, for remove()
577 >        QNode pcurr;       // predecessor of curr, for remove()
578          E nextItem;        // Cache of next item, once commited to in next
579  
580          Itr() {
581 <            nextNode = traversalHead();
566 <            advance();
581 >            findNext();
582          }
583  
584 <        E advance() {
585 <            prevNode = currentNode;
586 <            currentNode = nextNode;
587 <            E x = nextItem;
573 <
574 <            QNode p = nextNode.next;
584 >        /**
585 >         * Ensure next points to next valid node, or null if none.
586 >         */
587 >        void findNext() {
588              for (;;) {
589 <                if (p == null || !p.isData) {
590 <                    nextNode = null;
591 <                    nextItem = null;
592 <                    return x;
589 >                QNode pred = pnext;
590 >                QNode q = next;
591 >                if (pred == null || pred == q) {
592 >                    pred = traversalHead();
593 >                    q = pred.next;
594 >                }
595 >                if (q == null || !q.isData) {
596 >                    next = null;
597 >                    return;
598 >                }
599 >                Object x = q.get();
600 >                QNode s = q.next;
601 >                if (x != null && q != x && q != s) {
602 >                    nextItem = (E)x;
603 >                    snext = s;
604 >                    pnext = pred;
605 >                    next = q;
606 >                    return;
607                  }
608 <                Object item = p.get();
609 <                if (item != p && item != null) {
583 <                    nextNode = p;
584 <                    nextItem = (E)item;
585 <                    return x;
586 <                }
587 <                prevNode = p;
588 <                p = p.next;
608 >                pnext = q;
609 >                next = s;
610              }
611          }
612  
613          public boolean hasNext() {
614 <            return nextNode != null;
614 >            return next != null;
615          }
616  
617          public E next() {
618 <            if (nextNode == null) throw new NoSuchElementException();
619 <            return advance();
618 >            if (next == null) throw new NoSuchElementException();
619 >            pcurr = pnext;
620 >            curr = next;
621 >            pnext = next;
622 >            next = snext;
623 >            E x = nextItem;
624 >            findNext();
625 >            return x;
626          }
627  
628          public void remove() {
629 <            QNode p = currentNode;
630 <            QNode prev = prevNode;
604 <            if (prev == null || p == null)
629 >            QNode p = curr;
630 >            if (p == null)
631                  throw new IllegalStateException();
632              Object x = p.get();
633              if (x != null && x != p && p.compareAndSet(x, p))
634 <                clean(prev, p);
634 >                clean(pcurr, p);
635          }
636      }
637  
# Line 694 | Line 720 | public class LinkedTransferQueue<E> exte
720          return Integer.MAX_VALUE;
721      }
722  
723 +    public boolean remove(Object o) {
724 +        if (o == null)
725 +            return false;
726 +        for (;;) {
727 +            QNode pred = traversalHead();
728 +            for (;;) {
729 +                QNode q = pred.next;
730 +                if (q == null || !q.isData)
731 +                    return false;
732 +                if (q == pred) // restart
733 +                    break;
734 +                Object x = q.get();
735 +                if (x != null && x != q && o.equals(x) &&
736 +                    q.compareAndSet(x, q)) {
737 +                    clean(pred, q);
738 +                    return true;
739 +                }
740 +                pred = q;
741 +            }
742 +        }
743 +    }
744 +
745      /**
746       * Save the state to a stream (that is, serialize it).
747       *
# Line 704 | Line 752 | public class LinkedTransferQueue<E> exte
752      private void writeObject(java.io.ObjectOutputStream s)
753          throws java.io.IOException {
754          s.defaultWriteObject();
755 <        for (Iterator<E> it = iterator(); it.hasNext(); )
756 <            s.writeObject(it.next());
755 >        for (E e : this)
756 >            s.writeObject(e);
757          // Use trailing null as sentinel
758          s.writeObject(null);
759      }
# Line 730 | Line 778 | public class LinkedTransferQueue<E> exte
778  
779  
780      // Support for resetting head/tail while deserializing
781 +    private void resetHeadAndTail() {
782 +        QNode dummy = new QNode(null, false);
783 +        _unsafe.putObjectVolatile(this, headOffset,
784 +                                  new PaddedAtomicReference<QNode>(dummy));
785 +        _unsafe.putObjectVolatile(this, tailOffset,
786 +                                  new PaddedAtomicReference<QNode>(dummy));
787 +        _unsafe.putObjectVolatile(this, cleanMeOffset,
788 +                                  new PaddedAtomicReference<QNode>(null));
789 +    }
790  
791      // Temporary Unsafe mechanics for preliminary release
792 +    private static Unsafe getUnsafe() throws Throwable {
793 +        try {
794 +            return Unsafe.getUnsafe();
795 +        } catch (SecurityException se) {
796 +            try {
797 +                return java.security.AccessController.doPrivileged
798 +                    (new java.security.PrivilegedExceptionAction<Unsafe>() {
799 +                        public Unsafe run() throws Exception {
800 +                            return getUnsafePrivileged();
801 +                        }});
802 +            } catch (java.security.PrivilegedActionException e) {
803 +                throw e.getCause();
804 +            }
805 +        }
806 +    }
807 +
808 +    private static Unsafe getUnsafePrivileged()
809 +            throws NoSuchFieldException, IllegalAccessException {
810 +        Field f = Unsafe.class.getDeclaredField("theUnsafe");
811 +        f.setAccessible(true);
812 +        return (Unsafe) f.get(null);
813 +    }
814 +
815 +    private static long fieldOffset(String fieldName)
816 +            throws NoSuchFieldException {
817 +        return _unsafe.objectFieldOffset
818 +            (LinkedTransferQueue.class.getDeclaredField(fieldName));
819 +    }
820 +
821      private static final Unsafe _unsafe;
822      private static final long headOffset;
823      private static final long tailOffset;
824      private static final long cleanMeOffset;
825      static {
826          try {
827 <            if (LinkedTransferQueue.class.getClassLoader() != null) {
828 <                Field f = Unsafe.class.getDeclaredField("theUnsafe");
829 <                f.setAccessible(true);
830 <                _unsafe = (Unsafe)f.get(null);
831 <            }
746 <            else
747 <                _unsafe = Unsafe.getUnsafe();
748 <            headOffset = _unsafe.objectFieldOffset
749 <                (LinkedTransferQueue.class.getDeclaredField("head"));
750 <            tailOffset = _unsafe.objectFieldOffset
751 <                (LinkedTransferQueue.class.getDeclaredField("tail"));
752 <            cleanMeOffset = _unsafe.objectFieldOffset
753 <                (LinkedTransferQueue.class.getDeclaredField("cleanMe"));
754 <        } catch (Exception e) {
827 >            _unsafe = getUnsafe();
828 >            headOffset = fieldOffset("head");
829 >            tailOffset = fieldOffset("tail");
830 >            cleanMeOffset = fieldOffset("cleanMe");
831 >        } catch (Throwable e) {
832              throw new RuntimeException("Could not initialize intrinsics", e);
833          }
834      }
835  
759 –    private void resetHeadAndTail() {
760 –        QNode dummy = new QNode(null, false);
761 –        _unsafe.putObjectVolatile(this, headOffset,
762 –                                  new PaddedAtomicReference<QNode>(dummy));
763 –        _unsafe.putObjectVolatile(this, tailOffset,
764 –                                  new PaddedAtomicReference<QNode>(dummy));
765 –        _unsafe.putObjectVolatile(this, cleanMeOffset,
766 –                                  new PaddedAtomicReference<QNode>(null));
767 –
768 –    }
769 –
836   }

Diff Legend

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