https://github.com/google/guava/guava: Guava is a suite of core and expanded libraries that include utility classes, google's collections, io classes, and much much more. 
/*
 * Copyright (C) 2010 The Guava Authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
 * in compliance with the License. You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software distributed under the License
 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
 * or implied. See the License for the specific language governing permissions and limitations under
 * the License.
 */

package com.google.common.util.concurrent;

import static com.google.common.base.Preconditions.checkNotNull;

import com.google.common.annotations.Beta;
import com.google.common.annotations.GwtIncompatible;
import com.google.common.base.Throwables;
import com.google.errorprone.annotations.concurrent.GuardedBy;
import com.google.j2objc.annotations.Weak;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;
import java.util.function.BooleanSupplier;
import org.checkerframework.checker.nullness.qual.Nullable;


A synchronization abstraction supporting waiting on arbitrary boolean conditions.

This class is intended as a replacement for ReentrantLock. Code using Monitor is less error-prone and more readable than code using ReentrantLock, without significant performance loss. Monitor even has the potential for performance gain by optimizing the evaluation and signaling of conditions. Signaling is entirely implicit. By eliminating explicit signaling, this class can guarantee that only one thread is awakened when a condition becomes true (no "signaling storms" due to use of Condition.signalAll) and that no signals are lost (no "hangs" due to incorrect use of 
Condition.signal). 
A thread is said to occupy a monitor if it has entered the monitor but not yet
left. Only one thread may occupy a given monitor at any moment. A monitor is also
reentrant, so a thread may enter a monitor any number of times, and then must leave the same
number of times. The enter and leave operations have the same synchronization
semantics as the built-in Java language synchronization primitives.

A call to any of the enter methods with void return type should always be
followed immediately by a try/finally block to ensure that the current thread leaves the
monitor cleanly:


monitor.enter();
try {
  // do things while occupying the monitor
 } finally {
  monitor.leave();
 }



A call to any of the enter methods with boolean return type should always appear
as the condition of an if statement containing a try/finally block to ensure that
the current thread leaves the monitor cleanly:


if (monitor.tryEnter()) {
  try {
    // do things while occupying the monitor
  } finally {
    monitor.leave();
  }
 } else {
  // do other things since the monitor was not available
 }



Comparison with synchronized and ReentrantLock


The following examples show a simple threadsafe holder expressed using synchronized, ReentrantLock, and Monitor. 
synchronized


This version is the fewest lines of code, largely because the synchronization mechanism used is built into the language and runtime. But the programmer has to remember to avoid a couple of common bugs: The wait() must be inside a while instead of an if, and notifyAll() must be used instead of notify() because there are two different logical conditions being awaited. 

public class SafeBox<V> {
  private V value;
  public synchronized V get() throws InterruptedException {
    while (value == null) {
      wait();
    }
    V result = value;
    value = null;
    notifyAll();
    return result;
  }
  public synchronized void set(V newValue) throws InterruptedException {
    while (value != null) {
      wait();
    }
    value = newValue;
    notifyAll();
  }
 }



ReentrantLock


This version is much more verbose than the synchronized version, and still suffers from the need for the programmer to remember to use while instead of if. However, one advantage is that we can introduce two separate Condition objects, which allows us to use signal() instead of signalAll(), which may be a performance benefit. 

public class SafeBox<V> {
  private final ReentrantLock lock = new ReentrantLock();
  private final Condition valuePresent = lock.newCondition();
  private final Condition valueAbsent = lock.newCondition();
  private V value;
  public V get() throws InterruptedException {
    lock.lock();
    try {
      while (value == null) {
        valuePresent.await();
      }
      V result = value;
      value = null;
      valueAbsent.signal();
      return result;
    } finally {
      lock.unlock();
    }
  }
  public void set(V newValue) throws InterruptedException {
    lock.lock();
    try {
      while (value != null) {
        valueAbsent.await();
      }
      value = newValue;
      valuePresent.signal();
    } finally {
      lock.unlock();
    }
  }
 }



Monitor


This version adds some verbosity around the Guard objects, but removes that same verbosity, and more, from the get and set methods. Monitor implements the same efficient signaling as we had to hand-code in the ReentrantLock version above. Finally, the programmer no longer has to hand-code the wait loop, and therefore doesn't have to remember to use while instead of if. 

public class SafeBox<V> {
  private final Monitor monitor = new Monitor();
  private final Monitor.Guard valuePresent = new Monitor.Guard(monitor) {
    public boolean isSatisfied() {
      return value != null;
    }
  };
  private final Monitor.Guard valueAbsent = new Monitor.Guard(monitor) {
    public boolean isSatisfied() {
      return value == null;
    }
  };
  private V value;
  public V get() throws InterruptedException {
    monitor.enterWhen(valuePresent);
    try {
      V result = value;
      value = null;
      return result;
    } finally {
      monitor.leave();
    }
  }
  public void set(V newValue) throws InterruptedException {
    monitor.enterWhen(valueAbsent);
    try {
      value = newValue;
    } finally {
      monitor.leave();
    }
  }
 }



