Boost logo

Boost-Commit :

Subject: [Boost-commit] svn:boost r50261 - trunk/boost/intrusive/detail
From: igaztanaga_at_[hidden]
Date: 2008-12-13 08:56:16


Author: igaztanaga
Date: 2008-12-13 08:56:15 EST (Sat, 13 Dec 2008)
New Revision: 50261
URL: http://svn.boost.org/trac/boost/changeset/50261

Log:
* New treap-based containers: treap, treap_set, treap_multiset.
* Corrected compilation bug for Windows-based 64 bit compilers.
* Corrected exception-safety bugs in container constructors.
* Updated documentation to show rvalue-references funcions instead of emulation functions.
Added:
   trunk/boost/intrusive/detail/clear_on_destructor_base.hpp (contents, props changed)
Text files modified:
   trunk/boost/intrusive/detail/assert.hpp | 2
   trunk/boost/intrusive/detail/config_begin.hpp | 4
   trunk/boost/intrusive/detail/config_end.hpp | 2
   trunk/boost/intrusive/detail/ebo_functor_holder.hpp | 2
   trunk/boost/intrusive/detail/generic_hook.hpp | 2
   trunk/boost/intrusive/detail/hashtable_node.hpp | 2
   trunk/boost/intrusive/detail/list_node.hpp | 2
   trunk/boost/intrusive/detail/mpl.hpp | 4
   trunk/boost/intrusive/detail/parent_from_member.hpp | 2
   trunk/boost/intrusive/detail/rbtree_node.hpp | 2
   trunk/boost/intrusive/detail/slist_node.hpp | 2
   trunk/boost/intrusive/detail/transform_iterator.hpp | 2
   trunk/boost/intrusive/detail/tree_algorithms.hpp | 162 ++++++++++++++++++++-------------------
   trunk/boost/intrusive/detail/tree_node.hpp | 3
   trunk/boost/intrusive/detail/utilities.hpp | 13 ++
   15 files changed, 110 insertions(+), 96 deletions(-)

Modified: trunk/boost/intrusive/detail/assert.hpp
==============================================================================
--- trunk/boost/intrusive/detail/assert.hpp (original)
+++ trunk/boost/intrusive/detail/assert.hpp 2008-12-13 08:56:15 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
 /////////////////////////////////////////////////////////////////////////////
 //
-// (C) Copyright Ion Gaztanaga 2006-2007
+// (C) Copyright Ion Gaztanaga 2006-2008
 //
 // Distributed under the Boost Software License, Version 1.0.
 // (See accompanying file LICENSE_1_0.txt or copy at

Added: trunk/boost/intrusive/detail/clear_on_destructor_base.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/intrusive/detail/clear_on_destructor_base.hpp 2008-12-13 08:56:15 EST (Sat, 13 Dec 2008)
@@ -0,0 +1,36 @@
+//////} // ///////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2008-2008. Distributed under the Boost
+// Software License, Version 1.0. (See accompanying file
+// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+//
+// See http://www.boost.org/libs/intrusive for documentation.
+//
+/////////////////////////////////////////////////////////////////////////////
+
+#ifndef BOOST_INTRUSIVE_DETAIL_CLEAR_ON_DESTRUCTOR_HPP
+#define BOOST_INTRUSIVE_DETAIL_CLEAR_ON_DESTRUCTOR_HPP
+
+#include <boost/intrusive/detail/config_begin.hpp>
+
+namespace boost {
+namespace intrusive {
+namespace detail {
+
+template<class Derived>
+class clear_on_destructor_base
+{
+ protected:
+ ~clear_on_destructor_base()
+ {
+ static_cast<Derived*>(this)->clear();
+ }
+};
+
+} // namespace detail {
+} // namespace intrusive {
+} // namespace boost {
+
+#include <boost/intrusive/detail/config_end.hpp>
+
+#endif //#ifndef BOOST_INTRUSIVE_DETAIL_CLEAR_ON_DESTRUCTOR_HPP

Modified: trunk/boost/intrusive/detail/config_begin.hpp
==============================================================================
--- trunk/boost/intrusive/detail/config_begin.hpp (original)
+++ trunk/boost/intrusive/detail/config_begin.hpp 2008-12-13 08:56:15 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
 /////////////////////////////////////////////////////////////////////////////
 //
-// (C) Copyright Ion Gaztanaga 2006-2007
+// (C) Copyright Ion Gaztanaga 2006-2008
 //
 // Distributed under the Boost Software License, Version 1.0.
 // (See accompanying file LICENSE_1_0.txt or copy at
