diff options
Diffstat (limited to 'arch')
| -rw-r--r-- | arch/x86_64/include/arch/stl/stack.hpp | 67 | ||||
| -rw-r--r-- | arch/x86_64/include/arch/stl/vector.hpp | 174 |
2 files changed, 136 insertions, 105 deletions
diff --git a/arch/x86_64/include/arch/stl/stack.hpp b/arch/x86_64/include/arch/stl/stack.hpp index c78a25e..9ecf0ca 100644 --- a/arch/x86_64/include/arch/stl/stack.hpp +++ b/arch/x86_64/include/arch/stl/stack.hpp @@ -4,9 +4,6 @@ #include "arch/exception_handling/panic.hpp" #include "arch/stl/vector.hpp" -#include <algorithm> -#include <concepts> - namespace teachos::arch::stl { /** @@ -14,10 +11,18 @@ namespace teachos::arch::stl * custom memory management. * * @tparam T Element the stack instance should contain. + * @tparam Container Actual underlying container that should be wrapped to provide stack functionality. Requires + * access to pop_back(), push_back(), back(), size(), empty() and emplace_back() */ template<typename T, typename Container = stl::vector<T>> struct stack { + using container_type = Container; ///< Type of the underlying container used to implement stack-like interface. + using value_type = Container::value_type; ///< Type of the elements contained in the underlying container. + using size_type = Container::size_type; ///< Type of the size in the underlying container. + using reference = Container::reference; ///< Type of reference to the elements. + using const_reference = Container::const_reference; ///< Type of constant reference to the elements. + /** * @brief Default Constructor. */ @@ -27,11 +32,11 @@ namespace teachos::arch::stl * @brief Constructs data with the given amount of elements containg the given value or alterantively the default * constructed value. * - * @param capacity Amount of elements we want to create and set the given value for. + * @param n 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. */ - explicit stack(std::size_t capacity, T initial = T{}) - : _container(capacity, initial) + explicit stack(size_type n, value_type initial = value_type{}) + : _container(n, initial) { // Nothing to do. } @@ -64,10 +69,10 @@ namespace teachos::arch::stl /** * @brief Copy constructor. * - * @note Allocates underlying data container with the same capacity as vector we are copying from and copies all + * @note Allocates underlying data container with the same capacity as stack we are copying from and copies all * elements from it. * - * @param other Other instance of vector we want to copy the data from. + * @param other Other instance of stack we want to copy the data from. */ stack(stack<T> const & other) : _container(other) @@ -97,7 +102,7 @@ namespace teachos::arch::stl * * @return Current amount of elements. */ - std::size_t size() const { return _container.size(); } + auto size() const -> size_type { return _container.size(); } /** * @brief Returns a reference to the last element in the container. Calling back on an empty container causes @@ -105,7 +110,7 @@ namespace teachos::arch::stl * * @return Reference to the last element. */ - T & top() { return _container.back(); } + auto top() -> reference { return _container.back(); } /** * @brief Returns a reference to the last element in the container. Calling back on an empty container causes @@ -113,30 +118,25 @@ namespace teachos::arch::stl * * @return Reference to the last element. */ - T const & top() const { return _container.back(); } + auto top() const -> const_reference { return _container.back(); } /** - * @brief Appends the given element value to the end of the container. The new element is initalized as a copy of - * value. + * @brief Appends the given element value to the end of the container. The element is assigned through the + * assignment operator of the template type. The value is forwarded to the constructor as + * std::forward<U>(value), meaning it is either moved (rvalue) or copied (lvalue). * * @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. + * Otherwise only the end() iterator is invalidated. Uses a forward reference for the actual value passed, which + * allows the template method to be used by both lvalue and rvalues and compile a different implementation. * * @param value The value of the element to append. */ - void push(T const & value) { _container.push_back(value); } - - /** - * @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(T && value) { _container.push_back(std::move(value)); } + template<class U> + auto push(U && value) -> void + { + _container.push_back(std::forward<U>(value)); + } /** * @brief Appends a new element to the end of the container. The element is constructed through a constructor of the @@ -144,24 +144,27 @@ namespace teachos::arch::stl * * 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. + * the end() iterator is invalidated. Uses a forward reference for the actual value passed, which + * allows the template method to be used by both lvalue and rvalues and compile a different implementation. * * @tparam Args * @param args Arguments to forward to the constructor of the element - * @return T& + * @return value_type& */ template<class... Args> - auto emplace(Args &&... args) -> T & + auto emplace(Args &&... args) -> reference { _container.emplace_back(std::forward<Args>(args)...); } /** - * @brief Removes the last element of the container. Calling pop_back on an empty container results in halting the + * @brief Removes the last element of the container. + * + * @note 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() { _container.pop_back(); } + auto pop() -> void { _container.pop_back(); } /** * @brief Wheter there are currently any items this container or not. @@ -171,7 +174,7 @@ namespace teachos::arch::stl auto empty() const -> bool { return _container.empty(); } private: - Container _container = {}; ///< Underlying container used by the stack to actually save the data. + container_type _container = {}; ///< Underlying container used by the stack to actually save the data. }; } // namespace teachos::arch::stl diff --git a/arch/x86_64/include/arch/stl/vector.hpp b/arch/x86_64/include/arch/stl/vector.hpp index e14f2c9..c7d7853 100644 --- a/arch/x86_64/include/arch/stl/vector.hpp +++ b/arch/x86_64/include/arch/stl/vector.hpp @@ -2,9 +2,10 @@ #define TEACHOS_ARCH_X86_64_STL_VECTOR_HPP #include "arch/exception_handling/panic.hpp" +#include "arch/stl/container.hpp" +#include "arch/stl/contiguous_pointer_iterator.hpp" #include <algorithm> -#include <concepts> namespace teachos::arch::stl { @@ -17,6 +18,13 @@ namespace teachos::arch::stl template<typename T> struct vector { + using value_type = T; ///< Type of the elements contained in the container. + using size_type = std::size_t; ///< Type of the size in the container. + using reference = value_type &; ///< Type of reference to the elements. + using const_reference = value_type const &; ///< Type of constant reference to the elements. + using pointer = value_type *; ///< Type of pointer to the elements. + using const_pointer = value_type const *; ///< Type of constant pointer to the elements. + /** * @brief Default Constructor. */ @@ -26,15 +34,15 @@ namespace teachos::arch::stl * @brief Constructs data with the given amount of elements containg the given value or alterantively the default * constructed value. * - * @param capacity Amount of elements we want to create and set the given value for. + * @param n 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. */ - explicit vector(std::size_t capacity, T initial = T{}) - : _size(capacity) - , _capacity(capacity) - , _data(new T[_capacity]{}) + explicit vector(size_type n, value_type initial = value_type{}) + : _size(n) + , _capacity(n) + , _data(new value_type[_capacity]{}) { - std::ranges::fill(begin(), end(), initial); + std::ranges::fill(*this, initial); } /** @@ -48,9 +56,10 @@ namespace teachos::arch::stl explicit vector(InputIterator first, InputIterator last) : _size(std::distance(first, last)) , _capacity(std::distance(first, last)) - , _data(new T[_capacity]{}) + , _data(new value_type[_capacity]{}) { - std::copy(first, last, _data); + stl::container<InputIterator> container{first, last}; + std::ranges::copy(container, _data); } /** @@ -58,12 +67,12 @@ namespace teachos::arch::stl * * @param initalizer_list List we want to copy all elements from. */ - explicit vector(std::initializer_list<T> initalizer_list) + explicit vector(std::initializer_list<value_type> initalizer_list) : _size(initalizer_list.size()) , _capacity(initalizer_list.size()) - , _data(new T[_capacity]{}) + , _data(new value_type[_capacity]{}) { - std::copy(initalizer_list.begin(), initalizer_list.end(), _data); + std::ranges::copy(initalizer_list, _data); } /** @@ -74,13 +83,13 @@ namespace teachos::arch::stl * * @param other Other instance of vector we want to copy the data from. */ - vector(vector<T> const & other) + vector(vector<value_type> const & other) : _size(other._size) , _capacity(other._capacity) { delete[] _data; - _data = new T[_capacity]{}; - std::copy(other.begin(), other.end(), _data); + _data = new value_type[_capacity]{}; + std::ranges::copy(other, _data); } /** @@ -92,13 +101,13 @@ namespace teachos::arch::stl * @param other Other instance of vector we want to copy the data from. * @return Newly created copy. */ - vector<T> & operator=(vector<T> const & other) + vector<value_type> & operator=(vector<value_type> const & other) { delete[] _data; _size = other._size; _capacity = other._capacity; - _data = new T[_capacity]{}; - std::copy(other.begin(), other.end(), _data); + _data = new value_type[_capacity]{}; + std::ranges::copy(other, _data); return *this; } @@ -113,7 +122,7 @@ namespace teachos::arch::stl * * @return Current amount of elements. */ - std::size_t size() const { return _size; } + auto size() const -> size_type { return _size; } /** * @brief Amount of space the vector currently has, can be different than the size, because we allocate more than we @@ -121,7 +130,17 @@ namespace teachos::arch::stl * * @return Current amount of space the vector has for elements. */ - std::size_t capacity() const { return _capacity; } + auto capacity() const -> size_type { return _capacity; } + + /** + * @brief Array indexing operator. Allowing to access element at the given index. + * + * @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. + */ + auto operator[](size_type index) -> reference { return _data[index]; } /** * @brief Array indexing operator. Allowing to access element at the given index. @@ -131,7 +150,7 @@ namespace teachos::arch::stl * @param index Index we want to access elements at. * @return Reference to the underlying element. */ - T & operator[](std::size_t index) { return _data[index]; } + auto operator[](size_type index) const -> const_reference { return _data[index]; } /** * @brief Array indexing operator. Allowing to access element at the given index. @@ -141,46 +160,44 @@ namespace teachos::arch::stl * @param index Index we want to access elements at. * @return Reference to the underlying element. */ - T & at(std::size_t index) + auto at(size_type index) -> reference { - if (index >= _size) - { - exception_handling::panic("[Vector] Attempted to read element at invalid index"); - } + throw_if_out_of_range(index); return this->operator[](index); } /** - * @brief Appends the given element value to the end of the container. The new element is initalized as a copy of - * value. + * @brief Array indexing operator. Allowing to access element at the given index. * - * @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. + * @note Ensures we do not access element outside of the bounds of the array, if we do further execution is halted. * - * @param value The value of the element to append. + * @param index Index we want to access elements at. + * @return Reference to the underlying element. */ - void push_back(T const & value) + auto at(size_type index) const -> const_reference { - increase_capacity_if_full(); - _data[_size] = value; - (void)_size++; + throw_if_out_of_range(index); + return this->operator[](index); } /** - * @brief Appends the given element value to the end of the container. Value is moved into the new element. + * @brief Appends the given element value to the end of the container. The element is assigned through the + * assignment operator of the template type. The value is forwarded to the constructor as + * std::forward<U>(value), meaning it is either moved (rvalue) or copied (lvalue). * * @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. + * Otherwise only the end() iterator is invalidated. Uses a forward reference for the actual value passed, which + * allows the template method to be used by both lvalue and rvalues and compile a different implementation. * * @param value The value of the element to append. */ - void push_back(T && value) + template<class U> + auto push_back(U && value) -> void { increase_capacity_if_full(); - _data[_size] = std::move(value); - _size++; + _data[_size] = std::forward<U>(value); + (void)_size++; } /** @@ -189,17 +206,18 @@ namespace teachos::arch::stl * * 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. + * the end() iterator is invalidated. Uses a forward reference for the actual value passed, which + * allows the template method to be used by both lvalue and rvalues and compile a different implementation. * * @tparam Args * @param args Arguments to forward to the constructor of the element - * @return T& + * @return value_type& */ template<class... Args> - auto emplace_back(Args &&... args) -> T & + auto emplace_back(Args &&... args) -> value_type & { increase_capacity_if_full(); - _data[_size] = T{std::forward<Args>(args)...}; + _data[_size] = value_type{std::forward<Args>(args)...}; auto const index = _size++; return _data[index]; } @@ -209,7 +227,7 @@ namespace teachos::arch::stl * further execution. Iterators and references to the last element are invalidated. The end() * iterator is also invalidated. */ - void pop_back() + auto pop_back() -> void { throw_if_empty(); (void)_size--; @@ -221,7 +239,7 @@ namespace teachos::arch::stl * * @return Iterator to the first element. */ - T * begin() noexcept { return _data; } + auto begin() noexcept -> pointer { return _data; } /** * @brief Returns an iterator to the first element of the vector. @@ -229,7 +247,7 @@ namespace teachos::arch::stl * * @return Iterator to the first element. */ - T const * begin() const noexcept { return _data; } + auto begin() const noexcept -> const_pointer { return _data; } /** * @brief Returns an iterator to the first element of the vector. @@ -237,7 +255,7 @@ namespace teachos::arch::stl * * @return Iterator to the first element. */ - T const * cbegin() const noexcept { return begin(); } + auto cbegin() const noexcept -> const_pointer { return begin(); } /** * @brief Returns a reverse iterator to the first element of the reversed vector. It corresponds to the last element @@ -245,7 +263,7 @@ namespace teachos::arch::stl * * @return Reverse iterator to the first element. */ - T * rbegin() noexcept { return _data + _size - 1; } + auto rbegin() noexcept -> pointer { return _data + _size - 1; } /** * @brief Returns a reverse iterator to the first element of the reversed vector. It corresponds to the last element @@ -253,7 +271,7 @@ namespace teachos::arch::stl * * @return Reverse iterator to the first element. */ - T const * rbegin() const noexcept { return _data + _size - 1; } + auto rbegin() const noexcept -> const_pointer { return _data + _size - 1; } /** * @brief Returns a reverse iterator to the first element of the reversed vector. It corresponds to the last element @@ -261,7 +279,7 @@ namespace teachos::arch::stl * * @return Reverse iterator to the first element. */ - T const * crbegin() const noexcept { return rbegin(); } + auto crbegin() const noexcept -> const_pointer { return rbegin(); } /** * @brief Returns an iterator to the element following the last element of the vector. This element acts as a @@ -269,7 +287,7 @@ namespace teachos::arch::stl * * @return Iterator to the element following the last element. */ - T * end() noexcept { return _data + _size; } + auto end() noexcept -> pointer { return _data + _size; } /** * @brief Returns an iterator to the element following the last element of the vector. This element acts as a @@ -277,7 +295,7 @@ namespace teachos::arch::stl * * @return Iterator to the element following the last element. */ - T const * end() const noexcept { return _data + _size; } + auto end() const noexcept -> const_pointer { return _data + _size; } /** * @brief Returns an iterator to the element following the last element of the vector. This element acts as a @@ -285,7 +303,7 @@ namespace teachos::arch::stl * * @return Iterator to the element following the last element. */ - T const * cend() const noexcept { return end(); } + auto cend() const noexcept -> const_pointer { return end(); } /** * @brief Returns a reverse iterator to the element following the last element of the reversed vector. It @@ -294,7 +312,7 @@ namespace teachos::arch::stl * * @return Reverse iterator to the element following the last element. */ - T * rend() noexcept { return _data + size - 1; } + auto rend() noexcept -> pointer { return _data + size - 1; } /** * @brief Returns a reverse iterator to the element following the last element of the reversed vector. It @@ -303,7 +321,7 @@ namespace teachos::arch::stl * * @return Reverse iterator to the element following the last element. */ - T const * rend() const noexcept { return _data + size - 1; } + auto rend() const noexcept -> const_pointer { return _data + size - 1; } /** * @brief Returns a reverse iterator to the element following the last element of the reversed vector. It @@ -312,7 +330,7 @@ namespace teachos::arch::stl * * @return Reverse iterator to the element following the last element. */ - T const * crend() const noexcept { return rbegin(); } + auto crend() const noexcept -> const_pointer { return rbegin(); } /** * @brief Returns a pointer to the underlying array serving as element storage. The pointer is such that range @@ -322,7 +340,7 @@ namespace teachos::arch::stl * @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; } + auto data() -> pointer { return _data; } /** * @brief Returns a pointer to the underlying array serving as element storage. The pointer is such that range @@ -332,7 +350,7 @@ namespace teachos::arch::stl * @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; } + auto data() const -> const_pointer { return _data; } /** * @brief Returns a reference to the first element in the container. Calling front on an empty container causes @@ -340,7 +358,7 @@ namespace teachos::arch::stl * * @return Reference to the first element. */ - T & front() + auto front() -> reference { throw_if_empty(); return *begin(); @@ -352,7 +370,7 @@ namespace teachos::arch::stl * * @return Reference to the first element. */ - T const & front() const + auto front() const -> const_reference { throw_if_empty(); return *begin(); @@ -364,7 +382,7 @@ namespace teachos::arch::stl * * @return Reference to the last element. */ - T & back() + auto back() -> reference { throw_if_empty(); return *rbegin(); @@ -376,7 +394,7 @@ namespace teachos::arch::stl * * @return Reference to the last element. */ - T const & back() const + auto back() const -> const_reference { throw_if_empty(); return *rbegin(); @@ -409,7 +427,7 @@ namespace teachos::arch::stl * * @param new_capacity New capacity of the vector, in number of elements */ - void reserve(std::size_t new_capacity) + auto reserve(size_type new_capacity) -> void { if (new_capacity <= _capacity) { @@ -417,8 +435,9 @@ namespace teachos::arch::stl } _capacity = new_capacity; - T * temp = new T[_capacity]{}; - std::copy(begin(), end(), temp); + value_type * temp = new value_type[_capacity]{}; + stl::container<value_type *> container{begin(), end()}; + std::ranges::copy(container, temp); delete[] _data; _data = temp; } @@ -429,7 +448,7 @@ namespace teachos::arch::stl * 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() + auto shrink_to_fit() -> void { if (_size == _capacity) { @@ -437,8 +456,9 @@ namespace teachos::arch::stl } _capacity = _size; - T * temp = new T[_capacity]{}; - std::copy(begin(), end(), temp); + value_type * temp = new value_type[_capacity]{}; + stl::container<value_type *> container{begin(), end()}; + std::copy(container, temp); delete[] _data; _data = temp; } @@ -462,6 +482,14 @@ namespace teachos::arch::stl } } + auto throw_if_out_of_range(size_type index) const -> void + { + if (index >= _size) + { + exception_handling::panic("[Vector] Attempted to read element at invalid index"); + } + } + /** * @brief Increases the internal capacity to 1 if it was previously 0 and to * 2 after that, meaning exponential * growth. This is done to decrease the amount of single allocations done and because a power of 2 in memory size is @@ -475,9 +503,9 @@ namespace teachos::arch::stl } } - std::size_t _size = {}; ///< Amount of elements in the underlying data container - std::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 + size_type _size = {}; ///< Amount of elements in the underlying data container + size_type _capacity = {}; ///< Amount of space for elements in the underlying data container + value_type * _data = {}; ///< Pointer to the first element in the underlying data container }; } // namespace teachos::arch::stl |