1 /////////////////////////////////////////////////////////////////////////////
3 // (C) Copyright Ion Gaztanaga 2006-2014
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)
9 // See http://www.boost.org/libs/intrusive for documentation.
11 /////////////////////////////////////////////////////////////////////////////
13 #ifndef BOOST_INTRUSIVE_ANY_NODE_HPP
14 #define BOOST_INTRUSIVE_ANY_NODE_HPP
16 #ifndef BOOST_CONFIG_HPP
17 # include <boost/config.hpp>
20 #if defined(BOOST_HAS_PRAGMA_ONCE)
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>
33 template<class VoidPointer>
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;
45 template<class VoidPointer>
46 struct any_list_node_traits
48 typedef any_node<VoidPointer> node;
49 typedef typename node::node_ptr node_ptr;
50 typedef typename node::const_node_ptr const_node_ptr;
52 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_next(const const_node_ptr & n)
53 { return n->node_ptr_1; }
55 BOOST_INTRUSIVE_FORCEINLINE static void set_next(const node_ptr & n, const node_ptr & next)
56 { n->node_ptr_1 = next; }
58 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_previous(const const_node_ptr & n)
59 { return n->node_ptr_2; }
61 BOOST_INTRUSIVE_FORCEINLINE static void set_previous(const node_ptr & n, const node_ptr & prev)
62 { n->node_ptr_2 = prev; }
66 template<class VoidPointer>
67 struct any_slist_node_traits
69 typedef any_node<VoidPointer> node;
70 typedef typename node::node_ptr node_ptr;
71 typedef typename node::const_node_ptr const_node_ptr;
73 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_next(const const_node_ptr & n)
74 { return n->node_ptr_1; }
76 BOOST_INTRUSIVE_FORCEINLINE static void set_next(const node_ptr & n, const node_ptr & next)
77 { n->node_ptr_1 = next; }
81 template<class VoidPointer>
82 struct any_unordered_node_traits
83 : public any_slist_node_traits<VoidPointer>
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;
90 static const bool store_hash = true;
91 static const bool optimize_multikey = true;
93 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_next(const const_node_ptr & n)
94 { return n->node_ptr_1; }
96 BOOST_INTRUSIVE_FORCEINLINE static void set_next(const node_ptr & n, const node_ptr & next)
97 { n->node_ptr_1 = next; }
99 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_prev_in_group(const const_node_ptr & n)
100 { return n->node_ptr_2; }
102 BOOST_INTRUSIVE_FORCEINLINE static void set_prev_in_group(const node_ptr & n, const node_ptr & prev)
103 { n->node_ptr_2 = prev; }
105 BOOST_INTRUSIVE_FORCEINLINE static std::size_t get_hash(const const_node_ptr & n)
106 { return n->size_t_1; }
108 BOOST_INTRUSIVE_FORCEINLINE static void set_hash(const node_ptr & n, std::size_t h)
113 template<class VoidPointer>
114 struct any_rbtree_node_traits
116 typedef any_node<VoidPointer> node;
117 typedef typename node::node_ptr node_ptr;
118 typedef typename node::const_node_ptr const_node_ptr;
120 typedef std::size_t color;
122 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const const_node_ptr & n)
123 { return n->node_ptr_1; }
125 BOOST_INTRUSIVE_FORCEINLINE static void set_parent(const node_ptr & n, const node_ptr & p)
126 { n->node_ptr_1 = p; }
128 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const const_node_ptr & n)
129 { return n->node_ptr_2; }
131 BOOST_INTRUSIVE_FORCEINLINE static void set_left(const node_ptr & n, const node_ptr & l)
132 { n->node_ptr_2 = l; }
134 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const const_node_ptr & n)
135 { return n->node_ptr_3; }
137 BOOST_INTRUSIVE_FORCEINLINE static void set_right(const node_ptr & n, const node_ptr & r)
138 { n->node_ptr_3 = r; }
140 BOOST_INTRUSIVE_FORCEINLINE static color get_color(const const_node_ptr & n)
141 { return n->size_t_1; }
143 BOOST_INTRUSIVE_FORCEINLINE static void set_color(const node_ptr & n, color c)
146 BOOST_INTRUSIVE_FORCEINLINE static color black()
149 BOOST_INTRUSIVE_FORCEINLINE static color red()
154 template<class VoidPointer>
155 struct any_avltree_node_traits
157 typedef any_node<VoidPointer> node;
158 typedef typename node::node_ptr node_ptr;
159 typedef typename node::const_node_ptr const_node_ptr;
161 typedef std::size_t balance;
163 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const const_node_ptr & n)
164 { return n->node_ptr_1; }
166 BOOST_INTRUSIVE_FORCEINLINE static void set_parent(const node_ptr & n, const node_ptr & p)
167 { n->node_ptr_1 = p; }
169 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const const_node_ptr & n)
170 { return n->node_ptr_2; }
172 BOOST_INTRUSIVE_FORCEINLINE static void set_left(const node_ptr & n, const node_ptr & l)
173 { n->node_ptr_2 = l; }
175 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const const_node_ptr & n)
176 { return n->node_ptr_3; }
178 BOOST_INTRUSIVE_FORCEINLINE static void set_right(const node_ptr & n, const node_ptr & r)
179 { n->node_ptr_3 = r; }
181 BOOST_INTRUSIVE_FORCEINLINE static balance get_balance(const const_node_ptr & n)
182 { return n->size_t_1; }
184 BOOST_INTRUSIVE_FORCEINLINE static void set_balance(const node_ptr & n, balance b)
187 BOOST_INTRUSIVE_FORCEINLINE static balance negative()
190 BOOST_INTRUSIVE_FORCEINLINE static balance zero()
193 BOOST_INTRUSIVE_FORCEINLINE static balance positive()
198 template<class VoidPointer>
199 struct any_tree_node_traits
201 typedef any_node<VoidPointer> node;
202 typedef typename node::node_ptr node_ptr;
203 typedef typename node::const_node_ptr const_node_ptr;
205 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const const_node_ptr & n)
206 { return n->node_ptr_1; }
208 BOOST_INTRUSIVE_FORCEINLINE static void set_parent(const node_ptr & n, const node_ptr & p)
209 { n->node_ptr_1 = p; }
211 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const const_node_ptr & n)
212 { return n->node_ptr_2; }
214 BOOST_INTRUSIVE_FORCEINLINE static void set_left(const node_ptr & n, const node_ptr & l)
215 { n->node_ptr_2 = l; }
217 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const const_node_ptr & n)
218 { return n->node_ptr_3; }
220 BOOST_INTRUSIVE_FORCEINLINE static void set_right(const node_ptr & n, const node_ptr & r)
221 { n->node_ptr_3 = r; }
224 template<class VoidPointer>
225 class any_node_traits
228 typedef any_node<VoidPointer> node;
229 typedef typename node::node_ptr node_ptr;
230 typedef typename node::const_node_ptr const_node_ptr;
233 template<class VoidPointer>
237 static void function_not_available_for_any_hooks(typename detail::enable_if<detail::is_same<T, bool> >::type)
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;
246 //! <b>Requires</b>: node must not be part of any tree.
248 //! <b>Effects</b>: After the function unique(node) == true.
250 //! <b>Complexity</b>: Constant.
252 //! <b>Throws</b>: Nothing.
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(); };
258 //! <b>Effects</b>: Returns true if node is in the same state as if called init(node)
260 //! <b>Complexity</b>: Constant.
262 //! <b>Throws</b>: Nothing.
263 BOOST_INTRUSIVE_FORCEINLINE static bool inited(const const_node_ptr & node)
264 { return !node->node_ptr_1; };
266 BOOST_INTRUSIVE_FORCEINLINE static bool unique(const const_node_ptr & node)
267 { return !node->node_ptr_1; }
269 static void unlink(const node_ptr &)
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>();
275 static void swap_nodes(const node_ptr &, const node_ptr &)
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>();
285 template<class NodeTraits>
286 struct get_algo<AnyAlgorithm, NodeTraits>
288 typedef typename pointer_rebind<typename NodeTraits::node_ptr, void>::type void_pointer;
289 typedef any_algorithms<void_pointer> type;
294 } //namespace intrusive
297 #endif //BOOST_INTRUSIVE_ANY_NODE_HPP