ceph/src/boost/boost/intrusive/unordered_set_hook.hpp

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