RingDeque.hpp

Go to the documentation of this file.

#pragma once
#include <Pothos/Config.hpp>
#include <cstdlib> //size_t
#include <utility> //forward
#include <memory> //allocator
#include <cassert>

namespace Pothos {
namespace Util {

template <typename T, typename Allocator = std::allocator<T>>
class RingDeque
{
public:
    RingDeque(const size_t capacity = 1, const Allocator &allocator = Allocator());

    RingDeque(const RingDeque<T, Allocator> &other);

    RingDeque(RingDeque<T, Allocator> &&other);

    RingDeque &operator=(const RingDeque<T, Allocator> &other);

    RingDeque &operator=(RingDeque<T, Allocator> &&other);

    ~RingDeque(void);

    const T &operator[](const size_t offset) const;

    T &operator[](const size_t offset);

    template <typename U>
    void push_front(U &&elem);

    template <typename... Args>
    T &emplace_front(Args&&... args);

    void pop_front(void);

    const T &front(void) const;

    T &front(void);

    template <typename U>
    void push_back(U &&elem);

    template <typename... Args>
    T &emplace_back(Args&&... args);

    void pop_back(void);

    const T &back(void) const;

    T &back(void);

    bool empty(void) const;

    bool full(void) const;

    size_t size(void) const;

    size_t capacity(void) const;

    void set_capacity(const size_t capacity);

    void clear(void);

    typedef T value_type; 

    typedef Allocator allocator_type; 

private:
    Allocator _allocator;
    size_t _mask;
    size_t _capacity;
    size_t _frontIndex;
    size_t _numElements;
    T *_container;
};

namespace Detail {

    template <typename T>
    T nextPow2(const T &in)
    {
        T out(1);
        while (out < in) out <<= 1;
        return out;
    }

} //namespace Detail

template <typename T, typename A>
RingDeque<T, A>::RingDeque(const size_t capacity, const A &allocator):
    _allocator(allocator),
    _mask(Detail::nextPow2(capacity)-1),
    _capacity(capacity),
    _frontIndex(0),
    _numElements(0),
    _container(_allocator.allocate(_mask+1))
{
    assert(capacity > 0);
}

template <typename T, typename A>
RingDeque<T, A>::RingDeque(const RingDeque<T, A> &other):
    _mask(other._mask),
    _capacity(other._capacity),
    _frontIndex(0),
    _numElements(0),
    _container(_allocator.allocate(_mask+1))
{
    for (size_t i = 0; i < other.size(); i++)
    {
        this->push_back(other[i]);
    }
}

template <typename T, typename A>
RingDeque<T, A>::RingDeque(RingDeque<T, A> &&other):
    _allocator(std::move(other._allocator)),
    _mask(std::move(other._mask)),
    _capacity(std::move(other._capacity)),
    _frontIndex(std::move(other._frontIndex)),
    _numElements(std::move(other._numElements)),
    _container(std::move(other._container))
{
    other._numElements = 0;
    other._capacity = 0;
    other._container = nullptr;
}

template <typename T, typename A>
RingDeque<T, A> &RingDeque<T, A>::operator=(const RingDeque<T, A> &other)
{
    this->clear();
    this->set_capacity(other.capacity());
    for (size_t i = 0; i < other.size(); i++)
    {
        this->push_back(other[i]);
    }
    return *this;
}

template <typename T, typename A>
RingDeque<T, A> &RingDeque<T, A>::operator=(RingDeque<T, A> &&other)
{
    this->clear();
    _allocator.deallocate(_container, _mask+1);
    _allocator = std::move(other._allocator);
    _mask = std::move(other._mask);
    _capacity = std::move(other._capacity);
    _frontIndex = std::move(other._frontIndex);
    _numElements = std::move(other._numElements);
    _container = std::move(other._container);
    other._numElements = 0;
    other._capacity = 0;
    other._container = nullptr;
    return *this;
}

template <typename T, typename A>
RingDeque<T, A>::~RingDeque(void)
{
    if (_container == nullptr) return;
    this->clear();
    _allocator.deallocate(_container, _mask+1);
}

template <typename T, typename A>
const T &RingDeque<T, A>::operator[](const size_t offset) const
{
    return _container[(_frontIndex + offset) & _mask];
}

template <typename T, typename A>
T &RingDeque<T, A>::operator[](const size_t offset)
{
    return _container[(_frontIndex + offset) & _mask];
}

template <typename T, typename A>
template <typename U>
void RingDeque<T, A>::push_front(U &&elem)
{
    this->emplace_front(std::forward<U>(elem));
}

template <typename T, typename A>
template <typename... Args>
T &RingDeque<T, A>::emplace_front(Args&&... args)
{
    assert(not this->full());
    _frontIndex--;
    _numElements++;
    return *(new(&front()) T(std::forward<Args>(args)...));
}

template <typename T, typename A>
void RingDeque<T, A>::pop_front(void)
{
    assert(not this->empty());
    this->front().~T();
    _frontIndex++;
    _numElements--;
}

template <typename T, typename A>
const T &RingDeque<T, A>::front(void) const
{
    assert(not this->empty());
    return (*this)[0];
}

template <typename T, typename A>
T &RingDeque<T, A>::front(void)
{
    assert(not this->empty());
    return (*this)[0];
}

template <typename T, typename A>
template <typename U>
void RingDeque<T, A>::push_back(U &&elem)
{
    this->emplace_back(std::forward<U>(elem));
}

template <typename T, typename A>
template <typename... Args>
T &RingDeque<T, A>::emplace_back(Args&&... args)
{
    assert(not this->full());
    _numElements++;
    return *(new(&back()) T(std::forward<Args>(args)...));
}

template <typename T, typename A>
void RingDeque<T, A>::pop_back(void)
{
    assert(not this->empty());
    this->back().~T();
    _numElements--;
}

template <typename T, typename A>
const T &RingDeque<T, A>::back(void) const
{
    assert(not this->empty());
    return (*this)[size_t(_numElements-1)];
}

template <typename T, typename A>
T &RingDeque<T, A>::back(void)
{
    assert(not this->empty());
    return (*this)[size_t(_numElements-1)];
}

template <typename T, typename A>
bool RingDeque<T, A>::empty(void) const
{
    return _numElements == 0;
}

template <typename T, typename A>
bool RingDeque<T, A>::full(void) const
{
    return _numElements == _capacity;
}

template <typename T, typename A>
size_t RingDeque<T, A>::size(void) const
{
    return _numElements;
}

template <typename T, typename A>
size_t RingDeque<T, A>::capacity(void) const
{
    return _capacity;
}

template <typename T, typename A>
void RingDeque<T, A>::set_capacity(const size_t capacity)
{
    if (_numElements > capacity) return;
    RingDeque<T, A> newRing(capacity);
    while (not this->empty())
    {
        newRing.push_back(std::move(this->front()));
        this->pop_front();
    }
    *this = std::move(newRing);
}

template <typename T, typename A>
void RingDeque<T, A>::clear(void)
{
    while (not this->empty())
    {
        this->pop_front();
    }
}

} //namespace Util
} //namespace Pothos