From e024f616934bb78fba8c8101264806d507068d7e Mon Sep 17 00:00:00 2001
From: Christoph Lutz <chrlutz@googlemail.com>
Date: Tue, 6 Sep 2011 19:01:19 +0200
Subject: i#118224: kill O(n^2) complexity of unique bookmark name creation

---
 sw/source/core/doc/docbm.cxx       | 29 +++++++++++++++++++++++++----
 sw/source/core/inc/MarkManager.hxx |  8 ++++++++
 2 files changed, 33 insertions(+), 4 deletions(-)

diff --git a/sw/source/core/doc/docbm.cxx b/sw/source/core/doc/docbm.cxx
index e667e203872e..99590ba2b175 100644
--- a/sw/source/core/doc/docbm.cxx
+++ b/sw/source/core/doc/docbm.cxx
@@ -390,6 +390,7 @@ namespace sw { namespace mark
             pMarkBase->SetName(getUniqueMarkName(pMarkBase->GetName()));
 
         // register mark
+        m_aMarkNamesSet.insert(pMarkBase->GetName());
         lcl_InsertMarkSorted(m_vMarks, pMark);
         switch(eType)
         {
@@ -484,8 +485,10 @@ namespace sw { namespace mark
             " - Mark is not in my doc.");
         if(io_pMark->GetName() == rNewName)
             return true;
-        if(findMark(rNewName) != getMarksEnd())
+        if(hasMark(rNewName))
             return false;
+        m_aMarkNamesSet.erase(dynamic_cast< ::sw::mark::MarkBase* >(io_pMark)->GetName());
+        m_aMarkNamesSet.insert(rNewName);
         dynamic_cast< ::sw::mark::MarkBase* >(io_pMark)->SetName(rNewName);
         return true;
     }
@@ -737,6 +740,7 @@ namespace sw { namespace mark
         //it anymore.
         pMark_t xHoldPastErase = *aI;
         m_vMarks.erase(aI);
+        m_aMarkNamesSet.erase(ppMark->get()->GetName());
     }
 
     void MarkManager::deleteMark(const IMark* const pMark)
@@ -770,6 +774,7 @@ namespace sw { namespace mark
     {
         m_vFieldmarks.clear();
         m_vBookmarks.clear();
+        m_aMarkNamesSet.clear();
 #if OSL_DEBUG_LEVEL > 1
         for(iterator_t pBkmk = m_vMarks.begin();
             pBkmk != m_vMarks.end();
@@ -831,14 +836,25 @@ namespace sw { namespace mark
         OSL_ENSURE(rName.getLength(),
             "<MarkManager::getUniqueMarkName(..)>"
             " - a name should be proposed");
-        if(findMark(rName) == getMarksEnd()) return rName;
+        if(!hasMark(rName)) return rName;
         ::rtl::OUStringBuffer sBuf;
         ::rtl::OUString sTmp;
-        for(sal_Int32 nCnt = 1; nCnt < SAL_MAX_INT32; nCnt++)
+
+        // try the name "<rName>XXX" (where XXX is a number starting from 1) unless there is
+        // a unused name. Due to performance-reasons (especially in mailmerge-Szenarios) there
+        // is a map m_aMarkBasenameMapUniqueOffset which holds the next possible offset (XXX) for
+        // rName (so there is no need to test for nCnt-values smaller than the offset).
+        sal_Int32 nCnt = 1;
+        MarkBasenameMapUniqueOffset_t::const_iterator aIter = m_aMarkBasenameMapUniqueOffset.find(rName);
+        if(aIter != m_aMarkBasenameMapUniqueOffset.end()) nCnt = aIter->second;
+        while(nCnt < SAL_MAX_INT32)
         {
             sTmp = sBuf.append(rName).append(nCnt).makeStringAndClear();
-            if(findMark(sTmp) == getMarksEnd()) break;
+            nCnt++;
+            if(!hasMark(sTmp)) break;
         }
+        m_aMarkBasenameMapUniqueOffset[rName] = nCnt;
+
         return sTmp;
     }
 
@@ -849,6 +865,11 @@ namespace sw { namespace mark
         sort(m_vFieldmarks.begin(), m_vFieldmarks.end(), &lcl_MarkOrderingByStart);
     }
 
+    bool MarkManager::hasMark(const ::rtl::OUString& rName) const
+    {
+        return (m_aMarkNamesSet.find(rName) != m_aMarkNamesSet.end());
+    }
+
 }} // namespace ::sw::mark
 
 
diff --git a/sw/source/core/inc/MarkManager.hxx b/sw/source/core/inc/MarkManager.hxx
index 415b8e7b6a68..2581d55d22bf 100644
--- a/sw/source/core/inc/MarkManager.hxx
+++ b/sw/source/core/inc/MarkManager.hxx
@@ -31,9 +31,14 @@
 
 #include <IMark.hxx>
 #include <IDocumentMarkAccess.hxx>
+#include <boost/unordered_set.hpp>
+#include <boost/unordered_map.hpp>
 
 namespace sw { namespace mark
 {
+
+    typedef boost::unordered_map<rtl::OUString, sal_Int32, rtl::OUStringHash> MarkBasenameMapUniqueOffset_t;
+
     class MarkManager
         : private ::boost::noncopyable
         , virtual public IDocumentMarkAccess
@@ -72,6 +77,7 @@ namespace sw { namespace mark
             virtual const_iterator_t getMarksEnd() const;
             virtual sal_Int32 getMarksCount() const;
             virtual const_iterator_t findMark(const ::rtl::OUString& rName) const;
+            virtual bool hasMark(const ::rtl::OUString& rName) const;
 
             // bookmarks
             virtual const_iterator_t getBookmarksBegin() const;
@@ -92,6 +98,8 @@ namespace sw { namespace mark
             container_t m_vMarks;
             container_t m_vBookmarks;
             container_t m_vFieldmarks;
+            boost::unordered_set<rtl::OUString, rtl::OUStringHash> m_aMarkNamesSet;
+            mutable MarkBasenameMapUniqueOffset_t m_aMarkBasenameMapUniqueOffset;
             SwDoc * const m_pDoc;
     };
 }}
-- 
cgit v1.2.3