Boost-Commit :

Date view	Thread view	Subject view	Author view

From: igaztanaga_at_[hidden]
Date: 2008-01-25 18:07:54

Next message: daniel_james_at_[hidden]: "[Boost-commit] svn:boost r42975 - branches/unordered/trunk/libs/unordered/test/exception"
Previous message: dgregor_at_[hidden]: "[Boost-commit] svn:boost r42973 - branches/release/libs/logic/test"

Author: igaztanaga
Date: 2008-01-25 18:07:51 EST (Fri, 25 Jan 2008)
New Revision: 42974
URL: http://svn.boost.org/trac/boost/changeset/42974

Log:
1)Fixed gcc release mode warnings.
2)Replaced throw with BOOST_RETHROW when BOOST_TRY is used.
3)Fixed issues with singly linked lists

Text files modified:
   trunk/boost/interprocess/allocators/allocator.hpp | 3
   trunk/boost/interprocess/allocators/detail/adaptive_node_pool.hpp | 3
   trunk/boost/interprocess/allocators/detail/allocator_common.hpp | 2
   trunk/boost/interprocess/containers/deque.hpp | 5
   trunk/boost/interprocess/containers/detail/node_alloc_holder.hpp | 5
   trunk/boost/interprocess/containers/slist.hpp | 22
   trunk/boost/interprocess/containers/string.hpp | 2
   trunk/boost/interprocess/containers/vector.hpp | 2
   trunk/boost/interprocess/detail/algorithms.hpp | 2
   trunk/boost/interprocess/detail/managed_open_or_create_impl.hpp | 3
   trunk/boost/interprocess/detail/segment_manager_helper.hpp | 2
   trunk/boost/interprocess/indexes/iunordered_set_index.hpp | 5
   trunk/boost/interprocess/mem_algo/detail/mem_algo_common.hpp | 5
   trunk/boost/interprocess/mem_algo/detail/simple_seq_fit_impl.hpp | 1
   trunk/boost/interprocess/mem_algo/rbtree_best_fit.hpp | 2
   trunk/boost/interprocess/segment_manager.hpp | 13
   trunk/boost/interprocess/smart_ptr/detail/shared_count.hpp | 2
   trunk/boost/intrusive/circular_list_algorithms.hpp | 7
   trunk/boost/intrusive/circular_slist_algorithms.hpp | 269 ++++++++++-----------
   trunk/boost/intrusive/hashtable.hpp | 2
   trunk/boost/intrusive/intrusive_fwd.hpp | 1
   trunk/boost/intrusive/linear_slist_algorithms.hpp | 200 ++++++++--------
   trunk/boost/intrusive/list.hpp | 169 ++++++-------
   trunk/boost/intrusive/options.hpp | 14 +
   trunk/boost/intrusive/slist.hpp | 493 ++++++++++++++++++++++++++++-----------
   trunk/libs/interprocess/test/file_mapping_test.cpp | 10
   trunk/libs/interprocess/test/get_process_id_name.hpp | 5
   trunk/libs/interprocess/test/list_test.hpp | 30 +
   trunk/libs/intrusive/proj/vc7ide/_intrusivelib/_intrusivelib.vcproj | 3
   trunk/libs/intrusive/test/itestvalue.hpp | 12
   trunk/libs/intrusive/test/list_test.cpp | 58 ++++
   trunk/libs/intrusive/test/slist_test.cpp | 227 ++++++++++++++++--
   32 files changed, 1007 insertions(+), 572 deletions(-)

Modified: trunk/boost/interprocess/allocators/allocator.hpp
==============================================================================
--- trunk/boost/interprocess/allocators/allocator.hpp (original)
+++ trunk/boost/interprocess/allocators/allocator.hpp 2008-01-25 18:07:51 EST (Fri, 25 Jan 2008)
@@ -106,6 +106,9 @@
 <typename SegmentManager::
 multiallocation_chain
 , T> multiallocation_chain;
+// typedef typename SegmentManager::
+// multiallocation_chain multiallocation_chain;
+
 /// @endcond

 //!Obtains an allocator that allocates

Modified: trunk/boost/interprocess/allocators/detail/adaptive_node_pool.hpp
==============================================================================
--- trunk/boost/interprocess/allocators/detail/adaptive_node_pool.hpp (original)
+++ trunk/boost/interprocess/allocators/detail/adaptive_node_pool.hpp 2008-01-25 18:07:51 EST (Fri, 25 Jan 2008)
@@ -199,7 +199,6 @@
    //!can throw boost::interprocess::bad_alloc
    void allocate_nodes(multiallocation_chain &nodes, const std::size_t n)
    {
- std::size_t old_node_count = nodes.size();
       try{
          priv_invariants();
          for(std::size_t i = 0; i != n; ++i){
@@ -215,8 +214,6 @@
          this->priv_deallocate_free_chunks(m_max_free_chunks);
          throw;
       }
- //remove me
- assert((n+old_node_count) == (std::size_t)std::distance(nodes.get_it(), multiallocation_iterator()));
       priv_invariants();
    }

Modified: trunk/boost/interprocess/allocators/detail/allocator_common.hpp
==============================================================================
--- trunk/boost/interprocess/allocators/detail/allocator_common.hpp (original)
+++ trunk/boost/interprocess/allocators/detail/allocator_common.hpp 2008-01-25 18:07:51 EST (Fri, 25 Jan 2008)
@@ -174,7 +174,7 @@
       }
       BOOST_CATCH(...){
          this->cached_deallocation(multiallocation_iterator(chain.get_it()));
- throw;
+ BOOST_RETHROW
       }
       BOOST_CATCH_END
    }

Modified: trunk/boost/interprocess/containers/deque.hpp
==============================================================================
--- trunk/boost/interprocess/containers/deque.hpp (original)
+++ trunk/boost/interprocess/containers/deque.hpp 2008-01-25 18:07:51 EST (Fri, 25 Jan 2008)
@@ -1359,9 +1359,9 @@
 size_type new_nodes = (new_elems + this->s_buffer_size() - 1) /
 this->s_buffer_size();
 this->priv_reserve_map_at_front(new_nodes);
- size_type i;
+ size_type i = 1;
 BOOST_TRY {
- for (i = 1; i <= new_nodes; ++i)
+ for (; i <= new_nodes; ++i)
 *(this->members_.m_start.m_node - i) = this->priv_allocate_node();
 }
 BOOST_CATCH(...) {
@@ -1453,6 +1453,7 @@
 for(;first2 != mid2; ++first2){
 detail::get_pointer(&*first2)->~value_type();
 }
+ BOOST_RETHROW
 }
 BOOST_CATCH_END
 }

Modified: trunk/boost/interprocess/containers/detail/node_alloc_holder.hpp
==============================================================================
--- trunk/boost/interprocess/containers/detail/node_alloc_holder.hpp (original)
+++ trunk/boost/interprocess/containers/detail/node_alloc_holder.hpp 2008-01-25 18:07:51 EST (Fri, 25 Jan 2008)
@@ -176,7 +176,7 @@
 BOOST_CATCH(...){
 valueptr->first.~first_type();
 static_cast<hook_type*>(nodeptr)->~hook_type();
- throw;
+ BOOST_RETHROW
 }
 BOOST_CATCH_END
 }
@@ -201,7 +201,7 @@
 BOOST_CATCH(...){
 valueptr->first.~first_type();
 static_cast<hook_type*>(nodeptr)->~hook_type();
- throw;
+ BOOST_RETHROW
 }
 BOOST_CATCH_END
 }
@@ -296,6 +296,7 @@
 this->destroy(p);
 }
 this->node_alloc().deallocate_many(itbeg);
+ BOOST_RETHROW
 }
 BOOST_CATCH_END
 return beg;

Modified: trunk/boost/interprocess/containers/slist.hpp
==============================================================================
--- trunk/boost/interprocess/containers/slist.hpp (original)
+++ trunk/boost/interprocess/containers/slist.hpp 2008-01-25 18:07:51 EST (Fri, 25 Jan 2008)
@@ -347,7 +347,7 @@
 slist(InpIt first, InpIt last,
 const allocator_type& a = allocator_type())
 : AllocHolder(a)
- { this->insert_after(this->end_node(), first, last); }
+ { this->insert_after(this->before_begin(), first, last); }

 //! Effects: Copy constructs a list.
 //!
