Reworked HashMapStringKey class to keep only one pointer

2 files changed, 184 insertions, 49 deletions

diff --git a/Common/interface/HashUtils.hpp b/Common/interface/HashUtils.hpp
index a2f998a6..e3de5e92 100644
--- a/Common/interface/HashUtils.hpp
+++ b/Common/interface/HashUtils.hpp
@@ -95,83 +95,109 @@ struct CStringCompare<Char>
 
 /// This helper structure is intended to facilitate using strings as a
 /// hash table key. It provides constructors that can make a copy of the
-/// source string or just keep pointer to it, which enables searching in
+/// source string or just keep a pointer to it, which enables searching in
 /// the hash using raw const Char* pointers.
 struct HashMapStringKey
 {
 public:
     // This constructor can perform implicit const Char* -> HashMapStringKey
-    // conversion without copying the string
-    HashMapStringKey(const Char* Str, bool bMakeCopy = false) :
-        StrPtr{nullptr},
-        Hash{0}
+    // conversion without copying the string.
+    HashMapStringKey(const Char* _Str, bool bMakeCopy = false) :
+        Str{_Str}
     {
-        VERIFY(Str, "String pointer cannot be null");
+        VERIFY(Str, "String pointer must not be null");
+
+        Ownership_Hash = CStringHash<Char>{}.operator()(Str) & HashMask;
         if (bMakeCopy)
         {
-            MakeCopy(Str);
-        }
-        else
-        {
-            StrPtr = Str;
+            auto  LenWithZeroTerm = strlen(Str) + 1;
+            auto* StrCopy         = new char[LenWithZeroTerm];
+            memcpy(StrCopy, Str, LenWithZeroTerm);
+            Str = StrCopy;
+            Ownership_Hash |= StrOwnershipMask;
         }
     }
 
-    explicit // Make this constructor explicit to avoid unintentional string copies
-        HashMapStringKey(const String& Str) :
-        StrPtr{nullptr},
-        Hash{0}
+    // Make this constructor explicit to avoid unintentional string copies
+    explicit HashMapStringKey(const String& Str) :
+        HashMapStringKey{Str.c_str(), true}
     {
-        MakeCopy(Str.c_str());
     }
 
     HashMapStringKey(HashMapStringKey&& Key) noexcept :
         // clang-format off
-        StringBuff{std::move(Key.StringBuff)},
-        StrPtr    {std::move(Key.StrPtr)},
-        Hash      {0}
+        Str {Key.Str},
+        Ownership_Hash{Key.Ownership_Hash}
     // clang-format on
     {
-        Key.StrPtr = nullptr;
-        Key.Hash   = 0;
+        Key.Str            = nullptr;
+        Key.Ownership_Hash = 0;
+    }
+
+    ~HashMapStringKey()
+    {
+        if (Str != nullptr && (Ownership_Hash & StrOwnershipMask) != 0)
+            delete[] Str;
     }
 
     // Disable copy constuctor and assignments. The struct is designed
-    // to be initialized at creation time only
+    // to be initialized at creation time only.
     // clang-format off
     HashMapStringKey           (const HashMapStringKey&) = delete;
     HashMapStringKey& operator=(const HashMapStringKey&) = delete;
     HashMapStringKey& operator=(HashMapStringKey&&)      = delete;
     // clang-format on
 
-    // Comparison operator
     bool operator==(const HashMapStringKey& RHS) const
     {
-        if (StrPtr == RHS.StrPtr)
+        if (Str == RHS.Str)
             return true;
 
-        // Hash member might not have been initialized
-        if ((Hash != 0 && RHS.Hash != 0 && Hash != RHS.Hash) || StrPtr == nullptr || RHS.StrPtr == nullptr)
+        if (Str == nullptr)
+        {
+            VERIFY_EXPR(RHS.Str != nullptr);
+            return false;
+        }
+        else if (RHS.Str == nullptr)
+        {
+            VERIFY_EXPR(Str != nullptr);
             return false;
+        }
 
-        bool IsEqual = strcmp(StrPtr, RHS.StrPtr) == 0;
+        auto Hash    = GetHash();
+        auto RHSHash = RHS.GetHash();
+        if (Hash != RHSHash)
+        {
+            VERIFY_EXPR(strcmp(Str, RHS.Str) != 0);
+            return false;
+        }
+
+        bool IsEqual = strcmp(Str, RHS.Str) == 0;
 
 #if LOG_HASH_CONFLICTS
-        if (Hash != 0 && RHS.Hash != 0 && Hash == RHS.Hash && !IsEqual)
+        if (!IsEqual && Hash == RHSHash)
         {
-            LOG_WARNING_MESSAGE("Unequal strings \"", StrPtr, "\" and \"", RHS.StrPtr, "\" hashed to the same bucket. "
-                                                                                       "You may want to use better hash function. You may disable this warning by defining LOG_HASH_CONFLICTS to 0");
+            LOG_WARNING_MESSAGE("Unequal strings \"", Str, "\" and \"", RHS.Str,
+                                "\" have the same hash. You may want to use a better hash function. "
+                                "You may disable this warning by defining LOG_HASH_CONFLICTS to 0");
         }
 #endif
         return IsEqual;
     }
 
+    bool operator!=(const HashMapStringKey& RHS) const
+    {
+        return !(*this == RHS);
+    }
+
     size_t GetHash() const
     {
-        if (Hash == 0)
-            Hash = CStringHash<Char>()(StrPtr);
+        return Ownership_Hash & HashMask;
+    }
 
-        return Hash;
+    const Char* GetStr() const
+    {
+        return Str;
     }
 
     struct Hasher
@@ -182,24 +208,14 @@ public:
         }
     };
 
