fiber library(prototype)

libfiber.hpp

/*
 * libfiber.hpp
 *
 * (C) Copyright yohhoy 2012.
 * Distributed under the Boost Software License, Version 1.0.
 * (See copy at http://www.boost.org/LICENSE_1_0.txt)
 */
#ifndef LIBFIBER_HPP_INCLUDED_
#define LIBFIBER_HPP_INCLUDED_

#include <vector>
#include <functional>
#include <algorithm>
#include <boost/context/all.hpp>


/*
 * fiber namespace
 */
namespace fiber {

// forward decl.
class fiber;

/*
 * scheduling policy enum
 */
enum class policy {
    lazy  = 0,
    eager = 1
};


namespace detail {

// fiber base class
struct fiber_base {
    fiber_base() {}

    template <class F, class... Args>
    explicit fiber_base(F f, Args&&... args)
        : fn_(std::bind(f, std::forward<Args>(args)...))
        , ctx_(&fiber_base::thunk, this,
            boost::contexts::default_stacksize(),
            boost::contexts::stack_unwind,
            boost::contexts::return_to_caller)
    {}

    static void thunk(fiber_base* self)
    {
        assert(self->fn_ != nullptr);
        (self->fn_)();
    }

    std::function<void()> fn_;
    boost::contexts::context ctx_;
};

// fiber scheduler class
class scheduler {
private:
    scheduler()
        : sched_policy_(policy::lazy)
    {
        queue_.push_back(mainfiber());
    }
    scheduler(const scheduler&) = delete;
    scheduler& operator=(const scheduler&) = delete;

public:
    void append(fiber_base* f)
    {
        assert(std::find(queue_.begin(), queue_.end(), f) == queue_.end());
        queue_.push_back(f);
    }
    void remove(fiber_base* f)
    {
        auto i = std::find(queue_.begin(), queue_.end(), f);
        assert(i != queue_.end());
        queue_.erase(i);
    }
    void rotate()
    {
        std::rotate(queue_.begin(), std::next(queue_.begin()), queue_.end());
    }

    fiber_base* curr_fiber()
    {
        return queue_.front();
    }
    fiber_base* next_fiber(fiber_base* hint)
    {
        if (!hint) {
            rotate();
        } else {
            assert(std::find(queue_.begin(), queue_.end(), hint) != queue_.end());
            while (curr_fiber() != hint)
                rotate();
        }
        while (curr_fiber() != mainfiber() && curr_fiber()->ctx_.is_complete())
            rotate();
        return curr_fiber();
    }

    void yield(fiber_base* hint)
    {
        if (curr_fiber() == mainfiber()) {
            fiber_base* next = next_fiber(hint);
            while (next != mainfiber()) {
                if (next->ctx_.is_started())
                    hint = reinterpret_cast<fiber_base*>(next->ctx_.resume());
                else
                    hint = reinterpret_cast<fiber_base*>(next->ctx_.start());
                next = next_fiber(hint);
            }
        } else {
            curr_fiber()->ctx_.suspend(reinterpret_cast<intptr_t>(hint));
        }
    }
    void yield_eager(fiber_base* hint)
    {
        if (sched_policy_ == policy::eager)
            yield(hint);
    }

    policy& scheduling_policy() { return sched_policy_; }

    static fiber_base* mainfiber()
    {
        static fiber_base main_fiber;
        return &main_fiber;
    }

    static scheduler& instance()
    {
        static scheduler sched;
        return sched;
    }

private:
    std::vector<fiber_base*> queue_;
    policy sched_policy_;
};

} // namespace detail


/*
 * scheduling policy functions
 */
policy get_scheduling_policy()
{
    return detail::scheduler::instance().scheduling_policy();
}

policy set_scheduling_policy(policy new_policy)
{
    policy old_policy = detail::scheduler::instance().scheduling_policy();
    detail::scheduler::instance().scheduling_policy() = new_policy;
    return old_policy;
}


/*
 * fiber class
 */
class fiber {
public:
    // fiber::id
    typedef uintptr_t id;

    fiber() BOOST_NOEXCEPT {}

