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