diff options
Diffstat (limited to 'arch/x86_64/include')
| -rw-r--r-- | arch/x86_64/include/arch/memory/allocator/area_frame_allocator.hpp | 2 | ||||
| -rw-r--r-- | arch/x86_64/include/arch/memory/allocator/stack_frame_allocator.hpp | 67 | ||||
| -rw-r--r-- | arch/x86_64/include/arch/memory/heap/global_heap_allocator.hpp | 2 | ||||
| -rw-r--r-- | arch/x86_64/include/arch/stl/deque.hpp | 524 | ||||
| -rw-r--r-- | arch/x86_64/include/arch/stl/stack.hpp | 182 | ||||
| -rw-r--r-- | arch/x86_64/include/arch/stl/vector.hpp | 244 |
6 files changed, 927 insertions, 94 deletions
diff --git a/arch/x86_64/include/arch/memory/allocator/area_frame_allocator.hpp b/arch/x86_64/include/arch/memory/allocator/area_frame_allocator.hpp index b8370db..2244613 100644 --- a/arch/x86_64/include/arch/memory/allocator/area_frame_allocator.hpp +++ b/arch/x86_64/include/arch/memory/allocator/area_frame_allocator.hpp @@ -55,7 +55,7 @@ namespace teachos::arch::memory::allocator physical_frame next_free_frame; ///< The physical_frame after the last allocated one. std::optional<multiboot::memory_area> current_area; ///< The current memory area. multiboot::memory_area_container const - memory_areas; ///< All memory areas in custom container allows to use std::ranges + memory_areas; ///< All memory areas in custom container allows to use std::ranges. physical_frame const kernel_start; ///< The start address of the kernel code in memory. physical_frame const kernel_end; ///< The end address of the kernel code in memory. physical_frame const multiboot_start; ///< The start address of the multiboot code in memory. diff --git a/arch/x86_64/include/arch/memory/allocator/stack_frame_allocator.hpp b/arch/x86_64/include/arch/memory/allocator/stack_frame_allocator.hpp new file mode 100644 index 0000000..a8e7233 --- /dev/null +++ b/arch/x86_64/include/arch/memory/allocator/stack_frame_allocator.hpp @@ -0,0 +1,67 @@ +#ifndef TEACHOS_ARCH_X86_64_MEMORY_ALLOCATOR_STACK_FRAME_ALLOCATOR_HPP +#define TEACHOS_ARCH_X86_64_MEMORY_ALLOCATOR_STACK_FRAME_ALLOCATOR_HPP + +#include "arch/memory/allocator/physical_frame.hpp" +#include "arch/memory/multiboot/reader.hpp" +#include "arch/stl/stack.hpp" + +#include <optional> + +namespace teachos::arch::memory::allocator +{ + /** + * @brief Uses an internal stack-like dynamic structure to keep track of the address of all avaialable physical frames + * that are available using the memory areas read from the multiboot2 information pointer and simply pushes + * deallocated frames back onto the stack. Allows for constant speed O(1) allocation and deallocation + */ + struct stack_frame_allocator + { + /** + * @brief Constructor + * + * @param mem_info Structure containg all relevant information to map and allocate memory + */ + stack_frame_allocator(multiboot::memory_information const & mem_info); + + /** + * @brief Allocate memory by finding and returning a free physical frame. + * + * @return next free physical frame or nullopt if none was found. + */ + auto allocate_frame() -> std::optional<physical_frame>; + + /** + * @brief Deallocates a previously allocated physical frame. + * + * @param physical_frame Previously allocated physical_frame that should be deallocated. + */ + auto deallocate_frame(physical_frame const & physical_frame) -> void; + + private: + /** + * @brief Load all initally free physical frames from the current memory area into the underlying stack data + * structure so they can simply be accessed once required. Recallling the method will load all free physical frames + * from the next free memory area until there are no memory areas left. + */ + auto load_free_physical_frames() -> void; + + /** + * @brief Find the next memory area and write it into current_area. + */ + auto choose_next_area() -> void; + + stl::stack<physical_frame> free_frames; ///< All currently free physical frames in a LIFO (last-in, first-out) + ///< data structure. + physical_frame next_free_frame; ///< The physical_frame after the last allocated one. + std::optional<multiboot::memory_area> current_area; ///< The current memory area. + multiboot::memory_area_container const + memory_areas; ///< All memory areas in custom container allows to use std::ranges. + physical_frame const kernel_start; ///< The start address of the kernel code in memory. + physical_frame const kernel_end; ///< The end address of the kernel code in memory. + physical_frame const multiboot_start; ///< The start address of the multiboot code in memory. + physical_frame const multiboot_end; ///< The end address of the multiboot code in memory. + }; + +} // namespace teachos::arch::memory::allocator + +#endif // TEACHOS_ARCH_X86_64_MEMORY_ALLOCATOR_STACK_FRAME_ALLOCATOR_HPP diff --git a/arch/x86_64/include/arch/memory/heap/global_heap_allocator.hpp b/arch/x86_64/include/arch/memory/heap/global_heap_allocator.hpp index dff837e..772f171 100644 --- a/arch/x86_64/include/arch/memory/heap/global_heap_allocator.hpp +++ b/arch/x86_64/include/arch/memory/heap/global_heap_allocator.hpp @@ -16,7 +16,7 @@ namespace teachos::arch::memory::heap BUMP, ///< Use the bump allocator as the heap allocation implementation, be aware that using this allocator leaks ///< memory, because there is no delete implementation LINKED_LIST ///< Use the linked list allocator as the heap implementation, recommended because it does not leak - ///< memory and + ///< memory }; /** diff --git a/arch/x86_64/include/arch/stl/deque.hpp b/arch/x86_64/include/arch/stl/deque.hpp new file mode 100644 index 0000000..b4a3054 --- /dev/null +++ b/arch/x86_64/include/arch/stl/deque.hpp @@ -0,0 +1,524 @@ +#ifndef TEACHOS_ARCH_X86_64_STL_DEQUE_HPP +#define TEACHOS_ARCH_X86_64_STL_DEQUE_HPP + +#include "arch/exception_handling/panic.hpp" + +#include <algorithm> +#include <array> + +namespace teachos::arch::stl +{ + /** + * @brief Custom deque implementation mirroring the std::deque to allow for the usage of STL functionality with our + * custom memory management. + * + * @tparam T Element the deque instance should contain. + */ + template<typename T> + struct deque + { + 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 Deque block for the linked list, either added or removed if more or less space is required. + */ + struct block + { + std::array<value_type, 8U> data; ///< Data this block in the deque contains + block * next; ///< Optional pointer to the next free memory, holds nullptr if there is none. + }; + + /** + * @brief Default Constructor. + */ + deque() = default; + + /** + * @brief Constructs data with the given amount of elements containg the given value or alterantively the default + * constructed value. + * + * @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 deque(size_type n, value_type initial = value_type{}) + : _size(n) + , _capacity(n) + , _linked_list_start() + { + std::array<value_type, 8U> data{}; + std::ranges::fill_n(data, n, initial); + block block{data, nullptr}; + _linked_list_start = + █ // Taking reference to temporary, how would this be saved without causing issues later? + } + + /** + * @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 deque(InputIterator first, InputIterator last) + : _size(std::distance(first, last)) + , _capacity(std::distance(first, last)) + , _linked_list_start() + { + std::array<value_type, 8U> data{}; + stl::container<InputIterator> container{first, last}; + std::ranges::copy(container, data.begin()); + block block{data, nullptr}; + _linked_list_start = █ + } + + /** + * @brief Construct data by copying all elements from the initializer list. + * + * @param initalizer_list List we want to copy all elements from. + */ + explicit deque(std::initializer_list<value_type> initalizer_list) + : _size(initalizer_list.size()) + , _capacity(initalizer_list.size()) + , _data(new value_type[_capacity]{}) + { + std::ranges::copy(initalizer_list, _data); + } + + /** + * @brief Copy constructor. + * + * @note Allocates underlying data container with the same capacity as deque we are copying from and copies all + * elements from it. + * + * @param other Other instance of deque we want to copy the data from. + */ + deque(deque<value_type> const & other) + : _size(other._size) + , _capacity(other._capacity) + { + delete[] _data; + _data = new value_type[_capacity]{}; + std::ranges::copy(other, _data); + } + + /** + * @brief Copy assignment operator. + * + * @note Allocates underlying data container with the same capacity as deque we are copying from and copies all + * elements from it. + * + * @param other Other instance of deque we want to copy the data from. + * @return Newly created copy. + */ + deque<value_type> & operator=(deque<value_type> const & other) + { + delete[] _data; + _size = other._size; + _capacity = other._capacity; + _data = new value_type[_capacity]{}; + std::ranges::copy(other, _data); + return *this; + } + + /** + * @brief Destructor. + */ + ~deque() { delete[] _data; } + + /** + * @brief Amount of elements currently contained in this deque, will fill up until we have reached the capacity. If + * that is the case the capacity is increased automatically. + * + * @return Current amount of elements. + */ + auto size() const -> size_type { return _size; } + + /** + * @brief Amount of space the deque 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. + * + * @return Current amount of space the deque has for elements. + */ + 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. + * + * @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) const -> const_reference { return _data[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. + * + * @param index Index we want to access elements at. + * @return Reference to the underlying element. + */ + auto at(size_type index) -> reference + { + throw_if_out_of_range(index); + return this->operator[](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. + * + * @param index Index we want to access elements at. + * @return Reference to the underlying element. + */ + auto at(size_type index) const -> const_reference + { + 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. + * + * @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. + */ + template<class U> + auto push_back(U && value) -> void + { + increase_capacity_if_full(); + _data[_size] = std::forward<U>(value); + (void)_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 value_type& + */ + template<class... Args> + auto emplace_back(Args &&... args) -> value_type & + { + increase_capacity_if_full(); + _data[_size] = value_type{std::forward<Args>(args)...}; + auto const index = _size++; + 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. + */ + auto pop_back() -> void + { + throw_if_empty(); + (void)_size--; + } + + /** + * @brief Returns an iterator to the first element of the deque. + * If the deque is empty, the returned iterator will be equal to end(). + * + * @return Iterator to the first element. + */ + auto begin() noexcept -> pointer { return _data; } + + /** + * @brief Returns an iterator to the first element of the deque. + * If the deque is empty, the returned iterator will be equal to end(). + * + * @return Iterator to the first element. + */ + auto begin() const noexcept -> const_pointer { return _data; } + + /** + * @brief Returns an iterator to the first element of the deque. + * If the deque is empty, the returned iterator will be equal to end(). + * + * @return Iterator to the first element. + */ + auto cbegin() const noexcept -> const_pointer { return begin(); } + + /** + * @brief Returns a reverse iterator to the first element of the reversed deque. It corresponds to the last element + * of the non-reversed deque. If the deque is empty, the returned iterator will be equal to rend(). + * + * @return Reverse iterator to the first element. + */ + auto rbegin() noexcept -> pointer { return _data + _size - 1; } + + /** + * @brief Returns a reverse iterator to the first element of the reversed deque. It corresponds to the last element + * of the non-reversed deque. If the deque is empty, the returned iterator will be equal to rend(). + * + * @return Reverse iterator to the first element. + */ + auto rbegin() const noexcept -> const_pointer { return _data + _size - 1; } + + /** + * @brief Returns a reverse iterator to the first element of the reversed deque. It corresponds to the last element + * of the non-reversed deque. If the deque is empty, the returned iterator will be equal to rend(). + * + * @return Reverse iterator to the first element. + */ + auto crbegin() const noexcept -> const_pointer { return rbegin(); } + + /** + * @brief Returns an iterator to the element following the last element of the deque. This element acts as a + * placeholder, attempting to access it results in undefined behavior. + * + * @return Iterator to the element following the last element. + */ + auto end() noexcept -> pointer { return _data + _size; } + + /** + * @brief Returns an iterator to the element following the last element of the deque. This element acts as a + * placeholder, attempting to access it results in undefined behavior. + * + * @return Iterator to the element following the last element. + */ + auto end() const noexcept -> const_pointer { return _data + _size; } + + /** + * @brief Returns an iterator to the element following the last element of the deque. This element acts as a + * placeholder, attempting to access it results in undefined behavior. + * + * @return Iterator to the element following the last element. + */ + auto cend() const noexcept -> const_pointer { return end(); } + + /** + * @brief Returns a reverse iterator to the element following the last element of the reversed deque. It + * corresponds to the element preceding the first element of the non-reversed deque. This element acts as a + * placeholder, attempting to access it results in undefined behavior. + * + * @return Reverse iterator to the element following the last element. + */ + auto rend() noexcept -> pointer { return _data + size - 1; } + + /** + * @brief Returns a reverse iterator to the element following the last element of the reversed deque. It + * corresponds to the element preceding the first element of the non-reversed deque. This element acts as a + * placeholder, attempting to access it results in undefined behavior. + * + * @return Reverse iterator to the element following the last element. + */ + 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 deque. It + * corresponds to the element preceding the first element of the non-reversed deque. This element acts as a + * placeholder, attempting to access it results in undefined behavior. + * + * @return Reverse iterator to the element following the last element. + */ + 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 + * [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. + */ + auto data() -> pointer { 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. + */ + 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 + * undefined behavior. + * + * @return Reference to the first element. + */ + auto front() -> reference + { + throw_if_empty(); + 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. + */ + auto front() const -> const_reference + { + throw_if_empty(); + 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. + */ + auto back() -> reference + { + throw_if_empty(); + return *rbegin(); + } + + /** + * @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. + */ + auto back() const -> const_reference + { + throw_if_empty(); + return *rbegin(); + } + + /** + * @brief Increase the capacity of the deque (the total number of elements that the deque 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 deque. + * + * 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 deque 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 deque by reference and appends + * elements to it should usually not call reserve() on the deque, since it does not know of the deque'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 deque, in number of elements + */ + auto reserve(size_type new_capacity) -> void + { + if (new_capacity <= _capacity) + { + return; + } + + _capacity = new_capacity; + value_type * temp = new value_type[_capacity]{}; + stl::container<value_type *> container{begin(), end()}; + std::ranges::copy(container, temp); + delete[] _data; + _data = 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. + */ + auto shrink_to_fit() -> void + { + if (_size == _capacity) + { + return; + } + + _capacity = _size; + value_type * temp = new value_type[_capacity]{}; + stl::container<value_type *> container{begin(), end()}; + std::copy(container, temp); + delete[] _data; + _data = temp; + } + + /** + * @brief Wheter there are currently any items this container or not. + * + * @return True if there are no elements, false if there are. + */ + auto empty() const -> bool { return _size <= 0; } + + private: + /** + * @brief Halts the execution of the application if the data container is currently empty. + */ + auto throw_if_empty() const -> void + { + if (empty()) + { + exception_handling::panic("[Deque] Attempted to access element of currently empty deque"); + } + } + + auto throw_if_out_of_range(size_type index) const -> void + { + if (index >= _size) + { + exception_handling::panic("[Deque] 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 + * normally perferable for the cache. + */ + auto increase_capacity_if_full() -> void + { + if (_size == _capacity) + { + reserve(_capacity == 0U ? 1U : _capacity * 2U); + } + } + + size_type _size = {}; ///< Amount of elements in the underlying data container + size_type _capacity = {}; ///< Amount of space for elements in the underlying data container + block * _linked_list_start = {}; ///< Start pointer to the first element in the linked list + }; + +} // namespace teachos::arch::stl + +#endif // TEACHOS_ARCH_X86_64_STL_DEQUE_HPP diff --git a/arch/x86_64/include/arch/stl/stack.hpp b/arch/x86_64/include/arch/stl/stack.hpp new file mode 100644 index 0000000..316aacd --- /dev/null +++ b/arch/x86_64/include/arch/stl/stack.hpp @@ -0,0 +1,182 @@ +#ifndef TEACHOS_ARCH_X86_64_STL_STACK_HPP +#define TEACHOS_ARCH_X86_64_STL_STACK_HPP + +#include "arch/exception_handling/panic.hpp" +#include "arch/stl/deque.hpp" + +namespace teachos::arch::stl +{ + /** + * @brief Custom stack implementation mirroring the std::stack to allow for the usage of STL functionality with our + * 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::deque<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. + */ + stack() = default; + + /** + * @brief Constructs data with the given amount of elements containg the given value or alterantively the default + * constructed value. + * + * @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(size_type n, value_type initial = value_type{}) + : _container(n, initial) + { + // Nothing to do. + } + + /** + * @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 stack(InputIterator first, InputIterator last) + : _container(first, last) + { + // Nothing to do. + } + + /** + * @brief Construct data by copying all elements from the initializer list. + * + * @param initalizer_list List we want to copy all elements from. + */ + explicit stack(std::initializer_list<T> initalizer_list) + : _container(initalizer_list) + { + // Nothing to do. + } + + /** + * @brief Copy constructor. + * + * @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 stack we want to copy the data from. + */ + stack(stack<T> const & other) + : _container(other) + { + // Nothing to do. + } + + /** + * @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. + * + * @param other Other instance of vector we want to copy the data from. + * @return Newly created copy. + */ + stack<T> & operator=(stack<T> const & other) { _container = other; } + + /** + * @brief Destructor. + */ + ~stack() = default; + + /** + * @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. + * + * @return Current amount of elements. + */ + 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 + * undefined behavior. + * + * @return Reference to the last element. + */ + auto top() -> reference { return _container.back(); } + + /** + * @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. + */ + auto top() const -> const_reference { return _container.back(); } + + /** + * @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. 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. + */ + 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 + * 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. 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 value_type& + */ + template<class... Args> + auto emplace(Args &&... args) -> reference + { + _container.emplace_back(std::forward<Args>(args)...); + } + + /** + * @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. + */ + auto pop() -> void { _container.pop_back(); } + + /** + * @brief Wheter there are currently any items this container or not. + * + * @return True if there are no elements, false if there are. + */ + auto empty() const -> bool { return _container.empty(); } + + private: + container_type _container = {}; ///< Underlying container used by the stack to actually save the data. + }; + +} // namespace teachos::arch::stl + +#endif // TEACHOS_ARCH_X86_64_STL_STACK_HPP diff --git a/arch/x86_64/include/arch/stl/vector.hpp b/arch/x86_64/include/arch/stl/vector.hpp index f3d41fd..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}; |