rt/emul/compact/src/main/java/java/util/concurrent/locks/AbstractQueuedLongSynchronizer.java
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
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.
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).
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.
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
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
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/publicdomain/zero/1.0/
36 package java.util.concurrent.locks;
38 import java.util.concurrent.*;
41 * A version of {@link AbstractQueuedSynchronizer} in
42 * which synchronization state is maintained as a <tt>long</tt>.
43 * This class has exactly the same structure, properties, and methods
44 * as <tt>AbstractQueuedSynchronizer</tt> with the exception
45 * that all state-related parameters and results are defined
46 * as <tt>long</tt> rather than <tt>int</tt>. This class
47 * may be useful when creating synchronizers such as
48 * multilevel locks and barriers that require
51 * <p>See {@link AbstractQueuedSynchronizer} for usage
57 public abstract class AbstractQueuedLongSynchronizer
58 extends AbstractOwnableSynchronizer
59 implements java.io.Serializable {
61 private static final long serialVersionUID = 7373984972572414692L;
64 To keep sources in sync, the remainder of this source file is
65 exactly cloned from AbstractQueuedSynchronizer, replacing class
66 name and changing ints related with sync state to longs. Please
71 * Creates a new <tt>AbstractQueuedLongSynchronizer</tt> instance
72 * with initial synchronization state of zero.
74 protected AbstractQueuedLongSynchronizer() { }
77 * Wait queue node class.
79 * <p>The wait queue is a variant of a "CLH" (Craig, Landin, and
80 * Hagersten) lock queue. CLH locks are normally used for
81 * spinlocks. We instead use them for blocking synchronizers, but
82 * use the same basic tactic of holding some of the control
83 * information about a thread in the predecessor of its node. A
84 * "status" field in each node keeps track of whether a thread
85 * should block. A node is signalled when its predecessor
86 * releases. Each node of the queue otherwise serves as a
87 * specific-notification-style monitor holding a single waiting
88 * thread. The status field does NOT control whether threads are
89 * granted locks etc though. A thread may try to acquire if it is
90 * first in the queue. But being first does not guarantee success;
91 * it only gives the right to contend. So the currently released
92 * contender thread may need to rewait.
94 * <p>To enqueue into a CLH lock, you atomically splice it in as new
95 * tail. To dequeue, you just set the head field.
97 * +------+ prev +-----+ +-----+
98 * head | | <---- | | <---- | | tail
99 * +------+ +-----+ +-----+
102 * <p>Insertion into a CLH queue requires only a single atomic
103 * operation on "tail", so there is a simple atomic point of
104 * demarcation from unqueued to queued. Similarly, dequeing
105 * involves only updating the "head". However, it takes a bit
106 * more work for nodes to determine who their successors are,
107 * in part to deal with possible cancellation due to timeouts
110 * <p>The "prev" links (not used in original CLH locks), are mainly
111 * needed to handle cancellation. If a node is cancelled, its
112 * successor is (normally) relinked to a non-cancelled
113 * predecessor. For explanation of similar mechanics in the case
114 * of spin locks, see the papers by Scott and Scherer at
115 * http://www.cs.rochester.edu/u/scott/synchronization/
117 * <p>We also use "next" links to implement blocking mechanics.
118 * The thread id for each node is kept in its own node, so a
119 * predecessor signals the next node to wake up by traversing
120 * next link to determine which thread it is. Determination of
121 * successor must avoid races with newly queued nodes to set
122 * the "next" fields of their predecessors. This is solved
123 * when necessary by checking backwards from the atomically
124 * updated "tail" when a node's successor appears to be null.
125 * (Or, said differently, the next-links are an optimization
126 * so that we don't usually need a backward scan.)
128 * <p>Cancellation introduces some conservatism to the basic
129 * algorithms. Since we must poll for cancellation of other
130 * nodes, we can miss noticing whether a cancelled node is
131 * ahead or behind us. This is dealt with by always unparking
132 * successors upon cancellation, allowing them to stabilize on
133 * a new predecessor, unless we can identify an uncancelled
134 * predecessor who will carry this responsibility.
136 * <p>CLH queues need a dummy header node to get started. But
137 * we don't create them on construction, because it would be wasted
138 * effort if there is never contention. Instead, the node
139 * is constructed and head and tail pointers are set upon first
142 * <p>Threads waiting on Conditions use the same nodes, but
143 * use an additional link. Conditions only need to link nodes
144 * in simple (non-concurrent) linked queues because they are
145 * only accessed when exclusively held. Upon await, a node is
146 * inserted into a condition queue. Upon signal, the node is
147 * transferred to the main queue. A special value of status
148 * field is used to mark which queue a node is on.
150 * <p>Thanks go to Dave Dice, Mark Moir, Victor Luchangco, Bill
151 * Scherer and Michael Scott, along with members of JSR-166
152 * expert group, for helpful ideas, discussions, and critiques
153 * on the design of this class.
155 static final class Node {
156 /** Marker to indicate a node is waiting in shared mode */
157 static final Node SHARED = new Node();
158 /** Marker to indicate a node is waiting in exclusive mode */
159 static final Node EXCLUSIVE = null;
161 /** waitStatus value to indicate thread has cancelled */
162 static final int CANCELLED = 1;
163 /** waitStatus value to indicate successor's thread needs unparking */
164 static final int SIGNAL = -1;
165 /** waitStatus value to indicate thread is waiting on condition */
166 static final int CONDITION = -2;
168 * waitStatus value to indicate the next acquireShared should
169 * unconditionally propagate
171 static final int PROPAGATE = -3;
174 * Status field, taking on only the values:
175 * SIGNAL: The successor of this node is (or will soon be)
176 * blocked (via park), so the current node must
177 * unpark its successor when it releases or
178 * cancels. To avoid races, acquire methods must
179 * first indicate they need a signal,
180 * then retry the atomic acquire, and then,
182 * CANCELLED: This node is cancelled due to timeout or interrupt.
183 * Nodes never leave this state. In particular,
184 * a thread with cancelled node never again blocks.
185 * CONDITION: This node is currently on a condition queue.
186 * It will not be used as a sync queue node
187 * until transferred, at which time the status
188 * will be set to 0. (Use of this value here has
189 * nothing to do with the other uses of the
190 * field, but simplifies mechanics.)
191 * PROPAGATE: A releaseShared should be propagated to other
192 * nodes. This is set (for head node only) in
193 * doReleaseShared to ensure propagation
194 * continues, even if other operations have
196 * 0: None of the above
198 * The values are arranged numerically to simplify use.
199 * Non-negative values mean that a node doesn't need to
200 * signal. So, most code doesn't need to check for particular
201 * values, just for sign.
203 * The field is initialized to 0 for normal sync nodes, and
204 * CONDITION for condition nodes. It is modified using CAS
205 * (or when possible, unconditional volatile writes).
207 volatile int waitStatus;
210 * Link to predecessor node that current node/thread relies on
211 * for checking waitStatus. Assigned during enqueing, and nulled
212 * out (for sake of GC) only upon dequeuing. Also, upon
213 * cancellation of a predecessor, we short-circuit while
214 * finding a non-cancelled one, which will always exist
215 * because the head node is never cancelled: A node becomes
216 * head only as a result of successful acquire. A
217 * cancelled thread never succeeds in acquiring, and a thread only
218 * cancels itself, not any other node.
223 * Link to the successor node that the current node/thread
224 * unparks upon release. Assigned during enqueuing, adjusted
225 * when bypassing cancelled predecessors, and nulled out (for
226 * sake of GC) when dequeued. The enq operation does not
227 * assign next field of a predecessor until after attachment,
228 * so seeing a null next field does not necessarily mean that
229 * node is at end of queue. However, if a next field appears
230 * to be null, we can scan prev's from the tail to
231 * double-check. The next field of cancelled nodes is set to
232 * point to the node itself instead of null, to make life
233 * easier for isOnSyncQueue.
238 * The thread that enqueued this node. Initialized on
239 * construction and nulled out after use.
241 volatile Thread thread;
244 * Link to next node waiting on condition, or the special
245 * value SHARED. Because condition queues are accessed only
246 * when holding in exclusive mode, we just need a simple
247 * linked queue to hold nodes while they are waiting on
248 * conditions. They are then transferred to the queue to
249 * re-acquire. And because conditions can only be exclusive,
250 * we save a field by using special value to indicate shared
256 * Returns true if node is waiting in shared mode
258 final boolean isShared() {
259 return nextWaiter == SHARED;
263 * Returns previous node, or throws NullPointerException if null.
264 * Use when predecessor cannot be null. The null check could
265 * be elided, but is present to help the VM.
267 * @return the predecessor of this node
269 final Node predecessor() throws NullPointerException {
272 throw new NullPointerException();
277 Node() { // Used to establish initial head or SHARED marker
280 Node(Thread thread, Node mode) { // Used by addWaiter
281 this.nextWaiter = mode;
282 this.thread = thread;
285 Node(Thread thread, int waitStatus) { // Used by Condition
286 this.waitStatus = waitStatus;
287 this.thread = thread;
292 * Head of the wait queue, lazily initialized. Except for
293 * initialization, it is modified only via method setHead. Note:
294 * If head exists, its waitStatus is guaranteed not to be
297 private transient volatile Node head;
300 * Tail of the wait queue, lazily initialized. Modified only via
301 * method enq to add new wait node.
303 private transient volatile Node tail;
306 * The synchronization state.
308 private volatile long state;
311 * Returns the current value of synchronization state.
312 * This operation has memory semantics of a <tt>volatile</tt> read.
313 * @return current state value
315 protected final long getState() {
320 * Sets the value of synchronization state.
321 * This operation has memory semantics of a <tt>volatile</tt> write.
322 * @param newState the new state value
324 protected final void setState(long newState) {
329 * Atomically sets synchronization state to the given updated
330 * value if the current state value equals the expected value.
331 * This operation has memory semantics of a <tt>volatile</tt> read
334 * @param expect the expected value
335 * @param update the new value
336 * @return true if successful. False return indicates that the actual
337 * value was not equal to the expected value.
339 protected final boolean compareAndSetState(long expect, long update) {
340 // See below for intrinsics setup to support this
341 if (this.state == expect) {
351 * The number of nanoseconds for which it is faster to spin
352 * rather than to use timed park. A rough estimate suffices
353 * to improve responsiveness with very short timeouts.
355 static final long spinForTimeoutThreshold = 1000L;
358 * Inserts node into queue, initializing if necessary. See picture above.
359 * @param node the node to insert
360 * @return node's predecessor
362 private Node enq(final Node node) {
365 if (t == null) { // Must initialize
366 if (compareAndSetHead(new Node()))
370 if (compareAndSetTail(t, node)) {
379 * Creates and enqueues node for current thread and given mode.
381 * @param mode Node.EXCLUSIVE for exclusive, Node.SHARED for shared
382 * @return the new node
384 private Node addWaiter(Node mode) {
385 Node node = new Node(Thread.currentThread(), mode);
386 // Try the fast path of enq; backup to full enq on failure
390 if (compareAndSetTail(pred, node)) {
400 * Sets head of queue to be node, thus dequeuing. Called only by
401 * acquire methods. Also nulls out unused fields for sake of GC
402 * and to suppress unnecessary signals and traversals.
404 * @param node the node
406 private void setHead(Node node) {
413 * Wakes up node's successor, if one exists.
415 * @param node the node
417 private void unparkSuccessor(Node node) {
419 * If status is negative (i.e., possibly needing signal) try
420 * to clear in anticipation of signalling. It is OK if this
421 * fails or if status is changed by waiting thread.
423 int ws = node.waitStatus;
425 compareAndSetWaitStatus(node, ws, 0);
428 * Thread to unpark is held in successor, which is normally
429 * just the next node. But if cancelled or apparently null,
430 * traverse backwards from tail to find the actual
431 * non-cancelled successor.
434 if (s == null || s.waitStatus > 0) {
436 for (Node t = tail; t != null && t != node; t = t.prev)
437 if (t.waitStatus <= 0)
441 LockSupport.unpark(s.thread);
445 * Release action for shared mode -- signal successor and ensure
446 * propagation. (Note: For exclusive mode, release just amounts
447 * to calling unparkSuccessor of head if it needs signal.)
449 private void doReleaseShared() {
451 * Ensure that a release propagates, even if there are other
452 * in-progress acquires/releases. This proceeds in the usual
453 * way of trying to unparkSuccessor of head if it needs
454 * signal. But if it does not, status is set to PROPAGATE to
455 * ensure that upon release, propagation continues.
456 * Additionally, we must loop in case a new node is added
457 * while we are doing this. Also, unlike other uses of
458 * unparkSuccessor, we need to know if CAS to reset status
459 * fails, if so rechecking.
463 if (h != null && h != tail) {
464 int ws = h.waitStatus;
465 if (ws == Node.SIGNAL) {
466 if (!compareAndSetWaitStatus(h, Node.SIGNAL, 0))
467 continue; // loop to recheck cases
471 !compareAndSetWaitStatus(h, 0, Node.PROPAGATE))
472 continue; // loop on failed CAS
474 if (h == head) // loop if head changed
480 * Sets head of queue, and checks if successor may be waiting
481 * in shared mode, if so propagating if either propagate > 0 or
482 * PROPAGATE status was set.
484 * @param node the node
485 * @param propagate the return value from a tryAcquireShared
487 private void setHeadAndPropagate(Node node, long propagate) {
488 Node h = head; // Record old head for check below
491 * Try to signal next queued node if:
492 * Propagation was indicated by caller,
493 * or was recorded (as h.waitStatus) by a previous operation
494 * (note: this uses sign-check of waitStatus because
495 * PROPAGATE status may transition to SIGNAL.)
497 * The next node is waiting in shared mode,
498 * or we don't know, because it appears null
500 * The conservatism in both of these checks may cause
501 * unnecessary wake-ups, but only when there are multiple
502 * racing acquires/releases, so most need signals now or soon
505 if (propagate > 0 || h == null || h.waitStatus < 0) {
507 if (s == null || s.isShared())
512 // Utilities for various versions of acquire
515 * Cancels an ongoing attempt to acquire.
517 * @param node the node
519 private void cancelAcquire(Node node) {
520 // Ignore if node doesn't exist
526 // Skip cancelled predecessors
527 Node pred = node.prev;
528 while (pred.waitStatus > 0)
529 node.prev = pred = pred.prev;
531 // predNext is the apparent node to unsplice. CASes below will
532 // fail if not, in which case, we lost race vs another cancel
533 // or signal, so no further action is necessary.
534 Node predNext = pred.next;
536 // Can use unconditional write instead of CAS here.
537 // After this atomic step, other Nodes can skip past us.
538 // Before, we are free of interference from other threads.
539 node.waitStatus = Node.CANCELLED;
541 // If we are the tail, remove ourselves.
542 if (node == tail && compareAndSetTail(node, pred)) {
543 compareAndSetNext(pred, predNext, null);
545 // If successor needs signal, try to set pred's next-link
546 // so it will get one. Otherwise wake it up to propagate.
549 ((ws = pred.waitStatus) == Node.SIGNAL ||
550 (ws <= 0 && compareAndSetWaitStatus(pred, ws, Node.SIGNAL))) &&
551 pred.thread != null) {
552 Node next = node.next;
553 if (next != null && next.waitStatus <= 0)
554 compareAndSetNext(pred, predNext, next);
556 unparkSuccessor(node);
559 node.next = node; // help GC
564 * Checks and updates status for a node that failed to acquire.
565 * Returns true if thread should block. This is the main signal
566 * control in all acquire loops. Requires that pred == node.prev
568 * @param pred node's predecessor holding status
569 * @param node the node
570 * @return {@code true} if thread should block
572 private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
573 int ws = pred.waitStatus;
574 if (ws == Node.SIGNAL)
576 * This node has already set status asking a release
577 * to signal it, so it can safely park.
582 * Predecessor was cancelled. Skip over predecessors and
586 node.prev = pred = pred.prev;
587 } while (pred.waitStatus > 0);
591 * waitStatus must be 0 or PROPAGATE. Indicate that we
592 * need a signal, but don't park yet. Caller will need to
593 * retry to make sure it cannot acquire before parking.
595 compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
601 * Convenience method to interrupt current thread.
603 private static void selfInterrupt() {
604 Thread.currentThread().interrupt();
608 * Convenience method to park and then check if interrupted
610 * @return {@code true} if interrupted
612 private final boolean parkAndCheckInterrupt() {
613 LockSupport.park(this);
614 return Thread.interrupted();
618 * Various flavors of acquire, varying in exclusive/shared and
619 * control modes. Each is mostly the same, but annoyingly
620 * different. Only a little bit of factoring is possible due to
621 * interactions of exception mechanics (including ensuring that we
622 * cancel if tryAcquire throws exception) and other control, at
623 * least not without hurting performance too much.
627 * Acquires in exclusive uninterruptible mode for thread already in
628 * queue. Used by condition wait methods as well as acquire.
630 * @param node the node
631 * @param arg the acquire argument
632 * @return {@code true} if interrupted while waiting
634 final boolean acquireQueued(final Node node, long arg) {
635 boolean failed = true;
637 boolean interrupted = false;
639 final Node p = node.predecessor();
640 if (p == head && tryAcquire(arg)) {
642 p.next = null; // help GC
646 if (shouldParkAfterFailedAcquire(p, node) &&
647 parkAndCheckInterrupt())
657 * Acquires in exclusive interruptible mode.
658 * @param arg the acquire argument
660 private void doAcquireInterruptibly(long arg)
661 throws InterruptedException {
662 final Node node = addWaiter(Node.EXCLUSIVE);
663 boolean failed = true;
666 final Node p = node.predecessor();
667 if (p == head && tryAcquire(arg)) {
669 p.next = null; // help GC
673 if (shouldParkAfterFailedAcquire(p, node) &&
674 parkAndCheckInterrupt())
675 throw new InterruptedException();
684 * Acquires in exclusive timed mode.
686 * @param arg the acquire argument
687 * @param nanosTimeout max wait time
688 * @return {@code true} if acquired
690 private boolean doAcquireNanos(long arg, long nanosTimeout)
691 throws InterruptedException {
692 long lastTime = System.nanoTime();
693 final Node node = addWaiter(Node.EXCLUSIVE);
694 boolean failed = true;
697 final Node p = node.predecessor();
698 if (p == head && tryAcquire(arg)) {
700 p.next = null; // help GC
704 if (nanosTimeout <= 0)
706 if (shouldParkAfterFailedAcquire(p, node) &&
707 nanosTimeout > spinForTimeoutThreshold)
708 LockSupport.parkNanos(this, nanosTimeout);
709 long now = System.nanoTime();
710 nanosTimeout -= now - lastTime;
712 if (Thread.interrupted())
713 throw new InterruptedException();
722 * Acquires in shared uninterruptible mode.
723 * @param arg the acquire argument
725 private void doAcquireShared(long arg) {
726 final Node node = addWaiter(Node.SHARED);
727 boolean failed = true;
729 boolean interrupted = false;
731 final Node p = node.predecessor();
733 long r = tryAcquireShared(arg);
735 setHeadAndPropagate(node, r);
736 p.next = null; // help GC
743 if (shouldParkAfterFailedAcquire(p, node) &&
744 parkAndCheckInterrupt())
754 * Acquires in shared interruptible mode.
755 * @param arg the acquire argument
757 private void doAcquireSharedInterruptibly(long arg)
758 throws InterruptedException {
759 final Node node = addWaiter(Node.SHARED);
760 boolean failed = true;
763 final Node p = node.predecessor();
765 long r = tryAcquireShared(arg);
767 setHeadAndPropagate(node, r);
768 p.next = null; // help GC
773 if (shouldParkAfterFailedAcquire(p, node) &&
774 parkAndCheckInterrupt())
775 throw new InterruptedException();
784 * Acquires in shared timed mode.
786 * @param arg the acquire argument
787 * @param nanosTimeout max wait time
788 * @return {@code true} if acquired
790 private boolean doAcquireSharedNanos(long arg, long nanosTimeout)
791 throws InterruptedException {
793 long lastTime = System.nanoTime();
794 final Node node = addWaiter(Node.SHARED);
795 boolean failed = true;
798 final Node p = node.predecessor();
800 long r = tryAcquireShared(arg);
802 setHeadAndPropagate(node, r);
803 p.next = null; // help GC
808 if (nanosTimeout <= 0)
810 if (shouldParkAfterFailedAcquire(p, node) &&
811 nanosTimeout > spinForTimeoutThreshold)
812 LockSupport.parkNanos(this, nanosTimeout);
813 long now = System.nanoTime();
814 nanosTimeout -= now - lastTime;
816 if (Thread.interrupted())
817 throw new InterruptedException();
825 // Main exported methods
828 * Attempts to acquire in exclusive mode. This method should query
829 * if the state of the object permits it to be acquired in the
830 * exclusive mode, and if so to acquire it.
832 * <p>This method is always invoked by the thread performing
833 * acquire. If this method reports failure, the acquire method
834 * may queue the thread, if it is not already queued, until it is
835 * signalled by a release from some other thread. This can be used
836 * to implement method {@link Lock#tryLock()}.
839 * implementation throws {@link UnsupportedOperationException}.
841 * @param arg the acquire argument. This value is always the one
842 * passed to an acquire method, or is the value saved on entry
843 * to a condition wait. The value is otherwise uninterpreted
844 * and can represent anything you like.
845 * @return {@code true} if successful. Upon success, this object has
847 * @throws IllegalMonitorStateException if acquiring would place this
848 * synchronizer in an illegal state. This exception must be
849 * thrown in a consistent fashion for synchronization to work
851 * @throws UnsupportedOperationException if exclusive mode is not supported
853 protected boolean tryAcquire(long arg) {
854 throw new UnsupportedOperationException();
858 * Attempts to set the state to reflect a release in exclusive
861 * <p>This method is always invoked by the thread performing release.
863 * <p>The default implementation throws
864 * {@link UnsupportedOperationException}.
866 * @param arg the release argument. This value is always the one
867 * passed to a release method, or the current state value upon
868 * entry to a condition wait. The value is otherwise
869 * uninterpreted and can represent anything you like.
870 * @return {@code true} if this object is now in a fully released
871 * state, so that any waiting threads may attempt to acquire;
872 * and {@code false} otherwise.
873 * @throws IllegalMonitorStateException if releasing would place this
874 * synchronizer in an illegal state. This exception must be
875 * thrown in a consistent fashion for synchronization to work
877 * @throws UnsupportedOperationException if exclusive mode is not supported
879 protected boolean tryRelease(long arg) {
880 throw new UnsupportedOperationException();
884 * Attempts to acquire in shared mode. This method should query if
885 * the state of the object permits it to be acquired in the shared
886 * mode, and if so to acquire it.
888 * <p>This method is always invoked by the thread performing
889 * acquire. If this method reports failure, the acquire method
890 * may queue the thread, if it is not already queued, until it is
891 * signalled by a release from some other thread.
893 * <p>The default implementation throws {@link
894 * UnsupportedOperationException}.
896 * @param arg the acquire argument. This value is always the one
897 * passed to an acquire method, or is the value saved on entry
898 * to a condition wait. The value is otherwise uninterpreted
899 * and can represent anything you like.
900 * @return a negative value on failure; zero if acquisition in shared
901 * mode succeeded but no subsequent shared-mode acquire can
902 * succeed; and a positive value if acquisition in shared
903 * mode succeeded and subsequent shared-mode acquires might
904 * also succeed, in which case a subsequent waiting thread
905 * must check availability. (Support for three different
906 * return values enables this method to be used in contexts
907 * where acquires only sometimes act exclusively.) Upon
908 * success, this object has been acquired.
909 * @throws IllegalMonitorStateException if acquiring would place this
910 * synchronizer in an illegal state. This exception must be
911 * thrown in a consistent fashion for synchronization to work
913 * @throws UnsupportedOperationException if shared mode is not supported
915 protected long tryAcquireShared(long arg) {
916 throw new UnsupportedOperationException();
920 * Attempts to set the state to reflect a release in shared mode.
922 * <p>This method is always invoked by the thread performing release.
924 * <p>The default implementation throws
925 * {@link UnsupportedOperationException}.
927 * @param arg the release argument. This value is always the one
928 * passed to a release method, or the current state value upon
929 * entry to a condition wait. The value is otherwise
930 * uninterpreted and can represent anything you like.
931 * @return {@code true} if this release of shared mode may permit a
932 * waiting acquire (shared or exclusive) to succeed; and
933 * {@code false} otherwise
934 * @throws IllegalMonitorStateException if releasing would place this
935 * synchronizer in an illegal state. This exception must be
936 * thrown in a consistent fashion for synchronization to work
938 * @throws UnsupportedOperationException if shared mode is not supported
940 protected boolean tryReleaseShared(long arg) {
941 throw new UnsupportedOperationException();
945 * Returns {@code true} if synchronization is held exclusively with
946 * respect to the current (calling) thread. This method is invoked
947 * upon each call to a non-waiting {@link ConditionObject} method.
948 * (Waiting methods instead invoke {@link #release}.)
950 * <p>The default implementation throws {@link
951 * UnsupportedOperationException}. This method is invoked
952 * internally only within {@link ConditionObject} methods, so need
953 * not be defined if conditions are not used.
955 * @return {@code true} if synchronization is held exclusively;
956 * {@code false} otherwise
957 * @throws UnsupportedOperationException if conditions are not supported
959 protected boolean isHeldExclusively() {
960 throw new UnsupportedOperationException();
964 * Acquires in exclusive mode, ignoring interrupts. Implemented
965 * by invoking at least once {@link #tryAcquire},
966 * returning on success. Otherwise the thread is queued, possibly
967 * repeatedly blocking and unblocking, invoking {@link
968 * #tryAcquire} until success. This method can be used
969 * to implement method {@link Lock#lock}.
971 * @param arg the acquire argument. This value is conveyed to
972 * {@link #tryAcquire} but is otherwise uninterpreted and
973 * can represent anything you like.
975 public final void acquire(long arg) {
976 if (!tryAcquire(arg) &&
977 acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
982 * Acquires in exclusive mode, aborting if interrupted.
983 * Implemented by first checking interrupt status, then invoking
984 * at least once {@link #tryAcquire}, returning on
985 * success. Otherwise the thread is queued, possibly repeatedly
986 * blocking and unblocking, invoking {@link #tryAcquire}
987 * until success or the thread is interrupted. This method can be
988 * used to implement method {@link Lock#lockInterruptibly}.
990 * @param arg the acquire argument. This value is conveyed to
991 * {@link #tryAcquire} but is otherwise uninterpreted and
992 * can represent anything you like.
993 * @throws InterruptedException if the current thread is interrupted
995 public final void acquireInterruptibly(long arg)
996 throws InterruptedException {
997 if (Thread.interrupted())
998 throw new InterruptedException();
999 if (!tryAcquire(arg))
1000 doAcquireInterruptibly(arg);
1004 * Attempts to acquire in exclusive mode, aborting if interrupted,
1005 * and failing if the given timeout elapses. Implemented by first
1006 * checking interrupt status, then invoking at least once {@link
1007 * #tryAcquire}, returning on success. Otherwise, the thread is
1008 * queued, possibly repeatedly blocking and unblocking, invoking
1009 * {@link #tryAcquire} until success or the thread is interrupted
1010 * or the timeout elapses. This method can be used to implement
1011 * method {@link Lock#tryLock(long, TimeUnit)}.
1013 * @param arg the acquire argument. This value is conveyed to
1014 * {@link #tryAcquire} but is otherwise uninterpreted and
1015 * can represent anything you like.
1016 * @param nanosTimeout the maximum number of nanoseconds to wait
1017 * @return {@code true} if acquired; {@code false} if timed out
1018 * @throws InterruptedException if the current thread is interrupted
1020 public final boolean tryAcquireNanos(long arg, long nanosTimeout)
1021 throws InterruptedException {
1022 if (Thread.interrupted())
1023 throw new InterruptedException();
1024 return tryAcquire(arg) ||
1025 doAcquireNanos(arg, nanosTimeout);
1029 * Releases in exclusive mode. Implemented by unblocking one or
1030 * more threads if {@link #tryRelease} returns true.
1031 * This method can be used to implement method {@link Lock#unlock}.
1033 * @param arg the release argument. This value is conveyed to
1034 * {@link #tryRelease} but is otherwise uninterpreted and
1035 * can represent anything you like.
1036 * @return the value returned from {@link #tryRelease}
1038 public final boolean release(long arg) {
1039 if (tryRelease(arg)) {
1041 if (h != null && h.waitStatus != 0)
1049 * Acquires in shared mode, ignoring interrupts. Implemented by
1050 * first invoking at least once {@link #tryAcquireShared},
1051 * returning on success. Otherwise the thread is queued, possibly
1052 * repeatedly blocking and unblocking, invoking {@link
1053 * #tryAcquireShared} until success.
1055 * @param arg the acquire argument. This value is conveyed to
1056 * {@link #tryAcquireShared} but is otherwise uninterpreted
1057 * and can represent anything you like.
1059 public final void acquireShared(long arg) {
1060 if (tryAcquireShared(arg) < 0)
1061 doAcquireShared(arg);
1065 * Acquires in shared mode, aborting if interrupted. Implemented
1066 * by first checking interrupt status, then invoking at least once
1067 * {@link #tryAcquireShared}, returning on success. Otherwise the
1068 * thread is queued, possibly repeatedly blocking and unblocking,
1069 * invoking {@link #tryAcquireShared} until success or the thread
1071 * @param arg the acquire argument
1072 * This value is conveyed to {@link #tryAcquireShared} but is
1073 * otherwise uninterpreted and can represent anything
1075 * @throws InterruptedException if the current thread is interrupted
1077 public final void acquireSharedInterruptibly(long arg)
1078 throws InterruptedException {
1079 if (Thread.interrupted())
1080 throw new InterruptedException();
1081 if (tryAcquireShared(arg) < 0)
1082 doAcquireSharedInterruptibly(arg);
1086 * Attempts to acquire in shared mode, aborting if interrupted, and
1087 * failing if the given timeout elapses. Implemented by first
1088 * checking interrupt status, then invoking at least once {@link
1089 * #tryAcquireShared}, returning on success. Otherwise, the
1090 * thread is queued, possibly repeatedly blocking and unblocking,
1091 * invoking {@link #tryAcquireShared} until success or the thread
1092 * is interrupted or the timeout elapses.
1094 * @param arg the acquire argument. This value is conveyed to
1095 * {@link #tryAcquireShared} but is otherwise uninterpreted
1096 * and can represent anything you like.
1097 * @param nanosTimeout the maximum number of nanoseconds to wait
1098 * @return {@code true} if acquired; {@code false} if timed out
1099 * @throws InterruptedException if the current thread is interrupted
1101 public final boolean tryAcquireSharedNanos(long arg, long nanosTimeout)
1102 throws InterruptedException {
1103 if (Thread.interrupted())
1104 throw new InterruptedException();
1105 return tryAcquireShared(arg) >= 0 ||
1106 doAcquireSharedNanos(arg, nanosTimeout);
1110 * Releases in shared mode. Implemented by unblocking one or more
1111 * threads if {@link #tryReleaseShared} returns true.
1113 * @param arg the release argument. This value is conveyed to
1114 * {@link #tryReleaseShared} but is otherwise uninterpreted
1115 * and can represent anything you like.
1116 * @return the value returned from {@link #tryReleaseShared}
1118 public final boolean releaseShared(long arg) {
1119 if (tryReleaseShared(arg)) {
1126 // Queue inspection methods
1129 * Queries whether any threads are waiting to acquire. Note that
1130 * because cancellations due to interrupts and timeouts may occur
1131 * at any time, a {@code true} return does not guarantee that any
1132 * other thread will ever acquire.
1134 * <p>In this implementation, this operation returns in
1137 * @return {@code true} if there may be other threads waiting to acquire
1139 public final boolean hasQueuedThreads() {
1140 return head != tail;
1144 * Queries whether any threads have ever contended to acquire this
1145 * synchronizer; that is if an acquire method has ever blocked.
1147 * <p>In this implementation, this operation returns in
1150 * @return {@code true} if there has ever been contention
1152 public final boolean hasContended() {
1153 return head != null;
1157 * Returns the first (longest-waiting) thread in the queue, or
1158 * {@code null} if no threads are currently queued.
1160 * <p>In this implementation, this operation normally returns in
1161 * constant time, but may iterate upon contention if other threads are
1162 * concurrently modifying the queue.
1164 * @return the first (longest-waiting) thread in the queue, or
1165 * {@code null} if no threads are currently queued
1167 public final Thread getFirstQueuedThread() {
1168 // handle only fast path, else relay
1169 return (head == tail) ? null : fullGetFirstQueuedThread();
1173 * Version of getFirstQueuedThread called when fastpath fails
1175 private Thread fullGetFirstQueuedThread() {
1177 * The first node is normally head.next. Try to get its
1178 * thread field, ensuring consistent reads: If thread
1179 * field is nulled out or s.prev is no longer head, then
1180 * some other thread(s) concurrently performed setHead in
1181 * between some of our reads. We try this twice before
1182 * resorting to traversal.
1186 if (((h = head) != null && (s = h.next) != null &&
1187 s.prev == head && (st = s.thread) != null) ||
1188 ((h = head) != null && (s = h.next) != null &&
1189 s.prev == head && (st = s.thread) != null))
1193 * Head's next field might not have been set yet, or may have
1194 * been unset after setHead. So we must check to see if tail
1195 * is actually first node. If not, we continue on, safely
1196 * traversing from tail back to head to find first,
1197 * guaranteeing termination.
1201 Thread firstThread = null;
1202 while (t != null && t != head) {
1203 Thread tt = t.thread;
1212 * Returns true if the given thread is currently queued.
1214 * <p>This implementation traverses the queue to determine
1215 * presence of the given thread.
1217 * @param thread the thread
1218 * @return {@code true} if the given thread is on the queue
1219 * @throws NullPointerException if the thread is null
1221 public final boolean isQueued(Thread thread) {
1223 throw new NullPointerException();
1224 for (Node p = tail; p != null; p = p.prev)
1225 if (p.thread == thread)
1231 * Returns {@code true} if the apparent first queued thread, if one
1232 * exists, is waiting in exclusive mode. If this method returns
1233 * {@code true}, and the current thread is attempting to acquire in
1234 * shared mode (that is, this method is invoked from {@link
1235 * #tryAcquireShared}) then it is guaranteed that the current thread
1236 * is not the first queued thread. Used only as a heuristic in
1237 * ReentrantReadWriteLock.
1239 final boolean apparentlyFirstQueuedIsExclusive() {
1241 return (h = head) != null &&
1242 (s = h.next) != null &&
1248 * Queries whether any threads have been waiting to acquire longer
1249 * than the current thread.
1251 * <p>An invocation of this method is equivalent to (but may be
1252 * more efficient than):
1254 * getFirstQueuedThread() != Thread.currentThread() &&
1255 * hasQueuedThreads()}</pre>
1257 * <p>Note that because cancellations due to interrupts and
1258 * timeouts may occur at any time, a {@code true} return does not
1259 * guarantee that some other thread will acquire before the current
1260 * thread. Likewise, it is possible for another thread to win a
1261 * race to enqueue after this method has returned {@code false},
1262 * due to the queue being empty.
1264 * <p>This method is designed to be used by a fair synchronizer to
1265 * avoid <a href="AbstractQueuedSynchronizer#barging">barging</a>.
1266 * Such a synchronizer's {@link #tryAcquire} method should return
1267 * {@code false}, and its {@link #tryAcquireShared} method should
1268 * return a negative value, if this method returns {@code true}
1269 * (unless this is a reentrant acquire). For example, the {@code
1270 * tryAcquire} method for a fair, reentrant, exclusive mode
1271 * synchronizer might look like this:
1274 * protected boolean tryAcquire(int arg) {
1275 * if (isHeldExclusively()) {
1276 * // A reentrant acquire; increment hold count
1278 * } else if (hasQueuedPredecessors()) {
1281 * // try to acquire normally
1285 * @return {@code true} if there is a queued thread preceding the
1286 * current thread, and {@code false} if the current thread
1287 * is at the head of the queue or the queue is empty
1290 public final boolean hasQueuedPredecessors() {
1291 // The correctness of this depends on head being initialized
1292 // before tail and on head.next being accurate if the current
1293 // thread is first in queue.
1294 Node t = tail; // Read fields in reverse initialization order
1298 ((s = h.next) == null || s.thread != Thread.currentThread());
1302 // Instrumentation and monitoring methods
1305 * Returns an estimate of the number of threads waiting to
1306 * acquire. The value is only an estimate because the number of
1307 * threads may change dynamically while this method traverses
1308 * internal data structures. This method is designed for use in
1309 * monitoring system state, not for synchronization
1312 * @return the estimated number of threads waiting to acquire
1314 public final int getQueueLength() {
1316 for (Node p = tail; p != null; p = p.prev) {
1317 if (p.thread != null)
1324 * Returns a collection containing threads that may be waiting to
1325 * acquire. Because the actual set of threads may change
1326 * dynamically while constructing this result, the returned
1327 * collection is only a best-effort estimate. The elements of the
1328 * returned collection are in no particular order. This method is
1329 * designed to facilitate construction of subclasses that provide
1330 * more extensive monitoring facilities.
1332 * @return the collection of threads
1334 public final Collection<Thread> getQueuedThreads() {
1335 ArrayList<Thread> list = new ArrayList<Thread>();
1336 for (Node p = tail; p != null; p = p.prev) {
1337 Thread t = p.thread;
1345 * Returns a collection containing threads that may be waiting to
1346 * acquire in exclusive mode. This has the same properties
1347 * as {@link #getQueuedThreads} except that it only returns
1348 * those threads waiting due to an exclusive acquire.
1350 * @return the collection of threads
1352 public final Collection<Thread> getExclusiveQueuedThreads() {
1353 ArrayList<Thread> list = new ArrayList<Thread>();
1354 for (Node p = tail; p != null; p = p.prev) {
1355 if (!p.isShared()) {
1356 Thread t = p.thread;
1365 * Returns a collection containing threads that may be waiting to
1366 * acquire in shared mode. This has the same properties
1367 * as {@link #getQueuedThreads} except that it only returns
1368 * those threads waiting due to a shared acquire.
1370 * @return the collection of threads
1372 public final Collection<Thread> getSharedQueuedThreads() {
1373 ArrayList<Thread> list = new ArrayList<Thread>();
1374 for (Node p = tail; p != null; p = p.prev) {
1376 Thread t = p.thread;
1385 * Returns a string identifying this synchronizer, as well as its state.
1386 * The state, in brackets, includes the String {@code "State ="}
1387 * followed by the current value of {@link #getState}, and either
1388 * {@code "nonempty"} or {@code "empty"} depending on whether the
1391 * @return a string identifying this synchronizer, as well as its state
1393 public String toString() {
1394 long s = getState();
1395 String q = hasQueuedThreads() ? "non" : "";
1396 return super.toString() +
1397 "[State = " + s + ", " + q + "empty queue]";
1401 // Internal support methods for Conditions
1404 * Returns true if a node, always one that was initially placed on
1405 * a condition queue, is now waiting to reacquire on sync queue.
1406 * @param node the node
1407 * @return true if is reacquiring
1409 final boolean isOnSyncQueue(Node node) {
1410 if (node.waitStatus == Node.CONDITION || node.prev == null)
1412 if (node.next != null) // If has successor, it must be on queue
1415 * node.prev can be non-null, but not yet on queue because
1416 * the CAS to place it on queue can fail. So we have to
1417 * traverse from tail to make sure it actually made it. It
1418 * will always be near the tail in calls to this method, and
1419 * unless the CAS failed (which is unlikely), it will be
1420 * there, so we hardly ever traverse much.
1422 return findNodeFromTail(node);
1426 * Returns true if node is on sync queue by searching backwards from tail.
1427 * Called only when needed by isOnSyncQueue.
1428 * @return true if present
1430 private boolean findNodeFromTail(Node node) {
1442 * Transfers a node from a condition queue onto sync queue.
1443 * Returns true if successful.
1444 * @param node the node
1445 * @return true if successfully transferred (else the node was
1446 * cancelled before signal).
1448 final boolean transferForSignal(Node node) {
1450 * If cannot change waitStatus, the node has been cancelled.
1452 if (!compareAndSetWaitStatus(node, Node.CONDITION, 0))
1456 * Splice onto queue and try to set waitStatus of predecessor to
1457 * indicate that thread is (probably) waiting. If cancelled or
1458 * attempt to set waitStatus fails, wake up to resync (in which
1459 * case the waitStatus can be transiently and harmlessly wrong).
1462 int ws = p.waitStatus;
1463 if (ws > 0 || !compareAndSetWaitStatus(p, ws, Node.SIGNAL))
1464 LockSupport.unpark(node.thread);
1469 * Transfers node, if necessary, to sync queue after a cancelled
1470 * wait. Returns true if thread was cancelled before being
1472 * @param current the waiting thread
1473 * @param node its node
1474 * @return true if cancelled before the node was signalled
1476 final boolean transferAfterCancelledWait(Node node) {
1477 if (compareAndSetWaitStatus(node, Node.CONDITION, 0)) {
1482 * If we lost out to a signal(), then we can't proceed
1483 * until it finishes its enq(). Cancelling during an
1484 * incomplete transfer is both rare and transient, so just
1487 while (!isOnSyncQueue(node))
1493 * Invokes release with current state value; returns saved state.
1494 * Cancels node and throws exception on failure.
1495 * @param node the condition node for this wait
1496 * @return previous sync state
1498 final long fullyRelease(Node node) {
1499 boolean failed = true;
1501 long savedState = getState();
1502 if (release(savedState)) {
1506 throw new IllegalMonitorStateException();
1510 node.waitStatus = Node.CANCELLED;
1514 // Instrumentation methods for conditions
1517 * Queries whether the given ConditionObject
1518 * uses this synchronizer as its lock.
1520 * @param condition the condition
1521 * @return <tt>true</tt> if owned
1522 * @throws NullPointerException if the condition is null
1524 public final boolean owns(ConditionObject condition) {
1525 if (condition == null)
1526 throw new NullPointerException();
1527 return condition.isOwnedBy(this);
1531 * Queries whether any threads are waiting on the given condition
1532 * associated with this synchronizer. Note that because timeouts
1533 * and interrupts may occur at any time, a <tt>true</tt> return
1534 * does not guarantee that a future <tt>signal</tt> will awaken
1535 * any threads. This method is designed primarily for use in
1536 * monitoring of the system state.
1538 * @param condition the condition
1539 * @return <tt>true</tt> if there are any waiting threads
1540 * @throws IllegalMonitorStateException if exclusive synchronization
1542 * @throws IllegalArgumentException if the given condition is
1543 * not associated with this synchronizer
1544 * @throws NullPointerException if the condition is null
1546 public final boolean hasWaiters(ConditionObject condition) {
1547 if (!owns(condition))
1548 throw new IllegalArgumentException("Not owner");
1549 return condition.hasWaiters();
1553 * Returns an estimate of the number of threads waiting on the
1554 * given condition associated with this synchronizer. Note that
1555 * because timeouts and interrupts may occur at any time, the
1556 * estimate serves only as an upper bound on the actual number of
1557 * waiters. This method is designed for use in monitoring of the
1558 * system state, not for synchronization control.
1560 * @param condition the condition
1561 * @return the estimated number of waiting threads
1562 * @throws IllegalMonitorStateException if exclusive synchronization
1564 * @throws IllegalArgumentException if the given condition is
1565 * not associated with this synchronizer
1566 * @throws NullPointerException if the condition is null
1568 public final int getWaitQueueLength(ConditionObject condition) {
1569 if (!owns(condition))
1570 throw new IllegalArgumentException("Not owner");
1571 return condition.getWaitQueueLength();
1575 * Returns a collection containing those threads that may be
1576 * waiting on the given condition associated with this
1577 * synchronizer. Because the actual set of threads may change
1578 * dynamically while constructing this result, the returned
1579 * collection is only a best-effort estimate. The elements of the
1580 * returned collection are in no particular order.
1582 * @param condition the condition
1583 * @return the collection of threads
1584 * @throws IllegalMonitorStateException if exclusive synchronization
1586 * @throws IllegalArgumentException if the given condition is
1587 * not associated with this synchronizer
1588 * @throws NullPointerException if the condition is null
1590 public final Collection<Thread> getWaitingThreads(ConditionObject condition) {
1591 if (!owns(condition))
1592 throw new IllegalArgumentException("Not owner");
1593 return condition.getWaitingThreads();
1597 * Condition implementation for a {@link
1598 * AbstractQueuedLongSynchronizer} serving as the basis of a {@link
1599 * Lock} implementation.
1601 * <p>Method documentation for this class describes mechanics,
1602 * not behavioral specifications from the point of view of Lock
1603 * and Condition users. Exported versions of this class will in
1604 * general need to be accompanied by documentation describing
1605 * condition semantics that rely on those of the associated
1606 * <tt>AbstractQueuedLongSynchronizer</tt>.
1608 * <p>This class is Serializable, but all fields are transient,
1609 * so deserialized conditions have no waiters.
1613 public class ConditionObject implements Condition, java.io.Serializable {
1614 private static final long serialVersionUID = 1173984872572414699L;
1615 /** First node of condition queue. */
1616 private transient Node firstWaiter;
1617 /** Last node of condition queue. */
1618 private transient Node lastWaiter;
1621 * Creates a new <tt>ConditionObject</tt> instance.
1623 public ConditionObject() { }
1628 * Adds a new waiter to wait queue.
1629 * @return its new wait node
1631 private Node addConditionWaiter() {
1632 Node t = lastWaiter;
1633 // If lastWaiter is cancelled, clean out.
1634 if (t != null && t.waitStatus != Node.CONDITION) {
1635 unlinkCancelledWaiters();
1638 Node node = new Node(Thread.currentThread(), Node.CONDITION);
1642 t.nextWaiter = node;
1648 * Removes and transfers nodes until hit non-cancelled one or
1649 * null. Split out from signal in part to encourage compilers
1650 * to inline the case of no waiters.
1651 * @param first (non-null) the first node on condition queue
1653 private void doSignal(Node first) {
1655 if ( (firstWaiter = first.nextWaiter) == null)
1657 first.nextWaiter = null;
1658 } while (!transferForSignal(first) &&
1659 (first = firstWaiter) != null);
1663 * Removes and transfers all nodes.
1664 * @param first (non-null) the first node on condition queue
1666 private void doSignalAll(Node first) {
1667 lastWaiter = firstWaiter = null;
1669 Node next = first.nextWaiter;
1670 first.nextWaiter = null;
1671 transferForSignal(first);
1673 } while (first != null);
1677 * Unlinks cancelled waiter nodes from condition queue.
1678 * Called only while holding lock. This is called when
1679 * cancellation occurred during condition wait, and upon
1680 * insertion of a new waiter when lastWaiter is seen to have
1681 * been cancelled. This method is needed to avoid garbage
1682 * retention in the absence of signals. So even though it may
1683 * require a full traversal, it comes into play only when
1684 * timeouts or cancellations occur in the absence of
1685 * signals. It traverses all nodes rather than stopping at a
1686 * particular target to unlink all pointers to garbage nodes
1687 * without requiring many re-traversals during cancellation
1690 private void unlinkCancelledWaiters() {
1691 Node t = firstWaiter;
1694 Node next = t.nextWaiter;
1695 if (t.waitStatus != Node.CONDITION) {
1696 t.nextWaiter = null;
1700 trail.nextWaiter = next;
1713 * Moves the longest-waiting thread, if one exists, from the
1714 * wait queue for this condition to the wait queue for the
1717 * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
1718 * returns {@code false}
1720 public final void signal() {
1721 if (!isHeldExclusively())
1722 throw new IllegalMonitorStateException();
1723 Node first = firstWaiter;
1729 * Moves all threads from the wait queue for this condition to
1730 * the wait queue for the owning lock.
1732 * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
1733 * returns {@code false}
1735 public final void signalAll() {
1736 if (!isHeldExclusively())
1737 throw new IllegalMonitorStateException();
1738 Node first = firstWaiter;
1744 * Implements uninterruptible condition wait.
1746 * <li> Save lock state returned by {@link #getState}.
1747 * <li> Invoke {@link #release} with
1748 * saved state as argument, throwing
1749 * IllegalMonitorStateException if it fails.
1750 * <li> Block until signalled.
1751 * <li> Reacquire by invoking specialized version of
1752 * {@link #acquire} with saved state as argument.
1755 public final void awaitUninterruptibly() {
1756 Node node = addConditionWaiter();
1757 long savedState = fullyRelease(node);
1758 boolean interrupted = false;
1759 while (!isOnSyncQueue(node)) {
1760 LockSupport.park(this);
1761 if (Thread.interrupted())
1764 if (acquireQueued(node, savedState) || interrupted)
1769 * For interruptible waits, we need to track whether to throw
1770 * InterruptedException, if interrupted while blocked on
1771 * condition, versus reinterrupt current thread, if
1772 * interrupted while blocked waiting to re-acquire.
1775 /** Mode meaning to reinterrupt on exit from wait */
1776 private static final int REINTERRUPT = 1;
1777 /** Mode meaning to throw InterruptedException on exit from wait */
1778 private static final int THROW_IE = -1;
1781 * Checks for interrupt, returning THROW_IE if interrupted
1782 * before signalled, REINTERRUPT if after signalled, or
1783 * 0 if not interrupted.
1785 private int checkInterruptWhileWaiting(Node node) {
1786 return Thread.interrupted() ?
1787 (transferAfterCancelledWait(node) ? THROW_IE : REINTERRUPT) :
1792 * Throws InterruptedException, reinterrupts current thread, or
1793 * does nothing, depending on mode.
1795 private void reportInterruptAfterWait(int interruptMode)
1796 throws InterruptedException {
1797 if (interruptMode == THROW_IE)
1798 throw new InterruptedException();
1799 else if (interruptMode == REINTERRUPT)
1804 * Implements interruptible condition wait.
1806 * <li> If current thread is interrupted, throw InterruptedException.
1807 * <li> Save lock state returned by {@link #getState}.
1808 * <li> Invoke {@link #release} with
1809 * saved state as argument, throwing
1810 * IllegalMonitorStateException if it fails.
1811 * <li> Block until signalled or interrupted.
1812 * <li> Reacquire by invoking specialized version of
1813 * {@link #acquire} with saved state as argument.
1814 * <li> If interrupted while blocked in step 4, throw InterruptedException.
1817 public final void await() throws InterruptedException {
1818 if (Thread.interrupted())
1819 throw new InterruptedException();
1820 Node node = addConditionWaiter();
1821 long savedState = fullyRelease(node);
1822 int interruptMode = 0;
1823 while (!isOnSyncQueue(node)) {
1824 LockSupport.park(this);
1825 if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
1828 if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
1829 interruptMode = REINTERRUPT;
1830 if (node.nextWaiter != null) // clean up if cancelled
1831 unlinkCancelledWaiters();
1832 if (interruptMode != 0)
1833 reportInterruptAfterWait(interruptMode);
1837 * Implements timed condition wait.
1839 * <li> If current thread is interrupted, throw InterruptedException.
1840 * <li> Save lock state returned by {@link #getState}.
1841 * <li> Invoke {@link #release} with
1842 * saved state as argument, throwing
1843 * IllegalMonitorStateException if it fails.
1844 * <li> Block until signalled, interrupted, or timed out.
1845 * <li> Reacquire by invoking specialized version of
1846 * {@link #acquire} with saved state as argument.
1847 * <li> If interrupted while blocked in step 4, throw InterruptedException.
1850 public final long awaitNanos(long nanosTimeout)
1851 throws InterruptedException {
1852 if (Thread.interrupted())
1853 throw new InterruptedException();
1854 Node node = addConditionWaiter();
1855 long savedState = fullyRelease(node);
1856 long lastTime = System.nanoTime();
1857 int interruptMode = 0;
1858 while (!isOnSyncQueue(node)) {
1859 if (nanosTimeout <= 0L) {
1860 transferAfterCancelledWait(node);
1863 LockSupport.parkNanos(this, nanosTimeout);
1864 if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
1867 long now = System.nanoTime();
1868 nanosTimeout -= now - lastTime;
1871 if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
1872 interruptMode = REINTERRUPT;
1873 if (node.nextWaiter != null)
1874 unlinkCancelledWaiters();
1875 if (interruptMode != 0)
1876 reportInterruptAfterWait(interruptMode);
1877 return nanosTimeout - (System.nanoTime() - lastTime);
1881 * Implements absolute timed condition wait.
1883 * <li> If current thread is interrupted, throw InterruptedException.
1884 * <li> Save lock state returned by {@link #getState}.
1885 * <li> Invoke {@link #release} with
1886 * saved state as argument, throwing
1887 * IllegalMonitorStateException if it fails.
1888 * <li> Block until signalled, interrupted, or timed out.
1889 * <li> Reacquire by invoking specialized version of
1890 * {@link #acquire} with saved state as argument.
1891 * <li> If interrupted while blocked in step 4, throw InterruptedException.
1892 * <li> If timed out while blocked in step 4, return false, else true.
1895 public final boolean awaitUntil(Date deadline)
1896 throws InterruptedException {
1897 if (deadline == null)
1898 throw new NullPointerException();
1899 long abstime = deadline.getTime();
1900 if (Thread.interrupted())
1901 throw new InterruptedException();
1902 Node node = addConditionWaiter();
1903 long savedState = fullyRelease(node);
1904 boolean timedout = false;
1905 int interruptMode = 0;
1906 while (!isOnSyncQueue(node)) {
1907 if (System.currentTimeMillis() > abstime) {
1908 timedout = transferAfterCancelledWait(node);
1911 LockSupport.parkUntil(this, abstime);
1912 if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
1915 if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
1916 interruptMode = REINTERRUPT;
1917 if (node.nextWaiter != null)
1918 unlinkCancelledWaiters();
1919 if (interruptMode != 0)
1920 reportInterruptAfterWait(interruptMode);
1925 * Implements timed condition wait.
1927 * <li> If current thread is interrupted, throw InterruptedException.
1928 * <li> Save lock state returned by {@link #getState}.
1929 * <li> Invoke {@link #release} with
1930 * saved state as argument, throwing
1931 * IllegalMonitorStateException if it fails.
1932 * <li> Block until signalled, interrupted, or timed out.
1933 * <li> Reacquire by invoking specialized version of
1934 * {@link #acquire} with saved state as argument.
1935 * <li> If interrupted while blocked in step 4, throw InterruptedException.
1936 * <li> If timed out while blocked in step 4, return false, else true.
1939 public final boolean await(long time, TimeUnit unit)
1940 throws InterruptedException {
1942 throw new NullPointerException();
1943 long nanosTimeout = unit.toNanos(time);
1944 if (Thread.interrupted())
1945 throw new InterruptedException();
1946 Node node = addConditionWaiter();
1947 long savedState = fullyRelease(node);
1948 long lastTime = System.nanoTime();
1949 boolean timedout = false;
1950 int interruptMode = 0;
1951 while (!isOnSyncQueue(node)) {
1952 if (nanosTimeout <= 0L) {
1953 timedout = transferAfterCancelledWait(node);
1956 if (nanosTimeout >= spinForTimeoutThreshold)
1957 LockSupport.parkNanos(this, nanosTimeout);
1958 if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
1960 long now = System.nanoTime();
1961 nanosTimeout -= now - lastTime;
1964 if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
1965 interruptMode = REINTERRUPT;
1966 if (node.nextWaiter != null)
1967 unlinkCancelledWaiters();
1968 if (interruptMode != 0)
1969 reportInterruptAfterWait(interruptMode);
1973 // support for instrumentation
1976 * Returns true if this condition was created by the given
1977 * synchronization object.
1979 * @return {@code true} if owned
1981 final boolean isOwnedBy(AbstractQueuedLongSynchronizer sync) {
1982 return sync == AbstractQueuedLongSynchronizer.this;
1986 * Queries whether any threads are waiting on this condition.
1987 * Implements {@link AbstractQueuedLongSynchronizer#hasWaiters}.
1989 * @return {@code true} if there are any waiting threads
1990 * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
1991 * returns {@code false}
1993 protected final boolean hasWaiters() {
1994 if (!isHeldExclusively())
1995 throw new IllegalMonitorStateException();
1996 for (Node w = firstWaiter; w != null; w = w.nextWaiter) {
1997 if (w.waitStatus == Node.CONDITION)
2004 * Returns an estimate of the number of threads waiting on
2006 * Implements {@link AbstractQueuedLongSynchronizer#getWaitQueueLength}.
2008 * @return the estimated number of waiting threads
2009 * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
2010 * returns {@code false}
2012 protected final int getWaitQueueLength() {
2013 if (!isHeldExclusively())
2014 throw new IllegalMonitorStateException();
2016 for (Node w = firstWaiter; w != null; w = w.nextWaiter) {
2017 if (w.waitStatus == Node.CONDITION)
2024 * Returns a collection containing those threads that may be
2025 * waiting on this Condition.
2026 * Implements {@link AbstractQueuedLongSynchronizer#getWaitingThreads}.
2028 * @return the collection of threads
2029 * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
2030 * returns {@code false}
2032 protected final Collection<Thread> getWaitingThreads() {
2033 if (!isHeldExclusively())
2034 throw new IllegalMonitorStateException();
2035 ArrayList<Thread> list = new ArrayList<Thread>();
2036 for (Node w = firstWaiter; w != null; w = w.nextWaiter) {
2037 if (w.waitStatus == Node.CONDITION) {
2038 Thread t = w.thread;
2048 * CAS head field. Used only by enq.
2050 private final boolean compareAndSetHead(Node update) {
2059 * CAS tail field. Used only by enq.
2061 private final boolean compareAndSetTail(Node expect, Node update) {
2070 * CAS waitStatus field of a node.
2072 private static final boolean compareAndSetWaitStatus(Node node,
2075 if (node.waitStatus == expect) {
2076 node.waitStatus = update;
2083 * CAS next field of a node.
2085 private static final boolean compareAndSetNext(Node node,
2088 if (node.next == expect) {