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 "likely.hh"
6 #include <algorithm>
7 #include <cassert>
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 const int CAPACITY = 32; // initial capacity
23  static const 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  size_t capacity() const { return storageEnd - storage.data(); }
33  size_t spareFront() const { return useBegin - storage.data(); }
34  size_t spareBack() const { return storageEnd - useEnd; }
35  size_t size() const { return useEnd - useBegin; }
36  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  T& front() { return *useBegin; }
41  const T& front() const { return *useBegin; }
42 
43  T* begin() { return useBegin; }
44  const T* begin() const { return useBegin; }
45  T* end() { return useEnd; }
46  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 it's 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  template<typename SET_SENTINEL, typename LESS>
56  void insert(const T& t, SET_SENTINEL setSentinel, LESS less)
57  {
58  setSentinel(*useEnd); // put sentinel at the end
59  assert(less(t, *useEnd));
60 
61  T* it = useBegin;
62  while (!less(t, *it)) ++it;
63 
64  if ((it - useBegin) <= (useEnd - it)) {
65  if (likely(useBegin != storage.data())) {
66  insertFront(it, t);
67  } else if (useEnd != storageEnd) {
68  insertBack(it, t);
69  } else {
70  insertRealloc(it, t);
71  }
72  } else {
73  if (likely(useEnd != storageEnd)) {
74  insertBack(it, t);
75  } else if (useBegin != storage.data()) {
76  insertFront(it, t);
77  } else {
78  insertRealloc(it, t);
79  }
80  }
81  }
82 
83  // Remove the smallest element.
84  void remove_front()
85  {
86  assert(!empty());
87  ++useBegin;
88  }
89 
90  // Remove the first element for which the given predicate returns true.
91  template<typename PRED> bool remove(PRED p)
92  {
93  T* it = std::find_if(useBegin, useEnd, p);
94  if (it == useEnd) return false;
95 
96  if (unlikely((it - useBegin) < (useEnd - it - 1))) {
97  ++useBegin;
98  std::copy_backward(useBegin - 1, it, it + 1);
99  } else {
100  std::copy(it + 1, useEnd, it);
101  --useEnd;
102  }
103  return true;
104  }
105 
106  // Remove all elements for which the given predicate returns true.
107  template<typename PRED> void remove_all(PRED p)
108  {
109  useEnd = std::remove_if(useBegin, useEnd, p);
110  }
111 
112 private:
113  void insertFront(T* it, const T& t)
114  {
115  --useBegin;
116  std::copy(useBegin + 1, it, useBegin);
117  --it;
118  *it = t;
119  }
120  void insertBack(T* it, const T& t)
121  {
122  ++useEnd;
123  std::copy_backward(it, useEnd -1, useEnd);
124  *it = t;
125  }
126  void insertRealloc(T* it, const T& t)
127  {
128  size_t oldSize = storageEnd - storage.data();
129  size_t newSize = oldSize * 2;
130 
131  MemBuffer<T> newStorage(newSize + 1); // one extra for sentinel
132  T* newUseBegin = newStorage.data() + SPARE_FRONT;
133  std::copy(useBegin, it, newUseBegin);
134  *(newUseBegin + (it - useBegin)) = t;
135  std::copy(it, useEnd, newUseBegin + (it - useBegin) + 1);
136 
137  storage = std::move(newStorage);
138  storageEnd = storage.data() + newSize;
139  useBegin = newUseBegin;
140  useEnd = useBegin + oldSize + 1;
141  }
142 
143 private:
144  // Invariant: storage.data() <= useBegin <= useEnd <= storageEnd
145  MemBuffer<T> storage;
146  T* storageEnd;
147  T* useBegin;
148  T* useEnd;
149 };
150 
151 } // namespace openmsx
152 
153 #endif // SCHEDULERQUEUE_HH
const T * end() const
auto copy(InputRange &&range, OutputIter out)
Definition: ranges.hh:149
#define unlikely(x)
Definition: likely.hh:15
size_t spareBack() const
auto find_if(InputRange &&range, UnaryPredicate pred)
Definition: ranges.hh:113
const T & front() const
constexpr auto data(C &c) -> decltype(c.data())
Definition: span.hh:69
static const int CAPACITY
const T * data() const
Returns pointer to the start of the memory buffer.
Definition: MemBuffer.hh:90
size_t spareFront() const
const T * begin() const
Thanks to enen for testing this on a real cartridge:
Definition: Autofire.cc:5
#define likely(x)
Definition: likely.hh:14
TclObject t
void insert(const T &t, SET_SENTINEL setSentinel, LESS less)
static const int SPARE_FRONT