OXYGENHUB
◆ main openmsx / src / SchedulerQueue.hh
4.4 KiB · C++ · last changed chore(): initial commit 1 month ago source blame history raw
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;
24 
	SchedulerQueue()
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; // == storage.end() - 1 // for sentinel
146 
	T* useBegin;
147 
	T* useEnd;
148 
};
149
150 
} // namespace openmsx
151
152 
#endif // SCHEDULERQUEUE_HH