[PPL-devel] [GIT] ppl/ppl(sparse_matrices): CO_Tree: improve code in rebalance().

[Marco Poletti]

Module: ppl/ppl
Branch: sparse_matrices
Commit: 99b6226ff57e3df6e82f71ed0e0b4f2b1733453e
URL:    http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=99b6226ff57e3df6e82f71ed0e0b4f2b1733453e

Author: Marco Poletti <poletti.marco at gmail.com>
Date:   Thu Aug 26 09:41:26 2010 +0200

CO_Tree: improve code in rebalance().

---

 src/CO_Tree.cc |   31 +++++++++++--------------------
 1 files changed, 11 insertions(+), 20 deletions(-)

diff --git a/src/CO_Tree.cc b/src/CO_Tree.cc
index e9a70bc..d4b9123 100644
--- a/src/CO_Tree.cc
+++ b/src/CO_Tree.cc
@@ -739,6 +739,14 @@ PPL::CO_Tree::rebuild_bigger_tree() {
 PPL::CO_Tree::tree_iterator
 PPL::CO_Tree::rebalance(tree_iterator itr, dimension_type key,
                         const data_type& value) {
+  // Trees with reserved size 3 need not to be rebalanced.
+  // This check is needed because they can't be shrunk, so they may violate the
+  // density thresholds, and this would prevent the following while from working
+  // correctly.
+  if (reserved_size == 3) {
+    PPL_ASSERT(OK());
+    return tree_iterator(*this);
+  }
   PPL_ASSERT(itr->first == unused_index || itr.is_leaf());
   height_t itr_depth_minus_1 = itr.depth() - 1;
   height_t height = max_depth - itr_depth_minus_1;
@@ -760,26 +768,9 @@ PPL::CO_Tree::rebalance(tree_iterator itr, dimension_type key,
                                min_density_percent - itr_depth_minus_1
                                *(min_density_percent - min_leaf_density_percent)
                                /(max_depth - 1))) {
-    if (itr_depth_minus_1 == 0) {
-      // TODO: Check if this is correct
-      // We may arrive here, because we are using a fake subtree_size (it
-      // isn't the real tree size, because the inserted/deleted element is
-      // already taken into account).
-#ifndef NDEBUG
-      dimension_type real_subtree_size = subtree_size;
-      if (!deleting)
-        --real_subtree_size;
-      PPL_ASSERT(!is_greater_than_ratio(real_subtree_size,
-                                        subtree_reserved_size,
-                                        max_density_percent));
-      if (is_greater_than_ratio(real_subtree_size, subtree_reserved_size,
-                                min_density_percent))
-        PPL_ASSERT(is_greater_than_ratio(real_subtree_size,
-                                         subtree_reserved_size/2,
-                                         max_density_percent));
-#endif
-      break;
-    }
+    // The density in the tree is correct, so the while condition is always
+    // false for the root.
+    PPL_ASSERT(itr_depth_minus_1 != 0);
     bool is_right_brother = itr.is_right_child();
     itr.get_parent();
     if (is_right_brother)