cache mdds positions during ScDocument::CopyBlockFromClip() (tdf#112000)

Make RefUpdateContext and ScColumn::UpdateReferenceOnCopy() use the same
sc::ColumnBlockPositionSet that CopyFromClipContext uses. Without it
pathological cases like in tdf#112000 trigger quadratic cost because
of repeated mdds searches from the start.
Includes also an mdds patch that allows it to search backwards
from a position hint. Without it, this would be very difficult to fix
otherwise, as CopyFromClip() in ScDocument::CopyBlockFromClip()
moves the position hint past the area that UpdateReferenceOnCopy()
would use. It also just plain makes sense to try to go backwards
in an std::vector.

Change-Id: I985e3a40e4abf1a824e55c76d82579882fa75cc2
Reviewed-on: https://gerrit.libreoffice.org/72424
Tested-by: Jenkins
Reviewed-by: Luboš Luňák <l.lunak@collabora.com>

2 files changed, 51 insertions, 0 deletions

diff --git a/external/mdds/UnpackedTarball_mdds.mk b/external/mdds/UnpackedTarball_mdds.mk
index c015f4c13f5a..625204d29619 100644
--- a/external/mdds/UnpackedTarball_mdds.mk
+++ b/external/mdds/UnpackedTarball_mdds.mk
@@ -14,6 +14,7 @@ $(eval $(call gb_UnpackedTarball_set_tarball,mdds,$(MDDS_TARBALL)))
 $(eval $(call gb_UnpackedTarball_set_patchlevel,mdds,0))
 
 $(eval $(call gb_UnpackedTarball_add_patches,mdds,\
+	external/mdds/use-position-hint-also-back.patch \
 ))
 
 # vim: set noet sw=4 ts=4:
diff --git a/external/mdds/use-position-hint-also-back.patch b/external/mdds/use-position-hint-also-back.patch
new file mode 100644
index 000000000000..0b38c38d5536
--- /dev/null
+++ b/external/mdds/use-position-hint-also-back.patch
@@ -0,0 +1,50 @@
+From 726e2f02d14833bde2f7eef9677f5564c485a992 Mon Sep 17 00:00:00 2001
+From: =?UTF-8?q?Lubo=C5=A1=20Lu=C5=88=C3=A1k?= <l.lunak@centrum.cz>
+Date: Fri, 17 May 2019 13:55:20 +0200
+Subject: [PATCH] use position hint also when it is past the actual position
+
+The m_blocks data structure is a vector. It means that it can be
+also walked back, instead of resetting and starting from the very
+start.
+
+Allows a noticeable performance improvement in
+https://gerrit.libreoffice.org/#/c/72424/ .
+---
+ include/mdds/multi_type_vector_def.inl | 21 ++++++++++++++++++++-
+ 1 file changed, 20 insertions(+), 1 deletion(-)
+
+diff --git a/include/mdds/multi_type_vector_def.inl b/include/mdds/multi_type_vector_def.inl
+index 22a0ee2..09894e6 100644
+--- include/mdds/multi_type_vector_def.inl
++++ include/mdds/multi_type_vector_def.inl
+@@ -861,7 +861,26 @@ void multi_type_vector<_CellBlockFunc, _EventFunc>::get_block_position(
+ 
+     if (pos < start_row)
+     {
+-        // Position hint is past the insertion position. Reset.
++        // Position hint is past the insertion position.
++        // Walk back if that seems efficient.
++        if (pos > start_row / 2)
++        {
++            for (size_type i = block_index; i > 0;)
++            {
++                --i;
++                const block& blk = m_blocks[i];
++                start_row -= blk.m_size;
++                if (pos >= start_row)
++                {
++                    // Row is in this block.
++                    block_index = i;
++                    return;
++                }
++                // Specified row is not in this block.
++            }
++            assert(start_row == 0);
++        }
++        // Otherwise reset.
+         start_row = 0;
+         block_index = 0;
+     }
+-- 
+2.16.4
+