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