fdo#76260 - switch O(N^2) lookup in SwStyleSheetIterator to O(N)

The SwStyleSheetIterator is called a lot on import of DOCX;
potentially another N times - so this change saves 15%+ of load time,
81bn cycles of 457bn to startup and load the document.

Change-Id: I70ef0f1ebd3f4e05519be68c8a67f65b00f54719

2 files changed, 34 insertions, 12 deletions

diff --git a/sw/inc/docstyle.hxx b/sw/inc/docstyle.hxx
index 63a30e020de5..086207704614 100644
--- a/sw/inc/docstyle.hxx
+++ b/sw/inc/docstyle.hxx
@@ -25,6 +25,7 @@
 #include <svl/style.hxx>
 #include <svl/itemset.hxx>
 #include "swdllapi.h"
+#include <boost/unordered_map.hpp>
 
 #include <vector>
 
@@ -141,10 +142,13 @@ class SwStyleSheetIterator : public SfxStyleSheetIterator, public SfxListener
     class SwPoolFmtList
     {
         std::vector<OUString> maImpl;
+        typedef boost::unordered_map<OUString, sal_uInt32, OUStringHash> UniqueHash;
+        UniqueHash maUnique;
+        void rehash();
     public:
         SwPoolFmtList() {}
         void Append( char cChar, const OUString& rStr );
-        void Erase() { maImpl.clear(); }
+        void clear() { maImpl.clear(); maUnique.clear(); }
         size_t size() { return maImpl.size(); }
         bool empty() { return maImpl.empty(); }
         sal_uInt32 FindName(SfxStyleFamily eFam, const OUString &rName);
diff --git a/sw/source/uibase/app/docstyle.cxx b/sw/source/uibase/app/docstyle.cxx
index 146022b1e2b7..3f09c0f5110e 100644
--- a/sw/source/uibase/app/docstyle.cxx
+++ b/sw/source/uibase/app/docstyle.cxx
@@ -321,31 +321,49 @@ sal_uInt32 SwStyleSheetIterator::SwPoolFmtList::FindName(SfxStyleFamily eFam,
             break;
         }
         const OUString sSrch = OUString(cStyle) + rName;
-        for(size_t i = 0; i < maImpl.size(); ++i)
-            if(maImpl[i] == sSrch)
-                return i;
+
+        UniqueHash::const_iterator it = maUnique.find(sSrch);
+        if (it != maUnique.end())
+        {
+            sal_uInt32 nIdx = it->second;
+            assert (nIdx < maImpl.size());
+            assert (maImpl.size() == maUnique.size());
+            return nIdx;
+        }
     }
     return SAL_MAX_UINT32;
 }
 
+void SwStyleSheetIterator::SwPoolFmtList::rehash()
+{
+    maUnique.clear();
+    for (size_t i = 0; i < maImpl.size(); i++)
+        maUnique[maImpl[i]] = i;
+    assert (maImpl.size() == maUnique.size());
+}
+
 void SwStyleSheetIterator::SwPoolFmtList::RemoveName(SfxStyleFamily eFam,
                                                      const OUString &rName)
 {
     sal_uInt32 nTmpPos = FindName( eFam, rName );
     if( nTmpPos < maImpl.size() )
         maImpl.erase(maImpl.begin() + nTmpPos);
+
+    // assumption: this seldom occurs, the iterator is built, then emptied.
+    rehash();
+    assert (maImpl.size() == maUnique.size());
 }
 
 // Add Strings to the list of templates
 void SwStyleSheetIterator::SwPoolFmtList::Append( char cChar, const OUString& rStr )
 {
     const OUString aStr = OUString(cChar) + rStr;
-    for(std::vector<OUString>::const_iterator i = maImpl.begin();
-        i != maImpl.end(); ++i)
-    {
-        if(*i == aStr)
-            return;
-    }
+
+    UniqueHash::const_iterator it = maUnique.find(aStr);
+    if (it != maUnique.end())
+        return;
+
+    maUnique[aStr] = (sal_uInt32)maImpl.size();
     maImpl.push_back(aStr);
 }
 
@@ -2553,7 +2571,7 @@ SfxStyleSheetBase*  SwStyleSheetIterator::First()
     // Delete old list
     bFirstCalled = true;
     nLastPos = 0;
-    aLst.Erase();
+    aLst.clear();
 
     // Delete current
     mxIterSheet->Reset();
@@ -3010,7 +3028,7 @@ void SwStyleSheetIterator::InvalidateIterator()
     // this iterator not use a map?
     bFirstCalled = false;
     nLastPos = 0;
-    aLst.Erase();
+    aLst.clear();
 }
 
 void SwStyleSheetIterator::Notify( SfxBroadcaster&, const SfxHint& rHint )