@@ -44,6 +44,8 @@
    #pragma warning (disable : 4267) //conversion from 'X' to 'Y', possible loss of data
    #pragma warning (disable : 4127) //conditional expression is constant
    #pragma warning (disable : 4706) //assignment within conditional expression
+ #pragma warning (disable : 4541) //'typeid' used on polymorphic type 'boost::exception' with /GR-
+ #pragma warning (disable : 4512) //'typeid' used on polymorphic type 'boost::exception' with /GR-
 #endif
 
 //#define BOOST_INTRUSIVE_USE_ITERATOR_FACADE

Modified: trunk/boost/intrusive/detail/config_end.hpp
==============================================================================
--- trunk/boost/intrusive/detail/config_end.hpp (original)
+++ trunk/boost/intrusive/detail/config_end.hpp 2008-12-13 08:56:15 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
 /////////////////////////////////////////////////////////////////////////////
 //
-// (C) Copyright Ion Gaztanaga 2006-2007
+// (C) Copyright Ion Gaztanaga 2006-2008
 //
 // Distributed under the Boost Software License, Version 1.0.
 // (See accompanying file LICENSE_1_0.txt or copy at

Modified: trunk/boost/intrusive/detail/ebo_functor_holder.hpp
==============================================================================
--- trunk/boost/intrusive/detail/ebo_functor_holder.hpp (original)
+++ trunk/boost/intrusive/detail/ebo_functor_holder.hpp 2008-12-13 08:56:15 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
 /////////////////////////////////////////////////////////////////////////////
 //
-// (C) Copyright Joaquin M Lopez Munoz 2006-2007
+// (C) Copyright Joaquin M Lopez Munoz 2006-2008
 //
 // Distributed under the Boost Software License, Version 1.0.
 // (See accompanying file LICENSE_1_0.txt or copy at

Modified: trunk/boost/intrusive/detail/generic_hook.hpp
==============================================================================
--- trunk/boost/intrusive/detail/generic_hook.hpp (original)
+++ trunk/boost/intrusive/detail/generic_hook.hpp 2008-12-13 08:56:15 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
 /////////////////////////////////////////////////////////////////////////////
 //
-// (C) Copyright Ion Gaztanaga 2007
+// (C) Copyright Ion Gaztanaga 2007-2008
 //
 // Distributed under the Boost Software License, Version 1.0.
 // (See accompanying file LICENSE_1_0.txt or copy at

Modified: trunk/boost/intrusive/detail/hashtable_node.hpp
==============================================================================
--- trunk/boost/intrusive/detail/hashtable_node.hpp (original)
+++ trunk/boost/intrusive/detail/hashtable_node.hpp 2008-12-13 08:56:15 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
 /////////////////////////////////////////////////////////////////////////////
 //
-// (C) Copyright Ion Gaztanaga 2007
+// (C) Copyright Ion Gaztanaga 2007-2008
 //
 // Distributed under the Boost Software License, Version 1.0.
 // (See accompanying file LICENSE_1_0.txt or copy at

Modified: trunk/boost/intrusive/detail/list_node.hpp
==============================================================================
--- trunk/boost/intrusive/detail/list_node.hpp (original)
+++ trunk/boost/intrusive/detail/list_node.hpp 2008-12-13 08:56:15 EST (Sat, 13 Dec 2008)
@@ -1,7 +1,7 @@
 /////////////////////////////////////////////////////////////////////////////
 //
 // (C) Copyright Olaf Krzikalla 2004-2006.
-// (C) Copyright Ion Gaztanaga 2006-2007
+// (C) Copyright Ion Gaztanaga 2006-2008
 //
 // Distributed under the Boost Software License, Version 1.0.
 // (See accompanying file LICENSE_1_0.txt or copy at

Modified: trunk/boost/intrusive/detail/mpl.hpp
==============================================================================
--- trunk/boost/intrusive/detail/mpl.hpp (original)
+++ trunk/boost/intrusive/detail/mpl.hpp 2008-12-13 08:56:15 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
 /////////////////////////////////////////////////////////////////////////////
 //
-// (C) Copyright Ion Gaztanaga 2006-2007
+// (C) Copyright Ion Gaztanaga 2006-2008
 //
 // Distributed under the Boost Software License, Version 1.0.
 // (See accompanying file LICENSE_1_0.txt or copy at
@@ -129,7 +129,7 @@
 #define BOOST_INTRUSIVE_TT_DECL
 #endif
 
-#if defined(_MSC_EXTENSIONS) && !defined(__BORLAND__)
+#if defined(_MSC_EXTENSIONS) && !defined(__BORLAND__) && !defined(_WIN64)
 #define BOOST_INTRUSIVE_TT_TEST_MSC_FUNC_SIGS
 #endif
 

