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.hpp103
1 files changed, 83 insertions, 20 deletions
diff --git a/boost/intrusive/bstree_algorithms.hpp b/boost/intrusive/bstree_algorithms.hpp
index dcb7e5c4ff..e8caee0c94 100644
--- a/boost/intrusive/bstree_algorithms.hpp
+++ b/boost/intrusive/bstree_algorithms.hpp
@@ -63,14 +63,16 @@ struct bstree_node_checker
struct return_type
: public base_checker_t::return_type
{
- return_type() : min_key_node_ptr(const_node_ptr()), max_key_node_ptr(const_node_ptr()), node_count(0) {}
+ BOOST_INTRUSIVE_FORCEINLINE return_type()
+ : min_key_node_ptr(const_node_ptr()), max_key_node_ptr(const_node_ptr()), node_count(0)
+ {}
const_node_ptr min_key_node_ptr;
const_node_ptr max_key_node_ptr;
size_t node_count;
};
- bstree_node_checker(const NodePtrCompare& comp, ExtraChecker extra_checker)
+ BOOST_INTRUSIVE_FORCEINLINE bstree_node_checker(const NodePtrCompare& comp, ExtraChecker extra_checker)
: base_checker_t(extra_checker), comp_(comp)
{}
@@ -182,14 +184,14 @@ class bstree_algorithms : public bstree_algorithms_base<NodeTraits>
template<class Disposer>
struct dispose_subtree_disposer
{
- dispose_subtree_disposer(Disposer &disp, const node_ptr & subtree)
+ BOOST_INTRUSIVE_FORCEINLINE dispose_subtree_disposer(Disposer &disp, const node_ptr & subtree)
: disposer_(&disp), subtree_(subtree)
{}
- void release()
+ BOOST_INTRUSIVE_FORCEINLINE void release()
{ disposer_ = 0; }
- ~dispose_subtree_disposer()
+ BOOST_INTRUSIVE_FORCEINLINE ~dispose_subtree_disposer()
{
if(disposer_){
dispose_subtree(subtree_, *disposer_);
@@ -209,7 +211,7 @@ class bstree_algorithms : public bstree_algorithms_base<NodeTraits>
//! <b>Complexity</b>: Constant time.
//!
//! <b>Throws</b>: Nothing.
- static node_ptr begin_node(const const_node_ptr & header)
+ BOOST_INTRUSIVE_FORCEINLINE static node_ptr begin_node(const const_node_ptr & header)
{ return node_traits::get_left(header); }
//! <b>Requires</b>: 'header' is the header node of a tree.
@@ -219,7 +221,7 @@ class bstree_algorithms : public bstree_algorithms_base<NodeTraits>
//! <b>Complexity</b>: Constant time.
//!
//! <b>Throws</b>: Nothing.
- static node_ptr end_node(const const_node_ptr & header)
+ BOOST_INTRUSIVE_FORCEINLINE static node_ptr end_node(const const_node_ptr & header)
{ return detail::uncast(header); }
//! <b>Requires</b>: 'header' is the header node of a tree.
@@ -229,7 +231,7 @@ class bstree_algorithms : public bstree_algorithms_base<NodeTraits>
//! <b>Complexity</b>: Constant time.
//!
//! <b>Throws</b>: Nothing.
- static node_ptr root_node(const const_node_ptr & header)
+ BOOST_INTRUSIVE_FORCEINLINE static node_ptr root_node(const const_node_ptr & header)
{
node_ptr p = node_traits::get_parent(header);
return p ? p : detail::uncast(header);
@@ -243,7 +245,7 @@ class bstree_algorithms : public bstree_algorithms_base<NodeTraits>
//! <b>Complexity</b>: Constant time.
//!
//! <b>Throws</b>: Nothing.
- static bool unique(const const_node_ptr & node)
+ BOOST_INTRUSIVE_FORCEINLINE static bool unique(const const_node_ptr & node)
{ return !NodeTraits::get_parent(node); }
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
@@ -443,7 +445,7 @@ class bstree_algorithms : public bstree_algorithms_base<NodeTraits>
//! new_node is not equivalent to node_to_be_replaced according to the
//! ordering rules. This function is faster than erasing and inserting
//! the node, since no rebalancing and comparison is needed. Experimental function
- static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & new_node)
+ BOOST_INTRUSIVE_FORCEINLINE static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & new_node)
{
if(node_to_be_replaced == new_node)
return;
@@ -554,7 +556,7 @@ class bstree_algorithms : public bstree_algorithms_base<NodeTraits>
//! <b>Throws</b>: Nothing.
//!
//! <b>Nodes</b>: If node is inserted in a tree, this function corrupts the tree.
- static void init(const node_ptr & node)
+ BOOST_INTRUSIVE_FORCEINLINE static void init(const node_ptr & node)
{
NodeTraits::set_parent(node, node_ptr());
NodeTraits::set_left(node, node_ptr());
@@ -566,7 +568,7 @@ class bstree_algorithms : public bstree_algorithms_base<NodeTraits>
//! <b>Complexity</b>: Constant.
//!
//! <b>Throws</b>: Nothing.
- static bool inited(const const_node_ptr & node)
+ BOOST_INTRUSIVE_FORCEINLINE static bool inited(const const_node_ptr & node)
{
return !NodeTraits::get_parent(node) &&
!NodeTraits::get_left(node) &&
@@ -583,7 +585,7 @@ class bstree_algorithms : public bstree_algorithms_base<NodeTraits>
//! <b>Throws</b>: Nothing.
//!
//! <b>Nodes</b>: If node is inserted in a tree, this function corrupts the tree.
- static void init_header(const node_ptr & header)
+ BOOST_INTRUSIVE_FORCEINLINE static void init_header(const node_ptr & header)
{
NodeTraits::set_parent(header, node_ptr());
NodeTraits::set_left(header, header);
@@ -865,7 +867,7 @@ class bstree_algorithms : public bstree_algorithms_base<NodeTraits>
//!
//! <b>Throws</b>: If "comp" throws.
template<class KeyType, class KeyNodePtrCompare>
- static std::pair<node_ptr, node_ptr> equal_range
+ BOOST_INTRUSIVE_FORCEINLINE static std::pair<node_ptr, node_ptr> equal_range
(const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp)
{
return bounded_range(header, key, key, comp, true, true);
@@ -909,7 +911,7 @@ class bstree_algorithms : public bstree_algorithms_base<NodeTraits>
//!
//! <b>Throws</b>: If "comp" throws.
template<class KeyType, class KeyNodePtrCompare>
- static node_ptr lower_bound
+ BOOST_INTRUSIVE_FORCEINLINE static node_ptr lower_bound
(const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp)
{
return lower_bound_loop(NodeTraits::get_parent(header), detail::uncast(header), key, comp);
@@ -927,7 +929,7 @@ class bstree_algorithms : public bstree_algorithms_base<NodeTraits>
//!
//! <b>Throws</b>: If "comp" throws.
template<class KeyType, class KeyNodePtrCompare>
- static node_ptr upper_bound
+ BOOST_INTRUSIVE_FORCEINLINE static node_ptr upper_bound
(const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp)
{
return upper_bound_loop(NodeTraits::get_parent(header), detail::uncast(header), key, comp);
@@ -950,7 +952,7 @@ class bstree_algorithms : public bstree_algorithms_base<NodeTraits>
//! <b>Notes</b>: This function has only sense if a "insert_unique_check" has been
//! previously executed to fill "commit_data". No value should be inserted or
//! erased between the "insert_check" and "insert_commit" calls.
- static void insert_unique_commit
+ BOOST_INTRUSIVE_FORCEINLINE static void insert_unique_commit
(const node_ptr & header, const node_ptr & new_value, const insert_commit_data &commit_data)
{ return insert_commit(header, new_value, commit_data); }
@@ -1311,12 +1313,49 @@ class bstree_algorithms : public bstree_algorithms_base<NodeTraits>
//! <b>Complexity</b>: Amortized constant time.
//!
//! <b>Throws</b>: Nothing.
- static void erase(const node_ptr & header, const node_ptr & z)
+ BOOST_INTRUSIVE_FORCEINLINE static void erase(const node_ptr & header, const node_ptr & z)
{
data_for_rebalance ignored;
erase(header, z, ignored);
}
+ //! <b>Requires</b>: header1 and header2 must be the headers of trees tree1 and tree2
+ //! respectively, z a non-header node of tree1. NodePtrCompare is the comparison
+ //! function of tree1..
+ //!
+ //! <b>Effects</b>: Transfers node "z" from tree1 to tree2 if tree1 does not contain
+ //! a node that is equivalent to z.
+ //!
+ //! <b>Returns</b>: True if the node was trasferred, false otherwise.
+ //!
+ //! <b>Complexity</b>: Logarithmic.
+ //!
+ //! <b>Throws</b>: If the comparison throws.
+ template<class NodePtrCompare>
+ BOOST_INTRUSIVE_FORCEINLINE static bool transfer_unique
+ (const node_ptr & header1, NodePtrCompare comp, const node_ptr &header2, const node_ptr & z)
+ {
+ data_for_rebalance ignored;
+ return transfer_unique(header1, comp, header2, z, ignored);
+ }
+
+ //! <b>Requires</b>: header1 and header2 must be the headers of trees tree1 and tree2
+ //! respectively, z a non-header node of tree1. NodePtrCompare is the comparison
+ //! function of tree1..
+ //!
+ //! <b>Effects</b>: Transfers node "z" from tree1 to tree2.
+ //!
+ //! <b>Complexity</b>: Logarithmic.
+ //!
+ //! <b>Throws</b>: If the comparison throws.
+ template<class NodePtrCompare>
+ BOOST_INTRUSIVE_FORCEINLINE static void transfer_equal
+ (const node_ptr & header1, NodePtrCompare comp, const node_ptr &header2, const node_ptr & z)
+ {
+ data_for_rebalance ignored;
+ transfer_equal(header1, comp, header2, z, ignored);
+ }
+
//! <b>Requires</b>: node is a tree node but not the header.
//!
//! <b>Effects</b>: Unlinks the node and rebalances the tree.
@@ -1431,6 +1470,30 @@ class bstree_algorithms : public bstree_algorithms_base<NodeTraits>
}
protected:
+
+ template<class NodePtrCompare>
+ static bool transfer_unique
+ (const node_ptr & header1, NodePtrCompare comp, const node_ptr &header2, const node_ptr & z, data_for_rebalance &info)
+ {
+ insert_commit_data commit_data;
+ bool const transferable = insert_unique_check(header1, z, comp, commit_data).second;
+ if(transferable){
+ erase(header2, z, info);
+ insert_commit(header1, z, commit_data);
+ }
+ return transferable;
+ }
+
+ template<class NodePtrCompare>
+ static void transfer_equal
+ (const node_ptr & header1, NodePtrCompare comp, const node_ptr &header2, const node_ptr & z, data_for_rebalance &info)
+ {
+ insert_commit_data commit_data;
+ insert_equal_upper_bound_check(header1, z, comp, commit_data);
+ erase(header2, z, info);
+ insert_commit(header1, z, commit_data);
+ }
+
static void erase(const node_ptr & header, const node_ptr & z, data_for_rebalance &info)
{
node_ptr y(z);
@@ -1563,7 +1626,7 @@ class bstree_algorithms : public bstree_algorithms_base<NodeTraits>
//! <b>Complexity</b>: Constant.
//!
//! <b>Throws</b>: Nothing.
- static bool is_left_child(const node_ptr & p)
+ BOOST_INTRUSIVE_FORCEINLINE static bool is_left_child(const node_ptr & p)
{ return NodeTraits::get_left(NodeTraits::get_parent(p)) == p; }
//! <b>Requires</b>: p is a node of a tree.
@@ -1573,7 +1636,7 @@ class bstree_algorithms : public bstree_algorithms_base<NodeTraits>
//! <b>Complexity</b>: Constant.
//!
//! <b>Throws</b>: Nothing.
- static bool is_right_child(const node_ptr & p)
+ BOOST_INTRUSIVE_FORCEINLINE static bool is_right_child(const node_ptr & p)
{ return NodeTraits::get_right(NodeTraits::get_parent(p)) == p; }
static void insert_before_check
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-05 15:51:29 +0000