-    const Char* GetStr() const { return StrPtr; }
-
 private:
-    void MakeCopy(const Char* Str)
-    {
-        auto LenWithZeroTerm = strlen(Str) + 1;
-        StringBuff.reset(new char[LenWithZeroTerm]);
-        memcpy(StringBuff.get(), Str, LenWithZeroTerm);
-        StrPtr = StringBuff.get();
-    }
+    static constexpr size_t StrOwnershipBit  = sizeof(size_t) * 8 - 1;
+    static constexpr size_t StrOwnershipMask = size_t{1} << StrOwnershipBit;
+    static constexpr size_t HashMask         = ~StrOwnershipMask;
 
-    //                  !!! WARNING !!!
-    // We can't use String to store the buffer, because String default
-    // constructor always allocates memory even when the string is empty,
-    // nor can we use vector for the same reason
-    std::unique_ptr<Char[]> StringBuff; // Must be declared first
-    const Char*             StrPtr;     // Must be declared after StringBuff
-    mutable size_t          Hash;
+    const Char* Str = nullptr;
+    // We will use top bit of the hash to indicate if we own the pointer
+    size_t Ownership_Hash = 0;
 };
 
 } // namespace Diligent
diff --git a/Tests/DiligentCoreTest/src/Common/HashUtilsTest.cpp b/Tests/DiligentCoreTest/src/Common/HashUtilsTest.cpp
new file mode 100644
index 00000000..1f46f3dc
--- /dev/null
+++ b/Tests/DiligentCoreTest/src/Common/HashUtilsTest.cpp
@@ -0,0 +1,119 @@
+/*
+ *  Copyright 2019-2020 Diligent Graphics LLC
+ *  Copyright 2015-2019 Egor Yusov
+ *  
+ *  Licensed under the Apache License, Version 2.0 (the "License");
+ *  you may not use this file except in compliance with the License.
+ *  You may obtain a copy of the License at
+ *  
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *  
+ *  Unless required by applicable law or agreed to in writing, software
+ *  distributed under the License is distributed on an "AS IS" BASIS,
+ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *  See the License for the specific language governing permissions and
+ *  limitations under the License.
+ *
+ *  In no event and under no legal theory, whether in tort (including negligence), 
+ *  contract, or otherwise, unless required by applicable law (such as deliberate 
+ *  and grossly negligent acts) or agreed to in writing, shall any Contributor be
+ *  liable for any damages, including any direct, indirect, special, incidental, 
+ *  or consequential damages of any character arising as a result of this License or 
+ *  out of the use or inability to use the software (including but not limited to damages 
+ *  for loss of goodwill, work stoppage, computer failure or malfunction, or any and 
+ *  all other commercial damages or losses), even if such Contributor has been advised 
+ *  of the possibility of such damages.
+ */
+
+#include <unordered_map>
+
+#include "HashUtils.hpp"
+
+#include "gtest/gtest.h"
+
+using namespace Diligent;
+
+namespace
+{
+
+TEST(Common_HashUtils, HashMapStringKey)
+{
+    {
+        const char* Str = "Test String";
+
+        HashMapStringKey Key1{Str};
+        EXPECT_EQ(Key1.GetStr(), Str);
+        EXPECT_STREQ(Key1.GetStr(), Str);
+
+        HashMapStringKey Key2{Str, true};
+        EXPECT_NE(Key2.GetStr(), Str);
+        EXPECT_STREQ(Key2.GetStr(), Str);
+
+        EXPECT_EQ(Key1, Key1);
+        EXPECT_EQ(Key2, Key2);
+        EXPECT_EQ(Key1, Key2);
+
+        HashMapStringKey Key3{std::string{Str}};
+        EXPECT_NE(Key3.GetStr(), Str);
+        EXPECT_STREQ(Key3.GetStr(), Str);
+
+        EXPECT_EQ(Key3, Key1);
+        EXPECT_EQ(Key3, Key2);
+        EXPECT_EQ(Key3, Key3);
+    }
+
+    {
+        const char*      Str1 = "Test String 1";
+        const char*      Str2 = "Test String 2";
+        HashMapStringKey Key1{Str1};
+        HashMapStringKey Key2{Str2, true};
+        EXPECT_NE(Key1, Key2);
+
+        HashMapStringKey Key3{std::move(Key1)};
+        EXPECT_NE(Key1, Key2);
+        EXPECT_NE(Key2, Key1);
+
+        HashMapStringKey Key4{std::move(Key2)};
+        EXPECT_EQ(Key1, Key2);
+        EXPECT_EQ(Key2, Key1);
+        EXPECT_NE(Key3, Key4);
+    }
+
+    {
+        std::unordered_map<HashMapStringKey, int, HashMapStringKey::Hasher> TestMap;
+
+        const char* Str1 = "String1";
+        const char* Str2 = "String2";
+        const char* Str3 = "String3";
+        const int   Val1 = 1;
+        const int   Val2 = 2;
+
+        auto it_ins = TestMap.emplace(HashMapStringKey{Str1, true}, Val1);
+        EXPECT_TRUE(it_ins.second);
+        EXPECT_NE(it_ins.first->first.GetStr(), Str1);
+        EXPECT_STREQ(it_ins.first->first.GetStr(), Str1);
+
+        it_ins = TestMap.emplace(Str2, Val2);
+        EXPECT_TRUE(it_ins.second);
+        EXPECT_EQ(it_ins.first->first, Str2);
+
+        auto it = TestMap.find(Str1);
+        ASSERT_NE(it, TestMap.end());
+        EXPECT_EQ(it->second, Val1);
+        EXPECT_NE(it->first.GetStr(), Str1);
+        EXPECT_STREQ(it->first.GetStr(), Str1);
+
+        it = TestMap.find(Str2);
+        ASSERT_NE(it, TestMap.end());
+        EXPECT_EQ(it->second, Val2);
+        EXPECT_EQ(it->first.GetStr(), Str2);
+
+        it = TestMap.find(Str3);
+        EXPECT_EQ(it, TestMap.end());
+
+        it = TestMap.find(HashMapStringKey{std::string{Str3}});
+        EXPECT_EQ(it, TestMap.end());
+    }
+}
+
+} // namespace