Convert SwPageDescs to boost::multi_index

Page descriptions are exported via XIndexAccess, so they need a
stable array, currently a vector. On the other hand they are
referred by a unique name, so the lookup in the unsorted array is
O(n), not taking into account the amount of string comparisons.

The multi index container adds an ordered unique index, which
gets the lookup time down to O(log(n)) at the cost of a bit more
management overhead for most operations, which is largely
outweighted by the amount of lookup calls. These anyway have to be
done on insert to guarantee the unique naming.

Change-Id: I3fb892ff524f6a9804d9572c1825074c0810649e

5 files changed, 193 insertions, 43 deletions

diff --git a/sw/inc/doc.hxx b/sw/inc/doc.hxx
index b4c4868c3641..43472540dc0b 100644
--- a/sw/inc/doc.hxx
+++ b/sw/inc/doc.hxx
@@ -47,6 +47,7 @@
 #include <frmfmt.hxx>
 #include <charfmt.hxx>
 #include <docary.hxx>
+#include <pagedesc.hxx>
 
 #include <svtools/embedhlp.hxx>
 
@@ -107,7 +108,6 @@ class SwNodeRange;
 class SwNodes;
 class SwNumRule;
 class SwNumRuleTable;
-class SwPageDesc;
 class SwPagePreviewPrtData;
 class SwRootFrame;
 class SwRubyList;
@@ -223,8 +223,6 @@ namespace sfx2 {
     class LinkManager;
 }
 
-typedef std::vector<std::unique_ptr<SwPageDesc>> SwPageDescs;
-
 void SetAllScriptItem( SfxItemSet& rSet, const SfxPoolItem& rItem );
 
 // global function to start grammar checking in the document
@@ -907,7 +905,7 @@ public:
     SwPageDesc& GetPageDesc(size_t const i) { return *m_PageDescs[i]; }
     SwPageDesc* FindPageDesc(const OUString& rName, size_t* pPos = nullptr) const;
     // Just searches the pointer in the m_PageDescs vector!
-    bool        ContainsPageDesc(const SwPageDesc *pDesc, size_t* pPos = nullptr);
+    bool        ContainsPageDesc(const SwPageDesc *pDesc, size_t* pPos = nullptr) const;
 
     /** Copy the complete PageDesc - beyond document and "deep"!
      Optionally copying of PoolFormatId, -HlpId can be prevented. */
diff --git a/sw/inc/pagedesc.hxx b/sw/inc/pagedesc.hxx
index d55e85117808..c2fdf05d0503 100644
--- a/sw/inc/pagedesc.hxx
+++ b/sw/inc/pagedesc.hxx
@@ -30,9 +30,15 @@
 
 using namespace ::com::sun::star;
 
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/identity.hpp>
+#include <boost/multi_index/ordered_index.hpp>
+#include <boost/multi_index/random_access_index.hpp>
+
 class SfxPoolItem;
 class SwTextFormatColl;
 class SwNode;
+class SwPageDescs;
 
 /// Separator line adjustment.
 enum SwFootnoteAdj
@@ -125,15 +131,16 @@ namespace nsUseOnPage
     const UseOnPage PD_MIRROR         = 0x0007;
     const UseOnPage PD_HEADERSHARE    = 0x0040;
     const UseOnPage PD_FOOTERSHARE    = 0x0080;
+    const UseOnPage PD_FIRSTSHARE     = 0x0100;
     const UseOnPage PD_NOHEADERSHARE  = 0xFFBF; ///< For internal use only.
     const UseOnPage PD_NOFOOTERSHARE  = 0xFF7F; ///< For internal use only.
