Reworked HashMapStringKey class to keep only one pointer

1 files changed, 65 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