[ooo-build-commit] patches/dev300
Kohei Yoshida
kohei at kemper.freedesktop.org
Tue Jun 30 08:47:39 PDT 2009
patches/dev300/calc-perf-flat-segment-tree.diff | 183 ++++++++++++++++++++++--
1 file changed, 171 insertions(+), 12 deletions(-)
New commits:
commit 62463d8213185b834555ef6649801d1703e7d51f
Author: Kohei Yoshida <kyoshida at novell.com>
Date: Tue Jun 30 11:46:53 2009 -0400
Updated flat segment tree header files from the latest revision.
Take 2 -- the correct version.
* 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..8871733 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,19 +959,22 @@ 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
+
+}
+
More information about the ooo-build-commit
mailing list