tlx
Loading...
Searching...
No Matches
ring_buffer.hpp
Go to the documentation of this file.
1/*******************************************************************************
2 * tlx/container/ring_buffer.hpp
3 *
4 * Part of tlx - http://panthema.net/tlx
5 *
6 * Copyright (C) 2015-2017 Timo Bingmann <tb@panthema.net>
7 *
8 * All rights reserved. Published under the Boost Software License, Version 1.0
9 ******************************************************************************/
10
11#ifndef TLX_CONTAINER_RING_BUFFER_HEADER
12#define TLX_CONTAINER_RING_BUFFER_HEADER
13
14#include <cassert>
15#include <cstdint>
16#include <cstdlib>
17#include <memory>
18#include <vector>
19
21
22namespace tlx {
23
24//! \addtogroup tlx_container
25//! \{
26
27/*!
28 * A ring (circular) buffer of static (non-growing) size.
29 *
30 * Due to many modulo operations with capacity_, the capacity is rounded up to
31 * the next power of two, even for powers of two! This is because otherwise
32 * size() == end - begin == 0 after filling the ring buffer, and adding another
33 * size_ member requires more book-keeping.
34 */
35template <typename Type, class Allocator = std::allocator<Type> >
37{
38public:
39 using value_type = Type;
40 using allocator_type = Allocator;
41
42 using alloc_traits = std::allocator_traits<allocator_type>;
43
44 typedef Type& reference;
45 typedef const Type& const_reference;
46 typedef Type* pointer;
47 typedef const Type* const_pointer;
48
49 using size_type = typename allocator_type::size_type;
50 using difference_type = typename allocator_type::difference_type;
51
52 // using iterator;
53 // using const_iterator;
54 // using reverse_iterator = std::reverse_iterator<iterator>;
55 // using const_reverse_iterator = std::reverse_iterator<const_iterator>;
56
57 explicit RingBuffer(const Allocator& alloc = allocator_type()) noexcept
58 : max_size_(0), alloc_(alloc),
59 capacity_(0), mask_(0), data_(nullptr) { }
60
61 explicit RingBuffer(size_t max_size,
62 const Allocator& alloc = allocator_type())
63 : max_size_(max_size), alloc_(alloc),
65 mask_(capacity_ - 1),
67
68 //! copy-constructor: create new ring buffer
70 : max_size_(rb.max_size_),
71 alloc_(rb.alloc_),
73 mask_(rb.mask_),
75 // copy items using existing methods (we cannot just flat copy the array
76 // due to item construction).
77 for (size_t i = 0; i < rb.size(); ++i) {
78 push_back(rb[i]);
79 }
80 }
81
82 //! copyable: create new ring buffer
84 if (this == &rb) return *this;
85 // empty this buffer
86 clear();
87 // reallocate buffer if the size changes
88 if (capacity_ != rb.capacity_ || alloc_ != rb.alloc_)
89 {
90 alloc_.deallocate(data_, capacity_);
91 alloc_ = rb.alloc_;
93 data_ = alloc_.allocate(capacity_);
94 }
95 // copy over fields
97 mask_ = rb.mask_;
98 begin_ = end_ = 0;
99 // copy over items (we cannot just flat copy the array due to item
100 // construction).
101 for (size_t i = 0; i < rb.size(); ++i)
102 push_back(rb[i]);
103 return *this;
104 }
105
106 //! move-constructor: move buffer
107 RingBuffer(RingBuffer&& rb) noexcept
108 : max_size_(rb.max_size_),
109 alloc_(std::move(rb.alloc_)),
110 capacity_(rb.capacity_), mask_(rb.mask_),
111 data_(rb.data_),
112 begin_(rb.begin_), end_(rb.end_) {
113 // clear other buffer
114 rb.data_ = nullptr;
115 rb.begin_ = rb.end_ = 0;
116 rb.capacity_ = 0;
117 }
118
119 //! move-assignment operator: default
121 if (this == &rb) return *this;
122 // empty this buffer
123 clear();
124 alloc_.deallocate(data_, capacity_);
125 // move over variables
126 max_size_ = rb.max_size_;
127 alloc_ = std::move(rb.alloc_);
128 capacity_ = rb.capacity_, mask_ = rb.mask_;
129 data_ = rb.data_;
130 begin_ = rb.begin_, end_ = rb.end_;
131 // clear other buffer
132 rb.data_ = nullptr;
133 rb.begin_ = rb.end_ = 0;
134 rb.capacity_ = 0;
135 return *this;
136 }
137
139 clear();
140 alloc_.deallocate(data_, capacity_);
141 }
142
143 //! allocate buffer
144 void allocate(size_t max_size) {
145 assert(!data_);
148 mask_ = capacity_ - 1;
149 data_ = alloc_.allocate(capacity_);
150 }
151
152 //! deallocate buffer
153 void deallocate() {
154 if (data_) {
155 clear();
156 alloc_.deallocate(data_, capacity_);
157 data_ = nullptr;
158 }
159 }
160
161 //! \name Modifiers
162 //! \{
163
164 //! add element at the end
165 void push_back(const value_type& t) {
166 assert(size() + 1 <= max_size_);
167 alloc_traits::construct(alloc_, std::addressof(data_[end_]), t);
168 ++end_ &= mask_;
169 }
170
171 //! add element at the end
173 assert(size() + 1 <= max_size_);
174 alloc_traits::construct(
175 alloc_, std::addressof(data_[end_]), std::move(t));
176 ++end_ &= mask_;
177 }
178
179 //! emplace element at the end
180 template <typename... Args>
181 void emplace_back(Args&& ... args) {
182 assert(size() + 1 <= max_size_);
183 alloc_traits::construct(alloc_, std::addressof(data_[end_]),
184 std::forward<Args>(args) ...);
185 ++end_ &= mask_;
186 }
187
188 //! add element at the beginning
189 void push_front(const value_type& t) {
190 assert(size() + 1 <= max_size_);
191 --begin_ &= mask_;
192 alloc_traits::construct(alloc_, std::addressof(data_[begin_]), t);
193 }
194
195 //! add element at the beginning
197 assert(size() + 1 <= max_size_);
198 --begin_ &= mask_;
199 alloc_traits::construct(
200 alloc_, std::addressof(data_[begin_]), std::move(t));
201 }
202
203 //! emplace element at the beginning
204 template <typename... Args>
205 void emplace_front(Args&& ... args) {
206 assert(size() + 1 <= max_size_);
207 --begin_ &= mask_;
208 alloc_traits::construct(alloc_, std::addressof(data_[begin_]),
209 std::forward<Args>(args) ...);
210 }
211
212 //! remove element at the beginning
213 void pop_front() {
214 assert(!empty());
215 alloc_traits::destroy(alloc_, std::addressof(data_[begin_]));
216 ++begin_ &= mask_;
217 }
218
219 //! remove element at the end
220 void pop_back() {
221 assert(!empty());
222 alloc_traits::destroy(alloc_, std::addressof(data_[begin_]));
223 --end_ &= mask_;
224 }
225
226 //! reset buffer contents
227 void clear() {
228 while (begin_ != end_)
229 pop_front();
230 }
231
232 //! copy all element into the vector
233 void copy_to(std::vector<value_type>* out) const {
234 for (size_t i = 0; i < size(); ++i)
235 out->emplace_back(operator [] (i));
236 }
237
238 //! move all element from the RingBuffer into the vector
239 void move_to(std::vector<value_type>* out) {
240 while (!empty()) {
241 out->emplace_back(std::move(front()));
242 pop_front();
243 }
244 }
245
246 //! \}
247
248 //! \name Element access
249 //! \{
250
251 //! Returns a reference to the i-th element.
253 assert(i < size());
254 return data_[(begin_ + i) & mask_];
255 }
256 //! Returns a reference to the i-th element.
258 assert(i < size());
259 return data_[(begin_ + i) & mask_];
260 }
261
262 //! Returns a reference to the first element.
263 reference front() noexcept {
264 assert(!empty());
265 return data_[begin_];
266 }
267 //! Returns a reference to the first element.
268 const_reference front() const noexcept {
269 assert(!empty());
270 return data_[begin_];
271 }
272
273 //! Returns a reference to the last element.
274 reference back() noexcept {
275 assert(!empty());
276 return data_[(end_ - 1) & mask_];
277 }
278 //! Returns a reference to the last element.
279 const_reference back() const noexcept {
280 assert(!empty());
281 return data_[(end_ - 1) & mask_];
282 }
283
284 //! \}
285
286 //! \name Capacity
287 //! \{
288
289 //! return the number of items in the buffer
290 size_type size() const noexcept {
291 return (end_ - begin_) & mask_;
292 }
293
294 //! return the maximum number of items in the buffer.
295 size_t max_size() const noexcept {
296 return max_size_;
297 }
298
299 //! return actual capacity of the ring buffer.
300 size_t capacity() const noexcept {
301 return capacity_;
302 }
303
304 //! returns true if no items are in the buffer
305 bool empty() const noexcept {
306 return size() == 0;
307 }
308
309 //! \}
310
311 //! \name Serialization Methods for cereal
312 //! \{
313
314 template <class Archive>
315 void save(Archive& ar) const { // NOLINT
316 std::uint32_t ar_size = size();
317 ar(max_size_, ar_size);
318 for (size_t i = 0; i < ar_size; ++i) ar(operator [] (i));
319 }
320
321 template <class Archive>
322 void load(Archive& ar) { // NOLINT
323 ar(max_size_);
324
325 if (data_) {
326 clear();
327 alloc_.deallocate(data_, capacity_);
328 }
329
330 // setup buffer
332 mask_ = capacity_ - 1;
333 data_ = alloc_.allocate(capacity_);
334 begin_ = end_ = 0;
335
336 // load items
337 std::uint32_t ar_size;
338 ar(ar_size);
339
340 for (size_t i = 0; i < ar_size; ++i) {
341 push_back(Type());
342 ar(back());
343 }
344 }
345
346 //! \}
347
348protected:
349 //! target max_size of circular buffer prescribed by the user. Never equal
350 //! to the data_.size(), which is rounded up to a power of two.
351 size_t max_size_;
352
353 //! used allocator
355
356 //! capacity of data buffer. rounded up from max_size_ to next unequal power
357 //! of two.
358 size_t capacity_;
359
360 //! one-bits mask for calculating modulo of capacity using AND-mask.
361 size_t mask_;
362
363 //! the circular buffer of static size.
364 Type* data_;
365
366 //! iterator at current begin of ring buffer
368
369 //! iterator at current begin of ring buffer
371};
372
373//! \}
374
375} // namespace tlx
376
377#endif // !TLX_CONTAINER_RING_BUFFER_HEADER
378
379/******************************************************************************/
A ring (circular) buffer of static (non-growing) size.
Definition: ring_buffer.hpp:37
void pop_back()
remove element at the end
size_type size() const noexcept
return the number of items in the buffer
void push_front(value_type &&t)
add element at the beginning
Allocator allocator_type
Definition: ring_buffer.hpp:40
size_t capacity() const noexcept
return actual capacity of the ring buffer.
void load(Archive &ar)
void deallocate()
deallocate buffer
RingBuffer(RingBuffer &&rb) noexcept
move-constructor: move buffer
void allocate(size_t max_size)
allocate buffer
bool empty() const noexcept
returns true if no items are in the buffer
const Type * const_pointer
Definition: ring_buffer.hpp:47
void copy_to(std::vector< value_type > *out) const
copy all element into the vector
typename allocator_type::difference_type difference_type
Definition: ring_buffer.hpp:50
void pop_front()
remove element at the beginning
size_t max_size_
target max_size of circular buffer prescribed by the user.
size_type begin_
iterator at current begin of ring buffer
void push_back(const value_type &t)
add element at the end
size_type end_
iterator at current begin of ring buffer
void emplace_front(Args &&... args)
emplace element at the beginning
void push_front(const value_type &t)
add element at the beginning
size_t mask_
one-bits mask for calculating modulo of capacity using AND-mask.
void push_back(value_type &&t)
add element at the end
reference back() noexcept
Returns a reference to the last element.
Type * data_
the circular buffer of static size.
RingBuffer(size_t max_size, const Allocator &alloc=allocator_type())
Definition: ring_buffer.hpp:61
size_t capacity_
capacity of data buffer.
reference front() noexcept
Returns a reference to the first element.
size_t max_size() const noexcept
return the maximum number of items in the buffer.
reference operator[](size_type i) noexcept
Returns a reference to the i-th element.
RingBuffer(const RingBuffer &rb)
copy-constructor: create new ring buffer
Definition: ring_buffer.hpp:69
RingBuffer & operator=(const RingBuffer &rb)
copyable: create new ring buffer
Definition: ring_buffer.hpp:83
void emplace_back(Args &&... args)
emplace element at the end
void move_to(std::vector< value_type > *out)
move all element from the RingBuffer into the vector
void clear()
reset buffer contents
void save(Archive &ar) const
RingBuffer(const Allocator &alloc=allocator_type()) noexcept
Definition: ring_buffer.hpp:57
typename allocator_type::size_type size_type
Definition: ring_buffer.hpp:49
const Type & const_reference
Definition: ring_buffer.hpp:45
const_reference front() const noexcept
Returns a reference to the first element.
allocator_type alloc_
used allocator
std::allocator_traits< allocator_type > alloc_traits
Definition: ring_buffer.hpp:42
const_reference back() const noexcept
Returns a reference to the last element.
static int round_up_to_power_of_two(int i)
does what it says: round up to next power of two