ring_buffer.hpp

Go to the documentation of this file.

/*
 
Copyright 2025 Matthew Tolman
 
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
 
   http://www.apache.org/licenses/LICENSE-2.0
 
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
 
*/
 
#ifndef MTCORE_RING_BUFFER_HPP
#define MTCORE_RING_BUFFER_HPP
 
#include "iter.hpp"
#include "optional.hpp"
#include "result.hpp"

namespace mtcore {
  template<typename T>
  struct RingBuffer {
  private:
    Slice<T> elements = {};
    size_t head       = 0;
    size_t tail       = 0;
    size_t count      = 0;
 
  public:
    using Elem = T;

    decltype(auto) ptr_iter() noexcept {
      ensure(elements.head, "NOT INITIALIZED");
      return iter::ptr(*this);
    }

    decltype(auto) ptr_iter() const noexcept {
      ensure(elements.head, "NOT INITIALIZED");
      return iter::const_ptr(*this);
    }

    decltype(auto) iter() noexcept {
      ensure(elements.head, "NOT INITIALIZED");
      return iter::val(*this);
    }

    Result<void, AllocationError> init(Allocator &alloc, size_t initCapacity = 10) noexcept {
      ensure(!head && !tail && !count, "ALREADY INITIALIZED");
      ensure(elements.head == nullptr && elements.size() == 0, "ALREADY INITIALIZED!");
      initCapacity  = initCapacity ? initCapacity : 10;
      auto allocRes = alloc.create_many<T>(initCapacity);
      if (allocRes.is_error()) {
        return allocRes.error();
      }
 
      elements = *allocRes;
      return success();
    }

    Result<void, AllocationError> init(Allocator &alloc, std::initializer_list<T> init, size_t capacity = 0) noexcept {
      ensure(!head && !tail && !count, "ALREADY INITIALIZED");
      ensure(elements.head == nullptr && elements.size() == 0, "ALREADY INITIALIZED!");
      if (capacity < init.size()) {
        capacity = init.size();
      }
      capacity      = capacity ? capacity : 10;
      auto allocRes = alloc.create_many<T>(init.size());
      if (allocRes.is_error()) {
        return allocRes.error();
      }
 
      elements = *allocRes;
      for (const auto &elem: init) {
        (void) push_back(elem);
      }
 
      return success();
    }

    void deinit(Allocator &alloc) {
      if (elements.head) {
        alloc.destroy_many(elements);
        elements.head = nullptr;
      }
      elements.len = 0;
      head         = 0;
      tail         = 0;
      count        = 0;
    }

    const T &operator[](size_t i) const noexcept {
      ensure(elements.head, "NOT INITIALIZED");
      return at(i);
    }

    T &operator[](size_t i) noexcept {
      ensure(elements.head, "NOT INITIALIZED");
      return at(i);
    }

    [[nodiscard]] size_t size() const noexcept { return count; }
    [[nodiscard]] size_t capacity() const noexcept { return elements.size(); }

    [[nodiscard]] const T &at(size_t i) const noexcept {
      ensure(elements.head, "NOT INITIALIZED");
      ensure(i < count, "OUT OF BOUNDS ACCESS");
      auto index = i + head;
      if (index >= elements.size()) {
        index -= elements.size();
      }
      return elements[index];
    }

    T &at(size_t i) noexcept {
      ensure(elements.head, "NOT INITIALIZED");
      ensure(i < count, "OUT OF BOUNDS ACCESS");
      auto index = i + head;
      if (index >= elements.size()) {
        index -= elements.size();
      }
      return elements[index];
    }

    Result<void, AllocationError> push_back(Allocator &alloc, const T &elem) {
      ensure(elements.head, "NOT INITIALIZED");
      mtdefer { ensure(size() <= capacity(), "SIZE MISMATCH"); };
      if (auto err = grow_if_needed(alloc); err.is_error()) {
        return err;
      }
      if (push_back(elem).is_error()) {
        return error(AllocationError::ALLOCATION_FAILED);
      }
      return success();
    }

    Result<void, AllocationError> push_front(Allocator &alloc, const T &elem) {
      ensure(elements.head, "NOT INITIALIZED");
      mtdefer { ensure(size() <= capacity(), "SIZE MISMATCH"); };
      if (auto err = grow_if_needed(alloc); err.is_error()) {
        return err;
      }
      if (push_front(elem).is_error()) {
        return error(AllocationError::ALLOCATION_FAILED);
      }
      return success();
    }

    Result<void, CollectionAddNoAllocationError> push_back(const T &elem) {
      ensure(elements.head, "NOT INITIALIZED");
      mtdefer { ensure(size() <= capacity(), "SIZE MISMATCH"); };
      if (count >= elements.size()) {
        return error(CollectionAddNoAllocationError::NO_ROOM);
      }
 
      elements[tail++] = elem;
      count++;
      if (tail == elements.size()) {
        tail = 0;
      }
      return success();
    }
 
    Result<void, AllocationError> shrink_to_fit(Allocator &alloc) {
      const auto newSize = std::max(static_cast<size_t>(1), count);
      auto newBufferRes  = alloc.create_many<T>(newSize);
      if (newBufferRes.is_error()) {
        return newBufferRes.error();
      }
      auto newBuffer = *newBufferRes;
 
      for (size_t i = 0, curHead = head; i < newBuffer.size() && i < count; ++i) {
        mtdefer {
          curHead += 1;
          if (curHead == elements.size()) {
            curHead = 0;
          }
        };
        std::swap(newBuffer[i], elements[curHead]);
      }
      head  = 0;
      tail  = elements.size();
      count = tail - head;
      alloc.destroy_many(elements);
      elements = newBuffer;
      head     = 0;
      return success();
    }

