summaryrefslogtreecommitdiff
path: root/boost/intrusive
diff options
context:
space:
mode:
authorDongHun Kwak <dh0128.kwak@samsung.com>2016-10-06 01:41:18 (GMT)
committerDongHun Kwak <dh0128.kwak@samsung.com>2016-10-06 01:43:11 (GMT)
commitf763a99a501650eff2c60288aa6f10ef916d769e (patch)
tree02af7e13f9a38c888ebf340fe764cbe7dae99da9 /boost/intrusive
parent5cde13f21d36c7224b0e13d11c4b49379ae5210d (diff)
downloadboost-f763a99a501650eff2c60288aa6f10ef916d769e.zip
boost-f763a99a501650eff2c60288aa6f10ef916d769e.tar.gz
boost-f763a99a501650eff2c60288aa6f10ef916d769e.tar.bz2
Imported Upstream version 1.62.0upstream/1.62.0refs/changes/09/91109/1
Change-Id: I9d4c1ddb7b7d8f0069217ecc582700f9fda6dd4c Signed-off-by: DongHun Kwak <dh0128.kwak@samsung.com>
Diffstat (limited to 'boost/intrusive')
-rw-r--r--boost/intrusive/any_hook.hpp6
-rw-r--r--boost/intrusive/avl_set.hpp62
-rw-r--r--boost/intrusive/avl_set_hook.hpp6
-rw-r--r--boost/intrusive/avltree.hpp17
-rw-r--r--boost/intrusive/avltree_algorithms.hpp43
-rw-r--r--boost/intrusive/bs_set.hpp62
-rw-r--r--boost/intrusive/bs_set_hook.hpp6
-rw-r--r--boost/intrusive/bstree.hpp245
-rw-r--r--boost/intrusive/bstree_algorithms.hpp103
-rw-r--r--boost/intrusive/circular_list_algorithms.hpp22
-rw-r--r--boost/intrusive/circular_slist_algorithms.hpp12
-rw-r--r--boost/intrusive/detail/algo_type.hpp5
-rw-r--r--boost/intrusive/detail/any_node_and_algorithms.hpp14
-rw-r--r--boost/intrusive/detail/common_slist_algorithms.hpp14
-rw-r--r--boost/intrusive/detail/ebo_functor_holder.hpp2
-rw-r--r--boost/intrusive/detail/generic_hook.hpp16
-rw-r--r--boost/intrusive/detail/has_member_function_callable_with.hpp141
-rw-r--r--boost/intrusive/detail/key_nodeptr_comp.hpp110
-rw-r--r--boost/intrusive/detail/size_holder.hpp5
-rw-r--r--boost/intrusive/detail/tree_value_compare.hpp129
-rw-r--r--boost/intrusive/hashtable.hpp474
-rw-r--r--boost/intrusive/linear_slist_algorithms.hpp4
-rw-r--r--boost/intrusive/list.hpp6
-rw-r--r--boost/intrusive/list_hook.hpp6
-rw-r--r--boost/intrusive/options.hpp8
-rw-r--r--boost/intrusive/priority_compare.hpp19
-rw-r--r--boost/intrusive/rbtree.hpp17
-rw-r--r--boost/intrusive/rbtree_algorithms.hpp56
-rw-r--r--boost/intrusive/set.hpp62
-rw-r--r--boost/intrusive/set_hook.hpp6
-rw-r--r--boost/intrusive/sg_set.hpp59
-rw-r--r--boost/intrusive/sgtree.hpp76
-rw-r--r--boost/intrusive/sgtree_algorithms.hpp52
-rw-r--r--boost/intrusive/slist.hpp11
-rw-r--r--boost/intrusive/slist_hook.hpp11
-rw-r--r--boost/intrusive/splay_set.hpp62
-rw-r--r--boost/intrusive/splaytree.hpp17
-rw-r--r--boost/intrusive/splaytree_algorithms.hpp27
-rw-r--r--boost/intrusive/treap.hpp60
-rw-r--r--boost/intrusive/treap_algorithms.hpp28
-rw-r--r--boost/intrusive/treap_set.hpp62
-rw-r--r--boost/intrusive/unordered_set.hpp6
-rw-r--r--boost/intrusive/unordered_set_hook.hpp44
43 files changed, 1663 insertions, 530 deletions
diff --git a/boost/intrusive/any_hook.hpp b/boost/intrusive/any_hook.hpp
index 809507c..6d18781 100644
--- a/boost/intrusive/any_hook.hpp
+++ b/boost/intrusive/any_hook.hpp
@@ -48,7 +48,8 @@ struct make_any_base_hook
>::type packed_options;
typedef generic_hook
- < any_algorithms<typename packed_options::void_pointer>
+ < AnyAlgorithm
+ , any_node_traits<typename packed_options::void_pointer>
, typename packed_options::tag
, packed_options::link_mode
, AnyBaseHookId
@@ -153,7 +154,8 @@ struct make_any_member_hook
>::type packed_options;
typedef generic_hook
- < any_algorithms<typename packed_options::void_pointer>
+ < AnyAlgorithm
+ , any_node_traits<typename packed_options::void_pointer>
, member_tag
, packed_options::link_mode
, NoBaseHookId
diff --git a/boost/intrusive/avl_set.hpp b/boost/intrusive/avl_set.hpp
index 2c96204..d150140 100644
--- a/boost/intrusive/avl_set.hpp
+++ b/boost/intrusive/avl_set.hpp
@@ -26,6 +26,11 @@
namespace boost {
namespace intrusive {
+#if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
+template<class ValueTraits, class VoidOrKeyOfValue, class Compare, class SizeType, bool ConstantTimeSize, typename HeaderHolder>
+class avl_multiset_impl;
+#endif
+
//! The class template avl_set is an intrusive container, that mimics most of
//! the interface of std::set as described in the C++ standard.
//!
@@ -150,6 +155,15 @@ class avl_set_impl
//! @copydoc ::boost::intrusive::avltree::crend()const
const_reverse_iterator crend() const;
+ //! @copydoc ::boost::intrusive::avltree::root()
+ iterator root();
+
+ //! @copydoc ::boost::intrusive::avltree::root()const
+ const_iterator root() const;
+
+ //! @copydoc ::boost::intrusive::avltree::croot()const
+ const_iterator croot() const;
+
//! @copydoc ::boost::intrusive::avltree::container_from_end_iterator(iterator)
static avl_set_impl &container_from_end_iterator(iterator end_iterator);
@@ -399,6 +413,26 @@ class avl_set_impl
//! @copydoc ::boost::intrusive::avltree::remove_node
void remove_node(reference value);
+
+ //! @copydoc ::boost::intrusive::avltree::merge_unique
+ template<class ...Options2>
+ void merge(avl_set<T, Options2...> &source);
+
+ //! @copydoc ::boost::intrusive::avltree::merge_unique
+ template<class ...Options2>
+ void merge(avl_multiset<T, Options2...> &source);
+
+ #else
+
+ template<class Compare2>
+ void merge(avl_set_impl<ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, ConstantTimeSize, HeaderHolder> &source)
+ { return tree_type::merge_unique(source); }
+
+
+ template<class Compare2>
+ void merge(avl_multiset_impl<ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, ConstantTimeSize, HeaderHolder> &source)
+ { return tree_type::merge_unique(source); }
+
#endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
};
@@ -658,6 +692,15 @@ class avl_multiset_impl
//! @copydoc ::boost::intrusive::avltree::crend()const
const_reverse_iterator crend() const;
+ //! @copydoc ::boost::intrusive::avltree::root()
+ iterator root();
+
+ //! @copydoc ::boost::intrusive::avltree::root()const
+ const_iterator root() const;
+
+ //! @copydoc ::boost::intrusive::avltree::croot()const
+ const_iterator croot() const;
+
//! @copydoc ::boost::intrusive::avltree::container_from_end_iterator(iterator)
static avl_multiset_impl &container_from_end_iterator(iterator end_iterator);
@@ -865,6 +908,25 @@ class avl_multiset_impl
//! @copydoc ::boost::intrusive::avltree::remove_node
void remove_node(reference value);
+
+ //! @copydoc ::boost::intrusive::avltree::merge_equal
+ template<class ...Options2>
+ void merge(avl_multiset<T, Options2...> &source);
+
+ //! @copydoc ::boost::intrusive::avltree::merge_equal
+ template<class ...Options2>
+ void merge(avl_set<T, Options2...> &source);
+
+ #else
+
+ template<class Compare2>
+ void merge(avl_multiset_impl<ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, ConstantTimeSize, HeaderHolder> &source)
+ { return tree_type::merge_equal(source); }
+
+ template<class Compare2>
+ void merge(avl_set_impl<ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, ConstantTimeSize, HeaderHolder> &source)
+ { return tree_type::merge_equal(source); }
+
#endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
};
diff --git a/boost/intrusive/avl_set_hook.hpp b/boost/intrusive/avl_set_hook.hpp
index b61f95f..1871303 100644
--- a/boost/intrusive/avl_set_hook.hpp
+++ b/boost/intrusive/avl_set_hook.hpp
@@ -47,7 +47,8 @@ struct make_avl_set_base_hook
::type packed_options;
typedef generic_hook
- < avltree_algorithms<avltree_node_traits<typename packed_options::void_pointer, packed_options::optimize_size> >
+ < AvlTreeAlgorithms
+ , avltree_node_traits<typename packed_options::void_pointer, packed_options::optimize_size>
, typename packed_options::tag
, packed_options::link_mode
, AvlTreeBaseHookId
@@ -177,7 +178,8 @@ struct make_avl_set_member_hook
::type packed_options;
typedef generic_hook
- < avltree_algorithms<avltree_node_traits<typename packed_options::void_pointer, packed_options::optimize_size> >
+ < AvlTreeAlgorithms
+ , avltree_node_traits<typename packed_options::void_pointer, packed_options::optimize_size>
, member_tag
, packed_options::link_mode
, NoBaseHookId
diff --git a/boost/intrusive/avltree.hpp b/boost/intrusive/avltree.hpp
index 741d482..cdc9b75 100644
--- a/boost/intrusive/avltree.hpp
+++ b/boost/intrusive/avltree.hpp
@@ -189,6 +189,15 @@ class avltree_impl
//! @copydoc ::boost::intrusive::bstree::crend()const
const_reverse_iterator crend() const;
+ //! @copydoc ::boost::intrusive::bstree::root()
+ iterator root();
+
+ //! @copydoc ::boost::intrusive::bstree::root()const
+ const_iterator root() const;
+
+ //! @copydoc ::boost::intrusive::bstree::croot()const
+ const_iterator croot() const;
+
//! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(iterator)
static avltree_impl &container_from_end_iterator(iterator end_iterator);
@@ -427,6 +436,14 @@ class avltree_impl
//! @copydoc ::boost::intrusive::bstree::remove_node
void remove_node(reference value);
+ //! @copydoc ::boost::intrusive::bstree::merge_unique(bstree<T, Options2...>&)
+ template<class T, class ...Options2>
+ void merge_unique(avltree<T, Options2...> &);
+
+ //! @copydoc ::boost::intrusive::bstree::merge_equal(bstree<T, Options2...>&)
+ template<class T, class ...Options2>
+ void merge_equal(avltree<T, Options2...> &);
+
friend bool operator< (const avltree_impl &x, const avltree_impl &y);
friend bool operator==(const avltree_impl &x, const avltree_impl &y);
diff --git a/boost/intrusive/avltree_algorithms.hpp b/boost/intrusive/avltree_algorithms.hpp
index 60a981c..1459851 100644
--- a/boost/intrusive/avltree_algorithms.hpp
+++ b/boost/intrusive/avltree_algorithms.hpp
@@ -269,14 +269,35 @@ class avltree_algorithms
{
typename bstree_algo::data_for_rebalance info;
bstree_algo::erase(header, z, info);
- if(info.y != z){
- NodeTraits::set_balance(info.y, NodeTraits::get_balance(z));
- }
- //Rebalance avltree
- rebalance_after_erasure(header, info.x, info.x_parent);
+ rebalance_after_erasure(header, z, info);
return z;
}
+ //! @copydoc ::boost::intrusive::bstree_algorithms::transfer_unique
+ template<class NodePtrCompare>
+ static bool transfer_unique
+ (const node_ptr & header1, NodePtrCompare comp, const node_ptr &header2, const node_ptr & z)
+ {
+ typename bstree_algo::data_for_rebalance info;
+ bool const transferred = bstree_algo::transfer_unique(header1, comp, header2, z, info);
+ if(transferred){
+ rebalance_after_erasure(header2, z, info);
+ rebalance_after_insertion(header1, z);
+ }
+ return transferred;
+ }
+
+ //! @copydoc ::boost::intrusive::bstree_algorithms::transfer_equal
+ template<class NodePtrCompare>
+ static void transfer_equal
+ (const node_ptr & header1, NodePtrCompare comp, const node_ptr &header2, const node_ptr & z)
+ {
+ typename bstree_algo::data_for_rebalance info;
+ bstree_algo::transfer_equal(header1, comp, header2, z, info);
+ rebalance_after_erasure(header2, z, info);
+ rebalance_after_insertion(header1, z);
+ }
+
//! @copydoc ::boost::intrusive::bstree_algorithms::clone(const const_node_ptr&,const node_ptr&,Cloner,Disposer)
template <class Cloner, class Disposer>
static void clone
@@ -461,7 +482,17 @@ class avltree_algorithms
return true;
}
- static void rebalance_after_erasure(const node_ptr & header, node_ptr x, node_ptr x_parent)
+ static void rebalance_after_erasure
+ ( const node_ptr & header, const node_ptr &z, const typename bstree_algo::data_for_rebalance &info)
+ {
+ if(info.y != z){
+ NodeTraits::set_balance(info.y, NodeTraits::get_balance(z));
+ }
+ //Rebalance avltree
+ rebalance_after_erasure_restore_invariants(header, info.x, info.x_parent);
+ }
+
+ static void rebalance_after_erasure_restore_invariants(const node_ptr & header, node_ptr x, node_ptr x_parent)
{
for ( node_ptr root = NodeTraits::get_parent(header)
; x != root
diff --git a/boost/intrusive/bs_set.hpp b/boost/intrusive/bs_set.hpp
index 60f18a1..693b6d8 100644
--- a/boost/intrusive/bs_set.hpp
+++ b/boost/intrusive/bs_set.hpp
@@ -23,6 +23,11 @@
# pragma once
#endif
+#if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
+template<class ValueTraits, class VoidOrKeyOfValue, class Compare, class SizeType, bool ConstantTimeSize, typename HeaderHolder>
+class bs_multiset_impl;
+#endif
+
namespace boost {
namespace intrusive {
@@ -147,6 +152,15 @@ class bs_set_impl
//! @copydoc ::boost::intrusive::bstree::crend()const
const_reverse_iterator crend() const;
+ //! @copydoc ::boost::intrusive::bstree::root()
+ iterator root();
+
+ //! @copydoc ::boost::intrusive::bstree::root()const
+ const_iterator root() const;
+
+ //! @copydoc ::boost::intrusive::bstree::croot()const
+ const_iterator croot() const;
+
//! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(iterator)
static bs_set_impl &container_from_end_iterator(iterator end_iterator);
@@ -396,6 +410,26 @@ class bs_set_impl
//! @copydoc ::boost::intrusive::bstree::remove_node
void remove_node(reference value);
+
+ //! @copydoc ::boost::intrusive::bstree::merge_unique
+ template<class ...Options2>
+ void merge(bs_set<T, Options2...> &source);
+
+ //! @copydoc ::boost::intrusive::bstree::merge_unique
+ template<class ...Options2>
+ void merge(bs_multiset<T, Options2...> &source);
+
+ #else
+
+ template<class Compare2>
+ void merge(bs_set_impl<ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, ConstantTimeSize, HeaderHolder> &source)
+ { return tree_type::merge_unique(source); }
+
+
+ template<class Compare2>
+ void merge(bs_multiset_impl<ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, ConstantTimeSize, HeaderHolder> &source)
+ { return tree_type::merge_unique(source); }
+
#endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
};
@@ -654,6 +688,15 @@ class bs_multiset_impl
//! @copydoc ::boost::intrusive::bstree::crend()const
const_reverse_iterator crend() const;
+ //! @copydoc ::boost::intrusive::bstree::root()
+ iterator root();
+
+ //! @copydoc ::boost::intrusive::bstree::root()const
+ const_iterator root() const;
+
+ //! @copydoc ::boost::intrusive::bstree::croot()const
+ const_iterator croot() const;
+
//! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(iterator)
static bs_multiset_impl &container_from_end_iterator(iterator end_iterator);
@@ -861,6 +904,25 @@ class bs_multiset_impl
//! @copydoc ::boost::intrusive::bstree::remove_node
void remove_node(reference value);
+
+ //! @copydoc ::boost::intrusive::bstree::merge_equal
+ template<class ...Options2>
+ void merge(bs_multiset<T, Options2...> &source);
+
+ //! @copydoc ::boost::intrusive::bstree::merge_equal
+ template<class ...Options2>
+ void merge(bs_set<T, Options2...> &source);
+
+ #else
+
+ template<class Compare2>
+ void merge(bs_multiset_impl<ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, ConstantTimeSize, HeaderHolder> &source)
+ { return tree_type::merge_equal(source); }
+
+ template<class Compare2>
+ void merge(bs_set_impl<ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, ConstantTimeSize, HeaderHolder> &source)
+ { return tree_type::merge_equal(source); }
+
#endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
};
diff --git a/boost/intrusive/bs_set_hook.hpp b/boost/intrusive/bs_set_hook.hpp
index e96248b..a64c15a 100644
--- a/boost/intrusive/bs_set_hook.hpp
+++ b/boost/intrusive/bs_set_hook.hpp
@@ -47,7 +47,8 @@ struct make_bs_set_base_hook
::type packed_options;
typedef generic_hook
- < bstree_algorithms<tree_node_traits<typename packed_options::void_pointer> >
+ < BsTreeAlgorithms
+ , tree_node_traits<typename packed_options::void_pointer>
, typename packed_options::tag
, packed_options::link_mode
, BsTreeBaseHookId
@@ -176,7 +177,8 @@ struct make_bs_set_member_hook
::type packed_options;
typedef generic_hook
- < bstree_algorithms<tree_node_traits<typename packed_options::void_pointer> >
+ < BsTreeAlgorithms
+ , tree_node_traits<typename packed_options::void_pointer>
, member_tag
, packed_options::link_mode
, NoBaseHookId
diff --git a/boost/intrusive/bstree.hpp b/boost/intrusive/bstree.hpp
index 0fb9218..f2cdb42 100644
--- a/boost/intrusive/bstree.hpp
+++ b/boost/intrusive/bstree.hpp
@@ -105,7 +105,7 @@ struct bstbase3
struct holder_t : public ValueTraits
{
- explicit holder_t(const ValueTraits &vtraits)
+ BOOST_INTRUSIVE_FORCEINLINE explicit holder_t(const ValueTraits &vtraits)
: ValueTraits(vtraits)
{}
header_holder_type root;
@@ -121,34 +121,34 @@ struct bstbase3
return *base;
}
- bstbase3(const ValueTraits &vtraits)
+ BOOST_INTRUSIVE_FORCEINLINE bstbase3(const ValueTraits &vtraits)
: holder(vtraits)
{
node_algorithms::init_header(this->header_ptr());
}
- node_ptr header_ptr()
+ BOOST_INTRUSIVE_FORCEINLINE node_ptr header_ptr()
{ return holder.root.get_node(); }
- const_node_ptr header_ptr() const
+ BOOST_INTRUSIVE_FORCEINLINE const_node_ptr header_ptr() const
{ return holder.root.get_node(); }
- const value_traits &get_value_traits() const
+ BOOST_INTRUSIVE_FORCEINLINE const value_traits &get_value_traits() const
{ return this->holder; }
- value_traits &get_value_traits()
+ BOOST_INTRUSIVE_FORCEINLINE value_traits &get_value_traits()
{ return this->holder; }
typedef typename boost::intrusive::value_traits_pointers
<ValueTraits>::const_value_traits_ptr const_value_traits_ptr;
- const_value_traits_ptr priv_value_traits_ptr() const
+ BOOST_INTRUSIVE_FORCEINLINE const_value_traits_ptr priv_value_traits_ptr() const
{ return pointer_traits<const_value_traits_ptr>::pointer_to(this->get_value_traits()); }
iterator begin()
{ return iterator(node_algorithms::begin_node(this->header_ptr()), this->priv_value_traits_ptr()); }
- const_iterator begin() const
+ BOOST_INTRUSIVE_FORCEINLINE const_iterator begin() const
{ return cbegin(); }
const_iterator cbegin() const
@@ -157,37 +157,37 @@ struct bstbase3
iterator end()
{ return iterator(node_algorithms::end_node(this->header_ptr()), this->priv_value_traits_ptr()); }
- const_iterator end() const
+ BOOST_INTRUSIVE_FORCEINLINE const_iterator end() const
{ return cend(); }
- const_iterator cend() const
+ BOOST_INTRUSIVE_FORCEINLINE const_iterator cend() const
{ return const_iterator(node_algorithms::end_node(this->header_ptr()), this->priv_value_traits_ptr()); }
- iterator root()
+ BOOST_INTRUSIVE_FORCEINLINE iterator root()
{ return iterator(node_algorithms::root_node(this->header_ptr()), this->priv_value_traits_ptr()); }
- const_iterator root() const
+ BOOST_INTRUSIVE_FORCEINLINE const_iterator root() const
{ return croot(); }
- const_iterator croot() const
+ BOOST_INTRUSIVE_FORCEINLINE const_iterator croot() const
{ return const_iterator(node_algorithms::root_node(this->header_ptr()), this->priv_value_traits_ptr()); }
- reverse_iterator rbegin()
+ BOOST_INTRUSIVE_FORCEINLINE reverse_iterator rbegin()
{ return reverse_iterator(end()); }
- const_reverse_iterator rbegin() const
+ BOOST_INTRUSIVE_FORCEINLINE const_reverse_iterator rbegin() const
{ return const_reverse_iterator(end()); }
- const_reverse_iterator crbegin() const
+ BOOST_INTRUSIVE_FORCEINLINE const_reverse_iterator crbegin() const
{ return const_reverse_iterator(end()); }
- reverse_iterator rend()
+ BOOST_INTRUSIVE_FORCEINLINE reverse_iterator rend()
{ return reverse_iterator(begin()); }
- const_reverse_iterator rend() const
+ BOOST_INTRUSIVE_FORCEINLINE const_reverse_iterator rend() const
{ return const_reverse_iterator(begin()); }
- const_reverse_iterator crend() const
+ BOOST_INTRUSIVE_FORCEINLINE const_reverse_iterator crend() const
{ return const_reverse_iterator(begin()); }
void replace_node(iterator replace_this, reference with_this)
@@ -199,7 +199,7 @@ struct bstbase3
node_algorithms::init(replace_this.pointed_node());
}
- void rebalance()
+ BOOST_INTRUSIVE_FORCEINLINE void rebalance()
{ node_algorithms::rebalance(this->header_ptr()); }
iterator rebalance_subtree(iterator root)
@@ -223,7 +223,7 @@ struct bstbase3
const_iterator iterator_to(const_reference value) const
{ return const_iterator (this->get_value_traits().to_node_ptr(*pointer_traits<pointer>::const_cast_from(pointer_traits<const_pointer>::pointer_to(value))), this->priv_value_traits_ptr()); }
- static void init_node(reference value)
+ BOOST_INTRUSIVE_FORCEINLINE static void init_node(reference value)
{ node_algorithms::init(value_traits::to_node_ptr(value)); }
};
@@ -252,17 +252,18 @@ struct get_key_of_value<void, T>
typedef ::boost::intrusive::detail::identity<T> type;
};
-template<class T, class VoidOrKeyOfValue, class VoidOrKeyComp>
+template<class ValuePtr, class VoidOrKeyOfValue, class VoidOrKeyComp>
struct bst_key_types
{
+ typedef typename pointer_element<ValuePtr>::type value_type;
typedef typename get_key_of_value
- < VoidOrKeyOfValue, T>::type key_of_value;
- typedef typename key_of_value::type key_type;
+ < VoidOrKeyOfValue, value_type>::type key_of_value;
+ typedef typename key_of_value::type key_type;
typedef typename get_compare< VoidOrKeyComp
, key_type
- >::type key_compare;
+ >::type key_compare;
typedef tree_value_compare
- <key_type, T, key_compare, key_of_value> value_compare;
+ <ValuePtr, key_compare, key_of_value> value_compare;
};
template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, algo_types AlgoType, typename HeaderHolder>
@@ -271,15 +272,16 @@ struct bstbase2
//Use public inheritance to avoid MSVC bugs with closures
: public detail::ebo_functor_holder
< typename bst_key_types
- < typename ValueTraits::value_type
+ < typename ValueTraits::pointer
, VoidOrKeyOfValue
, VoidOrKeyComp
+
>::value_compare
>
, public bstbase3<ValueTraits, AlgoType, HeaderHolder>
{
typedef bstbase3<ValueTraits, AlgoType, HeaderHolder> treeheader_t;
- typedef bst_key_types< typename ValueTraits::value_type
+ typedef bst_key_types< typename ValueTraits::pointer
, VoidOrKeyOfValue
, VoidOrKeyComp> key_types;
typedef typename treeheader_t::value_traits value_traits;
@@ -311,17 +313,17 @@ struct bstbase2
typedef BOOST_INTRUSIVE_IMPDEF(typename pointer_traits<const_pointer>::difference_type) difference_type;
typedef typename node_algorithms::insert_commit_data insert_commit_data;
- value_compare value_comp() const
+ BOOST_INTRUSIVE_FORCEINLINE value_compare value_comp() const
{ return this->comp(); }
- key_compare key_comp() const
+ BOOST_INTRUSIVE_FORCEINLINE key_compare key_comp() const
{ return this->comp().key_comp(); }
//lower_bound
- iterator lower_bound(const key_type &key)
+ BOOST_INTRUSIVE_FORCEINLINE iterator lower_bound(const key_type &key)
{ return this->lower_bound(key, this->key_comp()); }
- const_iterator lower_bound(const key_type &key) const
+ BOOST_INTRUSIVE_FORCEINLINE const_iterator lower_bound(const key_type &key) const
{ return this->lower_bound(key, this->key_comp()); }
template<class KeyType, class KeyTypeKeyCompare>
@@ -339,7 +341,7 @@ struct bstbase2
}
//upper_bound
- iterator upper_bound(const key_type &key)
+ BOOST_INTRUSIVE_FORCEINLINE iterator upper_bound(const key_type &key)
{ return this->upper_bound(key, this->key_comp()); }
template<class KeyType, class KeyTypeKeyCompare>
@@ -349,7 +351,7 @@ struct bstbase2
(this->header_ptr(), key, this->key_node_comp(comp)), this->priv_value_traits_ptr());
}
- const_iterator upper_bound(const key_type &key) const
+ BOOST_INTRUSIVE_FORCEINLINE const_iterator upper_bound(const key_type &key) const
{ return this->upper_bound(key, this->key_comp()); }
template<class KeyType, class KeyTypeKeyCompare>
@@ -364,13 +366,13 @@ struct bstbase2
{ typedef detail::key_nodeptr_comp<KeyTypeKeyCompare, value_traits, key_of_value> type; };
template<class KeyTypeKeyCompare>
- typename key_node_comp_ret<KeyTypeKeyCompare>::type key_node_comp(KeyTypeKeyCompare comp) const
+ BOOST_INTRUSIVE_FORCEINLINE typename key_node_comp_ret<KeyTypeKeyCompare>::type key_node_comp(KeyTypeKeyCompare comp) const
{
return detail::key_nodeptr_comp<KeyTypeKeyCompare, value_traits, key_of_value>(comp, &this->get_value_traits());
}
//find
- iterator find(const key_type &key)
+ BOOST_INTRUSIVE_FORCEINLINE iterator find(const key_type &key)
{ return this->find(key, this->key_comp()); }
template<class KeyType, class KeyTypeKeyCompare>
@@ -380,7 +382,7 @@ struct bstbase2
(node_algorithms::find(this->header_ptr(), key, this->key_node_comp(comp)), this->priv_value_traits_ptr());
}
- const_iterator find(const key_type &key) const
+ BOOST_INTRUSIVE_FORCEINLINE const_iterator find(const key_type &key) const
{ return this->find(key, this->key_comp()); }
template<class KeyType, class KeyTypeKeyCompare>
@@ -391,7 +393,7 @@ struct bstbase2
}
//equal_range
- std::pair<iterator,iterator> equal_range(const key_type &key)
+ BOOST_INTRUSIVE_FORCEINLINE std::pair<iterator,iterator> equal_range(const key_type &key)
{ return this->equal_range(key, this->key_comp()); }
template<class KeyType, class KeyTypeKeyCompare>
@@ -403,7 +405,7 @@ struct bstbase2
, iterator(ret.second, this->priv_value_traits_ptr()));
}
- std::pair<const_iterator, const_iterator>
+ BOOST_INTRUSIVE_FORCEINLINE std::pair<const_iterator, const_iterator>
equal_range(const key_type &key) const
{ return this->equal_range(key, this->key_comp()); }
@@ -418,7 +420,7 @@ struct bstbase2
}
//lower_bound_range
- std::pair<iterator,iterator> lower_bound_range(const key_type &key)
+ BOOST_INTRUSIVE_FORCEINLINE std::pair<iterator,iterator> lower_bound_range(const key_type &key)
{ return this->lower_bound_range(key, this->key_comp()); }
template<class KeyType, class KeyTypeKeyCompare>
@@ -430,7 +432,7 @@ struct bstbase2
, iterator(ret.second, this->priv_value_traits_ptr()));
}
- std::pair<const_iterator, const_iterator>
+ BOOST_INTRUSIVE_FORCEINLINE std::pair<const_iterator, const_iterator>
lower_bound_range(const key_type &key) const
{ return this->lower_bound_range(key, this->key_comp()); }
@@ -445,7 +447,7 @@ struct bstbase2
}
//bounded_range
- std::pair<iterator,iterator> bounded_range
+ BOOST_INTRUSIVE_FORCEINLINE std::pair<iterator,iterator> bounded_range
(const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed)
{ return this->bounded_range(lower_key, upper_key, this->key_comp(), left_closed, right_closed); }
@@ -460,7 +462,7 @@ struct bstbase2
, iterator(ret.second, this->priv_value_traits_ptr()));
}
- std::pair<const_iterator,const_iterator> bounded_range
+ BOOST_INTRUSIVE_FORCEINLINE std::pair<const_iterator,const_iterator> bounded_range
(const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed) const
{ return this->bounded_range(lower_key, upper_key, this->key_comp(), left_closed, right_closed); }
@@ -476,11 +478,11 @@ struct bstbase2
}
//insert_unique_check
- std::pair<iterator, bool> insert_unique_check
+ BOOST_INTRUSIVE_FORCEINLINE std::pair<iterator, bool> insert_unique_check
(const key_type &key, insert_commit_data &commit_data)
{ return this->insert_unique_check(key, this->key_comp(), commit_data); }
- std::pair<iterator, bool> insert_unique_check
+ BOOST_INTRUSIVE_FORCEINLINE std::pair<iterator, bool> insert_unique_check
(const_iterator hint, const key_type &key, insert_commit_data &commit_data)
{ return this->insert_unique_check(hint, key, this->key_comp(), commit_data); }
@@ -525,7 +527,7 @@ struct bstbase_hack
typedef typename get_algo
<AlgoType, node_traits>::type algo_type;
- bstbase_hack(const key_compare & comp, const ValueTraits &vtraits)
+ BOOST_INTRUSIVE_FORCEINLINE bstbase_hack(const key_compare & comp, const ValueTraits &vtraits)
: base_type(comp, vtraits)
{
this->sz_traits().set_size(size_type(0));
@@ -533,10 +535,10 @@ struct bstbase_hack
typedef detail::size_holder<ConstantTimeSize, SizeType> size_traits;
- size_traits &sz_traits()
+ BOOST_INTRUSIVE_FORCEINLINE size_traits &sz_traits()
{ return static_cast<size_traits &>(*this); }
- const size_traits &sz_traits() const
+ BOOST_INTRUSIVE_FORCEINLINE const size_traits &sz_traits() const
{ return static_cast<const size_traits &>(*this); }
};
@@ -548,24 +550,16 @@ struct bstbase_hack<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, false, SizeTyp
typedef bstbase2< ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, AlgoType, HeaderHolder> base_type;
typedef typename base_type::value_compare value_compare;
typedef typename base_type::key_compare key_compare;
- bstbase_hack(const key_compare & comp, const ValueTraits &vtraits)
+ BOOST_INTRUSIVE_FORCEINLINE bstbase_hack(const key_compare & comp, const ValueTraits &vtraits)
: base_type(comp, vtraits)
{}
typedef detail::size_holder<false, SizeType> size_traits;
- size_traits &sz_traits()
- { return s_size_traits; }
-
- const size_traits &sz_traits() const
- { return s_size_traits; }
-
- static size_traits s_size_traits;
+ BOOST_INTRUSIVE_FORCEINLINE size_traits sz_traits() const
+ { return size_traits(); }
};
-template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, class SizeType, algo_types AlgoType, typename HeaderHolder>
-detail::size_holder<false, SizeType> bstbase_hack<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, false, SizeType, AlgoType, HeaderHolder>::s_size_traits;
-
//This class will
template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, bool ConstantTimeSize, class SizeType, algo_types AlgoType, typename HeaderHolder>
struct bstbase
@@ -584,7 +578,7 @@ struct bstbase
<AlgoType, node_traits>::type node_algorithms;
typedef SizeType size_type;
- bstbase(const key_compare & comp, const ValueTraits &vtraits)
+ BOOST_INTRUSIVE_FORCEINLINE bstbase(const key_compare & comp, const ValueTraits &vtraits)
: base_type(comp, vtraits)
{}
@@ -740,7 +734,7 @@ class bstree_impl
//! <b>Effects</b>: to-do
//!
- bstree_impl& operator=(BOOST_RV_REF(bstree_impl) x)
+ BOOST_INTRUSIVE_FORCEINLINE bstree_impl& operator=(BOOST_RV_REF(bstree_impl) x)
{ this->swap(x); return *this; }
#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
@@ -844,6 +838,27 @@ class bstree_impl
//! <b>Throws</b>: Nothing.
const_reverse_iterator crend() const;
+ //! <b>Effects</b>: Returns a iterator pointing to the root node of the container or end() if not present.
+ //!
+ //! <b>Complexity</b>: Constant.
+ //!
+ //! <b>Throws</b>: Nothing.
+ iterator root();
+
+ //! <b>Effects</b>: Returns a const_iterator pointing to the root node of the container or cend() if not present.
+ //!
+ //! <b>Complexity</b>: Constant.
+ //!
+ //! <b>Throws</b>: Nothing.
+ const_iterator root() const;
+
+ //! <b>Effects</b>: Returns a const_iterator pointing to the root node of the container or cend() if not present.
+ //!
+ //! <b>Complexity</b>: Constant.
+ //!
+ //! <b>Throws</b>: Nothing.
+ const_iterator croot() const;
+
#endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
//! <b>Precondition</b>: end_iterator must be a valid end iterator
@@ -955,11 +970,7 @@ class bstree_impl
::boost::adl_move_swap(this->comp(), this->comp());
//These can't throw
node_algorithms::swap_tree(this->header_ptr(), node_ptr(other.header_ptr()));
- if(constant_time_size){
- size_type backup = this->sz_traits().get_size();
- this->sz_traits().set_size(other.sz_traits().get_size());
- other.sz_traits().set_size(backup);
- }
+ this->sz_traits().swap(other.sz_traits());
}
//! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
@@ -1175,6 +1186,36 @@ class bstree_impl
#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
+ //! <b>Effects</b>: Checks if a value can be inserted in the container, using
+ //! a user provided key instead of the value itself.
+ //!
+ //! <b>Returns</b>: If there is an equivalent value
+ //! returns a pair containing an iterator to the already present value
+ //! and false. If the value can be inserted returns true in the returned
+ //! pair boolean and fills "commit_data" that is meant to be used with
+ //! the "insert_commit" function.
+ //!
+ //! <b>Complexity</b>: Average complexity is at most logarithmic.
+ //!
+ //! <b>Throws</b>: If the comp ordering function throws. Strong guarantee.
+ std::pair<iterator, bool> insert_unique_check(const key_type &key, insert_commit_data &commit_data);
+
+ //! <b>Effects</b>: Checks if a value can be inserted in the container, using
+ //! a user provided key instead of the value itself, using "hint"
+ //! as a hint to where it will be inserted.
+ //!
+ //! <b>Returns</b>: If there is an equivalent value
+ //! returns a pair containing an iterator to the already present value
+ //! and false. If the value can be inserted returns true in the returned
+ //! pair boolean and fills "commit_data" that is meant to be used with
+ //! the "insert_commit" function.
+ //!
+ //! <b>Complexity</b>: Logarithmic in general, but it's amortized
+ //! constant time if t is inserted immediately before hint.
+ //!
+ //! <b>Throws</b>: If the comp ordering function throws. Strong guarantee.
+ std::pair<iterator, bool> insert_unique_check(const_iterator hint, const key_type &key, insert_commit_data &commit_data);
+
//! <b>Requires</b>: comp must be a comparison function that induces
//! the same strict weak ordering as key_compare. The difference is that
//! comp compares an arbitrary key with the contained values.
@@ -1926,6 +1967,78 @@ class bstree_impl
node_algorithms::init(to_remove);
}
+ //! <b>Requires</b>: "source" container's Options can only can differ in the comparison
+ //! function from *this.
+ //!
+ //! <b>Effects</b>: Attempts to extract each element in source and insert it into a using
+ //! the comparison object of *this. If there is an element in a with key equivalent to the
+ //! key of an element from source, then that element is not extracted from source.
+ //!
+ //! <b>Postcondition</b>: Pointers and references to the transferred elements of source refer
+ //! to those same elements but as members of *this. Iterators referring to the transferred
+ //! elements will continue to refer to their elements, but they now behave as iterators into *this,
+ //! not into source.
+ //!
+ //! <b>Throws</b>: Nothing unless the comparison object throws.
+ //!
+ //! <b>Complexity</b>: N log(a.size() + N) (N has the value source.size())
+ #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
+ template<class T, class ...Options2> void merge_unique(bstree<T, Options2...> &);
+ #else
+ template<class Compare2>
+ void merge_unique(bstree_impl
+ <ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, ConstantTimeSize, AlgoType, HeaderHolder> &source)
+ #endif
+ {
+ node_ptr it (node_algorithms::begin_node(source.header_ptr()))
+ , itend(node_algorithms::end_node (source.header_ptr()));
+
+ while(it != itend){
+ node_ptr const p(it);
+ BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || !node_algorithms::unique(p));
+ it = node_algorithms::next_node(it);
+ if( node_algorithms::transfer_unique(this->header_ptr(), this->key_node_comp(this->key_comp()), source.header_ptr(), p) ){
+ source.sz_traits().decrement();
+ this->sz_traits().increment();
+ }
+ }
+ }
+
+ //! <b>Requires</b>: "source" container's Options can only can differ in the comparison
+ //! function from *this.
+ //!
+ //! <b>Effects</b>: Extracts each element in source and insert it into a using
+ //! the comparison object of *this.
+ //!
+ //! <b>Postcondition</b>: Pointers and references to the transferred elements of source refer
+ //! to those same elements but as members of *this. Iterators referring to the transferred
+ //! elements will continue to refer to their elements, but they now behave as iterators into *this,
+ //! not into source.
+ //!
+ //! <b>Throws</b>: Nothing unless the comparison object throws.
+ //!
+ //! <b>Complexity</b>: N log(a.size() + N) (N has the value source.size())
+ #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
+ template<class T, class ...Options2> void merge_equal(bstree<T, Options2...> &);
+ #else
+ template<class Compare2>
+ void merge_equal(bstree_impl
+ <ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, ConstantTimeSize, AlgoType, HeaderHolder> &source)
+ #endif
+ {
+ node_ptr it (node_algorithms::begin_node(source.header_ptr()))
+ , itend(node_algorithms::end_node (source.header_ptr()));
+
+ while(it != itend){
+ node_ptr const p(it);
+ BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || !node_algorithms::unique(p));
+ it = node_algorithms::next_node(it);
+ node_algorithms::transfer_equal(this->header_ptr(), this->key_node_comp(this->key_comp()), source.header_ptr(), p);
+ source.sz_traits().decrement();
+ this->sz_traits().increment();
+ }
+ }
+
//! <b>Effects</b>: Asserts the integrity of the container with additional checks provided by the user.
//!
//! <b>Complexity</b>: Linear time.
diff --git a/boost/intrusive/bstree_algorithms.hpp b/boost/intrusive/bstree_algorithms.hpp
index dcb7e5c..e8caee0 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
diff --git a/boost/intrusive/circular_list_algorithms.hpp b/boost/intrusive/circular_list_algorithms.hpp
index f343045..72eae32 100644
--- a/boost/intrusive/circular_list_algorithms.hpp
+++ b/boost/intrusive/circular_list_algorithms.hpp
@@ -67,7 +67,7 @@ class circular_list_algorithms
//! <b>Complexity</b>: Constant
//!
//! <b>Throws</b>: Nothing.
- static void init(const node_ptr &this_node)
+ BOOST_INTRUSIVE_FORCEINLINE static void init(const node_ptr &this_node)
{
const node_ptr null_node((node_ptr()));
NodeTraits::set_next(this_node, null_node);
@@ -80,7 +80,7 @@ class circular_list_algorithms
//! <b>Complexity</b>: Constant
//!
//! <b>Throws</b>: Nothing.
- static bool inited(const const_node_ptr &this_node)
+ BOOST_INTRUSIVE_FORCEINLINE static bool inited(const const_node_ptr &this_node)
{ return !NodeTraits::get_next(this_node); }
//! <b>Effects</b>: Constructs an empty list, making this_node the only
@@ -91,7 +91,7 @@ class circular_list_algorithms
//! <b>Complexity</b>: Constant
//!
//! <b>Throws</b>: Nothing.
- static void init_header(const node_ptr &this_node)
+ BOOST_INTRUSIVE_FORCEINLINE static void init_header(const node_ptr &this_node)
{
NodeTraits::set_next(this_node, this_node);
NodeTraits::set_previous(this_node, this_node);
@@ -106,7 +106,7 @@ class circular_list_algorithms
//! <b>Complexity</b>: Constant
//!
//! <b>Throws</b>: Nothing.
- static bool unique(const const_node_ptr &this_node)
+ BOOST_INTRUSIVE_FORCEINLINE static bool unique(const const_node_ptr &this_node)
{
node_ptr next = NodeTraits::get_next(this_node);
return !next || next == this_node;
@@ -138,7 +138,7 @@ class circular_list_algorithms
//! <b>Complexity</b>: Constant
//!
//! <b>Throws</b>: Nothing.
- static node_ptr unlink(const node_ptr &this_node)
+ BOOST_INTRUSIVE_FORCEINLINE static node_ptr unlink(const node_ptr &this_node)
{
node_ptr next(NodeTraits::get_next(this_node));
node_ptr prev(NodeTraits::get_previous(this_node));
@@ -154,7 +154,7 @@ class circular_list_algorithms
//! <b>Complexity</b>: Constant
//!
//! <b>Throws</b>: Nothing.
- static void unlink(const node_ptr &b, const node_ptr &e)
+ BOOST_INTRUSIVE_FORCEINLINE static void unlink(const node_ptr &b, const node_ptr &e)
{
if (b != e) {
node_ptr prevb(NodeTraits::get_previous(b));
@@ -170,14 +170,14 @@ class circular_list_algorithms
//! <b>Complexity</b>: Constant
//!
//! <b>Throws</b>: Nothing.
- static void link_before(const node_ptr &nxt_node, const node_ptr &this_node)
+ BOOST_INTRUSIVE_FORCEINLINE static void link_before(const node_ptr &nxt_node, const node_ptr &this_node)
{
node_ptr prev(NodeTraits::get_previous(nxt_node));
NodeTraits::set_previous(this_node, prev);
NodeTraits::set_next(this_node, nxt_node);
//nxt_node might be an alias for prev->next_
//so use it before NodeTraits::set_next(prev, ...)
- //is called and the reference changes it's value
+ //is called and the reference changes its value
NodeTraits::set_previous(nxt_node, this_node);
NodeTraits::set_next(prev, this_node);
}
@@ -189,7 +189,7 @@ class circular_list_algorithms
//! <b>Complexity</b>: Constant
//!
//! <b>Throws</b>: Nothing.
- static void link_after(const node_ptr &prev_node, const node_ptr &this_node)
+ BOOST_INTRUSIVE_FORCEINLINE static void link_after(const node_ptr &prev_node, const node_ptr &this_node)
{
node_ptr next(NodeTraits::get_next(prev_node));
NodeTraits::set_previous(this_node, prev_node);
@@ -435,14 +435,14 @@ class circular_list_algorithms
}
private:
- static void swap_prev(const node_ptr &this_node, const node_ptr &other_node)
+ BOOST_INTRUSIVE_FORCEINLINE static void swap_prev(const node_ptr &this_node, const node_ptr &other_node)
{
node_ptr temp(NodeTraits::get_previous(this_node));
NodeTraits::set_previous(this_node, NodeTraits::get_previous(other_node));
NodeTraits::set_previous(other_node, temp);
}
- static void swap_next(const node_ptr &this_node, const node_ptr &other_node)
+ BOOST_INTRUSIVE_FORCEINLINE static void swap_next(const node_ptr &this_node, const node_ptr &other_node)
{
node_ptr temp(NodeTraits::get_next(this_node));
NodeTraits::set_next(this_node, NodeTraits::get_next(other_node));
diff --git a/boost/intrusive/circular_slist_algorithms.hpp b/boost/intrusive/circular_slist_algorithms.hpp
index 951a40a..da840ef 100644
--- a/boost/intrusive/circular_slist_algorithms.hpp
+++ b/boost/intrusive/circular_slist_algorithms.hpp
@@ -141,7 +141,7 @@ class circular_slist_algorithms
//! <b>Complexity</b>: Constant
//!
//! <b>Throws</b>: Nothing.
- static void init_header(const node_ptr &this_node)
+ BOOST_INTRUSIVE_FORCEINLINE static void init_header(const node_ptr &this_node)
{ NodeTraits::set_next(this_node, this_node); }
//! <b>Requires</b>: this_node and prev_init_node must be in the same circular list.
@@ -153,7 +153,7 @@ class circular_slist_algorithms
//! <b>Complexity</b>: Linear to the number of elements between prev_init_node and this_node.
//!
//! <b>Throws</b>: Nothing.
- static node_ptr get_previous_node(const node_ptr &prev_init_node, const node_ptr &this_node)
+ BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_previous_node(const node_ptr &prev_init_node, const node_ptr &this_node)
{ return base_t::get_previous_node(prev_init_node, this_node); }
//! <b>Requires</b>: this_node must be in a circular list or be an empty circular list.
@@ -163,7 +163,7 @@ class circular_slist_algorithms
//! <b>Complexity</b>: Linear to the number of elements in the circular list.
//!
//! <b>Throws</b>: Nothing.
- static node_ptr get_previous_node(const node_ptr & this_node)
+ BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_previous_node(const node_ptr & this_node)
{ return base_t::get_previous_node(this_node, this_node); }
//! <b>Requires</b>: this_node must be in a circular list or be an empty circular list.
@@ -173,7 +173,7 @@ class circular_slist_algorithms
//! <b>Complexity</b>: Linear to the number of elements in the circular list.
//!
//! <b>Throws</b>: Nothing.
- static node_ptr get_previous_previous_node(const node_ptr & this_node)
+ BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_previous_previous_node(const node_ptr & this_node)
{ return get_previous_previous_node(this_node, this_node); }
//! <b>Requires</b>: this_node and p must be in the same circular list.
@@ -223,7 +223,7 @@ class circular_slist_algorithms
//! <b>Complexity</b>: Linear to the number of elements in the circular list
//!
//! <b>Throws</b>: Nothing.
- static void unlink(const node_ptr & this_node)
+ BOOST_INTRUSIVE_FORCEINLINE static void unlink(const node_ptr & this_node)
{
if(NodeTraits::get_next(this_node))
base_t::unlink_after(get_previous_node(this_node));
@@ -236,7 +236,7 @@ class circular_slist_algorithms
//! <b>Complexity</b>: Linear to the number of elements in the circular list.
//!
//! <b>Throws</b>: Nothing.
- static void link_before (const node_ptr & nxt_node, const node_ptr & this_node)
+ BOOST_INTRUSIVE_FORCEINLINE static void link_before (const node_ptr & nxt_node, const node_ptr & this_node)
{ base_t::link_after(get_previous_node(nxt_node), this_node); }
//! <b>Requires</b>: this_node and other_node must be nodes inserted
diff --git a/boost/intrusive/detail/algo_type.hpp b/boost/intrusive/detail/algo_type.hpp
index 6da48e9..70ec63f 100644
--- a/boost/intrusive/detail/algo_type.hpp
+++ b/boost/intrusive/detail/algo_type.hpp
@@ -35,7 +35,10 @@ enum algo_types
AvlTreeAlgorithms,
SgTreeAlgorithms,
SplayTreeAlgorithms,
- TreapAlgorithms
+ TreapAlgorithms,
+ UnorderedAlgorithms,
+ UnorderedCircularSlistAlgorithms,
+ AnyAlgorithm
};
template<algo_types AlgoType, class NodeTraits>
diff --git a/boost/intrusive/detail/any_node_and_algorithms.hpp b/boost/intrusive/detail/any_node_and_algorithms.hpp
index 4b087b5..26a1edc 100644
--- a/boost/intrusive/detail/any_node_and_algorithms.hpp
+++ b/boost/intrusive/detail/any_node_and_algorithms.hpp
@@ -23,8 +23,9 @@
#include <boost/intrusive/detail/workaround.hpp>
#include <boost/intrusive/pointer_rebind.hpp>
-#include <cstddef>
#include <boost/intrusive/detail/mpl.hpp>
+#include <boost/intrusive/detail/algo_type.hpp>
+#include <cstddef>
namespace boost {
namespace intrusive {
@@ -279,6 +280,17 @@ class any_algorithms
}
};
+///@cond
+
+template<class NodeTraits>
+struct get_algo<AnyAlgorithm, NodeTraits>
+{
+ typedef typename pointer_rebind<typename NodeTraits::node_ptr, void>::type void_pointer;
+ typedef any_algorithms<void_pointer> type;
+};
+
+///@endcond
+
} //namespace intrusive
} //namespace boost
diff --git a/boost/intrusive/detail/common_slist_algorithms.hpp b/boost/intrusive/detail/common_slist_algorithms.hpp
index c6fa289..5e6ff4d 100644
--- a/boost/intrusive/detail/common_slist_algorithms.hpp
+++ b/boost/intrusive/detail/common_slist_algorithms.hpp
@@ -52,34 +52,34 @@ class common_slist_algorithms
return p;
}
- static void init(const node_ptr & this_node)
+ BOOST_INTRUSIVE_FORCEINLINE static void init(const node_ptr & this_node)
{ NodeTraits::set_next(this_node, node_ptr()); }
- static bool unique(const const_node_ptr & this_node)
+ BOOST_INTRUSIVE_FORCEINLINE static bool unique(const const_node_ptr & this_node)
{
node_ptr next = NodeTraits::get_next(this_node);
return !next || next == this_node;
}
- static bool inited(const const_node_ptr & this_node)
+ BOOST_INTRUSIVE_FORCEINLINE static bool inited(const const_node_ptr & this_node)
{ return !NodeTraits::get_next(this_node); }
- static void unlink_after(const node_ptr & prev_node)
+ BOOST_INTRUSIVE_FORCEINLINE static void unlink_after(const node_ptr & prev_node)
{
const_node_ptr this_node(NodeTraits::get_next(prev_node));
NodeTraits::set_next(prev_node, NodeTraits::get_next(this_node));
}
- static void unlink_after(const node_ptr & prev_node, const node_ptr & last_node)
+ BOOST_INTRUSIVE_FORCEINLINE static void unlink_after(const node_ptr & prev_node, const node_ptr & last_node)
{ NodeTraits::set_next(prev_node, last_node); }
- static void link_after(const node_ptr & prev_node, const node_ptr & this_node)
+ BOOST_INTRUSIVE_FORCEINLINE static void link_after(const node_ptr & prev_node, const node_ptr & this_node)
{
NodeTraits::set_next(this_node, NodeTraits::get_next(prev_node));
NodeTraits::set_next(prev_node, this_node);
}
- static void incorporate_after(const node_ptr & bp, const node_ptr & b, const node_ptr & be)
+ BOOST_INTRUSIVE_FORCEINLINE static void incorporate_after(const node_ptr & bp, const node_ptr & b, const node_ptr & be)
{
node_ptr p(NodeTraits::get_next(bp));
NodeTraits::set_next(bp, b);
diff --git a/boost/intrusive/detail/ebo_functor_holder.hpp b/boost/intrusive/detail/ebo_functor_holder.hpp
index ef278ed..31b2f81 100644
--- a/boost/intrusive/detail/ebo_functor_holder.hpp
+++ b/boost/intrusive/detail/ebo_functor_holder.hpp
@@ -259,7 +259,7 @@ class ebo_functor_holder<T, false>
BOOST_INTRUSIVE_FORCEINLINE ebo_functor_holder& operator=(BOOST_COPY_ASSIGN_REF(ebo_functor_holder) x)
{
const ebo_functor_holder&r = x;
- this->get() = x.get();
+ this->get() = r;
return *this;
}
diff --git a/boost/intrusive/detail/generic_hook.hpp b/boost/intrusive/detail/generic_hook.hpp
index b57a12b..13421b8 100644
--- a/boost/intrusive/detail/generic_hook.hpp
+++ b/boost/intrusive/detail/generic_hook.hpp
@@ -26,6 +26,7 @@
#include <boost/intrusive/detail/mpl.hpp>
#include <boost/intrusive/detail/assert.hpp>
#include <boost/intrusive/detail/node_holder.hpp>
+#include <boost/intrusive/detail/algo_type.hpp>
#include <boost/static_assert.hpp>
namespace boost {
@@ -120,7 +121,8 @@ struct hooktags_impl
/// @endcond
template
- < class NodeAlgorithms
+ < boost::intrusive::algo_types Algo
+ , class NodeTraits
, class Tag
, link_mode_type LinkMode
, base_hook_type BaseHookType
@@ -135,20 +137,20 @@ class generic_hook
//from the hook.
: public detail::if_c
< detail::is_same<Tag, member_tag>::value
- , typename NodeAlgorithms::node
- , node_holder<typename NodeAlgorithms::node, Tag, BaseHookType>
+ , typename NodeTraits::node
+ , node_holder<typename NodeTraits::node, Tag, BaseHookType>
>::type
//If this is the a default-tagged base hook derive from a class that
//will define an special internal typedef. Containers will be able to detect this
//special typedef and obtain generic_hook's internal types in order to deduce
//value_traits for this hook.
, public hook_tags_definer
- < generic_hook<NodeAlgorithms, Tag, LinkMode, BaseHookType>
- , detail::is_same<Tag, dft_tag>::value*BaseHookType>
+ < generic_hook<Algo, NodeTraits, Tag, LinkMode, BaseHookType>
+ , detail::is_same<Tag, dft_tag>::value ? BaseHookType : NoBaseHookId>
/// @endcond
{
/// @cond
- typedef NodeAlgorithms node_algorithms;
+ typedef typename get_algo<Algo, NodeTraits>::type node_algorithms;
typedef typename node_algorithms::node node;
typedef typename node_algorithms::node_ptr node_ptr;
typedef typename node_algorithms::const_node_ptr const_node_ptr;
@@ -156,7 +158,7 @@ class generic_hook
public:
typedef hooktags_impl
- < typename NodeAlgorithms::node_traits
+ < NodeTraits
, Tag, LinkMode, BaseHookType> hooktags;
node_ptr this_ptr()
diff --git a/boost/intrusive/detail/has_member_function_callable_with.hpp b/boost/intrusive/detail/has_member_function_callable_with.hpp
index 2e73305..92ef60e 100644
--- a/boost/intrusive/detail/has_member_function_callable_with.hpp
+++ b/boost/intrusive/detail/has_member_function_callable_with.hpp
@@ -11,13 +11,22 @@
#ifndef BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_CALLABLE_WITH_HPP
#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_CALLABLE_WITH_HPP
-//Mark that we don't support 0 arg calls due to compiler ICE in GCC 3.4/4.0/4.1 and
-//wrong SFINAE for GCC 4.2/4.3
-#if defined(__GNUC__) && !defined(__clang__) && ((__GNUC__*100 + __GNUC_MINOR__*10) >= 340) && ((__GNUC__*100 + __GNUC_MINOR__*10) <= 430)
- #define BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_0_ARGS_UNSUPPORTED
-#elif defined(BOOST_INTEL) && (BOOST_INTEL < 1200 )
- #define BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_0_ARGS_UNSUPPORTED
+#ifndef BOOST_CONFIG_HPP
+# include <boost/config.hpp>
#endif
+
+//In case no decltype and no variadics, mark that we don't support 0 arg calls due to
+//compiler ICE in GCC 3.4/4.0/4.1 and, wrong SFINAE for GCC 4.2/4.3/MSVC10/MSVC11
+#if defined(BOOST_NO_CXX11_DECLTYPE) && defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
+# if defined(BOOST_GCC) && (BOOST_GCC < 40400)
+# define BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_0_ARGS_UNSUPPORTED
+# elif defined(BOOST_INTEL) && (BOOST_INTEL < 1200)
+# define BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_0_ARGS_UNSUPPORTED
+# elif defined(BOOST_MSVC) && (BOOST_MSVC < 1800)
+# define BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_0_ARGS_UNSUPPORTED
+# endif
+#endif //#if defined(BOOST_NO_CXX11_DECLTYPE) && defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
+
#include <cstddef>
#include <boost/move/utility_core.hpp>
#include <boost/move/detail/fwd_macros.hpp>
@@ -27,6 +36,11 @@ namespace boost_intrusive_hmfcw {
typedef char yes_type;
struct no_type{ char dummy[2]; };
+struct dont_care
+{
+ dont_care(...);
+};
+
#if defined(BOOST_NO_CXX11_DECLTYPE)
#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
@@ -39,11 +53,6 @@ struct make_dontcare
#endif
-struct dont_care
-{
- dont_care(...);
-};
-
struct private_type
{
static private_type p;
@@ -56,7 +65,7 @@ yes_type is_private_type(private_type const &);
#endif //#if defined(BOOST_NO_CXX11_DECLTYPE)
-#if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
+#if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_NO_CXX11_DECLTYPE)
template<typename T> struct remove_cv { typedef T type; };
template<typename T> struct remove_cv<const T> { typedef T type; };
@@ -124,7 +133,31 @@ BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEG
// declaration, special case and 0 arg specializaton
//
/////////////////////////////////////////////////////////
- /////////////////////////////////////////////////////////
+
+ template <typename Type>
+ class BOOST_MOVE_CAT(has_member_function_named_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)
+ {
+ struct BaseMixin
+ {
+ void BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME()
+ {} //Some compilers require the definition or linker errors happen
+ };
+
+ struct Base
+ : public boost_intrusive_hmfcw::remove_cv<Type>::type, public BaseMixin
+ { //Declare the unneeded default constructor as some old compilers wrongly require it with is_convertible
+ Base(){}
+ };
+ template <typename T, T t> class Helper{};
+
+ template <typename U>
+ static boost_intrusive_hmfcw::no_type deduce
+ (U*, Helper<void (BaseMixin::*)(), &U::BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME>* = 0);
+ static boost_intrusive_hmfcw::yes_type deduce(...);
+
+ public:
+ static const bool value = sizeof(boost_intrusive_hmfcw::yes_type) == sizeof(deduce((Base*)0));
+ };
#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
/////////////////////////////////////////////////////////
@@ -136,53 +169,45 @@ BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEG
/////////////////////////////////////////////////////////
//defined(BOOST_NO_CXX11_DECLTYPE) must be true
- template<class Fun, class ...DontCares>
+ template<class Fun>
struct FunWrapTmpl : Fun
{
using Fun::BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME;
+ FunWrapTmpl();
+ template<class ...DontCares>
boost_intrusive_hmfcw::private_type BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME(DontCares...) const;
};
+ template<typename Fun, bool HasFunc, class ...Args>
+ struct BOOST_MOVE_CAT(has_member_function_callable_with_impl_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME);
+
+ //No BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME member specialization
template<typename Fun, class ...Args>
- struct BOOST_MOVE_CAT(has_member_function_callable_with_,BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<Fun, Args...>
+ struct BOOST_MOVE_CAT(has_member_function_callable_with_impl_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)
+ <Fun, false, Args...>
{
- typedef FunWrapTmpl<typename boost_intrusive_hmfcw::make_dontcare<Args>::type...> FunWrap;
+ static const bool value = false;
+ };
- static bool const value = (sizeof(boost_intrusive_hmfcw::no_type) ==
- sizeof(boost_intrusive_hmfcw::is_private_type
- ( (::boost::move_detail::declval< FunWrap<Fun> >().
+ template<typename Fun, class ...Args>
+ struct BOOST_MOVE_CAT(has_member_function_callable_with_impl_,BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<Fun, true, Args...>
+ {
+ static bool const value = (sizeof(boost_intrusive_hmfcw::no_type) == sizeof(boost_intrusive_hmfcw::is_private_type
+ ( (::boost::move_detail::declval
+ < FunWrapTmpl<Fun> >().
BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME(::boost::move_detail::declval<Args>()...), 0) )
)
);
};
- #else //defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
-
- //Preprocessor must be used to generate specializations instead of variadic templates
- template <typename Type>
- class BOOST_MOVE_CAT(has_member_function_named_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)
- {
- struct BaseMixin
- {
- void BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME()
- {} //Some compilers require the definition or linker errors happen
- };
-
- struct Base
- : public boost_intrusive_hmfcw::remove_cv<Type>::type, public BaseMixin
- { //Declare the unneeded default constructor as some old compilers wrongly require it with is_convertible
- Base(){}
- };
- template <typename T, T t> class Helper{};
-
- template <typename U>
- static boost_intrusive_hmfcw::no_type deduce
- (U*, Helper<void (BaseMixin::*)(), &U::BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME>* = 0);
- static boost_intrusive_hmfcw::yes_type deduce(...);
-
- public:
- static const bool value = sizeof(boost_intrusive_hmfcw::yes_type) == sizeof(deduce((Base*)0));
- };
+ template<typename Fun, class ...Args>
+ struct BOOST_MOVE_CAT(has_member_function_callable_with_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)
+ : public BOOST_MOVE_CAT(has_member_function_callable_with_impl_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)
+ <Fun
+ , BOOST_MOVE_CAT(has_member_function_named_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<Fun>::value
+ , Args...>
+ {};
+ #else //defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
/////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////
@@ -222,24 +247,24 @@ BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEG
#if !defined(BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_0_ARGS_UNSUPPORTED)
- template<class F, std::size_t N = sizeof(boost::move_detail::declval<F>().BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME(), 0)>
- struct BOOST_MOVE_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)
- { boost_intrusive_hmfcw::yes_type dummy[N ? 1 : 2]; };
+ template<class F, std::size_t N = sizeof(boost::move_detail::declval<F>().BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME(), 0)>
+ struct BOOST_MOVE_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)
+ { boost_intrusive_hmfcw::yes_type dummy[N ? 1 : 2]; };
- template<typename Fun>
- struct BOOST_MOVE_CAT(has_member_function_callable_with_impl_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<Fun, true>
- {
- template<class U> static BOOST_MOVE_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<U>
- Test(BOOST_MOVE_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<U>*);
- template<class U> static boost_intrusive_hmfcw::no_type Test(...);
- static const bool value = sizeof(Test< Fun >(0)) == sizeof(boost_intrusive_hmfcw::yes_type);
- };
+ template<typename Fun>
+ struct BOOST_MOVE_CAT(has_member_function_callable_with_impl_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<Fun, true>
+ {
+ template<class U> static BOOST_MOVE_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<U>
+ Test(BOOST_MOVE_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<U>*);
+ template<class U> static boost_intrusive_hmfcw::no_type Test(...);
+ static const bool value = sizeof(Test< Fun >(0)) == sizeof(boost_intrusive_hmfcw::yes_type);
+ };
#else //defined(BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_0_ARGS_UNSUPPORTED)
template<typename Fun>
struct BOOST_MOVE_CAT(has_member_function_callable_with_impl_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<Fun, true>
- {//GCC [3.4-4.3) gives ICE when instantiating the 0 arg version so it is not supported.
+ { //Some compilers gives ICE when instantiating the 0 arg version so it is not supported.
static const bool value = true;
};
diff --git a/boost/intrusive/detail/key_nodeptr_comp.hpp b/boost/intrusive/detail/key_nodeptr_comp.hpp
index 1a5ec32..9d64f09 100644
--- a/boost/intrusive/detail/key_nodeptr_comp.hpp
+++ b/boost/intrusive/detail/key_nodeptr_comp.hpp
@@ -23,6 +23,8 @@
#include <boost/intrusive/detail/mpl.hpp>
#include <boost/intrusive/detail/ebo_functor_holder.hpp>
+#include <boost/intrusive/detail/tree_value_compare.hpp>
+
namespace boost {
namespace intrusive {
@@ -30,64 +32,84 @@ namespace detail {
template < class KeyTypeKeyCompare
, class ValueTraits
- , class KeyOfValue = void
+ , class KeyOfValue
>
-struct key_nodeptr_comp
- //Use public inheritance to avoid MSVC bugs with closures
- : public ebo_functor_holder<KeyTypeKeyCompare>
+struct key_nodeptr_comp_types
{
- typedef ValueTraits value_traits;
- typedef typename value_traits::value_type value_type;
- typedef typename value_traits::node_ptr node_ptr;
- typedef typename value_traits::const_node_ptr const_node_ptr;
- typedef ebo_functor_holder<KeyTypeKeyCompare> base_t;
+ typedef ValueTraits value_traits;
+ typedef typename value_traits::value_type value_type;
+ typedef typename value_traits::node_ptr node_ptr;
+ typedef typename value_traits::const_node_ptr const_node_ptr;
typedef typename detail::if_c
< detail::is_same<KeyOfValue, void>::value
, detail::identity<value_type>
, KeyOfValue
- >::type key_of_value;
- typedef typename key_of_value::type key_type;
-
- key_nodeptr_comp(KeyTypeKeyCompare kcomp, const ValueTraits *traits)
- : base_t(kcomp), traits_(traits)
- {}
+ >::type key_of_value;
+ typedef tree_value_compare
+ <typename ValueTraits::pointer, KeyTypeKeyCompare, key_of_value> base_t;
+};
- template<class T>
- struct is_node_ptr
+//This function object transforms a key comparison type to
+//a function that can compare nodes or nodes with nodes or keys.
+template < class KeyTypeKeyCompare
+ , class ValueTraits
+ , class KeyOfValue = void
+ >
+struct key_nodeptr_comp
+ //Use public inheritance to avoid MSVC bugs with closures
+ : public key_nodeptr_comp_types<KeyTypeKeyCompare, ValueTraits, KeyOfValue>::base_t
+{
+ typedef key_nodeptr_comp_types<KeyTypeKeyCompare, ValueTraits, KeyOfValue> types_t;
+ typedef typename types_t::value_traits value_traits;
+ typedef typename types_t::value_type value_type;
+ typedef typename types_t::node_ptr node_ptr;
+ typedef typename types_t::const_node_ptr const_node_ptr;
+ typedef typename types_t::base_t base_t;
+ typedef typename types_t::key_of_value key_of_value;
+
+ template <class P1>
+ struct is_same_or_nodeptr_convertible
{
- static const bool value = is_same<T, const_node_ptr>::value || is_same<T, node_ptr>::value;
+ static const bool same_type = is_same<P1,const_node_ptr>::value || is_same<P1,node_ptr>::value;
+ static const bool value = same_type || is_convertible<P1, const_node_ptr>::value;
};
- //key_forward
- template<class T>
- typename enable_if<is_node_ptr<T>, const key_type &>::type key_forward(const T &node) const
- { return key_of_value()(*traits_->to_value_ptr(node)); }
+ base_t base() const
+ { return static_cast<const base_t&>(*this); }
- template<class T>
- #if defined(BOOST_MOVE_HELPERS_RETURN_SFINAE_BROKEN)
- const T &key_forward (const T &key, typename disable_if<is_node_ptr<T> >::type* =0) const
- #else
- typename disable_if<is_node_ptr<T>, const T &>::type key_forward(const T &key) const
- #endif
- { return key; }
-
- //operator() 1 arg
- template<class KeyType>
- bool operator()(const KeyType &key1) const
- { return base_t::get()(this->key_forward(key1)); }
+ BOOST_INTRUSIVE_FORCEINLINE key_nodeptr_comp(KeyTypeKeyCompare kcomp, const ValueTraits *traits)
+ : base_t(kcomp), traits_(traits)
+ {}
- template<class KeyType>
- bool operator()(const KeyType &key1)
- { return base_t::get()(this->key_forward(key1)); }
+ //pred(pnode)
+ template<class T1>
+ BOOST_INTRUSIVE_FORCEINLINE bool operator()(const T1 &t1, typename enable_if_c< is_same_or_nodeptr_convertible<T1>::value >::type* =0) const
+ { return base().get()(key_of_value()(*traits_->to_value_ptr(t1))); }
//operator() 2 arg
- template<class KeyType, class KeyType2>
- bool operator()(const KeyType &key1, const KeyType2 &key2) const
- { return base_t::get()(this->key_forward(key1), this->key_forward(key2)); }
-
- template<class KeyType, class KeyType2>
- bool operator()(const KeyType &key1, const KeyType2 &key2)
- { return base_t::get()(this->key_forward(key1), this->key_forward(key2)); }
+ //pred(pnode, pnode)
+ template<class T1, class T2>
+ BOOST_INTRUSIVE_FORCEINLINE bool operator()
+ (const T1 &t1, const T2 &t2, typename enable_if_c< is_same_or_nodeptr_convertible<T1>::value && is_same_or_nodeptr_convertible<T2>::value >::type* =0) const
+ { return base()(*traits_->to_value_ptr(t1), *traits_->to_value_ptr(t2)); }
+
+ //pred(pnode, key)
+ template<class T1, class T2>
+ BOOST_INTRUSIVE_FORCEINLINE bool operator()
+ (const T1 &t1, const T2 &t2, typename enable_if_c< is_same_or_nodeptr_convertible<T1>::value && !is_same_or_nodeptr_convertible<T2>::value >::type* =0) const
+ { return base()(*traits_->to_value_ptr(t1), t2); }
+
+ //pred(key, pnode)
+ template<class T1, class T2>
+ BOOST_INTRUSIVE_FORCEINLINE bool operator()
+ (const T1 &t1, const T2 &t2, typename enable_if_c< !is_same_or_nodeptr_convertible<T1>::value && is_same_or_nodeptr_convertible<T2>::value >::type* =0) const
+ { return base()(t1, *traits_->to_value_ptr(t2)); }
+
+ //pred(key, key)
+ template<class T1, class T2>
+ BOOST_INTRUSIVE_FORCEINLINE bool operator()
+ (const T1 &t1, const T2 &t2, typename enable_if_c< !is_same_or_nodeptr_convertible<T1>::value && !is_same_or_nodeptr_convertible<T2>::value >::type* =0) const
+ { return base()(t1, t2); }
const ValueTraits *const traits_;
};
diff --git a/boost/intrusive/detail/size_holder.hpp b/boost/intrusive/detail/size_holder.hpp
index 9802ac3..bd14dc5 100644
--- a/boost/intrusive/detail/size_holder.hpp
+++ b/boost/intrusive/detail/size_holder.hpp
@@ -51,6 +51,9 @@ struct size_holder
BOOST_INTRUSIVE_FORCEINLINE void decrease(SizeType n)
{ size_ -= n; }
+ BOOST_INTRUSIVE_FORCEINLINE void swap(size_holder &other)
+ { SizeType tmp(size_); size_ = other.size_; other.size_ = tmp; }
+
SizeType size_;
};
@@ -77,6 +80,8 @@ struct size_holder<false, SizeType, Tag>
BOOST_INTRUSIVE_FORCEINLINE void decrease(SizeType)
{}
+
+ BOOST_INTRUSIVE_FORCEINLINE void swap(size_holder){}
};
} //namespace detail{
diff --git a/boost/intrusive/detail/tree_value_compare.hpp b/boost/intrusive/detail/tree_value_compare.hpp
index 810d894..c8f596f 100644
--- a/boost/intrusive/detail/tree_value_compare.hpp
+++ b/boost/intrusive/detail/tree_value_compare.hpp
@@ -21,67 +21,140 @@
#include <boost/intrusive/detail/workaround.hpp>
#include <boost/intrusive/detail/mpl.hpp>
#include <boost/intrusive/detail/ebo_functor_holder.hpp>
+#include <boost/intrusive/pointer_traits.hpp>
namespace boost{
namespace intrusive{
-template<class Key, class T, class KeyCompare, class KeyOfValue>
+//Needed to support smart references to value types
+template <class From, class ValuePtr>
+struct disable_if_smartref_to
+ : detail::disable_if_c
+ < detail::is_same
+ <From, typename pointer_traits
+ <ValuePtr>
+ ::reference>::value
+ || detail::is_same
+ <From, typename pointer_traits
+ < typename pointer_rebind
+ <ValuePtr, const typename pointer_element<ValuePtr>::type>::type>
+ ::reference>::value
+ >
+{};
+
+//This function object takes a KeyCompare function object
+//and compares values that contains keys using KeyOfValue
+template< class ValuePtr, class KeyCompare, class KeyOfValue
+ , bool = boost::intrusive::detail::is_same<typename pointer_element<ValuePtr>::type, typename KeyOfValue::type>::value >
struct tree_value_compare
: public boost::intrusive::detail::ebo_functor_holder<KeyCompare>
{
- typedef boost::intrusive::detail::ebo_functor_holder<KeyCompare> base_t;
- typedef T value_type;
- typedef KeyCompare key_compare;
- typedef KeyOfValue key_of_value;
- typedef Key key_type;
+ typedef typename pointer_element<ValuePtr>::type value_type;
+ typedef KeyCompare key_compare;
+ typedef KeyOfValue key_of_value;
+ typedef typename KeyOfValue::type key_type;
+ typedef boost::intrusive::detail::ebo_functor_holder<KeyCompare> base_t;
- tree_value_compare()
+ BOOST_INTRUSIVE_FORCEINLINE tree_value_compare()
: base_t()
{}
- explicit tree_value_compare(const key_compare &kcomp)
+ BOOST_INTRUSIVE_FORCEINLINE explicit tree_value_compare(const key_compare &kcomp)
: base_t(kcomp)
{}
- tree_value_compare (const tree_value_compare &x)
+ BOOST_INTRUSIVE_FORCEINLINE tree_value_compare (const tree_value_compare &x)
: base_t(x.base_t::get())
{}
- tree_value_compare &operator=(const tree_value_compare &x)
+ BOOST_INTRUSIVE_FORCEINLINE tree_value_compare &operator=(const tree_value_compare &x)
{ this->base_t::get() = x.base_t::get(); return *this; }
- tree_value_compare &operator=(const key_compare &x)
+ BOOST_INTRUSIVE_FORCEINLINE tree_value_compare &operator=(const key_compare &x)
{ this->base_t::get() = x; return *this; }
BOOST_INTRUSIVE_FORCEINLINE const key_compare &key_comp() const
{ return static_cast<const key_compare &>(*this); }
- BOOST_INTRUSIVE_FORCEINLINE key_compare &key_comp()
- { return static_cast<key_compare &>(*this); }
+ BOOST_INTRUSIVE_FORCEINLINE bool operator()(const key_type &key1, const key_type &key2) const
+ { return this->key_comp()(key1, key2); }
+
+ BOOST_INTRUSIVE_FORCEINLINE bool operator()(const value_type &value1, const value_type &value2) const
+ { return this->key_comp()(KeyOfValue()(value1), KeyOfValue()(value2)); }
+
+ BOOST_INTRUSIVE_FORCEINLINE bool operator()(const key_type &key1, const value_type &value2) const
+ { return this->key_comp()(key1, KeyOfValue()(value2)); }
+
+ BOOST_INTRUSIVE_FORCEINLINE bool operator()(const value_type &value1, const key_type &key2) const
+ { return this->key_comp()(KeyOfValue()(value1), key2); }
template<class U>
- struct is_key
- : boost::intrusive::detail::is_same<const U, const key_type>
- {};
+ BOOST_INTRUSIVE_FORCEINLINE bool operator()( const key_type &key1, const U &nonkey2
+ , typename disable_if_smartref_to<U, ValuePtr>::type* = 0) const
+ { return this->key_comp()(key1, nonkey2); }
template<class U>
- const key_type & key_forward
- (const U &key, typename boost::intrusive::detail::enable_if<is_key<U> >::type* = 0) const
- { return key; }
+ BOOST_INTRUSIVE_FORCEINLINE bool operator()( const U &nonkey1, const key_type &key2
+ , typename disable_if_smartref_to<U, ValuePtr>::type* = 0) const
+ { return this->key_comp()(nonkey1, key2); }
template<class U>
- BOOST_INTRUSIVE_FORCEINLINE const key_type & key_forward
- (const U &key, typename boost::intrusive::detail::disable_if<is_key<U> >::type* = 0) const
- { return KeyOfValue()(key); }
+ BOOST_INTRUSIVE_FORCEINLINE bool operator()( const value_type &value1, const U &nonvalue2
+ , typename disable_if_smartref_to<U, ValuePtr>::type* = 0) const
+ { return this->key_comp()(KeyOfValue()(value1), nonvalue2); }
- template<class KeyType, class KeyType2>
- BOOST_INTRUSIVE_FORCEINLINE bool operator()(const KeyType &key1, const KeyType2 &key2) const
- { return key_compare::operator()(this->key_forward(key1), this->key_forward(key2)); }
+ template<class U>
+ BOOST_INTRUSIVE_FORCEINLINE bool operator()( const U &nonvalue1, const value_type &value2
+ , typename disable_if_smartref_to<U, ValuePtr>::type* = 0) const
+ { return this->key_comp()(nonvalue1, KeyOfValue()(value2)); }
+};
- template<class KeyType, class KeyType2>
- BOOST_INTRUSIVE_FORCEINLINE bool operator()(const KeyType &key1, const KeyType2 &key2)
- { return key_compare::operator()(this->key_forward(key1), this->key_forward(key2)); }
+template<class ValuePtr, class KeyCompare, class KeyOfValue>
+struct tree_value_compare<ValuePtr, KeyCompare, KeyOfValue, true>
+ : public boost::intrusive::detail::ebo_functor_holder<KeyCompare>
+{
+ typedef typename pointer_element<ValuePtr>::type value_type;
+ typedef KeyCompare key_compare;
+ typedef KeyOfValue key_of_value;
+ typedef typename KeyOfValue::type key_type;
+
+ typedef boost::intrusive::detail::ebo_functor_holder<KeyCompare> base_t;
+
+
+ BOOST_INTRUSIVE_FORCEINLINE tree_value_compare()
+ : base_t()
+ {}
+
+ BOOST_INTRUSIVE_FORCEINLINE explicit tree_value_compare(const key_compare &kcomp)
+ : base_t(kcomp)
+ {}
+
+ BOOST_INTRUSIVE_FORCEINLINE tree_value_compare (const tree_value_compare &x)
+ : base_t(x.base_t::get())
+ {}
+
+ BOOST_INTRUSIVE_FORCEINLINE tree_value_compare &operator=(const tree_value_compare &x)
+ { this->base_t::get() = x.base_t::get(); return *this; }
+
+ BOOST_INTRUSIVE_FORCEINLINE tree_value_compare &operator=(const key_compare &x)
+ { this->base_t::get() = x; return *this; }
+
+ BOOST_INTRUSIVE_FORCEINLINE const key_compare &key_comp() const
+ { return static_cast<const key_compare &>(*this); }
+
+ BOOST_INTRUSIVE_FORCEINLINE bool operator()(const key_type &key1, const key_type &key2) const
+ { return this->key_comp()(key1, key2); }
+
+ template<class U>
+ BOOST_INTRUSIVE_FORCEINLINE bool operator()( const key_type &key1, const U &nonkey2
+ , typename disable_if_smartref_to<U, ValuePtr>::type* = 0) const
+ { return this->key_comp()(key1, nonkey2); }
+
+ template<class U>
+ BOOST_INTRUSIVE_FORCEINLINE bool operator()(const U &nonkey1, const key_type &key2
+ , typename disable_if_smartref_to<U, ValuePtr>::type* = 0) const
+ { return this->key_comp()(nonkey1, key2); }
};
} //namespace intrusive{
diff --git a/boost/intrusive/hashtable.hpp b/boost/intrusive/hashtable.hpp
index f9074c0..313da82 100644
--- a/boost/intrusive/hashtable.hpp
+++ b/boost/intrusive/hashtable.hpp
@@ -119,6 +119,8 @@ struct prime_list_holder
static const std::size_t prime_list_size;
};
+#if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
+
//We only support LLP64(Win64) or LP64(most Unix) data models
#ifdef _WIN64 //In 64 bit windows sizeof(size_t) == sizeof(unsigned long long)
#define BOOST_INTRUSIVE_PRIME_C(NUMBER) NUMBER##ULL
@@ -173,6 +175,8 @@ const std::size_t prime_list_holder<Dummy>::prime_list[] = {
#undef BOOST_INTRUSIVE_PRIME_C
#undef BOOST_INTRUSIVE_64_BIT_SIZE_T
+#endif //#if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
+
template<int Dummy>
const std::size_t prime_list_holder<Dummy>::prime_list_size
= sizeof(prime_list)/sizeof(std::size_t);
@@ -251,7 +255,7 @@ struct insert_commit_data_impl
};
template<class Node, class SlistNodePtr>
-inline typename pointer_traits<SlistNodePtr>::template rebind_pointer<Node>::type
+BOOST_INTRUSIVE_FORCEINLINE typename pointer_traits<SlistNodePtr>::template rebind_pointer<Node>::type
dcast_bucket_ptr(const SlistNodePtr &p)
{
typedef typename pointer_traits<SlistNodePtr>::template rebind_pointer<Node>::type node_ptr;
@@ -341,13 +345,13 @@ struct group_functions
}
}
- static void erase_from_group(const slist_node_ptr&, const node_ptr&, detail::false_)
+ BOOST_INTRUSIVE_FORCEINLINE static void erase_from_group(const slist_node_ptr&, const node_ptr&, detail::false_)
{}
- static node_ptr get_last_in_group(const node_ptr &first_in_group, detail::true_)
+ BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_last_in_group(const node_ptr &first_in_group, detail::true_)
{ return group_traits::get_next(first_in_group); }
- static node_ptr get_last_in_group(node_ptr n, detail::false_)
+ BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_last_in_group(node_ptr n, detail::false_)
{ return n; }
static node_ptr get_first_in_group(node_ptr n, detail::true_)
@@ -359,21 +363,21 @@ struct group_functions
return n;
}
- static node_ptr next_group_if_first_in_group(node_ptr ptr)
+ BOOST_INTRUSIVE_FORCEINLINE static node_ptr next_group_if_first_in_group(node_ptr ptr)
{
return node_traits::get_next(group_traits::get_next(ptr));
}
- static node_ptr get_first_in_group(const node_ptr &n, detail::false_)
+ BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_first_in_group(const node_ptr &n, detail::false_)
{ return n; }
- static void insert_in_group(const node_ptr &first_in_group, const node_ptr &n, true_)
+ BOOST_INTRUSIVE_FORCEINLINE static void insert_in_group(const node_ptr &first_in_group, const node_ptr &n, true_)
{ group_algorithms::link_after(first_in_group, n); }
static void insert_in_group(const node_ptr&, const node_ptr&, false_)
{}
- static node_ptr split_group(node_ptr const new_first_in_group)
+ BOOST_INTRUSIVE_FORCEINLINE static node_ptr split_group(node_ptr const new_first_in_group)
{
node_ptr const first((get_first_in_group)(new_first_in_group, detail::true_()));
if(first != new_first_in_group){
@@ -403,7 +407,7 @@ class incremental_rehash_rollback
, split_traits_(split_traits), released_(false)
{}
- void release()
+ BOOST_INTRUSIVE_FORCEINLINE void release()
{ released_ = true; }
~incremental_rehash_rollback()
@@ -426,21 +430,21 @@ class incremental_rehash_rollback
template<class NodeTraits>
struct node_functions
{
- static void store_hash(typename NodeTraits::node_ptr p, std::size_t h, true_)
+ BOOST_INTRUSIVE_FORCEINLINE static void store_hash(typename NodeTraits::node_ptr p, std::size_t h, true_)
{ return NodeTraits::set_hash(p, h); }
- static void store_hash(typename NodeTraits::node_ptr, std::size_t, false_)
+ BOOST_INTRUSIVE_FORCEINLINE static void store_hash(typename NodeTraits::node_ptr, std::size_t, false_)
{}
};
-inline std::size_t hash_to_bucket(std::size_t hash_value, std::size_t bucket_cnt, detail::false_)
+BOOST_INTRUSIVE_FORCEINLINE std::size_t hash_to_bucket(std::size_t hash_value, std::size_t bucket_cnt, detail::false_)
{ return hash_value % bucket_cnt; }
-inline std::size_t hash_to_bucket(std::size_t hash_value, std::size_t bucket_cnt, detail::true_)
+BOOST_INTRUSIVE_FORCEINLINE std::size_t hash_to_bucket(std::size_t hash_value, std::size_t bucket_cnt, detail::true_)
{ return hash_value & (bucket_cnt - 1); }
template<bool Power2Buckets, bool Incremental>
-inline std::size_t hash_to_bucket_split(std::size_t hash_value, std::size_t bucket_cnt, std::size_t split)
+BOOST_INTRUSIVE_FORCEINLINE std::size_t hash_to_bucket_split(std::size_t hash_value, std::size_t bucket_cnt, std::size_t split)
{
std::size_t bucket_number = detail::hash_to_bucket(hash_value, bucket_cnt, detail::bool_<Power2Buckets>());
if(Incremental)
@@ -535,11 +539,11 @@ struct downcast_node_to_value_t
template rebind_pointer
<const ValueTraits>::type const_value_traits_ptr;
- downcast_node_to_value_t(const const_value_traits_ptr &ptr)
+ BOOST_INTRUSIVE_FORCEINLINE downcast_node_to_value_t(const const_value_traits_ptr &ptr)
: base_t(ptr)
{}
- result_type operator()(first_argument_type arg) const
+ BOOST_INTRUSIVE_FORCEINLINE result_type operator()(first_argument_type arg) const
{ return this->base_t::operator()(static_cast<intermediate_argument_type>(arg)); }
};
@@ -554,14 +558,14 @@ struct node_cast_adaptor
typedef typename pointer_traits<NodePtr>::element_type node;
template<class ConvertibleToF, class RealValuTraits>
- node_cast_adaptor(const ConvertibleToF &c2f, const RealValuTraits *traits)
+ BOOST_INTRUSIVE_FORCEINLINE node_cast_adaptor(const ConvertibleToF &c2f, const RealValuTraits *traits)
: base_t(base_t(c2f, traits))
{}
- typename base_t::node_ptr operator()(const slist_node &to_clone)
+ BOOST_INTRUSIVE_FORCEINLINE typename base_t::node_ptr operator()(const slist_node &to_clone)
{ return base_t::operator()(static_cast<const node &>(to_clone)); }
- void operator()(SlistNodePtr to_clone)
+ BOOST_INTRUSIVE_FORCEINLINE void operator()(SlistNodePtr to_clone)
{
base_t::operator()(pointer_traits<NodePtr>::pointer_to(static_cast<node &>(*to_clone)));
}
@@ -610,56 +614,57 @@ struct bucket_plus_vtraits
<value_traits>::type bucket_ptr;
template<class BucketTraitsType>
- bucket_plus_vtraits(const ValueTraits &val_traits, BOOST_FWD_REF(BucketTraitsType) b_traits)
+ BOOST_INTRUSIVE_FORCEINLINE bucket_plus_vtraits(const ValueTraits &val_traits, BOOST_FWD_REF(BucketTraitsType) b_traits)
: data(val_traits, ::boost::forward<BucketTraitsType>(b_traits))
{}
- bucket_plus_vtraits & operator =(const bucket_plus_vtraits &x)
+ BOOST_INTRUSIVE_FORCEINLINE bucket_plus_vtraits & operator =(const bucket_plus_vtraits &x)
{ data.bucket_traits_ = x.data.bucket_traits_; return *this; }
- const_value_traits_ptr priv_value_traits_ptr() const
+ BOOST_INTRUSIVE_FORCEINLINE const_value_traits_ptr priv_value_traits_ptr() const
{ return pointer_traits<const_value_traits_ptr>::pointer_to(this->priv_value_traits()); }
//bucket_value_traits
//
- const bucket_plus_vtraits &get_bucket_value_traits() const
+ BOOST_INTRUSIVE_FORCEINLINE const bucket_plus_vtraits &get_bucket_value_traits() const
{ return *this; }
- bucket_plus_vtraits &get_bucket_value_traits()
+ BOOST_INTRUSIVE_FORCEINLINE bucket_plus_vtraits &get_bucket_value_traits()
{ return *this; }
- const_bucket_value_traits_ptr bucket_value_traits_ptr() const
+ BOOST_INTRUSIVE_FORCEINLINE const_bucket_value_traits_ptr bucket_value_traits_ptr() const
{ return pointer_traits<const_bucket_value_traits_ptr>::pointer_to(this->get_bucket_value_traits()); }
//value traits
//
- const value_traits &priv_value_traits() const
+ BOOST_INTRUSIVE_FORCEINLINE const value_traits &priv_value_traits() const
{ return this->data; }
- value_traits &priv_value_traits()
+ BOOST_INTRUSIVE_FORCEINLINE value_traits &priv_value_traits()
{ return this->data; }
//bucket_traits
//
- const bucket_traits &priv_bucket_traits() const
+ BOOST_INTRUSIVE_FORCEINLINE const bucket_traits &priv_bucket_traits() const
{ return this->data.bucket_traits_; }
- bucket_traits &priv_bucket_traits()
+ BOOST_INTRUSIVE_FORCEINLINE bucket_traits &priv_bucket_traits()
{ return this->data.bucket_traits_; }
//bucket operations
- bucket_ptr priv_bucket_pointer() const
+ BOOST_INTRUSIVE_FORCEINLINE bucket_ptr priv_bucket_pointer() const
{ return this->priv_bucket_traits().bucket_begin(); }
typename slist_impl::size_type priv_bucket_count() const
{ return this->priv_bucket_traits().bucket_count(); }
- bucket_ptr priv_invalid_bucket() const
+ BOOST_INTRUSIVE_FORCEINLINE bucket_ptr priv_invalid_bucket() const
{
const bucket_traits &rbt = this->priv_bucket_traits();
return rbt.bucket_begin() + rbt.bucket_count();
}
- siterator priv_invalid_local_it() const
+
+ BOOST_INTRUSIVE_FORCEINLINE siterator priv_invalid_local_it() const
{ return this->priv_bucket_traits().bucket_begin()->before_begin(); }
template<class NodeDisposer>
@@ -748,7 +753,7 @@ struct bucket_plus_vtraits
}
template<class NodeDisposer>
- static void priv_erase_node(bucket_type &b, siterator i, NodeDisposer node_disposer, detail::false_) //optimize multikey
+ BOOST_INTRUSIVE_FORCEINLINE static void priv_erase_node(bucket_type &b, siterator i, NodeDisposer node_disposer, detail::false_) //optimize multikey
{ b.erase_after_and_dispose(b.previous(i), node_disposer); }
template<class NodeDisposer, bool OptimizeMultikey>
@@ -807,7 +812,7 @@ struct bucket_plus_vtraits
return num_erased;
}
- static siterator priv_get_last(bucket_type &b, detail::false_) //NOT optimize multikey
+ BOOST_INTRUSIVE_FORCEINLINE static siterator priv_get_last(bucket_type &b, detail::false_) //NOT optimize multikey
{ return b.previous(b.end()); }
static siterator priv_get_previous(bucket_type &b, siterator i, detail::true_) //optimize multikey
@@ -822,7 +827,7 @@ struct bucket_plus_vtraits
return bucket_type::s_iterator_to(n);
}
- static siterator priv_get_previous(bucket_type &b, siterator i, detail::false_) //NOT optimize multikey
+ BOOST_INTRUSIVE_FORCEINLINE static siterator priv_get_previous(bucket_type &b, siterator i, detail::false_) //NOT optimize multikey
{ return b.previous(i); }
std::size_t priv_get_bucket_num_no_hash_store(siterator it, detail::true_) //optimize multikey
@@ -858,22 +863,22 @@ struct bucket_plus_vtraits
return static_cast<std::size_t>(&b - &*f);
}
- static std::size_t priv_stored_hash(slist_node_ptr n, detail::true_) //store_hash
+ BOOST_INTRUSIVE_FORCEINLINE static std::size_t priv_stored_hash(slist_node_ptr n, detail::true_) //store_hash
{ return node_traits::get_hash(detail::dcast_bucket_ptr<node>(n)); }
- static std::size_t priv_stored_hash(slist_node_ptr, detail::false_) //NO store_hash
+ BOOST_INTRUSIVE_FORCEINLINE static std::size_t priv_stored_hash(slist_node_ptr, detail::false_) //NO store_hash
{ return std::size_t(-1); }
- node &priv_value_to_node(reference v)
+ BOOST_INTRUSIVE_FORCEINLINE node &priv_value_to_node(reference v)
{ return *this->priv_value_traits().to_node_ptr(v); }
- const node &priv_value_to_node(const_reference v) const
+ BOOST_INTRUSIVE_FORCEINLINE const node &priv_value_to_node(const_reference v) const
{ return *this->priv_value_traits().to_node_ptr(v); }
- reference priv_value_from_slist_node(slist_node_ptr n)
+ BOOST_INTRUSIVE_FORCEINLINE reference priv_value_from_slist_node(slist_node_ptr n)
{ return *this->priv_value_traits().to_value_ptr(detail::dcast_bucket_ptr<node>(n)); }
- const_reference priv_value_from_slist_node(slist_node_ptr n) const
+ BOOST_INTRUSIVE_FORCEINLINE const_reference priv_value_from_slist_node(slist_node_ptr n) const
{ return *this->priv_value_traits().to_value_ptr(detail::dcast_bucket_ptr<node>(n)); }
void priv_clear_buckets(const bucket_ptr buckets_ptr, const size_type bucket_cnt)
@@ -889,19 +894,19 @@ struct bucket_plus_vtraits
}
}
- std::size_t priv_stored_or_compute_hash(const value_type &v, detail::true_) const //For store_hash == true
+ BOOST_INTRUSIVE_FORCEINLINE std::size_t priv_stored_or_compute_hash(const value_type &v, detail::true_) const //For store_hash == true
{ return node_traits::get_hash(this->priv_value_traits().to_node_ptr(v)); }
typedef hashtable_iterator<bucket_plus_vtraits, false> iterator;
typedef hashtable_iterator<bucket_plus_vtraits, true> const_iterator;
- iterator end()
+ BOOST_INTRUSIVE_FORCEINLINE iterator end()
{ return iterator(this->priv_invalid_local_it(), 0); }
- const_iterator end() const
+ BOOST_INTRUSIVE_FORCEINLINE const_iterator end() const
{ return this->cend(); }
- const_iterator cend() const
+ BOOST_INTRUSIVE_FORCEINLINE const_iterator cend() const
{ return const_iterator(this->priv_invalid_local_it(), 0); }
static size_type suggested_upper_bucket_count(size_type n)
@@ -926,9 +931,10 @@ struct bucket_plus_vtraits
struct data_type : public ValueTraits
{
template<class BucketTraitsType>
- data_type(const ValueTraits &val_traits, BOOST_FWD_REF(BucketTraitsType) b_traits)
+ BOOST_INTRUSIVE_FORCEINLINE data_type(const ValueTraits &val_traits, BOOST_FWD_REF(BucketTraitsType) b_traits)
: ValueTraits(val_traits), bucket_traits_(::boost::forward<BucketTraitsType>(b_traits))
{}
+
bucket_traits bucket_traits_;
} data;
};
@@ -1020,11 +1026,11 @@ struct bucket_hash_t
typedef detail::ebo_functor_holder<hasher> base_t;
template<class BucketTraitsType>
- bucket_hash_t(const ValueTraits &val_traits, BOOST_FWD_REF(BucketTraitsType) b_traits, const hasher & h)
+ BOOST_INTRUSIVE_FORCEINLINE bucket_hash_t(const ValueTraits &val_traits, BOOST_FWD_REF(BucketTraitsType) b_traits, const hasher & h)
: detail::ebo_functor_holder<hasher>(h), bucket_plus_vtraits_t(val_traits, ::boost::forward<BucketTraitsType>(b_traits))
{}
- const hasher &priv_hasher() const
+ BOOST_INTRUSIVE_FORCEINLINE const hasher &priv_hasher() const
{ return this->base_t::get(); }
hasher &priv_hasher()
@@ -1032,7 +1038,7 @@ struct bucket_hash_t
using bucket_plus_vtraits_t::priv_stored_or_compute_hash; //For store_hash == true
- std::size_t priv_stored_or_compute_hash(const value_type &v, detail::false_) const //For store_hash == false
+ BOOST_INTRUSIVE_FORCEINLINE std::size_t priv_stored_or_compute_hash(const value_type &v, detail::false_) const //For store_hash == false
{ return this->priv_hasher()(key_of_value()(v)); }
};
@@ -1077,19 +1083,19 @@ struct bucket_hash_equal_t
, equal_holder_t(e)
{}
- bucket_ptr priv_get_cache()
+ BOOST_INTRUSIVE_FORCEINLINE bucket_ptr priv_get_cache()
{ return this->bucket_hash_type::priv_bucket_pointer(); }
- void priv_set_cache(const bucket_ptr &)
+ BOOST_INTRUSIVE_FORCEINLINE void priv_set_cache(const bucket_ptr &)
{}
- size_type priv_get_cache_bucket_num()
+ BOOST_INTRUSIVE_FORCEINLINE size_type priv_get_cache_bucket_num()
{ return 0u; }
- void priv_initialize_cache()
+ BOOST_INTRUSIVE_FORCEINLINE void priv_initialize_cache()
{}
- void priv_swap_cache(bucket_hash_equal_t &)
+ BOOST_INTRUSIVE_FORCEINLINE void priv_swap_cache(bucket_hash_equal_t &)
{}
siterator priv_begin() const
@@ -1105,19 +1111,19 @@ struct bucket_hash_equal_t
return this->bucket_hash_type::priv_invalid_local_it();
}
- void priv_insertion_update_cache(size_type)
+ BOOST_INTRUSIVE_FORCEINLINE void priv_insertion_update_cache(size_type)
{}
- void priv_erasure_update_cache_range(size_type, size_type)
+ BOOST_INTRUSIVE_FORCEINLINE void priv_erasure_update_cache_range(size_type, size_type)
{}
- void priv_erasure_update_cache()
+ BOOST_INTRUSIVE_FORCEINLINE void priv_erasure_update_cache()
{}
- const key_equal &priv_equal() const
+ BOOST_INTRUSIVE_FORCEINLINE const key_equal &priv_equal() const
{ return this->equal_holder_t::get(); }
- key_equal &priv_equal()
+ BOOST_INTRUSIVE_FORCEINLINE key_equal &priv_equal()
{ return this->equal_holder_t::get(); }
};
@@ -1151,22 +1157,22 @@ struct bucket_hash_equal_t<ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, VoidOrK
typedef typename detail::unordered_bucket_ptr_impl
<typename bucket_hash_type::value_traits>::type bucket_ptr;
- bucket_ptr &priv_get_cache()
+ BOOST_INTRUSIVE_FORCEINLINE bucket_ptr &priv_get_cache()
{ return cached_begin_; }
- const bucket_ptr &priv_get_cache() const
+ BOOST_INTRUSIVE_FORCEINLINE const bucket_ptr &priv_get_cache() const
{ return cached_begin_; }
- void priv_set_cache(const bucket_ptr &p)
+ BOOST_INTRUSIVE_FORCEINLINE void priv_set_cache(const bucket_ptr &p)
{ cached_begin_ = p; }
- std::size_t priv_get_cache_bucket_num()
+ BOOST_INTRUSIVE_FORCEINLINE std::size_t priv_get_cache_bucket_num()
{ return this->cached_begin_ - this->bucket_hash_type::priv_bucket_pointer(); }
- void priv_initialize_cache()
+ BOOST_INTRUSIVE_FORCEINLINE void priv_initialize_cache()
{ this->cached_begin_ = this->bucket_hash_type::priv_invalid_bucket(); }
- void priv_swap_cache(bucket_hash_equal_t &other)
+ BOOST_INTRUSIVE_FORCEINLINE void priv_swap_cache(bucket_hash_equal_t &other)
{
::boost::adl_move_swap(this->cached_begin_, other.cached_begin_);
}
@@ -1189,10 +1195,10 @@ struct bucket_hash_equal_t<ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, VoidOrK
}
}
- const key_equal &priv_equal() const
+ BOOST_INTRUSIVE_FORCEINLINE const key_equal &priv_equal() const
{ return this->equal_holder_t::get(); }
- key_equal &priv_equal()
+ BOOST_INTRUSIVE_FORCEINLINE key_equal &priv_equal()
{ return this->equal_holder_t::get(); }
void priv_erasure_update_cache_range(size_type first_bucket_num, size_type last_bucket_num)
@@ -1243,10 +1249,13 @@ struct hashtable_size_traits_wrapper
size_traits size_traits_;
- const size_traits &priv_size_traits() const
+ typedef const size_traits & size_traits_const_t;
+ typedef size_traits & size_traits_t;
+
+ BOOST_INTRUSIVE_FORCEINLINE size_traits_const_t priv_size_traits() const
{ return size_traits_; }
- size_traits &priv_size_traits()
+ BOOST_INTRUSIVE_FORCEINLINE size_traits_t priv_size_traits()
{ return size_traits_; }
};
@@ -1265,18 +1274,13 @@ struct hashtable_size_traits_wrapper<DeriveFrom, SizeType, false>
typedef detail::size_holder< false, SizeType> size_traits;
- const size_traits &priv_size_traits() const
- { return size_traits_; }
-
- size_traits &priv_size_traits()
- { return size_traits_; }
+ typedef size_traits size_traits_const_t;
+ typedef size_traits size_traits_t;
- static size_traits size_traits_;
+ BOOST_INTRUSIVE_FORCEINLINE size_traits priv_size_traits() const
+ { return size_traits(); }
};
-template<class DeriveFrom, class SizeType>
-detail::size_holder< false, SizeType > hashtable_size_traits_wrapper<DeriveFrom, SizeType, false>::size_traits_;
-
//hashdata_internal
//Stores bucket_hash_equal_t and split_traits
template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyHash, class VoidOrKeyEqual, class BucketTraits, class SizeType, std::size_t BoolFlags>
@@ -1360,10 +1364,10 @@ struct hashdata_internal
: internal_type(val_traits, ::boost::forward<BucketTraitsType>(b_traits), h, e)
{}
- split_traits &priv_split_traits()
+ BOOST_INTRUSIVE_FORCEINLINE typename internal_type::size_traits_t priv_split_traits()
{ return this->priv_size_traits(); }
- const split_traits &priv_split_traits() const
+ BOOST_INTRUSIVE_FORCEINLINE typename internal_type::size_traits_const_t priv_split_traits() const
{ return this->priv_size_traits(); }
~hashdata_internal()
@@ -1402,12 +1406,12 @@ struct hashdata_internal
{ return bucket_plus_vtraits<ValueTraits, BucketTraits>::priv_stored_hash(n, false_value); }
//public functions
- SizeType split_count() const
+ BOOST_INTRUSIVE_FORCEINLINE SizeType split_count() const
{
return this->priv_split_traits().get_size();
}
- iterator iterator_to(reference value)
+ BOOST_INTRUSIVE_FORCEINLINE iterator iterator_to(reference value)
{
return iterator(bucket_type::s_iterator_to
(this->priv_value_to_node(value)), &this->get_bucket_value_traits());
@@ -1454,19 +1458,19 @@ struct hashdata_internal
return const_local_iterator(sit, this->priv_value_traits_ptr());
}
- size_type bucket_count() const
+ BOOST_INTRUSIVE_FORCEINLINE size_type bucket_count() const
{ return this->priv_bucket_count(); }
- size_type bucket_size(size_type n) const
+ BOOST_INTRUSIVE_FORCEINLINE size_type bucket_size(size_type n) const
{ return this->priv_bucket_pointer()[n].size(); }
- bucket_ptr bucket_pointer() const
+ BOOST_INTRUSIVE_FORCEINLINE bucket_ptr bucket_pointer() const
{ return this->priv_bucket_pointer(); }
- local_iterator begin(size_type n)
+ BOOST_INTRUSIVE_FORCEINLINE local_iterator begin(size_type n)
{ return local_iterator(this->priv_bucket_pointer()[n].begin(), this->priv_value_traits_ptr()); }
- const_local_iterator begin(size_type n) const
+ BOOST_INTRUSIVE_FORCEINLINE const_local_iterator begin(size_type n) const
{ return this->cbegin(n); }
const_local_iterator cbegin(size_type n) const
@@ -1481,7 +1485,7 @@ struct hashdata_internal
local_iterator end(size_type n)
{ return local_iterator(this->priv_bucket_pointer()[n].end(), this->priv_value_traits_ptr()); }
- const_local_iterator end(size_type n) const
+ BOOST_INTRUSIVE_FORCEINLINE const_local_iterator end(size_type n) const
{ return this->cend(n); }
const_local_iterator cend(size_type n) const
@@ -1493,19 +1497,19 @@ struct hashdata_internal
//Public functions for hashtable_impl
- iterator begin()
+ BOOST_INTRUSIVE_FORCEINLINE iterator begin()
{ return iterator(this->priv_begin(), &this->get_bucket_value_traits()); }
- const_iterator begin() const
+ BOOST_INTRUSIVE_FORCEINLINE const_iterator begin() const
{ return this->cbegin(); }
- const_iterator cbegin() const
+ BOOST_INTRUSIVE_FORCEINLINE const_iterator cbegin() const
{ return const_iterator(this->priv_begin(), &this->get_bucket_value_traits()); }
- hasher hash_function() const
+ BOOST_INTRUSIVE_FORCEINLINE hasher hash_function() const
{ return this->priv_hasher(); }
- key_equal key_eq() const
+ BOOST_INTRUSIVE_FORCEINLINE key_equal key_eq() const
{ return this->priv_equal(); }
};
@@ -1790,15 +1794,10 @@ class hashtable_impl
{
this->priv_swap_cache(x);
x.priv_initialize_cache();
- if(constant_time_size){
- this->priv_size_traits().set_size(size_type(0));
- this->priv_size_traits().set_size(x.priv_size_traits().get_size());
- x.priv_size_traits().set_size(size_type(0));
- }
- if(incremental){
- this->priv_split_traits().set_size(x.priv_split_traits().get_size());
- x.priv_split_traits().set_size(size_type(0));
- }
+ this->priv_size_traits().set_size(x.priv_size_traits().get_size());
+ x.priv_size_traits().set_size(size_type(0));
+ this->priv_split_traits().set_size(x.priv_split_traits().get_size());
+ x.priv_split_traits().set_size(size_type(0));
}
//! <b>Effects</b>: to-do
@@ -1946,8 +1945,8 @@ class hashtable_impl
::boost::adl_move_swap(this->priv_bucket_traits(), other.priv_bucket_traits());
::boost::adl_move_swap(this->priv_value_traits(), other.priv_value_traits());
this->priv_swap_cache(other);
- ::boost::adl_move_swap(this->priv_size_traits(), other.priv_size_traits());
- ::boost::adl_move_swap(this->priv_split_traits(), other.priv_split_traits());
+ this->priv_size_traits().swap(other.priv_size_traits());
+ this->priv_split_traits().swap(other.priv_split_traits());
}
//! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw
@@ -1970,7 +1969,7 @@ class hashtable_impl
//! <b>Throws</b>: If cloner or hasher throw or hash or equality predicate copying
//! throws. Basic guarantee.
template <class Cloner, class Disposer>
- void clone_from(const hashtable_impl &src, Cloner cloner, Disposer disposer)
+ BOOST_INTRUSIVE_FORCEINLINE void clone_from(const hashtable_impl &src, Cloner cloner, Disposer disposer)
{ this->priv_clone_from(src, cloner, disposer); }
//! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw
@@ -1993,7 +1992,7 @@ class hashtable_impl
//! <b>Throws</b>: If cloner or hasher throw or hash or equality predicate copying
//! throws. Basic guarantee.
template <class Cloner, class Disposer>
- void clone_from(BOOST_RV_REF(hashtable_impl) src, Cloner cloner, Disposer disposer)
+ BOOST_INTRUSIVE_FORCEINLINE void clone_from(BOOST_RV_REF(hashtable_impl) src, Cloner cloner, Disposer disposer)
{ this->priv_clone_from(static_cast<hashtable_impl&>(src), cloner, disposer); }
//! <b>Requires</b>: value must be an lvalue
@@ -2160,7 +2159,7 @@ class hashtable_impl
//! objects are inserted or erased from the unordered_set.
//!
//! After a successful rehashing insert_commit_data remains valid.
- std::pair<iterator, bool> insert_unique_check
+ BOOST_INTRUSIVE_FORCEINLINE std::pair<iterator, bool> insert_unique_check
( const key_type &key, insert_commit_data &commit_data)
{ return this->insert_unique_check(key, this->priv_hasher(), this->priv_equal(), commit_data); }
@@ -2204,7 +2203,7 @@ class hashtable_impl
//!
//! <b>Note</b>: Invalidates the iterators (but not the references)
//! to the erased element. No destructors are called.
- void erase(const_iterator i)
+ BOOST_INTRUSIVE_FORCEINLINE void erase(const_iterator i)
{ this->erase_and_dispose(i, detail::null_disposer()); }
//! <b>Effects</b>: Erases the range pointed to by b end e.
@@ -2216,7 +2215,7 @@ class hashtable_impl
//!
//! <b>Note</b>: Invalidates the iterators (but not the references)
//! to the erased elements. No destructors are called.
- void erase(const_iterator b, const_iterator e)
+ BOOST_INTRUSIVE_FORCEINLINE void erase(const_iterator b, const_iterator e)
{ this->erase_and_dispose(b, e, detail::null_disposer()); }
//! <b>Effects</b>: Erases all the elements with the given value.
@@ -2231,7 +2230,7 @@ class hashtable_impl
//!
//! <b>Note</b>: Invalidates the iterators (but not the references)
//! to the erased elements. No destructors are called.
- size_type erase(const key_type &key)
+ BOOST_INTRUSIVE_FORCEINLINE size_type erase(const key_type &key)
{ return this->erase(key, this->priv_hasher(), this->priv_equal()); }
//! <b>Requires</b>: "hash_func" must be a hash function that induces
@@ -2255,7 +2254,7 @@ class hashtable_impl
//! <b>Note</b>: Invalidates the iterators (but not the references)
//! to the erased elements. No destructors are called.
template<class KeyType, class KeyHasher, class KeyEqual>
- size_type erase(const KeyType& key, KeyHasher hash_func, KeyEqual equal_func)
+ BOOST_INTRUSIVE_FORCEINLINE size_type erase(const KeyType& key, KeyHasher hash_func, KeyEqual equal_func)
{ return this->erase_and_dispose(key, hash_func, equal_func, detail::null_disposer()); }
//! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
@@ -2342,7 +2341,7 @@ class hashtable_impl
//! <b>Note</b>: Invalidates the iterators (but not the references)
//! to the erased elements. No destructors are called.
template<class Disposer>
- size_type erase_and_dispose(const key_type &key, Disposer disposer)
+ BOOST_INTRUSIVE_FORCEINLINE size_type erase_and_dispose(const key_type &key, Disposer disposer)
{ return this->erase_and_dispose(key, this->priv_hasher(), this->priv_equal(), disposer); }
//! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
@@ -2440,7 +2439,7 @@ class hashtable_impl
//! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
//!
//! <b>Throws</b>: If the internal hasher or the equality functor throws.
- size_type count(const key_type &key) const
+ BOOST_INTRUSIVE_FORCEINLINE size_type count(const key_type &key) const
{ return this->count(key, this->priv_hasher(), this->priv_equal()); }
//! <b>Requires</b>: "hash_func" must be a hash function that induces
@@ -2471,7 +2470,7 @@ class hashtable_impl
//! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
//!
//! <b>Throws</b>: If the internal hasher or the equality functor throws.
- iterator find(const key_type &key)
+ BOOST_INTRUSIVE_FORCEINLINE iterator find(const key_type &key)
{ return this->find(key, this->priv_hasher(), this->priv_equal()); }
//! <b>Requires</b>: "hash_func" must be a hash function that induces
@@ -2509,7 +2508,7 @@ class hashtable_impl
//! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
//!
//! <b>Throws</b>: If the internal hasher or the equality functor throws.
- const_iterator find(const key_type &key) const
+ BOOST_INTRUSIVE_FORCEINLINE const_iterator find(const key_type &key) const
{ return this->find(key, this->priv_hasher(), this->priv_equal()); }
//! <b>Requires</b>: "hash_func" must be a hash function that induces
@@ -2549,7 +2548,7 @@ class hashtable_impl
//! <b>Complexity</b>: Average case O(this->count(value)). Worst case O(this->size()).
//!
//! <b>Throws</b>: If the internal hasher or the equality functor throws.
- std::pair<iterator,iterator> equal_range(const key_type &key)
+ BOOST_INTRUSIVE_FORCEINLINE std::pair<iterator,iterator> equal_range(const key_type &key)
{ return this->equal_range(key, this->priv_hasher(), this->priv_equal()); }
//! <b>Requires</b>: "hash_func" must be a hash function that induces
@@ -2590,7 +2589,7 @@ class hashtable_impl
//! <b>Complexity</b>: Average case O(this->count(value)). Worst case O(this->size()).
//!
//! <b>Throws</b>: If the internal hasher or the equality functor throws.
- std::pair<const_iterator, const_iterator>
+ BOOST_INTRUSIVE_FORCEINLINE std::pair<const_iterator, const_iterator>
equal_range(const key_type &key) const
{ return this->equal_range(key, this->priv_hasher(), this->priv_equal()); }
@@ -2725,7 +2724,7 @@ class hashtable_impl
//! <b>Throws</b>: If the hash functor throws.
//!
//! <b>Note</b>: the return value is in the range [0, this->bucket_count()).
- size_type bucket(const key_type& k) const
+ BOOST_INTRUSIVE_FORCEINLINE size_type bucket(const key_type& k) const
{ return this->bucket(k, this->priv_hasher()); }
//! <b>Requires</b>: "hash_func" must be a hash function that induces
@@ -2741,7 +2740,7 @@ class hashtable_impl
//!
//! <b>Note</b>: the return value is in the range [0, this->bucket_count()).
template<class KeyType, class KeyHasher>
- size_type bucket(const KeyType& k, KeyHasher hash_func) const
+ BOOST_INTRUSIVE_FORCEINLINE size_type bucket(const KeyType& k, KeyHasher hash_func) const
{ return this->priv_hash_to_bucket(hash_func(k)); }
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
@@ -2838,101 +2837,52 @@ class hashtable_impl
//! new_bucket_traits.bucket_count() can be bigger or smaller than this->bucket_count().
//! 'new_bucket_traits' copy constructor should not throw.
//!
- //! <b>Effects</b>: Updates the internal reference with the new bucket, erases
- //! the values from the old bucket and inserts then in the new one.
+ //! <b>Effects</b>:
+ //! If `new_bucket_traits.bucket_begin() == this->bucket_pointer()` is false,
+ //! unlinks values from the old bucket and inserts then in the new one according
+ //! to the hash value of values.
+ //!
+ //! If `new_bucket_traits.bucket_begin() == this->bucket_pointer()` is true,
+ //! the implementations avoids moving values as much as possible.
+ //!
//! Bucket traits hold by *this is assigned from new_bucket_traits.
//! If the container is configured as incremental<>, the split bucket is set
//! to the new bucket_count().
//!
//! If store_hash option is true, this method does not use the hash function.
+ //! If false, the implementation tries to minimize calls to the hash function
+ //! (e.g. once for equivalent values if optimize_multikey<true> is true).
+ //!
+ //! If rehash is successful updates the internal bucket_traits with new_bucket_traits.
//!
//! <b>Complexity</b>: Average case linear in this->size(), worst case quadratic.
//!
//! <b>Throws</b>: If the hasher functor throws. Basic guarantee.
- void rehash(const bucket_traits &new_bucket_traits)
- {
- const bucket_ptr new_buckets = new_bucket_traits.bucket_begin();
- size_type new_bucket_count = new_bucket_traits.bucket_count();
- const bucket_ptr old_buckets = this->priv_bucket_pointer();
- size_type old_bucket_count = this->priv_bucket_count();
-
- //Check power of two bucket array if the option is activated
- BOOST_INTRUSIVE_INVARIANT_ASSERT
- (!power_2_buckets || (0 == (new_bucket_count & (new_bucket_count-1u))));
-
- size_type n = this->priv_get_cache_bucket_num();
- const bool same_buffer = old_buckets == new_buckets;
- //If the new bucket length is a common factor
- //of the old one we can avoid hash calculations.
- const bool fast_shrink = (!incremental) && (old_bucket_count >= new_bucket_count) &&
- (power_2_buckets || (old_bucket_count % new_bucket_count) == 0);
- //If we are shrinking the same bucket array and it's
- //is a fast shrink, just rehash the last nodes
- size_type new_first_bucket_num = new_bucket_count;
- if(same_buffer && fast_shrink && (n < new_bucket_count)){
- new_first_bucket_num = n;
- n = new_bucket_count;
- }
-
- //Anti-exception stuff: they destroy the elements if something goes wrong.
- //If the source and destination buckets are the same, the second rollback function
- //is harmless, because all elements have been already unlinked and destroyed
- typedef detail::init_disposer<node_algorithms> NodeDisposer;
- typedef detail::exception_array_disposer<bucket_type, NodeDisposer, size_type> ArrayDisposer;
- NodeDisposer node_disp;
- ArrayDisposer rollback1(new_buckets[0], node_disp, new_bucket_count);
- ArrayDisposer rollback2(old_buckets[0], node_disp, old_bucket_count);
-
- //Put size in a safe value for rollback exception
- size_type const size_backup = this->priv_size_traits().get_size();
- this->priv_size_traits().set_size(0);
- //Put cache to safe position
- this->priv_initialize_cache();
- this->priv_insertion_update_cache(size_type(0u));
-
- //Iterate through nodes
- for(; n < old_bucket_count; ++n){
- bucket_type &old_bucket = old_buckets[n];
- if(!fast_shrink){
- for( siterator before_i(old_bucket.before_begin()), i(old_bucket.begin()), end_sit(old_bucket.end())
- ; i != end_sit
- ; i = before_i, ++i){
- const value_type &v = this->priv_value_from_slist_node(i.pointed_node());
- const std::size_t hash_value = this->priv_stored_or_compute_hash(v, store_hash_t());
- const size_type new_n = detail::hash_to_bucket_split<power_2_buckets, incremental>
- (hash_value, new_bucket_count, new_bucket_count);
- if(cache_begin && new_n < new_first_bucket_num)
- new_first_bucket_num = new_n;
- siterator const last = (priv_last_in_group)(i);
- if(same_buffer && new_n == n){
- before_i = last;
- }
- else{
- bucket_type &new_b = new_buckets[new_n];
- new_b.splice_after(new_b.before_begin(), old_bucket, before_i, last);
- }
- }
- }
- else{
- const size_type new_n = detail::hash_to_bucket_split<power_2_buckets, incremental>(n, new_bucket_count, new_bucket_count);
- if(cache_begin && new_n < new_first_bucket_num)
- new_first_bucket_num = new_n;
- bucket_type &new_b = new_buckets[new_n];
- new_b.splice_after( new_b.before_begin()
- , old_bucket
- , old_bucket.before_begin()
- , bucket_plus_vtraits_t::priv_get_last(old_bucket, optimize_multikey_t()));
- }
- }
+ BOOST_INTRUSIVE_FORCEINLINE void rehash(const bucket_traits &new_bucket_traits)
+ { this->rehash_impl(new_bucket_traits, false); }
- this->priv_size_traits().set_size(size_backup);
- this->priv_split_traits().set_size(new_bucket_count);
- this->priv_bucket_traits() = new_bucket_traits;
- this->priv_initialize_cache();
- this->priv_insertion_update_cache(new_first_bucket_num);
- rollback1.release();
- rollback2.release();
- }
+ //! <b>Note</b>: This function is used when keys from inserted elements are changed
+ //! (e.g. a language change when key is a string) but uniqueness and hash properties are
+ //! preserved so a fast full rehash recovers invariants for *this without extracting and
+ //! reinserting all elements again.
+ //!
+ //! <b>Requires</b>: Calls produced to the hash function should not alter the value uniqueness
+ //! properties of already inserted elements. If hasher(key1) == hasher(key2) was true when
+ //! elements were inserted, it shall be true during calls produced in the execution of this function.
+ //!
+ //! key_equal is not called inside this function so it is assumed that key_equal(value1, value2)
+ //! should produce the same results as before for inserted elements.
+ //!
+ //! <b>Effects</b>: Reprocesses all values hold by *this, recalculating their hash values
+ //! and redistributing them though the buckets.
+ //!
+ //! If store_hash option is true, this method uses the hash function and updates the stored hash value.
+ //!
+ //! <b>Complexity</b>: Average case linear in this->size(), worst case quadratic.
+ //!
+ //! <b>Throws</b>: If the hasher functor throws. Basic guarantee.
+ BOOST_INTRUSIVE_FORCEINLINE void full_rehash()
+ { this->rehash_impl(this->priv_bucket_traits(), true); }
//! <b>Requires</b>:
//!
@@ -3113,9 +3063,113 @@ class hashtable_impl
{ return !(x < y); }
/// @cond
- void check() const {}
+ BOOST_INTRUSIVE_FORCEINLINE void check() const {}
private:
+ void rehash_impl(const bucket_traits &new_bucket_traits, bool do_full_rehash)
+ {
+ const bucket_ptr new_buckets = new_bucket_traits.bucket_begin();
+ size_type new_bucket_count = new_bucket_traits.bucket_count();
+ const bucket_ptr old_buckets = this->priv_bucket_pointer();
+ size_type old_bucket_count = this->priv_bucket_count();
+
+ //Check power of two bucket array if the option is activated
+ BOOST_INTRUSIVE_INVARIANT_ASSERT
+ (!power_2_buckets || (0 == (new_bucket_count & (new_bucket_count-1u))));
+
+ size_type n = this->priv_get_cache_bucket_num();
+ const bool same_buffer = old_buckets == new_buckets;
+ //If the new bucket length is a common factor
+ //of the old one we can avoid hash calculations.
+ const bool fast_shrink = (!do_full_rehash) && (!incremental) && (old_bucket_count >= new_bucket_count) &&
+ (power_2_buckets || (old_bucket_count % new_bucket_count) == 0);
+ //If we are shrinking the same bucket array and it's
+ //is a fast shrink, just rehash the last nodes
+ size_type new_first_bucket_num = new_bucket_count;
+ if(same_buffer && fast_shrink && (n < new_bucket_count)){
+ new_first_bucket_num = n;
+ n = new_bucket_count;
+ }
+
+ //Anti-exception stuff: they destroy the elements if something goes wrong.
+ //If the source and destination buckets are the same, the second rollback function
+ //is harmless, because all elements have been already unlinked and destroyed
+ typedef detail::init_disposer<node_algorithms> NodeDisposer;
+ typedef detail::exception_array_disposer<bucket_type, NodeDisposer, size_type> ArrayDisposer;
+ NodeDisposer node_disp;
+ ArrayDisposer rollback1(new_buckets[0], node_disp, new_bucket_count);
+ ArrayDisposer rollback2(old_buckets[0], node_disp, old_bucket_count);
+
+ //Put size in a safe value for rollback exception
+ size_type const size_backup = this->priv_size_traits().get_size();
+ this->priv_size_traits().set_size(0);
+ //Put cache to safe position
+ this->priv_initialize_cache();
+ this->priv_insertion_update_cache(size_type(0u));
+
+ //Iterate through nodes
+ for(; n < old_bucket_count; ++n){
+ bucket_type &old_bucket = old_buckets[n];
+ if(!fast_shrink){
+ for( siterator before_i(old_bucket.before_begin()), i(old_bucket.begin()), end_sit(old_bucket.end())
+ ; i != end_sit
+ ; i = before_i, ++i){
+
+ //First obtain hash value (and store it if do_full_rehash)
+ std::size_t hash_value;
+ if(do_full_rehash){
+ value_type &v = this->priv_value_from_slist_node(i.pointed_node());
+ hash_value = this->priv_hasher()(key_of_value()(v));
+ node_functions_t::store_hash(pointer_traits<node_ptr>::pointer_to(this->priv_value_to_node(v)), hash_value, store_hash_t());
+ }
+ else{
+ const value_type &v = this->priv_value_from_slist_node(i.pointed_node());
+ hash_value = this->priv_stored_or_compute_hash(v, store_hash_t());
+ }
+
+ //Now calculate the new bucket position
+ const size_type new_n = detail::hash_to_bucket_split<power_2_buckets, incremental>
+ (hash_value, new_bucket_count, new_bucket_count);
+
+ //Update first used bucket cache
+ if(cache_begin && new_n < new_first_bucket_num)
+ new_first_bucket_num = new_n;
+
+ //If the target bucket is new, transfer the whole group
+ siterator const last = (priv_last_in_group)(i);
+
+ if(same_buffer && new_n == n){
+ before_i = last;
+ }
+ else{
+ bucket_type &new_b = new_buckets[new_n];
+ new_b.splice_after(new_b.before_begin(), old_bucket, before_i, last);
+ }
+ }
+ }
+ else{
+ const size_type new_n = detail::hash_to_bucket_split<power_2_buckets, incremental>(n, new_bucket_count, new_bucket_count);
+ if(cache_begin && new_n < new_first_bucket_num)
+ new_first_bucket_num = new_n;
+ bucket_type &new_b = new_buckets[new_n];
+ new_b.splice_after( new_b.before_begin()
+ , old_bucket
+ , old_bucket.before_begin()
+ , bucket_plus_vtraits_t::priv_get_last(old_bucket, optimize_multikey_t()));
+ }
+ }
+
+ this->priv_size_traits().set_size(size_backup);
+ this->priv_split_traits().set_size(new_bucket_count);
+ if(&new_bucket_traits != &this->priv_bucket_traits()){
+ this->priv_bucket_traits() = new_bucket_traits;
+ }
+ this->priv_initialize_cache();
+ this->priv_insertion_update_cache(new_first_bucket_num);
+ rollback1.release();
+ rollback2.release();
+ }
+
template <class MaybeConstHashtableImpl, class Cloner, class Disposer>
void priv_clone_from(MaybeConstHashtableImpl &src, Cloner cloner, Disposer disposer)
{
@@ -3498,26 +3552,26 @@ class hashtable
//Assert if passed value traits are compatible with the type
BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value));
- explicit hashtable ( const bucket_traits &b_traits
+ BOOST_INTRUSIVE_FORCEINLINE explicit hashtable ( const bucket_traits &b_traits
, const hasher & hash_func = hasher()
, const key_equal &equal_func = key_equal()
, const value_traits &v_traits = value_traits())
: Base(b_traits, hash_func, equal_func, v_traits)
{}
- hashtable(BOOST_RV_REF(hashtable) x)
+ BOOST_INTRUSIVE_FORCEINLINE hashtable(BOOST_RV_REF(hashtable) x)
: Base(BOOST_MOVE_BASE(Base, x))
{}
- hashtable& operator=(BOOST_RV_REF(hashtable) x)
+ BOOST_INTRUSIVE_FORCEINLINE hashtable& operator=(BOOST_RV_REF(hashtable) x)
{ return static_cast<hashtable&>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); }
template <class Cloner, class Disposer>
- void clone_from(const hashtable &src, Cloner cloner, Disposer disposer)
+ BOOST_INTRUSIVE_FORCEINLINE void clone_from(const hashtable &src, Cloner cloner, Disposer disposer)
{ Base::clone_from(src, cloner, disposer); }
template <class Cloner, class Disposer>
- void clone_from(BOOST_RV_REF(hashtable) src, Cloner cloner, Disposer disposer)
+ BOOST_INTRUSIVE_FORCEINLINE void clone_from(BOOST_RV_REF(hashtable) src, Cloner cloner, Disposer disposer)
{ Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer); }
};
diff --git a/boost/intrusive/linear_slist_algorithms.hpp b/boost/intrusive/linear_slist_algorithms.hpp
index 4b1f06f..6c8e9b7 100644
--- a/boost/intrusive/linear_slist_algorithms.hpp
+++ b/boost/intrusive/linear_slist_algorithms.hpp
@@ -141,7 +141,7 @@ class linear_slist_algorithms
//! <b>Complexity</b>: Constant
//!
//! <b>Throws</b>: Nothing.
- static void init_header(const node_ptr & this_node)
+ BOOST_INTRUSIVE_FORCEINLINE static void init_header(const node_ptr & this_node)
{ NodeTraits::set_next(this_node, node_ptr ()); }
//! <b>Requires</b>: this_node and prev_init_node must be in the same linear list.
@@ -153,7 +153,7 @@ class linear_slist_algorithms
//! <b>Complexity</b>: Linear to the number of elements between prev_init_node and this_node.
//!
//! <b>Throws</b>: Nothing.
- static node_ptr get_previous_node(const node_ptr & prev_init_node, const node_ptr & this_node)
+ BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_previous_node(const node_ptr & prev_init_node, const node_ptr & this_node)
{ return base_t::get_previous_node(prev_init_node, this_node); }
//! <b>Requires</b>: this_node must be in a linear list or be an empty linear list.
diff --git a/boost/intrusive/list.hpp b/boost/intrusive/list.hpp
index a59734a..a955c44 100644
--- a/boost/intrusive/list.hpp
+++ b/boost/intrusive/list.hpp
@@ -542,11 +542,7 @@ class list_impl
void swap(list_impl& other)
{
node_algorithms::swap_nodes(this->get_root_node(), other.get_root_node());
- if(constant_time_size){
- size_type backup = this->priv_size_traits().get_size();
- this->priv_size_traits().set_size(other.priv_size_traits().get_size());
- other.priv_size_traits().set_size(backup);
- }
+ this->priv_size_traits().swap(other.priv_size_traits());
}
//! <b>Effects</b>: Moves backwards all the elements, so that the first
diff --git a/boost/intrusive/list_hook.hpp b/boost/intrusive/list_hook.hpp
index aef7253..892e4e2 100644
--- a/boost/intrusive/list_hook.hpp
+++ b/boost/intrusive/list_hook.hpp
@@ -50,7 +50,8 @@ struct make_list_base_hook
>::type packed_options;
typedef generic_hook
- < circular_list_algorithms<list_node_traits<typename packed_options::void_pointer> >
+ < CircularListAlgorithms
+ , list_node_traits<typename packed_options::void_pointer>
, typename packed_options::tag
, packed_options::link_mode
, ListBaseHookId
@@ -177,7 +178,8 @@ struct make_list_member_hook
>::type packed_options;
typedef generic_hook
- < circular_list_algorithms<list_node_traits<typename packed_options::void_pointer> >
+ < CircularListAlgorithms
+ , list_node_traits<typename packed_options::void_pointer>
, member_tag
, packed_options::link_mode
, NoBaseHookId
diff --git a/boost/intrusive/options.hpp b/boost/intrusive/options.hpp
index fdcb5cb..6523ffb 100644
--- a/boost/intrusive/options.hpp
+++ b/boost/intrusive/options.hpp
@@ -61,12 +61,12 @@ BOOST_INTRUSIVE_OPTION_TYPE(size_type, SizeType, SizeType, size_type)
//!comparison functor for the value type
BOOST_INTRUSIVE_OPTION_TYPE(compare, Compare, Compare, compare)
-//!This option setter specifies the a function object
+//!This option setter specifies a function object
//!that specifies the type of the key of an associative
//!container and an operator to obtain it from a value type.
//!
-//!This function object must the define a `key_type` and
-//!a member with signature `const key_type & operator()(const value_type &) const`
+//!This function object must the define a `type` member typedef and
+//!a member with signature `type [const&] operator()(const value_type &) const`
//!that will return the key from a value_type of an associative container
BOOST_INTRUSIVE_OPTION_TYPE(key_of_value, KeyOfValue, KeyOfValue, key_of_value)
@@ -88,7 +88,7 @@ BOOST_INTRUSIVE_OPTION_CONSTANT(floating_point, bool, Enabled, floating_point)
//!functor for the value type
BOOST_INTRUSIVE_OPTION_TYPE(equal, Equal, Equal, equal)
-//!This option setter specifies the equality
+//!This option setter specifies the priority comparison
//!functor for the value type
BOOST_INTRUSIVE_OPTION_TYPE(priority, Priority, Priority, priority)
diff --git a/boost/intrusive/priority_compare.hpp b/boost/intrusive/priority_compare.hpp
index ffade48..f5589ce 100644
--- a/boost/intrusive/priority_compare.hpp
+++ b/boost/intrusive/priority_compare.hpp
@@ -26,7 +26,14 @@
namespace boost {
namespace intrusive {
-template <class T>
+/// @cond
+
+template<class U>
+void priority_order();
+
+/// @endcond
+
+template <class T = void>
struct priority_compare
{
//Compatibility with std::binary_function
@@ -40,6 +47,16 @@ struct priority_compare
}
};
+template <>
+struct priority_compare<void>
+{
+ template<class T, class U>
+ BOOST_INTRUSIVE_FORCEINLINE bool operator()(const T &t, const U &u) const
+ {
+ return priority_order(t, u);
+ }
+};
+
/// @cond
template<class PrioComp, class T>
diff --git a/boost/intrusive/rbtree.hpp b/boost/intrusive/rbtree.hpp
index 276362d..4f5d86d 100644
--- a/boost/intrusive/rbtree.hpp
+++ b/boost/intrusive/rbtree.hpp
@@ -188,6 +188,15 @@ class rbtree_impl
//! @copydoc ::boost::intrusive::bstree::crend()const
const_reverse_iterator crend() const;
+ //! @copydoc ::boost::intrusive::bstree::root()
+ iterator root();
+
+ //! @copydoc ::boost::intrusive::bstree::root()const
+ const_iterator root() const;
+
+ //! @copydoc ::boost::intrusive::bstree::croot()const
+ const_iterator croot() const;
+
//! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(iterator)
static rbtree_impl &container_from_end_iterator(iterator end_iterator);
@@ -430,6 +439,14 @@ class rbtree_impl
//! @copydoc ::boost::intrusive::bstree::remove_node
void remove_node(reference value);
+ //! @copydoc ::boost::intrusive::bstree::merge_unique(bstree<T, Options2...>&)
+ template<class T, class ...Options2>
+ void merge_unique(rbtree<T, Options2...> &);
+
+ //! @copydoc ::boost::intrusive::bstree::merge_equal(bstree<T, Options2...>&)
+ template<class T, class ...Options2>
+ void merge_equal(rbtree<T, Options2...> &);
+
friend bool operator< (const rbtree_impl &x, const rbtree_impl &y);
friend bool operator==(const rbtree_impl &x, const rbtree_impl &y);
diff --git a/boost/intrusive/rbtree_algorithms.hpp b/boost/intrusive/rbtree_algorithms.hpp
index 2a74e1b..6a7c563 100644
--- a/boost/intrusive/rbtree_algorithms.hpp
+++ b/boost/intrusive/rbtree_algorithms.hpp
@@ -284,20 +284,33 @@ class rbtree_algorithms
{
typename bstree_algo::data_for_rebalance info;
bstree_algo::erase(header, z, info);
+ rebalance_after_erasure(header, z, info);
+ return z;
+ }
- color new_z_color;
- if(info.y != z){
- new_z_color = NodeTraits::get_color(info.y);
- NodeTraits::set_color(info.y, NodeTraits::get_color(z));
- }
- else{
- new_z_color = NodeTraits::get_color(z);
- }
- //Rebalance rbtree if needed
- if(new_z_color != NodeTraits::red()){
- rebalance_after_erasure(header, info.x, info.x_parent);
+ //! @copydoc ::boost::intrusive::bstree_algorithms::transfer_unique
+ template<class NodePtrCompare>
+ static bool transfer_unique
+ (const node_ptr & header1, NodePtrCompare comp, const node_ptr &header2, const node_ptr & z)
+ {
+ typename bstree_algo::data_for_rebalance info;
+ bool const transferred = bstree_algo::transfer_unique(header1, comp, header2, z, info);
+ if(transferred){
+ rebalance_after_erasure(header2, z, info);
+ rebalance_after_insertion(header1, z);
}
- return z;
+ return transferred;
+ }
+
+ //! @copydoc ::boost::intrusive::bstree_algorithms::transfer_equal
+ template<class NodePtrCompare>
+ static void transfer_equal
+ (const node_ptr & header1, NodePtrCompare comp, const node_ptr &header2, const node_ptr & z)
+ {
+ typename bstree_algo::data_for_rebalance info;
+ bstree_algo::transfer_equal(header1, comp, header2, z, info);
+ rebalance_after_erasure(header2, z, info);
+ rebalance_after_insertion(header1, z);
}
//! @copydoc ::boost::intrusive::bstree_algorithms::clone(const const_node_ptr&,const node_ptr&,Cloner,Disposer)
@@ -431,7 +444,24 @@ class rbtree_algorithms
/// @cond
private:
- static void rebalance_after_erasure(const node_ptr & header, node_ptr x, node_ptr x_parent)
+ static void rebalance_after_erasure
+ ( const node_ptr & header, const node_ptr &z, const typename bstree_algo::data_for_rebalance &info)
+ {
+ color new_z_color;
+ if(info.y != z){
+ new_z_color = NodeTraits::get_color(info.y);
+ NodeTraits::set_color(info.y, NodeTraits::get_color(z));
+ }
+ else{
+ new_z_color = NodeTraits::get_color(z);
+ }
+ //Rebalance rbtree if needed
+ if(new_z_color != NodeTraits::red()){
+ rebalance_after_erasure_restore_invariants(header, info.x, info.x_parent);
+ }
+ }
+
+ static void rebalance_after_erasure_restore_invariants(const node_ptr & header, node_ptr x, node_ptr x_parent)
{
while(1){
if(x_parent == header || (x && NodeTraits::get_color(x) != NodeTraits::black())){
diff --git a/boost/intrusive/set.hpp b/boost/intrusive/set.hpp
index 36c46c7..3cd9013 100644
--- a/boost/intrusive/set.hpp
+++ b/boost/intrusive/set.hpp
@@ -28,6 +28,11 @@
namespace boost {
namespace intrusive {
+#if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
+template<class ValueTraits, class VoidOrKeyOfValue, class Compare, class SizeType, bool ConstantTimeSize, typename HeaderHolder>
+class multiset_impl;
+#endif
+
//! The class template set is an intrusive container, that mimics most of
//! the interface of std::set as described in the C++ standard.
//!
@@ -150,6 +155,15 @@ class set_impl
//! @copydoc ::boost::intrusive::rbtree::crend()const
const_reverse_iterator crend() const;
+ //! @copydoc ::boost::intrusive::rbtree::root()
+ iterator root();
+
+ //! @copydoc ::boost::intrusive::rbtree::root()const
+ const_iterator root() const;
+
+ //! @copydoc ::boost::intrusive::rbtree::croot()const
+ const_iterator croot() const;
+
//! @copydoc ::boost::intrusive::rbtree::container_from_end_iterator(iterator)
static set_impl &container_from_end_iterator(iterator end_iterator);
@@ -399,6 +413,26 @@ class set_impl
//! @copydoc ::boost::intrusive::rbtree::remove_node
void remove_node(reference value);
+
+ //! @copydoc ::boost::intrusive::rbtree::merge_unique
+ template<class ...Options2>
+ void merge(set<T, Options2...> &source);
+
+ //! @copydoc ::boost::intrusive::rbtree::merge_unique
+ template<class ...Options2>
+ void merge(multiset<T, Options2...> &source);
+
+ #else
+
+ template<class Compare2>
+ void merge(set_impl<ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, ConstantTimeSize, HeaderHolder> &source)
+ { return tree_type::merge_unique(source); }
+
+
+ template<class Compare2>
+ void merge(multiset_impl<ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, ConstantTimeSize, HeaderHolder> &source)
+ { return tree_type::merge_unique(source); }
+
#endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
};
@@ -658,6 +692,15 @@ class multiset_impl
//! @copydoc ::boost::intrusive::rbtree::crend()const
const_reverse_iterator crend() const;
+ //! @copydoc ::boost::intrusive::rbtree::root()
+ iterator root();
+
+ //! @copydoc ::boost::intrusive::rbtree::root()const
+ const_iterator root() const;
+
+ //! @copydoc ::boost::intrusive::rbtree::croot()const
+ const_iterator croot() const;
+
//! @copydoc ::boost::intrusive::rbtree::container_from_end_iterator(iterator)
static multiset_impl &container_from_end_iterator(iterator end_iterator);
@@ -865,6 +908,25 @@ class multiset_impl
//! @copydoc ::boost::intrusive::rbtree::remove_node
void remove_node(reference value);
+
+ //! @copydoc ::boost::intrusive::rbtree::merge_equal
+ template<class ...Options2>
+ void merge(multiset<T, Options2...> &source);
+
+ //! @copydoc ::boost::intrusive::rbtree::merge_equal
+ template<class ...Options2>
+ void merge(set<T, Options2...> &source);
+
+ #else
+
+ template<class Compare2>
+ void merge(multiset_impl<ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, ConstantTimeSize, HeaderHolder> &source)
+ { return tree_type::merge_equal(source); }
+
+ template<class Compare2>
+ void merge(set_impl<ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, ConstantTimeSize, HeaderHolder> &source)
+ { return tree_type::merge_equal(source); }
+
#endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
};
diff --git a/boost/intrusive/set_hook.hpp b/boost/intrusive/set_hook.hpp
index b641280..e303b64 100644
--- a/boost/intrusive/set_hook.hpp
+++ b/boost/intrusive/set_hook.hpp
@@ -49,7 +49,8 @@ struct make_set_base_hook
>::type packed_options;
typedef generic_hook
- < rbtree_algorithms<rbtree_node_traits<typename packed_options::void_pointer, packed_options::optimize_size> >
+ < RbTreeAlgorithms
+ , rbtree_node_traits<typename packed_options::void_pointer, packed_options::optimize_size>
, typename packed_options::tag
, packed_options::link_mode
, RbTreeBaseHookId
@@ -180,7 +181,8 @@ struct make_set_member_hook
>::type packed_options;
typedef generic_hook
- < rbtree_algorithms<rbtree_node_traits<typename packed_options::void_pointer, packed_options::optimize_size> >
+ < RbTreeAlgorithms
+ , rbtree_node_traits<typename packed_options::void_pointer, packed_options::optimize_size>
, member_tag
, packed_options::link_mode
, NoBaseHookId
diff --git a/boost/intrusive/sg_set.hpp b/boost/intrusive/sg_set.hpp
index 171bd59..745c379 100644
--- a/boost/intrusive/sg_set.hpp
+++ b/boost/intrusive/sg_set.hpp
@@ -26,6 +26,11 @@
namespace boost {
namespace intrusive {
+#if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
+template<class ValueTraits, class VoidOrKeyOfValue, class Compare, class SizeType, bool ConstantTimeSize, typename HeaderHolder>
+class sg_multiset_impl;
+#endif
+
//! The class template sg_set is an intrusive container, that mimics most of
//! the interface of std::sg_set as described in the C++ standard.
//!
@@ -148,6 +153,15 @@ class sg_set_impl
//! @copydoc ::boost::intrusive::sgtree::crend()const
const_reverse_iterator crend() const;
+ //! @copydoc ::boost::intrusive::sgtree::root()
+ iterator root();
+
+ //! @copydoc ::boost::intrusive::sgtree::root()const
+ const_iterator root() const;
+
+ //! @copydoc ::boost::intrusive::sgtree::croot()const
+ const_iterator croot() const;
+
//! @copydoc ::boost::intrusive::sgtree::container_from_end_iterator(iterator)
static sg_set_impl &container_from_end_iterator(iterator end_iterator);
@@ -410,6 +424,24 @@ class sg_set_impl
//! @copydoc ::boost::intrusive::sgtree::balance_factor(float)
void balance_factor(float new_alpha);
+ //! @copydoc ::boost::intrusive::rbtree::merge_unique
+ template<class ...Options2>
+ void merge(sg_set<T, Options2...> &source);
+
+ //! @copydoc ::boost::intrusive::rbtree::merge_unique
+ template<class ...Options2>
+ void merge(sg_multiset<T, Options2...> &source);
+
+ #else
+
+ template<class Compare2>
+ void merge(sg_set_impl<ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, FloatingPoint, HeaderHolder> &source)
+ { return tree_type::merge_unique(source); }
+
+ template<class Compare2>
+ void merge(sg_multiset_impl<ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, FloatingPoint, HeaderHolder> &source)
+ { return tree_type::merge_unique(source); }
+
#endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
};
@@ -669,6 +701,15 @@ class sg_multiset_impl
//! @copydoc ::boost::intrusive::sgtree::crend()const
const_reverse_iterator crend() const;
+ //! @copydoc ::boost::intrusive::sgtree::root()
+ iterator root();
+
+ //! @copydoc ::boost::intrusive::sgtree::root()const
+ const_iterator root() const;
+
+ //! @copydoc ::boost::intrusive::sgtree::croot()const
+ const_iterator croot() const;
+
//! @copydoc ::boost::intrusive::sgtree::container_from_end_iterator(iterator)
static sg_multiset_impl &container_from_end_iterator(iterator end_iterator);
@@ -889,6 +930,24 @@ class sg_multiset_impl
//! @copydoc ::boost::intrusive::sgtree::balance_factor(float)
void balance_factor(float new_alpha);
+ //! @copydoc ::boost::intrusive::treap::merge_unique
+ template<class ...Options2>
+ void merge(sg_multiset<T, Options2...> &source);
+
+ //! @copydoc ::boost::intrusive::treap::merge_unique
+ template<class ...Options2>
+ void merge(sg_set<T, Options2...> &source);
+
+ #else
+
+ template<class Compare2>
+ void merge(sg_multiset_impl<ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, FloatingPoint, HeaderHolder> &source)
+ { return tree_type::merge_equal(source); }
+
+ template<class Compare2>
+ void merge(sg_set_impl<ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, FloatingPoint, HeaderHolder> &source)
+ { return tree_type::merge_equal(source); }
+
#endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
};
diff --git a/boost/intrusive/sgtree.hpp b/boost/intrusive/sgtree.hpp
index 6e7af7d..033efb8 100644
--- a/boost/intrusive/sgtree.hpp
+++ b/boost/intrusive/sgtree.hpp
@@ -156,6 +156,9 @@ struct alpha_holder
multiply_by_alpha_t get_multiply_by_alpha_t() const
{ return multiply_by_alpha_t(alpha_); }
+ SizeType &get_max_tree_size()
+ { return max_tree_size_; }
+
protected:
float alpha_;
float inv_minus_logalpha_;
@@ -189,6 +192,10 @@ struct alpha_holder<false, SizeType>
multiply_by_alpha_t get_multiply_by_alpha_t() const
{ return multiply_by_alpha_t(); }
+ SizeType &get_max_tree_size()
+ { return max_tree_size_; }
+
+ protected:
SizeType max_tree_size_;
};
@@ -375,6 +382,15 @@ class sgtree_impl
//! @copydoc ::boost::intrusive::bstree::crend()const
const_reverse_iterator crend() const;
+ //! @copydoc ::boost::intrusive::bstree::root()
+ iterator root();
+
+ //! @copydoc ::boost::intrusive::bstree::root()const
+ const_iterator root() const;
+
+ //! @copydoc ::boost::intrusive::bstree::croot()const
+ const_iterator croot() const;
+
//! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(iterator)
static sgtree_impl &container_from_end_iterator(iterator end_iterator);
@@ -696,6 +712,66 @@ class sgtree_impl
this->max_tree_size_ = 0;
}
+ #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
+ //! @copydoc ::boost::intrusive::bstree::merge_unique
+ template<class T, class ...Options2> void merge_unique(sgtree<T, Options2...> &);
+ #else
+ template<class Compare2>
+ void merge_unique(sgtree_impl
+ <ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, FloatingPoint, HeaderHolder> &source)
+ #endif
+ {
+ node_ptr it (node_algorithms::begin_node(source.header_ptr()))
+ , itend(node_algorithms::end_node (source.header_ptr()));
+
+ while(it != itend){
+ node_ptr const p(it);
+ BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || !node_algorithms::unique(p));
+ it = node_algorithms::next_node(it);
+
+ std::size_t max_tree1_size = this->max_tree_size_;
+ std::size_t max_tree2_size = source.get_max_tree_size();
+ if( node_algorithms::transfer_unique
+ ( this->header_ptr(), this->key_node_comp(this->key_comp()), this->size(), max_tree1_size
+ , source.header_ptr(), p, source.size(), max_tree2_size
+ , this->get_h_alpha_func(), this->get_alpha_by_max_size_func()) ){
+ this->max_tree_size_ = (size_type)max_tree1_size;
+ this->sz_traits().increment();
+ source.get_max_tree_size() = (size_type)max_tree2_size;
+ source.sz_traits().decrement();
+ }
+ }
+ }
+
+ #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
+ //! @copydoc ::boost::intrusive::bstree::merge_equal
+ template<class T, class ...Options2> void merge_equal(sgtree<T, Options2...> &);
+ #else
+ template<class Compare2>
+ void merge_equal(sgtree_impl
+ <ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, FloatingPoint, HeaderHolder> &source)
+ #endif
+ {
+ node_ptr it (node_algorithms::begin_node(source.header_ptr()))
+ , itend(node_algorithms::end_node (source.header_ptr()));
+
+ while(it != itend){
+ node_ptr const p(it);
+ BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || !node_algorithms::unique(p));
+ it = node_algorithms::next_node(it);
+ std::size_t max_tree1_size = this->max_tree_size_;
+ std::size_t max_tree2_size = source.get_max_tree_size();
+ node_algorithms::transfer_equal
+ ( this->header_ptr(), this->key_node_comp(this->key_comp()), this->size(), max_tree1_size
+ , source.header_ptr(), p, source.size(), max_tree2_size
+ , this->get_h_alpha_func(), this->get_alpha_by_max_size_func());
+ this->max_tree_size_ = (size_type)max_tree1_size;
+ this->sz_traits().increment();
+ source.get_max_tree_size() = (size_type)max_tree2_size;
+ source.sz_traits().decrement();
+ }
+ }
+
#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
//! @copydoc ::boost::intrusive::bstree::count(const key_type &)const
size_type count(const key_type &key) const;
diff --git a/boost/intrusive/sgtree_algorithms.hpp b/boost/intrusive/sgtree_algorithms.hpp
index 2d74184..e6002a7 100644
--- a/boost/intrusive/sgtree_algorithms.hpp
+++ b/boost/intrusive/sgtree_algorithms.hpp
@@ -138,7 +138,6 @@ class sgtree_algorithms
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_algo::data_for_rebalance info;
bstree_algo::erase(header, z);
--tree_size;
if (tree_size > 0 &&
@@ -288,12 +287,38 @@ class sgtree_algorithms
//! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_commit(const node_ptr&,const node_ptr&,const insert_commit_data&)
template<class H_Alpha>
- 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
,std::size_t tree_size, H_Alpha h_alpha, std::size_t &max_tree_size)
+ { return insert_commit(header, new_value, commit_data, tree_size, h_alpha, max_tree_size); }
+
+ //! @copydoc ::boost::intrusive::bstree_algorithms::transfer_unique
+ template<class NodePtrCompare, class H_Alpha, class AlphaByMaxSize>
+ static bool transfer_unique
+ ( const node_ptr & header1, NodePtrCompare comp, std::size_t tree1_size, std::size_t &max_tree1_size
+ , const node_ptr &header2, const node_ptr & z, std::size_t tree2_size, std::size_t &max_tree2_size
+ ,H_Alpha h_alpha, AlphaByMaxSize alpha_by_maxsize)
{
- 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);
+ insert_commit_data commit_data;
+ bool const transferable = insert_unique_check(header1, z, comp, commit_data).second;
+ if(transferable){
+ erase(header2, z, tree2_size, max_tree2_size, alpha_by_maxsize);
+ insert_commit(header1, z, commit_data, tree1_size, h_alpha, max_tree1_size);
+ }
+ return transferable;
+ }
+
+ //! @copydoc ::boost::intrusive::bstree_algorithms::transfer_equal
+ template<class NodePtrCompare, class H_Alpha, class AlphaByMaxSize>
+ static void transfer_equal
+ ( const node_ptr & header1, NodePtrCompare comp, std::size_t tree1_size, std::size_t &max_tree1_size
+ , const node_ptr &header2, const node_ptr & z, std::size_t tree2_size, std::size_t &max_tree2_size
+ ,H_Alpha h_alpha, AlphaByMaxSize alpha_by_maxsize)
+ {
+ insert_commit_data commit_data;
+ insert_equal_upper_bound_check(header1, z, comp, commit_data);
+ erase(header2, z, tree2_size, max_tree2_size, alpha_by_maxsize);
+ insert_commit(header1, z, commit_data, tree1_size, h_alpha, max_tree1_size);
}
#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
@@ -310,6 +335,25 @@ class sgtree_algorithms
/// @cond
private:
+ template<class KeyType, class KeyNodePtrCompare>
+ static void insert_equal_upper_bound_check
+ (const node_ptr & header, const KeyType &key
+ ,KeyNodePtrCompare comp, insert_commit_data &commit_data)
+ {
+ std::size_t depth;
+ bstree_algo::insert_equal_upper_bound_check(header, key, comp, commit_data, &depth);
+ commit_data.depth = depth;
+ }
+
+ template<class H_Alpha>
+ static void insert_commit
+ (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_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);
+ }
+
template<class H_Alpha>
static void rebalance_after_insertion
(const node_ptr &x, std::size_t depth
diff --git a/boost/intrusive/slist.hpp b/boost/intrusive/slist.hpp
index d64bf49..0020699 100644
--- a/boost/intrusive/slist.hpp
+++ b/boost/intrusive/slist.hpp
@@ -343,8 +343,7 @@ class slist_impl
slist_impl(BOOST_RV_REF(slist_impl) x)
: data_(::boost::move(x.priv_value_traits()))
{
- this->priv_size_traits().set_size(size_type(0));
- node_algorithms::init_header(this->get_root_node());
+ this->set_default_constructed_state();
//nothrow, no need to rollback to release elements on exception
this->swap(x);
}
@@ -717,11 +716,7 @@ class slist_impl
else{
this->priv_swap_lists(this->get_root_node(), other.get_root_node(), detail::bool_<linear>());
}
- if(constant_time_size){
- size_type backup = this->priv_size_traits().get_size();
- this->priv_size_traits().set_size(other.priv_size_traits().get_size());
- other.priv_size_traits().set_size(backup);
- }
+ this->priv_size_traits().swap(other.priv_size_traits());
}
//! <b>Effects</b>: Moves backwards all the elements, so that the first
@@ -1265,7 +1260,7 @@ class slist_impl
if(l) *l = this->previous(this->cend());
}
else{
- const_iterator last_x(x.previous(x.end())); //<- constant time if cache_last is active
+ const_iterator last_x(x.previous(x.end())); //constant time if cache_last is active
node_ptr prev_n(prev.pointed_node());
node_ptr last_x_n(last_x.pointed_node());
if(cache_last){
diff --git a/boost/intrusive/slist_hook.hpp b/boost/intrusive/slist_hook.hpp
index eac2737..0f37772 100644
--- a/boost/intrusive/slist_hook.hpp
+++ b/boost/intrusive/slist_hook.hpp
@@ -50,7 +50,8 @@ struct make_slist_base_hook
>::type packed_options;
typedef generic_hook
- < circular_slist_algorithms<slist_node_traits<typename packed_options::void_pointer> >
+ < CircularSListAlgorithms
+ , slist_node_traits<typename packed_options::void_pointer>
, typename packed_options::tag
, packed_options::link_mode
, SlistBaseHookId
@@ -178,7 +179,8 @@ struct make_slist_member_hook
>::type packed_options;
typedef generic_hook
- < circular_slist_algorithms<slist_node_traits<typename packed_options::void_pointer> >
+ < CircularSListAlgorithms
+ , slist_node_traits<typename packed_options::void_pointer>
, member_tag
, packed_options::link_mode
, NoBaseHookId
@@ -270,6 +272,11 @@ class slist_member_hook
//! otherwise. This function can be used to test whether \c slist::iterator_to
//! will return a valid iterator.
//!
+ //! <b>Note</b>: If this member is called when the value is inserted in a
+ //! slist with the option linear<true>, this function will return "false"
+ //! for the last element, as it is not linked to anything (the next element is null),
+ //! so use with care.
+ //!
//! <b>Complexity</b>: Constant
bool is_linked() const;
diff --git a/boost/intrusive/splay_set.hpp b/boost/intrusive/splay_set.hpp
index 893b580..da7662e 100644
--- a/boost/intrusive/splay_set.hpp
+++ b/boost/intrusive/splay_set.hpp
@@ -23,6 +23,11 @@
# pragma once
#endif
+#if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
+template<class ValueTraits, class VoidOrKeyOfValue, class Compare, class SizeType, bool ConstantTimeSize, typename HeaderHolder>
+class splay_multiset_impl;
+#endif
+
namespace boost {
namespace intrusive {
@@ -148,6 +153,15 @@ class splay_set_impl
//! @copydoc ::boost::intrusive::splaytree::crend()const
const_reverse_iterator crend() const;
+ //! @copydoc ::boost::intrusive::splaytree::root()
+ iterator root();
+
+ //! @copydoc ::boost::intrusive::splaytree::root()const
+ const_iterator root() const;
+
+ //! @copydoc ::boost::intrusive::splaytree::croot()const
+ const_iterator croot() const;
+
//! @copydoc ::boost::intrusive::splaytree::container_from_end_iterator(iterator)
static splay_set_impl &container_from_end_iterator(iterator end_iterator);
@@ -420,6 +434,26 @@ class splay_set_impl
//! @copydoc ::boost::intrusive::splaytree::rebalance_subtree
iterator rebalance_subtree(iterator root);
+
+ //! @copydoc ::boost::intrusive::splaytree::merge_unique
+ template<class ...Options2>
+ void merge(splay_set<T, Options2...> &source);
+
+ //! @copydoc ::boost::intrusive::splaytree::merge_unique
+ template<class ...Options2>
+ void merge(splay_multiset<T, Options2...> &source);
+
+ #else
+
+ template<class Compare2>
+ void merge(splay_set_impl<ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, ConstantTimeSize, HeaderHolder> &source)
+ { return tree_type::merge_unique(source); }
+
+
+ template<class Compare2>
+ void merge(splay_multiset_impl<ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, ConstantTimeSize, HeaderHolder> &source)
+ { return tree_type::merge_unique(source); }
+
#endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
};
@@ -679,6 +713,15 @@ class splay_multiset_impl
//! @copydoc ::boost::intrusive::splaytree::crend()const
const_reverse_iterator crend() const;
+ //! @copydoc ::boost::intrusive::splaytree::root()
+ iterator root();
+
+ //! @copydoc ::boost::intrusive::splaytree::root()const
+ const_iterator root() const;
+
+ //! @copydoc ::boost::intrusive::splaytree::croot()const
+ const_iterator croot() const;
+
//! @copydoc ::boost::intrusive::splaytree::container_from_end_iterator(iterator)
static splay_multiset_impl &container_from_end_iterator(iterator end_iterator);
@@ -902,6 +945,25 @@ class splay_multiset_impl
//! @copydoc ::boost::intrusive::splaytree::rebalance_subtree
iterator rebalance_subtree(iterator root);
+
+ //! @copydoc ::boost::intrusive::splaytree::merge_equal
+ template<class ...Options2>
+ void merge(splay_multiset<T, Options2...> &source);
+
+ //! @copydoc ::boost::intrusive::splaytree::merge_equal
+ template<class ...Options2>
+ void merge(splay_set<T, Options2...> &source);
+
+ #else
+
+ template<class Compare2>
+ void merge(splay_multiset_impl<ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, ConstantTimeSize, HeaderHolder> &source)
+ { return tree_type::merge_equal(source); }
+
+ template<class Compare2>
+ void merge(splay_set_impl<ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, ConstantTimeSize, HeaderHolder> &source)
+ { return tree_type::merge_equal(source); }
+
#endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
};
diff --git a/boost/intrusive/splaytree.hpp b/boost/intrusive/splaytree.hpp
index afc1081..f6a1a93 100644
--- a/boost/intrusive/splaytree.hpp
+++ b/boost/intrusive/splaytree.hpp
@@ -183,6 +183,15 @@ class splaytree_impl
//! @copydoc ::boost::intrusive::bstree::crend()const
const_reverse_iterator crend() const;
+ //! @copydoc ::boost::intrusive::bstree::root()
+ iterator root();
+
+ //! @copydoc ::boost::intrusive::bstree::root()const
+ const_iterator root() const;
+
+ //! @copydoc ::boost::intrusive::bstree::croot()const
+ const_iterator croot() const;
+
//! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(iterator)
static splaytree_impl &container_from_end_iterator(iterator end_iterator);
@@ -454,6 +463,14 @@ class splaytree_impl
//! @copydoc ::boost::intrusive::bstree::remove_node
void remove_node(reference value);
+ //! @copydoc ::boost::intrusive::bstree::merge_unique(bstree<T, Options2...>&)
+ template<class T, class ...Options2>
+ void merge_unique(splaytree<T, Options2...> &);
+
+ //! @copydoc ::boost::intrusive::bstree::merge_equal(bstree<T, Options2...>&)
+ template<class T, class ...Options2>
+ void merge_equal(splaytree<T, Options2...> &);
+
#endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
//! <b>Requires</b>: i must be a valid iterator of *this.
diff --git a/boost/intrusive/splaytree_algorithms.hpp b/boost/intrusive/splaytree_algorithms.hpp
index 1c6afdf..be2e182 100644
--- a/boost/intrusive/splaytree_algorithms.hpp
+++ b/boost/intrusive/splaytree_algorithms.hpp
@@ -251,6 +251,33 @@ class splaytree_algorithms
bstree_algo::erase(header, z);
}
+ //! @copydoc ::boost::intrusive::bstree_algorithms::transfer_unique
+ template<class NodePtrCompare>
+ static bool transfer_unique
+ (const node_ptr & header1, NodePtrCompare comp, const node_ptr &header2, const node_ptr & z)
+ {
+ typename bstree_algo::insert_commit_data commit_data;
+ bool const transferable = bstree_algo::insert_unique_check(header1, z, comp, commit_data).second;
+ if(transferable){
+ erase(header2, z);
+ bstree_algo::insert_commit(header1, z, commit_data);
+ splay_up(z, header1);
+ }
+ return transferable;
+ }
+
+ //! @copydoc ::boost::intrusive::bstree_algorithms::transfer_equal
+ template<class NodePtrCompare>
+ static void transfer_equal
+ (const node_ptr & header1, NodePtrCompare comp, const node_ptr &header2, const node_ptr & z)
+ {
+ insert_commit_data commit_data;
+ splay_down(header1, z, comp);
+ bstree_algo::insert_equal_upper_bound_check(header1, z, comp, commit_data);
+ erase(header2, z);
+ bstree_algo::insert_commit(header1, z, commit_data);
+ }
+
#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
//! @copydoc ::boost::intrusive::bstree_algorithms::clone(const const_node_ptr&,const node_ptr&,Cloner,Disposer)
template <class Cloner, class Disposer>
diff --git a/boost/intrusive/treap.hpp b/boost/intrusive/treap.hpp
index 3852719..8567072 100644
--- a/boost/intrusive/treap.hpp
+++ b/boost/intrusive/treap.hpp
@@ -274,6 +274,16 @@ class treap_impl
//! @copydoc ::boost::intrusive::bstree::crend()const
const_reverse_iterator crend() const;
+
+ //! @copydoc ::boost::intrusive::bstree::root()
+ iterator root();
+
+ //! @copydoc ::boost::intrusive::bstree::root()const
+ const_iterator root() const;
+
+ //! @copydoc ::boost::intrusive::bstree::croot()const
+ const_iterator croot() const;
+
#endif
//! <b>Effects</b>: Returns a reverse_iterator pointing to the highest priority object of the
@@ -997,6 +1007,56 @@ class treap_impl
this->tree_type::sz_traits().set_size(0);
}
+ #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
+ //! @copydoc ::boost::intrusive::bstree::merge_unique
+ template<class T, class ...Options2> void merge_unique(sgtree<T, Options2...> &);
+ #else
+ template<class Compare2>
+ void merge_unique(treap_impl
+ <ValueTraits, VoidOrKeyOfValue, Compare2, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder> &source)
+ #endif
+ {
+ node_ptr it (node_algorithms::begin_node(source.header_ptr()))
+ , itend(node_algorithms::end_node (source.header_ptr()));
+
+ while(it != itend){
+ node_ptr const p(it);
+ BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || !node_algorithms::unique(p));
+ it = node_algorithms::next_node(it);
+
+ if( node_algorithms::transfer_unique
+ ( this->header_ptr(), this->key_node_comp(this->key_comp())
+ , this->key_node_prio_comp(this->priv_pcomp()), source.header_ptr(), p) ){
+ this->sz_traits().increment();
+ source.sz_traits().decrement();
+ }
+ }
+ }
+
+ #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
+ //! @copydoc ::boost::intrusive::bstree::merge_equal(bstree<T, Options2...>&)
+ template<class T, class ...Options2> void merge_equal(sgtree<T, Options2...> &);
+ #else
+ template<class Compare2>
+ void merge_equal(treap_impl
+ <ValueTraits, VoidOrKeyOfValue, Compare2, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder> &source)
+ #endif
+ {
+ node_ptr it (node_algorithms::begin_node(source.header_ptr()))
+ , itend(node_algorithms::end_node (source.header_ptr()));
+
+ while(it != itend){
+ node_ptr const p(it);
+ BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || !node_algorithms::unique(p));
+ it = node_algorithms::next_node(it);
+ node_algorithms::transfer_equal
+ ( this->header_ptr(), this->key_node_comp(this->key_comp())
+ , this->key_node_prio_comp(this->priv_pcomp()), source.header_ptr(), p);
+ this->sz_traits().increment();
+ source.sz_traits().decrement();
+ }
+ }
+
//! @copydoc ::boost::intrusive::bstree::check(ExtraChecker)const
template <class ExtraChecker>
void check(ExtraChecker extra_checker) const
diff --git a/boost/intrusive/treap_algorithms.hpp b/boost/intrusive/treap_algorithms.hpp
index 006a880..b1a82b3 100644
--- a/boost/intrusive/treap_algorithms.hpp
+++ b/boost/intrusive/treap_algorithms.hpp
@@ -569,6 +569,34 @@ class treap_algorithms
rotate_up_n(header, new_node, commit_data.rotations);
}
+ //! @copydoc ::boost::intrusive::bstree_algorithms::transfer_unique
+ template<class NodePtrCompare, class KeyNodePtrPrioCompare>
+ static bool transfer_unique
+ (const node_ptr & header1, NodePtrCompare comp, KeyNodePtrPrioCompare pcomp, const node_ptr &header2, const node_ptr & z)
+ {
+ insert_commit_data commit_data;
+ bool const transferable = insert_unique_check(header1, z, comp, pcomp, commit_data).second;
+ if(transferable){
+ erase(header2, z, pcomp);
+ insert_unique_commit(header1, z, commit_data);
+ }
+ return transferable;
+ }
+
+ //! @copydoc ::boost::intrusive::bstree_algorithms::transfer_equal
+ template<class NodePtrCompare, class KeyNodePtrPrioCompare>
+ static void transfer_equal
+ (const node_ptr & header1, NodePtrCompare comp, KeyNodePtrPrioCompare pcomp, const node_ptr &header2, const node_ptr & z)
+ {
+ insert_commit_data commit_data;
+ bstree_algo::insert_equal_upper_bound_check(header1, z, comp, commit_data);
+ rebalance_after_insertion_check(header1, commit_data.node, z, pcomp, commit_data.rotations);
+ rebalance_for_erasure(header2, z, pcomp);
+ bstree_algo::erase(header2, z);
+ bstree_algo::insert_unique_commit(header1, z, commit_data);
+ rotate_up_n(header1, z, commit_data.rotations);
+ }
+
#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
//! @copydoc ::boost::intrusive::bstree_algorithms::is_header
diff --git a/boost/intrusive/treap_set.hpp b/boost/intrusive/treap_set.hpp
index f97b376..bf162ba 100644
--- a/boost/intrusive/treap_set.hpp
+++ b/boost/intrusive/treap_set.hpp
@@ -26,6 +26,11 @@
namespace boost {
namespace intrusive {
+#if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
+template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, class VoidOrPrioComp, class SizeType, bool ConstantTimeSize, typename HeaderHolder>
+class treap_multiset_impl;
+#endif
+
//! The class template treap_set is an intrusive container, that mimics most of
//! the interface of std::set as described in the C++ standard.
//!
@@ -155,6 +160,15 @@ class treap_set_impl
//! @copydoc ::boost::intrusive::treap::crend()const
const_reverse_iterator crend() const;
+ //! @copydoc ::boost::intrusive::treap::root()
+ iterator root();
+
+ //! @copydoc ::boost::intrusive::treap::root()const
+ const_iterator root() const;
+
+ //! @copydoc ::boost::intrusive::treap::croot()const
+ const_iterator croot() const;
+
//! @copydoc ::boost::intrusive::treap::container_from_end_iterator(iterator)
static treap_set_impl &container_from_end_iterator(iterator end_iterator);
@@ -229,7 +243,7 @@ class treap_set_impl
iterator insert(const_iterator hint, reference value)
{ return tree_type::insert_unique(hint, value); }
- //! @copydoc ::boost::intrusive::treap::insert_unique_check(const key_type,insert_commit_data&)
+ //! @copydoc ::boost::intrusive::treap::insert_unique_check(const key_type&,insert_commit_data&)
std::pair<iterator, bool> insert_check( const key_type &key, insert_commit_data &commit_data)
{ return tree_type::insert_unique_check(key, commit_data); }
@@ -429,6 +443,25 @@ class treap_set_impl
//! @copydoc ::boost::intrusive::treap::remove_node
void remove_node(reference value);
+
+ //! @copydoc ::boost::intrusive::treap::merge_unique
+ template<class ...Options2>
+ void merge(treap_set<T, Options2...> &source);
+
+ //! @copydoc ::boost::intrusive::treap::merge_unique
+ template<class ...Options2>
+ void merge(treap_multiset<T, Options2...> &source);
+
+ #else
+
+ template<class Compare2>
+ void merge(treap_set_impl<ValueTraits, VoidOrKeyOfValue, Compare2, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder> &source)
+ { return tree_type::merge_unique(source); }
+
+ template<class Compare2>
+ void merge(treap_multiset_impl<ValueTraits, VoidOrKeyOfValue, Compare2, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder> &source)
+ { return tree_type::merge_unique(source); }
+
#endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
};
@@ -682,6 +715,15 @@ class treap_multiset_impl
//! @copydoc ::boost::intrusive::treap::crend()const
const_reverse_iterator crend() const;
+ //! @copydoc ::boost::intrusive::treap::root()
+ iterator root();
+
+ //! @copydoc ::boost::intrusive::treap::root()const
+ const_iterator root() const;
+
+ //! @copydoc ::boost::intrusive::treap::croot()const
+ const_iterator croot() const;
+
//! @copydoc ::boost::intrusive::treap::container_from_end_iterator(iterator)
static treap_multiset_impl &container_from_end_iterator(iterator end_iterator);
@@ -914,6 +956,24 @@ class treap_multiset_impl
//! @copydoc ::boost::intrusive::treap::remove_node
void remove_node(reference value);
+ //! @copydoc ::boost::intrusive::treap::merge_unique
+ template<class ...Options2>
+ void merge(treap_multiset<T, Options2...> &source);
+
+ //! @copydoc ::boost::intrusive::treap::merge_unique
+ template<class ...Options2>
+ void merge(treap_set<T, Options2...> &source);
+
+ #else
+
+ template<class Compare2>
+ void merge(treap_multiset_impl<ValueTraits, VoidOrKeyOfValue, Compare2, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder> &source)
+ { return tree_type::merge_equal(source); }
+
+ template<class Compare2>
+ void merge(treap_set_impl<ValueTraits, VoidOrKeyOfValue, Compare2, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder> &source)
+ { return tree_type::merge_equal(source); }
+
#endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
};
diff --git a/boost/intrusive/unordered_set.hpp b/boost/intrusive/unordered_set.hpp
index 1174dff..1968fa2 100644
--- a/boost/intrusive/unordered_set.hpp
+++ b/boost/intrusive/unordered_set.hpp
@@ -360,6 +360,9 @@ class unordered_set_impl
//! @copydoc ::boost::intrusive::hashtable::rehash(const bucket_traits &)
void rehash(const bucket_traits &new_bucket_traits);
+ //! @copydoc ::boost::intrusive::hashtable::full_rehash
+ void full_rehash();
+
//! @copydoc ::boost::intrusive::hashtable::incremental_rehash(bool)
bool incremental_rehash(bool grow = true);
@@ -836,6 +839,9 @@ class unordered_multiset_impl
//! @copydoc ::boost::intrusive::hashtable::rehash(const bucket_traits &)
void rehash(const bucket_traits &new_bucket_traits);
+ //! @copydoc ::boost::intrusive::hashtable::full_rehash
+ void full_rehash();
+
//! @copydoc ::boost::intrusive::hashtable::incremental_rehash(bool)
bool incremental_rehash(bool grow = true);
diff --git a/boost/intrusive/unordered_set_hook.hpp b/boost/intrusive/unordered_set_hook.hpp
index 95a575a..a18d235 100644
--- a/boost/intrusive/unordered_set_hook.hpp
+++ b/boost/intrusive/unordered_set_hook.hpp
@@ -152,19 +152,33 @@ struct uset_algo_wrapper : public Algo
{};
template<class VoidPointer, bool StoreHash, bool OptimizeMultiKey>
-struct get_uset_node_algo
+struct get_uset_node_traits
{
typedef typename detail::if_c
< (StoreHash || OptimizeMultiKey)
, unordered_node_traits<VoidPointer, StoreHash, OptimizeMultiKey>
, slist_node_traits<VoidPointer>
- >::type node_traits_type;
- typedef typename detail::if_c
- < OptimizeMultiKey
- , unordered_algorithms<node_traits_type>
- , uset_algo_wrapper< circular_slist_algorithms<node_traits_type> >
>::type type;
};
+
+template<bool OptimizeMultiKey>
+struct get_uset_algo_type
+{
+ static const algo_types value = OptimizeMultiKey ? UnorderedAlgorithms : UnorderedCircularSlistAlgorithms;
+};
+
+template<class NodeTraits>
+struct get_algo<UnorderedAlgorithms, NodeTraits>
+{
+ typedef unordered_algorithms<NodeTraits> type;
+};
+
+template<class NodeTraits>
+struct get_algo<UnorderedCircularSlistAlgorithms, NodeTraits>
+{
+ typedef uset_algo_wrapper< circular_slist_algorithms<NodeTraits> > type;
+};
+
/// @endcond
//! Helper metafunction to define a \c unordered_set_base_hook that yields to the same
@@ -187,10 +201,11 @@ struct make_unordered_set_base_hook
>::type packed_options;
typedef generic_hook
- < typename get_uset_node_algo < typename packed_options::void_pointer
- , packed_options::store_hash
- , packed_options::optimize_multikey
- >::type
+ < get_uset_algo_type <packed_options::optimize_multikey>::value
+ , typename get_uset_node_traits < typename packed_options::void_pointer
+ , packed_options::store_hash
+ , packed_options::optimize_multikey
+ >::type
, typename packed_options::tag
, packed_options::link_mode
, HashBaseHookId
@@ -326,10 +341,11 @@ struct make_unordered_set_member_hook
>::type packed_options;
typedef generic_hook
- < typename get_uset_node_algo< typename packed_options::void_pointer
- , packed_options::store_hash
- , packed_options::optimize_multikey
- >::type
+ < get_uset_algo_type <packed_options::optimize_multikey>::value
+ , typename get_uset_node_traits < typename packed_options::void_pointer
+ , packed_options::store_hash
+ , packed_options::optimize_multikey
+ >::type
, member_tag
, packed_options::link_mode
, NoBaseHookId