ceph/src/boost/libs/intrusive/include/boost/intrusive/avl_set_hook.hpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga 2007-2013
   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_AVL_SET_HOOK_HPP
  14 #define BOOST_INTRUSIVE_AVL_SET_HOOK_HPP
  15
  16 #include <boost/intrusive/detail/config_begin.hpp>
  17 #include <boost/intrusive/intrusive_fwd.hpp>
  18
  19 #include <boost/intrusive/detail/avltree_node.hpp>
  20 #include <boost/intrusive/avltree_algorithms.hpp>
  21 #include <boost/intrusive/options.hpp>
  22 #include <boost/intrusive/detail/generic_hook.hpp>
  23
  24 #if defined(BOOST_HAS_PRAGMA_ONCE)
  25 #  pragma once
  26 #endif
  27
  28 namespace boost {
  29 namespace intrusive {
  30
  31 //! Helper metafunction to define a \c avl_set_base_hook that yields to the same
  32 //! type when the same options (either explicitly or implicitly) are used.
  33 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
  34 template<class ...Options>
  35 #else
  36 template<class O1 = void, class O2 = void, class O3 = void, class O4 = void>
  37 #endif
  38 struct make_avl_set_base_hook
  39 {
  40    /// @cond
  41    typedef typename pack_options
  42       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
  43       <hook_defaults, O1, O2, O3, O4>
  44       #else
  45       <hook_defaults, Options...>
  46       #endif
  47       ::type packed_options;
  48
  49    typedef generic_hook
  50    < AvlTreeAlgorithms
  51    , avltree_node_traits<typename packed_options::void_pointer, packed_options::optimize_size>
  52    , typename packed_options::tag
  53    , packed_options::link_mode
  54    , AvlTreeBaseHookId
  55    > implementation_defined;
  56    /// @endcond
  57    typedef implementation_defined type;
  58 };
  59
  60 //! Derive a class from avl_set_base_hook in order to store objects in
  61 //! in an avl_set/avl_multiset. avl_set_base_hook holds the data necessary to maintain
  62 //! the avl_set/avl_multiset and provides an appropriate value_traits class for avl_set/avl_multiset.
  63 //!
  64 //! The hook admits the following options: \c tag<>, \c void_pointer<>,
  65 //! \c link_mode<> and \c optimize_size<>.
  66 //!
  67 //! \c tag<> defines a tag to identify the node.
  68 //! The same tag value can be used in different classes, but if a class is
  69 //! derived from more than one \c list_base_hook, then each \c list_base_hook needs its
  70 //! unique tag.
  71 //!
  72 //! \c void_pointer<> is the pointer type that will be used internally in the hook
  73 //! and the container configured to use this hook.
  74 //!
  75 //! \c link_mode<> will specify the linking mode of the hook (\c normal_link,
  76 //! \c auto_unlink or \c safe_link).
  77 //!
  78 //! \c optimize_size<> will tell the hook to optimize the hook for size instead
  79 //! of speed.
  80 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
  81 template<class ...Options>
  82 #else
  83 template<class O1, class O2, class O3, class O4>
  84 #endif
  85 class avl_set_base_hook
  86    :  public make_avl_set_base_hook
  87       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
  88       <O1, O2, O3, O4>
  89       #else
  90       <Options...>
  91       #endif
  92       ::type
  93 {
  94    #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
  95    public:
  96    //! <b>Effects</b>: If link_mode is \c auto_unlink or \c safe_link
  97    //!   initializes the node to an unlinked state.
  98    //!
  99    //! <b>Throws</b>: Nothing.
 100    avl_set_base_hook();
 101
 102    //! <b>Effects</b>: If link_mode is \c auto_unlink or \c safe_link
 103    //!   initializes the node to an unlinked state. The argument is ignored.
 104    //!
 105    //! <b>Throws</b>: Nothing.
 106    //!
 107    //! <b>Rationale</b>: Providing a copy-constructor
 108    //!   makes classes using the hook STL-compliant without forcing the
 109    //!   user to do some additional work. \c swap can be used to emulate
 110    //!   move-semantics.
 111    avl_set_base_hook(const avl_set_base_hook& );
 112
 113    //! <b>Effects</b>: Empty function. The argument is ignored.
 114    //!
 115    //! <b>Throws</b>: Nothing.
 116    //!
 117    //! <b>Rationale</b>: Providing an assignment operator
 118    //!   makes classes using the hook STL-compliant without forcing the
 119    //!   user to do some additional work. \c swap can be used to emulate
 120    //!   move-semantics.
 121    avl_set_base_hook& operator=(const avl_set_base_hook& );
 122
 123    //! <b>Effects</b>: If link_mode is \c normal_link, the destructor does
 124    //!   nothing (ie. no code is generated). If link_mode is \c safe_link and the
 125    //!   object is stored in a set an assertion is raised. If link_mode is
 126    //!   \c auto_unlink and \c is_linked() is true, the node is unlinked.
 127    //!
 128    //! <b>Throws</b>: Nothing.
 129    ~avl_set_base_hook();
 130
 131    //! <b>Effects</b>: Swapping two nodes swaps the position of the elements
 132    //!   related to those nodes in one or two containers. That is, if the node
 133    //!   this is part of the element e1, the node x is part of the element e2
 134    //!   and both elements are included in the containers s1 and s2, then after
 135    //!   the swap-operation e1 is in s2 at the position of e2 and e2 is in s1
 136    //!   at the position of e1. If one element is not in a container, then
 137    //!   after the swap-operation the other element is not in a container.
 138    //!   Iterators to e1 and e2 related to those nodes are invalidated.
 139    //!
 140    //! <b>Complexity</b>: Constant
 141    //!
 142    //! <b>Throws</b>: Nothing.
 143    void swap_nodes(avl_set_base_hook &other);
 144
 145    //! <b>Precondition</b>: link_mode must be \c safe_link or \c auto_unlink.
 146    //!
 147    //! <b>Returns</b>: true, if the node belongs to a container, false
 148    //!   otherwise. This function can be used to test whether \c set::iterator_to
 149    //!   will return a valid iterator.
 150    //!
 151    //! <b>Complexity</b>: Constant
 152    bool is_linked() const;
 153
 154    //! <b>Effects</b>: Removes the node if it's inserted in a container.
 155    //!   This function is only allowed if link_mode is \c auto_unlink.
 156    //!
 157    //! <b>Throws</b>: Nothing.
 158    void unlink();
 159    #endif
 160 };
 161
 162 //! Helper metafunction to define a \c avl_set_member_hook that yields to the same
 163 //! type when the same options (either explicitly or implicitly) are used.
 164 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 165 template<class ...Options>
 166 #else
 167 template<class O1 = void, class O2 = void, class O3 = void, class O4 = void>
 168 #endif
 169 struct make_avl_set_member_hook
 170 {
 171    /// @cond
 172    typedef typename pack_options
 173       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 174       <hook_defaults, O1, O2, O3, O4>
 175       #else
 176       <hook_defaults, Options...>
 177       #endif
 178       ::type packed_options;
 179
 180    typedef generic_hook
 181    < AvlTreeAlgorithms
 182    , avltree_node_traits<typename packed_options::void_pointer, packed_options::optimize_size>
 183    , member_tag
 184    , packed_options::link_mode
 185    , NoBaseHookId
 186    > implementation_defined;
 187    /// @endcond
 188    typedef implementation_defined type;
 189 };
 190
 191 //! Put a public data member avl_set_member_hook in order to store objects of this class in
 192 //! an avl_set/avl_multiset. avl_set_member_hook holds the data necessary for maintaining the
 193 //! avl_set/avl_multiset and provides an appropriate value_traits class for avl_set/avl_multiset.
 194 //!
 195 //! The hook admits the following options: \c void_pointer<>,
 196 //! \c link_mode<> and \c optimize_size<>.
 197 //!
 198 //! \c void_pointer<> is the pointer type that will be used internally in the hook
 199 //! and 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 optimize_size<> will tell the hook to optimize the hook for size instead
 205 //! of speed.
 206 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 207 template<class ...Options>
 208 #else
 209 template<class O1, class O2, class O3, class O4>
 210 #endif
 211 class avl_set_member_hook
 212    :  public make_avl_set_member_hook
 213       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 214       <O1, O2, O3, O4>
 215       #else
 216       <Options...>
 217       #endif
 218       ::type
 219 {
 220    #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 221    public:
 222    //! <b>Effects</b>: If link_mode is \c auto_unlink or \c safe_link
 223    //!   initializes the node to an unlinked state.
 224    //!
 225    //! <b>Throws</b>: Nothing.
 226    avl_set_member_hook();
 227
 228    //! <b>Effects</b>: If link_mode is \c auto_unlink or \c safe_link
 229    //!   initializes the node to an unlinked state. The argument is ignored.
 230    //!
 231    //! <b>Throws</b>: Nothing.
 232    //!
 233    //! <b>Rationale</b>: Providing a copy-constructor
 234    //!   makes classes using the hook STL-compliant without forcing the
 235    //!   user to do some additional work. \c swap can be used to emulate
 236    //!   move-semantics.
 237    avl_set_member_hook(const avl_set_member_hook& );
 238
 239    //! <b>Effects</b>: Empty function. The argument is ignored.
 240    //!
 241    //! <b>Throws</b>: Nothing.
 242    //!
 243    //! <b>Rationale</b>: Providing an assignment operator
 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    avl_set_member_hook& operator=(const avl_set_member_hook& );
 248
 249    //! <b>Effects</b>: If link_mode is \c normal_link, the destructor does
 250    //!   nothing (ie. no code is generated). If link_mode is \c safe_link and the
 251    //!   object is stored in a set an assertion is raised. If link_mode is
 252    //!   \c auto_unlink and \c is_linked() is true, the node is unlinked.
 253    //!
 254    //! <b>Throws</b>: Nothing.
 255    ~avl_set_member_hook();
 256
 257    //! <b>Effects</b>: Swapping two nodes swaps the position of the elements
 258    //!   related to those nodes in one or two containers. That is, if the node
 259    //!   this is part of the element e1, the node x is part of the element e2
 260    //!   and both elements are included in the containers s1 and s2, then after
 261    //!   the swap-operation e1 is in s2 at the position of e2 and e2 is in s1
 262    //!   at the position of e1. If one element is not in a container, then
 263    //!   after the swap-operation the other element is not in a container.
 264    //!   Iterators to e1 and e2 related to those nodes are invalidated.
 265    //!
 266    //! <b>Complexity</b>: Constant
 267    //!
 268    //! <b>Throws</b>: Nothing.
 269    void swap_nodes(avl_set_member_hook &other);
 270
 271    //! <b>Precondition</b>: link_mode must be \c safe_link or \c auto_unlink.
 272    //!
 273    //! <b>Returns</b>: true, if the node belongs to a container, false
 274    //!   otherwise. This function can be used to test whether \c set::iterator_to
 275    //!   will return a valid iterator.
 276    //!
 277    //! <b>Complexity</b>: Constant
 278    bool is_linked() const;
 279
 280    //! <b>Effects</b>: Removes the node if it's inserted in a container.
 281    //!   This function is only allowed if link_mode is \c auto_unlink.
 282    //!
 283    //! <b>Throws</b>: Nothing.
 284    void unlink();
 285    #endif
 286 };
 287
 288 } //namespace intrusive
 289 } //namespace boost
 290
 291 #include <boost/intrusive/detail/config_end.hpp>
 292
 293 #endif //BOOST_INTRUSIVE_AVL_SET_HOOK_HPP