463 lines
12 KiB
C++
463 lines
12 KiB
C++
#pragma once
|
|
|
|
#include <array>
|
|
#include <cassert>
|
|
#include <cstddef>
|
|
#include <cstdint>
|
|
#include <cstring>
|
|
|
|
namespace rims {
|
|
|
|
struct RingIndex {
|
|
using index_t = uint16_t;
|
|
|
|
constexpr RingIndex(index_t n) : N{n} {
|
|
reset();
|
|
}
|
|
|
|
constexpr void reset() {
|
|
_head = 0;
|
|
_tail = 0;
|
|
_full = false;
|
|
}
|
|
|
|
constexpr bool empty() const {
|
|
return (!_full && _head == _tail);
|
|
}
|
|
|
|
constexpr bool full() const {
|
|
return _full;
|
|
}
|
|
|
|
constexpr std::size_t size() const {
|
|
if (full()) {
|
|
return N;
|
|
}
|
|
if (_head >= _tail) {
|
|
return _head - _tail;
|
|
} else {
|
|
return N + _head - _tail;
|
|
}
|
|
}
|
|
|
|
constexpr std::size_t capacity() const {
|
|
return N;
|
|
}
|
|
|
|
constexpr std::size_t free() const {
|
|
return capacity() - size();
|
|
}
|
|
|
|
constexpr index_t increment_head() {
|
|
assert(not full());
|
|
return increment_head(1);
|
|
}
|
|
|
|
constexpr index_t increment_head(index_t n) {
|
|
assert(free() >= n);
|
|
_head = (_head + n) % N;
|
|
_full = _head == _tail;
|
|
return prev_head();
|
|
}
|
|
|
|
constexpr index_t decrement_head() {
|
|
assert(not empty());
|
|
_head = (_head + N - 1) % N;
|
|
_full = false;
|
|
return _head;
|
|
}
|
|
|
|
constexpr index_t increment_tail() {
|
|
assert(!empty());
|
|
return increment_tail(1);
|
|
}
|
|
|
|
constexpr index_t increment_tail(index_t n) {
|
|
assert(size() >= n);
|
|
_tail = (_tail + n) % N;
|
|
_full = false;
|
|
return prev_tail();
|
|
}
|
|
|
|
constexpr index_t head() const {
|
|
return _head;
|
|
}
|
|
|
|
constexpr index_t tail() const {
|
|
return _tail;
|
|
}
|
|
|
|
constexpr index_t firstFree() const {
|
|
assert(!full());
|
|
return head();
|
|
}
|
|
|
|
constexpr bool headAfterTail() const {
|
|
return head() >= tail();
|
|
}
|
|
constexpr std::size_t spaceBack() const {
|
|
if (headAfterTail()) {
|
|
return capacity() - head();
|
|
} else {
|
|
if (spaceMid() == 0) {
|
|
return capacity() - tail() - 1;
|
|
}
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
constexpr std::size_t spaceFront() const {
|
|
if (headAfterTail()) {
|
|
return tail();
|
|
} else {
|
|
if (spaceMid() == 0) {
|
|
return head();
|
|
}
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
constexpr std::size_t spaceMid() const {
|
|
const auto head2Tail = tail() - head();
|
|
return head2Tail > 0 ? head2Tail : 0;
|
|
}
|
|
|
|
using area = std::pair<index_t, std::size_t>;
|
|
constexpr std::pair<area, area> getFreeAreas() const {
|
|
assert((spaceFront() + spaceBack() + spaceMid()) == free());
|
|
|
|
const std::size_t capacityMid = spaceMid();
|
|
if (capacityMid) {
|
|
return {{head(), capacityMid}, {0, 0}};
|
|
} else {
|
|
return {{head(), spaceBack()}, {0, spaceFront()}};
|
|
}
|
|
}
|
|
|
|
private:
|
|
constexpr index_t prev_tail() const {
|
|
return _tail == 0 ? N - 1 : _tail - 1;
|
|
}
|
|
constexpr index_t prev_head() const {
|
|
return _head == 0 ? N - 1 : _head - 1;
|
|
}
|
|
|
|
index_t N{0};
|
|
index_t _head{0};
|
|
index_t _tail{0};
|
|
bool _full{false};
|
|
};
|
|
|
|
template <class T, std::size_t N> class RingBuffer {
|
|
public:
|
|
static_assert(std::is_trivial_v<T>);
|
|
static_assert(std::is_trivially_destructible_v<T>);
|
|
static_assert(std::is_trivially_copyable_v<T>);
|
|
|
|
using value_type = T;
|
|
explicit RingBuffer() : _index{N} {
|
|
}
|
|
|
|
T &push_back(const T &item) {
|
|
if (full()) {
|
|
pop_front();
|
|
}
|
|
|
|
auto at = _index.head();
|
|
std::construct_at(reinterpret_cast<T *>(std::addressof(_buf[_index.increment_head()])), item);
|
|
|
|
return directy_at(at);
|
|
}
|
|
|
|
void put_n(const T *items, std::size_t n) {
|
|
static_assert(std::is_trivially_constructible_v<T>);
|
|
assert(_index.free() >= n);
|
|
|
|
auto areas = _index.getFreeAreas();
|
|
|
|
assert((areas.first.second + areas.second.second) >= n);
|
|
|
|
std::memcpy(_buf[areas.first.first], items, areas.first.second * sizeof(T));
|
|
if (areas.first.second <= n) std::memcpy(_buf[areas.second.first], items + areas.first.second, areas.second.second * sizeof(T));
|
|
|
|
_index.increment_head(n);
|
|
}
|
|
|
|
T get() {
|
|
assert(not empty());
|
|
|
|
// Read data and advance the tail (we now have a free space)
|
|
T val = std::move(*reinterpret_cast<T *>(std::addressof(_buf[_index.tail()])));
|
|
destroy_at(_index.increment_tail());
|
|
|
|
return val;
|
|
}
|
|
|
|
// removes the last (youngest) element
|
|
void pop_back() {
|
|
assert(not empty());
|
|
|
|
destroy_at(_index.decrement_head());
|
|
}
|
|
|
|
// removes the first (oldest) element
|
|
void pop_front() {
|
|
assert(not empty());
|
|
|
|
destroy_at(_index.increment_tail());
|
|
}
|
|
|
|
// oldest element
|
|
const T &front() const {
|
|
assert(not empty());
|
|
|
|
return *cbegin();
|
|
}
|
|
T &front() {
|
|
assert(not empty());
|
|
|
|
return *begin();
|
|
}
|
|
|
|
const T &back() const {
|
|
assert(not empty());
|
|
|
|
return *std::prev(cend());
|
|
}
|
|
T &back() {
|
|
assert(not empty());
|
|
|
|
return *(std::prev(end()));
|
|
}
|
|
|
|
const T &at(std::size_t index) const {
|
|
assert(index < size());
|
|
return *(cbegin() + index);
|
|
}
|
|
|
|
T &at(std::size_t index) {
|
|
assert(index < size());
|
|
return *(begin() + index);
|
|
}
|
|
|
|
constexpr void reset() {
|
|
// destroy elements? :|
|
|
_index.reset();
|
|
}
|
|
|
|
constexpr bool empty() const {
|
|
return _index.empty();
|
|
}
|
|
|
|
constexpr bool full() const {
|
|
return _index.full();
|
|
}
|
|
|
|
constexpr std::size_t capacity() const {
|
|
return _index.capacity();
|
|
}
|
|
|
|
constexpr std::size_t size() const {
|
|
return _index.size();
|
|
}
|
|
|
|
constexpr std::size_t free() const {
|
|
return _index.free();
|
|
}
|
|
|
|
// Iterator class for ring_buffer
|
|
template <bool CONST> class iterator_base {
|
|
public:
|
|
using iterator_category = std::random_access_iterator_tag;
|
|
using value_type = T;
|
|
using difference_type = std::ptrdiff_t;
|
|
using pointer = std::conditional_t<CONST, const value_type *, value_type *>;
|
|
using reference = std::conditional_t<CONST, const value_type &, value_type &>;
|
|
|
|
using iterator_t = iterator_base<CONST>;
|
|
using buf_t = std::conditional_t<CONST, const std::array<std::byte[sizeof(T)], N>, std::array<std::byte[sizeof(T)], N>>;
|
|
|
|
constexpr iterator_base() = default;
|
|
constexpr iterator_base(buf_t &buf, std::size_t index, std::size_t tail, std::size_t head) : buf_(&buf), current_(index), tail_(tail), head_(head), looped_(false) {
|
|
}
|
|
|
|
constexpr iterator_base(const iterator_base &rhs) = default;
|
|
constexpr iterator_base(iterator_base &&rhs) = default;
|
|
constexpr iterator_base &operator=(const iterator_base &rhs) = default;
|
|
constexpr iterator_base &operator=(iterator_base &&rhs) = default;
|
|
|
|
reference operator*() const {
|
|
return *reinterpret_cast<pointer>(std::addressof((*buf_)[current_]));
|
|
}
|
|
|
|
pointer operator->() const {
|
|
return std::addressof(operator*());
|
|
}
|
|
|
|
constexpr iterator_t &operator++() {
|
|
current_ = (current_ + 1) % N;
|
|
// Detect if we have looped over the circular buffer
|
|
if (current_ == tail_ && looped_) {
|
|
current_ = head_; // Move iterator to end
|
|
}
|
|
if (current_ == head_) {
|
|
looped_ = true;
|
|
}
|
|
return *this;
|
|
}
|
|
|
|
constexpr iterator_t operator++(int) {
|
|
iterator_t tmp = *this;
|
|
++(*this);
|
|
return tmp;
|
|
}
|
|
|
|
constexpr iterator_t &operator--() {
|
|
if (current_ == 0) current_ = N - 1;
|
|
else current_--;
|
|
|
|
// Detect if we have looped over the circular buffer
|
|
if (current_ == head_ && looped_) {
|
|
current_ = tail_; // Move iterator to end
|
|
}
|
|
if (current_ == tail_) {
|
|
looped_ = true;
|
|
}
|
|
return *this;
|
|
}
|
|
|
|
constexpr iterator_t operator--(int) {
|
|
iterator_t tmp = *this;
|
|
--(*this);
|
|
return tmp;
|
|
}
|
|
|
|
constexpr bool operator==(const iterator_t &other) const {
|
|
return current_ == other.current_ && looped_;
|
|
}
|
|
|
|
constexpr iterator_t &operator+=(difference_type n) {
|
|
current_ = (current_ + n) % N;
|
|
return *this;
|
|
}
|
|
|
|
constexpr iterator_t &operator+=(const iterator_t &n) {
|
|
current_ = (current_ + n.current_) % N;
|
|
return *this;
|
|
}
|
|
|
|
constexpr iterator_t operator+(difference_type n) const {
|
|
std::size_t new_index = (current_ + n) % N;
|
|
return iterator_t(*buf_, new_index, tail_, head_);
|
|
}
|
|
|
|
constexpr friend iterator_t operator+(iterator_t it, const iterator_t &n) {
|
|
it += n;
|
|
return it;
|
|
}
|
|
|
|
constexpr friend iterator_t operator+(difference_type it, const iterator_t &n) {
|
|
iterator_t tmp = n;
|
|
tmp += it;
|
|
return tmp;
|
|
}
|
|
|
|
constexpr iterator_t &operator-=(difference_type n) {
|
|
current_ = (current_ + N - (n % N)) % N;
|
|
return *this;
|
|
}
|
|
|
|
constexpr friend iterator_t operator-(const iterator_t &lhs, difference_type n) {
|
|
iterator_t tmp = lhs;
|
|
tmp -= n;
|
|
return tmp;
|
|
}
|
|
|
|
constexpr friend difference_type operator-(const iterator_t &lhs, const iterator_t &rhs) {
|
|
if (lhs.current_ >= rhs.current_) {
|
|
return static_cast<difference_type>(lhs.current_ - rhs.current_);
|
|
} else {
|
|
return static_cast<difference_type>(N + lhs.current_ - rhs.current_);
|
|
}
|
|
}
|
|
|
|
constexpr reference operator[](difference_type n) const {
|
|
return *(*this + n);
|
|
}
|
|
|
|
// constexpr bool operator<(const iterator_t & other) const {
|
|
|
|
// return (*this - other) < 0;
|
|
// }
|
|
// constexpr bool operator>(const iterator_t & other) const {
|
|
// return other < *this;
|
|
// }
|
|
// constexpr bool operator<=(const iterator_t & other) const {
|
|
// return !(*this > other);
|
|
// }
|
|
// constexpr bool operator>=(const iterator_t & other) const {
|
|
// return !(*this < other);
|
|
// }
|
|
// constexpr bool operator!=(const iterator_t & other) const {
|
|
// return !(*this == other);
|
|
// }
|
|
|
|
private:
|
|
buf_t *buf_{nullptr};
|
|
std::size_t current_{0};
|
|
|
|
std::size_t tail_{0};
|
|
std::size_t head_{0};
|
|
|
|
bool looped_{false};
|
|
};
|
|
|
|
using iterator = iterator_base<false>;
|
|
using const_iterator = iterator_base<true>;
|
|
|
|
static_assert(std::bidirectional_iterator<iterator>);
|
|
// static_assert(std::random_access_iterator< iterator >);
|
|
static_assert(std::bidirectional_iterator<const_iterator>);
|
|
// static_assert(std::random_access_iterator< const_iterator >);
|
|
|
|
// Begin and end functions to return iterator
|
|
iterator begin() {
|
|
return {_buf, _index.tail(), _index.tail(), _index.head()};
|
|
}
|
|
const_iterator begin() const {
|
|
return {_buf, _index.tail(), _index.tail(), _index.head()};
|
|
}
|
|
|
|
const_iterator cbegin() const {
|
|
return {_buf, _index.tail(), _index.tail(), _index.head()};
|
|
}
|
|
|
|
iterator end() {
|
|
return {_buf, _index.head(), _index.tail(), _index.head()};
|
|
}
|
|
const_iterator end() const {
|
|
return {_buf, _index.head(), _index.tail(), _index.head()};
|
|
}
|
|
const_iterator cend() const {
|
|
return {_buf, _index.head(), _index.tail(), _index.head()};
|
|
}
|
|
|
|
private:
|
|
void destroy_at(int index) {
|
|
std::destroy_at(std::addressof(_buf[index]));
|
|
std::memset(std::addressof(_buf[index]), 0, sizeof(T));
|
|
}
|
|
|
|
const T &directy_at(int index) const {
|
|
return *reinterpret_cast<const T *>(std::addressof(_buf[index]));
|
|
}
|
|
T &directy_at(int index) {
|
|
return *reinterpret_cast<T *>(std::addressof(_buf[index]));
|
|
}
|
|
|
|
std::array<std::byte[sizeof(T)], N> _buf;
|
|
RingIndex _index;
|
|
};
|
|
|
|
} // namespace rims
|