]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | ///////////////////////////////////////////////////////////////////////////// |
2 | // | |
3 | // (C) Copyright Ion Gaztanaga 2006-2014 | |
4 | // | |
5 | // Distributed under the Boost Software License, Version 1.0. | |
6 | // (See accompanying file LICENSE_1_0.txt or copy at | |
7 | // http://www.boost.org/LICENSE_1_0.txt) | |
8 | // | |
9 | // See http://www.boost.org/libs/intrusive for documentation. | |
10 | // | |
11 | ///////////////////////////////////////////////////////////////////////////// | |
12 | ||
13 | #ifndef BOOST_INTRUSIVE_ANY_NODE_HPP | |
14 | #define BOOST_INTRUSIVE_ANY_NODE_HPP | |
15 | ||
16 | #ifndef BOOST_CONFIG_HPP | |
17 | # include <boost/config.hpp> | |
18 | #endif | |
19 | ||
20 | #if defined(BOOST_HAS_PRAGMA_ONCE) | |
21 | # pragma once | |
22 | #endif | |
23 | ||
24 | #include <boost/intrusive/detail/workaround.hpp> | |
25 | #include <boost/intrusive/pointer_rebind.hpp> | |
26 | #include <boost/intrusive/detail/mpl.hpp> | |
27 | #include <boost/intrusive/detail/algo_type.hpp> | |
28 | #include <cstddef> | |
29 | ||
30 | namespace boost { | |
31 | namespace intrusive { | |
32 | ||
33 | template<class VoidPointer> | |
34 | struct any_node | |
35 | { | |
36 | typedef any_node node; | |
37 | typedef typename pointer_rebind<VoidPointer, node>::type node_ptr; | |
38 | typedef typename pointer_rebind<VoidPointer, const node>::type const_node_ptr; | |
39 | node_ptr node_ptr_1; | |
40 | node_ptr node_ptr_2; | |
41 | node_ptr node_ptr_3; | |
42 | std::size_t size_t_1; | |
43 | }; | |
44 | ||
45 | template<class VoidPointer> | |
46 | struct any_list_node_traits | |
47 | { | |
48 | typedef any_node<VoidPointer> node; | |
49 | typedef typename node::node_ptr node_ptr; | |
50 | typedef typename node::const_node_ptr const_node_ptr; | |
51 | ||
52 | BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_next(const const_node_ptr & n) | |
53 | { return n->node_ptr_1; } | |
54 | ||
55 | BOOST_INTRUSIVE_FORCEINLINE static void set_next(const node_ptr & n, const node_ptr & next) | |
56 | { n->node_ptr_1 = next; } | |
57 | ||
58 | BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_previous(const const_node_ptr & n) | |
59 | { return n->node_ptr_2; } | |
60 | ||
61 | BOOST_INTRUSIVE_FORCEINLINE static void set_previous(const node_ptr & n, const node_ptr & prev) | |
62 | { n->node_ptr_2 = prev; } | |
63 | }; | |
64 | ||
65 | ||
66 | template<class VoidPointer> | |
67 | struct any_slist_node_traits | |
68 | { | |
69 | typedef any_node<VoidPointer> node; | |
70 | typedef typename node::node_ptr node_ptr; | |
71 | typedef typename node::const_node_ptr const_node_ptr; | |
72 | ||
73 | BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_next(const const_node_ptr & n) | |
74 | { return n->node_ptr_1; } | |
75 | ||
76 | BOOST_INTRUSIVE_FORCEINLINE static void set_next(const node_ptr & n, const node_ptr & next) | |
77 | { n->node_ptr_1 = next; } | |
78 | }; | |
79 | ||
80 | ||
81 | template<class VoidPointer> | |
82 | struct any_unordered_node_traits | |
83 | : public any_slist_node_traits<VoidPointer> | |
84 | { | |
85 | typedef any_slist_node_traits<VoidPointer> reduced_slist_node_traits; | |
86 | typedef typename reduced_slist_node_traits::node node; | |
87 | typedef typename reduced_slist_node_traits::node_ptr node_ptr; | |
88 | typedef typename reduced_slist_node_traits::const_node_ptr const_node_ptr; | |
89 | ||
90 | static const bool store_hash = true; | |
91 | static const bool optimize_multikey = true; | |
92 | ||
93 | BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_next(const const_node_ptr & n) | |
94 | { return n->node_ptr_1; } | |
95 | ||
96 | BOOST_INTRUSIVE_FORCEINLINE static void set_next(const node_ptr & n, const node_ptr & next) | |
97 | { n->node_ptr_1 = next; } | |
98 | ||
99 | BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_prev_in_group(const const_node_ptr & n) | |
100 | { return n->node_ptr_2; } | |
101 | ||
102 | BOOST_INTRUSIVE_FORCEINLINE static void set_prev_in_group(const node_ptr & n, const node_ptr & prev) | |
103 | { n->node_ptr_2 = prev; } | |
104 | ||
105 | BOOST_INTRUSIVE_FORCEINLINE static std::size_t get_hash(const const_node_ptr & n) | |
106 | { return n->size_t_1; } | |
107 | ||
108 | BOOST_INTRUSIVE_FORCEINLINE static void set_hash(const node_ptr & n, std::size_t h) | |
109 | { n->size_t_1 = h; } | |
110 | }; | |
111 | ||
112 | ||
113 | template<class VoidPointer> | |
114 | struct any_rbtree_node_traits | |
115 | { | |
116 | typedef any_node<VoidPointer> node; | |
117 | typedef typename node::node_ptr node_ptr; | |
118 | typedef typename node::const_node_ptr const_node_ptr; | |
119 | ||
120 | typedef std::size_t color; | |
121 | ||
122 | BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const const_node_ptr & n) | |
123 | { return n->node_ptr_1; } | |
124 | ||
125 | BOOST_INTRUSIVE_FORCEINLINE static void set_parent(const node_ptr & n, const node_ptr & p) | |
126 | { n->node_ptr_1 = p; } | |
127 | ||
128 | BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const const_node_ptr & n) | |
129 | { return n->node_ptr_2; } | |
130 | ||
131 | BOOST_INTRUSIVE_FORCEINLINE static void set_left(const node_ptr & n, const node_ptr & l) | |
132 | { n->node_ptr_2 = l; } | |
133 | ||
134 | BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const const_node_ptr & n) | |
135 | { return n->node_ptr_3; } | |
136 | ||
137 | BOOST_INTRUSIVE_FORCEINLINE static void set_right(const node_ptr & n, const node_ptr & r) | |
138 | { n->node_ptr_3 = r; } | |
139 | ||
140 | BOOST_INTRUSIVE_FORCEINLINE static color get_color(const const_node_ptr & n) | |
141 | { return n->size_t_1; } | |
142 | ||
143 | BOOST_INTRUSIVE_FORCEINLINE static void set_color(const node_ptr & n, color c) | |
144 | { n->size_t_1 = c; } | |
145 | ||
146 | BOOST_INTRUSIVE_FORCEINLINE static color black() | |
147 | { return 0u; } | |
148 | ||
149 | BOOST_INTRUSIVE_FORCEINLINE static color red() | |
150 | { return 1u; } | |
151 | }; | |
152 | ||
153 | ||
154 | template<class VoidPointer> | |
155 | struct any_avltree_node_traits | |
156 | { | |
157 | typedef any_node<VoidPointer> node; | |
158 | typedef typename node::node_ptr node_ptr; | |
159 | typedef typename node::const_node_ptr const_node_ptr; | |
160 | ||
161 | typedef std::size_t balance; | |
162 | ||
163 | BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const const_node_ptr & n) | |
164 | { return n->node_ptr_1; } | |
165 | ||
166 | BOOST_INTRUSIVE_FORCEINLINE static void set_parent(const node_ptr & n, const node_ptr & p) | |
167 | { n->node_ptr_1 = p; } | |
168 | ||
169 | BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const const_node_ptr & n) | |
170 | { return n->node_ptr_2; } | |
171 | ||
172 | BOOST_INTRUSIVE_FORCEINLINE static void set_left(const node_ptr & n, const node_ptr & l) | |
173 | { n->node_ptr_2 = l; } | |
174 | ||
175 | BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const const_node_ptr & n) | |
176 | { return n->node_ptr_3; } | |
177 | ||
178 | BOOST_INTRUSIVE_FORCEINLINE static void set_right(const node_ptr & n, const node_ptr & r) | |
179 | { n->node_ptr_3 = r; } | |
180 | ||
181 | BOOST_INTRUSIVE_FORCEINLINE static balance get_balance(const const_node_ptr & n) | |
182 | { return n->size_t_1; } | |
183 | ||
184 | BOOST_INTRUSIVE_FORCEINLINE static void set_balance(const node_ptr & n, balance b) | |
185 | { n->size_t_1 = b; } | |
186 | ||
187 | BOOST_INTRUSIVE_FORCEINLINE static balance negative() | |
188 | { return 0u; } | |
189 | ||
190 | BOOST_INTRUSIVE_FORCEINLINE static balance zero() | |
191 | { return 1u; } | |
192 | ||
193 | BOOST_INTRUSIVE_FORCEINLINE static balance positive() | |
194 | { return 2u; } | |
195 | }; | |
196 | ||
197 | ||
198 | template<class VoidPointer> | |
199 | struct any_tree_node_traits | |
200 | { | |
201 | typedef any_node<VoidPointer> node; | |
202 | typedef typename node::node_ptr node_ptr; | |
203 | typedef typename node::const_node_ptr const_node_ptr; | |
204 | ||
205 | BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const const_node_ptr & n) | |
206 | { return n->node_ptr_1; } | |
207 | ||
208 | BOOST_INTRUSIVE_FORCEINLINE static void set_parent(const node_ptr & n, const node_ptr & p) | |
209 | { n->node_ptr_1 = p; } | |
210 | ||
211 | BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const const_node_ptr & n) | |
212 | { return n->node_ptr_2; } | |
213 | ||
214 | BOOST_INTRUSIVE_FORCEINLINE static void set_left(const node_ptr & n, const node_ptr & l) | |
215 | { n->node_ptr_2 = l; } | |
216 | ||
217 | BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const const_node_ptr & n) | |
218 | { return n->node_ptr_3; } | |
219 | ||
220 | BOOST_INTRUSIVE_FORCEINLINE static void set_right(const node_ptr & n, const node_ptr & r) | |
221 | { n->node_ptr_3 = r; } | |
222 | }; | |
223 | ||
224 | template<class VoidPointer> | |
225 | class any_node_traits | |
226 | { | |
227 | public: | |
228 | typedef any_node<VoidPointer> node; | |
229 | typedef typename node::node_ptr node_ptr; | |
230 | typedef typename node::const_node_ptr const_node_ptr; | |
231 | }; | |
232 | ||
233 | template<class VoidPointer> | |
234 | class any_algorithms | |
235 | { | |
236 | template <class T> | |
237 | static void function_not_available_for_any_hooks(typename detail::enable_if<detail::is_same<T, bool> >::type) | |
238 | {} | |
239 | ||
240 | public: | |
241 | typedef any_node<VoidPointer> node; | |
242 | typedef typename node::node_ptr node_ptr; | |
243 | typedef typename node::const_node_ptr const_node_ptr; | |
244 | typedef any_node_traits<VoidPointer> node_traits; | |
245 | ||
246 | //! <b>Requires</b>: node must not be part of any tree. | |
247 | //! | |
248 | //! <b>Effects</b>: After the function unique(node) == true. | |
249 | //! | |
250 | //! <b>Complexity</b>: Constant. | |
251 | //! | |
252 | //! <b>Throws</b>: Nothing. | |
253 | //! | |
254 | //! <b>Nodes</b>: If node is inserted in a tree, this function corrupts the tree. | |
255 | BOOST_INTRUSIVE_FORCEINLINE static void init(const node_ptr & node) | |
256 | { node->node_ptr_1 = node_ptr(); }; | |
257 | ||
258 | //! <b>Effects</b>: Returns true if node is in the same state as if called init(node) | |
259 | //! | |
260 | //! <b>Complexity</b>: Constant. | |
261 | //! | |
262 | //! <b>Throws</b>: Nothing. | |
263 | BOOST_INTRUSIVE_FORCEINLINE static bool inited(const const_node_ptr & node) | |
264 | { return !node->node_ptr_1; }; | |
265 | ||
266 | BOOST_INTRUSIVE_FORCEINLINE static bool unique(const const_node_ptr & node) | |
267 | { return !node->node_ptr_1; } | |
268 | ||
269 | static void unlink(const node_ptr &) | |
270 | { | |
271 | //Auto-unlink hooks and unlink() are not available for any hooks | |
272 | any_algorithms<VoidPointer>::template function_not_available_for_any_hooks<node_ptr>(); | |
273 | } | |
274 | ||
275 | static void swap_nodes(const node_ptr &, const node_ptr &) | |
276 | { | |
277 | //Any nodes have no swap_nodes capability because they don't know | |
278 | //what algorithm they must use to unlink the node from the container | |
279 | any_algorithms<VoidPointer>::template function_not_available_for_any_hooks<node_ptr>(); | |
280 | } | |
281 | }; | |
282 | ||
283 | ///@cond | |
284 | ||
285 | template<class NodeTraits> | |
286 | struct get_algo<AnyAlgorithm, NodeTraits> | |
287 | { | |
288 | typedef typename pointer_rebind<typename NodeTraits::node_ptr, void>::type void_pointer; | |
289 | typedef any_algorithms<void_pointer> type; | |
290 | }; | |
291 | ||
292 | ///@endcond | |
293 | ||
294 | } //namespace intrusive | |
295 | } //namespace boost | |
296 | ||
297 | #endif //BOOST_INTRUSIVE_ANY_NODE_HPP |