[PPL-devel] [GIT] ppl/ppl(sparse_matrices): CO_Tree: use height_t instead of dimension_type for node heights and depths.
Marco Poletti
poletti.marco at gmail.com
Fri May 7 20:55:47 CEST 2010
Module: ppl/ppl
Branch: sparse_matrices
Commit: 6d75380ef8478339ba0145cae153f096f8111ff0
URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=6d75380ef8478339ba0145cae153f096f8111ff0
Author: Marco Poletti <poletti.marco at gmail.com>
Date: Fri May 7 17:32:36 2010 +0200
CO_Tree: use height_t instead of dimension_type for node heights and depths.
---
src/CO_Tree.cc | 18 +++++++++---------
src/CO_Tree.defs.hh | 20 ++++++++++----------
src/CO_Tree.inlines.hh | 14 +++++++-------
3 files changed, 26 insertions(+), 26 deletions(-)
diff --git a/src/CO_Tree.cc b/src/CO_Tree.cc
index afc2807..d33e9a1 100644
--- a/src/CO_Tree.cc
+++ b/src/CO_Tree.cc
@@ -165,7 +165,7 @@ PPL::CO_Tree::init(dimension_type reserved_size1) {
return;
}
- dimension_type l = 0;
+ height_t l = 0;
if (reserved_size1 == 0)
reserved_size1 = 1;
@@ -504,8 +504,8 @@ PPL::CO_Tree::rebalance(inorder_iterator& itr, dimension_type key,
PPL_ASSERT(!itr.get_right_child_value());
}
#endif
- dimension_type itr_depth_minus_1 = itr.depth() - 1;
- dimension_type height = max_depth - itr_depth_minus_1;
+ height_t itr_depth_minus_1 = itr.depth() - 1;
+ height_t height = max_depth - itr_depth_minus_1;
dimension_type subtree_size;
const bool deleting = itr->first == unused_index;
PPL_ASSERT(deleting || key != unused_index);
@@ -641,7 +641,7 @@ PPL::CO_Tree::count_used_in_subtree(inorder_iterator& itr) {
dimension_type n = 0;
#ifdef USE_PPL_CO_TREE_VEB_LAYOUT
- const dimension_type depth = itr.depth();
+ const height_t depth = itr.depth();
#ifndef NDEBUG
const dimension_type root_index = itr->first;
@@ -711,7 +711,7 @@ PPL::CO_Tree::count_used_in_subtree(inorder_const_iterator& itr) {
dimension_type n = 0;
#ifdef USE_PPL_CO_TREE_VEB_LAYOUT
- const dimension_type depth = itr.depth();
+ const height_t depth = itr.depth();
#ifndef NDEBUG
const dimension_type root_index = itr->first;
@@ -833,7 +833,7 @@ PPL::CO_Tree
#endif
#ifdef USE_PPL_CO_TREE_VEB_LAYOUT
- const dimension_type depth = root.depth();
+ const height_t depth = root.depth();
#endif // defined(USE_PPL_CO_TREE_DFS_LAYOUT)
while (root.get_right_child_value())
@@ -995,7 +995,7 @@ PPL::CO_Tree
#ifdef USE_PPL_CO_TREE_VEB_LAYOUT
const PPL::CO_Tree::level_data*
-PPL::CO_Tree::Level_Data_Cache::get_level_data(dimension_type height) {
+PPL::CO_Tree::Level_Data_Cache::get_level_data(height_t height) {
PPL_ASSERT(height >= 2);
if (cache[height] == NULL) {
cache[height] = new level_data[height];
@@ -1007,12 +1007,12 @@ PPL::CO_Tree::Level_Data_Cache::get_level_data(dimension_type height) {
void
PPL::CO_Tree::Level_Data_Cache
::fill_level_data(level_data* p,
- dimension_type min_depth, dimension_type max_depth) {
+ height_t min_depth, height_t max_depth) {
PPL_ASSERT(p != NULL);
if (min_depth == max_depth)
return;
- dimension_type d0 = (min_depth + max_depth) / 2;
+ height_t d0 = (min_depth + max_depth) / 2;
p[d0].depth_of_root_of_top_tree = min_depth;
p[d0].bottom_tree_size = ((dimension_type)1 << (max_depth - d0)) - 1;
diff --git a/src/CO_Tree.defs.hh b/src/CO_Tree.defs.hh
index ebbba0f..0960519 100644
--- a/src/CO_Tree.defs.hh
+++ b/src/CO_Tree.defs.hh
@@ -266,7 +266,7 @@ private:
struct level_data {
dimension_type bottom_tree_size;
dimension_type top_tree_size;
- dimension_type depth_of_root_of_top_tree;
+ height_t depth_of_root_of_top_tree;
};
#ifdef USE_PPL_CO_TREE_VEB_LAYOUT
@@ -274,14 +274,14 @@ private:
public:
- static const level_data* get_level_data(dimension_type height);
+ static const level_data* get_level_data(height_t height);
private:
- static const dimension_type max_depth = sizeof(dimension_type)*CHAR_BIT;
+ static const height_t max_depth = sizeof(dimension_type)*CHAR_BIT;
- static void fill_level_data(level_data* p, dimension_type min_depth,
- dimension_type max_depth);
+ static void fill_level_data(level_data* p, height_t min_depth,
+ height_t max_depth);
//! cache[0] and cache[1] are not used.
//! cache[i] contains NULL if get_level_data(i) has not been called yet,
@@ -410,7 +410,7 @@ private:
#endif // defined(USE_PPL_CO_TREE_VEB_LAYOUT)
//! The depth of the leaves in the static tree.
- dimension_type max_depth;
+ height_t max_depth;
//! 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.
@@ -530,14 +530,14 @@ public:
bool is_before_begin() const;
//! Returns the depth of the current node.
- dimension_type depth() const;
+ height_t depth() const;
const CO_Tree* get_tree() const;
private:
#ifdef USE_PPL_CO_TREE_VEB_LAYOUT
//! The depth of the current node in the vEB layout.
- dimension_type d;
+ height_t d;
//! Position of the node in a BFS layout.
dimension_type i;
@@ -685,7 +685,7 @@ public:
bool is_before_begin() const;
//! Returns the depth of the current node.
- dimension_type depth() const;
+ height_t depth() const;
CO_Tree* get_tree();
@@ -694,7 +694,7 @@ public:
private:
#ifdef USE_PPL_CO_TREE_VEB_LAYOUT
//! The depth of the current node in the vEB layout.
- dimension_type d;
+ height_t d;
//! Position of the node in a BFS layout.
dimension_type i;
diff --git a/src/CO_Tree.inlines.hh b/src/CO_Tree.inlines.hh
index 8de94c1..b27aa3e 100644
--- a/src/CO_Tree.inlines.hh
+++ b/src/CO_Tree.inlines.hh
@@ -837,7 +837,7 @@ CO_Tree::inorder_iterator::is_before_begin() const {
#endif // defined(USE_PPL_CO_TREE_DFS_LAYOUT)
}
-inline dimension_type
+inline CO_Tree::height_t
CO_Tree::inorder_iterator::depth() const {
PPL_ASSERT(tree != 0);
@@ -847,7 +847,7 @@ CO_Tree::inorder_iterator::depth() const {
#ifdef USE_PPL_CO_TREE_BFS_LAYOUT
dimension_type n = i;
- dimension_type d = 0;
+ height_t d = 0;
while (n != 0) {
n /= 2;
++d;
@@ -857,7 +857,7 @@ CO_Tree::inorder_iterator::depth() const {
#ifdef USE_PPL_CO_TREE_DFS_LAYOUT
dimension_type n = i;
- dimension_type d = 0;
+ height_t d = 0;
while ((n & (dimension_type)0x01U) == 0) {
n /= 2;
++d;
@@ -1112,7 +1112,7 @@ CO_Tree::inorder_iterator::operator=(const inorder_iterator& itr2) {
if (!is_at_end() && !is_before_begin()) {
d = itr2.d;
i = itr2.i;
- for (dimension_type i = 1; i <= itr2.d; ++i)
+ for (height_t i = 1; i <= itr2.d; ++i)
pos[i] = itr2.pos[i];
}
#endif // defined(USE_PPL_CO_TREE_VEB_LAYOUT)
@@ -1492,7 +1492,7 @@ CO_Tree::inorder_const_iterator::is_before_begin() const {
#endif // defined(USE_PPL_CO_TREE_DFS_LAYOUT)
}
-inline dimension_type
+inline CO_Tree::height_t
CO_Tree::inorder_const_iterator::depth() const {
PPL_ASSERT(tree != 0);
PPL_ASSERT(tree->reserved_size != 0);
@@ -1503,7 +1503,7 @@ CO_Tree::inorder_const_iterator::depth() const {
#ifdef USE_PPL_CO_TREE_BFS_LAYOUT
dimension_type n = i;
- dimension_type d = 0;
+ height_t d = 0;
while (n != 0) {
n /= 2;
++d;
@@ -1513,7 +1513,7 @@ CO_Tree::inorder_const_iterator::depth() const {
#ifdef USE_PPL_CO_TREE_DFS_LAYOUT
dimension_type n = i;
- dimension_type d = 0;
+ height_t d = 0;
while ((n & (dimension_type)0x01U) == 0) {
n /= 2;
++d;
More information about the PPL-devel
mailing list