Modified: trunk/boost/intrusive/detail/parent_from_member.hpp
==============================================================================
--- trunk/boost/intrusive/detail/parent_from_member.hpp (original)
+++ trunk/boost/intrusive/detail/parent_from_member.hpp 2008-12-13 08:56:15 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
 /////////////////////////////////////////////////////////////////////////////
 //
-// (C) Copyright Ion Gaztanaga 2007
+// (C) Copyright Ion Gaztanaga 2007-2008
 //
 // Distributed under the Boost Software License, Version 1.0.
 // (See accompanying file LICENSE_1_0.txt or copy at

Modified: trunk/boost/intrusive/detail/rbtree_node.hpp
==============================================================================
--- trunk/boost/intrusive/detail/rbtree_node.hpp (original)
+++ trunk/boost/intrusive/detail/rbtree_node.hpp 2008-12-13 08:56:15 EST (Sat, 13 Dec 2008)
@@ -1,7 +1,7 @@
 /////////////////////////////////////////////////////////////////////////////
 //
 // (C) Copyright Olaf Krzikalla 2004-2006.
-// (C) Copyright Ion Gaztanaga 2006-2007.
+// (C) Copyright Ion Gaztanaga 2006-2008.
 //
 // Distributed under the Boost Software License, Version 1.0.
 // (See accompanying file LICENSE_1_0.txt or copy at

Modified: trunk/boost/intrusive/detail/slist_node.hpp
==============================================================================
--- trunk/boost/intrusive/detail/slist_node.hpp (original)
+++ trunk/boost/intrusive/detail/slist_node.hpp 2008-12-13 08:56:15 EST (Sat, 13 Dec 2008)
@@ -1,7 +1,7 @@
 /////////////////////////////////////////////////////////////////////////////
 //
 // (C) Copyright Olaf Krzikalla 2004-2006.
-// (C) Copyright Ion Gaztanaga 2006-2007
+// (C) Copyright Ion Gaztanaga 2006-2008
 //
 // Distributed under the Boost Software License, Version 1.0.
 // (See accompanying file LICENSE_1_0.txt or copy at

Modified: trunk/boost/intrusive/detail/transform_iterator.hpp
==============================================================================
--- trunk/boost/intrusive/detail/transform_iterator.hpp (original)
+++ trunk/boost/intrusive/detail/transform_iterator.hpp 2008-12-13 08:56:15 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
 /////////////////////////////////////////////////////////////////////////////
 //
-// (C) Copyright Ion Gaztanaga 2007
+// (C) Copyright Ion Gaztanaga 2007-2008
 //
 // Distributed under the Boost Software License, Version 1.0.
 // (See accompanying file LICENSE_1_0.txt or copy at

Modified: trunk/boost/intrusive/detail/tree_algorithms.hpp
==============================================================================
--- trunk/boost/intrusive/detail/tree_algorithms.hpp (original)
+++ trunk/boost/intrusive/detail/tree_algorithms.hpp 2008-12-13 08:56:15 EST (Sat, 13 Dec 2008)
@@ -721,22 +721,6 @@
 
    static bool is_header(const_node_ptr p)
    {
-/*
- node_ptr p_parent = NodeTraits::get_parent(p);
- if(!p_parent)
- return true;
- if(!NodeTraits::get_parent(p_parent) != p)
- return false;
- if(NodeTraits::get_left(p) != 0){
- if(NodeTraits::get_parent(NodeTraits::get_left(p)) != p){
- is_header = true;
- }
- if(NodeTraits::get_parent(p) == NodeTraits::get_left(p)){
- is_header = true;
- }
- }
-*/
-
       bool is_header = false;
       if(NodeTraits::get_parent(p) == p){
          is_header = true;
@@ -1015,42 +999,71 @@
       }
    }
 
- //! <b>Requires</b>: "header" must be the header node of a tree.
- //! NodePtrCompare is a function object that induces a strict weak
- //! ordering compatible with the strict weak ordering used to create the
- //! the tree. NodePtrCompare compares two node_ptrs. "hint" is node from
- //! the "header"'s tree.
- //!
- //! <b>Effects</b>: Inserts new_node into the tree, using "hint" as a hint to
- //! where it will be inserted. If "hint" is the upper_bound
- //! the insertion takes constant time (two comparisons in the worst case).
- //!
- //! <b>Complexity</b>: Logarithmic in general, but it is amortized
- //! constant time if new_node is inserted immediately before "hint".
- //!
- //! <b>Throws</b>: If "comp" throws.
    template<class NodePtrCompare>
