path: root/ring.h

#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()) {
      std::optional<T> ret = std::move(vals[m_rc & kMASK]);
      pop();
      return ret;
    }
    return std::nullopt;
  }
#else
  constexpr T take() {
    assert(!is_empty());
    T ret = std::move(vals[m_rc & kMASK]);
    pop();
    return ret;
  }
#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