From b8fd52b6b3a7f002cff58ff8da0313a684cb3ab4 Mon Sep 17 00:00:00 2001
From: Fabian Imhof <fabian.imhof@ost.ch>
Date: Sun, 1 Dec 2024 11:44:30 +0000
Subject: implement heap linked_list deallocate

---
 .../src/memory/heap/linked_list_allocator.cpp      | 64 +++++++++++++++-------
 1 file changed, 43 insertions(+), 21 deletions(-)

(limited to 'arch/x86_64/src/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 9b27f70..3330399 100644
--- a/arch/x86_64/src/memory/heap/linked_list_allocator.cpp
+++ b/arch/x86_64/src/memory/heap/linked_list_allocator.cpp
@@ -60,43 +60,65 @@ namespace teachos::arch::memory::heap
     exception_handling::assert(size < min_allocatable_size(),
                                "[Linked List Allocator] Allocated memory cannot be smaller than 16 bytes");
 
+    auto const start_address = reinterpret_cast<std::size_t>(pointer);
+    auto const end_address = start_address + size;
+
     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))
+      if (reinterpret_cast<std::size_t>(current) >= end_address)
       {
-        auto new_block = new (pointer) memory_block(size, current);
-        previous->next = new_block;
-        return;
+        break;
       }
 
-      // elseif pointer + size == current
-      // combine memory block with current
-      // combine(previous, pointer, current)
-
-      previous = current;
+      previous->next = current;
       current = current->next;
     }
+
+    coalesce_free_memory_block(previous, current, pointer, size);
   }
 
   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_block);
-    auto const new_address = previous_address + size;
+    auto const start_address = reinterpret_cast<std::size_t>(current_block);
+    auto const end_address = start_address + size;
     current_block =
-        new (reinterpret_cast<void *>(new_address)) memory_block(current_block->size - size, current_block->next);
-    return reinterpret_cast<void *>(previous_address);
+        new (reinterpret_cast<void *>(end_address)) memory_block(current_block->size - size, current_block->next);
+    return reinterpret_cast<void *>(start_address);
   }
 
-  // auto linked_list_allocator::combine_free_memory_block(memory_block *& previous_block, memory_block *&
-  // current_block, std::size_t size) -> void *
+  auto linked_list_allocator::coalesce_free_memory_block(memory_block *& previous_block, memory_block *& current_block,
+                                                         void * pointer, std::size_t size) -> void *
+  {
+    auto const start_address = reinterpret_cast<std::size_t>(pointer);
+    auto const end_address = start_address + size;
+
+    auto block_size = size;
+    auto new_block_address = pointer;
+    auto next_block = current_block;
+
+    // If free memory block after block to deallocate is adjacent
+    if (end_address == reinterpret_cast<std::size_t>(current_block))
+    {
+      block_size += current_block->size;
+      next_block = current_block->next;
+
+      delete current_block;
+    }
+
+    // If free memory block before block to deallocate is adjacent
+    if (start_address == (reinterpret_cast<std::size_t>(previous_block) + previous_block->size))
+    {
+      block_size += previous_block->size;
+
+      previous_block->size = block_size;
+      previous_block->next = next_block;
+      return;
+    }
+
+    new (reinterpret_cast<void *>(new_block_address)) memory_block(block_size, next_block);
+  }
 
 }  // namespace teachos::arch::memory::heap
-- 
cgit v1.2.3