    Result<void, CollectionAddNoAllocationError> push_front(const T &elem) {
      ensure(elements.head, "NOT INITIALIZED");
      mtdefer { ensure(size() <= capacity(), "SIZE MISMATCH"); };
      if (count >= elements.size()) {
        return error(CollectionAddNoAllocationError::NO_ROOM);
      }
 
      auto new_head = head;
      if (new_head == 0) {
        new_head = elements.size() - 1;
      }
      else {
        new_head--;
      }
      elements[new_head] = elem;
      count++;
      head = new_head;
      return success();
    }

    Optional<T> pop_front() {
      ensure(elements.head, "NOT INITIALIZED");
      mtdefer { ensure(size() <= capacity(), "SIZE MISMATCH"); };
      if (count == 0) {
        return nullopt;
      }
 
      auto &res = elements[head++];
 
      count--;
      if (head == elements.size()) {
        head = 0;
      }
      return Optional{std::move(res)};
    }

    Optional<T> pop_back() {
      ensure(elements.head, "NOT INITIALIZED");
      mtdefer { ensure(size() <= capacity(), "SIZE MISMATCH"); };
      if (count == 0) {
        return nullopt;
      }
 
      auto new_tail = tail;
      if (new_tail == 0) {
        new_tail = elements.size() - 1;
      }
      else {
        new_tail--;
      }
 
      auto res = elements[tail];
      --count;
      tail = new_tail;
      return res;
    }
 
  private:
    Result<void, AllocationError> grow_if_needed(Allocator &alloc) {
      ensure(elements.head, "NOT INITIALIZED");
      mtdefer { ensure(size() <= capacity(), "SIZE MISMATCH"); };
      if (count < elements.size()) {
        return success();
      }
 
      size_t newSize = elements.len + ((elements.len + 1) / 2);
      ensure(newSize > size(), "FAILED TO GROW RING BUFFER");
      auto newElemAllocRes = alloc.create_many<T>(newSize);
      if (newElemAllocRes.is_error()) {
        return newElemAllocRes.error();
      }
 
      auto newElems = *newElemAllocRes;
      for (size_t i = 0, curHead = head; i < elements.size(); ++i) {
        mtdefer {
          curHead += 1;
          if (curHead == elements.size()) {
            curHead = 0;
          }
        };
        std::swap(newElems[i], elements[curHead]);
      }
      head  = 0;
      tail  = elements.size();
      count = tail - head;
      alloc.destroy_many(elements);
      elements = newElems;
      return success();
    }
  };
 
  static_assert(is_mutable_addressable<RingBuffer<int>>, "RING BUFFER IS NOT MUTABLE ADDRESSABLE");

  template<typename T, size_t Capacity = 10>
  struct FixedRingBuffer {
  private:
    std::array<T, Capacity> elements;
    size_t head  = 0;
    size_t tail  = 0;
    size_t count = 0;
 
  public:
    using Elem = T;

    [[nodiscard]] decltype(auto) ptr_iter() noexcept { return iter::ptr(*this); }

    [[nodiscard]] decltype(auto) ptr_iter() const noexcept { return iter::const_ptr(*this); }

    [[nodiscard]] decltype(auto) iter() noexcept { return iter::val(*this); }

    void init() {};

    void init(std::initializer_list<T> list) {
      ensure(list.size() < Capacity, "TOO MANY ELEMENTS PROVIDED");
      for (const auto &e: list) {
        (void) push_back(e);
      }
    }

    [[nodiscard]] const T &operator[](size_t i) const noexcept { return at(i); }

    [[nodiscard]] T &operator[](size_t i) noexcept { return at(i); }

    [[nodiscard]] size_t size() const noexcept { return count; }

    [[nodiscard]] const T &at(size_t i) const noexcept {
      ensure(i < count, "OUT OF BOUNDS ACCESS");
      auto index = i + head;
      if (index >= elements.size()) {
        index -= elements.size();
      }
      return elements[index];
    }

    [[nodiscard]] T &at(size_t i) noexcept {
      ensure(i < count, "OUT OF BOUNDS ACCESS");
      auto index = i + head;
      if (index >= elements.size()) {
        index -= elements.size();
      }
      return elements[index];
    }

    [[nodiscard]] Result<void, CollectionAddNoAllocationError> push_back(const T &elem) {
      if (count >= elements.size()) {
        return error(CollectionAddNoAllocationError::NO_ROOM);
      }
 
      elements[tail++] = elem;
      count++;
      if (tail == elements.size()) {
        tail = 0;
      }
      return success();
    }

    [[nodiscard]] Result<void, CollectionAddNoAllocationError> push_front(const T &elem) {
      if (count >= elements.size()) {
        return error(CollectionAddNoAllocationError::NO_ROOM);
      }
 
      auto new_head = head;
      if (new_head == 0) {
        new_head = elements.size() - 1;
      }
      else {
        new_head--;
      }
      elements[new_head] = elem;
      count++;
      head = new_head;
      return success();
    }

    [[nodiscard]] Optional<T> pop_front() {
      if (count == 0) {
        return nullopt;
      }
 
      auto res = std::move(elements[head++]);
 
      count--;
      if (head == elements.size()) {
        head = 0;
      }
      return res;
    }

    [[nodiscard]] Optional<T> pop_back() {
      if (count == 0) {
        return nullopt;
      }
 
      auto new_tail = tail;
      if (new_tail == 0) {
        new_tail = elements.size() - 1;
      }
      else {
        new_tail--;
      }
 
      auto res = elements[tail];
      --count;
      tail = new_tail;
      return res;
    }
  };
 
  static_assert(is_mutable_addressable<RingBuffer<int>>, "RING BUFFER IS NOT MUTABLE ADDRESSABLE");
 
}  // namespace mtcore
 
#endif  // MTCORE_RING_BUFFER_HPP