scheduler_sorted_aos.hpp

// Copyright 2022 TotalJustice.
// SPDX-License-Identifier: GPL-3.0-only
#pragma once

#ifndef SCHEDULER_USE_BOOST
    #define SCHEDULER_USE_BOOST 1
#endif

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

#include <cassert>
#include <cstdint>
#include <algorithm>
#if SCHEDULER_USE_BOOST
    #include <boost/container/static_vector.hpp>
#else
    #include <vector>
#endif

namespace scheduler {

using s32 = std::int32_t;
// id is the id of the event
// cycles_late will always be 0 if on time or negative if late
using Callback = void(*)(void* user, s32 id, s32 cycles_late);

enum : s32 { RESERVED_ID = 0 };
enum : s32 { TIMEOUT_VALUE = 0x70000000 };

template <size_t MaxCapaxity>
struct Scheduler {
public:
    // calls reset()
    Scheduler(s32 starting_cycles = 0, Callback reset_cb = nullptr, void* user = nullptr)
    {
        reset(starting_cycles, reset_cb, user);
    }

    // resets queue and cycles, adds reset event, optional custom callback
    void reset(s32 starting_cycles = 0, Callback reset_cb = nullptr, void* user = nullptr)
    {
        queue.clear(); // remove previous events
        queue.reserve(MaxCapaxity); // reserve max events upfront + timeout
        cycles = std::min<s32>(starting_cycles, TIMEOUT_VALUE);
        add_absolute(RESERVED_ID, TIMEOUT_VALUE, reset_cb ? reset_cb : reset_event, user ? user : this);
    }

    // fires all expired events
    void fire()
    {
        assert(!empty() && queue.front().time <= cycles && "should_fire() needs to be check before fire()");

        do {
            auto event = queue.front();
            std::ranges::pop_heap(queue, std::greater<>());
            queue.pop_back();
            event.callback(event.user, event.id, event.time - cycles);
        } while (!empty() && queue.front().time <= cycles);
    }

    // adds relative new / existing event. updates time,cb,user if existing
    void add(s32 id, s32 event_time, Callback cb, void* user)
    {
        add_absolute(id, cycles + event_time, cb, user);
    }

    // adds new / existing event. updates time,cb,user if existing
    void add_absolute(s32 id, s32 event_time, Callback cb, void* user)
    {
        const auto itr = std::ranges::find_if(queue, [id](auto& e){ return id == e.id; });

        // if event if already in queue then update time, cb and user.
        if (itr != queue.end()) [[unlikely]] // todo: profile unlikely
        {
            // fast path if front of queue
            if (itr == queue.begin())
            {
                std::ranges::pop_heap(queue, std::greater<>());
                queue.back().time = event_time;
                queue.back().callback = cb;
                queue.back().user = user;
                std::ranges::push_heap(queue, std::greater<>());
            }
            // otherwise, sadly we have to sort the queue :/
            else
            {
                itr->time = event_time;
                itr->callback = cb;
                itr->user = user;
                std::ranges::make_heap(queue, std::greater<>());
            }
        }
        // otherwise create new event
        else
        {
            queue.emplace_back(event_time, id, cb, user);
            std::ranges::push_heap(queue, std::greater<>());
        }
    }

    // removes an event, does nothing if event not enabled.
    void remove(s32 id)
    {
        // std::remove_if loops through every entry, do not use!
        const auto itr = std::ranges::find_if(queue, [id](auto& e){ return id == e.id; });

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

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

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

    // returns true if there are no events
    [[nodiscard]] auto empty() const -> bool
    {
        #if SCHEDULER_NEVER_EMPTY
            assert(!queue.empty() && "queue should never be empty!");
            return false;
        #else
            return queue.empty();
        #endif
    }

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

    // advances scheduler so that get_ticks() == get_next_event_cycles() if event has greater cycles
    void advance_to_next_event()
    {
        assert(!empty());
        // only advance if the next event time is greater than current time
        if (queue.front().time > cycles) [[likely]]
        {
            cycles = queue.front().time;
        }
    }

    // default reset event
    static void reset_event(void* user, s32 id, [[maybe_unused]] s32 _ = 0)
    {
        auto s = static_cast<Scheduler*>(user);

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

        s->cycles -= TIMEOUT_VALUE;
        s->add_absolute(id, TIMEOUT_VALUE, reset_event, user);
    }

private:
    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; }
    };

    s32 cycles; // remember to tick this!
#if SCHEDULER_USE_BOOST
    boost::container::static_vector<Event, MaxCapaxity> queue;
#else
    std::vector<Event> queue; // don't manually edit this!
#endif
};

} // namespace scheduler

