faster mapping from nodes to SwFrmFmt's anchored at them

The SwFrmFmtAnchorMap class provides reverse mapping
to SwFrmFmt::GetAnchor().GetCntntAnchor(), so that when code somewhere needs
to update SwFrmFmt's anchored at a position, it's not necessary to iterate
over all of them (which can be a large number e.g. with mail merge).

One special catch with the multimap of SwNodeIndex keys is that
the values of those keys change (whenever the node structure of the document
changes, indexes of nodes change as a result). This makes it impossible to use
any hashing container, as the hashes would change without the container
noticing, but multimap should work fine, as it just requires that the keys
remain sorted, and that is the case. Nevertheless, the old code in the two
converted places is intentionally left there in debug mode to verify the reverse
mapping is updated correctly.

I intentionally went with SwNodeIndex rather than SwPosition, as SwIndex
(the other component of SwPosition) was causing some trouble (see e.g. the
SwPosition comparison operator< , where two same positions are different if one
is registered and the other not) and it doesn't appear to be actually necessary.

Conflicts:
sw/inc/doc.hxx
sw/inc/frmfmt.hxx
sw/source/core/attr/swatrset.cxx
sw/source/core/doc/docnew.cxx
sw/source/core/inc/frmtool.hxx
sw/source/core/layout/atrfrm.cxx
sw/source/core/txtnode/ndtxt.cxx

Change-Id: I7f1768558f60155d4ba83c84aa7f9e34dc65ebf9

8 files changed, 172 insertions, 13 deletions

diff --git a/sw/inc/doc.hxx b/sw/inc/doc.hxx
index c7d7af8de5ef..fc258ef8ac21 100644
--- a/sw/inc/doc.hxx
+++ b/sw/inc/doc.hxx
@@ -128,6 +128,7 @@ class SwFmt;
 class SwFmtINetFmt;
 class SwFmtRefMark;
 class SwFrmFmt;
+class SwFrmFmtAnchorMap;
 class SwFrmFmts;
 class SwFtnIdxs;
 class SwFtnInfo;
@@ -297,6 +298,7 @@ class SW_DLLPUBLIC SwDoc :
     SwGrfFmtColl    *mpDfltGrfFmtColl;
 
     SwFrmFmts       *mpFrmFmtTbl;        ///< Format table
+    SwFrmFmtAnchorMap *mpFrmFmtAnchorMap;
     SwCharFmts      *mpCharFmtTbl;
     SwFrmFmts       *mpSpzFrmFmtTbl;
     SwSectionFmts   *mpSectionFmtTbl;
@@ -1214,6 +1216,9 @@ public:
     const SwCharFmt *GetDfltCharFmt() const { return mpDfltCharFmt;}
           SwCharFmt *GetDfltCharFmt()       { return mpDfltCharFmt;}
 
+    const SwFrmFmtAnchorMap* GetFrmFmtAnchorMap() const { return mpFrmFmtAnchorMap; }
+    SwFrmFmtAnchorMap* GetFrmFmtAnchorMap() { return mpFrmFmtAnchorMap; }
+
     /// @return the interface of the management of (auto)styles
     IStyleAccess& GetIStyleAccess() { return *mpStyleAccess; }
 
diff --git a/sw/inc/frmfmt.hxx b/sw/inc/frmfmt.hxx
index 742abca3397f..0c22837bb5b3 100644
--- a/sw/inc/frmfmt.hxx
+++ b/sw/inc/frmfmt.hxx
@@ -23,6 +23,8 @@
 #include <cppuhelper/weakref.hxx>
 #include <tools/gen.hxx>
 #include <format.hxx>
+#include <map>
+#include <ndindex.hxx>
 #include "swdllapi.h"
 
 class SwFlyFrm;
@@ -67,6 +69,7 @@ protected:
 
 public:
     TYPEINFO();     ///< Already in base class Client.
+    virtual ~SwFrmFmt();
 
     /// Destroys all Frms in aDepend (Frms are identified via PTR_CAST).
     virtual void DelFrms();
@@ -298,6 +301,30 @@ public:
 };
 
 
