[cvs] / jsr166 / src / main / java / util / concurrent / LinkedTransferQueue.java Repository:
ViewVC logotype

Diff of /jsr166/src/main/java/util/concurrent/LinkedTransferQueue.java

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 1.139, Mon Jan 9 17:46:26 2017 UTC revision 1.140, Sat Jan 14 06:59:57 2017 UTC
# Line 130  Line 130 
130       * correctly perform enqueue and dequeue operations by traversing       * correctly perform enqueue and dequeue operations by traversing
131       * from a pointer to the initial node; CASing the item of the       * from a pointer to the initial node; CASing the item of the
132       * first unmatched node on match and CASing the next field of the       * first unmatched node on match and CASing the next field of the
133       * trailing node on appends. (Plus some special-casing when       * trailing node on appends.  While this would be a terrible idea
134       * initially empty).  While this would be a terrible idea in       * in itself, it does have the benefit of not requiring ANY atomic
      * itself, it does have the benefit of not requiring ANY atomic  
135       * updates on head/tail fields.       * updates on head/tail fields.
136       *       *
137       * We introduce here an approach that lies between the extremes of       * We introduce here an approach that lies between the extremes of
# Line 238  Line 237 
237       * interior nodes) except in the case of cancellation/removal (see       * interior nodes) except in the case of cancellation/removal (see
238       * below).       * below).
239       *       *
      * We allow both the head and tail fields to be null before any  
      * nodes are enqueued; initializing upon first append.  This  
      * simplifies some other logic, as well as providing more  
      * efficient explicit control paths instead of letting JVMs insert  
      * implicit NullPointerExceptions when they are null.  While not  
      * currently fully implemented, we also leave open the possibility  
      * of re-nulling these fields when empty (which is complicated to  
      * arrange, for little benefit.)  
      *  
