From e95f207ecf1de5eed44744b6d84691c00b6f1e1c Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Markus=20H=C3=A4rer?= Date: Sun, 7 Jul 2024 18:34:11 +0200 Subject: Map: Make access log(n) if keys can be sorted --- xbmc/utils/Map.h | 26 +++++++++++++++++++++++--- 1 file changed, 23 insertions(+), 3 deletions(-) diff --git a/xbmc/utils/Map.h b/xbmc/utils/Map.h index 17af54548f..f4a1c872c4 100644 --- a/xbmc/utils/Map.h +++ b/xbmc/utils/Map.h @@ -26,7 +26,8 @@ * 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 class CMap @@ -55,6 +56,12 @@ public: // ++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); }); + } } ~CMap() = default; @@ -74,8 +81,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; } -- cgit v1.2.3 From 6fb722cf5b61ad366c6a7eb0918fdec9a5099423 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Markus=20H=C3=A4rer?= Date: Sun, 7 Jul 2024 21:34:19 +0200 Subject: TestMap: Add unit test for CMap --- xbmc/utils/test/CMakeLists.txt | 1 + xbmc/utils/test/TestMap.cpp | 65 ++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 66 insertions(+) create mode 100644 xbmc/utils/test/TestMap.cpp 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 + +#include + +// CMap with sortable keys. Keys are sorted at compile time and find uses binary search +TEST(TestMap, SortableKey) +{ + constexpr auto map = make_map({{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{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::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)); +} -- cgit v1.2.3 From 1be7403820c92d355d3115fc177e732b6e3b9cab Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Markus=20H=C3=A4rer?= Date: Sun, 7 Jul 2024 21:42:20 +0200 Subject: Map: Simplify constructor --- xbmc/utils/Map.h | 21 +-------------------- 1 file changed, 1 insertion(+), 20 deletions(-) diff --git a/xbmc/utils/Map.h b/xbmc/utils/Map.h index f4a1c872c4..21c4011621 100644 --- a/xbmc/utils/Map.h +++ b/xbmc/utils/Map.h @@ -36,26 +36,7 @@ public: template constexpr 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; - - // p = std::move(*begin); - // ++begin; - // - } + std::move(begin, end, m_map.begin()); if constexpr (requires(Key k) { std::less<>{}(k, k); }) { -- cgit v1.2.3 From 6137da592ce203e736249d40174cbc3b7aa183c3 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Markus=20H=C3=A4rer?= Date: Sun, 7 Jul 2024 22:05:45 +0200 Subject: Map: Make CMap constructor consteval --- xbmc/utils/Map.h | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/xbmc/utils/Map.h b/xbmc/utils/Map.h index 21c4011621..4e14432e05 100644 --- a/xbmc/utils/Map.h +++ b/xbmc/utils/Map.h @@ -34,7 +34,7 @@ class CMap { public: template - constexpr CMap(Iterable begin, Iterable end) + consteval CMap(Iterable begin, Iterable end) { std::move(begin, end, m_map.begin()); @@ -97,7 +97,7 @@ private: * */ template -constexpr auto make_map(std::pair(&&m)[Size]) -> CMap +consteval auto make_map(std::pair (&&m)[Size]) -> CMap { return CMap(std::begin(m), std::end(m)); } -- cgit v1.2.3