← Back to branch summary

~ubuntu-branches/ubuntu/trusty/monodevelop/trusty-proposed

« back to all changes in this revision

Viewing changes to external/ikvm/openjdk/java/util/concurrent/locks/AbstractQueuedSynchronizer.java

  • Committer: Package Import Robot
  • Author(s): Jo Shields
  • Date: 2013-05-12 09:46:03 UTC
  • mto: This revision was merged to the branch mainline in revision 29.
  • Revision ID: package-import@ubuntu.com-20130512094603-mad323bzcxvmcam0
Tags: upstream-4.0.5+dfsg
Import upstream version 4.0.5+dfsg

Show diffs side-by-side

added added

removed removed

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