1 /////////////////////////////////////////////////////////////////////////////
3 // (C) Copyright Olaf Krzikalla 2004-2006.
4 // (C) Copyright Ion Gaztanaga 2006-2013.
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)
10 // See http://www.boost.org/libs/intrusive for documentation.
12 /////////////////////////////////////////////////////////////////////////////
14 #ifndef BOOST_INTRUSIVE_RBTREE_NODE_HPP
15 #define BOOST_INTRUSIVE_RBTREE_NODE_HPP
17 #ifndef BOOST_CONFIG_HPP
18 # include <boost/config.hpp>
21 #if defined(BOOST_HAS_PRAGMA_ONCE)
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>
36 /////////////////////////////////////////////////////////////////////////////
38 // Generic node_traits for any pointer type //
40 /////////////////////////////////////////////////////////////////////////////
42 //This is the compact representation: 3 pointers
43 template<class VoidPointer>
44 struct compact_rbtree_node
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_;
53 //This is the normal representation: 3 pointers + enum
54 template<class VoidPointer>
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;
61 enum color { red_t, black_t };
62 node_ptr parent_, left_, right_;
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
71 typedef rbtree_node<VoidPointer> node;
72 typedef typename node::node_ptr node_ptr;
73 typedef typename node::const_node_ptr const_node_ptr;
75 typedef typename node::color color;
77 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const const_node_ptr & n)
78 { return n->parent_; }
80 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const node_ptr & n)
81 { return n->parent_; }
83 BOOST_INTRUSIVE_FORCEINLINE static void set_parent(const node_ptr & n, const node_ptr & p)
86 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const const_node_ptr & n)
89 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const node_ptr & n)
92 BOOST_INTRUSIVE_FORCEINLINE static void set_left(const node_ptr & n, const node_ptr & l)
95 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const const_node_ptr & n)
98 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const node_ptr & n)
101 BOOST_INTRUSIVE_FORCEINLINE static void set_right(const node_ptr & n, const node_ptr & r)
104 BOOST_INTRUSIVE_FORCEINLINE static color get_color(const const_node_ptr & n)
105 { return n->color_; }
107 BOOST_INTRUSIVE_FORCEINLINE static color get_color(const node_ptr & n)
108 { return n->color_; }
110 BOOST_INTRUSIVE_FORCEINLINE static void set_color(const node_ptr & n, color c)
113 BOOST_INTRUSIVE_FORCEINLINE static color black()
114 { return node::black_t; }
116 BOOST_INTRUSIVE_FORCEINLINE static color red()
117 { return node::red_t; }
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
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;
129 typedef pointer_plus_bits<node_ptr, 1> ptr_bit;
131 typedef typename node::color color;
133 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const const_node_ptr & n)
134 { return ptr_bit::get_pointer(n->parent_); }
136 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const node_ptr & n)
137 { return ptr_bit::get_pointer(n->parent_); }
139 BOOST_INTRUSIVE_FORCEINLINE static void set_parent(const node_ptr & n, const node_ptr & p)
140 { ptr_bit::set_pointer(n->parent_, p); }
142 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const const_node_ptr & n)
145 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const node_ptr & n)
148 BOOST_INTRUSIVE_FORCEINLINE static void set_left(const node_ptr & n, const node_ptr & l)
151 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const const_node_ptr & n)
152 { return n->right_; }
154 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const node_ptr & n)
155 { return n->right_; }
157 BOOST_INTRUSIVE_FORCEINLINE static void set_right(const node_ptr & n, const node_ptr & r)
160 BOOST_INTRUSIVE_FORCEINLINE static color get_color(const const_node_ptr & n)
161 { return (color)ptr_bit::get_bits(n->parent_); }
163 BOOST_INTRUSIVE_FORCEINLINE static color get_color(const node_ptr & n)
164 { return (color)ptr_bit::get_bits(n->parent_); }
166 BOOST_INTRUSIVE_FORCEINLINE static void set_color(const node_ptr & n, color c)
167 { ptr_bit::set_bits(n->parent_, c != 0); }
169 BOOST_INTRUSIVE_FORCEINLINE static color black()
170 { return node::black_t; }
172 BOOST_INTRUSIVE_FORCEINLINE static color red()
173 { return node::red_t; }
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>
182 template<class VoidPointer>
183 struct rbtree_node_traits_dispatch<VoidPointer, true>
184 : public compact_rbtree_node_traits_impl<VoidPointer>
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
193 (max_pointer_plus_bits
195 , detail::alignment_of<compact_rbtree_node<VoidPointer> >::value
200 } //namespace intrusive
203 #include <boost/intrusive/detail/config_end.hpp>
205 #endif //BOOST_INTRUSIVE_RBTREE_NODE_HPP