Author:Justin T. Sampson, Martin Buchholz
Since:10.0
/**
 * A synchronization abstraction supporting waiting on arbitrary boolean conditions.
 *
 * <p>This class is intended as a replacement for {@link ReentrantLock}. Code using {@code Monitor}
 * is less error-prone and more readable than code using {@code ReentrantLock}, without significant
 * performance loss. {@code Monitor} even has the potential for performance gain by optimizing the
 * evaluation and signaling of conditions. Signaling is entirely <a
 * href="http://en.wikipedia.org/wiki/Monitor_(synchronization)#Implicit_signaling">implicit</a>. By
 * eliminating explicit signaling, this class can guarantee that only one thread is awakened when a
 * condition becomes true (no "signaling storms" due to use of {@link
 * java.util.concurrent.locks.Condition#signalAll Condition.signalAll}) and that no signals are lost
 * (no "hangs" due to incorrect use of {@link java.util.concurrent.locks.Condition#signal
 * Condition.signal}).
 *
 * <p>A thread is said to <i>occupy</i> a monitor if it has <i>entered</i> the monitor but not yet
 * <i>left</i>. Only one thread may occupy a given monitor at any moment. A monitor is also
 * reentrant, so a thread may enter a monitor any number of times, and then must leave the same
 * number of times. The <i>enter</i> and <i>leave</i> operations have the same synchronization
 * semantics as the built-in Java language synchronization primitives.
 *
 * <p>A call to any of the <i>enter</i> methods with <b>void</b> return type should always be
 * followed immediately by a <i>try/finally</i> block to ensure that the current thread leaves the
 * monitor cleanly:
 *
 * <pre>{@code
 * monitor.enter();
 * try {
 *   // do things while occupying the monitor
 * } finally {
 *   monitor.leave();
 * }
 * }</pre>
 *
 * <p>A call to any of the <i>enter</i> methods with <b>boolean</b> return type should always appear
 * as the condition of an <i>if</i> statement containing a <i>try/finally</i> block to ensure that
 * the current thread leaves the monitor cleanly:
 *
 * <pre>{@code
 * if (monitor.tryEnter()) {
 *   try {
 *     // do things while occupying the monitor
 *   } finally {
 *     monitor.leave();
 *   }
 * } else {
 *   // do other things since the monitor was not available
 * }
 * }</pre>
 *
 * <h2>Comparison with {@code synchronized} and {@code ReentrantLock}</h2>
 *
 * <p>The following examples show a simple threadsafe holder expressed using {@code synchronized},
 * {@link ReentrantLock}, and {@code Monitor}.
 *
 * <h3>{@code synchronized}</h3>
 *
 * <p>This version is the fewest lines of code, largely because the synchronization mechanism used
 * is built into the language and runtime. But the programmer has to remember to avoid a couple of
 * common bugs: The {@code wait()} must be inside a {@code while} instead of an {@code if}, and
 * {@code notifyAll()} must be used instead of {@code notify()} because there are two different
 * logical conditions being awaited.
 *
 * <pre>{@code
 * public class SafeBox<V> {
 *   private V value;
 *
 *   public synchronized V get() throws InterruptedException {
 *     while (value == null) {
 *       wait();
 *     }
 *     V result = value;
 *     value = null;
 *     notifyAll();
 *     return result;
 *   }
 *
 *   public synchronized void set(V newValue) throws InterruptedException {
 *     while (value != null) {
 *       wait();
 *     }
 *     value = newValue;
 *     notifyAll();
 *   }
 * }
 * }</pre>
 *
 * <h3>{@code ReentrantLock}</h3>
 *
 * <p>This version is much more verbose than the {@code synchronized} version, and still suffers
 * from the need for the programmer to remember to use {@code while} instead of {@code if}. However,
 * one advantage is that we can introduce two separate {@code Condition} objects, which allows us to
 * use {@code signal()} instead of {@code signalAll()}, which may be a performance benefit.
 *
 * <pre>{@code
 * public class SafeBox<V> {
 *   private final ReentrantLock lock = new ReentrantLock();
 *   private final Condition valuePresent = lock.newCondition();
 *   private final Condition valueAbsent = lock.newCondition();
 *   private V value;
 *
 *   public V get() throws InterruptedException {
 *     lock.lock();
 *     try {
 *       while (value == null) {
 *         valuePresent.await();
 *       }
 *       V result = value;
 *       value = null;
 *       valueAbsent.signal();
 *       return result;
 *     } finally {
 *       lock.unlock();
 *     }
 *   }
 *
 *   public void set(V newValue) throws InterruptedException {
 *     lock.lock();
 *     try {
 *       while (value != null) {
 *         valueAbsent.await();
 *       }
 *       value = newValue;
 *       valuePresent.signal();
 *     } finally {
 *       lock.unlock();
 *     }
 *   }
 * }
 * }</pre>
 *
 * <h3>{@code Monitor}</h3>
 *
 * <p>This version adds some verbosity around the {@code Guard} objects, but removes that same
 * verbosity, and more, from the {@code get} and {@code set} methods. {@code Monitor} implements the
 * same efficient signaling as we had to hand-code in the {@code ReentrantLock} version above.
 * Finally, the programmer no longer has to hand-code the wait loop, and therefore doesn't have to
 * remember to use {@code while} instead of {@code if}.
 *
 * <pre>{@code
 * public class SafeBox<V> {
 *   private final Monitor monitor = new Monitor();
 *   private final Monitor.Guard valuePresent = new Monitor.Guard(monitor) {
 *     public boolean isSatisfied() {
 *       return value != null;
 *     }
 *   };
 *   private final Monitor.Guard valueAbsent = new Monitor.Guard(monitor) {
 *     public boolean isSatisfied() {
 *       return value == null;
 *     }
 *   };
 *   private V value;
 *
 *   public V get() throws InterruptedException {
 *     monitor.enterWhen(valuePresent);
 *     try {
 *       V result = value;
 *       value = null;
 *       return result;
 *     } finally {
 *       monitor.leave();
 *     }
 *   }
 *
 *   public void set(V newValue) throws InterruptedException {
 *     monitor.enterWhen(valueAbsent);
 *     try {
 *       value = newValue;
 *     } finally {
 *       monitor.leave();
 *     }
 *   }
 * }
 * }</pre>
 *
 * @author Justin T. Sampson
 * @author Martin Buchholz
 * @since 10.0
 */
