From a8b1699ca9c7e8c43eff79467451fd1fcb4fde9b Mon Sep 17 00:00:00 2001 From: Katarina Behrens Date: Mon, 1 Jul 2019 18:20:02 +0200 Subject: speed-up shape import if shapes need z-order rearranging setting z-order individually on each shape and broadcasting is O(n^2) (remaining shapes also need reordering) and this is bad bad bad for performance Change-Id: Ic9c9137a097f6ff524192693910f221885f77cc4 Reviewed-on: https://gerrit.libreoffice.org/75055 Tested-by: Jenkins Reviewed-by: Michael Stahl --- include/svx/svdpage.hxx | 1 + include/svx/unopage.hxx | 9 ++- offapi/UnoApi_offapi.mk | 1 + offapi/com/sun/star/drawing/XShapes3.idl | 43 ++++++++++++++ svx/source/svdraw/svdpage.cxx | 96 ++++++++++++++++++++++++++++++++ svx/source/unodraw/unopage.cxx | 7 +++ xmloff/source/draw/shapeimport.cxx | 37 ++++++++++++ 7 files changed, 192 insertions(+), 2 deletions(-) create mode 100644 offapi/com/sun/star/drawing/XShapes3.idl diff --git a/include/svx/svdpage.hxx b/include/svx/svdpage.hxx index 5ab621ccbd4c..60cf0bb49004 100644 --- a/include/svx/svdpage.hxx +++ b/include/svx/svdpage.hxx @@ -108,6 +108,7 @@ public: bool IsObjOrdNumsDirty() const { return mbObjOrdNumsDirty; } virtual void NbcInsertObject(SdrObject* pObj, size_t nPos=SAL_MAX_SIZE); virtual void InsertObject(SdrObject* pObj, size_t nPos=SAL_MAX_SIZE); + virtual void sort( std::vector& sortOrder ); /// remove from list without delete virtual SdrObject* NbcRemoveObject(size_t nObjNum); diff --git a/include/svx/unopage.hxx b/include/svx/unopage.hxx index 50b54a62c754..6814f859904a 100644 --- a/include/svx/unopage.hxx +++ b/include/svx/unopage.hxx @@ -24,12 +24,13 @@ #include #include #include +#include #include #include #include #include -#include +#include #include #include @@ -50,9 +51,10 @@ enum class SdrInventor : sal_uInt32; #define TWIPS_TO_MM(val) ((val * 127 + 36) / 72) #define MM_TO_TWIPS(val) ((val * 72 + 63) / 127) -class SVX_DLLPUBLIC SvxDrawPage : public ::cppu::WeakAggImplHelper6< css::drawing::XDrawPage, +class SVX_DLLPUBLIC SvxDrawPage : public ::cppu::WeakAggImplHelper7< css::drawing::XDrawPage, css::drawing::XShapeGrouper, css::drawing::XShapes2, + css::drawing::XShapes3, css::lang::XServiceInfo, css::lang::XUnoTunnel, css::lang::XComponent>, @@ -109,6 +111,9 @@ class SVX_DLLPUBLIC SvxDrawPage : public ::cppu::WeakAggImplHelper6< css::drawin virtual void SAL_CALL addTop( const css::uno::Reference< css::drawing::XShape >& xShape ) override; virtual void SAL_CALL addBottom( const css::uno::Reference< css::drawing::XShape >& xShape ) override; + // XShapes3 + virtual void SAL_CALL sort( const css::uno::Sequence< sal_Int32 >& sortOrder ) override; + // XElementAccess virtual css::uno::Type SAL_CALL getElementType() override; virtual sal_Bool SAL_CALL hasElements() override; diff --git a/offapi/UnoApi_offapi.mk b/offapi/UnoApi_offapi.mk index 4e36995a7d53..5fa55f8f191d 100644 --- a/offapi/UnoApi_offapi.mk +++ b/offapi/UnoApi_offapi.mk @@ -2376,6 +2376,7 @@ $(eval $(call gb_UnoApi_add_idlfiles,offapi,com/sun/star/drawing,\ XShapeMirror \ XShapes \ XShapes2 \ + XShapes3 \ XSlidePreviewCache \ XSlidePreviewCacheListener \ XSlideRenderer \ diff --git a/offapi/com/sun/star/drawing/XShapes3.idl b/offapi/com/sun/star/drawing/XShapes3.idl new file mode 100644 index 000000000000..ebb23e7d3a11 --- /dev/null +++ b/offapi/com/sun/star/drawing/XShapes3.idl @@ -0,0 +1,43 @@ +/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */ +/* + * This file is part of the LibreOffice project. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + */ + +#ifndef __com_sun_star_drawing_XShapes3_idl__ +#define __com_sun_star_drawing_XShapes3_idl__ + +#include + +module com { module sun { module star { module drawing { + +/** + * Yet another XShapes interface, enables sorting shapes with + * some extra attention paid to shapes with textboxes and overall + * performance + * + * @since LibreOffice 6.4 + */ +interface XShapes3 +{ + /** + * Sort shapes according to given sort order, for perf reason + * just rearrange and don't broadcast + * + * @param desired order of the shapes + * + * @since LibreOffice 6.4 + */ + + void sort( [in] sequence< long> sortOrder ) + raises( com::sun::star::lang::IllegalArgumentException ); +}; + +}; }; }; }; + +#endif + +/* vim:set shiftwidth=4 softtabstop=4 expandtab: */ diff --git a/svx/source/svdraw/svdpage.cxx b/svx/source/svdraw/svdpage.cxx index ae0a0c3cc1e3..8794c2355dd0 100644 --- a/svx/source/svdraw/svdpage.cxx +++ b/svx/source/svdraw/svdpage.cxx @@ -57,6 +57,8 @@ #include #include +#include + using namespace ::com::sun::star; class SdrObjList::WeakSdrObjectContainerType @@ -556,6 +558,100 @@ SdrObject* SdrObjList::SetObjectOrdNum(size_t nOldObjNum, size_t nNewObjNum) return pObj; } +void SdrObjList::sort( std::vector& sortOrder) +{ + // no negative indexes and indexes larger than maList size are allowed + auto it = std::find_if( sortOrder.begin(), sortOrder.end(), [this](const sal_Int32& rIt) + { return ( rIt < 0 || static_cast(rIt) >= maList.size() ); } ); + if ( it != sortOrder.end()) + throw css::lang::IllegalArgumentException("negative index of shape", nullptr, 1); + + // no duplicates + std::vector aNoDuplicates(sortOrder.size(), false); + for (size_t i = 0; i < sortOrder.size(); ++i ) + { + size_t idx = static_cast( sortOrder[i] ); + + if ( aNoDuplicates[idx] ) + throw css::lang::IllegalArgumentException("duplicate index of shape", nullptr, 2); + + aNoDuplicates[idx] = true; + } + + // example sortOrder [2 0 1] + // example maList [T T S T T] ( T T = shape with textbox, S = just a shape ) + // (shapes at positions 0 and 2 have a textbox) + + std::vector aNewList(maList.size()); + std::set aShapesWithTextbox; + std::vector aIncrements; + std::vector aDuplicates; + + if ( maList.size() > 1) + { + for (size_t i = 1; i< maList.size(); ++i) + { + // if this shape is a textbox, then look at its left neighbour + // (shape this textbox is in) + // and insert the number of textboxes to the left of it + if (maList[i]->IsTextBox()) + aShapesWithTextbox.insert( i - 1 - aShapesWithTextbox.size() ); + } + // example aShapesWithTextbox [0 2] + } + + aIncrements.push_back(0); + aDuplicates.push_back(sortOrder[0]); + + // corner case: 1st shape is a textbox, add it twice + // otherwise sortOrder loop below will skip it + if (aShapesWithTextbox.count(sortOrder[0]) > 0) + aDuplicates.push_back(sortOrder[0]); + + for (size_t i = 1; i< sortOrder.size(); ++i) + { + aDuplicates.push_back(sortOrder[i]); + + if (aShapesWithTextbox.count(sortOrder[i]) > 0) + { + aIncrements.push_back(aIncrements[i-1] + 1 ); + aDuplicates.push_back(sortOrder[i]); + } + else + { + aIncrements.push_back(aIncrements[i-1]); + } + + // example aDuplicates [2 2 0 0 1] + // example aIncrements [0 1 1] + } + + std::vector aNewSortOrder(maList.size()); + sal_Int32 nPrev = -1; + for (size_t i = 0; i< aDuplicates.size(); ++i) + { + if (nPrev != aDuplicates[i]) + aNewSortOrder[i] = aDuplicates[i] + aIncrements[aDuplicates[i]]; + else + aNewSortOrder[i] = aNewSortOrder[i-1] + 1; + + nPrev = aDuplicates[i]; + + // example aNewSortOrder [3 4 0 1 2] + } + + if ( aNewSortOrder.size() != maList.size()) + throw css::lang::IllegalArgumentException("mismatch of no. of shapes", nullptr, 0); + + for (size_t i = 0; i < aNewSortOrder.size(); ++i) + { + aNewList[i] = maList[ sortOrder[i] ]; + aNewList[i]->SetOrdNum(i); + } + + std::swap(aNewList, maList); +} + const tools::Rectangle& SdrObjList::GetAllObjSnapRect() const { if (mbRectsDirty) { diff --git a/svx/source/unodraw/unopage.cxx b/svx/source/unodraw/unopage.cxx index 5fca5403d042..28082f35e75f 100644 --- a/svx/source/unodraw/unopage.cxx +++ b/svx/source/unodraw/unopage.cxx @@ -27,6 +27,7 @@ #include #include #include +#include #include #include @@ -330,6 +331,12 @@ void SAL_CALL SvxDrawPage::remove( const Reference< drawing::XShape >& xShape ) mpModel->SetChanged(); } +void SvxDrawPage::sort( const css::uno::Sequence< sal_Int32 >& sortOrder ) +{ + auto newOrder = comphelper::sequenceToContainer>(sortOrder); + mpPage->sort(newOrder); +} + // css::container::XIndexAccess sal_Int32 SAL_CALL SvxDrawPage::getCount() { diff --git a/xmloff/source/draw/shapeimport.cxx b/xmloff/source/draw/shapeimport.cxx index f3a5183b976e..6708e48e73dc 100644 --- a/xmloff/source/draw/shapeimport.cxx +++ b/xmloff/source/draw/shapeimport.cxx @@ -23,6 +23,7 @@ #include #include +#include #include #include @@ -795,9 +796,45 @@ void ShapeSortContext::popGroupAndSort() while( nCount ); } + bool bSorted = std::is_sorted(maZOrderList.begin(), maZOrderList.end(), + [&](const ZOrderHint& rLeft, const ZOrderHint& rRight) + { return rLeft.nShould < rRight.nShould; } ); + + if (bSorted) + return; // nothin' to do + // sort z-ordered shapes by nShould field std::sort(maZOrderList.begin(), maZOrderList.end()); + uno::Reference xShapes3(mxShapes, uno::UNO_QUERY); + if( xShapes3.is()) + { + uno::Sequence aNewOrder(maZOrderList.size() + maUnsortedList.size()); + sal_Int32 nIndex = 0; + + for (ZOrderHint& rHint : maZOrderList) + { + // fill in the gaps from unordered list + for (vector::iterator aIt = maUnsortedList.begin(); aIt != maUnsortedList.end() && nIndex < rHint.nShould; ) + { + aNewOrder[nIndex++] = (*aIt).nIs; + aIt = maUnsortedList.erase(aIt); + } + + aNewOrder[nIndex] = rHint.nIs; + nIndex++; + } + + try + { + xShapes3->sort(aNewOrder); + maZOrderList.clear(); + return; + } + catch (const css::lang::IllegalArgumentException& /*e*/) + {} + } + // this is the current index, all shapes before that // index are finished sal_Int32 nIndex = 0; -- cgit v1.2.3