From e6d9330a978373ffc24209b5edf03eda6491f818 Mon Sep 17 00:00:00 2001 From: Dominick Allen Date: Wed, 2 Apr 2025 06:43:43 -0500 Subject: Add more testing for hash maps. --- include/fud_hash.hpp | 3 ++ include/fud_hash_map.hpp | 113 ++++++++++++++++++++++++++++++++++++++---- include/fud_hash_map_impl.hpp | 6 +++ test/test_hash_map.cpp | 91 +++++++++++++++++++++++++++++++++- 4 files changed, 201 insertions(+), 12 deletions(-) diff --git a/include/fud_hash.hpp b/include/fud_hash.hpp index a472171..8567e1f 100644 --- a/include/fud_hash.hpp +++ b/include/fud_hash.hpp @@ -36,6 +36,9 @@ namespace fud::detail { constexpr uint64_t roundToNearest2(uint64_t inputValue) noexcept { + if (inputValue == 0) { + return 1; + } uint64_t outputValue = inputValue - 1; constexpr uint8_t max2PowerShift = 32; for (uint8_t shift = 1; shift <= max2PowerShift; shift *= 2) { diff --git a/include/fud_hash_map.hpp b/include/fud_hash_map.hpp index dd6d080..9220876 100644 --- a/include/fud_hash_map.hpp +++ b/include/fud_hash_map.hpp @@ -194,10 +194,49 @@ class HashMap { return FudStatus::Success; } - FudStatus replace(const Key& key, const Value& value); - FudStatus replace(const Key& key, Value&& value); - FudStatus replace(Key&& key, const Value& value); - FudStatus replace(Key&& key, Value&& value); + FudStatus update(const Key& key, const Value& value) + { + auto hashIndexOption = lookup(key); + if (hashIndexOption.isNone()) { + return insert(key, value); + } + auto hashIndex{hashIndexOption.take()}; + m_data[hashIndex].value() = value; + return FudStatus::Success; + } + + FudStatus update(const Key& key, Value&& value) + { + auto hashIndexOption = lookup(key); + if (hashIndexOption.isNone()) { + return insert(key, std::move(value)); + } + auto hashIndex{hashIndexOption.take()}; + m_data[hashIndex].value() = std::move(value); + return FudStatus::Success; + } + + FudStatus update(Key&& key, const Value& value) + { + auto hashIndexOption = lookup(key); + if (hashIndexOption.isNone()) { + return insert(std::move(key), value); + } + auto hashIndex{hashIndexOption.take()}; + m_data[hashIndex].value() = value; + return FudStatus::Success; + } + + FudStatus update(Key&& key, Value&& value) + { + auto hashIndexOption = lookup(key); + if (hashIndexOption.isNone()) { + return insert(std::move(key), std::move(value)); + } + auto hashIndex{hashIndexOption.take()}; + m_data[hashIndex].value() = std::move(value); + return FudStatus::Success; + } FudStatus remove(const Key& key) { @@ -223,10 +262,61 @@ class HashMap { return FudStatus::Success; } - Option extract(const Key& key); - Option extract(Key& key); - Node extractPair(const Key& key); - Node extractPair(Key& key); + Option extract(const Key& key) + { + auto hashIndexOption = lookup(key); + if (hashIndexOption.isNone()) { + return NullOpt; + } + + auto hashIndex{hashIndexOption.value()}; + Option value{std::move(m_data[hashIndex].takeValue())}; + m_data[hashIndex].tombstone(); + + return value; + } + + Option extract(Key&& key) + { + auto hashIndexOption = lookup(std::move(key)); + if (hashIndexOption.isNone()) { + return NullOpt; + } + + auto hashIndex{hashIndexOption.value()}; + Option value{std::move(m_data[hashIndex].takeValue())}; + m_data[hashIndex].tombstone(); + + return value; + } + + KeyValuePair extractPair(const Key& key) + { + auto hashIndexOption = lookup(key); + if (hashIndexOption.isNone()) { + return NullOpt; + } + + auto hashIndex{hashIndexOption.value()}; + KeyValuePair kvPair{key, m_data[hashIndex].takeValue()}; + m_data[hashIndex].tombstone(); + + return kvPair; + } + + KeyValuePair extractPair(Key&& key) + { + auto hashIndexOption = lookup(key); + if (hashIndexOption.isNone()) { + return NullOpt; + } + + auto hashIndex{hashIndexOption.value()}; + KeyValuePair kvPair{std::move(key), m_data[hashIndex].takeValue()}; + m_data[hashIndex].tombstone(); + + return kvPair; + } Option get(const Key& key) { @@ -328,7 +418,7 @@ class HashMap { return status; } - Result exchange(const Key& key, const Value& value); + Result, FudStatus> exchange(const Key& key, const Value& value); protected: [[nodiscard]] double loadFactor() const @@ -398,6 +488,9 @@ class HashMap { Option lookup(const Key& key) const { + if (m_count == 0 || m_buckets == 0 || m_data == nullptr) { + return NullOpt; + } const auto hash = m_hasher(key, m_seed); const auto nearestPowerOf2 = detail::roundToNearest2(m_buckets); size_t probe = 0; @@ -419,7 +512,7 @@ class HashMap { } } - if (collision and m_data[hashIndex].key() == key) { + if (collision and hashIndex < m_buckets and m_data[hashIndex].key() == key) { return hashIndex; } diff --git a/include/fud_hash_map_impl.hpp b/include/fud_hash_map_impl.hpp index e4b79c4..6e224f9 100644 --- a/include/fud_hash_map_impl.hpp +++ b/include/fud_hash_map_impl.hpp @@ -151,6 +151,12 @@ struct MapEntry { return *std::bit_cast(m_valueData.data()); } + [[nodiscard]] Value&& takeValue() & + { + fudAssert(hasValue()); + return std::move(*std::bit_cast(m_valueData.data())); + } + constexpr void tombstone() noexcept { destroy(true); diff --git a/test/test_hash_map.cpp b/test/test_hash_map.cpp index c55eda3..9f01766 100644 --- a/test/test_hash_map.cpp +++ b/test/test_hash_map.cpp @@ -59,8 +59,16 @@ TEST(FudHash, InsertMoveKeyMoveValue) auto stringList{testStrings()}; HashMap mapInt2String{}; for (int index = 0; index < static_cast(stringList.size()); ++index) { + EXPECT_FALSE(mapInt2String.contains(index)); + EXPECT_FALSE(mapInt2String.contains(index * 1)); auto insertStatus = mapInt2String.insert(index * 1, String::from(stringList[index]).takeOkay()); EXPECT_EQ(insertStatus, FudStatus::Success); + EXPECT_TRUE(mapInt2String.contains(index)); + EXPECT_TRUE(mapInt2String.contains(index * 1)); + } + for (int index = 0; index < static_cast(stringList.size()); ++index) { + auto insertStatus = mapInt2String.insert(index * 1, String::from(stringList[index]).takeOkay()); + EXPECT_EQ(insertStatus, FudStatus::Exists); } EXPECT_EQ(mapInt2String.size(), stringList.size()); EXPECT_GT(mapInt2String.capacity(), mapInt2String.size()); @@ -76,9 +84,15 @@ TEST(FudHash, InsertMoveKeyCopyValue) auto stringList{testStrings()}; HashMap mapString2Int{}; for (int index = 0; index < static_cast(stringList.size()); ++index) { - auto insertStatus = mapString2Int.insert(String::from(stringList[index]).takeOkay(), index * 1); + EXPECT_FALSE(mapString2Int.contains(stringList[index])); + auto insertStatus = mapString2Int.insert(String::from(stringList[index]).takeOkay(), index); + EXPECT_TRUE(mapString2Int.contains(stringList[index])); EXPECT_EQ(insertStatus, FudStatus::Success); } + for (int index = 0; index < static_cast(stringList.size()); ++index) { + auto insertStatus = mapString2Int.insert(String::from(stringList[index]).takeOkay(), index); + EXPECT_EQ(insertStatus, FudStatus::Exists); + } EXPECT_EQ(mapString2Int.size(), stringList.size()); EXPECT_GT(mapString2Int.capacity(), mapString2Int.size()); @@ -104,6 +118,10 @@ TEST(FudHash, InsertCopyKeyMoveValue) auto insertStatus = mapInt2String.insert(index, String::from(stringList[index]).takeOkay()); EXPECT_EQ(insertStatus, FudStatus::Success); } + for (int index = 0; index < static_cast(stringList.size()); ++index) { + auto insertStatus = mapInt2String.insert(index, String::from(stringList[index]).takeOkay()); + EXPECT_EQ(insertStatus, FudStatus::Exists); + } EXPECT_EQ(mapInt2String.size(), stringList.size()); EXPECT_GT(mapInt2String.capacity(), mapInt2String.size()); @@ -123,6 +141,10 @@ TEST(FudHash, InsertCopyKeyCopyValue) auto insertStatus = mapView2Int.insert(stringViewList[index], index); EXPECT_EQ(insertStatus, FudStatus::Success); } + for (int index = 0; index < static_cast(stringViewList.size()); ++index) { + auto insertStatus = mapView2Int.insert(stringViewList[index], index); + EXPECT_EQ(insertStatus, FudStatus::Exists); + } EXPECT_EQ(mapView2Int.size(), stringViewList.size()); EXPECT_GT(mapView2Int.capacity(), mapView2Int.size()); @@ -138,7 +160,7 @@ TEST(FudHash, RemoveKeyConstRef) auto stringList{testStrings()}; HashMap mapString2Int{}; for (int index = 0; index < static_cast(stringList.size()); ++index) { - auto insertStatus = mapString2Int.insert(String::from(stringList[index]).takeOkay(), index * 1); + auto insertStatus = mapString2Int.insert(String::from(stringList[index]).takeOkay(), index); EXPECT_EQ(insertStatus, FudStatus::Success); } @@ -194,4 +216,69 @@ TEST(FudHash, RemoveKeyMoveRef) } } +TEST(FudHash, ExtractConstKey) +{ + auto stringList{testStrings()}; + HashMap mapString2Int{}; + for (int index = 0; index < static_cast(stringList.size()); ++index) { + auto insertStatus = mapString2Int.insert(String::from(stringList[index]).takeOkay(), index); + EXPECT_EQ(insertStatus, FudStatus::Success); + } + + EXPECT_EQ(mapString2Int.size(), stringList.size()); + EXPECT_GT(mapString2Int.capacity(), mapString2Int.size()); + + for (int index = 0; index < static_cast(stringList.size()); ++index) { + const int invalid = -1; + EXPECT_EQ(mapString2Int.get(stringList[index]).valueOr(invalid), index); + } + + for (int index = 0; index < static_cast(stringList.size()); ++index) { + auto valueOpt{mapString2Int.extract(stringList[index])}; + ASSERT_TRUE(valueOpt.hasValue()); + EXPECT_EQ(valueOpt.value(), index); + } + + for (const auto& entry : stringList) { + EXPECT_TRUE(mapString2Int.extract(entry).isNone()); + } + + for (const auto& entry : stringList) { + const int invalid = -1; + EXPECT_EQ(mapString2Int.get(entry).valueOr(invalid), invalid); + } +} + +TEST(FudHash, ExtractMoveKey) +{ + auto stringList{testStrings()}; + HashMap mapInt2String{}; + for (int index = 0; index < static_cast(stringList.size()); ++index) { + auto insertStatus = mapInt2String.insert(index, String::from(stringList[index]).takeOkay()); + EXPECT_EQ(insertStatus, FudStatus::Success); + } + + EXPECT_EQ(mapInt2String.size(), stringList.size()); + EXPECT_GT(mapInt2String.capacity(), mapInt2String.size()); + + const String invalid{String::makeFromCString("Invalid").takeOkay()}; + for (int index = 0; index < static_cast(stringList.size()); ++index) { + EXPECT_EQ(mapInt2String.getConstRef(index).valueOr(invalid), stringList[index]); + } + + for (int index = 0; index < static_cast(stringList.size()); ++index) { + auto valueOpt{mapInt2String.extract(index * 1)}; + ASSERT_TRUE(valueOpt.hasValue()); + EXPECT_EQ(valueOpt.value(), stringList[index]); + } + + for (int index = 0; index < stringList.size(); ++index) { + EXPECT_TRUE(mapInt2String.extract(index * 1).isNone()); + } + + for (int index = 0; index < static_cast(stringList.size()); ++index) { + EXPECT_EQ(mapInt2String.getConstRef(index).valueOr(invalid), invalid); + } +} + } // namespace fud -- cgit v1.2.3