implement first half of linked list dallocation

3 files changed, 47 insertions, 14 deletions

diff --git a/arch/x86_64/src/memory/heap/bump_allocator.cpp b/arch/x86_64/src/memory/heap/bump_allocator.cpp
index 8807645..bbf2021 100644
--- a/arch/x86_64/src/memory/heap/bump_allocator.cpp
+++ b/arch/x86_64/src/memory/heap/bump_allocator.cpp
@@ -42,7 +42,7 @@ namespace teachos::arch::memory::heap
     }
   }
 
-  auto bump_allocator::deallocate(uint8_t * pointer, std::size_t size) -> void
+  auto bump_allocator::deallocate(void * pointer, std::size_t size) -> void
   {
     if (pointer || size)
     {
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 a2a8c79..9b27f70 100644
--- a/arch/x86_64/src/memory/heap/linked_list_allocator.cpp
+++ b/arch/x86_64/src/memory/heap/linked_list_allocator.cpp
@@ -17,20 +17,24 @@ namespace teachos::arch::memory::heap
         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);
+    first = new (reinterpret_cast<void *>(heap_start)) memory_block(heap_size, nullptr);
   }
 
   auto linked_list_allocator::allocate(std::size_t size) -> void *
   {
+    exception_handling::assert(size < min_allocatable_size(),
+                               "[Linked List Allocator] Allocated memory cannot be smaller than 16 bytes");
+
     auto & previous = first;
     auto & current = first;
+
     while (current != nullptr)
     {
-      if (current->size > size)
+      if (current->size >= size + min_allocatable_size())
       {
-        return split_hole(current, size);
+        return split_free_memory_block(current, size);
       }
-      else if (current->size == size)
+      else if (current->size >= size)
       {
         if (previous != current)
         {
@@ -40,30 +44,59 @@ namespace teachos::arch::memory::heap
         {
           current = current->next;
         }
+
         delete current;
         return static_cast<void *>(current);
       }
+
       previous = current;
       current = current->next;
     }
     exception_handling::panic("[Linked List Allocator] Out of memory");
   }
 
-  auto linked_list_allocator::deallocate(uint8_t * pointer, std::size_t size) -> void
+  auto linked_list_allocator::deallocate(void * pointer, std::size_t size) -> void
   {
-    auto const deallocate_size = std::max(size, min_allocatable_size());
-    if (pointer || deallocate_size)
+    exception_handling::assert(size < min_allocatable_size(),
+                               "[Linked List Allocator] Allocated memory cannot be smaller than 16 bytes");
+
+    auto & previous = first;
+    auto & current = first;
+
+    while (current != nullptr)
     {
+      // if pointer + size < current
+      // create memory block
+      auto const previous_address = reinterpret_cast<std::size_t>(pointer);
+      auto const new_address = previous_address + size;
+
+      if (new_address != reinterpret_cast<std::size_t>(current) &&
+          previous_address != (reinterpret_cast<std::size_t>(previous) + previous->size))
+      {
+        auto new_block = new (pointer) memory_block(size, current);
+        previous->next = new_block;
+        return;
+      }
+
+      // elseif pointer + size == current
+      // combine memory block with current
+      // combine(previous, pointer, current)
+
+      previous = current;
+      current = current->next;
     }
   }
 
-  auto split_hole(memory_hole *& current_hole, std::size_t size) -> void *
+  auto linked_list_allocator::split_free_memory_block(memory_block *& current_block, std::size_t size) -> void *
   {
-    auto const previous_address = reinterpret_cast<std::size_t>(current_hole);
+    auto const previous_address = reinterpret_cast<std::size_t>(current_block);
     auto const new_address = previous_address + size;
-    current_hole =
-        new (reinterpret_cast<void *>(new_address)) memory_hole(current_hole->size - size, current_hole->next);
+    current_block =
+        new (reinterpret_cast<void *>(new_address)) memory_block(current_block->size - size, current_block->next);
     return reinterpret_cast<void *>(previous_address);
   }
 
+  // auto linked_list_allocator::combine_free_memory_block(memory_block *& previous_block, memory_block *&
+  // current_block, std::size_t size) -> void *
+
 }  // namespace teachos::arch::memory::heap
diff --git a/arch/x86_64/src/memory/heap/memory_hole.cpp b/arch/x86_64/src/memory/heap/memory_block.cpp
index 7590610..b68dd6d 100644
--- a/arch/x86_64/src/memory/heap/memory_hole.cpp
+++ b/arch/x86_64/src/memory/heap/memory_block.cpp
@@ -1,8 +1,8 @@
-#include "arch/memory/heap/memory_hole.hpp"
+#include "arch/memory/heap/memory_block.hpp"
 
 namespace teachos::arch::memory::heap
 {
-  memory_hole::memory_hole(std::size_t size, memory_hole * next)
+  memory_block::memory_block(std::size_t size, memory_block * next)
       : size(size)
       , next(next)
   {