summaryrefslogtreecommitdiff
path: root/boost/container/detail/tree.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'boost/container/detail/tree.hpp')
-rw-r--r--boost/container/detail/tree.hpp254
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> >