[PPL-devel] [GIT] ppl/ppl(sparse_matrices): CO_Tree: construct Coefficient objects only when needed.
Marco Poletti
poletti.marco at gmail.com
Tue Apr 13 22:36:02 CEST 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=0ff013e62483a62c87273baaee583086175a020f
Author: Marco Poletti <poletti.marco at 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
More information about the PPL-devel
mailing list