MLIB
Loading...
Searching...
No Matches
ringbuf.h
Go to the documentation of this file.
1/*
2 Copyright (c) Mircea Neacsu (2014-2025) Licensed under MIT License.
3 This file is part of MLIB project. See LICENSE file for full license terms.
4*/
5
7
8#pragma once
9
10#include <memory>
11#include <vector>
12#include <stdexcept>
13#include <assert.h>
14
15#if __has_include("defs.h")
16#include "defs.h"
17#endif
18
19namespace mlib {
20
22template <class T>
24{
25public:
26 using value_type = typename T;
27 using reference = typename T&;
28 using const_reference = typename T const&;
29 using size_type = typename size_t;
30
33 {
34 public:
35 // Following typedefs must exist to allow instantiation of std::iterator_traits
36 using difference_type = std::ptrdiff_t;
37 using value_type = T;
38 using reference = T const&;
39 using pointer = T const*;
40 using iterator_category = std::bidirectional_iterator_tag;
41
44 : ring (nullptr)
45 , pos (0)
46 {}
47
49 reference operator* ()
50 {
51 if (pos == (size_t)(-1))
52 throw std::range_error ("Ring buffer iterator at end!");
53 return ring->buf[pos];
54 }
55
57 const reference operator* () const
58 {
59 if (pos == (size_t)(-1))
60 throw std::range_error ("Ring buffer iterator at end!");
61 return ring->buf[pos];
62 }
63
65 pointer operator->()
66 {
67 if (pos == (size_t)(-1))
68 throw std::range_error ("Ring buffer iterator at end!");
69 return &ring->buf[pos];
70 }
71
73 const pointer operator->() const
74 {
75 if (pos == (size_t)(-1))
76 throw std::range_error ("Ring buffer iterator at end!");
77 return &ring->buf[pos];
78 }
79
82 {
83 const_iterator tmp = *this;
84 pos = ring->increment (pos);
85 return tmp;
86 }
87
90 {
91 pos = ring->increment (pos);
92 return *this;
93 }
94
97 {
98 const_iterator tmp = *this;
99 pos = ring->decrement (pos);
100 return tmp;
101 }
102
105 {
106 pos = ring->decrement (pos);
107 return *this;
108 }
109
111 bool operator== (const const_iterator& it) const
112 {
113 return (ring == it.ring) && (pos == it.pos);
114 }
115
117 bool operator!= (const const_iterator& it) const
118 {
119 return !operator== (it);
120 }
121
124 {
125 if (this != &rhs)
126 {
127 ring = rhs.ring;
128 pos = rhs.pos;
129 }
130 return *this;
131 }
132
134 const_iterator operator+ (size_t inc) const
135 {
136 const_iterator tmp = *this;
137 tmp.pos = ring->add (pos, inc);
138 return tmp;
139 }
140
143 {
144 pos = ring->add (pos, inc);
145 return *this;
146 }
147
149 const_iterator operator- (size_t dec) const
150 {
151 const_iterator tmp = *this;
152 tmp.pos = ring->subtract (pos, dec);
153 return tmp;
154 }
155
158 {
159 pos = ring->subtract (pos, dec);
160 return *this;
161 }
162
164 ptrdiff_t operator- (const const_iterator& other) const
165 {
166 assert (ring == other.ring);
167 size_t p1 = (pos != -1) ? pos
168 : (ring->back_idx == ring->front_idx) ? ring->sz
169 : ring->back_idx;
170 size_t p2 = (other.pos != -1) ? other.pos
171 : (ring->back_idx == ring->front_idx) ? ring->sz
172 : ring->back_idx;
173 if (p1 >= p2)
174 return p1 - p2;
175 else
176 return ring->cap - p2 + p1;
177 }
178
179 protected:
180 const_iterator (const ring_buffer* ring_, size_t pos_)
181 : ring (ring_)
182 , pos (ring->sz?pos_: -1)
183 {
184 }
185
186 const ring_buffer* ring;
187 size_t pos;
188 friend class ring_buffer;
189 };
190
191 class iterator final : public const_iterator
192 {
193 public:
194 // Following typedefs must exist to allow instantiation of std::iterator_traits
195 using difference_type = std::ptrdiff_t;
196 using value_type = T;
197 using reference = T&;
198 using pointer = T*;
199 using iterator_category = std::bidirectional_iterator_tag;
200 using my_base = const_iterator;
201
204 : const_iterator ()
205 {}
206
207 iterator (const const_iterator& ci)
208 : const_iterator (ci)
209 {}
210
212 reference operator* ()
213 {
214 return const_cast<reference> (my_base::operator* ());
215 }
216
218 pointer operator->()
219 {
220 return const_cast<pointer> (my_base::operator-> ());
221 }
222
225 {
226 return my_base::operator++ (x);
227 }
228
231 {
233 return *this;
234 }
235
238 {
239 return my_base::operator-- (x);
240 }
241
244 {
246 return *this;
247 }
248
251 {
253 return *this;
254 }
255
257 iterator operator+ (size_t inc) const
258 {
259 return my_base::operator+ (inc);
260 }
261
264 {
266 return *this;
267 }
268
270 iterator operator- (size_t dec) const
271 {
272 return my_base::operator- (dec);
273 }
274
277 {
279 return *this;
280 }
281
283 ptrdiff_t operator- (const const_iterator& other) const
284 {
285 return my_base::operator- (other);
286 }
287
288 private:
289 iterator (const ring_buffer* ring_, size_t pos_)
290 : const_iterator (ring_, pos_)
291 {}
292
293 friend class ring_buffer;
294 };
295
298 : buf (std::unique_ptr<T[]> (new T[size]))
299 , cap (size)
300 , front_idx (0)
301 , back_idx (0)
302 , sz (0)
303 {}
304
307 : cap (0)
308 , front_idx (0)
309 , back_idx (0)
310 , sz (0)
311 {}
312
315 : front_idx (other.front_idx)
316 , back_idx (other.back_idx)
317 , cap (other.cap)
318 , sz (other.sz)
319 {
320 if (other.cap)
321 {
322 buf = std::unique_ptr<T[]> (new T[other.cap]);
323 for (size_t i = 0; i < sz; i++)
324 {
325 size_t idx = (front_idx + i) % cap;
326 buf[idx] = other.buf[idx];
327 }
328 }
329 }
330
332 ring_buffer (std::initializer_list<T> il)
333 : buf (std::unique_ptr<T[]> (new T[il.size ()]))
334 , cap (il.size ())
335 , front_idx (0)
336 , back_idx (0)
337 , sz (il.size ())
338 {
339 size_t i = 0;
340 for (const auto v : il)
341 buf[i++] = std::move (v);
342 }
343
345 ring_buffer& operator= (const ring_buffer& rhs)
346 {
347 if (&rhs != this)
348 {
349 front_idx = rhs.front_idx;
350 back_idx = rhs.back_idx;
351 cap = rhs.cap;
352 sz = rhs.sz;
353 if (rhs.cap)
354 {
355 buf.reset (new T[rhs.cap]);
356 for (size_t i = 0; i < sz; i++)
357 {
358 size_t idx = (front_idx + i) % cap;
359 buf[idx] = rhs.buf[idx];
360 }
361 }
362 else
363 buf.reset ();
364 }
365 return *this;
366 }
367
369 bool operator== (const ring_buffer<T>& other) const
370 {
371 if (cap == other.cap && sz == other.sz)
372 {
373 for (size_t i = 0; i < sz; i++)
374 {
375 size_t idx1 = (front_idx + i) % cap;
376 size_t idx2 = (other.front_idx + i) % other.cap;
377 if (buf[idx1] != other.buf[idx2])
378 return false;
379 }
380 return true;
381 }
382 return false;
383 }
384
386 bool operator!= (const ring_buffer<T>& other) const
387 {
388 return !operator== (other);
389 }
390
392 operator std::vector<T> () const
393 {
394 std::vector<T> v (sz);
395 for (size_t i = 0; i < sz; i++)
396 v[i] = buf[(front_idx + i) % cap];
397
398 return v;
399 }
400
402 void push_back (const T& item)
403 {
404 if (!cap)
405 return; // container not allocated
406
407 if (sz && back_idx == front_idx)
408 front_idx = (front_idx + 1) % cap;
409 else
410 sz++;
411 buf[back_idx] = item;
412 back_idx = (back_idx + 1) % cap;
413 }
414
417 {
418 return iterator (this, front_idx);
419 }
420
423 {
424 return const_iterator (this, front_idx);
425 }
426
429 {
430 return const_iterator (this, front_idx);
431 }
432
435 {
436 return iterator (this, (size_t)(-1));
437 }
438
441 {
442 return const_iterator (this, (size_t)(-1));
443 }
444
447 {
448 return const_iterator (this, (size_t)(-1));
449 }
450
452 void pop_front ()
453 {
454 #ifdef _DEBUG
455 if (!sz)
456 throw std::range_error ("ring_buffer::pop_front - empty container");
457 #endif
458 front_idx = (front_idx + 1) % cap;
459 sz--;
460 }
461
463 T& front ()
464 {
465#ifdef _DEBUG
466 if (!sz)
467 throw std::range_error ("ring_buffer::front - empty container");
468#endif
469 return buf[front_idx];
470 }
471
473 const T& front () const
474 {
475#ifdef _DEBUG
476 if (!sz)
477 throw std::range_error ("ring_buffer::front - empty container");
478#endif
479 return buf[front_idx];
480 }
481
483 T& back ()
484 {
485#ifdef _DEBUG
486 if (!sz)
487 throw std::range_error ("ring_buffer::back - empty container");
488#endif
489 return buf[(back_idx + cap - 1) % cap];
490 }
491
493 const T& back () const
494 {
495#ifdef _DEBUG
496 if (!sz)
497 throw std::range_error ("ring_buffer::back - empty container");
498#endif
499 return buf[(back_idx + cap - 1) % cap];
500 }
501
505 {
506#ifdef _DEBUG
507 if (ptr.ring != this)
508 throw std::runtime_error ("ring_buffer<>::erase - Invalid iterator");
509#endif
510 if (sz == 0)
511 return end (); //erasing from an empty buffer is a no-op
512 size_t pos = ptr.pos == (size_t)-1 ? back_idx : ptr.pos;
513#ifdef _DEBUG
514 if ((front_idx < back_idx && (pos < front_idx || pos >= back_idx))
515 || (front_idx > back_idx && (pos < back_idx || pos >= front_idx)))
516 throw std::range_error ("ring_buffer<>::erase - Bad iterator position");
517#endif
518 for (auto p = pos; p != front_idx; )
519 {
520 auto pp = decrement (p);
521 assert (pp != (size_t)-1);
522 buf[p] = buf[pp];
523 p = pp;
524 }
525 --sz;
526 if (pos == front_idx)
527 pos = increment (pos);
528 front_idx = (front_idx + 1) % cap;
529 return iterator(this, pos);
530 }
531
533 void clear (void)
534 {
535 front_idx = back_idx;
536 sz = 0;
537 }
538
540 bool empty (void) const
541 {
542 return (sz == 0);
543 }
544
546 bool full (void) const
547 {
548 return (sz == cap);
549 }
550
552 size_t capacity () const
553 {
554 return cap;
555 };
556
558 void resize (size_t new_cap)
559 {
560 std::unique_ptr<T[]> newbuf (new_cap ? new T[new_cap] : nullptr);
561 if (new_cap)
562 {
563 if (sz >= new_cap)
564 sz = new_cap;
565 for (size_t i = 0; i < sz; i++)
566 newbuf[i] = buf[(front_idx + i) % cap];
567 }
568 else
569 sz = 0;
570 cap = new_cap;
571 buf.swap (newbuf);
572 front_idx = 0;
573 back_idx = cap ? (front_idx + sz) % cap : 0;
574 }
575
577 size_t size () const
578 {
579 return sz;
580 }
581
582private:
584 size_t increment (size_t pos) const
585 {
586 if (cap && pos != (size_t)-1)
587 pos = (pos + 1) % cap;
588 if (pos == back_idx)
589 pos = (size_t)-1;
590 return pos;
591 }
592
594 size_t decrement (size_t pos) const
595 {
596 if (cap)
597 {
598 if (pos == (size_t)-1)
599 pos = (back_idx + cap - 1) % cap;
600 else if (pos != front_idx)
601 pos = (pos + cap - 1) % cap;
602 }
603 return pos;
604 }
605
607 size_t add (size_t oldpos, size_t delta) const
608 {
609 if (cap && oldpos != -1)
610 {
611 size_t np = oldpos + (delta % cap);
612 if (np >= cap && np >= back_idx + cap)
613 np = (size_t)(-1);
614 else
615 np %= cap;
616 return np;
617 }
618 return oldpos;
619 }
620
622 size_t subtract (size_t oldpos, size_t delta) const
623 {
624 if (cap)
625 {
626 size_t np = (oldpos == (size_t)-1 ? back_idx : oldpos) - (delta % cap) + cap;
627 if (np < front_idx)
628 np = front_idx;
629 else
630 np %= cap;
631 return np;
632 }
633 return oldpos;
634 }
635
636 std::unique_ptr<T[]> buf; //the ring buffer
637 size_t front_idx; // start (oldest) element
638 size_t back_idx; // end (newest) element
639 size_t cap; // capacity
640 size_t sz; // size
641};
642
643} // namespace mlib
Iterator through the circular buffer.
Definition ringbuf.h:33
bool operator!=(const const_iterator &it) const
Inequality comparison.
Definition ringbuf.h:117
const_iterator()
Default constructor.
Definition ringbuf.h:43
const_iterator & operator+=(size_t inc)
Addition assignment operator.
Definition ringbuf.h:142
const_iterator & operator--()
Decrement operator (prefix)
Definition ringbuf.h:104
const_iterator & operator=(const const_iterator &rhs)
Assignment operator.
Definition ringbuf.h:123
reference operator*()
Dereference operator.
Definition ringbuf.h:49
const_iterator operator-(size_t dec) const
Subtraction operator.
Definition ringbuf.h:149
const pointer operator->() const
Object pointer (const version)
Definition ringbuf.h:73
pointer operator->()
Object pointer.
Definition ringbuf.h:65
const_iterator & operator-=(size_t dec)
Subtraction assignment operator.
Definition ringbuf.h:157
const_iterator operator+(size_t inc) const
Addition operator.
Definition ringbuf.h:134
bool operator==(const const_iterator &it) const
Equality comparison.
Definition ringbuf.h:111
const_iterator & operator++()
Increment operator (prefix)
Definition ringbuf.h:89
Definition ringbuf.h:192
iterator()
Default constructor.
Definition ringbuf.h:203
reference operator*()
Dereference operator.
Definition ringbuf.h:212
iterator & operator++()
Increment operator (prefix)
Definition ringbuf.h:230
iterator & operator--()
Decrement operator (prefix)
Definition ringbuf.h:243
iterator operator+(size_t inc) const
Addition operator.
Definition ringbuf.h:257
iterator & operator=(const const_iterator &rhs)
Assignment operator.
Definition ringbuf.h:250
iterator & operator-=(size_t dec)
Subtraction assignment operator.
Definition ringbuf.h:276
iterator operator-(size_t dec) const
Subtraction operator.
Definition ringbuf.h:270
iterator & operator+=(size_t inc)
Addition assignment operator.
Definition ringbuf.h:263
pointer operator->()
Object pointer.
Definition ringbuf.h:218
Circular buffer.
Definition ringbuf.h:24
void pop_front()
Remove oldest element from buffer.
Definition ringbuf.h:452
void clear(void)
Remove all elements from buffer.
Definition ringbuf.h:533
size_t size() const
Return number of elements in buffer.
Definition ringbuf.h:577
ring_buffer(const ring_buffer &other)
Copy constructor.
Definition ringbuf.h:314
T & front()
Return a reference to first (oldest) element in buffer.
Definition ringbuf.h:463
void push_back(const T &item)
Inserts new element in buffer.
Definition ringbuf.h:402
ring_buffer()
Default constructor.
Definition ringbuf.h:306
bool empty(void) const
Return true if buffer is empty.
Definition ringbuf.h:540
const T & front() const
Return a reference to first (oldest) element in buffer.
Definition ringbuf.h:473
ring_buffer(std::initializer_list< T > il)
Initializer list constructor.
Definition ringbuf.h:332
bool full(void) const
Return true if buffer is full.
Definition ringbuf.h:546
const_iterator begin() const
Return a const iterator pointing to first (oldest) element in buffer.
Definition ringbuf.h:422
void resize(size_t new_cap)
(Re)allocate buffer with a different capacity
Definition ringbuf.h:558
const T & back() const
Return reference to last (newest) element in buffer.
Definition ringbuf.h:493
size_t capacity() const
Return maximum buffer size.
Definition ringbuf.h:552
const_iterator cbegin()
Return a const iterator pointing to first (oldest) element in buffer.
Definition ringbuf.h:428
iterator end()
Return an iterator pointing past the last (newest) element in buffer.
Definition ringbuf.h:434
T & back()
Return reference to last (newest) element in buffer.
Definition ringbuf.h:483
const_iterator end() const
Return a const iterator pointing past the last (newest) element in buffer.
Definition ringbuf.h:440
iterator erase(const_iterator &ptr)
Definition ringbuf.h:504
ring_buffer(size_t size)
Constructor.
Definition ringbuf.h:297
const_iterator cend()
Return an iterator pointing past the last (newest) element in buffer.
Definition ringbuf.h:446
iterator begin()
Return an iterator pointing to first (oldest) element in buffer.
Definition ringbuf.h:416
bool operator!=(const timeval &t1, const timeval &t2)
"Not equal" operator
Definition tvops.h:73
bool operator==(const timeval &t1, const timeval &t2)
Equality operator.
Definition tvops.h:31