[ooo-build-commit] patches/dev300
Kohei Yoshida
kohei at kemper.freedesktop.org
Tue Jun 30 08:34:10 PDT 2009
patches/dev300/calc-perf-flat-segment-tree.diff | 493 +++++++++++++++---------
1 file changed, 323 insertions(+), 170 deletions(-)
New commits:
commit d162bd277d9959ebf941de43f0e44c362e5ac9c0
Author: Kohei Yoshida <kyoshida at novell.com>
Date: Tue Jun 30 11:33:03 2009 -0400
Revert "Updated flat segment tree header files from the latest revision."
I accidentally removed legitimate header files with that commit.
This reverts commit 31cd80f0ae4863859829b9c3123a5e0260de5750.
diff --git a/patches/dev300/calc-perf-flat-segment-tree.diff b/patches/dev300/calc-perf-flat-segment-tree.diff
index f6e4bd1..97c7e4e 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..59d1e0c
--- /dev/null
+++ sc/inc/mdds/flatsegmenttree.hxx
-@@ -0,0 +1,662 @@
+@@ -0,0 +1,509 @@
+/*************************************************************************
+ *
+ * Copyright (c) 2008-2009 Kohei Yoshida
@@ -39,10 +39,6 @@ index 0000000..d5ab674
+
+#include "node.hxx"
+
-+#ifdef UNIT_TEST
-+#include <vector>
-+#endif
-+
+namespace mdds {
+
+template<typename _Key, typename _Value>
@@ -314,73 +310,6 @@ index 0000000..d5ab674
+ m_valid_tree = false;
+ }
+
-+ /**
-+ * 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.
-+ *
-+ * @param start start value of the segment being removed.
-+ * @param end end value of the segment being removed.
-+ */
-+ void shift_segment_left(key_type start, key_type end)
-+ {
-+ if (start >= end)
-+ return;
-+
-+ node_base_ptr node_pos;
-+ if (get_node(m_left_leaf)->value_leaf.key == start)
-+ 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, m_left_leaf->right);
-+
-+ if (!node_pos)
-+ return;
-+
-+ key_type segment_size = end - start;
-+
-+ if (end < 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(node_pos, m_right_leaf, 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;
-+ 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)
-+ {
-+ 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(node_pos, m_right_leaf, segment_size);
-+ m_valid_tree = false;
-+ }
-+
+ bool search(key_type key, value_type& value, key_type* start = NULL, key_type* end = NULL) const
+ {
+ if (key < get_node(m_left_leaf)->value_leaf.key || get_node(m_right_leaf)->value_leaf.key <= key)
@@ -512,20 +441,14 @@ index 0000000..d5ab674
+ return m_valid_tree;
+ }
+
-+#ifdef UNIT_TEST
+ void dump_tree() const
+ {
+ using ::std::cout;
+ using ::std::endl;
+
-+ if (!m_valid_tree)
-+ assert(!"attempted to dump an invalid tree!");
++ ::mdds::dump_tree(m_root_node);
+
-+ size_t node_count = ::mdds::dump_tree(m_root_node);
-+ size_t node_instance_count = node_base::get_instance_count();
-+
-+ cout << "tree node count = " << node_count << " node instance count = " << node_instance_count << endl;
-+ assert(node_count == node_instance_count);
++ cout << endl << " node instance count = " << node_base::get_instance_count() << endl;
+ }
+
+ void dump_leaf_nodes() const
@@ -547,71 +470,6 @@ index 0000000..d5ab674
+ cout << endl << " node instance count = " << node_base::get_instance_count() << endl;
+ }
+
-+ /**
-+ * Verify keys in the leaf nodes.
-+ *
-+ * @param key_values vector containing key values in the left-to-right
-+ * order, including the key value of the rightmost leaf
-+ * node.
-+ */
-+ bool verify_keys(const ::std::vector<key_type>& key_values) const
-+ {
-+ node* cur_node = get_node(m_left_leaf);
-+ typename ::std::vector<key_type>::const_iterator itr = key_values.begin(), itr_end = key_values.end();
-+ for (; itr != itr_end; ++itr)
-+ {
-+ if (!cur_node)
-+ // Position past the right-mode node. Invalid.
-+ return false;
-+
-+ if (cur_node->value_leaf.key != *itr)
-+ // Key values differ.
-+ return false;
-+
-+ cur_node = get_node(cur_node->right);
-+ }
-+
-+ if (cur_node)
-+ // At this point, we expect the current node to be at the position
-+ // past the right-most node, which is NULL.
-+ return false;
-+
-+ return true;
-+ }
-+
-+ /**
-+ * Verify values in the leaf nodes.
-+ *
-+ * @param values vector containing values to verify against, in the
-+ * left-to-right order, <i>not</i> including the value of
-+ * the rightmost leaf node.
-+ */
-+ bool verify_values(const ::std::vector<value_type>& values) const
-+ {
-+ node* cur_node = get_node(m_left_leaf);
-+ node* end_node = get_node(m_right_leaf);
-+ typename ::std::vector<value_type>::const_iterator itr = values.begin(), itr_end = values.end();
-+ for (; itr != itr_end; ++itr)
-+ {
-+ if (cur_node == end_node || !cur_node)
-+ return false;
-+
-+ if (cur_node->value_leaf.value != *itr)
-+ // Key values differ.
-+ return false;
-+
-+ cur_node = get_node(cur_node->right);
-+ }
-+
-+ if (cur_node != end_node)
-+ // At this point, we expect the current node to be at the end of
-+ // range.
-+ return false;
-+
-+ return true;
-+ }
-+#endif
-+
+private:
+ flat_segment_tree();
+
@@ -645,17 +503,6 @@ index 0000000..d5ab674
+ return NULL;
+ }
+
-+ void shift_leaf_key(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);
-+ while (cur_node_p != end_node_p)
-+ {
-+ cur_node_p->value_leaf.key -= shift_value;
-+ cur_node_p = get_node(cur_node_p->right);
-+ }
-+ }
-+
+private:
+ node_base_ptr m_root_node;
+ node_base_ptr m_left_leaf;
@@ -668,10 +515,10 @@ index 0000000..d5ab674
+#endif
diff --git sc/inc/mdds/node.hxx sc/inc/mdds/node.hxx
new file mode 100644
-index 0000000..59749a0
+index 0000000..8975c86
--- /dev/null
+++ sc/inc/mdds/node.hxx
-@@ -0,0 +1,307 @@
+@@ -0,0 +1,301 @@
+/*************************************************************************
+ *
+ * Copyright (c) 2008-2009 Kohei Yoshida
@@ -918,17 +765,14 @@ index 0000000..59749a0
+ return build_tree_non_leaf(new_node_list);
+}
+
-+#ifdef UNIT_TEST
+template<typename _NodePtr>
-+size_t dump_tree_layer(const ::std::list<_NodePtr>& node_list, unsigned int level)
++void dump_tree_layer(const ::std::list<_NodePtr>& node_list, unsigned int level)
+{
+ using ::std::cout;
+ using ::std::endl;
+
+ if (node_list.empty())
-+ return 0;
-+
-+ size_t node_count = node_list.size();
++ return;
+
+ bool isLeaf = node_list.front()->is_leaf;
+ cout << "level " << level << " (" << (isLeaf?"leaf":"non-leaf") << ")" << endl;
@@ -959,23 +803,332 @@ index 0000000..59749a0
+ cout << endl;
+
+ if (!newList.empty())
-+ node_count += dump_tree_layer(newList, level+1);
-+
-+ return node_count;
++ dump_tree_layer(newList, level+1);
+}
+
+template<typename _NodePtr>
-+size_t dump_tree(const _NodePtr& root_node)
++void dump_tree(const _NodePtr& root_node)
+{
+ if (!root_node)
-+ return 0;
++ return;
+
+ ::std::list<_NodePtr> node_list;
+ node_list.push_back(root_node);
-+ return dump_tree_layer(node_list, 0);
++ dump_tree_layer(node_list, 0);
+}
++
++}
++
++#endif
+diff --git sc/inc/segmenttree.hxx sc/inc/segmenttree.hxx
+new file mode 100644
+index 0000000..f414002
+--- /dev/null
++++ sc/inc/segmenttree.hxx
+@@ -0,0 +1,85 @@
++/*************************************************************************
++ *
++ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
++ *
++ * Copyright 2008 by Sun Microsystems, Inc.
++ *
++ * OpenOffice.org - a multi-platform office productivity suite
++ *
++ * $RCSfile: compressedarray.hxx,v $
++ * $Revision: 1.7.32.2 $
++ *
++ * This file is part of OpenOffice.org.
++ *
++ * OpenOffice.org is free software: you can redistribute it and/or modify
++ * it under the terms of the GNU Lesser General Public License version 3
++ * only, as published by the Free Software Foundation.
++ *
++ * OpenOffice.org is distributed in the hope that it will be useful,
++ * but WITHOUT ANY WARRANTY; without even the implied warranty of
++ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
++ * GNU Lesser General Public License version 3 for more details
++ * (a copy is included in the LICENSE file that accompanied this code).
++ *
++ * You should have received a copy of the GNU Lesser General Public License
++ * version 3 along with OpenOffice.org. If not, see
++ * <http://www.openoffice.org/license.html>
++ * for a copy of the LGPLv3 License.
++ *
++ ************************************************************************/
++
++#ifndef SC_SEGMENTTREE_HXX
++#define SC_SEGMENTTREE_HXX
++
++#include "address.hxx"
++
++#include <memory>
++
++class ScFlatBoolSegmentsImpl;
++
++class ScFlatBoolRowSegments
++{
++public:
++ struct RangeData
++ {
++ SCROW mnRow1;
++ SCROW mnRow2;
++ bool mbValue;
++ };
++ ScFlatBoolRowSegments();
++ ~ScFlatBoolRowSegments();
++
++ void setTrue(SCROW nRow1, SCROW nRow2);
++ void setFalse(SCROW nRow1, SCROW nRow2);
++ bool getValue(SCROW nRow);
++ bool getRangeData(SCROW nRow, RangeData& rData);
++
++private:
++ ::std::auto_ptr<ScFlatBoolSegmentsImpl> mpImpl;
++};
++
++// ============================================================================
++
++class ScFlatBoolColSegments
++{
++public:
++ struct RangeData
++ {
++ SCCOL mnCol1;
++ SCCOL mnCol2;
++ bool mbValue;
++ };
++ ScFlatBoolColSegments();
++ ~ScFlatBoolColSegments();
++
++ void setTrue(SCCOL nCol1, SCCOL nCol2);
++ void setFalse(SCCOL nCol1, SCCOL nCol2);
++ bool getValue(SCCOL nCol);
++ bool getRangeData(SCCOL nCol, RangeData& rData);
++
++private:
++ ::std::auto_ptr<ScFlatBoolSegmentsImpl> mpImpl;
++};
++
++
+#endif
+diff --git sc/source/core/data/makefile.mk sc/source/core/data/makefile.mk
+index c631bb4..5fbec41 100644
+--- sc/source/core/data/makefile.mk
++++ sc/source/core/data/makefile.mk
+@@ -102,6 +102,7 @@ SLOFILES = \
+ $(SLO)$/phonetic.obj \
+ $(SLO)$/poolhelp.obj \
+ $(SLO)$/scimpexpmsg.obj \
++ $(SLO)$/segmenttree.obj \
+ $(SLO)$/sortparam.obj \
+ $(SLO)$/stlpool.obj \
+ $(SLO)$/stlsheet.obj \
+@@ -147,7 +148,8 @@ EXCEPTIONSFILES= \
+ $(SLO)$/dbdocutl.obj \
+ $(SLO)$/dptabsrc.obj \
+ $(SLO)$/drwlayer.obj \
+- $(SLO)$/globalx.obj
++ $(SLO)$/globalx.obj \
++ $(SLO)$/segmenttree.obj
+
+ .IF "$(OS)$(COM)$(CPUNAME)"=="LINUXGCCSPARC"
+ NOOPTFILES= \
+diff --git sc/source/core/data/segmenttree.cxx sc/source/core/data/segmenttree.cxx
+new file mode 100644
+index 0000000..b534de1
+--- /dev/null
++++ sc/source/core/data/segmenttree.cxx
+@@ -0,0 +1,193 @@
++/*************************************************************************
++ *
++ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
++ *
++ * Copyright 2008 by Sun Microsystems, Inc.
++ *
++ * OpenOffice.org - a multi-platform office productivity suite
++ *
++ * $RCSfile: compressedarray.hxx,v $
++ * $Revision: 1.7.32.2 $
++ *
++ * This file is part of OpenOffice.org.
++ *
++ * OpenOffice.org is free software: you can redistribute it and/or modify
++ * it under the terms of the GNU Lesser General Public License version 3
++ * only, as published by the Free Software Foundation.
++ *
++ * OpenOffice.org is distributed in the hope that it will be useful,
++ * but WITHOUT ANY WARRANTY; without even the implied warranty of
++ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
++ * GNU Lesser General Public License version 3 for more details
++ * (a copy is included in the LICENSE file that accompanied this code).
++ *
++ * You should have received a copy of the GNU Lesser General Public License
++ * version 3 along with OpenOffice.org. If not, see
++ * <http://www.openoffice.org/license.html>
++ * for a copy of the LGPLv3 License.
++ *
++ ************************************************************************/
++
++// MARKER(update_precomp.py): autogen include statement, do not remove
++#include "precompiled_sc.hxx"
+
++#include "segmenttree.hxx"
++#include "mdds/flatsegmenttree.hxx"
++
++#define USE_TREE_SEARCH 1
++
++class ScFlatBoolSegmentsImpl
++{
++public:
++ struct RangeData
++ {
++ SCCOLROW mnPos1;
++ SCCOLROW mnPos2;
++ bool mbValue;
++ };
++ ScFlatBoolSegmentsImpl(SCCOLROW nMax);
++ ~ScFlatBoolSegmentsImpl();
++
++ void setTrue(SCCOLROW nPos1, SCCOLROW nPos2);
++ void setFalse(SCCOLROW nPos1, SCCOLROW nPos2);
++ bool getValue(SCCOLROW nPos);
++ bool getRangeData(SCCOLROW nPos, RangeData& rData);
++
++private:
++ ScFlatBoolSegmentsImpl();
++ ScFlatBoolSegmentsImpl(const ScFlatBoolSegmentsImpl&);
++
++ ::mdds::flat_segment_tree<SCCOLROW, bool> maSegments;
++};
++
++ScFlatBoolSegmentsImpl::ScFlatBoolSegmentsImpl(SCCOLROW nMax) :
++ maSegments(0, nMax+1, false)
++{
+}
+
++ScFlatBoolSegmentsImpl::~ScFlatBoolSegmentsImpl()
++{
++}
++
++void ScFlatBoolSegmentsImpl::setTrue(SCCOLROW nPos1, SCCOLROW nPos2)
++{
++ maSegments.insert_segment(nPos1, nPos2+1, true);
++}
++
++void ScFlatBoolSegmentsImpl::setFalse(SCCOLROW nPos1, SCCOLROW nPos2)
++{
++ maSegments.insert_segment(nPos1, nPos2+1, false);
++}
++
++bool ScFlatBoolSegmentsImpl::getValue(SCCOLROW nPos)
++{
++ bool bValue = false;
++#if USE_TREE_SEARCH
++ if (!maSegments.is_tree_valid())
++ maSegments.build_tree();
++
++ maSegments.search_tree(nPos, bValue);
++#else
++ maSegments.search(nPos, bValue);
+#endif
++ return bValue;
++}
++
++bool ScFlatBoolSegmentsImpl::getRangeData(SCCOLROW nPos, RangeData& rData)
++{
++#if USE_TREE_SEARCH
++ if (!maSegments.is_tree_valid())
++ maSegments.build_tree();
++#endif
++
++ bool bValue;
++ SCCOLROW nPos1, nPos2;
++#if USE_TREE_SEARCH
++ if (!maSegments.search_tree(nPos, bValue, &nPos1, &nPos2))
++ return false;
++#else
++ if (!maSegments.search(nPos, bValue, &nPos1, &nPos2))
++ return false;
++#endif
++
++ rData.mnPos1 = nPos1;
++ rData.mnPos2 = nPos2-1; // end point is not inclusive.
++ rData.mbValue = bValue;
++ return true;
++}
++
++// ============================================================================
++
++ScFlatBoolRowSegments::ScFlatBoolRowSegments() :
++ mpImpl(new ScFlatBoolSegmentsImpl(static_cast<SCCOLROW>(MAXROW)))
++{
++}
++
++ScFlatBoolRowSegments::~ScFlatBoolRowSegments()
++{
++}
++
++void ScFlatBoolRowSegments::setTrue(SCROW nRow1, SCROW nRow2)
++{
++ mpImpl->setTrue(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2));
++}
++
++void ScFlatBoolRowSegments::setFalse(SCROW nRow1, SCROW nRow2)
++{
++ mpImpl->setFalse(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2));
++}
++
++bool ScFlatBoolRowSegments::getValue(SCROW nRow)
++{
++ return mpImpl->getValue(static_cast<SCCOLROW>(nRow));
++}
++
++bool ScFlatBoolRowSegments::getRangeData(SCROW nRow, RangeData& rData)
++{
++ ScFlatBoolSegmentsImpl::RangeData aData;
++ if (!mpImpl->getRangeData(static_cast<SCCOLROW>(nRow), aData))
++ return false;
++
++ rData.mbValue = aData.mbValue;
++ rData.mnRow1 = static_cast<SCROW>(aData.mnPos1);
++ rData.mnRow2 = static_cast<SCROW>(aData.mnPos2);
++ return true;
++}
++
++// ============================================================================
++
++ScFlatBoolColSegments::ScFlatBoolColSegments() :
++ mpImpl(new ScFlatBoolSegmentsImpl(static_cast<SCCOLROW>(MAXCOL)))
++{
++}
++
++ScFlatBoolColSegments::~ScFlatBoolColSegments()
++{
++}
++
++void ScFlatBoolColSegments::setTrue(SCCOL nCol1, SCCOL nCol2)
++{
++ mpImpl->setTrue(static_cast<SCCOLROW>(nCol1), static_cast<SCCOLROW>(nCol2));
++}
++
++void ScFlatBoolColSegments::setFalse(SCCOL nCol1, SCCOL nCol2)
++{
++ mpImpl->setFalse(static_cast<SCCOLROW>(nCol1), static_cast<SCCOLROW>(nCol2));
++}
++
++bool ScFlatBoolColSegments::getValue(SCCOL nCol)
++{
++ return mpImpl->getValue(static_cast<SCCOLROW>(nCol));
++}
++
++bool ScFlatBoolColSegments::getRangeData(SCCOL nCol, RangeData& rData)
++{
++ ScFlatBoolSegmentsImpl::RangeData aData;
++ if (!mpImpl->getRangeData(static_cast<SCCOLROW>(nCol), aData))
++ return false;
++
++ rData.mbValue = aData.mbValue;
++ rData.mnCol1 = static_cast<SCCOL>(aData.mnPos1);
++ rData.mnCol2 = static_cast<SCCOL>(aData.mnPos2);
++ return true;
++}
More information about the ooo-build-commit
mailing list