-    const UseOnPage PD_FIRSTSHARE = 0x0100;
-    const UseOnPage PD_NOFIRSTSHARE = 0xFEFF;
+    const UseOnPage PD_NOFIRSTSHARE   = 0xFEFF;
 }
 
 class SW_DLLPUBLIC SwPageDesc : public SwModify
 {
     friend class SwDoc;
+    friend class SwPageDescs;
 
     OUString    m_StyleName;
     SvxNumberType m_NumType;
@@ -154,6 +161,9 @@ class SW_DLLPUBLIC SwPageDesc : public SwModify
     /// Footnote information.
     SwPageFootnoteInfo m_IsFootnoteInfo;
 
+    /// Backref to the assigned SwPageDescs list to handle renames.
+    SwPageDescs  *m_pdList;
+
     /** Called for mirroring of Chg (doc).
        No adjustment at any other place. */
     SAL_DLLPRIVATE void Mirror();
@@ -162,12 +172,19 @@ class SW_DLLPUBLIC SwPageDesc : public SwModify
 
     SAL_DLLPRIVATE SwPageDesc(const OUString&, SwFrameFormat*, SwDoc *pDc );
 
+    struct change_name
+    {
+        change_name(const OUString &rName) : mName(rName) {}
+        void operator()(SwPageDesc *pPageDesc) { pPageDesc->m_StyleName = mName; }
+        const OUString &mName;
+    };
+
 protected:
    virtual void Modify( const SfxPoolItem* pOld, const SfxPoolItem *pNewValue ) override;
 
 public:
     const OUString& GetName() const { return m_StyleName; }
-    void SetName(const OUString& rNewName) { m_StyleName = rNewName; }
+    bool SetName(const OUString& rNewName);
 
     bool GetLandscape() const { return m_IsLandscape; }
     void SetLandscape( bool bNew ) { m_IsLandscape = bNew; }
@@ -253,11 +270,25 @@ public:
     static SwPageDesc* GetByName(SwDoc& rDoc, const OUString& rName);
 
     SwPageDesc& operator=( const SwPageDesc& );
+    bool        operator<(const SwPageDesc& pd) const
+        { return m_StyleName < pd.m_StyleName; }
 
     SwPageDesc( const SwPageDesc& );
     virtual ~SwPageDesc();
 };
 
