/*
 * 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. 
 */

#ifndef WTF_ParkingLot_h
#define WTF_ParkingLot_h

#include <chrono>
#include <functional>
#include <wtf/Atomics.h>
#include <wtf/ScopedLambda.h>
#include <wtf/Threading.h>

namespace WTF {

class ParkingLot {
    ParkingLot() = delete;
    ParkingLot(const ParkingLot&) = delete;

public:
    typedef std::chrono::steady_clock Clock;
    
    // Parks the thread in a queue associated with the given address, which cannot be null. The
    // parking only succeeds if the validation function returns true while the queue lock is held.
    // If validation returns false, it will unlock the internal parking queue and then it will
    // return without doing anything else. If validation returns true, it will enqueue the thread,
    // unlock the parking queue lock, call the beforeSleep function, and then it will sleep so long
    // as the thread continues to be on the queue and the timeout hasn't fired. Finally, this
    // returns true if we actually got unparked or false if the timeout was hit. Note that
    // beforeSleep is called with no locks held, so it's OK to do pretty much anything so long as
    // you don't recursively call parkConditionally(). You can call unparkOne()/unparkAll() though.
    // It's useful to use beforeSleep() to unlock some mutex in the implementation of
    // Condition::wait().
    template<typename ValidationFunctor, typename BeforeSleepFunctor>
    static bool parkConditionally(
        const void* address,
        ValidationFunctor&& validation,
        BeforeSleepFunctor&& beforeSleep,
        Clock::time_point timeout)
    {
        return parkConditionallyImpl(
            address,
            scopedLambda<bool()>(std::forward<ValidationFunctor>(validation)),
            scopedLambda<void()>(std::forward<BeforeSleepFunctor>(beforeSleep)),
            timeout);
    }

    // Simple version of parkConditionally() that covers the most common case: you want to park
    // indefinitely so long as the value at the given address hasn't changed.
    template<typename T, typename U>
    static bool compareAndPark(const Atomic<T>* address, U expected)
    {
        return parkConditionally(
            address,
            [address, expected] () -> bool {
                U value = address->load();
                return value == expected;
            },
            [] () { },
            Clock::time_point::max());
    }

    // Unparks one thread from the queue associated with the given address, which cannot be null.
    // Returns true if there may still be other threads on that queue, or false if there definitely
    // are no more threads on the queue.
    struct UnparkResult {
        bool didUnparkThread { false };
        bool mayHaveMoreThreads { false };
    };
    WTF_EXPORT_PRIVATE static UnparkResult unparkOne(const void* address);

    // Unparks one thread from the queue associated with the given address, and calls the given
    // functor while the address is locked. Reports to the callback whether any thread got unparked
    // and whether there may be any other threads still on the queue. This is an expert-mode version
    // of unparkOne() that allows for really good thundering herd avoidance in adaptive mutexes.
    // Without this, a lock implementation that uses unparkOne() has to have some trick for knowing
    // if there are still threads parked on the queue, so that it can set some bit in its lock word
    // to indicate that the next unlock() also needs to unparkOne(). But there is a race between
    // manipulating that bit and some other thread acquiring the lock. It's possible to work around
    // that race - see Rusty Russel's well-known usersem library - but it's not pretty. This form
    // allows that race to be completely avoided, since there is no way that a thread can be parked
    // while the callback is running.
    template<typename Callback>
    static void unparkOne(const void* address, Callback&& callback)
    {
        unparkOneImpl(address, scopedLambda<void(UnparkResult)>(std::forward<Callback>(callback)));
    }

    // Unparks every thread from the queue associated with the given address, which cannot be null.
    WTF_EXPORT_PRIVATE static void unparkAll(const void* address);

    // Locks the parking lot and walks all of the parked threads and the addresses they are waiting
    // on. Threads that are on the same queue are guaranteed to be walked from first to last, but the
    // queues may be randomly interleaved. For example, if the queue for address A1 has T1 and T2 and
    // the queue for address A2 has T3 and T4, then you might see iteration orders like:
    //
    // A1,T1 A1,T2 A2,T3 A2,T4
    // A2,T3 A2,T4 A1,T1 A1,T2
    // A1,T1 A2,T3 A1,T2 A2,T4
    // A1,T1 A2,T3 A2,T4 A1,T2
    //
    // As well as many other possible interleavings that all have T1 before T2 and T3 before T4 but are
    // otherwise unconstrained. This method is useful primarily for debugging. It's also used by unit
    // tests.
    WTF_EXPORT_PRIVATE static void forEach(std::function<void(ThreadIdentifier, const void*)>);

private:
    WTF_EXPORT_PRIVATE static bool parkConditionallyImpl(
        const void* address,
        const ScopedLambda<bool()>& validation,
        const ScopedLambda<void()>& beforeSleep,
        Clock::time_point timeout);
    
    WTF_EXPORT_PRIVATE static void unparkOneImpl(
        const void* address, const ScopedLambda<void(UnparkResult)>& callback);

    WTF_EXPORT_PRIVATE static void forEachImpl(const std::function<void(ThreadIdentifier, const void*)>&);
};

} // namespace WTF

using WTF::ParkingLot;

#endif // WTF_ParkingLot_h