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