- static node_ptr insert_equal
- (node_ptr header, node_ptr hint, node_ptr new_node, NodePtrCompare comp, std::size_t *pdepth = 0)
+ static void insert_equal_check
+ ( node_ptr header, node_ptr hint, node_ptr new_node, NodePtrCompare comp
+ , insert_commit_data &commit_data, std::size_t *pdepth = 0)
    {
       if(hint == header || !comp(hint, new_node)){
          node_ptr prev(hint);
          if(hint == NodeTraits::get_left(header) ||
             !comp(new_node, (prev = prev_node(hint)))){
             bool link_left = unique(header) || !NodeTraits::get_left(hint);
- link(header, new_node, link_left ? hint : prev, link_left);
- if(pdepth) *pdepth = depth(new_node) + 1;
- return new_node;
+ commit_data.link_left = link_left;
+ commit_data.node = link_left ? hint : prev;
+ if(pdepth){
+ *pdepth = commit_data.node == header ? 0 : depth(commit_data.node) + 1;
+ }
          }
          else{
- return insert_equal_upper_bound(header, new_node, comp, pdepth);
+ insert_equal_upper_bound_check(header, new_node, comp, commit_data, pdepth);
          }
       }
       else{
- return insert_equal_lower_bound(header, new_node, comp, pdepth);
+ insert_equal_lower_bound_check(header, new_node, comp, commit_data, pdepth);
       }
    }
 
+ template<class NodePtrCompare>
+ static void insert_equal_upper_bound_check
+ (node_ptr h, node_ptr new_node, NodePtrCompare comp, insert_commit_data & commit_data, std::size_t *pdepth = 0)
+ { insert_equal_check_impl(true, h, new_node, comp, commit_data, pdepth); }
+
+ template<class NodePtrCompare>
+ static void insert_equal_lower_bound_check
+ (node_ptr h, node_ptr new_node, NodePtrCompare comp, insert_commit_data & commit_data, std::size_t *pdepth = 0)
+ { insert_equal_check_impl(false, h, new_node, comp, commit_data, pdepth); }
+
+ template<class NodePtrCompare>
+ static node_ptr insert_equal
+ (node_ptr h, node_ptr hint, node_ptr new_node, NodePtrCompare comp, std::size_t *pdepth = 0)
+ {
+ insert_commit_data commit_data;
+ insert_equal_check(h, hint, new_node, comp, commit_data, pdepth);
+ link(h, new_node, commit_data.node, commit_data.link_left);
+ return new_node;
+ }
+
+ template<class NodePtrCompare>
+ static node_ptr insert_equal_upper_bound
+ (node_ptr h, node_ptr new_node, NodePtrCompare comp, std::size_t *pdepth = 0)
+ {
+ insert_commit_data commit_data;
+ insert_equal_upper_bound_check(h, new_node, comp, commit_data, pdepth);
+ link(h, new_node, commit_data.node, commit_data.link_left);
+ return new_node;
+ }
+
+ template<class NodePtrCompare>
+ static node_ptr insert_equal_lower_bound
+ (node_ptr h, node_ptr new_node, NodePtrCompare comp, std::size_t *pdepth = 0)
+ {
+ insert_commit_data commit_data;
+ insert_equal_lower_bound_check(h, new_node, comp, commit_data, pdepth);
+ link(h, new_node, commit_data.node, commit_data.link_left);
+ return new_node;
+ }
+
    //! <b>Requires</b>: p can't be a header node.
    //!
    //! <b>Effects</b>: Calculates the depth of a node: the depth of a
@@ -1071,48 +1084,6 @@
       return depth;
    }
 
- template<class NodePtrCompare>
- static node_ptr insert_equal_upper_bound
- (node_ptr h, node_ptr new_node, NodePtrCompare comp, std::size_t *pdepth = 0)
- {
- std::size_t depth = 0;
- node_ptr y(h);
- node_ptr x(NodeTraits::get_parent(y));
-
- while(x){
- ++depth;
- y = x;
- x = comp(new_node, x) ?
- NodeTraits::get_left(x) : NodeTraits::get_right(x);
- }
-
- bool link_left = (y == h) || comp(new_node, y);
- link(h, new_node, y, link_left);
- if(pdepth) *pdepth = depth;
- return new_node;
- }
-
- template<class NodePtrCompare>
- static node_ptr insert_equal_lower_bound
- (node_ptr h, node_ptr new_node, NodePtrCompare comp, std::size_t *pdepth = 0)
- {
- std::size_t depth = 0;
- node_ptr y(h);
- node_ptr x(NodeTraits::get_parent(y));
-
- while(x){
- ++depth;
- y = x;
- x = !comp(x, new_node) ?
- NodeTraits::get_left(x) : NodeTraits::get_right(x);
- }
-
- bool link_left = (y == h) || !comp(y, new_node);
- link(h, new_node, y, link_left);
- if(pdepth) *pdepth = depth;
- return new_node;
- }
-
    //! <b>Requires</b>: "cloner" must be a function
    //! object taking a node_ptr and returning a new cloned node of it. "disposer" must
    //! take a node_ptr and shouldn't throw.
