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