|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r85171 - in trunk/boost/intrusive: . detail
From: igaztanaga_at_[hidden]
Date: 2013-07-29 17:43:03
Author: igaztanaga
Date: 2013-07-29 17:43:03 EDT (Mon, 29 Jul 2013)
New Revision: 85171
URL: http://svn.boost.org/trac/boost/changeset/85171
Log:
Fixed some GCC warnings and errors
Text files modified:
trunk/boost/intrusive/avltree_algorithms.hpp | 48 +++++++++++++++---------------
trunk/boost/intrusive/bstree.hpp | 20 ++++++------
trunk/boost/intrusive/detail/generic_hook.hpp | 4 +-
trunk/boost/intrusive/detail/memory_util.hpp | 4 ++
trunk/boost/intrusive/detail/mpl.hpp | 19 +++--------
trunk/boost/intrusive/list.hpp | 2
trunk/boost/intrusive/pointer_traits.hpp | 4 +-
trunk/boost/intrusive/rbtree_algorithms.hpp | 62 ++++++++++++++++++++--------------------
trunk/boost/intrusive/sgtree_algorithms.hpp | 34 ++++++++++----------
trunk/boost/intrusive/splaytree_algorithms.hpp | 54 +++++++++++++++++-----------------
trunk/boost/intrusive/treap.hpp | 8 ++--
trunk/boost/intrusive/treap_algorithms.hpp | 42 +++++++++++++-------------
12 files changed, 149 insertions(+), 152 deletions(-)
Modified: trunk/boost/intrusive/avltree_algorithms.hpp
==============================================================================
--- trunk/boost/intrusive/avltree_algorithms.hpp Mon Jul 29 17:41:48 2013 (r85170)
+++ trunk/boost/intrusive/avltree_algorithms.hpp 2013-07-29 17:43:03 EDT (Mon, 29 Jul 2013) (r85171)
@@ -112,14 +112,14 @@
/// @cond
private:
- typedef bstree_algorithms<NodeTraits> bstree_algorithms;
+ typedef bstree_algorithms<NodeTraits> bstree_algo;
/// @endcond
public:
//! This type is the information that will be
//! filled by insert_unique_check
- typedef typename bstree_algorithms::insert_commit_data insert_commit_data;
+ typedef typename bstree_algo::insert_commit_data insert_commit_data;
#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
@@ -143,7 +143,7 @@
if(node1 == node2)
return;
- node_ptr header1(bstree_algorithms::get_header(node1)), header2(bstree_algorithms::get_header(node2));
+ node_ptr header1(bstree_algo::get_header(node1)), header2(bstree_algo::get_header(node2));
swap_nodes(node1, header1, node2, header2);
}
@@ -152,7 +152,7 @@
{
if(node1 == node2) return;
- bstree_algorithms::swap_nodes(node1, header1, node2, header2);
+ bstree_algo::swap_nodes(node1, header1, node2, header2);
//Swap balance
balance c = NodeTraits::get_balance(node1);
NodeTraits::set_balance(node1, NodeTraits::get_balance(node2));
@@ -164,13 +164,13 @@
{
if(node_to_be_replaced == new_node)
return;
- replace_node(node_to_be_replaced, bstree_algorithms::get_header(node_to_be_replaced), new_node);
+ replace_node(node_to_be_replaced, bstree_algo::get_header(node_to_be_replaced), new_node);
}
//! @copydoc ::boost::intrusive::bstree_algorithms::replace_node(const node_ptr&,const node_ptr&,const node_ptr&)
static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & header, const node_ptr & new_node)
{
- bstree_algorithms::replace_node(node_to_be_replaced, header, new_node);
+ bstree_algo::replace_node(node_to_be_replaced, header, new_node);
NodeTraits::set_balance(new_node, NodeTraits::get_balance(node_to_be_replaced));
}
@@ -217,15 +217,15 @@
//! <b>Nodes</b>: If node is inserted in a tree, this function corrupts the tree.
static void init_header(const node_ptr & header)
{
- bstree_algorithms::init_header(header);
+ bstree_algo::init_header(header);
NodeTraits::set_balance(header, NodeTraits::zero());
}
//! @copydoc ::boost::intrusive::bstree_algorithms::erase(const node_ptr&,const node_ptr&)
static node_ptr erase(const node_ptr & header, const node_ptr & z)
{
- typename bstree_algorithms::data_for_rebalance info;
- bstree_algorithms::erase(header, z, avltree_erase_fixup<NodeTraits>(), info);
+ typename bstree_algo::data_for_rebalance info;
+ bstree_algo::erase(header, z, avltree_erase_fixup<NodeTraits>(), info);
//Rebalance avltree
rebalance_after_erasure(header, info.x, info.x_parent);
return z;
@@ -237,7 +237,7 @@
(const const_node_ptr & source_header, const node_ptr & target_header, Cloner cloner, Disposer disposer)
{
avltree_node_cloner<NodeTraits, Cloner> new_cloner(cloner);
- bstree_algorithms::clone(source_header, target_header, new_cloner, disposer);
+ bstree_algo::clone(source_header, target_header, new_cloner, disposer);
}
#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
@@ -281,7 +281,7 @@
static node_ptr insert_equal_upper_bound
(const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp)
{
- bstree_algorithms::insert_equal_upper_bound(h, new_node, comp);
+ bstree_algo::insert_equal_upper_bound(h, new_node, comp);
rebalance_after_insertion(h, new_node);
return new_node;
}
@@ -291,7 +291,7 @@
static node_ptr insert_equal_lower_bound
(const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp)
{
- bstree_algorithms::insert_equal_lower_bound(h, new_node, comp);
+ bstree_algo::insert_equal_lower_bound(h, new_node, comp);
rebalance_after_insertion(h, new_node);
return new_node;
}
@@ -301,7 +301,7 @@
static node_ptr insert_equal
(const node_ptr & header, const node_ptr & hint, const node_ptr & new_node, NodePtrCompare comp)
{
- bstree_algorithms::insert_equal(header, hint, new_node, comp);
+ bstree_algo::insert_equal(header, hint, new_node, comp);
rebalance_after_insertion(header, new_node);
return new_node;
}
@@ -310,7 +310,7 @@
static node_ptr insert_before
(const node_ptr & header, const node_ptr & pos, const node_ptr & new_node)
{
- bstree_algorithms::insert_before(header, pos, new_node);
+ bstree_algo::insert_before(header, pos, new_node);
rebalance_after_insertion(header, new_node);
return new_node;
}
@@ -318,14 +318,14 @@
//! @copydoc ::boost::intrusive::bstree_algorithms::push_back(const node_ptr&,const node_ptr&)
static void push_back(const node_ptr & header, const node_ptr & new_node)
{
- bstree_algorithms::push_back(header, new_node);
+ bstree_algo::push_back(header, new_node);
rebalance_after_insertion(header, new_node);
}
//! @copydoc ::boost::intrusive::bstree_algorithms::push_front(const node_ptr&,const node_ptr&)
static void push_front(const node_ptr & header, const node_ptr & new_node)
{
- bstree_algorithms::push_front(header, new_node);
+ bstree_algo::push_front(header, new_node);
rebalance_after_insertion(header, new_node);
}
@@ -347,13 +347,13 @@
static void insert_unique_commit
(const node_ptr & header, const node_ptr & new_value, const insert_commit_data &commit_data)
{
- bstree_algorithms::insert_unique_commit(header, new_value, commit_data);
+ bstree_algo::insert_unique_commit(header, new_value, commit_data);
rebalance_after_insertion(header, new_value);
}
//! @copydoc ::boost::intrusive::bstree_algorithms::is_header
static bool is_header(const const_node_ptr & p)
- { return NodeTraits::get_balance(p) == NodeTraits::zero() && bstree_algorithms::is_header(p); }
+ { return NodeTraits::get_balance(p) == NodeTraits::zero() && bstree_algo::is_header(p); }
/// @cond
@@ -516,8 +516,8 @@
// / \ //
// e f //
node_ptr b = NodeTraits::get_left(a), c = NodeTraits::get_right(b);
- bstree_algorithms::rotate_left(b, hdr);
- bstree_algorithms::rotate_right(a, hdr);
+ bstree_algo::rotate_left(b, hdr);
+ bstree_algo::rotate_right(a, hdr);
left_right_balancing(a, b, c);
}
@@ -533,15 +533,15 @@
// / \ //
// e f //
node_ptr b = NodeTraits::get_right(a), c = NodeTraits::get_left(b);
- bstree_algorithms::rotate_right(b, hdr);
- bstree_algorithms::rotate_left(a, hdr);
+ bstree_algo::rotate_right(b, hdr);
+ bstree_algo::rotate_left(a, hdr);
left_right_balancing(b, a, c);
}
static void rotate_left(const node_ptr x, const node_ptr & hdr)
{
const node_ptr y = NodeTraits::get_right(x);
- bstree_algorithms::rotate_left(x, hdr);
+ bstree_algo::rotate_left(x, hdr);
// reset the balancing factor
if (NodeTraits::get_balance(y) == NodeTraits::positive()) {
@@ -557,7 +557,7 @@
static void rotate_right(const node_ptr x, const node_ptr & hdr)
{
const node_ptr y = NodeTraits::get_left(x);
- bstree_algorithms::rotate_right(x, hdr);
+ bstree_algo::rotate_right(x, hdr);
// reset the balancing factor
if (NodeTraits::get_balance(y) == NodeTraits::negative()) {
Modified: trunk/boost/intrusive/bstree.hpp
==============================================================================
--- trunk/boost/intrusive/bstree.hpp Mon Jul 29 17:41:48 2013 (r85170)
+++ trunk/boost/intrusive/bstree.hpp 2013-07-29 17:43:03 EDT (Mon, 29 Jul 2013) (r85171)
@@ -63,8 +63,8 @@
typedef typename node_traits::node_ptr node_ptr;
typedef typename node_traits::const_node_ptr const_node_ptr;
- bstbase3(const ValueTraits &val_traits)
- : ValueTraits(val_traits)
+ bstbase3(const ValueTraits &vtraits)
+ : ValueTraits(vtraits)
{}
static const bool external_value_traits =
@@ -212,8 +212,8 @@
typedef typename treeheader_t::node_ptr node_ptr;
typedef typename treeheader_t::const_node_ptr const_node_ptr;
- bstbase2(const value_compare &comp, const ValueTraits &val_traits)
- : treeheader_t(val_traits), detail::ebo_functor_holder<value_compare>(comp)
+ bstbase2(const value_compare &comp, const ValueTraits &vtraits)
+ : treeheader_t(vtraits), detail::ebo_functor_holder<value_compare>(comp)
{}
const value_compare &comp() const
@@ -378,10 +378,10 @@
(const KeyType &key, KeyValueCompare key_value_comp, insert_commit_data &commit_data)
{
detail::key_nodeptr_comp<KeyValueCompare, real_value_traits>
- comp(key_value_comp, &this->get_real_value_traits());
+ ocomp(key_value_comp, &this->get_real_value_traits());
std::pair<node_ptr, bool> ret =
(node_algorithms::insert_unique_check
- (this->header_ptr(), key, comp, commit_data));
+ (this->header_ptr(), key, ocomp, commit_data));
return std::pair<iterator, bool>(iterator(ret.first, this->real_value_traits_ptr()), ret.second);
}
@@ -391,10 +391,10 @@
,KeyValueCompare key_value_comp, insert_commit_data &commit_data)
{
detail::key_nodeptr_comp<KeyValueCompare, real_value_traits>
- comp(key_value_comp, &this->get_real_value_traits());
+ ocomp(key_value_comp, &this->get_real_value_traits());
std::pair<node_ptr, bool> ret =
(node_algorithms::insert_unique_check
- (this->header_ptr(), hint.pointed_node(), key, comp, commit_data));
+ (this->header_ptr(), hint.pointed_node(), key, ocomp, commit_data));
return std::pair<iterator, bool>(iterator(ret.first, this->real_value_traits_ptr()), ret.second);
}
};
@@ -417,8 +417,8 @@
<AlgoType, node_traits>::type algo_type;
typedef SizeType size_type;
- bstbase(const value_compare & comp, const ValueTraits &val_traits)
- : base_type(comp, val_traits)
+ bstbase(const value_compare & comp, const ValueTraits &vtraits)
+ : base_type(comp, vtraits)
{}
public:
Modified: trunk/boost/intrusive/detail/generic_hook.hpp
==============================================================================
--- trunk/boost/intrusive/detail/generic_hook.hpp Mon Jul 29 17:41:48 2013 (r85170)
+++ trunk/boost/intrusive/detail/generic_hook.hpp 2013-07-29 17:43:03 EDT (Mon, 29 Jul 2013) (r85171)
@@ -81,7 +81,7 @@
, link_mode_type LinkMode
, base_hook_type BaseHookType
>
-struct hooktags
+struct hooktags_impl
{
static const link_mode_type link_mode = LinkMode;
typedef Tag tag;
@@ -129,7 +129,7 @@
public:
- typedef hooktags
+ typedef hooktags_impl
< typename GetNodeAlgorithms::type::node_traits
, Tag, LinkMode, BaseHookType> hooktags;
Modified: trunk/boost/intrusive/detail/memory_util.hpp
==============================================================================
--- trunk/boost/intrusive/detail/memory_util.hpp Mon Jul 29 17:41:48 2013 (r85170)
+++ trunk/boost/intrusive/detail/memory_util.hpp 2013-07-29 17:43:03 EDT (Mon, 29 Jul 2013) (r85171)
@@ -45,6 +45,10 @@
template <> struct unvoid<void> { struct type { }; };
template <> struct unvoid<const void> { struct type { }; };
+template <typename T> struct unvoid_ref { typedef T &type; };
+template <> struct unvoid_ref<void> { struct type_impl { }; typedef type_impl & type; };
+template <> struct unvoid_ref<const void> { struct type_impl { }; typedef type_impl & type; };
+
template <typename T>
struct LowPriorityConversion
{
Modified: trunk/boost/intrusive/detail/mpl.hpp
==============================================================================
--- trunk/boost/intrusive/detail/mpl.hpp Mon Jul 29 17:41:48 2013 (r85170)
+++ trunk/boost/intrusive/detail/mpl.hpp 2013-07-29 17:43:03 EDT (Mon, 29 Jul 2013) (r85171)
@@ -283,20 +283,13 @@
template <typename T, typename U>
struct is_same
{
- typedef char yes_type;
- struct no_type
- {
- char padding[8];
- };
-
- template <typename V>
- static yes_type is_same_tester(V*, V*);
- static no_type is_same_tester(...);
-
- static T *t;
- static U *u;
+ static const bool value = false;
+};
- static const bool value = sizeof(yes_type) == sizeof(is_same_tester(t,u));
+template <typename T>
+struct is_same<T, T>
+{
+ static const bool value = true;
};
template<typename T>
Modified: trunk/boost/intrusive/list.hpp
==============================================================================
--- trunk/boost/intrusive/list.hpp Mon Jul 29 17:41:48 2013 (r85170)
+++ trunk/boost/intrusive/list.hpp 2013-07-29 17:43:03 EDT (Mon, 29 Jul 2013) (r85171)
@@ -174,7 +174,7 @@
real_value_traits &get_real_value_traits()
{ return this->get_real_value_traits(detail::bool_<external_value_traits>()); }
- typedef typename pointer_traits<node_ptr>::template rebind_pointer<const real_value_traits>::type const_real_value_traits_ptr;
+ typedef typename pointer_traits<node_ptr>::template rebind_pointer<real_value_traits const>::type const_real_value_traits_ptr;
const_real_value_traits_ptr real_value_traits_ptr() const
{ return pointer_traits<const_real_value_traits_ptr>::pointer_to(this->get_real_value_traits()); }
Modified: trunk/boost/intrusive/pointer_traits.hpp
==============================================================================
--- trunk/boost/intrusive/pointer_traits.hpp Mon Jul 29 17:41:48 2013 (r85170)
+++ trunk/boost/intrusive/pointer_traits.hpp 2013-07-29 17:43:03 EDT (Mon, 29 Jul 2013) (r85171)
@@ -74,7 +74,7 @@
typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT
(boost::intrusive::detail::, Ptr, difference_type, std::ptrdiff_t) difference_type;
//
- typedef typename boost::intrusive::detail::unvoid<element_type>::type& reference;
+ typedef typename boost::intrusive::detail::unvoid_ref<element_type>::type reference;
//
template <class U> struct rebind_pointer
{
@@ -224,7 +224,7 @@
//!shall be used instead of rebind<U> to obtain a pointer to U.
template <class U> using rebind = U*;
#else
- typedef typename boost::intrusive::detail::unvoid<element_type>::type& reference;
+ typedef typename boost::intrusive::detail::unvoid_ref<element_type>::type reference;
#if !defined(BOOST_NO_CXX11_TEMPLATE_ALIASES)
template <class U> using rebind = U*;
#endif
Modified: trunk/boost/intrusive/rbtree_algorithms.hpp
==============================================================================
--- trunk/boost/intrusive/rbtree_algorithms.hpp Mon Jul 29 17:41:48 2013 (r85170)
+++ trunk/boost/intrusive/rbtree_algorithms.hpp 2013-07-29 17:43:03 EDT (Mon, 29 Jul 2013) (r85171)
@@ -165,7 +165,7 @@
/// @cond
private:
- typedef bstree_algorithms<NodeTraits> bstree_algorithms;
+ typedef bstree_algorithms<NodeTraits> bstree_algo;
/// @endcond
@@ -173,7 +173,7 @@
//! This type is the information that will be
//! filled by insert_unique_check
- typedef typename bstree_algorithms::insert_commit_data insert_commit_data;
+ typedef typename bstree_algo::insert_commit_data insert_commit_data;
#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
@@ -197,7 +197,7 @@
if(node1 == node2)
return;
- node_ptr header1(bstree_algorithms::get_header(node1)), header2(bstree_algorithms::get_header(node2));
+ node_ptr header1(bstree_algo::get_header(node1)), header2(bstree_algo::get_header(node2));
swap_nodes(node1, header1, node2, header2);
}
@@ -206,7 +206,7 @@
{
if(node1 == node2) return;
- bstree_algorithms::swap_nodes(node1, header1, node2, header2);
+ bstree_algo::swap_nodes(node1, header1, node2, header2);
//Swap color
color c = NodeTraits::get_color(node1);
NodeTraits::set_color(node1, NodeTraits::get_color(node2));
@@ -218,13 +218,13 @@
{
if(node_to_be_replaced == new_node)
return;
- replace_node(node_to_be_replaced, bstree_algorithms::get_header(node_to_be_replaced), new_node);
+ replace_node(node_to_be_replaced, bstree_algo::get_header(node_to_be_replaced), new_node);
}
//! @copydoc ::boost::intrusive::bstree_algorithms::replace_node(const node_ptr&,const node_ptr&,const node_ptr&)
static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & header, const node_ptr & new_node)
{
- bstree_algorithms::replace_node(node_to_be_replaced, header, new_node);
+ bstree_algo::replace_node(node_to_be_replaced, header, new_node);
NodeTraits::set_color(new_node, NodeTraits::get_color(node_to_be_replaced));
}
@@ -262,15 +262,15 @@
//! @copydoc ::boost::intrusive::bstree_algorithms::init_header(const node_ptr&)
static void init_header(const node_ptr & header)
{
- bstree_algorithms::init_header(header);
+ bstree_algo::init_header(header);
NodeTraits::set_color(header, NodeTraits::red());
}
//! @copydoc ::boost::intrusive::bstree_algorithms::erase(const node_ptr&,const node_ptr&)
static node_ptr erase(const node_ptr & header, const node_ptr & z)
{
- typename bstree_algorithms::data_for_rebalance info;
- bstree_algorithms::erase(header, z, rbtree_erase_fixup<NodeTraits>(), info);
+ typename bstree_algo::data_for_rebalance info;
+ bstree_algo::erase(header, z, rbtree_erase_fixup<NodeTraits>(), info);
//Rebalance rbtree
if(NodeTraits::get_color(z) != NodeTraits::red()){
@@ -285,7 +285,7 @@
(const const_node_ptr & source_header, const node_ptr & target_header, Cloner cloner, Disposer disposer)
{
rbtree_node_cloner<NodeTraits, Cloner> new_cloner(cloner);
- bstree_algorithms::clone(source_header, target_header, new_cloner, disposer);
+ bstree_algo::clone(source_header, target_header, new_cloner, disposer);
}
#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
@@ -329,7 +329,7 @@
static node_ptr insert_equal_upper_bound
(const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp)
{
- bstree_algorithms::insert_equal_upper_bound(h, new_node, comp);
+ bstree_algo::insert_equal_upper_bound(h, new_node, comp);
rebalance_after_insertion(h, new_node);
return new_node;
}
@@ -339,7 +339,7 @@
static node_ptr insert_equal_lower_bound
(const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp)
{
- bstree_algorithms::insert_equal_lower_bound(h, new_node, comp);
+ bstree_algo::insert_equal_lower_bound(h, new_node, comp);
rebalance_after_insertion(h, new_node);
return new_node;
}
@@ -349,7 +349,7 @@
static node_ptr insert_equal
(const node_ptr & header, const node_ptr & hint, const node_ptr & new_node, NodePtrCompare comp)
{
- bstree_algorithms::insert_equal(header, hint, new_node, comp);
+ bstree_algo::insert_equal(header, hint, new_node, comp);
rebalance_after_insertion(header, new_node);
return new_node;
}
@@ -358,7 +358,7 @@
static node_ptr insert_before
(const node_ptr & header, const node_ptr & pos, const node_ptr & new_node)
{
- bstree_algorithms::insert_before(header, pos, new_node);
+ bstree_algo::insert_before(header, pos, new_node);
rebalance_after_insertion(header, new_node);
return new_node;
}
@@ -366,14 +366,14 @@
//! @copydoc ::boost::intrusive::bstree_algorithms::push_back(const node_ptr&,const node_ptr&)
static void push_back(const node_ptr & header, const node_ptr & new_node)
{
- bstree_algorithms::push_back(header, new_node);
+ bstree_algo::push_back(header, new_node);
rebalance_after_insertion(header, new_node);
}
//! @copydoc ::boost::intrusive::bstree_algorithms::push_front(const node_ptr&,const node_ptr&)
static void push_front(const node_ptr & header, const node_ptr & new_node)
{
- bstree_algorithms::push_front(header, new_node);
+ bstree_algo::push_front(header, new_node);
rebalance_after_insertion(header, new_node);
}
@@ -395,7 +395,7 @@
static void insert_unique_commit
(const node_ptr & header, const node_ptr & new_value, const insert_commit_data &commit_data)
{
- bstree_algorithms::insert_unique_commit(header, new_value, commit_data);
+ bstree_algo::insert_unique_commit(header, new_value, commit_data);
rebalance_after_insertion(header, new_value);
}
@@ -403,7 +403,7 @@
static bool is_header(const const_node_ptr & p)
{
return NodeTraits::get_color(p) == NodeTraits::red() &&
- bstree_algorithms::is_header(p);
+ bstree_algo::is_header(p);
}
/// @cond
@@ -418,7 +418,7 @@
if(NodeTraits::get_color(w) == NodeTraits::red()){
NodeTraits::set_color(w, NodeTraits::black());
NodeTraits::set_color(x_parent, NodeTraits::red());
- bstree_algorithms::rotate_left(x_parent, header);
+ bstree_algo::rotate_left(x_parent, header);
w = NodeTraits::get_right(x_parent);
}
if((!NodeTraits::get_left(w) || NodeTraits::get_color(NodeTraits::get_left(w)) == NodeTraits::black()) &&
@@ -431,14 +431,14 @@
if(!NodeTraits::get_right(w) || NodeTraits::get_color(NodeTraits::get_right(w)) == NodeTraits::black()){
NodeTraits::set_color(NodeTraits::get_left(w), NodeTraits::black());
NodeTraits::set_color(w, NodeTraits::red());
- bstree_algorithms::rotate_right(w, header);
+ bstree_algo::rotate_right(w, header);
w = NodeTraits::get_right(x_parent);
}
NodeTraits::set_color(w, NodeTraits::get_color(x_parent));
NodeTraits::set_color(x_parent, NodeTraits::black());
if(NodeTraits::get_right(w))
NodeTraits::set_color(NodeTraits::get_right(w), NodeTraits::black());
- bstree_algorithms::rotate_left(x_parent, header);
+ bstree_algo::rotate_left(x_parent, header);
break;
}
}
@@ -448,7 +448,7 @@
if(NodeTraits::get_color(w) == NodeTraits::red()){
NodeTraits::set_color(w, NodeTraits::black());
NodeTraits::set_color(x_parent, NodeTraits::red());
- bstree_algorithms::rotate_right(x_parent, header);
+ bstree_algo::rotate_right(x_parent, header);
w = NodeTraits::get_left(x_parent);
}
if((!NodeTraits::get_right(w) || NodeTraits::get_color(NodeTraits::get_right(w)) == NodeTraits::black()) &&
@@ -461,14 +461,14 @@
if(!NodeTraits::get_left(w) || NodeTraits::get_color(NodeTraits::get_left(w)) == NodeTraits::black()){
NodeTraits::set_color(NodeTraits::get_right(w), NodeTraits::black());
NodeTraits::set_color(w, NodeTraits::red());
- bstree_algorithms::rotate_left(w, header);
+ bstree_algo::rotate_left(w, header);
w = NodeTraits::get_left(x_parent);
}
NodeTraits::set_color(w, NodeTraits::get_color(x_parent));
NodeTraits::set_color(x_parent, NodeTraits::black());
if(NodeTraits::get_left(w))
NodeTraits::set_color(NodeTraits::get_left(w), NodeTraits::black());
- bstree_algorithms::rotate_right(x_parent, header);
+ bstree_algo::rotate_right(x_parent, header);
break;
}
}
@@ -483,7 +483,7 @@
while(p != NodeTraits::get_parent(header) && NodeTraits::get_color(NodeTraits::get_parent(p)) == NodeTraits::red()){
node_ptr p_parent(NodeTraits::get_parent(p));
node_ptr p_parent_parent(NodeTraits::get_parent(p_parent));
- if(bstree_algorithms::is_left_child(p_parent)){
+ if(bstree_algo::is_left_child(p_parent)){
node_ptr x = NodeTraits::get_right(p_parent_parent);
if(x && NodeTraits::get_color(x) == NodeTraits::red()){
NodeTraits::set_color(p_parent, NodeTraits::black());
@@ -492,15 +492,15 @@
p = p_parent_parent;
}
else {
- if(!bstree_algorithms::is_left_child(p)){
+ if(!bstree_algo::is_left_child(p)){
p = p_parent;
- bstree_algorithms::rotate_left(p, header);
+ bstree_algo::rotate_left(p, header);
}
node_ptr new_p_parent(NodeTraits::get_parent(p));
node_ptr new_p_parent_parent(NodeTraits::get_parent(new_p_parent));
NodeTraits::set_color(new_p_parent, NodeTraits::black());
NodeTraits::set_color(new_p_parent_parent, NodeTraits::red());
- bstree_algorithms::rotate_right(new_p_parent_parent, header);
+ bstree_algo::rotate_right(new_p_parent_parent, header);
}
}
else{
@@ -512,15 +512,15 @@
p = p_parent_parent;
}
else{
- if(bstree_algorithms::is_left_child(p)){
+ if(bstree_algo::is_left_child(p)){
p = p_parent;
- bstree_algorithms::rotate_right(p, header);
+ bstree_algo::rotate_right(p, header);
}
node_ptr new_p_parent(NodeTraits::get_parent(p));
node_ptr new_p_parent_parent(NodeTraits::get_parent(new_p_parent));
NodeTraits::set_color(new_p_parent, NodeTraits::black());
NodeTraits::set_color(new_p_parent_parent, NodeTraits::red());
- bstree_algorithms::rotate_left(new_p_parent_parent, header);
+ bstree_algo::rotate_left(new_p_parent_parent, header);
}
}
}
Modified: trunk/boost/intrusive/sgtree_algorithms.hpp
==============================================================================
--- trunk/boost/intrusive/sgtree_algorithms.hpp Mon Jul 29 17:41:48 2013 (r85170)
+++ trunk/boost/intrusive/sgtree_algorithms.hpp 2013-07-29 17:43:03 EDT (Mon, 29 Jul 2013) (r85171)
@@ -70,7 +70,7 @@
/// @cond
private:
- typedef bstree_algorithms<NodeTraits> bstree_algorithms;
+ typedef bstree_algorithms<NodeTraits> bstree_algo;
/// @endcond
@@ -78,7 +78,7 @@
//! This type is the information that will be
//! filled by insert_unique_check
struct insert_commit_data
- : bstree_algorithms::insert_commit_data
+ : bstree_algo::insert_commit_data
{
std::size_t depth;
};
@@ -137,12 +137,12 @@
template<class AlphaByMaxSize>
static node_ptr erase(const node_ptr & header, const node_ptr & z, std::size_t tree_size, std::size_t &max_tree_size, AlphaByMaxSize alpha_by_maxsize)
{
- //typename bstree_algorithms::data_for_rebalance info;
- bstree_algorithms::erase(header, z);
+ //typename bstree_algo::data_for_rebalance info;
+ bstree_algo::erase(header, z);
--tree_size;
if (tree_size > 0 &&
tree_size < alpha_by_maxsize(max_tree_size)){
- bstree_algorithms::rebalance(header);
+ bstree_algo::rebalance(header);
max_tree_size = tree_size;
}
return z;
@@ -196,7 +196,7 @@
,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size)
{
std::size_t depth;
- bstree_algorithms::insert_equal_upper_bound(h, new_node, comp, &depth);
+ bstree_algo::insert_equal_upper_bound(h, new_node, comp, &depth);
rebalance_after_insertion(new_node, depth, tree_size+1, h_alpha, max_tree_size);
return new_node;
}
@@ -208,7 +208,7 @@
,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size)
{
std::size_t depth;
- bstree_algorithms::insert_equal_lower_bound(h, new_node, comp, &depth);
+ bstree_algo::insert_equal_lower_bound(h, new_node, comp, &depth);
rebalance_after_insertion(new_node, depth, tree_size+1, h_alpha, max_tree_size);
return new_node;
}
@@ -220,7 +220,7 @@
,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size)
{
std::size_t depth;
- bstree_algorithms::insert_equal(header, hint, new_node, comp, &depth);
+ bstree_algo::insert_equal(header, hint, new_node, comp, &depth);
rebalance_after_insertion(new_node, depth, tree_size+1, h_alpha, max_tree_size);
return new_node;
}
@@ -232,7 +232,7 @@
,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size)
{
std::size_t depth;
- bstree_algorithms::insert_before(header, pos, new_node, &depth);
+ bstree_algo::insert_before(header, pos, new_node, &depth);
rebalance_after_insertion(new_node, depth, tree_size+1, h_alpha, max_tree_size);
return new_node;
}
@@ -243,7 +243,7 @@
,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size)
{
std::size_t depth;
- bstree_algorithms::push_back(header, new_node, &depth);
+ bstree_algo::push_back(header, new_node, &depth);
rebalance_after_insertion(new_node, depth, tree_size+1, h_alpha, max_tree_size);
}
@@ -253,7 +253,7 @@
,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size)
{
std::size_t depth;
- bstree_algorithms::push_front(header, new_node, &depth);
+ bstree_algo::push_front(header, new_node, &depth);
rebalance_after_insertion(new_node, depth, tree_size+1, h_alpha, max_tree_size);
}
@@ -265,7 +265,7 @@
{
std::size_t depth;
std::pair<node_ptr, bool> ret =
- bstree_algorithms::insert_unique_check(header, key, comp, commit_data, &depth);
+ bstree_algo::insert_unique_check(header, key, comp, commit_data, &depth);
commit_data.depth = depth;
return ret;
}
@@ -278,7 +278,7 @@
{
std::size_t depth;
std::pair<node_ptr, bool> ret =
- bstree_algorithms::insert_unique_check
+ bstree_algo::insert_unique_check
(header, hint, key, comp, commit_data, &depth);
commit_data.depth = depth;
return ret;
@@ -290,7 +290,7 @@
(const node_ptr & header, const node_ptr & new_value, const insert_commit_data &commit_data
,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size)
{
- bstree_algorithms::insert_unique_commit(header, new_value, commit_data);
+ bstree_algo::insert_unique_commit(header, new_value, commit_data);
rebalance_after_insertion(new_value, commit_data.depth, tree_size+1, h_alpha, max_tree_size);
}
@@ -333,7 +333,7 @@
for(std::size_t ancestor = 1; true; ++ancestor){
if(ancestor == depth){ //Check if whole tree must be rebuilt
max_tree_size = tree_size;
- bstree_algorithms::rebalance_subtree(NodeTraits::get_parent(s));
+ bstree_algo::rebalance_subtree(NodeTraits::get_parent(s));
break;
}
else{ //Go to the next scapegoat candidate
@@ -341,10 +341,10 @@
const node_ptr s_parent_left = NodeTraits::get_left(s_parent);
//Obtain parent's size (previous size + parent + sibling tree)
const node_ptr s_sibling = s_parent_left == s ? NodeTraits::get_right(s_parent) : s_parent_left;
- size += 1 + bstree_algorithms::subtree_size(s_sibling);
+ size += 1 + bstree_algo::subtree_size(s_sibling);
s = s_parent;
if(ancestor > h_alpha(size)){ //is 's' scapegoat?
- bstree_algorithms::rebalance_subtree(s);
+ bstree_algo::rebalance_subtree(s);
break;
}
}
Modified: trunk/boost/intrusive/splaytree_algorithms.hpp
==============================================================================
--- trunk/boost/intrusive/splaytree_algorithms.hpp Mon Jul 29 17:41:48 2013 (r85170)
+++ trunk/boost/intrusive/splaytree_algorithms.hpp 2013-07-29 17:43:03 EDT (Mon, 29 Jul 2013) (r85171)
@@ -118,7 +118,7 @@
{
/// @cond
private:
- typedef bstree_algorithms<NodeTraits> bstree_algorithms;
+ typedef bstree_algorithms<NodeTraits> bstree_algo;
/// @endcond
public:
@@ -129,7 +129,7 @@
//! This type is the information that will be
//! filled by insert_unique_check
- typedef typename bstree_algorithms::insert_commit_data insert_commit_data;
+ typedef typename bstree_algo::insert_commit_data insert_commit_data;
public:
#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
@@ -190,7 +190,7 @@
{
//posibility 1
if(splay && NodeTraits::get_left(z)){
- splay_up(bstree_algorithms::prev_node(z), header);
+ splay_up(bstree_algo::prev_node(z), header);
}
/*
//possibility 2
@@ -199,7 +199,7 @@
splay_up(l, header);
}*//*
if(splay && NodeTraits::get_left(z)){
- node_ptr l = bstree_algorithms::prev_node(z);
+ node_ptr l = bstree_algo::prev_node(z);
splay_up_impl(l, z);
}*/
/*
@@ -210,7 +210,7 @@
//if(splay)
//splay_up(z, header);
- bstree_algorithms::erase(header, z);
+ bstree_algo::erase(header, z);
}
#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
@@ -244,7 +244,7 @@
template<class KeyType, class KeyNodePtrCompare>
static std::size_t count
(const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp)
- { return bstree_algorithms::count(header, key, comp); }
+ { return bstree_algo::count(header, key, comp); }
//! @copydoc ::boost::intrusive::bstree_algorithms::lower_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare)
//! Additional notes: the first node of the range is splayed. The "splay" parameter which indicated if splaying
@@ -254,7 +254,7 @@
(const node_ptr & header, const KeyType &key, KeyNodePtrCompare comp, bool splay = true)
{
//splay_down(detail::uncast(header), key, comp);
- node_ptr y = bstree_algorithms::lower_bound(header, key, comp);
+ node_ptr y = bstree_algo::lower_bound(header, key, comp);
if(splay) splay_up(y, detail::uncast(header));
return y;
}
@@ -264,7 +264,7 @@
template<class KeyType, class KeyNodePtrCompare>
static node_ptr lower_bound
(const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp)
- { return bstree_algorithms::lower_bound(header, key, comp); }
+ { return bstree_algo::lower_bound(header, key, comp); }
//! @copydoc ::boost::intrusive::bstree_algorithms::upper_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare)
//! Additional notes: the first node of the range is splayed. The "splay" parameter which indicated if splaying
@@ -274,7 +274,7 @@
(const node_ptr & header, const KeyType &key, KeyNodePtrCompare comp, bool splay = true)
{
//splay_down(detail::uncast(header), key, comp);
- node_ptr y = bstree_algorithms::upper_bound(header, key, comp);
+ node_ptr y = bstree_algo::upper_bound(header, key, comp);
if(splay) splay_up(y, detail::uncast(header));
return y;
}
@@ -284,7 +284,7 @@
template<class KeyType, class KeyNodePtrCompare>
static node_ptr upper_bound
(const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp)
- { return bstree_algorithms::upper_bound(header, key, comp); }
+ { return bstree_algo::upper_bound(header, key, comp); }
//! @copydoc ::boost::intrusive::bstree_algorithms::find(const const_node_ptr&, const KeyType&,KeyNodePtrCompare)
//! Additional notes: the found node of the lower bound is splayed. The "splay" parameter which indicated if splaying
@@ -295,7 +295,7 @@
{
if(splay) splay_down(detail::uncast(header), key, comp);
node_ptr end = detail::uncast(header);
- node_ptr y = bstree_algorithms::lower_bound(header, key, comp);
+ node_ptr y = bstree_algo::lower_bound(header, key, comp);
node_ptr r = (y == end || comp(key, y)) ? end : y;
return r;
}
@@ -305,7 +305,7 @@
template<class KeyType, class KeyNodePtrCompare>
static node_ptr find
(const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp)
- { return bstree_algorithms::find(header, key, comp); }
+ { return bstree_algo::find(header, key, comp); }
//! @copydoc ::boost::intrusive::bstree_algorithms::equal_range(const const_node_ptr&,const KeyType&,KeyNodePtrCompare)
//! Additional notes: the first node of the range is splayed. The "splay" parameter which indicated if splaying
@@ -315,7 +315,7 @@
(const node_ptr & header, const KeyType &key, KeyNodePtrCompare comp, bool splay = true)
{
//splay_down(detail::uncast(header), key, comp);
- std::pair<node_ptr, node_ptr> ret = bstree_algorithms::equal_range(header, key, comp);
+ std::pair<node_ptr, node_ptr> ret = bstree_algo::equal_range(header, key, comp);
if(splay) splay_up(ret.first, detail::uncast(header));
return ret;
}
@@ -325,7 +325,7 @@
template<class KeyType, class KeyNodePtrCompare>
static std::pair<node_ptr, node_ptr> equal_range
(const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp)
- { return bstree_algorithms::equal_range(header, key, comp); }
+ { return bstree_algo::equal_range(header, key, comp); }
//! @copydoc ::boost::intrusive::bstree_algorithms::bounded_range(const const_node_ptr&,const KeyType&,const KeyType&,KeyNodePtrCompare,bool,bool)
//! Additional notes: the first node of the range is splayed. The "splay" parameter which indicated if splaying
@@ -336,7 +336,7 @@
, bool left_closed, bool right_closed, bool splay = true)
{
std::pair<node_ptr, node_ptr> ret =
- bstree_algorithms::bounded_range(header, lower_key, upper_key, comp, left_closed, right_closed);
+ bstree_algo::bounded_range(header, lower_key, upper_key, comp, left_closed, right_closed);
if(splay) splay_up(ret.first, detail::uncast(header));
return ret;
}
@@ -347,7 +347,7 @@
static std::pair<node_ptr, node_ptr> bounded_range
(const const_node_ptr & header, const KeyType &lower_key, const KeyType &upper_key, KeyNodePtrCompare comp
, bool left_closed, bool right_closed)
- { return bstree_algorithms::bounded_range(header, lower_key, upper_key, comp, left_closed, right_closed); }
+ { return bstree_algo::bounded_range(header, lower_key, upper_key, comp, left_closed, right_closed); }
//! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal_upper_bound(const node_ptr&,const node_ptr&,NodePtrCompare)
//! Additional note: the inserted node is splayed
@@ -356,7 +356,7 @@
(const node_ptr & header, const node_ptr & new_node, NodePtrCompare comp)
{
splay_down(header, new_node, comp);
- return bstree_algorithms::insert_equal_upper_bound(header, new_node, comp);
+ return bstree_algo::insert_equal_upper_bound(header, new_node, comp);
}
//! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal_lower_bound(const node_ptr&,const node_ptr&,NodePtrCompare)
@@ -366,7 +366,7 @@
(const node_ptr & header, const node_ptr & new_node, NodePtrCompare comp)
{
splay_down(header, new_node, comp);
- return bstree_algorithms::insert_equal_lower_bound(header, new_node, comp);
+ return bstree_algo::insert_equal_lower_bound(header, new_node, comp);
}
//! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal(const node_ptr&,const node_ptr&,const node_ptr&,NodePtrCompare)
@@ -376,7 +376,7 @@
(const node_ptr & header, const node_ptr & hint, const node_ptr & new_node, NodePtrCompare comp)
{
splay_down(header, new_node, comp);
- return bstree_algorithms::insert_equal(header, hint, new_node, comp);
+ return bstree_algo::insert_equal(header, hint, new_node, comp);
}
//! @copydoc ::boost::intrusive::bstree_algorithms::insert_before(const node_ptr&,const node_ptr&,const node_ptr&)
@@ -384,7 +384,7 @@
static node_ptr insert_before
(const node_ptr & header, const node_ptr & pos, const node_ptr & new_node)
{
- bstree_algorithms::insert_before(header, pos, new_node);
+ bstree_algo::insert_before(header, pos, new_node);
splay_up(new_node, header);
return new_node;
}
@@ -393,7 +393,7 @@
//! Additional note: the inserted node is splayed
static void push_back(const node_ptr & header, const node_ptr & new_node)
{
- bstree_algorithms::push_back(header, new_node);
+ bstree_algo::push_back(header, new_node);
splay_up(new_node, header);
}
@@ -401,7 +401,7 @@
//! Additional note: the inserted node is splayed
static void push_front(const node_ptr & header, const node_ptr & new_node)
{
- bstree_algorithms::push_front(header, new_node);
+ bstree_algo::push_front(header, new_node);
splay_up(new_node, header);
}
@@ -413,7 +413,7 @@
,KeyNodePtrCompare comp, insert_commit_data &commit_data)
{
splay_down(header, key, comp);
- return bstree_algorithms::insert_unique_check(header, key, comp, commit_data);
+ return bstree_algo::insert_unique_check(header, key, comp, commit_data);
}
//! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_check(const const_node_ptr&,const node_ptr&,const KeyType&,KeyNodePtrCompare,insert_commit_data&)
@@ -424,7 +424,7 @@
,KeyNodePtrCompare comp, insert_commit_data &commit_data)
{
splay_down(header, key, comp);
- return bstree_algorithms::insert_unique_check(header, hint, key, comp, commit_data);
+ return bstree_algo::insert_unique_check(header, hint, key, comp, commit_data);
}
#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
@@ -513,7 +513,7 @@
if(NodeTraits::get_left(t) == node_ptr() )
break;
if(comp(key, NodeTraits::get_left(t))){
- t = bstree_algorithms::rotate_right(t);
+ t = bstree_algo::rotate_right(t);
if(NodeTraits::get_left(t) == node_ptr())
break;
@@ -535,7 +535,7 @@
break;
if(comp(NodeTraits::get_right(t), key)){
- t = bstree_algorithms::rotate_left( t );
+ t = bstree_algo::rotate_left( t );
if(NodeTraits::get_right(t) == node_ptr() )
break;
@@ -628,7 +628,7 @@
node_ptr g = NodeTraits::get_parent(p);
//Test if g is header before breaking tree
//invariants that would make is_header invalid
- bool g_is_header = bstree_algorithms::is_header(g);
+ bool g_is_header = bstree_algo::is_header(g);
if(NodeTraits::get_left(p) == n){
NodeTraits::set_left(p, NodeTraits::get_right(n));
Modified: trunk/boost/intrusive/treap.hpp
==============================================================================
--- trunk/boost/intrusive/treap.hpp Mon Jul 29 17:41:48 2013 (r85170)
+++ trunk/boost/intrusive/treap.hpp 2013-07-29 17:43:03 EDT (Mon, 29 Jul 2013) (r85171)
@@ -542,12 +542,12 @@
, KeyValuePrioCompare key_value_pcomp, insert_commit_data &commit_data)
{
detail::key_nodeptr_comp<KeyValueCompare, real_value_traits>
- comp(key_value_comp, &this->get_real_value_traits());
+ ocomp(key_value_comp, &this->get_real_value_traits());
detail::key_nodeptr_comp<KeyValuePrioCompare, real_value_traits>
pcomp(key_value_pcomp, &this->get_real_value_traits());
std::pair<node_ptr, bool> ret =
(node_algorithms::insert_unique_check
- (this->tree_type::header_ptr(), key, comp, pcomp, commit_data));
+ (this->tree_type::header_ptr(), key, ocomp, pcomp, commit_data));
return std::pair<iterator, bool>(iterator(ret.first, this->real_value_traits_ptr()), ret.second);
}
@@ -594,12 +594,12 @@
, insert_commit_data &commit_data)
{
detail::key_nodeptr_comp<KeyValueCompare, real_value_traits>
- comp(key_value_comp, &this->get_real_value_traits());
+ ocomp(key_value_comp, &this->get_real_value_traits());
detail::key_nodeptr_comp<KeyValuePrioCompare, real_value_traits>
pcomp(key_value_pcomp, &this->get_real_value_traits());
std::pair<node_ptr, bool> ret =
(node_algorithms::insert_unique_check
- (this->tree_type::header_ptr(), hint.pointed_node(), key, comp, pcomp, commit_data));
+ (this->tree_type::header_ptr(), hint.pointed_node(), key, ocomp, pcomp, commit_data));
return std::pair<iterator, bool>(iterator(ret.first, this->real_value_traits_ptr()), ret.second);
}
Modified: trunk/boost/intrusive/treap_algorithms.hpp
==============================================================================
--- trunk/boost/intrusive/treap_algorithms.hpp Mon Jul 29 17:41:48 2013 (r85170)
+++ trunk/boost/intrusive/treap_algorithms.hpp 2013-07-29 17:43:03 EDT (Mon, 29 Jul 2013) (r85171)
@@ -81,6 +81,8 @@
/// @cond
private:
+ typedef bstree_algorithms<NodeTraits> bstree_algo;
+
class rerotate_on_destroy
{
rerotate_on_destroy& operator=(const rerotate_on_destroy&);
@@ -113,16 +115,14 @@
; p_parent = NodeTraits::get_parent(p)){
//Check if left child
if(p == NodeTraits::get_left(p_parent)){
- bstree_algorithms::rotate_right(p_parent, header);
+ bstree_algo::rotate_right(p_parent, header);
}
else{ //Right child
- bstree_algorithms::rotate_left(p_parent, header);
+ bstree_algo::rotate_left(p_parent, header);
}
}
}
- typedef bstree_algorithms<NodeTraits> bstree_algorithms;
-
/// @endcond
public:
@@ -130,7 +130,7 @@
//! filled by insert_unique_check
struct insert_commit_data
/// @cond
- : public bstree_algorithms::insert_commit_data
+ : public bstree_algo::insert_commit_data
/// @endcond
{
/// @cond
@@ -171,7 +171,7 @@
{
node_ptr x = NodeTraits::get_parent(node);
if(x){
- while(!bstree_algorithms::is_header(x))
+ while(!bstree_algo::is_header(x))
x = NodeTraits::get_parent(x);
erase(x, node, pcomp);
}
@@ -205,7 +205,7 @@
static node_ptr erase(const node_ptr & header, const node_ptr & z, NodePtrPriorityCompare pcomp)
{
rebalance_for_erasure(header, z, pcomp);
- bstree_algorithms::erase(header, z);
+ bstree_algo::erase(header, z);
return z;
}
@@ -270,7 +270,7 @@
(const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp, NodePtrPriorityCompare pcomp)
{
insert_commit_data commit_data;
- bstree_algorithms::insert_equal_upper_bound_check(h, new_node, comp, commit_data);
+ bstree_algo::insert_equal_upper_bound_check(h, new_node, comp, commit_data);
rebalance_check_and_commit(h, new_node, pcomp, commit_data);
return new_node;
}
@@ -295,7 +295,7 @@
(const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp, NodePtrPriorityCompare pcomp)
{
insert_commit_data commit_data;
- bstree_algorithms::insert_equal_lower_bound_check(h, new_node, comp, commit_data);
+ bstree_algo::insert_equal_lower_bound_check(h, new_node, comp, commit_data);
rebalance_check_and_commit(h, new_node, pcomp, commit_data);
return new_node;
}
@@ -323,7 +323,7 @@
(const node_ptr & h, const node_ptr & hint, const node_ptr & new_node, NodePtrCompare comp, NodePtrPriorityCompare pcomp)
{
insert_commit_data commit_data;
- bstree_algorithms::insert_equal_check(h, hint, new_node, comp, commit_data);
+ bstree_algo::insert_equal_check(h, hint, new_node, comp, commit_data);
rebalance_check_and_commit(h, new_node, pcomp, commit_data);
return new_node;
}
@@ -351,7 +351,7 @@
(const node_ptr & header, const node_ptr & pos, const node_ptr & new_node, NodePtrPriorityCompare pcomp)
{
insert_commit_data commit_data;
- bstree_algorithms::insert_before_check(header, pos, commit_data);
+ bstree_algo::insert_before_check(header, pos, commit_data);
rebalance_check_and_commit(header, new_node, pcomp, commit_data);
return new_node;
}
@@ -377,7 +377,7 @@
static void push_back(const node_ptr & header, const node_ptr & new_node, NodePtrPriorityCompare pcomp)
{
insert_commit_data commit_data;
- bstree_algorithms::push_back_check(header, commit_data);
+ bstree_algo::push_back_check(header, commit_data);
rebalance_check_and_commit(header, new_node, pcomp, commit_data);
}
@@ -402,7 +402,7 @@
static void push_front(const node_ptr & header, const node_ptr & new_node, NodePtrPriorityCompare pcomp)
{
insert_commit_data commit_data;
- bstree_algorithms::push_front_check(header, commit_data);
+ bstree_algo::push_front_check(header, commit_data);
rebalance_check_and_commit(header, new_node, pcomp, commit_data);
}
@@ -447,7 +447,7 @@
,insert_commit_data &commit_data)
{
std::pair<node_ptr, bool> ret =
- bstree_algorithms::insert_unique_check(header, key, comp, commit_data);
+ bstree_algo::insert_unique_check(header, key, comp, commit_data);
if(ret.second)
rebalance_after_insertion_check(header, commit_data.node, key, pcomp, commit_data.rotations);
return ret;
@@ -498,7 +498,7 @@
,KeyNodePtrCompare comp, KeyNodePtrPrioCompare pcomp, insert_commit_data &commit_data)
{
std::pair<node_ptr, bool> ret =
- bstree_algorithms::insert_unique_check(header, hint, key, comp, commit_data);
+ bstree_algo::insert_unique_check(header, hint, key, comp, commit_data);
if(ret.second)
rebalance_after_insertion_check(header, commit_data.node, key, pcomp, commit_data.rotations);
return ret;
@@ -524,7 +524,7 @@
static void insert_unique_commit
(const node_ptr & header, const node_ptr & new_node, const insert_commit_data &commit_data)
{
- bstree_algorithms::insert_unique_commit(header, new_node, commit_data);
+ bstree_algo::insert_unique_commit(header, new_node, commit_data);
rebalance_after_insertion_commit(header, new_node, commit_data.rotations);
}
@@ -547,10 +547,10 @@
node_ptr z_right = NodeTraits::get_right(z);
while(z_left || z_right){
if(!z_right || (z_left && pcomp(z_left, z_right))){
- bstree_algorithms::rotate_right(z, header);
+ bstree_algo::rotate_right(z, header);
}
else{
- bstree_algorithms::rotate_left(z, header);
+ bstree_algo::rotate_left(z, header);
}
++n;
z_left = NodeTraits::get_left(z);
@@ -565,7 +565,7 @@
{
rebalance_after_insertion_check(h, commit_data.node, new_node, pcomp, commit_data.rotations);
//No-throw
- bstree_algorithms::insert_unique_commit(h, new_node, commit_data);
+ bstree_algo::insert_unique_commit(h, new_node, commit_data);
rebalance_after_insertion_commit(h, new_node, commit_data.rotations);
}
@@ -594,10 +594,10 @@
; p_parent = NodeTraits::get_parent(p)){
//Check if left child
if(p == NodeTraits::get_left(p_parent)){
- bstree_algorithms::rotate_right(p_parent, header);
+ bstree_algo::rotate_right(p_parent, header);
}
else{ //Right child
- bstree_algorithms::rotate_left(p_parent, header);
+ bstree_algo::rotate_left(p_parent, header);
}
}
}
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk