diff options
Diffstat (limited to 'boost/intrusive/detail/rbtree_node.hpp')
| -rw-r--r-- | boost/intrusive/detail/rbtree_node.hpp | 71 |
1 files changed, 47 insertions, 24 deletions
diff --git a/boost/intrusive/detail/rbtree_node.hpp b/boost/intrusive/detail/rbtree_node.hpp index b76582bb61..ab50509c25 100644 --- a/boost/intrusive/detail/rbtree_node.hpp +++ b/boost/intrusive/detail/rbtree_node.hpp @@ -1,7 +1,7 @@ ///////////////////////////////////////////////////////////////////////////// // // (C) Copyright Olaf Krzikalla 2004-2006. -// (C) Copyright Ion Gaztanaga 2006-2012. +// (C) Copyright Ion Gaztanaga 2006-2013. // // Distributed under the Boost Software License, Version 1.0. // (See accompanying file LICENSE_1_0.txt or copy at @@ -14,12 +14,16 @@ #ifndef BOOST_INTRUSIVE_RBTREE_NODE_HPP #define BOOST_INTRUSIVE_RBTREE_NODE_HPP +#if defined(_MSC_VER) +# pragma once +#endif + #include <boost/intrusive/detail/config_begin.hpp> -#include <iterator> -#include <boost/intrusive/pointer_traits.hpp> +#include <boost/intrusive/pointer_rebind.hpp> #include <boost/intrusive/rbtree_algorithms.hpp> #include <boost/intrusive/pointer_plus_bits.hpp> #include <boost/intrusive/detail/mpl.hpp> +#include <boost/intrusive/detail/tree_node.hpp> namespace boost { namespace intrusive { @@ -34,9 +38,9 @@ namespace intrusive { template<class VoidPointer> struct compact_rbtree_node { - typedef typename pointer_traits - <VoidPointer>::template rebind_pointer - <compact_rbtree_node<VoidPointer> >::type node_ptr; + typedef compact_rbtree_node<VoidPointer> node; + typedef typename pointer_rebind<VoidPointer, node >::type node_ptr; + typedef typename pointer_rebind<VoidPointer, const node >::type const_node_ptr; enum color { red_t, black_t }; node_ptr parent_, left_, right_; }; @@ -45,9 +49,9 @@ struct compact_rbtree_node template<class VoidPointer> struct rbtree_node { - typedef typename pointer_traits - <VoidPointer>::template rebind_pointer - <rbtree_node<VoidPointer> >::type node_ptr; + typedef rbtree_node<VoidPointer> node; + typedef typename pointer_rebind<VoidPointer, node >::type node_ptr; + typedef typename pointer_rebind<VoidPointer, const node >::type const_node_ptr; enum color { red_t, black_t }; node_ptr parent_, left_, right_; @@ -60,27 +64,33 @@ template<class VoidPointer> struct default_rbtree_node_traits_impl { typedef rbtree_node<VoidPointer> node; - - typedef typename pointer_traits - <VoidPointer>::template rebind_pointer<node>::type node_ptr; - typedef typename pointer_traits - <VoidPointer>::template rebind_pointer<const node>::type const_node_ptr; + typedef typename node::node_ptr node_ptr; + typedef typename node::const_node_ptr const_node_ptr; typedef typename node::color color; - static const node_ptr & get_parent(const const_node_ptr & n) + static node_ptr get_parent(const const_node_ptr & n) + { return n->parent_; } + + static node_ptr get_parent(const node_ptr & n) { return n->parent_; } static void set_parent(const node_ptr & n, const node_ptr & p) { n->parent_ = p; } - static const node_ptr & get_left(const const_node_ptr & n) + static node_ptr get_left(const const_node_ptr & n) + { return n->left_; } + + static node_ptr get_left(const node_ptr & n) { return n->left_; } static void set_left(const node_ptr & n, const node_ptr & l) { n->left_ = l; } - static const node_ptr & get_right(const const_node_ptr & n) + static node_ptr get_right(const const_node_ptr & n) + { return n->right_; } + + static node_ptr get_right(const node_ptr & n) { return n->right_; } static void set_right(const node_ptr & n, const node_ptr & r) @@ -89,6 +99,9 @@ struct default_rbtree_node_traits_impl static color get_color(const const_node_ptr & n) { return n->color_; } + static color get_color(const node_ptr & n) + { return n->color_; } + static void set_color(const node_ptr & n, color c) { n->color_ = c; } @@ -105,10 +118,8 @@ template<class VoidPointer> struct compact_rbtree_node_traits_impl { typedef compact_rbtree_node<VoidPointer> node; - typedef typename pointer_traits - <VoidPointer>::template rebind_pointer<node>::type node_ptr; - typedef typename pointer_traits - <VoidPointer>::template rebind_pointer<const node>::type const_node_ptr; + typedef typename node::node_ptr node_ptr; + typedef typename node::const_node_ptr const_node_ptr; typedef pointer_plus_bits<node_ptr, 1> ptr_bit; @@ -117,16 +128,25 @@ struct compact_rbtree_node_traits_impl static node_ptr get_parent(const const_node_ptr & n) { return ptr_bit::get_pointer(n->parent_); } + static node_ptr get_parent(const node_ptr & n) + { return ptr_bit::get_pointer(n->parent_); } + static void set_parent(const node_ptr & n, const node_ptr & p) { ptr_bit::set_pointer(n->parent_, p); } - static const node_ptr & get_left(const const_node_ptr & n) + static node_ptr get_left(const const_node_ptr & n) + { return n->left_; } + + static node_ptr get_left(const node_ptr & n) { return n->left_; } static void set_left(const node_ptr & n, const node_ptr & l) { n->left_ = l; } - static const node_ptr & get_right(const const_node_ptr & n) + static node_ptr get_right(const const_node_ptr & n) + { return n->right_; } + + static node_ptr get_right(const node_ptr & n) { return n->right_; } static void set_right(const node_ptr & n, const node_ptr & r) @@ -135,6 +155,9 @@ struct compact_rbtree_node_traits_impl static color get_color(const const_node_ptr & n) { return (color)ptr_bit::get_bits(n->parent_); } + static color get_color(const node_ptr & n) + { return (color)ptr_bit::get_bits(n->parent_); } + static void set_color(const node_ptr & n, color c) { ptr_bit::set_bits(n->parent_, c != 0); } @@ -156,7 +179,7 @@ struct rbtree_node_traits_dispatch<VoidPointer, true> : public compact_rbtree_node_traits_impl<VoidPointer> {}; -//Inherit from the detail::link_dispatch depending on the embedding capabilities +//Inherit from rbtree_node_traits_dispatch depending on the embedding capabilities template<class VoidPointer, bool OptimizeSize = false> struct rbtree_node_traits : public rbtree_node_traits_dispatch |