ceph/src/boost/boost/intrusive/detail/avltree_node.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_AVLTREE_NODE_HPP
  14 #define BOOST_INTRUSIVE_AVLTREE_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/config_begin.hpp>
  25 #include <boost/intrusive/detail/workaround.hpp>
  26 #include <boost/intrusive/pointer_rebind.hpp>
  27 #include <boost/intrusive/avltree_algorithms.hpp>
  28 #include <boost/intrusive/pointer_plus_bits.hpp>
  29 #include <boost/intrusive/detail/mpl.hpp>
  30
  31 namespace boost {
  32 namespace intrusive {
  33
  34 /////////////////////////////////////////////////////////////////////////////
  35 //                                                                         //
  36 //                Generic node_traits for any pointer type                 //
  37 //                                                                         //
  38 /////////////////////////////////////////////////////////////////////////////
  39
  40 //This is the compact representation: 3 pointers
  41 template<class VoidPointer>
  42 struct compact_avltree_node
  43 {
  44    typedef typename pointer_rebind<VoidPointer, compact_avltree_node<VoidPointer> >::type       node_ptr;
  45    typedef typename pointer_rebind<VoidPointer, const compact_avltree_node<VoidPointer> >::type const_node_ptr;
  46    enum balance { negative_t, zero_t, positive_t };
  47    node_ptr parent_, left_, right_;
  48 };
  49
  50 //This is the normal representation: 3 pointers + enum
  51 template<class VoidPointer>
  52 struct avltree_node
  53 {
  54    typedef typename pointer_rebind<VoidPointer, avltree_node<VoidPointer> >::type         node_ptr;
  55    typedef typename pointer_rebind<VoidPointer, const avltree_node<VoidPointer> >::type   const_node_ptr;
  56    enum balance { negative_t, zero_t, positive_t };
  57    node_ptr parent_, left_, right_;
  58    balance balance_;
  59 };
  60
  61 //This is the default node traits implementation
  62 //using a node with 3 generic pointers plus an enum
  63 template<class VoidPointer>
  64 struct default_avltree_node_traits_impl
  65 {
  66    typedef avltree_node<VoidPointer> node;
  67    typedef typename node::node_ptr        node_ptr;
  68    typedef typename node::const_node_ptr  const_node_ptr;
  69
  70    typedef typename node::balance balance;
  71
  72    BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const const_node_ptr & n)
  73    {  return n->parent_;  }
  74
  75    BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const node_ptr & n)
  76    {  return n->parent_;  }
  77
  78    BOOST_INTRUSIVE_FORCEINLINE static void set_parent(const node_ptr & n, const node_ptr & p)
  79    {  n->parent_ = p;  }
  80
  81    BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const const_node_ptr & n)
  82    {  return n->left_;  }
  83
  84    BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const node_ptr & n)
  85    {  return n->left_;  }
  86
  87    BOOST_INTRUSIVE_FORCEINLINE static void set_left(const node_ptr & n, const node_ptr & l)
  88    {  n->left_ = l;  }
  89
  90    BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const const_node_ptr & n)
  91    {  return n->right_;  }
  92
  93    BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const node_ptr & n)
  94    {  return n->right_;  }
  95
  96    BOOST_INTRUSIVE_FORCEINLINE static void set_right(const node_ptr & n, const node_ptr & r)
  97    {  n->right_ = r;  }
  98
  99    BOOST_INTRUSIVE_FORCEINLINE static balance get_balance(const const_node_ptr & n)
 100    {  return n->balance_;  }
 101
 102    BOOST_INTRUSIVE_FORCEINLINE static balance get_balance(const node_ptr & n)
 103    {  return n->balance_;  }
 104
 105    BOOST_INTRUSIVE_FORCEINLINE static void set_balance(const node_ptr & n, balance b)
 106    {  n->balance_ = b;  }
 107
 108    BOOST_INTRUSIVE_FORCEINLINE static balance negative()
 109    {  return node::negative_t;  }
 110
 111    BOOST_INTRUSIVE_FORCEINLINE static balance zero()
 112    {  return node::zero_t;  }
 113
 114    BOOST_INTRUSIVE_FORCEINLINE static balance positive()
 115    {  return node::positive_t;  }
 116 };
 117
 118 //This is the compact node traits implementation
 119 //using a node with 3 generic pointers
 120 template<class VoidPointer>
 121 struct compact_avltree_node_traits_impl
 122 {
 123    typedef compact_avltree_node<VoidPointer> node;
 124    typedef typename node::node_ptr        node_ptr;
 125    typedef typename node::const_node_ptr  const_node_ptr;
 126    typedef typename node::balance balance;
 127
 128    typedef pointer_plus_bits<node_ptr, 2> ptr_bit;
 129
 130    BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const const_node_ptr & n)
 131    {  return ptr_bit::get_pointer(n->parent_);  }
 132
 133    BOOST_INTRUSIVE_FORCEINLINE static void set_parent(const node_ptr & n, const node_ptr & p)
 134    {  ptr_bit::set_pointer(n->parent_, p);  }
 135
 136    BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const const_node_ptr & n)
 137    {  return n->left_;  }
 138
 139    BOOST_INTRUSIVE_FORCEINLINE static void set_left(const node_ptr & n, const node_ptr & l)
 140    {  n->left_ = l;  }
 141
 142    BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const const_node_ptr & n)
 143    {  return n->right_;  }
 144
 145    BOOST_INTRUSIVE_FORCEINLINE static void set_right(const node_ptr & n, const node_ptr & r)
 146    {  n->right_ = r;  }
 147
 148    BOOST_INTRUSIVE_FORCEINLINE static balance get_balance(const const_node_ptr & n)
 149    {  return (balance)ptr_bit::get_bits(n->parent_);  }
 150
 151    BOOST_INTRUSIVE_FORCEINLINE static void set_balance(const node_ptr & n, balance b)
 152    {  ptr_bit::set_bits(n->parent_, (std::size_t)b);  }
 153
 154    BOOST_INTRUSIVE_FORCEINLINE static balance negative()
 155    {  return node::negative_t;  }
 156
 157    BOOST_INTRUSIVE_FORCEINLINE static balance zero()
 158    {  return node::zero_t;  }
 159
 160    BOOST_INTRUSIVE_FORCEINLINE static balance positive()
 161    {  return node::positive_t;  }
 162 };
 163
 164 //Dispatches the implementation based on the boolean
 165 template<class VoidPointer, bool Compact>
 166 struct avltree_node_traits_dispatch
 167    :  public default_avltree_node_traits_impl<VoidPointer>
 168 {};
 169
 170 template<class VoidPointer>
 171 struct avltree_node_traits_dispatch<VoidPointer, true>
 172    :  public compact_avltree_node_traits_impl<VoidPointer>
 173 {};
 174
 175 //Inherit from rbtree_node_traits_dispatch depending on the embedding capabilities
 176 template<class VoidPointer, bool OptimizeSize = false>
 177 struct avltree_node_traits
 178    :  public avltree_node_traits_dispatch
 179          < VoidPointer
 180          , OptimizeSize &&
 181             max_pointer_plus_bits
 182             < VoidPointer
 183             , detail::alignment_of<compact_avltree_node<VoidPointer> >::value
 184             >::value >= 2u
 185          >
 186 {};
 187
 188 } //namespace intrusive
 189 } //namespace boost
 190
 191 #include <boost/intrusive/detail/config_end.hpp>
 192
 193 #endif //BOOST_INTRUSIVE_AVLTREE_NODE_HPP