@Beta
@GwtIncompatible
@SuppressWarnings("GuardedBy") // TODO(b/35466881): Fix or suppress.
public final class Monitor {
  // TODO(user): Use raw LockSupport or AbstractQueuedSynchronizer instead of ReentrantLock.
  // TODO(user): "Port" jsr166 tests for ReentrantLock.
  //
  // TODO(user): Change API to make it impossible to use a Guard with the "wrong" monitor,
  //    by making the monitor implicit, and to eliminate other sources of IMSE.
  //    Imagine:
  //    guard.lock();
  //    try { /* monitor locked and guard satisfied here */ }
  //    finally { guard.unlock(); }
  // Here are Justin's design notes about this:
  //
  // This idea has come up from time to time, and I think one of my
  // earlier versions of Monitor even did something like this. I ended
  // up strongly favoring the current interface.
  //
  // I probably can't remember all the reasons (it's possible you
  // could find them in the code review archives), but here are a few:
  //
  // 1. What about leaving/unlocking? Are you going to do
  //    guard.enter() paired with monitor.leave()? That might get
  //    confusing. It's nice for the finally block to look as close as
  //    possible to the thing right before the try. You could have
  //    guard.leave(), but that's a little odd as well because the
  //    guard doesn't have anything to do with leaving. You can't
  //    really enforce that the guard you're leaving is the same one
  //    you entered with, and it doesn't actually matter.
  //
  // 2. Since you can enter the monitor without a guard at all, some
  //    places you'll have monitor.enter()/monitor.leave() and other
  //    places you'll have guard.enter()/guard.leave() even though
  //    it's the same lock being acquired underneath. Always using
  //    monitor.enterXXX()/monitor.leave() will make it really clear
  //    which lock is held at any point in the code.
  //
  // 3. I think "enterWhen(notEmpty)" reads better than "notEmpty.enter()".
  //
  // TODO(user): Implement ReentrantLock features:
  //    - toString() method
  //    - getOwner() method
  //    - getQueuedThreads() method
  //    - getWaitingThreads(Guard) method
  //    - implement Serializable
  //    - redo the API to be as close to identical to ReentrantLock as possible,
  //      since, after all, this class is also a reentrant mutual exclusion lock!?

  /*
   * One of the key challenges of this class is to prevent lost signals, while trying hard to
   * minimize unnecessary signals. One simple and correct algorithm is to signal some other waiter
   * with a satisfied guard (if one exists) whenever any thread occupying the monitor exits the
   * monitor, either by unlocking all of its held locks, or by starting to wait for a guard. This
   * includes exceptional exits, so all control paths involving signalling must be protected by a
   * finally block.
   *
   * Further optimizations of this algorithm become increasingly subtle. A wait that terminates
   * without the guard being satisfied (due to timeout, but not interrupt) can then immediately exit
   * the monitor without signalling. If it timed out without being signalled, it does not need to
   * "pass on" the signal to another thread. If it *was* signalled, then its guard must have been
   * satisfied at the time of signal, and has since been modified by some other thread to be
   * non-satisfied before reacquiring the lock, and that other thread takes over the responsibility
   * of signaling the next waiter.
   *
   * Unlike the underlying Condition, if we are not careful, an interrupt *can* cause a signal to be
   * lost, because the signal may be sent to a condition whose sole waiter has just been
   * interrupted.
   *
   * Imagine a monitor with multiple guards. A thread enters the monitor, satisfies all the guards,
   * and leaves, calling signalNextWaiter. With traditional locks and conditions, all the conditions
   * need to be signalled because it is not known which if any of them have waiters (and hasWaiters
   * can't be used reliably because of a check-then-act race). With our Monitor guards, we only
   * signal the first active guard that is satisfied. But the corresponding thread may have already
   * been interrupted and is waiting to reacquire the lock while still registered in activeGuards,
   * in which case the signal is a no-op, and the bigger-picture signal is lost unless interrupted
   * threads take special action by participating in the signal-passing game.
   */

  /*
   * Timeout handling is intricate, especially given our ambitious goals:
   * - Avoid underflow and overflow of timeout values when specified timeouts are close to
   *   Long.MIN_VALUE or Long.MAX_VALUE.
   * - Favor responding to interrupts over timeouts.
   * - System.nanoTime() is expensive enough that we want to call it the minimum required number of
   *   times, typically once before invoking a blocking method. This often requires keeping track of
   *   the first time in a method that nanoTime() has been invoked, for which the special value 0L
   *   is reserved to mean "uninitialized". If timeout is non-positive, then nanoTime need never be
   *   called.
   * - Keep behavior of fair and non-fair instances consistent.
   */

  
A boolean condition for which a thread may wait. A Guard is associated with a single Monitor. The monitor may check the guard at arbitrary times from any thread occupying the monitor, so code should not be written to rely on how often a guard might or might not be checked. 
If a Guard is passed into any method of a Monitor other than the one it is associated with, an IllegalMonitorStateException is thrown. 
Since:10.0
/**
   * A boolean condition for which a thread may wait. A {@code Guard} is associated with a single
   * {@code Monitor}. The monitor may check the guard at arbitrary times from any thread occupying
   * the monitor, so code should not be written to rely on how often a guard might or might not be
   * checked.
   *
   * <p>If a {@code Guard} is passed into any method of a {@code Monitor} other than the one it is
   * associated with, an {@link IllegalMonitorStateException} is thrown.
   *
   * @since 10.0
   */
  @Beta
  public abstract static class Guard {

    @Weak final Monitor monitor;
    final Condition condition;

    @GuardedBy("monitor.lock")
    int waiterCount = 0;

    
The next active guard 
/** The next active guard */
    @GuardedBy("monitor.lock")
    @Nullable
    Guard next;

