NET_CircularBuffer.h

Go to the documentation of this file.

/*
 * PROPRIETARY INFORMATION.  This software is proprietary to
 * Side Effects Software Inc., and is not to be reproduced,
 * transmitted, or disclosed in any way without written permission.
 *
 * NAME:        NET_CircularBuffer.h
 *
 * COMMENTS:
 *
 */

#ifndef __NET_CIRCULARBUFFER_H__
#define __NET_CIRCULARBUFFER_H__

#include "NET_API.h"

#include <UT/UT_Array.h>
#include <UT/UT_Format.h>
#include <UT/UT_Debug.h>

#include <SYS/SYS_Types.h>

#include <utility>
#include <cstring>

template <typename T>
class NET_CircularBuffer
{
public:
    using index_t = exint;
    using range_t = std::pair<T*, int>;
    using const_range_t = std::pair<const T*, int>;

    NET_CircularBuffer()
    {
        clear();
    }

    template <typename U>
    class base_iterator
    {
    public:
        using range_t = typename NET_CircularBuffer<U>::range_t;

        base_iterator(const range_t& one, const range_t& two) :
            myArrayOne(one), myArrayTwo(two), myCurrent(0)
        {}
        base_iterator(exint current) :
            myArrayOne(), myArrayTwo(), myCurrent(current)
        {}

        U* operator->() const
        {
            return this->item_(myCurrent);
        }
        U& operator*() const
        {
            return *(this->item_(myCurrent));
        }
        U& operator[](exint idx) const
        {
            return *(this->item_(idx));
        }
        base_iterator &operator++()
        {
            ++myCurrent;
            return *this;
        }
        base_iterator operator++(int)
        {
            base_iterator tmp = *this;
            ++myCurrent;
            return tmp;
        }
        base_iterator &operator--()
        {
            --myCurrent;
            return *this;
        }
        base_iterator operator--(int)
        {
            base_iterator tmp = *this;
            --myCurrent;
            return tmp;
        }
        base_iterator &operator+=(exint n)
        {
            myCurrent += n;
            return *this;
        }
        base_iterator operator+(exint n) const
        {
            base_iterator tmp = *this;
            tmp.myCurrent += n;
            return tmp;
        }
        base_iterator &operator-=(exint n)
        {
            return (*this) += (-n);
        }
        base_iterator operator-(exint n) const
        {
            return (*this) + (-n);
        }
        bool operator==(const base_iterator& it) const
        {
            return myCurrent == it.myCurrent;
        }
        bool operator!=(const base_iterator& it) const { return !(*this == it); }
        bool operator<(const base_iterator& it) const
        {
            return myCurrent < it.myCurrent;
        }
        bool operator<=(const base_iterator& it) const
        {
            return !(it < *this);
        }
        bool operator>(const base_iterator& it) const
        {
            return it < *this;
        }
        bool operator>=(const base_iterator& it) const
        {
            return !(*this < it);
        }
        exint operator-(const base_iterator& it) const
        {
            return myCurrent - it.myCurrent;
        }

    private:
        U* item_(exint idx) const
        {
            exint count = myArrayOne.second + myArrayTwo.second;
            UT_ASSERT(myCurrent <= count);

            if (myCurrent > count)
                return nullptr;

            if (myCurrent > myArrayOne.second)
            {
                exint idx = myCurrent - myArrayOne.second;
                return myArrayTwo.first + idx;
            }

            return myArrayOne.first + myCurrent;
        }

        range_t myArrayOne;
        range_t myArrayTwo;
        exint myCurrent;
    };

    using iterator = base_iterator<T>;
    using const_iterator = base_iterator<const T>;

    /// @brief The first element in the buffer. Undefined behaviour if the buffer
    /// is empty.
    ///
    /// @return The first element in the buffer
    T& front() { return myData[firstIndex_()]; }
    /// @brief The last element in the buffer. Undefined behaviour if the buffer
    /// is empty.
    ///
    /// @return The last element in the buffer. Undefined behaviour if the buffer
    /// is empty.
    T& back() { return myData[lastIndex_()]; }
    /// @brief The first element in the buffer. Undefined behaviour if the buffer
    /// is empty.
    ///
    /// @return The first element in the buffer.
    const T& front() const { return myData[firstIndex_()]; }
    /// @brief The last element in the buffer. Undefined behaviour if the buffer
    /// is empty.
    ///
    /// @return The last element in the buffer.
    const T& back() const { return myData[lastIndex_()]; }

