diff options
| author | DongHun Kwak <dh0128.kwak@samsung.com> | 2016-10-06 10:41:18 +0900 |
|---|---|---|
| committer | DongHun Kwak <dh0128.kwak@samsung.com> | 2016-10-06 10:43:11 +0900 |
| commit | f763a99a501650eff2c60288aa6f10ef916d769e (patch) | |
| tree | 02af7e13f9a38c888ebf340fe764cbe7dae99da9 /boost/intrusive | |
| parent | 5cde13f21d36c7224b0e13d11c4b49379ae5210d (diff) | |
| download | boost-f763a99a501650eff2c60288aa6f10ef916d769e.tar.gz boost-f763a99a501650eff2c60288aa6f10ef916d769e.tar.bz2 boost-f763a99a501650eff2c60288aa6f10ef916d769e.zip | |
Imported Upstream version 1.62.0upstream/1.62.0
Change-Id: I9d4c1ddb7b7d8f0069217ecc582700f9fda6dd4c
Signed-off-by: DongHun Kwak <dh0128.kwak@samsung.com>
Diffstat (limited to 'boost/intrusive')
43 files changed, 1663 insertions, 530 deletions
diff --git a/boost/intrusive/any_hook.hpp b/boost/intrusive/any_hook.hpp index 809507c3bf..6d187812a6 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 2c962046e5..d150140abd 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 b61f95f2f0..187130365b 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 741d482827..cdc9b75d60 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 60a981c381..1459851fb4 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 60f18a16a9..693b6d855c 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 e96248b4ec..a64c15ace5 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 0fb921887d..f2cdb428b4 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 dcb7e5c4ff..e8caee0c94 100644 --- a/boost/intrusive/bstree_algorithms.hpp +++ b/boost/intrusive/bstree_algorithms.hpp @@ -63,14 +63,16 @@ struct bstree_node_checker struct return_type : public base_checker_t::return_type { - return_type() : min_key_node_ptr(const_node_ptr()), max_key_node_ptr(const_node_ptr()), node_count(0) {} + BOOST_INTRUSIVE_FORCEINLINE return_type() + : min_key_node_ptr(const_node_ptr()), max_key_node_ptr(const_node_ptr()), node_count(0) + {} const_node_ptr min_key_node_ptr; const_node_ptr max_key_node_ptr; size_t node_count; }; - bstree_node_checker(const NodePtrCompare& comp, ExtraChecker extra_checker) + BOOST_INTRUSIVE_FORCEINLINE bstree_node_checker(const NodePtrCompare& comp, ExtraChecker extra_checker) : base_checker_t(extra_checker), comp_(comp) {} @@ -182,14 +184,14 @@ class bstree_algorithms : public bstree_algorithms_base<NodeTraits> template<class Disposer> struct dispose_subtree_disposer { - dispose_subtree_disposer(Disposer &disp, const node_ptr & subtree) + BOOST_INTRUSIVE_FORCEINLINE dispose_subtree_disposer(Disposer &disp, const node_ptr & subtree) : disposer_(&disp), subtree_(subtree) {} - void release() + BOOST_INTRUSIVE_FORCEINLINE void release() { disposer_ = 0; } - ~dispose_subtree_disposer() + BOOST_INTRUSIVE_FORCEINLINE ~dispose_subtree_disposer() { if(disposer_){ dispose_subtree(subtree_, *disposer_); @@ -209,7 +211,7 @@ class bstree_algorithms : public bstree_algorithms_base<NodeTraits> //! <b>Complexity</b>: Constant time. //! //! <b>Throws</b>: Nothing. - static node_ptr begin_node(const const_node_ptr & header) + BOOST_INTRUSIVE_FORCEINLINE static node_ptr begin_node(const const_node_ptr & header) { return node_traits::get_left(header); } //! <b>Requires</b>: 'header' is the header node of a tree. @@ -219,7 +221,7 @@ class bstree_algorithms : public bstree_algorithms_base<NodeTraits> //! <b>Complexity</b>: Constant time. //! //! <b>Throws</b>: Nothing. - static node_ptr end_node(const const_node_ptr & header) + BOOST_INTRUSIVE_FORCEINLINE static node_ptr end_node(const const_node_ptr & header) { return detail::uncast(header); } //! <b>Requires</b>: 'header' is the header node of a tree. @@ -229,7 +231,7 @@ class bstree_algorithms : public bstree_algorithms_base<NodeTraits> //! <b>Complexity</b>: Constant time. //! //! <b>Throws</b>: Nothing. - static node_ptr root_node(const const_node_ptr & header) + BOOST_INTRUSIVE_FORCEINLINE static node_ptr root_node(const const_node_ptr & header) { node_ptr p = node_traits::get_parent(header); return p ? p : detail::uncast(header); @@ -243,7 +245,7 @@ class bstree_algorithms : public bstree_algorithms_base<NodeTraits> //! <b>Complexity</b>: Constant time. //! //! <b>Throws</b>: Nothing. - static bool unique(const const_node_ptr & node) + BOOST_INTRUSIVE_FORCEINLINE static bool unique(const const_node_ptr & node) { return !NodeTraits::get_parent(node); } #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) @@ -443,7 +445,7 @@ class bstree_algorithms : public bstree_algorithms_base<NodeTraits> //! new_node is not equivalent to node_to_be_replaced according to the //! ordering rules. This function is faster than erasing and inserting //! the node, since no rebalancing and comparison is needed. Experimental function - static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & new_node) + BOOST_INTRUSIVE_FORCEINLINE static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & new_node) { if(node_to_be_replaced == new_node) return; @@ -554,7 +556,7 @@ class bstree_algorithms : public bstree_algorithms_base<NodeTraits> //! <b>Throws</b>: Nothing. //! //! <b>Nodes</b>: If node is inserted in a tree, this function corrupts the tree. - static void init(const node_ptr & node) + BOOST_INTRUSIVE_FORCEINLINE static void init(const node_ptr & node) { NodeTraits::set_parent(node, node_ptr()); NodeTraits::set_left(node, node_ptr()); @@ -566,7 +568,7 @@ class bstree_algorithms : public bstree_algorithms_base<NodeTraits> //! <b>Complexity</b>: Constant. //! //! <b>Throws</b>: Nothing. - static bool inited(const const_node_ptr & node) + BOOST_INTRUSIVE_FORCEINLINE static bool inited(const const_node_ptr & node) { return !NodeTraits::get_parent(node) && !NodeTraits::get_left(node) && @@ -583,7 +585,7 @@ class bstree_algorithms : public bstree_algorithms_base<NodeTraits> //! <b>Throws</b>: Nothing. //! //! <b>Nodes</b>: If node is inserted in a tree, this function corrupts the tree. - static void init_header(const node_ptr & header) + BOOST_INTRUSIVE_FORCEINLINE static void init_header(const node_ptr & header) { NodeTraits::set_parent(header, node_ptr()); NodeTraits::set_left(header, header); @@ -865,7 +867,7 @@ class bstree_algorithms : public bstree_algorithms_base<NodeTraits> //! //! <b>Throws</b>: If "comp" throws. template<class KeyType, class KeyNodePtrCompare> - static std::pair<node_ptr, node_ptr> equal_range + BOOST_INTRUSIVE_FORCEINLINE static std::pair<node_ptr, node_ptr> equal_range (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) { return bounded_range(header, key, key, comp, true, true); @@ -909,7 +911,7 @@ class bstree_algorithms : public bstree_algorithms_base<NodeTraits> //! //! <b>Throws</b>: If "comp" throws. template<class KeyType, class KeyNodePtrCompare> - static node_ptr lower_bound + BOOST_INTRUSIVE_FORCEINLINE static node_ptr lower_bound (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) { return lower_bound_loop(NodeTraits::get_parent(header), detail::uncast(header), key, comp); @@ -927,7 +929,7 @@ class bstree_algorithms : public bstree_algorithms_base<NodeTraits> //! //! <b>Throws</b>: If "comp" throws. template<class KeyType, class KeyNodePtrCompare> - static node_ptr upper_bound + BOOST_INTRUSIVE_FORCEINLINE static node_ptr upper_bound (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) { return upper_bound_loop(NodeTraits::get_parent(header), detail::uncast(header), key, comp); @@ -950,7 +952,7 @@ class bstree_algorithms : public bstree_algorithms_base<NodeTraits> //! <b>Notes</b>: This function has only sense if a "insert_unique_check" has been //! previously executed to fill "commit_data". No value should be inserted or //! erased between the "insert_check" and "insert_commit" calls. - static void insert_unique_commit + BOOST_INTRUSIVE_FORCEINLINE static void insert_unique_commit (const node_ptr & header, const node_ptr & new_value, const insert_commit_data &commit_data) { return insert_commit(header, new_value, commit_data); } @@ -1311,12 +1313,49 @@ class bstree_algorithms : public bstree_algorithms_base<NodeTraits> //! <b>Complexity</b>: Amortized constant time. //! //! <b>Throws</b>: Nothing. - static void erase(const node_ptr & header, const node_ptr & z) + BOOST_INTRUSIVE_FORCEINLINE static void erase(const node_ptr & header, const node_ptr & z) { data_for_rebalance ignored; erase(header, z, ignored); } + //! <b>Requires</b>: header1 and header2 must be the headers of trees tree1 and tree2 + //! respectively, z a non-header node of tree1. NodePtrCompare is the comparison + //! function of tree1.. + //! + //! <b>Effects</b>: Transfers node "z" from tree1 to tree2 if tree1 does not contain + //! a node that is equivalent to z. + //! + //! <b>Returns</b>: True if the node was trasferred, false otherwise. + //! + //! <b>Complexity</b>: Logarithmic. + //! + //! <b>Throws</b>: If the comparison throws. + template<class NodePtrCompare> + BOOST_INTRUSIVE_FORCEINLINE static bool transfer_unique + (const node_ptr & header1, NodePtrCompare comp, const node_ptr &header2, const node_ptr & z) + { + data_for_rebalance ignored; + return transfer_unique(header1, comp, header2, z, ignored); + } + + //! <b>Requires</b>: header1 and header2 must be the headers of trees tree1 and tree2 + //! respectively, z a non-header node of tree1. NodePtrCompare is the comparison + //! function of tree1.. + //! + //! <b>Effects</b>: Transfers node "z" from tree1 to tree2. + //! + //! <b>Complexity</b>: Logarithmic. + //! + //! <b>Throws</b>: If the comparison throws. + template<class NodePtrCompare> + BOOST_INTRUSIVE_FORCEINLINE static void transfer_equal + (const node_ptr & header1, NodePtrCompare comp, const node_ptr &header2, const node_ptr & z) + { + data_for_rebalance ignored; + transfer_equal(header1, comp, header2, z, ignored); + } + //! <b>Requires</b>: node is a tree node but not the header. //! //! <b>Effects</b>: Unlinks the node and rebalances the tree. @@ -1431,6 +1470,30 @@ class bstree_algorithms : public bstree_algorithms_base<NodeTraits> } protected: + + template<class NodePtrCompare> + static bool transfer_unique + (const node_ptr & header1, NodePtrCompare comp, const node_ptr &header2, const node_ptr & z, data_for_rebalance &info) + { + insert_commit_data commit_data; + bool const transferable = insert_unique_check(header1, z, comp, commit_data).second; + if(transferable){ + erase(header2, z, info); + insert_commit(header1, z, commit_data); + } + return transferable; + } + + template<class NodePtrCompare> + static void transfer_equal + (const node_ptr & header1, NodePtrCompare comp, const node_ptr &header2, const node_ptr & z, data_for_rebalance &info) + { + insert_commit_data commit_data; + insert_equal_upper_bound_check(header1, z, comp, commit_data); + erase(header2, z, info); + insert_commit(header1, z, commit_data); + } + static void erase(const node_ptr & header, const node_ptr & z, data_for_rebalance &info) { node_ptr y(z); @@ -1563,7 +1626,7 @@ class bstree_algorithms : public bstree_algorithms_base<NodeTraits> //! <b>Complexity</b>: Constant. //! //! <b>Throws</b>: Nothing. - static bool is_left_child(const node_ptr & p) + BOOST_INTRUSIVE_FORCEINLINE static bool is_left_child(const node_ptr & p) { return NodeTraits::get_left(NodeTraits::get_parent(p)) == p; } //! <b>Requires</b>: p is a node of a tree. @@ -1573,7 +1636,7 @@ class bstree_algorithms : public bstree_algorithms_base<NodeTraits> //! <b>Complexity</b>: Constant. //! //! <b>Throws</b>: Nothing. - static bool is_right_child(const node_ptr & p) + BOOST_INTRUSIVE_FORCEINLINE static bool is_right_child(const node_ptr & p) { return NodeTraits::get_right(NodeTraits::get_parent(p)) == p; } static void insert_before_check diff --git a/boost/intrusive/circular_list_algorithms.hpp b/boost/intrusive/circular_list_algorithms.hpp index f3430455ae..72eae326d1 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 951a40ab87..da840ef0c1 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 6da48e9e79..70ec63f574 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 4b087b582b..26a1edcd3e 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 c6fa289a23..5e6ff4d1aa 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 ef278ed805..31b2f81398 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 b57a12b458..13421b8805 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 2e73305d17..92ef60ee6d 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 1a5ec32acc..9d64f09bcd 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 9802ac32f1..bd14dc5049 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 810d894066..c8f596fc96 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 f9074c0141..313da829d3 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 4b1f06ff9f..6c8e9b797c 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 a59734a7de..a955c441ef 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 aef72537e7..892e4e20d7 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 fdcb5cb3c5..6523ffb574 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 ffade48b7c..f5589ce27b 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 276362d2fc..4f5d86dd6a 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 2a74e1b2cd..6a7c563cf0 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 36c46c7e6e..3cd9013d4b 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 b641280878..e303b6442b 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 171bd59ed1..745c3790b9 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 6e7af7dfd3..033efb878d 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 2d741841e1..e6002a73b0 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 d64bf49d18..00206990f6 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 eac27370ec..0f37772c6d 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 893b580812..da7662eeb1 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 afc10819a3..f6a1a93a9d 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 1c6afdf63c..be2e18227e 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 385271943e..8567072d54 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 006a880d15..b1a82b3d0f 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 f97b3760c2..bf162badf0 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 1174dff26f..1968fa250e 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 95a575a9fc..a18d2354c4 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 |