001/*
002 * Copyright (C) 2010 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017package com.google.common.util.concurrent;
018
019import static com.google.common.base.Preconditions.checkNotNull;
020
021import com.google.common.annotations.Beta;
022import com.google.common.base.Throwables;
023import com.google.common.collect.Lists;
024
025import java.util.ArrayList;
026import java.util.concurrent.TimeUnit;
027import java.util.concurrent.locks.Condition;
028import java.util.concurrent.locks.ReentrantLock;
029
030import javax.annotation.Nullable;
031import javax.annotation.concurrent.GuardedBy;
032
033/**
034 * A synchronization abstraction supporting waiting on arbitrary boolean conditions.
035 *
036 * <p>This class is intended as a replacement for {@link ReentrantLock}. Code using {@code Monitor}
037 * is less error-prone and more readable than code using {@code ReentrantLock}, without significant
038 * performance loss. {@code Monitor} even has the potential for performance gain by optimizing the
039 * evaluation and signaling of conditions.  Signaling is entirely
040 * <a href="http://en.wikipedia.org/wiki/Monitor_(synchronization)#Implicit_signaling">
041 * implicit</a>.
042 * By eliminating explicit signaling, this class can guarantee that only one thread is awakened
043 * when a condition becomes true (no "signaling storms" due to use of {@link
044 * java.util.concurrent.locks.Condition#signalAll Condition.signalAll}) and that no signals are lost
045 * (no "hangs" due to incorrect use of {@link java.util.concurrent.locks.Condition#signal
046 * Condition.signal}).
047 *
048 * <p>A thread is said to <i>occupy</i> a monitor if it has <i>entered</i> the monitor but not yet
049 * <i>left</i>. Only one thread may occupy a given monitor at any moment. A monitor is also
050 * reentrant, so a thread may enter a monitor any number of times, and then must leave the same
051 * number of times. The <i>enter</i> and <i>leave</i> operations have the same synchronization
052 * semantics as the built-in Java language synchronization primitives.
053 *
054 * <p>A call to any of the <i>enter</i> methods with <b>void</b> return type should always be
055 * followed immediately by a <i>try/finally</i> block to ensure that the current thread leaves the
056 * monitor cleanly: <pre>   {@code
057 *
058 *   monitor.enter();
059 *   try {
060 *     // do things while occupying the monitor
061 *   } finally {
062 *     monitor.leave();
063 *   }}</pre>
064 *
065 * A call to any of the <i>enter</i> methods with <b>boolean</b> return type should always appear as
066 * the condition of an <i>if</i> statement containing a <i>try/finally</i> block to ensure that the
067 * current thread leaves the monitor cleanly: <pre>   {@code
068 *
069 *   if (monitor.tryEnter()) {
070 *     try {
071 *       // do things while occupying the monitor
072 *     } finally {
073 *       monitor.leave();
074 *     }
075 *   } else {
076 *     // do other things since the monitor was not available
077 *   }}</pre>
078 *
079 * <h2>Comparison with {@code synchronized} and {@code ReentrantLock}</h2>
080 * 
081 * <p>The following examples show a simple threadsafe holder expressed using {@code synchronized},
082 * {@link ReentrantLock}, and {@code Monitor}.
083 * 
084 * <h3>{@code synchronized}</h3>
085 * 
086 * <p>This version is the fewest lines of code, largely because the synchronization mechanism used
087 * is built into the language and runtime. But the programmer has to remember to avoid a couple of
088 * common bugs: The {@code wait()} must be inside a {@code while} instead of an {@code if}, and
089 * {@code notifyAll()} must be used instead of {@code notify()} because there are two different
090 * logical conditions being awaited. <pre>   {@code
091 *
092 *   public class SafeBox<V> {
093 *     private V value;
094 *
095 *     public synchronized V get() throws InterruptedException {
096 *       while (value == null) {
097 *         wait();
098 *       }
099 *       V result = value;
100 *       value = null;
101 *       notifyAll();
102 *       return result;
103 *     }
104 *
105 *     public synchronized void set(V newValue) throws InterruptedException {
106 *       while (value != null) {
107 *         wait();
108 *       }
109 *       value = newValue;
110 *       notifyAll();
111 *     }
112 *   }}</pre>
113 * 
114 * <h3>{@code ReentrantLock}</h3>
115 * 
116 * <p>This version is much more verbose than the {@code synchronized} version, and still suffers
117 * from the need for the programmer to remember to use {@code while} instead of {@code if}.
118 * However, one advantage is that we can introduce two separate {@code Condition} objects, which
119 * allows us to use {@code signal()} instead of {@code signalAll()}, which may be a performance
120 * benefit. <pre>   {@code
121 *
122 *   public class SafeBox<V> {
123 *     private final ReentrantLock lock = new ReentrantLock();
124 *     private final Condition valuePresent = lock.newCondition();
125 *     private final Condition valueAbsent = lock.newCondition();
126 *     private V value;
127 *
128 *     public V get() throws InterruptedException {
129 *       lock.lock();
130 *       try {
131 *         while (value == null) {
132 *           valuePresent.await();
133 *         }
134 *         V result = value;
135 *         value = null;
136 *         valueAbsent.signal();
137 *         return result;
138 *       } finally {
139 *         lock.unlock();
140 *       }
141 *     }
142 *
143 *     public void set(V newValue) throws InterruptedException {
144 *       lock.lock();
145 *       try {
146 *         while (value != null) {
147 *           valueAbsent.await();
148 *         }
149 *         value = newValue;
150 *         valuePresent.signal();
151 *       } finally {
152 *         lock.unlock();
153 *       }
154 *     }
155 *   }}</pre>
156 * 
157 * <h3>{@code Monitor}</h3>
158 * 
159 * <p>This version adds some verbosity around the {@code Guard} objects, but removes that same
160 * verbosity, and more, from the {@code get} and {@code set} methods. {@code Monitor} implements the
161 * same efficient signaling as we had to hand-code in the {@code ReentrantLock} version above.
162 * Finally, the programmer no longer has to hand-code the wait loop, and therefore doesn't have to
163 * remember to use {@code while} instead of {@code if}. <pre>   {@code
164 *
165 *   public class SafeBox<V> {
166 *     private final Monitor monitor = new Monitor();
167 *     private final Monitor.Guard valuePresent = new Monitor.Guard(monitor) {
168 *       public boolean isSatisfied() {
169 *         return value != null;
170 *       }
171 *     };
172 *     private final Monitor.Guard valueAbsent = new Monitor.Guard(monitor) {
173 *       public boolean isSatisfied() {
174 *         return value == null;
175 *       }
176 *     };
177 *     private V value;
178 *
179 *     public V get() throws InterruptedException {
180 *       monitor.enterWhen(valuePresent);
181 *       try {
182 *         V result = value;
183 *         value = null;
184 *         return result;
185 *       } finally {
186 *         monitor.leave();
187 *       }
188 *     }
189 *
190 *     public void set(V newValue) throws InterruptedException {
191 *       monitor.enterWhen(valueAbsent);
192 *       try {
193 *         value = newValue;
194 *       } finally {
195 *         monitor.leave();
196 *       }
197 *     }
198 *   }}</pre>
199 * 
200 * @author Justin T. Sampson
201 * @since 10.0
202 */
203@Beta
204public final class Monitor {
205  // TODO: Use raw LockSupport or AbstractQueuedSynchronizer instead of ReentrantLock.
206
207  /**
208   * A boolean condition for which a thread may wait. A {@code Guard} is associated with a single
209   * {@code Monitor}. The monitor may check the guard at arbitrary times from any thread occupying
210   * the monitor, so code should not be written to rely on how often a guard might or might not be
211   * checked.
212   * 
213   * <p>If a {@code Guard} is passed into any method of a {@code Monitor} other than the one it is
214   * associated with, an {@link IllegalMonitorStateException} is thrown.
215   *
216   * @since 10.0
217   */
218  @Beta
219  public abstract static class Guard {
220    
221    final Monitor monitor;
222    final Condition condition;
223
224    @GuardedBy("monitor.lock")
225    int waiterCount = 0;
226
227    protected Guard(Monitor monitor) {
228      this.monitor = checkNotNull(monitor, "monitor");
229      this.condition = monitor.lock.newCondition();
230    }
231
232    /**
233     * Evaluates this guard's boolean condition. This method is always called with the associated
234     * monitor already occupied. Implementations of this method must depend only on state protected
235     * by the associated monitor, and must not modify that state.
236     */
237    public abstract boolean isSatisfied();
238
239    @Override
240    public final boolean equals(Object other) {
241      // Overridden as final to ensure identity semantics in Monitor.activeGuards.
242      return this == other;
243    }
244    
245    @Override
246    public final int hashCode() {
247      // Overridden as final to ensure identity semantics in Monitor.activeGuards.
248      return super.hashCode();
249    }
250
251  }
252
253  /**
254   * Whether this monitor is fair.
255   */
256  private final boolean fair;
257  
258  /**
259   * The lock underlying this monitor.
260   */
261  private final ReentrantLock lock;
262
263  /**
264   * The guards associated with this monitor that currently have waiters ({@code waiterCount > 0}).
265   * This is an ArrayList rather than, say, a HashSet so that iteration and almost all adds don't
266   * incur any object allocation overhead.
267   */
268  @GuardedBy("lock")
269  private final ArrayList<Guard> activeGuards = Lists.newArrayListWithCapacity(1);
270
271  /**
272   * Creates a monitor with a non-fair (but fast) ordering policy. Equivalent to {@code
273   * Monitor(false)}.
274   */
275  public Monitor() {
276    this(false);
277  }
278
279  /**
280   * Creates a monitor with the given ordering policy.
281   *
282   * @param fair whether this monitor should use a fair ordering policy rather than a non-fair (but
283   *        fast) one
284   */
285  public Monitor(boolean fair) {
286    this.fair = fair;
287    this.lock = new ReentrantLock(fair);
288  }
289
290  /**
291   * Enters this monitor. Blocks indefinitely.
292   */
293  public void enter() {
294    lock.lock();
295  }
296
297  /**
298   * Enters this monitor. Blocks indefinitely, but may be interrupted.
299   */
300  public void enterInterruptibly() throws InterruptedException {
301    lock.lockInterruptibly();
302  }
303
304  /**
305   * Enters this monitor. Blocks at most the given time.
306   *
307   * @return whether the monitor was entered
308   */
309  public boolean enter(long time, TimeUnit unit) {
310    final ReentrantLock lock = this.lock;
311    if (!fair && lock.tryLock()) {
312      return true;
313    }
314    long startNanos = System.nanoTime();
315    long timeoutNanos = unit.toNanos(time);
316    long remainingNanos = timeoutNanos;
317    boolean interruptIgnored = false;
318    try {
319      while (true) {
320        try {
321          return lock.tryLock(remainingNanos, TimeUnit.NANOSECONDS);
322        } catch (InterruptedException ignored) {
323          interruptIgnored = true;
324          remainingNanos = (timeoutNanos - (System.nanoTime() - startNanos));
325        }
326      }
327    } finally {
328      if (interruptIgnored) {
329        Thread.currentThread().interrupt();
330      }
331    }
332  }
333
334  /**
335   * Enters this monitor. Blocks at most the given time, and may be interrupted.
336   *
337   * @return whether the monitor was entered
338   */
339  public boolean enterInterruptibly(long time, TimeUnit unit) throws InterruptedException {
340    return lock.tryLock(time, unit);
341  }
342
343  /**
344   * Enters this monitor if it is possible to do so immediately. Does not block.
345   *
346   * <p><b>Note:</b> This method disregards the fairness setting of this monitor.
347   *
348   * @return whether the monitor was entered
349   */
350  public boolean tryEnter() {
351    return lock.tryLock();
352  }
353
354  /**
355   * Enters this monitor when the guard is satisfied. Blocks indefinitely, but may be interrupted.
356   */
357  public void enterWhen(Guard guard) throws InterruptedException {
358    if (guard.monitor != this) {
359      throw new IllegalMonitorStateException();
360    }
361    final ReentrantLock lock = this.lock;
362    boolean reentrant = lock.isHeldByCurrentThread();
363    boolean success = false;
364    lock.lockInterruptibly();
365    try {
366      waitInterruptibly(guard, reentrant);
367      success = true;
368    } finally {
369      if (!success) {
370        lock.unlock();
371      }
372    }
373  }
374
375  /**
376   * Enters this monitor when the guard is satisfied. Blocks indefinitely.
377   */
378  public void enterWhenUninterruptibly(Guard guard) {
379    if (guard.monitor != this) {
380      throw new IllegalMonitorStateException();
381    }
382    final ReentrantLock lock = this.lock;
383    boolean reentrant = lock.isHeldByCurrentThread();
384    boolean success = false;
385    lock.lock();
386    try {
387      waitUninterruptibly(guard, reentrant);
388      success = true;
389    } finally {
390      if (!success) {
391        lock.unlock();
392      }
393    }
394  }
395
396  /**
397   * Enters this monitor when the guard is satisfied. Blocks at most the given time, including both
398   * the time to acquire the lock and the time to wait for the guard to be satisfied, and may be
399   * interrupted.
400   *
401   * @return whether the monitor was entered
402   */
403  public boolean enterWhen(Guard guard, long time, TimeUnit unit) throws InterruptedException {
404    if (guard.monitor != this) {
405      throw new IllegalMonitorStateException();
406    }
407    final ReentrantLock lock = this.lock;
408    boolean reentrant = lock.isHeldByCurrentThread();
409    long remainingNanos;
410    if (!fair && lock.tryLock()) {
411      remainingNanos = unit.toNanos(time);
412    } else {
413      long startNanos = System.nanoTime();
414      if (!lock.tryLock(time, unit)) {
415        return false;
416      }
417      remainingNanos = unit.toNanos(time) - (System.nanoTime() - startNanos);
418    }
419    boolean satisfied = false;
420    try {
421      satisfied = waitInterruptibly(guard, remainingNanos, reentrant);
422    } finally {
423      if (!satisfied) {
424        lock.unlock();
425      }
426    }
427    return satisfied;
428  }
429
430  /**
431   * Enters this monitor when the guard is satisfied. Blocks at most the given time, including
432   * both the time to acquire the lock and the time to wait for the guard to be satisfied.
433   *
434   * @return whether the monitor was entered
435   */
436  public boolean enterWhenUninterruptibly(Guard guard, long time, TimeUnit unit) {
437    if (guard.monitor != this) {
438      throw new IllegalMonitorStateException();
439    }
440    final ReentrantLock lock = this.lock;
441    boolean reentrant = lock.isHeldByCurrentThread();
442    boolean interruptIgnored = false;
443    try {
444      long remainingNanos;
445      if (!fair && lock.tryLock()) {
446        remainingNanos = unit.toNanos(time);
447      } else {
448        long startNanos = System.nanoTime();
449        long timeoutNanos = unit.toNanos(time);
450        remainingNanos = timeoutNanos;
451        while (true) {
452          try {
453            if (lock.tryLock(remainingNanos, TimeUnit.NANOSECONDS)) {
454              break;
455            } else {
456              return false;
457            }
458          } catch (InterruptedException ignored) {
459            interruptIgnored = true;
460          } finally {
461            remainingNanos = (timeoutNanos - (System.nanoTime() - startNanos));
462          }
463        }
464      }
465      boolean satisfied = false;
466      try {
467        satisfied = waitUninterruptibly(guard, remainingNanos, reentrant);
468      } finally {
469        if (!satisfied) {
470          lock.unlock();
471        }
472      }
473      return satisfied;
474    } finally {
475      if (interruptIgnored) {
476        Thread.currentThread().interrupt();
477      }
478    }
479  }
480
481  /**
482   * Enters this monitor if the guard is satisfied. Blocks indefinitely acquiring the lock, but
483   * does not wait for the guard to be satisfied.
484   *
485   * @return whether the monitor was entered
486   */
487  public boolean enterIf(Guard guard) {
488    if (guard.monitor != this) {
489      throw new IllegalMonitorStateException();
490    }
491    final ReentrantLock lock = this.lock;
492    lock.lock();
493    boolean satisfied = false;
494    try {
495      satisfied = guard.isSatisfied();
496    } finally {
497      if (!satisfied) {
498        lock.unlock();
499      }
500    }
501    return satisfied;
502  }
503
504  /**
505   * Enters this monitor if the guard is satisfied. Blocks indefinitely acquiring the lock, but does
506   * not wait for the guard to be satisfied, and may be interrupted.
507   *
508   * @return whether the monitor was entered
509   */
510  public boolean enterIfInterruptibly(Guard guard) throws InterruptedException {
511    if (guard.monitor != this) {
512      throw new IllegalMonitorStateException();
513    }
514    final ReentrantLock lock = this.lock;
515    lock.lockInterruptibly();
516    boolean satisfied = false;
517    try {
518      satisfied = guard.isSatisfied();
519    } finally {
520      if (!satisfied) {
521        lock.unlock();
522      }
523    }
524    return satisfied;
525  }
526
527  /**
528   * Enters this monitor if the guard is satisfied. Blocks at most the given time acquiring the
529   * lock, but does not wait for the guard to be satisfied.
530   *
531   * @return whether the monitor was entered
532   */
533  public boolean enterIf(Guard guard, long time, TimeUnit unit) {
534    if (guard.monitor != this) {
535      throw new IllegalMonitorStateException();
536    }
537    final ReentrantLock lock = this.lock;
538    if (!enter(time, unit)) {
539      return false;
540    }
541    boolean satisfied = false;
542    try {
543      satisfied = guard.isSatisfied();
544    } finally {
545      if (!satisfied) {
546        lock.unlock();
547      }
548    }
549    return satisfied;
550  }
551
552  /**
553   * Enters this monitor if the guard is satisfied. Blocks at most the given time acquiring the
554   * lock, but does not wait for the guard to be satisfied, and may be interrupted.
555   *
556   * @return whether the monitor was entered
557   */
558  public boolean enterIfInterruptibly(Guard guard, long time, TimeUnit unit)
559      throws InterruptedException {
560    if (guard.monitor != this) {
561      throw new IllegalMonitorStateException();
562    }
563    final ReentrantLock lock = this.lock;
564    if (!lock.tryLock(time, unit)) {
565      return false;
566    }
567    boolean satisfied = false;
568    try {
569      satisfied = guard.isSatisfied();
570    } finally {
571      if (!satisfied) {
572        lock.unlock();
573      }
574    }
575    return satisfied;
576  }
577
578  /**
579   * Enters this monitor if it is possible to do so immediately and the guard is satisfied. Does not
580   * block acquiring the lock and does not wait for the guard to be satisfied.
581   *
582   * <p><b>Note:</b> This method disregards the fairness setting of this monitor.
583   *
584   * @return whether the monitor was entered
585   */
586  public boolean tryEnterIf(Guard guard) {
587    if (guard.monitor != this) {
588      throw new IllegalMonitorStateException();
589    }
590    final ReentrantLock lock = this.lock;
591    if (!lock.tryLock()) {
592      return false;
593    }
594    boolean satisfied = false;
595    try {
596      satisfied = guard.isSatisfied();
597    } finally {
598      if (!satisfied) {
599        lock.unlock();
600      }
601    }
602    return satisfied;
603  }
604
605  /**
606   * Waits for the guard to be satisfied. Waits indefinitely, but may be interrupted. May be
607   * called only by a thread currently occupying this monitor.
608   */
609  public void waitFor(Guard guard) throws InterruptedException {
610    if (guard.monitor != this) {
611      throw new IllegalMonitorStateException();
612    }
613    if (!lock.isHeldByCurrentThread()) {
614      throw new IllegalMonitorStateException();
615    }
616    waitInterruptibly(guard, true);
617  }
618
619  /**
620   * Waits for the guard to be satisfied. Waits indefinitely. May be called only by a thread
621   * currently occupying this monitor.
622   */
623  public void waitForUninterruptibly(Guard guard) {
624    if (guard.monitor != this) {
625      throw new IllegalMonitorStateException();
626    }
627    if (!lock.isHeldByCurrentThread()) {
628      throw new IllegalMonitorStateException();
629    }
630    waitUninterruptibly(guard, true);
631  }
632
633  /**
634   * Waits for the guard to be satisfied. Waits at most the given time, and may be interrupted.
635   * May be called only by a thread currently occupying this monitor.
636   *
637   * @return whether the guard is now satisfied
638   */
639  public boolean waitFor(Guard guard, long time, TimeUnit unit) throws InterruptedException {
640    if (guard.monitor != this) {
641      throw new IllegalMonitorStateException();
642    }
643    if (!lock.isHeldByCurrentThread()) {
644      throw new IllegalMonitorStateException();
645    }
646    return waitInterruptibly(guard, unit.toNanos(time), true);
647  }
648
649  /**
650   * Waits for the guard to be satisfied. Waits at most the given time. May be called only by a
651   * thread currently occupying this monitor.
652   *
653   * @return whether the guard is now satisfied
654   */
655  public boolean waitForUninterruptibly(Guard guard, long time, TimeUnit unit) {
656    if (guard.monitor != this) {
657      throw new IllegalMonitorStateException();
658    }
659    if (!lock.isHeldByCurrentThread()) {
660      throw new IllegalMonitorStateException();
661    }
662    return waitUninterruptibly(guard, unit.toNanos(time), true);
663  }
664
665  /**
666   * Leaves this monitor. May be called only by a thread currently occupying this monitor.
667   */
668  public void leave() {
669    final ReentrantLock lock = this.lock;
670    if (!lock.isHeldByCurrentThread()) {
671      throw new IllegalMonitorStateException();
672    }
673    try {
674      signalConditionsOfSatisfiedGuards(null);
675    } finally {
676      lock.unlock();
677    }
678  }
679
680  /**
681   * Returns whether this monitor is using a fair ordering policy.
682   */
683  public boolean isFair() {
684    return lock.isFair();
685  }
686
687  /**
688   * Returns whether this monitor is occupied by any thread. This method is designed for use in
689   * monitoring of the system state, not for synchronization control.
690   */
691  public boolean isOccupied() {
692    return lock.isLocked();
693  }
694
695  /**
696   * Returns whether the current thread is occupying this monitor (has entered more times than it
697   * has left).
698   */
699  public boolean isOccupiedByCurrentThread() {
700    return lock.isHeldByCurrentThread();
701  }
702
703  /**
704   * Returns the number of times the current thread has entered this monitor in excess of the number
705   * of times it has left. Returns 0 if the current thread is not occupying this monitor.
706   */
707  public int getOccupiedDepth() {
708    return lock.getHoldCount();
709  }
710
711  /**
712   * Returns an estimate of the number of threads waiting to enter this monitor. The value is only
713   * an estimate because the number of threads may change dynamically while this method traverses
714   * internal data structures. This method is designed for use in monitoring of the system state,
715   * not for synchronization control.
716   */
717  public int getQueueLength() {
718    return lock.getQueueLength();
719  }
720
721  /**
722   * Returns whether any threads are waiting to enter this monitor. Note that because cancellations
723   * may occur at any time, a {@code true} return does not guarantee that any other thread will ever
724   * enter this monitor. This method is designed primarily for use in monitoring of the system
725   * state.
726   */
727  public boolean hasQueuedThreads() {
728    return lock.hasQueuedThreads();
729  }
730
731  /**
732   * Queries whether the given thread is waiting to enter this monitor. Note that because
733   * cancellations may occur at any time, a {@code true} return does not guarantee that this thread
734   * will ever enter this monitor. This method is designed primarily for use in monitoring of the
735   * system state.
736   */
737  public boolean hasQueuedThread(Thread thread) {
738    return lock.hasQueuedThread(thread);
739  }
740
741  /**
742   * Queries whether any threads are waiting for the given guard to become satisfied. Note that
743   * because timeouts and interrupts may occur at any time, a {@code true} return does not guarantee
744   * that the guard becoming satisfied in the future will awaken any threads. This method is
745   * designed primarily for use in monitoring of the system state.
746   */
747  public boolean hasWaiters(Guard guard) {
748    if (guard.monitor != this) {
749      throw new IllegalMonitorStateException();
750    }
751    lock.lock();
752    try {
753      return guard.waiterCount > 0;
754    } finally {
755      lock.unlock();
756    }
757  }
758
759  /**
760   * Returns an estimate of the number of threads waiting for the given guard to become satisfied.
761   * Note that because timeouts and interrupts may occur at any time, the estimate serves only as an
762   * upper bound on the actual number of waiters. This method is designed for use in monitoring of
763   * the system state, not for synchronization control.
764   */
765  public int getWaitQueueLength(Guard guard) {
766    if (guard.monitor != this) {
767      throw new IllegalMonitorStateException();
768    }
769    lock.lock();
770    try {
771      return guard.waiterCount;
772    } finally {
773      lock.unlock();
774    }
775  }
776
777  @GuardedBy("lock")
778  private void signalConditionsOfSatisfiedGuards(@Nullable Guard interruptedGuard) {
779    final ArrayList<Guard> guards = this.activeGuards;
780    final int guardCount = guards.size();
781    try {
782      for (int i = 0; i < guardCount; i++) {
783        Guard guard = guards.get(i);
784        if ((guard == interruptedGuard) && (guard.waiterCount == 1)) {
785          // That one waiter was just interrupted and is throwing InterruptedException rather than
786          // paying attention to the guard being satisfied, so find another waiter on another guard.
787          continue;
788        }
789        if (guard.isSatisfied()) {
790          guard.condition.signal();
791          return;
792        }
793      }
794    } catch (Throwable throwable) {
795      for (int i = 0; i < guardCount; i++) {
796        Guard guard = guards.get(i);
797        guard.condition.signalAll();
798      }
799      throw Throwables.propagate(throwable);
800    }
801  }
802  
803  @GuardedBy("lock")
804  private void incrementWaiters(Guard guard) {
805    int waiters = guard.waiterCount++;
806    if (waiters == 0) {
807      activeGuards.add(guard);
808    }
809  }
810
811  @GuardedBy("lock")
812  private void decrementWaiters(Guard guard) {
813    int waiters = --guard.waiterCount;
814    if (waiters == 0) {
815      activeGuards.remove(guard);
816    }
817  }
818
819  @GuardedBy("lock")
820  private void waitInterruptibly(Guard guard, boolean signalBeforeWaiting)
821      throws InterruptedException {
822    if (!guard.isSatisfied()) {
823      if (signalBeforeWaiting) {
824        signalConditionsOfSatisfiedGuards(null);
825      }
826      incrementWaiters(guard);
827      try {
828        final Condition condition = guard.condition;
829        do {
830          try {
831            condition.await();
832          } catch (InterruptedException interrupt) {
833            try {
834              signalConditionsOfSatisfiedGuards(guard);
835            } catch (Throwable throwable) {
836              Thread.currentThread().interrupt();
837              throw Throwables.propagate(throwable);
838            }
839            throw interrupt;
840          }
841        } while (!guard.isSatisfied());
842      } finally {
843        decrementWaiters(guard);
844      }
845    }
846  }
847
848  @GuardedBy("lock")
849  private void waitUninterruptibly(Guard guard, boolean signalBeforeWaiting) {
850    if (!guard.isSatisfied()) {
851      if (signalBeforeWaiting) {
852        signalConditionsOfSatisfiedGuards(null);
853      }
854      incrementWaiters(guard);
855      try {
856        final Condition condition = guard.condition;
857        do {
858          condition.awaitUninterruptibly();
859        } while (!guard.isSatisfied());
860      } finally {
861        decrementWaiters(guard);
862      }
863    }
864  }
865
866  @GuardedBy("lock")
867  private boolean waitInterruptibly(Guard guard, long remainingNanos, boolean signalBeforeWaiting)
868      throws InterruptedException {
869    if (!guard.isSatisfied()) {
870      if (signalBeforeWaiting) {
871        signalConditionsOfSatisfiedGuards(null);
872      }
873      incrementWaiters(guard);
874      try {
875        final Condition condition = guard.condition;
876        do {
877          if (remainingNanos <= 0) {
878            return false;
879          }
880          try {
881            remainingNanos = condition.awaitNanos(remainingNanos);
882          } catch (InterruptedException interrupt) {
883            try {
884              signalConditionsOfSatisfiedGuards(guard);
885            } catch (Throwable throwable) {
886              Thread.currentThread().interrupt();
887              throw Throwables.propagate(throwable);
888            }
889            throw interrupt;
890          }
891        } while (!guard.isSatisfied());
892      } finally {
893        decrementWaiters(guard);
894      }
895    }
896    return true;
897  }
898
899  @GuardedBy("lock")
900  private boolean waitUninterruptibly(Guard guard, long timeoutNanos,
901      boolean signalBeforeWaiting) {
902    if (!guard.isSatisfied()) {
903      long startNanos = System.nanoTime();
904      if (signalBeforeWaiting) {
905        signalConditionsOfSatisfiedGuards(null);
906      }
907      boolean interruptIgnored = false;
908      try {
909        incrementWaiters(guard);
910        try {
911          final Condition condition = guard.condition;
912          long remainingNanos = timeoutNanos;
913          do {
914            if (remainingNanos <= 0) {
915              return false;
916            }
917            try {
918              remainingNanos = condition.awaitNanos(remainingNanos);
919            } catch (InterruptedException ignored) {
920              try {
921                signalConditionsOfSatisfiedGuards(guard);
922              } catch (Throwable throwable) {
923                Thread.currentThread().interrupt();
924                throw Throwables.propagate(throwable);
925              }
926              interruptIgnored = true;
927              remainingNanos = (timeoutNanos - (System.nanoTime() - startNanos));
928            }
929          } while (!guard.isSatisfied());
930        } finally {
931          decrementWaiters(guard);
932        }
933      } finally {
934        if (interruptIgnored) {
935          Thread.currentThread().interrupt();
936        }
937      }
938    }
939    return true;
940  }
941
942}