    /// @brief The begin iterator for the buffer.
    ///
    /// @return The begin iterator
    iterator begin() { return iterator(arrayOne(), arrayTwo()); }
    /// @brief The end iterator for the buffer.
    ///
    /// @return The end iterator.
    iterator end() { return iterator(size()); }
    /// @brief The begin const iterator for the buffer.
    ///
    /// @return The begin const iterator.
    const_iterator begin() const
    {
        return const_base_iterator(arrayOne(), arrayTwo());
    }
    /// @brief The end const iterator for the buffer.
    ///
    /// @return The end const iterator.
    const_iterator end() const
    {
        return const_base_iterator(size());
    }
    /// @brief Retrieve element at provided index.
    ///
    /// @param index The index to retrieve the element at.
    ///
    /// @return The element at index.
    T& operator[](int index)
    {
        UT_ASSERT_P(!isEmpty());
        index_t i = (firstIndex_() + index) % capacity();
        return myData[i];
    }
    /// @brief Retrieve element at provided index.
    ///
    /// @param index The index to retrieve the element at.
    ///
    /// @return The element at index.
    const T& operator[](int index) const
    {
        UT_ASSERT_P(!isEmpty());
        index_t i = (firstIndex_() + index) % capacity();
        return myData[i];
    }

    /// @brief Place a single element onto the back of the buffer.
    ///
    /// @param data
    void push(const T& data)
    {
        push(&data, 1);
    }
    /// @brief Place an array of elements onto the back of the buffer.
    ///
    /// @param data The array of elements to add to the buffer.
    /// @param count The number of elements in the array to add.
    void push(const T* data, exint count)
    {
        growIfNeeded_(count);

        UT_ASSERT(!isFull());
        UT_ASSERT(size() + count <= maxSize());

        exint start_idx = mask_(myWrite);
        exint end_idx = start_idx + count;

        T* start = myData.getArray() + start_idx;
        const T* data_start = data;

        exint full_count = count;

        // Check if we need to split up the copies into two. The first being
        // at the tail end and the second being at the beginning of the
        // underlying array.
        if (end_idx > capacity())
        {
            // Grab the chunk of data to copy
            exint chunk = capacity() - start_idx;
            UT_ASSERT(chunk > 0);
            std::memcpy(start, data_start, sizeof(T) * chunk);

            full_count -= chunk;
            start = myData.data();
            data_start += chunk;
        }

        // If there is anything else that needs to be copied do that at the
        // beginning of the underlying array.
        if (full_count > 0)
        {
            std::memcpy(start, data_start, sizeof(T) * full_count);
        }

        incrementWrite_(count);
    }
    /// @brief Remove a single element from the front of the buffer.
    ///
    /// @return The element removed.
    T pop()
    {
        UT_ASSERT(!isEmpty());
        T data = myData[myRead];
        incrementRead_(1);
        return data;
    }
    /// @brief Remove multiple elements from the front of the buffer.
    ///
    /// @param count The number of elements to remove.
    void pop(int count)
    {
        incrementRead_(count);
    }

    /// @brief Is the buffer currently full.
    ///
    /// @return True if the buffer is currently full. Any new push() calls will
    /// allocate more space.
    bool isFull() const { return increment_(myWrite) == myRead; }
    /// @brief Is the buffer currently empty.
    ///
    /// @return True if the buffer currently does not store any elements.
    bool isEmpty() const { return myRead == myWrite; }
    /// @brief The number of elements currently stored in the buffer.
    ///
    /// @return The current size of the buffer.
    exint size() const
    {
        if (myWrite >= myRead)
            return myWrite - myRead;
        return (capacity() - myRead) + myWrite;
    }
    /// @brief The number of elements currently stored in the buffer.
    ///
    /// @return The current size of the buffer.
    int entries() const { return size(); }
    /// @brief The current capacity of the buffer.
    ///
    /// @return The total capacity of the buffer.
    exint capacity() const { return myData.capacity(); }
    /// @brief The absolute maximum size of the buffer. Use size() if you need
    /// to know the current size of the buffer.
    ///
    /// @return The maximum size of the buffer.
    exint maxSize() const { return std::numeric_limits<index_t>::max(); }

