|
|
Boost-Commit : |
From: igaztanaga_at_[hidden]
Date: 2008-06-21 05:04:24
Author: igaztanaga
Date: 2008-06-21 05:04:21 EDT (Sat, 21 Jun 2008)
New Revision: 46571
URL: http://svn.boost.org/trac/boost/changeset/46571
Log:
gcc 4.3 fixes for normal and -std=c++0x modes
Added:
trunk/boost/intrusive/any_hook.hpp (contents, props changed)
trunk/boost/intrusive/detail/any_node_and_algorithms.hpp (contents, props changed)
Text files modified:
trunk/boost/intrusive/avltree_algorithms.hpp | 3
trunk/boost/intrusive/circular_list_algorithms.hpp | 1
trunk/boost/intrusive/circular_slist_algorithms.hpp | 1
trunk/boost/intrusive/detail/common_slist_algorithms.hpp | 3
trunk/boost/intrusive/detail/generic_hook.hpp | 53 +++++-----
trunk/boost/intrusive/detail/hashtable_node.hpp | 12 +-
trunk/boost/intrusive/detail/list_node.hpp | 1
trunk/boost/intrusive/detail/parent_from_member.hpp | 21 ++--
trunk/boost/intrusive/detail/slist_node.hpp | 1
trunk/boost/intrusive/detail/tree_algorithms.hpp | 7 -
trunk/boost/intrusive/detail/utilities.hpp | 19 +++
trunk/boost/intrusive/hashtable.hpp | 199 +++++++++++++++++++++++++--------------
trunk/boost/intrusive/intrusive_fwd.hpp | 17 +++
trunk/boost/intrusive/linear_slist_algorithms.hpp | 1
trunk/boost/intrusive/options.hpp | 94 ++++++++++++++----
trunk/boost/intrusive/rbtree_algorithms.hpp | 2
trunk/boost/intrusive/sgtree_algorithms.hpp | 2
trunk/boost/intrusive/splaytree_algorithms.hpp | 2
trunk/boost/intrusive/unordered_set.hpp | 18 ++-
trunk/boost/intrusive/unordered_set_hook.hpp | 29 +----
20 files changed, 311 insertions(+), 175 deletions(-)
Added: trunk/boost/intrusive/any_hook.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/intrusive/any_hook.hpp 2008-06-21 05:04:21 EDT (Sat, 21 Jun 2008)
@@ -0,0 +1,320 @@
+/////////////////////////////////////////////////////////////////////////////
+//
+// (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
+// http://www.boost.org/LICENSE_1_0.txt)
+//
+// See http://www.boost.org/libs/intrusive for documentation.
+//
+/////////////////////////////////////////////////////////////////////////////
+
+#ifndef BOOST_INTRUSIVE_ANY_HOOK_HPP
+#define BOOST_INTRUSIVE_ANY_HOOK_HPP
+
+#include <boost/intrusive/detail/config_begin.hpp>
+#include <boost/intrusive/intrusive_fwd.hpp>
+#include <boost/intrusive/detail/utilities.hpp>
+#include <boost/intrusive/detail/any_node_and_algorithms.hpp>
+#include <boost/intrusive/options.hpp>
+#include <boost/intrusive/detail/generic_hook.hpp>
+#include <boost/intrusive/detail/pointer_to_other.hpp>
+
+namespace boost {
+namespace intrusive {
+
+/// @cond
+template<class VoidPointer>
+struct get_any_node_algo
+{
+ typedef any_algorithms<VoidPointer> type;
+};
+/// @endcond
+
+//! Helper metafunction to define a \c \c any_base_hook that yields to the same
+//! type when the same options (either explicitly or implicitly) are used.
+#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
+template<class ...Options>
+#else
+template<class O1 = none, class O2 = none, class O3 = none>
+#endif
+struct make_any_base_hook
+{
+ /// @cond
+ typedef typename pack_options
+ < hook_defaults, O1, O2, O3>::type packed_options;
+
+ typedef detail::generic_hook
+ < get_any_node_algo<typename packed_options::void_pointer>
+ , typename packed_options::tag
+ , packed_options::link_mode
+ , detail::AnyBaseHook
+ > implementation_defined;
+ /// @endcond
+ typedef implementation_defined type;
+};
+
+//! Derive a class from this hook in order to store objects of that class
+//! in an intrusive container.
+//!
+//! The hook admits the following options: \c tag<>, \c void_pointer<> and
+//! \c link_mode<>.
+//!
+//! \c tag<> defines a tag to identify the node.
+//! The same tag value can be used in different classes, but if a class is
+//! derived from more than one \c any_base_hook, then each \c any_base_hook needs its
+//! unique tag.
+//!
+//! \c link_mode<> will specify the linking mode of the hook (\c normal_link, \c safe_link).
+//!
+//! \c void_pointer<> is the pointer type that will be used internally in the hook
+//! and the the container configured to use this hook.
+#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
+template<class ...Options>
+#else
+template<class O1, class O2, class O3>
+#endif
+class any_base_hook
+ : public make_any_base_hook<O1, O2, O3>::type
+{
+ #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
+ public:
+ //! <b>Effects</b>: If link_mode is or \c safe_link
+ //! initializes the node to an unlinked state.
+ //!
+ //! <b>Throws</b>: Nothing.
+ any_base_hook();
+
+ //! <b>Effects</b>: If link_mode is or \c safe_link
+ //! initializes the node to an unlinked state. The argument is ignored.
+ //!
+ //! <b>Throws</b>: Nothing.
+ //!
+ //! <b>Rationale</b>: Providing a copy-constructor
+ //! makes classes using the hook STL-compliant without forcing the
+ //! user to do some additional work. \c swap can be used to emulate
+ //! move-semantics.
+ any_base_hook(const any_base_hook& );
+
+ //! <b>Effects</b>: Empty function. The argument is ignored.
+ //!
+ //! <b>Throws</b>: Nothing.
+ //!
+ //! <b>Rationale</b>: Providing an assignment operator
+ //! makes classes using the hook STL-compliant without forcing the
+ //! user to do some additional work. \c swap can be used to emulate
+ //! move-semantics.
+ any_base_hook& operator=(const any_base_hook& );
+
+ //! <b>Effects</b>: If link_mode is \c normal_link, the destructor does
+ //! nothing (ie. no code is generated). If link_mode is \c safe_link and the
+ //! object is stored in a container an assertion is raised.
+ //!
+ //! <b>Throws</b>: Nothing.
+ ~any_base_hook();
+
+ //! <b>Precondition</b>: link_mode must be \c safe_link.
+ //!
+ //! <b>Returns</b>: true, if the node belongs to a container, false
+ //! otherwise. This function can be used to test whether \c container::iterator_to
+ //! will return a valid iterator.
+ //!
+ //! <b>Complexity</b>: Constant
+ bool is_linked() const;
+ #endif
+};
+
+//! Helper metafunction to define a \c \c any_member_hook that yields to the same
+//! type when the same options (either explicitly or implicitly) are used.
+#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
+template<class ...Options>
+#else
+template<class O1 = none, class O2 = none, class O3 = none>
+#endif
+struct make_any_member_hook
+{
+ /// @cond
+ typedef typename pack_options
+ < hook_defaults, O1, O2, O3>::type packed_options;
+
+ typedef detail::generic_hook
+ < get_any_node_algo<typename packed_options::void_pointer>
+ , member_tag
+ , packed_options::link_mode
+ , detail::NoBaseHook
+ > implementation_defined;
+ /// @endcond
+ typedef implementation_defined type;
+};
+
+//! Store this hook in a class to be inserted
+//! in an intrusive container.
+//!
+//! The hook admits the following options: \c void_pointer<> and
+//! \c link_mode<>.
+//!
+//! \c link_mode<> will specify the linking mode of the hook (\c normal_link or \c safe_link).
+//!
+//! \c void_pointer<> is the pointer type that will be used internally in the hook
+//! and the the container configured to use this hook.
+#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
+template<class ...Options>
+#else
+template<class O1, class O2, class O3>
+#endif
+class any_member_hook
+ : public make_any_member_hook<O1, O2, O3>::type
+{
+ #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
+ public:
+ //! <b>Effects</b>: If link_mode is or \c safe_link
+ //! initializes the node to an unlinked state.
+ //!
+ //! <b>Throws</b>: Nothing.
+ any_member_hook();
+
+ //! <b>Effects</b>: If link_mode is or \c safe_link
+ //! initializes the node to an unlinked state. The argument is ignored.
+ //!
+ //! <b>Throws</b>: Nothing.
+ //!
+ //! <b>Rationale</b>: Providing a copy-constructor
+ //! makes classes using the hook STL-compliant without forcing the
+ //! user to do some additional work. \c swap can be used to emulate
+ //! move-semantics.
+ any_member_hook(const any_member_hook& );
+
+ //! <b>Effects</b>: Empty function. The argument is ignored.
+ //!
+ //! <b>Throws</b>: Nothing.
+ //!
+ //! <b>Rationale</b>: Providing an assignment operator
+ //! makes classes using the hook STL-compliant without forcing the
+ //! user to do some additional work. \c swap can be used to emulate
+ //! move-semantics.
+ any_member_hook& operator=(const any_member_hook& );
+
+ //! <b>Effects</b>: If link_mode is \c normal_link, the destructor does
+ //! nothing (ie. no code is generated). If link_mode is \c safe_link and the
+ //! object is stored in a container an assertion is raised.
+ //!
+ //! <b>Throws</b>: Nothing.
+ ~any_member_hook();
+
+ //! <b>Precondition</b>: link_mode must be \c safe_link.
+ //!
+ //! <b>Returns</b>: true, if the node belongs to a container, false
+ //! otherwise. This function can be used to test whether \c container::iterator_to
+ //! will return a valid iterator.
+ //!
+ //! <b>Complexity</b>: Constant
+ bool is_linked() const;
+ #endif
+};
+
+/// @cond
+
+namespace detail{
+
+template<class ValueTraits>
+struct any_to_get_base_pointer_type
+{
+ typedef typename pointer_to_other
+ <typename ValueTraits::boost_intrusive_tags::node_traits::node_ptr, void>::type type;
+};
+
+template<class ValueTraits>
+struct any_to_get_member_pointer_type
+{
+ typedef typename pointer_to_other
+ <typename ValueTraits::node_ptr, void>::type type;
+};
+
+//!This option setter specifies that the container
+//!must use the specified base hook
+template<class BaseHook, template <class> class NodeTraits>
+struct any_to_some_hook
+{
+ typedef typename BaseHook::template pack<none>::value_traits old_value_traits;
+ template<class Base>
+ struct pack : public Base
+ {
+ struct value_traits : public old_value_traits
+ {
+ static const bool is_any_hook = true;
+ typedef typename detail::eval_if_c
+ < detail::internal_base_hook_bool_is_true<old_value_traits>::value
+ , any_to_get_base_pointer_type<old_value_traits>
+ , any_to_get_member_pointer_type<old_value_traits>
+ >::type void_pointer;
+ typedef NodeTraits<void_pointer> node_traits;
+ };
+ };
+};
+
+} //namespace detail{
+
+/// @endcond
+
+//!This option setter specifies that
+//!any hook should behave as an slist hook
+template<class BaseHook>
+struct any_to_slist_hook
+/// @cond
+ : public detail::any_to_some_hook<BaseHook, any_slist_node_traits>
+/// @endcond
+{};
+
+//!This option setter specifies that
+//!any hook should behave as an list hook
+template<class BaseHook>
+struct any_to_list_hook
+/// @cond
+ : public detail::any_to_some_hook<BaseHook, any_list_node_traits>
+/// @endcond
+{};
+
+//!This option setter specifies that
+//!any hook should behave as a set hook
+template<class BaseHook>
+struct any_to_set_hook
+/// @cond
+ : public detail::any_to_some_hook<BaseHook, any_rbtree_node_traits>
+/// @endcond
+{};
+
+//!This option setter specifies that
+//!any hook should behave as a set hook
+template<class BaseHook>
+struct any_to_avl_set_hook
+/// @cond
+ : public detail::any_to_some_hook<BaseHook, any_avltree_node_traits>
+/// @endcond
+{};
+
+//!This option setter specifies that any
+//!hook should behave as a set hook
+template<class BaseHook>
+struct any_to_bs_set_hook
+/// @cond
+ : public detail::any_to_some_hook<BaseHook, any_tree_node_traits>
+/// @endcond
+{};
+
+//!This option setter specifies that any hook
+//!should behave as an unordered set hook
+template<class BaseHook>
+struct any_to_unordered_set_hook
+/// @cond
+ : public detail::any_to_some_hook<BaseHook, any_unordered_node_traits>
+/// @endcond
+{};
+
+
+} //namespace intrusive
+} //namespace boost
+
+#include <boost/intrusive/detail/config_end.hpp>
+
+#endif //BOOST_INTRUSIVE_ANY_HOOK_HPP
Modified: trunk/boost/intrusive/avltree_algorithms.hpp
==============================================================================
--- trunk/boost/intrusive/avltree_algorithms.hpp (original)
+++ trunk/boost/intrusive/avltree_algorithms.hpp 2008-06-21 05:04:21 EDT (Sat, 21 Jun 2008)
@@ -68,6 +68,7 @@
class avltree_algorithms
{
public:
+ typedef typename NodeTraits::node node;
typedef NodeTraits node_traits;
typedef typename NodeTraits::node_ptr node_ptr;
typedef typename NodeTraits::const_node_ptr const_node_ptr;
@@ -75,8 +76,6 @@
/// @cond
private:
-
- typedef typename NodeTraits::node node;
typedef detail::tree_algorithms<NodeTraits> tree_algorithms;
template<class F>
Modified: trunk/boost/intrusive/circular_list_algorithms.hpp
==============================================================================
--- trunk/boost/intrusive/circular_list_algorithms.hpp (original)
+++ trunk/boost/intrusive/circular_list_algorithms.hpp 2008-06-21 05:04:21 EDT (Sat, 21 Jun 2008)
@@ -50,6 +50,7 @@
class circular_list_algorithms
{
public:
+ typedef typename NodeTraits::node node;
typedef typename NodeTraits::node_ptr node_ptr;
typedef typename NodeTraits::const_node_ptr const_node_ptr;
typedef NodeTraits node_traits;
Modified: trunk/boost/intrusive/circular_slist_algorithms.hpp
==============================================================================
--- trunk/boost/intrusive/circular_slist_algorithms.hpp (original)
+++ trunk/boost/intrusive/circular_slist_algorithms.hpp 2008-06-21 05:04:21 EDT (Sat, 21 Jun 2008)
@@ -54,6 +54,7 @@
typedef detail::common_slist_algorithms<NodeTraits> base_t;
/// @endcond
public:
+ typedef typename NodeTraits::node node;
typedef typename NodeTraits::node_ptr node_ptr;
typedef typename NodeTraits::const_node_ptr const_node_ptr;
typedef NodeTraits node_traits;
Added: trunk/boost/intrusive/detail/any_node_and_algorithms.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/intrusive/detail/any_node_and_algorithms.hpp 2008-06-21 05:04:21 EDT (Sat, 21 Jun 2008)
@@ -0,0 +1,292 @@
+/////////////////////////////////////////////////////////////////////////////
+//
+// (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
+// http://www.boost.org/LICENSE_1_0.txt)
+//
+// See http://www.boost.org/libs/intrusive for documentation.
+//
+/////////////////////////////////////////////////////////////////////////////
+
+#ifndef BOOST_INTRUSIVE_ANY_NODE_HPP
+#define BOOST_INTRUSIVE_ANY_NODE_HPP
+
+#include <boost/intrusive/detail/config_begin.hpp>
+#include <iterator>
+#include <boost/intrusive/detail/assert.hpp>
+#include <boost/intrusive/detail/pointer_to_other.hpp>
+#include <cstddef>
+
+namespace boost {
+namespace intrusive {
+
+template<class VoidPointer>
+struct any_node
+{
+ typedef typename boost::pointer_to_other
+ <VoidPointer, any_node>::type node_ptr;
+ node_ptr node_ptr_1;
+ node_ptr node_ptr_2;
+ node_ptr node_ptr_3;
+ std::size_t size_t_1;
+};
+
+template<class VoidPointer>
+struct any_list_node_traits
+{
+ typedef any_node<VoidPointer> node;
+ typedef typename boost::pointer_to_other
+ <VoidPointer, node>::type node_ptr;
+ typedef typename boost::pointer_to_other
+ <VoidPointer, const node>::type const_node_ptr;
+
+ static node_ptr get_next(const_node_ptr n)
+ { return n->node_ptr_1; }
+
+ static void set_next(node_ptr n, node_ptr next)
+ { n->node_ptr_1 = next; }
+
+ static node_ptr get_previous(const_node_ptr n)
+ { return n->node_ptr_2; }
+
+ static void set_previous(node_ptr n, node_ptr prev)
+ { n->node_ptr_2 = prev; }
+};
+
+
+template<class VoidPointer>
+struct any_slist_node_traits
+{
+ typedef any_node<VoidPointer> node;
+ typedef typename boost::pointer_to_other
+ <VoidPointer, node>::type node_ptr;
+ typedef typename boost::pointer_to_other
+ <VoidPointer, const node>::type const_node_ptr;
+
+ static node_ptr get_next(const_node_ptr n)
+ { return n->node_ptr_1; }
+
+ static void set_next(node_ptr n, node_ptr next)
+ { n->node_ptr_1 = next; }
+};
+
+
+template<class VoidPointer>
+struct any_unordered_node_traits
+ : public any_slist_node_traits<VoidPointer>
+{
+ typedef any_slist_node_traits<VoidPointer> reduced_slist_node_traits;
+ typedef typename reduced_slist_node_traits::node node;
+ typedef typename reduced_slist_node_traits::node_ptr node_ptr;
+ typedef typename reduced_slist_node_traits::const_node_ptr const_node_ptr;
+
+ static const bool store_hash = true;
+ static const bool optimize_multikey = true;
+
+ static node_ptr get_next(const_node_ptr n)
+ { return node_ptr(&static_cast<node &>(*n->node_ptr_1)); }
+
+ static void set_next(node_ptr n, node_ptr next)
+ { n->node_ptr_1 = next; }
+
+ static node_ptr get_prev_in_group(const_node_ptr n)
+ { return n->node_ptr_2; }
+
+ static void set_prev_in_group(node_ptr n, node_ptr prev)
+ { n->node_ptr_2 = prev; }
+
+ static std::size_t get_hash(const_node_ptr n)
+ { return n->size_t_1; }
+
+ static void set_hash(node_ptr n, std::size_t h)
+ { n->size_t_1 = h; }
+};
+
+
+template<class VoidPointer>
+struct any_rbtree_node_traits
+{
+ typedef any_node<VoidPointer> node;
+
+ typedef typename boost::pointer_to_other
+ <VoidPointer, node>::type node_ptr;
+ typedef typename boost::pointer_to_other
+ <VoidPointer, const node>::type const_node_ptr;
+
+ typedef std::size_t color;
+
+ static node_ptr get_parent(const_node_ptr n)
+ { return n->node_ptr_1; }
+
+ static void set_parent(node_ptr n, node_ptr p)
+ { n->node_ptr_1 = p; }
+
+ static node_ptr get_left(const_node_ptr n)
+ { return n->node_ptr_2; }
+
+ static void set_left(node_ptr n, node_ptr l)
+ { n->node_ptr_2 = l; }
+
+ static node_ptr get_right(const_node_ptr n)
+ { return n->node_ptr_3; }
+
+ static void set_right(node_ptr n, node_ptr r)
+ { n->node_ptr_3 = r; }
+
+ static color get_color(const_node_ptr n)
+ { return n->size_t_1; }
+
+ static void set_color(node_ptr n, color c)
+ { n->size_t_1 = c; }
+
+ static color black()
+ { return 0u; }
+
+ static color red()
+ { return 1u; }
+};
+
+
+template<class VoidPointer>
+struct any_avltree_node_traits
+{
+ typedef any_node<VoidPointer> node;
+
+ typedef typename boost::pointer_to_other
+ <VoidPointer, node>::type node_ptr;
+ typedef typename boost::pointer_to_other
+ <VoidPointer, const node>::type const_node_ptr;
+ typedef std::size_t balance;
+
+ static node_ptr get_parent(const_node_ptr n)
+ { return n->node_ptr_1; }
+
+ static void set_parent(node_ptr n, node_ptr p)
+ { n->node_ptr_1 = p; }
+
+ static node_ptr get_left(const_node_ptr n)
+ { return n->node_ptr_2; }
+
+ static void set_left(node_ptr n, node_ptr l)
+ { n->node_ptr_2 = l; }
+
+ static node_ptr get_right(const_node_ptr n)
+ { return n->node_ptr_3; }
+
+ static void set_right(node_ptr n, node_ptr r)
+ { n->node_ptr_3 = r; }
+
+ static balance get_balance(const_node_ptr n)
+ { return n->size_t_1; }
+
+ static void set_balance(node_ptr n, balance b)
+ { n->size_t_1 = b; }
+
+ static balance negative()
+ { return 0u; }
+
+ static balance zero()
+ { return 1u; }
+
+ static balance positive()
+ { return 2u; }
+};
+
+
+template<class VoidPointer>
+struct any_tree_node_traits
+{
+ typedef any_node<VoidPointer> node;
+
+ typedef typename boost::pointer_to_other
+ <VoidPointer, node>::type node_ptr;
+ typedef typename boost::pointer_to_other
+ <VoidPointer, const node>::type const_node_ptr;
+
+ static node_ptr get_parent(const_node_ptr n)
+ { return n->node_ptr_1; }
+
+ static void set_parent(node_ptr n, node_ptr p)
+ { n->node_ptr_1 = p; }
+
+ static node_ptr get_left(const_node_ptr n)
+ { return n->node_ptr_2; }
+
+ static void set_left(node_ptr n, node_ptr l)
+ { n->node_ptr_2 = l; }
+
+ static node_ptr get_right(const_node_ptr n)
+ { return n->node_ptr_3; }
+
+ static void set_right(node_ptr n, node_ptr r)
+ { n->node_ptr_3 = r; }
+};
+
+template<class VoidPointer>
+class any_node_traits
+{
+ public:
+ typedef any_node<VoidPointer> node;
+ typedef typename boost::pointer_to_other
+ <VoidPointer, node>::type node_ptr;
+ typedef typename boost::pointer_to_other
+ <VoidPointer, const node>::type const_node_ptr;
+};
+
+template<class VoidPointer>
+class any_algorithms
+{
+ public:
+ typedef any_node<VoidPointer> node;
+ typedef typename boost::pointer_to_other
+ <VoidPointer, node>::type node_ptr;
+ typedef typename boost::pointer_to_other
+ <VoidPointer, const node>::type const_node_ptr;
+ typedef any_node_traits<VoidPointer> node_traits;
+
+ //! <b>Requires</b>: node must not be part of any tree.
+ //!
+ //! <b>Effects</b>: After the function unique(node) == true.
+ //!
+ //! <b>Complexity</b>: Constant.
+ //!
+ //! <b>Throws</b>: Nothing.
+ //!
+ //! <b>Nodes</b>: If node is inserted in a tree, this function corrupts the tree.
+ static void init(node_ptr node)
+ { node->node_ptr_1 = 0; };
+
+ //! <b>Effects</b>: Returns true if node is in the same state as if called init(node)
+ //!
+ //! <b>Complexity</b>: Constant.
+ //!
+ //! <b>Throws</b>: Nothing.
+ static bool inited(const_node_ptr node)
+ { return !node->node_ptr_1; };
+
+ static bool unique(const_node_ptr node)
+ { return 0 == node->node_ptr_1; }
+
+ static void unlink(node_ptr)
+ {
+ //Auto-unlink hooks and unlink() call for safe hooks are not
+ //available for any hooks!!!
+ any_algorithms<VoidPointer>::unlink_not_available_for_any_hooks();
+ }
+
+ static void swap_nodes(node_ptr l, node_ptr r)
+ {
+ //Any nodes have no swap_nodes capability because they don't know
+ //what algorithm they must use from unlink them from the container
+ any_algorithms<VoidPointer>::swap_nodes_not_available_for_any_hooks();
+ }
+};
+
+} //namespace intrusive
+} //namespace boost
+
+#include <boost/intrusive/detail/config_end.hpp>
+
+#endif //BOOST_INTRUSIVE_ANY_NODE_HPP
Modified: trunk/boost/intrusive/detail/common_slist_algorithms.hpp
==============================================================================
--- trunk/boost/intrusive/detail/common_slist_algorithms.hpp (original)
+++ trunk/boost/intrusive/detail/common_slist_algorithms.hpp 2008-06-21 05:04:21 EDT (Sat, 21 Jun 2008)
@@ -26,6 +26,7 @@
class common_slist_algorithms
{
public:
+ typedef typename NodeTraits::node node;
typedef typename NodeTraits::node_ptr node_ptr;
typedef typename NodeTraits::const_node_ptr const_node_ptr;
typedef NodeTraits node_traits;
@@ -53,7 +54,7 @@
{
node_ptr next = NodeTraits::get_next(this_node);
return !next || next == this_node;
- }
+ }
static bool inited(const_node_ptr this_node)
{ return !NodeTraits::get_next(this_node); }
Modified: trunk/boost/intrusive/detail/generic_hook.hpp
==============================================================================
--- trunk/boost/intrusive/detail/generic_hook.hpp (original)
+++ trunk/boost/intrusive/detail/generic_hook.hpp 2008-06-21 05:04:21 EDT (Sat, 21 Jun 2008)
@@ -18,6 +18,7 @@
#include <boost/intrusive/detail/pointer_to_other.hpp>
#include <boost/intrusive/link_mode.hpp>
#include <boost/intrusive/detail/utilities.hpp>
+#include <boost/intrusive/detail/mpl.hpp>
#include <boost/static_assert.hpp>
namespace boost {
@@ -35,6 +36,7 @@
, SplaySetBaseHook
, AvlSetBaseHook
, BsSetBaseHook
+, AnyBaseHook
};
struct no_default_definer{};
@@ -70,6 +72,10 @@
struct default_definer<Hook, BsSetBaseHook>
{ typedef Hook default_bs_set_hook; };
+template <class Hook>
+struct default_definer<Hook, AnyBaseHook>
+{ typedef Hook default_any_hook; };
+
template <class Hook, unsigned int BaseHookType>
struct make_default_definer
{
@@ -90,11 +96,11 @@
typedef typename detail::if_c
<!detail::is_same<Tag, member_tag>::value
, detail::node_holder
- < typename GetNodeAlgorithms::type::node_traits::node
+ < typename GetNodeAlgorithms::type::node
, Tag
, LinkMode
, HookType>
- , typename GetNodeAlgorithms::type::node_traits::node
+ , typename GetNodeAlgorithms::type::node
>::type type;
};
@@ -122,38 +128,38 @@
, public make_node_holder<GetNodeAlgorithms, Tag, LinkMode, HookType>::type
/// @endcond
{
- public:
/// @cond
+ typedef typename GetNodeAlgorithms::type node_algorithms;
+ typedef typename node_algorithms::node node;
+ typedef typename node_algorithms::node_ptr node_ptr;
+ typedef typename node_algorithms::const_node_ptr const_node_ptr;
+
+ public:
struct boost_intrusive_tags
{
static const int hook_type = HookType;
static const link_mode_type link_mode = LinkMode;
- typedef Tag tag;
- typedef typename GetNodeAlgorithms::type node_algorithms;
- typedef typename node_algorithms::node_traits node_traits;
- typedef typename node_traits::node node;
- typedef typename node_traits::node_ptr node_ptr;
- typedef typename node_traits::const_node_ptr const_node_ptr;
+ typedef Tag tag;
+ typedef typename GetNodeAlgorithms::type::node_traits node_traits;
static const bool is_base_hook = !detail::is_same<Tag, member_tag>::value;
- enum { safemode_or_autounlink =
- (int)link_mode == (int)auto_unlink ||
- (int)link_mode == (int)safe_link };
+ static const bool safemode_or_autounlink =
+ (int)link_mode == (int)auto_unlink || (int)link_mode == (int)safe_link;
};
+
+ public:
/// @endcond
generic_hook()
{
if(boost_intrusive_tags::safemode_or_autounlink){
- boost_intrusive_tags::node_algorithms::init
- (static_cast<typename boost_intrusive_tags::node*>(this));
+ node_algorithms::init(static_cast<node*>(this));
}
}
generic_hook(const generic_hook& )
{
if(boost_intrusive_tags::safemode_or_autounlink){
- boost_intrusive_tags::node_algorithms::init
- (static_cast<typename boost_intrusive_tags::node*>(this));
+ node_algorithms::init(static_cast<node*>(this));
}
}
@@ -168,26 +174,23 @@
void swap_nodes(generic_hook &other)
{
- boost_intrusive_tags::node_algorithms::swap_nodes
- ( static_cast<typename boost_intrusive_tags::node*>(this)
- , static_cast<typename boost_intrusive_tags::node*>(&other));
+ node_algorithms::swap_nodes
+ ( static_cast<node*>(this), static_cast<node*>(&other));
}
bool is_linked() const
{
//is_linked() can be only used in safe-mode or auto-unlink
BOOST_STATIC_ASSERT(( boost_intrusive_tags::safemode_or_autounlink ));
- return !boost_intrusive_tags::node_algorithms::unique
- (static_cast<const typename boost_intrusive_tags::node*>(this));
+ return !node_algorithms::unique
+ (static_cast<const node*>(this));
}
void unlink()
{
BOOST_STATIC_ASSERT(( (int)boost_intrusive_tags::link_mode == (int)auto_unlink ));
- boost_intrusive_tags::node_algorithms::unlink
- (static_cast<typename boost_intrusive_tags::node*>(this));
- boost_intrusive_tags::node_algorithms::init
- (static_cast<typename boost_intrusive_tags::node*>(this));
+ node_algorithms::unlink(static_cast<node*>(this));
+ node_algorithms::init(static_cast<node*>(this));
}
};
Modified: trunk/boost/intrusive/detail/hashtable_node.hpp
==============================================================================
--- trunk/boost/intrusive/detail/hashtable_node.hpp (original)
+++ trunk/boost/intrusive/detail/hashtable_node.hpp 2008-06-21 05:04:21 EDT (Sat, 21 Jun 2008)
@@ -104,13 +104,13 @@
<typename Container::value_type, IsConst>::type
>
{
- typedef typename Container::real_value_traits real_value_traits;
- typedef typename Container::siterator siterator;
- typedef typename Container::const_siterator const_siterator;
- typedef typename Container::bucket_type bucket_type;
+ typedef typename Container::real_value_traits real_value_traits;
+ typedef typename Container::siterator siterator;
+ typedef typename Container::const_siterator const_siterator;
+ typedef typename Container::bucket_type bucket_type;
typedef typename boost::pointer_to_other
- < typename Container::pointer, const Container>::type const_cont_ptr;
- typedef typename Container::size_type size_type;
+ < typename Container::pointer, const Container>::type const_cont_ptr;
+ typedef typename Container::size_type size_type;
static typename Container::node_ptr downcast_bucket(typename bucket_type::node_ptr p)
{ return typename Container::node_ptr(&static_cast<typename Container::node&>(*p)); }
Modified: trunk/boost/intrusive/detail/list_node.hpp
==============================================================================
--- trunk/boost/intrusive/detail/list_node.hpp (original)
+++ trunk/boost/intrusive/detail/list_node.hpp 2008-06-21 05:04:21 EDT (Sat, 21 Jun 2008)
@@ -18,7 +18,6 @@
#include <iterator>
#include <boost/intrusive/detail/assert.hpp>
#include <boost/intrusive/detail/pointer_to_other.hpp>
-#include <boost/intrusive/circular_list_algorithms.hpp>
namespace boost {
namespace intrusive {
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-06-21 05:04:21 EDT (Sat, 21 Jun 2008)
@@ -13,12 +13,11 @@
#define BOOST_INTRUSIVE_PARENT_FROM_MEMBER_HPP
#include <boost/intrusive/detail/config_begin.hpp>
-#include <boost/static_assert.hpp>
#include <cstddef>
#if defined(BOOST_MSVC) || (defined (BOOST_WINDOWS) && defined(BOOST_INTEL))
-#define BOOST_INTRUSIVE_OFFSET_FROM_PTR2MEMBER_MSVC_COMPLIANT
-#include <boost/cstdint.hpp>
+#define BOOST_INTRUSIVE_MSVC_COMPLIANT_PTR_TO_MEMBER
+#include <boost/cstdint.hpp>
#endif
namespace boost {
@@ -26,16 +25,18 @@
namespace detail {
template<class Parent, class Member>
-inline std::size_t offset_from_pointer_to_member(const Member Parent::* ptr_to_member)
+inline std::ptrdiff_t offset_from_pointer_to_member(const Member Parent::* ptr_to_member)
{
//The implementation of a pointer to member is compiler dependent.
- #if defined(BOOST_INTRUSIVE_OFFSET_FROM_PTR2MEMBER_MSVC_COMPLIANT)
- //This works with gcc, msvc, ac++, ibmcpp
+ #if defined(BOOST_INTRUSIVE_MSVC_COMPLIANT_PTR_TO_MEMBER)
+ //msvc compliant compilers use their the first 32 bits as offset (even in 64 bit mode)
return *(const boost::int32_t*)(void*)&ptr_to_member;
- #elif defined(__GNUC__) || defined(__HP_aCC) || defined(BOOST_INTEL) || defined (__IBMCPP__) || defined (__DECCXX)
+ //This works with gcc, msvc, ac++, ibmcpp
+ #elif defined(__GNUC__) || defined(__HP_aCC) || defined(BOOST_INTEL) || \
+ defined(__IBMCPP__) || defined(__DECCXX)
const Parent * const parent = 0;
const char *const member = reinterpret_cast<const char*>(&(parent->*ptr_to_member));
- return std::size_t(member - reinterpret_cast<const char*>(parent));
+ return std::ptrdiff_t(member - reinterpret_cast<const char*>(parent));
#else
//This is the traditional C-front approach: __MWERKS__, __DMC__, __SUNPRO_CC
return (*(const std::ptrdiff_t*)(void*)&ptr_to_member) - 1;
@@ -60,8 +61,8 @@
} //namespace intrusive {
} //namespace boost {
-#ifdef BOOST_INTRUSIVE_OFFSET_FROM_PTR2MEMBER_MSVC_COMPLIANT
-#undef BOOST_INTRUSIVE_OFFSET_FROM_PTR2MEMBER_MSVC_COMPLIANT
+#ifdef BOOST_INTRUSIVE_MSVC_COMPLIANT_PTR_TO_MEMBER
+#undef BOOST_INTRUSIVE_MSVC_COMPLIANT_PTR_TO_MEMBER
#endif
#include <boost/intrusive/detail/config_end.hpp>
Modified: trunk/boost/intrusive/detail/slist_node.hpp
==============================================================================
--- trunk/boost/intrusive/detail/slist_node.hpp (original)
+++ trunk/boost/intrusive/detail/slist_node.hpp 2008-06-21 05:04:21 EDT (Sat, 21 Jun 2008)
@@ -18,7 +18,6 @@
#include <iterator>
#include <boost/intrusive/detail/assert.hpp>
#include <boost/intrusive/detail/pointer_to_other.hpp>
-#include <boost/intrusive/circular_slist_algorithms.hpp>
namespace boost {
namespace intrusive {
Modified: trunk/boost/intrusive/detail/tree_algorithms.hpp
==============================================================================
--- trunk/boost/intrusive/detail/tree_algorithms.hpp (original)
+++ trunk/boost/intrusive/detail/tree_algorithms.hpp 2008-06-21 05:04:21 EDT (Sat, 21 Jun 2008)
@@ -94,13 +94,8 @@
template<class NodeTraits>
class tree_algorithms
{
- /// @cond
- private:
-
- typedef typename NodeTraits::node node;
- /// @endcond
-
public:
+ typedef typename NodeTraits::node node;
typedef NodeTraits node_traits;
typedef typename NodeTraits::node_ptr node_ptr;
typedef typename NodeTraits::const_node_ptr const_node_ptr;
Modified: trunk/boost/intrusive/detail/utilities.hpp
==============================================================================
--- trunk/boost/intrusive/detail/utilities.hpp (original)
+++ trunk/boost/intrusive/detail/utilities.hpp 2008-06-21 05:04:21 EDT (Sat, 21 Jun 2008)
@@ -25,6 +25,7 @@
#include <climits>
#include <iterator>
#include <boost/cstdint.hpp>
+#include <boost/static_assert.hpp>
namespace boost {
namespace intrusive {
@@ -56,6 +57,24 @@
};
template <class T>
+struct internal_any_hook_bool
+{
+ template<bool Add>
+ struct two_or_three {one _[2 + Add];};
+ template <class U> static one test(...);
+ template <class U> static two_or_three<U::is_any_hook>
+ test (detail::bool_<U::is_any_hook>* = 0);
+ static const std::size_t value = sizeof(test<T>(0));
+};
+
+template <class T>
+struct internal_any_hook_bool_is_true
+{
+ static const bool value = internal_any_hook_bool<T>::value > sizeof(one)*2;
+};
+
+
+template <class T>
struct external_value_traits_bool
{
template<bool Add>
Modified: trunk/boost/intrusive/hashtable.hpp
==============================================================================
--- trunk/boost/intrusive/hashtable.hpp (original)
+++ trunk/boost/intrusive/hashtable.hpp 2008-06-21 05:04:21 EDT (Sat, 21 Jun 2008)
@@ -83,9 +83,8 @@
};
template<class SupposedValueTraits>
-struct unordered_bucket_impl
+struct real_from_supposed_value_traits
{
- /// @cond
typedef typename detail::eval_if_c
< detail::external_value_traits_is_true
<SupposedValueTraits>::value
@@ -93,15 +92,33 @@
<SupposedValueTraits>
, detail::identity
<SupposedValueTraits>
- >::type real_value_traits;
+ >::type type;
+};
+template<class SupposedValueTraits>
+struct get_slist_impl_from_supposed_value_traits
+{
+ typedef typename
+ real_from_supposed_value_traits
+ < SupposedValueTraits>::type real_value_traits;
typedef typename detail::get_node_traits
<real_value_traits>::type node_traits;
typedef typename get_slist_impl
<typename reduced_slist_node_traits
<node_traits>::type
- >::type slist_impl;
+ >::type type;
+};
+
+
+template<class SupposedValueTraits>
+struct unordered_bucket_impl
+{
+ /// @cond
+ typedef typename
+ get_slist_impl_from_supposed_value_traits
+ <SupposedValueTraits>::type slist_impl;
typedef detail::bucket_impl<slist_impl> implementation_defined;
+ /// @endcond
typedef implementation_defined type;
};
@@ -109,15 +126,6 @@
struct unordered_bucket_ptr_impl
{
/// @cond
-
- typedef typename detail::eval_if_c
- < detail::external_value_traits_is_true
- <SupposedValueTraits>::value
- , detail::eval_value_traits
- <SupposedValueTraits>
- , detail::identity
- <SupposedValueTraits>
- >::type real_value_traits;
typedef typename detail::get_node_traits
<SupposedValueTraits>::type::node_ptr node_ptr;
typedef typename unordered_bucket_impl
@@ -128,36 +136,6 @@
typedef implementation_defined type;
};
-} //namespace detail {
-
-/// @endcond
-
-template<class ValueTraitsOrHookOption>
-struct unordered_bucket
-{
- /// @cond
- typedef typename ValueTraitsOrHookOption::
- template pack<none>::value_traits supposed_value_traits;
- /// @endcond
- typedef typename detail::unordered_bucket_impl
- <supposed_value_traits>::type type;
-};
-
-template<class ValueTraitsOrHookOption>
-struct unordered_bucket_ptr
-{
- /// @cond
- typedef typename ValueTraitsOrHookOption::
- template pack<none>::value_traits supposed_value_traits;
- /// @endcond
- typedef typename detail::unordered_bucket_ptr_impl
- <supposed_value_traits>::type type;
-};
-
-/// @cond
-
-namespace detail{
-
template <class T>
struct store_hash_bool
{
@@ -275,8 +253,6 @@
std::size_t hash;
};
-} //namespace detail {
-
template <class T>
struct internal_default_uset_hook
{
@@ -285,6 +261,49 @@
static const bool value = sizeof(test<T>(0)) == sizeof(detail::two);
};
+} //namespace detail {
+
+//!This metafunction will obtain the type of a bucket
+//!from the value_traits or hook option to be used with
+//!a hash container.
+template<class ValueTraitsOrHookOption>
+struct unordered_bucket
+ : public detail::unordered_bucket_impl
+ <typename ValueTraitsOrHookOption::
+ template pack<none>::value_traits
+ >
+{};
+
+//!This metafunction will obtain the type of a bucket pointer
+//!from the value_traits or hook option to be used with
+//!a hash container.
+template<class ValueTraitsOrHookOption>
+struct unordered_bucket_ptr
+ : public detail::unordered_bucket_ptr_impl
+ <typename ValueTraitsOrHookOption::
+ template pack<none>::value_traits
+ >
+{};
+
+//!This metafunction will obtain the type of the default bucket traits
+//!(when the user does not specify the bucket_traits<> option) from the
+//!value_traits or hook option to be used with
+//!a hash container.
+template<class ValueTraitsOrHookOption>
+struct unordered_default_bucket_traits
+{
+ /// @cond
+ typedef typename ValueTraitsOrHookOption::
+ template pack<none>::value_traits supposed_value_traits;
+ typedef typename detail::
+ get_slist_impl_from_supposed_value_traits
+ <supposed_value_traits>::type slist_impl;
+ typedef detail::bucket_traits_impl
+ <slist_impl> implementation_defined;
+ /// @endcond
+ typedef implementation_defined type;
+};
+
template <class T>
struct get_default_uset_hook
{
@@ -300,6 +319,7 @@
, class BucketTraits
, bool Power2Buckets
, bool CacheBegin
+ , bool CompareHash
>
struct usetopt
{
@@ -312,6 +332,7 @@
static const bool power_2_buckets = Power2Buckets;
static const bool unique_keys = UniqueKeys;
static const bool cache_begin = CacheBegin;
+ static const bool compare_hash = CompareHash;
};
struct default_bucket_traits;
@@ -322,7 +343,7 @@
< none
, base_hook
< typename detail::eval_if_c
- < internal_default_uset_hook<T>::value
+ < detail::internal_default_uset_hook<T>::value
, get_default_uset_hook<T>
, detail::identity<none>
>::type
@@ -334,6 +355,7 @@
, bucket_traits<default_bucket_traits>
, power_2_buckets<false>
, cache_begin<false>
+ , compare_hash<false>
>::type
{};
@@ -441,17 +463,21 @@
= detail::optimize_multikey_is_true<node_traits>::value && !unique_keys;
static const bool power_2_buckets = Config::power_2_buckets;
static const bool cache_begin = Config::cache_begin;
+ static const bool compare_hash = Config::compare_hash;
/// @cond
private:
+ //Configuration error: compare_hash<> can't be specified without store_hash<>
+ //See documentation for more explanations
+ BOOST_STATIC_ASSERT((!compare_hash || store_hash));
+
typedef typename slist_impl::node_ptr slist_node_ptr;
typedef typename boost::pointer_to_other
<slist_node_ptr, void>::type void_pointer;
//We'll define group traits, but these won't be instantiated if
//optimize_multikey is not true
- typedef unordered_group_node_traits<void_pointer, node> group_traits;
+ typedef unordered_group_adapter<node_traits> group_traits;
typedef circular_slist_algorithms<group_traits> group_algorithms;
-
typedef detail::bool_<store_hash> store_hash_t;
typedef detail::bool_<optimize_multikey> optimize_multikey_t;
typedef detail::bool_<cache_begin> cache_begin_t;
@@ -831,7 +857,11 @@
if(!found_equal){
it = b.before_begin();
}
- this->priv_insert_in_group(found_equal ? dcast_bucket_ptr(it.pointed_node()) : node_ptr(0), n, optimize_multikey_t());
+ if(optimize_multikey){
+ node_ptr first_in_group = found_equal ?
+ dcast_bucket_ptr(it.pointed_node()) : node_ptr(0);
+ this->priv_insert_in_group(first_in_group, n, optimize_multikey_t());
+ }
priv_insertion_update_cache(bucket_num);
this->priv_size_traits().increment();
return iterator(b.insert_after(it, *n), this);
@@ -1136,10 +1166,10 @@
,KeyValueEqual equal_func, Disposer disposer)
{
size_type bucket_num;
- std::size_t hash;
+ std::size_t h;
siterator prev;
siterator it =
- this->priv_find(key, hash_func, equal_func, bucket_num, hash, prev);
+ this->priv_find(key, hash_func, equal_func, bucket_num, h, prev);
bool success = it != priv_invalid_local_it();
size_type count(0);
if(!success){
@@ -1156,7 +1186,14 @@
bucket_type &b = this->priv_buckets()[bucket_num];
for(siterator end = b.end(); it != end; ++count, ++it){
slist_node_ptr n(it.pointed_node());
- if(!equal_func(key, priv_value_from_slist_node(n))){
+ const value_type &v = priv_value_from_slist_node(n);
+ if(compare_hash){
+ std::size_t vh = this->priv_stored_hash(v, store_hash_t());
+ if(h != vh || !equal_func(key, v)){
+ break;
+ }
+ }
+ else if(!equal_func(key, v)){
break;
}
this->priv_size_traits().decrement();
@@ -1657,7 +1694,7 @@
BOOST_INTRUSIVE_INVARIANT_ASSERT
(!power_2_buckets || (0 == (new_buckets_len & (new_buckets_len-1u))));
- size_type n = this->priv_get_cache() - this->priv_buckets();
+ size_type n = priv_get_cache_bucket_num();
const bool same_buffer = old_buckets == new_buckets;
//If the new bucket length is a common factor
//of the old one we can avoid hash calculations.
@@ -1665,8 +1702,10 @@
(power_2_buckets ||(old_buckets_len % new_buckets_len) == 0);
//If we are shrinking the same bucket array and it's
//is a fast shrink, just rehash the last nodes
- if(same_buffer && fast_shrink){
+ size_type new_first_bucket_num = new_buckets_len;
+ if(same_buffer && fast_shrink && (n < new_buckets_len)){
n = new_buckets_len;
+ new_first_bucket_num = priv_get_cache_bucket_num();
}
//Anti-exception stuff: they destroy the elements if something goes wrong
@@ -1696,6 +1735,8 @@
const value_type &v = priv_value_from_slist_node(i.pointed_node());
const std::size_t hash_value = this->priv_stored_hash(v, store_hash_t());
const size_type new_n = priv_hash_to_bucket(hash_value, new_buckets_len);
+ if(cache_begin && new_n < new_first_bucket_num)
+ new_first_bucket_num = new_n;
siterator last = bucket_type::s_iterator_to
(*priv_get_last_in_group(dcast_bucket_ptr(i.pointed_node())));
if(same_buffer && new_n == n){
@@ -1710,6 +1751,8 @@
}
else{
const size_type new_n = priv_hash_to_bucket(n, new_buckets_len);
+ if(cache_begin && new_n < new_first_bucket_num)
+ new_first_bucket_num = new_n;
bucket_type &new_b = new_buckets[new_n];
if(!old_bucket.empty()){
new_b.splice_after( new_b.before_begin()
@@ -1723,8 +1766,8 @@
this->priv_size_traits().set_size(size_backup);
this->priv_real_bucket_traits() = new_bucket_traits;
priv_initialize_cache();
- priv_insertion_update_cache(size_type(0u));
- priv_erasure_update_cache();
+ priv_insertion_update_cache(new_first_bucket_num);
+ //priv_erasure_update_cache();
rollback1.release();
rollback2.release();
}
@@ -1912,16 +1955,16 @@
static node_ptr dcast_bucket_ptr(typename slist_impl::node_ptr p)
{ return node_ptr(&static_cast<node&>(*p)); }
- std::size_t priv_stored_hash(const value_type &v, detail::true_)
+ std::size_t priv_stored_hash(const value_type &v, detail::true_) const
{ return node_traits::get_hash(this->get_real_value_traits().to_node_ptr(v)); }
- std::size_t priv_stored_hash(const value_type &v, detail::false_)
+ std::size_t priv_stored_hash(const value_type &v, detail::false_) const
{ return priv_hasher()(v); }
- std::size_t priv_stored_hash(slist_node_ptr n, detail::true_)
+ std::size_t priv_stored_hash(slist_node_ptr n, detail::true_) const
{ return node_traits::get_hash(dcast_bucket_ptr(n)); }
- std::size_t priv_stored_hash(slist_node_ptr, detail::false_)
+ std::size_t priv_stored_hash(slist_node_ptr, detail::false_) const
{
//This code should never be reached!
BOOST_INTRUSIVE_INVARIANT_ASSERT(0);
@@ -2414,7 +2457,13 @@
while(it != b.end()){
const value_type &v = priv_value_from_slist_node(it.pointed_node());
- if(equal_func(key, v)){
+ if(compare_hash){
+ std::size_t vh = this->priv_stored_hash(v, store_hash_t());
+ if(h == vh && equal_func(key, v)){
+ return it;
+ }
+ }
+ else if(equal_func(key, v)){
return it;
}
if(optimize_multikey){
@@ -2470,7 +2519,15 @@
++it;
while(it != b.end()){
const value_type &v = priv_value_from_slist_node(it.pointed_node());
- if(!equal_func(key, v)){
+ if(compare_hash){
+ std::size_t hv = this->priv_stored_hash(v, store_hash_t());
+ if(hv != h || !equal_func(key, v)){
+ to_return.second = it;
+ bucket_number_second = bucket_number_first;
+ return to_return;
+ }
+ }
+ else if(!equal_func(key, v)){
to_return.second = it;
bucket_number_second = bucket_number_first;
return to_return;
@@ -2505,11 +2562,12 @@
, class O3 = none, class O4 = none
, class O5 = none, class O6 = none
, class O7 = none, class O8 = none
+ , class O9 = none
>
struct make_hashtable_opt
{
typedef typename pack_options
- < uset_defaults<T>, O1, O2, O3, O4, O5, O6, O7, O8>::type packed_options;
+ < uset_defaults<T>, O1, O2, O3, O4, O5, O6, O7, O8, O9>::type packed_options;
//Real value traits must be calculated from options
typedef typename detail::get_value_traits
@@ -2529,10 +2587,7 @@
typedef typename detail::get_slist_impl
<typename detail::reduced_slist_node_traits
<typename real_value_traits::node_traits>::type
- >::type slist_impl;
-
- typedef typename detail::reduced_slist_node_traits
- <typename real_value_traits::node_traits>::type node_traits;
+ >::type slist_impl;
typedef typename
detail::if_c< detail::is_same
@@ -2553,6 +2608,7 @@
, real_bucket_traits
, packed_options::power_2_buckets
, packed_options::cache_begin
+ , packed_options::compare_hash
> type;
};
/// @endcond
@@ -2566,6 +2622,7 @@
, class O3 = none, class O4 = none
, class O5 = none, class O6 = none
, class O7 = none, class O8 = none
+ , class O9 = none
>
#endif
struct make_hashtable
@@ -2573,7 +2630,7 @@
/// @cond
typedef hashtable_impl
< typename make_hashtable_opt
- <T, false, O1, O2, O3, O4, O5, O6, O7, O8>::type
+ <T, false, O1, O2, O3, O4, O5, O6, O7, O8, O9>::type
> implementation_defined;
/// @endcond
@@ -2581,12 +2638,12 @@
};
#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
-template<class T, class O1, class O2, class O3, class O4, class O5, class O6, class O7, class O8>
+template<class T, class O1, class O2, class O3, class O4, class O5, class O6, class O7, class O8, class O9>
class hashtable
- : public make_hashtable<T, O1, O2, O3, O4, O5, O6, O7, O8>::type
+ : public make_hashtable<T, O1, O2, O3, O4, O5, O6, O7, O8, O9>::type
{
typedef typename make_hashtable
- <T, O1, O2, O3, O4, O5, O6, O7, O8>::type Base;
+ <T, O1, O2, O3, O4, O5, O6, O7, O8, O9>::type Base;
public:
typedef typename Base::value_traits value_traits;
Modified: trunk/boost/intrusive/intrusive_fwd.hpp
==============================================================================
--- trunk/boost/intrusive/intrusive_fwd.hpp (original)
+++ trunk/boost/intrusive/intrusive_fwd.hpp 2008-06-21 05:04:21 EDT (Sat, 21 Jun 2008)
@@ -294,6 +294,7 @@
, class O6 = none
, class O7 = none
, class O8 = none
+ , class O9 = none
>
class hashtable;
@@ -307,6 +308,7 @@
, class O6 = none
, class O7 = none
, class O8 = none
+ , class O9 = none
>
class unordered_set;
@@ -320,6 +322,7 @@
, class O6 = none
, class O7 = none
, class O8 = none
+ , class O9 = none
>
class unordered_multiset;
@@ -339,6 +342,20 @@
>
class unordered_set_member_hook;
+template
+ < class O1 = none
+ , class O2 = none
+ , class O3 = none
+ >
+class any_base_hook;
+
+template
+ < class O1 = none
+ , class O2 = none
+ , class O3 = none
+ >
+class any_member_hook;
+
} //namespace intrusive {
} //namespace boost {
Modified: trunk/boost/intrusive/linear_slist_algorithms.hpp
==============================================================================
--- trunk/boost/intrusive/linear_slist_algorithms.hpp (original)
+++ trunk/boost/intrusive/linear_slist_algorithms.hpp 2008-06-21 05:04:21 EDT (Sat, 21 Jun 2008)
@@ -53,6 +53,7 @@
typedef detail::common_slist_algorithms<NodeTraits> base_t;
/// @endcond
public:
+ typedef typename NodeTraits::node node;
typedef typename NodeTraits::node_ptr node_ptr;
typedef typename NodeTraits::const_node_ptr const_node_ptr;
typedef NodeTraits node_traits;
Modified: trunk/boost/intrusive/options.hpp
==============================================================================
--- trunk/boost/intrusive/options.hpp (original)
+++ trunk/boost/intrusive/options.hpp 2008-06-21 05:04:21 EDT (Sat, 21 Jun 2008)
@@ -49,15 +49,56 @@
typedef typename BucketTraits::bucket_traits type;
};
-template<class T, class BaseHook>
-struct get_base_value_traits
+template <class T, class BaseHook>
+struct concrete_hook_base_value_traits
+{
+ typedef typename BaseHook::boost_intrusive_tags tags;
+ typedef detail::base_hook_traits
+ < T
+ , typename tags::node_traits
+ , tags::link_mode
+ , typename tags::tag
+ , tags::hook_type> type;
+};
+
+template <class BaseHook>
+struct concrete_hook_base_node_traits
+{ typedef typename BaseHook::boost_intrusive_tags::node_traits type; };
+
+template <class T, class BaseHook>
+struct any_hook_base_value_traits
{
+ typedef typename BaseHook::boost_intrusive_tags tags;
typedef detail::base_hook_traits
< T
- , typename BaseHook::boost_intrusive_tags::node_traits
- , BaseHook::boost_intrusive_tags::link_mode
- , typename BaseHook::boost_intrusive_tags::tag
- , BaseHook::boost_intrusive_tags::hook_type> type;
+ , typename BaseHook::node_traits
+ , tags::link_mode
+ , typename tags::tag
+ , tags::hook_type> type;
+};
+
+template <class BaseHook>
+struct any_hook_base_node_traits
+{ typedef typename BaseHook::node_traits type; };
+
+template<class T, class BaseHook>
+struct get_base_value_traits
+{
+ typedef typename detail::eval_if_c
+ < internal_any_hook_bool_is_true<BaseHook>::value
+ , any_hook_base_value_traits<T, BaseHook>
+ , concrete_hook_base_value_traits<T, BaseHook>
+ >::type type;
+};
+
+template<class BaseHook>
+struct get_base_node_traits
+{
+ typedef typename detail::eval_if_c
+ < internal_any_hook_bool_is_true<BaseHook>::value
+ , any_hook_base_node_traits<BaseHook>
+ , concrete_hook_base_node_traits<BaseHook>
+ >::type type;
};
template<class T, class MemberHook>
@@ -66,6 +107,12 @@
typedef typename MemberHook::member_value_traits type;
};
+template<class MemberHook>
+struct get_member_node_traits
+{
+ typedef typename MemberHook::member_value_traits::node_traits type;
+};
+
template<class T, class SupposedValueTraits>
struct get_value_traits
{
@@ -86,25 +133,12 @@
>::type type;
};
-template<class BaseHook>
-struct get_base_node_traits
-{
- typedef typename BaseHook::boost_intrusive_tags::node_traits type;
-};
-
-template<class MemberHook>
-struct get_member_node_traits
-{
- typedef typename MemberHook::member_value_traits::node_traits type;
-};
-
template<class ValueTraits>
struct get_explicit_node_traits
{
typedef typename ValueTraits::node_traits type;
};
-
template<class SupposedValueTraits>
struct get_node_traits
{
@@ -125,7 +159,6 @@
>::type type;
};
-
} //namespace detail{
@@ -258,7 +291,6 @@
struct member_hook
{
/// @cond
- typedef char Parent::* GenericPtrToMember;
typedef detail::member_hook_traits
< Parent
, MemberHook
@@ -272,6 +304,7 @@
/// @endcond
};
+
//!This option setter specifies that the container
//!must use the specified base hook
template<typename BaseHook>
@@ -457,6 +490,25 @@
/// @endcond
};
+
+//!This option setter specifies if the container will compare the hash value
+//!before comparing objects. This option can't be specified if store_hash<>
+//!is not true.
+//!This is specially helpful when we have containers with a high load factor.
+//!and the comparison function is much more expensive that comparing already
+//!stored hash values.
+template<bool Enabled>
+struct compare_hash
+{
+/// @cond
+ template<class Base>
+ struct pack : Base
+ {
+ static const bool compare_hash = Enabled;
+ };
+/// @endcond
+};
+
/// @cond
template<class Prev, class Next>
Modified: trunk/boost/intrusive/rbtree_algorithms.hpp
==============================================================================
--- trunk/boost/intrusive/rbtree_algorithms.hpp (original)
+++ trunk/boost/intrusive/rbtree_algorithms.hpp 2008-06-21 05:04:21 EDT (Sat, 21 Jun 2008)
@@ -116,6 +116,7 @@
{
public:
typedef NodeTraits node_traits;
+ typedef typename NodeTraits::node node;
typedef typename NodeTraits::node_ptr node_ptr;
typedef typename NodeTraits::const_node_ptr const_node_ptr;
typedef typename NodeTraits::color color;
@@ -123,7 +124,6 @@
/// @cond
private:
- typedef typename NodeTraits::node node;
typedef detail::tree_algorithms<NodeTraits> tree_algorithms;
template<class F>
Modified: trunk/boost/intrusive/sgtree_algorithms.hpp
==============================================================================
--- trunk/boost/intrusive/sgtree_algorithms.hpp (original)
+++ trunk/boost/intrusive/sgtree_algorithms.hpp 2008-06-21 05:04:21 EDT (Sat, 21 Jun 2008)
@@ -58,6 +58,7 @@
class sgtree_algorithms
{
public:
+ typedef typename NodeTraits::node node;
typedef NodeTraits node_traits;
typedef typename NodeTraits::node_ptr node_ptr;
typedef typename NodeTraits::const_node_ptr const_node_ptr;
@@ -65,7 +66,6 @@
/// @cond
private:
- typedef typename NodeTraits::node node;
typedef detail::tree_algorithms<NodeTraits> tree_algorithms;
static node_ptr uncast(const_node_ptr ptr)
Modified: trunk/boost/intrusive/splaytree_algorithms.hpp
==============================================================================
--- trunk/boost/intrusive/splaytree_algorithms.hpp (original)
+++ trunk/boost/intrusive/splaytree_algorithms.hpp 2008-06-21 05:04:21 EDT (Sat, 21 Jun 2008)
@@ -130,11 +130,11 @@
{
/// @cond
private:
- typedef typename NodeTraits::node node;
typedef detail::tree_algorithms<NodeTraits> tree_algorithms;
/// @endcond
public:
+ typedef typename NodeTraits::node node;
typedef NodeTraits node_traits;
typedef typename NodeTraits::node_ptr node_ptr;
typedef typename NodeTraits::const_node_ptr const_node_ptr;
Modified: trunk/boost/intrusive/unordered_set.hpp
==============================================================================
--- trunk/boost/intrusive/unordered_set.hpp (original)
+++ trunk/boost/intrusive/unordered_set.hpp 2008-06-21 05:04:21 EDT (Sat, 21 Jun 2008)
@@ -961,6 +961,7 @@
, class O3 = none, class O4 = none
, class O5 = none, class O6 = none
, class O7 = none, class O8 = none
+ , class O9 = none
>
#endif
struct make_unordered_set
@@ -968,19 +969,19 @@
/// @cond
typedef unordered_set_impl
< typename make_hashtable_opt
- <T, true, O1, O2, O3, O4, O5, O6, O7, O8>::type
+ <T, true, O1, O2, O3, O4, O5, O6, O7, O8, O9>::type
> implementation_defined;
/// @endcond
typedef implementation_defined type;
};
#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
-template<class T, class O1, class O2, class O3, class O4, class O5, class O6, class O7, class O8>
+template<class T, class O1, class O2, class O3, class O4, class O5, class O6, class O7, class O8, class O9>
class unordered_set
- : public make_unordered_set<T, O1, O2, O3, O4, O5, O6, O7, O8>::type
+ : public make_unordered_set<T, O1, O2, O3, O4, O5, O6, O7, O8, O9>::type
{
typedef typename make_unordered_set
- <T, O1, O2, O3, O4, O5, O6, O7, O8>::type Base;
+ <T, O1, O2, O3, O4, O5, O6, O7, O8, O9>::type Base;
//Assert if passed value traits are compatible with the type
BOOST_STATIC_ASSERT((detail::is_same<typename Base::value_traits::value_type, T>::value));
@@ -1894,6 +1895,7 @@
, class O3 = none, class O4 = none
, class O5 = none, class O6 = none
, class O7 = none, class O8 = none
+ , class O9 = none
>
#endif
struct make_unordered_multiset
@@ -1901,19 +1903,19 @@
/// @cond
typedef unordered_multiset_impl
< typename make_hashtable_opt
- <T, false, O1, O2, O3, O4, O5, O6, O7, O8>::type
+ <T, false, O1, O2, O3, O4, O5, O6, O7, O8, O9>::type
> implementation_defined;
/// @endcond
typedef implementation_defined type;
};
#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
-template<class T, class O1, class O2, class O3, class O4, class O5, class O6, class O7, class O8>
+template<class T, class O1, class O2, class O3, class O4, class O5, class O6, class O7, class O8, class O9>
class unordered_multiset
- : public make_unordered_multiset<T, O1, O2, O3, O4, O5, O6, O7, O8>::type
+ : public make_unordered_multiset<T, O1, O2, O3, O4, O5, O6, O7, O8, O9>::type
{
typedef typename make_unordered_multiset
- <T, O1, O2, O3, O4, O5, O6, O7, O8>::type Base;
+ <T, O1, O2, O3, O4, O5, O6, O7, O8, O9>::type Base;
//Assert if passed value traits are compatible with the type
BOOST_STATIC_ASSERT((detail::is_same<typename Base::value_traits::value_type, T>::value));
Modified: trunk/boost/intrusive/unordered_set_hook.hpp
==============================================================================
--- trunk/boost/intrusive/unordered_set_hook.hpp (original)
+++ trunk/boost/intrusive/unordered_set_hook.hpp 2008-06-21 05:04:21 EDT (Sat, 21 Jun 2008)
@@ -35,7 +35,6 @@
< VoidPointer
, unordered_node<VoidPointer, StoreHash, OptimizeMultiKey>
>::type node_ptr;
-// node_ptr next_;
node_ptr prev_in_group_;
std::size_t hash_;
};
@@ -48,7 +47,6 @@
< VoidPointer
, unordered_node<VoidPointer, false, true>
>::type node_ptr;
-// node_ptr next_;
node_ptr prev_in_group_;
};
@@ -60,7 +58,6 @@
< VoidPointer
, unordered_node<VoidPointer, true, false>
>::type node_ptr;
-// node_ptr next_;
std::size_t hash_;
};
@@ -97,34 +94,26 @@
{ n->hash_ = h; }
};
-template<class VoidPointer, class Node>
-struct unordered_group_node_traits
+template<class NodeTraits>
+struct unordered_group_adapter
{
- typedef Node node;
- typedef typename boost::pointer_to_other
- <VoidPointer, node>::type node_ptr;
- typedef typename boost::pointer_to_other
- <VoidPointer, const node>::type const_node_ptr;
+ typedef typename NodeTraits::node node;
+ typedef typename NodeTraits::node_ptr node_ptr;
+ typedef typename NodeTraits::const_node_ptr const_node_ptr;
static node_ptr get_next(const_node_ptr n)
- { return n->prev_in_group_; }
+ { return NodeTraits::get_prev_in_group(n); }
static void set_next(node_ptr n, node_ptr next)
- { n->prev_in_group_ = next; }
+ { NodeTraits::set_prev_in_group(n, next); }
};
template<class NodeTraits>
struct unordered_algorithms
: public circular_slist_algorithms<NodeTraits>
{
- typedef circular_slist_algorithms<NodeTraits> base_type;
- typedef unordered_group_node_traits
- < typename boost::pointer_to_other
- < typename NodeTraits::node_ptr
- , void
- >::type
- , typename NodeTraits::node
- > group_traits;
+ typedef circular_slist_algorithms<NodeTraits> base_type;
+ typedef unordered_group_adapter<NodeTraits> group_traits;
typedef circular_slist_algorithms<group_traits> group_algorithms;
static void init(typename base_type::node_ptr n)
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