aboutsummaryrefslogtreecommitdiff
path: root/arch/x86_64
diff options
context:
space:
mode:
Diffstat (limited to 'arch/x86_64')
-rw-r--r--arch/x86_64/include/arch/stl/deque.hpp524
-rw-r--r--arch/x86_64/include/arch/stl/stack.hpp4
-rw-r--r--arch/x86_64/src/memory/main.cpp10
3 files changed, 3 insertions, 535 deletions
diff --git a/arch/x86_64/include/arch/stl/deque.hpp b/arch/x86_64/include/arch/stl/deque.hpp
deleted file mode 100644
index b4a3054..0000000
--- a/arch/x86_64/include/arch/stl/deque.hpp
+++ /dev/null
@@ -1,524 +0,0 @@
-#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 =
- &block; // 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 = &block;
- }
-
- /**
- * @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
index 316aacd..9ecf0ca 100644
--- a/arch/x86_64/include/arch/stl/stack.hpp
+++ b/arch/x86_64/include/arch/stl/stack.hpp
@@ -2,7 +2,7 @@
#define TEACHOS_ARCH_X86_64_STL_STACK_HPP
#include "arch/exception_handling/panic.hpp"
-#include "arch/stl/deque.hpp"
+#include "arch/stl/vector.hpp"
namespace teachos::arch::stl
{
@@ -14,7 +14,7 @@ namespace teachos::arch::stl
* @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>>
+ 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.
diff --git a/arch/x86_64/src/memory/main.cpp b/arch/x86_64/src/memory/main.cpp
index 3041a75..bd094e0 100644
--- a/arch/x86_64/src/memory/main.cpp
+++ b/arch/x86_64/src/memory/main.cpp
@@ -5,7 +5,6 @@
#include "arch/kernel/cpu/msr.hpp"
#include "arch/memory/allocator/area_frame_allocator.hpp"
#include "arch/memory/allocator/concept.hpp"
-#include "arch/memory/allocator/stack_frame_allocator.hpp"
#include "arch/memory/heap/heap_allocator.hpp"
#include "arch/memory/paging/active_page_table.hpp"
#include "arch/memory/paging/kernel_mapper.hpp"
@@ -20,13 +19,6 @@ namespace teachos::arch::memory
return allocator::area_frame_allocator{memory_information};
}
- template<>
- auto create_frame_allocator(multiboot::memory_information const & memory_information)
- -> allocator::stack_frame_allocator
- {
- return allocator::stack_frame_allocator{memory_information};
- }
-
template<allocator::FrameAllocator T>
auto remap_heap(T & allocator, paging::active_page_table & active_table) -> void
{
@@ -52,7 +44,7 @@ namespace teachos::arch::memory
has_been_called = true;
auto const memory_information = multiboot::read_multiboot2();
- auto allocator = create_frame_allocator<allocator::stack_frame_allocator>(memory_information);
+ auto allocator = create_frame_allocator<allocator::area_frame_allocator>(memory_information);
kernel::cpu::set_cr0_bit(kernel::cpu::cr0_flags::WRITE_PROTECT);
kernel::cpu::set_efer_bit(kernel::cpu::efer_flags::NXE);
generated by cgit v1.2.3 (git 2.25.1) at 2026-04-20 01:39:45 +0000