WPILibC++ 2025.2.1
Loading...
Searching...
No Matches
circular_buffer.h
Go to the documentation of this file.
1// Copyright (c) FIRST and other WPILib contributors.
2// Open Source Software; you can modify and/or share it under the terms of
3// the WPILib BSD license file in the root directory of this project.
4
5#pragma once
6
7#include <cstddef>
8#include <iterator>
9#include <vector>
10
11namespace wpi {
12
13/**
14 * This is a simple circular buffer so we don't need to "bucket brigade" copy
15 * old values.
16 *
17 * @tparam T Buffer element type.
18 */
19template <class T>
21 public:
22 /**
23 * Constructs a circular buffer.
24 *
25 * @param size Maximum number of buffer elements.
26 */
27 constexpr explicit circular_buffer(size_t size) : m_data(size, T{}) {}
28
29 constexpr circular_buffer(const circular_buffer&) = default;
30 constexpr circular_buffer& operator=(const circular_buffer&) = default;
31 constexpr circular_buffer(circular_buffer&&) = default;
32 constexpr circular_buffer& operator=(circular_buffer&&) = default;
33
34 class iterator {
35 public:
36 using iterator_category = std::forward_iterator_tag;
37 using value_type = T;
38 using difference_type = std::ptrdiff_t;
39 using pointer = T*;
40 using reference = T&;
41
42 constexpr iterator(circular_buffer* buffer, size_t index)
43 : m_buffer{buffer}, m_index{index} {}
44
45 constexpr iterator& operator++() {
46 ++m_index;
47 return *this;
48 }
49 constexpr iterator operator++(int) {
50 iterator retval = *this;
51 ++(*this);
52 return retval;
53 }
54 constexpr bool operator==(const iterator&) const = default;
55 constexpr reference operator*() { return (*m_buffer)[m_index]; }
56
57 private:
58 circular_buffer* m_buffer;
59 size_t m_index;
60 };
61
63 public:
64 using iterator_category = std::forward_iterator_tag;
65 using value_type = T;
66 using difference_type = std::ptrdiff_t;
67 using pointer = T*;
68 using const_reference = const T&;
69
70 constexpr const_iterator(const circular_buffer* buffer, size_t index)
71 : m_buffer{buffer}, m_index{index} {}
72
74 ++m_index;
75 return *this;
76 }
77 constexpr const_iterator operator++(int) {
78 const_iterator retval = *this;
79 ++(*this);
80 return retval;
81 }
82 constexpr bool operator==(const const_iterator&) const = default;
83 constexpr const_reference operator*() const { return (*m_buffer)[m_index]; }
84
85 private:
86 const circular_buffer* m_buffer;
87 size_t m_index;
88 };
89
90 constexpr iterator begin() { return iterator(this, 0); }
91 constexpr iterator end() {
93 }
94
95 constexpr const_iterator begin() const { return const_iterator(this, 0); }
96 constexpr const_iterator end() const {
98 }
99
100 constexpr const_iterator cbegin() const { return const_iterator(this, 0); }
101 constexpr const_iterator cend() const {
103 }
104
105 /**
106 * Returns number of elements in buffer
107 */
108 constexpr size_t size() const { return m_length; }
109
110 /**
111 * Returns value at front of buffer
112 */
113 constexpr T& front() { return (*this)[0]; }
114
115 /**
116 * Returns value at front of buffer
117 */
118 constexpr const T& front() const { return (*this)[0]; }
119
120 /**
121 * Returns value at back of buffer
122 *
123 * If there are no elements in the buffer, calling this function results in
124 * undefined behavior.
125 */
126 constexpr T& back() {
127 return m_data[(m_front + m_length - 1) % m_data.size()];
128 }
129
130 /**
131 * Returns value at back of buffer
132 *
133 * If there are no elements in the buffer, calling this function results in
134 * undefined behavior.
135 */
136 constexpr const T& back() const {
137 return m_data[(m_front + m_length - 1) % m_data.size()];
138 }
139
140 /**
141 * Push a new value onto the front of the buffer.
142 *
143 * The value at the back is overwritten if the buffer is full.
144 */
145 constexpr void push_front(T value) {
146 if (m_data.size() == 0) {
147 return;
148 }
149
150 m_front = ModuloDec(m_front);
151
152 m_data[m_front] = value;
153
154 if (m_length < m_data.size()) {
155 m_length++;
156 }
157 }
158
159 /**
160 * Push a new value onto the back of the buffer.
161 *
162 * The value at the front is overwritten if the buffer is full.
163 */
164 constexpr void push_back(T value) {
165 if (m_data.size() == 0) {
166 return;
167 }
168
169 m_data[(m_front + m_length) % m_data.size()] = value;
170
171 if (m_length < m_data.size()) {
172 m_length++;
173 } else {
174 // Increment front if buffer is full to maintain size
175 m_front = ModuloInc(m_front);
176 }
177 }
178
179 /**
180 * Push a new value onto the front of the buffer that is constructed with the
181 * provided constructor arguments.
182 *
183 * The value at the back is overwritten if the buffer is full.
184 */
185 template <class... Args>
186 constexpr void emplace_front(Args&&... args) {
187 if (m_data.size() == 0) {
188 return;
189 }
190
191 m_front = ModuloDec(m_front);
192
193 m_data[m_front] = T{args...};
194
195 if (m_length < m_data.size()) {
196 m_length++;
197 }
198 }
199
200 /**
201 * Push a new value onto the back of the buffer that is constructed with the
202 * provided constructor arguments.
203 *
204 * The value at the front is overwritten if the buffer is full.
205 */
206 template <class... Args>
207 constexpr void emplace_back(Args&&... args) {
208 if (m_data.size() == 0) {
209 return;
210 }
211
212 m_data[(m_front + m_length) % m_data.size()] = T{args...};
213
214 if (m_length < m_data.size()) {
215 m_length++;
216 } else {
217 // Increment front if buffer is full to maintain size
218 m_front = ModuloInc(m_front);
219 }
220 }
221
222 /**
223 * Pop value at front of buffer.
224 *
225 * If there are no elements in the buffer, calling this function results in
226 * undefined behavior.
227 */
228 constexpr T pop_front() {
229 T& temp = m_data[m_front];
230 m_front = ModuloInc(m_front);
231 m_length--;
232 return temp;
233 }
234
235 /**
236 * Pop value at back of buffer.
237 *
238 * If there are no elements in the buffer, calling this function results in
239 * undefined behavior.
240 */
241 constexpr T pop_back() {
242 m_length--;
243 return m_data[(m_front + m_length) % m_data.size()];
244 }
245
246 /**
247 * Resizes internal buffer to given size.
248 */
249 constexpr void resize(size_t size) {
250 if (size > m_data.size()) {
251 // Find end of buffer
252 size_t insertLocation = (m_front + m_length) % m_data.size();
253
254 // If insertion location precedes front of buffer, push front index back
255 if (insertLocation <= m_front) {
256 m_front += size - m_data.size();
257 }
258
259 // Add elements to end of buffer
260 m_data.insert(m_data.begin() + insertLocation, size - m_data.size(), 0);
261 } else if (size < m_data.size()) {
262 /* 1) Shift element block start at "front" left as many blocks as were
263 * removed up to but not exceeding buffer[0]
264 * 2) Shrink buffer, which will remove even more elements automatically if
265 * necessary
266 */
267 size_t elemsToRemove = m_data.size() - size;
268 auto frontIter = m_data.begin() + m_front;
269 if (m_front < elemsToRemove) {
270 /* Remove elements from end of buffer before shifting start of element
271 * block. Doing so saves a few copies.
272 */
273 m_data.erase(frontIter + size, m_data.end());
274
275 // Shift start of element block to left
276 m_data.erase(m_data.begin(), frontIter);
277
278 // Update metadata
279 m_front = 0;
280 } else {
281 // Shift start of element block to left
282 m_data.erase(frontIter - elemsToRemove, frontIter);
283
284 // Update metadata
285 m_front -= elemsToRemove;
286 }
287
288 /* Length only changes during a shrink if all unused spaces have been
289 * removed. Length decreases as used spaces are removed to meet the
290 * required size.
291 */
292 if (m_length > size) {
293 m_length = size;
294 }
295 }
296 }
297
298 /**
299 * Empties internal buffer.
300 */
301 constexpr void reset() {
302 m_front = 0;
303 m_length = 0;
304 }
305
306 /**
307 * @return Element at index starting from front of buffer.
308 */
309 constexpr T& operator[](size_t index) {
310 return m_data[(m_front + index) % m_data.size()];
311 }
312
313 /**
314 * @return Element at index starting from front of buffer.
315 */
316 constexpr const T& operator[](size_t index) const {
317 return m_data[(m_front + index) % m_data.size()];
318 }
319
320 private:
321 std::vector<T> m_data;
322
323 // Index of element at front of buffer
324 size_t m_front = 0;
325
326 // Number of elements used in buffer
327 size_t m_length = 0;
328
329 /**
330 * Increment an index modulo the size of the buffer.
331 *
332 * @param index Index into the buffer.
333 * @return The incremented index.
334 */
335 constexpr size_t ModuloInc(size_t index) {
336 return (index + 1) % m_data.size();
337 }
338
339 /**
340 * Decrement an index modulo the size of the buffer.
341 *
342 * @param index Index into the buffer.
343 * @return The decremented index.
344 */
345 constexpr size_t ModuloDec(size_t index) {
346 if (index == 0) {
347 return m_data.size() - 1;
348 } else {
349 return index - 1;
350 }
351 }
352};
353
354} // namespace wpi
Definition circular_buffer.h:62
constexpr const_iterator & operator++()
Definition circular_buffer.h:73
constexpr const_iterator(const circular_buffer *buffer, size_t index)
Definition circular_buffer.h:70
std::ptrdiff_t difference_type
Definition circular_buffer.h:66
T value_type
Definition circular_buffer.h:65
std::forward_iterator_tag iterator_category
Definition circular_buffer.h:64
const T & const_reference
Definition circular_buffer.h:68
constexpr const_iterator operator++(int)
Definition circular_buffer.h:77
T * pointer
Definition circular_buffer.h:67
constexpr bool operator==(const const_iterator &) const =default
constexpr const_reference operator*() const
Definition circular_buffer.h:83
Definition circular_buffer.h:34
constexpr bool operator==(const iterator &) const =default
constexpr iterator operator++(int)
Definition circular_buffer.h:49
constexpr reference operator*()
Definition circular_buffer.h:55
std::ptrdiff_t difference_type
Definition circular_buffer.h:38
constexpr iterator & operator++()
Definition circular_buffer.h:45
T & reference
Definition circular_buffer.h:40
T * pointer
Definition circular_buffer.h:39
std::forward_iterator_tag iterator_category
Definition circular_buffer.h:36
constexpr iterator(circular_buffer *buffer, size_t index)
Definition circular_buffer.h:42
T value_type
Definition circular_buffer.h:37
This is a simple circular buffer so we don't need to "bucket brigade" copy old values.
Definition circular_buffer.h:20
constexpr T & operator[](size_t index)
Definition circular_buffer.h:309
constexpr const_iterator cend() const
Definition circular_buffer.h:101
constexpr const T & operator[](size_t index) const
Definition circular_buffer.h:316
constexpr T pop_front()
Pop value at front of buffer.
Definition circular_buffer.h:228
constexpr T & back()
Returns value at back of buffer.
Definition circular_buffer.h:126
constexpr const T & back() const
Returns value at back of buffer.
Definition circular_buffer.h:136
constexpr circular_buffer & operator=(const circular_buffer &)=default
constexpr void reset()
Empties internal buffer.
Definition circular_buffer.h:301
constexpr void emplace_back(Args &&... args)
Push a new value onto the back of the buffer that is constructed with the provided constructor argume...
Definition circular_buffer.h:207
constexpr const_iterator end() const
Definition circular_buffer.h:96
constexpr void emplace_front(Args &&... args)
Push a new value onto the front of the buffer that is constructed with the provided constructor argum...
Definition circular_buffer.h:186
constexpr const_iterator cbegin() const
Definition circular_buffer.h:100
constexpr T & front()
Returns value at front of buffer.
Definition circular_buffer.h:113
constexpr T pop_back()
Pop value at back of buffer.
Definition circular_buffer.h:241
constexpr circular_buffer(circular_buffer &&)=default
constexpr iterator end()
Definition circular_buffer.h:91
constexpr void push_front(T value)
Push a new value onto the front of the buffer.
Definition circular_buffer.h:145
constexpr iterator begin()
Definition circular_buffer.h:90
constexpr const_iterator begin() const
Definition circular_buffer.h:95
constexpr circular_buffer(size_t size)
Constructs a circular buffer.
Definition circular_buffer.h:27
constexpr void resize(size_t size)
Resizes internal buffer to given size.
Definition circular_buffer.h:249
constexpr circular_buffer & operator=(circular_buffer &&)=default
constexpr void push_back(T value)
Push a new value onto the back of the buffer.
Definition circular_buffer.h:164
constexpr size_t size() const
Returns number of elements in buffer.
Definition circular_buffer.h:108
constexpr const T & front() const
Returns value at front of buffer.
Definition circular_buffer.h:118
constexpr circular_buffer(const circular_buffer &)=default
Foonathan namespace.
Definition ntcore_cpp.h:26