+/**
+ Fast mapping from node positions to SwFrmFmt objects anchored at them.
+
+ SwFrmFmt::GetAnchor().GetCntntAnchor() provides the position where the object is anchored.
+ This class provides the reverse mapping. It intentionally uses SwNodeIndex instead of SwPosition
+ to allow simpler implementation, do SwIndex checking explicitly if needed.
+*/
+class SwFrmFmtAnchorMap
+{
+public:
+    SwFrmFmtAnchorMap( const SwDoc* doc );
+    void Add( SwFrmFmt* fmt, const SwNodeIndex& index );
+    void Remove( SwFrmFmt* fmt, const SwNodeIndex& index );
+    typedef std::multimap< SwNodeIndex, SwFrmFmt* >::const_iterator const_iterator;
+    typedef std::pair< const_iterator, const_iterator > const_iterator_pair;
+    const_iterator_pair equal_range( const SwNodeIndex& pos ) const;
+    const_iterator lower_bound( const SwNodeIndex& pos ) const;
+    const_iterator upper_bound( const SwNodeIndex& pos ) const;
+    const_iterator end() const;
+private:
+    std::multimap< SwNodeIndex, SwFrmFmt* > items;
+    const SwDoc* doc;
+};
+
 #endif
 
 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sw/source/core/attr/swatrset.cxx b/sw/source/core/attr/swatrset.cxx
index aa7ba15cff3b..4ca52ffd8f9c 100644
--- a/sw/source/core/attr/swatrset.cxx
+++ b/sw/source/core/attr/swatrset.cxx
@@ -25,6 +25,7 @@
 #include <editeng/brushitem.hxx>
 #include <editeng/lineitem.hxx>
 #include <editeng/boxitem.hxx>
+#include <fmtanchr.hxx>
 #include <fmtpdsc.hxx>
 #include <hintids.hxx>
 #include <istyleaccess.hxx>
@@ -300,12 +301,15 @@ void SwAttrSet::CopyToModify( SwModify& rMod ) const
                 }
             }
 
+            boost::scoped_ptr< SfxItemSet > tmpSet;
+
             const SwPageDesc* pPgDesc;
             if( pSrcDoc != pDstDoc && SFX_ITEM_SET == GetItemState(
                                             RES_PAGEDESC, sal_False, &pItem ) &&
                 0 != ( pPgDesc = ((SwFmtPageDesc*)pItem)->GetPageDesc()) )
             {
-                SfxItemSet aTmpSet( *this );
+                if( !tmpSet )
+                    tmpSet.reset( new SfxItemSet( *this ));
 
                 SwPageDesc* pDstPgDesc = pDstDoc->FindPageDescByName(pPgDesc->GetName());
                 if( !pDstPgDesc )
@@ -315,20 +319,33 @@ void SwAttrSet::CopyToModify( SwModify& rMod ) const
                 }
                 SwFmtPageDesc aDesc( pDstPgDesc );
                 aDesc.SetNumOffset( ((SwFmtPageDesc*)pItem)->GetNumOffset() );
-                aTmpSet.Put( aDesc );
+                tmpSet->Put( aDesc );
+            }
 
+            if( pSrcDoc != pDstDoc && SFX_ITEM_SET == GetItemState( RES_ANCHOR, false, &pItem )
+                && static_cast< const SwFmtAnchor* >( pItem )->GetCntntAnchor() != NULL )
+            {
+                if( !tmpSet )
+                    tmpSet.reset( new SfxItemSet( *this ));
+                // Anchors at any node position cannot be copied to another document, because the SwPosition
+                // would still point to the old document. It needs to be fixed up explicitly.
+                tmpSet->ClearItem( RES_ANCHOR );
+            }
+
+            if( tmpSet )
+            {
                 if( pCNd )
                 {
                     // #i92811#
                     if ( pNewListIdItem != 0 )
                     {
-                        aTmpSet.Put( *pNewListIdItem );
+                        tmpSet->Put( *pNewListIdItem );
                     }
-                    pCNd->SetAttr( aTmpSet );
+                    pCNd->SetAttr( *tmpSet );
                 }
                 else
                 {
-                    pFmt->SetFmtAttr( aTmpSet );
+                    pFmt->SetFmtAttr( *tmpSet );
                 }
             }
             else if( pCNd )
