ring: add simple statically sized ring buffer

1 files changed, 125 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