1 ///////////////////////////////////////////////////////////////////////////// 2 // 3 // (C) Copyright Olaf Krzikalla 2004-2006. 4 // (C) Copyright Ion Gaztanaga 2006-2013. 5 // 6 // Distributed under the Boost Software License, Version 1.0. 7 // (See accompanying file LICENSE_1_0.txt or copy at 8 // http://www.boost.org/LICENSE_1_0.txt) 9 // 10 // See http://www.boost.org/libs/intrusive for documentation. 11 // 12 ///////////////////////////////////////////////////////////////////////////// 13 14 #ifndef BOOST_INTRUSIVE_RBTREE_NODE_HPP 15 #define BOOST_INTRUSIVE_RBTREE_NODE_HPP 16 17 #ifndef BOOST_CONFIG_HPP 18 # include <boost/config.hpp> 19 #endif 20 21 #if defined(BOOST_HAS_PRAGMA_ONCE) 22 # pragma once 23 #endif 24 25 #include <boost/intrusive/detail/config_begin.hpp> 26 #include <boost/intrusive/detail/workaround.hpp> 27 #include <boost/intrusive/pointer_rebind.hpp> 28 #include <boost/intrusive/rbtree_algorithms.hpp> 29 #include <boost/intrusive/pointer_plus_bits.hpp> 30 #include <boost/intrusive/detail/mpl.hpp> 31 #include <boost/intrusive/detail/tree_node.hpp> 32 33 namespace boost { 34 namespace intrusive { 35 36 ///////////////////////////////////////////////////////////////////////////// 37 // // 38 // Generic node_traits for any pointer type // 39 // // 40 ///////////////////////////////////////////////////////////////////////////// 41 42 //This is the compact representation: 3 pointers 43 template<class VoidPointer> 44 struct compact_rbtree_node 45 { 46 typedef compact_rbtree_node<VoidPointer> node; 47 typedef typename pointer_rebind<VoidPointer, node >::type node_ptr; 48 typedef typename pointer_rebind<VoidPointer, const node >::type const_node_ptr; 49 enum color { red_t, black_t }; 50 node_ptr parent_, left_, right_; 51 }; 52 53 //This is the normal representation: 3 pointers + enum 54 template<class VoidPointer> 55 struct rbtree_node 56 { 57 typedef rbtree_node<VoidPointer> node; 58 typedef typename pointer_rebind<VoidPointer, node >::type node_ptr; 59 typedef typename pointer_rebind<VoidPointer, const node >::type const_node_ptr; 60 61 enum color { red_t, black_t }; 62 node_ptr parent_, left_, right_; 63 color color_; 64 }; 65 66 //This is the default node traits implementation 67 //using a node with 3 generic pointers plus an enum 68 template<class VoidPointer> 69 struct default_rbtree_node_traits_impl 70 { 71 typedef rbtree_node<VoidPointer> node; 72 typedef typename node::node_ptr node_ptr; 73 typedef typename node::const_node_ptr const_node_ptr; 74 75 typedef typename node::color color; 76 get_parentboost::intrusive::default_rbtree_node_traits_impl77 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const const_node_ptr & n) 78 { return n->parent_; } 79 get_parentboost::intrusive::default_rbtree_node_traits_impl80 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const node_ptr & n) 81 { return n->parent_; } 82 set_parentboost::intrusive::default_rbtree_node_traits_impl83 BOOST_INTRUSIVE_FORCEINLINE static void set_parent(node_ptr n, node_ptr p) 84 { n->parent_ = p; } 85 get_leftboost::intrusive::default_rbtree_node_traits_impl86 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const const_node_ptr & n) 87 { return n->left_; } 88 get_leftboost::intrusive::default_rbtree_node_traits_impl89 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const node_ptr & n) 90 { return n->left_; } 91 set_leftboost::intrusive::default_rbtree_node_traits_impl92 BOOST_INTRUSIVE_FORCEINLINE static void set_left(node_ptr n, node_ptr l) 93 { n->left_ = l; } 94 get_rightboost::intrusive::default_rbtree_node_traits_impl95 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const const_node_ptr & n) 96 { return n->right_; } 97 get_rightboost::intrusive::default_rbtree_node_traits_impl98 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const node_ptr & n) 99 { return n->right_; } 100 set_rightboost::intrusive::default_rbtree_node_traits_impl101 BOOST_INTRUSIVE_FORCEINLINE static void set_right(node_ptr n, node_ptr r) 102 { n->right_ = r; } 103 get_colorboost::intrusive::default_rbtree_node_traits_impl104 BOOST_INTRUSIVE_FORCEINLINE static color get_color(const const_node_ptr & n) 105 { return n->color_; } 106 get_colorboost::intrusive::default_rbtree_node_traits_impl107 BOOST_INTRUSIVE_FORCEINLINE static color get_color(const node_ptr & n) 108 { return n->color_; } 109 set_colorboost::intrusive::default_rbtree_node_traits_impl110 BOOST_INTRUSIVE_FORCEINLINE static void set_color(const node_ptr & n, color c) 111 { n->color_ = c; } 112 blackboost::intrusive::default_rbtree_node_traits_impl113 BOOST_INTRUSIVE_FORCEINLINE static color black() 114 { return node::black_t; } 115 redboost::intrusive::default_rbtree_node_traits_impl116 BOOST_INTRUSIVE_FORCEINLINE static color red() 117 { return node::red_t; } 118 }; 119 120 //This is the compact node traits implementation 121 //using a node with 3 generic pointers 122 template<class VoidPointer> 123 struct compact_rbtree_node_traits_impl 124 { 125 typedef compact_rbtree_node<VoidPointer> node; 126 typedef typename node::node_ptr node_ptr; 127 typedef typename node::const_node_ptr const_node_ptr; 128 129 typedef pointer_plus_bits<node_ptr, 1> ptr_bit; 130 131 typedef typename node::color color; 132 get_parentboost::intrusive::compact_rbtree_node_traits_impl133 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const const_node_ptr & n) 134 { return ptr_bit::get_pointer(n->parent_); } 135 get_parentboost::intrusive::compact_rbtree_node_traits_impl136 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const node_ptr & n) 137 { return ptr_bit::get_pointer(n->parent_); } 138 set_parentboost::intrusive::compact_rbtree_node_traits_impl139 BOOST_INTRUSIVE_FORCEINLINE static void set_parent(node_ptr n, node_ptr p) 140 { ptr_bit::set_pointer(n->parent_, p); } 141 get_leftboost::intrusive::compact_rbtree_node_traits_impl142 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const const_node_ptr & n) 143 { return n->left_; } 144 get_leftboost::intrusive::compact_rbtree_node_traits_impl145 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const node_ptr & n) 146 { return n->left_; } 147 set_leftboost::intrusive::compact_rbtree_node_traits_impl148 BOOST_INTRUSIVE_FORCEINLINE static void set_left(node_ptr n, node_ptr l) 149 { n->left_ = l; } 150 get_rightboost::intrusive::compact_rbtree_node_traits_impl151 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const const_node_ptr & n) 152 { return n->right_; } 153 get_rightboost::intrusive::compact_rbtree_node_traits_impl154 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const node_ptr & n) 155 { return n->right_; } 156 set_rightboost::intrusive::compact_rbtree_node_traits_impl157 BOOST_INTRUSIVE_FORCEINLINE static void set_right(node_ptr n, node_ptr r) 158 { n->right_ = r; } 159 get_colorboost::intrusive::compact_rbtree_node_traits_impl160 BOOST_INTRUSIVE_FORCEINLINE static color get_color(const const_node_ptr & n) 161 { return (color)ptr_bit::get_bits(n->parent_); } 162 get_colorboost::intrusive::compact_rbtree_node_traits_impl163 BOOST_INTRUSIVE_FORCEINLINE static color get_color(const node_ptr & n) 164 { return (color)ptr_bit::get_bits(n->parent_); } 165 set_colorboost::intrusive::compact_rbtree_node_traits_impl166 BOOST_INTRUSIVE_FORCEINLINE static void set_color(const node_ptr & n, color c) 167 { ptr_bit::set_bits(n->parent_, c != 0); } 168 blackboost::intrusive::compact_rbtree_node_traits_impl169 BOOST_INTRUSIVE_FORCEINLINE static color black() 170 { return node::black_t; } 171 redboost::intrusive::compact_rbtree_node_traits_impl172 BOOST_INTRUSIVE_FORCEINLINE static color red() 173 { return node::red_t; } 174 }; 175 176 //Dispatches the implementation based on the boolean 177 template<class VoidPointer, bool Compact> 178 struct rbtree_node_traits_dispatch 179 : public default_rbtree_node_traits_impl<VoidPointer> 180 {}; 181 182 template<class VoidPointer> 183 struct rbtree_node_traits_dispatch<VoidPointer, true> 184 : public compact_rbtree_node_traits_impl<VoidPointer> 185 {}; 186 187 //Inherit from rbtree_node_traits_dispatch depending on the embedding capabilities 188 template<class VoidPointer, bool OptimizeSize = false> 189 struct rbtree_node_traits 190 : public rbtree_node_traits_dispatch 191 < VoidPointer 192 , OptimizeSize && 193 (max_pointer_plus_bits 194 < VoidPointer 195 , detail::alignment_of<compact_rbtree_node<VoidPointer> >::value 196 >::value >= 1) 197 > 198 {}; 199 200 } //namespace intrusive 201 } //namespace boost 202 203 #include <boost/intrusive/detail/config_end.hpp> 204 205 #endif //BOOST_INTRUSIVE_RBTREE_NODE_HPP 206