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 
10 namespace 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.
19 template<typename T> class SchedulerQueue
20 {
21 public:
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.
83  void remove_front()
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 
111 private:
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 
142 private:
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
const T * begin() const
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 & 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