Optimize lcl_GetUniqueFlyName

(cherry picked from commit 403b074a707b2f13e8fb814f537ffb08d7f9b3ed)

Conflicts:

	sw/source/core/doc/docfmt.cxx
	sw/source/core/doc/doclay.cxx

Change-Id: Ic894ee471982496ac82dc426c803aba92b8554c2

3 files changed, 100 insertions, 29 deletions

diff --git a/sw/inc/docary.hxx b/sw/inc/docary.hxx
index 209d0da21803..ccc3e775aba9 100644
--- a/sw/inc/docary.hxx
+++ b/sw/inc/docary.hxx
@@ -103,9 +103,11 @@ struct SwFrmFmtSearch
 {
     sal_uInt16 type;
     const OUString& name;
+    sal_Int32 length;
 
-    SwFrmFmtSearch( sal_uInt16 _type, const OUString& _name )
-        :type( _type ), name( _name ) {}
+    SwFrmFmtSearch( sal_uInt16 _type,
+                    const OUString& _name, sal_Int32 _length )
+        :type( _type ), name( _name ), length( _length ) {}
 };
 
 struct CompareSwFrmFmts
@@ -115,6 +117,12 @@ struct CompareSwFrmFmts
     bool operator()(SwFrmFmtSearch const& lhs, SwFrmFmt* const& rhs) const;
 };
 
+struct PrefixCompareSwFrmFmts
+{
+    bool operator()(SwFrmFmt* const& lhs, SwFrmFmtSearch const& rhs) const;
+    bool operator()(SwFrmFmtSearch const& lhs, SwFrmFmt* const& rhs) const;
+};
+
 typedef o3tl::sorted_vector<SwFrmFmt*, CompareSwFrmFmts,
                             o3tl::find_partialorder_ptrequals> SwFrmFmtsBase;
 
@@ -142,9 +150,11 @@ public:
 
     const_iterator find( const value_type& x ) const;
     std::pair<const_iterator,const_iterator>
-        findRange( const value_type& x, bool& root ) const;
+        findRange( const value_type& x,
+                   bool& root, sal_Int32 length=-1 ) const;
     std::pair<const_iterator,const_iterator>
-        findRange( sal_uInt16 type, const OUString& name, bool& root ) const;
+        findRange( sal_uInt16 type, const OUString& name,
+                   bool& root, sal_Int32 length=-1 ) const;
 
     bool Contains( const value_type& x ) const;
 
diff --git a/sw/source/core/doc/docfmt.cxx b/sw/source/core/doc/docfmt.cxx
index 5926cd62b8be..48b47be03e60 100644
--- a/sw/source/core/doc/docfmt.cxx
+++ b/sw/source/core/doc/docfmt.cxx
@@ -2668,14 +2668,21 @@ SwFrmFmts::const_iterator SwFrmFmts::find( const value_type& x ) const
 }
 
 std::pair<SwFrmFmts::const_iterator,SwFrmFmts::const_iterator>
-SwFrmFmts::findRange( sal_uInt16 type, const OUString& name, bool& root ) const
+SwFrmFmts::findRange( sal_uInt16 type, const OUString& name, bool& root, sal_Int32 length ) const
 {
-    SwFrmFmtSearch x( type, name );
+    SwFrmFmtSearch x( type, name, length );
     std::pair<const_iterator, const_iterator> ret(end(), end());
     if ( !empty() ) {
-        ret = std::equal_range(begin() + GetOffset(), end(), x, CompareSwFrmFmts());
-        root = (front()->Which() == type
-             && front()->GetName().CompareTo( name ) == 0);
+        if ( length >= 0 ) {
+            ret = std::equal_range(begin() + GetOffset(), end(), x, PrefixCompareSwFrmFmts());
+            root = (front()->Which() == type
+                 && front()->GetName().CompareTo( name, length ) == 0);
+        }
+        else {
+            ret = std::equal_range(begin() + GetOffset(), end(), x, CompareSwFrmFmts());
+            root = (front()->Which() == type
+                 && front()->GetName().CompareTo( name ) == 0);
+        }
     }
     else
         root = false;
@@ -2683,9 +2690,9 @@ SwFrmFmts::findRange( sal_uInt16 type, const OUString& name, bool& root ) const
 }
 
 std::pair<SwFrmFmts::const_iterator,SwFrmFmts::const_iterator>
-SwFrmFmts::findRange( const value_type& x, bool& root ) const
+SwFrmFmts::findRange( const value_type& x, bool& root, sal_Int32 length ) const
 {
-    return findRange( x->Which(), x->GetName(), root );
+    return findRange( x->Which(), x->GetName(), root, length );
 }
 
 bool CompareSwFrmFmts::operator()(SwFrmFmt* const& lhs, SwFrmFmt* const& rhs) const
@@ -2715,6 +2722,24 @@ bool CompareSwFrmFmts::operator()(SwFrmFmtSearch const& lhs, SwFrmFmt* const& rh
     return (lhs.name.compareTo( rhs->GetName() ) < 0);
 }
 
