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

Comparing jsr166/src/jdk8/java/util/concurrent/LinkedTransferQueue.java (file contents):
Revision 1.2 by jsr166, Sat Nov 26 23:00:05 2016 UTC vs.
Revision 1.3 by jsr166, Tue Jan 3 04:44:37 2017 UTC

# Line 11 | Line 11 | import java.util.Arrays;
11   import java.util.Collection;
12   import java.util.Iterator;
13   import java.util.NoSuchElementException;
14 + import java.util.Objects;
15   import java.util.Queue;
16   import java.util.Spliterator;
17   import java.util.Spliterators;
# Line 549 | Line 550 | public class LinkedTransferQueue<E> exte
550          return U.compareAndSwapInt(this, SWEEPVOTES, cmp, val);
551      }
552  
553 +    /**
554 +     * Tries to CAS pred.next (or head, if pred is null) from c to p.
555 +     * Caller must ensure that we're not unlinking the trailing node.
556 +     */
557 +    private boolean tryCasSuccessor(Node pred, Node c, Node p) {
558 +        // assert p != null;
559 +        // assert c != p;
560 +        if (pred != null)
561 +            return pred.casNext(c, p);
562 +        if (casHead(c, p)) {
563 +            c.forgetNext();
564 +            return true;
565 +        }
566 +        return false;
567 +    }
568 +
569      /*
570       * Possible values for "how" argument in xfer method.
571       */
# Line 989 | Line 1006 | public class LinkedTransferQueue<E> exte
1006      }
1007  
1008      /** A customized variant of Spliterators.IteratorSpliterator */
1009 <    final class LTQSpliterator<E> implements Spliterator<E> {
1009 >    final class LTQSpliterator implements Spliterator<E> {
1010          static final int MAX_BATCH = 1 << 25;  // max batch array size;
1011          Node current;       // current node; null until initialized
1012          int batch;          // batch size for splits
# Line 997 | Line 1014 | public class LinkedTransferQueue<E> exte
1014          LTQSpliterator() {}
1015  
1016          public Spliterator<E> trySplit() {
1017 <            Node p;
1018 <            int b = batch;
1019 <            int n = (b <= 0) ? 1 : (b >= MAX_BATCH) ? MAX_BATCH : b + 1;
1020 <            if (!exhausted &&
1021 <                ((p = current) != null || (p = firstDataNode()) != null) &&
1022 <                p.next != null) {
1023 <                Object[] a = new Object[n];
1024 <                int i = 0;
1025 <                do {
1026 <                    Object e = p.item;
1027 <                    if (e != p && (a[i] = e) != null)
1028 <                        ++i;
1029 <                    if (p == (p = p.next))
1013 <                        p = firstDataNode();
1014 <                } while (p != null && i < n && p.isData);
1015 <                if ((current = p) == null)
1016 <                    exhausted = true;
1017 <                if (i > 0) {
1018 <                    batch = i;
1019 <                    return Spliterators.spliterator
1020 <                        (a, 0, i, (Spliterator.ORDERED |
1021 <                                   Spliterator.NONNULL |
1022 <                                   Spliterator.CONCURRENT));
1017 >            Node p, q;
1018 >            if ((p = current()) == null || (q = p.next) == null)
1019 >                return null;
1020 >            int i = 0, n = batch = Math.min(batch + 1, MAX_BATCH);
1021 >            Object[] a = null;
1022 >            do {
1023 >                final Object item = p.item;
1024 >                if (p.isData) {
1025 >                    if (item != null)
1026 >                        ((a != null) ? a : (a = new Object[n]))[i++] = item;
1027 >                } else if (item == null) {
1028 >                    p = null;
1029 >                    break;
1030                  }
1031 <            }
1032 <            return null;
1031 >                if (p == (p = q))
1032 >                    p = firstDataNode();
1033 >            } while (p != null && (q = p.next) != null && i < n);
1034 >            setCurrent(p);
1035 >            return (i == 0) ? null :
1036 >                Spliterators.spliterator(a, 0, i, (Spliterator.ORDERED |
1037 >                                                   Spliterator.NONNULL |
1038 >                                                   Spliterator.CONCURRENT));
1039          }
1040  
1028 –        @SuppressWarnings("unchecked")
1041          public void forEachRemaining(Consumer<? super E> action) {
1042 <            Node p;
1043 <            if (action == null) throw new NullPointerException();
1044 <            if (!exhausted &&
1045 <                ((p = current) != null || (p = firstDataNode()) != null)) {
1042 >            Objects.requireNonNull(action);
1043 >            final Node p;
1044 >            if ((p = current()) != null) {
1045 >                current = null;
1046                  exhausted = true;
1047 <                do {
1036 <                    Object e = p.item;
1037 <                    if (e != null && e != p)
1038 <                        action.accept((E)e);
1039 <                    if (p == (p = p.next))
1040 <                        p = firstDataNode();
1041 <                } while (p != null && p.isData);
1047 >                forEachFrom(action, p);
1048              }
1049          }
1050  
1051          @SuppressWarnings("unchecked")
1052          public boolean tryAdvance(Consumer<? super E> action) {
1053 +            Objects.requireNonNull(action);
1054              Node p;
1055 <            if (action == null) throw new NullPointerException();
1056 <            if (!exhausted &&
1050 <                ((p = current) != null || (p = firstDataNode()) != null)) {
1051 <                Object e;
1055 >            if ((p = current()) != null) {
1056 >                E e = null;
1057                  do {
1058 <                    if ((e = p.item) == p)
1059 <                        e = null;
1058 >                    final Object item = p.item;
1059 >                    final boolean isData = p.isData;
1060                      if (p == (p = p.next))
1061 <                        p = firstDataNode();
1062 <                } while (e == null && p != null && p.isData);
1063 <                if ((current = p) == null)
1064 <                    exhausted = true;
1061 >                        p = head;
1062 >                    if (isData) {
1063 >                        if (item != null) {
1064 >                            e = (E) item;
1065 >                            break;
1066 >                        }
1067 >                    }
1068 >                    else if (item == null)
1069 >                        p = null;
1070 >                } while (p != null);
1071 >                setCurrent(p);
1072                  if (e != null) {
1073 <                    action.accept((E)e);
1073 >                    action.accept(e);
1074                      return true;
1075                  }
1076              }
1077              return false;
1078          }
1079  
1080 +        private void setCurrent(Node p) {
1081 +            if ((current = p) == null)
1082 +                exhausted = true;
1083 +        }
1084 +
1085 +        private Node current() {
1086 +            Node p;
1087 +            if ((p = current) == null && !exhausted)
1088 +                setCurrent(p = firstDataNode());
1089 +            return p;
1090 +        }
1091 +
1092          public long estimateSize() { return Long.MAX_VALUE; }
1093  
1094          public int characteristics() {
1095 <            return Spliterator.ORDERED | Spliterator.NONNULL |
1096 <                Spliterator.CONCURRENT;
1095 >            return (Spliterator.ORDERED |
1096 >                    Spliterator.NONNULL |
1097 >                    Spliterator.CONCURRENT);
1098          }
1099      }
1100  
# Line 1090 | Line 1115 | public class LinkedTransferQueue<E> exte
1115       * @since 1.8
1116       */
1117      public Spliterator<E> spliterator() {
1118 <        return new LTQSpliterator<E>();
1118 >        return new LTQSpliterator();
1119      }
1120  
1121      /* -------------- Removal methods -------------- */
# Line 1533 | Line 1558 | public class LinkedTransferQueue<E> exte
1558          }
1559      }
1560  
1561 +    /**
1562 +     * Runs action on each element found during a traversal starting at p.
1563 +     * If p is null, the action is not run.
1564 +     */
1565 +    @SuppressWarnings("unchecked")
1566 +    void forEachFrom(Consumer<? super E> action, Node p) {
1567 +        for (Node c = p, pred = null; p != null; ) {
1568 +            final Object item; final boolean pAlive;
1569 +            if (pAlive = ((item = p.item) != null && p.isData))
1570 +                action.accept((E) item);
1571 +            else if (!p.isData && item == null)
1572 +                break;
1573 +            if ((c != p && !tryCasSuccessor(pred, c, c = p)) || pAlive) {
1574 +                pred = p;
1575 +                c = p = p.next;
1576 +            }
1577 +            else if (p == (p = p.next)) {
1578 +                pred = null;
1579 +                c = p = head;
1580 +            }
1581 +        }
1582 +    }
1583 +
1584 +    /**
1585 +     * @throws NullPointerException {@inheritDoc}
1586 +     */
1587 +    public void forEach(Consumer<? super E> action) {
1588 +        Objects.requireNonNull(action);
1589 +        forEachFrom(action, head);
1590 +    }
1591 +
1592      // Unsafe mechanics
1593  
1594      private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe();

Diff Legend

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