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

3 files changed, 178 insertions, 65 deletions

diff --git a/arch/x86_64/include/arch/memory/multiboot/memory_map.hpp b/arch/x86_64/include/arch/memory/multiboot/memory_map.hpp
index 3801e57..f9c902a 100644
--- a/arch/x86_64/include/arch/memory/multiboot/memory_map.hpp
+++ b/arch/x86_64/include/arch/memory/multiboot/memory_map.hpp
@@ -3,6 +3,7 @@
 
 #include "info.hpp"
 #include <cstdint>
+#include <iterator>
 
 namespace teachos::arch::memory::multiboot
 {
@@ -44,10 +45,14 @@ namespace teachos::arch::memory::multiboot
   };
 
   /**
-   * @brief Iterator for memory areas.
+   * @brief Random access iterator for memory areas.
    */
   struct memory_area_iterator
   {
+    using iterator_category = std::random_access_iterator_tag;  ///< Iterator category of this type.
+    using difference_type = std::ptrdiff_t;  ///< Type when diving one instance of this iterator by another.
+    using value_type = memory_area;          ///< Underlying value pointed to by this iterator.
+
     /**
      * @brief Defaulted constructor.
      */
@@ -57,30 +62,86 @@ namespace teachos::arch::memory::multiboot
      * @brief Constructor.
      *
      * @param p Underlying address the iterator should point too, ensure to not pass an invalid pointer or the
-     * constructo will halt execution.
+     * constructor will halt execution.
      */
-    explicit memory_area_iterator(memory_area * p);
+    explicit memory_area_iterator(value_type * p);
 
     /**
      * @brief Dereferences the initally given pointer to its value.
      *
      * @return Reference to the value.
      */
-    memory_area & operator*() const;
+    auto operator*() const -> value_type &;
+
+    /**
+     * @brief Get underlying value, which is the intially passed pointer.
+     *
+     * @return Underlying value passed intially.
+     */
+    auto operator->() const -> value_type *;
 
     /**
      * @brief Post increment operator. Returns a copy of the value.
      *
      * @return Copy of the incremented underlying address.
      */
-    memory_area_iterator operator++(int);
+    auto operator++(int) -> memory_area_iterator;
 
     /**
      * @brief Pre increment operator. Returns a reference to the changed value.
      *
      * @return Reference to the incremented underlying address.
      */
-    memory_area_iterator & operator++();
+    auto operator++() -> memory_area_iterator &;
+
+    /**
+     * @brief Addition assignment operator. Returns a reference to the changed value.
+     *
+     * @param value Value we want to add to the underlying address.
+     * @return Reference to the changed underlying address.
+     */
+    auto operator+=(difference_type value) -> memory_area_iterator &;
+
+    /**
+     * @brief Subtraction assignment operator. Returns a reference to the changed value.
+     *
+     * @param value Value we want to subtract from the underlying address.
+     * @return Reference to the changed underlying address.
+     */
+    auto operator-=(difference_type value) -> memory_area_iterator &;
+
+    /**
+     * @brief Addition operator. Returns the changed value.
+     *
+     * @param value Value we want to add to a copy of the underlying address.
+     * @return Copy of underlying address incremented by the given value.
+     */
+    auto operator+(difference_type value) const -> memory_area_iterator;
+
+    /**
+     * @brief Subtraction operator. Returns the changed value.
+     *
+     * @param value Value we want to subtrcat from a copy of the underlying address.
+     * @return Copy of underlying address decremented by the given value.
+     */
+    auto operator-(difference_type value) const -> memory_area_iterator;
+
+    /**
+     * @brief Subtraction operator. Returns the size difference between two iterators.
+     *
+     * @param other Other iterator we want to substract the underlying address with ours.
+     * @return Size difference between the underlying address of this instance and the given iterator.
+     */
+    auto operator-(const memory_area_iterator & other) const -> difference_type;
+
+    /**
+     * @brief Index operator overload. Returns a reference to the value at the given index. Simply returns the
+     * dereferenced underlying pointer incremented by the given index.
+     *
+     * @param index Index we want to access and get the value from.
+     * @return Reference to the value at the given index.
+     */
+    auto operator[](difference_type index) const -> value_type &;
 
     /**
      * @brief Defaulted comparsion operator. Simply compares the memory address of both iterators.
@@ -88,10 +149,18 @@ namespace teachos::arch::memory::multiboot
      * @param other Other iterator to compare to.
      * @return Whether both iterators point to the same underlying address in memory.
      */
-    bool operator==(memory_area_iterator const & other) const = default;
+    auto operator==(memory_area_iterator const & other) const -> bool = default;
+
+    /**
+     * @brief Defaulted threeway comparsion operator. Simply compares the memory address of both iterators.
+     *
+     * @param other Other iterator to compare to.
+     * @return Whether the given iterator is smaller or larger than this iterator.
+     */
+    auto operator<=>(memory_area_iterator const & other) const -> std::strong_ordering = default;
 
   private:
-    memory_area * ptr;  ///< Underlying address the iterator is currently pointing too.
+    value_type * ptr;  ///< Underlying address the iterator is currently pointing too.
   };
 
   /**
@@ -100,13 +169,16 @@ namespace teachos::arch::memory::multiboot
    */
   struct memory_area_container
   {
+    using iterator = memory_area_iterator;  ///< Iterators used by this container.
+    using size_type = std::size_t;          ///< Maximum size of this container.
+
     /**
      * @brief Constructor.
      *
      * @param begin Pointer to the first memory area, will be used to construct the begin iterator.
      * @param size Amount of entries in the container we want to construct.
      */
-    memory_area_container(memory_area * begin, std::size_t size);
+    memory_area_container(memory_area_iterator::value_type * begin, size_type size);
 
     /**
      * @brief Returns the iterator pointing to the first element of the memory area.
@@ -114,7 +186,7 @@ namespace teachos::arch::memory::multiboot
      *
      * @return Iterator pointing to first element of the memory area.
      */
-    auto begin() const -> memory_area_iterator;
+    auto begin() const -> iterator;
 
     /**
      * @brief Returns the iterator pointing to one past the last element of the memory area.
@@ -122,11 +194,26 @@ namespace teachos::arch::memory::multiboot
      *
      * @return Iterator pointing to one past the last element of the memory area.
      */
-    auto end() const -> memory_area_iterator;
+    auto end() const -> iterator;
+
+    /**
+     * @brief Calculates the size of this container, simply subtracts the iterator pointing to the first element by the
+     * last.
+     *
+     * @return Actual size of this container.
+     */
+    auto size() const -> size_type;
+
+    /**
+     * @brief Calcualtes the size and returns true if the size is 0 and the container therefore emtpy.
+     *
+     * @return Whether the container is empty, size being 0 or not
+     */
+    auto empty() const -> bool;
 
   private:
-    memory_area_iterator area_begin;  ///< Pointer to the first element of all memory areas.
-    memory_area_iterator area_end;    ///< Pointer to one pas the last element of all memory areas.
+    iterator area_begin;  ///< Pointer to the first element of all memory areas.
+    iterator area_end;    ///< Pointer to one pas the last element of all memory areas.
   };
 }  // namespace teachos::arch::memory::multiboot
 
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