///////////////////////////////////////////////////////////////////////////// | |
// | |
// (C) Copyright Olaf Krzikalla 2004-2006. | |
// (C) Copyright Ion Gaztanaga 2006-2009. | |
// | |
// 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_RBTREE_NODE_HPP | |
#define BOOST_INTRUSIVE_RBTREE_NODE_HPP | |
#include <boost/intrusive/detail/config_begin.hpp> | |
#include <iterator> | |
#include <boost/intrusive/detail/pointer_to_other.hpp> | |
#include <boost/intrusive/rbtree_algorithms.hpp> | |
#include <boost/intrusive/pointer_plus_bits.hpp> | |
#include <boost/intrusive/detail/mpl.hpp> | |
namespace boost { | |
namespace intrusive { | |
///////////////////////////////////////////////////////////////////////////// | |
// // | |
// Generic node_traits for any pointer type // | |
// // | |
///////////////////////////////////////////////////////////////////////////// | |
//This is the compact representation: 3 pointers | |
template<class VoidPointer> | |
struct compact_rbtree_node | |
{ | |
typedef typename pointer_to_other | |
<VoidPointer | |
,compact_rbtree_node<VoidPointer> >::type node_ptr; | |
enum color { red_t, black_t }; | |
node_ptr parent_, left_, right_; | |
}; | |
//This is the normal representation: 3 pointers + enum | |
template<class VoidPointer> | |
struct rbtree_node | |
{ | |
typedef typename pointer_to_other | |
<VoidPointer | |
,rbtree_node<VoidPointer> >::type node_ptr; | |
enum color { red_t, black_t }; | |
node_ptr parent_, left_, right_; | |
color color_; | |
}; | |
//This is the default node traits implementation | |
//using a node with 3 generic pointers plus an enum | |
template<class VoidPointer> | |
struct default_rbtree_node_traits_impl | |
{ | |
typedef rbtree_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 typename node::color color; | |
static node_ptr get_parent(const_node_ptr n) | |
{ return n->parent_; } | |
static void set_parent(node_ptr n, node_ptr p) | |
{ n->parent_ = p; } | |
static node_ptr get_left(const_node_ptr n) | |
{ return n->left_; } | |
static void set_left(node_ptr n, node_ptr l) | |
{ n->left_ = l; } | |
static node_ptr get_right(const_node_ptr n) | |
{ return n->right_; } | |
static void set_right(node_ptr n, node_ptr r) | |
{ n->right_ = r; } | |
static color get_color(const_node_ptr n) | |
{ return n->color_; } | |
static void set_color(node_ptr n, color c) | |
{ n->color_ = c; } | |
static color black() | |
{ return node::black_t; } | |
static color red() | |
{ return node::red_t; } | |
}; | |
//This is the compact node traits implementation | |
//using a node with 3 generic pointers | |
template<class VoidPointer> | |
struct compact_rbtree_node_traits_impl | |
{ | |
typedef compact_rbtree_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 pointer_plus_bits<node_ptr, 1> ptr_bit; | |
typedef typename node::color color; | |
static node_ptr get_parent(const_node_ptr n) | |
{ return ptr_bit::get_pointer(n->parent_); } | |
static void set_parent(node_ptr n, node_ptr p) | |
{ ptr_bit::set_pointer(n->parent_, p); } | |
static node_ptr get_left(const_node_ptr n) | |
{ return n->left_; } | |
static void set_left(node_ptr n, node_ptr l) | |
{ n->left_ = l; } | |
static node_ptr get_right(const_node_ptr n) | |
{ return n->right_; } | |
static void set_right(node_ptr n, node_ptr r) | |
{ n->right_ = r; } | |
static color get_color(const_node_ptr n) | |
{ return (color)ptr_bit::get_bits(n->parent_); } | |
static void set_color(node_ptr n, color c) | |
{ ptr_bit::set_bits(n->parent_, c != 0); } | |
static color black() | |
{ return node::black_t; } | |
static color red() | |
{ return node::red_t; } | |
}; | |
//Dispatches the implementation based on the boolean | |
template<class VoidPointer, bool Compact> | |
struct rbtree_node_traits_dispatch | |
: public default_rbtree_node_traits_impl<VoidPointer> | |
{}; | |
template<class VoidPointer> | |
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 | |
template<class VoidPointer, bool OptimizeSize = false> | |
struct rbtree_node_traits | |
: public rbtree_node_traits_dispatch | |
< VoidPointer | |
, OptimizeSize && | |
(max_pointer_plus_bits | |
< VoidPointer | |
, detail::alignment_of<compact_rbtree_node<VoidPointer> >::value | |
>::value >= 1) | |
> | |
{}; | |
} //namespace intrusive | |
} //namespace boost | |
#include <boost/intrusive/detail/config_end.hpp> | |
#endif //BOOST_INTRUSIVE_RBTREE_NODE_HPP |