diff options
| -rw-r--r-- | xbmc/utils/Map.h | 47 | ||||
| -rw-r--r-- | xbmc/utils/test/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | xbmc/utils/test/TestMap.cpp | 65 |
3 files changed, 90 insertions, 23 deletions
diff --git a/xbmc/utils/Map.h b/xbmc/utils/Map.h index 17af54548f..4e14432e05 100644 --- a/xbmc/utils/Map.h +++ b/xbmc/utils/Map.h @@ -26,34 +26,22 @@ * This class is useful for mapping enum values to strings that can be * compile time checked. This also helps with heap usage. * - * Lookups have linear complexity, so should not be used for "big" maps. + * Lookups have log(n) complexity if Key is comparable using std::less<>, + * otherwise it's linear. */ template<typename Key, typename Value, size_t Size> class CMap { public: template<typename Iterable> - constexpr CMap(Iterable begin, Iterable end) + consteval CMap(Iterable begin, Iterable end) { - size_t index = 0; - while (begin != end) - { - // c++17 doesn't have constexpr assignment operator for std::pair - auto& first = m_map[index].first; - auto& second = m_map[index].second; - ++index; - - first = std::move(begin->first); - second = std::move(begin->second); - ++begin; - - //! @todo: c++20 can use constexpr assignment operator instead - // auto& p = data[index]; - // ++index; + std::move(begin, end, m_map.begin()); - // p = std::move(*begin); - // ++begin; - // + if constexpr (requires(Key k) { std::less<>{}(k, k); }) + { + std::sort(m_map.begin(), m_map.end(), + [](const auto& a, const auto& b) { return std::less<>{}(a.first, b.first); }); } } @@ -74,8 +62,21 @@ public: constexpr auto find(const Key& key) const { - return std::find_if(m_map.cbegin(), m_map.cend(), - [&key](const auto& pair) { return pair.first == key; }); + if constexpr (requires(Key k) { std::less<>{}(k, k); }) + { + const auto iter = + std::lower_bound(m_map.cbegin(), m_map.cend(), key, + [](const auto& a, const auto& b) { return std::less<>{}(a.first, b); }); + if (iter != m_map.end() && !(key < iter->first)) + return iter; + else + return m_map.end(); + } + else + { + return std::find_if(m_map.cbegin(), m_map.cend(), + [&key](const auto& pair) { return pair.first == key; }); + } } constexpr size_t size() const { return Size; } @@ -96,7 +97,7 @@ private: * */ template<typename Key, typename Value, std::size_t Size> -constexpr auto make_map(std::pair<Key, Value>(&&m)[Size]) -> CMap<Key, Value, Size> +consteval auto make_map(std::pair<Key, Value> (&&m)[Size]) -> CMap<Key, Value, Size> { return CMap<Key, Value, Size>(std::begin(m), std::end(m)); } diff --git a/xbmc/utils/test/CMakeLists.txt b/xbmc/utils/test/CMakeLists.txt index 99bd4faaf7..82da6783a6 100644 --- a/xbmc/utils/test/CMakeLists.txt +++ b/xbmc/utils/test/CMakeLists.txt @@ -28,6 +28,7 @@ set(SOURCES TestAlarmClock.cpp TestLangCodeExpander.cpp TestLocale.cpp Testlog.cpp + TestMap.cpp TestMathUtils.cpp TestMime.cpp TestPOUtils.cpp diff --git a/xbmc/utils/test/TestMap.cpp b/xbmc/utils/test/TestMap.cpp new file mode 100644 index 0000000000..514c5a7c17 --- /dev/null +++ b/xbmc/utils/test/TestMap.cpp @@ -0,0 +1,65 @@ +/* + * Copyright (C) 2024 Team Kodi + * This file is part of Kodi - https://kodi.tv + * + * SPDX-License-Identifier: GPL-2.0-or-later + * See LICENSES/README.md for more information. + */ + +#include "utils/Map.h" + +#include <algorithm> + +#include <gtest/gtest.h> + +// CMap with sortable keys. Keys are sorted at compile time and find uses binary search +TEST(TestMap, SortableKey) +{ + constexpr auto map = make_map<int, std::string_view>({{3, "three"}, {1, "one"}, {2, "two"}}); + EXPECT_EQ(map.find(1)->second, "one"); + EXPECT_EQ(map.find(2)->second, "two"); + EXPECT_EQ(map.find(3)->second, "three"); + EXPECT_EQ(map.find(0), map.cend()); + EXPECT_EQ(map.find(4), map.cend()); + // Ensure content is sorted + EXPECT_TRUE( + std::is_sorted(map.cbegin(), map.cend(), [](auto& a, auto& b) { return a.first < b.first; })); +} + +// CMap with non sortable keys. Performs linear search in find +TEST(TestMap, NonSortableKey) +{ + struct Dummy + { + int i; + bool operator==(const Dummy& other) const { return i == other.i; } + }; + + constexpr auto map = make_map<Dummy, std::string_view>( + {{Dummy{3}, "three"}, {Dummy{1}, "one"}, {Dummy{2}, "two"}}); + EXPECT_EQ(map.find(Dummy{1})->second, "one"); + EXPECT_EQ(map.find(Dummy{2})->second, "two"); + EXPECT_EQ(map.find(Dummy{3})->second, "three"); + EXPECT_EQ(map.find(Dummy{0}), map.cend()); + EXPECT_EQ(map.find(Dummy{4}), map.cend()); +} + +// CMap compile time tests (not really a unit test...) +TEST(TestMap, EnumConstexpr) +{ + enum class ENUM + { + ONE, + TWO, + THREE, + ENUM_MAX, + }; + + constexpr auto map = make_map<ENUM, std::string_view>( + {{ENUM::ONE, "ONE"}, {ENUM::TWO, "TWO"}, {ENUM::THREE, "THREE"}}); + static_assert(map.find(ENUM::ONE)->second == "ONE"); + static_assert(map.find(ENUM::TWO)->second == "TWO"); + static_assert(map.find(ENUM::THREE)->second == "THREE"); + static_assert(map.find(ENUM::ENUM_MAX) == map.cend()); + static_assert(map.size() == size_t(ENUM::ENUM_MAX)); +} |