@@ -804,7 +804,7 @@
 //! Complexity: Linear to the difference between size() and new_size.
 void resize(size_type new_size, const T& x)
 {
- typename Icont::iterator end_n(this->icont().end()), cur(end_n), cur_next;
+ typename Icont::iterator end_n(this->icont().end()), cur(this->icont().before_begin()), cur_next;
 while (++(cur_next = cur) != end_n && new_size > 0){
 --new_size;
 cur = cur_next;
@@ -823,7 +823,7 @@
 //! Complexity: Linear to the difference between size() and new_size.
 void resize(size_type new_size)
 {
- typename Icont::iterator end_n(this->icont().end()), cur(end_n), cur_next;
+ typename Icont::iterator end_n(this->icont().end()), cur(this->icont().before_begin()), cur_next;
 size_type len = this->size();
 size_type left = new_size;

@@ -835,7 +835,7 @@
 this->erase_after(iterator(cur), iterator(end_n));
 }
 else{
- this->priv_create_and_insert_nodes(this->end(), new_size - len);
+ this->priv_create_and_insert_nodes(iterator(cur), new_size - len);
 }
 }

@@ -1252,9 +1252,9 @@

 void priv_fill_assign(size_type n, const T& val)
 {
- iterator end_n(end());
- iterator prev(before_begin());
- iterator node(begin());
+ iterator end_n(this->end());
+ iterator prev(this->before_begin());
+ iterator node(this->begin());
 for ( ; node != end_n && n > 0 ; --n){
 *node = val;
 prev = node;
@@ -1274,9 +1274,9 @@
 void priv_assign_dispatch(InpIt first, InpIt last,
 detail::false_)
 {
- iterator end_n(end());
- iterator prev(before_begin());
- iterator node(begin());
+ iterator end_n(this->end());
+ iterator prev(this->before_begin());
+ iterator node(this->begin());
 while (node != end_n && first != last){
 *node = *first;
 prev = node;
@@ -1295,7 +1295,7 @@

 template <class InIter>
 void priv_insert_after_range_dispatch(iterator prev_pos, InIter first, InIter last, detail::false_)
- { return priv_create_and_insert_nodes(prev_pos, first, last); }
+ { this->priv_create_and_insert_nodes(prev_pos, first, last); }

 //Functors for member algorithm defaults
 struct value_less

Modified: trunk/boost/interprocess/containers/string.hpp
==============================================================================
--- trunk/boost/interprocess/containers/string.hpp (original)
+++ trunk/boost/interprocess/containers/string.hpp 2008-01-25 18:07:51 EST (Fri, 25 Jan 2008)
@@ -1684,7 +1684,7 @@
          for (; constructed--; ++dest_init){
             this->destroy(dest_init);
          }
- BOOST_RETHROW;
+ BOOST_RETHROW
       }
       BOOST_CATCH_END
       return (constructed);

Modified: trunk/boost/interprocess/containers/vector.hpp
==============================================================================
--- trunk/boost/interprocess/containers/vector.hpp (original)
+++ trunk/boost/interprocess/containers/vector.hpp 2008-01-25 18:07:51 EST (Fri, 25 Jan 2008)
@@ -731,7 +731,7 @@
 //There is not enough memory, allocate a new
 //buffer or expand the old one.
 bool same_buffer_start;
- size_type real_cap;
+ size_type real_cap = 0;
 std::pair<pointer, bool> ret =
 this->allocation_command
 (allocate_new | expand_fwd | expand_bwd,

Modified: trunk/boost/interprocess/detail/algorithms.hpp
==============================================================================
--- trunk/boost/interprocess/detail/algorithms.hpp (original)
+++ trunk/boost/interprocess/detail/algorithms.hpp 2008-01-25 18:07:51 EST (Fri, 25 Jan 2008)
@@ -92,7 +92,7 @@
       for (; new_count--; ++dest_init){
          detail::get_pointer(&*dest_init)->~value_type();
       }
- BOOST_RETHROW;
+ BOOST_RETHROW
    }
    BOOST_CATCH_END
    return first;

Modified: trunk/boost/interprocess/detail/managed_open_or_create_impl.hpp
==============================================================================
--- trunk/boost/interprocess/detail/managed_open_or_create_impl.hpp (original)
+++ trunk/boost/interprocess/detail/managed_open_or_create_impl.hpp 2008-01-25 18:07:51 EST (Fri, 25 Jan 2008)
@@ -332,7 +332,8 @@

 //If the following throws, we will truncate the file to 1
 mapped_region region(dev, read_write, 0, 0, addr);
- boost::uint32_t *patomic_word = static_cast<boost::uint32_t*>(region.get_address());
+ boost::uint32_t *patomic_word = 0; //avoid gcc warning
+ patomic_word = static_cast<boost::uint32_t*>(region.get_address());
 boost::uint32_t previous = detail::atomic_cas32(patomic_word, InitializingSegment, UninitializedSegment);

 if(previous == UninitializedSegment){

Modified: trunk/boost/interprocess/detail/segment_manager_helper.hpp
==============================================================================
--- trunk/boost/interprocess/detail/segment_manager_helper.hpp (original)
+++ trunk/boost/interprocess/detail/segment_manager_helper.hpp 2008-01-25 18:07:51 EST (Fri, 25 Jan 2008)
@@ -210,7 +210,7 @@
    BOOST_CATCH(...){
       std::size_t destroyed = 0;
       table.destroy_n(mem, constructed, destroyed);
- BOOST_RETHROW;
+ BOOST_RETHROW
    }
    BOOST_CATCH_END
}

Modified: trunk/boost/interprocess/indexes/iunordered_set_index.hpp
==============================================================================
--- trunk/boost/interprocess/indexes/iunordered_set_index.hpp (original)
+++ trunk/boost/interprocess/indexes/iunordered_set_index.hpp 2008-01-25 18:07:51 EST (Fri, 25 Jan 2008)
@@ -289,15 +289,14 @@
       size_type cur_size = this->size();
       size_type cur_count = this->bucket_count();
       bucket_ptr old_p = this->bucket_pointer();
- size_type sug_count;

       if(!this->size() && old_p != bucket_ptr(&this->init_bucket)){
- sug_count = 1;
          this->rehash(bucket_traits(bucket_ptr(&this->init_bucket), 1));
          destroy_buckets(this->alloc, old_p, cur_count);
       }
       else{
- sug_count = index_type::suggested_upper_bucket_count(cur_size);
+ size_type sug_count = 0; //gcc warning
+ sug_count = index_type::suggested_upper_bucket_count(cur_size);

          if(sug_count >= cur_count)
             return;

Modified: trunk/boost/interprocess/mem_algo/detail/mem_algo_common.hpp
==============================================================================
--- trunk/boost/interprocess/mem_algo/detail/mem_algo_common.hpp (original)
+++ trunk/boost/interprocess/mem_algo/detail/mem_algo_common.hpp 2008-01-25 18:07:51 EST (Fri, 25 Jan 2008)
@@ -588,14 +588,15 @@
                if((received_units - total_used_units) >= (elem_units + MemoryAlgorithm::BlockCtrlUnits)){
                   std::size_t shrunk_received;
                   std::size_t shrunk_request = elem_units*Alignment - AllocatedCtrlBytes + UsableByPreviousChunk;
- bool ret = shrink
+ bool shrink_ok = shrink
                         (memory_algo
                         ,memory_algo->priv_get_user_buffer(new_block)
                         ,shrunk_request
                         ,shrunk_request
                         ,shrunk_received);
+ (void)shrink_ok;
                   //Shrink must always succeed with passed parameters
- BOOST_ASSERT(ret);
+ BOOST_ASSERT(shrink_ok);
                   //Some sanity checks
                   BOOST_ASSERT(shrunk_request == shrunk_received);
                   BOOST_ASSERT(elem_units == ((shrunk_request-UsableByPreviousChunk)/Alignment + AllocatedCtrlUnits));

Modified: trunk/boost/interprocess/mem_algo/detail/simple_seq_fit_impl.hpp
==============================================================================
--- trunk/boost/interprocess/mem_algo/detail/simple_seq_fit_impl.hpp (original)
+++ trunk/boost/interprocess/mem_algo/detail/simple_seq_fit_impl.hpp 2008-01-25 18:07:51 EST (Fri, 25 Jan 2008)
@@ -394,6 +394,7 @@

    std::size_t received_size;
    void *addr = priv_check_and_allocate(last_units, prev, last, received_size);
+ (void)addr;
    assert(addr);
    assert(received_size == last_units*Alignment - AllocatedCtrlBytes);

Modified: trunk/boost/interprocess/mem_algo/rbtree_best_fit.hpp
==============================================================================
--- trunk/boost/interprocess/mem_algo/rbtree_best_fit.hpp (original)
+++ trunk/boost/interprocess/mem_algo/rbtree_best_fit.hpp 2008-01-25 18:07:51 EST (Fri, 25 Jan 2008)
@@ -1138,6 +1138,7 @@
 }
 else{
 block_ctrl *prev = priv_prev_block(ptr);
+ (void)prev;
 assert(!priv_is_allocated_block(prev));
 return false;
 }
@@ -1151,6 +1152,7 @@
 assert(first_segment_block->m_prev_allocated);
 block_ctrl *end_block = reinterpret_cast<block_ctrl *>
 (detail::char_ptr_cast(first_segment_block) - first_segment_block->m_prev_size*Alignment);
+ (void)end_block;
 assert(priv_is_allocated_block(end_block));
 assert(end_block > first_segment_block);
 return end_block;

Modified: trunk/boost/interprocess/segment_manager.hpp
==============================================================================
--- trunk/boost/interprocess/segment_manager.hpp (original)
+++ trunk/boost/interprocess/segment_manager.hpp 2008-01-25 18:07:51 EST (Fri, 25 Jan 2008)
@@ -272,7 +272,8 @@

 //Now construct the header
 block_header_t * hdr = new(ptr_struct) block_header_t(block_info);
- void *ptr = hdr->value();
+ void *ptr = 0; //avoid gcc warning
+ ptr = hdr->value();

 //Now call constructors
 detail::array_construct(ptr, num, table);
@@ -1062,7 +1063,7 @@
 //Ignore exceptions
 BOOST_CATCH(...){
 if(dothrow)
- BOOST_RETHROW;
+ BOOST_RETHROW
 return 0;
 }
 BOOST_CATCH_END
@@ -1096,7 +1097,8 @@
 //Now construct the intrusive hook plus the header
 intrusive_value_type * intrusive_hdr = new(buffer_ptr) intrusive_value_type();
 block_header_t * hdr = new(intrusive_hdr->get_block_header())block_header_t(block_info);
- void *ptr = hdr->value();
+ void *ptr = 0; //avoid gcc warning
+ ptr = hdr->value();

 //Copy name to memory segment and insert data
 CharT *name_ptr = static_cast<CharT *>(hdr->template name<CharT>());
@@ -1109,7 +1111,7 @@
 //Ignore exceptions
 BOOST_CATCH(...){
 if(dothrow)
- BOOST_RETHROW;
+ BOOST_RETHROW
 return 0;
 }
 BOOST_CATCH_END
@@ -1235,7 +1237,8 @@
 }

 hdr = new(hdr)block_header_t(block_info);
- void *ptr = hdr->value();
+ void *ptr = 0; //avoid gcc warning
+ ptr = hdr->value();

 //Copy name to memory segment and insert data
 CharT *name_ptr = static_cast<CharT *>(hdr->template name<CharT>());

Modified: trunk/boost/interprocess/smart_ptr/detail/shared_count.hpp
==============================================================================
--- trunk/boost/interprocess/smart_ptr/detail/shared_count.hpp (original)
+++ trunk/boost/interprocess/smart_ptr/detail/shared_count.hpp 2008-01-25 18:07:51 EST (Fri, 25 Jan 2008)
@@ -92,7 +92,7 @@
       }
       BOOST_CATCH (...){
          d(p); // delete p
- throw;
+ BOOST_RETHROW
       }
       BOOST_CATCH_END
    }

Modified: trunk/boost/intrusive/circular_list_algorithms.hpp
==============================================================================
--- trunk/boost/intrusive/circular_list_algorithms.hpp (original)
+++ trunk/boost/intrusive/circular_list_algorithms.hpp 2008-01-25 18:07:51 EST (Fri, 25 Jan 2008)
@@ -154,10 +154,9 @@
    static void unlink(node_ptr b, node_ptr e)
    {
       if (b != e) {
- node_ptr prev(NodeTraits::get_previous(b));
- node_ptr next(NodeTraits::get_next(e));
- NodeTraits::set_previous(next, prev);
- NodeTraits::set_next(prev, next);
+ node_ptr prevb(NodeTraits::get_previous(b));
+ NodeTraits::set_previous(e, prevb);
+ NodeTraits::set_next(prevb, e);
       }
    }

Modified: trunk/boost/intrusive/circular_slist_algorithms.hpp
==============================================================================
--- trunk/boost/intrusive/circular_slist_algorithms.hpp (original)
+++ trunk/boost/intrusive/circular_slist_algorithms.hpp 2008-01-25 18:07:51 EST (Fri, 25 Jan 2008)
@@ -16,6 +16,7 @@

#include <boost/intrusive/detail/config_begin.hpp>
#include <boost/intrusive/intrusive_fwd.hpp>
+#include <boost/intrusive/detail/common_slist_algorithms.hpp>
#include <boost/intrusive/detail/assert.hpp>
#include <cstddef>

@@ -45,22 +46,98 @@
//! <tt>static void set_next(node_ptr n, node_ptr next);</tt>
template<class NodeTraits>
class circular_slist_algorithms
+ /// @cond
+ : public detail::common_slist_algorithms<NodeTraits>
+ /// @endcond
{
+ /// @cond
+ typedef detail::common_slist_algorithms<NodeTraits> base_t;
+ /// @endcond
 public:
 typedef typename NodeTraits::node_ptr node_ptr;
 typedef typename NodeTraits::const_node_ptr const_node_ptr;
 typedef NodeTraits node_traits;

+ #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
+
+ //! Effects: Constructs an non-used list element, putting the next
+ //! pointer to null:
+ //! <tt>NodeTraits::get_next(this_node) == 0
+ //!
+ //! Complexity: Constant
+ //!
+ //! Throws: Nothing.
+ static void init(node_ptr this_node);
+
 //! Requires: this_node must be in a circular list or be an empty circular list.
 //!
- //! Effects: Returns the previous node of this_node in the circular list.
+ //! Effects: Returns true is "this_node" is the only node of a circular list:
+ //! or it's a not inserted node:
+ //! <tt>return !NodeTraits::get_next(this_node) || NodeTraits::get_next(this_node) == this_node</tt>
 //!
- //! Complexity: Linear to the number of elements in the circular list.
+ //! Complexity: Constant
 //!
 //! Throws: Nothing.
- static node_ptr get_previous_node(node_ptr this_node)
- { return get_previous_node(this_node, this_node); }
+ static bool unique(const_node_ptr this_node);
+
+ //! Effects: Returns true is "this_node" has the same state as
+ //! if it was inited using "init(node_ptr)"
+ //!
+ //! Complexity: Constant
+ //!
+ //! Throws: Nothing.
+ static bool inited(const_node_ptr this_node);
+
+ //! Requires: prev_node must be in a circular list or be an empty circular list.
+ //!
+ //! Effects: Unlinks the next node of prev_node from the circular list.
+ //!
+ //! Complexity: Constant
+ //!
+ //! Throws: Nothing.
+ static void unlink_after(node_ptr prev_node);
+
+ //! Requires: prev_node and last_node must be in a circular list
+ //! or be an empty circular list.
+ //!
+ //! Effects: Unlinks the range (prev_node, last_node) from the circular list.
+ //!
+ //! Complexity: Constant
+ //!
+ //! Throws: Nothing.
+ static void unlink_after(node_ptr prev_node, node_ptr last_node);
+
+ //! Requires: prev_node must be a node of a circular list.
+ //!
+ //! Effects: Links this_node after prev_node in the circular list.
+ //!
+ //! Complexity: Constant
+ //!
+ //! Throws: Nothing.
+ static void link_after(node_ptr prev_node, node_ptr this_node);
+
+ //! Requires: b and e must be nodes of the same circular list or an empty range.
+ //! and p must be a node of a different circular list.
+ //!
+ //! Effects: Removes the nodes from (b, e] range from their circular list and inserts
+ //! them after p in p's circular list.
+ //!
+ //! Complexity: Constant
+ //!
+ //! Throws: Nothing.
+ static void transfer_after(node_ptr p, node_ptr b, node_ptr e);
+
+ #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED

+ //! Effects: Constructs an empty list, making this_node the only
+ //! node of the circular list:
+ //! <tt>NodeTraits::get_next(this_node) == this_node</tt>.
+ //!
+ //! Complexity: Constant
+ //!
+ //! Throws: Nothing.
+ static void init_header(node_ptr this_node)
+ { NodeTraits::set_next(this_node, this_node); }

 //! Requires: this_node and prev_init_node must be in the same circular list.
 //!
@@ -72,17 +149,17 @@
 //!
 //! Throws: Nothing.
 static node_ptr get_previous_node(node_ptr prev_init_node, node_ptr this_node)
- {
- node_ptr p = prev_init_node;
- for( node_ptr p_next
- ; this_node != (p_next = NodeTraits::get_next(p))
- ; p = p_next){
- //Logic error: possible use of linear lists with
- //operations only permitted with circular lists
- BOOST_INTRUSIVE_INVARIANT_ASSERT(p);
- }
- return p;
- }
+ { return base_t::get_previous_node(prev_init_node, this_node); }
+
+ //! Requires: this_node must be in a circular list or be an empty circular list.
+ //!
+ //! Effects: Returns the previous node of this_node in the circular list.
+ //!
+ //! Complexity: Linear to the number of elements in the circular list.
+ //!
+ //! Throws: Nothing.
+ static node_ptr get_previous_node(node_ptr this_node)
+ { return base_t::get_previous_node(this_node, this_node); }

 //! Requires: this_node must be in a circular list or be an empty circular list.
 //!
@@ -116,49 +193,6 @@
 return p;
 }

- //! Effects: Constructs an empty list, making this_node the only
- //! node of the circular list:
- //! <tt>NodeTraits::get_next(this_node) == this_node</tt>.
- //!
- //! Complexity: Constant
- //!
- //! Throws: Nothing.
- static void init_header(node_ptr this_node)
- { NodeTraits::set_next(this_node, this_node); }
-
- //! Effects: Constructs an non-used list element, putting the next
- //! pointer to null:
- //! <tt>NodeTraits::get_next(this_node) == 0
- //!
- //! Complexity: Constant
- //!
- //! Throws: Nothing.
- static void init(node_ptr this_node)
- { NodeTraits::set_next(this_node, 0); }
-
- //! Requires: this_node must be in a circular list or be an empty circular list.
- //!
- //! Effects: Returns true is "this_node" is the only node of a circular list:
- //! or it's a not inserted node:
- //! <tt>return !NodeTraits::get_next(this_node) || NodeTraits::get_next(this_node) == this_node</tt> or
- //!
- //! Complexity: Constant
- //!
- //! Throws: Nothing.
- static bool unique(const_node_ptr this_node)
- {
- node_ptr next = NodeTraits::get_next(this_node);
- return !next || next == this_node;
- }
-
- //! Effects: Returns true is "this_node" has the same state as if it was inited using "init(node_ptr)"
- //!
- //! Complexity: Constant
- //!
- //! Throws: Nothing.
- static bool inited(const_node_ptr this_node)
- { return !NodeTraits::get_next(this_node); }
-
 //! Requires: this_node must be in a circular list or be an empty circular list.
 //!
 //! Effects: Returns the number of nodes in a circular list. If the circular list
@@ -178,33 +212,6 @@
 return result;
 }

- //! Requires: prev_node must be in a circular list or be an empty circular list.
- //!
- //! Effects: Unlinks the next node of prev_node from the circular list.
- //!
- //! Complexity: Constant
- //!
- //! Throws: Nothing.
- static void unlink_after(node_ptr prev_node)
- {
- node_ptr this_node(NodeTraits::get_next(prev_node));
- NodeTraits::set_next(prev_node, NodeTraits::get_next(this_node));
- //NodeTraits::set_next(this_node, this_node);
- }
-
- //! Requires: nxt_node must be in a circular list or be an empty circular list.
- //!
- //! Effects: Unlinks the previous node of nxt_node from the circular list.
- //!
- //! Complexity: Linear to the elements in the circular list.
- //!
- //! Throws: Nothing.
- static void unlink_before(node_ptr nxt_node)
- {
- node_ptr prev_to_erase(get_previous_previous_node(nxt_node));
- unlink_after(prev_to_erase);
- }
-
 //! Requires: this_node must be in a circular list, be an empty circular list or be inited.
 //!
 //! Effects: Unlinks the node from the circular list.
@@ -215,20 +222,7 @@
 static void unlink(node_ptr this_node)
 {
 if(NodeTraits::get_next(this_node))
- unlink_after(get_previous_node(this_node));
- }
-
- //! Requires: prev_node must be a node of a circular list.
- //!
- //! Effects: Links this_node after prev_node in the circular list.
- //!
- //! Complexity: Constant
- //!
- //! Throws: Nothing.
- static void link_after(node_ptr prev_node, node_ptr this_node)
- {
- NodeTraits::set_next(this_node, NodeTraits::get_next(prev_node));
- NodeTraits::set_next(prev_node, this_node);
+ base_t::unlink_after(get_previous_node(this_node));
 }

 //! Requires: nxt_node must be a node of a circular list.
@@ -239,7 +233,7 @@
 //!
 //! Throws: Nothing.
 static void link_before (node_ptr nxt_node, node_ptr this_node)
- { link_after(get_previous_node(nxt_node), this_node); }
+ { base_t::link_after(get_previous_node(nxt_node), this_node); }

 //! Requires: this_node and other_node must be nodes inserted
 //! in circular lists or be empty circular lists.
@@ -255,17 +249,17 @@
 {
 if (other_node == this_node)
 return;
- bool this_inited = inited(this_node);
- bool other_inited = inited(other_node);
+ bool this_inited = base_t::inited(this_node);
+ bool other_inited = base_t::inited(other_node);
 if(this_inited){
- init_header(this_node);
+ base_t::init_header(this_node);
 }
 if(other_inited){
- init_header(other_node);
+ base_t::init_header(other_node);
 }

- bool empty1 = unique(this_node);
- bool empty2 = unique(other_node);
+ bool empty1 = base_t::unique(this_node);
+ bool empty2 = base_t::unique(other_node);
 node_ptr prev_this (get_previous_node(this_node));
 node_ptr prev_other(get_previous_node(other_node));

@@ -277,31 +271,10 @@
 NodeTraits::set_next(empty2 ? this_node : prev_other, this_node);

 if(this_inited){
- init(other_node);
+ base_t::init(other_node);
 }
 if(other_inited){
- init(this_node);
- }
- }
-
- //! Requires: b and e must be nodes of the same circular list or an empty range.
- //! and p must be a node of a different circular list.
- //!
- //! Effects: Removes the nodes from (b, e] range from their circular list and inserts
- //! them after p in p's circular list.
- //!
- //! Complexity: Constant
- //!
- //! Throws: Nothing.
- static void transfer_after(node_ptr p, node_ptr b, node_ptr e)
- {
- if (p != b && p != e) {
- node_ptr next_b = NodeTraits::get_next(b);
- node_ptr next_e = NodeTraits::get_next(e);
- node_ptr next_p = NodeTraits::get_next(p);
- NodeTraits::set_next(b, next_e);
- NodeTraits::set_next(e, next_p);
- NodeTraits::set_next(p, next_b);
+ base_t::init(this_node);
 }
 }

@@ -317,24 +290,27 @@
 node_ptr nxt(NodeTraits::get_next(i));
 if (nxt == e)
 break;
- transfer_after(e, i, nxt);
+ base_t::transfer_after(e, i, nxt);
 }
 }

 //! Effects: Moves the node p n positions towards the end of the list.
