diff options
author | px4dev <px4@purgatory.org> | 2013-09-09 17:36:07 +1000 |
---|---|---|
committer | Lorenz Meier <lm@inf.ethz.ch> | 2013-09-12 00:51:24 +0200 |
commit | 1828b57c581dda473d03c9c00cdbf354c7927f23 (patch) | |
tree | 84cd55d4dcdcb8c14f4542786e6b76123d36bd01 /src/drivers/device/ringbuffer.h | |
parent | 04f8e338b682d0f72f00ad12f22b5071a8f6bd18 (diff) | |
download | px4-firmware-1828b57c581dda473d03c9c00cdbf354c7927f23.tar.gz px4-firmware-1828b57c581dda473d03c9c00cdbf354c7927f23.tar.bz2 px4-firmware-1828b57c581dda473d03c9c00cdbf354c7927f23.zip |
ringbuffer: added force() and use lockless methods
this adds force() which can be used for drivers wanting consumers to
get the latest data when the buffer overflows
Diffstat (limited to 'src/drivers/device/ringbuffer.h')
-rw-r--r-- | src/drivers/device/ringbuffer.h | 136 |
1 files changed, 120 insertions, 16 deletions
diff --git a/src/drivers/device/ringbuffer.h b/src/drivers/device/ringbuffer.h index dc0c84052..c859be647 100644 --- a/src/drivers/device/ringbuffer.h +++ b/src/drivers/device/ringbuffer.h @@ -55,7 +55,7 @@ public: bool put(T &val); /** - * Put an item into the buffer. + * Put an item into the buffer if there is space. * * @param val Item to put * @return true if the item was put, false if the buffer is full @@ -63,6 +63,22 @@ public: bool put(const T &val); /** + * Force an item into the buffer, discarding an older item if there is not space. + * + * @param val Item to put + * @return true if an item was discarded to make space + */ + bool force(T &val); + + /** + * Force an item into the buffer, discarding an older item if there is not space. + * + * @param val Item to put + * @return true if an item was discarded to make space + */ + bool force(const T &val); + + /** * Get an item from the buffer. * * @param val Item that was gotten @@ -73,8 +89,8 @@ public: /** * Get an item from the buffer (scalars only). * - * @return The value that was fetched, or zero if the buffer was - * empty. + * @return The value that was fetched. If the buffer is empty, + * returns zero. */ T get(void); @@ -97,23 +113,23 @@ public: /* * Returns true if the buffer is empty. */ - bool empty() { return _tail == _head; } + bool empty(); /* * Returns true if the buffer is full. */ - bool full() { return _next(_head) == _tail; } + bool full(); /* * Returns the capacity of the buffer, or zero if the buffer could * not be allocated. */ - unsigned size() { return (_buf != nullptr) ? _size : 0; } + unsigned size(); /* * Empties the buffer. */ - void flush() { _head = _tail = _size; } + void flush(); private: T *const _buf; @@ -140,6 +156,38 @@ RingBuffer<T>::~RingBuffer() } template <typename T> +bool RingBuffer<T>::empty() +{ + return _tail == _head; +} + +template <typename T> +bool RingBuffer<T>::full() +{ + return _next(_head) == _tail; +} + +template <typename T> +unsigned RingBuffer<T>::size() +{ + return (_buf != nullptr) ? _size : 0; +} + +template <typename T> +void RingBuffer<T>::flush() +{ + T junk; + while (!empty()) + get(junk); +} + +template <typename T> +unsigned RingBuffer<T>::_next(unsigned index) +{ + return (0 == index) ? _size : (index - 1); +} + +template <typename T> bool RingBuffer<T>::put(T &val) { unsigned next = _next(_head); @@ -166,11 +214,54 @@ bool RingBuffer<T>::put(const T &val) } template <typename T> +bool RingBuffer<T>::force(T &val) +{ + bool overwrote = false; + + for (;;) { + if (put(val)) + break; + T junk; + get(junk); + overwrote = true; + } + return overwrote; +} + +template <typename T> +bool RingBuffer<T>::force(const T &val) +{ + bool overwrote = false; + + for (;;) { + if (put(val)) + break; + T junk; + get(junk); + overwrote = true; + } + return overwrote; +} + +template <typename T> bool RingBuffer<T>::get(T &val) { if (_tail != _head) { - val = _buf[_tail]; - _tail = _next(_tail); + unsigned candidate; + unsigned next; + do { + /* decide which element we think we're going to read */ + candidate = _tail; + + /* and what the corresponding next index will be */ + next = _next(candidate); + + /* go ahead and read from this index */ + val = _buf[candidate]; + + /* if the tail pointer didn't change, we got our item */ + } while (!__sync_bool_compare_and_swap(&_tail, candidate, next)); + return true; } else { return false; @@ -187,17 +278,30 @@ T RingBuffer<T>::get(void) template <typename T> unsigned RingBuffer<T>::space(void) { - return (_tail >= _head) ? (_size - (_tail - _head)) : (_head - _tail - 1); + unsigned tail, head; + + /* + * Make a copy of the head/tail pointers in a fashion that + * may err on the side of under-estimating the free space + * in the buffer in the case that the buffer is being updated + * asynchronously with our check. + * If the head pointer changes (reducing space) while copying, + * re-try the copy. + */ + do { + head = _head; + tail = _tail; + } while (head != _head); + + return (tail >= head) ? (_size - (tail - head)) : (head - tail - 1); } template <typename T> unsigned RingBuffer<T>::count(void) { + /* + * Note that due to the conservative nature of space(), this may + * over-estimate the number of items in the buffer. + */ return _size - space(); } - -template <typename T> -unsigned RingBuffer<T>::_next(unsigned index) -{ - return (0 == index) ? _size : (index - 1); -} |