1 ///////////////////////////////////////////////////////////////////////////// 2 // 3 // (C) Copyright Ion Gaztanaga 2007-2013 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_BS_SET_HOOK_HPP 14 #define BOOST_INTRUSIVE_BS_SET_HOOK_HPP 15 16 #include <boost/intrusive/detail/config_begin.hpp> 17 #include <boost/intrusive/intrusive_fwd.hpp> 18 19 #include <boost/intrusive/detail/tree_node.hpp> 20 #include <boost/intrusive/bstree_algorithms.hpp> 21 #include <boost/intrusive/options.hpp> 22 #include <boost/intrusive/detail/generic_hook.hpp> 23 24 #if defined(BOOST_HAS_PRAGMA_ONCE) 25 # pragma once 26 #endif 27 28 namespace boost { 29 namespace intrusive { 30 31 //! Helper metafunction to define a \c bs_set_base_hook that yields to the same 32 //! type when the same options (either explicitly or implicitly) are used. 33 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 34 template<class ...Options> 35 #else 36 template<class O1 = void, class O2 = void, class O3 = void> 37 #endif 38 struct make_bs_set_base_hook 39 { 40 /// @cond 41 typedef typename pack_options 42 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 43 < hook_defaults, O1, O2, O3> 44 #else 45 < hook_defaults, Options...> 46 #endif 47 ::type packed_options; 48 49 typedef generic_hook 50 < BsTreeAlgorithms 51 , tree_node_traits<typename packed_options::void_pointer> 52 , typename packed_options::tag 53 , packed_options::link_mode 54 , BsTreeBaseHookId 55 > implementation_defined; 56 /// @endcond 57 typedef implementation_defined type; 58 }; 59 60 //! Derive a class from bs_set_base_hook in order to store objects in 61 //! in a bs_set/bs_multiset. bs_set_base_hook holds the data necessary to maintain 62 //! the bs_set/bs_multiset and provides an appropriate value_traits class for bs_set/bs_multiset. 63 //! 64 //! The hook admits the following options: \c tag<>, \c void_pointer<>, 65 //! \c link_mode<>. 66 //! 67 //! \c tag<> defines a tag to identify the node. 68 //! The same tag value can be used in different classes, but if a class is 69 //! derived from more than one \c list_base_hook, then each \c list_base_hook needs its 70 //! unique tag. 71 //! 72 //! \c void_pointer<> is the pointer type that will be used internally in the hook 73 //! and the container configured to use this hook. 74 //! 75 //! \c link_mode<> will specify the linking mode of the hook (\c normal_link, 76 //! \c auto_unlink or \c safe_link). 77 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 78 template<class ...Options> 79 #else 80 template<class O1, class O2, class O3> 81 #endif 82 class bs_set_base_hook 83 : public make_bs_set_base_hook 84 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 85 <O1, O2, O3> 86 #else 87 <Options...> 88 #endif 89 ::type 90 91 { 92 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) 93 public: 94 //! <b>Effects</b>: If link_mode is \c auto_unlink or \c safe_link 95 //! initializes the node to an unlinked state. 96 //! 97 //! <b>Throws</b>: Nothing. 98 bs_set_base_hook(); 99 100 //! <b>Effects</b>: If link_mode is \c auto_unlink or \c safe_link 101 //! initializes the node to an unlinked state. The argument is ignored. 102 //! 103 //! <b>Throws</b>: Nothing. 104 //! 105 //! <b>Rationale</b>: Providing a copy-constructor 106 //! makes classes using the hook STL-compliant without forcing the 107 //! user to do some additional work. \c swap can be used to emulate 108 //! move-semantics. 109 bs_set_base_hook(const bs_set_base_hook& ); 110 111 //! <b>Effects</b>: Empty function. The argument is ignored. 112 //! 113 //! <b>Throws</b>: Nothing. 114 //! 115 //! <b>Rationale</b>: Providing an assignment operator 116 //! makes classes using the hook STL-compliant without forcing the 117 //! user to do some additional work. \c swap can be used to emulate 118 //! move-semantics. 119 bs_set_base_hook& operator=(const bs_set_base_hook& ); 120 121 //! <b>Effects</b>: If link_mode is \c normal_link, the destructor does 122 //! nothing (ie. no code is generated). If link_mode is \c safe_link and the 123 //! object is stored in a set an assertion is raised. If link_mode is 124 //! \c auto_unlink and \c is_linked() is true, the node is unlinked. 125 //! 126 //! <b>Throws</b>: Nothing. 127 ~bs_set_base_hook(); 128 129 //! <b>Effects</b>: Swapping two nodes swaps the position of the elements 130 //! related to those nodes in one or two containers. That is, if the node 131 //! this is part of the element e1, the node x is part of the element e2 132 //! and both elements are included in the containers s1 and s2, then after 133 //! the swap-operation e1 is in s2 at the position of e2 and e2 is in s1 134 //! at the position of e1. If one element is not in a container, then 135 //! after the swap-operation the other element is not in a container. 136 //! Iterators to e1 and e2 related to those nodes are invalidated. 137 //! 138 //! <b>Complexity</b>: Constant 139 //! 140 //! <b>Throws</b>: Nothing. 141 void swap_nodes(bs_set_base_hook &other); 142 143 //! <b>Precondition</b>: link_mode must be \c safe_link or \c auto_unlink. 144 //! 145 //! <b>Returns</b>: true, if the node belongs to a container, false 146 //! otherwise. This function can be used to test whether \c set::iterator_to 147 //! will return a valid iterator. 148 //! 149 //! <b>Complexity</b>: Constant 150 bool is_linked() const; 151 152 //! <b>Effects</b>: Removes the node if it's inserted in a container. 153 //! This function is only allowed if link_mode is \c auto_unlink. 154 //! 155 //! <b>Throws</b>: Nothing. 156 void unlink(); 157 #endif 158 }; 159 160 //! Helper metafunction to define a \c bs_set_member_hook that yields to the same 161 //! type when the same options (either explicitly or implicitly) are used. 162 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 163 template<class ...Options> 164 #else 165 template<class O1 = void, class O2 = void, class O3 = void> 166 #endif 167 struct make_bs_set_member_hook 168 { 169 /// @cond 170 typedef typename pack_options 171 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 172 < hook_defaults, O1, O2, O3> 173 #else 174 < hook_defaults, Options...> 175 #endif 176 177 ::type packed_options; 178 179 typedef generic_hook 180 < BsTreeAlgorithms 181 , tree_node_traits<typename packed_options::void_pointer> 182 , member_tag 183 , packed_options::link_mode 184 , NoBaseHookId 185 > implementation_defined; 186 /// @endcond 187 typedef implementation_defined type; 188 }; 189 190 //! Put a public data member bs_set_member_hook in order to store objects of this class in 191 //! a bs_set/bs_multiset. bs_set_member_hook holds the data necessary for maintaining the 192 //! bs_set/bs_multiset and provides an appropriate value_traits class for bs_set/bs_multiset. 193 //! 194 //! The hook admits the following options: \c void_pointer<>, \c link_mode<>. 195 //! 196 //! \c void_pointer<> is the pointer type that will be used internally in the hook 197 //! and the container configured to use this hook. 198 //! 199 //! \c link_mode<> will specify the linking mode of the hook (\c normal_link, 200 //! \c auto_unlink or \c safe_link). 201 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 202 template<class ...Options> 203 #else 204 template<class O1, class O2, class O3> 205 #endif 206 class bs_set_member_hook 207 : public make_bs_set_member_hook 208 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 209 <O1, O2, O3> 210 #else 211 <Options...> 212 #endif 213 ::type 214 { 215 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) 216 public: 217 //! <b>Effects</b>: If link_mode is \c auto_unlink or \c safe_link 218 //! initializes the node to an unlinked state. 219 //! 220 //! <b>Throws</b>: Nothing. 221 bs_set_member_hook(); 222 223 //! <b>Effects</b>: If link_mode is \c auto_unlink or \c safe_link 224 //! initializes the node to an unlinked state. The argument is ignored. 225 //! 226 //! <b>Throws</b>: Nothing. 227 //! 228 //! <b>Rationale</b>: Providing a copy-constructor 229 //! makes classes using the hook STL-compliant without forcing the 230 //! user to do some additional work. \c swap can be used to emulate 231 //! move-semantics. 232 bs_set_member_hook(const bs_set_member_hook& ); 233 234 //! <b>Effects</b>: Empty function. The argument is ignored. 235 //! 236 //! <b>Throws</b>: Nothing. 237 //! 238 //! <b>Rationale</b>: Providing an assignment operator 239 //! makes classes using the hook STL-compliant without forcing the 240 //! user to do some additional work. \c swap can be used to emulate 241 //! move-semantics. 242 bs_set_member_hook& operator=(const bs_set_member_hook& ); 243 244 //! <b>Effects</b>: If link_mode is \c normal_link, the destructor does 245 //! nothing (ie. no code is generated). If link_mode is \c safe_link and the 246 //! object is stored in a set an assertion is raised. If link_mode is 247 //! \c auto_unlink and \c is_linked() is true, the node is unlinked. 248 //! 249 //! <b>Throws</b>: Nothing. 250 ~bs_set_member_hook(); 251 252 //! <b>Effects</b>: Swapping two nodes swaps the position of the elements 253 //! related to those nodes in one or two containers. That is, if the node 254 //! this is part of the element e1, the node x is part of the element e2 255 //! and both elements are included in the containers s1 and s2, then after 256 //! the swap-operation e1 is in s2 at the position of e2 and e2 is in s1 257 //! at the position of e1. If one element is not in a container, then 258 //! after the swap-operation the other element is not in a container. 259 //! Iterators to e1 and e2 related to those nodes are invalidated. 260 //! 261 //! <b>Complexity</b>: Constant 262 //! 263 //! <b>Throws</b>: Nothing. 264 void swap_nodes(bs_set_member_hook &other); 265 266 //! <b>Precondition</b>: link_mode must be \c safe_link or \c auto_unlink. 267 //! 268 //! <b>Returns</b>: true, if the node belongs to a container, false 269 //! otherwise. This function can be used to test whether \c set::iterator_to 270 //! will return a valid iterator. 271 //! 272 //! <b>Complexity</b>: Constant 273 bool is_linked() const; 274 275 //! <b>Effects</b>: Removes the node if it's inserted in a container. 276 //! This function is only allowed if link_mode is \c auto_unlink. 277 //! 278 //! <b>Throws</b>: Nothing. 279 void unlink(); 280 #endif 281 }; 282 283 } //namespace intrusive 284 } //namespace boost 285 286 #include <boost/intrusive/detail/config_end.hpp> 287 288 #endif //BOOST_INTRUSIVE_BS_SET_HOOK_HPP 289