git.sesse.net Git - casparcg/blob - dependencies/boost/boost/intrusive/unordered_set_hook.hpp

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