diff --git a/sw/source/core/doc/docnew.cxx b/sw/source/core/doc/docnew.cxx
index bd24134527a2..a25ee2b76d21 100644
--- a/sw/source/core/doc/docnew.cxx
+++ b/sw/source/core/doc/docnew.cxx
@@ -196,6 +196,7 @@ SwDoc::SwDoc()
     mpDfltTxtFmtColl( new SwTxtFmtColl( GetAttrPool(), sTxtCollStr ) ),
     mpDfltGrfFmtColl( new SwGrfFmtColl( GetAttrPool(), sGrfCollStr ) ),
     mpFrmFmtTbl( new SwFrmFmts() ),
+    mpFrmFmtAnchorMap( new SwFrmFmtAnchorMap( this ) ),
     mpCharFmtTbl( new SwCharFmts() ),
     mpSpzFrmFmtTbl( new SwFrmFmts() ),
     mpSectionFmtTbl( new SwSectionFmts() ),
@@ -677,6 +678,7 @@ SwDoc::~SwDoc()
     delete mpDfltFrmFmt;
     delete mpLayoutCache;
     delete mpVirDev;
+    delete mpFrmFmtAnchorMap;
 
     SfxItemPool::Free(mpAttrPool);
 }
diff --git a/sw/source/core/inc/flyfrm.hxx b/sw/source/core/inc/flyfrm.hxx
index dc38ce694f98..d82bdae00f51 100644
--- a/sw/source/core/inc/flyfrm.hxx
+++ b/sw/source/core/inc/flyfrm.hxx
@@ -57,7 +57,7 @@ sal_Bool CalcClipRect( const SdrObject *pSdrObj, SwRect &rRect, sal_Bool bMove =
 class SwFlyFrm : public SwLayoutFrm, public SwAnchoredObject
 {
     // is allowed to lock, implemented in frmtool.cxx
-    friend void AppendObjs   ( const SwFrmFmts *, sal_uLong, SwFrm *, SwPageFrm * );
+    friend void AppendObjs   ( const SwFrmFmts *, sal_uLong, SwFrm *, SwPageFrm *, SwDoc* );
     friend void Notify( SwFlyFrm *, SwPageFrm *pOld, const SwRect &rOld,
                         const SwRect* pOldPrt );
 
diff --git a/sw/source/core/layout/atrfrm.cxx b/sw/source/core/layout/atrfrm.cxx
index 365632eb6719..5a6698db1945 100644
--- a/sw/source/core/layout/atrfrm.cxx
+++ b/sw/source/core/layout/atrfrm.cxx
@@ -2432,6 +2432,16 @@ void SwFrmFmt::SetName( const String& rNewName, sal_Bool bBroadcast )
         _list->insert( this );
 }
 
+SwFrmFmt::~SwFrmFmt()
+{
+    if( !GetDoc()->IsInDtor())
+    {
+        const SwFmtAnchor& anchor = GetAnchor();
+        if( anchor.GetCntntAnchor() != NULL )
+            GetDoc()->GetFrmFmtAnchorMap()->Remove( this, anchor.GetCntntAnchor()->nNode );
+    }
+}
+
 void SwFrmFmt::Modify( const SfxPoolItem* pOld, const SfxPoolItem* pNew )
 {
     SwFmtHeader *pH = 0;
@@ -2472,6 +2482,31 @@ void SwFrmFmt::Modify( const SfxPoolItem* pOld, const SfxPoolItem* pNew )
     {   // invalidate cached uno object
         SetXObject(uno::Reference<uno::XInterface>(0));
     }
+
+    const SwPosition* oldAnchorPosition = NULL;
+    const SwPosition* newAnchorPosition = NULL;
+    if( pNew && pNew->Which() == RES_ATTRSET_CHG )
+    {
+        const SfxPoolItem* tmp = NULL;
+        static_cast< const SwAttrSetChg* >(pNew)->GetChgSet()->GetItemState( RES_ANCHOR, false, &tmp );
+        if( tmp )
+            newAnchorPosition = static_cast< const SwFmtAnchor* >( tmp )->GetCntntAnchor();
+    }
+    if( pNew && pNew->Which() == RES_ANCHOR )
+        newAnchorPosition = static_cast< const SwFmtAnchor* >( pNew )->GetCntntAnchor();
+    if( pOld && pOld->Which() == RES_ATTRSET_CHG )
+    {
+        const SfxPoolItem* tmp = NULL;
+        static_cast< const SwAttrSetChg* >(pOld)->GetChgSet()->GetItemState( RES_ANCHOR, false, &tmp );
+        if( tmp )
+            oldAnchorPosition = static_cast< const SwFmtAnchor* >( tmp )->GetCntntAnchor();
+    }
+    if( pOld && pOld->Which() == RES_ANCHOR )
+        oldAnchorPosition = static_cast< const SwFmtAnchor* >( pOld )->GetCntntAnchor();
+    if( oldAnchorPosition != NULL && ( newAnchorPosition == NULL || oldAnchorPosition->nNode.GetIndex() != newAnchorPosition->nNode.GetIndex()))
+        GetDoc()->GetFrmFmtAnchorMap()->Remove( this, oldAnchorPosition->nNode );
+    if( newAnchorPosition != NULL && ( oldAnchorPosition == NULL || oldAnchorPosition->nNode.GetIndex() != newAnchorPosition->nNode.GetIndex()))
+        GetDoc()->GetFrmFmtAnchorMap()->Add( this, newAnchorPosition->nNode );
 }
 
 void SwFrmFmt::RegisterToFormat( SwFmt& rFmt )
@@ -3241,4 +3276,52 @@ IMapObject* SwFrmFmt::GetIMapObject( const Point& rPoint,
     return 0;
 }
 
+
+SwFrmFmtAnchorMap::SwFrmFmtAnchorMap( const SwDoc* _doc )
+: doc( _doc )
+{
+}
+
+void SwFrmFmtAnchorMap::Add( SwFrmFmt* fmt, const SwNodeIndex& pos )
+{
+    assert( pos.GetNode().GetDoc() == doc );
+    items.insert( std::make_pair( pos, fmt ));
+}
+
+void SwFrmFmtAnchorMap::Remove( SwFrmFmt* fmt, const SwNodeIndex& pos )
+{
+    assert( pos.GetNode().GetDoc() == doc );
+    typedef std::multimap< SwNodeIndex, SwFrmFmt* >::iterator iterator;
+    std::pair< iterator, iterator > range = items.equal_range( pos );
+    for( iterator it = range.first; it != range.second; ++it )
+    {
+        if( it->second == fmt )
+        {
+            items.erase( it );
+            return;
+        }
+    }
+    assert( false );
+}
+
+SwFrmFmtAnchorMap::const_iterator_pair SwFrmFmtAnchorMap::equal_range( const SwNodeIndex& pos ) const
+{
+    return items.equal_range( pos );
+}
+
+SwFrmFmtAnchorMap::const_iterator SwFrmFmtAnchorMap::lower_bound( const SwNodeIndex& pos ) const
+{
+    return items.lower_bound( pos );
+}
+
+SwFrmFmtAnchorMap::const_iterator SwFrmFmtAnchorMap::upper_bound( const SwNodeIndex& pos ) const
+{
+    return items.upper_bound( pos );
+}
+
+SwFrmFmtAnchorMap::const_iterator SwFrmFmtAnchorMap::end() const
+{
+    return items.end();
+}
+
 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sw/source/core/layout/frmtool.cxx b/sw/source/core/layout/frmtool.cxx
index 5572239038ef..be5c72768eed 100644
--- a/sw/source/core/layout/frmtool.cxx
+++ b/sw/source/core/layout/frmtool.cxx
@@ -1002,15 +1002,36 @@ SwCntntNotify::~SwCntntNotify()
 /*************************************************************************/
 
 void AppendObjs( const SwFrmFmts *pTbl, sal_uLong nIndex,
-                        SwFrm *pFrm, SwPageFrm *pPage )
+                        SwFrm *pFrm, SwPageFrm *pPage, SwDoc* doc )
 {
+#if OSL_DEBUG_LEVEL > 0
+    std::list<SwFrmFmt*> checkFmts;
     for ( sal_uInt16 i = 0; i < pTbl->size(); ++i )
     {
-        SwFrmFmt *pFmt = (SwFrmFmt*)(*pTbl)[i];
+        SwFrmFmt *pFmt = (*pTbl)[i];
         const SwFmtAnchor &rAnch = pFmt->GetAnchor();
         if ( rAnch.GetCntntAnchor() &&
              (rAnch.GetCntntAnchor()->nNode.GetIndex() == nIndex) )
         {
+            checkFmts.push_back( pFmt );
+        }
+    }
+#endif
+    SwFrmFmtAnchorMap::const_iterator_pair range = doc->GetFrmFmtAnchorMap()->equal_range( SwNodeIndex( doc->GetNodes(), nIndex ));
+    for( std::multimap< SwNodeIndex, SwFrmFmt* >::const_iterator it = range.first;
+         it != range.second;
+         )
+    {
+        SwFrmFmt *pFmt = it->second;
+        const SwFmtAnchor &rAnch = pFmt->GetAnchor();
+        if ( rAnch.GetCntntAnchor() &&
+             (rAnch.GetCntntAnchor()->nNode.GetIndex() == nIndex) )
+        {
+#if OSL_DEBUG_LEVEL > 0
+            std::list<SwFrmFmt*>::iterator checkPos = std::find( checkFmts.begin(), checkFmts.end(), pFmt );
+            assert( checkPos != checkFmts.end());
+            checkFmts.erase( checkPos );
+#endif
             const bool bFlyAtFly = rAnch.GetAnchorId() == FLY_AT_FLY; // LAYER_IMPL
             //Is a frame or a SdrObject described?
             const bool bSdrObj = RES_DRAWFRMFMT == pFmt->Which();
@@ -1028,8 +1049,8 @@ void AppendObjs( const SwFrmFmts *pTbl, sal_uLong nIndex,
                 if ( bSdrObj && 0 == (pSdrObj = pFmt->FindSdrObject()) )
                 {
                     OSL_ENSURE( !bSdrObj, "DrawObject not found." );
+                    ++it;
                     pFmt->GetDoc()->DelFrmFmt( pFmt );
-                    --i;
                     continue;
                 }
                 if ( pSdrObj )
@@ -1076,7 +1097,11 @@ void AppendObjs( const SwFrmFmts *pTbl, sal_uLong nIndex,
                 }
             }
         }
+        ++it;
     }
+#if OSL_DEBUG_LEVEL > 0
+    assert( checkFmts.empty());
+#endif
 }
 
 static bool lcl_ObjConnected( SwFrmFmt *pFmt, const SwFrm* pSib )
