[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.133, Mon Jan 2 00:10:14 2017 UTC revision 1.134, Mon Jan 2 04:41:13 2017 UTC
# Line 895  Line 895 
895          return (T[]) toArrayInternal(a);          return (T[]) toArrayInternal(a);
896      }      }
897    
898        /**
899         * Weakly-consistent iterator.
900         *
901         * Lazily updated ancestor is expected to be amortized O(1) remove(),
902         * but O(n) in the worst case, when lastRet is concurrently deleted.
903         */
904      final class Itr implements Iterator<E> {      final class Itr implements Iterator<E> {
905          private Node nextNode;   // next node to return item for          private Node nextNode;   // next node to return item for
906          private E nextItem;      // the corresponding item          private E nextItem;      // the corresponding item
907          private Node lastRet;    // last returned node, to support remove          private Node lastRet;    // last returned node, to support remove
908          private Node lastPred;   // predecessor to unlink lastRet          private Node ancestor;   // Helps unlink lastRet on remove()
909    
910          /**          /**
911           * Moves to next node after prev, or first node if prev null.           * Moves to next node after pred, or first node if pred null.
912           */           */
913          private void advance(Node prev) {          @SuppressWarnings("unchecked")
914              /*          private void advance(Node pred) {
915               * To track and avoid buildup of deleted nodes in the face              for (Node p = (pred == null) ? head : pred.next, c = p;
916               * of calls to both Queue.remove and Itr.remove, we must                   p != null; ) {
917               * include variants of unsplice and sweep upon each                  final Object item;
918               * advance: Upon Itr.remove, we may need to catch up links                  if ((item = p.item) != null && p.isData) {
919               * from lastPred, and upon other removes, we might need to                      nextNode = p;
920               * skip ahead from stale nodes and unsplice deleted ones                      nextItem = (E) item;
921               * found while advancing.                      if (c != p)
922               */                          tryCasSuccessor(pred, c, p);
   
             Node r, b; // reset lastPred upon possible deletion of lastRet  
             if ((r = lastRet) != null && !r.isMatched())  
                 lastPred = r;    // next lastPred is old lastRet  
             else if ((b = lastPred) == null || b.isMatched())  
                 lastPred = null; // at start of list  
             else {  
                 Node s, n;       // help with removal of lastPred.next  
                 while ((s = b.next) != null &&  
                        s != b && s.isMatched() &&  
                        (n = s.next) != null && n != s)  
                     b.casNext(s, n);  
             }  
   
             this.lastRet = prev;  
   
             for (Node p = prev, s, n;;) {  
                 s = (p == null) ? head : p.next;  
                 if (s == null)  
                     break;  
                 else if (s == p) {  
                     p = null;  
                     continue;  
                 }  
                 Object item = s.item;  
                 if (s.isData) {  
                     if (item != null) {  
                         @SuppressWarnings("unchecked") E itemE = (E) item;  
                         nextItem = itemE;  
                         nextNode = s;  
923                          return;                          return;
924                      }                      }
925                  }                  else if (!p.isData && item == null)
                 else if (item == null)  
                     break;  
                 // assert s.isMatched();  
                 if (p == null)  
                     p = s;  
                 else if ((n = s.next) == null)  
926                      break;                      break;
927                  else if (s == n)                  if (c != p && !tryCasSuccessor(pred, c, c = p)) {
928                      p = null;                      pred = p;
929                  else                      c = p = p.next;
930                      p.casNext(s, n);                  }
931                    else if (p == (p = p.next)) {
932                        pred = null;
933                        c = p = head;
934                    }
935              }              }
             nextNode = null;  
936              nextItem = null;              nextItem = null;
937                nextNode = null;
938          }          }
939    
940          Itr() {          Itr() {
# Line 975  Line 949 
949              final Node p;              final Node p;
950              if ((p = nextNode) == null) throw new NoSuchElementException();              if ((p = nextNode) == null) throw new NoSuchElementException();
951              E e = nextItem;              E e = nextItem;
952              advance(p);              advance(lastRet = p);
953              return e;              return e;
954          }          }
955    
956          // Default implementation of forEachRemaining is "good enough".          public void forEachRemaining(Consumer<? super E> action) {
957                Objects.requireNonNull(action);
958                Node q = null;
959                for (Node p; (p = nextNode) != null; advance(q = p))
960                    action.accept(nextItem);
961                if (q != null)
962                    lastRet = q;
963            }
964    
965          public final void remove() {          public final void remove() {
966              final Node lastRet = this.lastRet;              final Node lastRet = this.lastRet;
967              if (lastRet == null)              if (lastRet == null)
968                  throw new IllegalStateException();                  throw new IllegalStateException();
969              this.lastRet = null;              this.lastRet = null;
970              if (lastRet.tryMatchData())              if (lastRet.item == null)   // already deleted?
971                  unsplice(lastPred, lastRet);                  return;
972                // Advance ancestor, collapsing intervening dead nodes
973                Node pred = ancestor;
974                for (Node p = (pred == null) ? head : pred.next, c = p, q;
975                     p != null; ) {
976                    if (p == lastRet) {
977                        p.tryMatchData();
978                        if ((q = p.next) == null) q = p;
979                        if (c != q) tryCasSuccessor(pred, c, q);
980                        ancestor = pred;
981                        return;
982                    }
983                    final Object item; final boolean pAlive;
984                    if (pAlive = ((item = p.item) != null && p.isData)) {
985                        // exceptionally, nothing to do
986                    }
987                    else if (!p.isData && item == null)
988                        break;
989                    if ((c != p && !tryCasSuccessor(pred, c, c = p)) || pAlive) {
990                        pred = p;
991                        c = p = p.next;
992                    }
993                    else if (p == (p = p.next)) {
994                        pred = null;
995                        c = p = head;
996                    }
997                }
998                // traversal failed to find lastRet; must have been deleted;
999                // leave ancestor at original location to avoid overshoot;
1000                // better luck next time!
1001    
1002                // assert lastRet.isMatched();
1003          }          }
1004      }      }
1005    
# Line 1451  Line 1463 
1463                  }                  }
1464                  else if (!p.isData && item == null)                  else if (!p.isData && item == null)
1465                      break;                      break;
1466                  if (c != p && tryCasSuccessor(pred, c, p))                  if ((c != p && !tryCasSuccessor(pred, c, c = p)) || pAlive) {
                     c = p;  
                 q = p.next;  
                 if (pAlive || c != p) {  
1467                      pred = p;                      pred = p;
1468                      p = c = q;                      c = p = p.next;
1469                  }                  }
1470                  else if (p == (p = q))                  else if (p == (p = p.next))
1471                      continue restartFromHead;                      continue restartFromHead;
1472              }              }
1473              return false;              return false;
# Line 1477  Line 1486 
1486          if (o == null)          if (o == null)
1487              return false;              return false;
1488          restartFromHead: for (;;) {          restartFromHead: for (;;) {
1489              for (Node p = head, c = p, pred = null, q; p != null; ) {              for (Node p = head, c = p, pred = null; p != null; ) {
1490                  final Object item; final boolean pAlive;                  final Object item; final boolean pAlive;
1491                  if (pAlive = ((item = p.item) != null && p.isData)) {                  if (pAlive = ((item = p.item) != null && p.isData)) {
1492                      if (o.equals(item))                      if (o.equals(item))
# Line 1485  Line 1494 
1494                  }                  }
1495                  else if (!p.isData && item == null)                  else if (!p.isData && item == null)
1496                      break;                      break;
1497                  if (c != p && tryCasSuccessor(pred, c, p))                  if ((c != p && !tryCasSuccessor(pred, c, c = p)) || pAlive) {
                     c = p;  
                 q = p.next;  
                 if (pAlive || c != p) {  
1498                      pred = p;                      pred = p;
1499                      p = c = q;                      c = p = p.next;
1500                  }                  }
1501                  else if (p == (p = q))                  else if (p == (p = p.next))
1502                      continue restartFromHead;                      continue restartFromHead;
1503              }              }
1504              return false;              return false;
# Line 1605  Line 1611 
1611                      // p might already be self-linked here, but if so:                      // p might already be self-linked here, but if so:
1612                      // - CASing head will surely fail                      // - CASing head will surely fail
1613                      // - CASing pred's next will be useless but harmless.                      // - CASing pred's next will be useless but harmless.
1614                      if (c != p && tryCasSuccessor(pred, c, p))                      if ((c != p && !tryCasSuccessor(pred, c, c = p))
1615                          c = p;                          || pAlive) {
1616                      // if c != p, CAS failed, so abandon old pred                          // if CAS failed or alive, abandon old pred
                     if (pAlive || c != p) {  
1617                          hops = MAX_HOPS;                          hops = MAX_HOPS;
1618                          pred = p;                          pred = p;
1619                          c = q;                          c = q;
# Line 1626  Line 1631 
1631       */       */
1632      @SuppressWarnings("unchecked")      @SuppressWarnings("unchecked")
1633      void forEachFrom(Consumer<? super E> action, Node p) {      void forEachFrom(Consumer<? super E> action, Node p) {
1634          for (Node c = p, pred = null, q; p != null; ) {          for (Node c = p, pred = null; p != null; ) {
1635              final Object item; final boolean pAlive;              final Object item; final boolean pAlive;
1636              if (pAlive = ((item = p.item) != null && p.isData))              if (pAlive = ((item = p.item) != null && p.isData))
1637                  action.accept((E) item);                  action.accept((E) item);
1638              else if (!p.isData && item == null)              else if (!p.isData && item == null)
1639                  break;                  break;
1640              if (c != p && tryCasSuccessor(pred, c, p))              if ((c != p && !tryCasSuccessor(pred, c, c = p)) || pAlive) {
                 c = p;  
             q = p.next;  
             if (pAlive || c != p) {  
1641                  pred = p;                  pred = p;
1642                  p = c = q;                  c = p = p.next;
1643              }              }
1644              else if (p == (p = q)) {              else if (p == (p = p.next)) {
1645                  pred = null;                  pred = null;
1646                  c = p = head;                  c = p = head;
1647              }              }

Legend:
Removed from v.1.133  
changed lines
  Added in v.1.134

Doug Lea
ViewVC Help
Powered by ViewVC 1.0.8