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 get_parentboost::intrusive::default_avltree_node_traits_impl72 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const const_node_ptr & n) 73 { return n->parent_; } 74 get_parentboost::intrusive::default_avltree_node_traits_impl75 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const node_ptr & n) 76 { return n->parent_; } 77 set_parentboost::intrusive::default_avltree_node_traits_impl78 BOOST_INTRUSIVE_FORCEINLINE static void set_parent(node_ptr n, node_ptr p) 79 { n->parent_ = p; } 80 get_leftboost::intrusive::default_avltree_node_traits_impl81 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const const_node_ptr & n) 82 { return n->left_; } 83 get_leftboost::intrusive::default_avltree_node_traits_impl84 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const node_ptr & n) 85 { return n->left_; } 86 set_leftboost::intrusive::default_avltree_node_traits_impl87 BOOST_INTRUSIVE_FORCEINLINE static void set_left(node_ptr n, node_ptr l) 88 { n->left_ = l; } 89 get_rightboost::intrusive::default_avltree_node_traits_impl90 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const const_node_ptr & n) 91 { return n->right_; } 92 get_rightboost::intrusive::default_avltree_node_traits_impl93 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const node_ptr & n) 94 { return n->right_; } 95 set_rightboost::intrusive::default_avltree_node_traits_impl96 BOOST_INTRUSIVE_FORCEINLINE static void set_right(node_ptr n, node_ptr r) 97 { n->right_ = r; } 98 get_balanceboost::intrusive::default_avltree_node_traits_impl99 BOOST_INTRUSIVE_FORCEINLINE static balance get_balance(const const_node_ptr & n) 100 { return n->balance_; } 101 get_balanceboost::intrusive::default_avltree_node_traits_impl102 BOOST_INTRUSIVE_FORCEINLINE static balance get_balance(const node_ptr & n) 103 { return n->balance_; } 104 set_balanceboost::intrusive::default_avltree_node_traits_impl105 BOOST_INTRUSIVE_FORCEINLINE static void set_balance(const node_ptr & n, balance b) 106 { n->balance_ = b; } 107 negativeboost::intrusive::default_avltree_node_traits_impl108 BOOST_INTRUSIVE_FORCEINLINE static balance negative() 109 { return node::negative_t; } 110 zeroboost::intrusive::default_avltree_node_traits_impl111 BOOST_INTRUSIVE_FORCEINLINE static balance zero() 112 { return node::zero_t; } 113 positiveboost::intrusive::default_avltree_node_traits_impl114 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 get_parentboost::intrusive::compact_avltree_node_traits_impl130 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const const_node_ptr & n) 131 { return ptr_bit::get_pointer(n->parent_); } 132 set_parentboost::intrusive::compact_avltree_node_traits_impl133 BOOST_INTRUSIVE_FORCEINLINE static void set_parent(node_ptr n, node_ptr p) 134 { ptr_bit::set_pointer(n->parent_, p); } 135 get_leftboost::intrusive::compact_avltree_node_traits_impl136 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const const_node_ptr & n) 137 { return n->left_; } 138 set_leftboost::intrusive::compact_avltree_node_traits_impl139 BOOST_INTRUSIVE_FORCEINLINE static void set_left(node_ptr n, node_ptr l) 140 { n->left_ = l; } 141 get_rightboost::intrusive::compact_avltree_node_traits_impl142 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const const_node_ptr & n) 143 { return n->right_; } 144 set_rightboost::intrusive::compact_avltree_node_traits_impl145 BOOST_INTRUSIVE_FORCEINLINE static void set_right(node_ptr n, node_ptr r) 146 { n->right_ = r; } 147 get_balanceboost::intrusive::compact_avltree_node_traits_impl148 BOOST_INTRUSIVE_FORCEINLINE static balance get_balance(const const_node_ptr & n) 149 { return (balance)ptr_bit::get_bits(n->parent_); } 150 set_balanceboost::intrusive::compact_avltree_node_traits_impl151 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 negativeboost::intrusive::compact_avltree_node_traits_impl154 BOOST_INTRUSIVE_FORCEINLINE static balance negative() 155 { return node::negative_t; } 156 zeroboost::intrusive::compact_avltree_node_traits_impl157 BOOST_INTRUSIVE_FORCEINLINE static balance zero() 158 { return node::zero_t; } 159 positiveboost::intrusive::compact_avltree_node_traits_impl160 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 194