    protected Guard(Monitor monitor) {
      this.monitor = checkNotNull(monitor, "monitor");
      this.condition = monitor.lock.newCondition();
    }

    
Evaluates this guard's boolean condition. This method is always called with the associated
monitor already occupied. Implementations of this method must depend only on state protected
by the associated monitor, and must not modify that state.

/**
     * Evaluates this guard's boolean condition. This method is always called with the associated
     * monitor already occupied. Implementations of this method must depend only on state protected
     * by the associated monitor, and must not modify that state.
     */
    public abstract boolean isSatisfied();
  }

  
Whether this monitor is fair. 
/** Whether this monitor is fair. */
  private final boolean fair;

  
The lock underlying this monitor. 
/** The lock underlying this monitor. */
  private final ReentrantLock lock;

  
The guards associated with this monitor that currently have waiters (waiterCount > 0). A linked list threaded through the Guard.next field. 
/**
   * The guards associated with this monitor that currently have waiters ({@code waiterCount > 0}).
   * A linked list threaded through the Guard.next field.
   */
  @GuardedBy("lock")
  private Guard activeGuards = null;

  
Creates a monitor with a non-fair (but fast) ordering policy. Equivalent to 
Monitor(false). 
/**
   * Creates a monitor with a non-fair (but fast) ordering policy. Equivalent to {@code
   * Monitor(false)}.
   */
  public Monitor() {
    this(false);
  }

  
Creates a monitor with the given ordering policy.

Params:
  • fair – whether this monitor should use a fair ordering policy rather than a non-fair (but
    fast) one
/**
   * Creates a monitor with the given ordering policy.
   *
   * @param fair whether this monitor should use a fair ordering policy rather than a non-fair (but
   *     fast) one
   */
  public Monitor(boolean fair) {
    this.fair = fair;
    this.lock = new ReentrantLock(fair);
  }

  
Creates a new Guard for this monitor. @Param isSatisfied The guards boolean condition. See Guard.isSatisfied. 
/**
   * Creates a new {@link Guard} for {@code this} monitor. @Param isSatisfied The guards boolean
   * condition. See {@link Guard#isSatisfied}.
   */
  public Guard newGuard(final BooleanSupplier isSatisfied) {
    checkNotNull(isSatisfied, "isSatisfied");
    return new Guard(this) {
      @Override
      public boolean isSatisfied() {
        return isSatisfied.getAsBoolean();
      }
    };
  }

  
Enters this monitor. Blocks indefinitely. 
/** Enters this monitor. Blocks indefinitely. */
  public void enter() {
    lock.lock();
  }

  
Enters this monitor. Blocks at most the given time.

Returns:whether the monitor was entered
/**
   * Enters this monitor. Blocks at most the given time.
   *
   * @return whether the monitor was entered
   */
  public boolean enter(long time, TimeUnit unit) {
    final long timeoutNanos = toSafeNanos(time, unit);
    final ReentrantLock lock = this.lock;
    if (!fair && lock.tryLock()) {
      return true;
    }
    boolean interrupted = Thread.interrupted();
    try {
      final long startTime = System.nanoTime();
      for (long remainingNanos = timeoutNanos; ; ) {
        try {
          return lock.tryLock(remainingNanos, TimeUnit.NANOSECONDS);
        } catch (InterruptedException interrupt) {
          interrupted = true;
          remainingNanos = remainingNanos(startTime, timeoutNanos);
        }
      }
    } finally {
      if (interrupted) {
        Thread.currentThread().interrupt();
      }
    }
  }

  
Enters this monitor. Blocks indefinitely, but may be interrupted.

Throws:
  • InterruptedException – if interrupted while waiting
/**
   * Enters this monitor. Blocks indefinitely, but may be interrupted.
   *
   * @throws InterruptedException if interrupted while waiting
   */
  public void enterInterruptibly() throws InterruptedException {
    lock.lockInterruptibly();
  }

  
Enters this monitor. Blocks at most the given time, and may be interrupted.

Throws:
Returns:whether the monitor was entered
/**
   * Enters this monitor. Blocks at most the given time, and may be interrupted.
   *
   * @return whether the monitor was entered
   * @throws InterruptedException if interrupted while waiting
   */
  public boolean enterInterruptibly(long time, TimeUnit unit) throws InterruptedException {
    return lock.tryLock(time, unit);
  }

  
Enters this monitor if it is possible to do so immediately. Does not block.

Note: This method disregards the fairness setting of this monitor.

Returns:whether the monitor was entered
/**
   * Enters this monitor if it is possible to do so immediately. Does not block.
   *
   * <p><b>Note:</b> This method disregards the fairness setting of this monitor.
   *
   * @return whether the monitor was entered
   */
  public boolean tryEnter() {
    return lock.tryLock();
  }

  
Enters this monitor when the guard is satisfied. Blocks indefinitely, but may be interrupted.

Throws:
  • InterruptedException – if interrupted while waiting
/**
   * Enters this monitor when the guard is satisfied. Blocks indefinitely, but may be interrupted.
   *
   * @throws InterruptedException if interrupted while waiting
   */
  public void enterWhen(Guard guard) throws InterruptedException {
    if (guard.monitor != this) {
      throw new IllegalMonitorStateException();
    }
    final ReentrantLock lock = this.lock;
    boolean signalBeforeWaiting = lock.isHeldByCurrentThread();
    lock.lockInterruptibly();

    boolean satisfied = false;
    try {
      if (!guard.isSatisfied()) {
        await(guard, signalBeforeWaiting);
      }
      satisfied = true;
    } finally {
      if (!satisfied) {
        leave();
      }
    }
  }

  
Enters this monitor when the guard is satisfied. Blocks at most the given time, including both
the time to acquire the lock and the time to wait for the guard to be satisfied, and may be
interrupted.

Throws:
Returns:whether the monitor was entered, which guarantees that the guard is now satisfied
/**
   * Enters this monitor when the guard is satisfied. Blocks at most the given time, including both
   * the time to acquire the lock and the time to wait for the guard to be satisfied, and may be
   * interrupted.
   *
   * @return whether the monitor was entered, which guarantees that the guard is now satisfied
   * @throws InterruptedException if interrupted while waiting
   */
  public boolean enterWhen(Guard guard, long time, TimeUnit unit) throws InterruptedException {
    final long timeoutNanos = toSafeNanos(time, unit);
    if (guard.monitor != this) {
      throw new IllegalMonitorStateException();
    }
    final ReentrantLock lock = this.lock;
    boolean reentrant = lock.isHeldByCurrentThread();
    long startTime = 0L;

    locked:
    {
      if (!fair) {
        // Check interrupt status to get behavior consistent with fair case.
        if (Thread.interrupted()) {
          throw new InterruptedException();
        }
        if (lock.tryLock()) {
          break locked;
        }
      }
      startTime = initNanoTime(timeoutNanos);
      if (!lock.tryLock(time, unit)) {
        return false;
      }
    }

    boolean satisfied = false;
    boolean threw = true;
    try {
      satisfied =
          guard.isSatisfied()
              || awaitNanos(
                  guard,
                  (startTime == 0L) ? timeoutNanos : remainingNanos(startTime, timeoutNanos),
                  reentrant);
      threw = false;
      return satisfied;
    } finally {
      if (!satisfied) {
        try {
          // Don't need to signal if timed out, but do if interrupted
          if (threw && !reentrant) {
            signalNextWaiter();
          }
        } finally {
          lock.unlock();
        }
      }
    }
  }

  
Enters this monitor when the guard is satisfied. Blocks indefinitely. 
/** Enters this monitor when the guard is satisfied. Blocks indefinitely. */
  public void enterWhenUninterruptibly(Guard guard) {
    if (guard.monitor != this) {
      throw new IllegalMonitorStateException();
    }
    final ReentrantLock lock = this.lock;
    boolean signalBeforeWaiting = lock.isHeldByCurrentThread();
    lock.lock();

    boolean satisfied = false;
    try {
      if (!guard.isSatisfied()) {
        awaitUninterruptibly(guard, signalBeforeWaiting);
      }
      satisfied = true;
    } finally {
      if (!satisfied) {
        leave();
      }
    }
  }

  
Enters this monitor when the guard is satisfied. Blocks at most the given time, including both
the time to acquire the lock and the time to wait for the guard to be satisfied.

Returns:whether the monitor was entered, which guarantees that the guard is now satisfied
/**
   * Enters this monitor when the guard is satisfied. Blocks at most the given time, including both
   * the time to acquire the lock and the time to wait for the guard to be satisfied.
   *
   * @return whether the monitor was entered, which guarantees that the guard is now satisfied
   */
  public boolean enterWhenUninterruptibly(Guard guard, long time, TimeUnit unit) {
    final long timeoutNanos = toSafeNanos(time, unit);
    if (guard.monitor != this) {
      throw new IllegalMonitorStateException();
    }
    final ReentrantLock lock = this.lock;
    long startTime = 0L;
    boolean signalBeforeWaiting = lock.isHeldByCurrentThread();
    boolean interrupted = Thread.interrupted();
    try {
      if (fair || !lock.tryLock()) {
        startTime = initNanoTime(timeoutNanos);
        for (long remainingNanos = timeoutNanos; ; ) {
          try {
            if (lock.tryLock(remainingNanos, TimeUnit.NANOSECONDS)) {
              break;
            } else {
              return false;
            }
          } catch (InterruptedException interrupt) {
            interrupted = true;
            remainingNanos = remainingNanos(startTime, timeoutNanos);
          }
        }
      }

      boolean satisfied = false;
      try {
        while (true) {
          try {
            if (guard.isSatisfied()) {
              satisfied = true;
            } else {
              final long remainingNanos;
              if (startTime == 0L) {
                startTime = initNanoTime(timeoutNanos);
                remainingNanos = timeoutNanos;
              } else {
                remainingNanos = remainingNanos(startTime, timeoutNanos);
              }
              satisfied = awaitNanos(guard, remainingNanos, signalBeforeWaiting);
            }
            return satisfied;
          } catch (InterruptedException interrupt) {
            interrupted = true;
            signalBeforeWaiting = false;
          }
        }
      } finally {
        if (!satisfied) {
          lock.unlock(); // No need to signal if timed out
        }
      }
    } finally {
      if (interrupted) {
        Thread.currentThread().interrupt();
      }
    }
  }

  
Enters this monitor if the guard is satisfied. Blocks indefinitely acquiring the lock, but does
not wait for the guard to be satisfied.

Returns:whether the monitor was entered, which guarantees that the guard is now satisfied
/**
   * Enters this monitor if the guard is satisfied. Blocks indefinitely acquiring the lock, but does
   * not wait for the guard to be satisfied.
   *
   * @return whether the monitor was entered, which guarantees that the guard is now satisfied
   */
  public boolean enterIf(Guard guard) {
    if (guard.monitor != this) {
      throw new IllegalMonitorStateException();
    }
    final ReentrantLock lock = this.lock;
    lock.lock();

    boolean satisfied = false;
    try {
      return satisfied = guard.isSatisfied();
    } finally {
      if (!satisfied) {
        lock.unlock();
      }
    }
  }

  
Enters this monitor if the guard is satisfied. Blocks at most the given time acquiring the
lock, but does not wait for the guard to be satisfied.

Returns:whether the monitor was entered, which guarantees that the guard is now satisfied
/**
   * Enters this monitor if the guard is satisfied. Blocks at most the given time acquiring the
   * lock, but does not wait for the guard to be satisfied.
   *
   * @return whether the monitor was entered, which guarantees that the guard is now satisfied
   */
  public boolean enterIf(Guard guard, long time, TimeUnit unit) {
    if (guard.monitor != this) {
      throw new IllegalMonitorStateException();
    }
    if (!enter(time, unit)) {
      return false;
    }

    boolean satisfied = false;
    try {
      return satisfied = guard.isSatisfied();
    } finally {
      if (!satisfied) {
        lock.unlock();
      }
    }
  }

  
Enters this monitor if the guard is satisfied. Blocks indefinitely acquiring the lock, but does
not wait for the guard to be satisfied, and may be interrupted.

Throws:
Returns:whether the monitor was entered, which guarantees that the guard is now satisfied
/**
   * Enters this monitor if the guard is satisfied. Blocks indefinitely acquiring the lock, but does
   * not wait for the guard to be satisfied, and may be interrupted.
   *
   * @return whether the monitor was entered, which guarantees that the guard is now satisfied
   * @throws InterruptedException if interrupted while waiting
   */
  public boolean enterIfInterruptibly(Guard guard) throws InterruptedException {
    if (guard.monitor != this) {
      throw new IllegalMonitorStateException();
    }
    final ReentrantLock lock = this.lock;
    lock.lockInterruptibly();

    boolean satisfied = false;
    try {
      return satisfied = guard.isSatisfied();
    } finally {
      if (!satisfied) {
        lock.unlock();
      }
    }
  }

  
Enters this monitor if the guard is satisfied. Blocks at most the given time acquiring the
lock, but does not wait for the guard to be satisfied, and may be interrupted.

Returns:whether the monitor was entered, which guarantees that the guard is now satisfied
/**
   * Enters this monitor if the guard is satisfied. Blocks at most the given time acquiring the
   * lock, but does not wait for the guard to be satisfied, and may be interrupted.
   *
   * @return whether the monitor was entered, which guarantees that the guard is now satisfied
   */
  public boolean enterIfInterruptibly(Guard guard, long time, TimeUnit unit)
      throws InterruptedException {
    if (guard.monitor != this) {
      throw new IllegalMonitorStateException();
    }
    final ReentrantLock lock = this.lock;
    if (!lock.tryLock(time, unit)) {
      return false;
    }

    boolean satisfied = false;
    try {
      return satisfied = guard.isSatisfied();
    } finally {
      if (!satisfied) {
        lock.unlock();
      }
    }
  }

  
Enters this monitor if it is possible to do so immediately and the guard is satisfied. Does not
block acquiring the lock and does not wait for the guard to be satisfied.

Note: This method disregards the fairness setting of this monitor.

Returns:whether the monitor was entered, which guarantees that the guard is now satisfied
/**
   * Enters this monitor if it is possible to do so immediately and the guard is satisfied. Does not
   * block acquiring the lock and does not wait for the guard to be satisfied.
   *
   * <p><b>Note:</b> This method disregards the fairness setting of this monitor.
   *
   * @return whether the monitor was entered, which guarantees that the guard is now satisfied
   */
  public boolean tryEnterIf(Guard guard) {
    if (guard.monitor != this) {
      throw new IllegalMonitorStateException();
    }
    final ReentrantLock lock = this.lock;
    if (!lock.tryLock()) {
      return false;
    }

    boolean satisfied = false;
    try {
      return satisfied = guard.isSatisfied();
    } finally {
      if (!satisfied) {
        lock.unlock();
      }
    }
  }

  
Waits for the guard to be satisfied. Waits indefinitely, but may be interrupted. May be called
only by a thread currently occupying this monitor.

Throws:
  • InterruptedException – if interrupted while waiting
/**
   * Waits for the guard to be satisfied. Waits indefinitely, but may be interrupted. May be called
   * only by a thread currently occupying this monitor.
   *
   * @throws InterruptedException if interrupted while waiting
   */
  public void waitFor(Guard guard) throws InterruptedException {
    if (!((guard.monitor == this) & lock.isHeldByCurrentThread())) {
      throw new IllegalMonitorStateException();
    }
    if (!guard.isSatisfied()) {
      await(guard, true);
    }
  }

  
Waits for the guard to be satisfied. Waits at most the given time, and may be interrupted. May
be called only by a thread currently occupying this monitor.

Throws:
Returns:whether the guard is now satisfied
/**
   * Waits for the guard to be satisfied. Waits at most the given time, and may be interrupted. May
   * be called only by a thread currently occupying this monitor.
   *
   * @return whether the guard is now satisfied
   * @throws InterruptedException if interrupted while waiting
   */
  public boolean waitFor(Guard guard, long time, TimeUnit unit) throws InterruptedException {
    final long timeoutNanos = toSafeNanos(time, unit);
    if (!((guard.monitor == this) & lock.isHeldByCurrentThread())) {
      throw new IllegalMonitorStateException();
    }
    if (guard.isSatisfied()) {
      return true;
    }
    if (Thread.interrupted()) {
      throw new InterruptedException();
    }
    return awaitNanos(guard, timeoutNanos, true);
  }

  
Waits for the guard to be satisfied. Waits indefinitely. May be called only by a thread
currently occupying this monitor.

/**
   * Waits for the guard to be satisfied. Waits indefinitely. May be called only by a thread
   * currently occupying this monitor.
   */
  public void waitForUninterruptibly(Guard guard) {
    if (!((guard.monitor == this) & lock.isHeldByCurrentThread())) {
      throw new IllegalMonitorStateException();
    }
    if (!guard.isSatisfied()) {
      awaitUninterruptibly(guard, true);
    }
  }

  
Waits for the guard to be satisfied. Waits at most the given time. May be called only by a
thread currently occupying this monitor.

Returns:whether the guard is now satisfied
/**
   * Waits for the guard to be satisfied. Waits at most the given time. May be called only by a
   * thread currently occupying this monitor.
   *
   * @return whether the guard is now satisfied
   */
  public boolean waitForUninterruptibly(Guard guard, long time, TimeUnit unit) {
    final long timeoutNanos = toSafeNanos(time, unit);
    if (!((guard.monitor == this) & lock.isHeldByCurrentThread())) {
      throw new IllegalMonitorStateException();
    }
    if (guard.isSatisfied()) {
      return true;
    }
    boolean signalBeforeWaiting = true;
    final long startTime = initNanoTime(timeoutNanos);
    boolean interrupted = Thread.interrupted();
    try {
      for (long remainingNanos = timeoutNanos; ; ) {
        try {
          return awaitNanos(guard, remainingNanos, signalBeforeWaiting);
        } catch (InterruptedException interrupt) {
          interrupted = true;
          if (guard.isSatisfied()) {
            return true;
          }
          signalBeforeWaiting = false;
          remainingNanos = remainingNanos(startTime, timeoutNanos);
        }
      }
    } finally {
      if (interrupted) {
        Thread.currentThread().interrupt();
      }
    }
  }

  
Leaves this monitor. May be called only by a thread currently occupying this monitor. 
/** Leaves this monitor. May be called only by a thread currently occupying this monitor. */
  public void leave() {
    final ReentrantLock lock = this.lock;
    try {
      // No need to signal if we will still be holding the lock when we return
      if (lock.getHoldCount() == 1) {
        signalNextWaiter();
      }
    } finally {
      lock.unlock(); // Will throw IllegalMonitorStateException if not held
    }
  }

  
Returns whether this monitor is using a fair ordering policy. 
/** Returns whether this monitor is using a fair ordering policy. */
  public boolean isFair() {
    return fair;
  }

  
Returns whether this monitor is occupied by any thread. This method is designed for use in
monitoring of the system state, not for synchronization control.

/**
   * Returns whether this monitor is occupied by any thread. This method is designed for use in
   * monitoring of the system state, not for synchronization control.
   */
  public boolean isOccupied() {
    return lock.isLocked();
  }

  
Returns whether the current thread is occupying this monitor (has entered more times than it
has left).

/**
   * Returns whether the current thread is occupying this monitor (has entered more times than it
   * has left).
   */
  public boolean isOccupiedByCurrentThread() {
    return lock.isHeldByCurrentThread();
  }

  
Returns the number of times the current thread has entered this monitor in excess of the number
of times it has left. Returns 0 if the current thread is not occupying this monitor.

/**
   * Returns the number of times the current thread has entered this monitor in excess of the number
   * of times it has left. Returns 0 if the current thread is not occupying this monitor.
   */
  public int getOccupiedDepth() {
    return lock.getHoldCount();
  }

  
Returns an estimate of the number of threads waiting to enter this monitor. The value is only
an estimate because the number of threads may change dynamically while this method traverses
internal data structures. This method is designed for use in monitoring of the system state,
not for synchronization control.

/**
   * Returns an estimate of the number of threads waiting to enter this monitor. The value is only
   * an estimate because the number of threads may change dynamically while this method traverses
   * internal data structures. This method is designed for use in monitoring of the system state,
   * not for synchronization control.
   */
  public int getQueueLength() {
    return lock.getQueueLength();
  }

  
Returns whether any threads are waiting to enter this monitor. Note that because cancellations may occur at any time, a true return does not guarantee that any other thread will ever enter this monitor. This method is designed primarily for use in monitoring of the system state. 
/**
   * Returns whether any threads are waiting to enter this monitor. Note that because cancellations
   * may occur at any time, a {@code true} return does not guarantee that any other thread will ever
   * enter this monitor. This method is designed primarily for use in monitoring of the system
   * state.
   */
  public boolean hasQueuedThreads() {
    return lock.hasQueuedThreads();
  }

  
Queries whether the given thread is waiting to enter this monitor. Note that because cancellations may occur at any time, a true return does not guarantee that this thread will ever enter this monitor. This method is designed primarily for use in monitoring of the system state. 
/**
   * Queries whether the given thread is waiting to enter this monitor. Note that because
   * cancellations may occur at any time, a {@code true} return does not guarantee that this thread
   * will ever enter this monitor. This method is designed primarily for use in monitoring of the
   * system state.
   */
  public boolean hasQueuedThread(Thread thread) {
    return lock.hasQueuedThread(thread);
  }

  
Queries whether any threads are waiting for the given guard to become satisfied. Note that because timeouts and interrupts may occur at any time, a true return does not guarantee that the guard becoming satisfied in the future will awaken any threads. This method is designed primarily for use in monitoring of the system state. 
/**
   * Queries whether any threads are waiting for the given guard to become satisfied. Note that
   * because timeouts and interrupts may occur at any time, a {@code true} return does not guarantee
   * that the guard becoming satisfied in the future will awaken any threads. This method is
   * designed primarily for use in monitoring of the system state.
   */
  public boolean hasWaiters(Guard guard) {
    return getWaitQueueLength(guard) > 0;
  }

  
Returns an estimate of the number of threads waiting for the given guard to become satisfied.
Note that because timeouts and interrupts may occur at any time, the estimate serves only as an
upper bound on the actual number of waiters. This method is designed for use in monitoring of
the system state, not for synchronization control.

/**
   * Returns an estimate of the number of threads waiting for the given guard to become satisfied.
   * Note that because timeouts and interrupts may occur at any time, the estimate serves only as an
   * upper bound on the actual number of waiters. This method is designed for use in monitoring of
   * the system state, not for synchronization control.
   */
  public int getWaitQueueLength(Guard guard) {
    if (guard.monitor != this) {
      throw new IllegalMonitorStateException();
    }
    lock.lock();
    try {
      return guard.waiterCount;
    } finally {
      lock.unlock();
    }
  }

  
Returns unit.toNanos(time), additionally ensuring the returned value is not at risk of
overflowing or underflowing, by bounding the value between 0 and (Long.MAX_VALUE / 4) * 3.
Actually waiting for more than 219 years is not supported!

/**
   * Returns unit.toNanos(time), additionally ensuring the returned value is not at risk of
   * overflowing or underflowing, by bounding the value between 0 and (Long.MAX_VALUE / 4) * 3.
   * Actually waiting for more than 219 years is not supported!
   */
  private static long toSafeNanos(long time, TimeUnit unit) {
    long timeoutNanos = unit.toNanos(time);
    return (timeoutNanos <= 0L)
        ? 0L
        : (timeoutNanos > (Long.MAX_VALUE / 4) * 3) ? (Long.MAX_VALUE / 4) * 3 : timeoutNanos;
  }

  
Returns System.nanoTime() unless the timeout has already elapsed. Returns 0L if and only if the
timeout has already elapsed.

/**
   * Returns System.nanoTime() unless the timeout has already elapsed. Returns 0L if and only if the
   * timeout has already elapsed.
   */
  private static long initNanoTime(long timeoutNanos) {
    if (timeoutNanos <= 0L) {
      return 0L;
    } else {
      long startTime = System.nanoTime();
      return (startTime == 0L) ? 1L : startTime;
    }
  }

  
Returns the remaining nanos until the given timeout, or 0L if the timeout has already elapsed.
Caller must have previously sanitized timeoutNanos using toSafeNanos.

/**
   * Returns the remaining nanos until the given timeout, or 0L if the timeout has already elapsed.
   * Caller must have previously sanitized timeoutNanos using toSafeNanos.
   */
  private static long remainingNanos(long startTime, long timeoutNanos) {
    // assert timeoutNanos == 0L || startTime != 0L;

    // TODO : NOT CORRECT, BUT TESTS PASS ANYWAYS!
    // if (true) return timeoutNanos;
    // ONLY 2 TESTS FAIL IF WE DO:
    // if (true) return 0;

    return (timeoutNanos <= 0L) ? 0L : timeoutNanos - (System.nanoTime() - startTime);
  }

  
Signals some other thread waiting on a satisfied guard, if one exists.

We manage calls to this method carefully, to signal only when necessary, but never losing a
signal, which is the classic problem of this kind of concurrency construct. We must signal if
the current thread is about to relinquish the lock and may have changed the state protected by
the monitor, thereby causing some guard to be satisfied.

In addition, any thread that has been signalled when its guard was satisfied acquires the
responsibility of signalling the next thread when it again relinquishes the lock. Unlike a
normal Condition, there is no guarantee that an interrupted thread has not been signalled,
since the concurrency control must manage multiple Conditions. So this method must generally be
called when waits are interrupted.

On the other hand, if a signalled thread wakes up to discover that its guard is still not
satisfied, it does *not* need to call this method before returning to wait. This can only
happen due to spurious wakeup (ignorable) or another thread acquiring the lock before the
current thread can and returning the guard to the unsatisfied state. In the latter case the
other thread (last thread modifying the state protected by the monitor) takes over the
responsibility of signalling the next waiter.

This method must not be called from within a beginWaitingFor/endWaitingFor block, or else
the current thread's guard might be mistakenly signalled, leading to a lost signal.

/**
   * Signals some other thread waiting on a satisfied guard, if one exists.
   *
   * <p>We manage calls to this method carefully, to signal only when necessary, but never losing a
   * signal, which is the classic problem of this kind of concurrency construct. We must signal if
   * the current thread is about to relinquish the lock and may have changed the state protected by
   * the monitor, thereby causing some guard to be satisfied.
   *
   * <p>In addition, any thread that has been signalled when its guard was satisfied acquires the
   * responsibility of signalling the next thread when it again relinquishes the lock. Unlike a
   * normal Condition, there is no guarantee that an interrupted thread has not been signalled,
   * since the concurrency control must manage multiple Conditions. So this method must generally be
   * called when waits are interrupted.
   *
   * <p>On the other hand, if a signalled thread wakes up to discover that its guard is still not
   * satisfied, it does *not* need to call this method before returning to wait. This can only
   * happen due to spurious wakeup (ignorable) or another thread acquiring the lock before the
   * current thread can and returning the guard to the unsatisfied state. In the latter case the
   * other thread (last thread modifying the state protected by the monitor) takes over the
   * responsibility of signalling the next waiter.
   *
   * <p>This method must not be called from within a beginWaitingFor/endWaitingFor block, or else
   * the current thread's guard might be mistakenly signalled, leading to a lost signal.
   */
  @GuardedBy("lock")
  private void signalNextWaiter() {
    for (Guard guard = activeGuards; guard != null; guard = guard.next) {
      if (isSatisfied(guard)) {
        guard.condition.signal();
        break;
      }
    }
  }

