openMSX
circular_buffer.hh
Go to the documentation of this file.
1 
13 #ifndef CIRCULAR_BUFFER_HH
14 #define CIRCULAR_BUFFER_HH
15 
16 #include <algorithm>
17 #include <iterator>
18 #include <utility>
19 #include <cstddef>
20 #include <cstdlib>
21 
23 template<typename BUF, typename T> class cb_iterator
24 {
25 public:
26  using value_type = T;
27  using pointer = T*;
28  using reference = T&;
29  using difference_type = ptrdiff_t;
30  using iterator_category = std::random_access_iterator_tag;
31 
32  cb_iterator() : buf(nullptr), p(nullptr) {}
33  cb_iterator(const cb_iterator& it) : buf(it.buf), p(it.p) {}
34  cb_iterator(const BUF* buf_, T* p_) : buf(buf_), p(p_) {}
35 
37  buf = it.buf; p = it.p; return *this;
38  }
39 
40  [[nodiscard]] T& operator*() const { return *p; }
41  T* operator->() const { return p; }
42 
43  [[nodiscard]] difference_type operator-(const cb_iterator& it) const {
44  return index(p) - index(it.p);
45  }
46 
48  buf->increment(p);
49  if (p == buf->last) p = nullptr;
50  return *this;
51  }
53  if (p == nullptr) p = buf->last;
54  buf->decrement(p);
55  return *this;
56  }
57  cb_iterator operator++(int) { auto tmp = *this; ++*this; return tmp; }
58  cb_iterator operator--(int) { auto tmp = *this; --*this; return tmp; }
59 
61  if (n > 0) {
62  p = buf->add(p, n);
63  if (p == buf->last) p = nullptr;
64  } else if (n < 0) {
65  if (p == nullptr) p = buf->last;
66  p = buf->sub(p, -n);
67  } else {
68  // nothing, but _must_ be handled separately
69  }
70  return *this;
71  }
72  cb_iterator& operator-=(difference_type n) { *this += -n; return *this; }
73 
74  [[nodiscard]] cb_iterator operator+(difference_type n) { return cb_iterator(*this) += n; }
75  [[nodiscard]] cb_iterator operator-(difference_type n) { return cb_iterator(*this) -= n; }
76 
77  [[nodiscard]] T& operator[](difference_type n) const { return *(*this + n); }
78 
79  [[nodiscard]] bool operator==(const cb_iterator& it) const { return p == it.p; }
80  [[nodiscard]] bool operator!=(const cb_iterator& it) const { return p != it.p; }
81 
82  [[nodiscard]] bool operator<(const cb_iterator& it) const {
83  return index(p) < index(it.p);
84  }
85  [[nodiscard]] bool operator> (const cb_iterator& it) const { return it < *this; }
86  [[nodiscard]] bool operator<=(const cb_iterator& it) const { return !(it < *this); }
87  [[nodiscard]] bool operator>=(const cb_iterator& it) const { return !(*this < it); }
88 
89 private:
90  [[nodiscard]] size_t index(const T* q) const {
91  return q ? buf->index(q) : buf->size();
92  }
93 
94  const BUF* buf;
95  T* p; // invariant: end-iterator -> nullptr,
96  // other iterators -> pointer to element
97 };
98 
100 template<typename T> class circular_buffer
101 {
102 public:
105  using reverse_iterator = std::reverse_iterator< iterator>;
106  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
107  using value_type = T;
108  using pointer = T*;
109  using reference = T&;
110  using difference_type = ptrdiff_t;
111  using size_type = size_t;
112 
113  circular_buffer() = default;
114 
115  explicit circular_buffer(size_t buffer_capacity)
116  {
117  buf = allocate(buffer_capacity);
118  stop = buf + buffer_capacity;
119  first = last = buf;
120  }
121 
123  : siz(cb.size())
124  {
125  buf = allocate(cb.capacity());
126  stop = buf + cb.capacity();
127  first = buf;
128  try {
129  last = uninitialized_copy(cb.begin(), cb.end(), buf);
130  } catch (...) {
131  free(buf);
132  throw;
133  }
134  if (last == stop) last = buf;
135  }
136 
138  {
139  cb.swap(*this);
140  }
141 
143  destroy();
144  }
145 
147  if (this == &cb) return *this;
148  T* buff = allocate(cb.capacity());
149  try {
150  reset(buff,
151  uninitialized_copy(cb.begin(), cb.end(), buff),
152  cb.capacity());
153  } catch (...) {
154  free(buff);
155  throw;
156  }
157  return *this;
158  }
159 
161  cb.swap(*this);
162  circular_buffer().swap(cb);
163  return *this;
164  }
165 
166  void swap(circular_buffer& cb) noexcept {
167  std::swap(buf, cb.buf);
168  std::swap(stop, cb.stop);
169  std::swap(first, cb.first);
170  std::swap(last, cb.last);
171  std::swap(siz, cb.siz);
172  }
173 
174  [[nodiscard]] auto begin() {
175  return iterator(this, empty() ? nullptr : first);
176  }
177  [[nodiscard]] auto begin() const {
178  return const_iterator(this, empty() ? nullptr : first);
179  }
180  [[nodiscard]] auto end() { return iterator (this, nullptr); }
181  [[nodiscard]] auto end() const { return const_iterator(this, nullptr); }
182  [[nodiscard]] auto rbegin() { return reverse_iterator(end()); }
183  [[nodiscard]] auto rbegin() const { return const_reverse_iterator(end()); }
184  [[nodiscard]] auto rend() { return reverse_iterator(begin()); }
185  [[nodiscard]] auto rend() const { return const_reverse_iterator(begin()); }
186 
187  [[nodiscard]] auto& operator[](size_t i) { return *add(first, i); }
188  [[nodiscard]] auto& operator[](size_t i) const { return *add(first, i); }
189 
190  [[nodiscard]] auto& front() { return *first; }
191  [[nodiscard]] auto& front() const { return *first; }
192  [[nodiscard]] auto& back() { return *((last == buf ? stop : last) - 1); }
193  [[nodiscard]] auto& back() const { return *((last == buf ? stop : last) - 1); }
194 
195  [[nodiscard]] size_t size() const { return siz; }
196  [[nodiscard]] bool empty() const { return size() == 0; }
197  [[nodiscard]] bool full() const { return capacity() == size(); }
198  [[nodiscard]] size_t reserve() const { return capacity() - size(); }
199  [[nodiscard]] size_t capacity() const { return stop - buf; }
200 
201  void set_capacity(size_t new_capacity) {
202  if (new_capacity == capacity()) return;
203  T* new_buf = allocate(new_capacity);
204  iterator b = begin();
205  try {
206  reset(new_buf,
207  uninitialized_move_n(b, std::min(new_capacity, size()),
208  new_buf),
209  new_capacity);
210  } catch (...) {
211  free(new_buf);
212  throw;
213  }
214  }
215 
216  void push_back (const T& t) { push_back_impl <const T& >( t ); }
217  void push_back ( T&& t) { push_back_impl < T&&>(std::move(t)); }
218  void push_front(const T& t) { push_front_impl<const T& >( t ); }
219  void push_front( T&& t) { push_front_impl< T&&>(std::move(t)); }
220 
221  void push_back(std::initializer_list<T> list) {
222  for (auto& e : list) push_back(e);
223  }
224 
225  void pop_back() {
226  decrement(last);
227  last->~T();
228  --siz;
229  }
230 
231  void pop_front() {
232  first->~T();
233  increment(first);
234  --siz;
235  }
236 
237  void clear() {
238  for (size_t i = 0; i < size(); ++i, increment(first)) {
239  first->~T();
240  }
241  siz = 0;
242  }
243 
244 private:
245  [[nodiscard]] T* uninitialized_copy(const_iterator b, const_iterator e, T* dst) {
246  T* next = dst;
247  try {
248  while (b != e) {
249  ::new (dst) T(*b);
250  ++b; ++dst;
251  }
252  } catch (...) {
253  while (next != dst) {
254  next->~T();
255  ++next;
256  }
257  throw;
258  }
259  return dst;
260  }
261 
262  [[nodiscard]] T* uninitialized_move_n(iterator src, size_t n, T* dst) {
263  while (n) {
264  ::new (dst) T(std::move(*src));
265  ++src; ++dst; --n;
266  }
267  return dst;
268  }
269 
270  template<typename ValT> void push_back_impl(ValT t) {
271  ::new (last) T(static_cast<ValT>(t));
272  increment(last);
273  ++siz;
274  }
275 
276  template<typename ValT> void push_front_impl(ValT t) {
277  try {
278  decrement(first);
279  ::new (first) T(static_cast<ValT>(t));
280  ++siz;
281  } catch (...) {
282  increment(first);
283  throw;
284  }
285  }
286 
287  template<typename Pointer> void increment(Pointer& p) const {
288  if (++p == stop) p = buf;
289  }
290  template<typename Pointer> void decrement(Pointer& p) const {
291  if (p == buf) p = stop;
292  --p;
293  }
294  template<typename Pointer> [[nodiscard]] Pointer add(Pointer p, difference_type n) const {
295  p += n;
296  if (p >= stop) p -= capacity();
297  return p;
298  }
299  template<typename Pointer> [[nodiscard]] Pointer sub(Pointer p, difference_type n) const {
300  p -= n;
301  if (p < buf) p += capacity();
302  return p;
303  }
304 
305  [[nodiscard]] size_t index(const T* p) const {
306  return (p >= first)
307  ? (p - first)
308  : (stop - first) + (p - buf);
309  }
310 
311  [[nodiscard]] T* allocate(size_t n) {
312  return (n == 0) ? nullptr
313  : static_cast<T*>(malloc(n * sizeof(T)));
314  }
315 
316  void destroy() {
317  clear();
318  free(buf);
319  }
320 
321  void reset(T* new_buf, T* new_last, size_t new_capacity) {
322  destroy();
323  siz = new_last - new_buf;
324  first = buf = new_buf;
325  stop = buf + new_capacity;
326  last = new_last == stop ? buf : new_last;
327  }
328 
329 private:
330  T* buf = nullptr; // start of allocated area
331  T* stop = nullptr; // end of allocated area (exclusive)
332  T* first = nullptr; // position of the 1st element in the buffer
333  T* last = nullptr; // position past the last element
334  // note: both for a full or empty buffer first==last
335  size_t siz = 0; // number of elements in the buffer
336 
337  template<typename BUF, typename T2> friend class cb_iterator;
338 };
339 
340 
344 template<typename T> class cb_queue
345 {
346 public:
352 
353  cb_queue() = default;
354  explicit cb_queue(size_t capacity)
355  : buf(capacity) {}
356 
357  template<typename U>
358  void push_back(U&& u) { checkGrow(); buf.push_back(std::forward<U>(u)); }
359 
360  template<typename U>
361  void push_back(std::initializer_list<U> list) {
362  for (auto& e : list) push_back(e);
363  }
364 
365  T pop_front() {
366  T t = std::move(buf.front());
367  buf.pop_front();
368  return t;
369  }
370 
371  [[nodiscard]] const T& front() const { return buf.front(); }
372  [[nodiscard]] const T& back() const { return buf.back(); }
373  [[nodiscard]] const T& operator[](size_t i) const { return buf[i]; }
374 
375  [[nodiscard]] auto begin() { return buf.begin(); }
376  [[nodiscard]] auto end() { return buf.end(); }
377  [[nodiscard]] auto begin() const { return buf.begin(); }
378  [[nodiscard]] auto end() const { return buf.end(); }
379  [[nodiscard]] auto rbegin() { return buf.rbegin(); }
380  [[nodiscard]] auto rbegin() const { return buf.rbegin(); }
381  [[nodiscard]] auto rend() { return buf.rend(); }
382  [[nodiscard]] auto rend() const { return buf.rend(); }
383 
384  [[nodiscard]] size_t size() const { return buf.size(); }
385  [[nodiscard]] bool empty() const { return buf.empty(); }
386  void clear() { buf.clear(); }
387 
388  [[nodiscard]] auto& getBuffer() { return buf; }
389  [[nodiscard]] auto& getBuffer() const { return buf; }
390 
391 private:
392  void checkGrow() {
393  if (buf.full()) {
394  buf.set_capacity(std::max(size_t(4), buf.capacity() * 2));
395  }
396  }
397 
398  circular_buffer<T> buf;
399 };
400 
401 #endif
bool operator==(const cb_iterator &it) const
void push_back(std::initializer_list< T > list)
bool operator!=(const cb_iterator &it) const
typename circular_buffer< std::unique_ptr< openmsx::Frame > >::const_reverse_iterator const_reverse_iterator
cb_iterator & operator++()
typename circular_buffer< std::unique_ptr< openmsx::Frame > >::iterator iterator
void push_front(const T &t)
std::reverse_iterator< iterator > reverse_iterator
cb_iterator operator-(difference_type n)
circular_buffer & operator=(const circular_buffer &cb)
typename circular_buffer< std::unique_ptr< openmsx::Frame > >::reverse_iterator reverse_iterator
vecN< N, T > min(const vecN< N, T > &x, const vecN< N, T > &y)
Definition: gl_vec.hh:274
const T & back() const
bool operator<=(const cb_iterator &it) const
circular_buffer & operator=(circular_buffer &&cb) noexcept
size_t size() const
std::unique_ptr< openmsx::Frame > & reference
cb_iterator & operator+=(difference_type n)
std::reverse_iterator< const_iterator > const_reverse_iterator
cb_iterator operator++(int)
auto & getBuffer()
auto begin() const
auto rbegin() const
cb_iterator & operator-=(difference_type n)
vecN< N, T > max(const vecN< N, T > &x, const vecN< N, T > &y)
Definition: gl_vec.hh:292
cb_iterator(const BUF *buf_, T *p_)
auto end() const
This implements a queue on top of circular_buffer (not part of boost).
size_t size(std::string_view utf8)
T & operator[](difference_type n) const
bool empty() const
auto & operator[](size_t i)
bool operator>(const cb_iterator &it) const
auto & front() const
Circular buffer class, based on boost::circular_buffer/.
cb_iterator operator--(int)
size_t size() const
circular_buffer(circular_buffer &&cb) noexcept
void push_back(std::initializer_list< U > list)
cb_iterator operator+(difference_type n)
circular_buffer(const circular_buffer &cb)
auto & operator[](size_t i) const
auto end() const
auto & back() const
T & operator*() const
void swap(circular_buffer &cb) noexcept
auto rend() const
circular_buffer(size_t buffer_capacity)
cb_queue(size_t capacity)
ptrdiff_t difference_type
bool operator>=(const cb_iterator &it) const
std::random_access_iterator_tag iterator_category
auto begin() const
This code is heavily based on boost circular_buffer: http://www.boost.org/doc/libs/1_55_0/doc/html/ci...
T * operator->() const
difference_type operator-(const cb_iterator &it) const
const T & operator[](size_t i) const
auto rbegin() const
bool empty() const
auto & getBuffer() const
typename circular_buffer< std::unique_ptr< openmsx::Frame > >::const_iterator const_iterator
size_t reserve() const
bool full() const
void push_back(U &&u)
void set_capacity(size_t new_capacity)
size_t capacity() const
void push_back(T &&t)
void push_back(const T &t)
TclObject t
cb_iterator & operator--()
cb_iterator(const cb_iterator &it)
bool operator<(const cb_iterator &it) const
void push_front(T &&t)
cb_iterator & operator=(const cb_iterator &it)
auto rend() const
const T & front() const
typename circular_buffer< std::unique_ptr< openmsx::Frame > >::value_type value_type