- //!
+ //!
+ //! Returns: The previous node of p after the function if there has been any movement,
+ //! Null if n leads to no movement.
+ //!
 //! Throws: Nothing.
 //!
 //! Complexity: Linear to the number of elements plus the number moved positions.
- static void move_backwards(node_ptr p, std::size_t n)
+ static node_ptr move_backwards(node_ptr p, std::size_t n)
 {
 //Null shift, nothing to do
- if(!n) return;
+ if(!n) return 0;
 node_ptr first = NodeTraits::get_next(p);

 //count() == 1 or 2, nothing to do
 if(NodeTraits::get_next(first) == p)
- return;
+ return 0;

 bool end_found = false;
 node_ptr new_last(0);
@@ -350,11 +326,11 @@
 //Shortcut the shift with the modulo of the size of the list
 n %= i;
 if(!n)
- return;
+ return 0;
 i = 0;
 //Unlink p and continue the new first node search
 first = NodeTraits::get_next(p);
- unlink_after(new_last);
+ base_t::unlink_after(new_last);
 end_found = true;
 }
 }
@@ -362,26 +338,30 @@
 //If the p has not been found in the previous loop, find it
 //starting in the new first node and unlink it
 if(!end_found){
- unlink_after(get_previous_node(first, p));
+ base_t::unlink_after(base_t::get_previous_node(first, p));
 }

 //Now link p after the new last node
- link_after(new_last, p);
+ base_t::link_after(new_last, p);
+ return new_last;
 }

 //! Effects: Moves the node p n positions towards the beginning of the list.
 //!
+ //! Returns: The previous node of p after the function if there has been any movement,
+ //! Null if n leads equals to no movement.
+ //!
 //! Throws: Nothing.
 //!
 //! Complexity: Linear to the number of elements plus the number moved positions.
- static void move_forward(node_ptr p, std::size_t n)
+ static node_ptr move_forward(node_ptr p, std::size_t n)
 {
 //Null shift, nothing to do
- if(!n) return;
+ if(!n) return 0;
 node_ptr first = node_traits::get_next(p);

 //count() == 1 or 2, nothing to do
- if(node_traits::get_next(first) == p) return;
+ if(node_traits::get_next(first) == p) return 0;

 //Iterate until p is found to know where the current last node is.
 //If the shift count is less than the size of the list, we can also obtain
@@ -400,7 +380,7 @@
 //Shortcut the shift with the modulo of the size of the list
 std::size_t new_before_last_pos = (distance - (n % distance))% distance;
 //If the shift is a multiple of the size there is nothing to do
- if(!new_before_last_pos) return;
+ if(!new_before_last_pos) return 0;

 for( new_last = p
 ; new_before_last_pos--
@@ -410,8 +390,9 @@
 }

 //Now unlink p and link it after the new last node
- unlink_after(old_last);
- link_after(new_last, p);
+ base_t::unlink_after(old_last);
+ base_t::link_after(new_last, p);
+ return new_last;
 }
};

Modified: trunk/boost/intrusive/hashtable.hpp
==============================================================================
--- trunk/boost/intrusive/hashtable.hpp (original)
+++ trunk/boost/intrusive/hashtable.hpp 2008-01-25 18:07:51 EST (Fri, 25 Jan 2008)
@@ -747,7 +747,7 @@
             }
             BOOST_INTRUSIVE_CATCH(...){
                this->clear_and_dispose(disposer);
- BOOST_RETHROW;
+ BOOST_INTRUSIVE_RETHROW;
             }
             BOOST_INTRUSIVE_CATCH_END
          }

Modified: trunk/boost/intrusive/intrusive_fwd.hpp
==============================================================================
--- trunk/boost/intrusive/intrusive_fwd.hpp (original)
+++ trunk/boost/intrusive/intrusive_fwd.hpp 2008-01-25 18:07:51 EST (Fri, 25 Jan 2008)
@@ -70,6 +70,7 @@
    , class O2 = none
    , class O3 = none
    , class O4 = none
+ , class O5 = none
>
class slist;

Modified: trunk/boost/intrusive/linear_slist_algorithms.hpp
==============================================================================
--- trunk/boost/intrusive/linear_slist_algorithms.hpp (original)
+++ trunk/boost/intrusive/linear_slist_algorithms.hpp 2008-01-25 18:07:51 EST (Fri, 25 Jan 2008)
@@ -16,7 +16,9 @@

#include <boost/intrusive/detail/config_begin.hpp>
#include <boost/intrusive/intrusive_fwd.hpp>
+#include <boost/intrusive/detail/common_slist_algorithms.hpp>
#include <cstddef>
+#include <utility>

namespace boost {
namespace intrusive {
@@ -43,76 +45,110 @@
//! <tt>static void set_next(node_ptr n, node_ptr next);</tt>
template<class NodeTraits>
class linear_slist_algorithms
+ /// @cond
+ : public detail::common_slist_algorithms<NodeTraits>
+ /// @endcond
{
+ /// @cond
+ typedef detail::common_slist_algorithms<NodeTraits> base_t;
+ /// @endcond
 public:
 typedef typename NodeTraits::node_ptr node_ptr;
 typedef typename NodeTraits::const_node_ptr const_node_ptr;
 typedef NodeTraits node_traits;

- //! Requires: this_node and prev_init_node must be in the same linear list.
+ #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
+
+ //! Effects: Constructs an non-used list element, putting the next
+ //! pointer to null:
+ //! <tt>NodeTraits::get_next(this_node) == 0
 //!
- //! Effects: Returns the previous node of this_node in the linear list starting.
- //! the search from prev_init_node. The first node checked for equality
- //! is NodeTraits::get_next(prev_init_node).
+ //! Complexity: Constant
 //!
- //! Complexity: Linear to the number of elements between prev_init_node and this_node.
+ //! Throws: Nothing.
+ static void init(node_ptr this_node);
+
+ //! Requires: this_node must be in a circular list or be an empty circular list.
+ //!
+ //! Effects: Returns true is "this_node" is the only node of a circular list:
+ //! or it's a not inserted node:
+ //! <tt>return !NodeTraits::get_next(this_node) || NodeTraits::get_next(this_node) == this_node</tt>
+ //!
+ //! Complexity: Constant
 //!
 //! Throws: Nothing.
- static node_ptr get_previous_node(node_ptr prev_init_node, node_ptr this_node)
- {
- node_ptr p = prev_init_node;
- for( node_ptr p_next
- ; this_node != (p_next = NodeTraits::get_next(p))
- ; p = p_next){
- //empty
- }
- return p;
- }
+ static bool unique(const_node_ptr this_node);

- //! Effects: Constructs an empty list, making this_node the only
- //! node of the linear list:
- //! <tt>NodeTraits::get_next(this_node) == 0.
+ //! Effects: Returns true is "this_node" has the same state as if
+ //! it was inited using "init(node_ptr)"
 //!
 //! Complexity: Constant
 //!
 //! Throws: Nothing.
- static void init_header(node_ptr this_node)
- { NodeTraits::set_next(this_node, 0); }
+ static bool inited(const_node_ptr this_node);

- //! Effects: Constructs an non-used list element, putting the next
- //! pointer to null:
- //! <tt>NodeTraits::get_next(this_node) == 0
+ //! Requires: prev_node must be in a circular list or be an empty circular list.
+ //!
+ //! Effects: Unlinks the next node of prev_node from the circular list.
 //!
 //! Complexity: Constant
 //!
 //! Throws: Nothing.
- static void init(node_ptr this_node)
- { NodeTraits::set_next(this_node, 0); }
+ static void unlink_after(node_ptr prev_node);

- //! Requires: this_node must be in a linear list or be an empty linear list.
+ //! Requires: prev_node and last_node must be in a circular list
+ //! or be an empty circular list.
+ //!
+ //! Effects: Unlinks the range (prev_node, last_node) from the linear list.
+ //!
+ //! Complexity: Constant
+ //!
+ //! Throws: Nothing.
+ static void unlink_after(node_ptr prev_node, node_ptr last_node);
+
+ //! Requires: prev_node must be a node of a linear list.
 //!
- //! Effects: Returns true is "this_node" is the only node of a linear list:
- //! <tt>return NodeTraits::get_next(this_node) == this_node</tt>
+ //! Effects: Links this_node after prev_node in the linear list.
 //!
 //! Complexity: Constant
 //!
 //! Throws: Nothing.
- static bool unique(const_node_ptr this_node)
- {
- node_ptr next = NodeTraits::get_next(this_node);
- return !next || next == this_node;
- }
+ static void link_after(node_ptr prev_node, node_ptr this_node);

- //! Requires: this_node must be in a linear list or be an empty linear list.
+ //! Requires: b and e must be nodes of the same linear list or an empty range.
+ //! and p must be a node of a different linear list.
 //!
- //! Effects: Returns true is "this_node" is the only node of a linear list:
- //! <tt>return NodeTraits::get_next(this_node) == this_node</tt>
+ //! Effects: Removes the nodes from (b, e] range from their linear list and inserts
+ //! them after p in p's linear list.
 //!
 //! Complexity: Constant
 //!
 //! Throws: Nothing.
- static bool inited(const_node_ptr this_node)
- { return !NodeTraits::get_next(this_node); }
+ static void transfer_after(node_ptr p, node_ptr b, node_ptr e);
+
+ #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
+
+ //! Effects: Constructs an empty list, making this_node the only
+ //! node of the circular list:
+ //! <tt>NodeTraits::get_next(this_node) == this_node</tt>.
+ //!
+ //! Complexity: Constant
+ //!
+ //! Throws: Nothing.
+ static void init_header(node_ptr this_node)
+ { NodeTraits::set_next(this_node, 0); }
+
+ //! Requires: this_node and prev_init_node must be in the same linear list.
+ //!
+ //! Effects: Returns the previous node of this_node in the linear list starting.
+ //! the search from prev_init_node. The first node checked for equality
+ //! is NodeTraits::get_next(prev_init_node).
+ //!
+ //! Complexity: Linear to the number of elements between prev_init_node and this_node.
+ //!
+ //! Throws: Nothing.
+ static node_ptr get_previous_node(node_ptr prev_init_node, node_ptr this_node)
+ { return base_t::get_previous_node(prev_init_node, this_node); }

 //! Requires: this_node must be in a linear list or be an empty linear list.
 //!
@@ -133,32 +169,6 @@
 return result;
 }

- //! Requires: prev_node must be in a linear list or be an empty linear list.
- //!
- //! Effects: Unlinks the next node of prev_node from the linear list.
- //!
- //! Complexity: Constant
- //!
- //! Throws: Nothing.
- static void unlink_after(node_ptr prev_node)
- {
- node_ptr this_node(NodeTraits::get_next(prev_node));
- NodeTraits::set_next(prev_node, NodeTraits::get_next(this_node));
- }
-
- //! Requires: prev_node must be a node of a linear list.
- //!
- //! Effects: Links this_node after prev_node in the linear list.
- //!
- //! Complexity: Constant
- //!
- //! Throws: Nothing.
- static void link_after(node_ptr prev_node, node_ptr this_node)
- {
- NodeTraits::set_next(this_node, NodeTraits::get_next(prev_node));
- NodeTraits::set_next(prev_node, this_node);
- }
-
 //! Requires: this_node and other_node must be nodes inserted
 //! in linear lists or be empty linear lists.
 //!
@@ -176,27 +186,6 @@
 NodeTraits::set_next(other_node, this_nxt);
 }

- //! Requires: b and e must be nodes of the same linear list or an empty range.
- //! and p must be a node of a different linear list.
- //!
- //! Effects: Removes the nodes from (b, e] range from their linear list and inserts
- //! them after p in p's linear list.
- //!
- //! Complexity: Constant
- //!
- //! Throws: Nothing.
- static void transfer_after(node_ptr p, node_ptr b, node_ptr e)
- {
- if (p != b && p != e) {
- node_ptr next_b = NodeTraits::get_next(b);
- node_ptr next_e = NodeTraits::get_next(e);
- node_ptr next_p = NodeTraits::get_next(p);
- NodeTraits::set_next(b, next_e);
- NodeTraits::set_next(e, next_p);
- NodeTraits::set_next(p, next_b);
- }
- }
-
 //! Effects: Reverses the order of elements in the list.
 //!
 //! Returns: The new first node of the list.
@@ -211,7 +200,7 @@
 node_ptr first(p);
 while(i){
 node_ptr nxti(NodeTraits::get_next(i));
- unlink_after(p);
+ base_t::unlink_after(p);
 NodeTraits::set_next(i, first);
 first = i;
 i = nxti;
@@ -219,16 +208,21 @@
 return first;
 }

- //! Effects: Moves the node p n positions towards the end of the list.
+ //! Effects: Moves the first n nodes starting at p to the end of the list.
+ //!
+ //! Returns: A pair containing the new first and last node of the list or
+ //! if there has been any movement, a null pair if n leads to no movement.
 //!
 //! Throws: Nothing.
 //!
 //! Complexity: Linear to the number of elements plus the number moved positions.
- static node_ptr move_backwards(node_ptr p, std::size_t n)
+ static std::pair<node_ptr, node_ptr> move_first_n_backwards(node_ptr p, std::size_t n)
 {
+ std::pair<node_ptr, node_ptr> ret(0, 0);
 //Null shift, or count() == 0 or 1, nothing to do
- if(!n || !p || !NodeTraits::get_next(p))
- return p;
+ if(!n || !p || !NodeTraits::get_next(p)){
+ return ret;
+ }

 node_ptr first = p;
 bool end_found = false;
@@ -245,7 +239,7 @@
 if(first == 0){
 //Shortcut the shift with the modulo of the size of the list
 n %= i;
- if(!n) return p;
+ if(!n) return ret;
 old_last = new_last;
 i = 0;
 //Unlink p and continue the new first node search
@@ -258,25 +252,31 @@
 //If the p has not been found in the previous loop, find it
 //starting in the new first node and unlink it
 if(!end_found){
- old_last = get_previous_node(first, 0);
+ old_last = base_t::get_previous_node(first, 0);
 }

 //Now link p after the new last node
 NodeTraits::set_next(old_last, p);
 NodeTraits::set_next(new_last, 0);
- return first;
+ ret.first = first;
+ ret.second = new_last;
+ return ret;
 }

- //! Effects: Moves the node p n positions towards the beginning of the list.
+ //! Effects: Moves the first n nodes starting at p to the beginning of the list.
+ //!
+ //! Returns: A pair containing the new first and last node of the list or
+ //! if there has been any movement, a null pair if n leads to no movement.
 //!
 //! Throws: Nothing.
 //!
 //! Complexity: Linear to the number of elements plus the number moved positions.
- static node_ptr move_forward(node_ptr p, std::size_t n)
+ static std::pair<node_ptr, node_ptr> move_first_n_forward(node_ptr p, std::size_t n)
 {
+ std::pair<node_ptr, node_ptr> ret(0, 0);
 //Null shift, or count() == 0 or 1, nothing to do
 if(!n || !p || !NodeTraits::get_next(p))
- return p;
+ return ret;

 node_ptr first = p;

@@ -298,7 +298,7 @@
 std::size_t new_before_last_pos = (distance - (n % distance))% distance;
 //If the shift is a multiple of the size there is nothing to do
 if(!new_before_last_pos)
- return p;
+ return ret;

 for( new_last = p
 ; --new_before_last_pos
@@ -308,11 +308,13 @@
 }

 //Get the first new node
- node_ptr new_first = node_traits::get_next(new_last);
+ node_ptr new_first(node_traits::get_next(new_last));
 //Now put the old beginning after the old end
 NodeTraits::set_next(old_last, p);
 NodeTraits::set_next(new_last, 0);
- return new_first;
+ ret.first = new_first;
+ ret.second = new_last;
+ return ret;
 }
};

Modified: trunk/boost/intrusive/list.hpp
==============================================================================
--- trunk/boost/intrusive/list.hpp (original)
+++ trunk/boost/intrusive/list.hpp 2008-01-25 18:07:51 EST (Fri, 25 Jan 2008)
@@ -290,14 +290,8 @@
 //! Complexity: Constant.
 //!
 //! Note: Invalidates the iterators (but not the references) to the erased element.
- void pop_back()
- {
- node_ptr to_erase = node_traits::get_previous(this->get_root_node());
- node_algorithms::unlink(to_erase);
- this->priv_size_traits().decrement();
- if(safemode_or_autounlink)
- node_algorithms::init(to_erase);
- }
+ void pop_back()
+ { return this->pop_back_and_dispose(detail::null_disposer()); }