@@ -1557,6 +1528,39 @@
    }
 
    private:
+ template<class NodePtrCompare>
+ static void insert_equal_check_impl
+ (bool upper, node_ptr h, node_ptr new_node, NodePtrCompare comp, insert_commit_data & commit_data, std::size_t *pdepth = 0)
+ {
+ std::size_t depth = 0;
+ node_ptr y(h);
+ node_ptr x(NodeTraits::get_parent(y));
+ bool link_left;
+
+ if(upper){
+ while(x){
+ ++depth;
+ y = x;
+ x = comp(new_node, x) ?
+ NodeTraits::get_left(x) : NodeTraits::get_right(x);
+ }
+ link_left = (y == h) || comp(new_node, y);
+ }
+ else{
+ while(x){
+ ++depth;
+ y = x;
+ x = !comp(x, new_node) ?
+ NodeTraits::get_left(x) : NodeTraits::get_right(x);
+ }
+ link_left = (y == h) || !comp(y, new_node);
+ }
+
+ commit_data.link_left = link_left;
+ commit_data.node = y;
+ if(pdepth) *pdepth = depth;
+ }
+
    static void erase_impl(node_ptr header, node_ptr z, data_for_rebalance &info)
    {
       node_ptr y(z);

Modified: trunk/boost/intrusive/detail/tree_node.hpp
==============================================================================
--- trunk/boost/intrusive/detail/tree_node.hpp (original)
+++ trunk/boost/intrusive/detail/tree_node.hpp 2008-12-13 08:56:15 EST (Sat, 13 Dec 2008)
@@ -173,6 +173,9 @@
       return tree_iterator(node_algorithms::get_header(this->pointed_node()), this->get_container());
    }
 
+ tree_iterator<Container, false> unconst() const
+ { return tree_iterator<Container, false>(this->pointed_node(), this->get_container()); }
+
    private:
    struct members
       : public detail::select_constptr

Modified: trunk/boost/intrusive/detail/utilities.hpp
==============================================================================
--- trunk/boost/intrusive/detail/utilities.hpp (original)
+++ trunk/boost/intrusive/detail/utilities.hpp 2008-12-13 08:56:15 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
 /////////////////////////////////////////////////////////////////////////////
 //
-// (C) Copyright Ion Gaztanaga 2006-2007
+// (C) Copyright Ion Gaztanaga 2006-2008
 //
 // Distributed under the Boost Software License, Version 1.0.
 // (See accompanying file LICENSE_1_0.txt or copy at
@@ -211,20 +211,25 @@
 {
    typedef typename Container::real_value_traits real_value_traits;
    typedef typename real_value_traits::node_ptr node_ptr;
+ typedef typename real_value_traits::const_node_ptr const_node_ptr;
    typedef detail::ebo_functor_holder<KeyValueCompare> base_t;
    key_nodeptr_comp(KeyValueCompare kcomp, const Container *cont)
       : base_t(kcomp), cont_(cont)
    {}
 
    template<class KeyType>
- bool operator()(node_ptr node, const KeyType &key) const
+ bool operator()( const_node_ptr node, const KeyType &key
+ , typename enable_if_c
+ <!is_convertible<KeyType, const_node_ptr>::value>::type * = 0) const
    { return base_t::get()(*cont_->get_real_value_traits().to_value_ptr(node), key); }
 
    template<class KeyType>
- bool operator()(const KeyType &key, node_ptr node) const
+ bool operator()(const KeyType &key, const_node_ptr node
+ , typename enable_if_c
+ <!is_convertible<KeyType, const_node_ptr>::value>::type * = 0) const
    { return base_t::get()(key, *cont_->get_real_value_traits().to_value_ptr(node)); }
 
- bool operator()(node_ptr node1, node_ptr node2) const
+ bool operator()(const_node_ptr node1, const_node_ptr node2) const
    {
       return base_t::get()
          ( *cont_->get_real_value_traits().to_value_ptr(node1)


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