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