[GIT] ppl/ppl(sparse_matrices): CO_Tree: construct Coefficient objects only when needed.

13 Apr 2010

Module: ppl/ppl
Branch: sparse_matrices
Commit: 0ff013e62483a62c87273baaee583086175a020f
URL:    http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=0ff013e62483a...
Author: Marco Poletti poletti.marco@gmail.com
Date:   Tue Apr 13 22:28:03 2010 +0200
CO_Tree: construct Coefficient objects only when needed.
---
src/CO_Tree.cc         |   45 +++++++++++++++++++++++++++++++++------------
 src/CO_Tree.defs.hh    |    3 +++
 src/CO_Tree.inlines.hh |   27 ++++++++++-----------------
 3 files changed, 46 insertions(+), 29 deletions(-)

diff --git a/src/CO_Tree.cc b/src/CO_Tree.cc
index d39529a..a84efaf 100644
--- a/src/CO_Tree.cc
+++ b/src/CO_Tree.cc
@@ -200,8 +200,9 @@ PPL::CO_Tree::copy_data_from(const CO_Tree& x) {
     } else {
       if (top_n == 1) {
         PPL_ASSERT(root->first == unused_index);
+        PPL_ASSERT(itr->first != unused_index);
         root->first = itr->first;
-        root->second = itr->second;
+        new (&(root->second)) data_type(itr->second);
         itr.get_next_value();
         --stack_first_empty;
       } else {
@@ -247,10 +248,11 @@ PPL::CO_Tree::init(dimension_type reserved_size1) {
   l++;
reserved_size = ((dimension_type)1 << l) - 1;
-  data = new value_type[reserved_size + 1];
+  data = static_cast<value_type *>(operator new(sizeof(value_type)
+                                                *(reserved_size + 1)));
   // Mark all pairs as unused.
   for (dimension_type i = 1; i <= reserved_size; ++i)
-    data[i].first = unused_index;
+    new (&(data[i].first)) dimension_type(unused_index);
max_depth = l;
   rebuild_level_data(l);
@@ -261,6 +263,22 @@ PPL::CO_Tree::init(dimension_type reserved_size1) {
 }
void
+PPL::CO_Tree::destroy() {
+
+  if (reserved_size != 0) {
+    for (dimension_type i = 1; i <= reserved_size; ++i) {
+      if (data[i].first != unused_index)
+        data[i].second.~data_type();
+      data[i].first.~dimension_type();
+    }
+
+    operator delete(data);
+
+    delete [] level;
+  }
+}
+
+void
 PPL::CO_Tree::move_data_from(CO_Tree& tree) {
   PPL_ASSERT(size == 0);
   if (tree.size == 0)
@@ -327,7 +345,9 @@ PPL::CO_Tree::move_data_from(CO_Tree& tree) {
     } else {
       if (top_n == 1) {
         PPL_ASSERT(root->first == unused_index);
+        PPL_ASSERT(itr->first != unused_index);
         root->first = itr->first;
+        itr->first = unused_index;
         move_data_element(root->second, itr->second);
         itr.get_next_value();
         --stack_first_empty;
@@ -345,8 +365,8 @@ PPL::CO_Tree::move_data_from(CO_Tree& tree) {
     }
   }
   size = tree.size;
-  PPL_ASSERT(structure_OK());
-  PPL_ASSERT(tree.OK());
+  tree.size = 0;
+  PPL_ASSERT(tree.structure_OK());
 }
bool
@@ -480,7 +500,7 @@ PPL::CO_Tree::insert(dimension_type key1, const data_type& data1,
     itr.get_root();
     PPL_ASSERT(itr->first == unused_index);
     itr->first = key1;
-    itr->second = data1;
+    new (&(itr->second)) data_type(data1);
     size++;
PPL_ASSERT(OK());
@@ -518,7 +538,7 @@ PPL::CO_Tree::insert(dimension_type key1, const data_type& data1,
       itr.get_right_child();
     PPL_ASSERT(itr->first == unused_index);
     itr->first = key1;
-    itr->second = data1;
+    new (&(itr->second)) data_type(data1);
     size++;
} else {
@@ -612,8 +632,7 @@ PPL::CO_Tree::erase(inorder_iterator& itr) {
if (size == 1) {
     // Deleting the only element of this tree, now it is empty.
-    delete [] data;
-    delete [] level;
+    destroy();
     init(0);
     return;
   }
@@ -642,6 +661,7 @@ PPL::CO_Tree::erase(inorder_iterator& itr) {
                  > max_density);
 #endif
+  itr->second.~data_type();
   while (1) {
     dimension_type& current_key  = itr->first;
     data_type&      current_data = itr->second;
@@ -747,7 +767,7 @@ PPL::CO_Tree::redistribute_elements_in_subtree(inorder_iterator& itr,
   if (!added_key && can_add_key) {
     PPL_ASSERT(itr2->first == unused_index);
     itr2->first = key;
-    itr2->second = value;
+    new (&(itr2->second)) data_type(value);
     added_key = true;
   } else
     ++itr2;
@@ -795,7 +815,7 @@ PPL::CO_Tree
           PPL_ASSERT(!first_unused.is_before_begin());
           PPL_ASSERT(first_unused->first == unused_index);
           first_unused->first = key;
-          first_unused->second = value;
+          new (&(first_unused->second)) data_type(value);
           added_key = true;
           --first_unused;
           --subtree_size;
@@ -901,9 +921,10 @@ PPL::CO_Tree
       if (top_n == 1) {
         if (!added_key && (itr.is_at_end() || itr->first > key)) {
           PPL_ASSERT(root != itr);
+          PPL_ASSERT(root->first == unused_index);
           added_key = true;
           root->first = key;
-          root->second = value;
+          new (&(root->second)) data_type(value);
         } else {
           if (root != itr) {
             PPL_ASSERT(root->first == unused_index);
diff --git a/src/CO_Tree.defs.hh b/src/CO_Tree.defs.hh
index 10fb07e..56602f0 100644
--- a/src/CO_Tree.defs.hh
+++ b/src/CO_Tree.defs.hh
@@ -339,6 +339,9 @@ private:
   //! Initializes a tree with reserved size at least \p n .
   void init(dimension_type n);
+  //! Deallocates the tree. After this call, init() can be called again.
+  void destroy();
+
   //! Checks the invariant, but not the densities.
   bool structure_OK() const;
diff --git a/src/CO_Tree.inlines.hh b/src/CO_Tree.inlines.hh
index bfad42f..e8cd662 100644
--- a/src/CO_Tree.inlines.hh
+++ b/src/CO_Tree.inlines.hh
@@ -54,11 +54,7 @@ CO_Tree::operator=(const CO_Tree& x) {
if (this != &x) {
-    if (reserved_size != 0) {
-      delete [] data;
-      delete [] level;
-    }
-
+    destroy();
     init(x.reserved_size);
copy_data_from(x);
@@ -70,13 +66,9 @@ CO_Tree::operator=(const CO_Tree& x) {
 inline
 CO_Tree::~CO_Tree() {
-  PPL_ASSERT(OK());
-
-  if (level != NULL)
-    delete [] level;
+  PPL_ASSERT(structure_OK());
-  if (data != NULL)
-    delete [] data;
+  destroy();
 }
inline dimension_type
@@ -241,7 +233,7 @@ CO_Tree::lower_bound(inorder_const_iterator& itr, dimension_type key) const {
inline void
 CO_Tree::move_data_element(data_type& to, data_type& from) {
-  std::swap(to, from);
+  std::memcpy(&to, &from, sizeof(data_type));
 }
inline void
@@ -254,7 +246,7 @@ CO_Tree::rebuild_bigger_tree() {
     new_tree.init(new_reserved_size);
     new_tree.move_data_from(*this);
     swap(new_tree);
-    PPL_ASSERT(new_tree.OK());
+    PPL_ASSERT(new_tree.structure_OK());
   }
   PPL_ASSERT(structure_OK());
 }
@@ -262,8 +254,7 @@ CO_Tree::rebuild_bigger_tree() {
 inline void
 CO_Tree::rebuild_smaller_tree() {
   if (reserved_size == 3) {
-    delete [] data;
-    delete [] level;
+    destroy();
     init(0);
   } else {
     dimension_type new_reserved_size = reserved_size / 2;
@@ -271,7 +262,7 @@ CO_Tree::rebuild_smaller_tree() {
     new_tree.init(new_reserved_size);
     new_tree.move_data_from(*this);
     swap(new_tree);
-    PPL_ASSERT(new_tree.OK());
+    PPL_ASSERT(new_tree.structure_OK());
   }
   PPL_ASSERT(structure_OK());
 }
@@ -595,7 +586,6 @@ CO_Tree::inorder_iterator::get_next_value() {
 #ifndef NDEBUG
     const dimension_type previous_index = (*this)->first;
 #endif
-    PPL_ASSERT(previous_index != unused_index);
     if (get_right_child_value())
       while (get_left_child_value())
         ;
@@ -610,6 +600,9 @@ CO_Tree::inorder_iterator::get_next_value() {
#ifndef NDEBUG
     if (!at_end)
+      // previous_index could be unused_index because we deleted the current
+      // node, as we do in move_data_from().
+      if (previous_index != unused_index)
       PPL_ASSERT((*this)->first != unused_index
                  && (*this)->first > previous_index);
 #endif

    

Marco Poletti

tags (0)

participants (1)