From 051307f49f4cdfb86c527a475ab21feea4a664d7 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Matteo=20Gm=C3=BCr?= Date: Tue, 4 Mar 2025 18:01:49 +0000 Subject: Add more methods to vector to mimic stl interface partially. --- arch/x86_64/include/arch/stl/shared_pointer.hpp | 2 + arch/x86_64/include/arch/stl/vector.hpp | 381 ++++++++++++++++++------ arch/x86_64/src/memory/main.cpp | 9 + 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 + namespace teachos::arch::stl { template 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 +#include 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 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 + 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 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 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 & operator=(vector 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).... + * + * 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 + auto emplace_back(Args &&... args) -> T & + { + _data[_size] = T{std::forward(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> 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(0); + auto test3 = stl::make_shared(0); + if (test2 && test3) + { + } } } // namespace teachos::arch::memory -- cgit v1.2.3