Last active
January 26, 2024 18:18
-
-
Save ITotalJustice/5d1223e56951b4a3b7df093fe5325359 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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]; | |
}; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment