FYI , EASTL's ring_buffer...
186 views
Skip to first unread message
Paul Pedriana
Jul 2, 2015, 8:36:42 PM7/2/15
to unofficial-r...@googlegroups.com
I saw some discussion about ring buffer proposals and thought it might be useful to show what EASTL's ring_buffer looks like.
template <typename T, typename Pointer, typename Reference, typename Container>
struct ring_buffer_iterator
{
public:
typedef ring_buffer_iterator<T, Pointer, Reference, Container> this_type;
typedef T value_type;
typedef Pointer pointer;
typedef Reference reference;
typedef typename Container::size_type size_type;
typedef typename Container::difference_type difference_type;
typedef typename Container::iterator container_iterator;
typedef typename Container::const_iterator container_const_iterator;
typedef ring_buffer_iterator<T, T*, T&, Container> iterator;
typedef ring_buffer_iterator<T, const T*, const T&, Container> const_iterator;
typedef eastl::random_access_iterator_tag iterator_category;
public:
Container* mpContainer;
container_iterator mContainerIterator;
public:
ring_buffer_iterator();
ring_buffer_iterator(Container* pContainer, const container_iterator& containerIterator);
ring_buffer_iterator(const iterator& x);
ring_buffer_iterator& operator=(const iterator& x);
reference operator*() const;
pointer operator->() const;
this_type& operator++();
this_type operator++(int);
this_type& operator--();
this_type operator--(int);
this_type& operator+=(difference_type n);
this_type& operator-=(difference_type n);
this_type operator+(difference_type n) const;
this_type operator-(difference_type n) const;
protected:
void increment(difference_type n, eastl::input_iterator_tag);
void increment(difference_type n, eastl::random_access_iterator_tag);
}; // struct ring_buffer_iterator
/// ring_buffer
///
/// Implements a ring buffer via a given container type, which would
/// typically be a vector or array, though any container which supports
/// bidirectional iteration would work.
///
/// A ring buffer is a FIFO (first-in, first-out) container which acts
/// much like a queue. The difference is that a ring buffer is implemented
/// via chasing pointers around a container and moving the read and write
/// positions forward (and possibly wrapping around) as the container is
/// read and written via pop_front and push_back.
///
/// The benefit of a ring buffer is that memory allocations don't occur
/// and new elements are neither added nor removed from the container.
/// Elements in the container are simply assigned values in circles around
/// the container.
///
/// ring_buffer is different from other containers -- including adapter
/// containers -- in how iteration is done. Iteration of a ring buffer
/// starts at the current begin position, proceeds to the end of the underlying
/// container, and continues at the begin of the underlying container until
/// the ring buffer's current end position. Thus a ring_buffer does
/// indeed have a begin and an end, though the values of begin and end
/// chase each other around the container. An empty ring_buffer is one
/// in which end == begin, and a full ring_buffer is one in which
/// end + 1 == begin.
///
/// Example of a ring buffer layout, where + indicates queued items:
/// ++++++++++--------------------------------+++++++++
/// ^ ^
/// end begin
///
/// Empty ring buffer:
/// ---------------------------------------------------
/// ^
/// begin / end
///
/// Full ring buffer. Note that one item is necessarily unused; it is
/// analogous to a '\0' at the end of a C string:
/// +++++++++++++++++++++++++++++++++++++++++-+++++++++
/// ^^
/// end begin
///
/// A push_back operation on a ring buffer assigns the new value to end.
/// If there is no more space in the buffer, this will result in begin
/// being overwritten and the begin position being moved foward one position.
/// The user can use the full() function to detect this condition.
/// Note that elements in a ring buffer are not created or destroyed as
/// their are added and removed; they are merely assigned. Only on
/// container construction and destruction are any elements created and
/// destroyed.
///
/// The ring buffer can be used in either direction. By this we mean that
/// you can use push_back to add items and pop_front to remove them; or you can
/// use push_front to add items and pop_back to remove them. You aren't
/// limited to these operations; you can push or pop from either side
/// arbitrarily and you can insert or erase anywhere in the container.
///
/// The ring buffer requires the user to specify a Container type, which
/// by default is vector. However, any container with bidirectional iterators
/// will work, such as list, deque, string or any of the fixed_* versions
/// of these containers, such as fixed_string. Since ring buffer works via copying
/// elements instead of allocating and freeing nodes, inserting in the middle
/// of a ring buffer based on list (instead of vector) is no more efficient.
///
/// To use the ring buffer, its container must be resized to the desired
/// ring buffer size. Changing the size of a ring buffer may cause ring
/// buffer iterators to invalidate.
///
/// An alternative to using a ring buffer is to use a list with a user-created
/// node pool and custom allocator. There are various tradeoffs that result from this.
///
/// Example usage:
/// ring_buffer< int, list<int> > rb(100);
/// rb.push_back(1);
///
/// Example usage:
/// // Example of creating an on-screen debug log that shows 16
/// // strings at a time and scrolls older strings away.
///
/// // Create ring buffer of 16 strings.
/// ring_buffer< string, vector<string> > debugLogText(16);
///
/// // Reserve 128 chars for each line. This can make it so that no
/// // runtime memory allocations occur.
/// for(vector<string>::iterator it = debugLogText.get_container().begin(),
/// itEnd = debugLogText.get_container().end(); it != itEnd; ++it)
/// {
/// (*it).reserve(128);
/// }
///
/// // Add a new string, using push_front() and front() instead of
/// // push_front(str) in order to avoid creating a temporary str.
/// debugLogText.push_front();
/// debugLogText.front() = "Player fired weapon";
///
template <typename T, typename Container = eastl::vector<T>, typename Allocator = typename Container::allocator_type>
class ring_buffer
{
public:
typedef ring_buffer<T, Container, Allocator> this_type;
typedef Container container_type;
typedef Allocator allocator_type;
typedef typename Container::value_type value_type;
typedef typename Container::reference reference;
typedef typename Container::const_reference const_reference;
typedef typename Container::size_type size_type;
typedef typename Container::difference_type difference_type;
typedef typename Container::iterator container_iterator;
typedef typename Container::const_iterator container_const_iterator;
typedef ring_buffer_iterator<T, T*, T&, Container> iterator;
typedef ring_buffer_iterator<T, const T*, const T&, Container> const_iterator;
typedef eastl::reverse_iterator<iterator> reverse_iterator;
typedef eastl::reverse_iterator<const_iterator> const_reverse_iterator;
public: // We declare public so that global comparison operators can be implemented without adding an inline level and without tripping up GCC 2.x friend declaration failures. GCC (through at least v4.0) is poor at inlining and performance wins over correctness.
Container c; // We follow the naming convention established for stack, queue, priority_queue and name this 'c'. This variable must always have a size of at least 1, as even an empty ring_buffer has an unused terminating element.
protected:
container_iterator mBegin; // We keep track of where our begin and end are by using Container iterators.
container_iterator mEnd;
size_type mSize;
public:
// There currently isn't a ring_buffer constructor that specifies and initial size, unlike other containers.
explicit ring_buffer(size_type cap = 0); // Construct with an initial capacity (but size of 0).
explicit ring_buffer(size_type cap, const allocator_type& allocator);
explicit ring_buffer(const Container& x);
explicit ring_buffer(const allocator_type& allocator);
ring_buffer(const this_type& x);
#if EASTL_MOVE_SEMANTICS_ENABLED
ring_buffer(this_type&& x);
ring_buffer(this_type&& x, const allocator_type& allocator);
#endif
ring_buffer(std::initializer_list<value_type> ilist, const allocator_type& allocator = allocator_type()); // This function sets the capacity to be equal to the size of the initializer list.
// No destructor necessary. Default will do.
this_type& operator=(const this_type& x);
this_type& operator=(std::initializer_list<value_type> ilist);
#if EASTL_MOVE_SEMANTICS_ENABLED
this_type& operator=(this_type&& x);
#endif
template <typename InputIterator>
void assign(InputIterator first, InputIterator last);
void swap(this_type& x);
iterator begin() EA_NOEXCEPT;
const_iterator begin() const EA_NOEXCEPT;
const_iterator cbegin() const EA_NOEXCEPT;
iterator end() EA_NOEXCEPT;
const_iterator end() const EA_NOEXCEPT;
const_iterator cend() const EA_NOEXCEPT;
reverse_iterator rbegin() EA_NOEXCEPT;
const_reverse_iterator rbegin() const EA_NOEXCEPT;
const_reverse_iterator crbegin() const EA_NOEXCEPT;
reverse_iterator rend() EA_NOEXCEPT;
const_reverse_iterator rend() const EA_NOEXCEPT;
const_reverse_iterator crend() const EA_NOEXCEPT;
bool empty() const EA_NOEXCEPT;
bool full() const EA_NOEXCEPT;
size_type size() const EA_NOEXCEPT;
void resize(size_type n);
size_type capacity() const EA_NOEXCEPT;
void set_capacity(size_type n); // Sets the capacity to the given value, including values less than the current capacity. Adjusts the size downward if n < size, by throwing out the oldest elements in the buffer.
void reserve(size_type n); // Reserve a given capacity. Doesn't decrease the capacity; it only increases it (for compatibility with other containers' behavior).
reference front();
const_reference front() const;
reference back();
const_reference back() const;
void push_back(const value_type& value);
reference push_back();
void pop_back();
void push_front(const value_type& value);
reference push_front();
void pop_front();
reference operator[](size_type n);
const_reference operator[](size_type n) const;
// size_type read(value_type* pDestination, size_type nCount);
// size_type read(iterator** pPosition1, iterator** pPosition2, size_type& nCount1, size_type& nCount2);
#if EASTL_MOVE_SEMANTICS_ENABLED && EASTL_VARIADIC_TEMPLATES_ENABLED
template <class... Args>
void emplace_front(Args&&... args);
template <class... Args>
void emplace_back(Args&&... args);
template <class... Args>
iterator emplace(const_iterator position, Args&&... args);
#else
#if EASTL_MOVE_SEMANTICS_ENABLED
void push_front(value_type&& value);
void push_back(value_type&& value);
void emplace_front(value_type&& value);
void emplace_back(value_type&& value);
iterator emplace(const_iterator position, value_type&& value);
#endif
void emplace_front(const value_type& value);
void emplace_back(const value_type& value);
iterator emplace(const_iterator position, const value_type& value);
#endif
iterator insert(const_iterator position, const value_type& value);
void insert(const_iterator position, size_type n, const value_type& value);
void insert(const_iterator position, std::initializer_list<value_type> ilist);
template <typename InputIterator>
void insert(const_iterator position, InputIterator first, InputIterator last);
iterator erase(const_iterator position);
iterator erase(const_iterator first, const_iterator last);
reverse_iterator erase(const_reverse_iterator position);
reverse_iterator erase(const_reverse_iterator first, const_reverse_iterator last);
void clear();
container_type& get_container();
const container_type& get_container() const;
bool validate() const;
int validate_iterator(const_iterator i) const;
}; // class ring_buffer
template <typename T, typename Pointer, typename Reference, typename Container>
struct ring_buffer_iterator
{
public:
typedef ring_buffer_iterator<T, Pointer, Reference, Container> this_type;
typedef T value_type;
typedef Pointer pointer;
typedef Reference reference;
typedef typename Container::size_type size_type;
typedef typename Container::difference_type difference_type;
typedef typename Container::iterator container_iterator;
typedef typename Container::const_iterator container_const_iterator;
typedef ring_buffer_iterator<T, T*, T&, Container> iterator;
typedef ring_buffer_iterator<T, const T*, const T&, Container> const_iterator;
typedef eastl::random_access_iterator_tag iterator_category;
public:
Container* mpContainer;
container_iterator mContainerIterator;
public:
ring_buffer_iterator();
ring_buffer_iterator(Container* pContainer, const container_iterator& containerIterator);
ring_buffer_iterator(const iterator& x);
ring_buffer_iterator& operator=(const iterator& x);
reference operator*() const;
pointer operator->() const;
this_type& operator++();
this_type operator++(int);
this_type& operator--();
this_type operator--(int);
this_type& operator+=(difference_type n);
this_type& operator-=(difference_type n);
this_type operator+(difference_type n) const;
this_type operator-(difference_type n) const;
protected:
void increment(difference_type n, eastl::input_iterator_tag);
void increment(difference_type n, eastl::random_access_iterator_tag);
}; // struct ring_buffer_iterator
/// ring_buffer
///
/// Implements a ring buffer via a given container type, which would
/// typically be a vector or array, though any container which supports
/// bidirectional iteration would work.
///
/// A ring buffer is a FIFO (first-in, first-out) container which acts
/// much like a queue. The difference is that a ring buffer is implemented
/// via chasing pointers around a container and moving the read and write
/// positions forward (and possibly wrapping around) as the container is
/// read and written via pop_front and push_back.
///
/// The benefit of a ring buffer is that memory allocations don't occur
/// and new elements are neither added nor removed from the container.
/// Elements in the container are simply assigned values in circles around
/// the container.
///
/// ring_buffer is different from other containers -- including adapter
/// containers -- in how iteration is done. Iteration of a ring buffer
/// starts at the current begin position, proceeds to the end of the underlying
/// container, and continues at the begin of the underlying container until
/// the ring buffer's current end position. Thus a ring_buffer does
/// indeed have a begin and an end, though the values of begin and end
/// chase each other around the container. An empty ring_buffer is one
/// in which end == begin, and a full ring_buffer is one in which
/// end + 1 == begin.
///
/// Example of a ring buffer layout, where + indicates queued items:
/// ++++++++++--------------------------------+++++++++
/// ^ ^
/// end begin
///
/// Empty ring buffer:
/// ---------------------------------------------------
/// ^
/// begin / end
///
/// Full ring buffer. Note that one item is necessarily unused; it is
/// analogous to a '\0' at the end of a C string:
/// +++++++++++++++++++++++++++++++++++++++++-+++++++++
/// ^^
/// end begin
///
/// A push_back operation on a ring buffer assigns the new value to end.
/// If there is no more space in the buffer, this will result in begin
/// being overwritten and the begin position being moved foward one position.
/// The user can use the full() function to detect this condition.
/// Note that elements in a ring buffer are not created or destroyed as
/// their are added and removed; they are merely assigned. Only on
/// container construction and destruction are any elements created and
/// destroyed.
///
/// The ring buffer can be used in either direction. By this we mean that
/// you can use push_back to add items and pop_front to remove them; or you can
/// use push_front to add items and pop_back to remove them. You aren't
/// limited to these operations; you can push or pop from either side
/// arbitrarily and you can insert or erase anywhere in the container.
///
/// The ring buffer requires the user to specify a Container type, which
/// by default is vector. However, any container with bidirectional iterators
/// will work, such as list, deque, string or any of the fixed_* versions
/// of these containers, such as fixed_string. Since ring buffer works via copying
/// elements instead of allocating and freeing nodes, inserting in the middle
/// of a ring buffer based on list (instead of vector) is no more efficient.
///
/// To use the ring buffer, its container must be resized to the desired
/// ring buffer size. Changing the size of a ring buffer may cause ring
/// buffer iterators to invalidate.
///
/// An alternative to using a ring buffer is to use a list with a user-created
/// node pool and custom allocator. There are various tradeoffs that result from this.
///
/// Example usage:
/// ring_buffer< int, list<int> > rb(100);
/// rb.push_back(1);
///
/// Example usage:
/// // Example of creating an on-screen debug log that shows 16
/// // strings at a time and scrolls older strings away.
///
/// // Create ring buffer of 16 strings.
/// ring_buffer< string, vector<string> > debugLogText(16);
///
/// // Reserve 128 chars for each line. This can make it so that no
/// // runtime memory allocations occur.
/// for(vector<string>::iterator it = debugLogText.get_container().begin(),
/// itEnd = debugLogText.get_container().end(); it != itEnd; ++it)
/// {
/// (*it).reserve(128);
/// }
///
/// // Add a new string, using push_front() and front() instead of
/// // push_front(str) in order to avoid creating a temporary str.
/// debugLogText.push_front();
/// debugLogText.front() = "Player fired weapon";
///
template <typename T, typename Container = eastl::vector<T>, typename Allocator = typename Container::allocator_type>
class ring_buffer
{
public:
typedef ring_buffer<T, Container, Allocator> this_type;
typedef Container container_type;
typedef Allocator allocator_type;
typedef typename Container::value_type value_type;
typedef typename Container::reference reference;
typedef typename Container::const_reference const_reference;
typedef typename Container::size_type size_type;
typedef typename Container::difference_type difference_type;
typedef typename Container::iterator container_iterator;
typedef typename Container::const_iterator container_const_iterator;
typedef ring_buffer_iterator<T, T*, T&, Container> iterator;
typedef ring_buffer_iterator<T, const T*, const T&, Container> const_iterator;
typedef eastl::reverse_iterator<iterator> reverse_iterator;
typedef eastl::reverse_iterator<const_iterator> const_reverse_iterator;
public: // We declare public so that global comparison operators can be implemented without adding an inline level and without tripping up GCC 2.x friend declaration failures. GCC (through at least v4.0) is poor at inlining and performance wins over correctness.
Container c; // We follow the naming convention established for stack, queue, priority_queue and name this 'c'. This variable must always have a size of at least 1, as even an empty ring_buffer has an unused terminating element.
protected:
container_iterator mBegin; // We keep track of where our begin and end are by using Container iterators.
container_iterator mEnd;
size_type mSize;
public:
// There currently isn't a ring_buffer constructor that specifies and initial size, unlike other containers.
explicit ring_buffer(size_type cap = 0); // Construct with an initial capacity (but size of 0).
explicit ring_buffer(size_type cap, const allocator_type& allocator);
explicit ring_buffer(const Container& x);
explicit ring_buffer(const allocator_type& allocator);
ring_buffer(const this_type& x);
#if EASTL_MOVE_SEMANTICS_ENABLED
ring_buffer(this_type&& x);
ring_buffer(this_type&& x, const allocator_type& allocator);
#endif
ring_buffer(std::initializer_list<value_type> ilist, const allocator_type& allocator = allocator_type()); // This function sets the capacity to be equal to the size of the initializer list.
// No destructor necessary. Default will do.
this_type& operator=(const this_type& x);
this_type& operator=(std::initializer_list<value_type> ilist);
#if EASTL_MOVE_SEMANTICS_ENABLED
this_type& operator=(this_type&& x);
#endif
template <typename InputIterator>
void assign(InputIterator first, InputIterator last);
void swap(this_type& x);
iterator begin() EA_NOEXCEPT;
const_iterator begin() const EA_NOEXCEPT;
const_iterator cbegin() const EA_NOEXCEPT;
iterator end() EA_NOEXCEPT;
const_iterator end() const EA_NOEXCEPT;
const_iterator cend() const EA_NOEXCEPT;
reverse_iterator rbegin() EA_NOEXCEPT;
const_reverse_iterator rbegin() const EA_NOEXCEPT;
const_reverse_iterator crbegin() const EA_NOEXCEPT;
reverse_iterator rend() EA_NOEXCEPT;
const_reverse_iterator rend() const EA_NOEXCEPT;
const_reverse_iterator crend() const EA_NOEXCEPT;
bool empty() const EA_NOEXCEPT;
bool full() const EA_NOEXCEPT;
size_type size() const EA_NOEXCEPT;
void resize(size_type n);
size_type capacity() const EA_NOEXCEPT;
void set_capacity(size_type n); // Sets the capacity to the given value, including values less than the current capacity. Adjusts the size downward if n < size, by throwing out the oldest elements in the buffer.
void reserve(size_type n); // Reserve a given capacity. Doesn't decrease the capacity; it only increases it (for compatibility with other containers' behavior).
reference front();
const_reference front() const;
reference back();
const_reference back() const;
void push_back(const value_type& value);
reference push_back();
void pop_back();
void push_front(const value_type& value);
reference push_front();
void pop_front();
reference operator[](size_type n);
const_reference operator[](size_type n) const;
// size_type read(value_type* pDestination, size_type nCount);
// size_type read(iterator** pPosition1, iterator** pPosition2, size_type& nCount1, size_type& nCount2);
#if EASTL_MOVE_SEMANTICS_ENABLED && EASTL_VARIADIC_TEMPLATES_ENABLED
template <class... Args>
void emplace_front(Args&&... args);
template <class... Args>
void emplace_back(Args&&... args);
template <class... Args>
iterator emplace(const_iterator position, Args&&... args);
#else
#if EASTL_MOVE_SEMANTICS_ENABLED
void push_front(value_type&& value);
void push_back(value_type&& value);
void emplace_front(value_type&& value);
void emplace_back(value_type&& value);
iterator emplace(const_iterator position, value_type&& value);
#endif
void emplace_front(const value_type& value);
void emplace_back(const value_type& value);
iterator emplace(const_iterator position, const value_type& value);
#endif
iterator insert(const_iterator position, const value_type& value);
void insert(const_iterator position, size_type n, const value_type& value);
void insert(const_iterator position, std::initializer_list<value_type> ilist);
template <typename InputIterator>
void insert(const_iterator position, InputIterator first, InputIterator last);
iterator erase(const_iterator position);
iterator erase(const_iterator first, const_iterator last);
reverse_iterator erase(const_reverse_iterator position);
reverse_iterator erase(const_reverse_iterator first, const_reverse_iterator last);
void clear();
container_type& get_container();
const container_type& get_container() const;
bool validate() const;
int validate_iterator(const_iterator i) const;
}; // class ring_buffer
Nicolas Guillemot
Jul 3, 2015, 2:33:04 AM7/3/15
to Paul Pedriana, unofficial-r...@googlegroups.com
Thanks for sharing, Paul. This is a great implementation.
Many pieces of EASTL are viable standardization proposals with little modification necessary. I believe this was one of SG14's original goals (reviewing the EASTL paper and extracting proposals from it.) We should be looking at what EASTL is doing for any discussion in this forum.Also, I feel vindicated to see that not only does this coincidentally implement some things I recently suggested to Guy, but its example code uses fixed length strings! :P
--
You received this message because you are subscribed to the Google Groups "unofficial-real-time-cxx" group.
To unsubscribe from this group and stop receiving emails from it, send an email to unofficial-real-ti...@googlegroups.com.
To post to this group, send email to unofficial-r...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/unofficial-real-time-cxx/CAJ5r4P0MwqPds7R0O6STYM%2Bxif6LRcFFmsPsUs0GOzsZnWRObw%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.
Guy Davidson
Jul 3, 2015, 7:53:10 AM7/3/15
to unofficial-r...@googlegroups.com
Thanks Paul. That's nice. I'll consider this implementation when I take another look at mine. Might I ask:
- Why you chose bidirectional operation?
- Why you chose an empty element sentinel rather than an element count?
Cheers,
Guy
Reply all
Reply to author
Forward
Message has been deleted
0 new messages