diff options
| -rw-r--r-- | kernel/kapi/interrupts.cpp | 21 | ||||
| -rw-r--r-- | libs/kstd/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | libs/kstd/include/kstd/bits/flat_map.hpp | 82 | ||||
| -rw-r--r-- | libs/kstd/include/kstd/flat_map | 320 | ||||
| -rw-r--r-- | libs/kstd/tests/src/flat_map.cpp | 288 |
5 files changed, 708 insertions, 4 deletions
diff --git a/kernel/kapi/interrupts.cpp b/kernel/kapi/interrupts.cpp index e172e70..0e37bc3 100644 --- a/kernel/kapi/interrupts.cpp +++ b/kernel/kapi/interrupts.cpp @@ -1,10 +1,10 @@ #include "kapi/interrupts.hpp" +#include <kstd/flat_map> #include <kstd/print> #include <kstd/vector> #include <algorithm> -#include <array> #include <cstdint> namespace kapi::interrupts @@ -12,13 +12,20 @@ namespace kapi::interrupts namespace { - auto constinit handlers = std::array<kstd::vector<handler *>, 256>{}; + auto constinit handlers = kstd::flat_map<std::uint32_t, kstd::vector<handler *>>{}; } // namespace auto register_handler(std::uint32_t irq_number, handler & handler) -> void { - auto & handler_list = handlers.at(irq_number); - handler_list.push_back(&handler); + if (handlers.contains(irq_number)) + { + auto & handler_list = handlers.at(irq_number); + handler_list.push_back(&handler); + } + else + { + handlers.emplace(irq_number, kstd::vector{&handler}); + } } auto unregister_handler(std::uint32_t irq_number, handler & handler) -> void @@ -30,6 +37,12 @@ namespace kapi::interrupts auto dispatch(std::uint32_t irq_number) -> status { + if (!handlers.contains(irq_number)) + { + kstd::println(kstd::print_sink::stderr, "[OS:interrupts] No handler for IRQ{}", irq_number); + return status::unhandled; + } + auto & handler_list = handlers.at(irq_number); if (handler_list.empty()) diff --git a/libs/kstd/CMakeLists.txt b/libs/kstd/CMakeLists.txt index 06543ab..ff3c8cc 100644 --- a/libs/kstd/CMakeLists.txt +++ b/libs/kstd/CMakeLists.txt @@ -44,6 +44,7 @@ endif() if(NOT CMAKE_CROSSCOMPILING) add_executable("kstd_tests" + "tests/src/flat_map.cpp" "tests/src/vector.cpp" "tests/src/os_panic.cpp" ) diff --git a/libs/kstd/include/kstd/bits/flat_map.hpp b/libs/kstd/include/kstd/bits/flat_map.hpp new file mode 100644 index 0000000..903841e --- /dev/null +++ b/libs/kstd/include/kstd/bits/flat_map.hpp @@ -0,0 +1,82 @@ +#ifndef KSTD_BITS_FLAT_MAP_HPP +#define KSTD_BITS_FLAT_MAP_HPP + +#include <cstddef> +#include <iterator> +#include <utility> + +namespace kstd::bits +{ + + template<typename KeyType, typename MappedType, typename KeyIterator, typename MappedIterator> + struct flat_map_iterator + { + using iterator_category = std::random_access_iterator_tag; + using value_type = std::pair<KeyType, MappedType>; + using difference_type = std::ptrdiff_t; + using reference = std::pair<KeyType const &, MappedType &>; + using pointer = void; + + constexpr flat_map_iterator(KeyIterator key_iterator, MappedIterator mapped_iterator) + : m_key_iterator{key_iterator} + , m_mapped_iterator{mapped_iterator} + {} + + [[nodiscard]] auto key_iterator() const noexcept -> KeyIterator + { + return m_key_iterator; + } + + [[nodiscard]] constexpr auto operator*() const noexcept -> reference + { + return {*m_key_iterator, *m_mapped_iterator}; + } + + constexpr auto operator++() noexcept -> flat_map_iterator & + { + ++m_key_iterator; + ++m_mapped_iterator; + return *this; + } + + constexpr auto operator++(int) noexcept -> flat_map_iterator + { + auto copy = *this; + ++(*this); + return copy; + } + + constexpr auto operator--() noexcept -> flat_map_iterator & + { + --m_key_iterator; + --m_mapped_iterator; + return *this; + } + + constexpr auto operator--(int) noexcept -> flat_map_iterator + { + auto copy = *this; + --(*this); + return copy; + } + + [[nodiscard]] constexpr auto operator+(difference_type offset) const noexcept -> flat_map_iterator + { + return {m_key_iterator + offset, m_mapped_iterator + offset}; + } + + [[nodiscard]] constexpr auto operator-(flat_map_iterator const & other) const noexcept -> difference_type + { + return m_key_iterator - other.m_key_iterator; + } + + [[nodiscard]] constexpr auto operator<=>(flat_map_iterator const & other) const noexcept = default; + + private: + KeyIterator m_key_iterator{}; + MappedIterator m_mapped_iterator{}; + }; + +} // namespace kstd::bits + +#endif
\ No newline at end of file diff --git a/libs/kstd/include/kstd/flat_map b/libs/kstd/include/kstd/flat_map new file mode 100644 index 0000000..6ffbbcf --- /dev/null +++ b/libs/kstd/include/kstd/flat_map @@ -0,0 +1,320 @@ +#ifndef KSTD_FLAT_MAP_HPP +#define KSTD_FLAT_MAP_HPP + +#include <kstd/bits/flat_map.hpp> +#include <kstd/os/error.hpp> +#include <kstd/vector> + +#include <algorithm> +#include <concepts> +#include <cstddef> +#include <functional> +#include <iterator> +#include <utility> + +namespace kstd +{ + + template<typename KeyType, typename MappedType, typename KeyCompare = std::less<KeyType>, + typename KeyContainerType = kstd::vector<KeyType>, typename MappedContainerType = kstd::vector<MappedType>> + struct flat_map + { + using key_container_type = KeyContainerType; + using mapped_container_type = MappedContainerType; + using key_type = KeyType; + using mapped_type = MappedType; + using value_type = std::pair<key_type, mapped_type>; + using key_compare = KeyCompare; + using reference = std::pair<key_type const &, mapped_type &>; + using const_reference = std::pair<key_type const &, mapped_type const &>; + using size_type = std::size_t; + using difference_type = std::ptrdiff_t; + using iterator = bits::flat_map_iterator<KeyType, MappedType, typename key_container_type::iterator, + typename mapped_container_type::iterator>; + using const_iterator = + bits::flat_map_iterator<KeyType, MappedType const, typename key_container_type::const_iterator, + typename mapped_container_type::const_iterator>; + using reverse_iterator = std::reverse_iterator<iterator>; + using const_reverse_iterator = std::reverse_iterator<const_iterator>; + using containers = struct + { + key_container_type keys; + mapped_container_type values; + }; + + //! Compare two object of type value_type. + struct value_compare + { + constexpr auto operator()(const_reference lhs, const_reference rhs) const -> bool + { + return lhs.first < rhs.first; + } + }; + + //! Construct an empty flat map. + constexpr flat_map() + : flat_map{key_compare{}} + {} + + //! Construct an empty flat map using the given custom comparator. + //! + //! @param comparator The comparator to use for comparing keys. + constexpr explicit flat_map(key_compare const & comparator) + : m_containers{} + , m_comparator{comparator} + {} + + //! Get a reference to the mapped value associated with the given key. + //! + //! @warning This function will panic if the key is not found. + //! @param key The key to look up. + //! @return A reference to the mapped value. + [[nodiscard]] constexpr auto at(key_type const & key) -> mapped_type & + { + auto found = std::ranges::lower_bound(m_containers.keys, key, m_comparator); + if (found != m_containers.keys.cend() && !m_comparator(key, *found) && !m_comparator(*found, key)) + { + auto offset = std::distance(m_containers.keys.begin(), found); + return *(m_containers.values.begin() + offset); + } + os::panic("[kstd::flat_map] Key not found"); + } + + //! Get a reference to the mapped value associated with the given key. + //! + //! @warning This function will panic if the key is not found. + //! @param key The key to look up. + //! @return A const reference to the mapped value. + [[nodiscard]] constexpr auto at(key_type const & key) const -> mapped_type const & + { + auto found = std::ranges::lower_bound(m_containers.keys, key, m_comparator); + if (found != m_containers.keys.cend() && !m_comparator(key, *found) && !m_comparator(*found, key)) + { + auto offset = std::distance(m_containers.keys.cbegin(), found); + return *(m_containers.values.cbegin() + offset); + } + os::panic("[kstd::flat_map] Key not found"); + } + + //! Get a reference to the mapped value associated with the given key. + //! + //! @note This overload only participates in overload resolution if the key compare type is transparent. + //! @warning This function will panic if the key is not found. + //! @param x The key to look up. + //! @return A reference to the mapped value. + template<typename K> + requires requires(K const & k, key_type const & l) { typename key_compare::is_transparent; } + [[nodiscard]] constexpr auto at(K const & x) -> mapped_type & + { + auto found = find(x); + if (found != end()) + { + auto offset = std::distance(m_containers.keys.begin(), found.key_iterator()); + return *(m_containers.values.begin() + offset); + } + os::panic("[kstd::flat_map] Key not found"); + } + + //! Get a reference to the mapped value associated with the given key. + //! @note This overload only participates in overload resolution if the key compare type is transparent. + //! @warning This function will panic if the key is not found. + //! @param x The key to look up. + //! @return A const reference to the mapped value. + template<typename K> + requires requires(K const & k, key_type const & l) { typename key_compare::is_transparent; } + [[nodiscard]] auto at(K const & x) const -> mapped_type const & + { + auto found = find(x); + if (found != end()) + { + auto offset = std::distance(m_containers.keys.cbegin(), found.key_iterator()); + return *(m_containers.values.cbegin() + offset); + } + os::panic("[kstd::flat_map] Key not found"); + } + + //! Get an iterator to the first element. + [[nodiscard]] auto begin() noexcept -> iterator + { + return iterator{m_containers.keys.begin(), m_containers.values.begin()}; + } + + //! Get an iterator to the first element. + [[nodiscard]] auto begin() const noexcept -> const_iterator + { + return const_iterator{m_containers.keys.cbegin(), m_containers.values.cbegin()}; + } + + //! Get an iterator to the first element. + [[nodiscard]] auto cbegin() const noexcept -> const_iterator + { + return const_iterator{m_containers.keys.cbegin(), m_containers.values.cbegin()}; + } + + //! Get an iterator to the element past the last element. + [[nodiscard]] auto end() noexcept -> iterator + { + return iterator{m_containers.keys.end(), m_containers.values.end()}; + } + + //! Get an iterator to the element past the last element. + [[nodiscard]] auto end() const noexcept -> const_iterator + { + return const_iterator{m_containers.keys.cend(), m_containers.values.cend()}; + } + + //! Get an iterator to the element past the last element. + [[nodiscard]] auto cend() const noexcept -> const_iterator + { + return const_iterator{m_containers.keys.cend(), m_containers.values.cend()}; + } + + //! Get an iterator to the first element. + [[nodiscard]] auto rbegin() noexcept -> reverse_iterator + { + return reverse_iterator{end()}; + } + + //! Get an iterator to the first element. + [[nodiscard]] auto rbegin() const noexcept -> const_reverse_iterator + { + return const_reverse_iterator{cend()}; + } + + //! Get an iterator to the first element. + [[nodiscard]] auto crbegin() const noexcept -> const_reverse_iterator + { + return const_reverse_iterator{cend()}; + } + + //! Get an iterator to the element past the last element. + [[nodiscard]] auto rend() noexcept -> reverse_iterator + { + return reverse_iterator{begin()}; + } + + //! Get an iterator to the element past the last element. + [[nodiscard]] auto rend() const noexcept -> const_reverse_iterator + { + return const_reverse_iterator{cbegin()}; + } + + //! Get an iterator to the element past the last element. + [[nodiscard]] auto crend() const noexcept -> const_reverse_iterator + { + return const_reverse_iterator{cbegin()}; + } + + //! Try to insert a new key-value pair into the map. + //! + //! @param args Arguments to use for constructing the key-value pair. + //! @return A pair of an iterator to the inserted element and a boolean indicating whether the insertion took place. + template<typename... Args> + auto emplace(Args &&... args) -> std::pair<iterator, bool> + requires std::constructible_from<value_type, Args...> + { + auto value = value_type{std::forward<Args>(args)...}; + auto found = std::ranges::lower_bound(m_containers.keys, value.first, m_comparator); + + if (found != m_containers.keys.cend() && !m_comparator(value.first, *found) && !m_comparator(*found, value.first)) + { + auto offset = std::distance(m_containers.keys.begin(), found); + return { + iterator{m_containers.keys.begin() + offset, m_containers.values.begin() + offset}, + false + }; + } + + auto offset = std::distance(m_containers.keys.begin(), found); + auto key_iterator = m_containers.keys.begin() + offset; + auto mapped_iterator = m_containers.values.begin() + offset; + + auto inserted_key = m_containers.keys.insert(key_iterator, std::move(value.first)); + auto inserted_mapped = m_containers.values.insert(mapped_iterator, std::move(value.second)); + + return { + iterator{inserted_key, inserted_mapped}, + true + }; + } + + //! Find an element with an equivalent key. + //! + //! @param key The key to look up. + //! @return An iterator to the element with the equivalent key, or end() if no such element is found. + [[nodiscard]] auto find(key_type const & key) noexcept -> iterator + { + auto found = std::ranges::lower_bound(m_containers.keys, key, m_comparator); + if (found != m_containers.keys.cend() && !m_comparator(key, *found) && !m_comparator(*found, key)) + { + auto offset = std::distance(m_containers.keys.begin(), found); + return iterator{m_containers.keys.begin() + offset, m_containers.values.begin() + offset}; + } + return end(); + } + + //! Find an element with an equivalent key. + //! + //! @param key The key to look up. + //! @return An iterator to the element with the equivalent key, or end() if no such element is found. + [[nodiscard]] auto find(key_type const & key) const noexcept -> const_iterator + { + auto found = std::ranges::lower_bound(m_containers.keys, key, m_comparator); + if (found != m_containers.keys.cend() && !m_comparator(key, *found) && !m_comparator(*found, key)) + { + auto offset = std::distance(m_containers.keys.cbegin(), found); + return const_iterator{m_containers.keys.cbegin() + offset, m_containers.values.cbegin() + offset}; + } + return cend(); + } + + //! Find an element with an equivalent key. + //! @note This overload only participates in overload resolution if the key compare type is transparent. + //! @param x The key to look up. + //! @return An iterator to the element with the equivalent key, or end() if no such element is found. + template<typename K> + requires requires(K const & k, key_type const & l) { typename key_compare::is_transparent; } + [[nodiscard]] auto find(K const & x) noexcept -> iterator + { + auto found = std::ranges::lower_bound(m_containers.keys, x, m_comparator); + if (found != m_containers.keys.cend() && !m_comparator(x, *found) && !m_comparator(*found, x)) + { + auto offset = std::distance(m_containers.keys.begin(), found); + return iterator{m_containers.keys.begin() + offset, m_containers.values.begin() + offset}; + } + return end(); + } + + //! Find an element with an equivalent key. + //! @note This overload only participates in overload resolution if the key compare type is transparent. + //! @param x The key to look up. + //! @return An iterator to the element with the equivalent key, or end() if no such element is found. + template<typename K> + requires requires(K const & k, key_type const & l) { typename key_compare::is_transparent; } + [[nodiscard]] auto find(K const & x) const noexcept -> const_iterator + { + auto found = std::ranges::lower_bound(m_containers.keys, x, m_comparator); + if (found != m_containers.keys.cend() && !m_comparator(x, *found) && !m_comparator(*found, x)) + { + auto offset = std::distance(m_containers.keys.cbegin(), found); + return const_iterator{m_containers.keys.cbegin() + offset, m_containers.values.cbegin() + offset}; + } + return cend(); + } + + //! Check if the map contains the given key. + //! + //! @param key The key to check. + //! @return true iff. the key is found, false otherwise. + [[nodiscard]] constexpr auto contains(key_type const & key) const noexcept -> bool + { + return find(key) != cend(); + } + + private: + containers m_containers; + key_compare m_comparator; + }; +} // namespace kstd + +#endif
\ No newline at end of file diff --git a/libs/kstd/tests/src/flat_map.cpp b/libs/kstd/tests/src/flat_map.cpp new file mode 100644 index 0000000..cde136a --- /dev/null +++ b/libs/kstd/tests/src/flat_map.cpp @@ -0,0 +1,288 @@ +#include <kstd/flat_map> +#include <kstd/tests/os_panic.hpp> + +#include <catch2/catch_test_macros.hpp> + +#include <functional> + +SCENARIO("Flat Map initialization and construction", "[flat_map]") +{ + GIVEN("An empty context") + { + WHEN("constructing by default") + { + auto map = kstd::flat_map<int, int>{}; + + THEN("the Flat Map does not contain elements") + { + REQUIRE_FALSE(map.contains(1)); + } + } + } +} + +SCENARIO("Flat Map modifiers", "[flat_map]") +{ + GIVEN("An empty Flat Map") + { + auto map = kstd::flat_map<int, int>{}; + + WHEN("emplacing a new element") + { + auto [it, inserted] = map.emplace(1, 100); + + THEN("the map contains the new element") + { + REQUIRE(inserted); + REQUIRE(map.contains(1)); + } + } + + WHEN("emplacing an existing element") + { + map.emplace(1, 100); + auto [it, inserted] = map.emplace(1, 200); + + THEN("the map does not insert the duplicate") + { + REQUIRE_FALSE(inserted); + REQUIRE(map.contains(1)); + } + } + } +} + +SCENARIO("Flat Map element access", "[flat_map]") +{ + GIVEN("A populated Flat Map") + { + auto map = kstd::flat_map<int, int>{}; + map.emplace(1, 10); + map.emplace(2, 20); + map.emplace(3, 30); + + WHEN("accessing an existing element with at()") + { + auto & val = map.at(2); + + THEN("it returns a reference to the mapped value") + { + REQUIRE(val == 20); + } + + THEN("the mapped value can be modified") + { + val = 200; + REQUIRE(map.at(2) == 200); + } + } + + WHEN("accessing a non-existent element with at()") + { + THEN("it panics") + { + REQUIRE_THROWS_AS(map.at(4), kstd::tests::os_panic); + } + } + } + + GIVEN("A const populated Flat Map") + { + auto map_builder = kstd::flat_map<int, int>{}; + map_builder.emplace(1, 10); + map_builder.emplace(2, 20); + auto const map = map_builder; + + WHEN("accessing an existing element with const at()") + { + auto const & val = map.at(2); + + THEN("it returns a const reference to the mapped value") + { + REQUIRE(val == 20); + } + } + + WHEN("accessing a non-existent element with const at()") + { + THEN("it panics") + { + REQUIRE_THROWS_AS(map.at(4), kstd::tests::os_panic); + } + } + } +} + +SCENARIO("Flat Map iterators", "[flat_map]") +{ + GIVEN("A populated Flat Map") + { + auto map = kstd::flat_map<int, int>{}; + map.emplace(1, 10); + map.emplace(2, 20); + map.emplace(3, 30); + + WHEN("using forward iterators") + { + THEN("they navigate the elements in the correct forward order") + { + auto it = map.begin(); + REQUIRE(it != map.end()); + REQUIRE((*it).first == 1); + + ++it; + REQUIRE(it != map.end()); + REQUIRE((*it).first == 2); + + ++it; + REQUIRE(it != map.end()); + REQUIRE((*it).first == 3); + + ++it; + REQUIRE(it == map.end()); + } + + THEN("const forward iterators provide correct access") + { + auto it = map.cbegin(); + REQUIRE(it != map.cend()); + REQUIRE((*it).first == 1); + + ++it; + REQUIRE(it != map.cend()); + REQUIRE((*it).first == 2); + + ++it; + REQUIRE(it != map.cend()); + REQUIRE((*it).first == 3); + + ++it; + REQUIRE(it == map.cend()); + } + } + + WHEN("using reverse iterators") + { + THEN("they navigate the elements in the correct reverse order") + { + auto it = map.rbegin(); + REQUIRE(it != map.rend()); + REQUIRE((*it).first == 3); + + ++it; + REQUIRE(it != map.rend()); + REQUIRE((*it).first == 2); + + ++it; + REQUIRE(it != map.rend()); + REQUIRE((*it).first == 1); + + ++it; + REQUIRE(it == map.rend()); + } + + THEN("const reverse iterators provide correct access") + { + auto it = map.crbegin(); + REQUIRE(it != map.crend()); + REQUIRE((*it).first == 3); + + ++it; + REQUIRE(it != map.crend()); + REQUIRE((*it).first == 2); + + ++it; + REQUIRE(it != map.crend()); + REQUIRE((*it).first == 1); + + ++it; + REQUIRE(it == map.crend()); + } + } + } + + GIVEN("an empty Flat Map") + { + auto map = kstd::flat_map<int, int>{}; + + WHEN("getting iterators") + { + THEN("begin() equals end() and cbegin() equals cend()") + { + REQUIRE(map.begin() == map.end()); + REQUIRE(map.cbegin() == map.cend()); + } + + THEN("rbegin() equals rend() and crbegin() equals crend()") + { + REQUIRE(map.rbegin() == map.rend()); + REQUIRE(map.crbegin() == map.crend()); + } + } + } +} + +SCENARIO("Flat Map heterogeneous element access", "[flat_map]") +{ + GIVEN("A populated Flat Map with a transparent comparator") + { + auto map = kstd::flat_map<int, int, std::less<void>>{}; + map.emplace(1, 10); + map.emplace(2, 20); + map.emplace(3, 30); + + WHEN("accessing an existing element with a different key type via at()") + { + long const key = 2L; + auto & val = map.at(key); + + THEN("it returns a reference to the mapped value") + { + REQUIRE(val == 20); + } + + THEN("the mapped value can be modified") + { + val = 200; + REQUIRE(map.at(2L) == 200); + } + } + + WHEN("accessing a non-existent element with a different key type via at()") + { + long const key = 4L; + THEN("it panics") + { + REQUIRE_THROWS_AS(map.at(key), kstd::tests::os_panic); + } + } + } + + GIVEN("A const populated Flat Map with a transparent comparator") + { + auto map_builder = kstd::flat_map<int, int, std::less<void>>{}; + map_builder.emplace(1, 10); + map_builder.emplace(2, 20); + auto const map = map_builder; + + WHEN("accessing an existing element with a different key type via const at()") + { + long const key = 2L; + auto const & val = map.at(key); + + THEN("it returns a const reference to the mapped value") + { + REQUIRE(val == 20); + } + } + + WHEN("accessing a non-existent element with a different key type via const at()") + { + long const key = 4L; + THEN("it panics") + { + REQUIRE_THROWS_AS(map.at(key), kstd::tests::os_panic); + } + } + } +} |