 //! Requires: Disposer::operator()(pointer) shouldn't throw.
 //!
@@ -329,14 +323,8 @@
 //! Complexity: Constant.
 //!
 //! Note: Invalidates the iterators (but not the references) to the erased element.
- void pop_front()
- {
- node_ptr to_erase = node_traits::get_next(this->get_root_node());
- node_algorithms::unlink(to_erase);
- this->priv_size_traits().decrement();
- if(safemode_or_autounlink)
- node_algorithms::init(to_erase);
- }
+ void pop_front()
+ { return this->pop_front_and_dispose(detail::null_disposer()); }

 //! Requires: Disposer::operator()(pointer) shouldn't throw.
 //!
@@ -406,7 +394,7 @@
 //!
 //! Complexity: Constant.
 const_iterator begin() const
- { return cbegin(); }
+ { return this->cbegin(); }

 //! Effects: Returns a const_iterator to the first element contained in the list.
 //!
@@ -430,7 +418,7 @@
 //!
 //! Complexity: Constant.
 const_iterator end() const
- { return cend(); }
+ { return this->cend(); }

 //! Effects: Returns a constant iterator to the end of the list.
 //!
@@ -447,7 +435,7 @@
 //!
 //! Complexity: Constant.
 reverse_iterator rbegin()
- { return reverse_iterator(end()); }
+ { return reverse_iterator(this->end()); }

 //! Effects: Returns a const_reverse_iterator pointing to the beginning
 //! of the reversed list.
@@ -456,7 +444,7 @@
 //!
 //! Complexity: Constant.
 const_reverse_iterator rbegin() const
- { return crbegin(); }
+ { return this->crbegin(); }

 //! Effects: Returns a const_reverse_iterator pointing to the beginning
 //! of the reversed list.
@@ -483,7 +471,7 @@
 //!
 //! Complexity: Constant.
 const_reverse_iterator rend() const
- { return crend(); }
+ { return this->crend(); }

 //! Effects: Returns a const_reverse_iterator pointing to the end
 //! of the reversed list.
@@ -492,7 +480,7 @@
 //!
 //! Complexity: Constant.
 const_reverse_iterator crend() const
- { return const_reverse_iterator(begin()); }
+ { return const_reverse_iterator(this->begin()); }

 //! Precondition: end_iterator must be a valid end iterator
 //! of list.
@@ -503,7 +491,7 @@
 //!
 //! Complexity: Constant.
 static list_impl &container_from_end_iterator(iterator end_iterator)
- { return priv_container_from_end_iterator(end_iterator); }
+ { return list_impl::priv_container_from_end_iterator(end_iterator); }

 //! Precondition: end_iterator must be a valid end const_iterator
 //! of list.
@@ -514,7 +502,7 @@
 //!
 //! Complexity: Constant.
 static const list_impl &container_from_end_iterator(const_iterator end_iterator)
- { return priv_container_from_end_iterator(end_iterator); }
+ { return list_impl::priv_container_from_end_iterator(end_iterator); }

 //! Effects: Returns the number of the elements contained in the list.
 //!
@@ -540,7 +528,7 @@
 //!
 //! Note: Does not affect the validity of iterators and references.
 bool empty() const
- { return node_algorithms::unique(this->get_root_node()); }
+ { return node_algorithms::unique(this->get_root_node()); }

 //! Effects: Swaps the elements of x and *this.
 //!
@@ -596,16 +584,7 @@
 //! Note: Invalidates the iterators (but not the references) to the
 //! erased element.
 iterator erase(iterator i)
- {
- iterator erase = i;
- ++i;
- node_ptr to_erase = erase.pointed_node();
- node_algorithms::unlink(to_erase);
- this->priv_size_traits().decrement();
- if(safemode_or_autounlink)
- node_algorithms::init(to_erase);
- return i;
- }
+ { return this->erase_and_dispose(i, detail::null_disposer()); }

