libs: move vector to kstd

2 files changed, 609 insertions, 0 deletions

diff --git a/libs/kstd/include/kstd/bits/os.hpp b/libs/kstd/include/kstd/bits/os.hpp
new file mode 100644
index 0000000..0425b88
--- /dev/null
+++ b/libs/kstd/include/kstd/bits/os.hpp
@@ -0,0 +1,13 @@
+#ifndef KSTD_OS_HPP
+#define KSTD_OS_HPP
+
+#include <source_location>
+#include <string_view>
+
+namespace kstd::os
+{
+  [[noreturn]]
+  auto panic(std::string_view message, std::source_location = std::source_location::current()) -> void;
+}
+
+#endif
\ No newline at end of file
diff --git a/libs/kstd/include/kstd/vector.hpp b/libs/kstd/include/kstd/vector.hpp
new file mode 100644
index 0000000..1009e81
--- /dev/null
+++ b/libs/kstd/include/kstd/vector.hpp
@@ -0,0 +1,596 @@
+#ifndef KSTD_VECTOR_HPP
+#define KSTD_VECTOR_HPP
+
+#include "bits/os.hpp"
+
+#include <algorithm>
+
+namespace kstd
+{
+  /**
+   * @brief Custom vector implementation mirroring the std::vector to allow for the usage of STL functionality with our
+   * custom memory management.
+   *
+   * @tparam T Element the vector instance should contain.
+   */
+  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.
+     */
+    vector() = 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 vector(size_type n, value_type initial = value_type{})
+        : _size(n)
+        , _capacity(n)
+        , _data(new value_type[_capacity]{})
+    {
+      std::ranges::fill(*this, initial);
+    }
+
+    /**
+     * @brief Constructs data by copying all element from the given exclusive range.
+     *
+     * @tparam InputIterator Template that should have atleast input iterator characteristics.
+     * @param first Input iterator to the first element in the range we want to copy from.
+     * @param last Input iterator to one past the last element in the range we want to copy from.
+     */
+    template<typename InputIterator>
+    explicit vector(InputIterator first, InputIterator last)
+        : _size(std::distance(first, last))
+        , _capacity(std::distance(first, last))
+        , _data(new value_type[_capacity]{})
+    {
+      std::ranges::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<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 vector we are copying from and copies all
+     * elements from it.
+     *
+     * @param other Other instance of vector we want to copy the data from.
+     */
+    vector(vector<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 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.
+     */
+    [[gnu::section(".stl_text")]]
+    vector<value_type> & operator=(vector<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.
+     */
+    ~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.
+     *
+     * @return Current amount of elements.
+     */
+    [[gnu::section(".stl_text")]]
+    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
+     * exactly require to decrease the amount of allocations and deallocation to improve speed.
+     *
+     * @return Current amount of space the vector has for elements.
+     */
+    [[gnu::section(".stl_text")]]
+    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.
+     */
+    [[gnu::section(".stl_text")]]
+    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.
+     */
+    [[gnu::section(".stl_text")]]
+    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.
+     */
+    [[gnu::section(".stl_text")]]
+    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.
+     */
+    [[gnu::section(".stl_text")]]
+    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. 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>
+    [[gnu::section(".stl_text")]]
+    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. 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>
+    [[gnu::section(".stl_text")]]
+    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.
+     */
+    [[gnu::section(".stl_text")]]
+    auto pop_back() -> void
+    {
+      throw_if_empty();
+      (void)_size--;
+    }
+
+    /**
+     * @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.
+     */
+    [[gnu::section(".stl_text")]]
+    auto begin() noexcept -> pointer
+    {
+      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.
+     */
+    [[gnu::section(".stl_text")]]
+    auto begin() const noexcept -> const_pointer
+    {
+      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.
+     */
+    [[gnu::section(".stl_text")]]
+    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
+     * of the non-reversed vector. If the vector is empty, the returned iterator will be equal to rend().
+     *
+     * @return Reverse iterator to the first element.
+     */
+    [[gnu::section(".stl_text")]]
+    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
+     * of the non-reversed vector. If the vector is empty, the returned iterator will be equal to rend().
+     *
+     * @return Reverse iterator to the first element.
+     */
+    [[gnu::section(".stl_text")]]
+    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
+     * of the non-reversed vector. If the vector is empty, the returned iterator will be equal to rend().
+     *
+     * @return Reverse iterator to the first element.
+     */
+    [[gnu::section(".stl_text")]]
+    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
+     * placeholder, attempting to access it results in undefined behavior.
+     *
+     * @return Iterator to the element following the last element.
+     */
+    [[gnu::section(".stl_text")]]
+    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
+     * placeholder, attempting to access it results in undefined behavior.
+     *
+     * @return Iterator to the element following the last element.
+     */
+    [[gnu::section(".stl_text")]]
+    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
+     * placeholder, attempting to access it results in undefined behavior.
+     *
+     * @return Iterator to the element following the last element.
+     */
+    [[gnu::section(".stl_text")]]
+    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
+     * corresponds to the element preceding the first element of the non-reversed vector. This element acts as a
+     * placeholder, attempting to access it results in undefined behavior.
+     *
+     * @return Reverse iterator to the element following the last element.
+     */
+    [[gnu::section(".stl_text")]]
+    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
+     * corresponds to the element preceding the first element of the non-reversed vector. This element acts as a
+     * placeholder, attempting to access it results in undefined behavior.
+     *
+     * @return Reverse iterator to the element following the last element.
+     */
+    [[gnu::section(".stl_text")]]
+    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
+     * corresponds to the element preceding the first element of the non-reversed vector. This element acts as a
+     * placeholder, attempting to access it results in undefined behavior.
+     *
+     * @return Reverse iterator to the element following the last element.
+     */
+    [[gnu::section(".stl_text")]]
+    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.
+     */
+    [[gnu::section(".stl_text")]]
+    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.
+     */
+    [[gnu::section(".stl_text")]]
+    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.
+     */
+    [[gnu::section(".stl_text")]]
+    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.
+     */
+    [[gnu::section(".stl_text")]]
+    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.
+     */
+    [[gnu::section(".stl_text")]]
+    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.
+     */
+    [[gnu::section(".stl_text")]]
+    auto back() const -> const_reference
+    {
+      throw_if_empty();
+      return *rbegin();
+    }
+
+    /**
+     * @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
+     */
+    [[gnu::section(".stl_text")]]
+    auto reserve(size_type new_capacity) -> void
+    {
+      if (new_capacity <= _capacity)
+      {
+        return;
+      }
+
+      _capacity = new_capacity;
+      value_type * temp = new value_type[_capacity]{};
+      std::ranges::copy(begin(), end(), 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.
+     */
+    [[gnu::section(".stl_text")]]
+    auto shrink_to_fit() -> void
+    {
+      if (_size == _capacity)
+      {
+        return;
+      }
+
+      _capacity = _size;
+      value_type * temp = new value_type[_capacity]{};
+      std::ranges::copy(begin(), end(), 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.
+     */
+    [[gnu::section(".stl_text")]]
+    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())
+      {
+        os::panic("[Vector] Attempted to access element of currently empty vector");
+      }
+    }
+
+    auto throw_if_out_of_range(size_type index) const -> void
+    {
+      if (index >= _size)
+      {
+        os::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
+     * 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
+    value_type * _data = {};   ///< Pointer to the first element in the underlying data container
+  };
+
+}  // namespace kstd
+
+#endif