scheduler_sorted_soa.hpp

// Copyright 2022 TotalJustice.
// SPDX-License-Identifier: GPL-3.0-only
#pragma once

#ifndef SCHEDULER_USE_BOOST
    #define SCHEDULER_USE_BOOST 1
#endif

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

#include <cassert>
#include <cstdint>
#include <algorithm>
#if SCHEDULER_USE_BOOST
    #include <boost/container/static_vector.hpp>
#else
    #include <vector>
#endif

namespace scheduler {

using s32 = std::int32_t;
// id is the id of the event
// cycles_late will always be 0 if on time or negative if late
using Callback = void(*)(void* user, s32 id, s32 cycles_late);

enum : s32 { RESERVED_ID = 0 };
enum : s32 { TIMEOUT_VALUE = 0x70000000 };

template <size_t MaxCapaxity>
struct Scheduler {
public:
    // calls reset()
    Scheduler(s32 starting_cycles = 0, Callback reset_cb = nullptr, void* user = nullptr)
    {
        reset(starting_cycles, reset_cb, user);
    }

    // resets queue and cycles, adds reset event, optional custom callback
    void reset(s32 starting_cycles = 0, Callback reset_cb = nullptr, void* user = nullptr)
    {
        for (auto& e : events)
        {
            e.Disable();
        }
        queue.clear(); // remove previous events
        queue.reserve(MaxCapaxity); // reserve max events upfront + timeout
        cycles = std::min<s32>(starting_cycles, TIMEOUT_VALUE);
        add_absolute(RESERVED_ID, TIMEOUT_VALUE, reset_cb ? reset_cb : reset_event, user ? user : this);
    }

    // fires all expired events
    void fire()
    {
        assert(!empty() && queue.front().time <= cycles && "should_fire() needs to be check before fire()");

        do {
            const auto [time, id] = queue.front();
            std::ranges::pop_heap(queue, std::greater<>());
            queue.pop_back();
            const auto [callback, user] = events[id];
            events[id].Disable();
            callback(user, id, time - cycles);
        } while (!empty() && queue.front().time <= cycles);
    }

    // adds relative new / existing event. updates time,cb,user if existing
    void add(s32 id, s32 event_time, Callback cb, void* user)
    {
        add_absolute(id, cycles + event_time, cb, user);
    }

    // adds new / existing event. updates time,cb,user if existing
    void add_absolute(s32 id, s32 event_time, Callback cb, void* user)
    {
        if (events[id].Enabled()) // event is already active
        {
            const auto itr = std::ranges::find_if(queue, [id](auto& e){ return id == e.id; });
            // fast path if front of queue
            if (itr == queue.begin())
            {
                std::ranges::pop_heap(queue, std::greater<>());
                queue.back().time = event_time;
                std::ranges::push_heap(queue, std::greater<>());
            }
            // otherwise, sadly we have to sort the queue :/
            else
            {
                itr->time = event_time;
                std::ranges::make_heap(queue, std::greater<>());
            }
        }
        else
        {
            queue.emplace_back(event_time, id);
            std::ranges::push_heap(queue, std::greater<>());
        }
        events[id].callback = cb;
        events[id].user = user;
    }

    // removes an event, does nothing if event not enabled.
    void remove(s32 id)
    {
        if (events[id].Enabled())
        {
            events[id].Disable();
            const auto itr = std::ranges::find_if(queue, [id](auto& e){ return id == e.id; });
            assert(itr != queue.cend());
            queue.erase(itr);
            std::ranges::make_heap(queue, std::greater<>()); // optimise this
        }

    }

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

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

    // returns true if there are no events
    [[nodiscard]] auto empty() const -> bool
    {
        #if SCHEDULER_NEVER_EMPTY
            assert(!queue.empty() && "queue should never be empty!");
            return false;
        #else
            return queue.empty();
        #endif
    }

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

    // advances scheduler so that get_ticks() == get_next_event_cycles() if event has greater cycles
    void advance_to_next_event()
    {
        assert(!empty());
        // only advance if the next event time is greater than current time
        if (queue.front().time > cycles) [[likely]]
        {
            cycles = queue.front().time;
        }
    }

    // default reset event
    static void reset_event(void* user, s32 id, [[maybe_unused]] s32 _ = 0)
    {
        auto s = static_cast<Scheduler*>(user);

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

        s->cycles -= TIMEOUT_VALUE;
        s->add_absolute(id, TIMEOUT_VALUE, reset_event, user);
    }

private:
    struct Event {
        s32 time; // time until event expires (scheduler.cycles + event.cycle)
        s32 id; // event id

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

