Merge pull request #8 from SergeyMakeev/erase_now_returns_a_valid_ite…

…rator `Erase()` now returns an iterator following the last removed element (similar to std) The following code is now formally "legalized" and covered with unit tests. ``` Excalibur::HashTable<int, int> ht; for (auto it = ht.ibegin(); it != ht.iend(); ++it) { if (...condition...) { it = ht.erase(it); } } ```
SergeyMakeev · Jan 23, 2024 · 2cd900f · 2cd900f
2 parents 7b21ef7 + 2f91aeb
commit 2cd900f
Show file tree

Hide file tree

Showing 2 changed files with 193 additions and 16 deletions.
diff --git a/ExcaliburHash/ExcaliburHash.h b/ExcaliburHash/ExcaliburHash.h
@@ -52,7 +52,6 @@
     #endif
 #endif
 
-
 namespace Excalibur
 {
 
@@ -419,9 +418,30 @@ template <typename TKey, typename TValue, typename TKeyInfo = KeyInfo<TKey>> cla
             return m_item->value();
         }
 
+        static TItem* getNextValidItem(TItem* item, TItem* endItem) noexcept
+        {
+            do
+            {
+                item++;
+            } while (item < endItem && !item->isValid());
+            return item;
+        }
+
+        void copyFrom(const IteratorBase& other)
+        {
+            m_ht = other.m_ht;
+            m_item = other.m_item;
+        }
+
       public:
         IteratorBase() = delete;
 
+        IteratorBase(const IteratorBase& other) noexcept
+            : m_ht(other.m_ht)
+            , m_item(other.m_item)
+        {
+        }
+
         IteratorBase(const HashTable* ht, TItem* item) noexcept
             : m_ht(ht)
             , m_item(item)
@@ -442,13 +462,7 @@ template <typename TKey, typename TValue, typename TKeyInfo = KeyInfo<TKey>> cla
         IteratorBase& operator++() noexcept
         {
             TItem* endItem = m_ht->m_storage + m_ht->m_numBuckets;
-            TItem* EXLBR_RESTRICT item = m_item;
-            do
-            {
-                item++;
-            } while (item < endItem && !item->isValid());
-
-            m_item = item;
+            m_item = getNextValidItem(m_item, endItem);
             return *this;
         }
 
@@ -534,6 +548,19 @@ template <typename TKey, typename TValue, typename TKeyInfo = KeyInfo<TKey>> cla
       public:
         TIteratorKV() = delete;
 
+        TIteratorKV(const TIteratorKV& other)
+            : IteratorBase(other)
+            , tmpKv(reference<const TKey>(nullptr), reference<TIteratorValue>(nullptr))
+        {
+        }
+
+        TIteratorKV& operator=(const TIteratorKV& other) noexcept
+        {
+            IteratorBase::copyFrom(other);
+            // note: we'll automatically update tmpKv on the next access = no need to copy
+            return *this;
+        }
+
         TIteratorKV(const HashTable* ht, TItem* item) noexcept
             : IteratorBase(ht, item)
             , tmpKv(reference<const TKey>(nullptr), reference<TIteratorValue>(nullptr))
@@ -729,11 +756,14 @@ template <typename TKey, typename TValue, typename TKeyInfo = KeyInfo<TKey>> cla
         return IteratorKV(this, item);
     }
 
-    inline bool erase(const IteratorBase it)
+    inline TItem* eraseImpl(const IteratorBase it)
     {
+        TItem* EXLBR_RESTRICT item = m_storage;
+        TItem* const endItem = item + m_numBuckets;
+
         if (it == IteratorHelper<IteratorBase>::end(*this))
         {
-            return false;
+            return endItem;
         }
 
         EXLBR_ASSERT(m_numElements != 0);
@@ -748,25 +778,72 @@ template <typename TKey, typename TValue, typename TKeyInfo = KeyInfo<TKey>> cla
         // hash table now is empty. convert all tombstones to empty keys
         if (m_numElements == 0)
         {
-            TItem* EXLBR_RESTRICT item = m_storage;
-            TItem* const endItem = item + m_numBuckets;
             for (; item != endItem; item++)
             {
                 *item->key() = TKeyInfo::getEmpty();
             }
-            return true;
+            return endItem;
         }
 
         // overwrite key with empty key
         TKey* itemKey = const_cast<TKey*>(it.getKey());
         *itemKey = TKeyInfo::getTombstone();
-        return true;
+        return IteratorBase::getNextValidItem(it.m_item, endItem);
+    }
+
+    inline IteratorKV erase(const IteratorKV& it)
+    {
+        TItem* item = eraseImpl(it);
+        return IteratorKV(this, item);
     }
 
