Subject: [Boost-commit] svn:boost r52032 - in branches/release/boost/intrusive: . detail
From: igaztanaga_at_[hidden]
Date: 2009-03-28 10:30:56
Author: igaztanaga
Date: 2009-03-28 10:30:54 EDT (Sat, 28 Mar 2009)
New Revision: 52032
URL: http://svn.boost.org/trac/boost/changeset/52032
Log:
Changes for Boost.1.39
Text files modified:
branches/release/boost/intrusive/detail/ebo_functor_holder.hpp | 10 ++--
branches/release/boost/intrusive/detail/mpl.hpp | 2
branches/release/boost/intrusive/detail/parent_from_member.hpp | 3
branches/release/boost/intrusive/detail/tree_node.hpp | 8 +-
branches/release/boost/intrusive/hashtable.hpp | 4 +
branches/release/boost/intrusive/list.hpp | 34 +++++++++------
branches/release/boost/intrusive/rbtree.hpp | 8 +-
branches/release/boost/intrusive/slist.hpp | 83 +++++++++++++++++++++++++--------------
8 files changed, 91 insertions(+), 61 deletions(-)
Modified: branches/release/boost/intrusive/detail/ebo_functor_holder.hpp
==============================================================================
--- branches/release/boost/intrusive/detail/ebo_functor_holder.hpp (original)
+++ branches/release/boost/intrusive/detail/ebo_functor_holder.hpp 2009-03-28 10:30:54 EDT (Sat, 28 Mar 2009)
@@ -26,18 +26,18 @@
ebo_functor_holder_impl()
{}
ebo_functor_holder_impl(const T& t)
- : t(t)
+ : t_(t)
{}
template<class Arg1, class Arg2>
ebo_functor_holder_impl(const Arg1& arg1, const Arg2& arg2)
- : t(arg1, arg2)
+ : t_(arg1, arg2)
{}
- T& get(){return t;}
- const T& get()const{return t;}
+ T& get(){return t_;}
+ const T& get()const{return t_;}
private:
- T t;
+ T t_;
};
template<typename T>
Modified: branches/release/boost/intrusive/detail/mpl.hpp
==============================================================================
--- branches/release/boost/intrusive/detail/mpl.hpp (original)
+++ branches/release/boost/intrusive/detail/mpl.hpp 2009-03-28 10:30:54 EDT (Sat, 28 Mar 2009)
@@ -64,7 +64,7 @@
class false_t { char dummy[2]; };
static true_t dispatch(U);
static false_t dispatch(...);
- static T trigger();
+ static const T &trigger();
public:
static const bool value = sizeof(dispatch(trigger())) == sizeof(true_t);
};
Modified: branches/release/boost/intrusive/detail/parent_from_member.hpp
==============================================================================
--- branches/release/boost/intrusive/detail/parent_from_member.hpp (original)
+++ branches/release/boost/intrusive/detail/parent_from_member.hpp 2009-03-28 10:30:54 EDT (Sat, 28 Mar 2009)
@@ -15,7 +15,8 @@
#include <boost/intrusive/detail/config_begin.hpp>
#include <cstddef>
-#if defined(BOOST_MSVC) || (defined (BOOST_WINDOWS) && defined(BOOST_INTEL))
+#if defined(BOOST_MSVC) || ((defined(_WIN32) || defined(__WIN32__) || defined(WIN32)) && defined(BOOST_INTEL))
+
#define BOOST_INTRUSIVE_MSVC_COMPLIANT_PTR_TO_MEMBER
#include <boost/cstdint.hpp>
#endif
Modified: branches/release/boost/intrusive/detail/tree_node.hpp
==============================================================================
--- branches/release/boost/intrusive/detail/tree_node.hpp (original)
+++ branches/release/boost/intrusive/detail/tree_node.hpp 2009-03-28 10:30:54 EDT (Sat, 28 Mar 2009)
@@ -99,8 +99,8 @@
: members_ (0, 0)
{}
- explicit tree_iterator(node_ptr node, const Container *cont_ptr)
- : members_ (node, cont_ptr)
+ explicit tree_iterator(node_ptr nodeptr, const Container *cont_ptr)
+ : members_ (nodeptr, cont_ptr)
{}
tree_iterator(tree_iterator<Container, false> const& other)
@@ -110,8 +110,8 @@
const node_ptr &pointed_node() const
{ return members_.nodeptr_; }
- tree_iterator &operator=(const node_ptr &node)
- { members_.nodeptr_ = node; return static_cast<tree_iterator&>(*this); }
+ tree_iterator &operator=(const node_ptr &nodeptr)
+ { members_.nodeptr_ = nodeptr; return static_cast<tree_iterator&>(*this); }
public:
tree_iterator& operator++()
Modified: branches/release/boost/intrusive/hashtable.hpp
==============================================================================
--- branches/release/boost/intrusive/hashtable.hpp (original)
+++ branches/release/boost/intrusive/hashtable.hpp 2009-03-28 10:30:54 EDT (Sat, 28 Mar 2009)
@@ -718,6 +718,8 @@
//Constant-time size is incompatible with auto-unlink hooks!
BOOST_STATIC_ASSERT(!(constant_time_size && ((int)real_value_traits::link_mode == (int)auto_unlink)));
+ //Cache begin is incompatible with auto-unlink hooks!
+ BOOST_STATIC_ASSERT(!(cache_begin && ((int)real_value_traits::link_mode == (int)auto_unlink)));
template<class Disposer>
node_cast_adaptor<detail::node_disposer<Disposer, hashtable_impl> >
@@ -871,7 +873,7 @@
//! <b>Effects</b>: Returns true if the container is empty.
//!
- //! <b>Complexity</b>: if constant-time size and cache_last options are disabled,
+ //! <b>Complexity</b>: if constant-time size and cache_begin options are disabled,
//! average constant time (worst case, with empty() == true: O(this->bucket_count()).
//! Otherwise constant.
//!
Modified: branches/release/boost/intrusive/list.hpp
==============================================================================
--- branches/release/boost/intrusive/list.hpp (original)
+++ branches/release/boost/intrusive/list.hpp 2009-03-28 10:30:54 EDT (Sat, 28 Mar 2009)
@@ -978,7 +978,8 @@
carry.splice(carry.cbegin(), *this, this->cbegin());
int i = 0;
while(i < fill && !counter[i].empty()) {
- carry.merge(counter[i++], p);
+ counter[i].merge(carry, p);
+ carry.swap(counter[i++]);
}
carry.swap(counter[i]);
if(i == fill)
@@ -1021,21 +1022,26 @@
template<class Predicate>
void merge(list_impl& x, Predicate p)
{
- const_iterator e(this->end());
- const_iterator bx(x.begin());
- const_iterator ex(x.end());
-
- for (const_iterator b = this->cbegin(); b != e; ++b) {
- size_type n(0);
- const_iterator ix(bx);
- while(ix != ex && p(*ix, *b)){
- ++ix; ++n;
+ const_iterator e(this->cend()), ex(x.cend());
+ const_iterator b(this->cbegin());
+ while(!x.empty()){
+ const_iterator ix(x.cbegin());
+ while (b != e && !p(*ix, *b)){
+ ++b;
+ }
+ if(b == e){
+ //Now transfer the rest to the end of the container
+ this->splice(e, x);
+ break;
+ }
+ else{
+ size_type n(0);
+ do{
+ ++ix; ++n;
+ } while(ix != ex && p(*ix, *b));
+ this->splice(b, x, x.begin(), ix, n);
}
- this->splice(b, x, bx, ix, n);
- bx = ix;
}
- //Now transfer the rest at the end of the container
- this->splice(e, x);
}
//! <b>Effects</b>: Reverses the order of elements in the list.
Modified: branches/release/boost/intrusive/rbtree.hpp
==============================================================================
--- branches/release/boost/intrusive/rbtree.hpp (original)
+++ branches/release/boost/intrusive/rbtree.hpp 2009-03-28 10:30:54 EDT (Sat, 28 Mar 2009)
@@ -513,9 +513,9 @@
template<class Iterator>
void insert_equal(Iterator b, Iterator e)
{
- iterator end(this->end());
+ iterator iend(this->end());
for (; b != e; ++b)
- this->insert_equal(end, *b);
+ this->insert_equal(iend, *b);
}
//! <b>Requires</b>: value must be an lvalue
@@ -579,9 +579,9 @@
void insert_unique(Iterator b, Iterator e)
{
if(this->empty()){
- iterator end(this->end());
+ iterator iend(this->end());
for (; b != e; ++b)
- this->insert_unique(end, *b);
+ this->insert_unique(iend, *b);
}
else{
for (; b != e; ++b)
Modified: branches/release/boost/intrusive/slist.hpp
==============================================================================
--- branches/release/boost/intrusive/slist.hpp (original)
+++ branches/release/boost/intrusive/slist.hpp 2009-03-28 10:30:54 EDT (Sat, 28 Mar 2009)
@@ -598,7 +598,7 @@
void swap(slist_impl& other)
{
if(cache_last){
- this->priv_swap_cache_last(other);
+ priv_swap_cache_last(this, &other);
}
else{
this->priv_swap_lists(this->get_root_node(), other.get_root_node(), detail::bool_<linear>());
@@ -1264,6 +1264,7 @@
carry.splice_after(carry.cbefore_begin(), *this, this->cbefore_begin());
int i = 0;
while(i < fill && !counter[i].empty()) {
+ carry.swap(counter[i]);
last_inserted = carry.merge(counter[i++], p);
}
BOOST_INTRUSIVE_INVARIANT_ASSERT(counter[i].empty());
@@ -1340,24 +1341,26 @@
template<class Predicate>
iterator merge(slist_impl& x, Predicate p)
{
- const_iterator a(cbefore_begin()), e(cend()), ax(x.cbefore_begin()), ex(x.cend());
- const_iterator last_inserted(e);
- const_iterator a_next;
- while(++(a_next = a) != e && !x.empty()) {
- const_iterator ix(ax);
- const_iterator cx;
- size_type n(0);
- while(++(cx = ix) != ex && p(*cx, *a_next)){
- ++ix; ++n;
+ const_iterator e(this->cend()), ex(x.cend()), bb(this->cbefore_begin()),
+ bb_next, last_inserted(e);
+ while(!x.empty()){
+ const_iterator ibx_next(x.cbefore_begin()), ibx(ibx_next++);
+ while (++(bb_next = bb) != e && !p(*ibx_next, *bb_next)){
+ bb = bb_next;
}
- if(ax != ix){
- this->splice_after(a, x, ax, ix, n);
- last_inserted = ix;
+ if(bb_next == e){
+ //Now transfer the rest to the end of the container
+ last_inserted = this->splice_after(bb, x);
+ break;
+ }
+ else{
+ size_type n(0);
+ do{
+ ibx = ibx_next; ++n;
+ } while(++(ibx_next = ibx) != ex && p(*ibx_next, *bb_next));
+ this->splice_after(bb, x, x.before_begin(), ibx, n);
+ last_inserted = ibx;
}
- a = a_next;
- }
- if (!x.empty()){
- last_inserted = this->splice_after(a, x);
}
return last_inserted.unconst();
}
@@ -1711,22 +1714,40 @@
}
}
- void priv_swap_cache_last(slist_impl &other)
+ static void priv_swap_cache_last(slist_impl *this_impl, slist_impl *other_impl)
{
- node_ptr other_last(other.get_last_node());
- node_ptr this_last(this->get_last_node());
- node_ptr other_bfirst(other.get_root_node());
- node_ptr this_bfirst(this->get_root_node());
- node_algorithms::transfer_after(this_bfirst, other_bfirst, other_last);
- node_algorithms::transfer_after(other_bfirst, other_last != other_bfirst? other_last : this_bfirst, this_last);
- node_ptr tmp(this->get_last_node());
- this->set_last_node(other.get_last_node());
- other.set_last_node(tmp);
- if(this->get_last_node() == other_bfirst){
- this->set_last_node(this_bfirst);
+ bool other_was_empty = false;
+ if(this_impl->empty()){
+ //Check if both are empty or
+ if(other_impl->empty())
+ return;
+ //If this is empty swap pointers
+ slist_impl *tmp = this_impl;
+ this_impl = other_impl;
+ other_impl = tmp;
+ other_was_empty = true;
+ }
+ else{
+ other_was_empty = other_impl->empty();
}
- if(other.get_last_node() == this_bfirst){
- other.set_last_node(other_bfirst);
+
+ //Precondition: this is not empty
+ node_ptr other_old_last(other_impl->get_last_node());
+ node_ptr other_bfirst(other_impl->get_root_node());
+ node_ptr this_bfirst(this_impl->get_root_node());
+ node_ptr this_old_last(this_impl->get_last_node());
+
+ //Move all nodes from this to other's beginning
+ node_algorithms::transfer_after(other_bfirst, this_bfirst, this_old_last);
+ other_impl->set_last_node(this_old_last);
+
+ if(other_was_empty){
+ this_impl->set_last_node(this_bfirst);
+ }
+ else{
+ //Move trailing nodes from other to this
+ node_algorithms::transfer_after(this_bfirst, this_old_last, other_old_last);
+ this_impl->set_last_node(other_old_last);
}
}