    struct EventCallback {
        Callback callback; // function to call on event expire
        void* user; // user data passed to the callback

        [[nodiscard]] auto Enabled() const -> bool {
            return callback != nullptr;
        }

        void Disable() {
            callback = nullptr;
        }
    };

    s32 cycles; // remember to tick this!
#if SCHEDULER_USE_BOOST
    boost::container::static_vector<Event, MaxCapaxity> queue;
#else
    std::vector<Event> queue; // don't manually edit this!
#endif
    EventCallback events[MaxCapaxity];
};

} // namespace scheduler

scheduler_unsorted_aos.hpp

// Copyright 2022 TotalJustice.
// SPDX-License-Identifier: GPL-3.0-only
#pragma once

#include <cstdint>
#include <algorithm>
#include <cassert>

namespace scheduler {

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

using s32 = std::int32_t;
// id is the id of the event
// cycles_late will always be 0 if on time or negative if late
using Callback = void(*)(void* user, s32 id, s32 cycles_late);

enum : s32 { RESERVED_ID = 0 };
enum : s32 { TIMEOUT_VALUE = 0x70000000 };
enum : s32 { DISABLE_VALUE = 0x7FFFFFFF };

template <size_t MaxCapaxity>
struct Scheduler {
public:
    // calls reset()
    Scheduler(s32 starting_cycles = 0, Callback reset_cb = nullptr, void* user = nullptr)
    {
        reset(starting_cycles, reset_cb, user);
    }

    // resets queue and cycles, adds reset event, optional custom callback
    void reset(s32 starting_cycles = 0, Callback reset_cb = nullptr, void* user = nullptr)
    {
        for (auto& e : events)
        {
            e.Disable();
        }
        next_event_id = 0;
        cycles = std::min<s32>(starting_cycles, TIMEOUT_VALUE);
        add_absolute(RESERVED_ID, TIMEOUT_VALUE, reset_cb ? reset_cb : reset_event, user ? user : this);
    }

    // fires all expired events
    void fire()
    {
        do {
            const auto id = next_event_id;
            const auto event = events[id];
            events[id].Disable();
            find_next_event();
            event.callback(event.user, id, event.time - cycles);
        } while (!empty() && events[next_event_id].time <= cycles);
    }

    // adds relative new / existing event. updates time,cb,user if existing
    void add(s32 id, s32 event_time, Callback cb, void* user)
    {
        add_absolute(id, cycles + event_time, cb, user);
    }

    // adds new / existing event. updates time,cb,user if existing
    void add_absolute(s32 id, s32 event_time, Callback cb, void* user)
    {
        events[id].time = event_time;
        events[id].callback = cb;
        events[id].user = user;

        // check if we updated the next event
        if (id == next_event_id)
        {
            find_next_event();
        }
        // check if new event fires earlier
        else if (events[id].time < events[next_event_id].time)
        {
            next_event_id = id;
        }
    }

    // removes an event, does nothing if event not enabled.
    void remove(s32 id)
    {
        events[id].Disable();
        if (id == next_event_id)
        {
            find_next_event();
        }
    }

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

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

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

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

    // advances scheduler so that get_ticks() == get_next_event_cycles() if event has greater cycles
    void advance_to_next_event()
    {
        assert(!empty());
        // only advance if the next event time is greater than current time
        if (events[next_event_id].time > cycles) [[likely]]
        {
            cycles = events[next_event_id].time;
        }
    }

    void find_next_event()
    {
        s32 new_id = 0;
        for (s32 i = 1; i < MaxCapaxity; i++)
        {
            // don't need to explicitly check if an event is enabled
            // as the time will be set to 0x7FFFFFFF
            if (events[i].time < events[new_id].time)
            {
                new_id = i;
            }
        }
        next_event_id = new_id;
    }

    // default reset event
    static void reset_event(void* user, s32 id, [[maybe_unused]] s32 _ = 0)
    {
        auto s = static_cast<Scheduler*>(user);

        // no sort because order remains the same.
        for (auto& e : s->events)
        {
            if (e.Enabled())
            {
                e.time -= TIMEOUT_VALUE;
            }
        }

        s->cycles -= TIMEOUT_VALUE;
        s->add_absolute(id, TIMEOUT_VALUE, reset_event, user);
    }

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

        [[nodiscard]] auto Enabled() const -> bool
        {
            return time != DISABLE_VALUE;
        }

        void Disable()
        {
            time = DISABLE_VALUE;
        }
    };