+bool PrefixCompareSwFrmFmts::operator()(SwFrmFmt* const& lhs, SwFrmFmtSearch const& rhs) const
+{
+    if (lhs->Which() < rhs.type)
+        return true;
+    if (lhs->Which() > rhs.type)
+        return false;
+    return (lhs->GetName().CompareTo( rhs.name, rhs.length ) < 0);
+}
+
+bool PrefixCompareSwFrmFmts::operator()(SwFrmFmtSearch const& lhs, SwFrmFmt* const& rhs) const
+{
+    if (lhs.type < rhs->Which())
+        return true;
+    if (lhs.type > rhs->Which())
+        return false;
+    return (lhs.name.compareTo( rhs->GetName(), lhs.length ) < 0);
+}
+
 SwFrmFmts::find_insert_type SwFrmFmts::insert( const value_type& x, bool isNewRoot )
 {
     find_insert_type ret = SwFrmFmtsBase::insert( x );
diff --git a/sw/source/core/doc/doclay.cxx b/sw/source/core/doc/doclay.cxx
index 245b2b9040e0..3097633a3aff 100644
--- a/sw/source/core/doc/doclay.cxx
+++ b/sw/source/core/doc/doclay.cxx
@@ -1913,36 +1913,72 @@ static String lcl_GetUniqueFlyName( const SwDoc* pDoc, sal_uInt16 nDefStrId )
 
     const SwFrmFmts& rFmts = *pDoc->GetSpzFrmFmts();
 
+    // prepare the bitfield to flag found numbers
     sal_uInt16 nNum, nTmp, nFlagSize = ( rFmts.size() / 8 ) +2;
     sal_uInt8* pSetFlags = new sal_uInt8[ nFlagSize ];
-    sal_uInt16 n;
-
     memset( pSetFlags, 0, nFlagSize );
 
-    for( n = 0; n < rFmts.size(); ++n )
-    {
-        const SwFrmFmt* pFlyFmt = rFmts[ n ];
-        if( RES_FLYFRMFMT == pFlyFmt->Which() &&
-            pFlyFmt->GetName().Match( aName ) == nNmLen )
-        {
-            // Only get and set the Flag
-            nNum = static_cast< sal_uInt16 >( rtl_ustr_toInt32( pFlyFmt->GetName().GetBuffer() + nNmLen, 10 ) );
-            if( nNum-- && nNum < rFmts.size() )
-                pSetFlags[ nNum / 8 ] |= (0x01 << ( nNum & 0x07 ));
+    // find the range of fly names with common prefix
+    bool root;
+    const std::pair<SwFrmFmts::const_iterator,SwFrmFmts::const_iterator>
+        range = rFmts.findRange( RES_FLYFRMFMT, aName, root, nNmLen );
+    SwFrmFmts::const_iterator it = range.first;
+    sal_uInt16 n = 0;
+    bool found = false;
+
+    // check all number postfixes to find the first free number
+    while ( root || (it != range.second) ) {
+        const SwFrmFmt* pFlyFmt;
+        if ( root )
+            pFlyFmt = rFmts[ 0 ];
+        else {
+            pFlyFmt = *it;
+            it++;
+        }
+
+        // get / set the flag for the number
+        nNum = static_cast< sal_uInt16 >( rtl_ustr_toInt32( pFlyFmt->GetName().GetBuffer() + nNmLen, 10 ) );
+        if( nNum-- && nNum < rFmts.size() ) {
+            pSetFlags[ nNum / 8 ] |= (0x01 << ( nNum & 0x07 ));
+            if ( root ) {
+                // don't inc n for root; number can be everywhere
+                root = false;
+                continue;
+            }
+            else
+                n++;
+        }
+        else {
+            if ( root )
+                root = false;
+            continue;
+        }
+
+        // after 8 conversions, we can check for a hole, because the list is sorted
+        if( 0 == n % 8 ) {
+            if( 0xff != ( nTmp = pSetFlags[ n / 8 - 1 ] ))
+            {
+                // so determine the number
+                nNum = n - 8;
+                while( nTmp & 1 )
+                    ++nNum, nTmp >>= 1;
+                found = true;
+                break;
+            }
         }
     }
 
-    // All numbers are flagged accordingly, so determine the right one
-    nNum = rFmts.size();
-    for( n = 0; n < nFlagSize; ++n )
-        if( 0xff != ( nTmp = pSetFlags[ n ] ))
+    if ( !found ) {
+        if( 0xff != ( nTmp = pSetFlags[ n / 8 ] ))
         {
             // so determine the number
-            nNum = n * 8;
+            nNum = n - n % 8;
             while( nTmp & 1 )
                 ++nNum, nTmp >>= 1;
-            break;
         }
+        else
+            nNum = n;
+    }
 
     delete [] pSetFlags;
     return aName += OUString::number( ++nNum );