Mercurial > hg > vamp-build-and-test

comparison DEPENDENCIES/generic/include/boost/intrusive/detail/rbtree_node.hpp @ 16:2665513ce2d3

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add boost headers
author Chris Cannam
date Tue, 05 Aug 2014 11:11:38 +0100
parents
children c530137014c0
comparison
equal deleted inserted replaced
15:663ca0da4350 16:2665513ce2d3
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 #include <boost/intrusive/detail/config_begin.hpp>
18 #include <iterator>
19 #include <boost/intrusive/pointer_traits.hpp>
20 #include <boost/intrusive/rbtree_algorithms.hpp>
21 #include <boost/intrusive/pointer_plus_bits.hpp>
22 #include <boost/intrusive/detail/mpl.hpp>
23 #include <boost/intrusive/detail/utilities.hpp>
24 #include <boost/intrusive/detail/tree_node.hpp>
25
26 namespace boost {
27 namespace intrusive {
28
29 /////////////////////////////////////////////////////////////////////////////
30 // //
31 // Generic node_traits for any pointer type //
32 // //
33 /////////////////////////////////////////////////////////////////////////////
34
35 //This is the compact representation: 3 pointers
36 template<class VoidPointer>
37 struct compact_rbtree_node
38 {
39 typedef typename pointer_traits
40 <VoidPointer>::template rebind_pointer
41 <compact_rbtree_node<VoidPointer> >::type node_ptr;
42 enum color { red_t, black_t };
43 node_ptr parent_, left_, right_;
44 };
45
46 //This is the normal representation: 3 pointers + enum
47 template<class VoidPointer>
48 struct rbtree_node
49 {
50 typedef typename pointer_traits
51 <VoidPointer>::template rebind_pointer
52 <rbtree_node<VoidPointer> >::type node_ptr;
53
54 enum color { red_t, black_t };
55 node_ptr parent_, left_, right_;
56 color color_;
57 };
58
59 //This is the default node traits implementation
60 //using a node with 3 generic pointers plus an enum
61 template<class VoidPointer>
62 struct default_rbtree_node_traits_impl
63 {
64 typedef rbtree_node<VoidPointer> node;
65
66 typedef typename pointer_traits
67 <VoidPointer>::template rebind_pointer<node>::type node_ptr;
68 typedef typename pointer_traits
69 <VoidPointer>::template rebind_pointer<const node>::type const_node_ptr;
70
71 typedef typename node::color color;
72
73 static node_ptr get_parent(const const_node_ptr & n)
74 { return n->parent_; }
75
76 static node_ptr get_parent(const node_ptr & n)
77 { return n->parent_; }
78
79 static void set_parent(const node_ptr & n, const node_ptr & p)
80 { n->parent_ = p; }
81
82 static node_ptr get_left(const const_node_ptr & n)
83 { return n->left_; }
84
85 static node_ptr get_left(const node_ptr & n)
86 { return n->left_; }
87
88 static void set_left(const node_ptr & n, const node_ptr & l)
89 { n->left_ = l; }
90
91 static node_ptr get_right(const const_node_ptr & n)
92 { return n->right_; }
93
94 static node_ptr get_right(const node_ptr & n)
95 { return n->right_; }
96
97 static void set_right(const node_ptr & n, const node_ptr & r)
98 { n->right_ = r; }
99
100 static color get_color(const const_node_ptr & n)
101 { return n->color_; }
102
103 static color get_color(const node_ptr & n)
104 { return n->color_; }
105
106 static void set_color(const node_ptr & n, color c)
107 { n->color_ = c; }
108
109 static color black()
110 { return node::black_t; }
111
112 static color red()
113 { return node::red_t; }
114 };
115
116 //This is the compact node traits implementation
117 //using a node with 3 generic pointers
118 template<class VoidPointer>
119 struct compact_rbtree_node_traits_impl
120 {
121 typedef compact_rbtree_node<VoidPointer> node;
122 typedef typename pointer_traits
123 <VoidPointer>::template rebind_pointer<node>::type node_ptr;
124 typedef typename pointer_traits
125 <VoidPointer>::template rebind_pointer<const node>::type const_node_ptr;
126
127 typedef pointer_plus_bits<node_ptr, 1> ptr_bit;
128
129 typedef typename node::color color;
130
131 static node_ptr get_parent(const const_node_ptr & n)
132 { return ptr_bit::get_pointer(n->parent_); }
133
134 static node_ptr get_parent(const node_ptr & n)
135 { return ptr_bit::get_pointer(n->parent_); }
136
137 static void set_parent(const node_ptr & n, const node_ptr & p)
138 { ptr_bit::set_pointer(n->parent_, p); }
139
140 static node_ptr get_left(const const_node_ptr & n)
141 { return n->left_; }
142
143 static node_ptr get_left(const node_ptr & n)
144 { return n->left_; }
145
146 static void set_left(const node_ptr & n, const node_ptr & l)
147 { n->left_ = l; }
148
149 static node_ptr get_right(const const_node_ptr & n)
150 { return n->right_; }
151
152 static node_ptr get_right(const node_ptr & n)
153 { return n->right_; }
154
155 static void set_right(const node_ptr & n, const node_ptr & r)
156 { n->right_ = r; }
157
158 static color get_color(const const_node_ptr & n)
159 { return (color)ptr_bit::get_bits(n->parent_); }
160
161 static color get_color(const node_ptr & n)
162 { return (color)ptr_bit::get_bits(n->parent_); }
163
164 static void set_color(const node_ptr & n, color c)
165 { ptr_bit::set_bits(n->parent_, c != 0); }
166
167 static color black()
168 { return node::black_t; }
169
170 static color red()
171 { return node::red_t; }
172 };
173
174 //Dispatches the implementation based on the boolean
175 template<class VoidPointer, bool Compact>
176 struct rbtree_node_traits_dispatch
177 : public default_rbtree_node_traits_impl<VoidPointer>
178 {};
179
180 template<class VoidPointer>
181 struct rbtree_node_traits_dispatch<VoidPointer, true>
182 : public compact_rbtree_node_traits_impl<VoidPointer>
183 {};
184
185 //Inherit from the detail::link_dispatch depending on the embedding capabilities
186 template<class VoidPointer, bool OptimizeSize = false>
187 struct rbtree_node_traits
188 : public rbtree_node_traits_dispatch
189 < VoidPointer
190 , OptimizeSize &&
191 (max_pointer_plus_bits
192 < VoidPointer
193 , detail::alignment_of<compact_rbtree_node<VoidPointer> >::value
194 >::value >= 1)
195 >
196 {};
197
198 } //namespace intrusive
199 } //namespace boost
200
201 #include <boost/intrusive/detail/config_end.hpp>
202
203 #endif //BOOST_INTRUSIVE_RBTREE_NODE_HPP