@@ -1323,7 +1348,7 @@ void _InsertCnt( SwLayoutFrm *pLay, SwDoc *pDoc,
             pPrv = pFrm;
 
             if ( !pTbl->empty() && bObjsDirect && !bDontCreateObjects )
-                AppendObjs( pTbl, nIndex, pFrm, pPage );
+                AppendObjs( pTbl, nIndex, pFrm, pPage, pDoc );
         }
         else if ( pNd->IsTableNode() )
         {   //Should we have encountered a table?
@@ -1543,7 +1568,7 @@ void _InsertCnt( SwLayoutFrm *pLay, SwDoc *pDoc,
             {
                 SwFlyFrm* pFly = pLay->FindFlyFrm();
                 if( pFly )
-                    AppendObjs( pTbl, nIndex, pFly, pPage );
+                    AppendObjs( pTbl, nIndex, pFly, pPage, pDoc );
             }
         }
         else
diff --git a/sw/source/core/layout/tabfrm.cxx b/sw/source/core/layout/tabfrm.cxx
index 4c62cb97493e..402b32d0ae0c 100644
--- a/sw/source/core/layout/tabfrm.cxx
+++ b/sw/source/core/layout/tabfrm.cxx
@@ -66,7 +66,7 @@
 #include <switerator.hxx>
 
 extern void AppendObjs( const SwFrmFmts *pTbl, sal_uLong nIndex,
-                        SwFrm *pFrm, SwPageFrm *pPage );
+                        SwFrm *pFrm, SwPageFrm *pPage, SwDoc* doc );
 
 using namespace ::com::sun::star;
 
@@ -1230,7 +1230,7 @@ bool SwTabFrm::Split( const SwTwips nCutPos, bool bTryToSplit, bool bTableRowKee
                 while( pFrm )
                 {
                     nIndex = pFrm->GetNode()->GetIndex();
-                    AppendObjs( pTbl, nIndex, pFrm, pPage );
+                    AppendObjs( pTbl, nIndex, pFrm, pPage, GetFmt()->GetDoc());
                     pFrm = pFrm->GetNextCntntFrm();
                     if( !pHeadline->IsAnLower( pFrm ) )
                         break;