intrusive/detail/avltree_node.hpp

0001 /////////////////////////////////////////////////////////////////////////////
0002 //
0003 // (C) Copyright Ion Gaztanaga 2007-2013
0004 //
0005 // Distributed under the Boost Software License, Version 1.0.
0006 //    (See accompanying file LICENSE_1_0.txt or copy at
0007 //          http://www.boost.org/LICENSE_1_0.txt)
0008 //
0009 // See http://www.boost.org/libs/intrusive for documentation.
0010 //
0011 /////////////////////////////////////////////////////////////////////////////
0012
0013 #ifndef BOOST_INTRUSIVE_AVLTREE_NODE_HPP
0014 #define BOOST_INTRUSIVE_AVLTREE_NODE_HPP
0015
0016 #ifndef BOOST_CONFIG_HPP
0017 #  include <boost/config.hpp>
0018 #endif
0019
0020 #if defined(BOOST_HAS_PRAGMA_ONCE)
0021 #  pragma once
0022 #endif
0023
0024 #include <boost/intrusive/detail/config_begin.hpp>
0025 #include <boost/intrusive/detail/workaround.hpp>
0026 #include <boost/intrusive/pointer_rebind.hpp>
0027 #include <boost/intrusive/avltree_algorithms.hpp>
0028 #include <boost/intrusive/pointer_plus_bits.hpp>
0029 #include <boost/intrusive/detail/mpl.hpp>
0030
0031 namespace boost {
0032 namespace intrusive {
0033
0034 /////////////////////////////////////////////////////////////////////////////
0035 //                                                                         //
0036 //                Generic node_traits for any pointer type                 //
0037 //                                                                         //
0038 /////////////////////////////////////////////////////////////////////////////
0039
0040 //This is the compact representation: 3 pointers
0041 template<class VoidPointer>
0042 struct compact_avltree_node
0043 {
0044    typedef typename pointer_rebind<VoidPointer, compact_avltree_node<VoidPointer> >::type       node_ptr;
0045    typedef typename pointer_rebind<VoidPointer, const compact_avltree_node<VoidPointer> >::type const_node_ptr;
0046    enum balance { negative_t, zero_t, positive_t };
0047    node_ptr parent_, left_, right_;
0048 };
0049
0050 //This is the normal representation: 3 pointers + enum
0051 template<class VoidPointer>
0052 struct avltree_node
0053 {
0054    typedef typename pointer_rebind<VoidPointer, avltree_node<VoidPointer> >::type         node_ptr;
0055    typedef typename pointer_rebind<VoidPointer, const avltree_node<VoidPointer> >::type   const_node_ptr;
0056    enum balance { negative_t, zero_t, positive_t };
0057    node_ptr parent_, left_, right_;
0058    balance balance_;
0059 };
0060
0061 //This is the default node traits implementation
0062 //using a node with 3 generic pointers plus an enum
0063 template<class VoidPointer>
0064 struct default_avltree_node_traits_impl
0065 {
0066    typedef avltree_node<VoidPointer>      node;
0067    typedef typename node::node_ptr        node_ptr;
0068    typedef typename node::const_node_ptr  const_node_ptr;
0069
0070    typedef typename node::balance balance;
0071
0072    BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const_node_ptr n)
0073    {  return n->parent_;  }
0074
0075    BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(node_ptr n)
0076    {  return n->parent_;  }
0077
0078    BOOST_INTRUSIVE_FORCEINLINE static void set_parent(node_ptr n, node_ptr p)
0079    {  n->parent_ = p;  }
0080
0081    BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const_node_ptr n)
0082    {  return n->left_;  }
0083
0084    BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(node_ptr n)
0085    {  return n->left_;  }
0086
0087    BOOST_INTRUSIVE_FORCEINLINE static void set_left(node_ptr n, node_ptr l)
0088    {  n->left_ = l;  }
0089
0090    BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const_node_ptr n)
0091    {  return n->right_;  }
0092
0093    BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(node_ptr n)
0094    {  return n->right_;  }
0095
0096    BOOST_INTRUSIVE_FORCEINLINE static void set_right(node_ptr n, node_ptr r)
0097    {  n->right_ = r;  }
0098
0099    BOOST_INTRUSIVE_FORCEINLINE static balance get_balance(const_node_ptr n)
0100    {  return n->balance_;  }
0101
0102    BOOST_INTRUSIVE_FORCEINLINE static balance get_balance(node_ptr n)
0103    {  return n->balance_;  }
0104
0105    BOOST_INTRUSIVE_FORCEINLINE static void set_balance(node_ptr n, balance b)
0106    {  n->balance_ = b;  }
0107
0108    BOOST_INTRUSIVE_FORCEINLINE static balance negative()
0109    {  return node::negative_t;  }
0110
0111    BOOST_INTRUSIVE_FORCEINLINE static balance zero()
0112    {  return node::zero_t;  }
0113
0114    BOOST_INTRUSIVE_FORCEINLINE static balance positive()
0115    {  return node::positive_t;  }
0116 };
0117
0118 //This is the compact node traits implementation
0119 //using a node with 3 generic pointers
0120 template<class VoidPointer>
0121 struct compact_avltree_node_traits_impl
0122 {
0123    typedef compact_avltree_node<VoidPointer> node;
0124    typedef typename node::node_ptr           node_ptr;
0125    typedef typename node::const_node_ptr     const_node_ptr;
0126    typedef typename node::balance balance;
0127
0128    typedef pointer_plus_bits<node_ptr, 2> ptr_bit;
0129
0130    BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const_node_ptr n)
0131    {  return ptr_bit::get_pointer(n->parent_);  }
0132
0133    BOOST_INTRUSIVE_FORCEINLINE static void set_parent(node_ptr n, node_ptr p)
0134    {  ptr_bit::set_pointer(n->parent_, p);  }
0135
0136    BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const_node_ptr n)
0137    {  return n->left_;  }
0138
0139    BOOST_INTRUSIVE_FORCEINLINE static void set_left(node_ptr n, node_ptr l)
0140    {  n->left_ = l;  }
0141
0142    BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const_node_ptr n)
0143    {  return n->right_;  }
0144
0145    BOOST_INTRUSIVE_FORCEINLINE static void set_right(node_ptr n, node_ptr r)
0146    {  n->right_ = r;  }
0147
0148    BOOST_INTRUSIVE_FORCEINLINE static balance get_balance(const_node_ptr n)
0149    {  return (balance)ptr_bit::get_bits(n->parent_);  }
0150
0151    BOOST_INTRUSIVE_FORCEINLINE static void set_balance(node_ptr n, balance b)
0152    {  ptr_bit::set_bits(n->parent_, (std::size_t)b);  }
0153
0154    BOOST_INTRUSIVE_FORCEINLINE static balance negative()
0155    {  return node::negative_t;  }
0156
0157    BOOST_INTRUSIVE_FORCEINLINE static balance zero()
0158    {  return node::zero_t;  }
0159
0160    BOOST_INTRUSIVE_FORCEINLINE static balance positive()
0161    {  return node::positive_t;  }
0162 };
0163
0164 //Dispatches the implementation based on the boolean
0165 template<class VoidPointer, bool Compact>
0166 struct avltree_node_traits_dispatch
0167    :  public default_avltree_node_traits_impl<VoidPointer>
0168 {};
0169
0170 template<class VoidPointer>
0171 struct avltree_node_traits_dispatch<VoidPointer, true>
0172    :  public compact_avltree_node_traits_impl<VoidPointer>
0173 {};
0174
0175 //Inherit from rbtree_node_traits_dispatch depending on the embedding capabilities
0176 template<class VoidPointer, bool OptimizeSize = false>
0177 struct avltree_node_traits
0178    :  public avltree_node_traits_dispatch
0179          < VoidPointer
0180          , OptimizeSize &&
0181             max_pointer_plus_bits
0182             < VoidPointer
0183             , detail::alignment_of<compact_avltree_node<VoidPointer> >::value
0184             >::value >= 2u
0185          >
0186 {};
0187
0188 } //namespace intrusive
0189 } //namespace boost
0190
0191 #include <boost/intrusive/detail/config_end.hpp>
0192
0193 #endif //BOOST_INTRUSIVE_AVLTREE_NODE_HPP