optimize SharedStringPool::purge() and fix tests

which were checking the wrong thing - we don't care
about the input strings to intern(), we care
about which SharedString objects are still alive.

Change-Id: Ia35a173a02a24efb335268dcae4078a956d11098
Reviewed-on: https://gerrit.libreoffice.org/c/core/+/95177
Tested-by: Jenkins
Reviewed-by: Luboš Luňák <l.lunak@collabora.com>

2 files changed, 54 insertions, 21 deletions

diff --git a/svl/qa/unit/svl.cxx b/svl/qa/unit/svl.cxx
index 488cc04ecde7..6b44a96729d1 100644
--- a/svl/qa/unit/svl.cxx
+++ b/svl/qa/unit/svl.cxx
@@ -36,6 +36,7 @@
 #include <unotools/syslocale.hxx>
 
 #include <memory>
+#include <optional>
 #include <unicode/timezone.h>
 
 using namespace ::com::sun::star;
@@ -371,15 +372,11 @@ void Test::testSharedStringPoolPurge()
     CPPUNIT_ASSERT_EQUAL(static_cast<size_t>(0), aPool.getCount());
     CPPUNIT_ASSERT_EQUAL(static_cast<size_t>(0), aPool.getCountIgnoreCase());
 
-    // Now, create string objects on the heap.
-    std::unique_ptr<OUString> pStr1(new OUString("Andy"));
-    std::unique_ptr<OUString> pStr2(new OUString("andy"));
-    std::unique_ptr<OUString> pStr3(new OUString("ANDY"));
-    std::unique_ptr<OUString> pStr4(new OUString("Bruce"));
-    aPool.intern(*pStr1);
-    aPool.intern(*pStr2);
-    aPool.intern(*pStr3);
-    aPool.intern(*pStr4);
+    // Now, create string objects using optional so we can clear them
+    std::optional<svl::SharedString> pStr1 = aPool.intern("Andy");
+    std::optional<svl::SharedString> pStr2 = aPool.intern("andy");
+    std::optional<svl::SharedString> pStr3 = aPool.intern("ANDY");
+    std::optional<svl::SharedString> pStr4 = aPool.intern("Bruce");
 
     CPPUNIT_ASSERT_EQUAL(static_cast<size_t>(4), aPool.getCount());
     CPPUNIT_ASSERT_EQUAL(static_cast<size_t>(2), aPool.getCountIgnoreCase());
diff --git a/svl/source/misc/sharedstringpool.cxx b/svl/source/misc/sharedstringpool.cxx
index 5c26c912bc42..25898084f327 100644
--- a/svl/source/misc/sharedstringpool.cxx
+++ b/svl/source/misc/sharedstringpool.cxx
@@ -31,7 +31,7 @@ struct SharedStringPool::Impl
     mutable osl::Mutex maMutex;
     // set of upper-case, so we can share these as the value in the maStrMap
     std::unordered_set<OUString> maStrPoolUpper;
-    // map with rtl_uString* as key so we can avoid some ref-counting
+    // map with rtl_uString* as value so we can avoid some ref-counting
     std::unordered_map<OUString,rtl_uString*> maStrMap;
     const CharClass& mrCharClass;
 
@@ -57,7 +57,10 @@ SharedString SharedStringPool::intern( const OUString& rStr )
         if (aUpper == rStr)
         {
             auto insertResult = mpImpl->maStrPoolUpper.insert(rStr);
-            mapIt->second = insertResult.first->pData;
+            // need to use the same underlying rtl_uString object so the
+            // upper->upper detection in purge() works
+            auto pData = insertResult.first->pData;
+            mpImpl->maStrMap.insert_or_assign(mapIt, pData, pData);
         }
         else
         {
@@ -72,23 +75,56 @@ void SharedStringPool::purge()
 {
     osl::MutexGuard aGuard(&mpImpl->maMutex);
 
-    std::unordered_set<OUString> aNewStrPoolUpper;
+    // Because we can have an uppercase entry mapped to itself,
+    // and then a bunch of lowercase entries mapped to that same
+    // upper-case entry, we need to scan the map twice - the first
+    // time to remove lowercase entries, and then only can we
+    // check for unused uppercase entries.
+
+    auto it = mpImpl->maStrMap.begin();
+    auto itEnd = mpImpl->maStrMap.end();
+    while (it != itEnd)
     {
-        auto it = mpImpl->maStrMap.begin(), itEnd = mpImpl->maStrMap.end();
-        while (it != itEnd)
+        rtl_uString* p1 = it->first.pData;
+        rtl_uString* p2 = it->second;
+        if (p1 != p2)
         {
-            const rtl_uString* p = it->first.pData;
-            if (getRefCount(p) == 1)
+            // normal case - lowercase mapped to uppercase, which
+            // means that the lowercase entry has one ref-counted
+            // entry as the key in the map
+            if (getRefCount(p1) == 1)
+            {
                 it = mpImpl->maStrMap.erase(it);
-            else
+                // except that the uppercase entry may be mapped to
+                // by other lower-case entries
+                if (getRefCount(p2) == 1)
+                    mpImpl->maStrPoolUpper.erase(OUString::unacquired(&p2));
+                continue;
+            }
+        }
+        ++it;
+    }
+
+    it = mpImpl->maStrMap.begin();
+    itEnd = mpImpl->maStrMap.end();
+    while (it != itEnd)
+    {
+        rtl_uString* p1 = it->first.pData;
+        rtl_uString* p2 = it->second;
+        if (p1 == p2)
+        {
+            // uppercase which is mapped to itself, which means
+            // one ref-counted entry as the key in the map, and
+            // one ref-counted entry in the set
+            if (getRefCount(p1) == 2)
             {
-                // Still referenced outside the pool. Keep it.
-                aNewStrPoolUpper.insert(it->second);
-                ++it;
+                it = mpImpl->maStrMap.erase(it);
+                mpImpl->maStrPoolUpper.erase(OUString::unacquired(&p1));
+                continue;
             }
         }
+        ++it;
     }
-    mpImpl->maStrPoolUpper = std::move(aNewStrPoolUpper);
 }
 
 size_t SharedStringPool::getCount() const