    /// @brief A circular buffer can wrap around in memory. This is the first
    /// array of continious memory. If the buffer is not currently wrapped then
    /// the entire buffer will be present in this array and the second array
    /// will be empty.
    ///
    /// @return A pair of the start of the array and the length of the first
    /// array.
    range_t arrayOne()
    {
        exint start = firstIndex_();
        exint end = mask_(myWrite);
        if (end < start)
            end = capacity();

        range_t result = std::make_pair(myData.data() + start, end - start);
        return result;
    }
    /// @brief Holds information about the second array of contigous data. See
    /// arrayOne() for further details.
    ///
    /// @return A pair of that start of the array and the length of the
    /// second array.
    range_t arrayTwo()
    {
        exint first_index = firstIndex_();
        exint last_index = mask_(myWrite);
        if (isEmpty() || last_index >= first_index)
            return std::make_pair(nullptr, 0);

        range_t result = std::make_pair(myData.data(), mask_(myWrite));
        return result;
    }
    /// @brief Const variant of the arrayOne().
    ///
    /// @return See arrayOne()
    const_range_t arrayOne() const
    {
        return arrayOne();
    }
    /// @brief Const variant of the arrayTwo().
    ///
    /// @return See arrayTwo()
    const_range_t arrayTwo() const
    {
        return arrayTwo();
    }
    /// @brief Completely clear the buffer. This will free any currently
    /// allocated data.
    void clear()
    {
        myRead = 0;
        myWrite = 0;
        myData.setCapacity(0);
    }

    /// @brief Printout debug information about this buffer.
    void debug() const
    {
        UTformat(stderr, "Capacity: {}\n", capacity());
        UTformat(stderr, "Size: {}\n", size());
        UTformat(stderr, "Read: {} idx={}\n", myRead, mask_(myRead));
        UTformat(stderr, "Write: {} idx={}\n", myWrite, mask_(myWrite));
    }
private:
    /// @brief Calculate the index of a value.
    ///
    /// @param value The value to calculate the index.
    ///
    /// @return The index into the buffer.
    index_t mask_(index_t value) const
    {
        exint last = myData.capacity() - 1;
        if (value > last)
            return value - last - 1;
        return value;
    }
    /// @brief Check if we need to grow our buffer. This will check against the
    /// current size and the extra data we need for some operation. If the extra
    /// data we need isnt available we bump the size of our buffer.
    ///
    /// @param count The amount of data we need available for some operation.
    void growIfNeeded_(index_t count)
    {
        if (size() + count >= capacity())
        {
            exint new_size = UTbumpAlloc(size() + count);
            myData.setCapacity(new_size);
            myData.entries(new_size);
        }
    }
    /// @brief The first index into our buffer.
    ///
    /// @return The index of the first element in our buffer.
    index_t firstIndex_() const
    {
        if (isEmpty())
            return 0;

        return mask_(myRead);
    }
    /// @brief The last index into our buffer. This is the last index of an
    /// element and not the last index of our buffer. Use mask_(myWrite) if you
    /// need the first invalid index into the buffer (used for range iterators).
    ///
    /// @return The last index of a valid element in the buffer.
    index_t lastIndex_() const
    {
        if (isEmpty())
            return 0;

        return mask_(myWrite - 1);
    }
    index_t increment_(index_t index, index_t count = 1) const
    {
        return mask_(index + count);
    }
    void incrementRead_(index_t count)
    {
        myRead = increment_(myRead, count);
    }
    void incrementWrite_(index_t count)
    {
        myWrite = increment_(myWrite, count);
    }

    UT_Array<T> myData;
    index_t myRead;
    index_t myWrite;
};

#endif // __NET_CIRCULARBUFFER_H__