    template <class F, class... Args>
    explicit fiber(F f, Args&&... args)
        : impl_(new detail::fiber_base(f, std::forward<Args>(args)...))
    {
        detail::scheduler::instance().append(impl_.get());
        detail::scheduler::instance().yield_eager(impl_.get());
    }

    ~fiber()
    {
        if (joinable())
            std::terminate();
    }

    fiber(const fiber&) = delete;
    fiber& operator=(const fiber&) = delete;

    fiber(fiber&& rhs) BOOST_NOEXCEPT
    {
        swap(rhs);
    }
    fiber& operator=(fiber&& rhs) BOOST_NOEXCEPT
    {
        if (joinable())
            std::terminate();
        fiber(std::move(rhs)).swap(*this);
        return *this;
    }

    void swap(fiber& other) BOOST_NOEXCEPT
    {
        impl_.swap(other.impl_);
    }

    bool joinable() const BOOST_NOEXCEPT
    {
        return static_cast<bool>(impl_);
    }

    void join()
    {
        assert(joinable());
        while (!impl_->ctx_.is_complete())
            detail::scheduler::instance().yield(nullptr);
        detail::scheduler::instance().remove(impl_.get());
        impl_ = nullptr;
    }

    id get_id() const BOOST_NOEXCEPT
    {
        return impl_ ? reinterpret_cast<id>(impl_.get()) : id();
    }

private:
    std::unique_ptr<detail::fiber_base> impl_;
};


/*
 * this_fiber namespace
 */
namespace this_fiber {

inline fiber::id get_id() BOOST_NOEXCEPT
{
    return reinterpret_cast<fiber::id>(detail::scheduler::instance().curr_fiber());
}

inline void yield() BOOST_NOEXCEPT
{
    detail::scheduler::instance().yield(nullptr);
}

} // namespace this_fiber


/*
 * mutex class
 */
class mutex {
    friend class condition_variable;
public:
    mutex()
        : locked_(false), owner_() {}
    ~mutex()
    {
        assert(!locked_ && owner_ == fiber::id());
    }

    mutex(const mutex&) = delete;
    mutex& operator=(const mutex&) = delete;

    void lock()
    {
        assert(owner_ != this_fiber::get_id());
        while (locked_)
            detail::scheduler::instance().yield(nullptr);
        locked_ = true;
        owner_ = this_fiber::get_id();
    }
    bool try_lock()
    {
        if (locked_)
            return false;
        lock();
        return true;
    }
    void unlock()
    {
        assert(owner_ == this_fiber::get_id() && locked_);
        locked_ = false;
        owner_ = fiber::id();
        detail::scheduler::instance().yield_eager(nullptr);
    }

private:
    bool locked_;
    fiber::id owner_;
};


/*
 * recursive_mutex class
 */
class recursive_mutex {
public:
    recursive_mutex()
        : nlock_(0), owner_() {}
    ~recursive_mutex()
    {
        assert(!nlock_ && owner_ == fiber::id());
    }

    recursive_mutex(const recursive_mutex&) = delete;
    recursive_mutex& operator=(const recursive_mutex&) = delete;

    void lock()
    {
        while (owner_ != this_fiber::get_id() && 0 < nlock_)
            detail::scheduler::instance().yield(nullptr);
        ++nlock_;
        owner_ = this_fiber::get_id();
    }
    bool try_lock()
    {
        if (owner_ != this_fiber::get_id() && 0 < nlock_)
            return false;
        lock();
        return true;
    }
    void unlock()
    {
        assert(owner_ == this_fiber::get_id() && 0 < nlock_);
        if (--nlock_ == 0) {
            owner_ = fiber::id();
            detail::scheduler::instance().yield_eager(nullptr);
        }
    }

private:
    unsigned nlock_;
    fiber::id owner_;
};


/*
 * lock_guard template class
 */
template <class Mutex>
class lock_guard {
public:
    typedef Mutex mutex_type;

    explicit lock_guard(mutex_type& m)
        : m_(m)
    {
        m_.lock();
    }
    ~lock_guard()
    {
        m_.unlock();
    }