+    inline ConstIteratorKV erase(const ConstIteratorKV& it)
+    {
+        TItem* item = eraseImpl(it);
+        return ConstIteratorKV(this, item);
+    }
+
+    /*
+        inline bool erase(const IteratorBase it)
+        {
+            if (it == IteratorHelper<IteratorBase>::end(*this))
+            {
+                return false;
+            }
+
+            EXLBR_ASSERT(m_numElements != 0);
+            m_numElements--;
+
+            if constexpr ((!std::is_trivially_destructible<TValue>::value) && (has_values::value))
+            {
+                TValue* itemValue = const_cast<TValue*>(it.getValue());
+                destruct(itemValue);
+            }
+
+            // hash table now is empty. convert all tombstones to empty keys
+            if (m_numElements == 0)
+            {
+                TItem* EXLBR_RESTRICT item = m_storage;
+                TItem* const endItem = item + m_numBuckets;
+                for (; item != endItem; item++)
+                {
+                    *item->key() = TKeyInfo::getEmpty();
+                }
+                return true;
+            }
+
+            // overwrite key with empty key
+            TKey* itemKey = const_cast<TKey*>(it.getKey());
+            *itemKey = TKeyInfo::getTombstone();
+            return true;
+        }
+    */
+
     inline bool erase(const TKey& key)
     {
         auto it = find(key);
-        return erase(it);
+        erase(it);
+        return (it != iend());
     }
 
     inline bool reserve(uint32_t numBucketsNew)

diff --git a/ExcaliburHashTest04.cpp b/ExcaliburHashTest04.cpp
@@ -1,6 +1,23 @@
 #include "ExcaliburHash.h"
 #include "gtest/gtest.h"
 #include <array>
+#include <cstring>
+
+namespace Excalibur
+{
+template <> struct KeyInfo<std::string>
+{
+    static inline bool isValid(const std::string& key) noexcept { return !key.empty() && key.data()[0] != char(1); }
+    static inline std::string getTombstone() noexcept
+    {
+        // and let's hope that small string optimization will do the job
+        return std::string(1, char(1));
+    }
+    static inline std::string getEmpty() noexcept { return std::string(); }
+    static inline uint64_t hash(const std::string& key) noexcept { return std::hash<std::string>{}(key); }
+    static inline bool isEqual(const std::string& lhs, const std::string& rhs) noexcept { return lhs == rhs; }
+};
+} // namespace Excalibur
 
 struct ComplexValue
 {
@@ -49,7 +66,6 @@ struct ComplexValue
     bool isDeleted;
 };
 
-
 TEST(SmFlatHashMap, InsertFromItselfWhileGrow)
 {
     for (int i = 1; i <= 1000; i++)
@@ -77,3 +93,87 @@ TEST(SmFlatHashMap, InsertFromItselfWhileGrow)
         ASSERT_NE(it2, ht.end());
     }
 }
+
+TEST(SmFlatHashMap, CopyableIterators)
+{
+    Excalibur::HashTable<std::string, std::string> ht;
+
+    int sum = 0;
+    for (int i = 1; i <= 16; i++)
+    {
+        ht.emplace(std::to_string(i), std::to_string(i + 1));
+        sum += i;
+    }
+
+    Excalibur::HashTable<std::string, std::string>::IteratorKV it = ht.find(std::to_string(1));
+    ASSERT_NE(it, ht.end());
+    const std::string& val = it->second;
+
+    Excalibur::HashTable<std::string, std::string>::IteratorKV it2 = it;
+    ASSERT_NE(it2, ht.end());
+    const std::string& val2 = it2->second;
+
+    EXPECT_EQ(it, it2);
+    EXPECT_EQ(val, val2);
+
+    ++it2;
+    EXPECT_NE(it, it2);
+
+    it2 = it;
+    EXPECT_EQ(it, it2);
+
+    // capture before state
+    std::vector<std::string> before;
+    {
+        for (auto it3 = ht.ibegin(); it3 != ht.iend(); ++it3)
+        {
+            before.emplace_back(it3->first);
+        }
+        std::sort(before.begin(), before.end());
+    }
+
+
+    // iterate and remove
+    {
+        for (Excalibur::HashTable<std::string, std::string>::IteratorKV it3 = ht.ibegin(); it3 != ht.iend(); ++it3)
+        {
+            if (std::strcmp(it3->first.get().c_str(), "5") == 0)
+            {
+                it3 = ht.erase(it3);
+            }
+
+            if (std::strcmp(it3->first.get().c_str(), "9") == 0)
+            {
+                it3 = ht.erase(it3);
+            }
+        }
+    }
+
+    // capture after state
+    std::vector<std::string> after;
+    {
+        for (auto it3 = ht.ibegin(); it3 != ht.iend(); ++it3)
+        {
+            after.emplace_back(it3->first);
+        }
+
+        std::sort(after.begin(), after.end());
+    }
+
+    // make sure we've got the expected results
+    int sumBefore = 0;
+    for (const std::string& v : before)
+    {
+        int iv = std::stoi(v);
+        sumBefore += iv;
+    }
+    EXPECT_EQ(sumBefore, sum);
+
+    int sumAfter = 0;
+    for (const std::string& v : after)
+    {
+        int iv = std::stoi(v);
+        sumAfter += iv;
+    }
+    EXPECT_EQ(sumBefore-5-9, sumAfter);
+}