ring: add simple statically sized ring buffer

2 files changed, 218 insertions, 0 deletions

diff --git a/ring.h b/ring.h
new file mode 100644
index 0000000..3658ec4
--- /dev/null
+++ b/ring.h
@@ -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);
+}