  /**
   * Exactly like signalNextWaiter, but caller guarantees that guardToSkip need not be considered,
   * because caller has previously checked that guardToSkip.isSatisfied() returned false. An
   * optimization for the case that guardToSkip.isSatisfied() may be expensive.
   *
   * <p>We decided against using this method, since in practice, isSatisfied() is likely to be very
   * cheap (typically one field read). Resurrect this method if you find that not to be true.
   */
  //   @GuardedBy("lock")
  //   private void signalNextWaiterSkipping(Guard guardToSkip) {
  //     for (Guard guard = activeGuards; guard != null; guard = guard.next) {
  //       if (guard != guardToSkip && isSatisfied(guard)) {
  //         guard.condition.signal();
  //         break;
  //       }
  //     }
  //   }

  
Exactly like guard.isSatisfied(), but in addition signals all waiting threads in the (hopefully
unlikely) event that isSatisfied() throws.

/**
   * Exactly like guard.isSatisfied(), but in addition signals all waiting threads in the (hopefully
   * unlikely) event that isSatisfied() throws.
   */
  @GuardedBy("lock")
  private boolean isSatisfied(Guard guard) {
    try {
      return guard.isSatisfied();
    } catch (Throwable throwable) {
      signalAllWaiters();
      throw Throwables.propagate(throwable);
    }
  }

  
Signals all threads waiting on guards. 
/** Signals all threads waiting on guards. */
  @GuardedBy("lock")
  private void signalAllWaiters() {
    for (Guard guard = activeGuards; guard != null; guard = guard.next) {
      guard.condition.signalAll();
    }
  }

  
Records that the current thread is about to wait on the specified guard. 
/** Records that the current thread is about to wait on the specified guard. */
  @GuardedBy("lock")
  private void beginWaitingFor(Guard guard) {
    int waiters = guard.waiterCount++;
    if (waiters == 0) {
      // push guard onto activeGuards
      guard.next = activeGuards;
      activeGuards = guard;
    }
  }

  
Records that the current thread is no longer waiting on the specified guard. 
/** Records that the current thread is no longer waiting on the specified guard. */
  @GuardedBy("lock")
  private void endWaitingFor(Guard guard) {
    int waiters = --guard.waiterCount;
    if (waiters == 0) {
      // unlink guard from activeGuards
      for (Guard p = activeGuards, pred = null; ; pred = p, p = p.next) {
        if (p == guard) {
          if (pred == null) {
            activeGuards = p.next;
          } else {
            pred.next = p.next;
          }
          p.next = null; // help GC
          break;
        }
      }
    }
  }

