Start imlementation on actual algorithm

2 files changed, 36 insertions, 14 deletions

diff --git a/arch/x86_64/include/arch/memory/heap/linked_list_allocator.hpp b/arch/x86_64/include/arch/memory/heap/linked_list_allocator.hpp
index da7fc37..5f9a72b 100644
--- a/arch/x86_64/include/arch/memory/heap/linked_list_allocator.hpp
+++ b/arch/x86_64/include/arch/memory/heap/linked_list_allocator.hpp
@@ -52,15 +52,15 @@ namespace teachos::arch::memory::heap
      * for the allocation.
      *
      * @param current_hole Hole we want to split.
-     * @param new_hole New hole created by the split.
+     * @param size Size we want to allocate at the start of the hole.
      *
      * @return Address of the hole we just split.
      */
-    auto split_hole(memory_hole & current_hole, memory_hole *& new_hole) -> void *;
+    auto split_hole(memory_hole *& current_hole, std::size_t size) -> void *;
 
     std::size_t heap_start;  ///< Start of the allocatable heap area
     std::size_t heap_end;    ///< End of the allocatable heap area
-    memory_hole first;       ///< First free entry in our memory
+    memory_hole * first;     ///< First free entry in our memory
   };
 }  // namespace teachos::arch::memory::heap
 
diff --git a/arch/x86_64/src/memory/heap/linked_list_allocator.cpp b/arch/x86_64/src/memory/heap/linked_list_allocator.cpp
index 006d9c7..f4ba5e2 100644
--- a/arch/x86_64/src/memory/heap/linked_list_allocator.cpp
+++ b/arch/x86_64/src/memory/heap/linked_list_allocator.cpp
@@ -1,6 +1,7 @@
 #include "arch/memory/heap/linked_list_allocator.hpp"
 
 #include "arch/exception_handling/assert.hpp"
+#include "arch/exception_handling/panic.hpp"
 
 #include <algorithm>
 
@@ -9,19 +10,39 @@ namespace teachos::arch::memory::heap
   linked_list_allocator::linked_list_allocator(std::size_t heap_start, std::size_t heap_end)
       : heap_start(heap_start)
       , heap_end(heap_end)
-      , first(heap_end - heap_start, nullptr)
+      , first(nullptr)
   {
-    exception_handling::assert(heap_end - heap_start < min_allocatable_size(),
-                               "[Memory Hole List] Total heap size can not be smaller than minimum of 16 bytes to hold "
-                               "atleast one memory hole entry");
+    auto const heap_size = heap_end - heap_start;
+    exception_handling::assert(
+        heap_size < min_allocatable_size(),
+        "[Linked List Allocator] Total heap size can not be smaller than minimum of 16 bytes to hold "
+        "atleast one memory hole entry");
+    first = new (reinterpret_cast<void *>(heap_start)) memory_hole(heap_size, nullptr);
   }
 
   auto linked_list_allocator::allocate(std::size_t size) -> void *
   {
-    if (first.next == nullptr || size)
+    memory_hole * previous = nullptr;
+    auto current = first;
+    while (current != nullptr)
     {
+      if (current->size > size)
+      {
+        return split_hole(current, size);
+      }
+      else if (current->size == size)
+      {
+        if (previous != nullptr)
+        {
+          previous->next = current->next;
+        }
+        delete current;
+        return static_cast<void *>(current);
+      }
+      previous = current;
+      current = current->next;
     }
-    return nullptr;
+    exception_handling::panic("[Linked List Allocator] Out of memory");
   }
 
   auto linked_list_allocator::deallocate(uint8_t * pointer, std::size_t size) -> void
@@ -32,12 +53,13 @@ namespace teachos::arch::memory::heap
     }
   }
 
-  auto split_hole(memory_hole & current_hole, memory_hole *& new_hole) -> void *
+  auto split_hole(memory_hole *& current_hole, std::size_t size) -> void *
   {
-    if (new_hole)
-    {
-    }
-    return static_cast<void *>(&current_hole);
+    auto const previous_address = reinterpret_cast<std::size_t>(current_hole);
+    auto const new_address = previous_address + size;
+    current_hole =
+        new (reinterpret_cast<void *>(new_address)) memory_hole(current_hole->size - size, current_hole->next);
+    return reinterpret_cast<void *>(previous_address);
   }
 
 }  // namespace teachos::arch::memory::heap