[PPL-devel] [GIT] ppl/ppl(sparse_matrices): CO_Tree: use the first element of indexes[] as a marker, speeding up some iterator operations.

[Marco Poletti]

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

Author: Marco Poletti <poletti.marco at 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)
 }