kapi/memory: move buffered allocator

1 files changed, 138 insertions, 0 deletions

diff --git a/kapi/include/kapi/memory/buffered_allocator.hpp b/kapi/include/kapi/memory/buffered_allocator.hpp
new file mode 100644
index 0000000..49137c6
--- /dev/null
+++ b/kapi/include/kapi/memory/buffered_allocator.hpp
@@ -0,0 +1,138 @@
+#ifndef TEACHOS_KAPI_BUFFERED_ALLOCATOR_HPP
+#define TEACHOS_KAPI_BUFFERED_ALLOCATOR_HPP
+
+#include "kapi/memory.hpp"
+#include "kapi/system.hpp"
+
+#include <algorithm>
+#include <array>
+#include <cstddef>
+#include <optional>
+#include <utility>
+
+namespace kapi::memory
+{
+
+  template<std::size_t BufferSize>
+  struct buffered_allocator : frame_allocator
+  {
+    explicit buffered_allocator(frame_allocator * underlying)
+        : m_underlying{underlying}
+        , m_free{BufferSize}
+    {
+      auto from_underlying = m_underlying->allocate_many(BufferSize);
+      if (!from_underlying)
+      {
+        kapi::system::panic("[OS] Not enough frames available from underlying allocator.");
+      }
+      auto [first_frame, count] = *from_underlying;
+      std::ranges::generate_n(m_pool.begin(), count, [first_frame]() mutable { return first_frame++; });
+    }
+
+    buffered_allocator(buffered_allocator const &) = delete;
+    buffered_allocator(buffered_allocator && other) noexcept = delete;
+
+    ~buffered_allocator() override
+    {
+      std::ranges::for_each(m_pool, [this](auto const & maybe_frame) {
+        if (maybe_frame)
+        {
+          m_underlying->release_many({*maybe_frame, 1});
+        }
+      });
+    }
+
+    auto operator=(buffered_allocator const &) = delete;
+    auto operator=(buffered_allocator &&) = delete;
+
+    auto allocate_many(std::size_t count = 1) noexcept
+        -> std::optional<std::pair<kapi::memory::frame, std::size_t>> override
+    {
+      if (count > m_free)
+      {
+        return m_underlying->allocate_many(count);
+      }
+
+      auto start_of_set = std::ranges::find_if(m_pool, [](auto const & candidate) { return candidate.has_value(); });
+      if (start_of_set == m_pool.end())
+      {
+        return m_underlying->allocate_many(count);
+      }
+
+      if (std::distance(start_of_set, m_pool.end()) < static_cast<std::ptrdiff_t>(count))
+      {
+        return m_underlying->allocate_many(count);
+      }
+
+      auto number_of_consecutive_frames = 1uz;
+      for (auto current = std::next(start_of_set); current != m_pool.end() && number_of_consecutive_frames < count;
+           ++current)
+      {
+        if (*current && *start_of_set && **current == (**start_of_set) + 1)
+        {
+          ++number_of_consecutive_frames;
+          continue;
+        }
+        number_of_consecutive_frames = 0;
+        start_of_set = current;
+      }
+
+      if (std::distance(start_of_set, m_pool.end()) >= static_cast<std::ptrdiff_t>(count))
+      {
+        auto result = std::make_pair(**start_of_set, count);
+        m_free -= count;
+        std::ranges::for_each(start_of_set, start_of_set + count, [](auto & frame) { frame.reset(); });
+        sort_pool();
+        return result;
+      }
+      return m_underlying->allocate_many(count);
+    }
+
+    auto release_many(std::pair<kapi::memory::frame, std::size_t> frame_set) -> void override
+    {
+      if (m_free == BufferSize)
+      {
+        return m_underlying->release_many(frame_set);
+      }
+
+      auto [first_frame, count] = frame_set;
+      auto start_of_set = std::ranges::find_if(m_pool, [](auto const & candidate) { return !candidate.has_value(); });
+
+      for (auto current = start_of_set; current != m_pool.end() && count; ++current)
+      {
+        *current = first_frame++;
+        ++m_free;
+        --count;
+      }
+      sort_pool();
+
+      if (count)
+      {
+        m_underlying->release_many({first_frame, count});
+      }
+    }
+
+  private:
+    auto sort_pool() -> void
+    {
+      std::ranges::sort(m_pool, [](auto lhs, auto rhs) -> bool {
+        if (lhs && rhs)
+        {
+          return *lhs < *rhs;
+        }
+        if (!lhs)
+        {
+          return false;
+        }
+        return true;
+      });
+    }
+
+    frame_allocator * m_underlying;
+    std::size_t m_free;
+    std::array<std::optional<kapi::memory::frame>, BufferSize> m_pool{};
+  };
+
+}  // namespace kapi::memory
+
+#endif
\ No newline at end of file