+namespace std {
+   template<>
+   struct less<SwPageDesc*> {
+       bool operator()(const SwPageDesc *pPageDesc, const OUString &rName) const
+           { return pPageDesc->GetName() < rName; }
+       bool operator()(const OUString &rName, const SwPageDesc *pPageDesc) const
+           { return rName < pPageDesc->GetName(); }
+       bool operator()(const SwPageDesc *lhs, const SwPageDesc *rhs) const
+           { return lhs->GetName() < rhs->GetName(); }
+   };
+}
+
 inline void SwPageDesc::SetFollow( const SwPageDesc* pNew )
 {
     m_pFollow = pNew ? const_cast<SwPageDesc*>(pNew) : this;
@@ -347,6 +378,59 @@ namespace sw {
     class PageFootnoteHint final : public SfxHint {};
 }
 
+namespace bmi = boost::multi_index;
+
+typedef boost::multi_index_container<
+        SwPageDesc*,
+        bmi::indexed_by<
+            bmi::random_access<>,
+            bmi::ordered_unique< bmi::identity<SwPageDesc*> >
+        >
+    >
+    SwPageDescsBase;
+
+class SwPageDescs : private SwPageDescsBase
+{
+    // function updating ByName index via modify
+    friend bool SwPageDesc::SetName( const OUString& rNewName );
+
+    typedef nth_index<0>::type ByPos;
+    typedef nth_index<1>::type ByName;
+    typedef ByPos::iterator iterator;
+
+    using ByPos::modify;
+    iterator find_( const OUString &name ) const;
+
+public:
+    typedef ByPos::const_iterator const_iterator;
+    typedef SwPageDescsBase::size_type size_type;
+    typedef SwPageDescsBase::value_type value_type;
+
+    // frees all SwPageDesc!
+    virtual ~SwPageDescs();
+
+    using SwPageDescsBase::clear;
+    using SwPageDescsBase::empty;
+    using SwPageDescsBase::size;
+
+    std::pair<const_iterator,bool> push_back( const value_type& x );
+    void erase( const value_type& x );
+    void erase( size_type index );
+    void erase( const_iterator const& position );
+
+    const_iterator find( const OUString &name ) const
+        { return find_( name ); }
+    const value_type& operator[]( size_t index_ ) const
+        { return ByPos::operator[]( index_ ); }
+    const value_type& front() const { return ByPos::front(); }
+    const value_type& back() const { return ByPos::back(); }
+    const_iterator begin() const { return ByPos::begin(); }
+    const_iterator end() const { return ByPos::end(); }
+
+    bool contains( const value_type& x ) const
+        { return x->m_pdList == this; }
+};
+
 #endif // INCLUDED_SW_INC_PAGEDESC_HXX
 
 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sw/source/core/doc/docdesc.cxx b/sw/source/core/doc/docdesc.cxx
index 34df1d459d72..a4f30a9d5019 100644
--- a/sw/source/core/doc/docdesc.cxx
+++ b/sw/source/core/doc/docdesc.cxx
@@ -556,13 +556,13 @@ void SwDoc::PreDelPageDesc(SwPageDesc * pDel)
         return;
 
     // mba: test iteration as clients are removed while iteration
-    SwPageDescHint aHint(m_PageDescs[0].get());
+    SwPageDescHint aHint( m_PageDescs[0] );
     pDel->CallSwClientNotify( aHint );
 
     bool bHasLayout = getIDocumentLayoutAccess().HasLayout();
     if ( mpFootnoteInfo->DependsOn( pDel ) )
     {
-        mpFootnoteInfo->ChgPageDesc(m_PageDescs[0].get());
+        mpFootnoteInfo->ChgPageDesc( m_PageDescs[0] );
         if ( bHasLayout )
         {
             for( auto aLayout : GetAllLayouts() )
@@ -571,7 +571,7 @@ void SwDoc::PreDelPageDesc(SwPageDesc * pDel)
     }
     else if ( mpEndNoteInfo->DependsOn( pDel ) )
     {
-        mpEndNoteInfo->ChgPageDesc(m_PageDescs[0].get());
+        mpEndNoteInfo->ChgPageDesc( m_PageDescs[0] );
         if ( bHasLayout )
         {
             for( auto aLayout : GetAllLayouts() )
@@ -579,11 +579,11 @@ void SwDoc::PreDelPageDesc(SwPageDesc * pDel)
         }
     }
 
-    for (std::unique_ptr<SwPageDesc> & rpPageDesc : m_PageDescs)
+    for (SwPageDesc* pPageDesc : m_PageDescs)
     {
-        if (rpPageDesc->GetFollow() == pDel)
+        if (pPageDesc->GetFollow() == pDel)
         {
-            rpPageDesc->SetFollow(nullptr);
+            pPageDesc->SetFollow(nullptr);
             if( bHasLayout )
             {
                 for( auto aLayout : GetAllLayouts() )
@@ -666,7 +666,9 @@ SwPageDesc* SwDoc::MakePageDesc(const OUString &rName, const SwPageDesc *pCpy,
         pNew->GetFirstMaster().SetFormatAttr( SvxFrameDirectionItem(aFrameDirection, RES_FRAMEDIR) );
         pNew->GetFirstLeft().SetFormatAttr( SvxFrameDirectionItem(aFrameDirection, RES_FRAMEDIR) );
     }
-    m_PageDescs.push_back(std::unique_ptr<SwPageDesc>(pNew));
+
+    std::pair<SwPageDescs::const_iterator, bool> res = m_PageDescs.push_back( pNew );
+    SAL_WARN_IF(!res.second, "sw", "MakePageDesc called with existing name" );
 
     if (bBroadcast)
         BroadcastStyleOperation(rName, SfxStyleFamily::Page,
@@ -808,22 +810,14 @@ IMPL_LINK_NOARG_TYPED( SwDoc, DoUpdateModifiedOLE, Idle *, void )
     }
 }
 
-struct CompareSwPageDescName {
-    explicit CompareSwPageDescName(const OUString &rName) : mName(rName) {}
-    bool operator () (const std::unique_ptr<SwPageDesc>& other) const { return other->GetName() == mName; }
-    const OUString &mName;
-};
-
-template <class UnaryPredicate>
-static SwPageDesc* lcl_FindPageDesc( SwPageDescs *pPageDescs,
-                                     size_t *pPos, UnaryPredicate pred )
+static SwPageDesc* lcl_FindPageDesc( const SwPageDescs *pPageDescs,
+                                     size_t *pPos, const OUString &rName )
 {
-    SwPageDescs::iterator it = std::find_if(
-        pPageDescs->begin(), pPageDescs->end(), pred);
     SwPageDesc* res = nullptr;
+    SwPageDescs::const_iterator it = pPageDescs->find( rName );
     if( it != pPageDescs->end() )
     {
-        res = it->get();
+        res = *it;
         if( pPos )
             *pPos = std::distance( pPageDescs->begin(), it );
     }
@@ -834,25 +828,26 @@ static SwPageDesc* lcl_FindPageDesc( SwPageDescs *pPageDescs,
 
 SwPageDesc* SwDoc::FindPageDesc( const OUString & rName, size_t* pPos ) const
 {
-    return lcl_FindPageDesc<CompareSwPageDescName>(
-        const_cast <SwPageDescs *>( &m_PageDescs ), pPos,
-        CompareSwPageDescName(rName) );
+    return lcl_FindPageDesc(
+        const_cast <SwPageDescs *>( &m_PageDescs ), pPos, rName );
 }
 
-struct CompareSwPageDescToPtr {
-    explicit CompareSwPageDescToPtr(const SwPageDesc* ptr) : mPtr(ptr) {}
-    bool operator () (const std::unique_ptr<SwPageDesc>& other) const { return other.get() == mPtr; }
-    const SwPageDesc *mPtr;
-};
-
-bool SwDoc::ContainsPageDesc( const SwPageDesc *pDesc, size_t* pPos )
+bool SwDoc::ContainsPageDesc( const SwPageDesc *pDesc, size_t* pPos ) const
 {
-    if (pDesc == nullptr)
+    if( pDesc == nullptr )
         return false;
-    SwPageDesc *res = lcl_FindPageDesc<CompareSwPageDescToPtr>(
-        &m_PageDescs, pPos,
-        CompareSwPageDescToPtr(pDesc) );
-    return res != nullptr;
+    if( !m_PageDescs.contains( const_cast <SwPageDesc*>( pDesc ) ) ) {
+        if( pPos )
+            *pPos = SIZE_MAX;
+        return false;
+    }
+    if( ! pPos )
+        return true;
+
+    SwPageDesc* desc = lcl_FindPageDesc(
+        &m_PageDescs, pPos, pDesc->GetName() );
+    SAL_WARN_IF( desc != pDesc, "sw", "SwPageDescs container is broken!" );
+    return true;
 }
 
 void SwDoc::DelPageDesc( const OUString & rName, bool bBroadcast )
diff --git a/sw/source/core/doc/docnew.cxx b/sw/source/core/doc/docnew.cxx
index 42dbb2221dca..c89af978d782 100644
--- a/sw/source/core/doc/docnew.cxx
+++ b/sw/source/core/doc/docnew.cxx
@@ -496,6 +496,8 @@ SwDoc::~SwDoc()
     // Destroy these only after destroying the FormatIndices, because the content
     // of headers/footers has to be deleted as well. If in the headers/footers
     // there are still Flys registered at that point, we have a problem.
+    for( SwPageDesc *pPageDesc : m_PageDescs )
+        delete pPageDesc;
     m_PageDescs.clear();
 
     // Delete content selections.
@@ -707,7 +709,9 @@ void SwDoc::ClearDoc()
     // remove the dummy pagedesc from the array and delete all the old ones
     size_t nDummyPgDsc = 0;
     if (FindPageDesc(pDummyPgDsc->GetName(), &nDummyPgDsc))
-        pDummyPgDsc = m_PageDescs[nDummyPgDsc].release();
+        m_PageDescs.erase( nDummyPgDsc );
+    for( SwPageDesc *pPageDesc : m_PageDescs )
+        delete pPageDesc;
     m_PageDescs.clear();
 
     // Delete for Collections
@@ -744,7 +748,7 @@ void SwDoc::ClearDoc()
     getIDocumentStylePoolAccess().GetPageDescFromPool( RES_POOLPAGE_STANDARD );
     pFirstNd->ChgFormatColl( getIDocumentStylePoolAccess().GetTextCollFromPool( RES_POOLCOLL_STANDARD ));
     nDummyPgDsc = m_PageDescs.size();
-    m_PageDescs.push_back(std::unique_ptr<SwPageDesc>(pDummyPgDsc));
+    m_PageDescs.push_back( pDummyPgDsc );
     // set the layout back to the new standard pagedesc
     pFirstNd->ResetAllAttr();
     // delete now the dummy pagedesc
diff --git a/sw/source/core/layout/pagedesc.cxx b/sw/source/core/layout/pagedesc.cxx
index 05d0de2fd882..42f1a505b22d 100644
--- a/sw/source/core/layout/pagedesc.cxx
+++ b/sw/source/core/layout/pagedesc.cxx
@@ -51,6 +51,7 @@ SwPageDesc::SwPageDesc(const OUString& rName, SwFrameFormat *pFormat, SwDoc *con
     , m_eUse( (UseOnPage)(nsUseOnPage::PD_ALL | nsUseOnPage::PD_HEADERSHARE | nsUseOnPage::PD_FOOTERSHARE | nsUseOnPage::PD_FIRSTSHARE) )
     , m_IsLandscape( false )
     , m_IsHidden( false )
+    , m_pdList( nullptr )
 {
 }
 
@@ -71,6 +72,7 @@ SwPageDesc::SwPageDesc( const SwPageDesc &rCpy )
     , m_IsLandscape( rCpy.GetLandscape() )
     , m_IsHidden( rCpy.IsHidden() )
     , m_IsFootnoteInfo( rCpy.GetFootnoteInfo() )
+    , m_pdList( nullptr )
 {
 }
 
@@ -100,6 +102,22 @@ SwPageDesc::~SwPageDesc()
 {
 }
 
+bool SwPageDesc::SetName( const OUString& rNewName )
+{
+    bool renamed = true;
+    if (m_pdList) {
+        SwPageDescs::iterator it = m_pdList->find_( m_StyleName );
+        if( m_pdList->end() == it ) {
+            SAL_WARN( "sw", "SwPageDesc not found in expected m_pdList" );
+            return false;
+        }
+        renamed = m_pdList->modify( it, change_name( rNewName ), change_name( m_StyleName ) );
+    }
+    else
+        m_StyleName = rNewName;
+    return renamed;
+}
+
 /// Only the margin is mirrored.
 /// Attributes like borders and so on are copied 1:1.
 void SwPageDesc::Mirror()
@@ -462,4 +480,55 @@ SwPageDescExt::operator SwPageDesc() const
     return aResult;
 }
 
+SwPageDescs::~SwPageDescs()
+{
+    for(const_iterator it = begin(); it != end(); ++it)
+        delete *it;
+}
+
+SwPageDescs::iterator SwPageDescs::find_(const OUString &name) const
+{
+    const ByName &pd_named = get<1>();
+    ByName::iterator it = pd_named.find( name );
+    return iterator_to( *it );
+}
+
+std::pair<SwPageDescs::const_iterator,bool> SwPageDescs::push_back( const value_type& x )
+{
+    // SwPageDesc is not already in a SwPageDescs list!
+    assert( x->m_pdList == nullptr );
+
+    std::pair<iterator,bool> res = ByPos::push_back( x );
+    if( res.second )
+        x->m_pdList = this;
+    return res;
+}
+
+void SwPageDescs::erase( const value_type& x )
+{
+    // SwPageDesc is not in this SwPageDescs list!
+    assert( x->m_pdList == this );
+
+    iterator const ret = find_( x->GetName() );
+    if (ret != end())
+        ByPos::erase( ret );
+    else
+        SAL_WARN( "sw", "SwPageDesc is not in SwPageDescs m_pdList!" );
+    x->m_pdList = nullptr;
+}
+
+void SwPageDescs::erase( const_iterator const& position )
+{
+    // SwPageDesc is not in this SwPageDescs list!
+    assert( (*position)->m_pdList == this );
+
+    (*position)->m_pdList = nullptr;
+    ByPos::erase( position );
+}
+
+void SwPageDescs::erase( size_type index_ )
+{
+    erase( begin() + index_ );
+}
+
 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */