diff options
| -rw-r--r-- | ring.h | 125 | ||||
| -rw-r--r-- | test/ring.cc | 93 |
2 files changed, 218 insertions, 0 deletions
@@ -0,0 +1,125 @@ +#ifndef UTILS_RING_H +#define UTILS_RING_H + +#include <new> +#include <type_traits> +#include <utility> + +#if __cplusplus >= 201703L +#include <optional> +#endif + +#include <cassert> +#include <cstddef> + +/// Helper to check if the number N is of power two. +constexpr inline bool is_power_two(std::size_t n) { + return (n > 0) && (n & (n - 1)) == 0; +} + +// -- RING --------------------------------------------------------------------- + +/// ring +/// +/// A minimal statically sized ring buffer which can hold up to N elements of +/// type T. +template <typename T, std::size_t N> +class ring { + using cursor_t = std::size_t; + static_assert(std::is_unsigned<cursor_t>::value, + "cursor type must be unsigned"); + static_assert(is_power_two(N), "ring size must be of power of two"); + + public: + // -- CONSTRUCTOR ------------------------------------------------------------ + + explicit constexpr ring() {} + + // -- DESTRUCTOR ------------------------------------------------------------- + + ~ring() { + while (!is_empty()) { + pop(); + } + } + + // -- COPY ------------------------------------------------------------------- + + // Copy semantics deleted for simplicity. + ring(const ring&) = delete; + ring& operator=(const ring&) = delete; + + // -- MOVE ------------------------------------------------------------------- + + // Move semantics deleted for simplicity. + ring(ring&&) = delete; + ring& operator=(ring&&) = delete; + + // -- STATUS ----------------------------------------------------------------- + + constexpr cursor_t size() const { + return m_wc - m_rc; + } + + constexpr bool is_full() const { + return size() == N; + } + + constexpr bool is_empty() const { + return size() == 0; + } + + // -- INSERT ----------------------------------------------------------------- + + template <typename... Args> + constexpr bool emplace(Args&&... args) { + if (!is_full()) { + new (&vals[m_wc++ & kMASK]) T(std::forward<Args>(args)...); + return true; + } + return false; + } + + constexpr bool push(const T& t) { + return emplace(t); + } + + constexpr bool push(T&& t) { + return emplace(std::move(t)); + } + + // -- REMOVE ----------------------------------------------------------------- + + void pop() { + if (!is_empty()) { + vals[m_rc++ & kMASK].~T(); + } + } + +#if __cplusplus >= 201703L + constexpr std::optional<T> take() { + if (!is_empty()) { + const std::optional<T> kRet = std::move(vals[m_rc & kMASK]); + pop(); + return kRet; + } + return std::nullopt; + } +#endif + + // -- INTERNAL --------------------------------------------------------------- + + private: + static constexpr cursor_t kMASK = N - 1; + + union { + // Array is placed in unnamed union to not default construct the Ts, when + // constructing a ring<>. + T vals[N]; + }; + + cursor_t m_wc = 0; + cursor_t m_rc = 0; +}; + +#endif diff --git a/test/ring.cc b/test/ring.cc new file mode 100644 index 0000000..a42efaa --- /dev/null +++ b/test/ring.cc @@ -0,0 +1,93 @@ +#include <ring.h> + +#include <cstdio> + +#define LOG \ + if (false) { \ + } else \ + puts(__PRETTY_FUNCTION__) + +/// A helper sruct to count instances, copy- and move constructions. +struct m { + m() { + LOG; + ++cnt; + } + ~m() { + LOG; + --cnt; + } + m(const m&) { + LOG; + ++cnt; + ++cpy; + } + m(m&&) noexcept { + LOG; + ++cnt; + ++mov; + } + m& operator=(const m&) = delete; + m& operator=(m&&) = delete; + + static std::size_t cnt; + static std::size_t mov; + static std::size_t cpy; +}; + +std::size_t m::cnt = 0; +std::size_t m::mov = 0; +std::size_t m::cpy = 0; + +int main() { + { + ring<m, 8> r; + + assert(r.size() == 0); + assert(r.is_empty()); + assert(!r.is_full()); + + for (int i = 0; i < 10; ++i) { + bool ok = r.emplace(); + i < 8 ? assert(ok) : assert(!ok); + } + + assert(r.size() == 8); + assert(!r.is_empty()); + assert(r.is_full()); + +#if __cplusplus >= 201703L + auto v = r.take(); + assert(v.has_value()); + + assert(r.size() == 7); + assert(!r.is_empty()); + assert(!r.is_full()); +#endif + + assert(m::cnt == 8); + } + + assert(m::cnt == 0); + + m::mov = 0; + m::cpy = 0; + { + ring<m, 8> r; + + // Move construct m from an m rvalue reference. + assert(m::mov == 0); + r.push(m{}); + assert(m::mov == 1); + + // Copy construct m from an m lvalue reference. + m m; + assert(m::cpy == 0); + r.push(m); + assert(m::cpy == 1); + + assert(m::cnt == 3); + } + + assert(m::cnt == 0); +} |