    s32 cycles; // remember to tick this!
    s32 next_event_id;
    Event events[MaxCapaxity];
};

scheduler_unsorted_soa.hpp

// Copyright 2022 TotalJustice.
// SPDX-License-Identifier: GPL-3.0-only
#pragma once

#include <cstdint>
#include <algorithm>
#include <cassert>

namespace scheduler {

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

using s32 = std::int32_t;
// id is the id of the event
// cycles_late will always be 0 if on time or negative if late
using Callback = void(*)(void* user, s32 id, s32 cycles_late);

enum : s32 { RESERVED_ID = 0 };
enum : s32 { TIMEOUT_VALUE = 0x70000000 };
enum : s32 { DISABLE_VALUE = 0x7FFFFFFF };

template <size_t MaxCapaxity>
struct Scheduler {
public:
    // calls reset()
    Scheduler(s32 starting_cycles = 0, Callback reset_cb = nullptr, void* user = nullptr)
    {
        reset(starting_cycles, reset_cb, user);
    }

    // resets queue and cycles, adds reset event, optional custom callback
    void reset(s32 starting_cycles = 0, Callback reset_cb = nullptr, void* user = nullptr)
    {
        for (auto& e : events)
        {
            e.Disable();
        }
        next_event_id = 0;
        cycles = std::min<s32>(starting_cycles, TIMEOUT_VALUE);
        add_absolute(RESERVED_ID, TIMEOUT_VALUE, reset_cb ? reset_cb : reset_event, user ? user : this);
    }

    // fires all expired events
    void fire()
    {
        do {
            const auto id = next_event_id;
            const auto event = events[id];
            events[id].Disable();
            find_next_event();
            callbacks[id].callback(callbacks[id].user, id, event.time - cycles);
        } while (!empty() && events[next_event_id].time <= cycles);
    }

    // adds relative new / existing event. updates time,cb,user if existing
    void add(s32 id, s32 event_time, Callback cb, void* user)
    {
        add_absolute(id, cycles + event_time, cb, user);
    }

    // adds new / existing event. updates time,cb,user if existing
    void add_absolute(s32 id, s32 event_time, Callback cb, void* user)
    {
        events[id].time = event_time;
        callbacks[id].callback = cb;
        callbacks[id].user = user;

        // check if we updated the next event
        if (id == next_event_id)
        {
            find_next_event();
        }
        // check if new event fires earlier
        else if (events[id].time < events[next_event_id].time)
        {
            next_event_id = id;
        }
    }

    // removes an event, does nothing if event not enabled.
    void remove(s32 id)
    {
        events[id].Disable();
        if (id == next_event_id)
        {
            find_next_event();
        }
    }

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

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

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

    // return true if fire() should be called
    [[nodiscard]] auto should_fire() const -> bool
    {
        assert(!empty());
        return events[next_event_id].time <= cycles;
    }
    
    // advances scheduler so that get_ticks() == get_next_event_cycles() if event has greater cycles
    void advance_to_next_event()
    {
        assert(!empty());
        // only advance if the next event time is greater than current time
        if (events[next_event_id].time > cycles) [[likely]]
        {
            cycles = events[next_event_id].time;
        }
    }

    // default reset event
    static void reset_event(void* user, s32 id, [[maybe_unused]] s32 _ = 0)
    {
        auto s = static_cast<Scheduler*>(user);

        // no sort because order remains the same.
        for (auto& e : s->events)
        {
            if (e.Enabled())
            {
                e.time -= TIMEOUT_VALUE;
            }
        }

        s->cycles -= TIMEOUT_VALUE;
        s->add_absolute(id, TIMEOUT_VALUE, reset_event, user);
    }

private:
    void find_next_event()
    {
        s32 new_id = 0;
        for (s32 i = 1; i < MaxCapaxity; i++)
        {
            // don't need to explicitly check if an event is enabled
            // as the time will be set to 0x7FFFFFFF
            if (events[i].time < events[new_id].time)
            {
                new_id = i;
            }
        }
        next_event_id = new_id;
    }

    struct Event {
        s32 time; // time until event expires (scheduler.cycles + event.cycle)

        [[nodiscard]] auto Enabled() const -> bool
        {
            return time != DISABLE_VALUE;
        }

        void Disable()
        {
            time = DISABLE_VALUE;
        }
    };

    struct EventCallback {
        Callback callback; // function to call on event expire
        void* user; // user data passed to the callback
    };

    s32 cycles;
    s32 next_event_id;
    Event events[MaxCapaxity];
    EventCallback callbacks[MaxCapaxity];
};

} // namespace scheduler