[ooo-build-commit] .: patches/dev300
Kohei Yoshida
kohei at kemper.freedesktop.org
Mon Mar 1 21:13:58 PST 2010
patches/dev300/apply | 3
patches/dev300/calc-perf-ods-import-row-height.diff | 1329 ++++++++++++++++++++
2 files changed, 1332 insertions(+)
New commits:
commit 688567fbb26e7ad1c6dd7667ccb344ed34b8fd1c
Author: Kohei Yoshida <kyoshida at novell.com>
Date: Tue Mar 2 00:09:31 2010 -0500
Speed up import of ods documents.
* patches/dev300/apply:
* patches/dev300/calc-perf-ods-import-row-height.diff: this patch
eliminates performance bottlenecks of flat_segment_tree esp.
wrt row height import. (n#582693)
diff --git a/patches/dev300/apply b/patches/dev300/apply
index 9e0aab7..f904ce1 100644
--- a/patches/dev300/apply
+++ b/patches/dev300/apply
@@ -948,6 +948,9 @@ calc-xls-export-hidden-row-height.diff, n#573938, i#109391, kohei
# fix for print selected cells functionality.
calc-print-selected-cells-fix.diff, n#569328, i#109386, kohei
+# Speed up row height data import from ods documents.
+calc-perf-ods-import-row-height.diff, n#582693, kohei
+
[ LinuxOnly ]
# accelerate linking, by extreme cunning i#63927
# this is an increasingly marginal win ...
diff --git a/patches/dev300/calc-perf-ods-import-row-height.diff b/patches/dev300/calc-perf-ods-import-row-height.diff
new file mode 100644
index 0000000..c28c2c0
--- /dev/null
+++ b/patches/dev300/calc-perf-ods-import-row-height.diff
@@ -0,0 +1,1329 @@
+diff --git sc/inc/document.hxx sc/inc/document.hxx
+index 237e3f8..97acc5e 100644
+--- sc/inc/document.hxx
++++ sc/inc/document.hxx
+@@ -1247,6 +1247,9 @@ public:
+ SC_DLLPUBLIC void SetRowHeight( SCROW nRow, SCTAB nTab, USHORT nNewHeight );
+ SC_DLLPUBLIC void SetRowHeightRange( SCROW nStartRow, SCROW nEndRow, SCTAB nTab,
+ USHORT nNewHeight );
++
++ SC_DLLPUBLIC void SetRowHeightOnly( SCROW nStartRow, SCROW nEndRow, SCTAB nTab,
++ USHORT nNewHeight );
+ void SetManualHeight( SCROW nStartRow, SCROW nEndRow, SCTAB nTab, BOOL bManual );
+
+ SC_DLLPUBLIC USHORT GetColWidth( SCCOL nCol, SCTAB nTab ) const;
+diff --git sc/inc/mdds/flatsegmenttree.hxx sc/inc/mdds/flatsegmenttree.hxx
+index 23dfc04..3128888 100644
+--- sc/inc/mdds/flatsegmenttree.hxx
++++ sc/inc/mdds/flatsegmenttree.hxx
+@@ -31,13 +31,14 @@
+ #include <iostream>
+ #include <utility>
+ #include <cassert>
++#include <limits>
+
+ #include "node.hxx"
+
+ #ifdef UNIT_TEST
++#include <cstdio>
+ #include <vector>
+ #endif
+-
+ namespace mdds {
+
+ template<typename _Key, typename _Value>
+@@ -75,6 +76,29 @@ public:
+ {
+ }
+
++ bool equals(const node& r) const
++ {
++ if (is_leaf != r.is_leaf)
++ return false;
++
++ if (is_leaf)
++ {
++ if (value_leaf.key != r.value_leaf.key)
++ return false;
++ if (value_leaf.value != r.value_leaf.value)
++ return false;
++ }
++ else
++ {
++ if (value_nonleaf.low != r.value_nonleaf.low)
++ return false;
++ if (value_nonleaf.high != r.value_nonleaf.high)
++ return false;
++ }
++
++ return true;
++ }
++
+ virtual void fill_nonleaf_value(const node_base_ptr& left_node, const node_base_ptr& right_node)
+ {
+ // Parent node should carry the range of all of its child nodes.
+@@ -296,6 +320,11 @@ public:
+
+ get_node(m_right_leaf)->value_leaf.key = max_val;
+ m_right_leaf->left = m_left_leaf;
++
++ // We don't ever use the value of the right leaf node, but we need the
++ // value to be always the same, to make it easier to check for
++ // equality.
++ get_node(m_right_leaf)->value_leaf.value = ::std::numeric_limits<value_type>::max();
+ }
+
+ ~flat_segment_tree()
+@@ -316,7 +345,8 @@ public:
+ }
+
+ /**
+- * Insert a new segment into the tree.
++ * Insert a new segment into the tree. It searches for the point of
++ * insertion from the first leaf node.
+ *
+ * @param start_key start value of the segment being inserted. The value
+ * is inclusive.
+@@ -326,132 +356,17 @@ public:
+ */
+ void insert_segment(key_type start_key, key_type end_key, value_type val)
+ {
+- if (end_key < get_node(m_left_leaf)->value_leaf.key || start_key > get_node(m_right_leaf)->value_leaf.key)
+- // The new segment does not overlap the current interval.
+- return;
+-
+- if (start_key < get_node(m_left_leaf)->value_leaf.key)
+- // The start value should not be smaller than the current minimum.
+- start_key = get_node(m_left_leaf)->value_leaf.key;
+-
+- if (end_key > get_node(m_right_leaf)->value_leaf.key)
+- // The end value should not be larger than the current maximum.
+- end_key = get_node(m_right_leaf)->value_leaf.key;
+-
+- if (start_key >= end_key)
+- return;
+-
+- // Find the node with value that either equals or is greater than the
+- // start value.
+-
+- node_base_ptr start_pos = get_insertion_pos_leaf(start_key, m_left_leaf);
+- if (!start_pos)
+- // Insertion position not found. Bail out.
+- return;
+-
+- node_base_ptr end_pos = get_insertion_pos_leaf(end_key, start_pos);
+- if (!end_pos)
+- end_pos = m_right_leaf;
+-
+- node_base_ptr new_start_node;
+- value_type old_value;
+-
+- // Set the start node.
+-
+- if (get_node(start_pos)->value_leaf.key == start_key)
+- {
+- // Re-use the existing node, but save the old value for later.
+-
+- if (start_pos->left && get_node(start_pos->left)->value_leaf.value == val)
+- {
+- // Extend the existing segment.
+- old_value = get_node(start_pos)->value_leaf.value;
+- new_start_node = start_pos->left;
+- }
+- else
+- {
+- // Update the value of the existing node.
+- old_value = get_node(start_pos)->value_leaf.value;
+- get_node(start_pos)->value_leaf.value = val;
+- new_start_node = start_pos;
+- }
+- }
+- else if (get_node(start_pos->left)->value_leaf.value == val)
+- {
+- // Extend the existing segment.
+- old_value = get_node(start_pos->left)->value_leaf.value;
+- new_start_node = start_pos->left;
+- }
+- else
+- {
+- // Insert a new node before the insertion position node.
+- node_base_ptr new_node(new node(true));
+- get_node(new_node)->value_leaf.key = start_key;
+- get_node(new_node)->value_leaf.value = val;
+- new_start_node = new_node;
+-
+- node_base_ptr left_node = start_pos->left;
+- old_value = get_node(left_node)->value_leaf.value;
+-
+- // Link to the left node.
+- link_nodes(left_node, new_node);
+-
+- // Link to the right node.
+- link_nodes(new_node, start_pos);
+- }
+-
+- node_base_ptr cur_node = new_start_node->right;
+- while (cur_node != end_pos)
+- {
+- // Disconnect the link between the current node and the previous node.
+- cur_node->left->right.reset();
+- cur_node->left.reset();
+- old_value = get_node(cur_node)->value_leaf.value;
+-
+- cur_node = cur_node->right;
+- }
+-
+- // Set the end node.
+-
+- if (get_node(end_pos)->value_leaf.key == end_key)
+- {
+- // The new segment ends exactly at the end node position.
+-
+- if (end_pos->right && get_node(end_pos)->value_leaf.value == val)
+- {
+- // Remove this node, and connect the new start node with the
+- // node that comes after this node.
+- new_start_node->right = end_pos->right;
+- if (end_pos->right)
+- end_pos->right->left = new_start_node;
+- disconnect_node(end_pos.get());
+- }
+- else
+- {
+- // Just link the new segment to this node.
+- new_start_node->right = end_pos;
+- end_pos->left = new_start_node;
+- }
+- }
+- else if (old_value == val)
+- {
+- link_nodes(new_start_node, end_pos);
+- }
+- else
+- {
+- // Insert a new node before the insertion position node.
+- node_base_ptr new_node(new node(true));
+- get_node(new_node)->value_leaf.key = end_key;
+- get_node(new_node)->value_leaf.value = old_value;
+-
+- // Link to the left node.
+- link_nodes(new_start_node, new_node);
+-
+- // Link to the right node.
+- link_nodes(new_node, end_pos);
+- }
++ insert_segment_impl(start_key, end_key, val, true);
++ }
+
+- m_valid_tree = false;
++ /**
++ * Insert a new segment into the tree. Unlike <code>insert_segment</code>,
++ * this method searches for the point of insertion from the last leaf
++ * node toward the first.
++ */
++ void insert_segment_back(key_type start_key, key_type end_key, value_type val)
++ {
++ insert_segment_impl(start_key, end_key, val, false);
+ }
+
+ /**
+@@ -463,98 +378,7 @@ public:
+ * @param start start position of the segment being removed.
+ * @param end end position of the segment being removed.
+ */
+- void shift_segment_left(key_type start_key, key_type end_key)
+- {
+- if (start_key >= end_key)
+- return;
+-
+- key_type left_leaf_key = get_node(m_left_leaf)->value_leaf.key;
+- key_type right_leaf_key = get_node(m_right_leaf)->value_leaf.key;
+- if (start_key < left_leaf_key || end_key < left_leaf_key)
+- // invalid key value
+- return;
+-
+- if (start_key > right_leaf_key || end_key > right_leaf_key)
+- // invalid key value.
+- return;
+-
+- node_base_ptr node_pos;
+- if (left_leaf_key == start_key)
+- node_pos = m_left_leaf;
+- else
+- // Get the first node with a key value equal to or greater than the
+- // start key value. But we want to skip the leftmost node.
+- node_pos = get_insertion_pos_leaf(start_key, m_left_leaf->right);
+-
+- if (!node_pos)
+- return;
+-
+- key_type segment_size = end_key - start_key;
+-
+- if (node_pos == m_right_leaf)
+- {
+- // The segment being removed begins after the last node before the
+- // right-most node.
+-
+- if (right_leaf_key <= end_key)
+- {
+- // The end position equals or is past the right-most node.
+- append_new_segment(start_key);
+- }
+- else
+- {
+- // The end position stops before the right-most node. Simply
+- // append the blank segment to the end.
+- append_new_segment(right_leaf_key - segment_size);
+- }
+- return;
+- }
+-
+- if (end_key < get_node(node_pos)->value_leaf.key)
+- {
+- // The removed segment does not overlap with any nodes. Simply
+- // shift the key values of those nodes that come after the removed
+- // segment.
+- shift_leaf_key_left(node_pos, m_right_leaf, segment_size);
+- append_new_segment(right_leaf_key - segment_size);
+- m_valid_tree = false;
+- return;
+- }
+-
+- // Move the first node to the starting position, and from there search
+- // for the first node whose key value is greater than the end value.
+- get_node(node_pos)->value_leaf.key = start_key;
+- node_base_ptr start_pos = node_pos;
+- node_pos = node_pos->right;
+- value_type last_seg_value = get_node(start_pos)->value_leaf.value;
+- while (get_node(node_pos) != get_node(m_right_leaf) && get_node(node_pos)->value_leaf.key <= end_key)
+- {
+- last_seg_value = get_node(node_pos)->value_leaf.value;
+- node_base_ptr next = node_pos->right;
+- disconnect_node(node_pos.get());
+- node_pos = next;
+- }
+-
+- get_node(start_pos)->value_leaf.value = last_seg_value;
+- start_pos->right = node_pos;
+- node_pos->left = start_pos;
+- if (start_pos->left && get_node(start_pos->left)->value_leaf.value == get_node(start_pos)->value_leaf.value)
+- {
+- // Removing a segment resulted in two consecutive segments with
+- // identical value. Combine them by removing the 2nd redundant
+- // node.
+- start_pos->left->right = start_pos->right;
+- start_pos->right->left = start_pos->left;
+- disconnect_node(start_pos.get());
+- }
+-
+- shift_leaf_key_left(node_pos, m_right_leaf, segment_size);
+- m_valid_tree = false;
+-
+- // Insert at the end a new segment with the initial base value, for
+- // the length of the removed segment.
+- append_new_segment(right_leaf_key - segment_size);
+- }
++ void shift_segment_left(key_type start_key, key_type end_key);
+
+ /**
+ * Shift all segments that occur at or after the specified start position
+@@ -563,185 +387,29 @@ public:
+ * @param pos position where the right-shift occurs.
+ * @param size amount of shift (must be greater than 0)
+ */
+- void shift_segment_right(key_type pos, key_type size, bool skip_start_node)
+- {
+- if (size <= 0)
+- return;
+-
+- if (pos < get_node(m_left_leaf)->value_leaf.key || get_node(m_right_leaf)->value_leaf.key <= pos)
+- // specified position is out-of-bound
+- return;
+-
+- if (get_node(m_left_leaf)->value_leaf.key == pos)
+- {
+- // Position is at the leftmost node. Shift all the other nodes,
+- // and insert a new node at (pos + size) position.
+- node_base_ptr cur_node = m_left_leaf->right;
+- shift_leaf_key_right(cur_node, m_right_leaf, size);
++ void shift_segment_right(key_type pos, key_type size, bool skip_start_node);
+
+- if (get_node(m_left_leaf)->value_leaf.value != m_init_val)
+- {
+- // The leftmost leaf node has a non-initial value. We need to
+- // insert a new node to carry that value after the shift.
+- node_base_ptr new_node(new node(true));
+- get_node(new_node)->value_leaf.key = pos + size;
+- get_node(new_node)->value_leaf.value = get_node(m_left_leaf)->value_leaf.value;
+- get_node(m_left_leaf)->value_leaf.value = m_init_val;
+- new_node->left = m_left_leaf;
+- new_node->right = m_left_leaf->right;
+- m_left_leaf->right = new_node;
+- }
+-
+- m_valid_tree = false;
+- return;
+- }
+-
+- // Get the first node with a key value equal to or greater than the
+- // start key value. But we want to skip the leftmost node.
+- node_base_ptr cur_node = get_insertion_pos_leaf(pos, m_left_leaf->right);
+-
+- // If the point of insertion is at an existing node position, don't
+- // shift that node but start with the one after it if that's
+- // requested.
+- if (skip_start_node && cur_node && get_node(cur_node)->value_leaf.key == pos)
+- cur_node = cur_node->right;
+-
+- if (!cur_node)
+- return;
+-
+- shift_leaf_key_right(cur_node, m_right_leaf, size);
+- m_valid_tree = false;
+- }
+-
+- bool search(key_type key, value_type& value, key_type* start_key = NULL, key_type* end_key = NULL) const
+- {
+- if (key < get_node(m_left_leaf)->value_leaf.key || get_node(m_right_leaf)->value_leaf.key <= key)
+- // key value is out-of-bound.
+- return false;
++ bool search(key_type key, value_type& value, key_type* start_key = NULL, key_type* end_key = NULL) const;
+
+- const node* pos = get_insertion_pos_leaf(key, get_node(m_left_leaf));
+- if (pos->value_leaf.key == key)
+- {
+- value = pos->value_leaf.value;
+- if (start_key)
+- *start_key = pos->value_leaf.key;
+- if (end_key && pos->right)
+- *end_key = get_node(pos->right)->value_leaf.key;
+- return true;
+- }
+- else if (pos->left && get_node(pos->left)->value_leaf.key < key)
+- {
+- value = get_node(pos->left)->value_leaf.value;
+- if (start_key)
+- *start_key = get_node(pos->left)->value_leaf.key;
+- if (end_key)
+- *end_key = pos->value_leaf.key;
+- return true;
+- }
++ bool search_tree(key_type key, value_type& value, key_type* start_key = NULL, key_type* end_key = NULL) const;
+
+- return false;
+- }
++ void build_tree();
+
+- bool search_tree(key_type key, value_type& value, key_type* start_key = NULL, key_type* end_key = NULL) const
++ bool is_tree_valid() const
+ {
+- if (!m_root_node || !m_valid_tree)
+- {
+- // either tree has not been built, or is in an invalid state.
+- return false;
+- }
+-
+- if (key < get_node(m_left_leaf)->value_leaf.key || get_node(m_right_leaf)->value_leaf.key <= key)
+- {
+- // key value is out-of-bound.
+- return false;
+- }
+-
+- // Descend down the tree through the last non-leaf layer.
+-
+- node* cur_node = get_node(m_root_node);
+- while (true)
+- {
+- if (cur_node->left)
+- {
+- if (cur_node->left->is_leaf)
+- break;
+-
+- const nonleaf_value_type& v = get_node(cur_node->left)->value_nonleaf;
+- if (v.low <= key && key < v.high)
+- {
+- cur_node = get_node(cur_node->left);
+- continue;
+- }
+- }
+- else
+- {
+- // left child node can't be missing !
+- return false;
+- }
+-
+- if (cur_node->right)
+- {
+- const nonleaf_value_type& v = get_node(cur_node->right)->value_nonleaf;
+- if (v.low <= key && key < v.high)
+- {
+- cur_node = get_node(cur_node->right);
+- continue;
+- }
+- }
+- return false;
+- }
+-
+- assert(cur_node->left->is_leaf && cur_node->right->is_leaf);
+-
+- key_type key1 = get_node(cur_node->left)->value_leaf.key;
+- key_type key2 = get_node(cur_node->right)->value_leaf.key;
+-
+- if (key1 <= key && key < key2)
+- {
+- cur_node = get_node(cur_node->left);
+- }
+- else if (key2 <= key && key < cur_node->value_nonleaf.high)
+- {
+- cur_node = get_node(cur_node->right);
+- }
+- else
+- cur_node = NULL;
+-
+- if (!cur_node)
+- {
+- return false;
+- }
+-
+- value = cur_node->value_leaf.value;
+- if (start_key)
+- *start_key = cur_node->value_leaf.key;
+-
+- if (end_key)
+- {
+- assert(cur_node->right);
+- if (cur_node->right)
+- *end_key = get_node(cur_node->right)->value_leaf.key;
+- else
+- // This should never happen, but just in case....
+- *end_key = get_node(m_right_leaf)->value_leaf.key;
+- }
+-
+- return true;
++ return m_valid_tree;
+ }
+
+- void build_tree()
+- {
+- if (!m_left_leaf)
+- return;
+-
+- clear_tree(m_root_node);
+- m_root_node = ::mdds::build_tree(m_left_leaf);
+- m_valid_tree = true;
+- }
++ /**
++ * Equality between two flat_segment_tree instances is evaluated by
++ * comparing the keys and the values of the leaf nodes only. Neither the
++ * non-leaf nodes nor the validity of the tree is evaluated.
++ */
++ bool operator==(const flat_segment_tree<key_type, value_type>& r) const;
+
+- bool is_tree_valid() const
++ bool operator !=(const flat_segment_tree<key_type, value_type>& r) const
+ {
+- return m_valid_tree;
++ return !operator==(r);
+ }
+
+ #ifdef UNIT_TEST
+@@ -876,35 +544,12 @@ private:
+ m_valid_tree = false;
+ }
+
+- node_base_ptr get_insertion_pos_leaf(key_type key, const node_base_ptr& start_pos) const
+- {
+- node_base_ptr cur_node = start_pos;
+- while (cur_node)
+- {
+- if (key <= get_node(cur_node)->value_leaf.key)
+- {
+- // Found the insertion position.
+- return cur_node;
+- }
+- cur_node = cur_node->right;
+- }
+- return node_base_ptr();
+- }
++ void insert_segment_impl(key_type start_key, key_type end_key, value_type val, bool forward);
+
+- const node* get_insertion_pos_leaf(key_type key, const node* start_pos) const
+- {
+- const node* cur_node = start_pos;
+- while (cur_node)
+- {
+- if (key <= cur_node->value_leaf.key)
+- {
+- // Found the insertion position.
+- return cur_node;
+- }
+- cur_node = get_node(cur_node->right);
+- }
+- return NULL;
+- }
++ node_base_ptr get_insertion_pos_leaf(key_type key, const node_base_ptr& start_pos) const;
++ node_base_ptr get_insertion_pos_leaf_reverse(key_type key, const node_base_ptr& start_pos) const;
++
++ const node* get_insertion_pos_leaf(key_type key, const node* start_pos) const;
+
+ static void shift_leaf_key_left(node_base_ptr& begin_node, node_base_ptr& end_node, key_type shift_value)
+ {
+@@ -955,6 +600,510 @@ private:
+ bool m_valid_tree;
+ };
+
++template<typename _Key, typename _Value>
++void flat_segment_tree<_Key, _Value>::insert_segment_impl(key_type start_key, key_type end_key, value_type val, bool forward)
++{
++ if (end_key < get_node(m_left_leaf)->value_leaf.key || start_key > get_node(m_right_leaf)->value_leaf.key)
++ // The new segment does not overlap the current interval.
++ return;
++
++ if (start_key < get_node(m_left_leaf)->value_leaf.key)
++ // The start value should not be smaller than the current minimum.
++ start_key = get_node(m_left_leaf)->value_leaf.key;
++
++ if (end_key > get_node(m_right_leaf)->value_leaf.key)
++ // The end value should not be larger than the current maximum.
++ end_key = get_node(m_right_leaf)->value_leaf.key;
++
++ if (start_key >= end_key)
++ return;
++
++ // Find the node with value that either equals or is greater than the
++ // start value.
++
++ node_base_ptr start_pos;
++ if (forward)
++ {
++ start_pos = get_insertion_pos_leaf(start_key, m_left_leaf);
++ }
++ else
++ {
++ start_pos = get_insertion_pos_leaf_reverse(start_key, m_right_leaf);
++ if (start_pos)
++ start_pos = start_pos->right;
++ else
++ start_pos = m_left_leaf;
++ }
++ if (!start_pos)
++ {
++ // Insertion position not found. Bail out.
++ assert(!"Insertion position not found. Bail out");
++ return;
++ }
++
++
++ node_base_ptr end_pos = get_insertion_pos_leaf(end_key, start_pos);
++ if (!end_pos)
++ end_pos = m_right_leaf;
++
++ node_base_ptr new_start_node;
++ value_type old_value;
++
++ // Set the start node.
++
++ if (get_node(start_pos)->value_leaf.key == start_key)
++ {
++ // Re-use the existing node, but save the old value for later.
++
++ if (start_pos->left && get_node(start_pos->left)->value_leaf.value == val)
++ {
++ // Extend the existing segment.
++ old_value = get_node(start_pos)->value_leaf.value;
++ new_start_node = start_pos->left;
++ }
++ else
++ {
++ // Update the value of the existing node.
++ old_value = get_node(start_pos)->value_leaf.value;
++ get_node(start_pos)->value_leaf.value = val;
++ new_start_node = start_pos;
++ }
++ }
++ else if (get_node(start_pos->left)->value_leaf.value == val)
++ {
++ // Extend the existing segment.
++ old_value = get_node(start_pos->left)->value_leaf.value;
++ new_start_node = start_pos->left;
++ }
++ else
++ {
++ // Insert a new node before the insertion position node.
++ node_base_ptr new_node(new node(true));
++ get_node(new_node)->value_leaf.key = start_key;
++ get_node(new_node)->value_leaf.value = val;
++ new_start_node = new_node;
++
++ node_base_ptr left_node = start_pos->left;
++ old_value = get_node(left_node)->value_leaf.value;
++
++ // Link to the left node.
++ link_nodes(left_node, new_node);
++
++ // Link to the right node.
++ link_nodes(new_node, start_pos);
++ }
++
++ node_base_ptr cur_node = new_start_node->right;
++ while (cur_node != end_pos)
++ {
++ // Disconnect the link between the current node and the previous node.
++ cur_node->left->right.reset();
++ cur_node->left.reset();
++ old_value = get_node(cur_node)->value_leaf.value;
++
++ cur_node = cur_node->right;
++ }
++
++ // Set the end node.
++
++ if (get_node(end_pos)->value_leaf.key == end_key)
++ {
++ // The new segment ends exactly at the end node position.
++
++ if (end_pos->right && get_node(end_pos)->value_leaf.value == val)
++ {
++ // Remove this node, and connect the new start node with the
++ // node that comes after this node.
++ new_start_node->right = end_pos->right;
++ if (end_pos->right)
++ end_pos->right->left = new_start_node;
++ disconnect_node(end_pos.get());
++ }
++ else
++ {
++ // Just link the new segment to this node.
++ new_start_node->right = end_pos;
++ end_pos->left = new_start_node;
++ }
++ }
++ else if (old_value == val)
++ {
++ link_nodes(new_start_node, end_pos);
++ }
++ else
++ {
++ // Insert a new node before the insertion position node.
++ node_base_ptr new_node(new node(true));
++ get_node(new_node)->value_leaf.key = end_key;
++ get_node(new_node)->value_leaf.value = old_value;
++
++ // Link to the left node.
++ link_nodes(new_start_node, new_node);
++
++ // Link to the right node.
++ link_nodes(new_node, end_pos);
++ }
++
++ m_valid_tree = false;
++}
++
++template<typename _Key, typename _Value>
++void flat_segment_tree<_Key, _Value>::shift_segment_left(key_type start_key, key_type end_key)
++{
++ if (start_key >= end_key)
++ return;
++
++ key_type left_leaf_key = get_node(m_left_leaf)->value_leaf.key;
++ key_type right_leaf_key = get_node(m_right_leaf)->value_leaf.key;
++ if (start_key < left_leaf_key || end_key < left_leaf_key)
++ // invalid key value
++ return;
++
++ if (start_key > right_leaf_key || end_key > right_leaf_key)
++ // invalid key value.
++ return;
++
++ node_base_ptr node_pos;
++ if (left_leaf_key == start_key)
++ node_pos = m_left_leaf;
++ else
++ // Get the first node with a key value equal to or greater than the
++ // start key value. But we want to skip the leftmost node.
++ node_pos = get_insertion_pos_leaf(start_key, m_left_leaf->right);
++
++ if (!node_pos)
++ return;
++
++ key_type segment_size = end_key - start_key;
++
++ if (node_pos == m_right_leaf)
++ {
++ // The segment being removed begins after the last node before the
++ // right-most node.
++
++ if (right_leaf_key <= end_key)
++ {
++ // The end position equals or is past the right-most node.
++ append_new_segment(start_key);
++ }
++ else
++ {
++ // The end position stops before the right-most node. Simply
++ // append the blank segment to the end.
++ append_new_segment(right_leaf_key - segment_size);
++ }
++ return;
++ }
++
++ if (end_key < get_node(node_pos)->value_leaf.key)
++ {
++ // The removed segment does not overlap with any nodes. Simply
++ // shift the key values of those nodes that come after the removed
++ // segment.
++ shift_leaf_key_left(node_pos, m_right_leaf, segment_size);
++ append_new_segment(right_leaf_key - segment_size);
++ m_valid_tree = false;
++ return;
++ }
++
++ // Move the first node to the starting position, and from there search
++ // for the first node whose key value is greater than the end value.
++ get_node(node_pos)->value_leaf.key = start_key;
++ node_base_ptr start_pos = node_pos;
++ node_pos = node_pos->right;
++ value_type last_seg_value = get_node(start_pos)->value_leaf.value;
++ while (get_node(node_pos) != get_node(m_right_leaf) && get_node(node_pos)->value_leaf.key <= end_key)
++ {
++ last_seg_value = get_node(node_pos)->value_leaf.value;
++ node_base_ptr next = node_pos->right;
++ disconnect_node(node_pos.get());
++ node_pos = next;
++ }
++
++ get_node(start_pos)->value_leaf.value = last_seg_value;
++ start_pos->right = node_pos;
++ node_pos->left = start_pos;
++ if (start_pos->left && get_node(start_pos->left)->value_leaf.value == get_node(start_pos)->value_leaf.value)
++ {
++ // Removing a segment resulted in two consecutive segments with
++ // identical value. Combine them by removing the 2nd redundant
++ // node.
++ start_pos->left->right = start_pos->right;
++ start_pos->right->left = start_pos->left;
++ disconnect_node(start_pos.get());
++ }
++
++ shift_leaf_key_left(node_pos, m_right_leaf, segment_size);
++ m_valid_tree = false;
++
++ // Insert at the end a new segment with the initial base value, for
++ // the length of the removed segment.
++ append_new_segment(right_leaf_key - segment_size);
++}
++
++template<typename _Key, typename _Value>
++void flat_segment_tree<_Key, _Value>::shift_segment_right(key_type pos, key_type size, bool skip_start_node)
++{
++ if (size <= 0)
++ return;
++
++ if (pos < get_node(m_left_leaf)->value_leaf.key || get_node(m_right_leaf)->value_leaf.key <= pos)
++ // specified position is out-of-bound
++ return;
++
++ if (get_node(m_left_leaf)->value_leaf.key == pos)
++ {
++ // Position is at the leftmost node. Shift all the other nodes,
++ // and insert a new node at (pos + size) position.
++ node_base_ptr cur_node = m_left_leaf->right;
++ shift_leaf_key_right(cur_node, m_right_leaf, size);
++
++ if (get_node(m_left_leaf)->value_leaf.value != m_init_val)
++ {
++ // The leftmost leaf node has a non-initial value. We need to
++ // insert a new node to carry that value after the shift.
++ node_base_ptr new_node(new node(true));
++ get_node(new_node)->value_leaf.key = pos + size;
++ get_node(new_node)->value_leaf.value = get_node(m_left_leaf)->value_leaf.value;
++ get_node(m_left_leaf)->value_leaf.value = m_init_val;
++ new_node->left = m_left_leaf;
++ new_node->right = m_left_leaf->right;
++ m_left_leaf->right = new_node;
++ }
++
++ m_valid_tree = false;
++ return;
++ }
++
++ // Get the first node with a key value equal to or greater than the
++ // start key value. But we want to skip the leftmost node.
++ node_base_ptr cur_node = get_insertion_pos_leaf(pos, m_left_leaf->right);
++
++ // If the point of insertion is at an existing node position, don't
++ // shift that node but start with the one after it if that's
++ // requested.
++ if (skip_start_node && cur_node && get_node(cur_node)->value_leaf.key == pos)
++ cur_node = cur_node->right;
++
++ if (!cur_node)
++ return;
++
++ shift_leaf_key_right(cur_node, m_right_leaf, size);
++ m_valid_tree = false;
+ }
+
++template<typename _Key, typename _Value>
++bool flat_segment_tree<_Key, _Value>::search(
++ key_type key, value_type& value, key_type* start_key, key_type* end_key) const
++{
++ if (key < get_node(m_left_leaf)->value_leaf.key || get_node(m_right_leaf)->value_leaf.key <= key)
++ // key value is out-of-bound.
++ return false;
++
++ const node* pos = get_insertion_pos_leaf(key, get_node(m_left_leaf));
++ if (pos->value_leaf.key == key)
++ {
++ value = pos->value_leaf.value;
++ if (start_key)
++ *start_key = pos->value_leaf.key;
++ if (end_key && pos->right)
++ *end_key = get_node(pos->right)->value_leaf.key;
++ return true;
++ }
++ else if (pos->left && get_node(pos->left)->value_leaf.key < key)
++ {
++ value = get_node(pos->left)->value_leaf.value;
++ if (start_key)
++ *start_key = get_node(pos->left)->value_leaf.key;
++ if (end_key)
++ *end_key = pos->value_leaf.key;
++ return true;
++ }
++
++ return false;
++}
++
++template<typename _Key, typename _Value>
++bool flat_segment_tree<_Key, _Value>::search_tree(
++ key_type key, value_type& value, key_type* start_key, key_type* end_key) const
++{
++ if (!m_root_node || !m_valid_tree)
++ {
++ // either tree has not been built, or is in an invalid state.
++ return false;
++ }
++
++ if (key < get_node(m_left_leaf)->value_leaf.key || get_node(m_right_leaf)->value_leaf.key <= key)
++ {
++ // key value is out-of-bound.
++ return false;
++ }
++
++ // Descend down the tree through the last non-leaf layer.
++
++ node* cur_node = get_node(m_root_node);
++ while (true)
++ {
++ if (cur_node->left)
++ {
++ if (cur_node->left->is_leaf)
++ break;
++
++ const nonleaf_value_type& v = get_node(cur_node->left)->value_nonleaf;
++ if (v.low <= key && key < v.high)
++ {
++ cur_node = get_node(cur_node->left);
++ continue;
++ }
++ }
++ else
++ {
++ // left child node can't be missing !
++ return false;
++ }
++
++ if (cur_node->right)
++ {
++ const nonleaf_value_type& v = get_node(cur_node->right)->value_nonleaf;
++ if (v.low <= key && key < v.high)
++ {
++ cur_node = get_node(cur_node->right);
++ continue;
++ }
++ }
++ return false;
++ }
++
++ assert(cur_node->left->is_leaf && cur_node->right->is_leaf);
++
++ key_type key1 = get_node(cur_node->left)->value_leaf.key;
++ key_type key2 = get_node(cur_node->right)->value_leaf.key;
++
++ if (key1 <= key && key < key2)
++ {
++ cur_node = get_node(cur_node->left);
++ }
++ else if (key2 <= key && key < cur_node->value_nonleaf.high)
++ {
++ cur_node = get_node(cur_node->right);
++ }
++ else
++ cur_node = NULL;
++
++ if (!cur_node)
++ {
++ return false;
++ }
++
++ value = cur_node->value_leaf.value;
++ if (start_key)
++ *start_key = cur_node->value_leaf.key;
++
++ if (end_key)
++ {
++ assert(cur_node->right);
++ if (cur_node->right)
++ *end_key = get_node(cur_node->right)->value_leaf.key;
++ else
++ // This should never happen, but just in case....
++ *end_key = get_node(m_right_leaf)->value_leaf.key;
++ }
++
++ return true;
++}
++
++template<typename _Key, typename _Value>
++void flat_segment_tree<_Key, _Value>::build_tree()
++{
++ if (!m_left_leaf)
++ return;
++
++ clear_tree(m_root_node);
++ m_root_node = ::mdds::build_tree(m_left_leaf);
++ m_valid_tree = true;
++}
++
++template<typename _Key, typename _Value>
++bool flat_segment_tree<_Key, _Value>::operator==(const flat_segment_tree<key_type, value_type>& r) const
++{
++ const node* n1 = get_node(m_left_leaf);
++ const node* n2 = get_node(r.m_left_leaf);
++
++ if ((!n1 && n2) || (n1 && !n2))
++ // Either one of them is NULL;
++ return false;
++
++ while (n1)
++ {
++ if (!n2)
++ return false;
++
++ if (!n1->equals(*n2))
++ return false;
++
++ n1 = get_node(n1->right);
++ n2 = get_node(n2->right);
++ }
++
++ if (n2)
++ // n1 is NULL, but n2 is not.
++ return false;
++
++ // All leaf nodes are equal.
++ return true;
++}
++
++template<typename _Key, typename _Value>
++node_base_ptr flat_segment_tree<_Key, _Value>::get_insertion_pos_leaf(
++ key_type key, const node_base_ptr& start_pos) const
++{
++ node_base_ptr cur_node = start_pos;
++ while (cur_node)
++ {
++ if (key <= get_node(cur_node)->value_leaf.key)
++ {
++ // Found the insertion position.
++ return cur_node;
++ }
++ cur_node = cur_node->right;
++ }
++ return node_base_ptr();
++}
++
++template<typename _Key, typename _Value>
++node_base_ptr flat_segment_tree<_Key, _Value>::get_insertion_pos_leaf_reverse(
++ key_type key, const node_base_ptr& start_pos) const
++{
++ node_base_ptr cur_node = start_pos;
++ while (cur_node)
++ {
++ if (key > get_node(cur_node)->value_leaf.key)
++ {
++ // Found the insertion position.
++ return cur_node;
++ }
++ cur_node = cur_node->left;
++ }
++ return node_base_ptr();
++}
++
++template<typename _Key, typename _Value>
++const typename flat_segment_tree<_Key, _Value>::node*
++flat_segment_tree<_Key, _Value>::get_insertion_pos_leaf(key_type key, const node* start_pos) const
++{
++ const node* cur_node = start_pos;
++ while (cur_node)
++ {
++ if (key <= cur_node->value_leaf.key)
++ {
++ // Found the insertion position.
++ return cur_node;
++ }
++ cur_node = get_node(cur_node->right);
++ }
++ return NULL;
++}
++
++} // namespace mdds
++
+ #endif
+diff --git sc/inc/mdds/node.hxx sc/inc/mdds/node.hxx
+index 59749a0..04da08c 100644
+--- sc/inc/mdds/node.hxx
++++ sc/inc/mdds/node.hxx
+@@ -34,7 +34,7 @@
+
+ //#define DEBUG_NODE_BASE 1
+
+-#define USE_INTRUSIVE_PTR 0
++#define USE_INTRUSIVE_PTR 1
+
+ #if USE_INTRUSIVE_PTR
+ #include <boost/intrusive_ptr.hpp>
+diff --git sc/inc/segmenttree.hxx sc/inc/segmenttree.hxx
+index 3522d9b..b946f6c 100644
+--- sc/inc/segmenttree.hxx
++++ sc/inc/segmenttree.hxx
+@@ -156,6 +156,9 @@ public:
+
+ SCROW findLastNotOf(sal_uInt16 nValue) const;
+
++ void enableTreeSearch(bool bEnable);
++ void setInsertFromBack(bool bInsertFromBack);
++
+ private:
+ ::std::auto_ptr<ScFlatUInt16SegmentsImpl> mpImpl;
+ };
+diff --git sc/inc/table.hxx sc/inc/table.hxx
+index 5fb2be1..c1df60a 100644
+--- sc/inc/table.hxx
++++ sc/inc/table.hxx
+@@ -610,6 +610,16 @@ public:
+ void SetRowHeight( SCROW nRow, USHORT nNewHeight );
+ BOOL SetRowHeightRange( SCROW nStartRow, SCROW nEndRow, USHORT nNewHeight,
+ double nPPTX, double nPPTY );
++
++ /**
++ * Set specified row height to specified ranges. Don't check for drawing
++ * objects etc. Just set the row height. Nothing else.
++ *
++ * Note that setting a new row height via this function will not
++ * invalidate page breaks.
++ */
++ void SetRowHeightOnly( SCROW nStartRow, SCROW nEndRow, USHORT nNewHeight );
++
+ // nPPT fuer Test auf Veraenderung
+ void SetManualHeight( SCROW nStartRow, SCROW nEndRow, BOOL bManual );
+
+@@ -852,6 +862,8 @@ private:
+ void StartNeededListeners(); // only for cells where NeedsListening()==TRUE
+ void SetRelNameDirty();
+
++ void SetLoadingMedium(bool bLoading);
++
+ SCSIZE FillMaxRot( RowInfo* pRowInfo, SCSIZE nArrCount, SCCOL nX1, SCCOL nX2,
+ SCCOL nCol, SCROW nAttrRow1, SCROW nAttrRow2, SCSIZE nArrY,
+ const ScPatternAttr* pPattern, const SfxItemSet* pCondSet );
+diff --git sc/source/core/data/documen9.cxx sc/source/core/data/documen9.cxx
+index 5591d98..0d80f7a 100644
+--- sc/source/core/data/documen9.cxx
++++ sc/source/core/data/documen9.cxx
+@@ -826,6 +826,9 @@ void ScDocument::SetImportingXML( BOOL bVal )
+ SetLayoutRTL( nTab, TRUE ); // includes mirroring; bImportingXML must be cleared first
+ }
+ }
++
++ for (SCTAB nTab = 0; nTab <= MAXTAB && pTab[nTab]; ++nTab)
++ pTab[nTab]->SetLoadingMedium(bVal);
+ }
+
+ void ScDocument::SetXMLFromWrapper( BOOL bVal )
+diff --git sc/source/core/data/document.cxx sc/source/core/data/document.cxx
+index 917ddf9..2e5222e 100644
+--- sc/source/core/data/document.cxx
++++ sc/source/core/data/document.cxx
+@@ -3149,6 +3149,11 @@ void ScDocument::SetRowHeightRange( SCROW nStartRow, SCROW nEndRow, SCTAB nTab,
+ ( nStartRow, nEndRow, nNewHeight, 1.0, 1.0 );
+ }
+
++void ScDocument::SetRowHeightOnly( SCROW nStartRow, SCROW nEndRow, SCTAB nTab, USHORT nNewHeight )
++{
++ if ( ValidTab(nTab) && pTab[nTab] )
++ pTab[nTab]->SetRowHeightOnly( nStartRow, nEndRow, nNewHeight );
++}
+
+ void ScDocument::SetManualHeight( SCROW nStartRow, SCROW nEndRow, SCTAB nTab, BOOL bManual )
+ {
+diff --git sc/source/core/data/segmenttree.cxx sc/source/core/data/segmenttree.cxx
+index 7097157..8c4740d 100644
+--- sc/source/core/data/segmenttree.cxx
++++ sc/source/core/data/segmenttree.cxx
+@@ -70,15 +70,30 @@ public:
+ bool getFirst(RangeData& rData);
+ bool getNext(RangeData& rData);
+
++ void enableTreeSearch(bool b)
++ {
++ mbTreeSearchEnabled = b;
++ }
++
++ void setInsertFromBack(bool b)
++ {
++ mbInsertFromBack = b;
++ }
++
+ private:
+ typedef ::mdds::flat_segment_tree<SCCOLROW, ValueType> fst_type;
+ fst_type maSegments;
+ typename fst_type::const_iterator maItr;
++
++ bool mbTreeSearchEnabled:1;
++ bool mbInsertFromBack:1;
+ };
+
+ template<typename _ValueType, typename _ExtValueType>
+ ScFlatSegmentsImpl<_ValueType, _ExtValueType>::ScFlatSegmentsImpl(SCCOLROW nMax, ValueType nDefault) :
+- maSegments(0, nMax+1, nDefault)
++ maSegments(0, nMax+1, nDefault),
++ mbTreeSearchEnabled(true),
++ mbInsertFromBack(false)
+ {
+ }
+
+@@ -90,13 +105,22 @@ ScFlatSegmentsImpl<_ValueType, _ExtValueType>::~ScFlatSegmentsImpl()
+ template<typename _ValueType, typename _ExtValueType>
+ void ScFlatSegmentsImpl<_ValueType, _ExtValueType>::setValue(SCCOLROW nPos1, SCCOLROW nPos2, ValueType nValue)
+ {
+- maSegments.insert_segment(nPos1, nPos2+1, nValue);
++ if (mbInsertFromBack)
++ maSegments.insert_segment_back(nPos1, nPos2+1, nValue);
++ else
++ maSegments.insert_segment(nPos1, nPos2+1, nValue);
+ }
+
+ template<typename _ValueType, typename _ExtValueType>
+ typename ScFlatSegmentsImpl<_ValueType, _ExtValueType>::ValueType ScFlatSegmentsImpl<_ValueType, _ExtValueType>::getValue(SCCOLROW nPos)
+ {
+ ValueType nValue = 0;
++ if (!mbTreeSearchEnabled)
++ {
++ maSegments.search(nPos, nValue);
++ return nValue;
++ }
++
+ if (!maSegments.is_tree_valid())
+ maSegments.build_tree();
+
+@@ -136,13 +160,23 @@ ScFlatSegmentsImpl<_ValueType, _ExtValueType>::getSumValue(SCCOLROW nPos1, SCCOL
+ template<typename _ValueType, typename _ExtValueType>
+ bool ScFlatSegmentsImpl<_ValueType, _ExtValueType>::getRangeData(SCCOLROW nPos, RangeData& rData)
+ {
+- if (!maSegments.is_tree_valid())
+- maSegments.build_tree();
+-
+ ValueType nValue;
+ SCCOLROW nPos1, nPos2;
+- if (!maSegments.search_tree(nPos, nValue, &nPos1, &nPos2))
+- return false;
++
++ if (mbTreeSearchEnabled)
++ {
++ if (!maSegments.is_tree_valid())
++ maSegments.build_tree();
++
++ if (!maSegments.search_tree(nPos, nValue, &nPos1, &nPos2))
++ return false;
++ }
++ else
++ {
++ // Conduct leaf-node only search. Faster when searching between range insertion.
++ if (!maSegments.search(nPos, nValue, &nPos1, &nPos2))
++ return false;
++ }
+
+ rData.mnPos1 = nPos1;
+ rData.mnPos2 = nPos2-1; // end point is not inclusive.
+@@ -493,3 +527,14 @@ SCROW ScFlatUInt16RowSegments::findLastNotOf(sal_uInt16 nValue) const
+ {
+ return static_cast<SCROW>(mpImpl->findLastNotOf(nValue));
+ }
++
++void ScFlatUInt16RowSegments::enableTreeSearch(bool bEnable)
++{
++ mpImpl->enableTreeSearch(bEnable);
++}
++
++void ScFlatUInt16RowSegments::setInsertFromBack(bool bInsertFromBack)
++{
++ mpImpl->setInsertFromBack(bInsertFromBack);
++}
++
+diff --git sc/source/core/data/table2.cxx sc/source/core/data/table2.cxx
+index 7511774..f716198 100644
+--- sc/source/core/data/table2.cxx
++++ sc/source/core/data/table2.cxx
+@@ -1185,6 +1185,17 @@ void ScTable::SetRelNameDirty()
+ }
+
+
++void ScTable::SetLoadingMedium(bool bLoading)
++{
++ mpRowHeights->enableTreeSearch(!bLoading);
++
++ // When loading a medium, prefer inserting row heights from the back
++ // position since the row heights are stored and read in ascending order
++ // during import.
++ mpRowHeights->setInsertFromBack(bLoading);
++}
++
++
+ void ScTable::CalcAll()
+ {
+ for (SCCOL i=0; i<=MAXCOL; i++) aCol[i].CalcAll();
+@@ -2216,6 +2227,16 @@ BOOL ScTable::SetRowHeightRange( SCROW nStartRow, SCROW nEndRow, USHORT nNewHeig
+ return bChanged;
+ }
+
++void ScTable::SetRowHeightOnly( SCROW nStartRow, SCROW nEndRow, USHORT nNewHeight )
++{
++ if (!ValidRow(nStartRow) || !ValidRow(nEndRow) || !mpRowHeights)
++ return;
++
++ if (!nNewHeight)
++ nNewHeight = ScGlobal::nStdRowHeight;
++
++ mpRowHeights->setValue(nStartRow, nEndRow, nNewHeight);
++}
+
+ void ScTable::SetManualHeight( SCROW nStartRow, SCROW nEndRow, BOOL bManual )
+ {
+diff --git sc/source/ui/unoobj/docuno.cxx sc/source/ui/unoobj/docuno.cxx
+index 51c16b1..492a3f5 100644
+--- sc/source/ui/unoobj/docuno.cxx
++++ sc/source/ui/unoobj/docuno.cxx
+@@ -2891,8 +2891,11 @@ void SAL_CALL ScTableRowsObj::setPropertyValue(
+ sal_Int32 nNewHeight = 0;
+ if ( pDoc->IsImportingXML() && ( aValue >>= nNewHeight ) )
+ {
+- // used to set the stored row height for rows with optimal height when loading
+- pDoc->SetRowHeightRange( nStartRow, nEndRow, nTab, (USHORT)HMMToTwips(nNewHeight) );
++ // used to set the stored row height for rows with optimal height when loading.
++
++ // TODO: It's probably cleaner to use a different property name
++ // for this.
++ pDoc->SetRowHeightOnly( nStartRow, nEndRow, nTab, (USHORT)HMMToTwips(nNewHeight) );
+ }
+ else
+ {
More information about the ooo-build-commit
mailing list