[Libreoffice-commits] core.git: svx/source

[Noel Grandin (via logerrit)]

 svx/source/accessibility/ChildrenManagerImpl.cxx |   35 +++++++++++++++++++----
 1 file changed, 30 insertions(+), 5 deletions(-)

New commits:
commit 8f9fd6806ccfbf381a383efe5d143ead86ee49de
Author:     Noel Grandin <noel.gran...@collabora.co.uk>
AuthorDate: Wed Jun 29 19:47:20 2022 +0200
Commit:     Noel Grandin <noel.gran...@collabora.co.uk>
CommitDate: Thu Jun 30 19:13:16 2022 +0200

    tdf#137544 reduce cost of ChildrenManagerImpl::Update
    
    there are 2 O(n^2) algorithms here, reduce them to O(n log n) by
    pre-sorting
    
    Change-Id: Ib3912155cda62cac95b5037528e23ef3c686a7e8
    Reviewed-on: https://gerrit.libreoffice.org/c/core/+/136655
    Tested-by: Jenkins
    Reviewed-by: Noel Grandin <noel.gran...@collabora.co.uk>

diff --git a/svx/source/accessibility/ChildrenManagerImpl.cxx 
b/svx/source/accessibility/ChildrenManagerImpl.cxx
index 56b47c74b710..d22f81e76684 100644
--- a/svx/source/accessibility/ChildrenManagerImpl.cxx
+++ b/svx/source/accessibility/ChildrenManagerImpl.cxx
@@ -316,6 +316,21 @@ void ChildrenManagerImpl::CreateListOfVisibleShapes (
     }
 }
 
+namespace
+{
+struct ChildDescriptorLess
+{
+    bool operator()(const ChildDescriptor& lhs, const ChildDescriptor& rhs) 
const
+    {
+        auto pLhsShape = lhs.mxShape.get();
+        auto pRhsShape = rhs.mxShape.get();
+        if (pLhsShape || pRhsShape)
+            return pLhsShape < pRhsShape;
+        return lhs.mxAccessibleShape.get() < rhs.mxAccessibleShape.get();
+    }
+};
+}
+    
 void ChildrenManagerImpl::RemoveNonVisibleChildren (
     const ChildDescriptorListType& rNewChildList,
     ChildDescriptorListType& rOldChildList)
@@ -323,9 +338,16 @@ void ChildrenManagerImpl::RemoveNonVisibleChildren (
     // Iterate over list of formerly visible children and remove those that
     // are not visible anymore, i.e. member of the new list of visible
     // children.
+
+    // the lists have already been sorted in MergeAccessibilityInformation
+    auto newIt = rNewChildList.begin();
+    auto newEnd = rNewChildList.end();
+
     for (auto& rChild : rOldChildList)
     {
-        if (::std::find(rNewChildList.begin(), rNewChildList.end(), rChild) == 
rNewChildList.end())
+        while (newIt != newEnd && ChildDescriptorLess()(*newIt, rChild))
+            newIt++;
+        if (newIt == newEnd || !(*newIt == rChild) )
         {
             // The child is disposed when there is a UNO shape from which
             // the accessible shape can be created when the shape becomes
@@ -349,16 +371,19 @@ void ChildrenManagerImpl::RemoveNonVisibleChildren (
 void ChildrenManagerImpl::MergeAccessibilityInformation (
     ChildDescriptorListType& raNewChildList)
 {
-    ChildDescriptorListType::const_iterator aStartVisibleChildren = 
maVisibleChildren.begin();
+    // sort the lists by mxShape, and then walk them in parallel, which avoids 
an O(n^2) loop
+    std::sort(maVisibleChildren.begin(), maVisibleChildren.end(), 
ChildDescriptorLess());
+    std::sort(raNewChildList.begin(), raNewChildList.end(), 
ChildDescriptorLess());
+    ChildDescriptorListType::const_iterator aOldChildDescriptor = 
maVisibleChildren.begin();
     ChildDescriptorListType::const_iterator aEndVisibleChildren = 
maVisibleChildren.end();
 
     for (auto& rChild : raNewChildList)
     {
-        ChildDescriptorListType::const_iterator aOldChildDescriptor =
-            std::find(aStartVisibleChildren, aEndVisibleChildren, rChild);
+        while (aOldChildDescriptor != aEndVisibleChildren && 
ChildDescriptorLess()(*aOldChildDescriptor, rChild))
+            aOldChildDescriptor++;
 
         // Copy accessible shape if that exists in the old descriptor.
-        if (aOldChildDescriptor != aEndVisibleChildren &&
+        if (aOldChildDescriptor != aEndVisibleChildren && *aOldChildDescriptor 
== rChild &&
             aOldChildDescriptor->mxAccessibleShape.is())
         {
             rChild.mxAccessibleShape = aOldChildDescriptor->mxAccessibleShape;