[ooo-build-commit] patches/dev300
Kohei Yoshida
kohei at kemper.freedesktop.org
Tue Jun 30 08:28:30 PDT 2009
patches/dev300/calc-perf-flat-segment-tree.diff | 493 ++++++++----------------
1 file changed, 170 insertions(+), 323 deletions(-)
New commits:
commit 31cd80f0ae4863859829b9c3123a5e0260de5750
Author: Kohei Yoshida <kyoshida at novell.com>
Date: Tue Jun 30 11:27:33 2009 -0400
Updated flat segment tree header files from the latest revision.
* patches/dev300/calc-perf-flat-segment-tree.diff:
diff --git a/patches/dev300/calc-perf-flat-segment-tree.diff b/patches/dev300/calc-perf-flat-segment-tree.diff
index 97c7e4e..f6e4bd1 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..59d1e0c
+index 0000000..d5ab674
--- /dev/null
+++ sc/inc/mdds/flatsegmenttree.hxx
-@@ -0,0 +1,509 @@
+@@ -0,0 +1,662 @@
+/*************************************************************************
+ *
+ * Copyright (c) 2008-2009 Kohei Yoshida
@@ -39,6 +39,10 @@ index 0000000..59d1e0c
+
+#include "node.hxx"
+
++#ifdef UNIT_TEST
++#include <vector>
++#endif
++
+namespace mdds {
+
+template<typename _Key, typename _Value>
@@ -310,6 +314,73 @@ index 0000000..59d1e0c
+ 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)
@@ -441,14 +512,20 @@ index 0000000..59d1e0c
+ return m_valid_tree;
+ }
+
++#ifdef UNIT_TEST
+ void dump_tree() const
+ {
+ using ::std::cout;
+ using ::std::endl;
+
-+ ::mdds::dump_tree(m_root_node);
++ if (!m_valid_tree)
++ assert(!"attempted to dump an invalid tree!");
+
-+ cout << endl << " node instance count = " << node_base::get_instance_count() << endl;
++ 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);
+ }
+
+ void dump_leaf_nodes() const
@@ -470,6 +547,71 @@ index 0000000..59d1e0c
+ 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();
+
@@ -503,6 +645,17 @@ index 0000000..59d1e0c
+ 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;
@@ -515,10 +668,10 @@ index 0000000..59d1e0c
+#endif
diff --git sc/inc/mdds/node.hxx sc/inc/mdds/node.hxx
new file mode 100644
-index 0000000..8975c86
+index 0000000..59749a0
--- /dev/null
+++ sc/inc/mdds/node.hxx
-@@ -0,0 +1,301 @@
+@@ -0,0 +1,307 @@
+/*************************************************************************
+ *
+ * Copyright (c) 2008-2009 Kohei Yoshida
@@ -765,14 +918,17 @@ index 0000000..8975c86
+ return build_tree_non_leaf(new_node_list);
+}
+
++#ifdef UNIT_TEST
+template<typename _NodePtr>
-+void dump_tree_layer(const ::std::list<_NodePtr>& node_list, unsigned int level)
++size_t dump_tree_layer(const ::std::list<_NodePtr>& node_list, unsigned int level)
+{
+ using ::std::cout;
+ using ::std::endl;
+
+ if (node_list.empty())
-+ return;
++ return 0;
++
++ size_t node_count = node_list.size();
+
+ bool isLeaf = node_list.front()->is_leaf;
+ cout << "level " << level << " (" << (isLeaf?"leaf":"non-leaf") << ")" << endl;
@@ -803,332 +959,23 @@ index 0000000..8975c86
+ cout << endl;
+
+ if (!newList.empty())
-+ dump_tree_layer(newList, level+1);
++ node_count += dump_tree_layer(newList, level+1);
++
++ return node_count;
+}
+
+template<typename _NodePtr>
-+void dump_tree(const _NodePtr& root_node)
++size_t dump_tree(const _NodePtr& root_node)
+{
+ if (!root_node)
-+ return;
++ return 0;
+
+ ::std::list<_NodePtr> node_list;
+ node_list.push_back(root_node);
-+ dump_tree_layer(node_list, 0);
++ return 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