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

Author: Marco Poletti poletti.marco@gmail.com Date: Fri May 7 17:00:04 2010 +0200

CO_Tree: use the first element of indexes[] as a marker, speeding up some iterator operations.

---

src/CO_Tree.cc | 4 +++- src/CO_Tree.defs.hh | 5 ++--- src/CO_Tree.inlines.hh | 16 ++++++++++------ 3 files changed, 15 insertions(+), 10 deletions(-)

diff --git a/src/CO_Tree.cc b/src/CO_Tree.cc index fc73bf9..292a7be 100644 --- a/src/CO_Tree.cc +++ b/src/CO_Tree.cc @@ -189,7 +189,8 @@ PPL::CO_Tree::init(dimension_type reserved_size1) { for (dimension_type i = 1; i <= reserved_size; ++i) new (&(indexes[i])) dimension_type(unused_index);

- // This is used as a marker by unordered iterators. + // These are used as markers by iterators. + new (&(indexes[0])) dimension_type(0); new (&(indexes[reserved_size + 1])) dimension_type(0);

max_depth = l; @@ -212,6 +213,7 @@ PPL::CO_Tree::destroy() { data[i].~data_type(); indexes[i].~dimension_type(); } + indexes[0].~dimension_type(); indexes[reserved_size + 1].~dimension_type();

// We use malloc()/free() instead of operator new()/operator delete() diff --git a/src/CO_Tree.defs.hh b/src/CO_Tree.defs.hh index b81e6a8..79c7421 100644 --- a/src/CO_Tree.defs.hh +++ b/src/CO_Tree.defs.hh @@ -408,11 +408,10 @@ private: //! The depth of the leaves in the static tree. dimension_type max_depth;

- // TODO: don't waste the first element. //! The vector that contains the keys in the tree. //! If a pair has \p unused_index as first element, it means it is not used. - //! Its size is reserved_size + 2, because the first element is not used, - //! and the last element is used as marker for unordered iterators. + //! Its size is reserved_size + 2, because the first and the last elements + //! are used as markers for iterators. dimension_type* indexes;

//! The vector that contains the data of the keys in the tree. diff --git a/src/CO_Tree.inlines.hh b/src/CO_Tree.inlines.hh index 59e3dcf..8de94c1 100644 --- a/src/CO_Tree.inlines.hh +++ b/src/CO_Tree.inlines.hh @@ -419,10 +419,12 @@ CO_Tree::rebuild_bigger_tree() { new (&(new_indexes[j])) dimension_type(unused_index); }

- // This was used as a marker by unordered iterators. + // These were used as markers by iterators. + indexes[0].~dimension_type(); indexes[reserved_size + 1].~dimension_type();

- // This is used as a marker by unordered iterators. + // These are used as markers by iterators. + new (&(new_indexes[0])) dimension_type(0); new (&(new_indexes[new_reserved_size + 1])) dimension_type(0);

free(indexes); @@ -1094,8 +1096,9 @@ CO_Tree::inorder_iterator::get_previous_value() {

#ifdef USE_PPL_CO_TREE_DFS_LAYOUT --i; - while (i != 0 && tree->indexes[i] == unused_index) - --i; + if (!tree->empty()) + while (tree->indexes[i] == unused_index) + --i; #endif // defined(USE_PPL_CO_TREE_DFS_LAYOUT) }

@@ -1743,8 +1746,9 @@ CO_Tree::inorder_const_iterator::get_previous_value() {

#ifdef USE_PPL_CO_TREE_DFS_LAYOUT --i; - while (i != 0 && tree->indexes[i] == unused_index) - --i; + if (!tree->empty()) + while (tree->indexes[i] == unused_index) + --i; #endif // defined(USE_PPL_CO_TREE_DFS_LAYOUT) }