2 * Written by Doug Lea with assistance from members of JCP JSR-166
3 * Expert Group and released to the public domain, as explained at
4 * http://creativecommons.org/licenses/publicdomain
7 package java.util.concurrent.locks;
9 import java.util.concurrent.*;
10 import java.util.concurrent.atomic.*;
11 import sun.misc.Unsafe;
14 * A version of {@link AbstractQueuedSynchronizer} in
15 * which synchronization state is maintained as a <tt>long</tt>.
16 * This class has exactly the same structure, properties, and methods
17 * as <tt>AbstractQueuedSynchronizer</tt> with the exception
18 * that all state-related parameters and results are defined
19 * as <tt>long</tt> rather than <tt>int</tt>. This class
20 * may be useful when creating synchronizers such as
21 * multilevel locks and barriers that require
24 * <p>See {@link AbstractQueuedSynchronizer} for usage
30 public abstract class AbstractQueuedLongSynchronizer
31 extends AbstractOwnableSynchronizer
32 implements java.io.Serializable {
34 private static final long serialVersionUID = 7373984972572414692L;
37 To keep sources in sync, the remainder of this source file is
38 exactly cloned from AbstractQueuedSynchronizer, replacing class
39 name and changing ints related with sync state to longs. Please
44 * Creates a new <tt>AbstractQueuedLongSynchronizer</tt> instance
45 * with initial synchronization state of zero.
47 protected AbstractQueuedLongSynchronizer() { }
50 * Wait queue node class.
52 * <p>The wait queue is a variant of a "CLH" (Craig, Landin, and
53 * Hagersten) lock queue. CLH locks are normally used for
54 * spinlocks. We instead use them for blocking synchronizers, but
55 * use the same basic tactic of holding some of the control
56 * information about a thread in the predecessor of its node. A
57 * "status" field in each node keeps track of whether a thread
58 * should block. A node is signalled when its predecessor
59 * releases. Each node of the queue otherwise serves as a
60 * specific-notification-style monitor holding a single waiting
61 * thread. The status field does NOT control whether threads are
62 * granted locks etc though. A thread may try to acquire if it is
63 * first in the queue. But being first does not guarantee success;
64 * it only gives the right to contend. So the currently released
65 * contender thread may need to rewait.
67 * <p>To enqueue into a CLH lock, you atomically splice it in as new
68 * tail. To dequeue, you just set the head field.
70 * +------+ prev +-----+ +-----+
71 * head | | <---- | | <---- | | tail
72 * +------+ +-----+ +-----+
75 * <p>Insertion into a CLH queue requires only a single atomic
76 * operation on "tail", so there is a simple atomic point of
77 * demarcation from unqueued to queued. Similarly, dequeing
78 * involves only updating the "head". However, it takes a bit
79 * more work for nodes to determine who their successors are,
80 * in part to deal with possible cancellation due to timeouts
83 * <p>The "prev" links (not used in original CLH locks), are mainly
84 * needed to handle cancellation. If a node is cancelled, its
85 * successor is (normally) relinked to a non-cancelled
86 * predecessor. For explanation of similar mechanics in the case
87 * of spin locks, see the papers by Scott and Scherer at
88 * http://www.cs.rochester.edu/u/scott/synchronization/
90 * <p>We also use "next" links to implement blocking mechanics.
91 * The thread id for each node is kept in its own node, so a
92 * predecessor signals the next node to wake up by traversing
93 * next link to determine which thread it is. Determination of
94 * successor must avoid races with newly queued nodes to set
95 * the "next" fields of their predecessors. This is solved
96 * when necessary by checking backwards from the atomically
97 * updated "tail" when a node's successor appears to be null.
98 * (Or, said differently, the next-links are an optimization
99 * so that we don't usually need a backward scan.)
101 * <p>Cancellation introduces some conservatism to the basic
102 * algorithms. Since we must poll for cancellation of other
103 * nodes, we can miss noticing whether a cancelled node is
104 * ahead or behind us. This is dealt with by always unparking
105 * successors upon cancellation, allowing them to stabilize on
108 * <p>CLH queues need a dummy header node to get started. But
109 * we don't create them on construction, because it would be wasted
110 * effort if there is never contention. Instead, the node
111 * is constructed and head and tail pointers are set upon first
114 * <p>Threads waiting on Conditions use the same nodes, but
115 * use an additional link. Conditions only need to link nodes
116 * in simple (non-concurrent) linked queues because they are
117 * only accessed when exclusively held. Upon await, a node is
118 * inserted into a condition queue. Upon signal, the node is
119 * transferred to the main queue. A special value of status
120 * field is used to mark which queue a node is on.
122 * <p>Thanks go to Dave Dice, Mark Moir, Victor Luchangco, Bill
123 * Scherer and Michael Scott, along with members of JSR-166
124 * expert group, for helpful ideas, discussions, and critiques
125 * on the design of this class.
127 static final class Node {
128 /** waitStatus value to indicate thread has cancelled */
129 static final int CANCELLED = 1;
130 /** waitStatus value to indicate successor's thread needs unparking */
131 static final int SIGNAL = -1;
132 /** waitStatus value to indicate thread is waiting on condition */
133 static final int CONDITION = -2;
134 /** Marker to indicate a node is waiting in shared mode */
135 static final Node SHARED = new Node();
136 /** Marker to indicate a node is waiting in exclusive mode */
137 static final Node EXCLUSIVE = null;
140 * Status field, taking on only the values:
141 * SIGNAL: The successor of this node is (or will soon be)
142 * blocked (via park), so the current node must
143 * unpark its successor when it releases or
144 * cancels. To avoid races, acquire methods must
145 * first indicate they need a signal,
146 * then retry the atomic acquire, and then,
148 * CANCELLED: This node is cancelled due to timeout or interrupt.
149 * Nodes never leave this state. In particular,
150 * a thread with cancelled node never again blocks.
151 * CONDITION: This node is currently on a condition queue.
152 * It will not be used as a sync queue node until
153 * transferred. (Use of this value here
154 * has nothing to do with the other uses
155 * of the field, but simplifies mechanics.)
156 * 0: None of the above
158 * The values are arranged numerically to simplify use.
159 * Non-negative values mean that a node doesn't need to
160 * signal. So, most code doesn't need to check for particular
161 * values, just for sign.
163 * The field is initialized to 0 for normal sync nodes, and
164 * CONDITION for condition nodes. It is modified only using
167 volatile int waitStatus;
170 * Link to predecessor node that current node/thread relies on
171 * for checking waitStatus. Assigned during enqueing, and nulled
172 * out (for sake of GC) only upon dequeuing. Also, upon
173 * cancellation of a predecessor, we short-circuit while
174 * finding a non-cancelled one, which will always exist
175 * because the head node is never cancelled: A node becomes
176 * head only as a result of successful acquire. A
177 * cancelled thread never succeeds in acquiring, and a thread only
178 * cancels itself, not any other node.
183 * Link to the successor node that the current node/thread
184 * unparks upon release. Assigned once during enqueuing, and
185 * nulled out (for sake of GC) when no longer needed. Upon
186 * cancellation, we cannot adjust this field, but can notice
187 * status and bypass the node if cancelled. The enq operation
188 * does not assign next field of a predecessor until after
189 * attachment, so seeing a null next field does not
190 * necessarily mean that node is at end of queue. However, if
191 * a next field appears to be null, we can scan prev's from
192 * the tail to double-check.
197 * The thread that enqueued this node. Initialized on
198 * construction and nulled out after use.
200 volatile Thread thread;
203 * Link to next node waiting on condition, or the special
204 * value SHARED. Because condition queues are accessed only
205 * when holding in exclusive mode, we just need a simple
206 * linked queue to hold nodes while they are waiting on
207 * conditions. They are then transferred to the queue to
208 * re-acquire. And because conditions can only be exclusive,
209 * we save a field by using special value to indicate shared
215 * Returns true if node is waiting in shared mode
217 final boolean isShared() {
218 return nextWaiter == SHARED;
222 * Returns previous node, or throws NullPointerException if
223 * null. Use when predecessor cannot be null.
224 * @return the predecessor of this node
226 final Node predecessor() throws NullPointerException {
229 throw new NullPointerException();
234 Node() { // Used to establish initial head or SHARED marker
237 Node(Thread thread, Node mode) { // Used by addWaiter
238 this.nextWaiter = mode;
239 this.thread = thread;
242 Node(Thread thread, int waitStatus) { // Used by Condition
243 this.waitStatus = waitStatus;
244 this.thread = thread;
249 * Head of the wait queue, lazily initialized. Except for
250 * initialization, it is modified only via method setHead. Note:
251 * If head exists, its waitStatus is guaranteed not to be
254 private transient volatile Node head;
257 * Tail of the wait queue, lazily initialized. Modified only via
258 * method enq to add new wait node.
260 private transient volatile Node tail;
263 * The synchronization state.
265 private volatile long state;
268 * Returns the current value of synchronization state.
269 * This operation has memory semantics of a <tt>volatile</tt> read.
270 * @return current state value
272 protected final long getState() {
277 * Sets the value of synchronization state.
278 * This operation has memory semantics of a <tt>volatile</tt> write.
279 * @param newState the new state value
281 protected final void setState(long newState) {
286 * Atomically sets synchronization state to the given updated
287 * value if the current state value equals the expected value.
288 * This operation has memory semantics of a <tt>volatile</tt> read
291 * @param expect the expected value
292 * @param update the new value
293 * @return true if successful. False return indicates that the actual
294 * value was not equal to the expected value.
296 protected final boolean compareAndSetState(long expect, long update) {
297 // See below for intrinsics setup to support this
298 return unsafe.compareAndSwapLong(this, stateOffset, expect, update);
304 * The number of nanoseconds for which it is faster to spin
305 * rather than to use timed park. A rough estimate suffices
306 * to improve responsiveness with very short timeouts.
308 static final long spinForTimeoutThreshold = 1000L;
311 * Inserts node into queue, initializing if necessary. See picture above.
312 * @param node the node to insert
313 * @return node's predecessor
315 private Node enq(final Node node) {
318 if (t == null) { // Must initialize
319 Node h = new Node(); // Dummy header
322 if (compareAndSetHead(h)) {
329 if (compareAndSetTail(t, node)) {
338 * Creates and enqueues node for given thread and mode.
340 * @param current the thread
341 * @param mode Node.EXCLUSIVE for exclusive, Node.SHARED for shared
342 * @return the new node
344 private Node addWaiter(Node mode) {
345 Node node = new Node(Thread.currentThread(), mode);
346 // Try the fast path of enq; backup to full enq on failure
350 if (compareAndSetTail(pred, node)) {
360 * Sets head of queue to be node, thus dequeuing. Called only by
361 * acquire methods. Also nulls out unused fields for sake of GC
362 * and to suppress unnecessary signals and traversals.
364 * @param node the node
366 private void setHead(Node node) {
373 * Wakes up node's successor, if one exists.
375 * @param node the node
377 private void unparkSuccessor(Node node) {
379 * Try to clear status in anticipation of signalling. It is
380 * OK if this fails or if status is changed by waiting thread.
382 compareAndSetWaitStatus(node, Node.SIGNAL, 0);
385 * Thread to unpark is held in successor, which is normally
386 * just the next node. But if cancelled or apparently null,
387 * traverse backwards from tail to find the actual
388 * non-cancelled successor.
391 if (s == null || s.waitStatus > 0) {
393 for (Node t = tail; t != null && t != node; t = t.prev)
394 if (t.waitStatus <= 0)
398 LockSupport.unpark(s.thread);
402 * Sets head of queue, and checks if successor may be waiting
403 * in shared mode, if so propagating if propagate > 0.
405 * @param pred the node holding waitStatus for node
406 * @param node the node
407 * @param propagate the return value from a tryAcquireShared
409 private void setHeadAndPropagate(Node node, long propagate) {
411 if (propagate > 0 && node.waitStatus != 0) {
413 * Don't bother fully figuring out successor. If it
414 * looks null, call unparkSuccessor anyway to be safe.
417 if (s == null || s.isShared())
418 unparkSuccessor(node);
422 // Utilities for various versions of acquire
425 * Cancels an ongoing attempt to acquire.
427 * @param node the node
429 private void cancelAcquire(Node node) {
430 if (node != null) { // Ignore if node doesn't exist
432 // Can use unconditional write instead of CAS here
433 node.waitStatus = Node.CANCELLED;
434 unparkSuccessor(node);
439 * Checks and updates status for a node that failed to acquire.
440 * Returns true if thread should block. This is the main signal
441 * control in all acquire loops. Requires that pred == node.prev
443 * @param pred node's predecessor holding status
444 * @param node the node
445 * @return {@code true} if thread should block
447 private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
448 int s = pred.waitStatus;
451 * This node has already set status asking a release
452 * to signal it, so it can safely park
457 * Predecessor was cancelled. Move up to its predecessor
458 * and indicate retry.
460 node.prev = pred.prev;
463 * Indicate that we need a signal, but don't park yet. Caller
464 * will need to retry to make sure it cannot acquire before
467 compareAndSetWaitStatus(pred, 0, Node.SIGNAL);
472 * Convenience method to interrupt current thread.
474 private static void selfInterrupt() {
475 Thread.currentThread().interrupt();
479 * Convenience method to park and then check if interrupted
481 * @return {@code true} if interrupted
483 private final boolean parkAndCheckInterrupt() {
484 LockSupport.park(this);
485 return Thread.interrupted();
489 * Various flavors of acquire, varying in exclusive/shared and
490 * control modes. Each is mostly the same, but annoyingly
491 * different. Only a little bit of factoring is possible due to
492 * interactions of exception mechanics (including ensuring that we
493 * cancel if tryAcquire throws exception) and other control, at
494 * least not without hurting performance too much.
498 * Acquires in exclusive uninterruptible mode for thread already in
499 * queue. Used by condition wait methods as well as acquire.
501 * @param node the node
502 * @param arg the acquire argument
503 * @return {@code true} if interrupted while waiting
505 final boolean acquireQueued(final Node node, long arg) {
507 boolean interrupted = false;
509 final Node p = node.predecessor();
510 if (p == head && tryAcquire(arg)) {
512 p.next = null; // help GC
515 if (shouldParkAfterFailedAcquire(p, node) &&
516 parkAndCheckInterrupt())
519 } catch (RuntimeException ex) {
526 * Acquires in exclusive interruptible mode.
527 * @param arg the acquire argument
529 private void doAcquireInterruptibly(long arg)
530 throws InterruptedException {
531 final Node node = addWaiter(Node.EXCLUSIVE);
534 final Node p = node.predecessor();
535 if (p == head && tryAcquire(arg)) {
537 p.next = null; // help GC
540 if (shouldParkAfterFailedAcquire(p, node) &&
541 parkAndCheckInterrupt())
544 } catch (RuntimeException ex) {
548 // Arrive here only if interrupted
550 throw new InterruptedException();
554 * Acquires in exclusive timed mode.
556 * @param arg the acquire argument
557 * @param nanosTimeout max wait time
558 * @return {@code true} if acquired
560 private boolean doAcquireNanos(long arg, long nanosTimeout)
561 throws InterruptedException {
562 long lastTime = System.nanoTime();
563 final Node node = addWaiter(Node.EXCLUSIVE);
566 final Node p = node.predecessor();
567 if (p == head && tryAcquire(arg)) {
569 p.next = null; // help GC
572 if (nanosTimeout <= 0) {
576 if (nanosTimeout > spinForTimeoutThreshold &&
577 shouldParkAfterFailedAcquire(p, node))
578 LockSupport.parkNanos(this, nanosTimeout);
579 long now = System.nanoTime();
580 nanosTimeout -= now - lastTime;
582 if (Thread.interrupted())
585 } catch (RuntimeException ex) {
589 // Arrive here only if interrupted
591 throw new InterruptedException();
595 * Acquires in shared uninterruptible mode.
596 * @param arg the acquire argument
598 private void doAcquireShared(long arg) {
599 final Node node = addWaiter(Node.SHARED);
601 boolean interrupted = false;
603 final Node p = node.predecessor();
605 long r = tryAcquireShared(arg);
607 setHeadAndPropagate(node, r);
608 p.next = null; // help GC
614 if (shouldParkAfterFailedAcquire(p, node) &&
615 parkAndCheckInterrupt())
618 } catch (RuntimeException ex) {
625 * Acquires in shared interruptible mode.
626 * @param arg the acquire argument
628 private void doAcquireSharedInterruptibly(long arg)
629 throws InterruptedException {
630 final Node node = addWaiter(Node.SHARED);
633 final Node p = node.predecessor();
635 long r = tryAcquireShared(arg);
637 setHeadAndPropagate(node, r);
638 p.next = null; // help GC
642 if (shouldParkAfterFailedAcquire(p, node) &&
643 parkAndCheckInterrupt())
646 } catch (RuntimeException ex) {
650 // Arrive here only if interrupted
652 throw new InterruptedException();
656 * Acquires in shared timed mode.
658 * @param arg the acquire argument
659 * @param nanosTimeout max wait time
660 * @return {@code true} if acquired
662 private boolean doAcquireSharedNanos(long arg, long nanosTimeout)
663 throws InterruptedException {
665 long lastTime = System.nanoTime();
666 final Node node = addWaiter(Node.SHARED);
669 final Node p = node.predecessor();
671 long r = tryAcquireShared(arg);
673 setHeadAndPropagate(node, r);
674 p.next = null; // help GC
678 if (nanosTimeout <= 0) {
682 if (nanosTimeout > spinForTimeoutThreshold &&
683 shouldParkAfterFailedAcquire(p, node))
684 LockSupport.parkNanos(this, nanosTimeout);
685 long now = System.nanoTime();
686 nanosTimeout -= now - lastTime;
688 if (Thread.interrupted())
691 } catch (RuntimeException ex) {
695 // Arrive here only if interrupted
697 throw new InterruptedException();
700 // Main exported methods
703 * Attempts to acquire in exclusive mode. This method should query
704 * if the state of the object permits it to be acquired in the
705 * exclusive mode, and if so to acquire it.
707 * <p>This method is always invoked by the thread performing
708 * acquire. If this method reports failure, the acquire method
709 * may queue the thread, if it is not already queued, until it is
710 * signalled by a release from some other thread. This can be used
711 * to implement method {@link Lock#tryLock()}.
714 * implementation throws {@link UnsupportedOperationException}.
716 * @param arg the acquire argument. This value is always the one
717 * passed to an acquire method, or is the value saved on entry
718 * to a condition wait. The value is otherwise uninterpreted
719 * and can represent anything you like.
720 * @return {@code true} if successful. Upon success, this object has
722 * @throws IllegalMonitorStateException if acquiring would place this
723 * synchronizer in an illegal state. This exception must be
724 * thrown in a consistent fashion for synchronization to work
726 * @throws UnsupportedOperationException if exclusive mode is not supported
728 protected boolean tryAcquire(long arg) {
729 throw new UnsupportedOperationException();
733 * Attempts to set the state to reflect a release in exclusive
736 * <p>This method is always invoked by the thread performing release.
738 * <p>The default implementation throws
739 * {@link UnsupportedOperationException}.
741 * @param arg the release argument. This value is always the one
742 * passed to a release method, or the current state value upon
743 * entry to a condition wait. The value is otherwise
744 * uninterpreted and can represent anything you like.
745 * @return {@code true} if this object is now in a fully released
746 * state, so that any waiting threads may attempt to acquire;
747 * and {@code false} otherwise.
748 * @throws IllegalMonitorStateException if releasing would place this
749 * synchronizer in an illegal state. This exception must be
750 * thrown in a consistent fashion for synchronization to work
752 * @throws UnsupportedOperationException if exclusive mode is not supported
754 protected boolean tryRelease(long arg) {
755 throw new UnsupportedOperationException();
759 * Attempts to acquire in shared mode. This method should query if
760 * the state of the object permits it to be acquired in the shared
761 * mode, and if so to acquire it.
763 * <p>This method is always invoked by the thread performing
764 * acquire. If this method reports failure, the acquire method
765 * may queue the thread, if it is not already queued, until it is
766 * signalled by a release from some other thread.
768 * <p>The default implementation throws {@link
769 * UnsupportedOperationException}.
771 * @param arg the acquire argument. This value is always the one
772 * passed to an acquire method, or is the value saved on entry
773 * to a condition wait. The value is otherwise uninterpreted
774 * and can represent anything you like.
775 * @return a negative value on failure; zero if acquisition in shared
776 * mode succeeded but no subsequent shared-mode acquire can
777 * succeed; and a positive value if acquisition in shared
778 * mode succeeded and subsequent shared-mode acquires might
779 * also succeed, in which case a subsequent waiting thread
780 * must check availability. (Support for three different
781 * return values enables this method to be used in contexts
782 * where acquires only sometimes act exclusively.) Upon
783 * success, this object has been acquired.
784 * @throws IllegalMonitorStateException if acquiring would place this
785 * synchronizer in an illegal state. This exception must be
786 * thrown in a consistent fashion for synchronization to work
788 * @throws UnsupportedOperationException if shared mode is not supported
790 protected long tryAcquireShared(long arg) {
791 throw new UnsupportedOperationException();
795 * Attempts to set the state to reflect a release in shared mode.
797 * <p>This method is always invoked by the thread performing release.
799 * <p>The default implementation throws
800 * {@link UnsupportedOperationException}.
802 * @param arg the release argument. This value is always the one
803 * passed to a release method, or the current state value upon
804 * entry to a condition wait. The value is otherwise
805 * uninterpreted and can represent anything you like.
806 * @return {@code true} if this release of shared mode may permit a
807 * waiting acquire (shared or exclusive) to succeed; and
808 * {@code false} otherwise
809 * @throws IllegalMonitorStateException if releasing would place this
810 * synchronizer in an illegal state. This exception must be
811 * thrown in a consistent fashion for synchronization to work
813 * @throws UnsupportedOperationException if shared mode is not supported
815 protected boolean tryReleaseShared(long arg) {
816 throw new UnsupportedOperationException();
820 * Returns {@code true} if synchronization is held exclusively with
821 * respect to the current (calling) thread. This method is invoked
822 * upon each call to a non-waiting {@link ConditionObject} method.
823 * (Waiting methods instead invoke {@link #release}.)
825 * <p>The default implementation throws {@link
826 * UnsupportedOperationException}. This method is invoked
827 * internally only within {@link ConditionObject} methods, so need
828 * not be defined if conditions are not used.
830 * @return {@code true} if synchronization is held exclusively;
831 * {@code false} otherwise
832 * @throws UnsupportedOperationException if conditions are not supported
834 protected boolean isHeldExclusively() {
835 throw new UnsupportedOperationException();
839 * Acquires in exclusive mode, ignoring interrupts. Implemented
840 * by invoking at least once {@link #tryAcquire},
841 * returning on success. Otherwise the thread is queued, possibly
842 * repeatedly blocking and unblocking, invoking {@link
843 * #tryAcquire} until success. This method can be used
844 * to implement method {@link Lock#lock}.
846 * @param arg the acquire argument. This value is conveyed to
847 * {@link #tryAcquire} but is otherwise uninterpreted and
848 * can represent anything you like.
850 public final void acquire(long arg) {
851 if (!tryAcquire(arg) &&
852 acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
857 * Acquires in exclusive mode, aborting if interrupted.
858 * Implemented by first checking interrupt status, then invoking
859 * at least once {@link #tryAcquire}, returning on
860 * success. Otherwise the thread is queued, possibly repeatedly
861 * blocking and unblocking, invoking {@link #tryAcquire}
862 * until success or the thread is interrupted. This method can be
863 * used to implement method {@link Lock#lockInterruptibly}.
865 * @param arg the acquire argument. This value is conveyed to
866 * {@link #tryAcquire} but is otherwise uninterpreted and
867 * can represent anything you like.
868 * @throws InterruptedException if the current thread is interrupted
870 public final void acquireInterruptibly(long arg) throws InterruptedException {
871 if (Thread.interrupted())
872 throw new InterruptedException();
873 if (!tryAcquire(arg))
874 doAcquireInterruptibly(arg);
878 * Attempts to acquire in exclusive mode, aborting if interrupted,
879 * and failing if the given timeout elapses. Implemented by first
880 * checking interrupt status, then invoking at least once {@link
881 * #tryAcquire}, returning on success. Otherwise, the thread is
882 * queued, possibly repeatedly blocking and unblocking, invoking
883 * {@link #tryAcquire} until success or the thread is interrupted
884 * or the timeout elapses. This method can be used to implement
885 * method {@link Lock#tryLock(long, TimeUnit)}.
887 * @param arg the acquire argument. This value is conveyed to
888 * {@link #tryAcquire} but is otherwise uninterpreted and
889 * can represent anything you like.
890 * @param nanosTimeout the maximum number of nanoseconds to wait
891 * @return {@code true} if acquired; {@code false} if timed out
892 * @throws InterruptedException if the current thread is interrupted
894 public final boolean tryAcquireNanos(long arg, long nanosTimeout) throws InterruptedException {
895 if (Thread.interrupted())
896 throw new InterruptedException();
897 return tryAcquire(arg) ||
898 doAcquireNanos(arg, nanosTimeout);
902 * Releases in exclusive mode. Implemented by unblocking one or
903 * more threads if {@link #tryRelease} returns true.
904 * This method can be used to implement method {@link Lock#unlock}.
906 * @param arg the release argument. This value is conveyed to
907 * {@link #tryRelease} but is otherwise uninterpreted and
908 * can represent anything you like.
909 * @return the value returned from {@link #tryRelease}
911 public final boolean release(long arg) {
912 if (tryRelease(arg)) {
914 if (h != null && h.waitStatus != 0)
922 * Acquires in shared mode, ignoring interrupts. Implemented by
923 * first invoking at least once {@link #tryAcquireShared},
924 * returning on success. Otherwise the thread is queued, possibly
925 * repeatedly blocking and unblocking, invoking {@link
926 * #tryAcquireShared} until success.
928 * @param arg the acquire argument. This value is conveyed to
929 * {@link #tryAcquireShared} but is otherwise uninterpreted
930 * and can represent anything you like.
932 public final void acquireShared(long arg) {
933 if (tryAcquireShared(arg) < 0)
934 doAcquireShared(arg);
938 * Acquires in shared mode, aborting if interrupted. Implemented
939 * by first checking interrupt status, then invoking at least once
940 * {@link #tryAcquireShared}, returning on success. Otherwise the
941 * thread is queued, possibly repeatedly blocking and unblocking,
942 * invoking {@link #tryAcquireShared} until success or the thread
944 * @param arg the acquire argument.
945 * This value is conveyed to {@link #tryAcquireShared} but is
946 * otherwise uninterpreted and can represent anything
948 * @throws InterruptedException if the current thread is interrupted
950 public final void acquireSharedInterruptibly(long arg) throws InterruptedException {
951 if (Thread.interrupted())
952 throw new InterruptedException();
953 if (tryAcquireShared(arg) < 0)
954 doAcquireSharedInterruptibly(arg);
958 * Attempts to acquire in shared mode, aborting if interrupted, and
959 * failing if the given timeout elapses. Implemented by first
960 * checking interrupt status, then invoking at least once {@link
961 * #tryAcquireShared}, returning on success. Otherwise, the
962 * thread is queued, possibly repeatedly blocking and unblocking,
963 * invoking {@link #tryAcquireShared} until success or the thread
964 * is interrupted or the timeout elapses.
966 * @param arg the acquire argument. This value is conveyed to
967 * {@link #tryAcquireShared} but is otherwise uninterpreted
968 * and can represent anything you like.
969 * @param nanosTimeout the maximum number of nanoseconds to wait
970 * @return {@code true} if acquired; {@code false} if timed out
971 * @throws InterruptedException if the current thread is interrupted
973 public final boolean tryAcquireSharedNanos(long arg, long nanosTimeout) throws InterruptedException {
974 if (Thread.interrupted())
975 throw new InterruptedException();
976 return tryAcquireShared(arg) >= 0 ||
977 doAcquireSharedNanos(arg, nanosTimeout);
981 * Releases in shared mode. Implemented by unblocking one or more
982 * threads if {@link #tryReleaseShared} returns true.
984 * @param arg the release argument. This value is conveyed to
985 * {@link #tryReleaseShared} but is otherwise uninterpreted
986 * and can represent anything you like.
987 * @return the value returned from {@link #tryReleaseShared}
989 public final boolean releaseShared(long arg) {
990 if (tryReleaseShared(arg)) {
992 if (h != null && h.waitStatus != 0)
999 // Queue inspection methods
1002 * Queries whether any threads are waiting to acquire. Note that
1003 * because cancellations due to interrupts and timeouts may occur
1004 * at any time, a {@code true} return does not guarantee that any
1005 * other thread will ever acquire.
1007 * <p>In this implementation, this operation returns in
1010 * @return {@code true} if there may be other threads waiting to acquire
1012 public final boolean hasQueuedThreads() {
1013 return head != tail;
1017 * Queries whether any threads have ever contended to acquire this
1018 * synchronizer; that is if an acquire method has ever blocked.
1020 * <p>In this implementation, this operation returns in
1023 * @return {@code true} if there has ever been contention
1025 public final boolean hasContended() {
1026 return head != null;
1030 * Returns the first (longest-waiting) thread in the queue, or
1031 * {@code null} if no threads are currently queued.
1033 * <p>In this implementation, this operation normally returns in
1034 * constant time, but may iterate upon contention if other threads are
1035 * concurrently modifying the queue.
1037 * @return the first (longest-waiting) thread in the queue, or
1038 * {@code null} if no threads are currently queued
1040 public final Thread getFirstQueuedThread() {
1041 // handle only fast path, else relay
1042 return (head == tail)? null : fullGetFirstQueuedThread();
1046 * Version of getFirstQueuedThread called when fastpath fails
1048 private Thread fullGetFirstQueuedThread() {
1050 * The first node is normally h.next. Try to get its
1051 * thread field, ensuring consistent reads: If thread
1052 * field is nulled out or s.prev is no longer head, then
1053 * some other thread(s) concurrently performed setHead in
1054 * between some of our reads. We try this twice before
1055 * resorting to traversal.
1059 if (((h = head) != null && (s = h.next) != null &&
1060 s.prev == head && (st = s.thread) != null) ||
1061 ((h = head) != null && (s = h.next) != null &&
1062 s.prev == head && (st = s.thread) != null))
1066 * Head's next field might not have been set yet, or may have
1067 * been unset after setHead. So we must check to see if tail
1068 * is actually first node. If not, we continue on, safely
1069 * traversing from tail back to head to find first,
1070 * guaranteeing termination.
1074 Thread firstThread = null;
1075 while (t != null && t != head) {
1076 Thread tt = t.thread;
1085 * Returns true if the given thread is currently queued.
1087 * <p>This implementation traverses the queue to determine
1088 * presence of the given thread.
1090 * @param thread the thread
1091 * @return {@code true} if the given thread is on the queue
1092 * @throws NullPointerException if the thread is null
1094 public final boolean isQueued(Thread thread) {
1096 throw new NullPointerException();
1097 for (Node p = tail; p != null; p = p.prev)
1098 if (p.thread == thread)
1104 * Return {@code true} if the apparent first queued thread, if one
1105 * exists, is not waiting in exclusive mode. Used only as a heuristic
1106 * in ReentrantReadWriteLock.
1108 final boolean apparentlyFirstQueuedIsExclusive() {
1110 return ((h = head) != null && (s = h.next) != null &&
1111 s.nextWaiter != Node.SHARED);
1115 * Return {@code true} if the queue is empty or if the given thread
1116 * is at the head of the queue. This is reliable only if
1117 * <tt>current</tt> is actually Thread.currentThread() of caller.
1119 final boolean isFirst(Thread current) {
1121 return ((h = head) == null ||
1122 ((s = h.next) != null && s.thread == current) ||
1123 fullIsFirst(current));
1126 final boolean fullIsFirst(Thread current) {
1127 // same idea as fullGetFirstQueuedThread
1129 Thread firstThread = null;
1130 if (((h = head) != null && (s = h.next) != null &&
1131 s.prev == head && (firstThread = s.thread) != null))
1132 return firstThread == current;
1134 while (t != null && t != head) {
1135 Thread tt = t.thread;
1140 return firstThread == current || firstThread == null;
1144 // Instrumentation and monitoring methods
1147 * Returns an estimate of the number of threads waiting to
1148 * acquire. The value is only an estimate because the number of
1149 * threads may change dynamically while this method traverses
1150 * internal data structures. This method is designed for use in
1151 * monitoring system state, not for synchronization
1154 * @return the estimated number of threads waiting to acquire
1156 public final int getQueueLength() {
1158 for (Node p = tail; p != null; p = p.prev) {
1159 if (p.thread != null)
1166 * Returns a collection containing threads that may be waiting to
1167 * acquire. Because the actual set of threads may change
1168 * dynamically while constructing this result, the returned
1169 * collection is only a best-effort estimate. The elements of the
1170 * returned collection are in no particular order. This method is
1171 * designed to facilitate construction of subclasses that provide
1172 * more extensive monitoring facilities.
1174 * @return the collection of threads
1176 public final Collection<Thread> getQueuedThreads() {
1177 ArrayList<Thread> list = new ArrayList<Thread>();
1178 for (Node p = tail; p != null; p = p.prev) {
1179 Thread t = p.thread;
1187 * Returns a collection containing threads that may be waiting to
1188 * acquire in exclusive mode. This has the same properties
1189 * as {@link #getQueuedThreads} except that it only returns
1190 * those threads waiting due to an exclusive acquire.
1192 * @return the collection of threads
1194 public final Collection<Thread> getExclusiveQueuedThreads() {
1195 ArrayList<Thread> list = new ArrayList<Thread>();
1196 for (Node p = tail; p != null; p = p.prev) {
1197 if (!p.isShared()) {
1198 Thread t = p.thread;
1207 * Returns a collection containing threads that may be waiting to
1208 * acquire in shared mode. This has the same properties
1209 * as {@link #getQueuedThreads} except that it only returns
1210 * those threads waiting due to a shared acquire.
1212 * @return the collection of threads
1214 public final Collection<Thread> getSharedQueuedThreads() {
1215 ArrayList<Thread> list = new ArrayList<Thread>();
1216 for (Node p = tail; p != null; p = p.prev) {
1218 Thread t = p.thread;
1227 * Returns a string identifying this synchronizer, as well as its state.
1228 * The state, in brackets, includes the String {@code "State ="}
1229 * followed by the current value of {@link #getState}, and either
1230 * {@code "nonempty"} or {@code "empty"} depending on whether the
1233 * @return a string identifying this synchronizer, as well as its state
1235 public String toString() {
1236 long s = getState();
1237 String q = hasQueuedThreads()? "non" : "";
1238 return super.toString() +
1239 "[State = " + s + ", " + q + "empty queue]";
1243 // Internal support methods for Conditions
1246 * Returns true if a node, always one that was initially placed on
1247 * a condition queue, is now waiting to reacquire on sync queue.
1248 * @param node the node
1249 * @return true if is reacquiring
1251 final boolean isOnSyncQueue(Node node) {
1252 if (node.waitStatus == Node.CONDITION || node.prev == null)
1254 if (node.next != null) // If has successor, it must be on queue
1257 * node.prev can be non-null, but not yet on queue because
1258 * the CAS to place it on queue can fail. So we have to
1259 * traverse from tail to make sure it actually made it. It
1260 * will always be near the tail in calls to this method, and
1261 * unless the CAS failed (which is unlikely), it will be
1262 * there, so we hardly ever traverse much.
1264 return findNodeFromTail(node);
1268 * Returns true if node is on sync queue by searching backwards from tail.
1269 * Called only when needed by isOnSyncQueue.
1270 * @return true if present
1272 private boolean findNodeFromTail(Node node) {
1284 * Transfers a node from a condition queue onto sync queue.
1285 * Returns true if successful.
1286 * @param node the node
1287 * @return true if successfully transferred (else the node was
1288 * cancelled before signal).
1290 final boolean transferForSignal(Node node) {
1292 * If cannot change waitStatus, the node has been cancelled.
1294 if (!compareAndSetWaitStatus(node, Node.CONDITION, 0))
1298 * Splice onto queue and try to set waitStatus of predecessor to
1299 * indicate that thread is (probably) waiting. If cancelled or
1300 * attempt to set waitStatus fails, wake up to resync (in which
1301 * case the waitStatus can be transiently and harmlessly wrong).
1304 int c = p.waitStatus;
1305 if (c > 0 || !compareAndSetWaitStatus(p, c, Node.SIGNAL))
1306 LockSupport.unpark(node.thread);
1311 * Transfers node, if necessary, to sync queue after a cancelled
1312 * wait. Returns true if thread was cancelled before being
1314 * @param current the waiting thread
1315 * @param node its node
1316 * @return true if cancelled before the node was signalled.
1318 final boolean transferAfterCancelledWait(Node node) {
1319 if (compareAndSetWaitStatus(node, Node.CONDITION, 0)) {
1324 * If we lost out to a signal(), then we can't proceed
1325 * until it finishes its enq(). Cancelling during an
1326 * incomplete transfer is both rare and transient, so just
1329 while (!isOnSyncQueue(node))
1335 * Invokes release with current state value; returns saved state.
1336 * Cancels node and throws exception on failure.
1337 * @param node the condition node for this wait
1338 * @return previous sync state
1340 final long fullyRelease(Node node) {
1342 long savedState = getState();
1343 if (release(savedState))
1345 } catch (RuntimeException ex) {
1346 node.waitStatus = Node.CANCELLED;
1349 // reach here if release fails
1350 node.waitStatus = Node.CANCELLED;
1351 throw new IllegalMonitorStateException();
1354 // Instrumentation methods for conditions
1357 * Queries whether the given ConditionObject
1358 * uses this synchronizer as its lock.
1360 * @param condition the condition
1361 * @return <tt>true</tt> if owned
1362 * @throws NullPointerException if the condition is null
1364 public final boolean owns(ConditionObject condition) {
1365 if (condition == null)
1366 throw new NullPointerException();
1367 return condition.isOwnedBy(this);
1371 * Queries whether any threads are waiting on the given condition
1372 * associated with this synchronizer. Note that because timeouts
1373 * and interrupts may occur at any time, a <tt>true</tt> return
1374 * does not guarantee that a future <tt>signal</tt> will awaken
1375 * any threads. This method is designed primarily for use in
1376 * monitoring of the system state.
1378 * @param condition the condition
1379 * @return <tt>true</tt> if there are any waiting threads
1380 * @throws IllegalMonitorStateException if exclusive synchronization
1382 * @throws IllegalArgumentException if the given condition is
1383 * not associated with this synchronizer
1384 * @throws NullPointerException if the condition is null
1386 public final boolean hasWaiters(ConditionObject condition) {
1387 if (!owns(condition))
1388 throw new IllegalArgumentException("Not owner");
1389 return condition.hasWaiters();
1393 * Returns an estimate of the number of threads waiting on the
1394 * given condition associated with this synchronizer. Note that
1395 * because timeouts and interrupts may occur at any time, the
1396 * estimate serves only as an upper bound on the actual number of
1397 * waiters. This method is designed for use in monitoring of the
1398 * system state, not for synchronization control.
1400 * @param condition the condition
1401 * @return the estimated number of waiting threads
1402 * @throws IllegalMonitorStateException if exclusive synchronization
1404 * @throws IllegalArgumentException if the given condition is
1405 * not associated with this synchronizer
1406 * @throws NullPointerException if the condition is null
1408 public final int getWaitQueueLength(ConditionObject condition) {
1409 if (!owns(condition))
1410 throw new IllegalArgumentException("Not owner");
1411 return condition.getWaitQueueLength();
1415 * Returns a collection containing those threads that may be
1416 * waiting on the given condition associated with this
1417 * synchronizer. Because the actual set of threads may change
1418 * dynamically while constructing this result, the returned
1419 * collection is only a best-effort estimate. The elements of the
1420 * returned collection are in no particular order.
1422 * @param condition the condition
1423 * @return the collection of threads
1424 * @throws IllegalMonitorStateException if exclusive synchronization
1426 * @throws IllegalArgumentException if the given condition is
1427 * not associated with this synchronizer
1428 * @throws NullPointerException if the condition is null
1430 public final Collection<Thread> getWaitingThreads(ConditionObject condition) {
1431 if (!owns(condition))
1432 throw new IllegalArgumentException("Not owner");
1433 return condition.getWaitingThreads();
1437 * Condition implementation for a {@link
1438 * AbstractQueuedLongSynchronizer} serving as the basis of a {@link
1439 * Lock} implementation.
1441 * <p>Method documentation for this class describes mechanics,
1442 * not behavioral specifications from the point of view of Lock
1443 * and Condition users. Exported versions of this class will in
1444 * general need to be accompanied by documentation describing
1445 * condition semantics that rely on those of the associated
1446 * <tt>AbstractQueuedLongSynchronizer</tt>.
1448 * <p>This class is Serializable, but all fields are transient,
1449 * so deserialized conditions have no waiters.
1453 public class ConditionObject implements Condition, java.io.Serializable {
1454 private static final long serialVersionUID = 1173984872572414699L;
1455 /** First node of condition queue. */
1456 private transient Node firstWaiter;
1457 /** Last node of condition queue. */
1458 private transient Node lastWaiter;
1461 * Creates a new <tt>ConditionObject</tt> instance.
1463 public ConditionObject() { }
1468 * Adds a new waiter to wait queue.
1469 * @return its new wait node
1471 private Node addConditionWaiter() {
1472 Node node = new Node(Thread.currentThread(), Node.CONDITION);
1473 Node t = lastWaiter;
1477 t.nextWaiter = node;
1483 * Removes and transfers nodes until hit non-cancelled one or
1484 * null. Split out from signal in part to encourage compilers
1485 * to inline the case of no waiters.
1486 * @param first (non-null) the first node on condition queue
1488 private void doSignal(Node first) {
1490 if ( (firstWaiter = first.nextWaiter) == null)
1492 first.nextWaiter = null;
1493 } while (!transferForSignal(first) &&
1494 (first = firstWaiter) != null);
1498 * Removes and transfers all nodes.
1499 * @param first (non-null) the first node on condition queue
1501 private void doSignalAll(Node first) {
1502 lastWaiter = firstWaiter = null;
1504 Node next = first.nextWaiter;
1505 first.nextWaiter = null;
1506 transferForSignal(first);
1508 } while (first != null);
1512 * Returns true if given node is on this condition queue.
1513 * Call only when holding lock.
1515 private boolean isOnConditionQueue(Node node) {
1516 return node.next != null || node == lastWaiter;
1520 * Unlinks a cancelled waiter node from condition queue. This
1521 * is called when cancellation occurred during condition wait,
1522 * not lock wait, and is called only after lock has been
1523 * re-acquired by a cancelled waiter and the node is not known
1524 * to already have been dequeued. It is needed to avoid
1525 * garbage retention in the absence of signals. So even though
1526 * it may require a full traversal, it comes into play only
1527 * when timeouts or cancellations occur in the absence of
1530 private void unlinkCancelledWaiter(Node node) {
1531 Node t = firstWaiter;
1535 Node next = t.nextWaiter;
1539 trail.nextWaiter = next;
1540 if (lastWaiter == node)
1552 * Moves the longest-waiting thread, if one exists, from the
1553 * wait queue for this condition to the wait queue for the
1556 * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
1557 * returns {@code false}
1559 public final void signal() {
1560 if (!isHeldExclusively())
1561 throw new IllegalMonitorStateException();
1562 Node first = firstWaiter;
1568 * Moves all threads from the wait queue for this condition to
1569 * the wait queue for the owning lock.
1571 * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
1572 * returns {@code false}
1574 public final void signalAll() {
1575 if (!isHeldExclusively())
1576 throw new IllegalMonitorStateException();
1577 Node first = firstWaiter;
1583 * Implements uninterruptible condition wait.
1585 * <li> Save lock state returned by {@link #getState}
1586 * <li> Invoke {@link #release} with
1587 * saved state as argument, throwing
1588 * IllegalMonitorStateException if it fails.
1589 * <li> Block until signalled
1590 * <li> Reacquire by invoking specialized version of
1591 * {@link #acquire} with saved state as argument.
1594 public final void awaitUninterruptibly() {
1595 Node node = addConditionWaiter();
1596 long savedState = fullyRelease(node);
1597 boolean interrupted = false;
1598 while (!isOnSyncQueue(node)) {
1599 LockSupport.park(this);
1600 if (Thread.interrupted())
1603 if (acquireQueued(node, savedState) || interrupted)
1608 * For interruptible waits, we need to track whether to throw
1609 * InterruptedException, if interrupted while blocked on
1610 * condition, versus reinterrupt current thread, if
1611 * interrupted while blocked waiting to re-acquire.
1614 /** Mode meaning to reinterrupt on exit from wait */
1615 private static final int REINTERRUPT = 1;
1616 /** Mode meaning to throw InterruptedException on exit from wait */
1617 private static final int THROW_IE = -1;
1620 * Checks for interrupt, returning THROW_IE if interrupted
1621 * before signalled, REINTERRUPT if after signalled, or
1622 * 0 if not interrupted.
1624 private int checkInterruptWhileWaiting(Node node) {
1625 return (Thread.interrupted()) ?
1626 ((transferAfterCancelledWait(node))? THROW_IE : REINTERRUPT) :
1631 * Throws InterruptedException, reinterrupts current thread, or
1632 * does nothing, depending on mode.
1634 private void reportInterruptAfterWait(int interruptMode)
1635 throws InterruptedException {
1636 if (interruptMode == THROW_IE)
1637 throw new InterruptedException();
1638 else if (interruptMode == REINTERRUPT)
1643 * Implements interruptible condition wait.
1645 * <li> If current thread is interrupted, throw InterruptedException
1646 * <li> Save lock state returned by {@link #getState}
1647 * <li> Invoke {@link #release} with
1648 * saved state as argument, throwing
1649 * IllegalMonitorStateException if it fails.
1650 * <li> Block until signalled or interrupted
1651 * <li> Reacquire by invoking specialized version of
1652 * {@link #acquire} with saved state as argument.
1653 * <li> If interrupted while blocked in step 4, throw exception
1656 public final void await() throws InterruptedException {
1657 if (Thread.interrupted())
1658 throw new InterruptedException();
1659 Node node = addConditionWaiter();
1660 long savedState = fullyRelease(node);
1661 int interruptMode = 0;
1662 while (!isOnSyncQueue(node)) {
1663 LockSupport.park(this);
1664 if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
1667 if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
1668 interruptMode = REINTERRUPT;
1669 if (isOnConditionQueue(node))
1670 unlinkCancelledWaiter(node);
1671 if (interruptMode != 0)
1672 reportInterruptAfterWait(interruptMode);
1676 * Implements timed condition wait.
1678 * <li> If current thread is interrupted, throw InterruptedException
1679 * <li> Save lock state returned by {@link #getState}
1680 * <li> Invoke {@link #release} with
1681 * saved state as argument, throwing
1682 * IllegalMonitorStateException if it fails.
1683 * <li> Block until signalled, interrupted, or timed out
1684 * <li> Reacquire by invoking specialized version of
1685 * {@link #acquire} with saved state as argument.
1686 * <li> If interrupted while blocked in step 4, throw InterruptedException
1689 public final long awaitNanos(long nanosTimeout) throws InterruptedException {
1690 if (Thread.interrupted())
1691 throw new InterruptedException();
1692 Node node = addConditionWaiter();
1693 long savedState = fullyRelease(node);
1694 long lastTime = System.nanoTime();
1695 int interruptMode = 0;
1696 while (!isOnSyncQueue(node)) {
1697 if (nanosTimeout <= 0L) {
1698 transferAfterCancelledWait(node);
1701 LockSupport.parkNanos(this, nanosTimeout);
1702 if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
1705 long now = System.nanoTime();
1706 nanosTimeout -= now - lastTime;
1709 if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
1710 interruptMode = REINTERRUPT;
1711 if (isOnConditionQueue(node))
1712 unlinkCancelledWaiter(node);
1713 if (interruptMode != 0)
1714 reportInterruptAfterWait(interruptMode);
1715 return nanosTimeout - (System.nanoTime() - lastTime);
1719 * Implements absolute timed condition wait.
1721 * <li> If current thread is interrupted, throw InterruptedException
1722 * <li> Save lock state returned by {@link #getState}
1723 * <li> Invoke {@link #release} with
1724 * saved state as argument, throwing
1725 * IllegalMonitorStateException if it fails.
1726 * <li> Block until signalled, interrupted, or timed out
1727 * <li> Reacquire by invoking specialized version of
1728 * {@link #acquire} with saved state as argument.
1729 * <li> If interrupted while blocked in step 4, throw InterruptedException
1730 * <li> If timed out while blocked in step 4, return false, else true
1733 public final boolean awaitUntil(Date deadline) throws InterruptedException {
1734 if (deadline == null)
1735 throw new NullPointerException();
1736 long abstime = deadline.getTime();
1737 if (Thread.interrupted())
1738 throw new InterruptedException();
1739 Node node = addConditionWaiter();
1740 long savedState = fullyRelease(node);
1741 boolean timedout = false;
1742 int interruptMode = 0;
1743 while (!isOnSyncQueue(node)) {
1744 if (System.currentTimeMillis() > abstime) {
1745 timedout = transferAfterCancelledWait(node);
1748 LockSupport.parkUntil(this, abstime);
1749 if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
1752 if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
1753 interruptMode = REINTERRUPT;
1754 if (isOnConditionQueue(node))
1755 unlinkCancelledWaiter(node);
1756 if (interruptMode != 0)
1757 reportInterruptAfterWait(interruptMode);
1762 * Implements timed condition wait.
1764 * <li> If current thread is interrupted, throw InterruptedException
1765 * <li> Save lock state returned by {@link #getState}
1766 * <li> Invoke {@link #release} with
1767 * saved state as argument, throwing
1768 * IllegalMonitorStateException if it fails.
1769 * <li> Block until signalled, interrupted, or timed out
1770 * <li> Reacquire by invoking specialized version of
1771 * {@link #acquire} with saved state as argument.
1772 * <li> If interrupted while blocked in step 4, throw InterruptedException
1773 * <li> If timed out while blocked in step 4, return false, else true
1776 public final boolean await(long time, TimeUnit unit) throws InterruptedException {
1778 throw new NullPointerException();
1779 long nanosTimeout = unit.toNanos(time);
1780 if (Thread.interrupted())
1781 throw new InterruptedException();
1782 Node node = addConditionWaiter();
1783 long savedState = fullyRelease(node);
1784 long lastTime = System.nanoTime();
1785 boolean timedout = false;
1786 int interruptMode = 0;
1787 while (!isOnSyncQueue(node)) {
1788 if (nanosTimeout <= 0L) {
1789 timedout = transferAfterCancelledWait(node);
1792 LockSupport.parkNanos(this, nanosTimeout);
1793 if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
1795 long now = System.nanoTime();
1796 nanosTimeout -= now - lastTime;
1799 if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
1800 interruptMode = REINTERRUPT;
1801 if (isOnConditionQueue(node))
1802 unlinkCancelledWaiter(node);
1803 if (interruptMode != 0)
1804 reportInterruptAfterWait(interruptMode);
1808 // support for instrumentation
1811 * Returns true if this condition was created by the given
1812 * synchronization object.
1814 * @return {@code true} if owned
1816 final boolean isOwnedBy(AbstractQueuedLongSynchronizer sync) {
1817 return sync == AbstractQueuedLongSynchronizer.this;
1821 * Queries whether any threads are waiting on this condition.
1822 * Implements {@link AbstractQueuedLongSynchronizer#hasWaiters}.
1824 * @return {@code true} if there are any waiting threads
1825 * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
1826 * returns {@code false}
1828 protected final boolean hasWaiters() {
1829 if (!isHeldExclusively())
1830 throw new IllegalMonitorStateException();
1831 for (Node w = firstWaiter; w != null; w = w.nextWaiter) {
1832 if (w.waitStatus == Node.CONDITION)
1839 * Returns an estimate of the number of threads waiting on
1841 * Implements {@link AbstractQueuedLongSynchronizer#getWaitQueueLength}.
1843 * @return the estimated number of waiting threads
1844 * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
1845 * returns {@code false}
1847 protected final int getWaitQueueLength() {
1848 if (!isHeldExclusively())
1849 throw new IllegalMonitorStateException();
1851 for (Node w = firstWaiter; w != null; w = w.nextWaiter) {
1852 if (w.waitStatus == Node.CONDITION)
1859 * Returns a collection containing those threads that may be
1860 * waiting on this Condition.
1861 * Implements {@link AbstractQueuedLongSynchronizer#getWaitingThreads}.
1863 * @return the collection of threads
1864 * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
1865 * returns {@code false}
1867 protected final Collection<Thread> getWaitingThreads() {
1868 if (!isHeldExclusively())
1869 throw new IllegalMonitorStateException();
1870 ArrayList<Thread> list = new ArrayList<Thread>();
1871 for (Node w = firstWaiter; w != null; w = w.nextWaiter) {
1872 if (w.waitStatus == Node.CONDITION) {
1873 Thread t = w.thread;
1883 * Setup to support compareAndSet. We need to natively implement
1884 * this here: For the sake of permitting future enhancements, we
1885 * cannot explicitly subclass AtomicLong, which would be
1886 * efficient and useful otherwise. So, as the lesser of evils, we
1887 * natively implement using hotspot intrinsics API. And while we
1888 * are at it, we do the same for other CASable fields (which could
1889 * otherwise be done with atomic field updaters).
1891 private static final Unsafe unsafe = Unsafe.getUnsafe();
1892 private static final long stateOffset;
1893 private static final long headOffset;
1894 private static final long tailOffset;
1895 private static final long waitStatusOffset;
1899 stateOffset = unsafe.objectFieldOffset
1900 (AbstractQueuedLongSynchronizer.class.getDeclaredField("state"));
1901 headOffset = unsafe.objectFieldOffset
1902 (AbstractQueuedLongSynchronizer.class.getDeclaredField("head"));
1903 tailOffset = unsafe.objectFieldOffset
1904 (AbstractQueuedLongSynchronizer.class.getDeclaredField("tail"));
1905 waitStatusOffset = unsafe.objectFieldOffset
1906 (Node.class.getDeclaredField("waitStatus"));
1908 } catch (Exception ex) { throw new Error(ex); }
1912 * CAS head field. Used only by enq
1914 private final boolean compareAndSetHead(Node update) {
1915 return unsafe.compareAndSwapObject(this, headOffset, null, update);
1919 * CAS tail field. Used only by enq
1921 private final boolean compareAndSetTail(Node expect, Node update) {
1922 return unsafe.compareAndSwapObject(this, tailOffset, expect, update);
1926 * CAS waitStatus field of a node.
1928 private final static boolean compareAndSetWaitStatus(Node node,
1931 return unsafe.compareAndSwapInt(node, waitStatusOffset,