boost/intrusive/unordered_set_hook.hpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Olaf Krzikalla 2004-2006.
   4 // (C) Copyright Ion Gaztanaga  2006-2012
   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_UNORDERED_SET_HOOK_HPP
  15 #define BOOST_INTRUSIVE_UNORDERED_SET_HOOK_HPP
  16
  17 #include <boost/intrusive/detail/config_begin.hpp>
  18 #include <boost/intrusive/intrusive_fwd.hpp>
  19 #include <boost/pointer_cast.hpp>
  20 #include <boost/intrusive/detail/utilities.hpp>
  21 #include <boost/intrusive/pointer_traits.hpp>
  22 #include <boost/intrusive/slist_hook.hpp>
  23 #include <boost/intrusive/options.hpp>
  24 #include <boost/intrusive/pointer_traits.hpp>
  25 #include <boost/intrusive/detail/generic_hook.hpp>
  26
  27 namespace boost {
  28 namespace intrusive {
  29
  30 /// @cond
  31
  32 template<class VoidPointer, bool StoreHash, bool OptimizeMultiKey>
  33 struct unordered_node
  34    :  public slist_node<VoidPointer>
  35 {
  36    typedef typename pointer_traits
  37       <VoidPointer>::template rebind_pointer
  38          < unordered_node<VoidPointer, StoreHash, OptimizeMultiKey> >::type
  39       node_ptr;
  40    node_ptr    prev_in_group_;
  41    std::size_t hash_;
  42 };
  43
  44 template<class VoidPointer>
  45 struct unordered_node<VoidPointer, false, true>
  46    :  public slist_node<VoidPointer>
  47 {
  48    typedef typename pointer_traits
  49       <VoidPointer>::template rebind_pointer
  50          < unordered_node<VoidPointer, false, true> >::type
  51       node_ptr;
  52    node_ptr    prev_in_group_;
  53 };
  54
  55 template<class VoidPointer>
  56 struct unordered_node<VoidPointer, true, false>
  57    :  public slist_node<VoidPointer>
  58 {
  59    typedef typename pointer_traits
  60       <VoidPointer>::template rebind_pointer
  61          < unordered_node<VoidPointer, true, false> >::type
  62       node_ptr;
  63    std::size_t hash_;
  64 };
  65
  66 template<class VoidPointer, bool StoreHash, bool OptimizeMultiKey>
  67 struct unordered_node_traits
  68    :  public slist_node_traits<VoidPointer>
  69 {
  70    typedef slist_node_traits<VoidPointer> reduced_slist_node_traits;
  71    typedef unordered_node<VoidPointer, StoreHash, OptimizeMultiKey> node;
  72
  73    typedef typename pointer_traits
  74       <VoidPointer>::template rebind_pointer
  75          < node >::type node_ptr;
  76    typedef typename pointer_traits
  77       <VoidPointer>::template rebind_pointer
  78          < const node >::type const_node_ptr;
  79
  80    static const bool store_hash        = StoreHash;
  81    static const bool optimize_multikey = OptimizeMultiKey;
  82
  83    static node_ptr get_next(const const_node_ptr & n)
  84    {
  85       return pointer_traits<node_ptr>::pointer_to(static_cast<node&>(*n->next_));
  86    }
  87
  88    static void set_next(const node_ptr & n, const node_ptr & next)
  89    {  n->next_ = next;  }
  90
  91    static node_ptr get_prev_in_group(const const_node_ptr & n)
  92    {  return n->prev_in_group_;  }
  93
  94    static void set_prev_in_group(const node_ptr & n, const node_ptr & prev)
  95    {  n->prev_in_group_ = prev;  }
  96
  97    static std::size_t get_hash(const const_node_ptr & n)
  98    {  return n->hash_;  }
  99
 100    static void set_hash(const node_ptr & n, std::size_t h)
 101    {  n->hash_ = h;  }
 102 };
 103
 104 template<class NodeTraits>
 105 struct unordered_group_adapter
 106 {
 107    typedef typename NodeTraits::node            node;
 108    typedef typename NodeTraits::node_ptr        node_ptr;
 109    typedef typename NodeTraits::const_node_ptr  const_node_ptr;
 110
 111    static node_ptr get_next(const const_node_ptr & n)
 112    {  return NodeTraits::get_prev_in_group(n);  }
 113
 114    static void set_next(const node_ptr & n, const node_ptr & next)
 115    {  NodeTraits::set_prev_in_group(n, next);   }
 116 };
 117
 118 template<class NodeTraits>
 119 struct unordered_algorithms
 120    : public circular_slist_algorithms<NodeTraits>
 121 {
 122    typedef circular_slist_algorithms<NodeTraits>   base_type;
 123    typedef unordered_group_adapter<NodeTraits> group_traits;
 124    typedef circular_slist_algorithms<group_traits> group_algorithms;
 125
 126    static void init(typename base_type::node_ptr n)
 127    {
 128       base_type::init(n);
 129       group_algorithms::init(n);
 130    }
 131
 132    static void init_header(typename base_type::node_ptr n)
 133    {
 134       base_type::init_header(n);
 135       group_algorithms::init_header(n);
 136    }
 137
 138    static void unlink(typename base_type::node_ptr n)
 139    {
 140       base_type::unlink(n);
 141       group_algorithms::unlink(n);
 142    }
 143 };
 144
 145 template<class VoidPointer, bool StoreHash, bool OptimizeMultiKey>
 146 struct get_uset_node_algo
 147 {
 148    typedef typename detail::if_c
 149       < (StoreHash || OptimizeMultiKey)
 150       , unordered_node_traits<VoidPointer, StoreHash, OptimizeMultiKey>
 151       , slist_node_traits<VoidPointer>
 152       >::type node_traits_type;
 153    typedef typename detail::if_c
 154       < OptimizeMultiKey
 155       , unordered_algorithms<node_traits_type>
 156       , circular_slist_algorithms<node_traits_type>
 157       >::type type;
 158 };
 159 /// @endcond
 160
 161 //! Helper metafunction to define a \c unordered_set_base_hook that yields to the same
 162 //! type when the same options (either explicitly or implicitly) are used.
 163 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 164 template<class ...Options>
 165 #else
 166 template<class O1 = none, class O2 = none, class O3 = none, class O4 = none>
 167 #endif
 168 struct make_unordered_set_base_hook
 169 {
 170    /// @cond
 171    typedef typename pack_options
 172       < hook_defaults,
 173          #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 174          O1, O2, O3, O4
 175          #else
 176          Options...
 177          #endif
 178       >::type packed_options;
 179
 180    typedef detail::generic_hook
 181    < get_uset_node_algo<typename packed_options::void_pointer
 182                        , packed_options::store_hash
 183                        , packed_options::optimize_multikey
 184                        >
 185    , typename packed_options::tag
 186    , packed_options::link_mode
 187    , detail::UsetBaseHook
 188    > implementation_defined;
 189    /// @endcond
 190    typedef implementation_defined type;
 191 };
 192
 193 //! Derive a class from unordered_set_base_hook in order to store objects in
 194 //! in an unordered_set/unordered_multi_set. unordered_set_base_hook holds the data necessary to maintain
 195 //! the unordered_set/unordered_multi_set and provides an appropriate value_traits class for unordered_set/unordered_multi_set.
 196 //!
 197 //! The hook admits the following options: \c tag<>, \c void_pointer<>,
 198 //! \c link_mode<>, \c store_hash<> and \c optimize_multikey<>.
 199 //!
 200 //! \c tag<> defines a tag to identify the node.
 201 //! The same tag value can be used in different classes, but if a class is
 202 //! derived from more than one \c list_base_hook, then each \c list_base_hook needs its
 203 //! unique tag.
 204 //!
 205 //! \c void_pointer<> is the pointer type that will be used internally in the hook
 206 //! and the the container configured to use this hook.
 207 //!
 208 //! \c link_mode<> will specify the linking mode of the hook (\c normal_link,
 209 //! \c auto_unlink or \c safe_link).
 210 //!
 211 //! \c store_hash<> will tell the hook to store the hash of the value
 212 //! to speed up rehashings.
 213 //!
 214 //! \c optimize_multikey<> will tell the hook to store a link to form a group
 215 //! with other value with the same value to speed up searches and insertions
 216 //! in unordered_multisets with a great number of with equivalent keys.
 217 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 218 template<class ...Options>
 219 #else
 220 template<class O1, class O2, class O3, class O4>
 221 #endif
 222 class unordered_set_base_hook
 223    :  public make_unordered_set_base_hook<
 224          #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 225          O1, O2, O3, O4
 226          #else
 227          Options...
 228          #endif
 229       >::type
 230 {
 231    #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 232    public:
 233    //! <b>Effects</b>: If link_mode is \c auto_unlink or \c safe_link
 234    //!   initializes the node to an unlinked state.
 235    //!
 236    //! <b>Throws</b>: Nothing.
 237    unordered_set_base_hook();
 238
 239    //! <b>Effects</b>: If link_mode is \c auto_unlink or \c safe_link
 240    //!   initializes the node to an unlinked state. The argument is ignored.
 241    //!
 242    //! <b>Throws</b>: Nothing.
 243    //!
 244    //! <b>Rationale</b>: Providing a copy-constructor
 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    unordered_set_base_hook(const unordered_set_base_hook& );
 249
 250    //! <b>Effects</b>: Empty function. The argument is ignored.
 251    //!
 252    //! <b>Throws</b>: Nothing.
 253    //!
 254    //! <b>Rationale</b>: Providing an assignment operator
 255    //!   makes classes using the hook STL-compliant without forcing the
 256    //!   user to do some additional work. \c swap can be used to emulate
 257    //!   move-semantics.
 258    unordered_set_base_hook& operator=(const unordered_set_base_hook& );
 259
 260    //! <b>Effects</b>: If link_mode is \c normal_link, the destructor does
 261    //!   nothing (ie. no code is generated). If link_mode is \c safe_link and the
 262    //!   object is stored in an unordered_set an assertion is raised. If link_mode is
 263    //!   \c auto_unlink and \c is_linked() is true, the node is unlinked.
 264    //!
 265    //! <b>Throws</b>: Nothing.
 266    ~unordered_set_base_hook();
 267
 268    //! <b>Effects</b>: Swapping two nodes swaps the position of the elements
 269    //!   related to those nodes in one or two containers. That is, if the node
 270    //!   this is part of the element e1, the node x is part of the element e2
 271    //!   and both elements are included in the containers s1 and s2, then after
 272    //!   the swap-operation e1 is in s2 at the position of e2 and e2 is in s1
 273    //!   at the position of e1. If one element is not in a container, then
 274    //!   after the swap-operation the other element is not in a container.
 275    //!   Iterators to e1 and e2 related to those nodes are invalidated.
 276    //!
 277    //! <b>Complexity</b>: Constant
 278    //!
 279    //! <b>Throws</b>: Nothing.
 280    void swap_nodes(unordered_set_base_hook &other);
 281
 282    //! <b>Precondition</b>: link_mode must be \c safe_link or \c auto_unlink.
 283    //!
 284    //! <b>Returns</b>: true, if the node belongs to a container, false
 285    //!   otherwise. This function can be used to test whether \c unordered_set::iterator_to
 286    //!   will return a valid iterator.
 287    //!
 288    //! <b>Complexity</b>: Constant
 289    bool is_linked() const;
 290
 291    //! <b>Effects</b>: Removes the node if it's inserted in a container.
 292    //!   This function is only allowed if link_mode is \c auto_unlink.
 293    //!
 294    //! <b>Throws</b>: Nothing.
 295    void unlink();
 296    #endif
 297 };
 298
 299
 300 //! Helper metafunction to define a \c unordered_set_member_hook that yields to the same
 301 //! type when the same options (either explicitly or implicitly) are used.
 302 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 303 template<class ...Options>
 304 #else
 305 template<class O1 = none, class O2 = none, class O3 = none, class O4 = none>
 306 #endif
 307 struct make_unordered_set_member_hook
 308 {
 309    /// @cond
 310    typedef typename pack_options
 311       < hook_defaults,
 312          #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 313          O1, O2, O3, O4
 314          #else
 315          Options...
 316          #endif
 317       >::type packed_options;
 318
 319    typedef detail::generic_hook
 320    < get_uset_node_algo< typename packed_options::void_pointer
 321                        , packed_options::store_hash
 322                        , packed_options::optimize_multikey
 323                        >
 324    , member_tag
 325    , packed_options::link_mode
 326    , detail::NoBaseHook
 327    > implementation_defined;
 328    /// @endcond
 329    typedef implementation_defined type;
 330 };
 331
 332 //! Put a public data member unordered_set_member_hook in order to store objects of this class in
 333 //! an unordered_set/unordered_multi_set. unordered_set_member_hook holds the data necessary for maintaining the
 334 //! unordered_set/unordered_multi_set and provides an appropriate value_traits class for unordered_set/unordered_multi_set.
 335 //!
 336 //! The hook admits the following options: \c void_pointer<>,
 337 //! \c link_mode<> and \c store_hash<>.
 338 //!
 339 //! \c void_pointer<> is the pointer type that will be used internally in the hook
 340 //! and the the container configured to use this hook.
 341 //!
 342 //! \c link_mode<> will specify the linking mode of the hook (\c normal_link,
 343 //! \c auto_unlink or \c safe_link).
 344 //!
 345 //! \c store_hash<> will tell the hook to store the hash of the value
 346 //! to speed up rehashings.
 347 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 348 template<class ...Options>
 349 #else
 350 template<class O1, class O2, class O3, class O4>
 351 #endif
 352 class unordered_set_member_hook
 353    :  public make_unordered_set_member_hook<
 354          #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 355          O1, O2, O3, O4
 356          #else
 357          Options...
 358          #endif
 359    >::type
 360 {
 361    #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 362    public:
 363    //! <b>Effects</b>: If link_mode is \c auto_unlink or \c safe_link
 364    //!   initializes the node to an unlinked state.
 365    //!
 366    //! <b>Throws</b>: Nothing.
 367    unordered_set_member_hook();
 368
 369    //! <b>Effects</b>: If link_mode is \c auto_unlink or \c safe_link
 370    //!   initializes the node to an unlinked state. The argument is ignored.
 371    //!
 372    //! <b>Throws</b>: Nothing.
 373    //!
 374    //! <b>Rationale</b>: Providing a copy-constructor
 375    //!   makes classes using the hook STL-compliant without forcing the
 376    //!   user to do some additional work. \c swap can be used to emulate
 377    //!   move-semantics.
 378    unordered_set_member_hook(const unordered_set_member_hook& );
 379
 380    //! <b>Effects</b>: Empty function. The argument is ignored.
 381    //!
 382    //! <b>Throws</b>: Nothing.
 383    //!
 384    //! <b>Rationale</b>: Providing an assignment operator
 385    //!   makes classes using the hook STL-compliant without forcing the
 386    //!   user to do some additional work. \c swap can be used to emulate
 387    //!   move-semantics.
 388    unordered_set_member_hook& operator=(const unordered_set_member_hook& );
 389
 390    //! <b>Effects</b>: If link_mode is \c normal_link, the destructor does
 391    //!   nothing (ie. no code is generated). If link_mode is \c safe_link and the
 392    //!   object is stored in an unordered_set an assertion is raised. If link_mode is
 393    //!   \c auto_unlink and \c is_linked() is true, the node is unlinked.
 394    //!
 395    //! <b>Throws</b>: Nothing.
 396    ~unordered_set_member_hook();
 397
 398    //! <b>Effects</b>: Swapping two nodes swaps the position of the elements
 399    //!   related to those nodes in one or two containers. That is, if the node
 400    //!   this is part of the element e1, the node x is part of the element e2
 401    //!   and both elements are included in the containers s1 and s2, then after
 402    //!   the swap-operation e1 is in s2 at the position of e2 and e2 is in s1
 403    //!   at the position of e1. If one element is not in a container, then
 404    //!   after the swap-operation the other element is not in a container.
 405    //!   Iterators to e1 and e2 related to those nodes are invalidated.
 406    //!
 407    //! <b>Complexity</b>: Constant
 408    //!
 409    //! <b>Throws</b>: Nothing.
 410    void swap_nodes(unordered_set_member_hook &other);
 411
 412    //! <b>Precondition</b>: link_mode must be \c safe_link or \c auto_unlink.
 413    //!
 414    //! <b>Returns</b>: true, if the node belongs to a container, false
 415    //!   otherwise. This function can be used to test whether \c unordered_set::iterator_to
 416    //!   will return a valid iterator.
 417    //!
 418    //! <b>Complexity</b>: Constant
 419    bool is_linked() const;
 420
 421    //! <b>Effects</b>: Removes the node if it's inserted in a container.
 422    //!   This function is only allowed if link_mode is \c auto_unlink.
 423    //!
 424    //! <b>Throws</b>: Nothing.
 425    void unlink();
 426    #endif
 427 };
 428
 429 } //namespace intrusive
 430 } //namespace boost
 431
 432 #include <boost/intrusive/detail/config_end.hpp>
 433
 434 #endif //BOOST_INTRUSIVE_UNORDERED_SET_HOOK_HPP