openMSX
SchedulerQueue.hh
Go to the documentation of this file.
1#ifndef SCHEDULERQUEUE_HH
2#define SCHEDULERQUEUE_HH
3
4#include "MemBuffer.hh"
5#include <algorithm>
6#include <cassert>
7#include <concepts>
8#include <cstdlib>
9
10namespace openmsx {
11
12// This is similar to a sorted vector<T>. Though this container can have spare
13// capacity both at the front and at the end (vector only at the end). This
14// means that when you remove the smallest element and insert a new element
15// that's only slightly bigger than the smallest one, there's a very good
16// chance this insert runs in O(1) (for vector it's O(N), with N the size of
17// the vector). This is a scenario that occurs very often in the Scheduler
18// code.
19template<typename T> class SchedulerQueue
20{
21public:
22 static constexpr int CAPACITY = 32; // initial capacity
23 static constexpr int SPARE_FRONT = 1;
25 : storage (CAPACITY + 1) // one extra for sentinel
26 , storageEnd(storage.data() + CAPACITY)
27 , useBegin (storage.data() + SPARE_FRONT)
28 , useEnd (useBegin)
29 {
30 }
31
32 [[nodiscard]] size_t capacity() const { return storageEnd - storage.data(); }
33 [[nodiscard]] size_t spareFront() const { return useBegin - storage.data(); }
34 [[nodiscard]] size_t spareBack() const { return storageEnd - useEnd; }
35 [[nodiscard]] size_t size() const { return useEnd - useBegin; }
36 [[nodiscard]] bool empty() const { return useEnd == useBegin; }
37
38 // Returns reference to the first element, This is the smallest element
39 // according to the sorting criteria, see insert().
40 [[nodiscard]] T& front() { return *useBegin; }
41 [[nodiscard]] const T& front() const { return *useBegin; }
42
43 [[nodiscard]] T* begin() { return useBegin; }
44 [[nodiscard]] const T* begin() const { return useBegin; }
45 [[nodiscard]] T* end() { return useEnd; }
46 [[nodiscard]] const T* end() const { return useEnd; }
47
48 // Insert new element.
49 // Elements are sorted according to the given LESS predicate.
50 // SET_SENTINEL must set an element to its maximum value (so that
51 // 'less(x, sentinel)' is true for any x).
52 // (Important) two elements that are equivalent according to 'less'
53 // keep their relative order, IOW newly inserted elements are inserted
54 // after existing equivalent elements.
55 void insert(const T& t, std::invocable<T&> auto setSentinel, std::equivalence_relation<T, T> auto less)
56 {
57 setSentinel(*useEnd); // put sentinel at the end
58 assert(less(t, *useEnd));
59
60 T* it = useBegin;
61 while (!less(t, *it)) ++it;
62
63 if ((it - useBegin) <= (useEnd - it)) {
64 if (useBegin != storage.data()) [[likely]] {
65 insertFront(it, t);
66 } else if (useEnd != storageEnd) {
67 insertBack(it, t);
68 } else {
69 insertRealloc(it, t);
70 }
71 } else {
72 if (useEnd != storageEnd) [[likely]] {
73 insertBack(it, t);
74 } else if (useBegin != storage.data()) {
75 insertFront(it, t);
76 } else {
77 insertRealloc(it, t);
78 }
79 }
80 }
81
82 // Remove the smallest element.
84 {
85 assert(!empty());
86 ++useBegin;
87 }
88
89 // Remove the first element for which the given predicate returns true.
90 bool remove(std::predicate<T> auto p)
91 {
92 T* it = std::find_if(useBegin, useEnd, p);
93 if (it == useEnd) return false;
94
95 if ((it - useBegin) < (useEnd - it - 1)) [[unlikely]] {
96 ++useBegin;
97 std::copy_backward(useBegin - 1, it, it + 1);
98 } else {
99 std::copy(it + 1, useEnd, it);
100 --useEnd;
101 }
102 return true;
103 }
104
105 // Remove all elements for which the given predicate returns true.
106 void remove_all(std::predicate<T> auto p)
107 {
108 useEnd = std::remove_if(useBegin, useEnd, p);
109 }
110
111private:
112 void insertFront(T* it, const T& t)
113 {
114 --useBegin;
115 std::copy(useBegin + 1, it, useBegin);
116 --it;
117 *it = t;
118 }
119 void insertBack(T* it, const T& t)
120 {
121 ++useEnd;
122 std::copy_backward(it, useEnd -1, useEnd);
123 *it = t;
124 }
125 void insertRealloc(T* it, const T& t)
126 {
127 size_t oldSize = storageEnd - storage.data();
128 size_t newSize = oldSize * 2;
129
130 MemBuffer<T> newStorage(newSize + 1); // one extra for sentinel
131 T* newUseBegin = newStorage.data() + SPARE_FRONT;
132 std::copy(useBegin, it, newUseBegin);
133 *(newUseBegin + (it - useBegin)) = t;
134 std::copy(it, useEnd, newUseBegin + (it - useBegin) + 1);
135
136 storage = std::move(newStorage);
137 storageEnd = storage.data() + newSize;
138 useBegin = newUseBegin;
139 useEnd = useBegin + oldSize + 1;
140 }
141
142private:
143 // Invariant: storage.data() <= useBegin <= useEnd <= storageEnd
144 MemBuffer<T> storage;
145 T* storageEnd;
146 T* useBegin;
147 T* useEnd;
148};
149
150} // namespace openmsx
151
152#endif // SCHEDULERQUEUE_HH
TclObject t
static constexpr int CAPACITY
void insert(const T &t, std::invocable< T & > auto setSentinel, std::equivalence_relation< T, T > auto less)
static constexpr int SPARE_FRONT
bool remove(std::predicate< T > auto p)
void remove_all(std::predicate< T > auto p)
size_t spareBack() const
const T * end() const
size_t spareFront() const
const T * begin() const
const T & front() const
This file implemented 3 utility functions:
Definition: Autofire.cc:9
auto find_if(InputRange &&range, UnaryPredicate pred)
Definition: ranges.hh:157
auto remove_if(ForwardRange &&range, UnaryPredicate pred)
Definition: ranges.hh:238
auto copy(InputRange &&range, OutputIter out)
Definition: ranges.hh:208