summaryrefslogtreecommitdiff
path: root/boost/intrusive/bstree_algorithms.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'boost/intrusive/bstree_algorithms.hpp')
-rw-r--r--boost/intrusive/bstree_algorithms.hpp236
1 files changed, 72 insertions, 164 deletions
diff --git a/boost/intrusive/bstree_algorithms.hpp b/boost/intrusive/bstree_algorithms.hpp
index de5445ec52..f7e915e914 100644
--- a/boost/intrusive/bstree_algorithms.hpp
+++ b/boost/intrusive/bstree_algorithms.hpp
@@ -13,18 +13,20 @@
#ifndef BOOST_INTRUSIVE_BSTREE_ALGORITHMS_HPP
#define BOOST_INTRUSIVE_BSTREE_ALGORITHMS_HPP
-#if defined(_MSC_VER)
-# pragma once
-#endif
-
#include <cstddef>
#include <boost/intrusive/detail/config_begin.hpp>
#include <boost/intrusive/intrusive_fwd.hpp>
+#include <boost/intrusive/detail/bstree_algorithms_base.hpp>
#include <boost/intrusive/detail/assert.hpp>
#include <boost/intrusive/detail/uncast.hpp>
#include <boost/intrusive/detail/math.hpp>
#include <boost/intrusive/detail/algo_type.hpp>
-#include <utility>
+
+#include <boost/intrusive/detail/minimal_pair_header.hpp>
+
+#if defined(BOOST_HAS_PRAGMA_ONCE)
+# pragma once
+#endif
namespace boost {
namespace intrusive {
@@ -167,7 +169,7 @@ struct bstree_node_checker
//!
//! <tt>static void set_right(node_ptr n, node_ptr right);</tt>
template<class NodeTraits>
-class bstree_algorithms
+class bstree_algorithms : public bstree_algorithms_base<NodeTraits>
{
public:
typedef typename NodeTraits::node node;
@@ -178,7 +180,8 @@ class bstree_algorithms
typedef data_for_rebalance_t<node_ptr> data_for_rebalance;
/// @cond
-
+ typedef bstree_algorithms<NodeTraits> this_type;
+ typedef bstree_algorithms_base<NodeTraits> base_type;
private:
template<class Disposer>
struct dispose_subtree_disposer
@@ -247,6 +250,7 @@ class bstree_algorithms
static bool unique(const const_node_ptr & node)
{ return !NodeTraits::get_parent(node); }
+ #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
//! <b>Requires</b>: 'node' is a node of the tree or a header node.
//!
//! <b>Effects</b>: Returns the header of the tree.
@@ -254,42 +258,8 @@ class bstree_algorithms
//! <b>Complexity</b>: Logarithmic.
//!
//! <b>Throws</b>: Nothing.
- static node_ptr get_header(const const_node_ptr & node)
- {
- node_ptr n(detail::uncast(node));
- node_ptr p(NodeTraits::get_parent(node));
- //If p is null, then n is the header of an empty tree
- if(p){
- //Non-empty tree, check if n is neither root nor header
- node_ptr pp(NodeTraits::get_parent(p));
- //If granparent is not equal to n, then n is neither root nor header,
- //the try the fast path
- if(n != pp){
- do{
- n = p;
- p = pp;
- pp = NodeTraits::get_parent(pp);
- }while(n != pp);
- n = p;
- }
- //Check if n is root or header when size() > 0
- else if(!is_header(n)){
- n = p;
- }
- }
- return n;
- /*
- node_ptr h = detail::uncast(node);
- node_ptr p = NodeTraits::get_parent(node);
- if(p){
- while(!is_header(p))
- p = NodeTraits::get_parent(p);
- return p;
- }
- else{
- return h;
- }*/
- }
+ static node_ptr get_header(const const_node_ptr & node);
+ #endif
//! <b>Requires</b>: node1 and node2 can't be header nodes
//! of two trees.
@@ -311,7 +281,7 @@ class bstree_algorithms
if(node1 == node2)
return;
- node_ptr header1(get_header(node1)), header2(get_header(node2));
+ node_ptr header1(base_type::get_header(node1)), header2(base_type::get_header(node2));
swap_nodes(node1, header1, node2, header2);
}
@@ -481,7 +451,7 @@ class bstree_algorithms
{
if(node_to_be_replaced == new_node)
return;
- replace_node(node_to_be_replaced, get_header(node_to_be_replaced), new_node);
+ replace_node(node_to_be_replaced, base_type::get_header(node_to_be_replaced), new_node);
}
//! <b>Requires</b>: node_to_be_replaced must be inserted in a tree
@@ -541,6 +511,7 @@ class bstree_algorithms
}
}
+ #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
//! <b>Requires</b>: 'node' is a node from the tree except the header.
//!
//! <b>Effects</b>: Returns the next node of the tree.
@@ -548,22 +519,7 @@ class bstree_algorithms
//! <b>Complexity</b>: Average constant time.
//!
//! <b>Throws</b>: Nothing.
- static node_ptr next_node(const node_ptr & node)
- {
- node_ptr const n_right(NodeTraits::get_right(node));
- if(n_right){
- return minimum(n_right);
- }
- else {
- node_ptr n(node);
- node_ptr p(NodeTraits::get_parent(n));
- while(n == NodeTraits::get_right(p)){
- n = p;
- p = NodeTraits::get_parent(p);
- }
- return NodeTraits::get_right(n) != p ? p : n;
- }
- }
+ static node_ptr next_node(const node_ptr & node);
//! <b>Requires</b>: 'node' is a node from the tree except the leftmost node.
//!
@@ -572,25 +528,7 @@ class bstree_algorithms
//! <b>Complexity</b>: Average constant time.
//!
//! <b>Throws</b>: Nothing.
- static node_ptr prev_node(const node_ptr & node)
- {
- if(is_header(node)){
- return NodeTraits::get_right(node);
- //return maximum(NodeTraits::get_parent(node));
- }
- else if(NodeTraits::get_left(node)){
- return maximum(NodeTraits::get_left(node));
- }
- else {
- node_ptr p(node);
- node_ptr x = NodeTraits::get_parent(p);
- while(p == NodeTraits::get_left(x)){
- p = x;
- x = NodeTraits::get_parent(x);
- }
- return x;
- }
- }
+ static node_ptr prev_node(const node_ptr & node);
//! <b>Requires</b>: 'node' is a node of a tree but not the header.
//!
@@ -599,15 +537,7 @@ class bstree_algorithms
//! <b>Complexity</b>: Logarithmic to the size of the subtree.
//!
//! <b>Throws</b>: Nothing.
- static node_ptr minimum(node_ptr node)
- {
- for(node_ptr p_left = NodeTraits::get_left(node)
- ;p_left
- ;p_left = NodeTraits::get_left(node)){
- node = p_left;
- }
- return node;
- }
+ static node_ptr minimum(node_ptr node);
//! <b>Requires</b>: 'node' is a node of a tree but not the header.
//!
@@ -616,15 +546,8 @@ class bstree_algorithms
//! <b>Complexity</b>: Logarithmic to the size of the subtree.
//!
//! <b>Throws</b>: Nothing.
- static node_ptr maximum(node_ptr node)
- {
- for(node_ptr p_right = NodeTraits::get_right(node)
- ;p_right
- ;p_right = NodeTraits::get_right(node)){
- node = p_right;
- }
- return node;
- }
+ static node_ptr maximum(node_ptr node);
+ #endif
//! <b>Requires</b>: 'node' must not be part of any tree.
//!
@@ -716,7 +639,7 @@ class bstree_algorithms
if (leftmost_right){
NodeTraits::set_parent(leftmost_right, leftmost_parent);
- NodeTraits::set_left(header, bstree_algorithms::minimum(leftmost_right));
+ NodeTraits::set_left(header, base_type::minimum(leftmost_right));
if (is_root)
NodeTraits::set_parent(header, leftmost_right);
@@ -747,7 +670,7 @@ class bstree_algorithms
node_ptr beg(begin_node(header));
node_ptr end(end_node(header));
std::size_t i = 0;
- for(;beg != end; beg = next_node(beg)) ++i;
+ for(;beg != end; beg = base_type::next_node(beg)) ++i;
return i;
}
@@ -800,6 +723,7 @@ class bstree_algorithms
}
}
+ #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
//! <b>Requires</b>: p is a node of a tree.
//!
//! <b>Effects</b>: Returns true if p is the header of the tree.
@@ -807,22 +731,8 @@ class bstree_algorithms
//! <b>Complexity</b>: Constant.
//!
//! <b>Throws</b>: Nothing.
- static bool is_header(const const_node_ptr & p)
- {
- node_ptr p_left (NodeTraits::get_left(p));
- node_ptr p_right(NodeTraits::get_right(p));
- if(!NodeTraits::get_parent(p) || //Header condition when empty tree
- (p_left && p_right && //Header always has leftmost and rightmost
- (p_left == p_right || //Header condition when only node
- (NodeTraits::get_parent(p_left) != p ||
- NodeTraits::get_parent(p_right) != p ))
- //When tree size > 1 headers can't be leftmost's
- //and rightmost's parent
- )){
- return true;
- }
- return false;
- }
+ static bool is_header(const const_node_ptr & p);
+ #endif
//! <b>Requires</b>: "header" must be the header node of a tree.
//! KeyNodePtrCompare is a function object that induces a strict weak
@@ -849,7 +759,7 @@ class bstree_algorithms
//! ordering compatible with the strict weak ordering used to create the
//! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs.
//! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
- //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
+ //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be true.
//!
//! <b>Effects</b>: Returns an a pair with the following criteria:
//!
@@ -892,7 +802,7 @@ class bstree_algorithms
x = NodeTraits::get_left(x);
}
else{
- //x is inside the bounded range( x >= lower_key && x <= upper_key),
+ //x is inside the bounded range(lower_key <= x <= upper_key),
//so we must split lower and upper searches
//
//Sanity check: if lower_key and upper_key are equal, then both left_closed and right_closed can't be false
@@ -940,7 +850,7 @@ class bstree_algorithms
std::size_t n = 0;
while(ret.first != ret.second){
++n;
- ret.first = next_node(ret.first);
+ ret.first = base_type::next_node(ret.first);
}
return n;
}
@@ -985,7 +895,7 @@ class bstree_algorithms
node_ptr const lb(lower_bound(header, key, comp));
std::pair<node_ptr, node_ptr> ret_ii(lb, lb);
if(lb != header && !comp(key, lb)){
- ret_ii.second = next_node(ret_ii.second);
+ ret_ii.second = base_type::next_node(ret_ii.second);
}
return ret_ii;
}
@@ -1087,7 +997,7 @@ class bstree_algorithms
(const const_node_ptr & header, const KeyType &key
,KeyNodePtrCompare comp, insert_commit_data &commit_data
#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
- , std::size_t *pdepth = 0
+ , std::size_t *pdepth = 0
#endif
)
{
@@ -1164,7 +1074,7 @@ class bstree_algorithms
(const const_node_ptr & header, const node_ptr &hint, const KeyType &key
,KeyNodePtrCompare comp, insert_commit_data &commit_data
#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
- , std::size_t *pdepth = 0
+ , std::size_t *pdepth = 0
#endif
)
{
@@ -1172,7 +1082,7 @@ class bstree_algorithms
if(hint == header || comp(key, hint)){
node_ptr prev(hint);
//Previous value should be less than the key
- if(hint == begin_node(header) || comp((prev = prev_node(hint)), key)){
+ if(hint == begin_node(header) || comp((prev = base_type::prev_node(hint)), key)){
commit_data.link_left = unique(header) || !NodeTraits::get_left(hint);
commit_data.node = commit_data.link_left ? hint : prev;
if(pdepth){
@@ -1203,7 +1113,7 @@ class bstree_algorithms
static node_ptr insert_equal
(const node_ptr & h, const node_ptr & hint, const node_ptr & new_node, NodePtrCompare comp
#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
- , std::size_t *pdepth = 0
+ , std::size_t *pdepth = 0
#endif
)
{
@@ -1229,7 +1139,7 @@ class bstree_algorithms
static node_ptr insert_equal_upper_bound
(const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp
#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
- , std::size_t *pdepth = 0
+ , std::size_t *pdepth = 0
#endif
)
{
@@ -1255,7 +1165,7 @@ class bstree_algorithms
static node_ptr insert_equal_lower_bound
(const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp
#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
- , std::size_t *pdepth = 0
+ , std::size_t *pdepth = 0
#endif
)
{
@@ -1282,7 +1192,7 @@ class bstree_algorithms
static node_ptr insert_before
(const node_ptr & header, const node_ptr & pos, const node_ptr & new_node
#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
- , std::size_t *pdepth = 0
+ , std::size_t *pdepth = 0
#endif
)
{
@@ -1308,7 +1218,7 @@ class bstree_algorithms
static void push_back
(const node_ptr & header, const node_ptr & new_node
#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
- , std::size_t *pdepth = 0
+ , std::size_t *pdepth = 0
#endif
)
{
@@ -1333,7 +1243,7 @@ class bstree_algorithms
static void push_front
(const node_ptr & header, const node_ptr & new_node
#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
- , std::size_t *pdepth = 0
+ , std::size_t *pdepth = 0
#endif
)
{
@@ -1375,7 +1285,7 @@ class bstree_algorithms
//! the nodes of the target tree. If "cloner" throws, the cloned target nodes
//! are disposed using <tt>void disposer(const node_ptr &)</tt>.
//!
- //! <b>Complexity</b>: Linear to the number of element of the source tree plus the.
+ //! <b>Complexity</b>: Linear to the number of element of the source tree plus the
//! number of elements of tree target tree when calling this function.
//!
//! <b>Throws</b>: If cloner functor throws. If this happens target nodes are disposed.
@@ -1422,7 +1332,7 @@ class bstree_algorithms
{
node_ptr x = NodeTraits::get_parent(node);
if(x){
- while(!is_header(x))
+ while(!base_type::is_header(x))
x = NodeTraits::get_parent(x);
erase(x, node);
}
@@ -1503,27 +1413,25 @@ class bstree_algorithms
template<class Checker>
static void check(const const_node_ptr& header, Checker checker, typename Checker::return_type& checker_return)
{
- const_node_ptr root_node_ptr = NodeTraits::get_parent(header);
- if (!root_node_ptr)
- {
- // check left&right header pointers
- BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_left(header) == header);
- BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_right(header) == header);
- }
- else
- {
- // check parent pointer of root node
- BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_parent(root_node_ptr) == header);
- // check subtree from root
- check_subtree(root_node_ptr, checker, checker_return);
- // check left&right header pointers
- const_node_ptr p = root_node_ptr;
- while (NodeTraits::get_left(p)) { p = NodeTraits::get_left(p); }
- BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_left(header) == p);
- p = root_node_ptr;
- while (NodeTraits::get_right(p)) { p = NodeTraits::get_right(p); }
- BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_right(header) == p);
- }
+ const_node_ptr root_node_ptr = NodeTraits::get_parent(header);
+ if (!root_node_ptr){
+ // check left&right header pointers
+ BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_left(header) == header);
+ BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_right(header) == header);
+ }
+ else{
+ // check parent pointer of root node
+ BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_parent(root_node_ptr) == header);
+ // check subtree from root
+ check_subtree(root_node_ptr, checker, checker_return);
+ // check left&right header pointers
+ const_node_ptr p = root_node_ptr;
+ while (NodeTraits::get_left(p)) { p = NodeTraits::get_left(p); }
+ BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_left(header) == p);
+ p = root_node_ptr;
+ while (NodeTraits::get_right(p)) { p = NodeTraits::get_right(p); }
+ BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_right(header) == p);
+ }
}
protected:
@@ -1543,7 +1451,7 @@ class bstree_algorithms
}
else{ //make y != z
// y = find z's successor
- y = bstree_algorithms::minimum(z_right);
+ y = base_type::minimum(z_right);
x = NodeTraits::get_right(y); // x might be null.
}
@@ -1573,14 +1481,14 @@ class bstree_algorithms
x_parent = y;
}
NodeTraits::set_parent(y, z_parent);
- bstree_algorithms::set_child(header, y, z_parent, z_is_leftchild);
+ this_type::set_child(header, y, z_parent, z_is_leftchild);
}
else { // z has zero or one child, x is one child (it can be null)
//Just link x to z's parent
x_parent = z_parent;
if(x)
NodeTraits::set_parent(x, z_parent);
- bstree_algorithms::set_child(header, x, z_parent, z_is_leftchild);
+ this_type::set_child(header, x, z_parent, z_is_leftchild);
//Now update leftmost/rightmost in case z was one of them
if(NodeTraits::get_left(header) == z){
@@ -1588,14 +1496,14 @@ class bstree_algorithms
BOOST_ASSERT(!z_left);
NodeTraits::set_left(header, !z_right ?
z_parent : // makes leftmost == header if z == root
- bstree_algorithms::minimum(z_right));
+ base_type::minimum(z_right));
}
if(NodeTraits::get_right(header) == z){
//z_right must be null because z is the rightmost
BOOST_ASSERT(!z_right);
NodeTraits::set_right(header, !z_left ?
z_parent : // makes rightmost == header if z == root
- bstree_algorithms::maximum(z_left));
+ base_type::maximum(z_left));
}
}
@@ -1676,13 +1584,13 @@ class bstree_algorithms
(const node_ptr &header, const node_ptr & pos
, insert_commit_data &commit_data
#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
- , std::size_t *pdepth = 0
+ , std::size_t *pdepth = 0
#endif
)
{
node_ptr prev(pos);
if(pos != NodeTraits::get_left(header))
- prev = prev_node(pos);
+ prev = base_type::prev_node(pos);
bool link_left = unique(header) || !NodeTraits::get_left(pos);
commit_data.link_left = link_left;
commit_data.node = link_left ? pos : prev;
@@ -1694,7 +1602,7 @@ class bstree_algorithms
static void push_back_check
(const node_ptr & header, insert_commit_data &commit_data
#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
- , std::size_t *pdepth = 0
+ , std::size_t *pdepth = 0
#endif
)
{
@@ -1709,7 +1617,7 @@ class bstree_algorithms
static void push_front_check
(const node_ptr & header, insert_commit_data &commit_data
#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
- , std::size_t *pdepth = 0
+ , std::size_t *pdepth = 0
#endif
)
{
@@ -1733,7 +1641,7 @@ class bstree_algorithms
if(hint == header || !comp(hint, new_node)){
node_ptr prev(hint);
if(hint == NodeTraits::get_left(header) ||
- !comp(new_node, (prev = prev_node(hint)))){
+ !comp(new_node, (prev = base_type::prev_node(hint)))){
bool link_left = unique(header) || !NodeTraits::get_left(hint);
commit_data.link_left = link_left;
commit_data.node = link_left ? hint : prev;
@@ -1894,7 +1802,7 @@ class bstree_algorithms
}
}
size = len;
- }
+ }
static void compress_subtree(node_ptr scanner, std::size_t count)
{
@@ -1945,7 +1853,7 @@ class bstree_algorithms
BOOST_INTRUSIVE_INVARIANT_ASSERT((!inited(node)));
node_ptr x = NodeTraits::get_parent(node);
if(x){
- while(!is_header(x)){
+ while(!base_type::is_header(x)){
x = NodeTraits::get_parent(x);
}
return x;