[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.141, Sat Jan 14 21:14:47 2017 UTC revision 1.142, Sat Jan 14 23:28:10 2017 UTC
# Line 407  Line 407 
407    
408      /**      /**
409       * Queue nodes. Uses Object, not E, for items to allow forgetting       * Queue nodes. Uses Object, not E, for items to allow forgetting
410       * them after use.  Relies heavily on VarHandles to minimize       * them after use.  Writes that are intrinsically ordered wrt
411       * unnecessary ordering constraints: Writes that are intrinsically       * other accesses or CASes use simple relaxed forms.
      * ordered wrt other accesses or CASes use simple relaxed forms.  
412       */       */
413      static final class Node {      static final class Node {
414          final boolean isData;   // false if this is a request node          final boolean isData;   // false if this is a request node
415          volatile Object item;   // initially non-null if isData; CASed to match          volatile Object item;   // initially non-null if isData; CASed to match
416          volatile Node next;          volatile Node next;
417          volatile Thread waiter; // null until waiting          volatile Thread waiter; // null when not waiting for a match
   
         final boolean casNext(Node cmp, Node val) {  
             return NEXT.compareAndSet(this, cmp, val);  
         }  
   
         final boolean casItem(Object cmp, Object val) {  
             // assert isData == (cmp != null);  
             // assert isData == (val == null);  
             // assert !(cmp instanceof Node);  
             return ITEM.compareAndSet(this, cmp, val);  
         }  
418    
419          /**          /**
420           * Constructs a data node holding item if item is non-null,           * Constructs a data node holding item if item is non-null,
# Line 438  Line 426 
426              isData = (item != null);              isData = (item != null);
427          }          }
428    
429          /** Constructs a dead (matched data) dummy node. */          /** Constructs a (matched data) dummy node. */
430          Node() {          Node() {
431              isData = true;              isData = true;
432          }          }
433    
434            final boolean casNext(Node cmp, Node val) {
435                // assert val != null;
436                return NEXT.compareAndSet(this, cmp, val);
437            }
438    
439            final boolean casItem(Object cmp, Object val) {
440                // assert isData == (cmp != null);
441                // assert isData == (val == null);
442                // assert !(cmp instanceof Node);
443                return ITEM.compareAndSet(this, cmp, val);
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.
449           */           */
450          final void forgetNext() {          final void selfLink() {
451                // assert isMatched();
452              NEXT.setRelease(this, this);              NEXT.setRelease(this, this);
453          }          }
454    
# Line 482  Line 483 
483              return isData == (item == null);              return isData == (item == null);
484          }          }
485    
486            /** Tries to CAS-match this node; if successful, wakes waiter. */
487            final boolean tryMatch(Object cmp, Object val) {
488                if (casItem(cmp, val)) {
489                    LockSupport.unpark(waiter);
490                    return true;
491                }
492                return false;
493            }
494    
495          /**          /**
496           * Returns true if a node with the given mode cannot be           * Returns true if a node with the given mode cannot be
497           * appended to this node because this node is unmatched and           * appended to this node because this node is unmatched and
# Line 492  Line 502 
502              return d != haveData && d != (item == null);              return d != haveData && d != (item == null);
503          }          }
504    
         /**  
          * Tries to artificially match a data node -- used by remove.  
          */  
         final boolean tryMatchData() {  
             // assert isData;  
             final Object x;  
             if ((x = item) != null && casItem(x, null)) {  
                 LockSupport.unpark(waiter);  
                 return true;  
             }  
             return false;  
         }  
   
505          private static final long serialVersionUID = -3375979862319811754L;          private static final long serialVersionUID = -3375979862319811754L;
506      }      }
507    
# Line 564  Line 561 
561          if (pred != null)          if (pred != null)
562              return pred.casNext(c, p);              return pred.casNext(c, p);
563          if (casHead(c, p)) {          if (casHead(c, p)) {
564              c.forgetNext();              c.selfLink();
565              return true;              return true;
566          }          }
567          return false;          return false;
# Line 623  Line 620 
620                      // unmatched                      // unmatched
621                      if (isData == haveData)   // can't match                      if (isData == haveData)   // can't match
622                          break;                          break;
623                      if (p.casItem(item, e)) { // match                      if (p.tryMatch(item, e)) {
624                          for (Node q = p; q != h;) {                          for (Node q = p; q != h;) {
625                              Node n = q.next;  // update by 2 unless singleton                              Node n = q.next;  // update by 2 unless singleton
626                              if (head == h && casHead(h, n == null ? q : n)) {                              if (head == h && casHead(h, n == null ? q : n)) {
627                                  h.forgetNext();                                  h.selfLink();
628                                  break;                                  break;
629                              }                 // advance and retry                              }                 // advance and retry
630                              if ((h = head)   == null ||                              if ((h = head)   == null ||
631                                  (q = h.next) == null || !q.isMatched())                                  (q = h.next) == null || !q.isMatched())
632                                  break;        // unless slack < 2                                  break;        // unless slack < 2
633                          }                          }
                         LockSupport.unpark(p.waiter);  
634                          @SuppressWarnings("unchecked") E itemE = (E) item;                          @SuppressWarnings("unchecked") E itemE = (E) item;
635                          return itemE;                          return itemE;
636                      }                      }
# Line 792  Line 788 
788                      continue restartFromHead;                      continue restartFromHead;
789              }              }
790              if (p != h && casHead(h, p))              if (p != h && casHead(h, p))
791                  h.forgetNext();                  h.selfLink();
792              return first;              return first;
793          }          }
794      }      }
# Line 1017  Line 1013 
1013              for (Node p = (pred == null) ? head : pred.next, c = p, q;              for (Node p = (pred == null) ? head : pred.next, c = p, q;
1014                   p != null; ) {                   p != null; ) {
1015                  if (p == lastRet) {                  if (p == lastRet) {
1016                      p.tryMatchData();                      final Object item;
1017                        if ((item = p.item) != null)
1018                            p.tryMatch(item, null);
1019                      if ((q = p.next) == null) q = p;                      if ((q = p.next) == null) q = p;
1020                      if (c != q) tryCasSuccessor(pred, c, q);                      if (c != q) tryCasSuccessor(pred, c, q);
1021                      ancestor = pred;                      ancestor = pred;
# Line 1192  Line 1190 
1190                      if (hn == null)                      if (hn == null)
1191                          return;          // now empty                          return;          // now empty
1192                      if (hn != h && casHead(h, hn))                      if (hn != h && casHead(h, hn))
1193                          h.forgetNext();  // advance head                          h.selfLink();  // advance head
1194                  }                  }
1195                  if (pred.next != pred && s.next != s) { // recheck if offlist                  if (pred.next != pred && s.next != s) { // recheck if offlist
1196                      for (;;) {           // sweep now if enough votes                      for (;;) {           // sweep now if enough votes
# Line 1510  Line 1508 
1508                  final Object item;                  final Object item;
1509                  if ((item = p.item) != null) {                  if ((item = p.item) != null) {
1510                      if (p.isData) {                      if (p.isData) {
1511                          if (o.equals(item) && p.tryMatchData()) {                          if (o.equals(item) && p.tryMatch(item, null)) {
1512                              skipDeadNodes(pred, p, p, q);                              skipDeadNodes(pred, p, p, q);
1513                              return true;                              return true;
1514                          }                          }
# Line 1666  Line 1664 
1664                  final Object item; boolean pAlive;                  final Object item; boolean pAlive;
1665                  if (pAlive = ((item = p.item) != null && p.isData)) {                  if (pAlive = ((item = p.item) != null && p.isData)) {
1666                      if (filter.test((E) item)) {                      if (filter.test((E) item)) {
1667                          if (p.tryMatchData())                          if (p.tryMatch(item, null))
1668                              removed = true;                              removed = true;
1669                          pAlive = false;                          pAlive = false;
1670                      }                      }

Legend:
Removed from v.1.141  
changed lines
  Added in v.1.142

Doug Lea
ViewVC Help
Powered by ViewVC 1.0.8