 //! Requires: first and last must be valid iterator to elements in *this.
 //!
@@ -625,10 +604,7 @@
 iterator erase(iterator b, iterator e)
 {
 if(safemode_or_autounlink || constant_time_size){
- while(b != e){
- b = this->erase(b);
- }
- return b;
+ return this->erase_and_dispose(b, e, detail::null_disposer());
 }
 else{
 node_algorithms::unlink(b.pointed_node(), e.pointed_node());
@@ -653,14 +629,13 @@
 template <class Disposer>
 iterator erase_and_dispose(iterator i, Disposer disposer)
 {
- iterator erase = i;
+ node_ptr to_erase(i.pointed_node());
 ++i;
- node_ptr to_erase = erase.pointed_node();
 node_algorithms::unlink(to_erase);
 this->priv_size_traits().decrement();
 if(safemode_or_autounlink)
 node_algorithms::init(to_erase);
- disposer(get_real_value_traits().to_value_ptr(to_erase));
+ disposer(this->get_real_value_traits().to_value_ptr(to_erase));
 return i;
 }

@@ -681,10 +656,17 @@
 template <class Disposer>
 iterator erase_and_dispose(iterator b, iterator e, Disposer disposer)
 {
- while(b != e){
- b = this->erase_and_dispose(b, disposer);
+ node_ptr bp(b.pointed_node()), ep(e.pointed_node());
+ node_algorithms::unlink(bp, ep);
+ while(bp != ep){
+ node_ptr to_erase(bp);
+ bp = node_traits::get_next(bp);
+ if(safemode_or_autounlink)
+ node_algorithms::init(to_erase);
+ disposer(get_real_value_traits().to_value_ptr(to_erase));
+ this->priv_size_traits().decrement();
 }
- return b;
+ return e;
 }

 //! Effects: Erases all the elements of the container.
@@ -699,7 +681,7 @@
 void clear()
 {
 if(safemode_or_autounlink){
- this->erase(this->begin(), this->end());
+ this->clear_and_dispose(detail::null_disposer());
 }
 else{
 node_algorithms::init_header(this->get_root_node());
@@ -720,7 +702,18 @@
 //! Note: Invalidates the iterators to the erased elements.
 template <class Disposer>
 void clear_and_dispose(Disposer disposer)
- { this->erase_and_dispose(this->begin(), this->end(), disposer); }
+ {
+ iterator it(this->begin()), itend(this->end());
+ while(it != itend){
+ node_ptr to_erase(it.pointed_node());
+ ++it;
+ if(safemode_or_autounlink)
+ node_algorithms::init(to_erase);
+ disposer(get_real_value_traits().to_value_ptr(to_erase));
+ }
+ node_algorithms::init_header(this->get_root_node());
+ this->priv_size_traits().set_size(0);
+ }

 //! Requires: Disposer::operator()(pointer) shouldn't throw.
 //!
@@ -765,7 +758,7 @@
 //! Note: Does not affect the validity of iterators and references.
 iterator insert(iterator p, reference value)
 {
- node_ptr to_insert = get_real_value_traits().to_node_ptr(value);
+ node_ptr to_insert = this->get_real_value_traits().to_node_ptr(value);
 if(safemode_or_autounlink)
 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::inited(to_insert));
 node_algorithms::link_before(p.pointed_node(), to_insert);
@@ -894,19 +887,10 @@
 //! list. Iterators of this list and all the references are not invalidated.
 void splice(iterator p, list_impl&x, iterator start, iterator end)
 {
- if(start != end){
- if(constant_time_size){
- size_traits &thist = this->priv_size_traits();
- size_traits &xt = x.priv_size_traits();
- size_type increment = std::distance(start, end);
- node_algorithms::transfer(p.pointed_node(), start.pointed_node(), end.pointed_node());
- thist.set_size(thist.get_size() + increment);
- xt.set_size(xt.get_size() - increment);
- }
- else{
- node_algorithms::transfer(p.pointed_node(), start.pointed_node(), end.pointed_node());
- }
- }
+ if(constant_time_size)
+ this->splice(p, x, start, end, std::distance(start, end));
+ else
+ this->splice(p, x, start, end, 1);//distance is a dummy value
 }

 //! Requires: p must be a valid iterator of *this.
@@ -951,7 +935,7 @@
 //! Complexity: The number of comparisons is approximately N log N, where N
 //! is the list's size.
 void sort()
- { sort(std::less<value_type>()); }
+ { this->sort(std::less<value_type>()); }

 //! Requires: p must be a comparison function that induces a strict weak ordering
 //!
@@ -1004,7 +988,7 @@
 //!
 //! Note: Iterators and references are not invalidated
 void merge(list_impl& x)
- { merge(x, std::less<value_type>()); }
+ { this->merge(x, std::less<value_type>()); }

 //! Requires: p must be a comparison function that induces a strict weak
 //! ordering and both *this and x must be sorted according to that ordering
@@ -1023,9 +1007,9 @@
 template<class Predicate>
 void merge(list_impl& x, Predicate p)
 {
- iterator e = this->end();
- iterator bx = x.begin();
- iterator ex = x.end();
+ iterator e(this->end());
+ iterator bx(x.begin());
+ iterator ex(x.end());

 for (iterator b = this->begin(); b != e; ++b) {
 size_type n(0);
@@ -1060,7 +1044,7 @@
 //! Note: The relative order of elements that are not removed is unchanged,
 //! and iterators to elements that are not removed remain valid.
 void remove(const_reference value)
- { remove_if(detail::equal_to_value<const_reference>(value)); }
+ { this->remove_if(detail::equal_to_value<const_reference>(value)); }

 //! Requires: Disposer::operator()(pointer) shouldn't throw.
 //!
@@ -1075,7 +1059,7 @@
 //! and iterators to elements that are not removed remain valid.
 template<class Disposer>
 void remove_and_dispose(const_reference value, Disposer disposer)
- { remove_and_dispose_if(detail::equal_to_value<const_reference>(value), disposer); }
+ { this->remove_and_dispose_if(detail::equal_to_value<const_reference>(value), disposer); }

 //! Effects: Removes all the elements for which a specified
 //! predicate is satisfied. No destructors are called.
@@ -1088,7 +1072,7 @@
 //! and iterators to elements that are not removed remain valid.
 template<class Pred>
 void remove_if(Pred pred)
- { remove_and_dispose_if(pred, detail::null_disposer()); }
+ { this->remove_and_dispose_if(pred, detail::null_disposer()); }

 //! Requires: Disposer::operator()(pointer) shouldn't throw.
 //!
@@ -1105,17 +1089,15 @@
 template<class Pred, class Disposer>
 void remove_and_dispose_if(Pred pred, Disposer disposer)
 {
- iterator first = begin();
- iterator last = end();
- while(first != last) {
- iterator next = first;
- ++next;
- if(pred(*first)){
- pointer p = first.operator->();
- this->erase(first);
- disposer(p);
+ iterator cur(this->begin());
+ iterator last(this->end());
+ while(cur != last) {
+ if(pred(*cur)){
+ cur = this->erase_and_dispose(cur, disposer);
+ }
+ else{
+ ++cur;
 }
- first = next;
 }
 }

@@ -1129,7 +1111,7 @@
 //! Note: The relative order of elements that are not removed is unchanged,
 //! and iterators to elements that are not removed remain valid.
 void unique()
- { unique_and_dispose(std::equal_to<value_type>(), detail::null_disposer()); }
+ { this->unique_and_dispose(std::equal_to<value_type>(), detail::null_disposer()); }

 //! Effects: Removes adjacent duplicate elements or adjacent
 //! elements that satisfy some binary predicate from the list.
@@ -1143,7 +1125,7 @@
 //! and iterators to elements that are not removed remain valid.
 template<class BinaryPredicate>
 void unique(BinaryPredicate pred)
- { unique_and_dispose(pred, detail::null_disposer()); }
+ { this->unique_and_dispose(pred, detail::null_disposer()); }

 //! Requires: Disposer::operator()(pointer) shouldn't throw.
 //!
@@ -1159,7 +1141,7 @@
 //! and iterators to elements that are not removed remain valid.
 template<class Disposer>
 void unique_and_dispose(Disposer disposer)
- { unique_and_dispose(std::equal_to<value_type>(), disposer); }
+ { this->unique_and_dispose(std::equal_to<value_type>(), disposer); }

 //! Requires: Disposer::operator()(pointer) shouldn't throw.
 //!
@@ -1176,18 +1158,19 @@
 template<class BinaryPredicate, class Disposer>
 void unique_and_dispose(BinaryPredicate pred, Disposer disposer)
 {
- if(!this->empty()){
- iterator first = begin();
- iterator after = first;
+ iterator itend(this->end());
+ iterator cur(this->begin());
+
+ if(cur != itend){
+ iterator after(cur);
 ++after;
- while(after != this->end()){
- if(pred(*first, *after)){
- pointer p = after.operator->();
- after = erase(after);
- disposer(p);
+ while(after != itend){
+ if(pred(*cur, *after)){
+ after = this->erase_and_dispose(after, disposer);
 }
 else{
- first = after++;
+ cur = after;
+ ++after;
 }
 }
 }
@@ -1239,7 +1222,7 @@
 //!
 //! Note: Iterators and references are not invalidated.
 iterator iterator_to(reference value)
- {
+ {
 BOOST_INTRUSIVE_INVARIANT_ASSERT(!node_algorithms::inited(real_value_traits::to_node_ptr(value)));
 return iterator(real_value_traits::to_node_ptr(value), this);
 }
@@ -1254,7 +1237,7 @@
 //!
 //! Note: Iterators and references are not invalidated.
 const_iterator iterator_to(const_reference value) const
- {
+ {
 BOOST_INTRUSIVE_INVARIANT_ASSERT(!node_algorithms::inited(real_value_traits::to_node_ptr(const_cast<reference> (value))));
 return const_iterator(real_value_traits::to_node_ptr(const_cast<reference> (value)), this);
 }

Modified: trunk/boost/intrusive/options.hpp
==============================================================================
--- trunk/boost/intrusive/options.hpp (original)
+++ trunk/boost/intrusive/options.hpp 2008-01-25 18:07:51 EST (Fri, 25 Jan 2008)
@@ -360,6 +360,20 @@
/// @endcond
};

+//!This option setter specifies if the list container should
+//!use a linear implementation instead of a circular one.
+template<bool Enabled>
+struct cache_last
+{
+/// @cond
+ template<class Base>
+ struct pack : Base
+ {
+ static const bool cache_last = Enabled;
+ };
+/// @endcond
+};
+
//!This option setter specifies the bucket traits
//!class for unordered associative containers. When this option is specified,
//!instead of using the default bucket traits, a user defined holder will be defined

Modified: trunk/boost/intrusive/slist.hpp
==============================================================================
--- trunk/boost/intrusive/slist.hpp (original)
+++ trunk/boost/intrusive/slist.hpp 2008-01-25 18:07:51 EST (Fri, 25 Jan 2008)
@@ -28,7 +28,8 @@
#include <iterator>
#include <functional>
#include <algorithm>
-#include <cstddef>
+#include <cstddef> //std::size_t
+#include <utility> //std::pair

namespace boost {
namespace intrusive {
@@ -47,13 +48,27 @@
struct get_default_slist_hook
{ typedef typename T::default_slist_hook type; };

-template <class ValueTraits, class SizeType, bool ConstantTimeSize, bool Linear>
+template <class ValueTraits, class SizeType, bool ConstantTimeSize, bool Linear, bool CacheLast>
struct slistopt
{
 typedef ValueTraits value_traits;
 typedef SizeType size_type;
- static const bool constant_time_size = ConstantTimeSize;
- static const bool linear = Linear;
+ static const bool constant_time_size = ConstantTimeSize;
+ static const bool linear = Linear;
+ static const bool cache_last = CacheLast;
+};
+
+template<class Node, class NodePtr, bool>
+struct root_plus_last
+{
+ Node root_;
+ NodePtr last_;
+};
+
+template<class Node, class NodePtr>
+struct root_plus_last<Node, NodePtr, false>
+{
+ Node root_;
};

template <class T>
@@ -70,6 +85,7 @@
 , constant_time_size<true>
 , linear<false>
 , size_type<std::size_t>
+ , cache_last<false>
>::type
{};

@@ -89,15 +105,15 @@
//!
//! The container supports the following options:
//! \c base_hook<>/member_hook<>/value_traits<>,
-//! \c constant_time_size<> and \c size_type<>.
+//! \c constant_time_size<>, \c size_type<>,
+//! \c linear<> and \c cache_last<>.
//!
//! The iterators of slist are forward iterators. slist provides a static
//! function called "previous" to compute the previous iterator of a given iterator.
//! This function has linear complexity. To improve the usability esp. with
//! the '*_after' functions, ++end() == begin() and previous(begin()) == end()
-//! are defined. In addition, whenever you have an end iterator, 'after this
-//! iterator' means 'at the beginning of the list'. To improve the self-documentation
-//! a "before_begin()" function is defined, returning the end() iterator.
+//! are defined. An new special function "before_begin()" is defined, which returns
+//! an iterator that points one less the beginning of the list: ++before_begin() == begin()
#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
template<class T, class ...Options>
#else
@@ -141,6 +157,7 @@
 static const bool constant_time_size = Config::constant_time_size;
 static const bool stateful_value_traits = detail::store_cont_ptr_on_it<slist_impl>::value;
 static const bool linear = Config::linear;
+ static const bool cache_last = Config::cache_last;

 /// @cond
 private:
@@ -162,6 +179,14 @@
 BOOST_STATIC_ASSERT(!(constant_time_size && ((int)real_value_traits::link_mode == (int)auto_unlink)));
 //Linear singly linked lists are incompatible with auto-unlink hooks!
 BOOST_STATIC_ASSERT(!(linear && ((int)real_value_traits::link_mode == (int)auto_unlink)));
+ //A list with cached last node is incompatible with auto-unlink hooks!
+ BOOST_STATIC_ASSERT(!(cache_last && ((int)real_value_traits::link_mode == (int)auto_unlink)));
+
+ node_ptr get_end_node()
+ { return node_ptr(linear ? 0 : this->get_root_node()); }
+
+ const_node_ptr get_end_node() const
+ { return const_node_ptr(linear ? 0 : this->get_root_node()); }

 node_ptr get_root_node()
 { return node_ptr(&data_.root_plus_size_.root_); }
@@ -169,16 +194,49 @@
 const_node_ptr get_root_node() const
 { return const_node_ptr(&data_.root_plus_size_.root_); }

+ node_ptr get_last_node()
+ { return this->get_last_node(detail::bool_<cache_last>()); }
+
+ const_node_ptr get_last_node() const
+ { return this->get_last_node(detail::bool_<cache_last>()); }
+
+ void set_last_node(node_ptr n)
+ { return this->set_last_node(n, detail::bool_<cache_last>()); }
+
+ node_ptr get_last_node(detail::bool_<false>)
+ { return node_ptr(0); }
+
+ const_node_ptr get_last_node(detail::bool_<false>) const
+ { return const_node_ptr(0); }
+
+ void set_last_node(node_ptr, detail::bool_<false>)
+ {}
+
+ node_ptr get_last_node(detail::bool_<true>)
+ { return node_ptr(data_.root_plus_size_.last_); }
+
+ const_node_ptr get_last_node(detail::bool_<true>) const
+ { return const_node_ptr(data_.root_plus_size_.last_); }
+
+ void set_last_node(node_ptr n, detail::bool_<true>)
+ { data_.root_plus_size_.last_ = n; }
+
 static node_ptr uncast(const_node_ptr ptr)
+ { return node_ptr(const_cast<node*>(detail::get_pointer(ptr))); }
+
+ void set_default_constructed_state()
 {
- return node_ptr(const_cast<node*>(detail::get_pointer(ptr)));
+ node_algorithms::init_header(this->get_root_node());
+ this->priv_size_traits().set_size(size_type(0));
+ if(cache_last){
+ this->set_last_node(this->get_root_node());
+ }
 }

 struct root_plus_size
 : public size_traits
- {
- node root_;
- };
+ , public root_plus_last<node, node_ptr, cache_last>
+ {};

 struct data_t
 : public slist_impl::value_traits
@@ -228,10 +286,7 @@
 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks).
 slist_impl(const value_traits &v_traits = value_traits())
 : data_(v_traits)
- {
- this->priv_size_traits().set_size(size_type(0));
- node_algorithms::init_header(this->get_root_node());
- }
+ { this->set_default_constructed_state(); }

 //! Requires: Dereferencing iterator must yield an lvalue of type value_type.
 //!
@@ -245,9 +300,8 @@
 slist_impl(Iterator b, Iterator e, const value_traits &v_traits = value_traits())
 : data_(v_traits)
 {
- this->priv_size_traits().set_size(size_type(0));
- node_algorithms::init_header(this->get_root_node());
- insert_after(before_begin(), b, e);
+ this->set_default_constructed_state();
+ this->insert_after(this->before_begin(), b, e);
 }

 //! Effects: If it's a safe-mode
@@ -273,11 +327,10 @@
 void clear()
 {
 if(safemode_or_autounlink){
- this->erase_after(this->before_begin(), this->end());
+ this->clear_and_dispose(detail::null_disposer());
 }
 else{
- node_algorithms::init_header(this->get_root_node());
- this->priv_size_traits().set_size(size_type(0));
+ this->set_default_constructed_state();
 }
 }

@@ -293,7 +346,17 @@
 //! Note: Invalidates the iterators to the erased elements.
 template <class Disposer>
 void clear_and_dispose(Disposer disposer)
- { this->erase_after_and_dispose(this->before_begin(), this->end(), disposer); }
+ {
+ iterator it(this->begin()), itend(this->end());
+ while(it != itend){
+ node_ptr to_erase(it.pointed_node());
+ ++it;
+ if(safemode_or_autounlink)
+ node_algorithms::init(to_erase);
+ disposer(get_real_value_traits().to_value_ptr(to_erase));
+ }
+ this->set_default_constructed_state();
+ }

 //! Requires: value must be an lvalue.
 //!
@@ -310,10 +373,32 @@
 node_ptr to_insert = get_real_value_traits().to_node_ptr(value);
 if(safemode_or_autounlink)
 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::inited(to_insert));
+ if(cache_last){
+ if(this->empty()){
+ this->set_last_node(to_insert);
+ }
+ }
 node_algorithms::link_after(this->get_root_node(), to_insert);
 this->priv_size_traits().increment();
 }

+ //! Requires: value must be an lvalue.
+ //!
+ //! Effects: Inserts the value in the back of the list.
+ //! No copy constructors are called.
+ //!
+ //! Throws: Nothing.
+ //!
+ //! Complexity: Constant.
+ //!
+ //! Note: Does not affect the validity of iterators and references.
+ //! This function is only available is cache_last<> is true.
+ void push_back(reference value)
+ {
+ BOOST_STATIC_ASSERT((cache_last != 0));
+ this->insert_after(iterator(this->get_last_node(), this), value);
+ }
+
 //! Effects: Erases the first element of the list.
 //! No destructors are called.
 //!
@@ -323,13 +408,7 @@
 //!
 //! Note: Invalidates the iterators (but not the references) to the erased element.
 void pop_front()
- {
- node_ptr to_erase = node_traits::get_next(this->get_root_node());
- node_algorithms::unlink_after(this->get_root_node());
- this->priv_size_traits().decrement();
- if(safemode_or_autounlink)
- node_algorithms::init(to_erase);
- }
+ { return this->pop_front_and_dispose(detail::null_disposer()); }

 //! Requires: Disposer::operator()(pointer) shouldn't throw.
 //!
@@ -345,8 +424,16 @@
 void pop_front_and_dispose(Disposer disposer)
 {
 node_ptr to_erase = node_traits::get_next(this->get_root_node());
- this->pop_front();
+ node_algorithms::unlink_after(this->get_root_node());
+ this->priv_size_traits().decrement();
+ if(safemode_or_autounlink)
+ node_algorithms::init(to_erase);
 disposer(get_real_value_traits().to_value_ptr(to_erase));
+ if(cache_last){
+ if(this->empty()){
+ this->set_last_node(this->get_root_node());
+ }
+ }
 }

 //! Effects: Returns a reference to the first element of the list.
@@ -355,7 +442,7 @@
 //!
 //! Complexity: Constant.
 reference front()
- { return *get_real_value_traits().to_value_ptr(node_traits::get_next(this->get_root_node())); }
+ { return *this->get_real_value_traits().to_value_ptr(node_traits::get_next(this->get_root_node())); }

 //! Effects: Returns a const_reference to the first element of the list.
 //!
@@ -363,7 +450,35 @@
 //!
 //! Complexity: Constant.
 const_reference front() const
- { return *get_real_value_traits().to_value_ptr(uncast(node_traits::get_next(this->get_root_node()))); }
+ { return *this->get_real_value_traits().to_value_ptr(uncast(node_traits::get_next(this->get_root_node()))); }
+
+ //! Effects: Returns a reference to the last element of the list.
+ //!
+ //! Throws: Nothing.
+ //!
+ //! Complexity: Constant.
+ //!
+ //! Note: Does not affect the validity of iterators and references.
+ //! This function is only available is cache_last<> is true.
+ reference back()
+ {
+ BOOST_STATIC_ASSERT((cache_last != 0));
+ return *this->get_real_value_traits().to_value_ptr(this->get_last_node());
+ }
+
+ //! Effects: Returns a const_reference to the last element of the list.
+ //!
+ //! Throws: Nothing.
+ //!
+ //! Complexity: Constant.
+ //!
+ //! Note: Does not affect the validity of iterators and references.
+ //! This function is only available is cache_last<> is true.
+ const_reference back() const
+ {
+ BOOST_STATIC_ASSERT((cache_last != 0));
+ return *this->get_real_value_traits().to_value_ptr(this->get_last_node());
+ }

 //! Effects: Returns an iterator to the first element contained in the list.
 //!
@@ -387,7 +502,7 @@
 //!
 //! Complexity: Constant.
 const_iterator cbegin() const
- { return const_iterator (node_traits::get_next(this->get_root_node()), this); }
+ { return const_iterator(node_traits::get_next(this->get_root_node()), this); }

 //! Effects: Returns an iterator to the end of the list.
 //!
@@ -395,7 +510,7 @@
 //!
 //! Complexity: Constant.
 iterator end()
- { return iterator (linear ? 0 : this->get_root_node(), this); }
+ { return iterator(this->get_end_node(), this); }

 //! Effects: Returns a const_iterator to the end of the list.
 //!
@@ -403,7 +518,7 @@
 //!
 //! Complexity: Constant.
 const_iterator end() const
- { return const_iterator (linear ? 0 : uncast(this->get_root_node()), this); }
+ { return const_iterator(uncast(this->get_end_node()), this); }

 //! Effects: Returns a const_iterator to the end of the list.
 //!
@@ -449,7 +564,7 @@
 //!
 //! Complexity: Constant.
 static slist_impl &container_from_end_iterator(iterator end_iterator)
- { return priv_container_from_end_iterator(end_iterator); }
+ { return slist_impl::priv_container_from_end_iterator(end_iterator); }

 //! Precondition: end_iterator must be a valid end const_iterator
 //! of slist.
@@ -460,7 +575,7 @@
 //!
 //! Complexity: Constant.
 static const slist_impl &container_from_end_iterator(const_iterator end_iterator)
- { return priv_container_from_end_iterator(end_iterator); }
+ { return slist_impl::priv_container_from_end_iterator(end_iterator); }

 //! Effects: Returns the number of the elements contained in the list.
 //!
@@ -492,12 +607,18 @@
 //!
 //! Throws: Nothing.
 //!
- //! Complexity: Linear to the number of elements of both lists.
+ //! Complexity: Linear to the number of elements of both lists.
+ //! Constant-time if linear<> and/or cache_last<> options are used.
 //!
 //! Note: Does not affect the validity of iterators and references.
 void swap(slist_impl& other)
 {
- priv_swap_lists(this->get_root_node(), other.get_root_node(), detail::bool_<linear>());
+ if(cache_last){
+ this->priv_swap_cache_last(other);
+ }
+ else{
+ this->priv_swap_lists(this->get_root_node(), other.get_root_node(), detail::bool_<linear>());
+ }
 if(constant_time_size){
 size_type backup = this->priv_size_traits().get_size();
 this->priv_size_traits().set_size(other.priv_size_traits().get_size());
@@ -515,9 +636,7 @@
 //!
 //! Note: Iterators Does not affect the validity of iterators and references.
 void shift_backwards(size_type n = 1)
- {
- priv_shift_backwards(n, detail::bool_<linear>());
- }
+ { this->priv_shift_backwards(n, detail::bool_<linear>()); }

 //! Effects: Moves forward all the elements, so that the second
 //! element becomes the first, the third becomes the second...
@@ -529,9 +648,7 @@
 //!
 //! Note: Does not affect the validity of iterators and references.
 void shift_forward(size_type n = 1)
- {
- priv_shift_forward(n, detail::bool_<linear>());
- }
+ { this->priv_shift_forward(n, detail::bool_<linear>()); }

 //! Requires: Disposer::operator()(pointer) shouldn't throw.
 //!
@@ -548,18 +665,18 @@
 //! Throws: If cloner throws.
 template <class Cloner, class Disposer>
 void clone_from(const slist_impl &src, Cloner cloner, Disposer disposer)
- {
+ {
 this->clear_and_dispose(disposer);
 BOOST_INTRUSIVE_TRY{
- iterator prev = this->before_begin();
+ iterator prev(this->before_begin());
 const_iterator b(src.begin()), e(src.end());
- for(; b != e; ++b, ++prev){
- this->insert_after(prev, *cloner(*b));
+ for(; b != e; ++b){
+ prev = this->insert_after(prev, *cloner(*b));
 }
 }
 BOOST_INTRUSIVE_CATCH(...){
 this->clear_and_dispose(disposer);
- BOOST_RETHROW;
+ BOOST_INTRUSIVE_RETHROW;
 }
 BOOST_INTRUSIVE_CATCH_END
 }
@@ -582,7 +699,11 @@
 node_ptr n = get_real_value_traits().to_node_ptr(value);
 if(safemode_or_autounlink)
 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::inited(n));
- node_algorithms::link_after(prev_p.pointed_node(), n);
+ node_ptr prev_n(prev_p.pointed_node());
+ node_algorithms::link_after(prev_n, n);
+ if(cache_last && (this->get_last_node() == prev_n)){
+ this->set_last_node(n);
+ }
 this->priv_size_traits().increment();
 return iterator (n, this);
 }
@@ -603,7 +724,7 @@
 void insert_after(iterator prev_p, Iterator first, Iterator last)
 {
 for (; first != last; ++first)
- prev_p = insert_after(prev_p, *first);
+ prev_p = this->insert_after(prev_p, *first);
 }

 //! Requires: value must be an lvalue and p must point to an element
@@ -614,11 +735,12 @@
 //!
 //! Throws: Nothing.
 //!
- //! Complexity: Linear to the number of elements before p.
+ //! Complexity: Linear to the number of elements before p.
+ //! Constant-time if cache_last<> is true and p == end().
 //!
 //! Note: Does not affect the validity of iterators and references.
 iterator insert(iterator p, reference value)
- { return insert_after(this->previous(p), value); }
+ { return this->insert_after(this->previous(p), value); }

 //! Requires: Dereferencing iterator must yield
 //! an lvalue of type value_type and p must point to an element
@@ -631,11 +753,12 @@
 //!
 //! Complexity: Linear to the number of elements inserted plus linear
 //! to the elements before b.
+ //! Linear to the number of elements to insert if cache_last<> option is true and p == end().
 //!
 //! Note: Does not affect the validity of iterators and references.
 template<class Iterator>
 void insert(iterator p, Iterator b, Iterator e)
- { return insert_after(this->previous(p), b, e); }
+ { return this->insert_after(this->previous(p), b, e); }

 //! Effects: Erases the element after the element pointed by prev of
 //! the list. No destructors are called.
@@ -698,7 +821,7 @@
 //! Note: Invalidates the iterators (but not the references) to the
 //! erased elements.
 iterator erase(iterator first, iterator last)
- { return erase_after(this->previous(first), last); }
+ { return this->erase_after(this->previous(first), last); }

 //! Requires: Disposer::operator()(pointer) shouldn't throw.
 //!
@@ -721,7 +844,11 @@
 ++it;
 node_ptr to_erase(it.pointed_node());
 ++it;
- node_algorithms::unlink_after(prev.pointed_node());
+ node_ptr prev_n(prev.pointed_node());
+ node_algorithms::unlink_after(prev_n);
+ if(cache_last && (to_erase == this->get_last_node())){
+ this->set_last_node(prev_n);
+ }
 this->priv_size_traits().decrement();
 if(safemode_or_autounlink)
 node_algorithms::init(to_erase);
@@ -746,10 +873,19 @@
 template<class Disposer>
 iterator erase_after_and_dispose(iterator before_first, iterator last, Disposer disposer)
 {
- iterator next(before_first);
- ++next;
- while(next != last){
- next = this->erase_after_and_dispose(before_first, disposer);
+ node_ptr bfp(before_first.pointed_node()), lp(last.pointed_node());
+ node_ptr fp(node_traits::get_next(bfp));
+ node_algorithms::unlink_after(bfp, lp);
+ while(fp != lp){
+ node_ptr to_erase(fp);
+ fp = node_traits::get_next(fp);
+ if(safemode_or_autounlink)
+ node_algorithms::init(to_erase);
+ disposer(get_real_value_traits().to_value_ptr(to_erase));
+ this->priv_size_traits().decrement();
+ }
+ if(cache_last && (node_traits::get_next(bfp) == this->get_end_node())){
+ this->set_last_node(bfp);
 }
 return last;
 }
@@ -792,7 +928,7 @@
 //! erased elements.
 template<class Disposer>
 iterator erase_and_dispose(iterator first, iterator last, Disposer disposer)
- { return erase_after_and_dispose(this->previous(first), last, disposer); }
+ { return this->erase_after_and_dispose(this->previous(first), last, disposer); }

 //! Requires: Dereferencing iterator must yield
 //! an lvalue of type value_type.
@@ -813,7 +949,7 @@
 void assign(Iterator b, Iterator e)
 {
 this->clear();
- this->insert_after(before_begin(), b, e);
+ this->insert_after(this->before_begin(), b, e);
 }

 //! Requires: Disposer::operator()(pointer) shouldn't throw.
@@ -850,18 +986,21 @@
 //!
 //! Throws: Nothing.
 //!
- //! Complexity: Linear to the elements contained in x
+ //! Complexity: Linear to the elements contained in x.
+ //! Constant-time if cache_last<> option is true.
 //!
 //! Note: Iterators of values obtained from list x now point to elements of this
 //! list. Iterators of this list and all the references are not invalidated.
 iterator splice_after(iterator prev, slist_impl &x)
 {
 if (!x.empty()){
- iterator last_x(x.previous(x.end()));
- node_algorithms::transfer_after
- ( prev.pointed_node()
- , x.before_begin().pointed_node()
- , last_x.pointed_node());
+ iterator last_x(x.previous(x.end())); //<- constant time if cache_last is active
+ node_ptr prev_n(prev.pointed_node());
+ node_ptr last_x_n(last_x.pointed_node());
+ if(cache_last && node_traits::get_next(prev_n) == this->get_end_node()){
+ this->set_last_node(last_x_n);
+ }
+ node_algorithms::transfer_after( prev_n, x.before_begin().pointed_node(), last_x_n);
 this->priv_size_traits().set_size(this->priv_size_traits().get_size() + x.priv_size_traits().get_size());
 x.priv_size_traits().set_size(size_type(0));
 return last_x;
@@ -884,15 +1023,12 @@
 //!
 //! Note: Iterators of values obtained from list x now point to elements of this
 //! list. Iterators of this list and all the references are not invalidated.
- void splice_after(iterator prev, slist_impl &x, iterator prev_ele)
+ void splice_after(iterator prev_pos, slist_impl &x, iterator prev_ele)
 {
- iterator nxt = prev_ele;
- ++nxt;
- if (nxt != prev && prev_ele != prev){
- node_algorithms::transfer_after
- (prev.pointed_node(), prev_ele.pointed_node(), nxt.pointed_node());
- this->priv_size_traits().increment();
- x.priv_size_traits().decrement();
+ iterator elem = prev_ele;
+ ++elem;
+ if (elem != prev_pos && prev_ele != prev_pos){
+ this->splice_after(prev_pos, x, prev_ele, elem, 1);
 }
 }

@@ -913,19 +1049,11 @@
 //! list. Iterators of this list and all the references are not invalidated.
 void splice_after(iterator prev_pos, slist_impl &x, iterator before_first, iterator before_last)
 {
- if (before_first != before_last){
- if(constant_time_size){
- size_type increment = std::distance(before_first, before_last);
- node_algorithms::transfer_after
- (prev_pos.pointed_node(), before_first.pointed_node(), before_last.pointed_node());
- this->priv_size_traits().set_size(this->priv_size_traits().get_size() + increment);
- x.priv_size_traits().set_size(x.priv_size_traits().get_size() - increment);
- }
- else{
- node_algorithms::transfer_after
- (prev_pos.pointed_node(), before_first.pointed_node(), before_last.pointed_node());
- }
- }
+ if(constant_time_size)
+ this->splice_after(prev_pos, x, before_first, before_last, std::distance(before_first, before_last));
+ else
+ this->priv_splice_after
+ (prev_pos.pointed_node(), x, before_first.pointed_node(), before_last.pointed_node());
 }

 //! Requires: prev_pos must be a dereferenceable iterator in *this or be
@@ -945,17 +1073,13 @@
 void splice_after(iterator prev_pos, slist_impl &x, iterator before_first, iterator before_last, difference_type n)
 {
 if(n){
+ BOOST_INTRUSIVE_INVARIANT_ASSERT(std::distance(before_first, before_last) == n);
+ this->priv_splice_after
+ (prev_pos.pointed_node(), x, before_first.pointed_node(), before_last.pointed_node());
 if(constant_time_size){
- BOOST_INTRUSIVE_INVARIANT_ASSERT(std::distance(before_first, before_last) == n);
- node_algorithms::transfer_after
- (prev_pos.pointed_node(), before_first.pointed_node(), before_last.pointed_node());
 this->priv_size_traits().set_size(this->priv_size_traits().get_size() + n);
 x.priv_size_traits().set_size(x.priv_size_traits().get_size() - n);
 }
- else{
- node_algorithms::transfer_after
- (prev_pos.pointed_node(), before_first.pointed_node(), before_last.pointed_node());
- }
 }
 }

@@ -973,11 +1097,13 @@
 //!
 //! Complexity: Linear to the elements contained in x plus linear to
 //! the elements before it.
+ //! Linear to the elements before it if cache_last<> option is true.
+ //! Constant-time if cache_last<> option is true and it == end().
 //!
 //! Note: Iterators of values obtained from list x now point to elements of this
 //! list. Iterators of this list and all the references are not invalidated.
 iterator splice(iterator it, slist_impl &x)
- { return splice_after(this->previous(it), x); }
+ { return this->splice_after(this->previous(it), x); }

 //! Requires: it p must be a valid iterator of *this.
 //! elem must point to an element contained in list
@@ -989,11 +1115,12 @@
 //! Throws: Nothing.
 //!
 //! Complexity: Linear to the elements before pos and before elem.
+ //! Linear to the elements before elem if cache_last<> option is true and pos == end().
 //!
 //! Note: Iterators of values obtained from list x now point to elements of this
 //! list. Iterators of this list and all the references are not invalidated.
 void splice(iterator pos, slist_impl &x, iterator elem)
- { return splice_after(this->previous(pos), x, this->previous(elem)); }
+ { return this->splice_after(this->previous(pos), x, x.previous(elem)); }

 //! Requires: pos must be a dereferenceable iterator in *this
 //! and first and last belong to x and first and last a valid range on x.
@@ -1004,13 +1131,16 @@
 //!
 //! Throws: Nothing.
 //!
- //! Complexity: Linear to the sum of elements before pos, first, and last.
- //! Plus linear to the number of elements transferred if constant_time_size is true.
+ //! Complexity: Linear to the sum of elements before pos, first, and last
+ //! plus linear to the number of elements transferred if constant_time_size is true.
+ //! Linear to the sum of elements before first, and last
+ //! plus linear to the number of elements transferred if constant_time_size is true
+ //! if cache_last<> is true and pos == end()
 //!
 //! Note: Iterators of values obtained from list x now point to elements of this
 //! list. Iterators of this list and all the references are not invalidated.
 void splice(iterator pos, slist_impl &x, iterator first, iterator last)
- { return splice_after(this->previous(pos), x, this->previous(first), this->previous(last)); }
+ { return this->splice_after(this->previous(pos), x, x.previous(first), x.previous(last)); }

 //! Requires: pos must be a dereferenceable iterator in *this
 //! and first and last belong to x and first and last a valid range on x.
@@ -1023,11 +1153,13 @@
 //! Throws: Nothing.
 //!
 //! Complexity: Linear to the sum of elements before pos, first, and last.
+ //! Linear to the sum of elements before first and last
+ //! if cache_last<> is true and pos == end().
 //!
 //! Note: Iterators of values obtained from list x now point to elements of this
 //! list. Iterators of this list and all the references are not invalidated.
 void splice(iterator pos, slist_impl &x, iterator first, iterator last, difference_type n)
- { return splice_after(this->previous(pos), x, this->previous(first), this->previous(last), n); }
+ { return this->splice_after(this->previous(pos), x, x.previous(first), x.previous(last), n); }

 //! Effects: This function sorts the list *this according to std::less<value_type>.
 //! The sort is stable, that is, the relative order of equivalent elements is preserved.
@@ -1173,8 +1305,13 @@
 //! Complexity: This function is linear to the contained elements.
 //!
 //! Note: Iterators and references are not invalidated
- void reverse()
- { priv_reverse(detail::bool_<linear>()); }
+ void reverse()
+ {
+ if(cache_last && !this->empty()){
+ this->set_last_node(node_traits::get_next(this->get_root_node()));
+ }
+ this->priv_reverse(detail::bool_<linear>());
+ }

 //! Effects: Removes all the elements that compare equal to value.
 //! No destructors are called.
@@ -1187,7 +1324,7 @@
 //! and iterators to elements that are not removed remain valid. This function is
 //! linear time: it performs exactly size() comparisons for equality.
 void remove(const_reference value)
- { remove_if(detail::equal_to_value<const_reference>(value)); }
+ { this->remove_if(detail::equal_to_value<const_reference>(value)); }

 //! Requires: Disposer::operator()(pointer) shouldn't throw.
 //!
@@ -1202,7 +1339,7 @@
 //! and iterators to elements that are not removed remain valid.
 template<class Disposer>
 void remove_and_dispose(const_reference value, Disposer disposer)
- { remove_and_dispose_if(detail::equal_to_value<const_reference>(value), disposer); }
+ { this->remove_and_dispose_if(detail::equal_to_value<const_reference>(value), disposer); }

 //! Effects: Removes all the elements for which a specified
 //! predicate is satisfied. No destructors are called.
@@ -1215,7 +1352,7 @@
 //! and iterators to elements that are not removed remain valid.
 template<class Pred>
 void remove_if(Pred pred)
- { remove_and_dispose_if(pred, detail::null_disposer()); }
+ { this->remove_and_dispose_if(pred, detail::null_disposer()); }

 //! Requires: Disposer::operator()(pointer) shouldn't throw.
 //!
@@ -1232,18 +1369,20 @@
 template<class Pred, class Disposer>
 void remove_and_dispose_if(Pred pred, Disposer disposer)
 {
- iterator bcur(this->before_begin()), cur, e(this->end());
+ iterator bcur(this->before_begin()), cur(this->begin()), e(this->end());

- while(++(cur = bcur) != e){
+ while(cur != e){
 if (pred(*cur)){
- pointer p = cur.operator->();
- this->erase_after(bcur);
- disposer(p);
+ cur = this->erase_after_and_dispose(bcur, disposer);
 }
 else{
- ++bcur;
+ bcur = cur;
+ ++cur;
 }
 }
+ if(cache_last){
+ this->set_last_node(bcur.pointed_node());
+ }
 }

 //! Effects: Removes adjacent duplicate elements or adjacent
@@ -1256,7 +1395,7 @@
 //! Note: The relative order of elements that are not removed is unchanged,
 //! and iterators to elements that are not removed remain valid.
 void unique()
- { unique_and_dispose(std::equal_to<value_type>(), detail::null_disposer()); }
+ { this->unique_and_dispose(std::equal_to<value_type>(), detail::null_disposer()); }

 //! Effects: Removes adjacent duplicate elements or adjacent
 //! elements that satisfy some binary predicate from the list.
@@ -1270,7 +1409,7 @@
 //! and iterators to elements that are not removed remain valid.
 template<class BinaryPredicate>
 void unique(BinaryPredicate pred)
- { unique_and_dispose(pred, detail::null_disposer()); }
+ { this->unique_and_dispose(pred, detail::null_disposer()); }

 //! Requires: Disposer::operator()(pointer) shouldn't throw.
 //!
@@ -1286,7 +1425,7 @@
 //! and iterators to elements that are not removed remain valid.
 template<class Disposer>
 void unique_and_dispose(Disposer disposer)
- { unique(std::equal_to<value_type>(), disposer); }
+ { this->unique(std::equal_to<value_type>(), disposer); }

 //! Requires: Disposer::operator()(pointer) shouldn't throw.
 //!
@@ -1303,21 +1442,23 @@
 template<class BinaryPredicate, class Disposer>
 void unique_and_dispose(BinaryPredicate pred, Disposer disposer)
 {
- iterator end_n(end());
- iterator cur(begin());
- iterator cur_next;
-
- if (cur != end_n) {
- while(++(cur_next = cur) != end_n) {
- if (pred(*cur, *cur_next)){
- pointer p = cur_next.operator->();
- this->erase_after(cur);
- disposer(p);
+ iterator end_n(this->end());
+ iterator bcur(this->begin());
+ if(bcur != end_n){
+ iterator cur(bcur);
+ ++cur;
+ while(cur != end_n) {
+ if (pred(*bcur, *cur)){
+ cur = this->erase_after_and_dispose(bcur, disposer);
 }
 else{
+ bcur = cur;
 ++cur;
 }
 }
+ if(cache_last){
+ this->set_last_node(bcur.pointed_node());
+ }
 }
 }

@@ -1367,7 +1508,7 @@
 //!
 //! Note: Iterators and references are not invalidated.
 iterator iterator_to(reference value)
- {
+ {
 //BOOST_INTRUSIVE_INVARIANT_ASSERT (!node_algorithms::inited(value_traits::to_node_ptr(value)));
 return iterator (value_traits::to_node_ptr(value), this);
 }
@@ -1382,7 +1523,7 @@
 //!
 //! Note: Iterators and references are not invalidated.
 const_iterator iterator_to(const_reference value) const
- {
+ {
 //BOOST_INTRUSIVE_INVARIANT_ASSERT (!node_algorithms::inited(value_traits::to_node_ptr(const_cast<reference> (value))));
 return const_iterator (value_traits::to_node_ptr(const_cast<reference> (value)), this);
 }
@@ -1393,12 +1534,16 @@
 //!
 //! Throws: Nothing.
 //!
- //! Complexity: Linear to the number of elements before i.
+ //! Complexity: Linear to the number of elements before i.
+ //! Constant if cache_last<> is true and i == end().
 iterator previous(iterator i)
 {
+ if(cache_last && (i.pointed_node() == this->get_end_node())){
+ return iterator(this->get_last_node(), this);
+ }
 return iterator
 (node_algorithms::get_previous_node
- (before_begin().pointed_node(), i.pointed_node()), 0);
+ (this->before_begin().pointed_node(), i.pointed_node()), this);
 }

 //! Returns: The const_iterator to the element before i in the list.
@@ -1408,14 +1553,30 @@
 //! Throws: Nothing.
 //!
 //! Complexity: Linear to the number of elements before i.
+ //! Constant if cache_last<> is true and i == end().
 const_iterator previous(const_iterator i) const
 {
+ if(cache_last && (i.pointed_node() == this->get_end_node())){
+ return iterator(uncast(this->get_last_node()), this);
+ }
 return const_iterator
 (node_algorithms::get_previous_node
- (before_begin().pointed_node(), i.pointed_node()), 0);
+ (this->before_begin().pointed_node(), i.pointed_node()), this);
 }

 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);
+ }
+ }
+ node_algorithms::transfer_after(prev_pos_n, before_first_n, before_last_n);
+ }

 void priv_reverse(detail::bool_<false>)
 { node_algorithms::reverse(this->get_root_node()); }
@@ -1429,26 +1590,63 @@

 void priv_shift_backwards(size_type n, detail::bool_<false>)
 {
- node_algorithms::move_forward(this->get_root_node(), (std::size_t)n);
+ node_ptr last = node_algorithms::move_forward(this->get_root_node(), (std::size_t)n);
+ if(cache_last && last){
+ this->set_last_node(last);
+ }
 }

 void priv_shift_backwards(size_type n, detail::bool_<true>)
 {
- node_ptr new_first = node_algorithms::move_forward
- (node_traits::get_next(this->get_root_node()), (std::size_t)n);
- node_traits::set_next(this->get_root_node(), new_first);
+ std::pair<node_ptr, node_ptr> ret(
+ node_algorithms::move_first_n_forward
+ (node_traits::get_next(this->get_root_node()), (std::size_t)n));
+ if(ret.first){
+ node_traits::set_next(this->get_root_node(), ret.first);
+ if(cache_last){
+ this->set_last_node(ret.second);
+ }
+ }
 }

 void priv_shift_forward(size_type n, detail::bool_<false>)
 {
- node_algorithms::move_backwards(this->get_root_node(), (std::size_t)n);
+ node_ptr last = node_algorithms::move_backwards(this->get_root_node(), (std::size_t)n);
+ if(cache_last && last){
+ this->set_last_node(last);
+ }
 }

 void priv_shift_forward(size_type n, detail::bool_<true>)
 {
- node_ptr new_first = node_algorithms::move_backwards
- (node_traits::get_next(this->get_root_node()), (std::size_t)n);
- node_traits::set_next(this->get_root_node(), new_first);
+ std::pair<node_ptr, node_ptr> ret(
+ node_algorithms::move_first_n_backwards
+ (node_traits::get_next(this->get_root_node()), (std::size_t)n));
+ if(ret.first){
+ node_traits::set_next(this->get_root_node(), ret.first);
+ if(cache_last){
+ this->set_last_node(ret.second);
+ }
+ }
+ }
+
+ void priv_swap_cache_last(slist_impl &other)
+ {
+ 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);
+ }
+ if(other.get_last_node() == this_bfirst){
+ other.set_last_node(other_bfirst);
+ }
 }

 //circular version
@@ -1465,7 +1663,7 @@
 //singly linked lists (because "end" is represented by the null pointer)
 BOOST_STATIC_ASSERT(!linear);
 root_plus_size *r = detail::parent_from_member<root_plus_size, node>
- ( detail::get_pointer(end_iterator.pointed_node()), &root_plus_size::root_);
+ ( detail::get_pointer(end_iterator.pointed_node()), (&root_plus_size::root_));
 data_t *d = detail::parent_from_member<data_t, root_plus_size>
 ( r, &data_t::root_plus_size_);
 slist_impl *s = detail::parent_from_member<slist_impl, data_t>(d, &slist_impl::data_);
@@ -1595,13 +1793,13 @@
#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
template<class T, class ...Options>
#else
-template<class T, class O1 = none, class O2 = none, class O3 = none, class O4 = none>
+template<class T, class O1 = none, class O2 = none, class O3 = none, class O4 = none, class O5 = none>
#endif
struct make_slist
{
 /// @cond
 typedef typename pack_options
- < slist_defaults<T>, O1, O2, O3, O4>::type packed_options;
+ < slist_defaults<T>, O1, O2, O3, O4, O5>::type packed_options;
 typedef typename detail::get_value_traits
 <T, typename packed_options::value_traits>::type value_traits;
 typedef slist_impl
@@ -1611,6 +1809,7 @@
 , typename packed_options::size_type
 , packed_options::constant_time_size
 , packed_options::linear
+ , packed_options::cache_last
>
> implementation_defined;
 /// @endcond
@@ -1619,12 +1818,12 @@

#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
-template<class T, class O1, class O2, class O3, class O4>
+template<class T, class O1, class O2, class O3, class O4, class O5>
class slist
- : public make_slist<T, O1, O2, O3, O4>::type
+ : public make_slist<T, O1, O2, O3, O4, O5>::type
{
 typedef typename make_slist
- <T, O1, O2, O3, O4>::type Base;
+ <T, O1, O2, O3, O4, O5>::type Base;
 typedef typename Base::real_value_traits real_value_traits;
 //Assert if passed value traits are compatible with the type
 BOOST_STATIC_ASSERT((detail::is_same<typename real_value_traits::value_type, T>::value));

Modified: trunk/libs/interprocess/test/file_mapping_test.cpp
==============================================================================
--- trunk/libs/interprocess/test/file_mapping_test.cpp (original)
+++ trunk/libs/interprocess/test/file_mapping_test.cpp 2008-01-25 18:07:51 EST (Fri, 25 Jan 2008)
@@ -9,15 +9,15 @@
//////////////////////////////////////////////////////////////////////////////

#include <boost/interprocess/detail/config_begin.hpp>
-#include <ios> // for std::streamoff
-#include <fstream>
+#include <ios> //std::streamoff
+#include <fstream> //std::ofstream, std::ifstream
#include <iostream>
#include <boost/interprocess/file_mapping.hpp>
#include <boost/interprocess/mapped_region.hpp>
-#include <memory>
-#include <cstdio>
-#include <string>
+#include <memory> //std::auto_ptr
+#include <stdexcept> //std::exception
#include <cstdio> //std::remove
+#include <cstddef> //std::size_t
#include "get_process_id_name.hpp"

using namespace boost::interprocess;

Modified: trunk/libs/interprocess/test/get_process_id_name.hpp
==============================================================================
--- trunk/libs/interprocess/test/get_process_id_name.hpp (original)
+++ trunk/libs/interprocess/test/get_process_id_name.hpp 2008-01-25 18:07:51 EST (Fri, 25 Jan 2008)
@@ -12,9 +12,8 @@
#define BOOST_INTERPROCESS_GET_PROCESS_ID_NAME_HPP

#include <boost/config.hpp>
-#include <string>
-#include <algorithm>
-#include <sstream>
+#include <string> //std::string
+#include <sstream> //std::stringstream
#include <boost/interprocess/detail/os_thread_functions.hpp>

namespace boost{

Modified: trunk/libs/interprocess/test/list_test.hpp
==============================================================================
--- trunk/libs/interprocess/test/list_test.hpp (original)
+++ trunk/libs/interprocess/test/list_test.hpp 2008-01-25 18:07:51 EST (Fri, 25 Jan 2008)
@@ -39,7 +39,8 @@
 shmlist->push_back(move(move_me));
 stdlist->push_back(i);
 }
- if(!CheckEqualContainers(shmlist, stdlist)) return 1;
+ if(!CheckEqualContainers(shmlist, stdlist))
+ return 1;
 return 0;
 }
};
@@ -56,7 +57,8 @@
 shmlist->push_front(move(move_me));
 stdlist->push_front(i);
 }
- if(!CheckEqualContainers(shmlist, stdlist)) return 1;
+ if(!CheckEqualContainers(shmlist, stdlist))
+ return 1;
 return 0;
 }
};
@@ -69,7 +71,8 @@
 {
 shmlist->pop_back();
 stdlist->pop_back();
- if(!CheckEqualContainers(shmlist, stdlist)) return 1;
+ if(!CheckEqualContainers(shmlist, stdlist))
+ return 1;
 return 0;
 }
};
@@ -177,12 +180,14 @@

 shmlist->unique();
 stdlist->unique();
- if(!CheckEqualContainers(shmlist, stdlist)) return 1;
+ if(!CheckEqualContainers(shmlist, stdlist))
+ return 1;

 if(copied_allocators_equal){
 shmlist->sort(std::greater<IntType>());
 stdlist->sort(std::greater<int>());
- if(!CheckEqualContainers(shmlist, stdlist)) return 1;
+ if(!CheckEqualContainers(shmlist, stdlist))
+ return 1;
 }

 shmlist->resize(25);
@@ -191,7 +196,8 @@
 stdlist->resize(50);
 shmlist->resize(0);
 stdlist->resize(0);
- if(!CheckEqualContainers(shmlist, stdlist)) return 1;
+ if(!CheckEqualContainers(shmlist, stdlist))
+ return 1;

 if(push_data_t::execute(max, shmlist, stdlist)){
 return 1;
@@ -209,7 +215,8 @@
 if(copied_allocators_equal){
 shmlist->splice(shmlist->begin(), othershmlist);
 stdlist->splice(stdlist->begin(), otherstdlist);
- if(!CheckEqualContainers(shmlist, stdlist)) return 1;
+ if(!CheckEqualContainers(shmlist, stdlist))
+ return 1;
 }

 listsize = (int)shmlist->size();
@@ -225,15 +232,18 @@
 if(copied_allocators_equal){
 shmlist->sort(std::greater<IntType>());
 stdlist->sort(std::greater<int>());
- if(!CheckEqualContainers(shmlist, stdlist)) return 1;
+ if(!CheckEqualContainers(shmlist, stdlist))
+ return 1;

 othershmlist.sort(std::greater<IntType>());
 otherstdlist.sort(std::greater<int>());
- if(!CheckEqualContainers(&othershmlist, &otherstdlist)) return 1;
+ if(!CheckEqualContainers(&othershmlist, &otherstdlist))
+ return 1;

 shmlist->merge(othershmlist, std::greater<IntType>());
 stdlist->merge(otherstdlist, std::greater<int>());
- if(!CheckEqualContainers(shmlist, stdlist)) return 1;
+ if(!CheckEqualContainers(shmlist, stdlist))
+ return 1;
 }
 }

Modified: trunk/libs/intrusive/proj/vc7ide/_intrusivelib/_intrusivelib.vcproj
==============================================================================
--- trunk/libs/intrusive/proj/vc7ide/_intrusivelib/_intrusivelib.vcproj (original)
+++ trunk/libs/intrusive/proj/vc7ide/_intrusivelib/_intrusivelib.vcproj 2008-01-25 18:07:51 EST (Fri, 25 Jan 2008)
@@ -217,6 +217,9 @@
 RelativePath="..\..\..\..\..\boost\intrusive\detail\avltree_node.hpp">
 </File>
 <File
+ RelativePath="..\..\..\..\..\boost\intrusive\detail\common_slist_algorithms.hpp">
+ </File>
+ <File
 RelativePath="..\..\..\..\..\boost\intrusive\detail\config_begin.hpp">
 </File>
 <File

Modified: trunk/libs/intrusive/test/itestvalue.hpp
==============================================================================
--- trunk/libs/intrusive/test/itestvalue.hpp (original)
+++ trunk/libs/intrusive/test/itestvalue.hpp 2008-01-25 18:07:51 EST (Fri, 25 Jan 2008)
@@ -237,7 +237,7 @@
 // have to be handled appropriately when copied:

 testvalue & operator= (const testvalue& src)
- {
+ {/*
 set_base_hook_t::operator=(src);
 set_auto_base_hook_t::operator=(src);
 this->set_node_ = src.set_node_;
@@ -270,7 +270,7 @@
 slist_auto_base_hook_t::operator=(src);
 this->slist_node_ = src.slist_node_;
 this->slist_auto_node_ = src.slist_auto_node_;
-
+*/
 value_ = src.value_;
 return *this;
 }
@@ -366,6 +366,14 @@
 }
};

+struct is_even
+{
+ template<class VoidPointer, bool constant_time_size>
+ bool operator()
+ (const testvalue<VoidPointer, constant_time_size>& v1) const
+ { return (v1.value_ & 1) == 0; }
+};
+
} //namespace boost{
} //namespace intrusive{

Modified: trunk/libs/intrusive/test/list_test.cpp
==============================================================================
--- trunk/libs/intrusive/test/list_test.cpp (original)
+++ trunk/libs/intrusive/test/list_test.cpp 2008-01-25 18:07:51 EST (Fri, 25 Jan 2008)
@@ -31,6 +31,8 @@
 static void test_all(std::vector<value_type>& values);
 static void test_front_back(std::vector<value_type>& values);
 static void test_sort(std::vector<value_type>& values);
+ static void test_merge(std::vector<value_type>& values);
+ static void test_remove_unique(std::vector<value_type>& values);
 static void test_insert(std::vector<value_type>& values);
 static void test_shift(std::vector<value_type>& values);
 static void test_swap(std::vector<value_type>& values);
@@ -58,6 +60,8 @@

 test_front_back(values);
 test_sort(values);
+ test_merge(values);
+ test_remove_unique(values);
 test_insert(values);
 test_shift(values);
 test_swap(values);
@@ -126,6 +130,60 @@
 { int init_values [] = { 5, 3, 1, 4, 2 };
 TEST_INTRUSIVE_SEQUENCE( init_values, testlist.begin() ); }
}
+
+//test: merge due to error in merge implementation:
+template<class ValueTraits>
+void test_list<ValueTraits>
+ ::test_remove_unique (std::vector<typename ValueTraits::value_type>& values)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef list
+ < value_type
+ , value_traits<ValueTraits>
+ , size_type<std::size_t>
+ , constant_time_size<value_type::constant_time_size>
+ > list_type;
+ {
+ list_type list(values.begin(), values.end());
+ list.remove_if(is_even());
+ int init_values [] = { 1, 3, 5 };
+ TEST_INTRUSIVE_SEQUENCE( init_values, list.begin() );
+ }
+ {
+ std::vector<typename ValueTraits::value_type> values2(values);
+ list_type list(values.begin(), values.end());
+ list.insert(list.end(), values2.begin(), values2.end());
+ list.sort();
+ int init_values [] = { 1, 1, 2, 2, 3, 3, 4, 4, 5, 5 };
+ TEST_INTRUSIVE_SEQUENCE( init_values, list.begin() );
+ list.unique();
+ int init_values2 [] = { 1, 2, 3, 4, 5 };
+ TEST_INTRUSIVE_SEQUENCE( init_values2, list.begin() );
+ }
+}
+
+//test: merge due to error in merge implementation:
+template<class ValueTraits>
+void test_list<ValueTraits>
+ ::test_merge (std::vector<typename ValueTraits::value_type>& values)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef list
+ < value_type
+ , value_traits<ValueTraits>
+ , size_type<std::size_t>
+ , constant_time_size<value_type::constant_time_size>
+ > list_type;
+ list_type testlist1, testlist2;
+ testlist1.push_front (values[0]);
+ testlist2.push_front (values[4]);
+ testlist2.push_front (values[3]);
+ testlist2.push_front (values[2]);
+ testlist1.merge (testlist2);
+
+ int init_values [] = { 1, 3, 4, 5 };
+ TEST_INTRUSIVE_SEQUENCE( init_values, testlist1.begin() );
+}

//test: assign, insert, const_iterator, const_reverse_iterator, erase, s_iterator_to:
template<class ValueTraits>

Modified: trunk/libs/intrusive/test/slist_test.cpp
==============================================================================
--- trunk/libs/intrusive/test/slist_test.cpp (original)
+++ trunk/libs/intrusive/test/slist_test.cpp 2008-01-25 18:07:51 EST (Fri, 25 Jan 2008)
@@ -24,25 +24,28 @@

using namespace boost::intrusive;

-template<class ValueTraits, bool Linear>
+template<class ValueTraits, bool Linear, bool CacheLast>
struct test_slist
{
 typedef typename ValueTraits::value_type value_type;
- static void test_all (std::vector<value_type>& values);
- static void test_front_back (std::vector<value_type>& values);
+ static void test_all(std::vector<value_type>& values);
+ static void test_front(std::vector<value_type>& values);
+ static void test_back(std::vector<value_type>& values, detail::bool_<true>);
+ static void test_back(std::vector<value_type>& values, detail::bool_<false>);
 static void test_sort(std::vector<value_type>& values);
- static void test_merge (std::vector<value_type>& values);
+ static void test_merge(std::vector<value_type>& values);
+ static void test_remove_unique(std::vector<value_type>& values);
 static void test_insert(std::vector<value_type>& values);
 static void test_shift(std::vector<value_type>& values);
 static void test_swap(std::vector<value_type>& values);
- static void test_slow_insert (std::vector<value_type>& values);
- static void test_clone (std::vector<value_type>& values);
+ static void test_slow_insert(std::vector<value_type>& values);
+ static void test_clone(std::vector<value_type>& values);
 static void test_container_from_end(std::vector<value_type> &, detail::bool_<true>){}
 static void test_container_from_end(std::vector<value_type> &values, detail::bool_<false>);
};

-template<class ValueTraits, bool Linear>
-void test_slist<ValueTraits, Linear>
+template<class ValueTraits, bool Linear, bool CacheLast>
+void test_slist<ValueTraits, Linear, CacheLast>
 ::test_all (std::vector<typename ValueTraits::value_type>& values)
{
 typedef typename ValueTraits::value_type value_type;
@@ -52,6 +55,7 @@
 , size_type<std::size_t>
 , constant_time_size<value_type::constant_time_size>
 , linear<Linear>
+ , cache_last<CacheLast>
> list_type;
 {
 list_type list(values.begin(), values.end());
@@ -60,9 +64,11 @@
 list.insert(list.end(), values.begin(), values.end());
 test::test_sequence_container(list, values);
 }
- test_front_back (values);
+ test_front(values);
+ test_back(values, detail::bool_<CacheLast>());
 test_sort(values);
 test_merge (values);
+ test_remove_unique(values);
 test_insert(values);
 test_shift(values);
 test_slow_insert (values);
@@ -72,9 +78,9 @@
}

//test: push_front, pop_front, front, size, empty:
-template<class ValueTraits, bool Linear>
-void test_slist<ValueTraits, Linear>
- ::test_front_back (std::vector<typename ValueTraits::value_type>& values)
+template<class ValueTraits, bool Linear, bool CacheLast>
+void test_slist<ValueTraits, Linear, CacheLast>
+ ::test_front(std::vector<typename ValueTraits::value_type>& values)
{
 typedef typename ValueTraits::value_type value_type;
 typedef slist
@@ -83,6 +89,7 @@
 , size_type<std::size_t>
 , constant_time_size<value_type::constant_time_size>
 , linear<Linear>
+ , cache_last<CacheLast>
> list_type;
 list_type testlist;
 BOOST_TEST (testlist.empty());
@@ -101,11 +108,45 @@

 testlist.pop_front();
 BOOST_TEST (testlist.empty());
-}
+}
+
+//test: push_front, pop_front, front, size, empty:
+template<class ValueTraits, bool Linear, bool CacheLast>
+void test_slist<ValueTraits, Linear, CacheLast>
+ ::test_back(std::vector<typename ValueTraits::value_type>& values, detail::bool_<true>)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef slist
+ < value_type
+ , value_traits<ValueTraits>
+ , size_type<std::size_t>
+ , constant_time_size<value_type::constant_time_size>
+ , linear<Linear>
+ , cache_last<CacheLast>
+ > list_type;
+ list_type testlist;
+ BOOST_TEST (testlist.empty());
+
+ testlist.push_back (values[0]);
+ BOOST_TEST (testlist.size() == 1);
+ BOOST_TEST (&testlist.front() == &values[0]);
+ BOOST_TEST (&testlist.back() == &values[0]);
+ testlist.push_back(values[1]);
+ BOOST_TEST(*testlist.previous(testlist.end()) == values[1]);
+ BOOST_TEST (&testlist.front() == &values[0]);
+ BOOST_TEST (&testlist.back() == &values[1]);
+}
+
+//test: push_front, pop_front, front, size, empty:
+template<class ValueTraits, bool Linear, bool CacheLast>
+void test_slist<ValueTraits, Linear, CacheLast>
+ ::test_back(std::vector<typename ValueTraits::value_type>&, detail::bool_<false>)
+{}
+

//test: merge due to error in merge implementation:
-template<class ValueTraits, bool Linear>
-void test_slist<ValueTraits, Linear>
+template<class ValueTraits, bool Linear, bool CacheLast>
+void test_slist<ValueTraits, Linear, CacheLast>
 ::test_merge (std::vector<typename ValueTraits::value_type>& values)
{
 typedef typename ValueTraits::value_type value_type;
@@ -115,6 +156,7 @@
 , size_type<std::size_t>
 , constant_time_size<value_type::constant_time_size>
 , linear<Linear>
+ , cache_last<CacheLast>
> list_type;
 list_type testlist1, testlist2;
 testlist1.push_front (values[0]);
@@ -127,9 +169,42 @@
 TEST_INTRUSIVE_SEQUENCE( init_values, testlist1.begin() );
}

+//test: merge due to error in merge implementation:
+template<class ValueTraits, bool Linear, bool CacheLast>
+void test_slist<ValueTraits, Linear, CacheLast>
+ ::test_remove_unique (std::vector<typename ValueTraits::value_type>& values)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef slist
+ < value_type
+ , value_traits<ValueTraits>
+ , size_type<std::size_t>
+ , constant_time_size<value_type::constant_time_size>
+ , linear<Linear>
+ , cache_last<CacheLast>
+ > list_type;
+ {
+ list_type list(values.begin(), values.end());
+ list.remove_if(is_even());
+ int init_values [] = { 1, 3, 5 };
+ TEST_INTRUSIVE_SEQUENCE( init_values, list.begin() );
+ }
+ {
+ std::vector<typename ValueTraits::value_type> values2(values);
+ list_type list(values.begin(), values.end());
+ list.insert_after(list.before_begin(), values2.begin(), values2.end());
+ list.sort();
+ int init_values [] = { 1, 1, 2, 2, 3, 3, 4, 4, 5, 5 };
+ TEST_INTRUSIVE_SEQUENCE( init_values, list.begin() );
+ list.unique();
+ int init_values2 [] = { 1, 2, 3, 4, 5 };
+ TEST_INTRUSIVE_SEQUENCE( init_values2, list.begin() );
+ }
+}
+
//test: constructor, iterator, sort, reverse:
-template<class ValueTraits, bool Linear>
-void test_slist<ValueTraits, Linear>
+template<class ValueTraits, bool Linear, bool CacheLast>
+void test_slist<ValueTraits, Linear, CacheLast>
 ::test_sort(std::vector<typename ValueTraits::value_type>& values)
{
 typedef typename ValueTraits::value_type value_type;
@@ -139,6 +214,7 @@
 , size_type<std::size_t>
 , constant_time_size<value_type::constant_time_size>
 , linear<Linear>
+ , cache_last<CacheLast>
> list_type;
 list_type testlist (values.begin(), values.end());

@@ -155,8 +231,8 @@
}

//test: assign, insert_after, const_iterator, erase_after, s_iterator_to, previous:
-template<class ValueTraits, bool Linear>
-void test_slist<ValueTraits, Linear>
+template<class ValueTraits, bool Linear, bool CacheLast>
+void test_slist<ValueTraits, Linear, CacheLast>
 ::test_insert(std::vector<typename ValueTraits::value_type>& values)
{
 typedef typename ValueTraits::value_type value_type;
@@ -166,6 +242,7 @@
 , size_type<std::size_t>
 , constant_time_size<value_type::constant_time_size>
 , linear<Linear>
+ , cache_last<CacheLast>
> list_type;
 list_type testlist;
 testlist.assign (&values[0] + 2, &values[0] + 5);
@@ -195,8 +272,8 @@
}

//test: insert, const_iterator, erase, siterator_to:
-template<class ValueTraits, bool Linear>
-void test_slist<ValueTraits, Linear>
+template<class ValueTraits, bool Linear, bool CacheLast>
+void test_slist<ValueTraits, Linear, CacheLast>
 ::test_slow_insert (std::vector<typename ValueTraits::value_type>& values)
{
 typedef typename ValueTraits::value_type value_type;
@@ -206,6 +283,7 @@
 , size_type<std::size_t>
 , constant_time_size<value_type::constant_time_size>
 , linear<Linear>
+ , cache_last<CacheLast>
> list_type;
 list_type testlist;
 testlist.push_front (values[4]);
@@ -239,8 +317,8 @@
 BOOST_TEST (testlist.front().value_ == 3);
}

-template<class ValueTraits, bool Linear>
-void test_slist<ValueTraits, Linear>
+template<class ValueTraits, bool Linear, bool CacheLast>
+void test_slist<ValueTraits, Linear, CacheLast>
 ::test_shift(std::vector<typename ValueTraits::value_type>& values)
{
 typedef typename ValueTraits::value_type value_type;
@@ -250,6 +328,7 @@
 , size_type<std::size_t>
 , constant_time_size<value_type::constant_time_size>
 , linear<Linear>
+ , cache_last<CacheLast>
> list_type;
 list_type testlist;

@@ -285,8 +364,8 @@
}

//test: insert_after (seq-version), swap, splice_after:
-template<class ValueTraits, bool Linear>
-void test_slist<ValueTraits, Linear>
+template<class ValueTraits, bool Linear, bool CacheLast>
+void test_slist<ValueTraits, Linear, CacheLast>
 ::test_swap(std::vector<typename ValueTraits::value_type>& values)
{
 typedef typename ValueTraits::value_type value_type;
@@ -296,6 +375,7 @@
 , size_type<std::size_t>
 , constant_time_size<value_type::constant_time_size>
 , linear<Linear>
+ , cache_last<CacheLast>
> list_type;
 {
 list_type testlist1 (&values[0], &values[0] + 2);
@@ -363,8 +443,8 @@
 }
}

-template<class ValueTraits, bool Linear>
-void test_slist<ValueTraits, Linear>
+template<class ValueTraits, bool Linear, bool CacheLast>
+void test_slist<ValueTraits, Linear, CacheLast>
 ::test_clone(std::vector<typename ValueTraits::value_type>& values)
{
 typedef typename ValueTraits::value_type value_type;
@@ -374,6 +454,7 @@
 , size_type<std::size_t>
 , constant_time_size<value_type::constant_time_size>
 , linear<Linear>
+ , cache_last<CacheLast>
> list_type;

 list_type testlist1 (&values[0], &values[0] + values.size());
@@ -385,8 +466,8 @@
 BOOST_TEST (testlist2.empty());
}

-template<class ValueTraits, bool Linear>
-void test_slist<ValueTraits, Linear>
+template<class ValueTraits, bool Linear, bool CacheLast>
+void test_slist<ValueTraits, Linear, CacheLast>
 ::test_container_from_end(std::vector<typename ValueTraits::value_type>& values
 ,detail::bool_<false>)
{
@@ -397,6 +478,7 @@
 , size_type<std::size_t>
 , constant_time_size<value_type::constant_time_size>
 , linear<Linear>
+ , cache_last<CacheLast>
> list_type;
 list_type testlist1 (&values[0], &values[0] + values.size());
 BOOST_TEST (testlist1 == list_type::container_from_end_iterator(testlist1.end()));
@@ -419,6 +501,7 @@
 , typename value_type::slist_base_hook_t
>::type
 , false
+ , false
>::test_all(data);
 test_slist < typename detail::get_member_value_traits
 < value_type
@@ -428,6 +511,7 @@
>
>::type
 , false
+ , false
>::test_all(data);

 //Now linear slists
@@ -436,6 +520,7 @@
 , typename value_type::slist_base_hook_t
>::type
 , true
+ , false
>::test_all(data);

 test_slist < typename detail::get_member_value_traits
@@ -446,8 +531,47 @@
>
>::type
 , true
+ , false
+ >::test_all(data);
+
+ //Now the same but caching the last node
+ test_slist < typename detail::get_base_value_traits
+ < value_type
+ , typename value_type::slist_base_hook_t
+ >::type
+ , false
+ , true
+ >::test_all(data);
+ test_slist < typename detail::get_member_value_traits
+ < value_type
+ , member_hook< value_type
+ , typename value_type::slist_member_hook_t
+ , &value_type::slist_node_
+ >
+ >::type
+ , false
+ , true
+ >::test_all(data);
+
+ //Now linear slists
+ test_slist < typename detail::get_base_value_traits
+ < value_type
+ , typename value_type::slist_base_hook_t
+ >::type
+ , true
+ , true
>::test_all(data);

+ test_slist < typename detail::get_member_value_traits
+ < value_type
+ , member_hook< value_type
+ , typename value_type::slist_member_hook_t
+ , &value_type::slist_node_
+ >
+ >::type
+ , true
+ , true
+ >::test_all(data);
 return 0;
 }
};
@@ -468,6 +592,7 @@
 , typename value_type::slist_base_hook_t
>::type
 , false
+ , false
>::test_all(data);

 test_slist < typename detail::get_member_value_traits
@@ -478,6 +603,7 @@
>
>::type
 , false
+ , false
>::test_all(data);

 test_slist < typename detail::get_base_value_traits
@@ -485,6 +611,7 @@
 , typename value_type::slist_auto_base_hook_t
>::type
 , false
+ , false
>::test_all(data);

 test_slist < typename detail::get_member_value_traits
@@ -495,6 +622,7 @@
>
>::type
 , false
+ , false
>::test_all(data);

 test_slist < typename detail::get_base_value_traits
@@ -502,6 +630,7 @@
 , typename value_type::slist_base_hook_t
>::type
 , true
+ , false
>::test_all(data);

 test_slist < typename detail::get_member_value_traits
@@ -512,6 +641,46 @@
>
>::type
 , true
+ , false
+ >::test_all(data);
+
+ //Now cache last
+ test_slist < typename detail::get_base_value_traits
+ < value_type
+ , typename value_type::slist_base_hook_t
+ >::type
+ , false
+ , true
+ >::test_all(data);
+
+ test_slist < typename detail::get_member_value_traits
+ < value_type
+ , member_hook< value_type
+ , typename value_type::slist_member_hook_t
+ , &value_type::slist_node_
+ >
+ >::type
+ , false
+ , true
+ >::test_all(data);
+
+ test_slist < typename detail::get_base_value_traits
+ < value_type
+ , typename value_type::slist_base_hook_t
+ >::type
+ , true
+ , true
+ >::test_all(data);
+
+ test_slist < typename detail::get_member_value_traits
+ < value_type
+ , member_hook< value_type
+ , typename value_type::slist_member_hook_t
+ , &value_type::slist_node_
+ >
+ >::type
+ , true
+ , true
>::test_all(data);
 return 0;
 }

Next message: daniel_james_at_[hidden]: "[Boost-commit] svn:boost r42975 - branches/unordered/trunk/libs/unordered/test/exception"
Previous message: dgregor_at_[hidden]: "[Boost-commit] svn:boost r42973 - branches/release/libs/logic/test"

Date view	Thread view	Subject view	Author view

Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk