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) throws InterruptedException {

 994         if (Thread.interrupted())
 995             throw new InterruptedException();
 996         if (!tryAcquire(arg))
 997             doAcquireInterruptibly(arg);
 998     }
 999 
1000     /**
1001      * Attempts to acquire in exclusive mode, aborting if interrupted,
1002      * and failing if the given timeout elapses.  Implemented by first
1003      * checking interrupt status, then invoking at least once {@link
1004      * #tryAcquire}, returning on success.  Otherwise, the thread is
1005      * queued, possibly repeatedly blocking and unblocking, invoking
1006      * {@link #tryAcquire} until success or the thread is interrupted
1007      * or the timeout elapses.  This method can be used to implement
1008      * method {@link Lock#tryLock(long, TimeUnit)}.
1009      *
1010      * @param arg the acquire argument.  This value is conveyed to
1011      *        {@link #tryAcquire} but is otherwise uninterpreted and
1012      *        can represent anything you like.
1013      * @param nanosTimeout the maximum number of nanoseconds to wait
1014      * @return {@code true} if acquired; {@code false} if timed out
1015      * @throws InterruptedException if the current thread is interrupted
1016      */
1017     public final boolean tryAcquireNanos(long arg, long nanosTimeout) throws InterruptedException {

1018         if (Thread.interrupted())
1019             throw new InterruptedException();
1020         return tryAcquire(arg) ||
1021             doAcquireNanos(arg, nanosTimeout);
1022     }
1023 
1024     /**
1025      * Releases in exclusive mode.  Implemented by unblocking one or
1026      * more threads if {@link #tryRelease} returns true.
1027      * This method can be used to implement method {@link Lock#unlock}.
1028      *
1029      * @param arg the release argument.  This value is conveyed to
1030      *        {@link #tryRelease} but is otherwise uninterpreted and
1031      *        can represent anything you like.
1032      * @return the value returned from {@link #tryRelease}
1033      */
1034     public final boolean release(long arg) {
1035         if (tryRelease(arg)) {
1036             Node h = head;
1037             if (h != null && h.waitStatus != 0)
1038                 unparkSuccessor(h);
1039             return true;
1040         }
1041         return false;
1042     }
1043 
1044     /**
1045      * Acquires in shared mode, ignoring interrupts.  Implemented by
1046      * first invoking at least once {@link #tryAcquireShared},
1047      * returning on success.  Otherwise the thread is queued, possibly
1048      * repeatedly blocking and unblocking, invoking {@link
1049      * #tryAcquireShared} until success.
1050      *
1051      * @param arg the acquire argument.  This value is conveyed to
1052      *        {@link #tryAcquireShared} but is otherwise uninterpreted
1053      *        and can represent anything you like.
1054      */
1055     public final void acquireShared(long arg) {
1056         if (tryAcquireShared(arg) < 0)
1057             doAcquireShared(arg);
1058     }
1059 
1060     /**
1061      * Acquires in shared mode, aborting if interrupted.  Implemented
1062      * by first checking interrupt status, then invoking at least once
1063      * {@link #tryAcquireShared}, returning on success.  Otherwise the
1064      * thread is queued, possibly repeatedly blocking and unblocking,
1065      * invoking {@link #tryAcquireShared} until success or the thread
1066      * is interrupted.
1067      * @param arg the acquire argument
1068      * This value is conveyed to {@link #tryAcquireShared} but is
1069      * otherwise uninterpreted and can represent anything
1070      * you like.
1071      * @throws InterruptedException if the current thread is interrupted
1072      */
1073     public final void acquireSharedInterruptibly(long arg) throws InterruptedException {

1074         if (Thread.interrupted())
1075             throw new InterruptedException();
1076         if (tryAcquireShared(arg) < 0)
1077             doAcquireSharedInterruptibly(arg);
1078     }
1079 
1080     /**
1081      * Attempts to acquire in shared mode, aborting if interrupted, and
1082      * failing if the given timeout elapses.  Implemented by first
1083      * checking interrupt status, then invoking at least once {@link
1084      * #tryAcquireShared}, returning on success.  Otherwise, the
1085      * thread is queued, possibly repeatedly blocking and unblocking,
1086      * invoking {@link #tryAcquireShared} until success or the thread
1087      * is interrupted or the timeout elapses.
1088      *
1089      * @param arg the acquire argument.  This value is conveyed to
1090      *        {@link #tryAcquireShared} but is otherwise uninterpreted
1091      *        and can represent anything you like.
1092      * @param nanosTimeout the maximum number of nanoseconds to wait
1093      * @return {@code true} if acquired; {@code false} if timed out
1094      * @throws InterruptedException if the current thread is interrupted
1095      */
1096     public final boolean tryAcquireSharedNanos(long arg, long nanosTimeout) throws InterruptedException {

1097         if (Thread.interrupted())
1098             throw new InterruptedException();
1099         return tryAcquireShared(arg) >= 0 ||
1100             doAcquireSharedNanos(arg, nanosTimeout);
1101     }
1102 
1103     /**
1104      * Releases in shared mode.  Implemented by unblocking one or more
1105      * threads if {@link #tryReleaseShared} returns true.
1106      *
1107      * @param arg the release argument.  This value is conveyed to
1108      *        {@link #tryReleaseShared} but is otherwise uninterpreted
1109      *        and can represent anything you like.
1110      * @return the value returned from {@link #tryReleaseShared}
1111      */
1112     public final boolean releaseShared(long arg) {
1113         if (tryReleaseShared(arg)) {
1114             doReleaseShared();
1115             return true;
1116         }
1117         return false;
1118     }
1119 
1120     // Queue inspection methods
1121 
1122     /**
1123      * Queries whether any threads are waiting to acquire. Note that
1124      * because cancellations due to interrupts and timeouts may occur
1125      * at any time, a {@code true} return does not guarantee that any
1126      * other thread will ever acquire.
1127      *
1128      * <p>In this implementation, this operation returns in
1129      * constant time.
1130      *
1131      * @return {@code true} if there may be other threads waiting to acquire
1132      */
1133     public final boolean hasQueuedThreads() {
1134         return head != tail;
1135     }
1136 
1137     /**
1138      * Queries whether any threads have ever contended to acquire this
1139      * synchronizer; that is if an acquire method has ever blocked.
1140      *
1141      * <p>In this implementation, this operation returns in
1142      * constant time.
1143      *
1144      * @return {@code true} if there has ever been contention
1145      */
1146     public final boolean hasContended() {
1147         return head != null;
1148     }
1149 
1150     /**
1151      * Returns the first (longest-waiting) thread in the queue, or
1152      * {@code null} if no threads are currently queued.
1153      *
1154      * <p>In this implementation, this operation normally returns in
1155      * constant time, but may iterate upon contention if other threads are
1156      * concurrently modifying the queue.
1157      *
1158      * @return the first (longest-waiting) thread in the queue, or
1159      *         {@code null} if no threads are currently queued
1160      */
1161     public final Thread getFirstQueuedThread() {
1162         // handle only fast path, else relay
1163         return (head == tail) ? null : fullGetFirstQueuedThread();
1164     }
1165 
1166     /**
1167      * Version of getFirstQueuedThread called when fastpath fails
1168      */
1169     private Thread fullGetFirstQueuedThread() {
1170         /*
1171          * The first node is normally head.next. Try to get its
1172          * thread field, ensuring consistent reads: If thread
1173          * field is nulled out or s.prev is no longer head, then
1174          * some other thread(s) concurrently performed setHead in
1175          * between some of our reads. We try this twice before
1176          * resorting to traversal.
1177          */
1178         Node h, s;
1179         Thread st;
1180         if (((h = head) != null && (s = h.next) != null &&
1181              s.prev == head && (st = s.thread) != null) ||
1182             ((h = head) != null && (s = h.next) != null &&
1183              s.prev == head && (st = s.thread) != null))
1184             return st;
1185 
1186         /*
1187          * Head's next field might not have been set yet, or may have
1188          * been unset after setHead. So we must check to see if tail
1189          * is actually first node. If not, we continue on, safely
1190          * traversing from tail back to head to find first,
1191          * guaranteeing termination.
1192          */
1193 
1194         Node t = tail;
1195         Thread firstThread = null;
1196         while (t != null && t != head) {
1197             Thread tt = t.thread;
1198             if (tt != null)
1199                 firstThread = tt;
1200             t = t.prev;
1201         }
1202         return firstThread;
1203     }
1204 
1205     /**
1206      * Returns true if the given thread is currently queued.
1207      *
1208      * <p>This implementation traverses the queue to determine
1209      * presence of the given thread.
1210      *
1211      * @param thread the thread
1212      * @return {@code true} if the given thread is on the queue
1213      * @throws NullPointerException if the thread is null
1214      */
1215     public final boolean isQueued(Thread thread) {
1216         if (thread == null)
1217             throw new NullPointerException();
1218         for (Node p = tail; p != null; p = p.prev)
1219             if (p.thread == thread)
1220                 return true;
1221         return false;
1222     }
1223 
1224     /**
1225      * Returns {@code true} if the apparent first queued thread, if one
1226      * exists, is waiting in exclusive mode.  If this method returns
1227      * {@code true}, and the current thread is attempting to acquire in
1228      * shared mode (that is, this method is invoked from {@link
1229      * #tryAcquireShared}) then it is guaranteed that the current thread
1230      * is not the first queued thread.  Used only as a heuristic in
1231      * ReentrantReadWriteLock.
1232      */
1233     final boolean apparentlyFirstQueuedIsExclusive() {
1234         Node h, s;
1235         return (h = head) != null &&
1236             (s = h.next)  != null &&
1237             !s.isShared()         &&
1238             s.thread != null;
1239     }
1240 
1241     /**
1242      * Queries whether any threads have been waiting to acquire longer
1243      * than the current thread.
1244      *
1245      * <p>An invocation of this method is equivalent to (but may be
1246      * more efficient than):
1247      *  <pre> {@code
1248      * getFirstQueuedThread() != Thread.currentThread() &&
1249      * hasQueuedThreads()}</pre>
1250      *
1251      * <p>Note that because cancellations due to interrupts and
1252      * timeouts may occur at any time, a {@code true} return does not
1253      * guarantee that some other thread will acquire before the current
1254      * thread.  Likewise, it is possible for another thread to win a
1255      * race to enqueue after this method has returned {@code false},
1256      * due to the queue being empty.
1257      *
1258      * <p>This method is designed to be used by a fair synchronizer to
1259      * avoid <a href="AbstractQueuedSynchronizer#barging">barging</a>.
1260      * Such a synchronizer's {@link #tryAcquire} method should return
1261      * {@code false}, and its {@link #tryAcquireShared} method should
1262      * return a negative value, if this method returns {@code true}
1263      * (unless this is a reentrant acquire).  For example, the {@code
1264      * tryAcquire} method for a fair, reentrant, exclusive mode
1265      * synchronizer might look like this:
1266      *
1267      *  <pre> {@code
1268      * protected boolean tryAcquire(int arg) {
1269      *   if (isHeldExclusively()) {
1270      *     // A reentrant acquire; increment hold count
1271      *     return true;
1272      *   } else if (hasQueuedPredecessors()) {
1273      *     return false;
1274      *   } else {
1275      *     // try to acquire normally
1276      *   }
1277      * }}</pre>
1278      *
1279      * @return {@code true} if there is a queued thread preceding the
1280      *         current thread, and {@code false} if the current thread
1281      *         is at the head of the queue or the queue is empty
1282      * @since 1.7
1283      */
1284     public final boolean hasQueuedPredecessors() {
1285         // The correctness of this depends on head being initialized
1286         // before tail and on head.next being accurate if the current
1287         // thread is first in queue.
1288         Node t = tail; // Read fields in reverse initialization order
1289         Node h = head;
1290         Node s;
1291         return h != t &&
1292             ((s = h.next) == null || s.thread != Thread.currentThread());
1293     }
1294 
1295 
1296     // Instrumentation and monitoring methods
1297 
1298     /**
1299      * Returns an estimate of the number of threads waiting to
1300      * acquire.  The value is only an estimate because the number of
1301      * threads may change dynamically while this method traverses
1302      * internal data structures.  This method is designed for use in
1303      * monitoring system state, not for synchronization
1304      * control.
1305      *
1306      * @return the estimated number of threads waiting to acquire
1307      */
1308     public final int getQueueLength() {
1309         int n = 0;
1310         for (Node p = tail; p != null; p = p.prev) {
1311             if (p.thread != null)
1312                 ++n;
1313         }
1314         return n;
1315     }
1316 
1317     /**
1318      * Returns a collection containing threads that may be waiting to
1319      * acquire.  Because the actual set of threads may change
1320      * dynamically while constructing this result, the returned
1321      * collection is only a best-effort estimate.  The elements of the
1322      * returned collection are in no particular order.  This method is
1323      * designed to facilitate construction of subclasses that provide
1324      * more extensive monitoring facilities.
1325      *
1326      * @return the collection of threads
1327      */
1328     public final Collection<Thread> getQueuedThreads() {
1329         ArrayList<Thread> list = new ArrayList<Thread>();
1330         for (Node p = tail; p != null; p = p.prev) {
1331             Thread t = p.thread;
1332             if (t != null)
1333                 list.add(t);
1334         }
1335         return list;
1336     }
1337 
1338     /**
1339      * Returns a collection containing threads that may be waiting to
1340      * acquire in exclusive mode. This has the same properties
1341      * as {@link #getQueuedThreads} except that it only returns
1342      * those threads waiting due to an exclusive acquire.
1343      *
1344      * @return the collection of threads
1345      */
1346     public final Collection<Thread> getExclusiveQueuedThreads() {
1347         ArrayList<Thread> list = new ArrayList<Thread>();
1348         for (Node p = tail; p != null; p = p.prev) {
1349             if (!p.isShared()) {
1350                 Thread t = p.thread;
1351                 if (t != null)
1352                     list.add(t);
1353             }
1354         }
1355         return list;
1356     }
1357 
1358     /**
1359      * Returns a collection containing threads that may be waiting to
1360      * acquire in shared mode. This has the same properties
1361      * as {@link #getQueuedThreads} except that it only returns
1362      * those threads waiting due to a shared acquire.
1363      *
1364      * @return the collection of threads
1365      */
1366     public final Collection<Thread> getSharedQueuedThreads() {
1367         ArrayList<Thread> list = new ArrayList<Thread>();
1368         for (Node p = tail; p != null; p = p.prev) {
1369             if (p.isShared()) {
1370                 Thread t = p.thread;
1371                 if (t != null)
1372                     list.add(t);
1373             }
1374         }
1375         return list;
1376     }
1377 
1378     /**
1379      * Returns a string identifying this synchronizer, as well as its state.
1380      * The state, in brackets, includes the String {@code "State ="}
1381      * followed by the current value of {@link #getState}, and either
1382      * {@code "nonempty"} or {@code "empty"} depending on whether the
1383      * queue is empty.
1384      *
1385      * @return a string identifying this synchronizer, as well as its state
1386      */
1387     public String toString() {
1388         long s = getState();
1389         String q  = hasQueuedThreads() ? "non" : "";
1390         return super.toString() +
1391             "[State = " + s + ", " + q + "empty queue]";
1392     }
1393 
1394 
1395     // Internal support methods for Conditions
1396 
1397     /**
1398      * Returns true if a node, always one that was initially placed on
1399      * a condition queue, is now waiting to reacquire on sync queue.
1400      * @param node the node
1401      * @return true if is reacquiring
1402      */
1403     final boolean isOnSyncQueue(Node node) {
1404         if (node.waitStatus == Node.CONDITION || node.prev == null)
1405             return false;
1406         if (node.next != null) // If has successor, it must be on queue
1407             return true;
1408         /*
1409          * node.prev can be non-null, but not yet on queue because
1410          * the CAS to place it on queue can fail. So we have to
1411          * traverse from tail to make sure it actually made it.  It
1412          * will always be near the tail in calls to this method, and
1413          * unless the CAS failed (which is unlikely), it will be
1414          * there, so we hardly ever traverse much.
1415          */
1416         return findNodeFromTail(node);
1417     }
1418 
1419     /**
1420      * Returns true if node is on sync queue by searching backwards from tail.
1421      * Called only when needed by isOnSyncQueue.
1422      * @return true if present
1423      */
1424     private boolean findNodeFromTail(Node node) {
1425         Node t = tail;
1426         for (;;) {
1427             if (t == node)
1428                 return true;
1429             if (t == null)
1430                 return false;
1431             t = t.prev;
1432         }
1433     }
1434 
1435     /**
1436      * Transfers a node from a condition queue onto sync queue.
1437      * Returns true if successful.
1438      * @param node the node
1439      * @return true if successfully transferred (else the node was
1440      * cancelled before signal).
1441      */
1442     final boolean transferForSignal(Node node) {
1443         /*
1444          * If cannot change waitStatus, the node has been cancelled.
1445          */
1446         if (!compareAndSetWaitStatus(node, Node.CONDITION, 0))
1447             return false;
1448 
1449         /*
1450          * Splice onto queue and try to set waitStatus of predecessor to
1451          * indicate that thread is (probably) waiting. If cancelled or
1452          * attempt to set waitStatus fails, wake up to resync (in which
1453          * case the waitStatus can be transiently and harmlessly wrong).
1454          */
1455         Node p = enq(node);
1456         int ws = p.waitStatus;
1457         if (ws > 0 || !compareAndSetWaitStatus(p, ws, Node.SIGNAL))
1458             LockSupport.unpark(node.thread);
1459         return true;
1460     }
1461 
1462     /**
1463      * Transfers node, if necessary, to sync queue after a cancelled
1464      * wait. Returns true if thread was cancelled before being
1465      * signalled.
1466      * @param current the waiting thread
1467      * @param node its node
1468      * @return true if cancelled before the node was signalled
1469      */
1470     final boolean transferAfterCancelledWait(Node node) {
1471         if (compareAndSetWaitStatus(node, Node.CONDITION, 0)) {
1472             enq(node);
1473             return true;
1474         }
1475         /*
1476          * If we lost out to a signal(), then we can't proceed
1477          * until it finishes its enq().  Cancelling during an
1478          * incomplete transfer is both rare and transient, so just
1479          * spin.
1480          */
1481         while (!isOnSyncQueue(node))
1482             Thread.yield();
1483         return false;
1484     }
1485 
1486     /**
1487      * Invokes release with current state value; returns saved state.
1488      * Cancels node and throws exception on failure.
1489      * @param node the condition node for this wait
1490      * @return previous sync state
1491      */
1492     final long fullyRelease(Node node) {
1493         boolean failed = true;
1494         try {
1495             long savedState = getState();
1496             if (release(savedState)) {
1497                 failed = false;
1498                 return savedState;
1499             } else {
1500                 throw new IllegalMonitorStateException();
1501             }
1502         } finally {
1503             if (failed)
1504                 node.waitStatus = Node.CANCELLED;
1505         }
1506     }
1507 
1508     // Instrumentation methods for conditions
1509 
1510     /**
1511      * Queries whether the given ConditionObject
1512      * uses this synchronizer as its lock.
1513      *
1514      * @param condition the condition
1515      * @return <tt>true</tt> if owned
1516      * @throws NullPointerException if the condition is null
1517      */
1518     public final boolean owns(ConditionObject condition) {
1519         if (condition == null)
1520             throw new NullPointerException();
1521         return condition.isOwnedBy(this);
1522     }
1523 
1524     /**
1525      * Queries whether any threads are waiting on the given condition
1526      * associated with this synchronizer. Note that because timeouts
1527      * and interrupts may occur at any time, a <tt>true</tt> return
1528      * does not guarantee that a future <tt>signal</tt> will awaken
1529      * any threads.  This method is designed primarily for use in
1530      * monitoring of the system state.
1531      *
1532      * @param condition the condition
1533      * @return <tt>true</tt> if there are any waiting threads
1534      * @throws IllegalMonitorStateException if exclusive synchronization
1535      *         is not held
1536      * @throws IllegalArgumentException if the given condition is
1537      *         not associated with this synchronizer
1538      * @throws NullPointerException if the condition is null
1539      */
1540     public final boolean hasWaiters(ConditionObject condition) {
1541         if (!owns(condition))
1542             throw new IllegalArgumentException("Not owner");
1543         return condition.hasWaiters();
1544     }
1545 
1546     /**
1547      * Returns an estimate of the number of threads waiting on the
1548      * given condition associated with this synchronizer. Note that
1549      * because timeouts and interrupts may occur at any time, the
1550      * estimate serves only as an upper bound on the actual number of
1551      * waiters.  This method is designed for use in monitoring of the
1552      * system state, not for synchronization control.
1553      *
1554      * @param condition the condition
1555      * @return the estimated number of waiting threads
1556      * @throws IllegalMonitorStateException if exclusive synchronization
1557      *         is not held
1558      * @throws IllegalArgumentException if the given condition is
1559      *         not associated with this synchronizer
1560      * @throws NullPointerException if the condition is null
1561      */
1562     public final int getWaitQueueLength(ConditionObject condition) {
1563         if (!owns(condition))
1564             throw new IllegalArgumentException("Not owner");
1565         return condition.getWaitQueueLength();
1566     }
1567 
1568     /**
1569      * Returns a collection containing those threads that may be
1570      * waiting on the given condition associated with this
1571      * synchronizer.  Because the actual set of threads may change
1572      * dynamically while constructing this result, the returned
1573      * collection is only a best-effort estimate. The elements of the
1574      * returned collection are in no particular order.
1575      *
1576      * @param condition the condition
1577      * @return the collection of threads
1578      * @throws IllegalMonitorStateException if exclusive synchronization
1579      *         is not held
1580      * @throws IllegalArgumentException if the given condition is
1581      *         not associated with this synchronizer
1582      * @throws NullPointerException if the condition is null
1583      */
1584     public final Collection<Thread> getWaitingThreads(ConditionObject condition) {
1585         if (!owns(condition))
1586             throw new IllegalArgumentException("Not owner");
1587         return condition.getWaitingThreads();
1588     }
1589 
1590     /**
1591      * Condition implementation for a {@link
1592      * AbstractQueuedLongSynchronizer} serving as the basis of a {@link
1593      * Lock} implementation.
1594      *
1595      * <p>Method documentation for this class describes mechanics,
1596      * not behavioral specifications from the point of view of Lock
1597      * and Condition users. Exported versions of this class will in
1598      * general need to be accompanied by documentation describing
1599      * condition semantics that rely on those of the associated
1600      * <tt>AbstractQueuedLongSynchronizer</tt>.
1601      *
1602      * <p>This class is Serializable, but all fields are transient,
1603      * so deserialized conditions have no waiters.
1604      *
1605      * @since 1.6
1606      */
1607     public class ConditionObject implements Condition, java.io.Serializable {
1608         private static final long serialVersionUID = 1173984872572414699L;
1609         /** First node of condition queue. */
1610         private transient Node firstWaiter;
1611         /** Last node of condition queue. */
1612         private transient Node lastWaiter;
1613 
1614         /**
1615          * Creates a new <tt>ConditionObject</tt> instance.
1616          */
1617         public ConditionObject() { }
1618 
1619         // Internal methods
1620 
1621         /**
1622          * Adds a new waiter to wait queue.
1623          * @return its new wait node
1624          */
1625         private Node addConditionWaiter() {
1626             Node t = lastWaiter;
1627             // If lastWaiter is cancelled, clean out.
1628             if (t != null && t.waitStatus != Node.CONDITION) {
1629                 unlinkCancelledWaiters();
1630                 t = lastWaiter;
1631             }
1632             Node node = new Node(Thread.currentThread(), Node.CONDITION);
1633             if (t == null)
1634                 firstWaiter = node;
1635             else
1636                 t.nextWaiter = node;
1637             lastWaiter = node;
1638             return node;
1639         }
1640 
1641         /**
1642          * Removes and transfers nodes until hit non-cancelled one or
1643          * null. Split out from signal in part to encourage compilers
1644          * to inline the case of no waiters.
1645          * @param first (non-null) the first node on condition queue
1646          */
1647         private void doSignal(Node first) {
1648             do {
1649                 if ( (firstWaiter = first.nextWaiter) == null)
1650                     lastWaiter = null;
1651                 first.nextWaiter = null;
1652             } while (!transferForSignal(first) &&
1653                      (first = firstWaiter) != null);
1654         }
1655 
1656         /**
1657          * Removes and transfers all nodes.
1658          * @param first (non-null) the first node on condition queue
1659          */
1660         private void doSignalAll(Node first) {
1661             lastWaiter = firstWaiter = null;
1662             do {
1663                 Node next = first.nextWaiter;
1664                 first.nextWaiter = null;
1665                 transferForSignal(first);
1666                 first = next;
1667             } while (first != null);
1668         }
1669 
1670         /**
1671          * Unlinks cancelled waiter nodes from condition queue.
1672          * Called only while holding lock. This is called when
1673          * cancellation occurred during condition wait, and upon
1674          * insertion of a new waiter when lastWaiter is seen to have
1675          * been cancelled. This method is needed to avoid garbage
1676          * retention in the absence of signals. So even though it may
1677          * require a full traversal, it comes into play only when
1678          * timeouts or cancellations occur in the absence of
1679          * signals. It traverses all nodes rather than stopping at a
1680          * particular target to unlink all pointers to garbage nodes
1681          * without requiring many re-traversals during cancellation
1682          * storms.
1683          */
1684         private void unlinkCancelledWaiters() {
1685             Node t = firstWaiter;
1686             Node trail = null;
1687             while (t != null) {
1688                 Node next = t.nextWaiter;
1689                 if (t.waitStatus != Node.CONDITION) {
1690                     t.nextWaiter = null;
1691                     if (trail == null)
1692                         firstWaiter = next;
1693                     else
1694                         trail.nextWaiter = next;
1695                     if (next == null)
1696                         lastWaiter = trail;
1697                 }
1698                 else
1699                     trail = t;
1700                 t = next;
1701             }
1702         }
1703 
1704         // public methods
1705 
1706         /**
1707          * Moves the longest-waiting thread, if one exists, from the
1708          * wait queue for this condition to the wait queue for the
1709          * owning lock.
1710          *
1711          * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
1712          *         returns {@code false}
1713          */
1714         public final void signal() {
1715             if (!isHeldExclusively())
1716                 throw new IllegalMonitorStateException();
1717             Node first = firstWaiter;
1718             if (first != null)
1719                 doSignal(first);
1720         }
1721 
1722         /**
1723          * Moves all threads from the wait queue for this condition to
1724          * the wait queue for the owning lock.
1725          *
1726          * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
1727          *         returns {@code false}
1728          */
1729         public final void signalAll() {
1730             if (!isHeldExclusively())
1731                 throw new IllegalMonitorStateException();
1732             Node first = firstWaiter;
1733             if (first != null)
1734                 doSignalAll(first);
1735         }
1736 
1737         /**
1738          * Implements uninterruptible condition wait.
1739          * <ol>
1740          * <li> Save lock state returned by {@link #getState}.
1741          * <li> Invoke {@link #release} with
1742          *      saved state as argument, throwing
1743          *      IllegalMonitorStateException if it fails.
1744          * <li> Block until signalled.
1745          * <li> Reacquire by invoking specialized version of
1746          *      {@link #acquire} with saved state as argument.
1747          * </ol>
1748          */
1749         public final void awaitUninterruptibly() {
1750             Node node = addConditionWaiter();
1751             long savedState = fullyRelease(node);
1752             boolean interrupted = false;
1753             while (!isOnSyncQueue(node)) {
1754                 LockSupport.park(this);
1755                 if (Thread.interrupted())
1756                     interrupted = true;
1757             }
1758             if (acquireQueued(node, savedState) || interrupted)
1759                 selfInterrupt();
1760         }
1761 
1762         /*
1763          * For interruptible waits, we need to track whether to throw
1764          * InterruptedException, if interrupted while blocked on
1765          * condition, versus reinterrupt current thread, if
1766          * interrupted while blocked waiting to re-acquire.
1767          */
1768 
1769         /** Mode meaning to reinterrupt on exit from wait */
1770         private static final int REINTERRUPT =  1;
1771         /** Mode meaning to throw InterruptedException on exit from wait */
1772         private static final int THROW_IE    = -1;
1773 
1774         /**
1775          * Checks for interrupt, returning THROW_IE if interrupted
1776          * before signalled, REINTERRUPT if after signalled, or
1777          * 0 if not interrupted.
1778          */
1779         private int checkInterruptWhileWaiting(Node node) {
1780             return Thread.interrupted() ?
1781                 (transferAfterCancelledWait(node) ? THROW_IE : REINTERRUPT) :
1782                 0;
1783         }
1784 
1785         /**
1786          * Throws InterruptedException, reinterrupts current thread, or
1787          * does nothing, depending on mode.
1788          */
1789         private void reportInterruptAfterWait(int interruptMode)
1790             throws InterruptedException {
1791             if (interruptMode == THROW_IE)
1792                 throw new InterruptedException();
1793             else if (interruptMode == REINTERRUPT)
1794                 selfInterrupt();
1795         }
1796 
1797         /**
1798          * Implements interruptible condition wait.
1799          * <ol>
1800          * <li> If current thread is interrupted, throw InterruptedException.
1801          * <li> Save lock state returned by {@link #getState}.
1802          * <li> Invoke {@link #release} with
1803          *      saved state as argument, throwing
1804          *      IllegalMonitorStateException if it fails.
1805          * <li> Block until signalled or interrupted.
1806          * <li> Reacquire by invoking specialized version of
1807          *      {@link #acquire} with saved state as argument.
1808          * <li> If interrupted while blocked in step 4, throw InterruptedException.
1809          * </ol>
1810          */
1811         public final void await() throws InterruptedException {
1812             if (Thread.interrupted())
1813                 throw new InterruptedException();
1814             Node node = addConditionWaiter();
1815             long savedState = fullyRelease(node);
1816             int interruptMode = 0;
1817             while (!isOnSyncQueue(node)) {
1818                 LockSupport.park(this);
1819                 if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
1820                     break;
1821             }
1822             if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
1823                 interruptMode = REINTERRUPT;
1824             if (node.nextWaiter != null) // clean up if cancelled
1825                 unlinkCancelledWaiters();
1826             if (interruptMode != 0)
1827                 reportInterruptAfterWait(interruptMode);
1828         }
1829 
1830         /**
1831          * Implements timed condition wait.
1832          * <ol>
1833          * <li> If current thread is interrupted, throw InterruptedException.
1834          * <li> Save lock state returned by {@link #getState}.
1835          * <li> Invoke {@link #release} with
1836          *      saved state as argument, throwing
1837          *      IllegalMonitorStateException if it fails.
1838          * <li> Block until signalled, interrupted, or timed out.
1839          * <li> Reacquire by invoking specialized version of
1840          *      {@link #acquire} with saved state as argument.
1841          * <li> If interrupted while blocked in step 4, throw InterruptedException.
1842          * </ol>
1843          */
1844         public final long awaitNanos(long nanosTimeout) throws InterruptedException {

1845             if (Thread.interrupted())
1846                 throw new InterruptedException();
1847             Node node = addConditionWaiter();
1848             long savedState = fullyRelease(node);
1849             long lastTime = System.nanoTime();
1850             int interruptMode = 0;
1851             while (!isOnSyncQueue(node)) {
1852                 if (nanosTimeout <= 0L) {
1853                     transferAfterCancelledWait(node);
1854                     break;
1855                 }
1856                 LockSupport.parkNanos(this, nanosTimeout);
1857                 if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
1858                     break;
1859 
1860                 long now = System.nanoTime();
1861                 nanosTimeout -= now - lastTime;
1862                 lastTime = now;
1863             }
1864             if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
1865                 interruptMode = REINTERRUPT;
1866             if (node.nextWaiter != null)
1867                 unlinkCancelledWaiters();
1868             if (interruptMode != 0)
1869                 reportInterruptAfterWait(interruptMode);
1870             return nanosTimeout - (System.nanoTime() - lastTime);
1871         }
1872 
1873         /**
1874          * Implements absolute timed condition wait.
1875          * <ol>
1876          * <li> If current thread is interrupted, throw InterruptedException.
1877          * <li> Save lock state returned by {@link #getState}.
1878          * <li> Invoke {@link #release} with
1879          *      saved state as argument, throwing
1880          *      IllegalMonitorStateException if it fails.
1881          * <li> Block until signalled, interrupted, or timed out.
1882          * <li> Reacquire by invoking specialized version of
1883          *      {@link #acquire} with saved state as argument.
1884          * <li> If interrupted while blocked in step 4, throw InterruptedException.
1885          * <li> If timed out while blocked in step 4, return false, else true.
1886          * </ol>
1887          */
1888         public final boolean awaitUntil(Date deadline) throws InterruptedException {

1889             if (deadline == null)
1890                 throw new NullPointerException();
1891             long abstime = deadline.getTime();
1892             if (Thread.interrupted())
1893                 throw new InterruptedException();
1894             Node node = addConditionWaiter();
1895             long savedState = fullyRelease(node);
1896             boolean timedout = false;
1897             int interruptMode = 0;
1898             while (!isOnSyncQueue(node)) {
1899                 if (System.currentTimeMillis() > abstime) {
1900                     timedout = transferAfterCancelledWait(node);
1901                     break;
1902                 }
1903                 LockSupport.parkUntil(this, abstime);
1904                 if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
1905                     break;
1906             }
1907             if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
1908                 interruptMode = REINTERRUPT;
1909             if (node.nextWaiter != null)
1910                 unlinkCancelledWaiters();
1911             if (interruptMode != 0)
1912                 reportInterruptAfterWait(interruptMode);
1913             return !timedout;
1914         }
1915 
1916         /**
1917          * Implements timed condition wait.
1918          * <ol>
1919          * <li> If current thread is interrupted, throw InterruptedException.
1920          * <li> Save lock state returned by {@link #getState}.
1921          * <li> Invoke {@link #release} with
1922          *      saved state as argument, throwing
1923          *      IllegalMonitorStateException if it fails.
1924          * <li> Block until signalled, interrupted, or timed out.
1925          * <li> Reacquire by invoking specialized version of
1926          *      {@link #acquire} with saved state as argument.
1927          * <li> If interrupted while blocked in step 4, throw InterruptedException.
1928          * <li> If timed out while blocked in step 4, return false, else true.
1929          * </ol>
1930          */
1931         public final boolean await(long time, TimeUnit unit) throws InterruptedException {

1932             if (unit == null)
1933                 throw new NullPointerException();
1934             long nanosTimeout = unit.toNanos(time);
1935             if (Thread.interrupted())
1936                 throw new InterruptedException();
1937             Node node = addConditionWaiter();
1938             long savedState = fullyRelease(node);
1939             long lastTime = System.nanoTime();
1940             boolean timedout = false;
1941             int interruptMode = 0;
1942             while (!isOnSyncQueue(node)) {
1943                 if (nanosTimeout <= 0L) {
1944                     timedout = transferAfterCancelledWait(node);
1945                     break;
1946                 }
1947                 if (nanosTimeout >= spinForTimeoutThreshold)
1948                     LockSupport.parkNanos(this, nanosTimeout);
1949                 if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
1950                     break;
1951                 long now = System.nanoTime();
1952                 nanosTimeout -= now - lastTime;
1953                 lastTime = now;
1954             }
1955             if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
1956                 interruptMode = REINTERRUPT;
1957             if (node.nextWaiter != null)
1958                 unlinkCancelledWaiters();
1959             if (interruptMode != 0)
1960                 reportInterruptAfterWait(interruptMode);
1961             return !timedout;
1962         }
1963 
1964         //  support for instrumentation
1965 
1966         /**
1967          * Returns true if this condition was created by the given
1968          * synchronization object.
1969          *
1970          * @return {@code true} if owned
1971          */
1972         final boolean isOwnedBy(AbstractQueuedLongSynchronizer sync) {
1973             return sync == AbstractQueuedLongSynchronizer.this;
1974         }
1975 
1976         /**
1977          * Queries whether any threads are waiting on this condition.
1978          * Implements {@link AbstractQueuedLongSynchronizer#hasWaiters}.
1979          *
1980          * @return {@code true} if there are any waiting threads
1981          * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
1982          *         returns {@code false}
1983          */
1984         protected final boolean hasWaiters() {
1985             if (!isHeldExclusively())
1986                 throw new IllegalMonitorStateException();
1987             for (Node w = firstWaiter; w != null; w = w.nextWaiter) {
1988                 if (w.waitStatus == Node.CONDITION)
1989                     return true;
1990             }
1991             return false;
1992         }
1993 
1994         /**
1995          * Returns an estimate of the number of threads waiting on
1996          * this condition.
1997          * Implements {@link AbstractQueuedLongSynchronizer#getWaitQueueLength}.
1998          *
1999          * @return the estimated number of waiting threads
2000          * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
2001          *         returns {@code false}
2002          */
2003         protected final int getWaitQueueLength() {
2004             if (!isHeldExclusively())
2005                 throw new IllegalMonitorStateException();
2006             int n = 0;
2007             for (Node w = firstWaiter; w != null; w = w.nextWaiter) {
2008                 if (w.waitStatus == Node.CONDITION)
2009                     ++n;
2010             }
2011             return n;
2012         }
2013 
2014         /**
2015          * Returns a collection containing those threads that may be
2016          * waiting on this Condition.
2017          * Implements {@link AbstractQueuedLongSynchronizer#getWaitingThreads}.
2018          *
2019          * @return the collection of threads
2020          * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
2021          *         returns {@code false}
2022          */
2023         protected final Collection<Thread> getWaitingThreads() {
2024             if (!isHeldExclusively())
2025                 throw new IllegalMonitorStateException();
2026             ArrayList<Thread> list = new ArrayList<Thread>();
2027             for (Node w = firstWaiter; w != null; w = w.nextWaiter) {
2028                 if (w.waitStatus == Node.CONDITION) {
2029                     Thread t = w.thread;
2030                     if (t != null)
2031                         list.add(t);
2032                 }
2033             }
2034             return list;
2035         }
2036     }
2037 
2038     /**
2039      * Setup to support compareAndSet. We need to natively implement
2040      * this here: For the sake of permitting future enhancements, we
2041      * cannot explicitly subclass AtomicLong, which would be
2042      * efficient and useful otherwise. So, as the lesser of evils, we
2043      * natively implement using hotspot intrinsics API. And while we
2044      * are at it, we do the same for other CASable fields (which could
2045      * otherwise be done with atomic field updaters).
2046      */
2047     private static final Unsafe unsafe = Unsafe.getUnsafe();
2048     private static final long stateOffset;
2049     private static final long headOffset;
2050     private static final long tailOffset;
2051     private static final long waitStatusOffset;
2052     private static final long nextOffset;
2053 
2054     static {
2055         try {
2056             stateOffset = unsafe.objectFieldOffset
2057                 (AbstractQueuedLongSynchronizer.class.getDeclaredField("state"));
2058             headOffset = unsafe.objectFieldOffset
2059                 (AbstractQueuedLongSynchronizer.class.getDeclaredField("head"));
2060             tailOffset = unsafe.objectFieldOffset
2061                 (AbstractQueuedLongSynchronizer.class.getDeclaredField("tail"));
2062             waitStatusOffset = unsafe.objectFieldOffset
2063                 (Node.class.getDeclaredField("waitStatus"));
2064             nextOffset = unsafe.objectFieldOffset
2065                 (Node.class.getDeclaredField("next"));
2066 
2067         } catch (Exception ex) { throw new Error(ex); }
2068     }
2069 
2070     /**
2071      * CAS head field. Used only by enq.
2072      */
2073     private final boolean compareAndSetHead(Node update) {
2074         return unsafe.compareAndSwapObject(this, headOffset, null, update);
2075     }
2076 
2077     /**
2078      * CAS tail field. Used only by enq.
2079      */
2080     private final boolean compareAndSetTail(Node expect, Node update) {
2081         return unsafe.compareAndSwapObject(this, tailOffset, expect, update);
2082     }
2083 
2084     /**
2085      * CAS waitStatus field of a node.
2086      */
2087     private final static boolean compareAndSetWaitStatus(Node node,
2088                                                          int expect,
2089                                                          int update) {
2090         return unsafe.compareAndSwapInt(node, waitStatusOffset,
2091                                         expect, update);
2092     }
2093 
2094     /**
2095      * CAS next field of a node.
2096      */
2097     private final static boolean compareAndSetNext(Node node,
2098                                                    Node expect,
2099                                                    Node update) {
2100         return unsafe.compareAndSwapObject(node, nextOffset, expect, update);
2101     }
2102 }
--- EOF ---