/*
 * Copyright (C) 2015-2016 Apple Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
 */

#pragma once

#include <wtf/Lock.h>
#include <wtf/Noncopyable.h>
#include <wtf/ParkingLot.h>
#include <wtf/TimeWithDynamicClockType.h>

namespace WTF {

// This is a condition variable that is suitable for use with any lock-like object, including
// our own WTF::Lock. It features standard wait()/notifyOne()/notifyAll() methods in addition to
// a variety of wait-with-timeout methods. This includes methods that use WTF's own notion of
// time, like wall-clock time (i.e. WallTime) and monotonic time (i.e. MonotonicTime). This is
// a very efficient condition variable. It only requires one byte of memory. notifyOne() and
// notifyAll() require just a load and branch for the fast case where no thread is waiting.
// This condition variable, when used with WTF::Lock, can outperform a system condition variable
// and lock by up to 58x.
class Condition final {
    WTF_MAKE_NONCOPYABLE(Condition);
    WTF_MAKE_FAST_ALLOCATED;
public:
    // Condition will accept any kind of time and convert it internally, but this typedef tells
    // you what kind of time Condition would be able to use without conversions. However, if you
    // are unlikely to be affected by the cost of conversions, it is better to use MonotonicTime.
    using Time = ParkingLot::Time;

    constexpr Condition() = default;

    // Wait on a parking queue while releasing the given lock. It will unlock the lock just before
    // parking, and relock it upon wakeup. Returns true if we woke up due to some call to
    // notifyOne() or notifyAll(). Returns false if we woke up due to a timeout. Note that this form
    // of waitUntil() has some quirks:
    //
    // No spurious wake-up: in order for this to return before the timeout, some notifyOne() or
    // notifyAll() call must have happened. No scenario other than timeout or notify can lead to this
    // method returning. This means, for example, that you can't use pthread cancelation or signals to
    // cause early return.
    //
    // Past timeout: it's possible for waitUntil() to be called with a timeout in the past. In that
    // case, waitUntil() will still release the lock and reacquire it. waitUntil() will always return
    // false in that case. This is subtly different from some pthread_cond_timedwait() implementations,
    // which may not release the lock for past timeout. But, this behavior is consistent with OpenGroup
    // documentation for timedwait().
    template<typename LockType>
    bool waitUntil(LockType& lock, const TimeWithDynamicClockType& timeout)
    {
        return waitUntilUnchecked(lock, timeout);
    }

    bool waitUntil(Lock& lock, const TimeWithDynamicClockType& timeout) WTF_REQUIRES_LOCK(lock)
    {
        return waitUntilUnchecked(lock, timeout);
    }

    // Wait until the given predicate is satisfied. Returns true if it is satisfied in the end.
    // May return early due to timeout.
    template<typename LockType, typename Functor>
    bool waitUntil(LockType& lock, const TimeWithDynamicClockType& timeout, const Functor& predicate)
    {
        return waitUntilUnchecked(lock, timeout, predicate);
    }

    template<typename Functor>
    bool waitUntil(Lock& lock, const TimeWithDynamicClockType& timeout, const Functor& predicate) WTF_REQUIRES_LOCK(lock)
    {
        return waitUntilUnchecked(lock, timeout, predicate);
    }

    // Wait until the given predicate is satisfied. Returns true if it is satisfied in the end.
    // May return early due to timeout.
    template<typename LockType, typename Functor>
    bool waitFor(LockType& lock, Seconds relativeTimeout, const Functor& predicate)
    {
        return waitUntil(lock, MonotonicTime::timePointFromNow(relativeTimeout), predicate);
    }

    template<typename Functor>
    bool waitFor(Lock& lock, Seconds relativeTimeout, const Functor& predicate) WTF_REQUIRES_LOCK(lock)
    {
        return waitUntil(lock, MonotonicTime::timePointFromNow(relativeTimeout), predicate);
    }
    
    template<typename LockType>
    bool waitFor(LockType& lock, Seconds relativeTimeout)
    {
        return waitUntil(lock, MonotonicTime::timePointFromNow(relativeTimeout));
    }

    bool waitFor(Lock& lock, Seconds relativeTimeout) WTF_REQUIRES_LOCK(lock)
    {
        return waitUntil(lock, MonotonicTime::timePointFromNow(relativeTimeout));
    }

    template<typename LockType>
    void wait(LockType& lock)
    {
        waitUntil(lock, Time::infinity());
    }

    void wait(Lock& lock) WTF_REQUIRES_LOCK(lock)
    {
        waitUntil(lock, Time::infinity());
    }

    template<typename LockType, typename Functor>
    void wait(LockType& lock, const Functor& predicate)
    {
        while (!predicate())
            wait(lock);
    }

    template<typename Functor>
    void wait(Lock& lock, const Functor& predicate) WTF_REQUIRES_LOCK(lock)
    {
        while (!predicate())
            wait(lock);
    }

    // Note that this method is extremely fast when nobody is waiting. It is not necessary to try to
    // avoid calling this method. This returns true if someone was actually woken up.
    bool notifyOne()
    {
        if (!m_hasWaiters.load()) {
            // At this exact instant, there is nobody waiting on this condition. The way to visualize
            // this is that if unparkOne() ran to completion without obstructions at this moment, it
            // wouldn't wake anyone up. Hence, we have nothing to do!
            return false;
        }
        
        bool didNotifyThread = false;
        ParkingLot::unparkOne(
            &m_hasWaiters,
            [&] (ParkingLot::UnparkResult result) -> intptr_t {
                if (!result.mayHaveMoreThreads)
                    m_hasWaiters.store(false);
                didNotifyThread = result.didUnparkThread;
                return 0;
            });
        return didNotifyThread;
    }
    
    void notifyAll()
    {
        if (!m_hasWaiters.load()) {
            // See above.
            return;
        }

        // It's totally safe for us to set this to false without any locking, because this thread is
        // guaranteed to then unparkAll() anyway. So, if there is a race with some thread calling
        // wait() just before this store happens, that thread is guaranteed to be awoken by the call to
        // unparkAll(), below.
        m_hasWaiters.store(false);
        
        ParkingLot::unparkAll(&m_hasWaiters);
    }
    
private:
    template<typename LockType>
    bool waitUntilUnchecked(LockType& lock, const TimeWithDynamicClockType& timeout) WTF_IGNORES_THREAD_SAFETY_ANALYSIS
    {
        bool result;
        if (timeout < timeout.nowWithSameClock()) {
            lock.unlock();
            result = false;
        } else {
            result = ParkingLot::parkConditionally(
                &m_hasWaiters,
                [this] () -> bool {
                    // Let everyone know that we will be waiting. Do this while we hold the queue lock,
                    // to prevent races with notifyOne().
                    m_hasWaiters.store(true);
                    return true;
                },
                [&lock] () WTF_IGNORES_THREAD_SAFETY_ANALYSIS {
                    lock.unlock();
                },
                timeout).wasUnparked;
        }
        lock.lock();
        return result;
    }

    template<typename LockType, typename Functor>
    bool waitUntilUnchecked(LockType& lock, const TimeWithDynamicClockType& timeout, const Functor& predicate) WTF_IGNORES_THREAD_SAFETY_ANALYSIS
    {
        while (!predicate()) {
            if (!waitUntil(lock, timeout))
                return predicate();
        }
        return true;
    }

    Atomic<bool> m_hasWaiters { false };
};

using StaticCondition = Condition;

} // namespace WTF

using WTF::Condition;
using WTF::StaticCondition;