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 get_nextboost::intrusive::any_list_node_traits52 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_next(const const_node_ptr & n) 53 { return n->node_ptr_1; } 54 set_nextboost::intrusive::any_list_node_traits55 BOOST_INTRUSIVE_FORCEINLINE static void set_next(node_ptr n, node_ptr next) 56 { n->node_ptr_1 = next; } 57 get_previousboost::intrusive::any_list_node_traits58 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_previous(const const_node_ptr & n) 59 { return n->node_ptr_2; } 60 set_previousboost::intrusive::any_list_node_traits61 BOOST_INTRUSIVE_FORCEINLINE static void set_previous(node_ptr n, 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 get_nextboost::intrusive::any_slist_node_traits73 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_next(const const_node_ptr & n) 74 { return n->node_ptr_1; } 75 set_nextboost::intrusive::any_slist_node_traits76 BOOST_INTRUSIVE_FORCEINLINE static void set_next(node_ptr n, 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 get_nextboost::intrusive::any_unordered_node_traits93 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_next(const const_node_ptr & n) 94 { return n->node_ptr_1; } 95 set_nextboost::intrusive::any_unordered_node_traits96 BOOST_INTRUSIVE_FORCEINLINE static void set_next(node_ptr n, node_ptr next) 97 { n->node_ptr_1 = next; } 98 get_prev_in_groupboost::intrusive::any_unordered_node_traits99 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_prev_in_group(const const_node_ptr & n) 100 { return n->node_ptr_2; } 101 set_prev_in_groupboost::intrusive::any_unordered_node_traits102 BOOST_INTRUSIVE_FORCEINLINE static void set_prev_in_group(node_ptr n, node_ptr prev) 103 { n->node_ptr_2 = prev; } 104 get_hashboost::intrusive::any_unordered_node_traits105 BOOST_INTRUSIVE_FORCEINLINE static std::size_t get_hash(const const_node_ptr & n) 106 { return n->size_t_1; } 107 set_hashboost::intrusive::any_unordered_node_traits108 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 get_parentboost::intrusive::any_rbtree_node_traits122 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const const_node_ptr & n) 123 { return n->node_ptr_1; } 124 set_parentboost::intrusive::any_rbtree_node_traits125 BOOST_INTRUSIVE_FORCEINLINE static void set_parent(node_ptr n, node_ptr p) 126 { n->node_ptr_1 = p; } 127 get_leftboost::intrusive::any_rbtree_node_traits128 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const const_node_ptr & n) 129 { return n->node_ptr_2; } 130 set_leftboost::intrusive::any_rbtree_node_traits131 BOOST_INTRUSIVE_FORCEINLINE static void set_left(node_ptr n, node_ptr l) 132 { n->node_ptr_2 = l; } 133 get_rightboost::intrusive::any_rbtree_node_traits134 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const const_node_ptr & n) 135 { return n->node_ptr_3; } 136 set_rightboost::intrusive::any_rbtree_node_traits137 BOOST_INTRUSIVE_FORCEINLINE static void set_right(node_ptr n, node_ptr r) 138 { n->node_ptr_3 = r; } 139 get_colorboost::intrusive::any_rbtree_node_traits140 BOOST_INTRUSIVE_FORCEINLINE static color get_color(const const_node_ptr & n) 141 { return n->size_t_1; } 142 set_colorboost::intrusive::any_rbtree_node_traits143 BOOST_INTRUSIVE_FORCEINLINE static void set_color(const node_ptr & n, color c) 144 { n->size_t_1 = c; } 145 blackboost::intrusive::any_rbtree_node_traits146 BOOST_INTRUSIVE_FORCEINLINE static color black() 147 { return 0u; } 148 redboost::intrusive::any_rbtree_node_traits149 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 get_parentboost::intrusive::any_avltree_node_traits163 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const const_node_ptr & n) 164 { return n->node_ptr_1; } 165 set_parentboost::intrusive::any_avltree_node_traits166 BOOST_INTRUSIVE_FORCEINLINE static void set_parent(node_ptr n, node_ptr p) 167 { n->node_ptr_1 = p; } 168 get_leftboost::intrusive::any_avltree_node_traits169 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const const_node_ptr & n) 170 { return n->node_ptr_2; } 171 set_leftboost::intrusive::any_avltree_node_traits172 BOOST_INTRUSIVE_FORCEINLINE static void set_left(node_ptr n, node_ptr l) 173 { n->node_ptr_2 = l; } 174 get_rightboost::intrusive::any_avltree_node_traits175 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const const_node_ptr & n) 176 { return n->node_ptr_3; } 177 set_rightboost::intrusive::any_avltree_node_traits178 BOOST_INTRUSIVE_FORCEINLINE static void set_right(node_ptr n, node_ptr r) 179 { n->node_ptr_3 = r; } 180 get_balanceboost::intrusive::any_avltree_node_traits181 BOOST_INTRUSIVE_FORCEINLINE static balance get_balance(const const_node_ptr & n) 182 { return n->size_t_1; } 183 set_balanceboost::intrusive::any_avltree_node_traits184 BOOST_INTRUSIVE_FORCEINLINE static void set_balance(const node_ptr & n, balance b) 185 { n->size_t_1 = b; } 186 negativeboost::intrusive::any_avltree_node_traits187 BOOST_INTRUSIVE_FORCEINLINE static balance negative() 188 { return 0u; } 189 zeroboost::intrusive::any_avltree_node_traits190 BOOST_INTRUSIVE_FORCEINLINE static balance zero() 191 { return 1u; } 192 positiveboost::intrusive::any_avltree_node_traits193 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 get_parentboost::intrusive::any_tree_node_traits205 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const const_node_ptr & n) 206 { return n->node_ptr_1; } 207 set_parentboost::intrusive::any_tree_node_traits208 BOOST_INTRUSIVE_FORCEINLINE static void set_parent(node_ptr n, node_ptr p) 209 { n->node_ptr_1 = p; } 210 get_leftboost::intrusive::any_tree_node_traits211 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const const_node_ptr & n) 212 { return n->node_ptr_2; } 213 set_leftboost::intrusive::any_tree_node_traits214 BOOST_INTRUSIVE_FORCEINLINE static void set_left(node_ptr n, node_ptr l) 215 { n->node_ptr_2 = l; } 216 get_rightboost::intrusive::any_tree_node_traits217 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const const_node_ptr & n) 218 { return n->node_ptr_3; } 219 set_rightboost::intrusive::any_tree_node_traits220 BOOST_INTRUSIVE_FORCEINLINE static void set_right(node_ptr n, 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> function_not_available_for_any_hooks(typename detail::enable_if<detail::is_same<T,bool>>::type)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. init(const node_ptr & node)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. inited(const const_node_ptr & node)263 BOOST_INTRUSIVE_FORCEINLINE static bool inited(const const_node_ptr & node) 264 { return !node->node_ptr_1; }; 265 unique(const const_node_ptr & node)266 BOOST_INTRUSIVE_FORCEINLINE static bool unique(const const_node_ptr & node) 267 { return !node->node_ptr_1; } 268 unlink(const node_ptr &)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 swap_nodes(const node_ptr &,const node_ptr &)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 298