[ooo-build-commit] patches/dev300
Kohei Yoshida
kohei at kemper.freedesktop.org
Wed Jul 1 09:56:42 PDT 2009
patches/dev300/calc-perf-flat-segment-tree.diff | 144 ++++++++++++++++++++---
patches/dev300/calc-perf-table-hidden-flags.diff | 30 ++++
2 files changed, 161 insertions(+), 13 deletions(-)
New commits:
commit afe7e0d8c85bc2cf95f3e70cef081255ec99ff20
Author: Kohei Yoshida <kyoshida at novell.com>
Date: Wed Jul 1 12:55:36 2009 -0400
Shift hidden and filtered flags when necessary.
Shift hidden and filtered flags for row/column insertions and column
deletions. This (hopefully) concludes the fix for n#516406.
* patches/dev300/calc-perf-flat-segment-tree.diff:
* patches/dev300/calc-perf-table-hidden-flags.diff:
diff --git a/patches/dev300/calc-perf-flat-segment-tree.diff b/patches/dev300/calc-perf-flat-segment-tree.diff
index caf2dc8..e7ee4c3 100644
--- a/patches/dev300/calc-perf-flat-segment-tree.diff
+++ b/patches/dev300/calc-perf-flat-segment-tree.diff
@@ -1,9 +1,9 @@
diff --git sc/inc/mdds/flatsegmenttree.hxx sc/inc/mdds/flatsegmenttree.hxx
new file mode 100644
-index 0000000..d5ab674
+index 0000000..96a6256
--- /dev/null
+++ sc/inc/mdds/flatsegmenttree.hxx
-@@ -0,0 +1,662 @@
+@@ -0,0 +1,761 @@
+/*************************************************************************
+ *
+ * Copyright (c) 2008-2009 Kohei Yoshida
@@ -147,6 +147,7 @@ index 0000000..d5ab674
+ m_root_node(static_cast<node*>(NULL)),
+ m_left_leaf(new node(true)),
+ m_right_leaf(new node(true)),
++ m_init_val(init_val),
+ m_valid_tree(false)
+ {
+ // we need to create two end nodes during initialization.
@@ -316,8 +317,8 @@ index 0000000..d5ab674
+
+ /**
+ * Remove a segment specified by the start and end key values, and shift
-+ * the remaining segments (segments with key values greater than the end
-+ * key of the removed segment) to left.
++ * the remaining segments (i.e. those segments that come after the removed
++ * segment) to left.
+ *
+ * @param start start value of the segment being removed.
+ * @param end end value of the segment being removed.
@@ -327,8 +328,18 @@ index 0000000..d5ab674
+ if (start >= end)
+ 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 < left_leaf_key || end < left_leaf_key)
++ // invalid key value
++ return;
++
++ if (start > right_leaf_key || end > right_leaf_key)
++ // invalid key value.
++ return;
++
+ node_base_ptr node_pos;
-+ if (get_node(m_left_leaf)->value_leaf.key == start)
++ if (left_leaf_key == start)
+ node_pos = m_left_leaf;
+ else
+ // Get the first node with a key value equal to or greater than the
@@ -345,7 +356,7 @@ index 0000000..d5ab674
+ // 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(node_pos, m_right_leaf, segment_size);
++ shift_leaf_key_left(node_pos, m_right_leaf, segment_size);
+ m_valid_tree = false;
+ return;
+ }
@@ -377,7 +388,64 @@ index 0000000..d5ab674
+ disconnect_node(start_pos.get());
+ }
+
-+ shift_leaf_key(node_pos, m_right_leaf, segment_size);
++ shift_leaf_key_left(node_pos, m_right_leaf, segment_size);
++ m_valid_tree = false;
++ }
++
++ /**
++ * Shift all segments that occur at or after the specified start position
++ * to right by the size specified.
++ *
++ * @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);
++
++ 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;
+ }
+
@@ -645,7 +713,7 @@ index 0000000..d5ab674
+ return NULL;
+ }
+
-+ void shift_leaf_key(node_base_ptr& begin_node, node_base_ptr& end_node, key_type shift_value)
++ static void shift_leaf_key_left(node_base_ptr& begin_node, node_base_ptr& end_node, key_type shift_value)
+ {
+ node* cur_node_p = get_node(begin_node);
+ node* end_node_p = get_node(end_node);
@@ -656,10 +724,41 @@ index 0000000..d5ab674
+ }
+ }
+
++ static void shift_leaf_key_right(node_base_ptr& cur_node, node_base_ptr& end_node, key_type shift_value)
++ {
++ key_type end_node_key = get_node(end_node)->value_leaf.key;
++ while (get_node(cur_node) != get_node(end_node))
++ {
++ get_node(cur_node)->value_leaf.key += shift_value;
++ if (get_node(cur_node)->value_leaf.key < end_node_key)
++ {
++ // The node is still in-bound. Keep shifting.
++ cur_node = cur_node->right;
++ continue;
++ }
++
++ // This node has been pushed outside the end node position.
++ // Remove all nodes that follows, and connect the previous node
++ // with the end node.
++
++ node_base_ptr last_node = cur_node->left;
++ while (get_node(cur_node) != get_node(end_node))
++ {
++ node_base_ptr next_node = cur_node->right;
++ disconnect_node(cur_node);
++ cur_node = next_node;
++ }
++ last_node->right = end_node;
++ end_node->left = last_node;
++ return;
++ }
++ }
++
+private:
+ node_base_ptr m_root_node;
+ node_base_ptr m_left_leaf;
+ node_base_ptr m_right_leaf;
++ value_type m_init_val;
+ bool m_valid_tree;
+};
+
@@ -981,10 +1080,10 @@ index 0000000..59749a0
+#endif
diff --git sc/inc/segmenttree.hxx sc/inc/segmenttree.hxx
new file mode 100644
-index 0000000..f414002
+index 0000000..466f9ed
--- /dev/null
+++ sc/inc/segmenttree.hxx
-@@ -0,0 +1,87 @@
+@@ -0,0 +1,89 @@
+/*************************************************************************
+ *
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
@@ -1041,6 +1140,7 @@ index 0000000..f414002
+ bool getValue(SCROW nRow);
+ bool getRangeData(SCROW nRow, RangeData& rData);
+ void removeSegment(SCROW nRow1, SCROW nRow2);
++ void insertSegment(SCROW nRow, SCROW nSize, bool bSkipStartBoundary);
+
+private:
+ ::std::auto_ptr<ScFlatBoolSegmentsImpl> mpImpl;
@@ -1065,6 +1165,7 @@ index 0000000..f414002
+ bool getValue(SCCOL nCol);
+ bool getRangeData(SCCOL nCol, RangeData& rData);
+ void removeSegment(SCCOL nCol1, SCCOL nCol2);
++ void insertSegment(SCCOL nCol, SCCOL nSize, bool bSkipStartBoundary);
+
+private:
+ ::std::auto_ptr<ScFlatBoolSegmentsImpl> mpImpl;
@@ -1096,10 +1197,10 @@ index c631bb4..5fbec41 100644
NOOPTFILES= \
diff --git sc/source/core/data/segmenttree.cxx sc/source/core/data/segmenttree.cxx
new file mode 100644
-index 0000000..b534de1
+index 0000000..be8e408
--- /dev/null
+++ sc/source/core/data/segmenttree.cxx
-@@ -0,0 +1,209 @@
+@@ -0,0 +1,225 @@
+/*************************************************************************
+ *
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
@@ -1155,6 +1256,7 @@ index 0000000..b534de1
+ bool getValue(SCCOLROW nPos);
+ bool getRangeData(SCCOLROW nPos, RangeData& rData);
+ void removeSegment(SCCOLROW nPos1, SCCOLROW nPos2);
++ void insertSegment(SCCOLROW nPos, SCCOLROW nSize, bool bSkipStartBoundary);
+
+private:
+ ScFlatBoolSegmentsImpl();
@@ -1224,6 +1326,11 @@ index 0000000..b534de1
+ maSegments.shift_segment_left(nPos1, nPos2);
+}
+
++void ScFlatBoolSegmentsImpl::insertSegment(SCCOLROW nPos, SCCOLROW nSize, bool bSkipStartBoundary)
++{
++ maSegments.shift_segment_right(nPos, nSize, bSkipStartBoundary);
++}
++
+// ============================================================================
+
+ScFlatBoolRowSegments::ScFlatBoolRowSegments() :
@@ -1267,6 +1374,11 @@ index 0000000..b534de1
+ mpImpl->removeSegment(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2));
+}
+
++void ScFlatBoolRowSegments::insertSegment(SCROW nRow, SCROW nSize, bool bSkipStartBoundary)
++{
++ mpImpl->insertSegment(static_cast<SCCOLROW>(nRow), static_cast<SCCOLROW>(nSize), bSkipStartBoundary);
++}
++
+// ============================================================================
+
+ScFlatBoolColSegments::ScFlatBoolColSegments() :
@@ -1307,5 +1419,11 @@ index 0000000..b534de1
+
+void ScFlatBoolColSegments::removeSegment(SCCOL nCol1, SCCOL nCol2)
+{
-+ mpImpl->removeSegment(static_cast<SCCOLROW>(nCol1), static_cast<SCCOLROW>(nCol1));
++ mpImpl->removeSegment(static_cast<SCCOLROW>(nCol1), static_cast<SCCOLROW>(nCol2));
++}
++
++void ScFlatBoolColSegments::insertSegment(SCCOL nCol, SCCOL nSize, bool bSkipStartBoundary)
++{
++ mpImpl->insertSegment(static_cast<SCCOLROW>(nCol), static_cast<SCCOLROW>(nSize), bSkipStartBoundary);
+}
+
diff --git a/patches/dev300/calc-perf-table-hidden-flags.diff b/patches/dev300/calc-perf-table-hidden-flags.diff
index 5bfd8f4..656161c 100644
--- a/patches/dev300/calc-perf-table-hidden-flags.diff
+++ b/patches/dev300/calc-perf-table-hidden-flags.diff
@@ -1016,6 +1016,16 @@ diff --git sc/source/core/data/table2.cxx sc/source/core/data/table2.cxx
index 151e3d7..2220604 100644
--- sc/source/core/data/table2.cxx
+++ sc/source/core/data/table2.cxx
+@@ -131,6 +131,9 @@ void ScTable::InsertRow( SCCOL nStartCol, SCCOL nEndCol, SCROW nStartRow, SCSIZE
+ }
+ if (pOutlineTable)
+ pOutlineTable->InsertRow( nStartRow, nSize );
++
++ mpFilteredRows->insertSegment(nStartRow, nSize, true);
++ mpHiddenRows->insertSegment(nStartRow, nSize, true);
+ }
+
+ for (SCCOL j=nStartCol; j<=nEndCol; j++)
@@ -157,6 +157,9 @@ void ScTable::DeleteRow( SCCOL nStartCol, SCCOL nEndCol, SCROW nStartRow, SCSIZE
if (pOutlineTable->DeleteRow( nStartRow, nSize ))
if (pUndoOutline)
@@ -1026,6 +1036,26 @@ index 151e3d7..2220604 100644
}
{ // scope for bulk broadcast
+@@ -205,6 +208,9 @@ void ScTable::InsertCol( SCCOL nStartCol, SCROW nStartRow, SCROW nEndRow, SCSIZE
+ }
+ if (pOutlineTable)
+ pOutlineTable->InsertCol( nStartCol, nSize );
++
++ mpHiddenCols->insertSegment(nStartCol, nSize, true);
++ mpFilteredCols->insertSegment(nStartCol, nSize, true);
+ }
+
+
+@@ -259,6 +265,9 @@ void ScTable::DeleteCol( SCCOL nStartCol, SCROW nStartRow, SCROW nEndRow, SCSIZE
+ if (pOutlineTable->DeleteCol( nStartCol, nSize ))
+ if (pUndoOutline)
+ *pUndoOutline = TRUE;
++
++ mpHiddenCols->removeSegment(nStartCol, nStartCol+nSize);
++ mpFilteredCols->removeSegment(nStartCol, nStartCol+nSize);
+ }
+
+
@@ -353,20 +353,21 @@ void ScTable::CopyToClip(SCCOL nCol1, SCROW nRow1, SCCOL nCol2, SCROW nRow2,
// copy widths/heights, and only "hidden", "filtered" and "manual" flags
// also for all preceding columns/rows, to have valid positions for drawing objects
More information about the ooo-build-commit
mailing list