ceph/src/boost/libs/intrusive/include/boost/intrusive/detail/any_node_and_algorithms.hpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga  2006-2014
   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_ANY_NODE_HPP
  14 #define BOOST_INTRUSIVE_ANY_NODE_HPP
  15
  16 #ifndef BOOST_CONFIG_HPP
  17 #  include <boost/config.hpp>
  18 #endif
  19
  20 #if defined(BOOST_HAS_PRAGMA_ONCE)
  21 #  pragma once
  22 #endif
  23
  24 #include <boost/intrusive/detail/workaround.hpp>
  25 #include <boost/intrusive/pointer_rebind.hpp>
  26 #include <boost/intrusive/detail/mpl.hpp>
  27 #include <boost/intrusive/detail/algo_type.hpp>
  28 #include <cstddef>
  29
  30 namespace boost {
  31 namespace intrusive {
  32
  33 template<class VoidPointer>
  34 struct any_node
  35 {
  36    typedef any_node                                               node;
  37    typedef typename pointer_rebind<VoidPointer, node>::type       node_ptr;
  38    typedef typename pointer_rebind<VoidPointer, const node>::type const_node_ptr;
  39    node_ptr    node_ptr_1;
  40    node_ptr    node_ptr_2;
  41    node_ptr    node_ptr_3;
  42    std::size_t size_t_1;
  43 };
  44
  45 template<class VoidPointer>
  46 struct any_list_node_traits
  47 {
  48    typedef any_node<VoidPointer>          node;
  49    typedef typename node::node_ptr        node_ptr;
  50    typedef typename node::const_node_ptr  const_node_ptr;
  51
  52    BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_next(const const_node_ptr & n)
  53    {  return n->node_ptr_1;  }
  54
  55    BOOST_INTRUSIVE_FORCEINLINE static void set_next(const node_ptr & n, const node_ptr & next)
  56    {  n->node_ptr_1 = next;  }
  57
  58    BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_previous(const const_node_ptr & n)
  59    {  return n->node_ptr_2;  }
  60
  61    BOOST_INTRUSIVE_FORCEINLINE static void set_previous(const node_ptr & n, const node_ptr & prev)
  62    {  n->node_ptr_2 = prev;  }
  63 };
  64
  65
  66 template<class VoidPointer>
  67 struct any_slist_node_traits
  68 {
  69    typedef any_node<VoidPointer>          node;
  70    typedef typename node::node_ptr        node_ptr;
  71    typedef typename node::const_node_ptr  const_node_ptr;
  72
  73    BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_next(const const_node_ptr & n)
  74    {  return n->node_ptr_1;  }
  75
  76    BOOST_INTRUSIVE_FORCEINLINE static void set_next(const node_ptr & n, const node_ptr & next)
  77    {  n->node_ptr_1 = next;  }
  78 };
  79
  80
  81 template<class VoidPointer>
  82 struct any_unordered_node_traits
  83    :  public any_slist_node_traits<VoidPointer>
  84 {
  85    typedef any_slist_node_traits<VoidPointer>                  reduced_slist_node_traits;
  86    typedef typename reduced_slist_node_traits::node            node;
  87    typedef typename reduced_slist_node_traits::node_ptr        node_ptr;
  88    typedef typename reduced_slist_node_traits::const_node_ptr  const_node_ptr;
  89
  90    static const bool store_hash        = true;
  91    static const bool optimize_multikey = true;
  92
  93    BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_next(const const_node_ptr & n)
  94    {  return n->node_ptr_1;   }
  95
  96    BOOST_INTRUSIVE_FORCEINLINE static void set_next(const node_ptr & n, const node_ptr & next)
  97    {  n->node_ptr_1 = next;  }
  98
  99    BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_prev_in_group(const const_node_ptr & n)
 100    {  return n->node_ptr_2;  }
 101
 102    BOOST_INTRUSIVE_FORCEINLINE static void set_prev_in_group(const node_ptr & n, const node_ptr & prev)
 103    {  n->node_ptr_2 = prev;  }
 104
 105    BOOST_INTRUSIVE_FORCEINLINE static std::size_t get_hash(const const_node_ptr & n)
 106    {  return n->size_t_1;  }
 107
 108    BOOST_INTRUSIVE_FORCEINLINE static void set_hash(const node_ptr & n, std::size_t h)
 109    {  n->size_t_1 = h;  }
 110 };
 111
 112
 113 template<class VoidPointer>
 114 struct any_rbtree_node_traits
 115 {
 116    typedef any_node<VoidPointer>          node;
 117    typedef typename node::node_ptr        node_ptr;
 118    typedef typename node::const_node_ptr  const_node_ptr;
 119
 120    typedef std::size_t color;
 121
 122    BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const const_node_ptr & n)
 123    {  return n->node_ptr_1;  }
 124
 125    BOOST_INTRUSIVE_FORCEINLINE static void set_parent(const node_ptr & n, const node_ptr & p)
 126    {  n->node_ptr_1 = p;  }
 127
 128    BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const const_node_ptr & n)
 129    {  return n->node_ptr_2;  }
 130
 131    BOOST_INTRUSIVE_FORCEINLINE static void set_left(const node_ptr & n, const node_ptr & l)
 132    {  n->node_ptr_2 = l;  }
 133
 134    BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const const_node_ptr & n)
 135    {  return n->node_ptr_3;  }
 136
 137    BOOST_INTRUSIVE_FORCEINLINE static void set_right(const node_ptr & n, const node_ptr & r)
 138    {  n->node_ptr_3 = r;  }
 139
 140    BOOST_INTRUSIVE_FORCEINLINE static color get_color(const const_node_ptr & n)
 141    {  return n->size_t_1;  }
 142
 143    BOOST_INTRUSIVE_FORCEINLINE static void set_color(const node_ptr & n, color c)
 144    {  n->size_t_1 = c;  }
 145
 146    BOOST_INTRUSIVE_FORCEINLINE static color black()
 147    {  return 0u;  }
 148
 149    BOOST_INTRUSIVE_FORCEINLINE static color red()
 150    {  return 1u;  }
 151 };
 152
 153
 154 template<class VoidPointer>
 155 struct any_avltree_node_traits
 156 {
 157    typedef any_node<VoidPointer>          node;
 158    typedef typename node::node_ptr        node_ptr;
 159    typedef typename node::const_node_ptr  const_node_ptr;
 160
 161    typedef std::size_t balance;
 162
 163    BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const const_node_ptr & n)
 164    {  return n->node_ptr_1;  }
 165
 166    BOOST_INTRUSIVE_FORCEINLINE static void set_parent(const node_ptr & n, const node_ptr & p)
 167    {  n->node_ptr_1 = p;  }
 168
 169    BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const const_node_ptr & n)
 170    {  return n->node_ptr_2;  }
 171
 172    BOOST_INTRUSIVE_FORCEINLINE static void set_left(const node_ptr & n, const node_ptr & l)
 173    {  n->node_ptr_2 = l;  }
 174
 175    BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const const_node_ptr & n)
 176    {  return n->node_ptr_3;  }
 177
 178    BOOST_INTRUSIVE_FORCEINLINE static void set_right(const node_ptr & n, const node_ptr & r)
 179    {  n->node_ptr_3 = r;  }
 180
 181    BOOST_INTRUSIVE_FORCEINLINE static balance get_balance(const const_node_ptr & n)
 182    {  return n->size_t_1;  }
 183
 184    BOOST_INTRUSIVE_FORCEINLINE static void set_balance(const node_ptr & n, balance b)
 185    {  n->size_t_1 = b;  }
 186
 187    BOOST_INTRUSIVE_FORCEINLINE static balance negative()
 188    {  return 0u;  }
 189
 190    BOOST_INTRUSIVE_FORCEINLINE static balance zero()
 191    {  return 1u;  }
 192
 193    BOOST_INTRUSIVE_FORCEINLINE static balance positive()
 194    {  return 2u;  }
 195 };
 196
 197
 198 template<class VoidPointer>
 199 struct any_tree_node_traits
 200 {
 201    typedef any_node<VoidPointer>          node;
 202    typedef typename node::node_ptr        node_ptr;
 203    typedef typename node::const_node_ptr  const_node_ptr;
 204
 205    BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const const_node_ptr & n)
 206    {  return n->node_ptr_1;  }
 207
 208    BOOST_INTRUSIVE_FORCEINLINE static void set_parent(const node_ptr & n, const node_ptr & p)
 209    {  n->node_ptr_1 = p;  }
 210
 211    BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const const_node_ptr & n)
 212    {  return n->node_ptr_2;  }
 213
 214    BOOST_INTRUSIVE_FORCEINLINE static void set_left(const node_ptr & n, const node_ptr & l)
 215    {  n->node_ptr_2 = l;  }
 216
 217    BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const const_node_ptr & n)
 218    {  return n->node_ptr_3;  }
 219
 220    BOOST_INTRUSIVE_FORCEINLINE static void set_right(const node_ptr & n, const node_ptr & r)
 221    {  n->node_ptr_3 = r;  }
 222 };
 223
 224 template<class VoidPointer>
 225 class any_node_traits
 226 {
 227    public:
 228    typedef any_node<VoidPointer>          node;
 229    typedef typename node::node_ptr        node_ptr;
 230    typedef typename node::const_node_ptr  const_node_ptr;
 231 };
 232
 233 template<class VoidPointer>
 234 class any_algorithms
 235 {
 236    template <class T>
 237    static void function_not_available_for_any_hooks(typename detail::enable_if<detail::is_same<T, bool> >::type)
 238    {}
 239
 240    public:
 241    typedef any_node<VoidPointer>          node;
 242    typedef typename node::node_ptr        node_ptr;
 243    typedef typename node::const_node_ptr  const_node_ptr;
 244    typedef any_node_traits<VoidPointer>   node_traits;
 245
 246    //! <b>Requires</b>: node must not be part of any tree.
 247    //!
 248    //! <b>Effects</b>: After the function unique(node) == true.
 249    //!
 250    //! <b>Complexity</b>: Constant.
 251    //!
 252    //! <b>Throws</b>: Nothing.
 253    //!
 254    //! <b>Nodes</b>: If node is inserted in a tree, this function corrupts the tree.
 255    BOOST_INTRUSIVE_FORCEINLINE static void init(const node_ptr & node)
 256    {  node->node_ptr_1 = node_ptr();   };
 257
 258    //! <b>Effects</b>: Returns true if node is in the same state as if called init(node)
 259    //!
 260    //! <b>Complexity</b>: Constant.
 261    //!
 262    //! <b>Throws</b>: Nothing.
 263    BOOST_INTRUSIVE_FORCEINLINE static bool inited(const const_node_ptr & node)
 264    {  return !node->node_ptr_1;  };
 265
 266    BOOST_INTRUSIVE_FORCEINLINE static bool unique(const const_node_ptr & node)
 267    {  return !node->node_ptr_1; }
 268
 269    static void unlink(const node_ptr &)
 270    {
 271       //Auto-unlink hooks and unlink() are not available for any hooks
 272       any_algorithms<VoidPointer>::template function_not_available_for_any_hooks<node_ptr>();
 273    }
 274
 275    static void swap_nodes(const node_ptr &, const node_ptr &)
 276    {
 277       //Any nodes have no swap_nodes capability because they don't know
 278       //what algorithm they must use to unlink the node from the container
 279       any_algorithms<VoidPointer>::template function_not_available_for_any_hooks<node_ptr>();
 280    }
 281 };
 282
 283 ///@cond
 284
 285 template<class NodeTraits>
 286 struct get_algo<AnyAlgorithm, NodeTraits>
 287 {
 288    typedef typename pointer_rebind<typename NodeTraits::node_ptr, void>::type void_pointer;
 289    typedef any_algorithms<void_pointer> type;
 290 };
 291
 292 ///@endcond
 293
 294 } //namespace intrusive
 295 } //namespace boost
 296
 297 #endif //BOOST_INTRUSIVE_ANY_NODE_HPP