Source for java.util.concurrent.locks.AbstractQueuedLongSynchronizer

   1: /*
   2:  * Written by Doug Lea with assistance from members of JCP JSR-166
   3:  * Expert Group and released to the public domain, as explained at
   4:  * http://creativecommons.org/licenses/publicdomain
   5:  */
   6: 
   7: package java.util.concurrent.locks;
   8: import java.util.*;
   9: import java.util.concurrent.*;
  10: import java.util.concurrent.atomic.*;
  11: import sun.misc.Unsafe;
  12: 
  13: /**
  14:  * A version of {@link AbstractQueuedSynchronizer} in
  15:  * which synchronization state is maintained as a <tt>long</tt>.
  16:  * This class has exactly the same structure, properties, and methods
  17:  * as <tt>AbstractQueuedSynchronizer</tt> with the exception
  18:  * that all state-related parameters and results are defined
  19:  * as <tt>long</tt> rather than <tt>int</tt>. This class
  20:  * may be useful when creating synchronizers such as
  21:  * multilevel locks and barriers that require
  22:  * 64 bits of state.
  23:  *
  24:  * <p>See {@link AbstractQueuedSynchronizer} for usage
  25:  * notes and examples.
  26:  *
  27:  * @since 1.6
  28:  * @author Doug Lea
  29:  */
  30: public abstract class AbstractQueuedLongSynchronizer
  31:     extends AbstractOwnableSynchronizer
  32:     implements java.io.Serializable {
  33: 
  34:     private static final long serialVersionUID = 7373984972572414692L;
  35: 
  36:     /*
  37:       To keep sources in sync, the remainder of this source file is
  38:       exactly cloned from AbstractQueuedSynchronizer, replacing class
  39:       name and changing ints related with sync state to longs. Please
  40:       keep it that way.
  41:     */
  42: 
  43:     /**
  44:      * Creates a new <tt>AbstractQueuedLongSynchronizer</tt> instance
  45:      * with initial synchronization state of zero.
  46:      */
  47:     protected AbstractQueuedLongSynchronizer() { }
  48: 
  49:     /**
  50:      * Wait queue node class.
  51:      *
  52:      * <p>The wait queue is a variant of a "CLH" (Craig, Landin, and
  53:      * Hagersten) lock queue. CLH locks are normally used for
  54:      * spinlocks.  We instead use them for blocking synchronizers, but
  55:      * use the same basic tactic of holding some of the control
  56:      * information about a thread in the predecessor of its node.  A
  57:      * "status" field in each node keeps track of whether a thread
  58:      * should block.  A node is signalled when its predecessor
  59:      * releases.  Each node of the queue otherwise serves as a
  60:      * specific-notification-style monitor holding a single waiting
  61:      * thread. The status field does NOT control whether threads are
  62:      * granted locks etc though.  A thread may try to acquire if it is
  63:      * first in the queue. But being first does not guarantee success;
  64:      * it only gives the right to contend.  So the currently released
  65:      * contender thread may need to rewait.
  66:      *
  67:      * <p>To enqueue into a CLH lock, you atomically splice it in as new
  68:      * tail. To dequeue, you just set the head field.
  69:      * <pre>
  70:      *      +------+  prev +-----+       +-----+
  71:      * head |      | <---- |     | <---- |     |  tail
  72:      *      +------+       +-----+       +-----+
  73:      * </pre>
  74:      *
  75:      * <p>Insertion into a CLH queue requires only a single atomic
  76:      * operation on "tail", so there is a simple atomic point of
  77:      * demarcation from unqueued to queued. Similarly, dequeing
  78:      * involves only updating the "head". However, it takes a bit
  79:      * more work for nodes to determine who their successors are,
  80:      * in part to deal with possible cancellation due to timeouts
  81:      * and interrupts.
  82:      *
  83:      * <p>The "prev" links (not used in original CLH locks), are mainly
  84:      * needed to handle cancellation. If a node is cancelled, its
  85:      * successor is (normally) relinked to a non-cancelled
  86:      * predecessor. For explanation of similar mechanics in the case
  87:      * of spin locks, see the papers by Scott and Scherer at
  88:      * http://www.cs.rochester.edu/u/scott/synchronization/
  89:      *
  90:      * <p>We also use "next" links to implement blocking mechanics.
  91:      * The thread id for each node is kept in its own node, so a
  92:      * predecessor signals the next node to wake up by traversing
  93:      * next link to determine which thread it is.  Determination of
  94:      * successor must avoid races with newly queued nodes to set
  95:      * the "next" fields of their predecessors.  This is solved
  96:      * when necessary by checking backwards from the atomically
  97:      * updated "tail" when a node's successor appears to be null.
  98:      * (Or, said differently, the next-links are an optimization
  99:      * so that we don't usually need a backward scan.)
 100:      *
 101:      * <p>Cancellation introduces some conservatism to the basic
 102:      * algorithms.  Since we must poll for cancellation of other
 103:      * nodes, we can miss noticing whether a cancelled node is
 104:      * ahead or behind us. This is dealt with by always unparking
 105:      * successors upon cancellation, allowing them to stabilize on
 106:      * a new predecessor.
 107:      *
 108:      * <p>CLH queues need a dummy header node to get started. But
 109:      * we don't create them on construction, because it would be wasted
 110:      * effort if there is never contention. Instead, the node
 111:      * is constructed and head and tail pointers are set upon first
 112:      * contention.
 113:      *
 114:      * <p>Threads waiting on Conditions use the same nodes, but
 115:      * use an additional link. Conditions only need to link nodes
 116:      * in simple (non-concurrent) linked queues because they are
 117:      * only accessed when exclusively held.  Upon await, a node is
 118:      * inserted into a condition queue.  Upon signal, the node is
 119:      * transferred to the main queue.  A special value of status
 120:      * field is used to mark which queue a node is on.
 121:      *
 122:      * <p>Thanks go to Dave Dice, Mark Moir, Victor Luchangco, Bill
 123:      * Scherer and Michael Scott, along with members of JSR-166
 124:      * expert group, for helpful ideas, discussions, and critiques
 125:      * on the design of this class.
 126:      */
 127:     static final class Node {
 128:         /** waitStatus value to indicate thread has cancelled */
 129:         static final int CANCELLED =  1;
 130:         /** waitStatus value to indicate successor's thread needs unparking */
 131:         static final int SIGNAL    = -1;
 132:         /** waitStatus value to indicate thread is waiting on condition */
 133:         static final int CONDITION = -2;
 134:         /** Marker to indicate a node is waiting in shared mode */
 135:         static final Node SHARED = new Node();
 136:         /** Marker to indicate a node is waiting in exclusive mode */
 137:         static final Node EXCLUSIVE = null;
 138: 
 139:         /**
 140:          * Status field, taking on only the values:
 141:          *   SIGNAL:     The successor of this node is (or will soon be)
 142:          *               blocked (via park), so the current node must
 143:          *               unpark its successor when it releases or
 144:          *               cancels. To avoid races, acquire methods must
 145:          *               first indicate they need a signal,
 146:          *               then retry the atomic acquire, and then,
 147:          *               on failure, block.
 148:          *   CANCELLED:  This node is cancelled due to timeout or interrupt.
 149:          *               Nodes never leave this state. In particular,
 150:          *               a thread with cancelled node never again blocks.
 151:          *   CONDITION:  This node is currently on a condition queue.
 152:          *               It will not be used as a sync queue node until
 153:          *               transferred. (Use of this value here
 154:          *               has nothing to do with the other uses
 155:          *               of the field, but simplifies mechanics.)
 156:          *   0:          None of the above
 157:          *
 158:          * The values are arranged numerically to simplify use.
 159:          * Non-negative values mean that a node doesn't need to
 160:          * signal. So, most code doesn't need to check for particular
 161:          * values, just for sign.
 162:          *
 163:          * The field is initialized to 0 for normal sync nodes, and
 164:          * CONDITION for condition nodes.  It is modified only using
 165:          * CAS.
 166:          */
 167:         volatile int waitStatus;
 168: 
 169:         /**
 170:          * Link to predecessor node that current node/thread relies on
 171:          * for checking waitStatus. Assigned during enqueing, and nulled
 172:          * out (for sake of GC) only upon dequeuing.  Also, upon
 173:          * cancellation of a predecessor, we short-circuit while
 174:          * finding a non-cancelled one, which will always exist
 175:          * because the head node is never cancelled: A node becomes
 176:          * head only as a result of successful acquire. A
 177:          * cancelled thread never succeeds in acquiring, and a thread only
 178:          * cancels itself, not any other node.
 179:          */
 180:         volatile Node prev;
 181: 
 182:         /**
 183:          * Link to the successor node that the current node/thread
 184:          * unparks upon release. Assigned once during enqueuing, and
 185:          * nulled out (for sake of GC) when no longer needed.  Upon
 186:          * cancellation, we cannot adjust this field, but can notice
 187:          * status and bypass the node if cancelled.  The enq operation
 188:          * does not assign next field of a predecessor until after
 189:          * attachment, so seeing a null next field does not
 190:          * necessarily mean that node is at end of queue. However, if
 191:          * a next field appears to be null, we can scan prev's from
 192:          * the tail to double-check.
 193:          */
 194:         volatile Node next;
 195: 
 196:         /**
 197:          * The thread that enqueued this node.  Initialized on
 198:          * construction and nulled out after use.
 199:          */
 200:         volatile Thread thread;
 201: 
 202:         /**
 203:          * Link to next node waiting on condition, or the special
 204:          * value SHARED.  Because condition queues are accessed only
 205:          * when holding in exclusive mode, we just need a simple
 206:          * linked queue to hold nodes while they are waiting on
 207:          * conditions. They are then transferred to the queue to
 208:          * re-acquire. And because conditions can only be exclusive,
 209:          * we save a field by using special value to indicate shared
 210:          * mode.
 211:          */
 212:         Node nextWaiter;
 213: 
 214:         /**
 215:          * Returns true if node is waiting in shared mode
 216:          */
 217:         final boolean isShared() {
 218:             return nextWaiter == SHARED;
 219:         }
 220: 
 221:         /**
 222:          * Returns previous node, or throws NullPointerException if
 223:          * null.  Use when predecessor cannot be null.
 224:          * @return the predecessor of this node
 225:          */
 226:         final Node predecessor() throws NullPointerException {
 227:             Node p = prev;
 228:             if (p == null)
 229:                 throw new NullPointerException();
 230:             else
 231:                 return p;
 232:         }
 233: 
 234:         Node() {    // Used to establish initial head or SHARED marker
 235:         }
 236: 
 237:         Node(Thread thread, Node mode) {     // Used by addWaiter
 238:             this.nextWaiter = mode;
 239:             this.thread = thread;
 240:         }
 241: 
 242:         Node(Thread thread, int waitStatus) { // Used by Condition
 243:             this.waitStatus = waitStatus;
 244:             this.thread = thread;
 245:         }
 246:     }
 247: 
 248:     /**
 249:      * Head of the wait queue, lazily initialized.  Except for
 250:      * initialization, it is modified only via method setHead.  Note:
 251:      * If head exists, its waitStatus is guaranteed not to be
 252:      * CANCELLED.
 253:      */
 254:     private transient volatile Node head;
 255: 
 256:     /**
 257:      * Tail of the wait queue, lazily initialized.  Modified only via
 258:      * method enq to add new wait node.
 259:      */
 260:     private transient volatile Node tail;
 261: 
 262:     /**
 263:      * The synchronization state.
 264:      */
 265:     private volatile long state;
 266: 
 267:     /**
 268:      * Returns the current value of synchronization state.
 269:      * This operation has memory semantics of a <tt>volatile</tt> read.
 270:      * @return current state value
 271:      */
 272:     protected final long getState() {
 273:         return state;
 274:     }
 275: 
 276:     /**
 277:      * Sets the value of synchronization state.
 278:      * This operation has memory semantics of a <tt>volatile</tt> write.
 279:      * @param newState the new state value
 280:      */
 281:     protected final void setState(long newState) {
 282:         state = newState;
 283:     }
 284: 
 285:     /**
 286:      * Atomically sets synchronization state to the given updated
 287:      * value if the current state value equals the expected value.
 288:      * This operation has memory semantics of a <tt>volatile</tt> read
 289:      * and write.
 290:      *
 291:      * @param expect the expected value
 292:      * @param update the new value
 293:      * @return true if successful. False return indicates that the actual
 294:      *         value was not equal to the expected value.
 295:      */
 296:     protected final boolean compareAndSetState(long expect, long update) {
 297:         // See below for intrinsics setup to support this
 298:         return unsafe.compareAndSwapLong(this, stateOffset, expect, update);
 299:     }
 300: 
 301:     // Queuing utilities
 302: 
 303:     /**
 304:      * The number of nanoseconds for which it is faster to spin
 305:      * rather than to use timed park. A rough estimate suffices
 306:      * to improve responsiveness with very short timeouts.
 307:      */
 308:     static final long spinForTimeoutThreshold = 1000L;
 309: 
 310:     /**
 311:      * Inserts node into queue, initializing if necessary. See picture above.
 312:      * @param node the node to insert
 313:      * @return node's predecessor
 314:      */
 315:     private Node enq(final Node node) {
 316:         for (;;) {
 317:             Node t = tail;
 318:             if (t == null) { // Must initialize
 319:                 Node h = new Node(); // Dummy header
 320:                 h.next = node;
 321:                 node.prev = h;
 322:                 if (compareAndSetHead(h)) {
 323:                     tail = node;
 324:                     return h;
 325:                 }
 326:             }
 327:             else {
 328:                 node.prev = t;
 329:                 if (compareAndSetTail(t, node)) {
 330:                     t.next = node;
 331:                     return t;
 332:                 }
 333:             }
 334:         }
 335:     }
 336: 
 337:     /**
 338:      * Creates and enqueues node for given thread and mode.
 339:      *
 340:      * @param current the thread
 341:      * @param mode Node.EXCLUSIVE for exclusive, Node.SHARED for shared
 342:      * @return the new node
 343:      */
 344:     private Node addWaiter(Node mode) {
 345:         Node node = new Node(Thread.currentThread(), mode);
 346:         // Try the fast path of enq; backup to full enq on failure
 347:         Node pred = tail;
 348:         if (pred != null) {
 349:             node.prev = pred;
 350:             if (compareAndSetTail(pred, node)) {
 351:                 pred.next = node;
 352:                 return node;
 353:             }
 354:         }
 355:         enq(node);
 356:         return node;
 357:     }
 358: 
 359:     /**
 360:      * Sets head of queue to be node, thus dequeuing. Called only by
 361:      * acquire methods.  Also nulls out unused fields for sake of GC
 362:      * and to suppress unnecessary signals and traversals.
 363:      *
 364:      * @param node the node
 365:      */
 366:     private void setHead(Node node) {
 367:         head = node;
 368:         node.thread = null;
 369:         node.prev = null;
 370:     }
 371: 
 372:     /**
 373:      * Wakes up node's successor, if one exists.
 374:      *
 375:      * @param node the node
 376:      */
 377:     private void unparkSuccessor(Node node) {
 378:         /*
 379:          * Try to clear status in anticipation of signalling.  It is
 380:          * OK if this fails or if status is changed by waiting thread.
 381:          */
 382:         compareAndSetWaitStatus(node, Node.SIGNAL, 0);
 383: 
 384:         /*
 385:          * Thread to unpark is held in successor, which is normally
 386:          * just the next node.  But if cancelled or apparently null,
 387:          * traverse backwards from tail to find the actual
 388:          * non-cancelled successor.
 389:          */
 390:         Node s = node.next;
 391:         if (s == null || s.waitStatus > 0) {
 392:             s = null;
 393:             for (Node t = tail; t != null && t != node; t = t.prev)
 394:                 if (t.waitStatus <= 0)
 395:                     s = t;
 396:         }
 397:         if (s != null)
 398:             LockSupport.unpark(s.thread);
 399:     }
 400: 
 401:     /**
 402:      * Sets head of queue, and checks if successor may be waiting
 403:      * in shared mode, if so propagating if propagate > 0.
 404:      *
 405:      * @param pred the node holding waitStatus for node
 406:      * @param node the node
 407:      * @param propagate the return value from a tryAcquireShared
 408:      */
 409:     private void setHeadAndPropagate(Node node, long propagate) {
 410:         setHead(node);
 411:         if (propagate > 0 && node.waitStatus != 0) {
 412:             /*
 413:              * Don't bother fully figuring out successor.  If it
 414:              * looks null, call unparkSuccessor anyway to be safe.
 415:              */
 416:             Node s = node.next;
 417:             if (s == null || s.isShared())
 418:                 unparkSuccessor(node);
 419:         }
 420:     }
 421: 
 422:     // Utilities for various versions of acquire
 423: 
 424:     /**
 425:      * Cancels an ongoing attempt to acquire.
 426:      *
 427:      * @param node the node
 428:      */
 429:     private void cancelAcquire(Node node) {
 430:         if (node != null) { // Ignore if node doesn't exist
 431:             node.thread = null;
 432:             // Can use unconditional write instead of CAS here
 433:             node.waitStatus = Node.CANCELLED;
 434:             unparkSuccessor(node);
 435:         }
 436:     }
 437: 
 438:     /**
 439:      * Checks and updates status for a node that failed to acquire.
 440:      * Returns true if thread should block. This is the main signal
 441:      * control in all acquire loops.  Requires that pred == node.prev
 442:      *
 443:      * @param pred node's predecessor holding status
 444:      * @param node the node
 445:      * @return {@code true} if thread should block
 446:      */
 447:     private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
 448:         int s = pred.waitStatus;
 449:         if (s < 0)
 450:             /*
 451:              * This node has already set status asking a release
 452:              * to signal it, so it can safely park
 453:              */
 454:             return true;
 455:         if (s > 0)
 456:             /*
 457:              * Predecessor was cancelled. Move up to its predecessor
 458:              * and indicate retry.
 459:              */
 460:             node.prev = pred.prev;
 461:         else
 462:             /*
 463:              * Indicate that we need a signal, but don't park yet. Caller
 464:              * will need to retry to make sure it cannot acquire before
 465:              * parking.
 466:              */
 467:             compareAndSetWaitStatus(pred, 0, Node.SIGNAL);
 468:         return false;
 469:     }
 470: 
 471:     /**
 472:      * Convenience method to interrupt current thread.
 473:      */
 474:     private static void selfInterrupt() {
 475:         Thread.currentThread().interrupt();
 476:     }
 477: 
 478:     /**
 479:      * Convenience method to park and then check if interrupted
 480:      *
 481:      * @return {@code true} if interrupted
 482:      */
 483:     private final boolean parkAndCheckInterrupt() {
 484:         LockSupport.park(this);
 485:         return Thread.interrupted();
 486:     }
 487: 
 488:     /*
 489:      * Various flavors of acquire, varying in exclusive/shared and
 490:      * control modes.  Each is mostly the same, but annoyingly
 491:      * different.  Only a little bit of factoring is possible due to
 492:      * interactions of exception mechanics (including ensuring that we
 493:      * cancel if tryAcquire throws exception) and other control, at
 494:      * least not without hurting performance too much.
 495:      */
 496: 
 497:     /**
 498:      * Acquires in exclusive uninterruptible mode for thread already in
 499:      * queue. Used by condition wait methods as well as acquire.
 500:      *
 501:      * @param node the node
 502:      * @param arg the acquire argument
 503:      * @return {@code true} if interrupted while waiting
 504:      */
 505:     final boolean acquireQueued(final Node node, long arg) {
 506:         try {
 507:             boolean interrupted = false;
 508:             for (;;) {
 509:                 final Node p = node.predecessor();
 510:                 if (p == head && tryAcquire(arg)) {
 511:                     setHead(node);
 512:                     p.next = null; // help GC
 513:                     return interrupted;
 514:                 }
 515:                 if (shouldParkAfterFailedAcquire(p, node) &&
 516:                     parkAndCheckInterrupt())
 517:                     interrupted = true;
 518:             }
 519:         } catch (RuntimeException ex) {
 520:             cancelAcquire(node);
 521:             throw ex;
 522:         }
 523:     }
 524: 
 525:     /**
 526:      * Acquires in exclusive interruptible mode.
 527:      * @param arg the acquire argument
 528:      */
 529:     private void doAcquireInterruptibly(long arg)
 530:         throws InterruptedException {
 531:         final Node node = addWaiter(Node.EXCLUSIVE);
 532:         try {
 533:             for (;;) {
 534:                 final Node p = node.predecessor();
 535:                 if (p == head && tryAcquire(arg)) {
 536:                     setHead(node);
 537:                     p.next = null; // help GC
 538:                     return;
 539:                 }
 540:                 if (shouldParkAfterFailedAcquire(p, node) &&
 541:                     parkAndCheckInterrupt())
 542:                     break;
 543:             }
 544:         } catch (RuntimeException ex) {
 545:             cancelAcquire(node);
 546:             throw ex;
 547:         }
 548:         // Arrive here only if interrupted
 549:         cancelAcquire(node);
 550:         throw new InterruptedException();
 551:     }
 552: 
 553:     /**
 554:      * Acquires in exclusive timed mode.
 555:      *
 556:      * @param arg the acquire argument
 557:      * @param nanosTimeout max wait time
 558:      * @return {@code true} if acquired
 559:      */
 560:     private boolean doAcquireNanos(long arg, long nanosTimeout)
 561:         throws InterruptedException {
 562:         long lastTime = System.nanoTime();
 563:         final Node node = addWaiter(Node.EXCLUSIVE);
 564:         try {
 565:             for (;;) {
 566:                 final Node p = node.predecessor();
 567:                 if (p == head && tryAcquire(arg)) {
 568:                     setHead(node);
 569:                     p.next = null; // help GC
 570:                     return true;
 571:                 }
 572:                 if (nanosTimeout <= 0) {
 573:                     cancelAcquire(node);
 574:                     return false;
 575:                 }
 576:                 if (nanosTimeout > spinForTimeoutThreshold &&
 577:                     shouldParkAfterFailedAcquire(p, node))
 578:                     LockSupport.parkNanos(this, nanosTimeout);
 579:                 long now = System.nanoTime();
 580:                 nanosTimeout -= now - lastTime;
 581:                 lastTime = now;
 582:                 if (Thread.interrupted())
 583:                     break;
 584:             }
 585:         } catch (RuntimeException ex) {
 586:             cancelAcquire(node);
 587:             throw ex;
 588:         }
 589:         // Arrive here only if interrupted
 590:         cancelAcquire(node);
 591:         throw new InterruptedException();
 592:     }
 593: 
 594:     /**
 595:      * Acquires in shared uninterruptible mode.
 596:      * @param arg the acquire argument
 597:      */
 598:     private void doAcquireShared(long arg) {
 599:         final Node node = addWaiter(Node.SHARED);
 600:         try {
 601:             boolean interrupted = false;
 602:             for (;;) {
 603:                 final Node p = node.predecessor();
 604:                 if (p == head) {
 605:                     long r = tryAcquireShared(arg);
 606:                     if (r >= 0) {
 607:                         setHeadAndPropagate(node, r);
 608:                         p.next = null; // help GC
 609:                         if (interrupted)
 610:                             selfInterrupt();
 611:                         return;
 612:                     }
 613:                 }
 614:                 if (shouldParkAfterFailedAcquire(p, node) &&
 615:                     parkAndCheckInterrupt())
 616:                     interrupted = true;
 617:             }
 618:         } catch (RuntimeException ex) {
 619:             cancelAcquire(node);
 620:             throw ex;
 621:         }
 622:     }
 623: 
 624:     /**
 625:      * Acquires in shared interruptible mode.
 626:      * @param arg the acquire argument
 627:      */
 628:     private void doAcquireSharedInterruptibly(long arg)
 629:         throws InterruptedException {
 630:         final Node node = addWaiter(Node.SHARED);
 631:         try {
 632:             for (;;) {
 633:                 final Node p = node.predecessor();
 634:                 if (p == head) {
 635:                     long r = tryAcquireShared(arg);
 636:                     if (r >= 0) {
 637:                         setHeadAndPropagate(node, r);
 638:                         p.next = null; // help GC
 639:                         return;
 640:                     }
 641:                 }
 642:                 if (shouldParkAfterFailedAcquire(p, node) &&
 643:                     parkAndCheckInterrupt())
 644:                     break;
 645:             }
 646:         } catch (RuntimeException ex) {
 647:             cancelAcquire(node);
 648:             throw ex;
 649:         }
 650:         // Arrive here only if interrupted
 651:         cancelAcquire(node);
 652:         throw new InterruptedException();
 653:     }
 654: 
 655:     /**
 656:      * Acquires in shared timed mode.
 657:      *
 658:      * @param arg the acquire argument
 659:      * @param nanosTimeout max wait time
 660:      * @return {@code true} if acquired
 661:      */
 662:     private boolean doAcquireSharedNanos(long arg, long nanosTimeout)
 663:         throws InterruptedException {
 664: 
 665:         long lastTime = System.nanoTime();
 666:         final Node node = addWaiter(Node.SHARED);
 667:         try {
 668:             for (;;) {
 669:                 final Node p = node.predecessor();
 670:                 if (p == head) {
 671:                     long r = tryAcquireShared(arg);
 672:                     if (r >= 0) {
 673:                         setHeadAndPropagate(node, r);
 674:                         p.next = null; // help GC
 675:                         return true;
 676:                     }
 677:                 }
 678:                 if (nanosTimeout <= 0) {
 679:                     cancelAcquire(node);
 680:                     return false;
 681:                 }
 682:                 if (nanosTimeout > spinForTimeoutThreshold &&
 683:                     shouldParkAfterFailedAcquire(p, node))
 684:                     LockSupport.parkNanos(this, nanosTimeout);
 685:                 long now = System.nanoTime();
 686:                 nanosTimeout -= now - lastTime;
 687:                 lastTime = now;
 688:                 if (Thread.interrupted())
 689:                     break;
 690:             }
 691:         } catch (RuntimeException ex) {
 692:             cancelAcquire(node);
 693:             throw ex;
 694:         }
 695:         // Arrive here only if interrupted
 696:         cancelAcquire(node);
 697:         throw new InterruptedException();
 698:     }
 699: 
 700:     // Main exported methods
 701: 
 702:     /**
 703:      * Attempts to acquire in exclusive mode. This method should query
 704:      * if the state of the object permits it to be acquired in the
 705:      * exclusive mode, and if so to acquire it.
 706:      *
 707:      * <p>This method is always invoked by the thread performing
 708:      * acquire.  If this method reports failure, the acquire method
 709:      * may queue the thread, if it is not already queued, until it is
 710:      * signalled by a release from some other thread. This can be used
 711:      * to implement method {@link Lock#tryLock()}.
 712:      *
 713:      * <p>The default
 714:      * implementation throws {@link UnsupportedOperationException}.
 715:      *
 716:      * @param arg the acquire argument. This value is always the one
 717:      *        passed to an acquire method, or is the value saved on entry
 718:      *        to a condition wait.  The value is otherwise uninterpreted
 719:      *        and can represent anything you like.
 720:      * @return {@code true} if successful. Upon success, this object has
 721:      *         been acquired.
 722:      * @throws IllegalMonitorStateException if acquiring would place this
 723:      *         synchronizer in an illegal state. This exception must be
 724:      *         thrown in a consistent fashion for synchronization to work
 725:      *         correctly.
 726:      * @throws UnsupportedOperationException if exclusive mode is not supported
 727:      */
 728:     protected boolean tryAcquire(long arg) {
 729:         throw new UnsupportedOperationException();
 730:     }
 731: 
 732:     /**
 733:      * Attempts to set the state to reflect a release in exclusive
 734:      * mode.
 735:      *
 736:      * <p>This method is always invoked by the thread performing release.
 737:      *
 738:      * <p>The default implementation throws
 739:      * {@link UnsupportedOperationException}.
 740:      *
 741:      * @param arg the release argument. This value is always the one
 742:      *        passed to a release method, or the current state value upon
 743:      *        entry to a condition wait.  The value is otherwise
 744:      *        uninterpreted and can represent anything you like.
 745:      * @return {@code true} if this object is now in a fully released
 746:      *         state, so that any waiting threads may attempt to acquire;
 747:      *         and {@code false} otherwise.
 748:      * @throws IllegalMonitorStateException if releasing would place this
 749:      *         synchronizer in an illegal state. This exception must be
 750:      *         thrown in a consistent fashion for synchronization to work
 751:      *         correctly.
 752:      * @throws UnsupportedOperationException if exclusive mode is not supported
 753:      */
 754:     protected boolean tryRelease(long arg) {
 755:         throw new UnsupportedOperationException();
 756:     }
 757: 
 758:     /**
 759:      * Attempts to acquire in shared mode. This method should query if
 760:      * the state of the object permits it to be acquired in the shared
 761:      * mode, and if so to acquire it.
 762:      *
 763:      * <p>This method is always invoked by the thread performing
 764:      * acquire.  If this method reports failure, the acquire method
 765:      * may queue the thread, if it is not already queued, until it is
 766:      * signalled by a release from some other thread.
 767:      *
 768:      * <p>The default implementation throws {@link
 769:      * UnsupportedOperationException}.
 770:      *
 771:      * @param arg the acquire argument. This value is always the one
 772:      *        passed to an acquire method, or is the value saved on entry
 773:      *        to a condition wait.  The value is otherwise uninterpreted
 774:      *        and can represent anything you like.
 775:      * @return a negative value on failure; zero if acquisition in shared
 776:      *         mode succeeded but no subsequent shared-mode acquire can
 777:      *         succeed; and a positive value if acquisition in shared
 778:      *         mode succeeded and subsequent shared-mode acquires might
 779:      *         also succeed, in which case a subsequent waiting thread
 780:      *         must check availability. (Support for three different
 781:      *         return values enables this method to be used in contexts
 782:      *         where acquires only sometimes act exclusively.)  Upon
 783:      *         success, this object has been acquired.
 784:      * @throws IllegalMonitorStateException if acquiring would place this
 785:      *         synchronizer in an illegal state. This exception must be
 786:      *         thrown in a consistent fashion for synchronization to work
 787:      *         correctly.
 788:      * @throws UnsupportedOperationException if shared mode is not supported
 789:      */
 790:     protected long tryAcquireShared(long arg) {
 791:         throw new UnsupportedOperationException();
 792:     }
 793: 
 794:     /**
 795:      * Attempts to set the state to reflect a release in shared mode.
 796:      *
 797:      * <p>This method is always invoked by the thread performing release.
 798:      *
 799:      * <p>The default implementation throws
 800:      * {@link UnsupportedOperationException}.
 801:      *
 802:      * @param arg the release argument. This value is always the one
 803:      *        passed to a release method, or the current state value upon
 804:      *        entry to a condition wait.  The value is otherwise
 805:      *        uninterpreted and can represent anything you like.
 806:      * @return {@code true} if this release of shared mode may permit a
 807:      *         waiting acquire (shared or exclusive) to succeed; and
 808:      *         {@code false} otherwise
 809:      * @throws IllegalMonitorStateException if releasing would place this
 810:      *         synchronizer in an illegal state. This exception must be
 811:      *         thrown in a consistent fashion for synchronization to work
 812:      *         correctly.
 813:      * @throws UnsupportedOperationException if shared mode is not supported
 814:      */
 815:     protected boolean tryReleaseShared(long arg) {
 816:         throw new UnsupportedOperationException();
 817:     }
 818: 
 819:     /**
 820:      * Returns {@code true} if synchronization is held exclusively with
 821:      * respect to the current (calling) thread.  This method is invoked
 822:      * upon each call to a non-waiting {@link ConditionObject} method.
 823:      * (Waiting methods instead invoke {@link #release}.)
 824:      *
 825:      * <p>The default implementation throws {@link
 826:      * UnsupportedOperationException}. This method is invoked
 827:      * internally only within {@link ConditionObject} methods, so need
 828:      * not be defined if conditions are not used.
 829:      *
 830:      * @return {@code true} if synchronization is held exclusively;
 831:      *         {@code false} otherwise
 832:      * @throws UnsupportedOperationException if conditions are not supported
 833:      */
 834:     protected boolean isHeldExclusively() {
 835:         throw new UnsupportedOperationException();
 836:     }
 837: 
 838:     /**
 839:      * Acquires in exclusive mode, ignoring interrupts.  Implemented
 840:      * by invoking at least once {@link #tryAcquire},
 841:      * returning on success.  Otherwise the thread is queued, possibly
 842:      * repeatedly blocking and unblocking, invoking {@link
 843:      * #tryAcquire} until success.  This method can be used
 844:      * to implement method {@link Lock#lock}.
 845:      *
 846:      * @param arg the acquire argument.  This value is conveyed to
 847:      *        {@link #tryAcquire} but is otherwise uninterpreted and
 848:      *        can represent anything you like.
 849:      */
 850:     public final void acquire(long arg) {
 851:         if (!tryAcquire(arg) &&
 852:             acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
 853:             selfInterrupt();
 854:     }
 855: 
 856:     /**
 857:      * Acquires in exclusive mode, aborting if interrupted.
 858:      * Implemented by first checking interrupt status, then invoking
 859:      * at least once {@link #tryAcquire}, returning on
 860:      * success.  Otherwise the thread is queued, possibly repeatedly
 861:      * blocking and unblocking, invoking {@link #tryAcquire}
 862:      * until success or the thread is interrupted.  This method can be
 863:      * used to implement method {@link Lock#lockInterruptibly}.
 864:      *
 865:      * @param arg the acquire argument.  This value is conveyed to
 866:      *        {@link #tryAcquire} but is otherwise uninterpreted and
 867:      *        can represent anything you like.
 868:      * @throws InterruptedException if the current thread is interrupted
 869:      */
 870:     public final void acquireInterruptibly(long arg) throws InterruptedException {
 871:         if (Thread.interrupted())
 872:             throw new InterruptedException();
 873:         if (!tryAcquire(arg))
 874:             doAcquireInterruptibly(arg);
 875:     }
 876: 
 877:     /**
 878:      * Attempts to acquire in exclusive mode, aborting if interrupted,
 879:      * and failing if the given timeout elapses.  Implemented by first
 880:      * checking interrupt status, then invoking at least once {@link
 881:      * #tryAcquire}, returning on success.  Otherwise, the thread is
 882:      * queued, possibly repeatedly blocking and unblocking, invoking
 883:      * {@link #tryAcquire} until success or the thread is interrupted
 884:      * or the timeout elapses.  This method can be used to implement
 885:      * method {@link Lock#tryLock(long, TimeUnit)}.
 886:      *
 887:      * @param arg the acquire argument.  This value is conveyed to
 888:      *        {@link #tryAcquire} but is otherwise uninterpreted and
 889:      *        can represent anything you like.
 890:      * @param nanosTimeout the maximum number of nanoseconds to wait
 891:      * @return {@code true} if acquired; {@code false} if timed out
 892:      * @throws InterruptedException if the current thread is interrupted
 893:      */
 894:     public final boolean tryAcquireNanos(long arg, long nanosTimeout) throws InterruptedException {
 895:     if (Thread.interrupted())
 896:         throw new InterruptedException();
 897:     return tryAcquire(arg) ||
 898:         doAcquireNanos(arg, nanosTimeout);
 899:     }
 900: 
 901:     /**
 902:      * Releases in exclusive mode.  Implemented by unblocking one or
 903:      * more threads if {@link #tryRelease} returns true.
 904:      * This method can be used to implement method {@link Lock#unlock}.
 905:      *
 906:      * @param arg the release argument.  This value is conveyed to
 907:      *        {@link #tryRelease} but is otherwise uninterpreted and
 908:      *        can represent anything you like.
 909:      * @return the value returned from {@link #tryRelease}
 910:      */
 911:     public final boolean release(long arg) {
 912:         if (tryRelease(arg)) {
 913:             Node h = head;
 914:             if (h != null && h.waitStatus != 0)
 915:                 unparkSuccessor(h);
 916:             return true;
 917:         }
 918:         return false;
 919:     }
 920: 
 921:     /**
 922:      * Acquires in shared mode, ignoring interrupts.  Implemented by
 923:      * first invoking at least once {@link #tryAcquireShared},
 924:      * returning on success.  Otherwise the thread is queued, possibly
 925:      * repeatedly blocking and unblocking, invoking {@link
 926:      * #tryAcquireShared} until success.
 927:      *
 928:      * @param arg the acquire argument.  This value is conveyed to
 929:      *        {@link #tryAcquireShared} but is otherwise uninterpreted
 930:      *        and can represent anything you like.
 931:      */
 932:     public final void acquireShared(long arg) {
 933:         if (tryAcquireShared(arg) < 0)
 934:             doAcquireShared(arg);
 935:     }
 936: 
 937:     /**
 938:      * Acquires in shared mode, aborting if interrupted.  Implemented
 939:      * by first checking interrupt status, then invoking at least once
 940:      * {@link #tryAcquireShared}, returning on success.  Otherwise the
 941:      * thread is queued, possibly repeatedly blocking and unblocking,
 942:      * invoking {@link #tryAcquireShared} until success or the thread
 943:      * is interrupted.
 944:      * @param arg the acquire argument.
 945:      * This value is conveyed to {@link #tryAcquireShared} but is
 946:      * otherwise uninterpreted and can represent anything
 947:      * you like.
 948:      * @throws InterruptedException if the current thread is interrupted
 949:      */
 950:     public final void acquireSharedInterruptibly(long arg) throws InterruptedException {
 951:         if (Thread.interrupted())
 952:             throw new InterruptedException();
 953:         if (tryAcquireShared(arg) < 0)
 954:             doAcquireSharedInterruptibly(arg);
 955:     }
 956: 
 957:     /**
 958:      * Attempts to acquire in shared mode, aborting if interrupted, and
 959:      * failing if the given timeout elapses.  Implemented by first
 960:      * checking interrupt status, then invoking at least once {@link
 961:      * #tryAcquireShared}, returning on success.  Otherwise, the
 962:      * thread is queued, possibly repeatedly blocking and unblocking,
 963:      * invoking {@link #tryAcquireShared} until success or the thread
 964:      * is interrupted or the timeout elapses.
 965:      *
 966:      * @param arg the acquire argument.  This value is conveyed to
 967:      *        {@link #tryAcquireShared} but is otherwise uninterpreted
 968:      *        and can represent anything you like.
 969:      * @param nanosTimeout the maximum number of nanoseconds to wait
 970:      * @return {@code true} if acquired; {@code false} if timed out
 971:      * @throws InterruptedException if the current thread is interrupted
 972:      */
 973:     public final boolean tryAcquireSharedNanos(long arg, long nanosTimeout) throws InterruptedException {
 974:     if (Thread.interrupted())
 975:         throw new InterruptedException();
 976:     return tryAcquireShared(arg) >= 0 ||
 977:         doAcquireSharedNanos(arg, nanosTimeout);
 978:     }
 979: 
 980:     /**
 981:      * Releases in shared mode.  Implemented by unblocking one or more
 982:      * threads if {@link #tryReleaseShared} returns true.
 983:      *
 984:      * @param arg the release argument.  This value is conveyed to
 985:      *        {@link #tryReleaseShared} but is otherwise uninterpreted
 986:      *        and can represent anything you like.
 987:      * @return the value returned from {@link #tryReleaseShared}
 988:      */
 989:     public final boolean releaseShared(long arg) {
 990:         if (tryReleaseShared(arg)) {
 991:             Node h = head;
 992:             if (h != null && h.waitStatus != 0)
 993:                 unparkSuccessor(h);
 994:             return true;
 995:         }
 996:         return false;
 997:     }
 998: 
 999:     // Queue inspection methods
1000: 
1001:     /**
1002:      * Queries whether any threads are waiting to acquire. Note that
1003:      * because cancellations due to interrupts and timeouts may occur
1004:      * at any time, a {@code true} return does not guarantee that any
1005:      * other thread will ever acquire.
1006:      *
1007:      * <p>In this implementation, this operation returns in
1008:      * constant time.
1009:      *
1010:      * @return {@code true} if there may be other threads waiting to acquire
1011:      */
1012:     public final boolean hasQueuedThreads() {
1013:         return head != tail;
1014:     }
1015: 
1016:     /**
1017:      * Queries whether any threads have ever contended to acquire this
1018:      * synchronizer; that is if an acquire method has ever blocked.
1019:      *
1020:      * <p>In this implementation, this operation returns in
1021:      * constant time.
1022:      *
1023:      * @return {@code true} if there has ever been contention
1024:      */
1025:     public final boolean hasContended() {
1026:         return head != null;
1027:     }
1028: 
1029:     /**
1030:      * Returns the first (longest-waiting) thread in the queue, or
1031:      * {@code null} if no threads are currently queued.
1032:      *
1033:      * <p>In this implementation, this operation normally returns in
1034:      * constant time, but may iterate upon contention if other threads are
1035:      * concurrently modifying the queue.
1036:      *
1037:      * @return the first (longest-waiting) thread in the queue, or
1038:      *         {@code null} if no threads are currently queued
1039:      */
1040:     public final Thread getFirstQueuedThread() {
1041:         // handle only fast path, else relay
1042:         return (head == tail)? null : fullGetFirstQueuedThread();
1043:     }
1044: 
1045:     /**
1046:      * Version of getFirstQueuedThread called when fastpath fails
1047:      */
1048:     private Thread fullGetFirstQueuedThread() {
1049:         /*
1050:          * The first node is normally h.next. Try to get its
1051:          * thread field, ensuring consistent reads: If thread
1052:          * field is nulled out or s.prev is no longer head, then
1053:          * some other thread(s) concurrently performed setHead in
1054:          * between some of our reads. We try this twice before
1055:          * resorting to traversal.
1056:          */
1057:         Node h, s;
1058:         Thread st;
1059:         if (((h = head) != null && (s = h.next) != null &&
1060:              s.prev == head && (st = s.thread) != null) ||
1061:             ((h = head) != null && (s = h.next) != null &&
1062:              s.prev == head && (st = s.thread) != null))
1063:             return st;
1064: 
1065:         /*
1066:          * Head's next field might not have been set yet, or may have
1067:          * been unset after setHead. So we must check to see if tail
1068:          * is actually first node. If not, we continue on, safely
1069:          * traversing from tail back to head to find first,
1070:          * guaranteeing termination.
1071:          */
1072: 
1073:         Node t = tail;
1074:         Thread firstThread = null;
1075:         while (t != null && t != head) {
1076:             Thread tt = t.thread;
1077:             if (tt != null)
1078:                 firstThread = tt;
1079:             t = t.prev;
1080:         }
1081:         return firstThread;
1082:     }
1083: 
1084:     /**
1085:      * Returns true if the given thread is currently queued.
1086:      *
1087:      * <p>This implementation traverses the queue to determine
1088:      * presence of the given thread.
1089:      *
1090:      * @param thread the thread
1091:      * @return {@code true} if the given thread is on the queue
1092:      * @throws NullPointerException if the thread is null
1093:      */
1094:     public final boolean isQueued(Thread thread) {
1095:         if (thread == null)
1096:             throw new NullPointerException();
1097:         for (Node p = tail; p != null; p = p.prev)
1098:             if (p.thread == thread)
1099:                 return true;
1100:         return false;
1101:     }
1102: 
1103:     /**
1104:      * Return {@code true} if the apparent first queued thread, if one
1105:      * exists, is not waiting in exclusive mode. Used only as a heuristic
1106:      * in ReentrantReadWriteLock.
1107:      */
1108:     final boolean apparentlyFirstQueuedIsExclusive() {
1109:         Node h, s;
1110:         return ((h = head) != null && (s = h.next) != null &&
1111:                 s.nextWaiter != Node.SHARED);
1112:     }
1113: 
1114:     /**
1115:      * Return {@code true} if the queue is empty or if the given thread
1116:      * is at the head of the queue. This is reliable only if
1117:      * <tt>current</tt> is actually Thread.currentThread() of caller.
1118:      */
1119:     final boolean isFirst(Thread current) {
1120:         Node h, s;
1121:         return ((h = head) == null ||
1122:                 ((s = h.next) != null && s.thread == current) ||
1123:                 fullIsFirst(current));
1124:     }
1125: 
1126:     final boolean fullIsFirst(Thread current) {
1127:         // same idea as fullGetFirstQueuedThread
1128:         Node h, s;
1129:         Thread firstThread = null;
1130:         if (((h = head) != null && (s = h.next) != null &&
1131:              s.prev == head && (firstThread = s.thread) != null))
1132:             return firstThread == current;
1133:         Node t = tail;
1134:         while (t != null && t != head) {
1135:             Thread tt = t.thread;
1136:             if (tt != null)
1137:                 firstThread = tt;
1138:             t = t.prev;
1139:         }
1140:         return firstThread == current || firstThread == null;
1141:     }
1142: 
1143: 
1144:     // Instrumentation and monitoring methods
1145: 
1146:     /**
1147:      * Returns an estimate of the number of threads waiting to
1148:      * acquire.  The value is only an estimate because the number of
1149:      * threads may change dynamically while this method traverses
1150:      * internal data structures.  This method is designed for use in
1151:      * monitoring system state, not for synchronization
1152:      * control.
1153:      *
1154:      * @return the estimated number of threads waiting to acquire
1155:      */
1156:     public final int getQueueLength() {
1157:         int n = 0;
1158:         for (Node p = tail; p != null; p = p.prev) {
1159:             if (p.thread != null)
1160:                 ++n;
1161:         }
1162:         return n;
1163:     }
1164: 
1165:     /**
1166:      * Returns a collection containing threads that may be waiting to
1167:      * acquire.  Because the actual set of threads may change
1168:      * dynamically while constructing this result, the returned
1169:      * collection is only a best-effort estimate.  The elements of the
1170:      * returned collection are in no particular order.  This method is
1171:      * designed to facilitate construction of subclasses that provide
1172:      * more extensive monitoring facilities.
1173:      *
1174:      * @return the collection of threads
1175:      */
1176:     public final Collection<Thread> getQueuedThreads() {
1177:         ArrayList<Thread> list = new ArrayList<Thread>();
1178:         for (Node p = tail; p != null; p = p.prev) {
1179:             Thread t = p.thread;
1180:             if (t != null)
1181:                 list.add(t);
1182:         }
1183:         return list;
1184:     }
1185: 
1186:     /**
1187:      * Returns a collection containing threads that may be waiting to
1188:      * acquire in exclusive mode. This has the same properties
1189:      * as {@link #getQueuedThreads} except that it only returns
1190:      * those threads waiting due to an exclusive acquire.
1191:      *
1192:      * @return the collection of threads
1193:      */
1194:     public final Collection<Thread> getExclusiveQueuedThreads() {
1195:         ArrayList<Thread> list = new ArrayList<Thread>();
1196:         for (Node p = tail; p != null; p = p.prev) {
1197:             if (!p.isShared()) {
1198:                 Thread t = p.thread;
1199:                 if (t != null)
1200:                     list.add(t);
1201:             }
1202:         }
1203:         return list;
1204:     }
1205: 
1206:     /**
1207:      * Returns a collection containing threads that may be waiting to
1208:      * acquire in shared mode. This has the same properties
1209:      * as {@link #getQueuedThreads} except that it only returns
1210:      * those threads waiting due to a shared acquire.
1211:      *
1212:      * @return the collection of threads
1213:      */
1214:     public final Collection<Thread> getSharedQueuedThreads() {
1215:         ArrayList<Thread> list = new ArrayList<Thread>();
1216:         for (Node p = tail; p != null; p = p.prev) {
1217:             if (p.isShared()) {
1218:                 Thread t = p.thread;
1219:                 if (t != null)
1220:                     list.add(t);
1221:             }
1222:         }
1223:         return list;
1224:     }
1225: 
1226:     /**
1227:      * Returns a string identifying this synchronizer, as well as its state.
1228:      * The state, in brackets, includes the String {@code "State ="}
1229:      * followed by the current value of {@link #getState}, and either
1230:      * {@code "nonempty"} or {@code "empty"} depending on whether the
1231:      * queue is empty.
1232:      *
1233:      * @return a string identifying this synchronizer, as well as its state
1234:      */
1235:     public String toString() {
1236:         long s = getState();
1237:         String q  = hasQueuedThreads()? "non" : "";
1238:         return super.toString() +
1239:             "[State = " + s + ", " + q + "empty queue]";
1240:     }
1241: 
1242: 
1243:     // Internal support methods for Conditions
1244: 
1245:     /**
1246:      * Returns true if a node, always one that was initially placed on
1247:      * a condition queue, is now waiting to reacquire on sync queue.
1248:      * @param node the node
1249:      * @return true if is reacquiring
1250:      */
1251:     final boolean isOnSyncQueue(Node node) {
1252:         if (node.waitStatus == Node.CONDITION || node.prev == null)
1253:             return false;
1254:         if (node.next != null) // If has successor, it must be on queue
1255:             return true;
1256:         /*
1257:          * node.prev can be non-null, but not yet on queue because
1258:          * the CAS to place it on queue can fail. So we have to
1259:          * traverse from tail to make sure it actually made it.  It
1260:          * will always be near the tail in calls to this method, and
1261:          * unless the CAS failed (which is unlikely), it will be
1262:          * there, so we hardly ever traverse much.
1263:          */
1264:         return findNodeFromTail(node);
1265:     }
1266: 
1267:     /**
1268:      * Returns true if node is on sync queue by searching backwards from tail.
1269:      * Called only when needed by isOnSyncQueue.
1270:      * @return true if present
1271:      */
1272:     private boolean findNodeFromTail(Node node) {
1273:         Node t = tail;
1274:         for (;;) {
1275:             if (t == node)
1276:                 return true;
1277:             if (t == null)
1278:                 return false;
1279:             t = t.prev;
1280:         }
1281:     }
1282: 
1283:     /**
1284:      * Transfers a node from a condition queue onto sync queue.
1285:      * Returns true if successful.
1286:      * @param node the node
1287:      * @return true if successfully transferred (else the node was
1288:      * cancelled before signal).
1289:      */
1290:     final boolean transferForSignal(Node node) {
1291:         /*
1292:          * If cannot change waitStatus, the node has been cancelled.
1293:          */
1294:         if (!compareAndSetWaitStatus(node, Node.CONDITION, 0))
1295:             return false;
1296: 
1297:         /*
1298:          * Splice onto queue and try to set waitStatus of predecessor to
1299:          * indicate that thread is (probably) waiting. If cancelled or
1300:          * attempt to set waitStatus fails, wake up to resync (in which
1301:          * case the waitStatus can be transiently and harmlessly wrong).
1302:          */
1303:         Node p = enq(node);
1304:         int c = p.waitStatus;
1305:         if (c > 0 || !compareAndSetWaitStatus(p, c, Node.SIGNAL))
1306:             LockSupport.unpark(node.thread);
1307:         return true;
1308:     }
1309: 
1310:     /**
1311:      * Transfers node, if necessary, to sync queue after a cancelled
1312:      * wait. Returns true if thread was cancelled before being
1313:      * signalled.
1314:      * @param current the waiting thread
1315:      * @param node its node
1316:      * @return true if cancelled before the node was signalled.
1317:      */
1318:     final boolean transferAfterCancelledWait(Node node) {
1319:         if (compareAndSetWaitStatus(node, Node.CONDITION, 0)) {
1320:             enq(node);
1321:             return true;
1322:         }
1323:         /*
1324:          * If we lost out to a signal(), then we can't proceed
1325:          * until it finishes its enq().  Cancelling during an
1326:          * incomplete transfer is both rare and transient, so just
1327:          * spin.
1328:          */
1329:         while (!isOnSyncQueue(node))
1330:             Thread.yield();
1331:         return false;
1332:     }
1333: 
1334:     /**
1335:      * Invokes release with current state value; returns saved state.
1336:      * Cancels node and throws exception on failure.
1337:      * @param node the condition node for this wait
1338:      * @return previous sync state
1339:      */
1340:     final long fullyRelease(Node node) {
1341:         try {
1342:             long savedState = getState();
1343:             if (release(savedState))
1344:                 return savedState;
1345:         } catch (RuntimeException ex) {
1346:             node.waitStatus = Node.CANCELLED;
1347:             throw ex;
1348:         }
1349:         // reach here if release fails
1350:         node.waitStatus = Node.CANCELLED;
1351:         throw new IllegalMonitorStateException();
1352:     }
1353: 
1354:     // Instrumentation methods for conditions
1355: 
1356:     /**
1357:      * Queries whether the given ConditionObject
1358:      * uses this synchronizer as its lock.
1359:      *
1360:      * @param condition the condition
1361:      * @return <tt>true</tt> if owned
1362:      * @throws NullPointerException if the condition is null
1363:      */
1364:     public final boolean owns(ConditionObject condition) {
1365:         if (condition == null)
1366:             throw new NullPointerException();
1367:         return condition.isOwnedBy(this);
1368:     }
1369: 
1370:     /**
1371:      * Queries whether any threads are waiting on the given condition
1372:      * associated with this synchronizer. Note that because timeouts
1373:      * and interrupts may occur at any time, a <tt>true</tt> return
1374:      * does not guarantee that a future <tt>signal</tt> will awaken
1375:      * any threads.  This method is designed primarily for use in
1376:      * monitoring of the system state.
1377:      *
1378:      * @param condition the condition
1379:      * @return <tt>true</tt> if there are any waiting threads
1380:      * @throws IllegalMonitorStateException if exclusive synchronization
1381:      *         is not held
1382:      * @throws IllegalArgumentException if the given condition is
1383:      *         not associated with this synchronizer
1384:      * @throws NullPointerException if the condition is null
1385:      */
1386:     public final boolean hasWaiters(ConditionObject condition) {
1387:         if (!owns(condition))
1388:             throw new IllegalArgumentException("Not owner");
1389:         return condition.hasWaiters();
1390:     }
1391: 
1392:     /**
1393:      * Returns an estimate of the number of threads waiting on the
1394:      * given condition associated with this synchronizer. Note that
1395:      * because timeouts and interrupts may occur at any time, the
1396:      * estimate serves only as an upper bound on the actual number of
1397:      * waiters.  This method is designed for use in monitoring of the
1398:      * system state, not for synchronization control.
1399:      *
1400:      * @param condition the condition
1401:      * @return the estimated number of waiting threads
1402:      * @throws IllegalMonitorStateException if exclusive synchronization
1403:      *         is not held
1404:      * @throws IllegalArgumentException if the given condition is
1405:      *         not associated with this synchronizer
1406:      * @throws NullPointerException if the condition is null
1407:      */
1408:     public final int getWaitQueueLength(ConditionObject condition) {
1409:         if (!owns(condition))
1410:             throw new IllegalArgumentException("Not owner");
1411:         return condition.getWaitQueueLength();
1412:     }
1413: 
1414:     /**
1415:      * Returns a collection containing those threads that may be
1416:      * waiting on the given condition associated with this
1417:      * synchronizer.  Because the actual set of threads may change
1418:      * dynamically while constructing this result, the returned
1419:      * collection is only a best-effort estimate. The elements of the
1420:      * returned collection are in no particular order.
1421:      *
1422:      * @param condition the condition
1423:      * @return the collection of threads
1424:      * @throws IllegalMonitorStateException if exclusive synchronization
1425:      *         is not held
1426:      * @throws IllegalArgumentException if the given condition is
1427:      *         not associated with this synchronizer
1428:      * @throws NullPointerException if the condition is null
1429:      */
1430:     public final Collection<Thread> getWaitingThreads(ConditionObject condition) {
1431:         if (!owns(condition))
1432:             throw new IllegalArgumentException("Not owner");
1433:         return condition.getWaitingThreads();
1434:     }
1435: 
1436:     /**
1437:      * Condition implementation for a {@link
1438:      * AbstractQueuedLongSynchronizer} serving as the basis of a {@link
1439:      * Lock} implementation.
1440:      *
1441:      * <p>Method documentation for this class describes mechanics,
1442:      * not behavioral specifications from the point of view of Lock
1443:      * and Condition users. Exported versions of this class will in
1444:      * general need to be accompanied by documentation describing
1445:      * condition semantics that rely on those of the associated
1446:      * <tt>AbstractQueuedLongSynchronizer</tt>.
1447:      *
1448:      * <p>This class is Serializable, but all fields are transient,
1449:      * so deserialized conditions have no waiters.
1450:      *
1451:      * @since 1.6
1452:      */
1453:     public class ConditionObject implements Condition, java.io.Serializable {
1454:         private static final long serialVersionUID = 1173984872572414699L;
1455:         /** First node of condition queue. */
1456:         private transient Node firstWaiter;
1457:         /** Last node of condition queue. */
1458:         private transient Node lastWaiter;
1459: 
1460:         /**
1461:          * Creates a new <tt>ConditionObject</tt> instance.
1462:          */
1463:         public ConditionObject() { }
1464: 
1465:         // Internal methods
1466: 
1467:         /**
1468:          * Adds a new waiter to wait queue.
1469:          * @return its new wait node
1470:          */
1471:         private Node addConditionWaiter() {
1472:             Node node = new Node(Thread.currentThread(), Node.CONDITION);
1473:             Node t = lastWaiter;
1474:             if (t == null)
1475:                 firstWaiter = node;
1476:             else
1477:                 t.nextWaiter = node;
1478:             lastWaiter = node;
1479:             return node;
1480:         }
1481: 
1482:         /**
1483:          * Removes and transfers nodes until hit non-cancelled one or
1484:          * null. Split out from signal in part to encourage compilers
1485:          * to inline the case of no waiters.
1486:          * @param first (non-null) the first node on condition queue
1487:          */
1488:         private void doSignal(Node first) {
1489:             do {
1490:                 if ( (firstWaiter = first.nextWaiter) == null)
1491:                     lastWaiter = null;
1492:                 first.nextWaiter = null;
1493:             } while (!transferForSignal(first) &&
1494:                      (first = firstWaiter) != null);
1495:         }
1496: 
1497:         /**
1498:          * Removes and transfers all nodes.
1499:          * @param first (non-null) the first node on condition queue
1500:          */
1501:         private void doSignalAll(Node first) {
1502:             lastWaiter = firstWaiter  = null;
1503:             do {
1504:                 Node next = first.nextWaiter;
1505:                 first.nextWaiter = null;
1506:                 transferForSignal(first);
1507:                 first = next;
1508:             } while (first != null);
1509:         }
1510: 
1511:         /**
1512:          * Returns true if given node is on this condition queue.
1513:          * Call only when holding lock.
1514:          */
1515:         private boolean isOnConditionQueue(Node node) {
1516:             return node.next != null || node == lastWaiter;
1517:         }
1518: 
1519:         /**
1520:          * Unlinks a cancelled waiter node from condition queue.  This
1521:          * is called when cancellation occurred during condition wait,
1522:          * not lock wait, and is called only after lock has been
1523:          * re-acquired by a cancelled waiter and the node is not known
1524:          * to already have been dequeued.  It is needed to avoid
1525:          * garbage retention in the absence of signals. So even though
1526:          * it may require a full traversal, it comes into play only
1527:          * when timeouts or cancellations occur in the absence of
1528:          * signals.
1529:          */
1530:         private void unlinkCancelledWaiter(Node node) {
1531:             Node t = firstWaiter;
1532:             Node trail = null;
1533:             while (t != null) {
1534:                 if (t == node) {
1535:                     Node next = t.nextWaiter;
1536:                     if (trail == null)
1537:                         firstWaiter = next;
1538:                     else
1539:                         trail.nextWaiter = next;
1540:                     if (lastWaiter == node)
1541:                         lastWaiter = trail;
1542:                     break;
1543:                 }
1544:                 trail = t;
1545:                 t = t.nextWaiter;
1546:             }
1547:         }
1548: 
1549:         // public methods
1550: 
1551:         /**
1552:          * Moves the longest-waiting thread, if one exists, from the
1553:          * wait queue for this condition to the wait queue for the
1554:          * owning lock.
1555:          *
1556:          * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
1557:          *         returns {@code false}
1558:          */
1559:         public final void signal() {
1560:             if (!isHeldExclusively())
1561:                 throw new IllegalMonitorStateException();
1562:             Node first = firstWaiter;
1563:             if (first != null)
1564:                 doSignal(first);
1565:         }
1566: 
1567:         /**
1568:          * Moves all threads from the wait queue for this condition to
1569:          * the wait queue for the owning lock.
1570:          *
1571:          * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
1572:          *         returns {@code false}
1573:          */
1574:         public final void signalAll() {
1575:             if (!isHeldExclusively())
1576:                 throw new IllegalMonitorStateException();
1577:             Node first = firstWaiter;
1578:             if (first != null)
1579:                 doSignalAll(first);
1580:         }
1581: 
1582:         /**
1583:          * Implements uninterruptible condition wait.
1584:          * <ol>
1585:          * <li> Save lock state returned by {@link #getState}
1586:          * <li> Invoke {@link #release} with
1587:          *      saved state as argument, throwing
1588:          *      IllegalMonitorStateException if it fails.
1589:          * <li> Block until signalled
1590:          * <li> Reacquire by invoking specialized version of
1591:          *      {@link #acquire} with saved state as argument.
1592:          * </ol>
1593:          */
1594:         public final void awaitUninterruptibly() {
1595:             Node node = addConditionWaiter();
1596:             long savedState = fullyRelease(node);
1597:             boolean interrupted = false;
1598:             while (!isOnSyncQueue(node)) {
1599:                 LockSupport.park(this);
1600:                 if (Thread.interrupted())
1601:                     interrupted = true;
1602:             }
1603:             if (acquireQueued(node, savedState) || interrupted)
1604:                 selfInterrupt();
1605:         }
1606: 
1607:         /*
1608:          * For interruptible waits, we need to track whether to throw
1609:          * InterruptedException, if interrupted while blocked on
1610:          * condition, versus reinterrupt current thread, if
1611:          * interrupted while blocked waiting to re-acquire.
1612:          */
1613: 
1614:         /** Mode meaning to reinterrupt on exit from wait */
1615:         private static final int REINTERRUPT =  1;
1616:         /** Mode meaning to throw InterruptedException on exit from wait */
1617:         private static final int THROW_IE    = -1;
1618: 
1619:         /**
1620:          * Checks for interrupt, returning THROW_IE if interrupted
1621:          * before signalled, REINTERRUPT if after signalled, or
1622:          * 0 if not interrupted.
1623:          */
1624:         private int checkInterruptWhileWaiting(Node node) {
1625:             return (Thread.interrupted()) ?
1626:                 ((transferAfterCancelledWait(node))? THROW_IE : REINTERRUPT) :
1627:                 0;
1628:         }
1629: 
1630:         /**
1631:          * Throws InterruptedException, reinterrupts current thread, or
1632:          * does nothing, depending on mode.
1633:          */
1634:         private void reportInterruptAfterWait(int interruptMode)
1635:             throws InterruptedException {
1636:             if (interruptMode == THROW_IE)
1637:                 throw new InterruptedException();
1638:             else if (interruptMode == REINTERRUPT)
1639:                 selfInterrupt();
1640:         }
1641: 
1642:         /**
1643:          * Implements interruptible condition wait.
1644:          * <ol>
1645:          * <li> If current thread is interrupted, throw InterruptedException
1646:          * <li> Save lock state returned by {@link #getState}
1647:          * <li> Invoke {@link #release} with
1648:          *      saved state as argument, throwing
1649:          *      IllegalMonitorStateException  if it fails.
1650:          * <li> Block until signalled or interrupted
1651:          * <li> Reacquire by invoking specialized version of
1652:          *      {@link #acquire} with saved state as argument.
1653:          * <li> If interrupted while blocked in step 4, throw exception
1654:          * </ol>
1655:          */
1656:         public final void await() throws InterruptedException {
1657:             if (Thread.interrupted())
1658:                 throw new InterruptedException();
1659:             Node node = addConditionWaiter();
1660:             long savedState = fullyRelease(node);
1661:             int interruptMode = 0;
1662:             while (!isOnSyncQueue(node)) {
1663:                 LockSupport.park(this);
1664:                 if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
1665:                     break;
1666:             }
1667:             if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
1668:                 interruptMode = REINTERRUPT;
1669:             if (isOnConditionQueue(node))
1670:                 unlinkCancelledWaiter(node);
1671:             if (interruptMode != 0)
1672:                 reportInterruptAfterWait(interruptMode);
1673:         }
1674: 
1675:         /**
1676:          * Implements timed condition wait.
1677:          * <ol>
1678:          * <li> If current thread is interrupted, throw InterruptedException
1679:          * <li> Save lock state returned by {@link #getState}
1680:          * <li> Invoke {@link #release} with
1681:          *      saved state as argument, throwing
1682:          *      IllegalMonitorStateException  if it fails.
1683:          * <li> Block until signalled, interrupted, or timed out
1684:          * <li> Reacquire by invoking specialized version of
1685:          *      {@link #acquire} with saved state as argument.
1686:          * <li> If interrupted while blocked in step 4, throw InterruptedException
1687:          * </ol>
1688:          */
1689:         public final long awaitNanos(long nanosTimeout) throws InterruptedException {
1690:             if (Thread.interrupted())
1691:                 throw new InterruptedException();
1692:             Node node = addConditionWaiter();
1693:             long savedState = fullyRelease(node);
1694:             long lastTime = System.nanoTime();
1695:             int interruptMode = 0;
1696:             while (!isOnSyncQueue(node)) {
1697:                 if (nanosTimeout <= 0L) {
1698:                     transferAfterCancelledWait(node);
1699:                     break;
1700:                 }
1701:                 LockSupport.parkNanos(this, nanosTimeout);
1702:                 if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
1703:                     break;
1704: 
1705:                 long now = System.nanoTime();
1706:                 nanosTimeout -= now - lastTime;
1707:                 lastTime = now;
1708:             }
1709:             if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
1710:                 interruptMode = REINTERRUPT;
1711:             if (isOnConditionQueue(node))
1712:                 unlinkCancelledWaiter(node);
1713:             if (interruptMode != 0)
1714:                 reportInterruptAfterWait(interruptMode);
1715:             return nanosTimeout - (System.nanoTime() - lastTime);
1716:         }
1717: 
1718:         /**
1719:          * Implements absolute timed condition wait.
1720:          * <ol>
1721:          * <li> If current thread is interrupted, throw InterruptedException
1722:          * <li> Save lock state returned by {@link #getState}
1723:          * <li> Invoke {@link #release} with
1724:          *      saved state as argument, throwing
1725:          *      IllegalMonitorStateException  if it fails.
1726:          * <li> Block until signalled, interrupted, or timed out
1727:          * <li> Reacquire by invoking specialized version of
1728:          *      {@link #acquire} with saved state as argument.
1729:          * <li> If interrupted while blocked in step 4, throw InterruptedException
1730:          * <li> If timed out while blocked in step 4, return false, else true
1731:          * </ol>
1732:          */
1733:         public final boolean awaitUntil(Date deadline) throws InterruptedException {
1734:             if (deadline == null)
1735:                 throw new NullPointerException();
1736:             long abstime = deadline.getTime();
1737:             if (Thread.interrupted())
1738:                 throw new InterruptedException();
1739:             Node node = addConditionWaiter();
1740:             long savedState = fullyRelease(node);
1741:             boolean timedout = false;
1742:             int interruptMode = 0;
1743:             while (!isOnSyncQueue(node)) {
1744:                 if (System.currentTimeMillis() > abstime) {
1745:                     timedout = transferAfterCancelledWait(node);
1746:                     break;
1747:                 }
1748:                 LockSupport.parkUntil(this, abstime);
1749:                 if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
1750:                     break;
1751:             }
1752:             if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
1753:                 interruptMode = REINTERRUPT;
1754:             if (isOnConditionQueue(node))
1755:                 unlinkCancelledWaiter(node);
1756:             if (interruptMode != 0)
1757:                 reportInterruptAfterWait(interruptMode);
1758:             return !timedout;
1759:         }
1760: 
1761:         /**
1762:          * Implements timed condition wait.
1763:          * <ol>
1764:          * <li> If current thread is interrupted, throw InterruptedException
1765:          * <li> Save lock state returned by {@link #getState}
1766:          * <li> Invoke {@link #release} with
1767:          *      saved state as argument, throwing
1768:          *      IllegalMonitorStateException  if it fails.
1769:          * <li> Block until signalled, interrupted, or timed out
1770:          * <li> Reacquire by invoking specialized version of
1771:          *      {@link #acquire} with saved state as argument.
1772:          * <li> If interrupted while blocked in step 4, throw InterruptedException
1773:          * <li> If timed out while blocked in step 4, return false, else true
1774:          * </ol>
1775:          */
1776:         public final boolean await(long time, TimeUnit unit) throws InterruptedException {
1777:             if (unit == null)
1778:                 throw new NullPointerException();
1779:             long nanosTimeout = unit.toNanos(time);
1780:             if (Thread.interrupted())
1781:                 throw new InterruptedException();
1782:             Node node = addConditionWaiter();
1783:             long savedState = fullyRelease(node);
1784:             long lastTime = System.nanoTime();
1785:             boolean timedout = false;
1786:             int interruptMode = 0;
1787:             while (!isOnSyncQueue(node)) {
1788:                 if (nanosTimeout <= 0L) {
1789:                     timedout = transferAfterCancelledWait(node);
1790:                     break;
1791:                 }
1792:                 LockSupport.parkNanos(this, nanosTimeout);
1793:                 if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
1794:                     break;
1795:                 long now = System.nanoTime();
1796:                 nanosTimeout -= now - lastTime;
1797:                 lastTime = now;
1798:             }
1799:             if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
1800:                 interruptMode = REINTERRUPT;
1801:             if (isOnConditionQueue(node))
1802:                 unlinkCancelledWaiter(node);
1803:             if (interruptMode != 0)
1804:                 reportInterruptAfterWait(interruptMode);
1805:             return !timedout;
1806:         }
1807: 
1808:         //  support for instrumentation
1809: 
1810:         /**
1811:          * Returns true if this condition was created by the given
1812:          * synchronization object.
1813:          *
1814:          * @return {@code true} if owned
1815:          */
1816:         final boolean isOwnedBy(AbstractQueuedLongSynchronizer sync) {
1817:             return sync == AbstractQueuedLongSynchronizer.this;
1818:         }
1819: 
1820:         /**
1821:          * Queries whether any threads are waiting on this condition.
1822:          * Implements {@link AbstractQueuedLongSynchronizer#hasWaiters}.
1823:          *
1824:          * @return {@code true} if there are any waiting threads
1825:          * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
1826:          *         returns {@code false}
1827:          */
1828:         protected final boolean hasWaiters() {
1829:             if (!isHeldExclusively())
1830:                 throw new IllegalMonitorStateException();
1831:             for (Node w = firstWaiter; w != null; w = w.nextWaiter) {
1832:                 if (w.waitStatus == Node.CONDITION)
1833:                     return true;
1834:             }
1835:             return false;
1836:         }
1837: 
1838:         /**
1839:          * Returns an estimate of the number of threads waiting on
1840:          * this condition.
1841:          * Implements {@link AbstractQueuedLongSynchronizer#getWaitQueueLength}.
1842:          *
1843:          * @return the estimated number of waiting threads
1844:          * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
1845:          *         returns {@code false}
1846:          */
1847:         protected final int getWaitQueueLength() {
1848:             if (!isHeldExclusively())
1849:                 throw new IllegalMonitorStateException();
1850:             int n = 0;
1851:             for (Node w = firstWaiter; w != null; w = w.nextWaiter) {
1852:                 if (w.waitStatus == Node.CONDITION)
1853:                     ++n;
1854:             }
1855:             return n;
1856:         }
1857: 
1858:         /**
1859:          * Returns a collection containing those threads that may be
1860:          * waiting on this Condition.
1861:          * Implements {@link AbstractQueuedLongSynchronizer#getWaitingThreads}.
1862:          *
1863:          * @return the collection of threads
1864:          * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
1865:          *         returns {@code false}
1866:          */
1867:         protected final Collection<Thread> getWaitingThreads() {
1868:             if (!isHeldExclusively())
1869:                 throw new IllegalMonitorStateException();
1870:             ArrayList<Thread> list = new ArrayList<Thread>();
1871:             for (Node w = firstWaiter; w != null; w = w.nextWaiter) {
1872:                 if (w.waitStatus == Node.CONDITION) {
1873:                     Thread t = w.thread;
1874:                     if (t != null)
1875:                         list.add(t);
1876:                 }
1877:             }
1878:             return list;
1879:         }
1880:     }
1881: 
1882:     /**
1883:      * Setup to support compareAndSet. We need to natively implement
1884:      * this here: For the sake of permitting future enhancements, we
1885:      * cannot explicitly subclass AtomicLong, which would be
1886:      * efficient and useful otherwise. So, as the lesser of evils, we
1887:      * natively implement using hotspot intrinsics API. And while we
1888:      * are at it, we do the same for other CASable fields (which could
1889:      * otherwise be done with atomic field updaters).
1890:      */
1891:     private static final Unsafe unsafe = Unsafe.getUnsafe();
1892:     private static final long stateOffset;
1893:     private static final long headOffset;
1894:     private static final long tailOffset;
1895:     private static final long waitStatusOffset;
1896: 
1897:     static {
1898:         try {
1899:             stateOffset = unsafe.objectFieldOffset
1900:                 (AbstractQueuedLongSynchronizer.class.getDeclaredField("state"));
1901:             headOffset = unsafe.objectFieldOffset
1902:                 (AbstractQueuedLongSynchronizer.class.getDeclaredField("head"));
1903:             tailOffset = unsafe.objectFieldOffset
1904:                 (AbstractQueuedLongSynchronizer.class.getDeclaredField("tail"));
1905:             waitStatusOffset = unsafe.objectFieldOffset
1906:                 (Node.class.getDeclaredField("waitStatus"));
1907: 
1908:         } catch (Exception ex) { throw new Error(ex); }
1909:     }
1910: 
1911:     /**
1912:      * CAS head field. Used only by enq
1913:      */
1914:     private final boolean compareAndSetHead(Node update) {
1915:         return unsafe.compareAndSwapObject(this, headOffset, null, update);
1916:     }
1917: 
1918:     /**
1919:      * CAS tail field. Used only by enq
1920:      */
1921:     private final boolean compareAndSetTail(Node expect, Node update) {
1922:         return unsafe.compareAndSwapObject(this, tailOffset, expect, update);
1923:     }
1924: 
1925:     /**
1926:      * CAS waitStatus field of a node.
1927:      */
1928:     private final static boolean compareAndSetWaitStatus(Node node,
1929:                                                          int expect,
1930:                                                          int update) {
1931:         return unsafe.compareAndSwapInt(node, waitStatusOffset,
1932:                                         expect, update);
1933:     }
1934: }