    lock_guard(const lock_guard&) = delete;
    lock_guard& operator=(const lock_guard&) = delete;

private:
    mutex_type& m_;
};


// tags for unique_lock
struct defer_lock_t {};
struct try_to_lock_t {};
struct adopt_lock_t {};

constexpr defer_lock_t defer_lock{};
constexpr try_to_lock_t try_to_lock{};
constexpr adopt_lock_t adopt_lock{};

/*
 * unique_lock template class
 */
template <class Mutex>
class unique_lock {
public:
    typedef Mutex mutex_type;

    unique_lock() BOOST_NOEXCEPT
        : pm_(nullptr), owns_(false) {}
    explicit unique_lock(mutex_type& m) BOOST_NOEXCEPT
        : pm_(&m), owns_(false)
    {
        pm_->lock();
        owns_ = true;
    }
    unique_lock(mutex_type& m, defer_lock_t)
        : pm_(&m), owns_(false) {}
    unique_lock(mutex_type& m, try_to_lock_t)
        : pm_(&m), owns_(m.try_lock()) {}
    unique_lock(mutex_type& m, adopt_lock_t)
        : pm_(&m), owns_(true) {}
    ~unique_lock()
    {
        if (owns_)
            pm_->unlock();
    }

    unique_lock(const unique_lock&) = delete;
    unique_lock& operator=(const unique_lock&) = delete;

    unique_lock(unique_lock&& rhs) BOOST_NOEXCEPT
        : pm_(rhs.pm_), owns_(rhs.owns_)
    {
        rhs.pm_ = nullptr;
        rhs.owns_ = false;
    }
    unique_lock& operator=(unique_lock&& rhs) BOOST_NOEXCEPT
    {
        if (owns_)
            pm_->unlock();
        unique_lock(std::move(rhs)).swap(*this);
        return *this;
    }

    void lock()
    {
        assert(pm_ && !owns_);
        pm_->lock();
        owns_ = true;
    }
    bool try_lock()
    {
        assert(pm_ && !owns_);
        owns_ = pm_->try_lock();
        return owns_;
    }
    void unlock()
    {
        assert(pm_ && owns_);
        pm_->unlock();
        owns_ = false;
    }

    void swap(unique_lock& other) BOOST_NOEXCEPT
    {
        std::swap(pm_, other.pm_);
        std::swap(owns_, other.owns_);
    }
    mutex_type* release() BOOST_NOEXCEPT
    {
        mutex_type* ret = pm_;
        pm_ = nullptr;
        owns_ = false;
        return ret;
    }

    bool owns_lock() const BOOST_NOEXCEPT { return owns_; }
    explicit operator bool() BOOST_NOEXCEPT { return owns_; }
    mutex_type* mutex() const BOOST_NOEXCEPT { return pm_; }

private:
    mutex_type* pm_;
    bool owns_;
};


/*
 * condition_variable class
 */
class condition_variable {
    struct unlock_guard {
        unlock_guard(mutex& m) : m_(m) { m_.unlock(); }
        ~unlock_guard() { m_.lock(); }
        mutex& m_;
    };
public:
    condition_variable()
        : nwaiter_(0), nsignal_(0) {}
    ~condition_variable() {}

    condition_variable(const condition_variable&) = delete;
    condition_variable& operator=(const condition_variable&) = delete;

    void notify_one() BOOST_NOEXCEPT
    {
        if (0 < nwaiter_) {
            ++nsignal_;
            detail::scheduler::instance().yield_eager(nullptr);
        }
    }
    void notify_all() BOOST_NOEXCEPT
    {
        if (0 < nwaiter_) {
            nsignal_ += nwaiter_;
            detail::scheduler::instance().yield_eager(nullptr);
        }
    }
    void wait(unique_lock<mutex>& lock)
    {
        assert(lock.owns_lock() && lock.mutex()->owner_ == this_fiber::get_id());
        ++nwaiter_;
        unlock_guard ulk(*lock.mutex());
        do {
            detail::scheduler::instance().yield(nullptr);
        } while (nsignal_ == 0);
        --nsignal_;
        --nwaiter_;
    }
    template <class Pred>
    void wait(unique_lock<mutex>& lock, Pred pred)
    {
        while (!pred())
            wait(lock);
    }

private:
    unsigned nwaiter_;
    unsigned nsignal_;
};

} // namespace fiber


#endif // LIBFIBER_HPP_INCLUDED_

GCC 4.6.3 + Boost 1.50.0 (svn-trunk r77773)