From 61c47d50284e2ac45bfb1641b7f79a350bfaad5a Mon Sep 17 00:00:00 2001 From: Noel Grandin Date: Thu, 19 May 2022 16:31:42 +0200 Subject: optimise NumberedCollection::impl_searchFreeNumber some more Change-Id: I3740bb4f425020eb420fa6217b7c1373befa7e04 Reviewed-on: https://gerrit.libreoffice.org/c/core/+/134646 Tested-by: Jenkins Reviewed-by: Noel Grandin --- comphelper/source/misc/numberedcollection.cxx | 27 ++++++++++----------------- 1 file changed, 10 insertions(+), 17 deletions(-) (limited to 'comphelper') diff --git a/comphelper/source/misc/numberedcollection.cxx b/comphelper/source/misc/numberedcollection.cxx index 59088fe9c6b1..146f002eab3f 100644 --- a/comphelper/source/misc/numberedcollection.cxx +++ b/comphelper/source/misc/numberedcollection.cxx @@ -178,32 +178,25 @@ OUString SAL_CALL NumberedCollection::getUntitledPrefix() */ ::sal_Int32 NumberedCollection::impl_searchFreeNumber () { - // create ordered list of all possible numbers. - std::vector< ::sal_Int32 > lPossibleNumbers; - lPossibleNumbers.reserve(m_lComponents.size() + 1); - ::sal_Int32 c = static_cast<::sal_Int32>(m_lComponents.size ()); - ::sal_Int32 i = 1; - - // c can't be less than 0 ... otherwise hash.size() has an error :-) - // But we need at least n+1 numbers here. - c += 1; - - for (i=1; i<=c; ++i) - lPossibleNumbers.push_back (i); + // create bitset, where each position represents one possible number. + std::vector aUsedNumbers((m_lComponents.size() * 2) + 1, false); for (const auto& rPair : m_lComponents) { - std::vector< ::sal_Int32 >::iterator pPossible = std::find(lPossibleNumbers.begin (), lPossibleNumbers.end (), rPair.second.nNumber); - if (pPossible != lPossibleNumbers.end ()) - lPossibleNumbers.erase (pPossible); + // numbers start at 1 + sal_Int32 pos = rPair.second.nNumber - 1; + if (pos >= static_cast(aUsedNumbers.size())) + aUsedNumbers.resize(pos * 2, false); // should be rare + aUsedNumbers[pos] = true; } // a) non free numbers ... return INVALID_NUMBER - if (lPossibleNumbers.empty()) + auto it = std::find(aUsedNumbers.begin(), aUsedNumbers.end(), false); + if (it == aUsedNumbers.end()) return css::frame::UntitledNumbersConst::INVALID_NUMBER; // b) return first free number - return *(lPossibleNumbers.begin ()); + return it - aUsedNumbers.begin() + 1; } void NumberedCollection::impl_cleanUpDeadItems ( TNumberedItemHash& lItems , -- cgit