[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.151, Mon Jan 16 22:26:01 2017 UTC revision 1.152, Tue Jan 17 02:44:59 2017 UTC
# Line 334  Line 334 
334       * from, the head of list.       * from, the head of list.
335       *       *
336       * Without taking these into account, it would be possible for an       * Without taking these into account, it would be possible for an
337       * unbounded number of supposedly removed nodes to remain       * unbounded number of supposedly removed nodes to remain reachable.
338       * reachable.  Situations leading to such buildup are uncommon but       * Situations leading to such buildup are uncommon but can occur in
339       * can occur in practice; for example when a series of short timed       * practice; for example when a series of short timed calls to poll
340       * calls to poll repeatedly time out but never otherwise fall off       * repeatedly time out but never otherwise fall off the list because
341       * the list because of an untimed call to take at the front of the       * of an untimed call to take() at the front of the queue.
      * queue.  
342       *       *
343       * When these cases arise, rather than always retraversing the       * When these cases arise, rather than always retraversing the
344       * entire list to find an actual predecessor to unlink (which       * entire list to find an actual predecessor to unlink (which
# Line 352  Line 351 
351       * We perform sweeps by the thread hitting threshold (rather than       * We perform sweeps by the thread hitting threshold (rather than
352       * background threads or by spreading work to other threads)       * background threads or by spreading work to other threads)
353       * because in the main contexts in which removal occurs, the       * because in the main contexts in which removal occurs, the
354       * caller is already timed-out, cancelled, or performing a       * caller is timed-out or cancelled, which are not time-critical
355       * potentially O(n) operation (e.g. remove(x)), none of which are       * enough to warrant the overhead that alternatives would impose
356       * time-critical enough to warrant the overhead that alternatives       * on other threads.
      * would impose on other threads.  
357       *       *
358       * Because the sweepVotes estimate is conservative, and because       * Because the sweepVotes estimate is conservative, and because
359       * nodes become unlinked "naturally" as they fall off the head of       * nodes become unlinked "naturally" as they fall off the head of
# Line 367  Line 365 
365       * quiescent queues. The value defined below was chosen       * quiescent queues. The value defined below was chosen
366       * empirically to balance these under various timeout scenarios.       * empirically to balance these under various timeout scenarios.
367       *       *
368         * Because traversal operations on the linked list of nodes are a
369         * natural opportunity to sweep dead nodes, we generally do so,
370         * including all the operations that might remove elements as they
371         * traverse, such as removeIf and Iterator.remove.  This largely
372         * eliminates long chains of dead interior nodes, except from
373         * cancelled or timed out blocking operations.
374         *
375       * Note that we cannot self-link unlinked interior nodes during       * Note that we cannot self-link unlinked interior nodes during
376       * sweeps. However, the associated garbage chains terminate when       * sweeps. However, the associated garbage chains terminate when
377       * some successor ultimately falls off the head of the list and is       * some successor ultimately falls off the head of the list and is
# Line 533  Line 538 
538       */       */
539      private transient volatile Node tail;      private transient volatile Node tail;
540    
541      /** The number of apparent failures to unsplice removed nodes */      /** The number of apparent failures to unsplice cancelled nodes */
542      private transient volatile int sweepVotes;      private transient volatile int sweepVotes;
543    
544      private boolean casTail(Node cmp, Node val) {      private boolean casTail(Node cmp, Node val) {
# Line 546  Line 551 
551          return HEAD.compareAndSet(this, cmp, val);          return HEAD.compareAndSet(this, cmp, val);
552      }      }
553    
554      private boolean casSweepVotes(int cmp, int val) {      /** Atomic version of ++sweepVotes. */
555          return SWEEPVOTES.compareAndSet(this, cmp, val);      private int incSweepVotes() {
556            return (int) SWEEPVOTES.getAndAdd(this, 1) + 1;
557      }      }
558    
559      /**      /**
# Line 1182  Line 1188 
1188          // assert pred != s;          // assert pred != s;
1189          // assert s != null;          // assert s != null;
1190          // assert s.isMatched();          // assert s.isMatched();
1191            // assert (SWEEP_THRESHOLD & (SWEEP_THRESHOLD - 1)) == 0;
1192          s.waiter = null; // disable signals          s.waiter = null; // disable signals
1193          /*          /*
1194           * See above for rationale. Briefly: if pred still points to           * See above for rationale. Briefly: if pred still points to
# Line 1206  Line 1213 
1213                      if (hn != h && casHead(h, hn))                      if (hn != h && casHead(h, hn))
1214                          h.selfLink();  // advance head                          h.selfLink();  // advance head
1215                  }                  }
1216                  if (pred.next != pred && s.next != s) { // recheck if offlist                  // sweep every SWEEP_THRESHOLD votes
1217                      for (;;) {           // sweep now if enough votes                  if (pred.next != pred && s.next != s // recheck if offlist
1218                          int v = sweepVotes;                      && (incSweepVotes() & (SWEEP_THRESHOLD - 1)) == 0)
                         if (v < SWEEP_THRESHOLD) {  
                             if (casSweepVotes(v, v + 1))  
                                 break;  
                         }  
                         else if (casSweepVotes(v, 0)) {  
1219                              sweep();                              sweep();
                             break;  
                         }  
                     }  
                 }  
1220              }              }
1221          }          }
1222      }      }

Legend:
Removed from v.1.151  
changed lines
  Added in v.1.152

Doug Lea
ViewVC Help
Powered by ViewVC 1.0.8