Mercurial > hg > vamp-build-and-test
diff DEPENDENCIES/generic/include/boost/container/detail/tree.hpp @ 101:c530137014c0
Update Boost headers (1.58.0)
| author | Chris Cannam |
|---|---|
| date | Mon, 07 Sep 2015 11:12:49 +0100 |
| parents | 2665513ce2d3 |
| children |
line wrap: on
line diff
--- a/DEPENDENCIES/generic/include/boost/container/detail/tree.hpp Fri Sep 04 12:01:02 2015 +0100 +++ b/DEPENDENCIES/generic/include/boost/container/detail/tree.hpp Mon Sep 07 11:12:49 2015 +0100 @@ -1,6 +1,6 @@ ////////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2005-2012. Distributed under the Boost +// (C) Copyright Ion Gaztanaga 2005-2013. Distributed under the Boost // Software License, Version 1.0. (See accompanying file // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) // @@ -11,51 +11,66 @@ #ifndef BOOST_CONTAINER_TREE_HPP #define BOOST_CONTAINER_TREE_HPP -#include "config_begin.hpp" +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + +#include <boost/container/detail/config_begin.hpp> #include <boost/container/detail/workaround.hpp> +// container +#include <boost/container/allocator_traits.hpp> #include <boost/container/container_fwd.hpp> +#include <boost/container/options.hpp> -#include <boost/move/utility.hpp> -#include <boost/intrusive/pointer_traits.hpp> -#include <boost/type_traits/has_trivial_destructor.hpp> -#include <boost/detail/no_exceptions_support.hpp> -#include <boost/intrusive/rbtree.hpp> -#include <boost/container/detail/utilities.hpp> +// container/detail +#include <boost/container/detail/algorithm.hpp> //algo_equal(), algo_lexicographical_compare +#include <boost/container/detail/compare_functors.hpp> +#include <boost/container/detail/destroyers.hpp> +#include <boost/container/detail/iterator.hpp> #include <boost/container/detail/iterators.hpp> -#include <boost/container/detail/algorithms.hpp> #include <boost/container/detail/node_alloc_holder.hpp> -#include <boost/container/detail/destroyers.hpp> #include <boost/container/detail/pair.hpp> #include <boost/container/detail/type_traits.hpp> -#include <boost/container/allocator_traits.hpp> -#include <boost/detail/no_exceptions_support.hpp> -#ifndef BOOST_CONTAINER_PERFECT_FORWARDING -#include <boost/container/detail/preprocessor.hpp> +// intrusive +#include <boost/intrusive/pointer_traits.hpp> +#include <boost/intrusive/rbtree.hpp> +#include <boost/intrusive/avltree.hpp> +#include <boost/intrusive/splaytree.hpp> +#include <boost/intrusive/sgtree.hpp> +// intrusive/detail +#include <boost/intrusive/detail/minimal_pair_header.hpp> //pair +// move +#include <boost/move/utility_core.hpp> +// move/detail +#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) +#include <boost/move/detail/fwd_macros.hpp> #endif - -#include <utility> //std::pair -#include <iterator> -#include <algorithm> +// other +#include <boost/core/no_exceptions_support.hpp> namespace boost { namespace container { namespace container_detail { -template<class Key, class Value, class KeyCompare, class KeyOfValue> +template<class Key, class T, class Compare, class KeyOfValue> struct tree_value_compare - : public KeyCompare + : public Compare { - typedef Value value_type; - typedef KeyCompare key_compare; + typedef T value_type; + typedef Compare key_compare; typedef KeyOfValue key_of_value; typedef Key key_type; explicit tree_value_compare(const key_compare &kcomp) - : KeyCompare(kcomp) + : Compare(kcomp) {} tree_value_compare() - : KeyCompare() + : Compare() {} const key_compare &key_comp() const @@ -64,68 +79,103 @@ key_compare &key_comp() { return static_cast<key_compare &>(*this); } - template<class T> + template<class U> struct is_key { - static const bool value = is_same<const T, const key_type>::value; + static const bool value = is_same<const U, const key_type>::value; }; - template<class T> - typename enable_if_c<is_key<T>::value, const key_type &>::type - key_forward(const T &key) const + template<class U> + typename enable_if_c<is_key<U>::value, const key_type &>::type + key_forward(const U &key) const { return key; } - template<class T> - typename enable_if_c<!is_key<T>::value, const key_type &>::type - key_forward(const T &key) const + template<class U> + typename enable_if_c<!is_key<U>::value, const key_type &>::type + key_forward(const U &key) const { return KeyOfValue()(key); } template<class KeyType, class KeyType2> bool operator()(const KeyType &key1, const KeyType2 &key2) const { return key_compare::operator()(this->key_forward(key1), this->key_forward(key2)); } + + template<class KeyType, class KeyType2> + bool operator()(const KeyType &key1, const KeyType2 &key2) + { return key_compare::operator()(this->key_forward(key1), this->key_forward(key2)); } }; -template<class VoidPointer> -struct rbtree_hook +template<class VoidPointer, boost::container::tree_type_enum tree_type_value, bool OptimizeSize> +struct intrusive_tree_hook; + +template<class VoidPointer, bool OptimizeSize> +struct intrusive_tree_hook<VoidPointer, boost::container::red_black_tree, OptimizeSize> { typedef typename container_detail::bi::make_set_base_hook < container_detail::bi::void_pointer<VoidPointer> , container_detail::bi::link_mode<container_detail::bi::normal_link> - , container_detail::bi::optimize_size<true> + , container_detail::bi::optimize_size<OptimizeSize> + >::type type; +}; + +template<class VoidPointer, bool OptimizeSize> +struct intrusive_tree_hook<VoidPointer, boost::container::avl_tree, OptimizeSize> +{ + typedef typename container_detail::bi::make_avl_set_base_hook + < container_detail::bi::void_pointer<VoidPointer> + , container_detail::bi::link_mode<container_detail::bi::normal_link> + , container_detail::bi::optimize_size<OptimizeSize> + >::type type; +}; + +template<class VoidPointer, bool OptimizeSize> +struct intrusive_tree_hook<VoidPointer, boost::container::scapegoat_tree, OptimizeSize> +{ + typedef typename container_detail::bi::make_bs_set_base_hook + < container_detail::bi::void_pointer<VoidPointer> + , container_detail::bi::link_mode<container_detail::bi::normal_link> + >::type type; +}; + +template<class VoidPointer, bool OptimizeSize> +struct intrusive_tree_hook<VoidPointer, boost::container::splay_tree, OptimizeSize> +{ + typedef typename container_detail::bi::make_bs_set_base_hook + < container_detail::bi::void_pointer<VoidPointer> + , container_detail::bi::link_mode<container_detail::bi::normal_link> >::type type; }; //This trait is used to type-pun std::pair because in C++03 //compilers std::pair is useless for C++11 features template<class T> -struct rbtree_internal_data_type +struct tree_internal_data_type { typedef T type; }; template<class T1, class T2> -struct rbtree_internal_data_type< std::pair<T1, T2> > +struct tree_internal_data_type< std::pair<T1, T2> > { typedef pair<T1, T2> type; }; - //The node to be store in the tree -template <class T, class VoidPointer> -struct rbtree_node - : public rbtree_hook<VoidPointer>::type +template <class T, class VoidPointer, boost::container::tree_type_enum tree_type_value, bool OptimizeSize> +struct tree_node + : public intrusive_tree_hook<VoidPointer, tree_type_value, OptimizeSize>::type { private: - //BOOST_COPYABLE_AND_MOVABLE(rbtree_node) - rbtree_node(); + //BOOST_COPYABLE_AND_MOVABLE(tree_node) + tree_node(); public: - typedef typename rbtree_hook<VoidPointer>::type hook_type; + typedef typename intrusive_tree_hook + <VoidPointer, tree_type_value, OptimizeSize>::type hook_type; + typedef T value_type; + typedef typename tree_internal_data_type<T>::type internal_type; - typedef T value_type; - typedef typename rbtree_internal_data_type<T>::type internal_type; - - typedef rbtree_node<T, VoidPointer> node_type; + typedef tree_node< T, VoidPointer + , tree_type_value, OptimizeSize> node_type; T &get_data() { @@ -141,17 +191,17 @@ internal_type m_data; - template<class A, class B> - void do_assign(const std::pair<const A, B> &p) + template<class T1, class T2> + void do_assign(const std::pair<const T1, T2> &p) { - const_cast<A&>(m_data.first) = p.first; + const_cast<T1&>(m_data.first) = p.first; m_data.second = p.second; } - template<class A, class B> - void do_assign(const pair<const A, B> &p) + template<class T1, class T2> + void do_assign(const pair<const T1, T2> &p) { - const_cast<A&>(m_data.first) = p.first; + const_cast<T1&>(m_data.first) = p.first; m_data.second = p.second; } @@ -159,17 +209,17 @@ void do_assign(const V &v) { m_data = v; } - template<class A, class B> - void do_move_assign(std::pair<const A, B> &p) + template<class T1, class T2> + void do_move_assign(std::pair<const T1, T2> &p) { - const_cast<A&>(m_data.first) = ::boost::move(p.first); + const_cast<T1&>(m_data.first) = ::boost::move(p.first); m_data.second = ::boost::move(p.second); } - template<class A, class B> - void do_move_assign(pair<const A, B> &p) + template<class T1, class T2> + void do_move_assign(pair<const T1, T2> &p) { - const_cast<A&>(m_data.first) = ::boost::move(p.first); + const_cast<T1&>(m_data.first) = ::boost::move(p.first); m_data.second = ::boost::move(p.second); } @@ -178,6 +228,11 @@ { m_data = ::boost::move(v); } }; +template <class T, class VoidPointer, boost::container::tree_type_enum tree_type_value, bool OptimizeSize> +struct iiterator_node_value_type< tree_node<T, VoidPointer, tree_type_value, OptimizeSize> > { + typedef T type; +}; + template<class Node, class Icont> class insert_equal_end_hint_functor { @@ -210,228 +265,297 @@ namespace container_detail { -template<class A, class ValueCompare> -struct intrusive_rbtree_type +template< class NodeType, class NodeCompareType + , class SizeType, class HookType + , boost::container::tree_type_enum tree_type_value> +struct intrusive_tree_dispatch; + +template<class NodeType, class NodeCompareType, class SizeType, class HookType> +struct intrusive_tree_dispatch + <NodeType, NodeCompareType, SizeType, HookType, boost::container::red_black_tree> { + typedef typename container_detail::bi::make_rbtree + <NodeType + ,container_detail::bi::compare<NodeCompareType> + ,container_detail::bi::base_hook<HookType> + ,container_detail::bi::constant_time_size<true> + ,container_detail::bi::size_type<SizeType> + >::type type; +}; + +template<class NodeType, class NodeCompareType, class SizeType, class HookType> +struct intrusive_tree_dispatch + <NodeType, NodeCompareType, SizeType, HookType, boost::container::avl_tree> +{ + typedef typename container_detail::bi::make_avltree + <NodeType + ,container_detail::bi::compare<NodeCompareType> + ,container_detail::bi::base_hook<HookType> + ,container_detail::bi::constant_time_size<true> + ,container_detail::bi::size_type<SizeType> + >::type type; +}; + +template<class NodeType, class NodeCompareType, class SizeType, class HookType> +struct intrusive_tree_dispatch + <NodeType, NodeCompareType, SizeType, HookType, boost::container::scapegoat_tree> +{ + typedef typename container_detail::bi::make_sgtree + <NodeType + ,container_detail::bi::compare<NodeCompareType> + ,container_detail::bi::base_hook<HookType> + ,container_detail::bi::floating_point<true> + ,container_detail::bi::size_type<SizeType> + >::type type; +}; + +template<class NodeType, class NodeCompareType, class SizeType, class HookType> +struct intrusive_tree_dispatch + <NodeType, NodeCompareType, SizeType, HookType, boost::container::splay_tree> +{ + typedef typename container_detail::bi::make_splaytree + <NodeType + ,container_detail::bi::compare<NodeCompareType> + ,container_detail::bi::base_hook<HookType> + ,container_detail::bi::constant_time_size<true> + ,container_detail::bi::size_type<SizeType> + >::type type; +}; + +template<class Allocator, class ValueCompare, boost::container::tree_type_enum tree_type_value, bool OptimizeSize> +struct intrusive_tree_type +{ + private: typedef typename boost::container:: - allocator_traits<A>::value_type value_type; + allocator_traits<Allocator>::value_type value_type; typedef typename boost::container:: - allocator_traits<A>::void_pointer void_pointer; + allocator_traits<Allocator>::void_pointer void_pointer; typedef typename boost::container:: - allocator_traits<A>::size_type size_type; - typedef typename container_detail::rbtree_node - <value_type, void_pointer> node_type; - typedef node_compare<ValueCompare, node_type> node_compare_type; - typedef typename container_detail::bi::make_rbtree - <node_type - ,container_detail::bi::compare<node_compare_type> - ,container_detail::bi::base_hook<typename rbtree_hook<void_pointer>::type> - ,container_detail::bi::constant_time_size<true> - ,container_detail::bi::size_type<size_type> - >::type container_type; - typedef container_type type ; + allocator_traits<Allocator>::size_type size_type; + typedef typename container_detail::tree_node + < value_type, void_pointer + , tree_type_value, OptimizeSize> node_type; + typedef value_to_node_compare + <node_type, ValueCompare> node_compare_type; + //Deducing the hook type from node_type (e.g. node_type::hook_type) would + //provoke an early instantiation of node_type that could ruin recursive + //tree definitions, so retype the complete type to avoid any problem. + typedef typename intrusive_tree_hook + <void_pointer, tree_type_value + , OptimizeSize>::type hook_type; + public: + typedef typename intrusive_tree_dispatch + < node_type, node_compare_type + , size_type, hook_type + , tree_type_value>::type type; +}; + +//Trait to detect manually rebalanceable tree types +template<boost::container::tree_type_enum tree_type_value> +struct is_manually_balanceable +{ static const bool value = true; }; + +template<> struct is_manually_balanceable<red_black_tree> +{ static const bool value = false; }; + +template<> struct is_manually_balanceable<avl_tree> +{ static const bool value = false; }; + +//Proxy traits to implement different operations depending on the +//is_manually_balanceable<>::value +template< boost::container::tree_type_enum tree_type_value + , bool IsManuallyRebalanceable = is_manually_balanceable<tree_type_value>::value> +struct intrusive_tree_proxy +{ + template<class Icont> + static void rebalance(Icont &) {} +}; + +template<boost::container::tree_type_enum tree_type_value> +struct intrusive_tree_proxy<tree_type_value, true> +{ + template<class Icont> + static void rebalance(Icont &c) + { c.rebalance(); } }; } //namespace container_detail { namespace container_detail { -template <class Key, class Value, class KeyOfValue, - class KeyCompare, class A> -class rbtree +//This functor will be used with Intrusive clone functions to obtain +//already allocated nodes from a intrusive container instead of +//allocating new ones. When the intrusive container runs out of nodes +//the node holder is used instead. +template<class AllocHolder, bool DoMove> +class RecyclingCloner +{ + typedef typename AllocHolder::intrusive_container intrusive_container; + typedef typename AllocHolder::Node node_type; + typedef typename AllocHolder::NodePtr node_ptr_type; + + public: + RecyclingCloner(AllocHolder &holder, intrusive_container &itree) + : m_holder(holder), m_icont(itree) + {} + + static void do_assign(node_ptr_type &p, const node_type &other, bool_<true>) + { p->do_move_assign(const_cast<node_type &>(other).m_data); } + + static void do_assign(node_ptr_type &p, const node_type &other, bool_<false>) + { p->do_assign(other.m_data); } + + node_ptr_type operator()(const node_type &other) const + { + if(node_ptr_type p = m_icont.unlink_leftmost_without_rebalance()){ + //First recycle a node (this can't throw) + BOOST_TRY{ + //This can throw + this->do_assign(p, other, bool_<DoMove>()); + return p; + } + BOOST_CATCH(...){ + //If there is an exception destroy the whole source + m_holder.destroy_node(p); + while((p = m_icont.unlink_leftmost_without_rebalance())){ + m_holder.destroy_node(p); + } + BOOST_RETHROW + } + BOOST_CATCH_END + } + else{ + return m_holder.create_node(other.m_data); + } + } + + AllocHolder &m_holder; + intrusive_container &m_icont; +}; + +template<class KeyValueCompare, class Node> +//where KeyValueCompare is tree_value_compare<Key, T, Compare, KeyOfValue> +struct key_node_compare + : private KeyValueCompare +{ + explicit key_node_compare(const KeyValueCompare &comp) + : KeyValueCompare(comp) + {} + + template<class T> + struct is_node + { + static const bool value = is_same<T, Node>::value; + }; + + template<class T> + typename enable_if_c<is_node<T>::value, const typename KeyValueCompare::value_type &>::type + key_forward(const T &node) const + { return node.get_data(); } + + template<class T> + typename enable_if_c<!is_node<T>::value, const T &>::type + key_forward(const T &key) const + { return key; } + + template<class KeyType, class KeyType2> + bool operator()(const KeyType &key1, const KeyType2 &key2) const + { return KeyValueCompare::operator()(this->key_forward(key1), this->key_forward(key2)); } +}; + +template <class Key, class T, class KeyOfValue, + class Compare, class Allocator, + class Options = tree_assoc_defaults> +class tree : protected container_detail::node_alloc_holder - < A - , typename container_detail::intrusive_rbtree_type - <A, tree_value_compare<Key, Value, KeyCompare, KeyOfValue> - >::type - , tree_value_compare<Key, Value, KeyCompare, KeyOfValue> + < Allocator + , typename container_detail::intrusive_tree_type + < Allocator, tree_value_compare<Key, T, Compare, KeyOfValue> //ValComp + , Options::tree_type, Options::optimize_size>::type > { typedef tree_value_compare - <Key, Value, KeyCompare, KeyOfValue> ValComp; - typedef typename container_detail::intrusive_rbtree_type - < A, ValComp>::type Icont; - typedef container_detail::node_alloc_holder - <A, Icont, ValComp> AllocHolder; + <Key, T, Compare, KeyOfValue> ValComp; + typedef typename container_detail::intrusive_tree_type + < Allocator, ValComp, Options::tree_type + , Options::optimize_size>::type Icont; + typedef container_detail::node_alloc_holder + <Allocator, Icont> AllocHolder; typedef typename AllocHolder::NodePtr NodePtr; - typedef rbtree < Key, Value, KeyOfValue - , KeyCompare, A> ThisType; + typedef tree < Key, T, KeyOfValue + , Compare, Allocator, Options> ThisType; typedef typename AllocHolder::NodeAlloc NodeAlloc; + typedef boost::container:: + allocator_traits<NodeAlloc> allocator_traits_type; typedef typename AllocHolder::ValAlloc ValAlloc; typedef typename AllocHolder::Node Node; typedef typename Icont::iterator iiterator; typedef typename Icont::const_iterator iconst_iterator; typedef container_detail::allocator_destroyer<NodeAlloc> Destroyer; - typedef typename AllocHolder::allocator_v1 allocator_v1; - typedef typename AllocHolder::allocator_v2 allocator_v2; typedef typename AllocHolder::alloc_version alloc_version; + typedef intrusive_tree_proxy<Options::tree_type> intrusive_tree_proxy_t; - class RecyclingCloner; - friend class RecyclingCloner; - - class RecyclingCloner - { - public: - RecyclingCloner(AllocHolder &holder, Icont &irbtree) - : m_holder(holder), m_icont(irbtree) - {} - - NodePtr operator()(const Node &other) const - { - if(NodePtr p = m_icont.unlink_leftmost_without_rebalance()){ - //First recycle a node (this can't throw) - BOOST_TRY{ - //This can throw - p->do_assign(other.m_data); - return p; - } - BOOST_CATCH(...){ - //If there is an exception destroy the whole source - m_holder.destroy_node(p); - while((p = m_icont.unlink_leftmost_without_rebalance())){ - m_holder.destroy_node(p); - } - BOOST_RETHROW - } - BOOST_CATCH_END - } - else{ - return m_holder.create_node(other.m_data); - } - } - - AllocHolder &m_holder; - Icont &m_icont; - }; - - class RecyclingMoveCloner; - friend class RecyclingMoveCloner; - - class RecyclingMoveCloner - { - public: - RecyclingMoveCloner(AllocHolder &holder, Icont &irbtree) - : m_holder(holder), m_icont(irbtree) - {} - - NodePtr operator()(const Node &other) const - { - if(NodePtr p = m_icont.unlink_leftmost_without_rebalance()){ - //First recycle a node (this can't throw) - BOOST_TRY{ - //This can throw - p->do_move_assign(const_cast<Node &>(other).m_data); - return p; - } - BOOST_CATCH(...){ - //If there is an exception destroy the whole source - m_holder.destroy_node(p); - while((p = m_icont.unlink_leftmost_without_rebalance())){ - m_holder.destroy_node(p); - } - BOOST_RETHROW - } - BOOST_CATCH_END - } - else{ - return m_holder.create_node(other.m_data); - } - } - - AllocHolder &m_holder; - Icont &m_icont; - }; - - BOOST_COPYABLE_AND_MOVABLE(rbtree) + BOOST_COPYABLE_AND_MOVABLE(tree) public: typedef Key key_type; - typedef Value value_type; - typedef A allocator_type; - typedef KeyCompare key_compare; + typedef T value_type; + typedef Allocator allocator_type; + typedef Compare key_compare; typedef ValComp value_compare; typedef typename boost::container:: - allocator_traits<A>::pointer pointer; + allocator_traits<Allocator>::pointer pointer; typedef typename boost::container:: - allocator_traits<A>::const_pointer const_pointer; + allocator_traits<Allocator>::const_pointer const_pointer; typedef typename boost::container:: - allocator_traits<A>::reference reference; + allocator_traits<Allocator>::reference reference; typedef typename boost::container:: - allocator_traits<A>::const_reference const_reference; + allocator_traits<Allocator>::const_reference const_reference; typedef typename boost::container:: - allocator_traits<A>::size_type size_type; + allocator_traits<Allocator>::size_type size_type; typedef typename boost::container:: - allocator_traits<A>::difference_type difference_type; - typedef difference_type rbtree_difference_type; - typedef pointer rbtree_pointer; - typedef const_pointer rbtree_const_pointer; - typedef reference rbtree_reference; - typedef const_reference rbtree_const_reference; + allocator_traits<Allocator>::difference_type difference_type; + typedef difference_type tree_difference_type; + typedef pointer tree_pointer; + typedef const_pointer tree_const_pointer; + typedef reference tree_reference; + typedef const_reference tree_const_reference; typedef NodeAlloc stored_allocator_type; private: - template<class KeyValueCompare> - struct key_node_compare - : private KeyValueCompare - { - key_node_compare(const KeyValueCompare &comp) - : KeyValueCompare(comp) - {} - - template<class T> - struct is_node - { - static const bool value = is_same<T, Node>::value; - }; - - template<class T> - typename enable_if_c<is_node<T>::value, const value_type &>::type - key_forward(const T &node) const - { return node.get_data(); } - - template<class T> - typename enable_if_c<!is_node<T>::value, const T &>::type - key_forward(const T &key) const - { return key; } - - template<class KeyType, class KeyType2> - bool operator()(const KeyType &key1, const KeyType2 &key2) const - { return KeyValueCompare::operator()(this->key_forward(key1), this->key_forward(key2)); } - }; - - typedef key_node_compare<value_compare> KeyNodeCompare; + typedef key_node_compare<value_compare, Node> KeyNodeCompare; public: - typedef container_detail::iterator<iiterator, false> iterator; - typedef container_detail::iterator<iiterator, true > const_iterator; - typedef std::reverse_iterator<iterator> reverse_iterator; - typedef std::reverse_iterator<const_iterator> const_reverse_iterator; + typedef container_detail::iterator_from_iiterator<iiterator, false> iterator; + typedef container_detail::iterator_from_iiterator<iiterator, true > const_iterator; + typedef boost::container::reverse_iterator<iterator> reverse_iterator; + typedef boost::container::reverse_iterator<const_iterator> const_reverse_iterator; - rbtree() - : AllocHolder(ValComp(key_compare())) + tree() + : AllocHolder() {} - explicit rbtree(const key_compare& comp, const allocator_type& a = allocator_type()) - : AllocHolder(a, ValComp(comp)) + explicit tree(const key_compare& comp, const allocator_type& a = allocator_type()) + : AllocHolder(ValComp(comp), a) {} - explicit rbtree(const allocator_type& a) + explicit tree(const allocator_type& a) : AllocHolder(a) {} template <class InputIterator> - rbtree(bool unique_insertion, InputIterator first, InputIterator last, const key_compare& comp, + tree(bool unique_insertion, InputIterator first, InputIterator last, const key_compare& comp, const allocator_type& a #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) , typename container_detail::enable_if_c < container_detail::is_input_iterator<InputIterator>::value - || container_detail::is_same<alloc_version, allocator_v1>::value + || container_detail::is_same<alloc_version, version_1>::value >::type * = 0 #endif ) - : AllocHolder(a, value_compare(comp)) + : AllocHolder(value_compare(comp), a) { //Use cend() as hint to achieve linear time for //ordered ranges as required by the standard @@ -450,16 +574,16 @@ } template <class InputIterator> - rbtree(bool unique_insertion, InputIterator first, InputIterator last, const key_compare& comp, + tree(bool unique_insertion, InputIterator first, InputIterator last, const key_compare& comp, const allocator_type& a #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) , typename container_detail::enable_if_c < !(container_detail::is_input_iterator<InputIterator>::value - || container_detail::is_same<alloc_version, allocator_v1>::value) + || container_detail::is_same<alloc_version, version_1>::value) >::type * = 0 #endif ) - : AllocHolder(a, value_compare(comp)) + : AllocHolder(value_compare(comp), a) { if(unique_insertion){ //Use cend() as hint to achieve linear time for @@ -473,22 +597,22 @@ else{ //Optimized allocation and construction this->allocate_many_and_construct - ( first, std::distance(first, last) + ( first, boost::container::iterator_distance(first, last) , insert_equal_end_hint_functor<Node, Icont>(this->icont())); } } template <class InputIterator> - rbtree( ordered_range_t, InputIterator first, InputIterator last + tree( ordered_range_t, InputIterator first, InputIterator last , const key_compare& comp = key_compare(), const allocator_type& a = allocator_type() #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) , typename container_detail::enable_if_c < container_detail::is_input_iterator<InputIterator>::value - || container_detail::is_same<alloc_version, allocator_v1>::value + || container_detail::is_same<alloc_version, version_1>::value >::type * = 0 #endif ) - : AllocHolder(a, value_compare(comp)) + : AllocHolder(value_compare(comp), a) { for ( ; first != last; ++first){ this->push_back_impl(*first); @@ -496,57 +620,57 @@ } template <class InputIterator> - rbtree( ordered_range_t, InputIterator first, InputIterator last + tree( ordered_range_t, InputIterator first, InputIterator last , const key_compare& comp = key_compare(), const allocator_type& a = allocator_type() #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) , typename container_detail::enable_if_c < !(container_detail::is_input_iterator<InputIterator>::value - || container_detail::is_same<alloc_version, allocator_v1>::value) + || container_detail::is_same<alloc_version, version_1>::value) >::type * = 0 #endif ) - : AllocHolder(a, value_compare(comp)) + : AllocHolder(value_compare(comp), a) { //Optimized allocation and construction this->allocate_many_and_construct - ( first, std::distance(first, last) + ( first, boost::container::iterator_distance(first, last) , container_detail::push_back_functor<Node, Icont>(this->icont())); } - rbtree(const rbtree& x) - : AllocHolder(x, x.value_comp()) + tree(const tree& x) + : AllocHolder(x.value_comp(), x) { this->icont().clone_from (x.icont(), typename AllocHolder::cloner(*this), Destroyer(this->node_alloc())); } - rbtree(BOOST_RV_REF(rbtree) x) - : AllocHolder(::boost::move(static_cast<AllocHolder&>(x)), x.value_comp()) + tree(BOOST_RV_REF(tree) x) + : AllocHolder(BOOST_MOVE_BASE(AllocHolder, x), x.value_comp()) {} - rbtree(const rbtree& x, const allocator_type &a) - : AllocHolder(a, x.value_comp()) + tree(const tree& x, const allocator_type &a) + : AllocHolder(x.value_comp(), a) { this->icont().clone_from (x.icont(), typename AllocHolder::cloner(*this), Destroyer(this->node_alloc())); } - rbtree(BOOST_RV_REF(rbtree) x, const allocator_type &a) - : AllocHolder(a, x.value_comp()) + tree(BOOST_RV_REF(tree) x, const allocator_type &a) + : AllocHolder(x.value_comp(), a) { if(this->node_alloc() == x.node_alloc()){ this->icont().swap(x.icont()); } else{ this->icont().clone_from - (x.icont(), typename AllocHolder::cloner(*this), Destroyer(this->node_alloc())); + (x.icont(), typename AllocHolder::move_cloner(*this), Destroyer(this->node_alloc())); } } - ~rbtree() + ~tree() {} //AllocHolder clears the tree - rbtree& operator=(BOOST_COPY_ASSIGN_REF(rbtree) x) + tree& operator=(BOOST_COPY_ASSIGN_REF(tree) x) { if (&x != this){ NodeAlloc &this_alloc = this->get_stored_allocator(); @@ -565,7 +689,7 @@ //Now recreate the source tree reusing nodes stored by other_tree this->icont().clone_from (x.icont() - , RecyclingCloner(*this, other_tree) + , RecyclingCloner<AllocHolder, false>(*this, other_tree) , Destroyer(this->node_alloc())); //If there are remaining nodes, destroy them @@ -577,49 +701,55 @@ return *this; } - rbtree& operator=(BOOST_RV_REF(rbtree) x) + tree& operator=(BOOST_RV_REF(tree) x) + BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value + && boost::container::container_detail::is_nothrow_move_assignable<Compare>::value ) { - if (&x != this){ - NodeAlloc &this_alloc = this->get_stored_allocator(); - const NodeAlloc &x_alloc = x.get_stored_allocator(); - //If allocators are equal we can just swap pointers - if(this_alloc == x_alloc){ - //Destroy and swap pointers - this->clear(); - this->icont() = ::boost::move(x.icont()); - //Move allocator if needed - this->AllocHolder::move_assign_alloc(x); - } - //If unequal allocators, then do a one by one move - else{ - //Transfer all the nodes to a temporary tree - //If anything goes wrong, all the nodes will be destroyed - //automatically - Icont other_tree(::boost::move(this->icont())); + BOOST_ASSERT(this != &x); + NodeAlloc &this_alloc = this->node_alloc(); + NodeAlloc &x_alloc = x.node_alloc(); + const bool propagate_alloc = allocator_traits<NodeAlloc>:: + propagate_on_container_move_assignment::value; + const bool allocators_equal = this_alloc == x_alloc; (void)allocators_equal; + //Resources can be transferred if both allocators are + //going to be equal after this function (either propagated or already equal) + if(propagate_alloc || allocators_equal){ + //Destroy + this->clear(); + //Move allocator if needed + this->AllocHolder::move_assign_alloc(x); + //Obtain resources + this->icont() = boost::move(x.icont()); + } + //Else do a one by one move + else{ + //Transfer all the nodes to a temporary tree + //If anything goes wrong, all the nodes will be destroyed + //automatically + Icont other_tree(::boost::move(this->icont())); - //Now recreate the source tree reusing nodes stored by other_tree - this->icont().clone_from - (x.icont() - , RecyclingMoveCloner(*this, other_tree) - , Destroyer(this->node_alloc())); + //Now recreate the source tree reusing nodes stored by other_tree + this->icont().clone_from + (x.icont() + , RecyclingCloner<AllocHolder, true>(*this, other_tree) + , Destroyer(this->node_alloc())); - //If there are remaining nodes, destroy them - NodePtr p; - while((p = other_tree.unlink_leftmost_without_rebalance())){ - AllocHolder::destroy_node(p); - } + //If there are remaining nodes, destroy them + NodePtr p; + while((p = other_tree.unlink_leftmost_without_rebalance())){ + AllocHolder::destroy_node(p); } } return *this; } - public: + public: // accessors: value_compare value_comp() const - { return this->icont().value_comp().value_comp(); } + { return this->icont().value_comp().predicate(); } key_compare key_comp() const - { return this->icont().value_comp().value_comp().key_comp(); } + { return this->icont().value_comp().predicate().key_comp(); } allocator_type get_allocator() const { return allocator_type(this->node_alloc()); } @@ -698,6 +828,8 @@ { return AllocHolder::max_size(); } void swap(ThisType& x) + BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value + && boost::container::container_detail::is_nothrow_swappable<Compare>::value ) { AllocHolder::swap(x); } public: @@ -732,9 +864,9 @@ template<class MovableConvertible> iterator insert_unique_commit - (BOOST_FWD_REF(MovableConvertible) mv, insert_commit_data &data) + (BOOST_FWD_REF(MovableConvertible) v, insert_commit_data &data) { - NodePtr tmp = AllocHolder::create_node(boost::forward<MovableConvertible>(mv)); + NodePtr tmp = AllocHolder::create_node(boost::forward<MovableConvertible>(v)); scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); iterator ret(this->icont().insert_unique_commit(*tmp, data)); destroy_deallocator.release(); @@ -753,13 +885,13 @@ } template<class MovableConvertible> - std::pair<iterator,bool> insert_unique(BOOST_FWD_REF(MovableConvertible) mv) + std::pair<iterator,bool> insert_unique(BOOST_FWD_REF(MovableConvertible) v) { insert_commit_data data; std::pair<iterator,bool> ret = - this->insert_unique_check(KeyOfValue()(mv), data); + this->insert_unique_check(KeyOfValue()(v), data); if(ret.second){ - ret.first = this->insert_unique_commit(boost::forward<MovableConvertible>(mv), data); + ret.first = this->insert_unique_commit(boost::forward<MovableConvertible>(v), data); } return ret; } @@ -767,9 +899,9 @@ private: template<class MovableConvertible> - void push_back_impl(BOOST_FWD_REF(MovableConvertible) mv) + void push_back_impl(BOOST_FWD_REF(MovableConvertible) v) { - NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(mv))); + NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(v))); //push_back has no-throw guarantee so avoid any deallocator/destroyer this->icont().push_back(*tmp); } @@ -806,18 +938,18 @@ public: - #ifdef BOOST_CONTAINER_PERFECT_FORWARDING + #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) template <class... Args> - std::pair<iterator, bool> emplace_unique(Args&&... args) + std::pair<iterator, bool> emplace_unique(BOOST_FWD_REF(Args)... args) { return this->emplace_unique_impl(AllocHolder::create_node(boost::forward<Args>(args)...)); } template <class... Args> - iterator emplace_hint_unique(const_iterator hint, Args&&... args) + iterator emplace_hint_unique(const_iterator hint, BOOST_FWD_REF(Args)... args) { return this->emplace_unique_hint_impl(hint, AllocHolder::create_node(boost::forward<Args>(args)...)); } template <class... Args> - iterator emplace_equal(Args&&... args) + iterator emplace_equal(BOOST_FWD_REF(Args)... args) { NodePtr tmp(AllocHolder::create_node(boost::forward<Args>(args)...)); scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); @@ -827,7 +959,7 @@ } template <class... Args> - iterator emplace_hint_equal(const_iterator hint, Args&&... args) + iterator emplace_hint_equal(const_iterator hint, BOOST_FWD_REF(Args)... args) { NodePtr tmp(AllocHolder::create_node(boost::forward<Args>(args)...)); scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); @@ -836,49 +968,41 @@ return ret; } - #else //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING + #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) - #define BOOST_PP_LOCAL_MACRO(n) \ - BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \ - std::pair<iterator, bool> emplace_unique(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ - { \ - return this->emplace_unique_impl \ - (AllocHolder::create_node(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _))); \ - } \ - \ - BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \ - iterator emplace_hint_unique(const_iterator hint \ - BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ - { \ - return this->emplace_unique_hint_impl \ - (hint, AllocHolder::create_node(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _))); \ - } \ - \ - BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \ - iterator emplace_equal(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ - { \ - NodePtr tmp(AllocHolder::create_node(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _))); \ - scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); \ - iterator ret(this->icont().insert_equal(this->icont().end(), *tmp)); \ - destroy_deallocator.release(); \ - return ret; \ - } \ - \ - BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \ - iterator emplace_hint_equal(const_iterator hint \ - BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ - { \ - NodePtr tmp(AllocHolder::create_node(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _))); \ - scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); \ - iterator ret(this->icont().insert_equal(hint.get(), *tmp)); \ - destroy_deallocator.release(); \ - return ret; \ - } \ - //! - #define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS) - #include BOOST_PP_LOCAL_ITERATE() + #define BOOST_CONTAINER_TREE_EMPLACE_CODE(N) \ + BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ + std::pair<iterator, bool> emplace_unique(BOOST_MOVE_UREF##N)\ + { return this->emplace_unique_impl(AllocHolder::create_node(BOOST_MOVE_FWD##N)); }\ + \ + BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ + iterator emplace_hint_unique(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ + { return this->emplace_unique_hint_impl(hint, AllocHolder::create_node(BOOST_MOVE_FWD##N)); }\ + \ + BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ + iterator emplace_equal(BOOST_MOVE_UREF##N)\ + {\ + NodePtr tmp(AllocHolder::create_node(BOOST_MOVE_FWD##N));\ + scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());\ + iterator ret(this->icont().insert_equal(this->icont().end(), *tmp));\ + destroy_deallocator.release();\ + return ret;\ + }\ + \ + BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ + iterator emplace_hint_equal(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ + {\ + NodePtr tmp(AllocHolder::create_node(BOOST_MOVE_FWD##N));\ + scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());\ + iterator ret(this->icont().insert_equal(hint.get(), *tmp));\ + destroy_deallocator.release();\ + return ret;\ + }\ + // + BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_TREE_EMPLACE_CODE) + #undef BOOST_CONTAINER_TREE_EMPLACE_CODE - #endif //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING + #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) iterator insert_unique(const_iterator hint, const value_type& v) { @@ -891,14 +1015,14 @@ } template<class MovableConvertible> - iterator insert_unique(const_iterator hint, BOOST_FWD_REF(MovableConvertible) mv) + iterator insert_unique(const_iterator hint, BOOST_FWD_REF(MovableConvertible) v) { insert_commit_data data; std::pair<iterator,bool> ret = - this->insert_unique_check(hint, KeyOfValue()(mv), data); + this->insert_unique_check(hint, KeyOfValue()(v), data); if(!ret.second) return ret.first; - return this->insert_unique_commit(boost::forward<MovableConvertible>(mv), data); + return this->insert_unique_commit(boost::forward<MovableConvertible>(v), data); } template <class InputIterator> @@ -918,9 +1042,9 @@ } template<class MovableConvertible> - iterator insert_equal(BOOST_FWD_REF(MovableConvertible) mv) + iterator insert_equal(BOOST_FWD_REF(MovableConvertible) v) { - NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(mv))); + NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(v))); scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); iterator ret(this->icont().insert_equal(this->icont().end(), *tmp)); destroy_deallocator.release(); @@ -937,9 +1061,9 @@ } template<class MovableConvertible> - iterator insert_equal(const_iterator hint, BOOST_FWD_REF(MovableConvertible) mv) + iterator insert_equal(const_iterator hint, BOOST_FWD_REF(MovableConvertible) v) { - NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(mv))); + NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(v))); scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); iterator ret(this->icont().insert_equal(hint.get(), *tmp)); destroy_deallocator.release(); @@ -965,7 +1089,8 @@ void clear() { AllocHolder::clear(alloc_version()); } - // set operations: + // search operations. Const and non-const overloads even if no iterator is returned + // so splay implementations can to their rebalancing when searching in non-const versions iterator find(const key_type& k) { return iterator(this->icont().find(k, KeyNodeCompare(value_comp()))); } @@ -1001,83 +1126,68 @@ return std::pair<const_iterator,const_iterator> (const_iterator(ret.first), const_iterator(ret.second)); } + + std::pair<iterator,iterator> lower_bound_range(const key_type& k) + { + std::pair<iiterator, iiterator> ret = + this->icont().lower_bound_range(k, KeyNodeCompare(value_comp())); + return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second)); + } + + std::pair<const_iterator, const_iterator> lower_bound_range(const key_type& k) const + { + std::pair<iiterator, iiterator> ret = + this->non_const_icont().lower_bound_range(k, KeyNodeCompare(value_comp())); + return std::pair<const_iterator,const_iterator> + (const_iterator(ret.first), const_iterator(ret.second)); + } + + void rebalance() + { intrusive_tree_proxy_t::rebalance(this->icont()); } + + friend bool operator==(const tree& x, const tree& y) + { return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin()); } + + friend bool operator<(const tree& x, const tree& y) + { return ::boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); } + + friend bool operator!=(const tree& x, const tree& y) + { return !(x == y); } + + friend bool operator>(const tree& x, const tree& y) + { return y < x; } + + friend bool operator<=(const tree& x, const tree& y) + { return !(y < x); } + + friend bool operator>=(const tree& x, const tree& y) + { return !(x < y); } + + friend void swap(tree& x, tree& y) + { x.swap(y); } }; -template <class Key, class Value, class KeyOfValue, - class KeyCompare, class A> -inline bool -operator==(const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x, - const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& y) -{ - return x.size() == y.size() && - std::equal(x.begin(), x.end(), y.begin()); -} - -template <class Key, class Value, class KeyOfValue, - class KeyCompare, class A> -inline bool -operator<(const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x, - const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& y) -{ - return std::lexicographical_compare(x.begin(), x.end(), - y.begin(), y.end()); -} - -template <class Key, class Value, class KeyOfValue, - class KeyCompare, class A> -inline bool -operator!=(const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x, - const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& y) { - return !(x == y); -} - -template <class Key, class Value, class KeyOfValue, - class KeyCompare, class A> -inline bool -operator>(const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x, - const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& y) { - return y < x; -} - -template <class Key, class Value, class KeyOfValue, - class KeyCompare, class A> -inline bool -operator<=(const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x, - const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& y) { - return !(y < x); -} - -template <class Key, class Value, class KeyOfValue, - class KeyCompare, class A> -inline bool -operator>=(const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x, - const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& y) { - return !(x < y); -} - - -template <class Key, class Value, class KeyOfValue, - class KeyCompare, class A> -inline void -swap(rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x, - rbtree<Key,Value,KeyOfValue,KeyCompare,A>& y) -{ - x.swap(y); -} - } //namespace container_detail { } //namespace container { -/* + +template <class T> +struct has_trivial_destructor_after_move; + //!has_trivial_destructor_after_move<> == true_type //!specialization for optimizations -template <class K, class V, class KOV, -class C, class A> +template <class Key, class T, class KeyOfValue, class Compare, class Allocator, class Options> struct has_trivial_destructor_after_move - <boost::container::container_detail::rbtree<K, V, KOV, C, A> > + < + ::boost::container::container_detail::tree + <Key, T, KeyOfValue, Compare, Allocator, Options> + > { - static const bool value = has_trivial_destructor_after_move<A>::value && has_trivial_destructor_after_move<C>::value; + typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer; + static const bool value = ::boost::has_trivial_destructor_after_move<Allocator>::value && + ::boost::has_trivial_destructor_after_move<pointer>::value && + ::boost::has_trivial_destructor_after_move<Compare>::value; }; -*/ + } //namespace boost { #include <boost/container/detail/config_end.hpp>