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)