Thrill  0.1
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 <[email protected]>
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 
22 namespace 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  */
35 template <typename Type, class Allocator = std::allocator<Type> >
37 {
38 public:
39  using value_type = Type;
40  using allocator_type = Allocator;
41 
42  using alloc_traits = std::allocator_traits<allocator_type>;
43 
44  using reference = typename allocator_type::reference;
45  using const_reference = typename allocator_type::const_reference;
46  using pointer = typename allocator_type::pointer;
47  using const_pointer = typename allocator_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),
64  capacity_(round_up_to_power_of_two(max_size + 1)),
65  mask_(capacity_ - 1),
67 
68  //! copy-constructor: create new ring buffer
70  : max_size_(rb.max_size_),
71  alloc_(rb.alloc_),
72  capacity_(rb.capacity_),
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_;
92  capacity_ = rb.capacity_;
93  data_ = alloc_.allocate(capacity_);
94  }
95  // copy over fields
96  max_size_ = rb.max_size_;
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_);
147  capacity_ = round_up_to_power_of_two(max_size + 1);
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
172  void push_back(value_type&& t) {
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
196  void push_front(value_type&& t) {
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  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  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 
348 protected:
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.
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 /******************************************************************************/
bool empty() const noexcept
returns true if no items are in the buffer
RingBuffer(const Allocator &alloc=allocator_type()) noexcept
Definition: ring_buffer.hpp:57
void push_back(const value_type &t)
add element at the end
A ring (circular) buffer of static (non-growing) size.
Definition: ring_buffer.hpp:36
size_t max_size() const noexcept
return the maximum number of items in the buffer.
Type
VFS object type.
Definition: file_io.hpp:52
void clear()
reset buffer contents
reference back() noexcept
Returns a reference to the last element.
size_t mask_
one-bits mask for calculating modulo of capacity using AND-mask.
allocator_type alloc_
used allocator
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
std::allocator< Input > allocator_type
Definition: ring_buffer.hpp:40
void emplace_back(Args &&... args)
emplace element at the end
typename allocator_type::size_type size_type
Definition: ring_buffer.hpp:49
void deallocate()
deallocate buffer
size_type size() const noexcept
return the number of items in the buffer
void copy_to(std::vector< value_type > *out) const
copy all element into the vector
typename allocator_type::const_reference const_reference
Definition: ring_buffer.hpp:45
void push_front(value_type &&t)
add element at the beginning
RingBuffer(RingBuffer &&rb) noexcept
move-constructor: move buffer
RingBuffer(size_t max_size, const Allocator &alloc=allocator_type())
Definition: ring_buffer.hpp:61
typename allocator_type::reference reference
Definition: ring_buffer.hpp:44
typename allocator_type::const_pointer const_pointer
Definition: ring_buffer.hpp:47
reference front() noexcept
Returns a reference to the first element.
void pop_front()
remove element at the beginning
size_t capacity() const noexcept
return actual capacity of the ring buffer.
size_type begin_
iterator at current begin of ring buffer
typename allocator_type::difference_type difference_type
Definition: ring_buffer.hpp:50
reference operator[](size_type i) noexcept
Returns a reference to the i-th element.
void allocate(size_t max_size)
allocate buffer
void load(Archive &ar)
Type * data_
the circular buffer of static size.
void push_back(value_type &&t)
add element at the end
void emplace_front(Args &&... args)
emplace element at the beginning
std::allocator_traits< allocator_type > alloc_traits
Definition: ring_buffer.hpp:42
void pop_back()
remove element at the end
typename allocator_type::pointer pointer
Definition: ring_buffer.hpp:46
static int round_up_to_power_of_two(int i)
does what it says: round up to next power of two
void save(Archive &ar) const
void push_front(const value_type &t)
add element at the beginning
size_type end_
iterator at current begin of ring buffer
const_reference front() const noexcept
Returns a reference to the first element.
void move_to(std::vector< value_type > *out)
move all element from the RingBuffer into the vector
const_reference back() const noexcept
Returns a reference to the last element.