Class ring_buffer

Synopsis

#include <include/EASTL/bonus/ring_buffer.h>

template <typename T, typename Container = eastl::vector<T>, typename Allocator = typename Container::allocator_type>
class ring_buffer

Description

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 analagous 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";

Mentioned in

Methods

ring_buffer overloadThere currently isn't a ring_buffer constructor that specifies an initial size, unlike other containers.
assign
back overload
begin overload
capacity
cbegin
cend
clear
crbegin
crend
empty
end overload
erase overload
front overload
full
get_container overload
insert overloadTo consider: size_type read(value_type* pDestination, size_type nCount); size_type read(iterator** pPosition1, iterator** pPosition2, size_type& nCount1, size_type& nCount2); To do: template <class..
operator= overloadNo destructor necessary. Default will do.
operator[] overload
pop_back
pop_front
push_back overloadA push_back operation on a ring buffer assigns the new value to end
push_front overload
rbegin overload
rend overload
reserve
resize
set_capacity
size
swap
validate
validate_iterator

Source

Lines 203-335 in include/EASTL/bonus/ring_buffer.h.

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 an 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);
    ring_buffer(this_type&& x);
    ring_buffer(this_type&& x, const allocator_type& allocator);
    ring_buffer(std::initializer_list<value_type> ilist, const allocator_type& allocator = EASTL_RING_BUFFER_DEFAULT_ALLOCATOR); // 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);
    this_type& operator=(this_type&& x);
    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;
    size_type              capacity() const EA_NOEXCEPT;
    void                   resize(size_type n);
    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            push_front(const value_type& value);
    reference       push_front();
    void            pop_back();
    void            pop_front();
    reference       operator[](size_type n);
    const_reference operator[](size_type n) const;
    // To consider:
    // size_type read(value_type* pDestination, size_type nCount);
    // size_type read(iterator** pPosition1, iterator** pPosition2, size_type& nCount1, size_type& nCount2);
    /* To do:
        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);
    */
    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;
protected:
    //size_type DoGetSize(EASTL_ITC_NS::input_iterator_tag) const;
    //size_type DoGetSize(EASTL_ITC_NS::random_access_iterator_tag) const;
}; // class ring_buffer





Add Discussion as Guest

Log in