summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorChristoph Lutz <chrlutz@googlemail.com>2011-09-06 19:01:19 +0200
committerBjoern Michaelsen <bjoern.michaelsen@canonical.com>2011-09-06 19:04:00 +0200
commite024f616934bb78fba8c8101264806d507068d7e (patch)
tree567c315ecf2f493b67c271e68721c2e3f308a968
parentb8162ca024faf539e5e5ae62d39ccaa03b71e82e (diff)
i#118224: kill O(n^2) complexity of unique bookmark name creation
-rw-r--r--sw/source/core/doc/docbm.cxx29
-rw-r--r--sw/source/core/inc/MarkManager.hxx8
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;
};
}}