NaN-safe comparison and hashing

commit_hash:46d59ab3acbd313753d3e46f3a6f10a8ebc424d8

9 files changed, 294 insertions, 2 deletions

diff --git a/library/cpp/yt/misc/compare-inl.h b/library/cpp/yt/misc/compare-inl.h
new file mode 100644
index 0000000000..b9dfb5319f
--- /dev/null
+++ b/library/cpp/yt/misc/compare-inl.h
@@ -0,0 +1,71 @@
+#ifndef COMPARE_INL_H_
+#error "Direct inclusion of this file is not allowed, include compare.h"
+// For the sake of sane code completion.
+#include "compare.h"
+#endif
+
+#include "numeric_helpers.h"
+
+#include <util/generic/string.h>
+
+#include <string>
+#include <string_view>
+
+namespace NYT {
+
+////////////////////////////////////////////////////////////////////////////////
+
+template <class T>
+Y_FORCE_INLINE int TernaryCompare(const T& lhs, const T& rhs)
+{
+    if (lhs == rhs) {
+        return 0;
+    } else if (lhs < rhs) {
+        return -1;
+    } else {
+        return +1;
+    }
+}
+
+//! An optimized version for string types.
+template <class T>
+    requires
+        std::is_same_v<T, TString> ||
+        std::is_same_v<T, TStringBuf> ||
+        std::is_same_v<T, std::string> ||
+        std::is_same_v<T, std::string_view>
+Y_FORCE_INLINE int TernaryCompare(const T& lhs, const T& rhs)
+{
+    return GetSign(std::string_view(lhs).compare(std::string_view(rhs)));
+}
+
+template <class T>
+Y_FORCE_INLINE int NaNSafeTernaryCompare(const T& lhs, const T& rhs)
+{
+    return TernaryCompare(lhs, rhs);
+}
+
+template <class T>
+    requires std::is_floating_point_v<T>
+Y_FORCE_INLINE int NaNSafeTernaryCompare(const T& lhs, const T& rhs)
+{
+    if (lhs < rhs) {
+        return -1;
+    } else if (lhs > rhs) {
+        return +1;
+    } else if (std::isnan(lhs)) {
+        if (std::isnan(rhs)) {
+            return 0;
+        } else {
+            return +1;
+        }
+    } else if (std::isnan(rhs)) {
+        return -1;
+    } else {
+        return 0;
+    }
+}
+
+////////////////////////////////////////////////////////////////////////////////
+
+} // namespace NYT
diff --git a/library/cpp/yt/misc/compare.h b/library/cpp/yt/misc/compare.h
new file mode 100644
index 0000000000..22e452b355
--- /dev/null
+++ b/library/cpp/yt/misc/compare.h
@@ -0,0 +1,28 @@
+#pragma once
+
+#include <util/generic/string.h>
+
+#include <string_view>
+
+namespace NYT {
+
+////////////////////////////////////////////////////////////////////////////////
+
+//! Compares #lhs with #rhs;
+//! returns -1 (if |lhs < rhs|), 0 (if |lhs == rhs|), or 1 (|lhs > rhs|).
+template <class T>
+int TernaryCompare(const T& lhs, const T& rhs);
+
+//! Same as #TernaryCompare but handles NaN values gracefully
+//! (assuming NaNs are larger than any regular number and all NaNs are equal).
+//! If |T| is not a floating-point type, #NaNSafeTernaryCompare is equivalent to #TernaryCompare.
+template <class T>
+int NaNSafeTernaryCompare(const T& lhs, const T& rhs);
+
+////////////////////////////////////////////////////////////////////////////////
+
+} // namespace NYT
+
+#define COMPARE_INL_H_
+#include "compare-inl.h"
+#undef COMPARE_INL_H_
diff --git a/library/cpp/yt/misc/hash-inl.h b/library/cpp/yt/misc/hash-inl.h
index 46eeefe620..159748a09b 100644
--- a/library/cpp/yt/misc/hash-inl.h
+++ b/library/cpp/yt/misc/hash-inl.h
@@ -4,6 +4,8 @@
 #include "hash.h"
 #endif
 
+#include <cmath>
+
 namespace NYT {
 
 ////////////////////////////////////////////////////////////////////////////////
@@ -29,6 +31,19 @@ void HashCombine(size_t& h, const T& k)
     HashCombine(h, THash<T>()(k));
 }
 
+template <class T>
+Y_FORCE_INLINE size_t NaNSafeHash(const T& value)
+{
+    return ::THash<T>()(value);
+}
+
+template <class T>
+    requires std::is_floating_point_v<T>
+Y_FORCE_INLINE size_t NaNSafeHash(const T& value)
+{
+    return std::isnan(value) ? 0 : ::THash<T>()(value);
+}
+
 ////////////////////////////////////////////////////////////////////////////////
 
 template <class TElement, class TUnderlying>
