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

Comparing jsr166/src/main/java/util/concurrent/LinkedTransferQueue.java (file contents):
Revision 1.151 by jsr166, Mon Jan 16 22:26:01 2017 UTC vs.
Revision 1.152 by jsr166, Tue Jan 17 02:44:59 2017 UTC

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

Diff Legend

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