  /*
   * Methods that loop waiting on a guard's condition until the guard is satisfied, while recording
   * this fact so that other threads know to check our guard and signal us. It's caller's
   * responsibility to ensure that the guard is *not* currently satisfied.
   */

  @GuardedBy("lock")
  private void await(Guard guard, boolean signalBeforeWaiting) throws InterruptedException {
    if (signalBeforeWaiting) {
      signalNextWaiter();
    }
    beginWaitingFor(guard);
    try {
      do {
        guard.condition.await();
      } while (!guard.isSatisfied());
    } finally {
      endWaitingFor(guard);
    }
  }

  @GuardedBy("lock")
  private void awaitUninterruptibly(Guard guard, boolean signalBeforeWaiting) {
    if (signalBeforeWaiting) {
      signalNextWaiter();
    }
    beginWaitingFor(guard);
    try {
      do {
        guard.condition.awaitUninterruptibly();
      } while (!guard.isSatisfied());
    } finally {
      endWaitingFor(guard);
    }
  }

  
Caller should check before calling that guard is not satisfied. 
/** Caller should check before calling that guard is not satisfied. */
  @GuardedBy("lock")
  private boolean awaitNanos(Guard guard, long nanos, boolean signalBeforeWaiting)
      throws InterruptedException {
    boolean firstTime = true;
    try {
      do {
        if (nanos <= 0L) {
          return false;
        }
        if (firstTime) {
          if (signalBeforeWaiting) {
            signalNextWaiter();
          }
          beginWaitingFor(guard);
          firstTime = false;
        }
        nanos = guard.condition.awaitNanos(nanos);
      } while (!guard.isSatisfied());
      return true;
    } finally {
      if (!firstTime) {
        endWaitingFor(guard);
      }
    }
  }
}