summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/fud_hash.hpp3
-rw-r--r--include/fud_hash_map.hpp113
-rw-r--r--include/fud_hash_map_impl.hpp6
-rw-r--r--test/test_hash_map.cpp91
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<Value> extract(const Key& key);
- Option<Value> extract(Key& key);
- Node extractPair(const Key& key);
- Node extractPair(Key& key);
+ Option<Value> extract(const Key& key)
+ {
+ auto hashIndexOption = lookup(key);
+ if (hashIndexOption.isNone()) {
+ return NullOpt;
+ }
+
+ auto hashIndex{hashIndexOption.value()};
+ Option<Value> value{std::move(m_data[hashIndex].takeValue())};
+ m_data[hashIndex].tombstone();
+
+ return value;
+ }
+
+ Option<Value> extract(Key&& key)
+ {
+ auto hashIndexOption = lookup(std::move(key));
+ if (hashIndexOption.isNone()) {
+ return NullOpt;
+ }
+
+ auto hashIndex{hashIndexOption.value()};
+ Option<Value> 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<Value> get(const Key& key)
{
@@ -328,7 +418,7 @@ class HashMap {
return status;
}
- Result<Value, FudStatus> exchange(const Key& key, const Value& value);
+ Result<Option<Value>, FudStatus> exchange(const Key& key, const Value& value);
protected:
[[nodiscard]] double loadFactor() const
@@ -398,6 +488,9 @@ class HashMap {
Option<size_t> 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<Value*>(m_valueData.data());
}
+ [[nodiscard]] Value&& takeValue() &
+ {
+ fudAssert(hasValue());
+ return std::move(*std::bit_cast<Value*>(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<int, String> mapInt2String{};
for (int index = 0; index < static_cast<int>(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<int>(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<String, int> mapString2Int{};
for (int index = 0; index < static_cast<int>(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<int>(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<int>(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<int>(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<String, int> mapString2Int{};
for (int index = 0; index < static_cast<int>(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<String, int> mapString2Int{};
+ for (int index = 0; index < static_cast<int>(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<int>(stringList.size()); ++index) {
+ const int invalid = -1;
+ EXPECT_EQ(mapString2Int.get(stringList[index]).valueOr(invalid), index);
+ }
+
+ for (int index = 0; index < static_cast<int>(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<int, String> mapInt2String{};
+ for (int index = 0; index < static_cast<int>(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<int>(stringList.size()); ++index) {
+ EXPECT_EQ(mapInt2String.getConstRef(index).valueOr(invalid), stringList[index]);
+ }
+
+ for (int index = 0; index < static_cast<int>(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<int>(stringList.size()); ++index) {
+ EXPECT_EQ(mapInt2String.getConstRef(index).valueOr(invalid), invalid);
+ }
+}
+
} // namespace fud
generated by cgit v1.2.3 (git 2.39.1) at 2025-04-20 11:19:22 +0000