diff options
Diffstat (limited to 'boost/container/detail/tree.hpp')
-rw-r--r-- | boost/container/detail/tree.hpp | 254 |
1 files changed, 122 insertions, 132 deletions
diff --git a/boost/container/detail/tree.hpp b/boost/container/detail/tree.hpp index 6cd91ed2a6..3ab1536204 100644 --- a/boost/container/detail/tree.hpp +++ b/boost/container/detail/tree.hpp @@ -1,6 +1,6 @@ ////////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2005-2011. Distributed under the Boost +// (C) Copyright Ion Gaztanaga 2005-2012. 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) // @@ -27,7 +27,7 @@ #include <boost/container/detail/destroyers.hpp> #include <boost/container/detail/pair.hpp> #include <boost/container/detail/type_traits.hpp> -#include <boost/container/allocator/allocator_traits.hpp> +#include <boost/container/allocator_traits.hpp> #ifndef BOOST_CONTAINER_PERFECT_FORWARDING #include <boost/container/detail/preprocessor.hpp> #endif @@ -45,7 +45,7 @@ struct value_compare_impl : public KeyCompare { typedef Value value_type; - typedef KeyCompare key_compare; + typedef KeyCompare key_compare; typedef KeyOfValue key_of_value; typedef Key key_type; @@ -90,70 +90,38 @@ struct rbtree_hook >::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_type +struct rbtree_internal_data_type { typedef T type; }; template<class T1, class T2> -struct rbtree_type< std::pair<T1, T2> > +struct rbtree_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 { private: - BOOST_COPYABLE_AND_MOVABLE(rbtree_node) + //BOOST_COPYABLE_AND_MOVABLE(rbtree_node) + rbtree_node(); public: typedef typename rbtree_hook<VoidPointer>::type hook_type; typedef T value_type; - typedef typename rbtree_type<T>::type internal_type; + typedef typename rbtree_internal_data_type<T>::type internal_type; typedef rbtree_node<T, VoidPointer> node_type; - rbtree_node() - : m_data() - {} - - rbtree_node(const rbtree_node &other) - : m_data(other.m_data) - {} - - rbtree_node(BOOST_RV_REF(rbtree_node) other) - : m_data(boost::move(other.m_data)) - {} - - #ifndef BOOST_CONTAINER_PERFECT_FORWARDING - - #define BOOST_PP_LOCAL_MACRO(n) \ - template<BOOST_PP_ENUM_PARAMS(n, class P)> \ - rbtree_node(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ - : m_data(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)) \ - {} \ - //! - #define BOOST_PP_LOCAL_LIMITS (1, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS) - #include BOOST_PP_LOCAL_ITERATE() - - #else //#ifndef BOOST_CONTAINER_PERFECT_FORWARDING - - template<class ...Args> - rbtree_node(Args &&...args) - : m_data(boost::forward<Args>(args)...) - {} - #endif//#ifndef BOOST_CONTAINER_PERFECT_FORWARDING - - rbtree_node &operator=(const rbtree_node &other) - { do_assign(other.m_data); return *this; } - - rbtree_node &operator=(BOOST_RV_REF(rbtree_node) other) - { do_move(other.m_data); return *this; } - T &get_data() { T* ptr = reinterpret_cast<T*>(&this->m_data); @@ -166,7 +134,6 @@ struct rbtree_node return *ptr; } - private: internal_type m_data; template<class A, class B> @@ -188,22 +155,22 @@ struct rbtree_node { m_data = v; } template<class A, class B> - void do_move(std::pair<const A, B> &p) + void do_move_assign(std::pair<const A, B> &p) { - const_cast<A&>(m_data.first) = boost::move(p.first); - m_data.second = boost::move(p.second); + const_cast<A&>(m_data.first) = ::boost::move(p.first); + m_data.second = ::boost::move(p.second); } template<class A, class B> - void do_move(pair<const A, B> &p) + void do_move_assign(pair<const A, B> &p) { - const_cast<A&>(m_data.first) = boost::move(p.first); - m_data.second = boost::move(p.second); + const_cast<A&>(m_data.first) = ::boost::move(p.first); + m_data.second = ::boost::move(p.second); } template<class V> - void do_move(V &v) - { m_data = boost::move(v); } + void do_move_assign(V &v) + { m_data = ::boost::move(v); } }; }//namespace container_detail { @@ -236,13 +203,13 @@ struct intrusive_rbtree_type namespace container_detail { -template <class Key, class Value, class KeyOfValue, +template <class Key, class Value, class KeyOfValue, class KeyCompare, class A> class rbtree : protected container_detail::node_alloc_holder < A , typename container_detail::intrusive_rbtree_type - <A, value_compare_impl<Key, Value, KeyCompare, KeyOfValue> + <A, value_compare_impl<Key, Value, KeyCompare, KeyOfValue> >::type , KeyCompare > @@ -251,7 +218,7 @@ class rbtree < A, value_compare_impl <Key, Value, KeyCompare, KeyOfValue> >::type Icont; - typedef container_detail::node_alloc_holder + typedef container_detail::node_alloc_holder <A, Icont, KeyCompare> AllocHolder; typedef typename AllocHolder::NodePtr NodePtr; typedef rbtree < Key, Value, KeyOfValue @@ -282,7 +249,7 @@ class rbtree //First recycle a node (this can't throw) try{ //This can throw - *p = other; + p->do_assign(other.m_data); return p; } catch(...){ @@ -295,7 +262,7 @@ class rbtree } } else{ - return m_holder.create_node(other); + return m_holder.create_node(other.m_data); } } @@ -319,7 +286,7 @@ class rbtree //First recycle a node (this can't throw) try{ //This can throw - *p = boost::move(other); + p->do_move_assign(const_cast<Node &>(other).m_data); return p; } catch(...){ @@ -332,7 +299,7 @@ class rbtree } } else{ - return m_holder.create_node(other); + return m_holder.create_node(other.m_data); } } @@ -431,17 +398,17 @@ class rbtree {} //Pointer like operators - const_reference operator*() const + const_reference operator*() const { return m_it->get_data(); } - const_pointer operator->() const + const_pointer operator->() const { return const_pointer(&m_it->get_data()); } //Increment / Decrement - const_iterator& operator++() + const_iterator& operator++() { prot_incr(); return *this; } - const_iterator operator++(int) + const_iterator operator++(int) { iiterator tmp = m_it; ++*this; return const_iterator(tmp); } const_iterator& operator--() @@ -465,7 +432,7 @@ class rbtree explicit iterator(iiterator it) : const_iterator(it) {} - + iiterator get() { return this->m_it; } @@ -478,16 +445,18 @@ class rbtree iterator(){} //Pointer like operators - reference operator*() const { return this->m_it->get_data(); } - pointer operator->() const { return pointer(&this->m_it->get_data()); } + reference operator*() const + { return this->m_it->get_data(); } + pointer operator->() const + { return boost::intrusive::pointer_traits<pointer>::pointer_to(this->m_it->get_data()); } //Increment / Decrement - iterator& operator++() + iterator& operator++() { this->prot_incr(); return *this; } iterator operator++(int) { iiterator tmp = this->m_it; ++*this; return iterator(tmp); } - + iterator& operator--() { this->prot_decr(); return *this; } @@ -524,17 +493,36 @@ class rbtree priv_create_and_insert_ordered_nodes(first, last, alloc_version(), ItCat()); } - rbtree(const rbtree& x) + rbtree(const rbtree& x) : AllocHolder(x, x.key_comp()) { 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.key_comp()) + rbtree(BOOST_RV_REF(rbtree) x) + : AllocHolder(::boost::move(static_cast<AllocHolder&>(x)), x.key_comp()) {} + rbtree(const rbtree& x, const allocator_type &a) + : AllocHolder(a, x.key_comp()) + { + 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.key_comp()) + { + 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())); + } + } + ~rbtree() {} //AllocHolder clears the tree @@ -552,7 +540,7 @@ class rbtree //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())); + Icont other_tree(::boost::move(this->icont())); //Now recreate the source tree reusing nodes stored by other_tree this->icont().clone_from @@ -578,7 +566,7 @@ class rbtree if(this_alloc == x_alloc){ //Destroy and swap pointers this->clear(); - this->icont() = boost::move(x.icont()); + this->icont() = ::boost::move(x.icont()); //Move allocator if needed this->AllocHolder::move_assign_alloc(x); } @@ -587,7 +575,7 @@ class rbtree //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())); + Icont other_tree(::boost::move(this->icont())); //Now recreate the source tree reusing nodes stored by other_tree this->icont().clone_from @@ -605,18 +593,18 @@ class rbtree return *this; } - public: + public: // accessors: - value_compare value_comp() const + value_compare value_comp() const { return this->icont().value_comp().value_comp(); } - key_compare key_comp() const + key_compare key_comp() const { return this->icont().value_comp().value_comp().key_comp(); } - allocator_type get_allocator() const + allocator_type get_allocator() const { return allocator_type(this->node_alloc()); } - const stored_allocator_type &get_stored_allocator() const + const stored_allocator_type &get_stored_allocator() const { return this->node_alloc(); } stored_allocator_type &get_stored_allocator() @@ -647,46 +635,46 @@ class rbtree { return this->crend(); } //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - const_iterator cbegin() const + const_iterator cbegin() const { return const_iterator(this->non_const_icont().begin()); } //! <b>Effects</b>: Returns a const_iterator to the end of the container. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - const_iterator cend() const + const_iterator cend() const { return const_iterator(this->non_const_icont().end()); } - //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning - //! of the reversed container. - //! + //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning + //! of the reversed container. + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - const_reverse_iterator crbegin() const - { return const_reverse_iterator(cend()); } + const_reverse_iterator crbegin() const + { return const_reverse_iterator(cend()); } //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end - //! of the reversed container. - //! + //! of the reversed container. + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - const_reverse_iterator crend() const + const_reverse_iterator crend() const { return const_reverse_iterator(cbegin()); } - bool empty() const + bool empty() const { return !this->size(); } - size_type size() const + size_type size() const { return this->icont().size(); } - size_type max_size() const + size_type max_size() const { return AllocHolder::max_size(); } void swap(ThisType& x) @@ -700,7 +688,7 @@ class rbtree std::pair<iterator,bool> insert_unique_check (const key_type& key, insert_commit_data &data) { - std::pair<iiterator, bool> ret = + std::pair<iiterator, bool> ret = this->icont().insert_unique_check(key, KeyNodeCompare(value_comp()), data); return std::pair<iterator, bool>(iterator(ret.first), ret.second); } @@ -708,7 +696,7 @@ class rbtree std::pair<iterator,bool> insert_unique_check (const_iterator hint, const key_type& key, insert_commit_data &data) { - std::pair<iiterator, bool> ret = + std::pair<iiterator, bool> ret = this->icont().insert_unique_check(hint.get(), key, KeyNodeCompare(value_comp()), data); return std::pair<iterator, bool>(iterator(ret.first), ret.second); } @@ -757,12 +745,14 @@ class rbtree { value_type &v = p->get_data(); insert_commit_data data; + scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(p, this->node_alloc()); std::pair<iterator,bool> ret = this->insert_unique_check(KeyOfValue()(v), data); if(!ret.second){ - Destroyer(this->node_alloc())(p); return ret; } + //No throw insertion part, release rollback + destroy_deallocator.release(); return std::pair<iterator,bool> ( iterator(iiterator(this->icont().insert_unique_commit(*p, data))) , true ); @@ -872,9 +862,9 @@ class rbtree if(this->empty()){ //Insert with end hint, to achieve linear //complexity if [first, last) is ordered - const_iterator end(this->end()); + const_iterator hint(this->cend()); for( ; first != last; ++first) - this->insert_unique(end, *first); + hint = this->insert_unique(hint, *first); } else{ for( ; first != last; ++first) @@ -913,9 +903,9 @@ class rbtree { //Insert with end hint, to achieve linear //complexity if [first, last) is ordered - const_iterator end(this->cend()); + const_iterator hint(this->cend()); for( ; first != last; ++first) - this->insert_equal(end, *first); + hint = this->insert_equal(hint, *first); } iterator erase(const_iterator position) @@ -927,7 +917,7 @@ class rbtree iterator erase(const_iterator first, const_iterator last) { return iterator(AllocHolder::erase_range(first.get(), last.get(), alloc_version())); } - void clear() + void clear() { AllocHolder::clear(alloc_version()); } // set operations: @@ -953,14 +943,14 @@ class rbtree { return const_iterator(this->non_const_icont().upper_bound(k, KeyNodeCompare(value_comp()))); } std::pair<iterator,iterator> equal_range(const key_type& k) - { + { std::pair<iiterator, iiterator> ret = this->icont().equal_range(k, KeyNodeCompare(value_comp())); return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second)); } std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const - { + { std::pair<iiterator, iiterator> ret = this->non_const_icont().equal_range(k, KeyNodeCompare(value_comp())); return std::pair<const_iterator,const_iterator> @@ -1072,63 +1062,63 @@ class rbtree } }; -template <class Key, class Value, class KeyOfValue, +template <class Key, class Value, class KeyOfValue, class KeyCompare, class A> -inline bool -operator==(const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x, +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, +template <class Key, class Value, class KeyOfValue, class KeyCompare, class A> -inline bool -operator<(const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x, +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(), + return std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); } -template <class Key, class Value, class KeyOfValue, +template <class Key, class Value, class KeyOfValue, class KeyCompare, class A> -inline bool -operator!=(const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x, +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, +template <class Key, class Value, class KeyOfValue, class KeyCompare, class A> -inline bool -operator>(const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x, +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, +template <class Key, class Value, class KeyOfValue, class KeyCompare, class A> -inline bool -operator<=(const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x, +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, +template <class Key, class Value, class KeyOfValue, class KeyCompare, class A> -inline bool -operator>=(const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x, +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, +template <class Key, class Value, class KeyOfValue, class KeyCompare, class A> -inline void -swap(rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x, +inline void +swap(rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x, rbtree<Key,Value,KeyOfValue,KeyCompare,A>& y) { x.swap(y); @@ -1139,7 +1129,7 @@ swap(rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x, /* //!has_trivial_destructor_after_move<> == true_type //!specialization for optimizations -template <class K, class V, class KOV, +template <class K, class V, class KOV, class C, class A> struct has_trivial_destructor_after_move <boost::container::container_detail::rbtree<K, V, KOV, C, A> > |