boost/intrusive/bs_set_hook.hpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga 2007-2008
   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 #include <boost/intrusive/detail/utilities.hpp>
  19 #include <boost/intrusive/detail/tree_node.hpp>
  20 #include <boost/intrusive/detail/tree_algorithms.hpp>
  21 #include <boost/intrusive/options.hpp>
  22 #include <boost/intrusive/detail/generic_hook.hpp>
  23
  24 namespace boost {
  25 namespace intrusive {
  26
  27 /// @cond
  28 template<class VoidPointer>
  29 struct get_bs_set_node_algo
  30 {
  31    typedef detail::tree_algorithms<tree_node_traits<VoidPointer> > type;
  32 };
  33 /// @endcond
  34
  35 //! Helper metafunction to define a \c bs_set_base_hook that yields to the same
  36 //! type when the same options (either explicitly or implicitly) are used.
  37 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
  38 template<class ...Options>
  39 #else
  40 template<class O1 = none, class O2 = none, class O3 = none>
  41 #endif
  42 struct make_bs_set_base_hook
  43 {
  44    /// @cond
  45    typedef typename pack_options
  46    #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
  47       < hook_defaults, O1, O2, O3>
  48    #else
  49       < hook_defaults, Options...>
  50    #endif
  51    ::type packed_options;
  52
  53    //Scapegoat trees can't be auto unlink trees
  54    BOOST_STATIC_ASSERT(((int)packed_options::link_mode != (int)auto_unlink));
  55
  56    typedef detail::generic_hook
  57    < get_bs_set_node_algo<typename packed_options::void_pointer>
  58    , typename packed_options::tag
  59    , packed_options::link_mode
  60    , detail::BsSetBaseHook
  61    > implementation_defined;
  62    /// @endcond
  63    typedef implementation_defined type;
  64 };
  65
  66 //! Derive a class from bs_set_base_hook in order to store objects in
  67 //! in a bs_set/bs_multiset. bs_set_base_hook holds the data necessary to maintain
  68 //! the bs_set/bs_multiset and provides an appropriate value_traits class for bs_set/bs_multiset.
  69 //!
  70 //! The hook admits the following options: \c tag<>, \c void_pointer<>,
  71 //! \c link_mode<>.
  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 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
  84 template<class ...Options>
  85 #else
  86 template<class O1, class O2, class O3>
  87 #endif
  88 class bs_set_base_hook
  89    :  public make_bs_set_base_hook
  90    #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
  91       <O1, O2, O3>
  92    #else
  93       <Options...>
  94    #endif
  95    ::type
  96
  97 {
  98    #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
  99    //! <b>Effects</b>: If link_mode is \c auto_unlink or \c safe_link
 100    //!   initializes the node to an unlinked state.
 101    //!
 102    //! <b>Throws</b>: Nothing.
 103    bs_set_base_hook();
 104
 105    //! <b>Effects</b>: If link_mode is \c auto_unlink or \c safe_link
 106    //!   initializes the node to an unlinked state. The argument is ignored.
 107    //!
 108    //! <b>Throws</b>: Nothing.
 109    //!
 110    //! <b>Rationale</b>: Providing a copy-constructor
 111    //!   makes classes using the hook STL-compliant without forcing the
 112    //!   user to do some additional work. \c swap can be used to emulate
 113    //!   move-semantics.
 114    bs_set_base_hook(const bs_set_base_hook& );
 115
 116    //! <b>Effects</b>: Empty function. The argument is ignored.
 117    //!
 118    //! <b>Throws</b>: Nothing.
 119    //!
 120    //! <b>Rationale</b>: Providing an assignment operator
 121    //!   makes classes using the hook STL-compliant without forcing the
 122    //!   user to do some additional work. \c swap can be used to emulate
 123    //!   move-semantics.
 124    bs_set_base_hook& operator=(const bs_set_base_hook& );
 125
 126    //! <b>Effects</b>: If link_mode is \c normal_link, the destructor does
 127    //!   nothing (ie. no code is generated). If link_mode is \c safe_link and the
 128    //!   object is stored in a set an assertion is raised. If link_mode is
 129    //!   \c auto_unlink and \c is_linked() is true, the node is unlinked.
 130    //!
 131    //! <b>Throws</b>: Nothing.
 132    ~bs_set_base_hook();
 133
 134    //! <b>Effects</b>: Swapping two nodes swaps the position of the elements
 135    //!   related to those nodes in one or two containers. That is, if the node
 136    //!   this is part of the element e1, the node x is part of the element e2
 137    //!   and both elements are included in the containers s1 and s2, then after
 138    //!   the swap-operation e1 is in s2 at the position of e2 and e2 is in s1
 139    //!   at the position of e1. If one element is not in a container, then
 140    //!   after the swap-operation the other element is not in a container.
 141    //!   Iterators to e1 and e2 related to those nodes are invalidated.
 142    //!
 143    //! <b>Complexity</b>: Constant
 144    //!
 145    //! <b>Throws</b>: Nothing.
 146    void swap_nodes(bs_set_base_hook &other);
 147
 148    //! <b>Precondition</b>: link_mode must be \c safe_link or \c auto_unlink.
 149    //!
 150    //! <b>Returns</b>: true, if the node belongs to a container, false
 151    //!   otherwise. This function can be used to test whether \c set::iterator_to
 152    //!   will return a valid iterator.
 153    //!
 154    //! <b>Complexity</b>: Constant
 155    bool is_linked() const;
 156
 157    //! <b>Effects</b>: Removes the node if it's inserted in a container.
 158    //!   This function is only allowed if link_mode is \c auto_unlink.
 159    //!
 160    //! <b>Throws</b>: Nothing.
 161    void unlink();
 162    #endif
 163 };
 164
 165 //! Helper metafunction to define a \c bs_set_member_hook that yields to the same
 166 //! type when the same options (either explicitly or implicitly) are used.
 167 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 168 template<class ...Options>
 169 #else
 170 template<class O1 = none, class O2 = none, class O3 = none>
 171 #endif
 172 struct make_bs_set_member_hook
 173 {
 174    /// @cond
 175    typedef typename pack_options
 176    #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 177       < hook_defaults, O1, O2, O3>
 178    #else
 179       < hook_defaults, Options...>
 180    #endif
 181
 182    ::type packed_options;
 183
 184    //Scapegoat trees can't be auto unlink trees
 185    BOOST_STATIC_ASSERT(((int)packed_options::link_mode != (int)auto_unlink));
 186
 187    typedef detail::generic_hook
 188    < get_bs_set_node_algo<typename packed_options::void_pointer>
 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 bs_set_member_hook in order to store objects of this class in
 198 //! a bs_set/bs_multiset. bs_set_member_hook holds the data necessary for maintaining the
 199 //! bs_set/bs_multiset and provides an appropriate value_traits class for bs_set/bs_multiset.
 200 //!
 201 //! The hook admits the following options: \c void_pointer<>, \c link_mode<>.
 202 //!
 203 //! \c void_pointer<> is the pointer type that will be used internally in the hook
 204 //! and the the container configured to use this hook.
 205 //!
 206 //! \c link_mode<> will specify the linking mode of the hook (\c normal_link,
 207 //! \c auto_unlink or \c safe_link).
 208 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 209 template<class ...Options>
 210 #else
 211 template<class O1, class O2, class O3>
 212 #endif
 213 class bs_set_member_hook
 214    :  public make_bs_set_member_hook
 215       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 216       <O1, O2, O3>
 217       #else
 218       <Options...>
 219       #endif
 220       ::type
 221 {
 222    #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 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    bs_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    bs_set_member_hook(const bs_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    bs_set_member_hook& operator=(const bs_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    ~bs_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(bs_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_BS_SET_HOOK_HPP