simple-ish, fast-ish, generic-ish scheduler implementation

scheduler.cpp

#include "scheduler.hpp"
#include <algorithm>

namespace scheduler {
namespace {

// s32 overflows at 0x7FFFFFFF, just over 100 million gap
constexpr s32 TIMEOUT_VALUE = 0x70000000;

void reset_event(void* user, [[maybe_unused]] s32 _)
{
    auto s = static_cast<Scheduler*>(user);

    // no sort because order remains the same.
    std::for_each(s->queue.begin(), s->queue.end(), [](auto& e){ e.time -= TIMEOUT_VALUE; });

    s->cycles -= TIMEOUT_VALUE;
    s->add(RESERVED_ID, TIMEOUT_VALUE, reset_event, user);
}

} // namespace

Scheduler::Scheduler()
{
    reset();
}

void Scheduler::reset(s32 starting_cycles, Callback reset_cb)
{
    queue.clear();
    cycles = std::min(starting_cycles, TIMEOUT_VALUE);
    add(RESERVED_ID, TIMEOUT_VALUE, reset_cb ? reset_cb : reset_event, this);
}

void Scheduler::fire()
{
    while (!empty())
    {
        const auto event = queue.front();
        if (event.time > cycles)
        {
            break;
        }
        std::pop_heap(queue.begin(), queue.end(), std::greater<>());
        queue.pop_back();
        event.callback(event.user, cycles - event.time);
    }
}

void Scheduler::add(s32 id, s32 event_time, Callback cb, void* user)
{
    add_absolute(id, cycles + event_time, cb, user);
}

void Scheduler::add_absolute(s32 id, s32 event_time, Callback cb, void* user)
{
    const auto itr = std::find_if(queue.begin(), queue.end(), [id](auto& e){ return id == e.id; });

    // if event if already in queue then update time, cb and user.
    if (itr != queue.end())
    {
        itr->time = event_time;
        itr->callback = cb;
        itr->user = user;
        std::push_heap(queue.begin(), queue.end(), std::greater<>());
    }
    // otherwise create new event
    else
    {
        queue.emplace_back(Event{event_time, id, cb, user});
        std::push_heap(queue.begin(), queue.end(), std::greater<>());
    }
}

void Scheduler::remove(s32 id)
{
    const auto itr = std::remove_if(queue.begin(), queue.end(), [id](auto& e) { return id == e.id; });

    if (itr != queue.end())
    {
        queue.erase(itr, queue.end());
        std::make_heap(queue.begin(), queue.end(), std::greater<>()); // optimise this
    }
}

void Scheduler::advance_to_next_event()
{
    if (!empty())
    {
        // only advance if the next event time is greater than current time
        if (queue.front().time > cycles)
        {
            cycles = queue.front().time;
        }
    }
}

auto Scheduler::has_event(s32 id) const -> bool
{
    const auto itr = std::find_if(queue.begin(), queue.end(), [id](auto& e){ return id == e.id; });
    return itr != queue.end();
}

auto Scheduler::get_event_cycles(s32 id) const -> s32
{
    const auto itr = std::find_if(queue.begin(), queue.end(), [id](auto& e){ return id == e.id; });
    if (itr == queue.end())
    {
        return 0;
    }
    return itr->time;
}

} // namespace scheduler

scheduler.hpp

/*
simple-ish, fast-ish, generic-ish scheduler implementation.
based on discussion <https://github.com/dolphin-emu/dolphin/pull/4168>

NOTE: scheduler struct is not suitable for savestates
there is is example code below showing how save/load state.

License: Public Domain or ZLIB (if license is required).
*/
#pragma once

#include <cstdint>
#include <vector>

// set this to 0 if the scheduler can be empty, 1 by default
// due to the reset event always being set!
#ifndef SCHEDULER_NEVER_EMPTY
    #define SCHEDULER_NEVER_EMPTY 1
#endif

namespace scheduler {

using s32 = std::int32_t;
using Callback = void(*)(void* user, s32 cycles_late);

enum { RESERVED_ID = 0x7FFFFFFF };

struct Event {
    s32 time; // time until event expires (scheduler.cycles + event.cycle)
    s32 id; // event id
    Callback callback; // function to call on event expire
    void* user; // user data passed to the callback

    // used for std::_heap functions
    auto operator>(const Event& rhs) const -> bool { return time > rhs.time; }
};

struct Scheduler {
    std::vector<Event> queue; // don't manually edit this!
    s32 cycles; // remember to tick this!

    // calls reset()
    Scheduler();
    // resets queue and cycles, adds reset event, optional custom callback
    void reset(s32 starting_cycles = 0, Callback reset_cb = nullptr);
    // fires all expired events
    void fire();
    // adds relative new / existing event. updates time,cb,user if existing
    void add(s32 id, s32 event_time, Callback cb, void* user);
    // adds new / existing event. updates time,cb,user if existing
    void add_absolute(s32 id, s32 event_time, Callback cb, void* user);
    // removes an event, does nothing if event not enabled.
    void remove(s32 id);
    // advances scheduler so that get_ticks() == get_next_event_cycles()
    void advance_to_next_event();
    // returns if an event is found with matching id
    [[nodiscard]] auto has_event(s32 id) const -> bool;
    // returns event cycles or 0 if not found
    [[nodiscard]] auto get_event_cycles(s32 id) const -> s32;

    // advance scheduler by number of ticks
    constexpr void tick(s32 ticks)
    {
        cycles += ticks;
    }

    // returns current time of the scheduler
    [[nodiscard]] constexpr auto get_ticks() const -> s32
    {
        return cycles;
    }

    // returns true if there are no events
    [[nodiscard]] inline auto empty() const -> bool
    {
        #if SCHEDULER_NEVER_EMPTY
        return false;
        #else
        return queue.empty();
        #endif
    }

    // return true if fire() should be called
    [[nodiscard]] inline auto should_fire() const -> bool
    {
        if (empty())
        {
            return false;
        }
        return queue[0].time <= cycles;
    }

    // return cycles of next event or 0 if no events
    [[nodiscard]] inline auto get_next_event_cycles() const -> s32
    {
        if (empty())
        {
            return 0;
        }
        return queue[0].time;
    }
};


/*
here's an example of implementing save/load state

enum ID {
    PPU,
    APU,
    TIMER,
    DMA,
    MAX,
};

static_assert(ID::MAX < scheduler::RESERVED_ID);

struct EventEntry {
    std::int32_t enabled; // don't use bool here because padding!
    std::int32_t time;
};

void savestate()
{
    std::array<EventEntry, ID::MAX> events{};
    s32 scheduler_cycles = scheduler.get_ticks();

    for (std::size_t i = 0; i < events.size(); i++)
    {
        // see if we have this event in queue, if we do, it's enabled
        if (scheduler.has_event(i))
        {
            events[i].enabled = true;
            events[i].cycles = scheduler.get_event_cycles(i);
        }
    }

    // write state data
    write(events.data(), events.size());
    write(&scheduler_cycles, sizeof(scheduler_cycles));
}

void loadstate()
{
    std::array<EventEntry, ID::MAX> events;
    s32 scheduler_cycles;

    // read state data
    read(&scheduler_cycles, sizeof(scheduler_cycles));
    read(events.data(), events.size());

    // need to reset scheduler to remove all events and reset
    // to the saved time.
    scheduler.reset(scheduler_cycles);

    for (std::size_t i = 0; i < events.size(); i++)
    {
        if (events.enabled)
        {
            scheduler.add_absolute(i, events[i].cycles, callback);
        }
    }
}
*/

} // namespace scheduler