[PPL-devel] [GIT] ppl/ppl(sparse_matrices): CO_Tree: optimize go_down_searching_key() for the DFS layout.

[Marco Poletti]

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

Author: Marco Poletti <poletti.marco at gmail.com>
Date:   Sat May  8 18:35:00 2010 +0200

CO_Tree: optimize go_down_searching_key() for the DFS layout.

---

 src/CO_Tree.defs.hh    |    6 +--
 src/CO_Tree.inlines.hh |  132 ++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 134 insertions(+), 4 deletions(-)

diff --git a/src/CO_Tree.defs.hh b/src/CO_Tree.defs.hh
index 21fcd1e..c185103 100644
--- a/src/CO_Tree.defs.hh
+++ b/src/CO_Tree.defs.hh
@@ -583,8 +583,7 @@ private:
   //! The tree the iterator points to.
   const CO_Tree* tree;
 
-  friend dimension_type
-    CO_Tree::count_used_in_subtree(inorder_const_iterator& itr);
+  friend class CO_Tree;
 };
 
 class CO_Tree::inorder_iterator {
@@ -743,8 +742,7 @@ private:
   friend inorder_const_iterator&
     inorder_const_iterator::operator=(const inorder_iterator&);
 
-  friend dimension_type
-    CO_Tree::count_used_in_subtree(inorder_iterator& itr);
+  friend class CO_Tree;
 };
 
 } // namespace Parma_Polyhedra_Library
diff --git a/src/CO_Tree.inlines.hh b/src/CO_Tree.inlines.hh
index 8797d65..f91f8ac 100644
--- a/src/CO_Tree.inlines.hh
+++ b/src/CO_Tree.inlines.hh
@@ -353,7 +353,71 @@ CO_Tree::go_down_searching_key(inorder_const_iterator& itr,
 
 inline void
 CO_Tree::lower_bound(inorder_iterator& itr, dimension_type key) {
+#ifdef USE_PPL_CO_TREE_DFS_LAYOUT
+  PPL_ASSERT(!empty());
+  PPL_ASSERT(itr.is_at_end() || itr->first <= key);
+
+  if (itr.is_before_begin())
+    ++itr;
+
+  PPL_ASSERT(itr.is_at_end() || itr->first <= key);
+
+  if (itr.is_at_end())
+    return;
+
+  dimension_type low_index = itr.i;
+  dimension_type high_index = reserved_size;
+
+  PPL_ASSERT(low_index > 0);
+
+  while (low_index + 1 < high_index) {
+
+    dimension_type avg = (low_index + high_index) / 2;
+    dimension_type index = avg;
+
+    while (indexes[index] == unused_index)
+      ++index;
+
+    if (index > high_index || indexes[index] > key) {
+      high_index = avg;
+    } else {
+      low_index = index;
+    }
+  }
+
+  if (low_index == high_index) {
+    if (indexes[low_index] == unused_index || indexes[low_index] < key)
+      ++low_index;
+    while (indexes[low_index] == unused_index)
+      ++low_index;
+
+  } else {
+    PPL_ASSERT(low_index + 1 == high_index);
+    if (indexes[low_index] == unused_index || indexes[low_index] < key) {
+      ++low_index;
+      if (indexes[low_index] == unused_index || indexes[low_index] < key)
+        ++low_index;
+    }
+    while (indexes[low_index] == unused_index)
+      ++low_index;
+  }
+
+  itr.i = low_index;
+
+#ifndef NDEBUG
+  inorder_iterator itr2 = itr;
+  itr2.get_previous_value();
+  PPL_ASSERT(itr2.is_before_begin() || itr2->first < key);
+  itr2.get_next_value();
+  PPL_ASSERT(itr2 == itr);
+#endif
+
+  PPL_ASSERT(itr.is_at_end() || itr->first >= key);
+
+#else // defined(USE_PPL_CO_TREE_DFS_LAYOUT)
+
   PPL_ASSERT(!empty());
+  PPL_ASSERT(itr.is_at_end() || itr->first <= key);
   if (itr->first <= key)
     while (itr.has_parent() && itr->first < key)
       itr.get_parent();
@@ -378,11 +442,77 @@ CO_Tree::lower_bound(inorder_iterator& itr, dimension_type key) {
   itr.get_next_value();
 #endif
   PPL_ASSERT(itr.is_at_end() || itr->first >= key);
+
+#endif // defined(USE_PPL_CO_TREE_DFS_LAYOUT)
 }
 
 inline void
 CO_Tree::lower_bound(inorder_const_iterator& itr, dimension_type key) const {
+#ifdef USE_PPL_CO_TREE_DFS_LAYOUT
+  PPL_ASSERT(!empty());
+  PPL_ASSERT(itr.is_at_end() || itr->first <= key);
+
+  if (itr.is_before_begin())
+    ++itr;
+
+  PPL_ASSERT(itr.is_at_end() || itr->first <= key);
+
+  if (itr.is_at_end())
+    return;
+
+  dimension_type low_index = itr.i;
+  dimension_type high_index = reserved_size;
+
+  PPL_ASSERT(low_index > 0);
+
+  while (low_index + 1 < high_index) {
+
+    dimension_type avg = (low_index + high_index) / 2;
+    dimension_type index = avg;
+
+    while (indexes[index] == unused_index)
+      ++index;
+
+    if (index > high_index || indexes[index] > key) {
+      high_index = avg;
+    } else {
+      low_index = index;
+    }
+  }
+
+  if (low_index == high_index) {
+    if (indexes[low_index] == unused_index || indexes[low_index] < key)
+      ++low_index;
+    while (indexes[low_index] == unused_index)
+      ++low_index;
+
+  } else {
+    PPL_ASSERT(low_index + 1 == high_index);
+    if (indexes[low_index] == unused_index || indexes[low_index] < key) {
+      ++low_index;
+      if (indexes[low_index] == unused_index || indexes[low_index] < key)
+        ++low_index;
+    }
+    while (indexes[low_index] == unused_index)
+      ++low_index;
+  }
+
+  itr.i = low_index;
+
+#ifndef NDEBUG
+  inorder_const_iterator itr2 = itr;
+  itr2.get_previous_value();
+  PPL_ASSERT(itr2.is_before_begin() || itr2->first < key);
+  itr2.get_next_value();
+  PPL_ASSERT(itr2 == itr);
+#endif
+
+  PPL_ASSERT(itr.is_at_end() || itr->first >= key);
+
+#else // defined(USE_PPL_CO_TREE_DFS_LAYOUT)
+
   PPL_ASSERT(!empty());
+  PPL_ASSERT(itr.is_at_end() || itr->first <= key);
   if (itr->first <= key)
     while (itr.has_parent() && itr->first < key)
       itr.get_parent();
@@ -407,6 +537,8 @@ CO_Tree::lower_bound(inorder_const_iterator& itr, dimension_type key) const {
   itr.get_next_value();
 #endif
   PPL_ASSERT(itr.is_at_end() || itr->first >= key);
+
+#endif // defined(USE_PPL_CO_TREE_DFS_LAYOUT)
 }
 
 inline void