Use container and C++20 range algorithms for allocator.

2 files changed, 78 insertions, 52 deletions

diff --git a/arch/x86_64/src/memory/allocator/area_frame_allocator.cpp b/arch/x86_64/src/memory/allocator/area_frame_allocator.cpp
index c3f77e1..d91b7f4 100644
--- a/arch/x86_64/src/memory/allocator/area_frame_allocator.cpp
+++ b/arch/x86_64/src/memory/allocator/area_frame_allocator.cpp
@@ -23,33 +23,21 @@ namespace teachos::arch::memory::allocator
   auto area_frame_allocator::choose_next_area() -> void
   {
     current_area = std::nullopt;
+    auto next_area_with_free_frames = memory_areas | std::views::filter([this](multiboot::memory_area const & area) {
+                                        auto address = area.base_address + area.area_length - 1;
+                                        return physical_frame::containing_address(address) >= next_free_frame;
+                                      });
 
-    /**auto filtered_areas = memory_areas | std::views::filter([this](multiboot::memory_area area) {
-                            auto address = area.base_address + area.area_length - 1;
-                            return physical_frame::containing_address(address) >= next_free_frame;
-                          });**/
+    auto lowest_area_with_free_frames =
+        std::ranges::min_element(next_area_with_free_frames, [](multiboot::memory_area a, multiboot::memory_area b) {
+          return a.base_address < b.base_address;
+        });
 
-    std::ranges::min_element(memory_areas, [](multiboot::memory_area a, multiboot::memory_area b) {
-      return a.base_address < b.base_address;
-    });
-
-    for (auto area : memory_areas)
-    {
-      std::size_t address = area.base_address + area.area_length - 1;
-      if (physical_frame::containing_address(address) >= next_free_frame)
-      {
-        // The `next_free_frame` address is smaller than the last address of the current area
-        if (!current_area || area.base_address < current_area->base_address)
-        {
-          current_area = area;
-        }
-      }
-    }
-
-    if (current_area)
+    if (lowest_area_with_free_frames != next_area_with_free_frames.end())
     {
+      current_area = *lowest_area_with_free_frames;
       // Update the `next_free_frame` according to the new memory area
-      physical_frame start_frame = physical_frame::containing_address(current_area->base_address);
+      auto start_frame = physical_frame::containing_address(current_area.value().base_address);
       if (next_free_frame < start_frame)
       {
         next_free_frame = start_frame;
@@ -63,36 +51,38 @@ namespace teachos::arch::memory::allocator
      * Only try to allocate memory if current_area is not null, because
      * the current_area is null if there is no more available memory.
      */
-    if (current_area)
+    if (!current_area)
     {
-      physical_frame physical_frame{next_free_frame.frame_number};
+      return std::nullopt;
+    }
 
-      struct physical_frame current_area_last_frame = {
-          physical_frame::containing_address(current_area->base_address + current_area->area_length - 1)};
+    auto address = current_area.value().base_address + current_area.value().area_length - 1;
+    physical_frame current_area_last_frame = physical_frame::containing_address(address);
 
-      if (next_free_frame > current_area_last_frame)
-      {
-        // All frames of current area are used, switch to next area
-        choose_next_area();
-      }
-      else if (physical_frame >= multiboot_start && physical_frame <= kernel_end)
-      {
-        // `physical_frame` is used by the kernel or multiboot information structure
-        next_free_frame = allocator::physical_frame{kernel_end.frame_number + 1};
-      }
-      else
-      {
-        // Frame is unused, increment `next_free_frame` and return it
-        next_free_frame.frame_number += 1;
-        return physical_frame;
-      }
-
-      // `physical_frame` was not valid, try it again with the updated `next_free_frame`
-      return allocate_frame();
+    if (next_free_frame > current_area_last_frame)
+    {
+      // All frames of current area are used, switch to next area.
+      choose_next_area();
+    }
+    else if (next_free_frame >= kernel_start && next_free_frame <= kernel_end)
+    {
+      // `physical_frame` is used by the kernel or multiboot information structure.
+      next_free_frame = allocator::physical_frame{kernel_end.frame_number + 1};
+    }
+    else if (next_free_frame >= multiboot_start && next_free_frame <= multiboot_end)
+    {
+      // `physical_frame` is used by the kernel or multiboot information structure.
+      next_free_frame = allocator::physical_frame{multiboot_end.frame_number + 1};
+    }
+    else
+    {
+      // Frame is unused, increment `next_free_frame` and return it.
+      next_free_frame.frame_number += 1;
+      return next_free_frame;
     }
 
-    // no free frames left
-    return std::nullopt;
+    // `physical_frame` was not valid, try it again with the updated `next_free_frame`.
+    return allocate_frame();
   }
 
   auto area_frame_allocator::deallocate_frame(physical_frame physical_frame) -> void
diff --git a/arch/x86_64/src/memory/multiboot/memory_map.cpp b/arch/x86_64/src/memory/multiboot/memory_map.cpp
index da7f05d..b5e2759 100644
--- a/arch/x86_64/src/memory/multiboot/memory_map.cpp
+++ b/arch/x86_64/src/memory/multiboot/memory_map.cpp
@@ -4,18 +4,21 @@
 
 namespace teachos::arch::memory::multiboot
 {
-  memory_area_iterator::memory_area_iterator(multiboot::memory_area * p)
+  memory_area_iterator::memory_area_iterator(value_type * p)
       : ptr(p)
   {
     exception_handling::assert(ptr, "[Memory Area] Attempted to pass nullptr as iterator");
   }
 
-  multiboot::memory_area & memory_area_iterator::operator*() const { return *ptr; }
+  auto memory_area_iterator::operator*() const -> value_type & { return *ptr; }
+
+  auto memory_area_iterator::operator->() const -> value_type * { return ptr; }
 
   auto memory_area_iterator::operator++(int) -> memory_area_iterator
   {
-    ++(*this);
-    return *this;
+    memory_area_iterator old_value = *this;
+    ++ptr;
+    return old_value;
   }
 
   auto memory_area_iterator::operator++() -> memory_area_iterator &
@@ -24,6 +27,35 @@ namespace teachos::arch::memory::multiboot
     return *this;
   }
 
+  auto memory_area_iterator::operator+=(difference_type value) -> memory_area_iterator &
+  {
+    ptr += value;
+    return *this;
+  }
+
+  auto memory_area_iterator::operator-=(difference_type value) -> memory_area_iterator &
+  {
+    ptr -= value;
+    return *this;
+  }
+
+  auto memory_area_iterator::operator+(difference_type value) const -> memory_area_iterator
+  {
+    return memory_area_iterator{ptr + value};
+  }
+
+  auto memory_area_iterator::operator-(difference_type value) const -> memory_area_iterator
+  {
+    return memory_area_iterator{ptr - value};
+  }
+
+  auto memory_area_iterator::operator-(const memory_area_iterator & other) const -> difference_type
+  {
+    return ptr - other.ptr;
+  }
+
+  auto memory_area_iterator::operator[](difference_type index) const -> value_type & { return *(ptr + index); }
+
   memory_area_container::memory_area_container(memory_area * begin, std::size_t size)
       : area_begin(begin)
       , area_end(begin + size)
@@ -34,4 +66,8 @@ namespace teachos::arch::memory::multiboot
   auto memory_area_container::begin() const -> multiboot::memory_area_iterator { return area_begin; }
 
   auto memory_area_container::end() const -> multiboot::memory_area_iterator { return area_end; }
+
+  auto memory_area_container::size() const -> size_type { return std::distance(begin(), end()); }
+
+  auto memory_area_container::empty() const -> bool { return size() == 0; }
 }  // namespace teachos::arch::memory::multiboot