boost/intrusive/set_hook.hpp

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