Line data Source code
1 : /** \file circularBuffer.hpp
2 : * \author Jared R. Males
3 : * \brief A circular buffer class
4 : * \ingroup signal_processing_files
5 : *
6 : */
7 :
8 : //***********************************************************************//
9 : // Copyright 2020 Jared R. Males (jaredmales@gmail.com)
10 : //
11 : // This file is part of mxlib.
12 : //
13 : // mxlib is free software: you can redistribute it and/or modify
14 : // it under the terms of the GNU General Public License as published by
15 : // the Free Software Foundation, either version 3 of the License, or
16 : // (at your option) any later version.
17 : //
18 : // mxlib is distributed in the hope that it will be useful,
19 : // but WITHOUT ANY WARRANTY; without even the implied warranty of
20 : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
21 : // GNU General Public License for more details.
22 : //
23 : // You should have received a copy of the GNU General Public License
24 : // along with mxlib. If not, see <http://www.gnu.org/licenses/>.
25 : //***********************************************************************//
26 :
27 : #ifndef sigproc_circularBuffer
28 : #define sigproc_circularBuffer
29 :
30 : #include <atomic>
31 : #include <vector>
32 :
33 : namespace mx
34 : {
35 : namespace sigproc
36 : {
37 :
38 : /** \defgroup circular_buffer Circular Buffer
39 : * \brief A circular buffer class
40 : *
41 : * Three options for the circular buffer are provided, each inheriting the same underlying interface. The choices
42 : * vary the way in which the wrapping is handled at the beginning and end of the storage. These are:
43 : * - circularBufferMod: uses the mod operator, this is slowest in all situations and is provided for comparison
44 : * - circularBufferBranch: uses an if statement (branch) to test for location in memory. Slower in sequential access,
45 : * possibly slightly faster in random access.
46 : * - circularBufferIndex: uses a pre-populated index array, which adds some memory overhead. Fastest in sequential
47 : * access, possibly slightly slower in random access.
48 : *
49 : * Benchmarks are clear that circularBufferIndex is fastest for sequential acceess, e.g. one element after the other in
50 : * sequential order, by something like 30%. For random access circularBufferBranch is possibly slightly faster, but not
51 : * enough tests were performed to be conclusive.
52 : *
53 : * circularBufferMod is always much slower due to use of the `%` operator. Don't use this for real work.
54 : *
55 : * The memory overhead of circularBufferIndex is `3*maxEntries*sizeof(indexT)`, where `maxEntries` is the maximum length
56 : * of the buffer, and indexT is the type used for indexing and sizes. The factor of 3 enables negative offsets, i.e.
57 : * for traversal in reverse.
58 : *
59 : * \note circularBufferIndex will not properly wrap until it is full. Attempts to access wrapped entries prior
60 : * to inserting maxEntries entries will segfault.
61 : *
62 : * \todo perform circular buffer testing on an isolated core, with one test per executable
63 : * \todo implement a circular buffer with fixed power-of-two size to test `&` modulo
64 : *
65 : * \ingroup signal_processing
66 : */
67 :
68 : /// CRTP base class for all circular buffers, providing the underlying memory management and accessors.
69 : /** The CRTP derived classes implement a standard interface based on how they handle wrapping from the end
70 : * to the beginning of the buffer.
71 : *
72 : * \tparam _derivedT the child class type
73 : * \tparam _storedT the type stored in teh circular buffer
74 : * \tparam _indexT the index type, also used for sizes (must be signed)
75 : *
76 : * \ingroup circular_buffer
77 : */
78 : template <typename _derivedT, typename _storedT, typename _indexT>
79 : class circularBufferBase
80 : {
81 : public:
82 : typedef _derivedT derivedT; ///< The child class
83 :
84 : typedef _storedT storedT; ///< The type stored in the circular buffer
85 : typedef _indexT indexT; ///< The index type, also used for sizes
86 :
87 : static_assert( std::is_signed_v<_indexT> == true, "circularBuffer indexT must be signed" );
88 :
89 : protected:
90 : std::vector<storedT> m_buffer; ///< The circular buffer storage
91 :
92 : indexT m_maxEntries{ 0 }; ///< The maximum number of entries to allow in the buffer before wrapping
93 : indexT m_nextEntry{ 0 }; ///< Index into m_buffer of the next entry. This is the oldest entry in the buffer.
94 : indexT m_latest{ 0 }; ///< Index into m_buff of the latest entry. This is the newest entry in the buffer.
95 :
96 : uint64_t m_mono{ 0 }; /**< A monotonic counter, which is incremented for each new entry,
97 : and reset on call to maxEntries.*/
98 :
99 : public:
100 : /// Default c'tor
101 : circularBufferBase();
102 :
103 : /// Sizing constructor
104 : /** Sets the maximum size of the buffer. Note that this will not be the size until
105 : * a full set of entries have been added to the buffer.
106 : */
107 : explicit circularBufferBase( indexT maxEnt /**< [in] the maximum number of entries this buffer will hold*/ );
108 :
109 : /// Set the maximum size of the buffer.
110 : /** Note that this will not be the size until
111 : * a full set of entries have been added to the buffer.
112 : */
113 : void maxEntries( indexT maxEnt /**< [in] the maximum number of entries this buffer will hold*/ );
114 :
115 : /// Get the maximum size of the buffer.
116 : /** Note that this is not the current size of the buffer until
117 : * at least maxEntries have been added. Use size() to check current size.
118 : *
119 : * \returns the maximum size of the buffer, m_maxEntries
120 : */
121 : indexT maxEntries();
122 :
123 : /// Get the number of entries.
124 : /** Note that this is the current size. It will not
125 : * be the same as maxEntries() until at least maxEntries
126 : * have been added.
127 : */
128 : indexT size() const;
129 :
130 : /// Add the next entry to the circular buffer
131 : /** Adds the entry (will incur a deep copy) and updates
132 : * the wrapping system.
133 : */
134 : void nextEntry( const storedT &newEnt /**< [in] the new entry to add to the buffer*/ );
135 :
136 : /// Move to the next entry in the circular buffer
137 : /** If not yet at maxEntries entries, this emplaces a new default constructed entry.
138 : * Otherwise it increments counters so that the old latest entry is now the newest entry.
139 : */
140 : void nextEntry();
141 :
142 : /// Returns the index of the earliest entry
143 : /** This is particularly useful for accessing entries with the at() function
144 : * over an unchanging sequence if asynchronous updates are possible.
145 : */
146 : indexT earliest();
147 :
148 : /// Returns the index of the latest entry
149 : /**
150 : */
151 : indexT latest();
152 :
153 : uint64_t mono();
154 :
155 : /// Get the entry at a given index
156 : /** `idx=0` is the earliest entry in the buffer. `idx=1` is the one after that.
157 : * I.e., this counts forward from the oldest data
158 : *
159 : * \returns a reference to the indicated entry in the circular buffer.
160 : */
161 : storedT &operator[]( indexT idx /**< [in] the index of the entry to access*/ );
162 :
163 : const storedT &operator[]( indexT idx /**< [in] the index of the entry to access*/ ) const;
164 :
165 : /// Get the entry at a given index relative a fixed reference entry
166 : /** `idx=0` is the entry at refEntry. `idx=1` is the one after that.
167 : * I.e., this counts forward from the oldest data
168 : *
169 : * \returns a reference to the indicated entry in the circular buffer.
170 : */
171 : storedT &at( indexT refEntry, ///< [in] the entry to start counting from
172 : indexT idx ///< [in] the index of the entry to access
173 : );
174 :
175 : /// Get the entry at a given index relative a fixed start entry, const version
176 : /** `idx=0` is the entry at refEntry. `idx=1` is the one after that.
177 : * I.e., this counts forward from the oldest data
178 : *
179 : * \overload
180 : *
181 : * \returns a const reference to the indicated entry in the circular buffer.
182 : */
183 : const storedT &at( indexT refEntry, ///< [in] the entry to start counting from
184 : indexT idx ///< [in] the index of the entry to access
185 : ) const;
186 :
187 : private:
188 50 : derivedT &derived()
189 : {
190 50 : return *static_cast<derivedT *>( this );
191 : }
192 :
193 : const derivedT &derived() const
194 : {
195 : return *static_cast<const derivedT *>( this );
196 : }
197 : };
198 :
199 : template <class derivedT, typename storedT, typename indexT>
200 5 : circularBufferBase<derivedT, storedT, indexT>::circularBufferBase()
201 : {
202 5 : }
203 :
204 : template <class derivedT, typename storedT, typename indexT>
205 : circularBufferBase<derivedT, storedT, indexT>::circularBufferBase( indexT maxEnt )
206 : {
207 : maxEntries( maxEnt );
208 : }
209 :
210 : template <class derivedT, typename storedT, typename indexT>
211 5 : void circularBufferBase<derivedT, storedT, indexT>::maxEntries( indexT maxEnt )
212 : {
213 5 : m_buffer.clear();
214 5 : m_nextEntry = 0;
215 5 : m_latest = 0;
216 :
217 5 : m_maxEntries = maxEnt;
218 5 : m_buffer.reserve( m_maxEntries );
219 :
220 5 : derived().setMaxEntries( maxEnt );
221 :
222 5 : m_mono = 0;
223 5 : }
224 :
225 : template <class derivedT, typename storedT, typename indexT>
226 : indexT circularBufferBase<derivedT, storedT, indexT>::maxEntries()
227 : {
228 : return m_maxEntries;
229 : }
230 :
231 : template <class derivedT, typename storedT, typename indexT>
232 : indexT circularBufferBase<derivedT, storedT, indexT>::size() const
233 : {
234 : return m_buffer.size();
235 : }
236 :
237 : template <class derivedT, typename storedT, typename indexT>
238 28 : void circularBufferBase<derivedT, storedT, indexT>::nextEntry( const storedT &newEnt )
239 : {
240 28 : if( m_buffer.size() < m_maxEntries )
241 : {
242 24 : m_buffer.push_back( newEnt );
243 24 : m_latest = m_buffer.size() - 1;
244 24 : m_nextEntry = 0;
245 : }
246 : else
247 : {
248 4 : m_buffer[m_nextEntry] = newEnt;
249 4 : m_latest = m_nextEntry;
250 4 : ++m_nextEntry;
251 4 : if( m_nextEntry > m_buffer.size() - 1 )
252 : {
253 0 : m_nextEntry = 0;
254 : }
255 : }
256 :
257 28 : ++m_mono;
258 28 : }
259 :
260 : template <class derivedT, typename storedT, typename indexT>
261 : void circularBufferBase<derivedT, storedT, indexT>::nextEntry()
262 : {
263 : if( m_buffer.size() < m_maxEntries )
264 : {
265 : m_buffer.emplace_back();
266 : m_latest = m_buffer.size() - 1;
267 : m_nextEntry = 0;
268 : }
269 : else
270 : {
271 : m_latest = m_nextEntry;
272 : ++m_nextEntry;
273 : if( m_nextEntry > m_buffer.size() - 1 )
274 : {
275 : m_nextEntry = 0;
276 : }
277 : }
278 :
279 : ++m_mono;
280 : }
281 :
282 : template <class derivedT, typename storedT, typename indexT>
283 4 : indexT circularBufferBase<derivedT, storedT, indexT>::earliest()
284 : {
285 4 : return m_nextEntry;
286 : }
287 :
288 : template <class derivedT, typename storedT, typename indexT>
289 4 : indexT circularBufferBase<derivedT, storedT, indexT>::latest()
290 : {
291 4 : return m_latest;
292 : }
293 :
294 : template <class derivedT, typename storedT, typename indexT>
295 : uint64_t circularBufferBase<derivedT, storedT, indexT>::mono()
296 : {
297 : return m_mono;
298 : }
299 :
300 : template <class derivedT, typename storedT, typename indexT>
301 45 : storedT &circularBufferBase<derivedT, storedT, indexT>::operator[]( indexT idx )
302 : {
303 45 : return derived().at( m_nextEntry, idx );
304 : }
305 :
306 : template <class derivedT, typename storedT, typename indexT>
307 : const storedT &circularBufferBase<derivedT, storedT, indexT>::operator[]( indexT idx ) const
308 : {
309 : return derived().at( m_nextEntry, idx );
310 : }
311 :
312 : template <class derivedT, typename storedT, typename indexT>
313 : storedT &circularBufferBase<derivedT, storedT, indexT>::at( indexT refEntry, indexT idx )
314 : {
315 : return derived().at( refEntry, idx );
316 : }
317 :
318 : template <class derivedT, typename storedT, typename indexT>
319 : const storedT &circularBufferBase<derivedT, storedT, indexT>::at( indexT refEntry, indexT idx ) const
320 : {
321 : return derived().at( refEntry, idx );
322 : }
323 :
324 : /// Circular buffer which wraps with an if statement (branching) [faster than mod, less memory than index]
325 : /**
326 : * \ingroup circular_buffer
327 : */
328 : template <typename _storedT, typename _indexT>
329 : class circularBufferBranch : public circularBufferBase<circularBufferBranch<_storedT, _indexT>, _storedT, _indexT>
330 : {
331 : public:
332 : typedef _storedT storedT; ///< The maximum number of entries to allow in the buffer before wrapping
333 : typedef _indexT indexT; ///< The index type, also used for sizes
334 :
335 : public:
336 : /// Default c'tor
337 3 : circularBufferBranch() : circularBufferBase<circularBufferBranch, storedT, indexT>()
338 : {
339 3 : }
340 :
341 : /// Sizing constructor
342 : /** Sets the maximum size of the buffer. Note that this will not be the size until
343 : * a full set of entries have been added to the buffer.
344 : */
345 : explicit circularBufferBranch( indexT maxEnt /**< [in] the maximum number of entries this buffer will hold*/ )
346 : : circularBufferBase<circularBufferBranch, storedT, indexT>( maxEnt )
347 : {
348 : }
349 :
350 : /// Interface implementation for maxEntries.
351 : /** Resets the wrap entry to 0.
352 : */
353 3 : void setMaxEntries( indexT maxEnt /**< [in] the maximum number of entries this buffer will hold*/ )
354 : {
355 3 : }
356 :
357 : /// Interface implementation for entry access
358 : /** Accesses the idx-th element relative to refEntry, using a branch (if-statement) to wrap
359 : *
360 : * \returns a reference to the idx-th element
361 : */
362 31 : storedT &at( indexT refEntry, ///< [in] the entry to start counting from
363 : indexT idx ///< [in] the index of the entry to access
364 : )
365 : {
366 31 : indexT _idx = refEntry + idx;
367 31 : if( _idx < 0 )
368 : {
369 10 : return this->m_buffer[_idx + this->m_buffer.size()];
370 : }
371 21 : else if( _idx > this->m_buffer.size() - 1 )
372 : {
373 3 : return this->m_buffer[_idx - this->m_buffer.size()];
374 : }
375 : else
376 : {
377 18 : return this->m_buffer[_idx];
378 : }
379 : }
380 :
381 : /// Interface implementation for entry access, const version
382 : /** Accesses the idx-th element relative to refEntry, using a branch (if-statement) to wrap
383 : *
384 : * \overload
385 : *
386 : * \returns a const reference to the idx-th element
387 : */
388 : const storedT &at( indexT refEntry, ///< [in] the entry to start counting from
389 : indexT idx ///< [in] the index of the entry to access
390 : ) const
391 : {
392 : indexT _idx = refEntry + idx;
393 : if( _idx < 0 )
394 : {
395 : return this->m_buffer[_idx + this->m_buffer.size()];
396 : }
397 : else if( _idx > this->m_buffer.size() - 1 )
398 : {
399 : return this->m_buffer[_idx - this->m_buffer.size()];
400 : }
401 : else
402 : {
403 : return this->m_buffer[_idx];
404 : }
405 : }
406 : };
407 :
408 : /// Circular buffer which wraps with the mod operator [very slow]
409 : /**
410 : * \ingroup circular_buffer
411 : */
412 : template <typename _storedT, typename _indexT>
413 : class circularBufferMod : public circularBufferBase<circularBufferMod<_storedT, _indexT>, _storedT, _indexT>
414 : {
415 : public:
416 : typedef _storedT storedT; ///< The maximum number of entries to allow in the buffer before wrapping
417 : typedef _indexT indexT; ///< The index type, also used for sizes
418 :
419 : /// Default c'tor
420 : circularBufferMod() : circularBufferBase<circularBufferMod, storedT, indexT>()
421 : {
422 : }
423 :
424 : /// Sizing constructor
425 : /** Sets the maximum size of the buffer. Note that this will not be the size until
426 : * a full set of entries have been added to the buffer.
427 : */
428 : explicit circularBufferMod( indexT maxEnt /**< [in] the maximum number of entries this buffer will hold*/ )
429 : : circularBufferBase<circularBufferMod, storedT, indexT>( maxEnt )
430 : {
431 : }
432 :
433 : /// Interface implementation for maxEntries.
434 : /** A no-op
435 : */
436 : void setMaxEntries( indexT maxEnt /**< [in] the maximum number of entries this buffer will hold*/ )
437 : {
438 : }
439 :
440 : /// Interface implementation for entry access
441 : /** Accesses the idx-th element relative to refEntry, using the mod operator to wrap
442 : *
443 : * \returns a reference to the idx-th element
444 : */
445 : storedT &at( indexT refEntry, ///< [in] the entry to start counting from
446 : indexT idx ///< [in] the index of the entry to access
447 : )
448 : {
449 : return this->m_buffer[( refEntry + idx ) % this->m_buffer.size()];
450 : }
451 :
452 : /// Interface implementation for entry access, const version
453 : /** Accesses the idx-th element relative to refEntry, using the mod operator to wrap
454 : *
455 : * \overload
456 : *
457 : * \returns a const reference to the idx-th element
458 : */
459 : const storedT &at( indexT refEntry, ///< [in] the entry to start counting from
460 : indexT idx ///< [in] the index of the entry to access
461 : ) const
462 : {
463 : return this->m_buffer[( refEntry + idx ) % this->m_buffer.size()];
464 : }
465 : };
466 :
467 : /// Circular buffer which wraps with a pre-populated indices array [generally fastest]
468 : /**
469 : * \ingroup circular_buffer
470 : */
471 : template <typename _storedT, typename _indexT, bool fixed_size = false>
472 : class circularBufferIndex;
473 :
474 : template <typename _storedT, typename _indexT>
475 : class circularBufferIndex<_storedT, _indexT, false>
476 : : public circularBufferBase<circularBufferIndex<_storedT, _indexT, false>, _storedT, _indexT>
477 : {
478 : public:
479 : typedef _storedT storedT; ///< The maximum number of entries to allow in the buffer before wrapping
480 : typedef _indexT indexT; ///< The index type, also used for sizes
481 :
482 : protected:
483 : std::vector<size_t> m_indices; ///< Vector of indices for fast indexing into parent's m_buffer
484 :
485 : public:
486 : /// Default c'tor
487 2 : circularBufferIndex() : circularBufferBase<circularBufferIndex, storedT, indexT>()
488 : {
489 2 : }
490 :
491 : /// Sizing constructor
492 : /** Sets the maximum size of the buffer. Note that this will not be the size until
493 : * a full set of entries have been added to the buffer.
494 : */
495 : explicit circularBufferIndex( indexT maxEnt /**< [in] the maximum number of entries this buffer will hold*/ )
496 : : circularBufferBase<circularBufferIndex, storedT, indexT>( maxEnt )
497 : {
498 : }
499 :
500 : /// Interface implementation for maxEntries.
501 : /** Resizes and populates the indices array.
502 : */
503 2 : void setMaxEntries( indexT maxEnt /**< [in] the maximum number of entries this buffer will hold*/ )
504 : {
505 2 : m_indices.resize( 3 * this->m_maxEntries );
506 12 : for( size_t i = 0; i < this->m_maxEntries; ++i )
507 : {
508 10 : m_indices[i] = i;
509 10 : m_indices[this->m_maxEntries + i] = i;
510 10 : m_indices[2 * this->m_maxEntries + i] = i;
511 : }
512 2 : }
513 :
514 : /// Interface implementation for entry access
515 : /** Accesses the idx-th element relative to refEntry, using the pre-populated indices to wrap
516 : *
517 : * \returns a reference to the idx-th element
518 : */
519 22 : storedT &at( indexT refEntry, ///< [in] the entry to start counting from
520 : indexT idx ///< [in] the index of the entry to access
521 : )
522 : {
523 22 : return this->m_buffer[m_indices[this->m_maxEntries + refEntry + idx]];
524 : }
525 :
526 : /// Interface implementation for entry access, const version
527 : /** Accesses the idx-th element relative to refEntry, using the pre-populated indices to wrap
528 : *
529 : * \overload
530 : *
531 : * \returns a const reference to the idx-th element
532 : */
533 : const storedT &at( indexT refEntry, ///< [in] the entry to start counting from
534 : indexT idx ///< [in] the index of the entry to access
535 : ) const
536 : {
537 : return this->m_buffer[this->m_maxEntries + m_indices[refEntry + idx]];
538 : }
539 : };
540 :
541 : /// Fixed-size circular buffer specialization for single-producer/single-consumer use.
542 : /**
543 : * \ingroup circular_buffer
544 : */
545 : template <typename _storedT, typename _indexT>
546 : class circularBufferIndex<_storedT, _indexT, true>
547 : {
548 : public:
549 : typedef _storedT storedT; ///< The maximum number of entries to allow in the buffer before wrapping
550 : typedef _indexT indexT; ///< The index type, also used for sizes
551 :
552 : static_assert( std::is_signed_v<_indexT> == true, "circularBuffer indexT must be signed" );
553 : static_assert( std::is_trivially_copyable_v<_storedT> == true,
554 : "fixed_size circularBufferIndex requires trivially copyable storedT" );
555 :
556 : /// Snapshot of the readable state of the buffer.
557 : struct snapshotT
558 : {
559 : indexT earliest{ 0 }; ///< Earliest readable slot in the current snapshot.
560 : indexT latest{ 0 }; ///< Latest published slot in the current snapshot.
561 : indexT validEntries{ 0 }; ///< Number of currently valid entries.
562 : indexT maxEntries{ 0 }; ///< Fixed capacity.
563 : uint64_t mono{ 0 }; ///< Publication generation for retry validation.
564 : bool full{ false }; ///< Whether the buffer has reached fixed capacity.
565 : };
566 :
567 : protected:
568 : std::vector<storedT> m_buffer; ///< The circular buffer storage.
569 : std::vector<size_t> m_indices; ///< Vector of indices for fast indexing into m_buffer.
570 :
571 : std::atomic<indexT> m_nextEntry{ 0 }; ///< The slot that will be written next by the producer.
572 : std::atomic<indexT> m_latest{ 0 }; ///< The latest slot published by the producer.
573 : std::atomic<indexT> m_validEntries{ 0 }; ///< The number of valid published entries.
574 : std::atomic<uint64_t> m_mono{ 0 }; ///< A monotonic publication counter.
575 :
576 : indexT m_maxEntries{ 0 }; ///< Fixed capacity of the buffer.
577 :
578 : public:
579 : /// Default c'tor.
580 : circularBufferIndex() = default;
581 :
582 : /// Sizing constructor.
583 : explicit circularBufferIndex( indexT maxEnt /**< [in] the maximum number of entries this buffer will hold*/ )
584 : {
585 : maxEntries( maxEnt );
586 : }
587 :
588 : /// Set the maximum size of the buffer.
589 : void maxEntries( indexT maxEnt /**< [in] the maximum number of entries this buffer will hold*/ )
590 : {
591 : m_buffer.clear();
592 : m_indices.clear();
593 :
594 : m_maxEntries = maxEnt;
595 :
596 : if( m_maxEntries > 0 )
597 : {
598 : m_buffer.resize( m_maxEntries );
599 : m_indices.resize( 3 * m_maxEntries );
600 :
601 : for( size_t i = 0; i < static_cast<size_t>( m_maxEntries ); ++i )
602 : {
603 : m_indices[i] = i;
604 : m_indices[m_maxEntries + i] = i;
605 : m_indices[2 * m_maxEntries + i] = i;
606 : }
607 : }
608 :
609 : m_nextEntry.store( 0, std::memory_order_release );
610 : m_latest.store( 0, std::memory_order_release );
611 : m_validEntries.store( 0, std::memory_order_release );
612 : m_mono.store( 0, std::memory_order_release );
613 : }
614 :
615 : /// Get the fixed capacity of the buffer.
616 : indexT maxEntries()
617 : {
618 : return m_maxEntries;
619 : }
620 :
621 : /// Get the number of valid entries.
622 : indexT size() const
623 : {
624 : return m_validEntries.load( std::memory_order_acquire );
625 : }
626 :
627 : /// Add the next entry to the circular buffer.
628 : void nextEntry( const storedT &newEnt /**< [in] the new entry to add to the buffer*/ )
629 : {
630 : if( m_maxEntries <= 0 )
631 : {
632 : return;
633 : }
634 :
635 : indexT next = m_nextEntry.load( std::memory_order_relaxed );
636 :
637 : m_buffer[next] = newEnt;
638 :
639 : indexT latest = next;
640 : ++next;
641 : if( next >= m_maxEntries )
642 : {
643 : next = 0;
644 : }
645 :
646 : indexT validEntries = m_validEntries.load( std::memory_order_relaxed );
647 : if( validEntries < m_maxEntries )
648 : {
649 : ++validEntries;
650 : }
651 :
652 : m_latest.store( latest, std::memory_order_relaxed );
653 : m_validEntries.store( validEntries, std::memory_order_relaxed );
654 : m_nextEntry.store( next, std::memory_order_relaxed );
655 : m_mono.fetch_add( 1, std::memory_order_release );
656 : }
657 :
658 : /// Move to the next entry using a default constructed value.
659 : void nextEntry()
660 : {
661 : nextEntry( storedT{} );
662 : }
663 :
664 : /// Returns the index of the earliest entry.
665 : indexT earliest() const
666 : {
667 : snapshotT sn = snapshot();
668 : return sn.earliest;
669 : }
670 :
671 : /// Returns the index of the latest entry.
672 : indexT latest() const
673 : {
674 : return m_latest.load( std::memory_order_acquire );
675 : }
676 :
677 : /// Returns the publication counter.
678 : uint64_t mono() const
679 : {
680 : return m_mono.load( std::memory_order_acquire );
681 : }
682 :
683 : /// Get the entry at a given index.
684 : storedT operator[]( indexT idx /**< [in] the index of the entry to access*/ ) const
685 : {
686 : snapshotT sn = snapshot();
687 :
688 : if( sn.validEntries <= 0 )
689 : {
690 : return storedT{};
691 : }
692 :
693 : return at( sn.earliest, idx );
694 : }
695 :
696 : /// Get the entry at a given index relative a fixed reference entry.
697 : storedT at( indexT refEntry, ///< [in] the entry to start counting from
698 : indexT idx ///< [in] the index of the entry to access
699 : ) const
700 : {
701 : return m_buffer[physicalIndex( refEntry, idx )];
702 : }
703 :
704 : /// Return a snapshot of the current readable region.
705 : snapshotT snapshot() const
706 : {
707 : snapshotT sn;
708 :
709 : sn.mono = m_mono.load( std::memory_order_acquire );
710 : sn.latest = m_latest.load( std::memory_order_relaxed );
711 : sn.validEntries = m_validEntries.load( std::memory_order_relaxed );
712 : sn.maxEntries = m_maxEntries;
713 : sn.full = ( sn.validEntries == sn.maxEntries && sn.maxEntries > 0 );
714 :
715 : if( sn.full )
716 : {
717 : sn.earliest = m_nextEntry.load( std::memory_order_relaxed );
718 : }
719 : else
720 : {
721 : sn.earliest = 0;
722 : }
723 :
724 : return sn;
725 : }
726 :
727 : /// Determine whether a logical window is readable from the provided snapshot.
728 : bool windowReadable( const snapshotT &sn, ///< [in] the snapshot to validate against
729 : indexT refEntry, ///< [in] the entry to start counting from
730 : indexT count ///< [in] the number of entries requested
731 : ) const
732 : {
733 : if( count <= 0 || refEntry < 0 || count > sn.validEntries )
734 : {
735 : return false;
736 : }
737 :
738 : if( !sn.full )
739 : {
740 : return refEntry + count <= sn.validEntries;
741 : }
742 :
743 : for( indexT n = 0; n < count; ++n )
744 : {
745 : if( physicalIndex( refEntry, n ) == sn.earliest )
746 : {
747 : return false;
748 : }
749 : }
750 :
751 : return true;
752 : }
753 :
754 : /// Copy a logical sequence into caller-owned storage, retrying if the producer advances.
755 : bool loadSequence( indexT refEntry, ///< [in] the entry to start counting from
756 : indexT count, ///< [in] the number of entries requested
757 : storedT *dest, ///< [out] destination storage of size count
758 : snapshotT &sn, ///< [out] the validated snapshot used for the copy
759 : int maxRetries = 3 /**< [in] the maximum number of retries*/
760 : ) const
761 : {
762 : if( dest == nullptr )
763 : {
764 : return false;
765 : }
766 :
767 : for( int retry = 0; retry < maxRetries; ++retry )
768 : {
769 : sn = snapshot();
770 :
771 : if( !windowReadable( sn, refEntry, count ) )
772 : {
773 : return false;
774 : }
775 :
776 : for( indexT n = 0; n < count; ++n )
777 : {
778 : dest[n] = m_buffer[physicalIndex( refEntry, n )];
779 : }
780 :
781 : if( m_mono.load( std::memory_order_acquire ) == sn.mono )
782 : {
783 : return true;
784 : }
785 : }
786 :
787 : return false;
788 : }
789 :
790 : /// Copy a logical sequence from a caller-supplied snapshot, validating that the producer has not advanced.
791 : bool loadSequence( const snapshotT &sn, ///< [in] the snapshot to validate against
792 : indexT refEntry, ///< [in] the entry to start counting from
793 : indexT count, ///< [in] the number of entries requested
794 : storedT *dest ///< [out] destination storage of size count
795 : ) const
796 : {
797 : if( dest == nullptr || !windowReadable( sn, refEntry, count ) )
798 : {
799 : return false;
800 : }
801 :
802 : for( indexT n = 0; n < count; ++n )
803 : {
804 : dest[n] = m_buffer[physicalIndex( refEntry, n )];
805 : }
806 :
807 : return m_mono.load( std::memory_order_acquire ) == sn.mono;
808 : }
809 :
810 : /// Copy the latest logical sequence into caller-owned storage, retrying if the producer advances.
811 : bool loadLatestSequence( indexT count, ///< [in] the number of entries requested
812 : storedT *dest, ///< [out] destination storage of size count
813 : snapshotT &sn, ///< [out] the validated snapshot used for the copy
814 : int maxRetries = 3 /**< [in] the maximum number of retries*/
815 : ) const
816 : {
817 : for( int retry = 0; retry < maxRetries; ++retry )
818 : {
819 : sn = snapshot();
820 :
821 : if( count <= 0 || count > sn.validEntries )
822 : {
823 : return false;
824 : }
825 :
826 : indexT refEntry;
827 : if( sn.latest >= count - 1 )
828 : {
829 : refEntry = sn.latest - ( count - 1 );
830 : }
831 : else
832 : {
833 : refEntry = sn.maxEntries + sn.latest - ( count - 1 );
834 : }
835 :
836 : if( !windowReadable( sn, refEntry, count ) )
837 : {
838 : return false;
839 : }
840 :
841 : for( indexT n = 0; n < count; ++n )
842 : {
843 : dest[n] = m_buffer[physicalIndex( refEntry, n )];
844 : }
845 :
846 : if( m_mono.load( std::memory_order_acquire ) == sn.mono )
847 : {
848 : return true;
849 : }
850 : }
851 :
852 : return false;
853 : }
854 :
855 : protected:
856 : /// Convert a logical index into a physical slot index.
857 : indexT physicalIndex( indexT refEntry, ///< [in] the entry to start counting from
858 : indexT idx ///< [in] the index of the entry to access
859 : ) const
860 : {
861 : return static_cast<indexT>( m_indices[m_maxEntries + refEntry + idx] );
862 : }
863 : };
864 :
865 : } // namespace sigproc
866 : } // namespace mx
867 :
868 : #endif // sigproc_circularBuffer
|
