Add more methods to vector to mimic stl interface partially.

3 files changed, 306 insertions, 86 deletions

diff --git a/arch/x86_64/include/arch/stl/shared_pointer.hpp b/arch/x86_64/include/arch/stl/shared_pointer.hpp
index 79a9f82..4a9dec5 100644
--- a/arch/x86_64/include/arch/stl/shared_pointer.hpp
+++ b/arch/x86_64/include/arch/stl/shared_pointer.hpp
@@ -1,6 +1,8 @@
 #ifndef TEACHOS_ARCH_X86_64_STL_SHARED_POINTER_HPP
 #define TEACHOS_ARCH_X86_64_STL_SHARED_POINTER_HPP
 
+#include <atomic>
+
 namespace teachos::arch::stl
 {
   template<typename T>
diff --git a/arch/x86_64/include/arch/stl/vector.hpp b/arch/x86_64/include/arch/stl/vector.hpp
index 62be704..5bebf62 100644
--- a/arch/x86_64/include/arch/stl/vector.hpp
+++ b/arch/x86_64/include/arch/stl/vector.hpp
@@ -2,190 +2,399 @@
 #define TEACHOS_ARCH_X86_64_STL_VECTOR_HPP
 
 #include "arch/exception_handling/panic.hpp"
-#include "arch/shared/container.hpp"
-#include "arch/shared/contiguous_pointer_iterator.hpp"
 
 #include <algorithm>
+#include <concepts>
 
 namespace teachos::arch::stl
 {
   /**
    * @brief Custom vector implementation mirroring the std::vector to allow for the usage of STL functionality with our
-   * custom memory management
+   * custom memory management.
    *
-   * @tparam T Element the vector instance should contain
+   * @tparam T Element the vector instance should contain.
    */
   template<typename T>
   struct vector
   {
     /**
-     * @brief Defaulted constructor. Initalizes empty vector
+     * @brief Defaulted constructor. Initalizes empty vector.
      */
     vector() = default;
 
     /**
      * @brief Constructs data with the given amount of elements containg the given value or alterantively the default
-     * constructed value
+     * constructed value.
      *
-     * @param capacity Amount of elements we want to create and set the given value for
-     * @param initial Inital value of all elements in the underlying data array
+     * @param capacity Amount of elements we want to create and set the given value for.
+     * @param initial Inital value of all elements in the underlying data array.
      */
-    vector(size_t capacity, T initial = T{})
-        : capacity(capacity)
-        , size(capacity)
-        , data(new T[capacity]{})
+    explicit vector(size_t capacity, T initial = T{})
+        : _size(capacity)
+        , _capacity(capacity)
+        , _data(new T[_capacity]{})
     {
-      auto const begin = data;
-      auto const end = data + size;
-      vector_container container{begin, end};
-      std::ranges::fill(container, inital);
+      std::ranges::fill(begin(), end(), initial);
     }
 
     /**
-     * @brief Copy constructor
+     * @brief Constructs data by copying all element from the given exclusive range.
+     *
+     * @tparam InputIterator Template that should have atleast input iterator characteristics.
+     * @param first Input iterator to the first element in the range we want to copy from.
+     * @param last Input iterator to one past the last element in the range we want to copy from.
+     */
+    template<typename InputIterator>
+    explicit vector(InputIterator first, InputIterator last)
+        : _size(std::distance(first, last))
+        , _capacity(std::distance(first, last))
+        , _data(new T[_capacity]{})
+    {
+      std::copy(first, last, _data);
+    }
+
+    /**
+     * @brief Construct data by copying all elements from the initializer list.
+     *
+     * @param initalizer_list List we want to copy all elements from.
+     */
+    explicit vector(std::initializer_list<T> initalizer_list)
+        : _size(initalizer_list.size())
+        , _capacity(initalizer_list.size())
+        , _data(new T[_capacity]{})
+    {
+      std::copy(initalizer_list.begin(), initalizer_list.end(), _data);
+    }
+
+    /**
+     * @brief Copy constructor.
      *
      * @note Allocates underlying data container with the same capacity as vector we are copying from and copies all
-     * elements from it
+     * elements from it.
      *
-     * @param other Other instance of vector we want to copy the data from
+     * @param other Other instance of vector we want to copy the data from.
      */
     vector(vector<T> const & other)
-        : size(size)
-        , capacity(capacity)
+        : _size(other._size)
+        , _capacity(other._capacity)
     {
-      delete[] data;
-      data = new T[capacity]{};
-
-      auto const begin = other.data;
-      auto const end = other.data + size;
-      vector_container container{begin, end};
-      std::ranges::copy(container, data);
+      delete[] _data;
+      _data = new T[_capacity]{};
+      std::copy(other.begin(), other.end(), _data);
     }
 
     /**
-     * @brief Copy assignment operator
+     * @brief Copy assignment operator.
      *
      * @note Allocates underlying data container with the same capacity as vector we are copying from and copies all
-     * elements from it
+     * elements from it.
      *
-     * @param other Other instance of vector we want to copy the data from
-     * @return Newly created copy
+     * @param other Other instance of vector we want to copy the data from.
+     * @return Newly created copy.
      */
     vector<T> & operator=(vector<T> const & other)
     {
-      delete[] data;
-      size = other.size();
-      capacity = other.capacity();
-      data = new T[capacity]{};
-
-      auto const begin = other.data;
-      auto const end = other.data + size;
-      vector_container container{begin, end};
-      std::ranges::copy(container, data);
+      delete[] _data;
+      _size = other._size;
+      _capacity = other._capacity;
+      _data = new T[_capacity]{};
+      std::copy(other.begin(), other.end(), _data);
       return *this;
     }
 
     /**
-     * @brief Destructor
+     * @brief Destructor.
      */
-    ~vector() { delete[] data; }
+    ~vector() { delete[] _data; }
 
     /**
      * @brief Amount of elements currently contained in this vector, will fill up until we have reached the capacity. If
-     * that is the case the capacity is increased automatically
+     * that is the case the capacity is increased automatically.
      *
-     * @return Current amount of elements
+     * @return Current amount of elements.
      */
-    size_t size() const { return size; }
+    size_t size() const { return _size; }
 
     /**
      * @brief Amount of space the vector currently has, can be different than the size, because we allocate more than we
-     * exactly require to decrease the amount of allocations and deallocation to improve speed
+     * exactly require to decrease the amount of allocations and deallocation to improve speed.
      *
-     * @return Current amount of space the vector has for elements
+     * @return Current amount of space the vector has for elements.
      */
-    size_t capacity() const { return capacity; }
+    size_t capacity() const { return _capacity; }
 
     /**
-     * @brief Array indexing operator. Allowing to access element at the given index
+     * @brief Array indexing operator. Allowing to access element at the given index.
      *
-     * @note Does not do any bounds checks use at() for that
+     * @note Does not do any bounds checks use at() for that.
      *
-     * @param index Index we want to access elements at
-     * @return Reference to the underlying element
+     * @param index Index we want to access elements at.
+     * @return Reference to the underlying element.
      */
-    T & operator[](size_t index) { return data[index]; }
+    T & operator[](size_t index) { return _data[index]; }
 
     /**
-     * @brief Array indexing operator. Allowing to access element at the given index
+     * @brief Array indexing operator. Allowing to access element at the given index.
      *
-     * @note Ensures we do not access element outside of the bounds of the array, if we do further execution is halted
+     * @note Ensures we do not access element outside of the bounds of the array, if we do further execution is halted.
      *
-     * @param index Index we want to access elements at
-     * @return Reference to the underlying element
+     * @param index Index we want to access elements at.
+     * @return Reference to the underlying element.
      */
     T & at(size_t index)
     {
-      if (index >= size)
+      if (index >= _size)
       {
         exception_handling::panic("[Vector] Attempted to read element at invalid index");
       }
-      return this->operator[](size);
+      return this->operator[](index);
     }
 
-    void push_back(T & const element) {}
+    /**
+     * @brief Appends the given element value to the end of the container. The new element is initalized as a copy of
+     * value.
+     *
+     * @note If after the operation the new size() is greater than old capacity() a reallocation takes place,
+     * in which case all iterators (including the end() iterator) and all references to the elements are invalidated.
+     * Otherwise only the end() iterator is invalidated.
+     *
+     * @param value The value of the element to append.
+     */
+    void push_back(T const & value)
+    {
+      _data[_size] = value;
+      _size++;
 
-    void emplace_back(T && const element)
+      if (_size == _capacity)
+      {
+        reserve(_capacity * 2);
+      }
+    }
+
+    /**
+     * @brief Appends the given element value to the end of the container. Value is moved into the new element.
+     *
+     * @note If after the operation the new size() is greater than old capacity() a reallocation takes place,
+     * in which case all iterators (including the end() iterator) and all references to the elements are invalidated.
+     * Otherwise only the end() iterator is invalidated.
+     *
+     * @param value The value of the element to append.
+     */
+    void push_back(T && value)
     {
-      // If no cacacity, increase capacity
-      if (size == capacity)
+      _data[_size] = std::move(value);
+      _size++;
+
+      if (_size == _capacity)
       {
-        reserve(capacity * 2);
+        reserve(_capacity * 2);
       }
+    }
 
-      data[size] = element;
-      size++;
+    /**
+     * @brief Appends a new element to the end of the container. The element is constructed through a constructor of the
+     * template type. The arguments args... are forwarded to the constructor as std::forward<Args>(args)....
+     *
+     * If after the operation the new size() is greater than old capacity() a reallocation takes place, in which case
+     * all iterators (including the end() iterator) and all references to the elements are invalidated. Otherwise only
+     * the end() iterator is invalidated.
+     *
+     * @tparam Args
+     * @param args Arguments to forward to the constructor of the element
+     * @return T&
+     */
+    template<class... Args>
+    auto emplace_back(Args &&... args) -> T &
+    {
+      _data[_size] = T{std::forward<Args>(args)...};
+      auto const index = _size++;
+
+      if (_size == _capacity)
+      {
+        reserve(_capacity * 2);
+      }
+      return _data[index];
     }
 
+    /**
+     * @brief Removes the last element of the container. Calling pop_back on an empty container results in halting the
+     * further execution. Iterators and references to the last element are invalidated. The end()
+     * iterator is also invalidated.
+     */
     void pop_back()
     {
-      if (size <= 0)
+      if (_size <= 0)
       {
         exception_handling::panic("[Vector] Attempted to pop back last element of already empty vector");
       }
-      size--;
+      _size--;
     }
 
-    T & front() { return *data; }
+    /**
+     * @brief Returns an iterator to the first element of the vector.
+     * If the vector is empty, the returned iterator will be equal to end().
+     *
+     * @return Iterator to the first element.
+     */
+    T * begin() noexcept { return _data; }
+
+    /**
+     * @brief Returns an iterator to the first element of the vector.
+     * If the vector is empty, the returned iterator will be equal to end().
+     *
+     * @return Iterator to the first element.
+     */
+    T const * begin() const noexcept { return _data; }
+
+    /**
+     * @brief Returns an iterator to the first element of the vector.
+     * If the vector is empty, the returned iterator will be equal to end().
+     *
+     * @return Iterator to the first element.
+     */
+    T const * cbegin() const noexcept { return begin(); }
+
+    /**
+     * @brief Returns an iterator to the element following the last element of the vector. This element acts as a
+     * placeholder, attempting to access it results in undefined behavior.
+     *
+     * @return Iterator to the element following the last element.
+     */
+    T * end() noexcept { return _data + _size; }
+
+    /**
+     * @brief Returns an iterator to the element following the last element of the vector. This element acts as a
+     * placeholder, attempting to access it results in undefined behavior.
+     *
+     * @return Iterator to the element following the last element.
+     */
+    T const * end() const noexcept { return _data + _size; }
+
+    /**
+     * @brief Returns an iterator to the element following the last element of the vector. This element acts as a
+     * placeholder, attempting to access it results in undefined behavior.
+     *
+     * @return Iterator to the element following the last element.
+     */
+    T const * cend() const noexcept { return end(); }
+
+    /**
+     * @brief Returns a pointer to the underlying array serving as element storage. The pointer is such that range
+     * [data(), data() + size()) is always a valid range, even if the container is empty (data() is not dereferenceable
+     * in that case).
+     *
+     * @return Pointer to the underlying element storage. For non-empty containers, the returned pointer compares equal
+     * to the address of the first element.
+     */
+    T * data() { return _data; }
+
+    /**
+     * @brief Returns a pointer to the underlying array serving as element storage. The pointer is such that range
+     * [data(), data() + size()) is always a valid range, even if the container is empty (data() is not dereferenceable
+     * in that case).
+     *
+     * @return Pointer to the underlying element storage. For non-empty containers, the returned pointer compares equal
+     * to the address of the first element.
+     */
+    T const * data() const { return _data; }
 
-    T & back() { return *(data + size); }
+    /**
+     * @brief Returns a reference to the first element in the container. Calling front on an empty container causes
+     * undefined behavior.
+     *
+     * @return Reference to the first element.
+     */
+    T & front() { return *begin(); }
+
+    /**
+     * @brief Returns a reference to the first element in the container. Calling front on an empty container causes
+     * undefined behavior.
+     *
+     * @return Reference to the first element.
+     */
+    T const & front() const { return *begin(); }
 
+    /**
+     * @brief Returns a reference to the last element in the container. Calling back on an empty container causes
+     * undefined behavior.
+     *
+     * @return Reference to the last element.
+     */
+    T & back() { return *end(); }
+
+    /**
+     * @brief Returns a reference to the last element in the container. Calling back on an empty container causes
+     * undefined behavior.
+     *
+     * @return Reference to the last element.
+     */
+    T const & back() const { return *end(); }
+
+    /**
+     * @brief Increase the capacity of the vector (the total number of elements that the vector can hold without
+     * requiring reallocation) to a value that's greater or equal to new_cap. If new_cap is greater than the current
+     * capacity(), new storage is allocated, otherwise the function does nothing.
+     *
+     * reserve() does not change the size of the vector.
+     *
+     * If new_cap is greater than capacity(), all iterators (including the end() iterator) and all references to the
+     * elements are invalidated. Otherwise, no iterators or references are invalidated.
+     *
+     * After a call to reserve(), insertions will not trigger reallocation unless the insertion would make the size of
+     * the vector greater than the value of capacity().
+     *
+     * @note Correctly using reserve() can prevent unnecessary reallocations, but inappropriate uses of reserve() (for
+     * instance, calling it before every push_back() call) may actually increase the number of reallocations (by causing
+     * the capacity to grow linearly rather than exponentially) and result in increased computational complexity and
+     * decreased performance. For example, a function that receives an arbitrary vector by reference and appends
+     * elements to it should usually not call reserve() on the vector, since it does not know of the vector's usage
+     * characteristics.
+     *
+     * When inserting a range, the range version of insert() is generally preferable as it preserves the correct
+     * capacity growth behavior, unlike reserve() followed by a series of push_back()s.
+     *
+     * reserve() cannot be used to reduce the capacity of the container; to that end shrink_to_fit() is provided.
+     *
+     * @param new_capacity New capacity of the vector, in number of elements
+     */
     void reserve(size_t new_capacity)
     {
-      if (new_capacity < size)
+      if (new_capacity <= _capacity)
       {
-        // Creating new array with less capacity than is required to keep all current elements makes no sense
         return;
       }
 
-      T * temp = new T[new_capacity];
+      _capacity = new_capacity;
+      T * temp = new T[_capacity]{};
+      std::copy(begin(), end(), temp);
+      delete[] _data;
+      _data = temp;
+    }
 
-      auto const begin = other.data;
-      auto const end = other.data + capacity;
-      vector_container container{begin, end};
-      std::ranges::copy(container, temp);
+    /**
+     * @brief Requests the removal of unused capacity. Meaning it requests to reduce capacity() to size().
+     *
+     * If reallocation occurs, all iterators (including the end() iterator) and all references to the elements are
+     * invalidated. If no reallocation occurs, no iterators or references are invalidated.
+     */
+    void shrink_to_fit()
+    {
+      if (_size == _capacity)
+      {
+        return;
+      }
 
-      delete[] data;
-      capacity = new_capacity;
-      data = temp;
+      _capacity = _size;
+      T * temp = new T[_capacity]{};
+      std::copy(begin(), end(), temp);
+      delete[] _data;
+      _data = temp;
     }
 
   private:
-    T * data = {};         ///< Pointer to the first element in the underlying data container
-    size_t capacity = {};  ///< Amount of space for elements in the underlying data container
-    size_t size = {};      ///< Amount of elements in the underlying data container
-
-    typedef shared::container<shared::contiguous_pointer_iterator<T>> vector_container;
+    size_t _size = {};      ///< Amount of elements in the underlying data container
+    size_t _capacity = {};  ///< Amount of space for elements in the underlying data container
+    T * _data = {};         ///< Pointer to the first element in the underlying data container
   };
 
 }  // namespace teachos::arch::stl
diff --git a/arch/x86_64/src/memory/main.cpp b/arch/x86_64/src/memory/main.cpp
index a6f91d9..08308db 100644
--- a/arch/x86_64/src/memory/main.cpp
+++ b/arch/x86_64/src/memory/main.cpp
@@ -7,6 +7,9 @@
 #include "arch/memory/heap/heap_allocator.hpp"
 #include "arch/memory/paging/active_page_table.hpp"
 #include "arch/memory/paging/kernel_mapper.hpp"
+#include "arch/stl/shared_pointer.hpp"
+#include "arch/stl/unique_pointer.hpp"
+#include "arch/stl/vector.hpp"
 
 namespace teachos::arch::memory
 {
@@ -49,5 +52,11 @@ namespace teachos::arch::memory
     remap_heap(allocator, active_table);
     video::vga::text::write("Heap remapping successful", video::vga::text::common_attributes::green_on_black);
     video::vga::text::newline();
+
+    auto test2 = stl::make_unique<int>(0);
+    auto test3 = stl::make_shared<int>(0);
+    if (test2 && test3)
+    {
+    }
   }
 }  // namespace teachos::arch::memory