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/pointer_rebind.hpp> 25 #include <cstddef> 26 #include <boost/intrusive/detail/mpl.hpp> 27 28 namespace boost { 29 namespace intrusive { 30 31 template<class VoidPointer> 32 struct any_node 33 { 34 typedef any_node node; 35 typedef typename pointer_rebind<VoidPointer, node>::type node_ptr; 36 typedef typename pointer_rebind<VoidPointer, const node>::type const_node_ptr; 37 node_ptr node_ptr_1; 38 node_ptr node_ptr_2; 39 node_ptr node_ptr_3; 40 std::size_t size_t_1; 41 }; 42 43 template<class VoidPointer> 44 struct any_list_node_traits 45 { 46 typedef any_node<VoidPointer> node; 47 typedef typename node::node_ptr node_ptr; 48 typedef typename node::const_node_ptr const_node_ptr; 49 get_nextboost::intrusive::any_list_node_traits50 static node_ptr get_next(const const_node_ptr & n) 51 { return n->node_ptr_1; } 52 set_nextboost::intrusive::any_list_node_traits53 static void set_next(const node_ptr & n, const node_ptr & next) 54 { n->node_ptr_1 = next; } 55 get_previousboost::intrusive::any_list_node_traits56 static node_ptr get_previous(const const_node_ptr & n) 57 { return n->node_ptr_2; } 58 set_previousboost::intrusive::any_list_node_traits59 static void set_previous(const node_ptr & n, const node_ptr & prev) 60 { n->node_ptr_2 = prev; } 61 }; 62 63 64 template<class VoidPointer> 65 struct any_slist_node_traits 66 { 67 typedef any_node<VoidPointer> node; 68 typedef typename node::node_ptr node_ptr; 69 typedef typename node::const_node_ptr const_node_ptr; 70 get_nextboost::intrusive::any_slist_node_traits71 static node_ptr get_next(const const_node_ptr & n) 72 { return n->node_ptr_1; } 73 set_nextboost::intrusive::any_slist_node_traits74 static void set_next(const node_ptr & n, const node_ptr & next) 75 { n->node_ptr_1 = next; } 76 }; 77 78 79 template<class VoidPointer> 80 struct any_unordered_node_traits 81 : public any_slist_node_traits<VoidPointer> 82 { 83 typedef any_slist_node_traits<VoidPointer> reduced_slist_node_traits; 84 typedef typename reduced_slist_node_traits::node node; 85 typedef typename reduced_slist_node_traits::node_ptr node_ptr; 86 typedef typename reduced_slist_node_traits::const_node_ptr const_node_ptr; 87 88 static const bool store_hash = true; 89 static const bool optimize_multikey = true; 90 get_nextboost::intrusive::any_unordered_node_traits91 static node_ptr get_next(const const_node_ptr & n) 92 { return n->node_ptr_1; } 93 set_nextboost::intrusive::any_unordered_node_traits94 static void set_next(const node_ptr & n, const node_ptr & next) 95 { n->node_ptr_1 = next; } 96 get_prev_in_groupboost::intrusive::any_unordered_node_traits97 static node_ptr get_prev_in_group(const const_node_ptr & n) 98 { return n->node_ptr_2; } 99 set_prev_in_groupboost::intrusive::any_unordered_node_traits100 static void set_prev_in_group(const node_ptr & n, const node_ptr & prev) 101 { n->node_ptr_2 = prev; } 102 get_hashboost::intrusive::any_unordered_node_traits103 static std::size_t get_hash(const const_node_ptr & n) 104 { return n->size_t_1; } 105 set_hashboost::intrusive::any_unordered_node_traits106 static void set_hash(const node_ptr & n, std::size_t h) 107 { n->size_t_1 = h; } 108 }; 109 110 111 template<class VoidPointer> 112 struct any_rbtree_node_traits 113 { 114 typedef any_node<VoidPointer> node; 115 typedef typename node::node_ptr node_ptr; 116 typedef typename node::const_node_ptr const_node_ptr; 117 118 typedef std::size_t color; 119 get_parentboost::intrusive::any_rbtree_node_traits120 static node_ptr get_parent(const const_node_ptr & n) 121 { return n->node_ptr_1; } 122 set_parentboost::intrusive::any_rbtree_node_traits123 static void set_parent(const node_ptr & n, const node_ptr & p) 124 { n->node_ptr_1 = p; } 125 get_leftboost::intrusive::any_rbtree_node_traits126 static node_ptr get_left(const const_node_ptr & n) 127 { return n->node_ptr_2; } 128 set_leftboost::intrusive::any_rbtree_node_traits129 static void set_left(const node_ptr & n, const node_ptr & l) 130 { n->node_ptr_2 = l; } 131 get_rightboost::intrusive::any_rbtree_node_traits132 static node_ptr get_right(const const_node_ptr & n) 133 { return n->node_ptr_3; } 134 set_rightboost::intrusive::any_rbtree_node_traits135 static void set_right(const node_ptr & n, const node_ptr & r) 136 { n->node_ptr_3 = r; } 137 get_colorboost::intrusive::any_rbtree_node_traits138 static color get_color(const const_node_ptr & n) 139 { return n->size_t_1; } 140 set_colorboost::intrusive::any_rbtree_node_traits141 static void set_color(const node_ptr & n, color c) 142 { n->size_t_1 = c; } 143 blackboost::intrusive::any_rbtree_node_traits144 static color black() 145 { return 0u; } 146 redboost::intrusive::any_rbtree_node_traits147 static color red() 148 { return 1u; } 149 }; 150 151 152 template<class VoidPointer> 153 struct any_avltree_node_traits 154 { 155 typedef any_node<VoidPointer> node; 156 typedef typename node::node_ptr node_ptr; 157 typedef typename node::const_node_ptr const_node_ptr; 158 159 typedef std::size_t balance; 160 get_parentboost::intrusive::any_avltree_node_traits161 static node_ptr get_parent(const const_node_ptr & n) 162 { return n->node_ptr_1; } 163 set_parentboost::intrusive::any_avltree_node_traits164 static void set_parent(const node_ptr & n, const node_ptr & p) 165 { n->node_ptr_1 = p; } 166 get_leftboost::intrusive::any_avltree_node_traits167 static node_ptr get_left(const const_node_ptr & n) 168 { return n->node_ptr_2; } 169 set_leftboost::intrusive::any_avltree_node_traits170 static void set_left(const node_ptr & n, const node_ptr & l) 171 { n->node_ptr_2 = l; } 172 get_rightboost::intrusive::any_avltree_node_traits173 static node_ptr get_right(const const_node_ptr & n) 174 { return n->node_ptr_3; } 175 set_rightboost::intrusive::any_avltree_node_traits176 static void set_right(const node_ptr & n, const node_ptr & r) 177 { n->node_ptr_3 = r; } 178 get_balanceboost::intrusive::any_avltree_node_traits179 static balance get_balance(const const_node_ptr & n) 180 { return n->size_t_1; } 181 set_balanceboost::intrusive::any_avltree_node_traits182 static void set_balance(const node_ptr & n, balance b) 183 { n->size_t_1 = b; } 184 negativeboost::intrusive::any_avltree_node_traits185 static balance negative() 186 { return 0u; } 187 zeroboost::intrusive::any_avltree_node_traits188 static balance zero() 189 { return 1u; } 190 positiveboost::intrusive::any_avltree_node_traits191 static balance positive() 192 { return 2u; } 193 }; 194 195 196 template<class VoidPointer> 197 struct any_tree_node_traits 198 { 199 typedef any_node<VoidPointer> node; 200 typedef typename node::node_ptr node_ptr; 201 typedef typename node::const_node_ptr const_node_ptr; 202 get_parentboost::intrusive::any_tree_node_traits203 static node_ptr get_parent(const const_node_ptr & n) 204 { return n->node_ptr_1; } 205 set_parentboost::intrusive::any_tree_node_traits206 static void set_parent(const node_ptr & n, const node_ptr & p) 207 { n->node_ptr_1 = p; } 208 get_leftboost::intrusive::any_tree_node_traits209 static node_ptr get_left(const const_node_ptr & n) 210 { return n->node_ptr_2; } 211 set_leftboost::intrusive::any_tree_node_traits212 static void set_left(const node_ptr & n, const node_ptr & l) 213 { n->node_ptr_2 = l; } 214 get_rightboost::intrusive::any_tree_node_traits215 static node_ptr get_right(const const_node_ptr & n) 216 { return n->node_ptr_3; } 217 set_rightboost::intrusive::any_tree_node_traits218 static void set_right(const node_ptr & n, const node_ptr & r) 219 { n->node_ptr_3 = r; } 220 }; 221 222 template<class VoidPointer> 223 class any_node_traits 224 { 225 public: 226 typedef any_node<VoidPointer> node; 227 typedef typename node::node_ptr node_ptr; 228 typedef typename node::const_node_ptr const_node_ptr; 229 }; 230 231 template<class VoidPointer> 232 class any_algorithms 233 { 234 template <class T> function_not_available_for_any_hooks(typename detail::enable_if<detail::is_same<T,bool>>::type)235 static void function_not_available_for_any_hooks(typename detail::enable_if<detail::is_same<T, bool> >::type) 236 {} 237 238 public: 239 typedef any_node<VoidPointer> node; 240 typedef typename node::node_ptr node_ptr; 241 typedef typename node::const_node_ptr const_node_ptr; 242 typedef any_node_traits<VoidPointer> node_traits; 243 244 //! <b>Requires</b>: node must not be part of any tree. 245 //! 246 //! <b>Effects</b>: After the function unique(node) == true. 247 //! 248 //! <b>Complexity</b>: Constant. 249 //! 250 //! <b>Throws</b>: Nothing. 251 //! 252 //! <b>Nodes</b>: If node is inserted in a tree, this function corrupts the tree. init(const node_ptr & node)253 static void init(const node_ptr & node) 254 { node->node_ptr_1 = 0; }; 255 256 //! <b>Effects</b>: Returns true if node is in the same state as if called init(node) 257 //! 258 //! <b>Complexity</b>: Constant. 259 //! 260 //! <b>Throws</b>: Nothing. inited(const const_node_ptr & node)261 static bool inited(const const_node_ptr & node) 262 { return !node->node_ptr_1; }; 263 unique(const const_node_ptr & node)264 static bool unique(const const_node_ptr & node) 265 { return 0 == node->node_ptr_1; } 266 unlink(const node_ptr &)267 static void unlink(const node_ptr &) 268 { 269 //Auto-unlink hooks and unlink() are not available for any hooks 270 any_algorithms<VoidPointer>::template function_not_available_for_any_hooks<node_ptr>(); 271 } 272 swap_nodes(const node_ptr &,const node_ptr &)273 static void swap_nodes(const node_ptr &, const node_ptr &) 274 { 275 //Any nodes have no swap_nodes capability because they don't know 276 //what algorithm they must use to unlink the node from the container 277 any_algorithms<VoidPointer>::template function_not_available_for_any_hooks<node_ptr>(); 278 } 279 }; 280 281 } //namespace intrusive 282 } //namespace boost 283 284 #endif //BOOST_INTRUSIVE_ANY_NODE_HPP 285