240       * All enqueue/dequeue operations are handled by the single method       * All enqueue/dequeue operations are handled by the single method
241       * "xfer" with parameters indicating whether to act as some form       * "xfer" with parameters indicating whether to act as some form
242       * of offer, put, poll, take, or transfer (each possibly with       * of offer, put, poll, take, or transfer (each possibly with
# Line 278  Line 268 
268       * 2. Try to append a new node (method tryAppend)       * 2. Try to append a new node (method tryAppend)
269       *       *
270       *    Starting at current tail pointer, find the actual last node       *    Starting at current tail pointer, find the actual last node
271       *    and try to append a new node (or if head was null, establish       *    and try to append a new node. Nodes can be appended only if
272       *    the first node). Nodes can be appended only if their       *    their predecessors are either already matched or are of the
273       *    predecessors are either already matched or are of the same       *    same mode. If we detect otherwise, then a new node with
274       *    mode. If we detect otherwise, then a new node with opposite       *    opposite mode must have been appended during traversal, so
275       *    mode must have been appended during traversal, so we must       *    we must restart at phase 1. The traversal and update steps
276       *    restart at phase 1. The traversal and update steps are       *    are otherwise similar to phase 1: Retrying upon CAS misses
277       *    otherwise similar to phase 1: Retrying upon CAS misses and       *    and checking for staleness.  In particular, if a self-link
278       *    checking for staleness.  In particular, if a self-link is       *    is encountered, then we can safely jump to a node on the
279       *    encountered, then we can safely jump to a node on the list       *    list by continuing the traversal at current head.
      *    by continuing the traversal at current head.  
280       *       *
281       *    On successful append, if the call was ASYNC, return.       *    On successful append, if the call was ASYNC, return.
282       *       *
# Line 440  Line 429 
429          }          }
430    
431          /**          /**
432           * Constructs a new node.  Uses relaxed write because item can           * Constructs a data node holding item if item is non-null,
433           * only be seen after publication via casNext.           * else a request node.  Uses relaxed write because item can
434             * only be seen after piggy-backing publication via CAS.
435           */           */
436          Node(Object item) {          Node(Object item) {
437              ITEM.set(this, item);              ITEM.set(this, item);
438              isData = (item != null);              isData = (item != null);
439          }          }
440    
441            /** Constructs a dead (matched data) dummy node. */
442            Node() {
443                isData = true;
444            }
445    
446          /**          /**
447           * Links node to itself to avoid garbage retention.  Called           * Links node to itself to avoid garbage retention.  Called
448           * only after CASing head field, so uses relaxed write.           * only after CASing head field, so uses relaxed write.
# Line 456  Line 451 
451              NEXT.setRelease(this, this);              NEXT.setRelease(this, this);
452          }          }
453    
454            final void appendRelaxed(Node next) {
455                // assert next != null;
456                // assert this.next == null;
457                NEXT.set(this, next);
458            }
459    
460          /**          /**
461           * Sets item (of a request node) to self and waiter to null,           * Sets item (of a request node) to self and waiter to null,
462           * to avoid garbage retention after matching or cancelling.           * to avoid garbage retention after matching or cancelling.
# Line 505  Line 506 
506          }          }
507    
508          private static final long serialVersionUID = -3375979862319811754L;          private static final long serialVersionUID = -3375979862319811754L;
   
         // VarHandle mechanics  
         private static final VarHandle ITEM;  
         private static final VarHandle NEXT;  
         private static final VarHandle WAITER;  
         static {  
             try {  
                 MethodHandles.Lookup l = MethodHandles.lookup();  
                 ITEM = l.findVarHandle(Node.class, "item", Object.class);  
                 NEXT = l.findVarHandle(Node.class, "next", Node.class);  
                 WAITER = l.findVarHandle(Node.class, "waiter", Thread.class);  
             } catch (ReflectiveOperationException e) {  
                 throw new Error(e);  
             }  
         }  
509      }      }
510    
511      /** head of the queue; null until first enqueue */      /**
512         * A node from which the first live (non-matched) node (if any)
513         * can be reached in O(1) time.
514         * Invariants:
515         * - all live nodes are reachable from head via .next
516         * - head != null
517         * - (tmp = head).next != tmp || tmp != head
518         * Non-invariants:
519         * - head may or may not be live
520         * - it is permitted for tail to lag behind head, that is, for tail
521         *   to not be reachable from head!
522         */
523      transient volatile Node head;      transient volatile Node head;
524    
525      /** tail of the queue; null until first append */      /**
526         * A node from which the last node on list (that is, the unique
527         * node with node.next == null) can be reached in O(1) time.
528         * Invariants:
529         * - the last node is always reachable from tail via .next
530         * - tail != null
531         * Non-invariants:
532         * - tail may or may not be live
533         * - it is permitted for tail to lag behind head, that is, for tail
534         *   to not be reachable from head!
535         * - tail.next may or may not be self-linked.
536         */
537      private transient volatile Node tail;      private transient volatile Node tail;
538    
539      /** The number of apparent failures to unsplice removed nodes */      /** The number of apparent failures to unsplice removed nodes */
540      private transient volatile int sweepVotes;      private transient volatile int sweepVotes;
541    
542      private boolean casTail(Node cmp, Node val) {      private boolean casTail(Node cmp, Node val) {
543            // assert cmp != null;
544            // assert val != null;
545          return TAIL.compareAndSet(this, cmp, val);          return TAIL.compareAndSet(this, cmp, val);
546      }      }
547    
# Line 655  Line 665 
665       * predecessor       * predecessor
666       */       */
667      private Node tryAppend(Node s, boolean haveData) {      private Node tryAppend(Node s, boolean haveData) {
668            // assert head != null;
669            // assert tail != null;
670          for (Node t = tail, p = t;;) {        // move p to last node and append          for (Node t = tail, p = t;;) {        // move p to last node and append
671              Node n, u;                        // temps for reads of next & tail              Node n, u;                        // temps for reads of next & tail
672              if (p == null && (p = head) == null) {              if (p == null)
673                  if (casHead(null, s))                  p = head;
                     return s;                 // initialize  
             }  
674              else if (p.cannotPrecede(haveData))              else if (p.cannotPrecede(haveData))
675                  return null;                  // lost race vs opposite mode                  return null;                  // lost race vs opposite mode
676              else if ((n = p.next) != null)    // not last; keep traversing              else if ((n = p.next) != null)    // not last; keep traversing
# Line 1223  Line 1233 
1233       * Creates an initially empty {@code LinkedTransferQueue}.       * Creates an initially empty {@code LinkedTransferQueue}.
1234       */       */
1235      public LinkedTransferQueue() {      public LinkedTransferQueue() {
1236            head = tail = new Node();
1237      }      }
1238    
1239      /**      /**
# Line 1235  Line 1246 
1246       *         of its elements are null       *         of its elements are null
1247       */       */
1248      public LinkedTransferQueue(Collection<? extends E> c) {      public LinkedTransferQueue(Collection<? extends E> c) {
1249          this();          Node h = null, t = null;
1250          addAll(c);          for (E e : c) {
1251                Node newNode = new Node(Objects.requireNonNull(e));
1252                if (h == null)
1253                    h = t = newNode;
1254                else
1255                    t.appendRelaxed(t = newNode);
1256            }
1257            if (h == null)
1258                h = t = new Node();
1259            head = h;
1260            tail = t;
1261      }      }
1262    
1263      /**      /**
# Line 1580  Line 1601 
1601       */       */
1602      private void readObject(java.io.ObjectInputStream s)      private void readObject(java.io.ObjectInputStream s)
1603          throws java.io.IOException, ClassNotFoundException {          throws java.io.IOException, ClassNotFoundException {
1604          s.defaultReadObject();  
1605          for (;;) {          // Read in elements until trailing null sentinel found
1606            Node h = null, t = null;
1607            for (Object item; (item = s.readObject()) != null; ) {
1608              @SuppressWarnings("unchecked")              @SuppressWarnings("unchecked")
1609              E item = (E) s.readObject();              Node newNode = new Node((E) item);
1610              if (item == null)              if (h == null)
1611                  break;                  h = t = newNode;
1612              else              else
1613                  offer(item);                  t.appendRelaxed(t = newNode);
1614          }          }
1615            if (h == null)
1616                h = t = new Node();
1617            head = h;
1618            tail = t;
1619      }      }
1620    
1621      /**      /**
# Line 1701  Line 1728 
1728      private static final VarHandle HEAD;      private static final VarHandle HEAD;
1729      private static final VarHandle TAIL;      private static final VarHandle TAIL;
1730      private static final VarHandle SWEEPVOTES;      private static final VarHandle SWEEPVOTES;
1731        static final VarHandle ITEM;
1732        static final VarHandle NEXT;
1733        static final VarHandle WAITER;
1734      static {      static {
1735          try {          try {
1736              MethodHandles.Lookup l = MethodHandles.lookup();              MethodHandles.Lookup l = MethodHandles.lookup();
# Line 1710  Line 1740 
1740                                     Node.class);                                     Node.class);
1741              SWEEPVOTES = l.findVarHandle(LinkedTransferQueue.class, "sweepVotes",              SWEEPVOTES = l.findVarHandle(LinkedTransferQueue.class, "sweepVotes",
1742                                           int.class);                                           int.class);
1743                ITEM = l.findVarHandle(Node.class, "item", Object.class);
1744                NEXT = l.findVarHandle(Node.class, "next", Node.class);
1745                WAITER = l.findVarHandle(Node.class, "waiter", Thread.class);
1746          } catch (ReflectiveOperationException e) {          } catch (ReflectiveOperationException e) {
1747              throw new Error(e);              throw new Error(e);
1748          }          }

Legend:
Removed from v.1.139  
changed lines
  Added in v.1.140

Doug Lea
ViewVC Help
Powered by ViewVC 1.0.8