diff --git a/library/cpp/yt/misc/hash.h b/library/cpp/yt/misc/hash.h
index 2fecf89506..fe4087c331 100644
--- a/library/cpp/yt/misc/hash.h
+++ b/library/cpp/yt/misc/hash.h
@@ -17,6 +17,12 @@ void HashCombine(size_t& h, size_t k);
 template <class T>
 void HashCombine(size_t& h, const T& k);
 
+//! Computes the hash of #value handling NaN values gracefully
+//! (returning the same constant for all NaNs).
+//! If |T| is not a floating-point type, #NaNSafeHash is equivalent to #THash.
+template <class T>
+size_t NaNSafeHash(const T& value);
+
 ////////////////////////////////////////////////////////////////////////////////
 
 //! Provides a hasher that randomizes the results of another one.
@@ -25,12 +31,11 @@ class TRandomizedHash
 {
 public:
     TRandomizedHash();
-    size_t operator () (const TElement& element) const;
+    size_t operator()(const TElement& element) const;
 
 private:
     size_t Seed_;
     TUnderlying Underlying_;
-
 };
 
 ////////////////////////////////////////////////////////////////////////////////
diff --git a/library/cpp/yt/misc/numeric_helpers-inl.h b/library/cpp/yt/misc/numeric_helpers-inl.h
new file mode 100644
index 0000000000..c0dbc07490
--- /dev/null
+++ b/library/cpp/yt/misc/numeric_helpers-inl.h
@@ -0,0 +1,59 @@
+#ifndef NUMERIC_HELPERS_INL_H_
+#error "Direct inclusion of this file is not allowed, include numeric_helpers.h"
+// For the sake of sane code completion.
+#include "numeric_helpers.h"
+#endif
+
+#include <cstdlib>
+#include <cinttypes>
+#include <cmath>
+#include <algorithm>
+
+#include <util/system/compiler.h>
+
+namespace NYT {
+
+////////////////////////////////////////////////////////////////////////////////
+
+template <class T>
+T DivCeil(const T& numerator, const T& denominator)
+{
+    YT_VERIFY(denominator != 0);
+    auto res = std::div(numerator, denominator);
+    return res.quot + (res.rem > static_cast<T>(0) ? static_cast<T>(1) : static_cast<T>(0));
+}
+
+template <typename T>
+T DivRound(const T& numerator, const T& denominator)
+{
+    auto res = std::div(numerator, denominator);
+    return res.quot + (res.rem >= (denominator + 1) / 2 ? static_cast<T>(1) : static_cast<T>(0));
+}
+
+template <class T>
+T RoundUp(const T& numerator, const T& denominator)
+{
+    return DivCeil(numerator, denominator) * denominator;
+}
+
+template <class T>
+T RoundDown(const T& numerator, const T& denominator)
+{
+    return (numerator / denominator) * denominator;
+}
+
+template <class T>
+Y_FORCE_INLINE int GetSign(const T& value)
+{
+    if (value < 0) {
+        return -1;
+    } else if (value > 0) {
+        return +1;
+    } else {
+        return 0;
+    }
+}
+
+////////////////////////////////////////////////////////////////////////////////
+
+} // namespace NYT
diff --git a/library/cpp/yt/misc/numeric_helpers.h b/library/cpp/yt/misc/numeric_helpers.h
new file mode 100644
index 0000000000..20844029c2
--- /dev/null
+++ b/library/cpp/yt/misc/numeric_helpers.h
@@ -0,0 +1,31 @@
+#pragma once
+
+namespace NYT {
+
+////////////////////////////////////////////////////////////////////////////////
+
+template <class T>
+T DivCeil(const T& numerator, const T& denominator);
+
+//! A version of division that is a bit less noisy around the situation
+//! when numerator is almost divisible by denominator. Round up if the remainder
+//! is at least half of denominator, otherwise round down.
+template<class T>
+T DivRound(const T& numerator, const T& denominator);
+
+template <class T>
+T RoundUp(const T& numerator, const T& denominator);
+
+template <class T>
+T RoundDown(const T& numerator, const T& denominator);
+
+template <class T>
+int GetSign(const T& value);
+
+////////////////////////////////////////////////////////////////////////////////
+
+} // namespace NYT
+
+#define NUMERIC_HELPERS_INL_H_
+#include "numeric_helpers-inl.h"
+#undef NUMERIC_HELPERS_INL_H_
diff --git a/library/cpp/yt/misc/unittests/compare_ut.cpp b/library/cpp/yt/misc/unittests/compare_ut.cpp
new file mode 100644
index 0000000000..da149a0690
--- /dev/null
+++ b/library/cpp/yt/misc/unittests/compare_ut.cpp
@@ -0,0 +1,62 @@
+#include <library/cpp/testing/gtest/gtest.h>
+
+#include <library/cpp/yt/misc/compare.h>
+
+namespace NYT {
+namespace {
+
+////////////////////////////////////////////////////////////////////////////////
+
+TEST(TCompareTest, TernaryCompare)
+{
+    EXPECT_EQ(TernaryCompare(123, 123), 0);
+    EXPECT_EQ(TernaryCompare(10, 20), -1);
+    EXPECT_EQ(TernaryCompare(20, 10), +1);
+    EXPECT_EQ(TernaryCompare(std::nan("1"), std::nan("1")), +1);
+    EXPECT_EQ(TernaryCompare(std::nan("1"), std::nan("2")), +1);
+    EXPECT_EQ(TernaryCompare(std::nan("1"), 123.0), +1);
+    EXPECT_EQ(TernaryCompare(123.0, std::nan("1")), +1);
+}
+
+TEST(TCompareTest, NaNSafeTernaryCompare)
+{
+    EXPECT_EQ(NaNSafeTernaryCompare(std::nan("1"), std::nan("1")), 0);
+    EXPECT_EQ(NaNSafeTernaryCompare(std::nan("1"), std::nan("2")), 0);
+    EXPECT_EQ(NaNSafeTernaryCompare(123.0, std::nan("1")), -1);
+    EXPECT_EQ(NaNSafeTernaryCompare(std::nan("1"), 123.0), +1);
+}
+
+////////////////////////////////////////////////////////////////////////////////
+
+template <class T>
+class TTernaryCompareStringTest
+    : public ::testing::Test
+{ };
+
+TYPED_TEST_SUITE_P(TTernaryCompareStringTest);
+
+TYPED_TEST_P(TTernaryCompareStringTest, Compare)
+{
+    EXPECT_EQ(TernaryCompare(TypeParam("abc"), TypeParam("abc")), 0);
+    EXPECT_EQ(TernaryCompare(TypeParam("x"), TypeParam("y")), -1);
+    EXPECT_EQ(TernaryCompare(TypeParam("y"), TypeParam("x")), +1);
+}
+
+REGISTER_TYPED_TEST_SUITE_P(TTernaryCompareStringTest, Compare);
+
+using TTernaryCompareStringTestTypes = ::testing::Types<
+    TString,
+    TStringBuf,
+    std::string,
+    std::string_view
+>;
+
+INSTANTIATE_TYPED_TEST_SUITE_P(
+    TypeParametrized,
+    TTernaryCompareStringTest,
+    TTernaryCompareStringTestTypes);
+
+////////////////////////////////////////////////////////////////////////////////
+
+} // namespace
+} // namespace NYT
diff --git a/library/cpp/yt/misc/unittests/hash_ut.cpp b/library/cpp/yt/misc/unittests/hash_ut.cpp
new file mode 100644
index 0000000000..0c336be5dc
--- /dev/null
+++ b/library/cpp/yt/misc/unittests/hash_ut.cpp
@@ -0,0 +1,19 @@
+#include <library/cpp/testing/gtest/gtest.h>
+
+#include <library/cpp/yt/misc/hash.h>
+
+namespace NYT {
+namespace {
+
+////////////////////////////////////////////////////////////////////////////////
+
+TEST(THashTest, NaNSafeHash)
+{
+    EXPECT_EQ(NaNSafeHash(123), THash<int>()(123));
+    EXPECT_EQ(NaNSafeHash(std::nan("1")), NaNSafeHash(std::nan("2")));
+}
+
+////////////////////////////////////////////////////////////////////////////////
+
+} // namespace
+} // namespace NYT
diff --git a/library/cpp/yt/misc/unittests/ya.make b/library/cpp/yt/misc/unittests/ya.make
index aa6d182c4b..63df71fb83 100644
--- a/library/cpp/yt/misc/unittests/ya.make
+++ b/library/cpp/yt/misc/unittests/ya.make
@@ -4,8 +4,10 @@ INCLUDE(${ARCADIA_ROOT}/library/cpp/yt/ya_cpp.make.inc)
 
 SRCS(
     cast_ut.cpp
+    compare_ut.cpp
     enum_ut.cpp
     guid_ut.cpp
+    hash_ut.cpp
     non_null_ptr_ut.cpp
     preprocessor_ut.cpp
     strong_typedef_ut.cpp