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.j2objc.annotations.Weak;
024
025import java.util.concurrent.TimeUnit;
026import java.util.concurrent.locks.Condition;
027import java.util.concurrent.locks.ReentrantLock;
028
029import javax.annotation.concurrent.GuardedBy;
030
031/**
032 * A synchronization abstraction supporting waiting on arbitrary boolean conditions.
033 *
034 * <p>This class is intended as a replacement for {@link ReentrantLock}. Code using {@code Monitor}
035 * is less error-prone and more readable than code using {@code ReentrantLock}, without significant
036 * performance loss. {@code Monitor} even has the potential for performance gain by optimizing the
037 * evaluation and signaling of conditions.  Signaling is entirely
038 * <a href="http://en.wikipedia.org/wiki/Monitor_(synchronization)#Implicit_signaling">
039 * implicit</a>.
040 * By eliminating explicit signaling, this class can guarantee that only one thread is awakened
041 * when a condition becomes true (no "signaling storms" due to use of {@link
042 * java.util.concurrent.locks.Condition#signalAll Condition.signalAll}) and that no signals are lost
043 * (no "hangs" due to incorrect use of {@link java.util.concurrent.locks.Condition#signal
044 * Condition.signal}).
045 *
046 * <p>A thread is said to <i>occupy</i> a monitor if it has <i>entered</i> the monitor but not yet
047 * <i>left</i>. Only one thread may occupy a given monitor at any moment. A monitor is also
048 * reentrant, so a thread may enter a monitor any number of times, and then must leave the same
049 * number of times. The <i>enter</i> and <i>leave</i> operations have the same synchronization
050 * semantics as the built-in Java language synchronization primitives.
051 *
052 * <p>A call to any of the <i>enter</i> methods with <b>void</b> return type should always be
053 * followed immediately by a <i>try/finally</i> block to ensure that the current thread leaves the
054 * monitor cleanly: <pre>   {@code
055 *
056 *   monitor.enter();
057 *   try {
058 *     // do things while occupying the monitor
059 *   } finally {
060 *     monitor.leave();
061 *   }}</pre>
062 *
063 * <p>A call to any of the <i>enter</i> methods with <b>boolean</b> return type should always
064 * appear as the condition of an <i>if</i> statement containing a <i>try/finally</i> block to
065 * ensure that the current thread leaves the monitor cleanly: <pre>   {@code
066 *
067 *   if (monitor.tryEnter()) {
068 *     try {
069 *       // do things while occupying the monitor
070 *     } finally {
071 *       monitor.leave();
072 *     }
073 *   } else {
074 *     // do other things since the monitor was not available
075 *   }}</pre>
076 *
077 * <h2>Comparison with {@code synchronized} and {@code ReentrantLock}</h2>
078 *
079 * <p>The following examples show a simple threadsafe holder expressed using {@code synchronized},
080 * {@link ReentrantLock}, and {@code Monitor}.
081 *
082 * <h3>{@code synchronized}</h3>
083 *
084 * <p>This version is the fewest lines of code, largely because the synchronization mechanism used
085 * is built into the language and runtime. But the programmer has to remember to avoid a couple of
086 * common bugs: The {@code wait()} must be inside a {@code while} instead of an {@code if}, and
087 * {@code notifyAll()} must be used instead of {@code notify()} because there are two different
088 * logical conditions being awaited. <pre>   {@code
089 *
090 *   public class SafeBox<V> {
091 *     private V value;
092 *
093 *     public synchronized V get() throws InterruptedException {
094 *       while (value == null) {
095 *         wait();
096 *       }
097 *       V result = value;
098 *       value = null;
099 *       notifyAll();
100 *       return result;
101 *     }
102 *
103 *     public synchronized void set(V newValue) throws InterruptedException {
104 *       while (value != null) {
105 *         wait();
106 *       }
107 *       value = newValue;
108 *       notifyAll();
109 *     }
110 *   }}</pre>
111 *
112 * <h3>{@code ReentrantLock}</h3>
113 *
114 * <p>This version is much more verbose than the {@code synchronized} version, and still suffers
115 * from the need for the programmer to remember to use {@code while} instead of {@code if}.
116 * However, one advantage is that we can introduce two separate {@code Condition} objects, which
117 * allows us to use {@code signal()} instead of {@code signalAll()}, which may be a performance
118 * benefit. <pre>   {@code
119 *
120 *   public class SafeBox<V> {
121 *     private final ReentrantLock lock = new ReentrantLock();
122 *     private final Condition valuePresent = lock.newCondition();
123 *     private final Condition valueAbsent = lock.newCondition();
124 *     private V value;
125 *
126 *     public V get() throws InterruptedException {
127 *       lock.lock();
128 *       try {
129 *         while (value == null) {
130 *           valuePresent.await();
131 *         }
132 *         V result = value;
133 *         value = null;
134 *         valueAbsent.signal();
135 *         return result;
136 *       } finally {
137 *         lock.unlock();
138 *       }
139 *     }
140 *
141 *     public void set(V newValue) throws InterruptedException {
142 *       lock.lock();
143 *       try {
144 *         while (value != null) {
145 *           valueAbsent.await();
146 *         }
147 *         value = newValue;
148 *         valuePresent.signal();
149 *       } finally {
150 *         lock.unlock();
151 *       }
152 *     }
153 *   }}</pre>
154 *
155 * <h3>{@code Monitor}</h3>
156 *
157 * <p>This version adds some verbosity around the {@code Guard} objects, but removes that same
158 * verbosity, and more, from the {@code get} and {@code set} methods. {@code Monitor} implements the
159 * same efficient signaling as we had to hand-code in the {@code ReentrantLock} version above.
160 * Finally, the programmer no longer has to hand-code the wait loop, and therefore doesn't have to
161 * remember to use {@code while} instead of {@code if}. <pre>   {@code
162 *
163 *   public class SafeBox<V> {
164 *     private final Monitor monitor = new Monitor();
165 *     private final Monitor.Guard valuePresent = new Monitor.Guard(monitor) {
166 *       public boolean isSatisfied() {
167 *         return value != null;
168 *       }
169 *     };
170 *     private final Monitor.Guard valueAbsent = new Monitor.Guard(monitor) {
171 *       public boolean isSatisfied() {
172 *         return value == null;
173 *       }
174 *     };
175 *     private V value;
176 *
177 *     public V get() throws InterruptedException {
178 *       monitor.enterWhen(valuePresent);
179 *       try {
180 *         V result = value;
181 *         value = null;
182 *         return result;
183 *       } finally {
184 *         monitor.leave();
185 *       }
186 *     }
187 *
188 *     public void set(V newValue) throws InterruptedException {
189 *       monitor.enterWhen(valueAbsent);
190 *       try {
191 *         value = newValue;
192 *       } finally {
193 *         monitor.leave();
194 *       }
195 *     }
196 *   }}</pre>
197 *
198 * @author Justin T. Sampson
199 * @author Martin Buchholz
200 * @since 10.0
201 */
202@Beta
203public final class Monitor {
204  // TODO(user): Use raw LockSupport or AbstractQueuedSynchronizer instead of ReentrantLock.
205  // TODO(user): "Port" jsr166 tests for ReentrantLock.
206  //
207  // TODO(user): Change API to make it impossible to use a Guard with the "wrong" monitor,
208  //    by making the monitor implicit, and to eliminate other sources of IMSE.
209  //    Imagine:
210  //    guard.lock();
211  //    try { /* monitor locked and guard satisfied here */ }
212  //    finally { guard.unlock(); }
213  // Here are Justin's design notes about this:
214  //
215  // This idea has come up from time to time, and I think one of my
216  // earlier versions of Monitor even did something like this. I ended
217  // up strongly favoring the current interface.
218  //
219  // I probably can't remember all the reasons (it's possible you
220  // could find them in the code review archives), but here are a few:
221  //
222  // 1. What about leaving/unlocking? Are you going to do
223  //    guard.enter() paired with monitor.leave()? That might get
224  //    confusing. It's nice for the finally block to look as close as
225  //    possible to the thing right before the try. You could have
226  //    guard.leave(), but that's a little odd as well because the
227  //    guard doesn't have anything to do with leaving. You can't
228  //    really enforce that the guard you're leaving is the same one
229  //    you entered with, and it doesn't actually matter.
230  //
231  // 2. Since you can enter the monitor without a guard at all, some
232  //    places you'll have monitor.enter()/monitor.leave() and other
233  //    places you'll have guard.enter()/guard.leave() even though
234  //    it's the same lock being acquired underneath. Always using
235  //    monitor.enterXXX()/monitor.leave() will make it really clear
236  //    which lock is held at any point in the code.
237  //
238  // 3. I think "enterWhen(notEmpty)" reads better than "notEmpty.enter()".
239  //
240  // TODO(user): Implement ReentrantLock features:
241  //    - toString() method
242  //    - getOwner() method
243  //    - getQueuedThreads() method
244  //    - getWaitingThreads(Guard) method
245  //    - implement Serializable
246  //    - redo the API to be as close to identical to ReentrantLock as possible,
247  //      since, after all, this class is also a reentrant mutual exclusion lock!?
248
249  /*
250   * One of the key challenges of this class is to prevent lost signals, while trying hard to
251   * minimize unnecessary signals.  One simple and correct algorithm is to signal some other
252   * waiter with a satisfied guard (if one exists) whenever any thread occupying the monitor
253   * exits the monitor, either by unlocking all of its held locks, or by starting to wait for a
254   * guard.  This includes exceptional exits, so all control paths involving signalling must be
255   * protected by a finally block.
256   *
257   * Further optimizations of this algorithm become increasingly subtle.  A wait that terminates
258   * without the guard being satisfied (due to timeout, but not interrupt) can then immediately
259   * exit the monitor without signalling.  If it timed out without being signalled, it does not
260   * need to "pass on" the signal to another thread.  If it *was* signalled, then its guard must
261   * have been satisfied at the time of signal, and has since been modified by some other thread
262   * to be non-satisfied before reacquiring the lock, and that other thread takes over the
263   * responsibility of signaling the next waiter.
264   *
265   * Unlike the underlying Condition, if we are not careful, an interrupt *can* cause a signal to
266   * be lost, because the signal may be sent to a condition whose sole waiter has just been
267   * interrupted.
268   *
269   * Imagine a monitor with multiple guards.  A thread enters the monitor, satisfies all the
270   * guards, and leaves, calling signalNextWaiter.  With traditional locks and conditions, all
271   * the conditions need to be signalled because it is not known which if any of them have
272   * waiters (and hasWaiters can't be used reliably because of a check-then-act race).  With our
273   * Monitor guards, we only signal the first active guard that is satisfied.  But the
274   * corresponding thread may have already been interrupted and is waiting to reacquire the lock
275   * while still registered in activeGuards, in which case the signal is a no-op, and the
276   * bigger-picture signal is lost unless interrupted threads take special action by
277   * participating in the signal-passing game.
278   */
279
280  /*
281   * Timeout handling is intricate, especially given our ambitious goals:
282   * - Avoid underflow and overflow of timeout values when specified timeouts are close to
283   *   Long.MIN_VALUE or Long.MAX_VALUE.
284   * - Favor responding to interrupts over timeouts.
285   * - System.nanoTime() is expensive enough that we want to call it the minimum required number of
286   *   times, typically once before invoking a blocking method.  This often requires keeping track
287   *   of the first time in a method that nanoTime() has been invoked, for which the special value
288   *   0L is reserved to mean "uninitialized".  If timeout is non-positive, then nanoTime need
289   *   never be called.
290   * - Keep behavior of fair and non-fair instances consistent.
291   */
292
293  /**
294   * A boolean condition for which a thread may wait. A {@code Guard} is associated with a single
295   * {@code Monitor}. The monitor may check the guard at arbitrary times from any thread occupying
296   * the monitor, so code should not be written to rely on how often a guard might or might not be
297   * checked.
298   *
299   * <p>If a {@code Guard} is passed into any method of a {@code Monitor} other than the one it is
300   * associated with, an {@link IllegalMonitorStateException} is thrown.
301   *
302   * @since 10.0
303   */
304  @Beta
305  public abstract static class Guard {
306
307    @Weak final Monitor monitor;
308    final Condition condition;
309
310    @GuardedBy("monitor.lock")
311    int waiterCount = 0;
312
313    /** The next active guard */
314    @GuardedBy("monitor.lock")
315    Guard next;
316
317    protected Guard(Monitor monitor) {
318      this.monitor = checkNotNull(monitor, "monitor");
319      this.condition = monitor.lock.newCondition();
320    }
321
322    /**
323     * Evaluates this guard's boolean condition. This method is always called with the associated
324     * monitor already occupied. Implementations of this method must depend only on state protected
325     * by the associated monitor, and must not modify that state.
326     */
327    public abstract boolean isSatisfied();
328
329  }
330
331  /**
332   * Whether this monitor is fair.
333   */
334  private final boolean fair;
335
336  /**
337   * The lock underlying this monitor.
338   */
339  private final ReentrantLock lock;
340
341  /**
342   * The guards associated with this monitor that currently have waiters ({@code waiterCount > 0}).
343   * A linked list threaded through the Guard.next field.
344   */
345  @GuardedBy("lock")
346  private Guard activeGuards = null;
347
348  /**
349   * Creates a monitor with a non-fair (but fast) ordering policy. Equivalent to {@code
350   * Monitor(false)}.
351   */
352  public Monitor() {
353    this(false);
354  }
355
356  /**
357   * Creates a monitor with the given ordering policy.
358   *
359   * @param fair whether this monitor should use a fair ordering policy rather than a non-fair (but
360   *        fast) one
361   */
362  public Monitor(boolean fair) {
363    this.fair = fair;
364    this.lock = new ReentrantLock(fair);
365  }
366
367  /**
368   * Enters this monitor. Blocks indefinitely.
369   */
370  public void enter() {
371    lock.lock();
372  }
373
374  /**
375   * Enters this monitor. Blocks indefinitely, but may be interrupted.
376   *
377   * @throws InterruptedException if interrupted while waiting
378   */
379  public void enterInterruptibly() throws InterruptedException {
380    lock.lockInterruptibly();
381  }
382
383  /**
384   * Enters this monitor. Blocks at most the given time.
385   *
386   * @return whether the monitor was entered
387   */
388  public boolean enter(long time, TimeUnit unit) {
389    final long timeoutNanos = toSafeNanos(time, unit);
390    final ReentrantLock lock = this.lock;
391    if (!fair && lock.tryLock()) {
392      return true;
393    }
394    boolean interrupted = Thread.interrupted();
395    try {
396      final long startTime = System.nanoTime();
397      for (long remainingNanos = timeoutNanos;;) {
398        try {
399          return lock.tryLock(remainingNanos, TimeUnit.NANOSECONDS);
400        } catch (InterruptedException interrupt) {
401          interrupted = true;
402          remainingNanos = remainingNanos(startTime, timeoutNanos);
403        }
404      }
405    } finally {
406      if (interrupted) {
407        Thread.currentThread().interrupt();
408      }
409    }
410  }
411
412  /**
413   * Enters this monitor. Blocks at most the given time, and may be interrupted.
414   *
415   * @return whether the monitor was entered
416   * @throws InterruptedException if interrupted while waiting
417   */
418  public boolean enterInterruptibly(long time, TimeUnit unit) throws InterruptedException {
419    return lock.tryLock(time, unit);
420  }
421
422  /**
423   * Enters this monitor if it is possible to do so immediately. Does not block.
424   *
425   * <p><b>Note:</b> This method disregards the fairness setting of this monitor.
426   *
427   * @return whether the monitor was entered
428   */
429  public boolean tryEnter() {
430    return lock.tryLock();
431  }
432
433  /**
434   * Enters this monitor when the guard is satisfied. Blocks indefinitely, but may be interrupted.
435   *
436   * @throws InterruptedException if interrupted while waiting
437   */
438  public void enterWhen(Guard guard) throws InterruptedException {
439    if (guard.monitor != this) {
440      throw new IllegalMonitorStateException();
441    }
442    final ReentrantLock lock = this.lock;
443    boolean signalBeforeWaiting = lock.isHeldByCurrentThread();
444    lock.lockInterruptibly();
445
446    boolean satisfied = false;
447    try {
448      if (!guard.isSatisfied()) {
449        await(guard, signalBeforeWaiting);
450      }
451      satisfied = true;
452    } finally {
453      if (!satisfied) {
454        leave();
455      }
456    }
457  }
458
459  /**
460   * Enters this monitor when the guard is satisfied. Blocks indefinitely.
461   */
462  public void enterWhenUninterruptibly(Guard guard) {
463    if (guard.monitor != this) {
464      throw new IllegalMonitorStateException();
465    }
466    final ReentrantLock lock = this.lock;
467    boolean signalBeforeWaiting = lock.isHeldByCurrentThread();
468    lock.lock();
469
470    boolean satisfied = false;
471    try {
472      if (!guard.isSatisfied()) {
473        awaitUninterruptibly(guard, signalBeforeWaiting);
474      }
475      satisfied = true;
476    } finally {
477      if (!satisfied) {
478        leave();
479      }
480    }
481  }
482
483  /**
484   * Enters this monitor when the guard is satisfied. Blocks at most the given time, including both
485   * the time to acquire the lock and the time to wait for the guard to be satisfied, and may be
486   * interrupted.
487   *
488   * @return whether the monitor was entered, which guarantees that the guard is now satisfied
489   * @throws InterruptedException if interrupted while waiting
490   */
491  public boolean enterWhen(Guard guard, long time, TimeUnit unit) throws InterruptedException {
492    final long timeoutNanos = toSafeNanos(time, unit);
493    if (guard.monitor != this) {
494      throw new IllegalMonitorStateException();
495    }
496    final ReentrantLock lock = this.lock;
497    boolean reentrant = lock.isHeldByCurrentThread();
498    long startTime = 0L;
499
500 locked: {
501      if (!fair) {
502        // Check interrupt status to get behavior consistent with fair case.
503        if (Thread.interrupted()) {
504          throw new InterruptedException();
505        }
506        if (lock.tryLock()) {
507          break locked;
508        }
509      }
510      startTime = initNanoTime(timeoutNanos);
511      if (!lock.tryLock(time, unit)) {
512        return false;
513      }
514    }
515
516    boolean satisfied = false;
517    boolean threw = true;
518    try {
519      satisfied = guard.isSatisfied()
520          || awaitNanos(guard,
521                        (startTime == 0L)
522                            ? timeoutNanos
523                            : remainingNanos(startTime, timeoutNanos),
524                        reentrant);
525      threw = false;
526      return satisfied;
527    } finally {
528      if (!satisfied) {
529        try {
530          // Don't need to signal if timed out, but do if interrupted
531          if (threw && !reentrant) {
532            signalNextWaiter();
533          }
534        } finally {
535          lock.unlock();
536        }
537      }
538    }
539  }
540
541  /**
542   * Enters this monitor when the guard is satisfied. Blocks at most the given time, including
543   * both the time to acquire the lock and the time to wait for the guard to be satisfied.
544   *
545   * @return whether the monitor was entered, which guarantees that the guard is now satisfied
546   */
547  public boolean enterWhenUninterruptibly(Guard guard, long time, TimeUnit unit) {
548    final long timeoutNanos = toSafeNanos(time, unit);
549    if (guard.monitor != this) {
550      throw new IllegalMonitorStateException();
551    }
552    final ReentrantLock lock = this.lock;
553    long startTime = 0L;
554    boolean signalBeforeWaiting = lock.isHeldByCurrentThread();
555    boolean interrupted = Thread.interrupted();
556    try {
557      if (fair || !lock.tryLock()) {
558        startTime = initNanoTime(timeoutNanos);
559        for (long remainingNanos = timeoutNanos;;) {
560          try {
561            if (lock.tryLock(remainingNanos, TimeUnit.NANOSECONDS)) {
562              break;
563            } else {
564              return false;
565            }
566          } catch (InterruptedException interrupt) {
567            interrupted = true;
568            remainingNanos = remainingNanos(startTime, timeoutNanos);
569          }
570        }
571      }
572
573      boolean satisfied = false;
574      try {
575        while (true) {
576          try {
577            if (guard.isSatisfied()) {
578              satisfied = true;
579            } else {
580              final long remainingNanos;
581              if (startTime == 0L) {
582                startTime = initNanoTime(timeoutNanos);
583                remainingNanos = timeoutNanos;
584              } else {
585                remainingNanos = remainingNanos(startTime, timeoutNanos);
586              }
587              satisfied = awaitNanos(guard, remainingNanos, signalBeforeWaiting);
588            }
589            return satisfied;
590          } catch (InterruptedException interrupt) {
591            interrupted = true;
592            signalBeforeWaiting = false;
593          }
594        }
595      } finally {
596        if (!satisfied) {
597          lock.unlock();  // No need to signal if timed out
598        }
599      }
600    } finally {
601      if (interrupted) {
602        Thread.currentThread().interrupt();
603      }
604    }
605  }
606
607  /**
608   * Enters this monitor if the guard is satisfied. Blocks indefinitely acquiring the lock, but
609   * does not wait for the guard to be satisfied.
610   *
611   * @return whether the monitor was entered, which guarantees that the guard is now satisfied
612   */
613  public boolean enterIf(Guard guard) {
614    if (guard.monitor != this) {
615      throw new IllegalMonitorStateException();
616    }
617    final ReentrantLock lock = this.lock;
618    lock.lock();
619
620    boolean satisfied = false;
621    try {
622      return satisfied = guard.isSatisfied();
623    } finally {
624      if (!satisfied) {
625        lock.unlock();
626      }
627    }
628  }
629
630  /**
631   * Enters this monitor if the guard is satisfied. Blocks indefinitely acquiring the lock, but does
632   * not wait for the guard to be satisfied, and may be interrupted.
633   *
634   * @return whether the monitor was entered, which guarantees that the guard is now satisfied
635   * @throws InterruptedException if interrupted while waiting
636   */
637  public boolean enterIfInterruptibly(Guard guard) throws InterruptedException {
638    if (guard.monitor != this) {
639      throw new IllegalMonitorStateException();
640    }
641    final ReentrantLock lock = this.lock;
642    lock.lockInterruptibly();
643
644    boolean satisfied = false;
645    try {
646      return satisfied = guard.isSatisfied();
647    } finally {
648      if (!satisfied) {
649        lock.unlock();
650      }
651    }
652  }
653
654  /**
655   * Enters this monitor if the guard is satisfied. Blocks at most the given time acquiring the
656   * lock, but does not wait for the guard to be satisfied.
657   *
658   * @return whether the monitor was entered, which guarantees that the guard is now satisfied
659   */
660  public boolean enterIf(Guard guard, long time, TimeUnit unit) {
661    if (guard.monitor != this) {
662      throw new IllegalMonitorStateException();
663    }
664    if (!enter(time, unit)) {
665      return false;
666    }
667
668    boolean satisfied = false;
669    try {
670      return satisfied = guard.isSatisfied();
671    } finally {
672      if (!satisfied) {
673        lock.unlock();
674      }
675    }
676  }
677
678  /**
679   * Enters this monitor if the guard is satisfied. Blocks at most the given time acquiring the
680   * lock, but does not wait for the guard to be satisfied, and may be interrupted.
681   *
682   * @return whether the monitor was entered, which guarantees that the guard is now satisfied
683   */
684  public boolean enterIfInterruptibly(Guard guard, long time, TimeUnit unit)
685      throws InterruptedException {
686    if (guard.monitor != this) {
687      throw new IllegalMonitorStateException();
688    }
689    final ReentrantLock lock = this.lock;
690    if (!lock.tryLock(time, unit)) {
691      return false;
692    }
693
694    boolean satisfied = false;
695    try {
696      return satisfied = guard.isSatisfied();
697    } finally {
698      if (!satisfied) {
699        lock.unlock();
700      }
701    }
702  }
703
704  /**
705   * Enters this monitor if it is possible to do so immediately and the guard is satisfied. Does not
706   * block acquiring the lock and does not wait for the guard to be satisfied.
707   *
708   * <p><b>Note:</b> This method disregards the fairness setting of this monitor.
709   *
710   * @return whether the monitor was entered, which guarantees that the guard is now satisfied
711   */
712  public boolean tryEnterIf(Guard guard) {
713    if (guard.monitor != this) {
714      throw new IllegalMonitorStateException();
715    }
716    final ReentrantLock lock = this.lock;
717    if (!lock.tryLock()) {
718      return false;
719    }
720
721    boolean satisfied = false;
722    try {
723      return satisfied = guard.isSatisfied();
724    } finally {
725      if (!satisfied) {
726        lock.unlock();
727      }
728    }
729  }
730
731  /**
732   * Waits for the guard to be satisfied. Waits indefinitely, but may be interrupted. May be
733   * called only by a thread currently occupying this monitor.
734   *
735   * @throws InterruptedException if interrupted while waiting
736   */
737  public void waitFor(Guard guard) throws InterruptedException {
738    if (!((guard.monitor == this) & lock.isHeldByCurrentThread())) {
739      throw new IllegalMonitorStateException();
740    }
741    if (!guard.isSatisfied()) {
742      await(guard, true);
743    }
744  }
745
746  /**
747   * Waits for the guard to be satisfied. Waits indefinitely. May be called only by a thread
748   * currently occupying this monitor.
749   */
750  public void waitForUninterruptibly(Guard guard) {
751    if (!((guard.monitor == this) & lock.isHeldByCurrentThread())) {
752      throw new IllegalMonitorStateException();
753    }
754    if (!guard.isSatisfied()) {
755      awaitUninterruptibly(guard, true);
756    }
757  }
758
759  /**
760   * Waits for the guard to be satisfied. Waits at most the given time, and may be interrupted.
761   * May be called only by a thread currently occupying this monitor.
762   *
763   * @return whether the guard is now satisfied
764   * @throws InterruptedException if interrupted while waiting
765   */
766  public boolean waitFor(Guard guard, long time, TimeUnit unit) throws InterruptedException {
767    final long timeoutNanos = toSafeNanos(time, unit);
768    if (!((guard.monitor == this) & lock.isHeldByCurrentThread())) {
769      throw new IllegalMonitorStateException();
770    }
771    if (guard.isSatisfied()) {
772      return true;
773    }
774    if (Thread.interrupted()) {
775      throw new InterruptedException();
776    }
777    return awaitNanos(guard, timeoutNanos, true);
778  }
779
780  /**
781   * Waits for the guard to be satisfied. Waits at most the given time. May be called only by a
782   * thread currently occupying this monitor.
783   *
784   * @return whether the guard is now satisfied
785   */
786  public boolean waitForUninterruptibly(Guard guard, long time, TimeUnit unit) {
787    final long timeoutNanos = toSafeNanos(time, unit);
788    if (!((guard.monitor == this) & lock.isHeldByCurrentThread())) {
789      throw new IllegalMonitorStateException();
790    }
791    if (guard.isSatisfied()) {
792      return true;
793    }
794    boolean signalBeforeWaiting = true;
795    final long startTime = initNanoTime(timeoutNanos);
796    boolean interrupted = Thread.interrupted();
797    try {
798      for (long remainingNanos = timeoutNanos;;) {
799        try {
800          return awaitNanos(guard, remainingNanos, signalBeforeWaiting);
801        } catch (InterruptedException interrupt) {
802          interrupted = true;
803          if (guard.isSatisfied()) {
804            return true;
805          }
806          signalBeforeWaiting = false;
807          remainingNanos = remainingNanos(startTime, timeoutNanos);
808        }
809      }
810    } finally {
811      if (interrupted) {
812        Thread.currentThread().interrupt();
813      }
814    }
815  }
816
817  /**
818   * Leaves this monitor. May be called only by a thread currently occupying this monitor.
819   */
820  public void leave() {
821    final ReentrantLock lock = this.lock;
822    try {
823      // No need to signal if we will still be holding the lock when we return
824      if (lock.getHoldCount() == 1) {
825        signalNextWaiter();
826      }
827    } finally {
828      lock.unlock();  // Will throw IllegalMonitorStateException if not held
829    }
830  }
831
832  /**
833   * Returns whether this monitor is using a fair ordering policy.
834   */
835  public boolean isFair() {
836    return fair;
837  }
838
839  /**
840   * Returns whether this monitor is occupied by any thread. This method is designed for use in
841   * monitoring of the system state, not for synchronization control.
842   */
843  public boolean isOccupied() {
844    return lock.isLocked();
845  }
846
847  /**
848   * Returns whether the current thread is occupying this monitor (has entered more times than it
849   * has left).
850   */
851  public boolean isOccupiedByCurrentThread() {
852    return lock.isHeldByCurrentThread();
853  }
854
855  /**
856   * Returns the number of times the current thread has entered this monitor in excess of the number
857   * of times it has left. Returns 0 if the current thread is not occupying this monitor.
858   */
859  public int getOccupiedDepth() {
860    return lock.getHoldCount();
861  }
862
863  /**
864   * Returns an estimate of the number of threads waiting to enter this monitor. The value is only
865   * an estimate because the number of threads may change dynamically while this method traverses
866   * internal data structures. This method is designed for use in monitoring of the system state,
867   * not for synchronization control.
868   */
869  public int getQueueLength() {
870    return lock.getQueueLength();
871  }
872
873  /**
874   * Returns whether any threads are waiting to enter this monitor. Note that because cancellations
875   * may occur at any time, a {@code true} return does not guarantee that any other thread will ever
876   * enter this monitor. This method is designed primarily for use in monitoring of the system
877   * state.
878   */
879  public boolean hasQueuedThreads() {
880    return lock.hasQueuedThreads();
881  }
882
883  /**
884   * Queries whether the given thread is waiting to enter this monitor. Note that because
885   * cancellations may occur at any time, a {@code true} return does not guarantee that this thread
886   * will ever enter this monitor. This method is designed primarily for use in monitoring of the
887   * system state.
888   */
889  public boolean hasQueuedThread(Thread thread) {
890    return lock.hasQueuedThread(thread);
891  }
892
893  /**
894   * Queries whether any threads are waiting for the given guard to become satisfied. Note that
895   * because timeouts and interrupts may occur at any time, a {@code true} return does not guarantee
896   * that the guard becoming satisfied in the future will awaken any threads. This method is
897   * designed primarily for use in monitoring of the system state.
898   */
899  public boolean hasWaiters(Guard guard) {
900    return getWaitQueueLength(guard) > 0;
901  }
902
903  /**
904   * Returns an estimate of the number of threads waiting for the given guard to become satisfied.
905   * Note that because timeouts and interrupts may occur at any time, the estimate serves only as an
906   * upper bound on the actual number of waiters. This method is designed for use in monitoring of
907   * the system state, not for synchronization control.
908   */
909  public int getWaitQueueLength(Guard guard) {
910    if (guard.monitor != this) {
911      throw new IllegalMonitorStateException();
912    }
913    lock.lock();
914    try {
915      return guard.waiterCount;
916    } finally {
917      lock.unlock();
918    }
919  }
920
921  /**
922   * Returns unit.toNanos(time), additionally ensuring the returned value is not at risk of
923   * overflowing or underflowing, by bounding the value between 0 and (Long.MAX_VALUE / 4) * 3.
924   * Actually waiting for more than 219 years is not supported!
925   */
926  private static long toSafeNanos(long time, TimeUnit unit) {
927    long timeoutNanos = unit.toNanos(time);
928    return (timeoutNanos <= 0L) ? 0L
929        : (timeoutNanos > (Long.MAX_VALUE / 4) * 3) ? (Long.MAX_VALUE / 4) * 3
930        : timeoutNanos;
931  }
932
933  /**
934   * Returns System.nanoTime() unless the timeout has already elapsed.
935   * Returns 0L if and only if the timeout has already elapsed.
936   */
937  private static long initNanoTime(long timeoutNanos) {
938    if (timeoutNanos <= 0L) {
939      return 0L;
940    } else {
941      long startTime = System.nanoTime();
942      return (startTime == 0L) ? 1L : startTime;
943    }
944  }
945
946  /**
947   * Returns the remaining nanos until the given timeout, or 0L if the timeout has already elapsed.
948   * Caller must have previously sanitized timeoutNanos using toSafeNanos.
949   */
950  private static long remainingNanos(long startTime, long timeoutNanos) {
951    // assert timeoutNanos == 0L || startTime != 0L;
952
953    // TODO : NOT CORRECT, BUT TESTS PASS ANYWAYS!
954    // if (true) return timeoutNanos;
955    // ONLY 2 TESTS FAIL IF WE DO:
956    // if (true) return 0;
957
958    return (timeoutNanos <= 0L) ? 0L : timeoutNanos - (System.nanoTime() - startTime);
959  }
960
961  /**
962   * Signals some other thread waiting on a satisfied guard, if one exists.
963   *
964   * We manage calls to this method carefully, to signal only when necessary, but never losing a
965   * signal, which is the classic problem of this kind of concurrency construct.  We must signal if
966   * the current thread is about to relinquish the lock and may have changed the state protected by
967   * the monitor, thereby causing some guard to be satisfied.
968   *
969   * In addition, any thread that has been signalled when its guard was satisfied acquires the
970   * responsibility of signalling the next thread when it again relinquishes the lock.  Unlike a
971   * normal Condition, there is no guarantee that an interrupted thread has not been signalled,
972   * since the concurrency control must manage multiple Conditions.  So this method must generally
973   * be called when waits are interrupted.
974   *
975   * On the other hand, if a signalled thread wakes up to discover that its guard is still not
976   * satisfied, it does *not* need to call this method before returning to wait.  This can only
977   * happen due to spurious wakeup (ignorable) or another thread acquiring the lock before the
978   * current thread can and returning the guard to the unsatisfied state.  In the latter case the
979   * other thread (last thread modifying the state protected by the monitor) takes over the
980   * responsibility of signalling the next waiter.
981   *
982   * This method must not be called from within a beginWaitingFor/endWaitingFor block, or else the
983   * current thread's guard might be mistakenly signalled, leading to a lost signal.
984   */
985  @GuardedBy("lock")
986  private void signalNextWaiter() {
987    for (Guard guard = activeGuards; guard != null; guard = guard.next) {
988      if (isSatisfied(guard)) {
989        guard.condition.signal();
990        break;
991      }
992    }
993  }
994
995  /**
996   * Exactly like signalNextWaiter, but caller guarantees that guardToSkip need not be considered,
997   * because caller has previously checked that guardToSkip.isSatisfied() returned false.
998   * An optimization for the case that guardToSkip.isSatisfied() may be expensive.
999   *
1000   * We decided against using this method, since in practice, isSatisfied() is likely to be very
1001   * cheap (typically one field read).  Resurrect this method if you find that not to be true.
1002   */
1003//   @GuardedBy("lock")
1004//   private void signalNextWaiterSkipping(Guard guardToSkip) {
1005//     for (Guard guard = activeGuards; guard != null; guard = guard.next) {
1006//       if (guard != guardToSkip && isSatisfied(guard)) {
1007//         guard.condition.signal();
1008//         break;
1009//       }
1010//     }
1011//   }
1012
1013  /**
1014   * Exactly like guard.isSatisfied(), but in addition signals all waiting threads in the
1015   * (hopefully unlikely) event that isSatisfied() throws.
1016   */
1017  @GuardedBy("lock")
1018  private boolean isSatisfied(Guard guard) {
1019    try {
1020      return guard.isSatisfied();
1021    } catch (Throwable throwable) {
1022      signalAllWaiters();
1023      throw Throwables.propagate(throwable);
1024    }
1025  }
1026
1027  /**
1028   * Signals all threads waiting on guards.
1029   */
1030  @GuardedBy("lock")
1031  private void signalAllWaiters() {
1032    for (Guard guard = activeGuards; guard != null; guard = guard.next) {
1033      guard.condition.signalAll();
1034    }
1035  }
1036
1037  /**
1038   * Records that the current thread is about to wait on the specified guard.
1039   */
1040  @GuardedBy("lock")
1041  private void beginWaitingFor(Guard guard) {
1042    int waiters = guard.waiterCount++;
1043    if (waiters == 0) {
1044      // push guard onto activeGuards
1045      guard.next = activeGuards;
1046      activeGuards = guard;
1047    }
1048  }
1049
1050  /**
1051   * Records that the current thread is no longer waiting on the specified guard.
1052   */
1053  @GuardedBy("lock")
1054  private void endWaitingFor(Guard guard) {
1055    int waiters = --guard.waiterCount;
1056    if (waiters == 0) {
1057      // unlink guard from activeGuards
1058      for (Guard p = activeGuards, pred = null;; pred = p, p = p.next) {
1059        if (p == guard) {
1060          if (pred == null) {
1061            activeGuards = p.next;
1062          } else {
1063            pred.next = p.next;
1064          }
1065          p.next = null;  // help GC
1066          break;
1067        }
1068      }
1069    }
1070  }
1071
1072  /*
1073   * Methods that loop waiting on a guard's condition until the guard is satisfied, while
1074   * recording this fact so that other threads know to check our guard and signal us.
1075   * It's caller's responsibility to ensure that the guard is *not* currently satisfied.
1076   */
1077
1078  @GuardedBy("lock")
1079  private void await(Guard guard, boolean signalBeforeWaiting)
1080      throws InterruptedException {
1081    if (signalBeforeWaiting) {
1082      signalNextWaiter();
1083    }
1084    beginWaitingFor(guard);
1085    try {
1086      do {
1087        guard.condition.await();
1088      } while (!guard.isSatisfied());
1089    } finally {
1090      endWaitingFor(guard);
1091    }
1092  }
1093
1094  @GuardedBy("lock")
1095  private void awaitUninterruptibly(Guard guard, boolean signalBeforeWaiting) {
1096    if (signalBeforeWaiting) {
1097      signalNextWaiter();
1098    }
1099    beginWaitingFor(guard);
1100    try {
1101      do {
1102        guard.condition.awaitUninterruptibly();
1103      } while (!guard.isSatisfied());
1104    } finally {
1105      endWaitingFor(guard);
1106    }
1107  }
1108
1109  /**
1110   * Caller should check before calling that guard is not satisfied.
1111   */
1112  @GuardedBy("lock")
1113  private boolean awaitNanos(Guard guard, long nanos, boolean signalBeforeWaiting)
1114      throws InterruptedException {
1115    boolean firstTime = true;
1116    try {
1117      do {
1118        if (nanos <= 0L) {
1119          return false;
1120        }
1121        if (firstTime) {
1122          if (signalBeforeWaiting) {
1123            signalNextWaiter();
1124          }
1125          beginWaitingFor(guard);
1126          firstTime = false;
1127        }
1128        nanos = guard.condition.awaitNanos(nanos);
1129      } while (!guard.isSatisfied());
1130      return true;
1131    } finally {
1132      if (!firstTime) {
1133        endWaitingFor(guard);
1134      }
1135    }
1136  }
1137
1138}