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

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

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

revision 1.58, Thu Aug 18 20:44:14 2005 UTC revision 1.59, Thu Aug 18 21:37:58 2005 UTC
# Line 93  Line 93 
93       * in extending them for use in synchronous queues, as well as       * in extending them for use in synchronous queues, as well as
94       * dealing with cancellation. The main differences include:       * dealing with cancellation. The main differences include:
95       *       *
96       *  1. The orginal algorithms used bit-marked pointers, but       *  1. The original algorithms used bit-marked pointers, but
97       *     the ones here use mode bits in nodes, leading to a number       *     the ones here use mode bits in nodes, leading to a number
98       *     of further adaptations.       *     of further adaptations.
99       *  2. SynchronousQueues must block threads waiting to become       *  2. SynchronousQueues must block threads waiting to become
# Line 120  Line 120 
120       *       *
121       * While garbage collection takes care of most node reclamation       * While garbage collection takes care of most node reclamation
122       * issues that otherwise complicate nonblocking algorithms, care       * issues that otherwise complicate nonblocking algorithms, care
123       * is made to "forget" references to data, other nodes, and       * is taken to "forget" references to data, other nodes, and
124       * threads that might be held on to long-term by blocked       * threads that might be held on to long-term by blocked
125       * threads. In cases where setting to null would otherwise       * threads. In cases where setting to null would otherwise
126       * conflict with main algorithms, this is done by changing a       * conflict with main algorithms, this is done by changing a
127       * node's link to now point to the node itself. This doesn't arise       * node's link to now point to the node itself. This doesn't arise
128       * much for Stack nodes (because blocked threads do not hang on to       * much for Stack nodes (because blocked threads do not hang on to
129       * old head pointers), but references in Queue nodes must be       * old head pointers), but references in Queue nodes must be
130       * agressively forgotten to avoid reachability of everything any       * aggressively forgotten to avoid reachability of everything any
131       * node has ever referred to since arrival.       * node has ever referred to since arrival.
132       */       */
133    
# Line 136  Line 136 
136       */       */
137      static abstract class Transferer {      static abstract class Transferer {
138          /**          /**
139           * Perform a put or take.           * Performs a put or take.
140             *
141           * @param e if non-null, the item to be handed to a consumer;           * @param e if non-null, the item to be handed to a consumer;
142           * if null, requests that transfer return an item offered by           *          if null, requests that transfer return an item
143           * producer.           *          offered by producer.
144           * @param timed if this operation should timeout           * @param timed if this operation should timeout
145           * @param nanos the timeout, in nanoseconds           * @param nanos the timeout, in nanoseconds
146           * @return if nonnull, the item provided or received; if null,           * @return if non-null, the item provided or received; if null,
147           * the operation failed due to timeout or interrupt -- the           *         the operation failed due to timeout or interrupt --
148           * caller can distinguish which of these occurred by checking           *         the caller can distinguish which of these occurred
149           * Thread.interrupted.           *         by checking Thread.interrupted.
150           */           */
151          abstract Object transfer(Object e, boolean timed, long nanos);          abstract Object transfer(Object e, boolean timed, long nanos);
152      }      }
# Line 226  Line 227 
227                  (SNode.class, SNode.class, "match");                  (SNode.class, SNode.class, "match");
228    
229              /**              /**
230               * Try to match node s to this node, if so, waking up               * Tries to match node s to this node, if so, waking up
231               * thread. Fulfillers call tryMatch to identify their               * thread. Fulfillers call tryMatch to identify their
232               * waiters. Waiters block until they have been               * waiters. Waiters block until they have been
233               * matched.               * matched.
# Line 247  Line 248 
248              }              }
249    
250              /**              /**
251               * Try to cancel a wait by matching node to itself.               * Tries to cancel a wait by matching node to itself.
252               */               */
253              void tryCancel() {              void tryCancel() {
254                  matchUpdater.compareAndSet(this, null, this);                  matchUpdater.compareAndSet(this, null, this);
# Line 375  Line 376 
376               * When a node/thread is about to block, it sets its waiter               * When a node/thread is about to block, it sets its waiter
377               * field and then rechecks state at least one more time               * field and then rechecks state at least one more time
378               * before actually parking, thus covering race vs               * before actually parking, thus covering race vs
379               * fulfiller noticing that waiter is nonnull so should be               * fulfiller noticing that waiter is non-null so should be
380               * woken.               * woken.
381               *               *
382               * When invoked by nodes that appear at the point of call               * When invoked by nodes that appear at the point of call
# Line 447  Line 448 
448               * it. But we can stop when we see any node known to               * it. But we can stop when we see any node known to
449               * follow s. We use s.next unless it too is cancelled, in               * follow s. We use s.next unless it too is cancelled, in
450               * which case we try the node one past. We don't check any               * which case we try the node one past. We don't check any
451               * futher because we don't want to doubly traverse just to               * further because we don't want to doubly traverse just to
452               * find sentinel.               * find sentinel.
453               */               */
454    
# Line 479  Line 480 
480           * marked pointers. The algorithm is a little simpler than           * marked pointers. The algorithm is a little simpler than
481           * that for stacks because fulfillers do not need explicit           * that for stacks because fulfillers do not need explicit
482           * nodes, and matching is done by CAS'ing QNode.item field           * nodes, and matching is done by CAS'ing QNode.item field
483           * from nonnull to null (for put) or vice versa (for take).           * from non-null to null (for put) or vice versa (for take).
484           */           */
485    
486          /** Node class for TransferQueue. */          /** Node class for TransferQueue. */
# Line 513  Line 514 
514              }              }
515    
516              /**              /**
517               * Try to cancel by CAS'ing ref to this as item.               * Tries to cancel by CAS'ing ref to this as item.
518               */               */
519              void tryCancel(Object cmp) {              void tryCancel(Object cmp) {
520                  itemUpdater.compareAndSet(this, cmp, this);                  itemUpdater.compareAndSet(this, cmp, this);
# Line 555  Line 556 
556              (TransferQueue.class,  QNode.class, "head");              (TransferQueue.class,  QNode.class, "head");
557    
558          /**          /**
559           * Tries to cas nh as new head; if successful unlink           * Tries to cas nh as new head; if successful, unlink
560           * old head's next node to avoid garbage retention.           * old head's next node to avoid garbage retention.
561           */           */
562          void advanceHead(QNode h, QNode nh) {          void advanceHead(QNode h, QNode nh) {
# Line 622  Line 623 
623              for (;;) {              for (;;) {
624                  QNode t = tail;                  QNode t = tail;
625                  QNode h = head;                  QNode h = head;
626                  if (t == null || h == null)         // saw unitialized values                  if (t == null || h == null)         // saw uninitialized values
627                      continue;                       // spin                      continue;                       // spin
628    
629                  if (h == t || t.isData == isData) { // empty or same-mode                  if (h == t || t.isData == isData) { // empty or same-mode
# Line 938  Line 939 
939      }      }
940    
941      /**      /**
942       * Returns <tt>false</tt> unless given collection is empty.       * Returns <tt>false</tt> unless the given collection is empty.
943       * A <tt>SynchronousQueue</tt> has no internal capacity.       * A <tt>SynchronousQueue</tt> has no internal capacity.
944       * @param c the collection       * @param c the collection
945       * @return <tt>false</tt> unless given collection is empty       * @return <tt>false</tt> unless given collection is empty
Legend:
Removed from v.1.58  
changed lines
  Added in v.1.59
Doug Lea
 ViewVC Help
Powered by ViewVC 1.0.8