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
77 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const const_node_ptr & n)
78 { return n->parent_; }
79
80 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const node_ptr & n)
81 { return n->parent_; }
82
83 BOOST_INTRUSIVE_FORCEINLINE static void set_parent(const node_ptr & n, const node_ptr & p)
84 { n->parent_ = p; }
85
86 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const const_node_ptr & n)
87 { return n->left_; }
88
89 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const node_ptr & n)
90 { return n->left_; }
91
92 BOOST_INTRUSIVE_FORCEINLINE static void set_left(const node_ptr & n, const node_ptr & l)
93 { n->left_ = l; }
94
95 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const const_node_ptr & n)
96 { return n->right_; }
97
98 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const node_ptr & n)
99 { return n->right_; }
100
101 BOOST_INTRUSIVE_FORCEINLINE static void set_right(const node_ptr & n, const node_ptr & r)
102 { n->right_ = r; }
103
104 BOOST_INTRUSIVE_FORCEINLINE static color get_color(const const_node_ptr & n)
105 { return n->color_; }
106
107 BOOST_INTRUSIVE_FORCEINLINE static color get_color(const node_ptr & n)
108 { return n->color_; }
109
110 BOOST_INTRUSIVE_FORCEINLINE static void set_color(const node_ptr & n, color c)
|
(1) Event deref_parm: |
Directly dereferencing parameter "n". |
111 { n->color_ = c; }
112
113 BOOST_INTRUSIVE_FORCEINLINE static color black()
114 { return node::black_t; }
115
116 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
133 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const const_node_ptr & n)
134 { return ptr_bit::get_pointer(n->parent_); }
135
136 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const node_ptr & n)
137 { return ptr_bit::get_pointer(n->parent_); }
138
139 BOOST_INTRUSIVE_FORCEINLINE static void set_parent(const node_ptr & n, const node_ptr & p)
140 { ptr_bit::set_pointer(n->parent_, p); }
141
142 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const const_node_ptr & n)
143 { return n->left_; }
144
145 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const node_ptr & n)
146 { return n->left_; }
147
148 BOOST_INTRUSIVE_FORCEINLINE static void set_left(const node_ptr & n, const node_ptr & l)
149 { n->left_ = l; }
150
151 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const const_node_ptr & n)
152 { return n->right_; }
153
154 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const node_ptr & n)
155 { return n->right_; }
156
157 BOOST_INTRUSIVE_FORCEINLINE static void set_right(const node_ptr & n, const node_ptr & r)
158 { n->right_ = r; }
159
160 BOOST_INTRUSIVE_FORCEINLINE static color get_color(const const_node_ptr & n)
161 { return (color)ptr_bit::get_bits(n->parent_); }
162
163 BOOST_INTRUSIVE_FORCEINLINE static color get_color(const node_ptr & n)
164 { return (color)ptr_bit::get_bits(n->parent_); }
165
166 BOOST_INTRUSIVE_FORCEINLINE static void set_color(const node_ptr & n, color c)
167 { ptr_bit::set_bits(n->parent_, c != 0); }
168
169 BOOST_INTRUSIVE_FORCEINLINE static color black()
170 { return node::black_t; }
171
172 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