From: igaztanaga_at_[hidden]
Date: 2008-05-23 18:32:56
Author: igaztanaga
Date: 2008-05-23 18:32:55 EDT (Fri, 23 May 2008)
New Revision: 45696
URL: http://svn.boost.org/trac/boost/changeset/45696
Log:
#1912: some copy edits on boost.intrusive
#1932: move semantics for shared objects
#1635: Incomplete include guard in boost/intrusive
Text files modified:
trunk/boost/intrusive/detail/utilities.hpp | 6 +
trunk/boost/intrusive/hashtable.hpp | 2
trunk/boost/intrusive/list.hpp | 37 +++++++++++++-
trunk/boost/intrusive/slist.hpp | 102 +++++++++++++++++++++++++++++++++------
trunk/boost/intrusive/unordered_set.hpp | 4
5 files changed, 127 insertions(+), 24 deletions(-)
Modified: trunk/boost/intrusive/detail/utilities.hpp
==============================================================================
--- trunk/boost/intrusive/detail/utilities.hpp (original)
+++ trunk/boost/intrusive/detail/utilities.hpp 2008-05-23 18:32:55 EDT (Fri, 23 May 2008)
@@ -391,7 +391,11 @@
template<class Hook>
void destructor_impl(Hook &hook, detail::link_dispatch<safe_link>)
-{ (void)hook; BOOST_INTRUSIVE_SAFE_HOOK_DESTRUCTOR_ASSERT(!hook.is_linked()); }
+{ //If this assertion raises, you might have destroyed an object
+ //while it was still inserted in a container that is alive.
+ //If so, remove the object from the container before destroying it.
+ (void)hook; BOOST_INTRUSIVE_SAFE_HOOK_DESTRUCTOR_ASSERT(!hook.is_linked());
+}
template<class Hook>
void destructor_impl(Hook &hook, detail::link_dispatch<auto_unlink>)
Modified: trunk/boost/intrusive/hashtable.hpp
==============================================================================
--- trunk/boost/intrusive/hashtable.hpp (original)
+++ trunk/boost/intrusive/hashtable.hpp 2008-05-23 18:32:55 EDT (Fri, 23 May 2008)
@@ -343,7 +343,7 @@
//! is used to construct intrusive unordered_set and unordered_multiset containers. The
//! no-throw guarantee holds only, if the Equal object and Hasher don't throw.
//!
-//! hashtable is a pseudo-intrusive container: each object to be stored in the
+//! hashtable is a semi-intrusive container: each object to be stored in the
//! container must contain a proper hook, but the container also needs
//! additional auxiliary memory to work: hashtable needs a pointer to an array
//! of type `bucket_type` to be passed in the constructor. This bucket array must
Modified: trunk/boost/intrusive/list.hpp
==============================================================================
--- trunk/boost/intrusive/list.hpp (original)
+++ trunk/boost/intrusive/list.hpp 2008-05-23 18:32:55 EDT (Fri, 23 May 2008)
@@ -586,7 +586,7 @@
iterator erase(iterator i)
{ return this->erase_and_dispose(i, detail::null_disposer()); }
- //! <b>Requires</b>: first and last must be valid iterator to elements in *this.
+ //! <b>Requires</b>: b and e must be valid iterators to elements in *this.
//!
//! <b>Effects</b>: Erases the element range pointed by b and e
//! No destructors are called.
@@ -596,8 +596,8 @@
//!
//! <b>Throws</b>: Nothing.
//!
- //! <b>Complexity</b>: Linear to the number of elements erased if it's a safe-mode
- //! or auto-unlink value. Constant time otherwise.
+ //! <b>Complexity</b>: Linear to the number of erased elements if it's a safe-mode
+ //! or auto-unlink value, or constant-time size is enabled. Constant-time otherwise.
//!
//! <b>Note</b>: Invalidates the iterators (but not the references) to the
//! erased elements.
@@ -612,6 +612,37 @@
}
}
+ //! <b>Requires</b>: b and e must be valid iterators to elements in *this.
+ //! n must be std::distance(b, e).
+ //!
+ //! <b>Effects</b>: Erases the element range pointed by b and e
+ //! No destructors are called.
+ //!
+ //! <b>Returns</b>: the first element remaining beyond the removed elements,
+ //! or end() if no such element exists.
+ //!
+ //! <b>Throws</b>: Nothing.
+ //!
+ //! <b>Complexity</b>: Linear to the number of erased elements if it's a safe-mode
+ //! or auto-unlink value is enabled. Constant-time otherwise.
+ //!
+ //! <b>Note</b>: Invalidates the iterators (but not the references) to the
+ //! erased elements.
+ iterator erase(iterator b, iterator e, difference_type n)
+ {
+ BOOST_INTRUSIVE_INVARIANT_ASSERT(std::distance(b, e) == difference_type(n));
+ if(safemode_or_autounlink || constant_time_size){
+ return this->erase_and_dispose(b, e, detail::null_disposer());
+ }
+ else{
+ if(constant_time_size){
+ this->priv_size_traits().set_size(this->priv_size_traits().get_size() - n);
+ }
+ node_algorithms::unlink(b.pointed_node(), e.pointed_node());
+ return e;
+ }
+ }
+
//! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
//!
//! <b>Effects</b>: Erases the element pointed by i of the list.
Modified: trunk/boost/intrusive/slist.hpp
==============================================================================
--- trunk/boost/intrusive/slist.hpp (original)
+++ trunk/boost/intrusive/slist.hpp 2008-05-23 18:32:55 EDT (Fri, 23 May 2008)
@@ -778,12 +778,64 @@
//!
//! <b>Throws</b>: Nothing.
//!
- //! <b>Complexity</b>: Lineal to the elements (last - before_first + 1).
+ //! <b>Complexity</b>: Linear to the number of erased elements if it's a safe-mode
+ //! , auto-unlink value or constant-time size is activated. Constant time otherwise.
//!
//! <b>Note</b>: Invalidates the iterators (but not the references) to the
//! erased element.
iterator erase_after(iterator before_first, iterator last)
- { return this->erase_after_and_dispose(before_first, last, detail::null_disposer()); }
+ {
+ if(safemode_or_autounlink || constant_time_size){
+ return this->erase_after_and_dispose(before_first, last, detail::null_disposer());
+ }
+ else{
+ node_ptr bfp = before_first.pointed_node();
+ node_ptr lp = last.pointed_node();
+ if(cache_last){
+ if((lp == this->get_end_node())){
+ this->set_last_node(bfp);
+ }
+ }
+ node_algorithms::unlink_after(bfp, lp);
+ return last;
+ }
+ }
+
+ //! <b>Effects</b>: Erases the range (before_first, last) from
+ //! the list. n must be std::distance(before_first, last) - 1.
+ //! No destructors are called.
+ //!
+ //! <b>Returns</b>: the first element remaining beyond the removed elements,
+ //! or end() if no such element exists.
+ //!
+ //! <b>Throws</b>: Nothing.
+ //!
+ //! <b>Complexity</b>: constant-time if link_mode is normal_link.
+ //! Linear to the elements (last - before_first) otherwise.
+ //!
+ //! <b>Note</b>: Invalidates the iterators (but not the references) to the
+ //! erased element.
+ iterator erase_after(iterator before_first, iterator last, difference_type n)
+ {
+ BOOST_INTRUSIVE_INVARIANT_ASSERT(std::distance(++iterator(before_first), last) == difference_type(n));
+ if(safemode_or_autounlink){
+ return this->erase_after(before_first, last);
+ }
+ else{
+ node_ptr bfp = before_first.pointed_node();
+ node_ptr lp = last.pointed_node();
+ if(cache_last){
+ if((lp == this->get_end_node())){
+ this->set_last_node(bfp);
+ }
+ }
+ node_algorithms::unlink_after(bfp, lp);
+ if(constant_time_size){
+ this->priv_size_traits().set_size(this->priv_size_traits().get_size() - n);
+ }
+ return last;
+ }
+ }
//! <b>Effects</b>: Erases the element pointed by i of the list.
//! No destructors are called.
@@ -810,14 +862,30 @@
//!
//! <b>Throws</b>: Nothing.
//!
- //! <b>Complexity</b>: Linear to the number of elements erased plus linear
- //! to the elements before first.
+ //! <b>Complexity</b>: Linear to the elements before last.
//!
//! <b>Note</b>: Invalidates the iterators (but not the references) to the
//! erased elements.
iterator erase(iterator first, iterator last)
{ return this->erase_after(this->previous(first), last); }
+ //! <b>Effects</b>: Erases the range [first, last) from
+ //! the list. n must be std::distance(first, last).
+ //! No destructors are called.
+ //!
+ //! <b>Returns</b>: the first element remaining beyond the removed elements,
+ //! or end() if no such element exists.
+ //!
+ //! <b>Throws</b>: Nothing.
+ //!
+ //! <b>Complexity</b>: linear to the elements before first if link_mode is normal_link
+ //! and constant_time_size is activated. Linear to the elements before last otherwise.
+ //!
+ //! <b>Note</b>: Invalidates the iterators (but not the references) to the
+ //! erased element.
+ iterator erase(iterator first, iterator last, difference_type n)
+ { return this->erase_after(this->previous(first), last, n); }
+
//! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
//!
//! <b>Effects</b>: Erases the element after the element pointed by prev of
@@ -885,7 +953,7 @@
//!
//! <b>Throws</b>: Nothing.
//!
- //! <b>Complexity</b>: Lineal to the elements (last - before_first).
+ //! <b>Complexity</b>: Lineal to the elements (last - before_first + 1).
//!
//! <b>Note</b>: Invalidates the iterators to the erased element.
template<class Disposer>
@@ -939,7 +1007,7 @@
//!
//! <b>Throws</b>: Nothing.
//!
- //! <b>Complexity</b>: Linear to the number of elements erased plus linear
+ //! <b>Complexity</b>: Linear to the number of erased elements plus linear
//! to the elements before first.
//!
//! <b>Note</b>: Invalidates the iterators (but not the references) to the
@@ -1047,10 +1115,7 @@
void splice_after(iterator prev_pos, slist_impl &x, iterator prev_ele)
{
iterator elem = prev_ele;
- ++elem;
- if (elem != prev_pos && prev_ele != prev_pos){
- this->splice_after(prev_pos, x, prev_ele, elem, 1);
- }
+ this->splice_after(prev_pos, x, prev_ele, ++elem, 1);
}
//! <b>Requires</b>: prev_pos must be a dereferenceable iterator in *this or be
@@ -1588,15 +1653,18 @@
private:
void priv_splice_after(node_ptr prev_pos_n, slist_impl &x, node_ptr before_first_n, node_ptr before_last_n)
{
- if(cache_last){
- if(node_traits::get_next(prev_pos_n) == this->get_end_node()){
- this->set_last_node(before_last_n);
- }
- if(node_traits::get_next(before_last_n) == x.get_end_node()){
- x.set_last_node(before_first_n);
+ if (before_first_n != before_last_n && prev_pos_n != before_first_n && prev_pos_n != before_last_n)
+ {
+ if(cache_last){
+ if(node_traits::get_next(prev_pos_n) == this->get_end_node()){
+ this->set_last_node(before_last_n);
+ }
+ if(node_traits::get_next(before_last_n) == x.get_end_node()){
+ x.set_last_node(before_first_n);
+ }
}
+ node_algorithms::transfer_after(prev_pos_n, before_first_n, before_last_n);
}
- node_algorithms::transfer_after(prev_pos_n, before_first_n, before_last_n);
}
void priv_reverse(detail::bool_<false>)
Modified: trunk/boost/intrusive/unordered_set.hpp
==============================================================================
--- trunk/boost/intrusive/unordered_set.hpp (original)
+++ trunk/boost/intrusive/unordered_set.hpp 2008-05-23 18:32:55 EDT (Fri, 23 May 2008)
@@ -24,7 +24,7 @@
//! The class template unordered_set is an intrusive container, that mimics most of
//! the interface of std::tr1::unordered_set as described in the C++ TR1.
//!
-//! unordered_set is a pseudo-intrusive container: each object to be stored in the
+//! unordered_set is a semi-intrusive container: each object to be stored in the
//! container must contain a proper hook, but the container also needs
//! additional auxiliary memory to work: unordered_set needs a pointer to an array
//! of type `bucket_type` to be passed in the constructor. This bucket array must
@@ -1019,7 +1019,7 @@
//! The class template unordered_multiset is an intrusive container, that mimics most of
//! the interface of std::tr1::unordered_multiset as described in the C++ TR1.
//!
-//! unordered_multiset is a pseudo-intrusive container: each object to be stored in the
+//! unordered_multiset is a semi-intrusive container: each object to be stored in the
//! container must contain a proper hook, but the container also needs
//! additional auxiliary memory to work: unordered_multiset needs a pointer to an array
//! of type `bucket_type` to be passed in the constructor. This bucket array must